《数据结构》课程实验指导
《数据结构》实验教学大纲
课程代码：0806523006开课学期：3 开课专业：信息管理与信息系统
总学时/实验学时：64/16 总学分/实验学分：3.5/0.5
一、课程简介
数据结构是计算机各专业的重要技术基础课。在计算机科学中，数据结构不仅是一般程序设计的基础，而且是编译原理、操作系统、数据库系统及其它系统程序和大型应用程序开发的重要基础。数据结构课程主要讨论各种主要数据结构的特点、计算机内的表示方法、处理数据的算法以及对算法性能的分析。通过对本课程的系统学习使学生掌握各种数据结构的特点、存储表示、运算的原理和方法，学会从问题入手，分析研究计算机加工的数据结构的特性，以便为应用所涉及的数据选择适当的逻辑结构、存储机构及其相应的操作算法，并初步掌握时间和空间分析技术。另一方面，本课程的学习过程也是进行复杂程序设计的训练过程，通过对本课程算法设计和上机实践的训练，还应培养学生的数据抽象能力和程序设计的能力。
二、实验的地位、作用和目的
数据结构是一门实践性较强的基础课程，本课程实验主要是着眼于原理和应用的结合，通过实验，一方面能使学生学会把书上学到的知识用于解决实际问题，加强培养学生如何根据计算机所处理对象的特点来组织数据存储和编写性能好的操作算法的能力，为以后相关课程的学习和大型软件的开发打下扎实的基础。另一方面使书上的知识变活，起到深化理解和灵活掌握教学内容的目的。
三、实验方式与基本要求
实验方式是上机编写完成实验项目指定功能的程序，并调试、运行，最终得出正确结果。具体实验要求如下：
1.问题分析
充分地分析和理解问题本身，弄清要求，包括功能要求、性能要求、设计要求和约束，以及基本数据特性、数据间联系等等。
2.数据结构设计
针对要解决的问题，考虑各种可能的数据结构，并且力求从中选出最佳方案（必须连同算法实现一起考虑），确定主要的数据结构和全程变量。对引入的每种数据结构和全程变量要详细说明其功用、初值和操作的特点。
3.算法设计
算法设计分概要和详细设计。概要设计着重解决程序的模块设计问题，这包括考虑如何把被开发的问题程序自顶向下分解成若干程序模块，并决定模块的接口，即模块间的相互关系以及模块之间的信息交换问题。详细设计则要决定每个模块内部的具体算法，包括输入、处理和输出。
4.测试用例设计
准备典型测试数据和测试方案。测试数据要有代表性、敏感性。测试方案包括模块测试
和模块集成测试。
5.上机调试
对程序进行编译，纠正程序中可能出现的语法错误。调试前，先运行一遍程序看看究竟将会发生什么。如果情况很糟，则根据事先设计的测试方案并结合现场情况进行错误跟踪，包括打印执行路径或输出中间变量值等手段。
6. 程序性能分析
在运行结果正确的前提下再分析程序中主要算法是否具有较好的时间复杂度和空间复杂度。如果没有，则通过改变数据结构或操作方法使编写的程序性能达到最佳。
7. 实验总结
每个实验完成后要认真书写实验报告，对程序运行的结构，要认真分析，总结每次实验项目的体会与收获。
四、报告与考核
每个实验都要求学生根据上机内容写出实验报告，报告要求包括以下七个方面的内容：1．实验目的；
2．实验内容；
3．实验要求；
4．算法设计；
5．详细程序清单；
6．程序运行结果；
7．实验心得体会。
考核方式：
每个实验项目根据以下两个方面进行考核：
1．指导教师随堂抽查学生的实验过程（包括实验预习、实验出勤、实验结果的测试），并根据抽查结果评定学生成绩，此成绩占此实验总成绩的70%；
2．学生编写课程设计实验报告，每位学生按照实验报告的内容和要求编写详细的实验报告并打印上交给指导老师，由指导老师根据每位学生的完成情况评定成绩，此成绩占实验总成绩的30%。
五、设备及器材材料配置
硬件：奔腾以上PC机
软件：TURBO C、C++或Java
六、实验指导书及主要参考书
[1]朱蓉.数据结构实验指导书
[2]张铭.数据结构与算法.高教出版社.2008.6
[3]张铭.数据结构与算法－－学习指导与习题解析. 高教出版社.2009
[4]耿国华等数据结构-C语言描述. 高教出版社.2005.7
[5]刘怀亮. 数据结构(C语言描述) .冶金出版社.2005.2
[6]刘怀亮. 数据结构(C语言描述)习题与实验指导导.冶金出版社.2005.2
[7]蔡子经，施伯乐.数据结构教程.上海:复旦大学出版社.1994
[8]严蔚敏,吴伟民.数据结构(C语言版).北京：清华大学出版社.1999；
[9]严蔚敏,吴伟民.数据结构题集(C语言版).北京：清华大学出版社.1999；
[10]徐孝凯.数据结构课程实验.北京：清华大学出版社.2002；
[11]孟佳娜,胡潇琨.算法与数据结构实验与习题.北京：机械工业出版社.2004.
七、实验项目与内容提要
实验B01: 顺序表的操作实验
一、实验名称和性质
二、实验目的
1．掌握线性表的顺序存储结构的表示和实现方法。
2．掌握顺序表基本操作的算法实现。
3．了解顺序表的应用。
三、实验内容
1．建立顺序表。
2．在顺序表上实现插入、删除和查找操作（验证性内容）。
3．删除有序顺序表中的重复元素（设计性内容）。
4．完成一个简单学生成绩管理系统的设计（应用性设计内容）。
四、实验的软硬件环境要求
硬件环境要求：
PC机（单机）
使用的软件名称、版本号以及模块：
Windows环境下的TurboC2.0以上或VC++等。
五、知识准备
前期要求熟练掌握了C语言的编程规则、方法和顺序表的基本操作算法。
六、验证性实验
1．实验要求
编程实现如下功能：
（1）根据输入顺序表的长度n和各个数据元素值建立一个顺序表，并输出顺序表中各元素值，观察输入的内容与输出的内容是否一致。
（2）在顺序表的第i个元素之前插入一个值为x的元素，并输出插入后的顺序表中各元素值。
（3）删除顺序表中第i个元素，并输出删除后的顺序表中各元素值。
（4）在顺序表中查找值为e的数据元素，如果查找成功，则显示“查找成功”和该元素在顺序表中的位置，否则显示“查找失败”。
2. 实验相关原理：
线性表的顺序存储结构称为顺序表，顺序表的存储结构描述为：
#define MAXLEN 30 /*线性表的最大长度*/
typedef struct
{ Elemtype elem[MAXLEN]; /*顺序表中存放元素的数组，其中elemtype为抽象数据类型，在程序具体实现时可以用任意类型代替*/
int length; /*顺序表的长度，即元素个数*/
}Sqlist; /*顺序表的类型*/
【核心算法提示】
1．顺序表插入操作的基本步骤：要在顺序表中的第i个数据元素之前插入一个数据元素x,首先要判断插入位置i是否合法，假设线性表的表长为n，则i的合法值范围：1≤i≤n+1，若是合法位置，就再判断顺序表是否满，如果满，则增加空间或结束操作，如果不满，则将第i个数据元素及其之后的所有数据元素都后移一个位置，此时第i个位置已经腾空，再将待插入的数据元素x插入到该位置上，最后将线性表的表长增加1。
2．顺序表删除操作的基本步骤：要删除顺序表中的第i个数据元素，首先仍然要判断i 的合法性，i 的合法范围是1≤i≤n，若是合法位置，则将第i个数据元素之后的所有数据元素都前移一个位置，最后将线性表的表长减1。
3．顺序表查找操作的基本步骤：要在顺序表中查找一个给定值为e的数据元素，则可以采用顺序查找的方法，从顺序表中第1个数据元素开始依次将数据元素值与给定值e进行比较，若相等则查找成功，函数返回该数据元素在顺序表中的位置，若顺序表中所有元素都与给定值e不相片，则查找失败，函数返回0值。
【核心算法描述】
status Sqlist_insert(Sqlist &L,int i,Elemtype x)
/*在顺序表L中第i个元素前插入新元素x*/
{ if (i<1||i>L.length+1) return ERROR; /*插入位置不正确则出错*/
if (L.length>=MAXLEN) return OVERFLOW;
/*顺序表L中已放满元素，再做插入操作则溢出*/
for(j=L.length-1;j>=i-1;j--)
L.elem[j+1]=L.elem[j];/*将第i个元素及后续元素位置向后移一位*/
L.elem[i-1]=x; /*在第i个元素位置处插入新元素x*/
L.length++; /*顺序表L的长度加1*/
return OK;
}
status Sqlist_delete(Sqlist &L,int i,Elemtype &e)
/*在顺序表L中删除第i个元素*/
{ if (i<1||i>L.length) return ERROR; /*删除位置不正确则出错*/
for(j=i;j<=L.length-1;j++)
L.elem[j-1]=L.elem[j]; /*将第i+1个元素及后继元素位置向前移一位*/
L.length--; /*顺序表L的长度减1*/
return OK；
}
int Sqlist_search(Sqlist L,Elemtype x)
/* 在顺序表中查找值为x的元素，如果找到，则函数返回该元素在顺序表中的位置，否则返回0*/ { for (i=1;i<=L.length&&L.elem[i-1]!=x;i++);
/*从第一个元素开始依次将每个元素值与给定值x比较*/
if (i<=L.length)
return i;
else
return o;
}
3．源程序代码参考
#include
#define MAXLEN 50
typedef struct{int elem[MAXLEN];
int length;}Sqlist;
Sqlist Sqlist_insert(Sqlist L,int i,int x) /*顺序表插入函数*/
{int j;
if(i<1||i>L.length+1)
printf("ERROR!");
else if(L.length>=MAXLEN)
printf("OVERFLOW!");
else { for(j=L.length-1;j>=i-1;j--)
L.elem[j+1]=L.elem[j];
L.elem[i-1]=x;
L.length++;
}
return L;
}
Sqlist Sqlist_delete(Sqlist L,int i) /*顺序表删除函数*/
{int j;
if(i<1||i>L.length) printf("ERROR!");
else { for(j=i;j<=L.length-1;j++)
L.elem[j-1]=L.elem[j];
L.length--;
}
return L;
}
int Sqlist_search(Sqlist L,int x)/* 顺序表查找函数*/
{ int i;
for (i=1;i<=L.length&&L.elem[i-1]!=x;i++);
if (i<=L.length)
return i;
else
return 0;
}
void Sqlist_display(Sqlist L) /*顺序表元素输出函数*/
{ int j;
for(j=0;j<=L.length-1;j++)
printf("%4d ",L.elem[j]);
printf("\n");
}
void main() /*主函数 */
{ Sqlist L;
int i,x,j;
printf("\nplease input the length:");/*请求输入顺序表中元素个数*/
scanf("%d",&L.length);
printf("please input the Value:\n");/*请求输入顺序表中各个元素*/
for(j=0;j<=L.length-1;j++)
scanf("%d",&L.elem[j]);
printf("please input the insert position:"); /*请求输入插入操作位置*/
scanf("%d",&i);
printf("please input the insert node:");/*请求输入需要插入的新元素*/
scanf("%d",&x);
L=Sqlist_insert(L,i,x);/*调用顺序表插入函数*/
Sqlist_display(L);/*调用顺序表元素输出函数*/
printf("please input the delete position:");/*请求输入删除操作位置*/
scanf("%d",&i);
L=Sqlist_delete(L,i);/*调用顺序表删除函数*/
Sqlist_display(L);/*调用顺序表元素输出函数*/
printf("please input the search node:");
scanf("%d",&x);
if (Sqlist_search(L,x)) /*如果查找成功，则显示查找成功和找到的元素位置，否则显示查
找不成功*/
printf(" search is success and %d is %d position\n",x,Sqlist_search(L,x));
else
printf(" search is unsuccess\n");
}
4．运行结果参考如图1-1所示：
图1-1: 验证性实验运行结果
七、设计性实验
编程实现删除有序顺序表中的所有重复元素，即使有序顺序表中相同的元素只保留一个。
⑴实验要求
①根据输入的n个非递减的有序数据建立一个有序顺序表，并输出有序顺序表中各元素值。
②删除有序顺序表中所有的重复元素，并显示删除后的有序顺序表中各元素值。
⑵核心算法提示
要在有序顺序表中删除重复的元素，首先就要抓住有序顺序表的特性：重复的元素总是在相邻的位置上，如：12，15，15，15，35，56，56，78。则删除重复元素后所得的有序表为：12，15，35，56，78。下面给出大致的操作步骤：从第 1 个元素开始，依次将它与后面相邻的元素进行比较，如果相等则将前面那个相等的元素从顺序表中删除；如果不相等，则继续往下比较，如此重复，直到最后一个元素为止。
⑶核心算法描述
Sqlist delSqlist(Sqlist L)
{int i=0,j;
while(i if (L.elem[i]==L.elem[i+1]) /*相邻的两个元素比较相等*/ { for (j=i+1;j L.elem[j-1]=L.elem[j]; L.length--; /*有序顺序表的表长减1*/ } else i++; return L; } 八、应用性设计实验 编程实现一个简单学生成绩表的操作。 实验要求 此系统的功能包括： ①查询：按特定的条件查找学生 ②修改：按学号对某个学生的某门课程成绩进行修改 ③插入：增加新学生的信息 ④删除：按学号删除已退学的学生的信息。 学生成绩表的数据如下： 要求采用顺序存储结构来实现对上述成绩表的相关操作。 实验B02: 链表的操作实验 一、实验名称和性质 二、实验目的 1．掌握线性表的链式存储结构的表示和实现方法。 2．掌握链表基本操作的算法实现。 三、实验内容 1．建立单链表，并在单链表上实现插入、删除和查找操作（验证性内容）。 2．建立双向链表，并在双向链表上实现插入、删除和查找操作（设计性内容）。 3．计算已知一个单链表中数据域值为一个指定值x的结点个数（应用性设计内容）。 四、实验的软硬件环境要求 硬件环境要求： PC机（单机） 使用的软件名称、版本号以及模块： Windows环境下的TurboC2.0以上或VC++ 等。 五、知识准备 前期要求熟练掌握了C语言的编程规则、方法和单链表和双向链表的基本操作算法。 六、验证性实验 1．实验要求 编程实现如下功能： （1）根据输入的一系列整数，以0标志结束，用头插法建立单链表，并输出单链表中各元素值，观察输入的内容与输出的内容是否一致。 （2）在单链表的第i个元素之前插入一个值为x的元素，并输出插入后的单链表中各元素值。 （3）删除单链表中第i个元素，并输出删除后的单链表中各元素值。 （4）在单链表中查找第i个元素，如果查找成功，则显示该元素的值，否则显示该元素不存在。 2. 实验相关原理： 线性表的链式储结构是用一组任意的存储单元依次存放线性表中的元素，这组存储单元可以是连续的，也可以是不连续的。为反映出各元素在线性表中的前后逻辑关系，对每个数据元素来说，除了存储其本身数据值之外，还需增加一个或多个指针域，每个指针域的值称为指针，又称作链，它用来指示它在线性表中的前驱或后继的存储地址。这两个部分的的一起组成一个数据元素的存储映像，称为结点，若干个结点链接成链表。如果一个结点中只含 一个指针的链表，则称单链表。单链表的存储结构描述如下： typedef struct Lnode { Elemtype data;/*数据域*/ struct Lnode *next;/*指针域*/ }LNODE,*Linklist; /*其中LNODE为结点类型名，Linklist为指向结点的指针类型名*/ 【核心算法提示】 1．链表建立操作的基本步骤：链表是一个动态的结构，它不需要予分配空间，因此建立链表的过程是一个结点“逐个插入”的过程。先建立一个只含头结点的空单链表，然后依次生成新结点，再不断地将其插入到链表的头部或尾部，分别称其为“头插法”和“尾插法”。 2．链表查找操作的基本步骤：因链表是一种"顺序存取"的结构，则要在带头结点的链表中查找到第i个元素，必须从头结点开始沿着后继指针依次"点数"，直到点到第i 个结点为止,如果查找成功，则用e返回第i个元素值。头结点可看成是第0个结点。 3．链表插入操作的基本步骤：先确定要插入的位置，如果插入位置合法，则再生成新的结点，最后通过修改链将新结点插入到指定的位置上。 4．链表删除操作的基本步骤：先确定要删除的结点位置，如果位置合法，则再通过修改链使被删结点从链表中“卸下”，最后释放被删结点的空间。 【核心算法描述】 void creat1(Linklist &L) /*输入一系列整数，以0标志结束，将这些整数作为data域并用头 插法建立一个带头结点的单链表的函数*/ { L=(Linklist)malloc(sizeof(LNODE));/*生成头结点*/ L->next=NULL;/*头结点的指针域初始为空*/ scanf("%d",&node); while(node!=0) { p=(Linklist)malloc(sizeof(LNODE));/*为一个新结点的分配空间*/ p->data=node; /*为新结点数据域赋值*/ p->next=L->next;/*新结点指针域指向开始结点*/ L->next=p; /*头结点指针域指向新结点，即新结点成为开始结点*/ scanf("%d",&node); } } void creat2(Linklist &L) /*输入一系列整数，以0标志结束，将这些整数作为data域并用尾插 法建立一个带头结点的单链表的函数*/ { L=(Linklist)malloc(sizeof(LNODE));/*为头结点分配空间*/ L->next=NULL; /*头结点的指针域初始为空*/ r=L; /*尾指针初始指向头结点*/ scanf("%d",&node); while(node!=0) { p=(Linklist)malloc(sizeof(LNODE));/*为一个新结点分配空间*/ p->data=node; /*新结点数据域赋值*/ p->next=NULL; /*新结点指针域为空*/ r->next=p;/*尾结点指针域指向新结点*/ r=p; /*尾指针指向新结点，即新结点成为尾结点*/ scanf("%d",&node); } } status list_search(Linklist L, int i;Elemtype &e) /*在带头结点的单链表L中查找第i个元素，如果查找成功则用e返回其值*/ { p=L->next; /*使指针p指向第1个元素结点*/ j=1; /*计数器赋初值为1*/ while (p&& j { p=p->next; j++; } if (!p&& j>i) return ERROR; /*如果i值不合法，即i值小于1或大于表长，则出错*/ e=p->data; /*如果第i个元素存在，则将该元素值赋给e*/ return OK; } status list_insert(Linklist &L,int i;Elemtype x) /*在带头结点的单链表L中第i个位置之前插入新元素x*/ { p=L; j=0; while(p!=NULL&&j 个位置*/ { p=p->next; ++j; } if(p==NULL||j>i-1) return ERROR; /*若位置不正确,即i小于1或大于表的长度加1，则出错*/ s=(Linklist)malloc(sizeof(LNODE)); /*分配一个新结点的空间*/ s->data=x; /*为新结点数据域赋值*/ /*下面两条语句就是完成修改链，将新结点s插入到p结点之后*/ s->next=p->next; /*新结点指针域指向p的后继结点*/ p->next=s; /*新结点成为p的后继结点*/ return OK; } status list_delete(Linklist &L,int i,Elemtype &x) /*在带头结点的单链表L中，删除第i个元素结点,并用x返回其值*/ { p=L;j=0; while(p->next!=NULL&&j { p=p->next; ++j; } if (p->next==NULL||j>i-1) return ERROR; /*若位置不正确，即i小于1或大于表长，则出错*/ q=p->next; /* q指向p的后继结点*/ p->next=q->next; /*q的后继结点成为p的后继结点*/ x=q->data; /*用x返回第i个位置的元素*/ free(q); /*释放q所指的被删结点的空间*/ return OK; } 3．源程序代码参考 #include #include typedef struct Lnode { int data; struct Lnode *next; } LNODE,*Linklist; Linklist creat(Linklist L) /*单链表建立函数*/ {int node; Linklist p; L=(Linklist)malloc(sizeof(LNODE)); L->next=NULL; printf("\nplease input the node(end with 0):\n "); /*请求输入线性表中各个元素，以0结束*/ scanf("%d",&node); while(node!=0) {p=(Linklist)malloc(sizeof(LNODE)); if (!p) exit(); p->data=node; p->next=L->next; L->next=p; scanf("%d",&node); } return L; } Linklist insert(Linklist L,int i,int x) /*单链表插入函数*/ { int j;Linklist p,s; p=L; j=0; while (p!=NULL&&j { p=p->next; ++j; } if (p==NULL||j>i-1) printf("\n ERROR position!\n"); else { s=(Linklist)malloc(sizeof(LNODE)); s->data=x; s->next=p->next; p->next=s; } return L; } Linklist delete(Linklist L,int i) /*单链表删除函数*/ { int j,x; Linklist p,q; p=L; j=0; while(p->next!=NULL&&j {p=p->next; ++j; } if(p->next==NULL||j>i-1) printf("\n ERROE position!\n"); else { q=p->next; p->next=q->next; x=q->data; printf("the delete data is:%d\n",x); free(q); } return L; } int search(Linklist L, int i) /*单链上的查找函数*/ { Linklist p; int j; p=L->next; j=1; while (p&& j { p=p->next; j++; } if (!p&& j>i) return 0; /*如果i值不合法，即i值小于1或大于表长，则函数返回0值*/ else return(p->data); /*否则函数返回第i个元素的值*/ } void display(Linklist L) /*单链表元素输出函数*/ { Linklist p; p=L->next; while(p!=NULL) { printf("%4d",p->data); p=p->next; } printf("\n"); } main()/*主函数*/ {Linklist L=NULL; int i,x; L=creat(L);/*调用单链表建立函数*/ printf("the Linklist is:\n"); display(L); /*调用单链表元素输出(遍历)函数*/ printf("please input the position you want to insert:");/*请求输入插入操作位置*/ scanf("%d",&i); printf("please input the node you want to insert:");/*请求输入需要插入的元素*/ scanf("%d",&x); L=insert(L,i,x);/*调用单链表插入函数*/ printf("the Linklist after inserted is:\n"); display(L);/*调用单链表元素输出(遍历)函数*/ printf("please input the node position you want to delete:"); /*请求输入删除操作位置*/ scanf("%d",&i); L=delete(L,i); /*调用单链表删除函数*/ printf("the Linklist after deleted is:\n"); display(L); /*调用单链表元素输出(遍历)函数*/ printf("please input the position you want to search:"); /*请求输入待查找元素的位置*/ scanf("%d",&i); x=search(L,i); /*调用单链表查找函数*/ if (x) /*如果查找成功，则显示第i个元素的值，否则显示第i个元素不存在*/ printf(" the %dth elem is %d\n",i,x); else printf(" the %dth elem is not exsit\n"); } 4．运行结果参考如图2-1所示： 图2-1: 验证性实验运行结果 七、设计性实验 1. 编程实现在双向循环链表上的插入、删除和查找操作 ⑴实验要求 （1）输入链表的长度和各元素的值，用尾插法建立双向循环链表，并输出链表中各元素值，观察输入的内容与输出的内容是否一致。 （2）在双向循环链表的第i个元素之前插入一个值为x的元素，并输出插入后的链表中各元素值。 （3）删除双向循环链表中第i个元素，并输出删除后的链表中各元素值。 （4）在双向循环链表中查找值为x元素，如果查找成功，则显示该元素在链表中的位置，否则显示该元素不存在。 ⑵核心算法提示 双向循环链表采用的存储结构描述如下： typedef struct DULNODE { Elemtype data; /*数据域*/ struct DULNODE *prior; /*指向前驱结点的指针域*/ struct DULNODE *next;/*指向后继结点的指针域*/ }DULNODE,*DuLinklist; typedef int Elemtype; 不论是建立双向循环链表还是在双向循环链表中进行插入、删除和查找操作，其操作方法和步骤都跟单链表类似。只不过要注意两点： （1）凡是在操作中遇到有修改链的地方，都要进行前驱和后继两个指针的修改。 （2）单链表操作算法中的判断条件：p= =NULL 或p!=NULL ,在循环链表的操作算法中则需改为：p!= L,其中L为链表的头指针。 ⑶核心算法描述 void DuList_creat (DuLinklist &L,int n) /*输入n个整数（其中n为表长），将这些整数作为data 域并用尾插法建立一个带头结点的双向循环链表的函数*/ { L=( DuLinklist)malloc(sizeof(DULNODE));/*为头结点分配空间*/ L->next=L->prior=L; /*使头结点的后继指针和前驱指针都指向自身，形成空的双向循环链表*/ r=L; /*尾指针初始指向头结点*/ for (i=0;i { p=(DuLinklist)malloc(sizeof(DULNODE));/*为一个新结点分配空间*/ scanf("%d",&p->data); /*从键盘输入值，并保存在新结点数据域中*/ p->next=r->next; /*新结点后继指针指向尾结点r的后继结点*/ p->prior=r; /*新结点的前驱指针指向尾结点r*/ r->next=p; /*尾结点的后继指针指向新结点*/ r=p; /*尾指针指向新结点，即新结点成为尾结点*/ } L->prior=r; /*使尾结点成为头结点的前驱结点*/ } status DuList_search(DuLinklist L, int i;Elemtype &e) /*在带头结点的双向循环链表L中查找第i个元素，如果查找成功则用e返回其值*/ { p=L->next; /*使指针p指向第1个元素结点*/ j=1; /*计数器赋初值为1*/ while (p!=L && j { p=p->next; j++; } if (j!=i) return ERROR; /*如果i值不合法，即i值小于1或大于表长，则出错*/ e=p->data; /*如果第i个元素存在，则将该元素值赋给e*/ return OK; } status DuList_insert(DuLinklist &L,int i;Elemtype x) /*在带头结点的双向循环链表L中第i个位置之前插入新元素x*/ { p=L->next; j=1; while(p!=L &&j ++j; } if(j!=i) return ERROR; /*若位置不正确,即i小于1或大于表的长度加1，则出错*/ s=(DuLinklist)malloc(sizeof(DULNODE)); /*为一个新结点s分配空间*/ s->data=x; /*为新结点数据域赋值*/ /*下面四条语句就是完成修改链，将新结点s插入到p结点之前*/ s->next=p; p->prior->next=s; s->prior=p->prior; p->prior=s; return OK; } status DuList_delete(DuLinklist &L,int i,Elemtype &x) /*在带头结点的双向循环链表L中，删除第i个元素结点，并用x返回其值*/ { p=L->next;j=1; while(p!=L&&j { p=p->next; ++j; } if (j!=i) return ERROR; /*若位置不正确，即i小于1或大于表长，则出错*/ q=p; /*记下被删结点*/ p->prior->next=p->next; /*修改链使得p结点从链中脱离*/ p->next->prior=p->prior; x=q->data; printf("the delete data is:%d\n",x); free(q); //释放被删结点空间 return OK; } 提醒: 请将上述算法与单链表上相应操作的算法对照学习，特别注意它们不相同的地方。 八、应用性设计实验 编写一个程序，计算出一个单链表中数据域值为一个指定值x的结点个数。 实验要求： ⑴从键盘输入若干个整数，以此序列为顺序建立一个不带头结点的单链表； ⑵输出此单链表中的各个数据元素值； ⑶给定一个x的具体整数值，计算并返回此单链表中数据域值为x的结点个数值。 实验B03: 栈的操作实验 一、实验名称和性质 二、实验目的 1．掌握栈的存储结构的表示和实现方法。 2．掌握栈的入栈和出栈等基本操作算法实现。 3．了解栈在解决实际问题中的简单应用。 三、实验内容 1．建立顺序栈，并在顺序栈上实现入栈和出栈操作（验证性内容）。 2．建立链栈，并在链栈上实现入栈和出栈操作（设计性内容）。 3．实现汉诺（Hanoi）塔求解问题（应用性设计内容）。 四、实验的软硬件环境要求 硬件环境要求： PC机（单机） 使用的软件名称、版本号以及模块： Windows环境下的TurboC2.0以上或VC++等。 五、知识准备 前期要求熟练掌握了C语言的编程规则、方法和顺序栈、链栈的基本操作算法。 六、验证性实验 1．实验要求 编程实现如下功能： （1）根据输入的栈中元素个数n和各元素值建立一个顺序栈，并输出栈中各元素值。 （2）将数据元素e入栈，并输出入栈后的顺序栈中各元素值。 （3）将顺序栈中的栈顶元素出栈，并输出出栈元素的值和出栈后顺序栈中各元素值。 2. 实验相关原理： 栈是一种插入和删除操作都限制在表的一端进行的特殊线性表，它的操作具有“先进后出”的特性。采用顺序存储结构的栈称为顺序栈。栈的存储结构描述如下：#define MAXSIZE 100; /*顺序栈的最大长度*/ typedef struct { Selemtype base[MAXSIZE]; /*存储栈中数据元素的数组*/ int top; /*top为栈顶指针，它指示栈顶元素的存储空间的下一个存储单元*/ }Sqstack; 【核心算法提示】 1．顺序栈入栈操作的基本步骤：首先判断顺序栈是否为满，如果满，则函数返回ERROR，否则将待入栈的数据元素存放在top所指示的存储单元中，再使top后移一个存储单元位置，即将top值加1，最后函数返回OK。 2．顺序栈出栈操作的基本步骤：首先判断顺序栈是否为空，如果空，则函数返回ERROR，否则将栈顶指针前移一个存储单元位置，即将top值减1,再将top所指示的栈顶元素用e 返回其值，并使函数返回OK。 【核心算法描述】 status Push(Sqstack &S,Selemtype e) /*将数据元素e压入到顺序栈S中，使其成为新的栈项元素*/ { if (S.top >=MAXSIZE) /*如果栈满，则函数返回ERROR*/ return ERROR; S.base[S.top++]=e;/*将新元素e存放在top所指示的存储单元中,并使top值加1*/ return OK; } status Pop(Sqstack &S,Selemtype &e) /*将顺序栈S中的栈顶元素从栈中删除，并用e返回其值*/ { if (S.top==0) /*如果栈空，则函数返回ERROR*/ Return ERROR; e=S.base[--S.top];/*将top值减1,并用e保存top所指示的栈顶元素值*/ return OK; } 3．源程序代码参考 #define MAXSIZE 100 typedef struct { int base[MAXSIZE]; int top; /*top指示存储栈顶元素的下一存储单元*/ }Sqstack; /*顺序栈的类型定义*/ Sqstack Push(Sqstack S,int e) /*顺序栈的入栈操作函数*/ { if (S.top>=MAXSIZE) printf("Stack is Overflow\n"); else S.base[S.top++]=e; return S; } Sqstack Pop(Sqstack S,int *e) /*顺序栈的出栈操作函数*/ { if (S.top==0) printf("Stack is Empty\n"); else 《数据结构》实验指导书 郑州轻工业学院 2016.02.20 目录 前言 (3) 实验01 顺序表的基本操作 (7) 实验02 单链表的基本操作 (19) 实验03 栈的基本操作 (32) 实验04 队列的基本操作 (35) 实验05 二叉树的基本操作 (38) 实验06 哈夫曼编码 (40) 实验07 图的两种存储和遍历 (42) 实验08 最小生成树、拓扑排序和最短路径 (46) 实验09 二叉排序树的基本操作 (48) 实验10 哈希表的生成 (50) 实验11 常用的内部排序算法 (52) 附：实验报告模板 .......... 错误！未定义书签。 前言 《数据结构》是计算机相关专业的一门核心基础课程，是编译原理、操作系统、数据库系统及其它系统程序和大型应用程序开发的重要基础，也是很多高校考研专业课之一。它主要介绍线性结构、树型结构、图状结构三种逻辑结构的特点和在计算机内的存储方法，并在此基础上介绍一些典型算法及其时、空效率分析。这门课程的主要任务是研究数据的逻辑关系以及这种逻辑关系在计算机中的表示、存储和运算，培养学生能够设计有效表达和简化算法的数据结构，从而提高其程序设计能力。通过学习，要求学生能够掌握各种数据结构的特点、存储表示和典型算法的设计思想及程序实现，能够根据实际问题选取合适的数据表达和存储方案，设计出简洁、高效、实用的算法，为后续课程的学习及软件开发打下良好的基础。另外本课程的学习过程也是进行复杂程序设计的训练过程，通过算法设计和上机实践的训练，能够培养学生的数据抽象能力和程序设计能力。学习这门课程，习题和实验是两个关键环节。学生理解算法，上机实验是最佳的途径之一。因此，实验环节的好坏是学生能否学好《数据结构》的关键。为了更好地配合学生实验，特编写实验指导书。 一、实验目的 本课程实验主要是为了原理和应用的结合，通过实验一方面使学生更好的理解数据结构的概念 《C语言》实验指导书 2016年１0月 实验一Ｃ程序得运行环境与运行方法 一、实验目得 1。掌握所用得C语言环境得基本操作方法、 2.掌握编辑、编译、连接与运行C程序。 二、实验内容与要求 1、学习使用Viｓual C＋＋6.0环境开发C程序。 (1)在磁盘上建立自己得文件夹,用于存放C程序,如“e:\cexam”。 (2)启动Ｖisｕal C＋＋６。０、执行“开始”-—“所有程序”——“Miｃrosoft Ｖisual Ｓtｕdｉo 6。０"——“Miｃrosoft Ｖｉsual Stｕdｉo ６.0”命令,进入VC++编程环境,如图1 所示。 图1 MｉcrosｏfｔVisual Studiｏ6、0窗口 (3)新建C 程序文件。 执行“文件”——“新建”命令,单击如图2所示得“文件”选项卡,选中“C++So ｕrcｅFile”; 图 2 新建文件 在“文件”文本框中输入文件名test1, 则C源程序被命名为tesｔ1。cｐp,若想指定扩展名为.c,则需在“文件”文本框中输入文件名ｔest1.c;在“目录”下拉列表框选择已经建立得文件夹,如,单击“确定”按钮,就新建了Ｃ源程序文件,并显示编辑窗口与信息窗口,如图3所示,然后在编辑窗口中输入程序。 (4)保存程序。 在如图3得界面输入程序代码。由于完全就是Wｉndows 界面,输入及修改可借助鼠标与菜单进行,十分方便。当输入结束后,执行“文件”——“保存”命令,保存源文件。 图３编辑源程序(5)编译程序。信息窗口编辑窗口 执行“组建”--“编译［test１、cｐp］”命令,弹出消息框,如图4所示,单击“就是"按钮,开始编译,并在信息窗口中显示编译信息。如果信息窗口中显示“test1.obｊ-0ｅｒror(s),0 waｒniｎg(ｓ)",表示编译正确,没有发现错误与警告,并生成了目标文件ｔest1、oｂj、 图４产生工作区消息框 如果显示错误信息,说明程序中存在严重得错误,必须改正,双击某行出错信息,程序窗口中会指示对应出错位置,根据信息窗口得提示分别予以纠正;如果显示警告信息,说明这些错误并未影响目标文件得生成,但通常也应该改正。 (6)连接程序。 执行“组建”——“组建[tｅst1.exe］”命令,开始连接,并在信息窗口中显示连接信息、如果信息窗口中出现“test１.ｅxｅ—0 error(ｓ),0 warｎiｎg(ｓ)”,表示连接成功, 并生成了可执行文件tｅｓt1、eｘe。 (7)运行程序。 执行“组建"——“执行［tｅsｔ１、exe]”命令,自动弹出运行窗口,如图５所示,显示运行结果。其中“Ｐｒesｓａｎy key to ｃontinｕe”提示用户按任意键退出运行窗口,返回到VＣ＋＋编辑窗口。 图 5 显示运行结果 (8)关闭程序工作区。 当一个程序编译连接后,VC++系统自动产生相应得工作区,以完成程序得运行与调试。若想执行第二个程序时,必须关闭前一个程序得工作区,然后通过新得编译连接,产生第二个程序得工作区。否则得话运行得将一直就是前一个程序。 执行“文件"--“关闭工作区命令",弹出得对话框如图 6所示,单击“就是”按钮,关闭工作区。 图 6 关闭所有文档窗口 (9)打开文件、 如果要再次打开C源文件,可以执行“文件”——“打开”命令,在查找范围中找到 《数据结构》实验指导 (计算机信息大类适用) 实验报告至少包含以下内容： 实验名称 实验目的与要求: 实验内容与步骤（需要你进行细化）: 实验结果（若顺利完成，可简单说明；若实验过程中遇到问题，也请在此说明） 收获与体会（根据个人的实际情况进行说明，不得空缺） 实验1 大整数加法（8课时） 目的与要求： 1、线性表的链式存储结构及其基本运算、实现方法和技术的训练。 2、单链表的简单应用训练。 3、熟悉标准模版库STL中的链表相关的知识。 内容与步骤: 1、编程实现单链表的基本操作。 2、利用单链表存储大整数（大整数的位数不限）。 3、利用单链表实现两个大整数的相加运算。 4、进行测试，完成HLOJ(https://www.doczj.com/doc/5d3902844.html,) 9515 02-线性表大整数A+B。 5、用STL之list完成上面的任务。 6、尝试完成HLOJ 9516 02-线性表大菲波数。 实验2 栈序列匹配（8课时） 目的与要求 1、栈的顺序存储结构及其基本运算、实现方法和技术的训练。 2、栈的简单应用训练。 3、熟悉标准模版库STL中的栈相关的知识。 内容与步骤: 1、编程实现顺序栈及其基本操作。 2、对于给出的入栈序列和出栈序列，判断2个序列是否相容。即：能否利用栈 将入栈序列转换为出栈序列。 3、进行测试，完成HLOJ 9525 03-栈与队列栈序列匹配。 4、用STL之stack完成上面的任务。 5、尝试完成HLOJ 9522 03-栈与队列胡同。 实验3 二叉排序树（8课时） 目的与要求 1、二叉树的链式存储结构及其基本运算、实现方法和技术的训练。 2、二叉树的遍历方法的训练。 3、二叉树的简单应用。 内容与步骤: 1、编程实现采用链式存储结构的二叉排序树。 2、实现插入节点的操作。 3、实现查找节点的操作（若查找失败，则将新节点插入二叉排序树）。 4、利用遍历算法对该二叉排序树中结点的关键字按递增和递减顺序输出，完成 HLOJ 9576 07-查找二叉排序树。 5、尝试利用二叉排序树完成HLOJ 9580 07-查找Let the Balloon Rise。 实验4 最小生成树（8课时） 目的与要求 1、图的邻接矩阵存储结构及其相关运算的训练。 2、掌握最小生成树的概念。 3、利用Prim算法求解最小生成树。 实验背景： 给定一个地区的n个城市间的距离网，用Prim算法建立最小生成树，并计算得到的最小生成树的代价。要求显示得到的最小生成树中包括了哪些城市间的道路，并显示得到的最小生成树的代价。 内容与步骤: 1、建立采用邻接矩阵的图。 2、编程实现Prim算法，求解最小生成树的代价。 3、尝试利用Prim算法完成：HLOJ 9561 06-图最小生成树。 《数据结构》实验指导书 实验一顺序表 实验目的： 熟悉顺序表的逻辑特性、存储表示方法和顺序表的基本操作。 实验要求： 了解并熟悉顺序表的逻辑特性、存储表示方法和顺序表的基本操作的实现和应用。 实验内容： 1、编写程序实现在线性表中找出最大的和最小的数据元素，并符合下列要求： （1）设数据元素为整数，实现线性表的顺序存储表示。 （2）从键盘输入10个数据元素，利用顺序表的基本操作建立该表。 （3）利用顺序表的基本操作，找出表中最大的和最小的数据元素（用于比较的字段为整数）。 2、编写一个程序实现在学生成绩中找出最高分和最低分，并符合下列要求： （1）数据元素为学生成绩（含姓名、成绩等字段）。 （2）要求尽可能少地修改第一题的程序来得到此题的新程序，即要符合第一题的所有要求。（这里用于比较的字段为分数） 实验二链表 实验目的： 熟悉链表的逻辑特性、存储表示方法的特点和链式表的基本操作。 实验要求： 了解并熟悉链式表的逻辑特性、存储表示方法和链式表的基本操作的实现和应用。 实验内容： 1、编写一个程序建立存放学生成绩的有序链表并实现相关操作，要求如下： （1）设学生成绩表中的数据元素由学生姓名和学生成绩字段组成，实现这样的线性表的链式存储表示。 （2）键盘输入10个（或若干个，特殊数据来标记输入数据的结束）数据元素，利用链表的基本操作建立学生成绩单链表，要求该表为有序表 并带有头结点。（用于比较的字段为分数）。 （3）输入关键字值x，打印出表中所有关键字值<=x的结点。（用于比较的关键字字段为分数）。 （4）输入关键字值x，删除表中所有关键字值<=x的结点。（用于比较的关键字字段为分数）。 （5）输入关键字值x，并插入到表中，使所在的链表仍为有序表。（用于比较的字段为分数）。 实验三栈的应用 实验目的： 熟悉栈的逻辑特性、存储表示方法和栈的基本操作。 实验要求： 了解并熟悉栈的逻辑特性、顺序和链式存储表示方法和栈的基本操作的实现和应用。 实验内容： (1)判断一个表达式中的括号（仅有一种括号，小、中或大括号） 是否配对。编写并实现它的算法。 (2)用不同的存储方法，求解上面的问题。 (3)* 若表达式中既有小括号，又有大括号（或中括号），且允许 互相嵌套，但不能交叉，写出判断这样的表达式是否合法的算 法。如 2+3*（4-{5+2}*3）为合法；2+3*（4-{5+2 * 3} 、 2+3*（4-[5+2 * 3）为不合法。 内江职业技术学院 上机实验指导书 科目：C语言程序设计 系别：电商学院 班级：15软件1班 教师：王刚 2015—2016学年第一学期 《计算机基础》课程实验指导书 目录 实验一C语言概述 (1) 实验二基本数据类型 (3) 实验三输入输出和算法 (6) 实验四选择和循环结构 (10) 实验五循环结构和函数 (13) 实验六模块化设计 (14) 实验七一维数组和字符串 (18) 实验八多维数组和指针 (20) 实验九指针 (22) 实验十指针和结构体 (23) 实验十一链表和共同体 (26) 实验十二文件 (27) 教材和参考书 1、教材： 《谭浩强、张基温，《C/C++程序设计教程》，高等教育出版社。 2、参考书： （1）《（美）H.M.Deitel,P.J.Deitel著，薛万鹏译，《C程序设计教程》，机械工业出版社。 （2）杨路明，《C语言程序设计教程》，北京邮电大学出版社。 实验一C语言概述 一、实验目的 1、了解所用的计算机系统。 2、了解在该系统上如何进行编辑、编译、连接和运行一个Ｃ程序。 3、通过运行简单的Ｃ程序了解Ｃ程序的特点。 二、实验内容 1、熟悉C语言集成环境。 2、利用C语言集成环境进行编辑、编译、连接和运行一个Ｃ程序。 3、运行一个自己编写的程序,程序的功能是输出两行文字。 三、实验设备及环境 微机若干台，并安装有C语言软件。 四、实验步骤 １、熟悉所用的系统。了解Windows资源管理器的使用方法：文件的查看、复制、运行等方法，C所在目录，文本文件的建立方法。 2、进入C，并新建一个C源程序文件。 3、熟悉C的集成环境，了解各菜单项有哪些子菜单。 4、输入下面的程序，注意区分大小写。 #include 《数据结构》实验指导书 贵州大学 电子信息学院 通信工程 目录 实验一顺序表的操作 (3) 实验二链表操作 (8) 实验三集合、稀疏矩阵和广义表 (19) 实验四栈和队列 (42) 实验五二叉树操作、图形或网状结构 (55) 实验六查找、排序 (88) 贵州大学实验报告 (109) 实验一顺序表的操作 实验学时：2学时 实验类型：验证 实验要求：必修 一、实验目的和要求 1、熟练掌握线性表的基本操作在顺序存储和链式存储上的实现。 2、以线性表的各种操作（建立、插入、删除等）的实现为重点。 3、掌握线性表的动态分配顺序存储结构的定义和基本操作的实现。 二、实验内容及步骤要求 1、定义顺序表类型，输入一组整型数据，建立顺序表。 typedef int ElemType; //定义顺序表 struct List{ ElemType *list; int Size; int MaxSize; }; 2、实现该线性表的删除。 3、实现该线性表的插入。 4、实现线性表中数据的显示。 5、实现线性表数据的定位和查找。 6、编写一个主函数，调试上述算法。 7、完成实验报告。 三、实验原理、方法和手段 1、根据实验内容编程，上机调试、得出正确的运行程序。 2、编译运行程序，观察运行情况和输出结果。 四、实验条件 运行Visual c++的微机一台 五、实验结果与分析 对程序进行调试，并将运行结果进行截图、对所得到的的结果分析。 六、实验总结 记录实验感受、上机过程中遇到的困难及解决办法、遗留的问题、意见和建议等，并将其写入实验报告中。 【附录----源程序】 #include 《C语言程序设计》实验指导书 每次实验（10分）一共100分，最后折合成50分计入最终成绩。 第一次实验（一星期完成） ●内容一：熟悉编译环境和工具 在VS中键入以下的这段程序 1）关键字变色，自动缩近，智能提醒 2）代码风格和注释 3）编译出错，连接出错。修改错误 4）调试，断点，监控变量，进入函数，跳出函数。监控内存，监控堆栈 在linux中键入以下这段程序 1）熟悉VIM程序，gcc编译程序(开两个终端窗口) 2）熟悉GDB调试程序的基本技巧。(list,backstrac; break, watch,delete; next, continue, run; print,set,help) 其中，help命令是一个非常的参考，如果忘记了某条具体的命令，可以随时去参考help命令来得到相关的细节。 3）介绍《鸟歌的私房菜》这本书 ●内容二：登陆https://www.doczj.com/doc/5d3902844.html,网站，在线提交。 1）熟悉基本的提交方法和规则 2）现场演示反作弊程序的效果 ●程序： 输入：两个整数，用空格分隔， 输出：两个整数的和，计算两个整数的和的功能，要求用函数实现，同时如果输入有错误，例如（12 abc）程序能够给出“error input”的提示。 参考输入： 12 33 参考输出： 45 参考输入： 12 abc 参考输出： error input ●思考和扩展（无标准答案） 如果用户输入12 12abc 如何判断并终止程序，输出“error input”的提示 第二次实验（一星期完成） ●内容一：登陆ACM，演示OJ系统 1）介绍这个网站，有兴趣的同学可以去尝试一下（） ●内容二：计算工资/小时程序 1）强制类型转换 2）一共有多少位的算法 3）整形数的溢出，以及针对特定问题，如何解决溢出问题 注意：linux编译下应该加上–lm 开关。 ●程序： 输入：工资数，小时数（整数，空格分隔）。 输出：工资/小时数（精确到小数点后2位），并根据四舍五入取整，然后将取整的数平方后计算一共有几位，后三位分别是什么？ 参考输入： 2345 2 ←input (separate by space) 参考输出： 1172.50 ←average salary 1173 ← round off to integer 7 ← number of digit 0 2 5 ← the last three digit (separate by space) 第三次实验（两星期完成） ●内容一：介绍linux 下的grep，并给出相应的实例。重点介绍下面要用到的四个符号。 ●内容二：正则表达式 ^ 代表字符串开始 . 代表任意字符 $ 代表字符串末尾 《数据结构》课程实验指导 《数据结构》实验教学大纲 课程代码：0806523006开课学期：3 开课专业：信息管理与信息系统 总学时/实验学时：64/16 总学分/实验学分：3.5/0.5 一、课程简介 数据结构是计算机各专业的重要技术基础课。在计算机科学中，数据结构不仅是一般程序设计的基础，而且是编译原理、操作系统、数据库系统及其它系统程序和大型应用程序开发的重要基础。数据结构课程主要讨论各种主要数据结构的特点、计算机内的表示方法、处理数据的算法以及对算法性能的分析。通过对本课程的系统学习使学生掌握各种数据结构的特点、存储表示、运算的原理和方法，学会从问题入手，分析研究计算机加工的数据结构的特性，以便为应用所涉及的数据选择适当的逻辑结构、存储机构及其相应的操作算法，并初步掌握时间和空间分析技术。另一方面，本课程的学习过程也是进行复杂程序设计的训练过程，通过对本课程算法设计和上机实践的训练，还应培养学生的数据抽象能力和程序设计的能力。 二、实验的地位、作用和目的 数据结构是一门实践性较强的基础课程，本课程实验主要是着眼于原理和应用的结合，通过实验，一方面能使学生学会把书上学到的知识用于解决实际问题，加强培养学生如何根据计算机所处理对象的特点来组织数据存储和编写性能好的操作算法的能力，为以后相关课程的学习和大型软件的开发打下扎实的基础。另一方面使书上的知识变活，起到深化理解和灵活掌握教学内容的目的。 三、实验方式与基本要求 实验方式是上机编写完成实验项目指定功能的程序，并调试、运行，最终得出正确结果。具体实验要求如下： 1.问题分析 充分地分析和理解问题本身，弄清要求，包括功能要求、性能要求、设计要求和约束，以及基本数据特性、数据间联系等等。 2.数据结构设计 针对要解决的问题，考虑各种可能的数据结构，并且力求从中选出最佳方案（必须连同算法实现一起考虑），确定主要的数据结构和全程变量。对引入的每种数据结构和全程变量要详细说明其功用、初值和操作的特点。 3.算法设计 算法设计分概要和详细设计。概要设计着重解决程序的模块设计问题，这包括考虑如何把被开发的问题程序自顶向下分解成若干程序模块，并决定模块的接口，即模块间的相互关系以及模块之间的信息交换问题。详细设计则要决定每个模块内部的具体算法，包括输入、处理和输出。 4.测试用例设计 准备典型测试数据和测试方案。测试数据要有代表性、敏感性。测试方案包括模块测试 《数据结构》实验指导书 实验类别：课内实验实验课程名称：数据结构 实验室名称：软件工程实验室实验课程编号：N02070601 总学时：64 学分： 4 适用专业：计算机科学与技术、网络工程、物联网工程、数字媒体专业 先修课程：计算机科学导论、离散数学 实验在教学培养计划中地位、作用： 数据结构是计算机软件相关专业的主干课程，也是计算机软硬件专业的重要基础课程。数据结构课程实验的目的是通过实验掌握数据结构的基本理论和算法，并运用它们来解决实际问题。数据结构课程实验是提高学生动手能力的重要的实践教学环节，对于培养学生的基本素质以及掌握程序设计的基本技能并养成良好的程序设计习惯方面发挥重要的作用。 实验一线性表的应用（2学时） 1、实验目的 通过本实验，掌握线性表链式存储结构的基本原理和基本运算以及在实际问题中的应用。 2、实验内容 建立某班学生的通讯录，要求用链表存储。 具体功能包括： （1）可以实现插入一个同学的通讯录记录； （2）能够删除某位同学的通讯录； （3）对通讯录打印输出。 3、实验要求 （1）定义通讯录内容的结构体； （2）建立存储通讯录的链表结构并初始化； （3）建立主函数： 1）建立录入函数（返回主界面） 2）建立插入函数（返回主界面） 3）建立删除函数（返回主界面） 4）建立输出和打印函数（返回主界面） I）通过循环对所有成员记录输出 II）输出指定姓名的某个同学的通讯录记录 5）退出 实验二树的应用（2学时） 1、实验目的 通过本实验掌握二叉排序树的建立和排序算法，了解二叉排序树在实际中的应用并熟练运用二叉排序树解决实际问题。 2、实验内容 建立一个由多种化妆品品牌价格组成的二叉排序树，并按照价格从低到高的顺序 打印输出。 3、实验要求 （1）创建化妆品信息的结构体； （2）定义二叉排序树链表的结点结构； （3）依次输入各类化妆品品牌的价格并按二叉排序树的要求创建一个二叉排序树链表；（4）对二叉排序树进行中序遍历输出，打印按价格从低到高顺序排列的化妆品品牌信息。 实验三图的应用（2学时） C语言程序设计实验指导书 沈岚岚吕元长编写 桂林电子科技大学信息科技学院 2012.03 前言上机实验的目的和要求 一上机实验的目的 上机实验的目的，绝不仅仅是为了验证教材和讲课的内容，或者验证自己所编程序正确与否。学习程序语言，上机实验的目的如下： 1 加深对讲授内容的理解，尤其是一些语法规定，光靠课堂讲授，既枯燥无味又难以记住，通过多次上机，就能自然、熟练地掌握语法规定。 2 了解和熟悉C语言程序开发环境。熟悉一两种环境（计算机系统的软件和硬件条件），再遇到其他的系统时便会触类旁通，很快学会。 3 学会上机调试程序，也就是善于发现程序中的错误，并且能很快地排除这些错误，使程序能够正确地运行。要真正掌握计算机应用技术，就不仅应当了解和熟悉有关理论和方法，而且要求自己动手实践能力强。 4 在做实验时千万不要在程序通过后就认为万事大吉，完成任务了，应当在通过的程序上做一些调试和修改，看看会得到什么结果。多动脑筋思考，将会对你有很大帮助。 二上机实验前的准备工作 1 了解所用的计算机系统的性能和使用方法； 2 复习和掌握与本实验有关的教学内容； 3 准备好上机所用的程序，切忌自己不思考、不编制程序或抄袭别人的程序； 4 准备好调试和运行时所需的数据。 三上机实验的步骤 1 调出C语言编译系统，进入C语言工作环境； 2 输入自己编制好的程序； 3 检查输入是否有错，及时更正； 4 进行编译和连接； 5 运行程序，分析结果。 四、实验结束，整理实验报告 实验报告应包括以下内容： 1 上机题目； 2 程序清单； 3 运行结果； 4 对结果的分析和本次获得的经验和体会。 五邑大学计算机学院 数据结构实验指导手册 2015年3月 目录 实验一线性表 (1) 1．实验目的 (1) 2．实验内容 (1) 3．解题思路 (1) 实验二栈 (4) 1．实验目的 (4) 2．实验内容 (4) 3．解题思路 (4) 实验三队列 (8) 1．实验目的 (8) 2．实验内容 (8) 3．解题思路 (8) 实验四二叉树 (12) 1．实验目的 (12) 2．实验内容 (12) 3．解题思路 (12) 实验五哈夫曼树 (18) 1．实验目的 (18) 2．实验内容 (18) 3．解题思路 (18) 实验六图的基本存储 (21) 1．实验目的 (21) 2．实验内容 (21) 3．解题思路 (21) 实验七图的应用 (26) 1．实验目的 (26) 2．实验内容 (26) 3．解题思路 (26) 实验八查找 (30) 1．实验目的 (30) 2．实验内容 (30) 3．解题思路 (30) 实验九排序 (32) 1．实验目的 (32) 2．实验内容 (32) 3．解题思路 (32) 说明 (36) 附录实验报告模板 (37) 实验一线性表 1．实验目的 （1）了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系有顺序存储结构和链式存储结构； （2）掌握这两种存储结构的描述方法； （3）掌握线性表的基本操作（查找、插入、删除）； （4）考虑时间和空间复杂度设计算法。 2．实验内容 （1）创建一个顺序表，存放在数组A[N]中，元素的类型为整型，设计算法调整A，使其左边的所有元素小于0，右边的所有元素大于0（要求算法的时间复杂度和空间复杂度均为O(n)）。 （2）建立一个循环单链表，其节点有prior，data和next三个域，其中data为数据域，存放元素的有效信息，next域为指针域，指向后继节点，prior为指针域，它的值为NULL。编写一个算法将此表改为循环双链表。 3．解题思路 （1）如图1-1所示，设立两个工作指针i和j，i由数组的左端向右移动，查找大于等于0的数，j由数组的右端向左端移动，查找小于0的数，然后交换，如图1-2所示，直到i>=j，调整结束。 图1-1 数据结构实验指导书（C语言版） 2017年9月 目录 1、顺序表的实现 (1) 2、链栈的实现 (3) 3、前序遍历二叉树 (5) 4、图的深度优先遍历算法 (7) 5、散列查找 (9) 1、顺序表的实现 1. 实验目的 ⑴掌握线性表的顺序存储结构； ⑵验证顺序表及其基本操作的实现； ⑶理解算法与程序的关系，能够将顺序表算法转换为对应的程序。 2. 实验内容 ⑴建立含有若干个元素的顺序表； ⑵对已建立的顺序表实现插入、删除、查找等基本操作。 3. 实现提示 定义顺序表的数据类型——顺序表结构体SeqList，在SeqList基础上实现题目要求的插入、删除、查找等基本操作，为便于查看操作结果，设计一个输出函数依次输出顺序表的元素。简单起见，本实验假定线性表的数据元素为int型，要求学生： （1）将实验程序调试通过后，用模板类改写； （2）加入求线性表的长度等基本操作； （3）重新给定测试数据，验证抛出异常机制。 4. 实验程序 在编程环境下新建一个工程“顺序表验证实验”，并新建相应文件，文件包括顺序表结构体SeqList的定义，范例程序如下： #define MaxSize 100 /*假设顺序表最多存放100个元素*/ typedef int DataType; /*定义线性表的数据类型，假设为int型*/ typedef struct { DataType data[MaxSize]; /*存放数据元素的数组*/ int length; /*线性表的长度*/ } SeqList; 文件包括建立顺序表、遍历顺序表、按值查找、插入操作、删除操作成员函数的定义，范例程序如下： int CreatList(SeqList *L, DataType a[ ], int n) { if (n > MaxSize) {printf("顺序表的空间不够，无法建立顺序表\n"); return 0;} for (int i = 0; i < n; i++) L->data[i] = a[i]; L->length = n; return 1; } 实验1 C语言初步与编程环境介绍（2学时） 1．目的要求 1）熟悉C语言基本结构， 2）熟悉VC控制台应用程序设计的使用方法。 2．实验内容 （1）创建项目，分别将教材P13和P14程序输入并编译。 （2）下列程序能正确运行吗？如果能，写出运行结果；如果不能，指出错误原因并改正。 Main() { printf("hello\n"); } 附：VC 6.0 环境的使用方法介绍 Microsoft Visual C++ （简称VC）是微软公司生产的基于其Windows系统的软件开发工具。它具有使用灵活，并与32位Windows内核（使用于Windows 95/98/NT/2000）高度兼容的特点，从而被Windows程序员们广泛使用。同时，VC同样可以加工处理C语言程序，与标准的ANSI C语言兼容。VC提供了一种控制台操作方式，本实验课程主要在控制台方式下进行设计运行。 一、什么是控制台程序？ Win32控制台程序(Win32 Console Application)是一类Windows程序，它不使用复杂的图形用户界面，程序与用户交互时通过一个标准的文本窗口，通过标准的输入输出流（I/O Streams）进行。 一个最简单的控制台程序如下： #include 控制台程序按照下面几个步骤进行。 1、打开VC集成开发环境。 双击桌面图标“Microsoft Visual C++ 6.0”，或者从系统菜单“开始”/“程序”/“Microsoft Visual Studio 6.0”/“Microsoft Visual C++ 6.0”(如图1)，打开VC 开发环境（如图2）。 图 1 从开始菜单中打开VC开发环境 图 2 VC开发环境界面 实验一线性表及其应用 实验目的： 1、掌握线性表的顺序存储结构和顺序存储结构中的各种基本操作 2、掌握线性表的链式存储结构和链式存储结构中的各种基本操作 实验内容： 1、建立一个顺序表L＝{21，23，16，45，65，17，31，9}，输出该表中各元素的值，然后在第i＝4的位置插入元素68。 2、建立一个带头接点的单链表，各节点的值为{21，34，2，15，21，7，8}，要求将用户输入的数据按尾插入法来建立相应的单链表。 实验时数： 4学时（第10周和第11周） 实验地点：逸夫楼3320 实验二栈的基本操作 试验目的： 掌握栈的顺序表示及其基本操作 实验内容： 1、写一函数实现栈的建立。 2、分别写两个函数实现入栈和出栈操作。 3、在主函数中分别调用上面的三个函数实现栈的基本操作。 实验时数： 2学时（第12周） 实验三二叉树的基本操作 试验目的： 1、掌握二叉树的建立和存储 2、掌握二叉树的三种遍历方法 实验内容： 1、建立如图所示的二叉树，使用的树的二叉链表存储。 2、写三个函数分别实现二叉树的前序、中序和后序遍历，在主函数中分别调用这三个函数，输出这三种遍历的遍历序列。 实验时数： 3学时（第13周和第14周） 实验四图的广度和深度遍历 试验目的： 1、掌握图的存储方法 2、掌握图的两种遍历方法和图中最短路径算法 实验内容： 假设以一个带权有向图表示某一个区域的公交线路网，图中顶点代表一些区域中的重要场所，弧代表已有的公交线路，弧上的权表示该线路上的票价（或搭乘所需时间），试设计一个交通指南系统，指导前来咨询者以最低的票价或最少的时间从区域中的某一个场所到达另一个场所。 实验时数： 3学时（第14周和第15周） 实验各种排序算法实现 试验目的： 1、掌握各种内部排序算法并能实现 2、了解各种方法的排序过程以及时间复杂度 实验内容： 分别用直接插入排序、冒泡排序、直接选择排序和快速排序对下列序列进行排序{6，46 ，2，5，10，23，18，34，29，55，20}，输出排序后的结果。 实验时数： 4学时（第16周和第17周） 《C语言程序设计》 实 验 指 导 书 华中师范大学信息技术系 二00九年三月 项目一：熟悉C语言的运行环境及简单程序设计 (11) 实验一熟悉C语言的运行环境 实验二c程序初步 (3) 实验三数据类型及输入输出 (5) 实验四运算符与表达式 (8) 项目二：流程控制、指针、数组、模块化程序设计 实验五分支程序设计 (9) 项目六循环程序设计 (11) 项目七函数 (12) 项目八数组 (13) 项目九指针 (15) 项目三：综合程序设计——竞赛编排及优胜排序 （注：每个项目应包含实验学习目标、实验内容、实验原理、实验设备、实验步骤、实验注意事项或实验思考等内容。 基本型实验应有明确的实验学习目标、详细的过程和具体的结果；综合设计型实验应有明确的实验学习目标、可参考的过程和实验结果评价标准） 实验基本要求 1、每次实验前，学生必须预习实验内容，实验程序必须自行编制、自行调试。 2、每次实验，学生都必须提交实验报告，内容包括实验目的、实验内容、实验程序、实验过程（软件的使用、程序的调试）等，见下面的实验报告模版。 3、学生第一次上机时，应在教师机指定文件夹下建立以自己学号+姓名的子文件夹，例如学号为2005683001的学生张三，应在教师机指定文件夹下建立“2005683001张三”的子文件夹，此文件夹就是学生张三存放本课程实验全部文档的文件夹，也是教师评价学生饰演成绩的主要依据。 4、学生每次实验完毕后，都应将实验报告、实验程序等文档上传到教师机自己建立的子文件夹中。 5、学生每次实验，都应该在考勤表上签到。 附 华中师范大学信息技术系c语言程序设计实验报告 实验目的： 实验设备（包括软件）： 实验内容： 实验过程： 实验程序及实验结果： 实验体会： 目录 实验规则 (2) 实验环境 (2) 实验报告要求 (3) 实验一单链表（一） (4) 实验二单链表（二） (5) 实验三栈 (6) 实验四二叉树 (7) 实验五最短路径 (8) 实验六内部排序 (9) 实验规则 为了顺利完成实验教学任务，确保人身、设备的安全，培养严谨、踏实、实事求是的科学作风和爱护国家财产的优良品质，特制定以下实验规则： 1、实验前必须充分预习，完成指定的预习任务。预习要求如下： （1）认真阅读指导书，进行必要的设计与计算。 （2）熟悉实验内容。 （3）预先复习，并按要求编写程序。 （4）未完成预习任务者不得进入实验室。 2、遵守以下纪律： （1）在实验室不得做和实验无关的事情。 （2）进行任课老师指定内容以外的实验，必须经指导教师同意。 （3）遵守纪律，不迟到。 （4）保持实验室内安静、整洁，爱护公物，不许乱写乱画。 实验环境 本实验在386以上的微机上进行，运行环境为VC6.0。 实验报告要求 1、实验题目 2．实验目的 3．实验环境 4．实验内容与完成情况（可以附上自主设计的源程序）5．出现的问题及对问题的解决方案 6．实验思考：（学生对本次实验的收获的总结） 一、实验目的 掌握线性表的链式存储结构及其基本操作。 二、预习要求 1、看懂书上的算法，深入理解链表的物理存储模式和逻辑模式。 2、根据要求，编写程序准备上机调试。 三、实验内容 实现一个简单的学生信息管理系统，该系统的功能有： 1、利用单链表建立学生基本信息表 2、浏览每个学生的信息 3、根据学号查询某个学生的基本信息 4、添加学生信息到单链表中 5、删除一个学生的信息 四、实现提示 设计结点的结构体类型，包括学生的学号、姓名、年龄、性别；要求设计一个简单的菜单界面，根据需要选择所要进行的操作；构造函数，每一个函数实现上述的一个功能。 北京林业大学 实验任务书 备注：实验共分4次，其中实验1――实验3为设计性实验，实验4为综合性实验，具体安排下面一一列出。 北京林业大学 10学年—11学年第 2学期数据结构实验任务书 专业名称：实验学时： 4 课程名称：数据结构任课教师：李冬梅 实验题目：线性表的基本操作 实验环境： Visual C++ 实验目的： 1、掌握线性表的定义； 2、掌握线性表的基本操作，如建立、查找、插入和删除等。 实验内容： 定义一个包含学生信息（学号，姓名，成绩）的的顺序表和链表，使其具有如下功能： (1) 根据指定学生个数，逐个输入学生信息； (2) 逐个显示学生表中所有学生的相关信息； (3) 根据姓名进行查找，返回此学生的学号和成绩； (4) 根据指定的位置可返回相应的学生信息（学号，姓名，成绩）； (5) 给定一个学生信息，插入到表中指定的位置； (6) 删除指定位置的学生记录； (7) 统计表中学生个数。 实验提示： 学生信息的定义： typedef struct { char no[8]; //8位学号 char name[20]; //姓名 int price; //成绩 }Student; 顺序表的定义 typedef struct { Student *elem; //指向数据元素的基地址 int length; //线性表的当前长度 }SqList； 链表的定义： typedef struct LNode{ Student data; //数据域 struct LNode *next; //指针域 }LNode,*LinkList; 实验要求： (1) 程序要添加适当的注释，程序的书写要采用缩进格式。 (2) 程序要具在一定的健壮性，即当输入数据非法时，程序也能适当地做出反应，如插入删除时指定的位置不对等等。 (3) 程序要做到界面友好，在程序运行时用户可以根据相应的提示信息进行操作。 (4) 根据实验报告模板详细书写实验报告,在实验报告中给出链表根据姓名进行查找的算法和插入算法的流程图。 (5) 上传源程序和实验报告到ftp的相应班级所在文件夹。顺序表的源程序保存为SqList.cpp，链表的源程序保存为LinkList.cpp，实验报告命名为：实验报告1.doc。源程序和实验报告压缩为一个文件（如果定义了头文件则一起压缩），按以下方式命名：学号姓名.rar，如070814101薛力.rar。 《数据结构与算法》实验指导书马晓波秦俊平刘利民编 内蒙古工业大学信息工程学院计算机系 2008年9月1日 《数据结构与算法》实验教学大纲 三、实验目的、内容与要求 实验一线性表的创建与访问算法设计(4学时) （一）实验目的 数据结构于算法实验是计算机类本科学生计算机软件知识重要的实验环节，它将使学生从实践上学会用高级语言程序设计、实现复杂的数据结构，为大型软件设计奠定基础。本实验以某种线性表的创建与访问算法设计作为实验内容，举一反三，全面、深刻掌握线性结构的实现方法，培养解决问题的能力。 （二）实验内容 1、编写生成线性表的函数，线性表的元素从键盘输入； 2、编写在线性表中插入元素的函数； 3、编写在线性表中删除元素的函数； 4、编写输出线性表的函数； 5、编写主函数，调用以上各函数，以便能观察出原线性表以及作了插入或删除后线性表的屏 幕输出。 方案一采用顺序存储结构实现线性表。 方案二采用单链表结构实现线性表。 （三）实验要求 1、掌握线性结构的机器内表示； 2、掌握线性结构之上的算法设计与实现； 3、列表对比分析两种数据结构的相应操作的时间复杂度、空间复杂度，阐明产生差异的原因。 实验二二叉树的创建与访问算法设计(4学时) （一）实验目的 本实验以二叉树的创建与访问算法设计作为实验内容，掌握树型结构的实现方法，培养解决负责问题的能力。 （二）实验内容 1、编写生成二叉树的函数，二叉树的元素从键盘输入； 2、编写在二叉树中插入元素的函数； 3、编写在二叉树中删除元素的函数； 4、编写遍历并输出二叉树的函数。 方案一采用递归算法实现二叉树遍历算法。 方案二采用非递归算法实现二叉树遍历算法。 （三）实验要求 1、掌握树型结构的机器内表示； 2、掌握树型结构之上的算法设计与实现； 3、列表对比分析两种数据结构的相应操作的时间复杂度、空间复杂度，阐明产生差异的原因。 实验三图的创建与访问算法设计(4学时) （一）实验目的 本实验以图的创建与访问算法设计作为实验内容，掌握图型结构的实现方法，培养解决负责问题的能力。 （二）实验内容 1、编写生成图的函数，图的元素从文件输入； 2、编写在图中插入元素的函数； 3、编写在图中删除元素的函数； 4、编写遍历并输出图的函数。 方案一采用BFS深度优先搜索算法实现图的遍历。 方案二采用DFS广度优先搜索算法实现图的遍历。 （三）实验要求 1、掌握图结构的机器内表示； 2、掌握图型结构之上的算法设计与实现； 3、列表对比分析两种数据结构的相应操作的时间复杂度、空间复杂度，阐明产生差异的原因。 四、考核方式 1、学生课前要认真阅读实验教材，理解实验内容与相关理论知识的关系，并完成预习报告； 2、实验课上教师讲解实验难点及需要注意的问题，并对实验数据签字； 3、学生课后要完成实验报告，并将签字的实验数据与实验报告交给带课教师； 4、教师根据学生实验情况，及时对实验内容和方法进行必要的调整和改进。 根据实验预习报告、实验课考勤、课上实验能力与实验效果、实验报告的完成情况确定最终的实验成绩，实验成绩占课程总成绩的10%。 五、建议教材与教学参考书 1、建议教材 [1]严蔚敏、吴伟民主编. 数据结构（C语言版）. 北京：清华大学出版社，1997 2、教学参考书 [1] 严蔚敏、吴伟民主编. 数据结构题集（C语言版）. 北京：清华大学出版社，1997 [2] 李春葆编. 数据结构习题与解析. 北京：清华大学出版社，2002 [3] 刘振鹏主编. 数据结构. 北京：中国铁道出版社，2003 [4] 许卓群编．数据结构．北京：中央电大出版社， 2001 [5] Anany Levitin著．潘彦译．算法设计与分析．北京：清华大学出版社， 2004数据结构实验指导书(2016.03.11)
C语言实验指导书
《数据结构》实验指导
数据结构实验指导书
《C语言》实验指导书
2017数据结构实验指导书
C语言实验指导书
《数据结构》实验指导书(C语言版)
《数据结构》实验指导书
C语言实验指导书
数据结构实验指导手册(2015版)
数据结构实验指导书(C版)
C语言实验指导书
数据结构实验指导书
《C语言》实验指导书
数据结构实验指导书
数据结构实验指导书2.
数据结构实验指导书
相关主题
文本预览