算法与数据结构实验报告实验四

算法与数据结构实验报告

实验四

实验名称：模式匹配算法KMP 姓名：卢丽娟

学号： 211006289

专业：软件专业

班级：二班

指导教师：陈亦萍

日期: 2012年5月5日

1、实验目的

本实验是要利用模式匹配算法KMP来实现串的应用。

2、实验内容与实验步骤

构建一主串和一子串，采用定长存储结构实现，调用KMP算法，测试不同的输入数据，查看其结果，要做到能够输出模式串的next的值，以及模式串在主串中的定位函数值。

步骤如下：

1. 初始化字符串

void InitString(HString &T)

{ // 初始化(产生空串)字符串T

T.length=0;T.ch=NULL;}//InitString

2.int StrAssign(HString &T,char *chars)

{// 生成一个其值等于串常量chars的串T

int i,j;

if(T.ch) free(T.ch); //释放T原有空间

i=strlen(chars);//求chars的长度i

if(!i)

{//chars的长度为0

T.ch=NULL; T.length=0; }//if

else

{ T.ch=(char*)malloc(i*sizeof(char));//分配串空间 if(!T.ch) exit(-1); //失败

for(j=0;j

return OK;}//StrAssign

3.输出字符串

void StrPrint(HString &T)

{ int i;

for(i=0;i

printf("%c",T.ch[i]);printf("\n");}//StrPrint

4.求出模式串T的next函数值

void get_next(HString T,int next[])

{ // 求模式串T的next函数修正值并存入数组next

int i=0,j=-1; next[0]=-1;

while(i

{ if(j==-1||T.ch[i]==T.ch[j])

{ ++i; ++j; next[i]=j;}//if

else j=next[j];}

printf("模式串T的next[]的值为:\n");

for(j=0;j

printf("%d",next[j]+1);}//get_next

5. 求出模式串在主串中的定位函数值

int Index_KMP(HString S,HString T,int pos,int next[])

{ // 利用模式串T的next函数求T在主串S中第pos个字符之后的位置的KMP算法。

// 其中,T非空,1≤pos≤StrLength(S)

int i=pos,j=0;

while(i

if(j==-1||S.ch[i]==T.ch[j]) // 继续比较后继字符

{ ++i;++j;}

else // 模式串向右移动 j=next[j];

if(j>=T.length) // 匹配成功 return i-T.length;

else return 0; }//Index_KMP

6.输入函数

void InputS(HString &s)

{ char ch[80];

printf("输入主串s:\n");scanf("%s",ch);StrAssign(s,ch);}

7.输入模式串

void PrintfS(HString &t)

{ char ch[90];

printf("输入模式串

t:\n");scanf("%s",ch);StrAssign(t,ch);}//InputS

8.主函数，调用以上函数来实现实验，得出结果。

3、实验环境

操作系统windows XP、开发平台:Microsoft Visual C++ 6.0

4、实验过程与分析

主要是在get_next函数中，i和j的初始值有些不对，导致输出模式串的next[]的值是错误的，还有就是没有判断模式匹配失败的情况，经过反复修改，才发现了错误，并改正。

5、实验结论

测试的数据、输出的结果如下：

(1)输入主串s:

ababcabcaabcbaabc

输入模式串t:

aabc

模式串T的next[]的值为:

0121

结果:

在主串位置9匹配

(2)输入主串s:

aabbcaabadddd

输入模式串t:

adc

模式串T的next[]的值为:

011

结果:

模式匹配失败

6、附录

#include"stdio.h"

#include"stdlib.h"

#include"string.h"

#include"ctype.h"

#define OK 1

#define ERROR 0

typedef intStatus; // Status是函数的类型,其值是函数结果状态代码，如OK等

typedef intBoolean; // Boolean是布尔类型,其值是TRUE或false #define N 16 // 数据元素个数

#define MAXKEYLEN16 // 关键字的最大长度

#define STACK_INIT_SIZE 10 // 存储空间初始分配量

#define STACKINCREMENT 2 // 存储空间分配增量

typedef struct

{ char *ch;int length;}HString;

void InitString(HString &T)

{ // 初始化(产生空串)字符串T

T.length=0;T.ch=NULL;}//InitString

int StrAssign(HString &T,char *chars)

{// 生成一个其值等于串常量chars的串T

int i,j;

if(T.ch) free(T.ch); //释放T原有空间

i=strlen(chars);//求chars的长度i

if(!i)

{//chars的长度为0

T.ch=NULL; T.length=0; }//if

else

{ T.ch=(char*)malloc(i*sizeof(char));//分配串空间

if(!T.ch) exit(-1); //失败

for(j=0;j

void StrPrint(HString &T)

{ int i;

for(i=0;i

printf("%c",T.ch[i]);printf("\n");}//StrPrint

void get_next(HString T,int next[])

{ // 求模式串T的next函数修正值并存入数组next

int i=0,j=-1; next[0]=-1;

while(i

{ if(j==-1||T.ch[i]==T.ch[j])

{ ++i; ++j; next[i]=j;}//if

else j=next[j];}

printf("模式串T的next[]的值为:\n");

for(j=0;j

printf("%d",next[j]+1);}//get_next

int Index_KMP(HString S,HString T,int pos,int next[])

{ // 利用模式串T的next函数求T在主串S中第pos个字符之后的位置的KMP算法。

// 其中,T非空,1≤pos≤StrLength(S)

int i=pos,j=0;

while(i

if(j==-1||S.ch[i]==T.ch[j]) // 继续比较后继字符

{ ++i;++j;}

else // 模式串向右移动 j=next[j];

if(j>=T.length) // 匹配成功 return i-T.length;

else return 0; }//Index_KMP

void InputS(HString &s)

{ char ch[80];

printf("输入主串s:\n");scanf("%s",ch);StrAssign(s,ch);} void PrintfS(HString &t)

{ char ch[90];

printf("输入模式串

t:\n");scanf("%s",ch);StrAssign(t,ch);}//InputS

int main()

{ int i,pos=1,p[N];HString t,s;

InitString(s);//由于HSring定义了指针，所以必须初始化

InitString(t);

InputS(s);PrintfS(t);

get_next(t,p);

i=Index_KMP(s,t,pos,p);

if(!i) printf("\n结果:\n模式匹配失败\n");

else printf("\n结果:\n在主串位置%d匹配\n",i+1);

return 1;

}

山东大学数据库第四次实验实验报告

實驗4 視圖操作 實驗目の：掌握創建、刪除視圖のSQL語句の用法，掌握使用企業管理器創建、視圖の方法。 實驗准備： 1)了解創建視圖方法。 2)了解修改視圖のSQL 語句の語法格式。 實驗內容： 1)使用企業管理器創建視圖 a)在pubs數據庫中以authors表為基礎，建立一個名為CA_authorの視圖， 使用該視圖時，將顯示所有state為CAの作者の基本信息。 2)使用SQL語句創建視圖 a)在查詢分析器中利用author表建立一個每個作者のID，lname，fname， phone，addressの視圖S_author。 b)建立一個employee_date視圖，利用employee表中信息，顯示1991年 1月1日之後雇傭の雇員のid，name，minit，job_id。 3)刪除視圖 a)使用企業管理器S_author視圖 b)使用SQL語句刪除CA_author、employee_date視圖 實驗要求： 用不同の方法創建視圖。 實驗步驟如下： 一、使用企業管理器創建視圖 a )在pubs數據庫中以authors表為基礎，建立一個名為CA_author の視圖，使用該視圖時，將顯示所有state為CAの作者の基本信息。

①右鍵點擊pubs數據庫文件下の視圖，選擇“新建視圖”，在彈出來の“添加表”中添加表authors。 ②在“添加表”一欄中添加表authors後點擊“關閉”，並全選author表中所有項目。 ③點擊保存，從彈出來の“選擇名稱”框中輸入視圖名稱“CA_author”。

④添加名為CA_author の視圖成功。 ⑤顯示所有state為CAの作者の基本信息。

数据结构与算法基础知识总结

数据结构与算法基础知识总结 1 算法 算法：是指解题方案的准确而完整的描述。 算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。 算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。特征包括： （1）可行性； （2）确定性，算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性； （3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义； （4）拥有足够的情报。 算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。 指令系统：一个计算机系统能执行的所有指令的集合。 基本运算和操作包括：算术运算、逻辑运算、关系运算、数据传输。 算法的控制结构：顺序结构、选择结构、循环结构。 算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。 算法复杂度：算法时间复杂度和算法空间复杂度。 算法时间复杂度是指执行算法所需要的计算工作量。 算法空间复杂度是指执行这个算法所需要的内存空间。 2 数据结构的基本基本概念 数据结构研究的三个方面： （1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构； （2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。 数据结构是指相互有关联的数据元素的集合。 数据的逻辑结构包含： （1）表示数据元素的信息； （2）表示各数据元素之间的前后件关系。 数据的存储结构有顺序、链接、索引等。 线性结构条件：

（1）有且只有一个根结点； （2）每一个结点最多有一个前件，也最多有一个后件。 非线性结构：不满足线性结构条件的数据结构。 3 线性表及其顺序存储结构 线性表由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。 在复杂线性表中，由若干项数据元素组成的数据元素称为记录，而由多个记录构成的线性表又称为文件。 非空线性表的结构特征： （1）且只有一个根结点a1，它无前件； （2）有且只有一个终端结点an，它无后件； （3）除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。结点个数n称为线性表的长度，当n=0时，称为空表。 线性表的顺序存储结构具有以下两个基本特点： （1）线性表中所有元素的所占的存储空间是连续的； （2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。 ai的存储地址为：adr(ai)=adr(a1)+(i-1)k,，adr(a1)为第一个元素的地址，k代表每个元素占的字节数。 顺序表的运算：插入、删除。（详见14--16页） 4 栈和队列 栈是限定在一端进行插入与删除的线性表，允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。 栈按照“先进后出”（filo）或“后进先出”（lifo）组织数据，栈具有记忆作用。用top表示栈顶位置，用bottom表示栈底。 栈的基本运算：（1）插入元素称为入栈运算；（2）删除元素称为退栈运算；（3）读栈顶元素是将栈顶元素赋给一个指定的变量，此时指针无变化。 队列是指允许在一端（队尾）进入插入，而在另一端（队头）进行删除的线性表。rear指针指向队尾，front指针指向队头。 队列是“先进行出”（fifo）或“后进后出”（lilo）的线性表。 队列运算包括（1）入队运算：从队尾插入一个元素；（2）退队运算：从队头删除一个元素。循环队列：s=0表示队列空，s=1且front=rear表示队列满

数据库实验报告

合肥工业大学实验报告一 课程名称：数据库系统原理及应用学号： 20095382 姓名：魏泽民 专业班级：电子商务09-1班 指导教师：马华伟 二零一一年十月

一、实验目的： （1）熟练掌握数据更新语句，灵活地操作插入数据、修改数据和删除数据； （2）熟练掌握关系数据库中的完整性概念的应用； （3）了解数据录入的方法和过程。 （4）掌握单表查询的基本方法； （5）掌握连接查询的基本方法； （6）熟练掌握以下练习，并进行以下各类查询： ①选择表中的若干列、查询全部列、查询经过计算的值； ②选择表中的若干元组，即消除取值重复的行与查询满足指定条件的元组（包 括：比较大小、确定范围、确定集合、字符匹配、涉及空值和多种条件查询）； ③对查询结果排序； ④使用集函数； ⑤对查询结果分组 （7）熟练掌握以下练习，并进行下列各类连接查询： ①等值与非等值连接查询； ②自身连接； ③外连接； ④复合条件连接； （8）掌握嵌套查询的基本方法； （9）掌握集合查询的基本方法； （10）熟练掌握查询视图操作 （11）熟练掌握更新视图操作 （12）熟练关系的完整性概念，领会视图的用途 （13）练习以下各类查询： ①带有IN谓词的子查询； ②带有比较运算符的子查询； ③带有ANY或ALL谓词的子查询； ④带有EXISTS谓词的子查询； ⑤视图查询与更新操作； 二、实验要求： （1）为了便于程序正确性测试，需要对自己建立起来的数据表录入一些模拟数据（模拟数据是指符合数据格式要求的假数据），然后按照教材中结构化查询语言SQL章节例题和习题自己组织SQL语句：

（2）设计的SQL程序应该涵盖数据更新操作的全部内容不，包括插入、修改、删除； （3）综合运用SQL语句实现数据插入、修改、删除等操作的综合运用能力。 （4）按照SQL语言编程要求，实现各类查询和检索操作； （5）利用后台的SQL平台环境，编程验证数据库的控制保护功能。 （6）将查询视图命令等价改写为对数据表的查询操作命令，利用SQL编程设计完成并进行效率分析。 三、实验内容： （1）根据以下给定的数据表信息分别对student, course, score, teacher, teching 表进行数据插入和修改，以完成给定的数据录入，同时要求输入班级同学名录模拟客观真实情况，给student、score表添加30条以上记录，以便以后查询应用方便。 Student表：

数据结构与算法实验指导实验十

#include"stdio.h" #include"stdlib.h" #define NULL 0 #define maxsize 50 typedef struct node{ char data; struct node *lchild,*rchild; }Bitree; int a[maxsize]; int temp=0; Bitree *Q[maxsize]; Bitree *Creatree(){ char ch; int front,rear; Bitree *T,*S; T=NULL; front=1;rear=0; printf("建立二叉树,以@表示虚节点，以#结束输入:\n"); ch=getchar(); while(ch!='#'){ S=NULL; if(ch!='@'){ //@表示虚节点不是虚节点是建立新节点 S=(Bitree *)malloc(sizeof(Bitree)); S->data=ch; S->lchild=S->rchild=NULL; } rear++;Q[rear]=S; //将虚节点指针NULL或新节点地址入队 if(rear==1) T=S; //输入第一个节点为根节点 else{ if(S!=NULL&&Q[front]!=NULL) if(rear%2==0) Q[front]->lchild=S; else Q[front]->rchild=S; if(rear%2==1) front++; //节点Q[front]的两个孩子已经处理完毕，front+1 } ch=getchar(); } return T; } void Inorder(Bitree *T){ //中序遍历二叉树，并将每个结点数据存入数组中if(T!=NULL){ Inorder(T->lchild);

数据库实验报告完整

华北电力大学 实验报告 | | 实验名称数据库实验 课程名称数据库 | | 专业班级：学生姓名： 学号：成绩： 指导教师：实验日期：2015/7/9

《数据库原理课程设计》课程设计 任务书 一、目的与要求 1.本实验是为计算机各专业的学生在学习数据库原理后，为培养更好的解决问题和实际动手能力 而设置的实践环节。通过这个环节，使学生具备应用数据库原理对数据库系统进行设计的能力。 为后继课程和毕业设计打下良好基础。 2.通过该实验，培养学生在建立数据库系统过程中使用关系数据理论的能力。 3.通过对一个数据库系统的设计，培养学生对数据库需求分析、数据库方案设计、系统编码、界 面设计和软件调试等各方面的能力。是一门考查学生数据库原理、面向对象设计方法、软件工程和信息系统分析与设计等课程的综合实验。 二、主要内容 针对一个具有实际应用场景的中小型系统（见题目附录）进行数据库设计，重点分析系统涉及的实体、实体之间的联系，实现增加、删除、更新、查询数据记录等基本操作。大致分为如下步骤： 1. 理解系统的数据库需求，分析实体及实体间联系，画出E-R图： 1）分析确定实体的属性和码，完成对该实体的实体完整性、用户自定义完整性的定义。 2）设计实体之间的联系，包括联系类型和联系的属性。最后画出完整的E-R图。 2．根据设计好的E-R图及关系数据库理论知识设计数据库模式： 1）把E-R图转换为逻辑模式； 2）规范化设计。使用关系范式理论证明所设计的关系至少属于3NF并写出证明过程；如果不属于3NF则进行模式分解，直到该关系满足3NF为止，要求写出分解过程。 3）设计关系模式间的参照完整性，要求实现级联删除和级联更新。 4）用SQL语言完成数据库内模式的设计。 3．数据库权限的设计： 1）根据系统分析，完成授权操作； 2）了解学习收回权限的操作。 4．完成用户界面的设计，对重要数据进行加密。

算法与数据结构实验

学生实验报告册 （理工类） 课程名称：算法与数据结构专业班级 学生学号：学生： 所属院部：计算机工程学院指导教师：章海鸥 2016 ——2017 学年第 1 学期 金陵科技学院教务处制 实验报告书写要求 实验报告原则上要求学生手写，要求书写工整。若因课程特点需打印的，要遵照以下字体、字号、间距等的具体要求。纸一律采用 A4的纸。

实验报告书写说明 实验报告中一至四项容为必填项，包括实验目的和要求；实验仪器和设备；实验容与过程；实验结果与分析。各院部可根据学科特点和实验具体要求增加项目。 填写注意事项 （1）细致观察，及时、准确、如实记录。 （2）准确说明，层次清晰。 （3）尽量采用专用术语来说明事物。 （4）外文、符号、公式要准确，应使用统一规定的名词和符号。 （5）应独立完成实验报告的书写，严禁抄袭、复印，一经发现，以零分论处。 实验报告批改说明 实验报告的批改要及时、认真、仔细，一律用红色笔批改。实验报告的批改成绩采用百分制，具体评分标准由各院部自行制定。 实验报告装订要求 实验批改完毕后，任课老师将每门课程的每个实验项目的实验报告以自然班为单位、按学号升序排列，装订成册，并附上一份该门课程的实验大纲。

实验项目名称：顺序表实验学时： 2 同组学生：╱实验地点： 实验日期：实验成绩： 批改教师：批改时间：

实验1 顺序表 一、实验目的和要求 掌握顺序表的定位、插入、删除等操作。 二、实验仪器和设备 VC6.0 三、实验容与过程（含程序清单及流程图） 1、必做题 （1）编写程序建立一个顺序表，并逐个输出顺序表中所有数据元素的值。 编写主函数测试结果。 （2）编写顺序表定位操作子函数，在顺序表中查找是否存在数据元素x。 如果存在，返回顺序表中和x值相等的第1个数据元素的序号（序号 从0开始编号）；如果不存在，返回－1。编写主函数测试结果。 （3）在递增有序的顺序表中插入一个新结点x，保持顺序表的有序性。 解题思路：首先查找插入的位置，再移位，最后进行插入操作；从第 一个元素开始找到第一个大于该新结点值x的元素位置i即为插入位 置；然后将从表尾开始依次将元素后移一个位置直至元素i；最后将 新结点x插入到i位置。 （4）删除顺序表中所有等于X的数据元素。 2、选做题 （5）已知两个顺序表A和B按元素值递增有序排列，要求写一算法实现将A和B归并成一个按元素值递减有序排列的顺序表（允许表中含有值 相同的元素）。 程序清单： (1) #include #define maxsize 20 typedef int datatype; typedef struct{ datatype data[maxsize];

算法与数据结构实验册

实验报告书写要求 实验报告原则上要求学生手写，要求书写工整。若因课程特点需打印的，要遵照以下字体、字号、间距等的具体要求。纸张一律采用A4的纸张。 实验报告书写说明 实验报告中一至四项内容为必填项，包括实验目的和要求；实验仪器和设备；实验内容与过程；实验结果与分析。各院部可根据学科特点和实验具体要求增加项目。 填写注意事项 （1）细致观察，及时、准确、如实记录。 （2）准确说明，层次清晰。 （3）尽量采用专用术语来说明事物。 （4）外文、符号、公式要准确，应使用统一规定的名词和符号。 （5）应独立完成实验报告的书写，严禁抄袭、复印，一经发现，以零分论处。 实验报告批改说明 实验报告的批改要及时、认真、仔细，一律用红色笔批改。实验报告的批改成绩采用百分制，具体评分标准由各院部自行制定。 实验报告装订要求 实验批改完毕后，任课老师将每门课程的每个实验项目的实验报告以自然班为单位、按学号升序排列，装订成册，并附上一份该门课 程的实验大纲。

实验项目名称：顺序表实验学时： 2 同组学生姓名：全班同学实验地点： 1318 实验日期： 10 月14号实验成绩： 批改教师：批改时间：

实验1 顺序表 一、实验目的和要求 掌握顺序表的定位、插入、删除等操作。 二、实验仪器和设备 Turbo C 2.0 三、实验内容与过程（含程序清单及流程图） 1、必做题 （1）编写程序建立一个数续表，并逐个输出顺序表中所有数据元素的值。 编写主函数测试结果。 （2）编写顺序表定位操作子函数，在顺序表中查找是否存在数据元素x。 如果存在，返回顺序表中和x值相等的第1个数据元素的序号（序号 从0开始编号）；如果不存在，返回－1。编写主函数测试结果。 （3）在递增有序的顺序表中插入一个新结点x，保持顺序表的有序性。 解题思路：首先查找插入的位置，再移位，最后进行插入操作；从第 一个元素开始找到第一个大于该新结点值x的元素位置i即为插入位 置；然后将从表尾开始依次将元素后移一个位置直至元素i；最后将新 结点x插入到i位置。 （4）删除顺序表中所有等于X的数据元素。 2、选做题 （5）已知两个顺序表A和B按元素值递增有序排列，要求写一算法实现将A和B归并成一个按元素值递减有序排列的顺序表（允许表中含有值 相同的元素）。 程序清单： 第一题： #include #define maxsize 100 typedef struct{ int datatype [maxsize]; int last; }sequenlist; void main(){ sequenlist a={{1,2,3,4},4}; for(int i=0;i

计科本科生《算法与数据结构》实验报告4

学院专业姓名学号 实验1：约瑟夫环问题（3学时） [问题描述] 将编号为1，2，…，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个开始按顺时针方向自1开始报数，报到m时停止报数。报m的人出列，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。 [实验目的] （1）掌握线性表的顺序存储结构和循环顺序存储结构。 [实验内容及要求] （1）构造数据结构。 （2）对线性表进行初始化。 [测试数据] 输入一组n，m值时，程序输出出列顺序。 [思考] （1）你采用的存储结构是顺序表还是循环顺序表？哪个比较合适？ （2）当存储结构为循环链表时，如何修改你的程序？并考虑两种存储结构的优缺点。

学院专业姓名学号 实验2：ADT List（线性表）（3学时） [问题描述] 线性表是典型的线性结构，实现ADT List，并在此基础上实现两个集合的交运算或并运算。[实验目的] （1）掌握线性表的链表存储结构。 （2）掌握在单链表上基本操作的实现。 （3）在掌握单链表的基本操作上进行综合题的实现。 [实验内容及要求] （1）要求用带头结点的单链表存储两个集合中的元素和最终的结果。 （2）集合的元素限定为十进制数，程序应对出现重复的数据进行过滤，即链表中没有重复数据。 （3）显示两个集合的内容及其运算结果。 [测试数据] （1）set1={3, 8, 5, 8,11}，set2={22, 6, 8, 3, 15,11,20 } set1∪set2＝ set1∩set2＝ （2）set1={1, 3, 5, 7}，set2={2, 3, 7, 14, 25,38} set1∪set2＝ set1∩set2＝

数据结构与算法的实验报告

数据结构与算法第二次实验报告 电子105班 赵萌 2010021526

实验二：栈和队列的定义及基本操作 一、实验目的： . 熟练掌握栈和队列的特点 . 掌握栈的定义和基本操作，熟练掌握顺序栈的操作及应用 . 掌握对列的定义和基本操作，熟练掌握链式队列的操作及应用, 掌握环形队列的入队和出队等基本操作 . 加深对栈结构和队列结构的理解，逐步培养解决实际问题的编程能力 二、实验内容: 定义顺序栈，完成栈的基本操作：空栈、入栈、出栈、取栈顶元素; 实现十进制数与八进制数的转换; 定义链式队列，完成队列的基本操作：入队和出队; 1．问题描述： （1）利用栈的顺序存储结构,设计一组输入数据（假定为一组整数），能够对顺序栈进行如下操作： . 初始化一个空栈，分配一段连续的存储空间，且设定好栈顶和栈底; . 完成一个元素的入栈操作，修改栈顶指针; . 完成一个元素的出栈操作，修改栈顶指针; . 读取栈顶指针所指向的元素的值; . 将十进制数N 和其它d 进制数的转换是计算机实现计算的基本问题，其解决方案很多，其中最简单方法基于下列原理：即除 d 取余法。例如：（1348）10=（2504）8 N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2 从中我们可以看出，最先产生的余数 4 是转换结果的最低位，这正好符合栈的特性即后进先出的特性。 所以可以用顺序栈来模拟这个过程。以此来实现十进制数与八进制数的转换; . 编写主程序，实现对各不同的算法调用。 （2）利用队列的链式存储结构,设计一组输入数据（假定为一组整数），能够对链式队列进行如下操作： . 初始化一个空队列，形成一个带表头结点的空队; . 完成一个元素的入队操作，修改队尾指针; . 完成一个元素的出队操作，修改队头指针; . 修改主程序，实现对各不同的算法调用。

数据库实验报告4

数据库-实验报告4 学号：11122604 姓名：陆亮 第4周（第四章：数据更新、视图、嵌入式SQL部分自学） 一、实验课： 1.建立计算机学院总评不及格成绩学生的视图，包括学生学号、姓名、性别、手机、所选 课程和成绩。 2.在E表中插入记录，把每个学生没学过的课程都插入到E表中，使得每个学生都选修每 门课。 3.求年龄大于所有女同学年龄的男学生姓名和年龄。 4.在E表中修改08305001课程的平时成绩，若成绩小于等于75分时提高5%，若成绩大于 75分时提高4%。 5.删除没有开课的学院。//删除记录而不是表。删除表要用其他。 6.查询优、良、中、及格、不及格学生人数 二，代码： create view student_fail(xh,xm,xb,sjhm,kh,zpcj)as(select distinct S.xh,S.xm,S.xb,S.sjhm,E.kh,E.zpcj from S,E where S.xh=E.xh and E.zpcj<'60'); insert into E select distinct S.xh,O.xq,O.kh,O.gh ,null,null,null from S,O where not exists(select*from E where E.xh =S.xh and E.kh =O.kh ); select S.xm,S.csrq from S where S.csrq<(select min(csrq)from S group by S.xb having xb ='女') update E set pscj = pscj*1.04 where pscj>75; update E set pscj = pscj*1.05 where pscj<75; delete from D where yxh not in(select yxh from T ,O where T.gh = O.gh)

数据结构与算法实验报告册

. . 河南工程学院 理学院学院 实验报告 （数据结构与算法） 学期: 课程: 专业: 班级: 学号: 姓名: 指导教师:

. . 目录 实验一线性表1（顺序表及单链表的合并） (1) 实验二线性表2（循环链表实现约瑟夫环） (1) 实验三栈和队列的应用（表达式求值和杨辉三角） (1) 实验四赫夫曼编码 实验五最小生成树 (1) 实验六排序算法

. . 实验一线性表1 一、实验学时：2学时 二、实验目的 1.了解线性表的逻辑结构特性是数据元素之间存在着线性关系。在计算机中 表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。 2.熟练掌握这两类存储结构的描述方法以及线性表的基本操作在这两种存储 结构上的实现。 三、实验内容 1. 编写程序，实现顺序表的合并。 2. 编写程序，实现单链表的合并。 四、主要仪器设备及耗材 硬件：计算机一台 软件：VC++ 6.0，MSDN2003或者以上版本 五、算法设计 1. 顺序表合并的基本思想 程序流程图： 2. 单链表合并的基本思想 程序流程图 六、程序清单

. 七、实现结果 .

. 八、实验体会或对改进实验的建议.

. . 实验二线性表2 一、实验学时：2学时 二、实验目的 1.了解双向循环链表的逻辑结构特性，理解与单链表的区别与联系。 2.熟练掌握双向循环链表的存储结构以及基本操作。 三、实验内容 编写程序，采用循环链表实现约瑟夫环。 设有编号为1，2，……，n的n(n>0)个人围成一个圈，从第1个人开始报数，报到m时停止报数，报m的人出圈，再从他的下一个人起重新报数，报到m时停止报数，报m的出圈，……，如此下去，直到所有人全部出圈为止。当任意给定n和m后，设计算法求n个人出圈的次序。 四、主要仪器设备及耗材 硬件：计算机一台 软件：VC++ 6.0，MSDN2003或者以上版本 五、算法设计 约瑟夫环实现的基本思想 程序流程图： 六、程序清单

数据结构实验报告全集

数据结构实验报告全集 实验一线性表基本操作和简单程序 1．实验目的 （1）掌握使用Visual C++ 上机调试程序的基本方法； （2）掌握线性表的基本操作：初始化、插入、删除、取数据元素等运算在顺序存储结构和链表存储结构上的程序设计方法。 2．实验要求 （1）认真阅读和掌握和本实验相关的教材内容。 （2）认真阅读和掌握本章相关内容的程序。 （3）上机运行程序。 （4）保存和打印出程序的运行结果，并结合程序进行分析。 （5）按照你对线性表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果 实验代码： 1）头文件模块 #include >验目的 掌握顺序栈的基本操作：初始化栈、判栈空否、入栈、出栈、取栈顶数据元素等运算以及程序实现方法。 2.实验要求 （1）认真阅读和掌握和本实验相关的教材内容。 （2）分析问题的要求，编写和调试完成程序。 （3）保存和打印出程序的运行结果，并分析程序的运行结果。 3.实验内容 利用栈的基本操作实现一个判断算术表达式中包含圆括号、方括号是否正确配对的程序。具体完成如下：

（1）定义栈的顺序存取结构。 （2）分别定义顺序栈的基本操作（初始化栈、判栈空否、入栈、出栈等）。 （3）定义一个函数用来判断算术表达式中包含圆括号、方括号是否正确配对。其中，括号配对共有四种情况：左右括号配对次序不正确；右括号多于左括号；左括号多于右括号；左右括号匹配正确。 （4）设计一个测试主函数进行测试。 （5）对程序的运行结果进行分析。 实验代码： #include < > #define MaxSize 100 typedef struct { int data[MaxSize]; int top; }SqStack;

数据结构与算法基础

数据结构与算法基础 一．判断题： 1．数据元素是数据的最小单位。 2．数据结构是带有结构的数据元素的集合。 3．数据结构、数据元素、数据项在计算机中的映像（或表示）分别称为存储结构、结点、数据域。 4．数据项是数据的基本单位。 5．数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要而建立的。 6．数据的物理结构是指数据在计算机内实际的存储形式。 7．算法和程序没有区别，所以在数据结构中二者是通用的。 答案： 1．错误 2．正确 3．正确 4．错误 5．正确 6．正确 7．错误 二． 数据结构是研究数据的 A 和 B 以及它们之间的相互关系，并对这种结构定义相应的 C ，设计出相应的 D ，而确保经过这些运算后所得到的新结构是 E 结构类型。 供选择答案： A、Ｂ：ａ理想结构ｂ抽象结构ｃ物理结构ｄ逻辑结构 Ｃ、Ｄ、Ｅ：ａ运算ｂ算法ｃ结构ｄ规则ｅ现在的ｆ原来的 答案： Ａ：ｃＢ；ｄＣ：ａＤ：ｂＥ：ｆ 三．从供选择的答案中选取正确的答案填在下面叙述中的横线上： 1． A 是描述客观事物的数字、字符以及所能输入到计算机中并被计算机程序加工处理的符号的集合。 2. B 是数据的基本单位,即数据集合中的个体。有时一个 B 由若干个___C____组成，在这种情况下，称 B 为记录。 C 是数据的最小单位。而由记录所组成的线性表为 D 。 3. E 是具有相同特性的数据元素的集合，是数据的子集。 4. Ｆ是带有结构特性数据元素的集合。 5. 被计算机加工的数据元素不是孤立无关的，它们彼此之间一般存在着某种联系。通常将数据元素的这种关系称为Ｇ。 6. 算法的计算量的大小称为计算的Ｈ。 供选择的答案： Ａ－Ｆ：ａ数据元素ｂ符号ｃ记录ｄ文件ｅ数据ｆ数据项ｇ数据对象ｈ关键字ｉ数据结构

数据库原理实验报告四(有答案)

南京晓庄学院 《数据库原理与应用》课程实验报告 实验四查询设计实验 所在院(系):数学与信息技术学院 班级： 学号： 姓名：

1.实验目的 (1)了解查询的目的，掌握SELECT语句的基本语法和查询条件的表示方法。 (2)掌握数据排序和数据联接查询的方法。 (3)掌握SQL Server查询分析器的使用方法。 2.实验要求 (1)针对“TM”数据库，在SQL Server查询分析器中，用T-SQL语句实现以下单表查询 操作，并将将调试成功的T-SQL命令，填入实验报告中。 a)查询所有课程的详细情况。 b)查询来自江苏或山东的学生学号和姓名，并以中文名称显示输出的列名。 c)查询选修了课程的学生学号（一人选了多门课程的话，学号只显示一次）。 d)查询选修课程号为07253001的学号和成绩，并要求对查询结果按成绩降 序排列，如果成绩相同则按学号升序排列。 e)查询所有学生的学号、姓名和年龄。 f)查询选修课程号为07253001的成绩在85-95之间的学生学号和成绩，并 将成绩乘以0.7输出。 g)查询数学与信息技术学院（DEPT_ID为07）或物理与电子工程学院 (DEPT_ID为09)姓张的学生的信息。。 h)查询所有核心课程（课程名中带*的）的情况。 i)查询缺少了成绩的学生的学号和课程号，查询结果按课程号升序排列。 (2)在SQL Server查询分析器中，用T-SQL语句实现下列数据联接查询操作： a)查询每个学生的情况以及他（她）所选修的课程。 b)查询学生的学号、姓名、选修的课程名及成绩。 c)查询选修C语言程序设计且成绩为85分以上的学生学号、姓名及成绩。 d)查询和学生柏文楠是同一个民族的学生（用自身联接实现）。 e)分别用等值联接和内联接查询有授课记录的老师的姓名。 f)用外联接查询所有老师的授课情况，输出老师的工号、姓名、职称、院 系、担任的课程号和授课的学期，结果按院系和职称升序排列。如果该 老师没有授课历史，在课程号和授课的学期中显示空值 (3)在SQL Server Management Studio中新建查询，完成以上查询命令的同时，熟悉SQL编 辑器工具栏中各快捷按钮的作用。 (4)按要求完成实验报告。

