《数据结构》实验教学大纲
课程面向的专业:电子商务
课程属性:专业基础课
课程教学总学时: 69 学时(其中理论教学 51 学时、实验教学16学时)
实验名称及学时分配
一、实验类别:验证性实验
二、实验目的:
验证线形表、栈、队列、树、图等数据结构的创建、插入、删除、查找等运算操作;
验证查找算法和各种排序算法,并对算法的时间复杂度和空间负责度进行优劣比较。
三、实验内容:
1.实验一线性表的操作
掌握线性表的基本操作:插入、删除、查找以及线性表合并等运算在顺序存储结构和链接存储结构上的运算。
2.实验二栈的基本操作
掌握栈的基本操作:初始化栈、判栈为空、出栈、入栈等运算。
3.实验三二叉树基本操作
创建、遍历、插入、删除、显示二叉树,通过二叉树的基本操作,掌握树结构的处理方法。
4.实验四图的基本操作
(1)分别用邻接矩阵和邻接表实现以下操作:
图的创建、遍历、插入、删除、最短路径。
(2)熟悉图的常用存储结构和基本操作。
5.实验五常用查找算法的对比分析
分别实现线性表的查找:顺序查找、二分查找、索引查找、分块查找;树型查找;散列查找等。并比较各算法的时、空性能。
6. 实验六常用排序算法的对比分析
(1)分别实现直接插入排序、冒泡排序、简单选择排序、希尔排序、快速排序、堆排序,并随机生成 30 个数,比较各算法的时、空性能和稳定性。
(2)掌握常用排序算法的特点,以便根据实际情况选择使用。
四、实验要求:
1. 阅读实验指导书
每一次实验从阅读实验指导书开始。对于本次实验的实验目的、实验题目、实现提示以及思考题目、选做题目等应认真了解。
2. 算法设计
分析实验题目,参考实现提示,进行算法设计。
3. 程序设计
根据已完成的算法,用 C 语言进行程序设计。
4. 调试和测试
将所编程序在计算机上调试通过,并选取若干组测试数据对程序进行尽可能全面的测试。
5. 整理完成实验报告
实验报告一般包括下列内容:
(1)实验者姓名、学号、专业和班级,课程名称(数据结构课程设计),实验日期等;
(2)本交实验的实验编号及实验名称(例如:实验一线性表的应用)
(3)本次实验的实验目的;
(4)本次实验的实验地点、设备编号、硬件及软件环境;
(5)程序结构的描述及各模块的规格说明;
(6)主要算法及其基本思想;
(7)调试过程简述(调试过程是否顺利,遇到些什么问题,如何解决的,以及上机操作所花费的时间等);
(8)测试数据和相应输出的客观纪录,对运行结果的分析讨论。
五、需要的仪器设备:
多媒体微型计算机Pentium Ⅲ700MHz 以上,120.0MB RAM 以上;Windows98/2000,Visual C++6.0 或Turbo C
六、考核方式
采用上机情况、程序质量、实习报告相结合的形式,满分为 100 分。
1.上机情况( 30% )
包括出勤情况、调试表现、是否上网、玩游戏。
2.程序质量( 50% )
3.实验报告( 20% )
#include
#include
#Typedef int elemType;
/****************************************************************** ******/
/*以下是关于线性表顺序存储操作的16种算法*/
/****************************************************************** ******/
struct List{
elemType *list;
int size;
int maxSize;
};
void againMalloc(structList*L)
{
/*空间扩展为原来的2倍,并由p指针所指向,原内容被自动拷贝到p 所指向的存储空间*/
elemType*p=realloc(L->list,2*L->maxSize*sizeof(elemType));
if(!p){ /*分配失败则退出运行*/
printf("存储空间分配失败! ");
exit(1);
}
L->list=p; /*使list指向新线性表空间*/
L->maxSize=2*L->maxSize; /*把线性表空间大小修改为新的长度*/ }
/*1.初始化线性表L,即进行动态存储空间分配并置L为一个空表*/
void initList(struct List *L,int ms)
{
/*检查ms是否有效,若无效的则退出运行*/
if(ms<=0){
printf("MaxSize非法! ");
exit(1); /*执行此函数中止程序运行,此函数在stdlib.h中有定义*/
}
L->maxSize=ms; /*设置线性表空间大小为ms*/
L->size=0;
L->list=malloc(ms*sizeof(elemType));
if(!L->list){
printf("空间分配失败! ");
exit(1);
}
return;
}
/*2.清除线性表L中的所有元素,释放存储空间,使之成为一个空表*/
void clearList(struct List *L)
{
if(L->list!=NULL){
free(L->list);
L->list=0;
L->size=L->maxSize=0;
}
return;
}
/*3.返回线性表L当前的长度,若L为空则返回0*/
int sizeList(struct List *L)
{
Return L->size;
}
/*4.判断线性表L是否为空,若为空则返回1,否则返回0*/
Int emptyList(struct List *L)
{
if(L->size==0){
return1;
}
else{
return0;
}
}
/*5.返回线性表L中第pos个元素的值,若pos超出范围,则停止程序运行*/ elemTypegetElem(structList*L,intpos)
{
if(pos<1||pos>L->size){ /*若pos越界则退出运行*/
printf("元素序号越界! ");
exit(1);
}
Return L->list[pos-1]; /*返回线性表中序号为pos值的元素值*/ }
/*6.顺序扫描(即遍历)输出线性表L中的每个元素*/
Void traverseList(struct List *L)
{
inti;
for(i=0;i
printf("%d",L->list[i]);
}
printf(" ");
return;
}
/*7.从线性表L中查找值与x相等的元素,若查找成功则返回其位置,否则返回-1*/
Int findList(structList *L,elemType x)
{
inti;
for(i=0;i
if(L->list[i]==x){
return i;
}
}
Return -1;
}
/*8.把线性表L中第pos个元素的值修改为x的值,若修改成功返回1,否则返回0*/
Int updatePosList(struct List *L,intpos,elemTypex)
{
if(pos<1||pos>L->size){ /*若pos越界则修改失败*/
return0;
}
L->list[pos-1]=x;
return1;
}
/*9.向线性表L的表头插入元素x*/
Void inserFirstList(structList*L,elemTypex)
{
inti;
if(L->size==L->maxSize){
againMalloc(L);
}
for(i=L->size-1;i>=0;i--){
L->list[i+1]=L->list[i];
}
L->list[0]=x;
L->size++;
return;
}
/*10.向线性表L的表尾插入元素x*/
voidinsertLastList(structList*L,elemTypex)
{
if(L->size==L->maxSize){ /*重新分配更大的存储空间*/
againMalloc(L);
}
L->list[L->size]=x; /*把x插入到表尾*/
L->size++; /*线性表的长度增加1*/
return;
}
/*11.向线性表L中第pos个元素位置插入元素x,若插入成功返回1,否则返回0*/
intinsertPosList(structList*L,intpos,elemTypex)
{
inti;
if(pos<1||pos>L->size+1){ /*若pos越界则插入失败*/
return0;
}
if(L->size==L->maxSize){ /*重新分配更大的存储空间*/
againMalloc(L);
}
for(i=L->size-1;i>=pos-1;i--){
L->list[i+1]=L->list[i];
}
L->list[pos-1]=x;
L->size++;
return1;
}
/*12.向有序线性表L中插入元素x, 使得插入后仍然有序*/ voidinsertOrderList(structList*L,elemTypex)
{
inti,j;
/*若数组空间用完则重新分配更大的存储空间*/
if(L->size==L->maxSize){
againMalloc(L);
}
/*顺序查找出x的插入位置*/
for(i=0;i
if(x
break;
}
}
/*从表尾到下标i元素依次后移一个位置,把i的位置空出来*/ for(j=L->size-1;j>=i;j--)
L->list[j+1]=L->list[j];
/*把x值赋给下标为i的元素*/
L->list[i]=x;
/*线性表长度增加1*/
L->size++;
return;
}
/*13.从线性表L中删除表头元素并返回它,若删除失败则停止程序运行*/ elemTypedeleteFirstList(structList*L)
{
elemTypetemp;
inti;
if(L->size==0){
printf("线性表为空,不能进行删除操作! ");
exit(1);
}
temp=L->list[0];
for(i=1;i
L->list[i-1]=L->list[i];
L->size--;
returntemp;
}
/*14.从线性表L中删除表尾元素并返回它,若删除失败则停止程序运行*/ elemTypedeleteLastList(structList*L)
{
if(L->size==0){
printf("线性表为空,不能进行删除操作! ");
exit(1);
}
L->size--;
returnL->list[L->size]; /*返回原来表尾元素的值*/ }
/*15.从线性表L中删除第pos个元素并返回它,若删除失败则停止程序运行*/
elemTypedeletePosList(structList*L,intpos)
{
elemTypetemp;
inti;
if(pos<1||pos>L->size){ /*pos越界则删除失败*/ printf("pos值越界,不能进行删除操作! ");
exit(1);
}
temp=L->list[pos-1];
for(i=pos;i
L->list[i-1]=L->list[i];
L->size--;
returntemp;
}
/*16.从线性表L中删除值为x的第一个元素,若成功返回1,失败返回0*/ intdeleteValueList(structList*L,elemTypex)
{
inti,j;
/*从线性表中顺序查找出值为x的第一个元素*/
for(i=0;i
if(L->list[i]==x){
break;
}
}
/*若查找失败,表明不存在值为x的元素,返回0*/
if(i==L->size){
return0;
}
/*删除值为x的元素L->list[i]*/
for(j=i+1;j
L->list[j-1]=L->list[j];
}
L->size--;
return1;
}
/****************************************************************** ******/
voidmain()
{
inta[10]={2,4,6,8,10,12,14,16,18,20};
inti;
structListL;
initList(&L,5);
for(i=0;i<10;i++){
insertLastList(&L,a[i]);
}
insertPosList(&L,11,48); insertPosList(&L,1,64);
printf("%d ",getElem(&L,1));
traverseList(&L);
printf("%d ",findList(&L,10));
updatePosList(&L,3,20);
printf("%d ",getElem(&L,3));
traverseList(&L);
deleteFirstList(&L); deleteFirstList(&L);
deleteLastList(&L); deleteLastList(&L);
deletePosList(&L,5); ;deletePosList(&L,7);
printf("%d ",sizeList(&L));
printf("%d ",emptyList(&L));
traverseList(&L);
clearList(&L);
return0;
}#include
#include
#defineNN12
#defineMM20
typedefintelemType;
/****************************************************************** ******/
/* 以下是关于线性表链接存储(单链表)操作的16种算法*/
/****************************************************************** ******/
structsNode{ /*定义单链表结点类型*/
elemTypedata;
structsNode*next;
};
/*1.初始化线性表,即置单链表的表头指针为空*/
voidinitList(structsNode**hl)
{
*hl=NULL;
return;
}
/*2.清除线性表L中的所有元素,即释放单链表L中所有的结点,使之成为一个空表*/
voidclearList(structsNode**hl)
{
/*cp和np分别作为指向两个相邻结点的指针*/
structsNode*cp,*np;
cp=*hl;
/*遍历单链表,依次释放每个结点*/
while(cp!=NULL){
np=cp->next; /*保存下一个结点的指针*/
free(cp);
cp=np;
}
*hl=NULL; /*置单链表的表头指针为空*/
return;
}
/*3.返回单链表的长度*/
intsizeList(structsNode*hl)
{
intcount=0; /*用于统计结点的个数*/
while(hl!=NULL){
count++;
hl=hl->next;
}
returncount;
}
/*4.检查单链表是否为空,若为空则返回1,否则返回0*/ intemptyList(structsNode*hl)
{
if(hl==NULL){
return1;
}else{
return0;
}
}
/*5.返回单链表中第pos个结点中的元素,若pos超出范围,则停止程序运行*/
elemTypegetElem(structsNode*hl,intpos)
{
inti=0; /*统计已遍历的结点个数*/
if(pos<1){
printf("pos值非法,退出运行! ");
exit(1);
}
while(hl!=NULL){
i++;
if(i==pos){
break;
}
hl=hl->next;
}
if(hl!=NULL){
returnhl->data;
}else{
printf("pos值非法,退出运行! ");
exit(1);
}
}
/*6.遍历一个单链表*/
voidtraverseList(structsNode*hl)
{
while(hl!=NULL){
printf("%5d",hl->data);
hl=hl->next;
}
printf(" ");
return;
}
/*7.从单链表中查找具有给定值x的第一个元素,若查找成功则返回该结点data域的存储地址,否则返回NULL*/
elemType*findList(structsNode*hl,elemTypex)
{
while(hl!=NULL){
if(hl->data==x){
return&hl->data;
}else{
hl=hl->next;
}
}
returnNULL;
}
/*8.把单链表中第pos个结点的值修改为x的值,若修改成功返回1,否则返回0*/
intupdatePosList(structsNode*hl,intpos,elemTypex)
{
inti=0;
structsNode*p=hl;
while(p!=NULL){ /*查找第pos个结点*/
i++;
if(pos==i){
break;
}else{
p=p->next;
}
}
if(pos==i){
p->data=x;
return1;
}else{
return0;
}
}
/*9.向单链表的表头插入一个元素*/
voidinsertFirstList(structsNode**hl,elemTypex)
{
structsNode*newP;
newP=malloc(sizeof(structsNode));
if(newP==NULL){
printf("内存分配失败,退出运行! ");
exit(1);
}
newP->data=x; /*把x的值赋给新结点的data域*/ /*把新结点作为新的表头结点插入*/
newP->next=*hl;
*hl=newP;
return;
}
/*10.向单链表的末尾添加一个元素*/
voidinsertLastList(structsNode**hl,elemTypex)
{
structsNode*newP;
newP=malloc(sizeof(structsNode));
if(newP==NULL){
printf("内在分配失败,退出运行! ");
exit(1);
}
/*把x的值赋给新结点的data域,把空值赋给新结点的next域*/
newP->data=x;
newP->next=NULL;
/*若原表为空,则作为表头结点插入*/
if(*hl==NULL){
*hl=newP;
}
/*查找到表尾结点并完成插入*/
else{
structsNode*p=NULL;
while(p->next!=NULL){
p=p->next;
}
p->next=newP;
}
return;
}
/*11.向单链表中第pos个结点位置插入元素为x的结点,若插入成功返回1,否则返回0*/
intinsetPosList(structsNode**hl,intpos,elemTypex){
inti=0;
structsNode*newP;
structsNode*cp=*hl,*ap=NULL;
/*对pos值小于等于0的情况进行处理*/
if(pos<=0){
printf("pos值非法,返回0表示插入失败! ");
return0;
}
/*查找第pos个结点*/
while(cp!=NULL){
i++;
if(pos==i){
break;
}else{
ap=cp;
cp=cp->next;
}
}
/*产生新结点,若分配失败,则停止插入*/
newP=malloc(sizeof(structsNode));
if(newP==NULL)
{
printf("内存分配失败,无法进行插入操作! ");
return0;
}
/*把x的值赋给新结点的data域*/
newP->data=x;
/*把新结点插入到表头*/
if(ap==NULL){
newP->next=cp; /*或改为newP->next=*hl;*/
*hl=newP;
}
/*把新结点插入到ap和cp之间*/
else{
newP->next=cp;
ap->next=newP;
}
return1; /*插入成功返回1*/
}
/*12.向有序单链表中插入元素x结点,使得插入后仍然有序*/ voidinsertOrderList(structsNode**hl,elemTypex)
{
/*把单链表的表头指针赋给cp,把ap置空*/
structsNode*cp=*hl,*ap=NULL;
/*建立新结点*/
structsNode*newP;
newP=malloc(sizeof(structsNode));
if(newP==NULL){
printf("内在分配失败,退出运行! ");
exit(1);
}
newP->data=x; /*把x的值赋给新结点的data域*/ /*把新结点插入到表头*/
if((cp==NULL)||(x
newP->next=cp;
*hl=newP;
return;
}
/*顺序查找出x结点的插入位置*/
while(cp!=NULL){
if(x
break;
}else{
实验2 查找算法的实现和应用?实验目的 1. 熟练掌握静态查找表的查找方法; 2. 熟练掌握动态查找表的查找方法; 3. 掌握hash表的技术. ?实验内容 1.用二分查找法对查找表进行查找; 2.建立二叉排序树并对该树进行查找; 3.确定hash函数及冲突处理方法,建立一个hash表并实现查找。 程序代码 #include cout<<"Not present!"; } return 0; } 结果 二叉排序树 #include #include<> #include<> #include<> #define MAXSIZE 100 typedef int DataType; typedef struct stack { DataType data[MAXSIZE]; int top; }sqstack; sqstack *InitStack(sqstack *S)出* 1.顺序栈的初始化*┃\n"); printf("\t┃* * *┃\n"); printf("\t┃************************************************************┃\n"); printf("\t┃* * *┃\n"); printf("\t┃* 2.元素的入栈* 3.元素的出栈*┃\n"); printf("\t┃* * *┃\n"); printf("\t┃************************************************************┃\n"); printf("\t┃* * *┃\n"); printf("\t┃* 4.取栈顶元素* 5.判空*┃\n"); printf("\t┃* * *┃\n"); printf("\t┃************************************************************┃\n"); printf("\t┃* *┃\n"); printf("\t┃* 6.将十进制数转换为其他进制数*┃\n"); printf("\t┃* *┃\n"); printf("\t┃************************************************************┃\n"); printf("\t┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛\n"); while ((m='0')&&(m='1')&&(m='2')&&(m='3')&&(m='4')&&(m='5')&&(m='6')&&(m='7')) { printf("\n请选择你需要操作的步骤(0至7):"); fflush(stdin); scanf("%c",&m); switch(m) { case '0': { exit(0); break; } 宁波工程学院电信学院计算机教研室 实验报告 课程名称:___ 数据结构 ___ __ 实验项目:链串的基本算法 指导教师: 实验位置:电子楼二楼机房姓名: 学号: 班级:计科102 日期: 2011/10/13 一、实验目的 1)熟悉串的定义和串的基本操作。 2)掌握链串的基本运算。 3)加深对串数据结构的理解,逐步培养解决实际问题的编程能力。 二、实验环境 装有Visual C++6.0的计算机。 三、实验内容 编写一个程序,实现链串的各种基本运算,并在此基础上设计一个主程序。具体如下: 编写栈的基本操作函数 链串类型定义如下所示: typedef struct snode{ char data; struct snode *next; }listring; (1)串赋值Assign(s,t) 将一个字符串常量赋给串s,即生成一个其值等于t的串s (2)串复制StrCopy(s,t) ?将串t赋给串s (3)计算串长度StrLength(s) ?返回串s中字符个数 (4)判断串相等StrEqual(s,t) ?若两个串s与t相等则返回1;否则返回0。 (5)串连接Concat(s,t) ?返回由两个串s和t连接在一起形成的新串。 (6)求子串SubStr(s,i,j) ?返回串s中从第i(1≤i≤StrLength(s))个字符开始的、由连续j 个字符组成的子串。 (7)插入InsStr (s,i,t) ?将串t插入到串s的第i(1≤i≤StrLength(s)+1)个字符中,即将t 的第一个字符作为s的第i个字符,并返回产生的新串(8)串删除DelStr (s,i,j) ?从串s中删去从第i(1≤i≤StrLength(s))个字符开始的长度为j 的子串,并返回产生的新串。 (9)串替换RepStr (s,s1,s2) ?在串s中,将所有出现的子串s1均替换成s2。 (10)输出串DispStr(s) ?输出串s的所有元素值 (11)判断串是否为空IsEmpty(s) 编写主函数 调用上述函数实现下列操作: (1)建立串s=“abcdefghijklmn”,串s1=“xyz”,串t=“hijk” (2)复制串t到t1,并输出t1的长度 (3)在串s的第9个字符位置插入串s1而产生串s2,并输出s2 (4)删除s第2个字符开始的5个字符而产生串s3,并输出s3 (5)将串s第2个字符开始的3个字符替换成串s1而产生串s4,并输出s4 (6)提取串s的第8个字符开始的4个字符而产生串s5,并输出s5 (7)将串s1和串t连接起来而产生串s6,并输出s6 (8)比较串s1和s5是否相等,输出结果 程序清单: #include 重庆文理学院软件工程学院实验报告册 专业:_____软件工程__ _ 班级:_____软件工程2班__ _ 学号:_____201258014054 ___ 姓名:_____周贵宇___________ 课程名称:___ 数据结构 _ 指导教师:_____胡章平__________ 2013年 06 月 25 日 实验序号 1 实验名称实验一线性表基本操作实验地点S-C1303 实验日期2013年04月22日 实验内容1.编程实现在顺序存储的有序表中插入一个元素(数据类型为整型)。 2.编程实现把顺序表中从i个元素开始的k个元素删除(数据类型为整型)。 3.编程序实现将单链表的数据逆置,即将原表的数据(a1,a2….an)变成 (an,…..a2,a1)。(单链表的数据域数据类型为一结构体,包括学生的部分信息:学号,姓名,年龄) 实验过程及步骤1. #include { ElemType elem[MAXSIZE]; /*线性表占用的数组空间*/ int last; /*记录线性表中最后一个元素在数组elem[ ]中的位置(下标值),空表置为-1*/ }SeqList; #include "common.h" #include "seqlist.h" void px(SeqList *A,int j); void main() { SeqList *l; int p,q,r; int i; l=(SeqList*)malloc(sizeof(SeqList)); printf("请输入线性表的长度:"); scanf("%d",&r); l->last = r-1; printf("请输入线性表的各元素值:\n"); for(i=0; i<=l->last; i++) { scanf("%d",&l->elem[i]); } px(l,i); printf("请输入要插入的值:\n"); 数据结构实验报告 一.题目要求 1)编程实现二叉排序树,包括生成、插入,删除; 2)对二叉排序树进行先根、中根、和后根非递归遍历; 3)每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。 4)分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率,并说明在什么情况下二叉排序树效率高,为什么? 二.解决方案 对于前三个题目要求,我们用一个程序实现代码如下 #include 实验报告 实验六图的应用及其实现 一、实验目的 1.进一步功固图常用的存储结构。 2.熟练掌握在图的邻接表实现图的基本操作。 3.理解掌握AOV网、AOE网在邻接表上的实现以及解决简单的应用问题。 二、实验内容 一>.基础题目:(本类题目属于验证性的,要求学生独立完成) [题目一]:从键盘上输入AOV网的顶点和有向边的信息,建立其邻接表存储结构,然后对该图拓扑排序,并输出拓扑序列. 试设计程序实现上述AOV网 的类型定义和基本操作,完成上述功能。 [题目二]:从键盘上输入AOE网的顶点和有向边的信息,建立其邻接表存储结构,输出其关键路径和关键路径长度。试设计程序实现上述AOE网类型定义和基本操作,完成上述功能。 测试数据:教材图7.29 【题目五】连通OR 不连通 描述:给定一个无向图,一共n个点,请编写一个程序实现两种操作: D x y 从原图中删除连接x,y节点的边。 Q x y 询问x,y节点是否连通 输入 第一行两个数n,m(5<=n<=40000,1<=m<=100000) 接下来m行,每行一对整数 x y (x,y<=n),表示x,y之间有边相连。保证没有重复的边。 接下来一行一个整数 q(q<=100000) 以下q行每行一种操作,保证不会有非法删除。 输出 按询问次序输出所有Q操作的回答,连通的回答C,不连通的回答D 样例输入 3 3 1 2 1 3 2 3 5 Q 1 2 D 1 2 Q 1 2 D 3 2 Q 1 2 样例输出 C C D 【题目六】 Sort Problem An ascending sorted sequence of distinct values is one in which some form of a less-than operator is used to order the elements from smallest to largest. For example, the sorted sequence A, B, C, D implies that A < B, B < C and C < D. in this problem, we will give you a set of relations of the form A < B and ask you to determine whether a sorted order has been specified or not. 【Input】 Input consists of multiple problem instances. Each instance starts with a line containing two positive integers n and m. the first value indicated the number of objects to sort, where 2 <= n<= 26. The objects to be sorted will be the first n characters of the uppercase alphabet. The second value m indicates the number of relations of the form A < B which will be given in this problem instance. 1 <= m <= 100. Next will be m lines, each containing one such relation consisting of three characters: an uppercase letter, the character "<" and a second uppercase letter. No letter will be outside the range of the first n letters of the alphabet. Values of n = m = 0 indicate end of input. 【Output】 For each problem instance, output consists of one line. This line should be one of the following three: Sorted sequence determined: y y y… y. Sorted sequence cannot be determined. Inconsistency found. 实验三的实验报告 学期: 2010 至_2011 第 2 学期 2011年 3月 27日课程名称: 数据结构专业:信息与计算科学 09 级5班实验编号: 03 实验项目:栈和队列实验指导教师 _冯山_姓名:朱群学号: 2009060548 实验成绩: 一实验目的: (1)熟练掌握栈和队列的抽象数据类型及其结构特点; (2)实现基本的栈和队列的基本操作算法程序。 二实验内容:(类C算法的程序实现,任选其一) (1) 设计与实现基本的堆栈和队列结构下的各种操作(如堆栈的PUSH、POP 等操作)(必做); (2)以表达式计算为例,完成一个可以进行算术表达式计算功能的算法设计 与实现(选做); (3)以迷宫问题为例,以堆栈结构完成迷宫问题的求解算法和程序(选做)。三实验准备: 1) 计算机设备;2)程序调试环境的准备,如TC环境;3)实验内容的算法分 析与代码设计与分析准备。 四实验步骤: 1.录入程序代码并进行调试和算法分析; 2.编写实验报告。 五实验过程 一设计与实现基本的堆栈结构下的各种操作(如堆栈的PUSH、POP等操作)(1)问题描述 实现堆栈各种基本操作,如Pop,Push,GetTop等操作,即输入数据,通过Push入栈,再通过Pop操作输出出栈的元素,即入栈a,b,c,d,出栈d,c,b,a (2)算法实现及基本思想 堆栈是后进先出的线性表,由Push输入元素,Pop输出元素,堆栈的Push 操作思想,即插入元素e为新的的栈顶元素,先判断栈满与否,追加存储空间,然后将e值赋给栈顶指针Top。输入数据时用for循环 堆栈的Pop操作思想,先判断栈是否为空,若栈不空,则删除栈的栈顶元素,用e返回其值, (3)数据结构 栈的顺序存储结构 Typedef struct { 姓名: 学号: 班级: 2010年12月15日 实验一线性表的应用 【实验目的】 1、熟练掌握线性表的基本操作在顺序存储和链式存储上的实现。、; 2、以线性表的各种操作(建立、插入、删除、遍历等)的实现为重点; 3、掌握线性表的动态分配顺序存储结构的定义和基本操作的实现; 4、通过本章实验帮助学生加深对C语言的使用(特别是函数的参数调用、指针类型的 应用和链表的建立等各种基本操作)。 【实验内容】 约瑟夫问题的实现:n只猴子要选猴王,所有的猴子按1,2,…,n编号围坐一圈,从第一号开始按1,2…,m报数,凡报到m号的猴子退出圈外,如此次循环报数,知道圈内剩下一只猴子时,这个猴子就是猴王。编写一个程序实现上述过程,n和m由键盘输入。【实验要求】 1、要求用顺序表和链表分别实现约瑟夫问题。 2、独立完成,严禁抄袭。 3、上的实验报告有如下部分组成: ①实验名称 ②实验目的 ③实验内容:问题描述:数据描述:算法描述:程序清单:测试数据 算法: #include 实验编号:3四川师大《数据结构》实验报告2016年10月29日 实验三栈与队列及其应用_ 一.实验目得及要求 (1)掌握栈与队列这两种特殊得线性表,熟悉它们得特性,在实际问题背景下灵活运用它们; (2)本实验训练得要点就是“栈”得观点及其典型用法; (3)掌握问题求解得状态表示及其递归算法,以及由递归程序到非递归程序得转化方法。 二.实验内容 (1)编程实现栈在两种存储结构中得基本操作(栈得初始化、判栈空、入栈、出栈等); (2)应用栈得基本操作,实现数制转换(任意进制); (3)编程实现队列在两种存储结构中得基本操作(队列得初始化、判队列空、入队列、出队列); (4)利用栈实现任一个表达式中得语法检查(括号得匹配)。 (5)利用栈实现表达式得求值。 注:(1)~(3)必做,(4)~(5)选做。 三.主要仪器设备及软件 (1)PC机 (2)Dev C++ ,Visual C++, VS2010等 四.实验主要流程、基本操作或核心代码、算法片段(该部分如不够填写,请另加附页)(1)编程实现栈在两种存储结构中得基本操作(栈得初始化、判栈空、入栈、出栈等); A、顺序储存: ?代码部分: //Main、cpp: #include"SStack、h" int main() { SqStack S; SElemType e; int elect=1; InitStack(S); cout << "已经创建一个存放字符型得栈" << endl; while (elect) { Muse(); cin >> elect; cout << endl; switch (elect) { case 1: cout << "input data:"; cin >> e; Push(S, e); break; case 2: if(Pop(S, e)) {cout << e <<" is pop"<< endl; } else{cout<<"blank"< 长春大学计算机学院网络工程专业 数据结构实验报告 实验名称:实验二栈和队列的操作与应用 班级:网络14406 姓名:李奎学号:041440624 实验地点:日期: 一、实验目的: 1.熟练掌握栈和队列的特点。 2.掌握栈的定义和基本操作,熟练掌握顺序栈的操作及应用。 3.掌握链队的入队和出队等基本操作。 4.加深对栈结构和队列结构的理解,逐步培养解决实际问题的编程能力。 二、实验内容、要求和环境: 注:将完成的实验报告重命名为:班级+学号+姓名+(实验二),(如:041340538张三(实验二)),发邮件到:ccujsjzl@https://www.sodocs.net/doc/7814315097.html,。提交时限:本次实验后24小时之内。 阅读程序,完成填空,并上机运行调试。 1、顺序栈,对于输入的任意一个非负十进制整数,打印输出与其等值的八进制数 (1)文件SqStackDef. h 中实现了栈的顺序存储表示 #define STACK_INIT_SIZE 10 /* 存储空间初始分配量*/ #define STACKINCREMENT 2 /* 存储空间分配增量*/ typedef struct SqStack { SElemType *base; /* 在栈构造之前和销毁之后,base 的值为NULL */ SElemType *top; /* 栈顶指针*/ int stacksize; /* 当前已分配的存储空间,以元素为单位*/ }SqStack; /* 顺序栈*/ (2)文件SqStackAlgo.h 中实现顺序栈的基本操作(存储结构由SqStackDef.h 定义) Status InitStack(SqStack &S) { /* 构造一个空栈S */ S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!S.base) exit(OVERFLOW); /* 存储分配失败*/ S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK; } int StackLength(SqStack S) { // 返回S 的元素个数,即栈的长度, 编写此函数 洛阳理工学院实验报告 附:源程序: #include { InsertBST(&((*bst)->lchild),key); return OK; } else if(key>(*bst)->key) { InsertBST(&((*bst)->rchild),key); return OK; } } void CreateBST(BSTree *bst) { int key; *bst=NULL; scanf("%d", &key); while (key!=ENDKEY) { InsertBST(bst, key); scanf("%d", &key); } } BSTree SearchBST(BSTree bst, int key) { if(!bst) return NULL; else if(bst->key==key) return bst; //查找成功 else if(bst->key>key) return SearchBST(bst->lchild,key); else return SearchBST(bst->rchild,key); 实验报告 学院(系)名称:计算机科学与工程学院 姓名赵振宇学号20175302 专业 计算机科学与技术 班级 2017级4班实验项目 实验三:图的遍历与应用 课程名称 数据结构与算法 课程代码 0661913 实验时间 2019年5月27日 第3、4节 实验地点 7-219 考核标准实验过程25分 程序运行20分 回答问题15分 实验报告30分 特色功能5分 考勤违纪情况5分 成绩 成绩栏 其它批改意见: 教师签字: 考核内容 评价在实验课堂中的表现,包括实验态度、编写程序过程等内容等。 □功能完善,□功能不全□有小错□无法运行 ○正确○基本正确○有提示○无法回答 ○完整○较完整 ○一般 ○内容极少○无报告 ○有 ○无 ○有 ○无一、实验目的 1、实验目的:通过实验使学生理解图的主要存储结构,掌握图的构造算法、图的深度优先和广度优先遍历算法,能运用图解决具体应用问题。 二、实验题目与要求 要求:第1题为必做题,2,3,4至少选一 1.输入指定的边数和顶点数建立图,并输出深度优先遍历和广度优先遍历的结果。 1)问题描述:在主程序中设计一个简单的菜单,分别调用相应的函数功能:1…图的建立2…深度优先遍历图3…广度优先遍历图0…结束 2)实验要求:在程序中定义下述函数,并实现要求的函数功能:CreateGraph():按从键盘的数据建立图 DFSGrahp():深度优先遍历图 BFSGrahp():广度优先遍历图 3)实验提示: 图的存储可采用邻接表或邻接矩阵; 图存储数据类型定义(邻接表存储) #define MAX_VERTEX_NUM8//顶点最大个数 typedef struct ArcNode {int adjvex; struct ArcNode*nextarc; int weight;//边的权 }ArcNode;//表结点 #define VertexType int//顶点元素类型 typedef struct VNode {int degree,indegree;//顶点的度,入度 VertexType data; ArcNode*firstarc; }Vnode/*头结点*/,AdjList[MAX_VERTEX_NUM]; typedef struct{ AdjList vertices; int vexnum,arcnum;//顶点的实际数,边的实际数}ALGraph; 4)注意问题: 注意理解各算法实现时所采用的存储结构。 注意区别正、逆邻接。 2.教学计划编制问题 一、实验目的 1.进一步掌握指针变量的含义。 2.掌握二叉树的结构特征,以及各种存储结构的特点及使用范围。 3.掌握用指针类型描述、访问和处理二叉树的运算。 二、实验要求 1.认真阅读和掌握本实验的参考程序。 2.按照对二叉树的操作需要,在创建好二叉树后再通过遍历算法验证创建结果。3.保存程序的运行结果,并结合程序进行分析。 三、实验内容 以下参考程序是按完全二叉树思想将输入的字符串生成二叉树,并通过遍历来验证二叉树创建正确与否,但不能创建非完全二叉树,请认真研究该程序,然后模仿教材例6.4初始化方式创建二叉树:所有的空指针均用#表示,如教材图 6-13对应的二叉树,建立时的初始序列为:AB#D##CE##F##。然后通过遍历算法验证二叉树是否正确(先递归验证后非递归验证)。 参考程序略 程序代码如下: #include "stdio.h" #include "stdlib.h" typedef char Datatype; #define MAXSIZE 100 typedef struct bnode { Datatype data; struct bnode *lchild,*rchild; }BNode,*BTree; typedef struct{ BTree data[MAXSIZE]; int front,rear; }seqqueue,*Pseqqueue; typedef struct{ BNode *node; int flag; }Data; typedef struct node { Data Data[MAXSIZE]; int top; }SeqStack,*PSeqStack; PSeqStack Init(void) 实验六图的应用及其实现 一、实验目的 1.进一步功固图常用的存储结构。 2.熟练掌握在图的邻接表实现图的基本操作。 3.理解掌握AOE网在邻接表上的实现及解决简单的应用问题。 二、实验内容 [题目]:从键盘上输入AOE网的顶点和有向边的信息,建立其邻接表存储结构,输出其关键路径和关键路径长度。试设计程序实现上述AOE网类型定义和基本操作,完成上述功能。 三、实验步骤 (一)、数据结构与核心算法的设计描述 本实验题目是基于图的基本操作以及邻接表的存储结构之上,着重拓扑排序算法的应用,做好本实验的关键在于理解拓扑排序算法的实质及其代码的实现。 (二)、函数调用及主函数设计 以下是头文件中数据结构的设计和相关函数的声明: typedef struct ArcNode // 弧结点 { int adjvex; struct ArcNode *nextarc; InfoType info; }ArcNode; typedef struct VNode //表头结点 { VertexType vexdata; ArcNode *firstarc; }VNode,AdjList[MAX_VERTEX_NUM]; typedef struct //图的定义 { AdjList vertices; int vexnum,arcnum; int kind; }MGraph; typedef struct SqStack //栈的定义 { SElemType *base; SElemType *top; int stacksize; }SqStack; int CreateGraph(MGraph &G);//AOE网的创建 int CriticalPath(MGraph &G);//输出关键路径 (三)、程序调试及运行结果分析 (四)、实验总结 在做本实验的过程中,拓扑排具体代码的实现起着很重要的作用,反复的调试和测试占据着实验大量的时间,每次对错误的修改都加深了对实验和具体算法的理解,自己的查错能力以及其他各方面的能力也都得到了很好的提高。最终实验结果也符合实验的预期效果。 四、主要算法流程图及程序清单 1、主要算法流程图: 2、程序清单: 创建AOE网模块: int CreateGraph(MGraph &G) //创建有向网 { int i,j,k,Vi,Vj; ArcNode *p; cout<<"\n请输入顶点的数目、边的数目"< 数据结构实验3 《数据结构与算法》实验报告 实验序号:3 实验项目名称:链式表的操作学号1507112104 姓名陈忠表专业、班15商智实验地点指导教师林开标实验时间16.11.09 一、实验目的及要求 1. 通过实验理解单链表的逻辑结构; 2. 通过实验掌握单链表的基本操作和具体的函数实现。 二、实验设备(环境)及要求 微型计算机; windows 操作系统; Microsoft Visual Studio 6.0集成开发环境。 三、实验内容与步骤 链式表表示和实现线性表的如下: #include"stdio.h" #include"stdlib.h" typedef struct node //定义结点 { int data; //结点的数据域为整型 struct node *next; //结点的指针域 }ListNode; typedef ListNode * LinkList; // 自 定义LinkList单链表类型 LinkList CreatListR1(); //函数,用尾插入法建立带头结点的单链表 ListNode *LocateNode(LinkList head, int key); //函数,按值查找结点 void DeleteList(LinkList head,int key); //函数,删除指定值的结点 void printlist(LinkList head); //函数,打印链表中的所有值 void DeleteAll(LinkList head); //函数,删除所有结点,释放内存 //==========主函数============== void main() { int num; char ch; LinkList head; head=CreatListR1(); //用尾插入 法建立单链表,返回头指针 printlist(head); //遍历链表 输出其值 printf(" Delete node (y/n):"); //输入 实验难度: A □ B □ C □序号学号姓名成绩 指导教师(签名) 学期:2017秋季学期 任课教师: 实验题目: 组员及组长: 承担工作: 联系电话: 电子邮件: 完成提交时间:年月日 一、【实验构思(Conceive)】(10%) (本部分应包括:描述实验实现的基本思路,包括所用到的离散数学、工程数学、程序设计等相关知识,对问题进行概要性地分析) 魔王语言的解释规则: 大写字母表示魔王语言的词汇,小写字母表示人的词汇语言,魔王语言中可以包含括号,魔王语言的产生式规则在程序中给定,当接收用户输入的合法的魔王语言时,通过调用魔王语言翻译函数来实现翻译。 在 A 的基础上,(根据产生式)自定义规则,将一段魔王的话翻译为有意义的人类语言(中文):输入wasjg,则魔王语言解释为“我爱数据结构”。 运用了离散数学的一些基本知识及程序设计知识。 二、【实验设计(Design)】(20%) (本部分应包括:抽象数据类型的定义和基本操作说明,程序包含的模块以及各模块间的调用关系,关键算法伪码描述及程序流程图等,如有界面则需包括界面设计,功能说明等) //---------------抽象数据类型的定义------------------// #define STACK_INIT_SIZE 50 #define STACKINCREMENT 10 #define OVERLOW -2 #define ERROR -1 typedef struct { char *base; //顺序栈的栈底指针 int top; //顺序栈的栈顶 int size; //栈元素空间的大小 }SqStack; //结构体类型顺序栈 typedef struct { char *base; int front; int rear; }SqQueue; //结构体类型队列 //---------------各个模块功能的描述------------------// void Init_SqStack(SqStack &s) //初始化顺序桟 void Push_SqStack(SqStack &s, char c) //压入数据 int Pop_SqStack(SqStack &s, char &e) //出桟 char GetTop_SqStack(SqStack s)//或得栈顶 2011~2012第一学期数据结构实验报告 班级:信管一班 学号:201051018 姓名:史孟晨 实验报告题目及要求 一、实验题目 设某班级有M(6)名学生,本学期共开设N(3)门课程,要求实现并修改如下程序(算法)。 1. 输入学生的学号、姓名和 N 门课程的成绩(输入提示和输出显示使用汉字系统), 输出实验结果。(15分) 2. 计算每个学生本学期 N 门课程的总分,输出总分和N门课程成绩排在前 3 名学 生的学号、姓名和成绩。 3. 按学生总分和 N 门课程成绩关键字升序排列名次,总分相同者同名次。 二、实验要求 1.修改算法。将奇偶排序算法升序改为降序。(15分) 2.用选择排序、冒泡排序、插入排序分别替换奇偶排序算法,并将升序算法修改为降序算法;。(45分)) 3.编译、链接以上算法,按要求写出实验报告(25)。 4. 修改后算法的所有语句必须加下划线,没做修改语句保持按原样不动。 5.用A4纸打印输出实验报告。 三、实验报告说明 实验数据可自定义,每种排序算法数据要求均不重复。 (1) 实验题目:《N门课程学生成绩名次排序算法实现》; (2) 实验目的:掌握各种排序算法的基本思想、实验方法和验证算法的准确性; (3) 实验要求:对算法进行上机编译、链接、运行; (4) 实验环境(Windows XP-sp3,Visual c++); (5) 实验算法(给出四种排序算法修改后的全部清单); (6) 实验结果(四种排序算法模拟运行后的实验结果); (7) 实验体会(文字说明本实验成功或不足之处)。 三、实验源程序(算法) Score.c #include "stdio.h" #include "string.h" #define M 6 #define N 3 struct student { char name[10]; int number; int score[N+1]; /*score[N]为总分,score[0]-score[2]为学科成绩*/ }stu[M]; void changesort(struct student a[],int n,int j) {int flag=1,i; struct student temp; while(flag) { flag=0; for(i=1;i 一,实验题目 实验六堆栈实验 设计算法,把一个十进制整数转化为二进制数输出。 二,问题分析 本程序要求将一个十进制整数转化为二进制数输出。完成此功能所要解决的问题是熟练掌握和运用入栈和出栈操作,实现十进制整数转化为二进制数。 (1)数据的输入形式和输入值得范围:输入的是一个十进制整数,且其为正整数。 (2)结果的输出形式:输出的是一个二进制整数 (3)测试数据:1)9 2)4500 三,概要设计 1.为了实现上述程序功能,需要: 构造一个空的顺序栈s 将十进制整数除以2的余数入栈 将余数按顺序出栈 2.本程序包含7个函数: 1)主函数main(); 2)顺序栈判栈空函数stackempty(seqstack *s) 3)顺序栈置空栈函数seqstack *initstack(seqstack *s) 4)顺序栈入栈函数push(seqstack *s,int x) 5)顺序栈出栈函数pop(seqstack *s) 6)顺序栈取栈顶元素函数gettop(seqstack *s) 7)将十进制数转换为二进制数函数setnum(int num) 各函数间关系如下: 四,详细设计 1,顺序表的结构类型定义: typedef struct{ int data[maxlen]; int top; }seqstack; 2,顺序栈入栈函数的伪代码: void push(seqstack *s,int x){ if(s->top<=maxlen-1&&s->top>=-1){ s->top++; s->data[s->top]=x;} else printf("error");} 3,顺序栈出栈函数的伪代码: void pop(seqstack *s){ if(s->top>=0) s->top--; else printf("error"); } 4,将十进制数转换为二进制数函数伪代码: void setnum(int num){ seqstack s; initstack(&s); while(num){ int k=num%2; push(&s,k); num=num/2;} while(!stackempty(&s)){ int x=gettop(&s); printf("%d",x); pop(&s); } } 五,源代码 #include "stdio.h" #define maxlen 100 typedef struct{ //定义顺序栈的结构类型 int data[maxlen]; int top; }seqstack; int stackempty(seqstack *s){ //顺序栈判栈空算法if(s->top>=0) return 0; else return 1; } seqstack *initstack(seqstack *s){ //顺序栈置空栈算法s->top=-1; return s; }数据结构实验三(顺序栈的基本操作)
数据结构实验报告3--链串
数据结构实验答案1
数据结构实验报告
数据结构_实验六_报告
数据结构 实验报告三
数据结构实验报告
数据结构_实验三_栈和队列及其应用
数据结构实验
数据结构实验六
数据结构实验三
数据结构实验3二叉树
数据结构实验六 图的应用及其实现
数据结构实验3
(精选)云南大学软件学院数据结构实验3
数据结构实验报告及心得体会
数据结构实验六 堆栈实验