数据库实验三实验报告

数据库___课程实验报告实验名称：交互式SQL（二） 姓名班级学号 实验台 编号 同组学生 实验课表现出勤、表现得分25% 实验报告 得分50% 实验总分操作结果得分25% 实验目的： 1．学会熟练使用INSERT语句对数据表进行数据插入操作。 2．学会使用UPDATE语句对数据表中的数据进行修改操作。 3．学会使用DELETE语句对数据表中的数据进行删除操作。 4．了解使用视图的目的与好处，掌握视图与基本表的关系，掌握如何使用SQL语句创建、修改、删除和查询视图。 实验内容： 一、数据的插入、删除和修改 创建表XS1（包括学号、姓名、性别和出生日期字段，各个字段属性自定），然后使用SELECT子句向表XS1中插入多行数据（专业为“电子”的学生数据）。 create view xs1() as select学号,姓名,性别,出生日期from xs where专业='电子'; 修改XS1表的结构，增加1个“平均成绩”字段，并根据XS_KC表修改每个学生的“平均成绩”。 alter table xs1 add平均成绩int; update xs1 set平均成绩=( select avg(成绩)from xs_kc where xs_kc.学号=xs1.学号group by学号); 将XS表中计算机专业的学生的总学分增加10分。 update xs set总学分=总学分+10 where专业='计算机'; 将XS表中学号为“4102101”的同学的总学分增加4分,备注改为“提前修完一门课程”。 update xs set总学分=总学分+4,备注='提前修完一门课程' where学号='4102101'; 将XS_KC表中学号为“4102101”的同学的“计算机基础”课程的成绩增加10分。 update xs_kc set成绩=成绩+10 where学号='4102101'and课程号= (select课程号from kc where kc.课程名='计算机基础'); 修改XS1表的结构，增加1个“总学分”字段，并使其值为该学生所学各门功课的学分之和。 alter table xs1 add总学分tinyint; update xs1 set总学分= (select sum(学分)from kc,xs_kc where xs_kc.学号=xs1.学号and xs_kc.课程号= kc.课程号

全国计算机二级第1章数据结构与算法

考点1 算法的复杂度 【考点精讲】 1．算法的基本概念 计算机算法为计算机解题的过程实际上是在实施某种算法。 算法的基本特征：可行性、确定性、有穷性、拥有足够的情报。 2．算法复杂度 算法复杂度包括时间复杂度和空间复杂度。 名称 描述 时间复杂度 是指执行算法所需要的计算工作量 空间复杂度 是指执行这个算法所需要的内存空间 考点2 逻辑结构和存储结构 【考点精讲】 1．逻辑结构 数据的逻辑结构是对数据元素之间的逻辑关系的描述，它可以用一个数据元素的集合和定义在此集合中的若干关系来表示。数据的逻辑结构有两个要素：一是数据元素的集合，通常记为D；二是D上的关系，它反映了数据元素之间的前后件关系，通常记为R。一个数据结构可以表示成 B=（D，R） 其中B表示数据结构。为了反映D中各数据元素之间的前后件关系，一般用二元组来表示。例如，如果把一年四季看作一个数据结构，则可表示成 B =（D,R） D ={春季，夏季，秋季，冬季} R ={（春季，夏季）,（夏季，秋季），（秋季，冬季）} 2．存储结构 数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构（也称数据的物理结构）。 由于数据元素在计算机存储空间中的位置关系可能与逻辑关系不同，因此，为了表示存放在计算机存储空间中的各数据元素之间的逻辑关系（即前后件关系），在数据的存储结构中，不仅要存放各数据元素的信息，还需要存放各数据元素之间的前后件关系的信息。 一种数据的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序、链接等存

储结构。 顺序存储方式主要用于线性的数据结构，它把逻辑上相邻的数据元素存储在物理上相邻的存储单元里，结点之间的关系由存储单元的邻接关系来体现。 链式存储结构就是在每个结点中至少包含一个指针域，用指针来体现数据元素之间逻辑上的联系。 考点3 线性结构和非线性结构 【考点精讲】 根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分为两大类型：线性结构与非线性结构。如果一个非空的数据结构满足下列两个条件： （1）有且只有一个根结点； （2）每一个结点最多有一个前件，也最多有一个后件。 则称该数据结构为线性结构。线性结构又称线性表。在一个线性结构中插入或删除任何一个结点后还应是线性结构。栈、队列、串等都线性结构。 如果一个数据结构不是线性结构，则称之为非线性结构。数组、广义表、树和图等数据结构都是非线性结构。 考点4 栈 【考点精讲】 1．栈的基本概念 栈（stack）是一种特殊的线性表，是限定只在一端进行插入与删除的线性表。在栈中，一端是封闭的，既不允许进行插入元素，也不允许删除元素；另一端是开口的，允许插入和删除元素。通常称插入、删除的这一端为栈顶，另一端为栈底。当表中没有元素时称为空栈。栈顶元素总是后被插入的元素，从而也是最先被删除的元素；栈底元素总是最先被插入的元素，从而也是最后才能被删除的元素。 栈是按照“先进后出”或“后进先出”的原则组织数据的。例如，枪械的子弹匣就可以用来形象的表示栈结构。子弹匣的一端是完全封闭的，最后被压入弹匣的子弹总是最先被弹出，而最先被压入的子弹最后才能被弹出。 2．栈的顺序存储及其运算 栈的基本运算有三种：入栈、退栈与读栈顶元素。 （1）入栈运算：入栈运算是指在栈顶位置插入一个新元素。 （2）退栈运算：退栈是指取出栈顶元素并赋给一个指定的变量。 （3）读栈顶元素：读栈顶元素是指将栈顶元素赋给一个指定的变量。 考点5 队列 【考点精讲】 1．队列的基本概念 队列是只允许在一端进行删除，在另一端进行插入的顺序表，通常将允许删除的这一端称为队头，允许插入的这一端称为队尾。 当表中没有元素时称为空队列。 队列的修改是依照先进先出的原则进行的，因此队列也称为先进先出的线性表，或者后进后出的线性表。例如：火车进遂道，最先进遂道的是火车头，最后是火车尾，而火车出遂道的时候也是火车头先出，最后出的是火车尾。若有队列： Q =（q1，q2，…，qn） 那么，q1为队头元素（排头元素），qn为队尾元素。队列中的元素是按照q1，q2，…，qn 的顺序进入的，退出队列也只能按照这个次序依次退出，即只有在q1，q2，…，qn-1 都退队之后，qn才能退出队列。因最先进入队列的元素将最先出队，所以队列具有先进先出的

(完整版)数据库实验报告

数据库实验报告姓名学号

目录 一．实验标题：2 二．实验目的：2 三．实验内容：2 四．上机软件：3 五．实验步骤：3 （一）SQL Server 2016简介3（二）创建数据库 4 （三）创建数据库表 7（四）添加数据17 六．分析与讨论： 19

一．实验标题： 创建数据库和数据表 二．实验目的： 1.理解数据库、数据表、约束等相关概念； 2.掌握创建数据库的T-SQL命令； 3.掌握创建和修改数据表的T-SQL命令； 4.掌握创建数据表中约束的T-SQL命令和方法； 5.掌握向数据表中添加数据的T-SQL命令和方法三．实验内容： 1.打开“我的电脑”或“资源管理器”，在磁盘空间以自己的姓名或学号建立文件夹； 2.在SQL Server Management Studio中，使用create database命令建立“学生-选课”数据库，数据库文件存储在步骤1建立的文件夹下，数据库文件名称自由定义； 3.在建立的“学生-选课”数据库中建立学生、课程和选课三张表，其结构及约束条件如表所示，要求为属性选择合适的数据长度； 4.添加具体数据；

四．上机软件： SQL Server 2016 五．实验步骤： （一）SQL Server 2016简介 1.SQL Server 2016的界面 2.启动和退出SQL Server 2016 1)双击图标，即出现SQL Server2016的初始界 2)选择“文件”菜单中的“退出”命令，或单击控制按钮中的“×”即可 注意事项： 1.在退出SQL Server 2016之前，应先将已经打开的数据库进行保存， 2.如果没有执行保存命令，系统会自动出现保存提示框，根据需要选择相应的操作

《算法与数据结构》实验报告(2014) 内蒙古大学

《算法与数据结构》实验报告 班级____________ 姓名___________ 学号_____________ 实验1：线性表的应用（6学时） [问题描述] 一个线性表A中包含有三类字符：数字字符、字母字符、其他字符。试写一个函数实现对线性表A的拆分，使得线性表A、B、C分别各自指向同一类字符。 [实验目的] （1）熟练掌握链表的基本操作； （2）运用链表解决实际问题。 [实验内容及要求] （1）首先通过输入字符建立线性表A； （2）在拆分时，必须使用原表A的结点空间，不能额外创建新结点； （3）拆分后，原表A指向数字字符，且其内容的前后次序与原表中的前后次序必须一致，新的表B指向字母字符，新的表C指向其他字符。其中要求删除B中 的重复结点（如“abbcdexec”，变为“abcdex”）。 （4）分别输出表A、B（删除重复结点后的内容）、C的内容； （5）判断拆分后的表A是否是中心对称的（如123321或12321都是中心对称的），若是，则输出1，否则输出0。 [示例输入/输出] 示例输入： 1aabccd2e3f(!3c<2g1> (用于创建原表A的输入字符串) 示例输出： 123321 (拆分后表A的内容) abcdef (拆分后表B的内容) (!<> (拆分后表C的内容) 1 (拆分后表A是中心对称的)

《算法与数据结构》实验报告 班级____________ 姓名___________ 学号_____________ 实验2：表达式求值（6学时） [问题描述] 表达式求值是计算机实现程序设计语言中的基本问题之一，也是栈应用的一个典型例子，通过本实验，对输入的一个表达式进行求值。 [实验目的] （1）掌握栈的应用； （2）掌握算符优先表达式求值的算法； （3）掌握字符串处理和数值的转换； （4）练习上述知识的综合应用。 [实验内容及要求] （1）表达式以字符串形式输入。如：12*（12.4+20.15）/25，结果以字符串形式输出（保留小数点后2位）。 （2）运算数是实数，运算符有+ - * / ，带括号，常用函数有：开方sqr()、正弦sin() 、余弦cos()、四舍五入取整rd()。函数的优先级高于+ - * /。 （3）能够有效判别表达式的输入格式是否有误（如缺失操作数、括号不匹配、函数名错误等），若输入错误，输出为“error！”。 [示例输入/输出] 示例输入： 12*（12.4+20.15）/25 15.4/(2-sin(5.12)*)+21 示例输出： 15.62 error！

算法与数据结构实验

学生实验报告册 （理工类） 金陵科技学院教务处制 实验报告书写要求 实验报告原则上要求学生手写，要求书写工整。若因课程特点需

打印的，要遵照以下字体、字号、间距等的具体要求。纸张一律采用A4的纸张。 实验报告书写说明 实验报告中一至四项内容为必填项，包括实验目的和要求；实验仪器和设备；实验内容与过程；实验结果与分析。各院部可根据学科特点和实验具体要求增加项目。 填写注意事项 （1）细致观察，及时、准确、如实记录。 （2）准确说明，层次清晰。 （3）尽量采用专用术语来说明事物。 （4）外文、符号、公式要准确，应使用统一规定的名词和符号。 （5）应独立完成实验报告的书写，严禁抄袭、复印，一经发现，以零分论处。 实验报告批改说明 实验报告的批改要及时、认真、仔细，一律用红色笔批改。实验报告的批改成绩采用百分制，具体评分标准由各院部自行制定。 实验报告装订要求 实验批改完毕后，任课老师将每门课程的每个实验项目的实验报告以自然班为单位、按学号升序排列，装订成册，并附上一份该门课程的实验大纲。

实验项目名称：顺序表实验学时： 2 同组学生姓名：实验地点：A101 实验日期： 4.5 实验成绩： 批改教师：批改时间：

实验1 顺序表 一、实验目的和要求 掌握顺序表的定位、插入、删除等操作。 二、实验仪器和设备 Turbo C 2.0 三、实验内容与过程（含程序清单及流程图） 1、必做题 （1）编写程序建立一个顺序表，并逐个输出顺序表中所有数据元素的值。 编写主函数测试结果。 （2）编写顺序表定位操作子函数，在顺序表中查找是否存在数据元素x。 如果存在，返回顺序表中和x值相等的第1个数据元素的序号（序号 从0开始编号）；如果不存在，返回－1。编写主函数测试结果。 （3）在递增有序的顺序表中插入一个新结点x，保持顺序表的有序性。 解题思路：首先查找插入的位置，再移位，最后进行插入操作；从第 一个元素开始找到第一个大于该新结点值x的元素位置i即为插入位 置；然后将从表尾开始依次将元素后移一个位置直至元素i；最后将新 结点x插入到i位置。 （4）删除顺序表中所有等于X的数据元素。 2、选做题 （5）已知两个顺序表A和B按元素值递增有序排列，要求写一算法实现将A和B归并成一个按元素值递减有序排列的顺序表（允许表中含有值 相同的元素）。