数据结构实验讲义课件

《数据结构实验讲义课件》由会员分享，可在线阅读，更多相关《数据结构实验讲义课件（47页珍藏版）》请在金锄头文库上搜索。

1、 前一页 休息实验一实验一 C语言复习语言复习l教学目的与要求 本实验的目的是帮助大家复习C语言的使用方法，特别是指针、结构体的内容，同时也为以后的各个实验做准备 l教学的重点与难点 指针、结构体、数组三种数据类型的混合使用 前一页 休息实验预习检查内容l指针指向数组后，数组元素的访问有哪些形式？指针指向数组后，数组元素的访问有哪些形式？l在下列类型定义后，表达式在下列类型定义后，表达式a3.num的逻辑含义的逻辑含义是什么？类型是什么？是什么？类型是什么？struct studentlong num；float score；struct student *next；a5； 答:3号元素的nu

2、m数据域long类型 前一页 休息例题例题#define NULL 0struct studentlong num；float score；struct student *next；main () struct student a,b,c,*head,*p； a.num=99101；a.score=89.5； b.num=99103；b.score=90； c.num=99107；c.score=85；/a 、b、 c变量赋值head=&a；a.next=&b；/a的后续为的后续为bb.next=&c；c.next=NULL；p=head；do printf（“%ld%5.1fn”,p-num

3、,p-score ）；）；/*输输出学号和成绩出学号和成绩*/ p=p-next；while( )； 答：答：p!=NULL 前一页 休息l9、设计一个可进行复数运算的演示程序。、设计一个可进行复数运算的演示程序。要求：实现下列六种基本运算：要求：实现下列六种基本运算：1）由输入）由输入的实部和虚部生成一个复数；的实部和虚部生成一个复数；2）两个复数）两个复数求和；求和；3）两个复数求差；）两个复数求差；4）两个复数求）两个复数求积；积；5）从已知复数中分离出实部；）从已知复数中分离出实部；6）从）从已知复数中分离出虚部。运算结果以相应已知复数中分离出虚部。运算结果以相应的复数或实数的表示形式

4、显示。的复数或实数的表示形式显示。l10、设计一个可进行有理数运算的演示程、设计一个可进行有理数运算的演示程序。要求：实现两个有理数相加、相减、序。要求：实现两个有理数相加、相减、相乘以及求分子或求分母的运算。相乘以及求分子或求分母的运算。实验内容及要求实验内容及要求 前一页 休息l有有10个学生，每个学生的数据包括学号、个学生，每个学生的数据包括学号、姓名、姓名、3门课的成绩，从键盘输入门课的成绩，从键盘输入10个学个学生数据，要求打印出生数据，要求打印出3门课总平均成绩，门课总平均成绩，以及最高分的学生的数据。以及最高分的学生的数据。l 要求：用要求：用input函数输入函数输入10个学生

5、数据，个学生数据，用用average 函数求总平均分；用函数求总平均分；用max函数函数找出最高分的学生数据；总平均分和最高找出最高分的学生数据；总平均分和最高分学生的数据都在主函数中输出。分学生的数据都在主函数中输出。 实验内容及要求实验内容及要求 前一页 休息讨论讨论l指出下列程序段的错误：lstruct studentllong num；lfloat score；lstruct student *next；la,b,c,*p；l a.next=&b;l b.next=&c;l p=a;l while (p)lprintf(“%ld%5.2f”,p-num,p-score);l P+;l

6、答：增加：c.next=NULL;p=a; =P=&a;P+; =P=p-next; 前一页 休息第二讲 线性表l教学目的与要求教学目的与要求 掌握数据结构中表的基本概念。熟练掌握线性表的基本操作，插入、删除、查找等运算在顺序存储结构和链接存储结构上的实现。熟练掌握链表的各种操作和应用。l教学的重点与难点教学的重点与难点线性表的基本操作在链接存储结构上的实现。 前一页 休息实验预习检查内容l完成下列程序，指出完成下列程序，指出main的结构的结构l#include l#define MaxLen 50ltypedef int elemtype； struct datatype elemtype

7、 *elem; int length; typedef struct datatype sqlist ； 前一页 休息lvoid create (sqlist *a)llint i,n；la-elem=(elemtype *)malloc(MaxLen*sizeof(elemtype);lprintf（“创建一个顺序表创建一个顺序表n”）；）；lprintf（“输入元素个数：输入元素个数：”）；）；lscanf（“%d,&a-length)；lfor (i=0；ilength；i+)ll printf（“输入第输入第%d个元素值：个元素值：”,i）；）；l scanf（“%d,a-elem+i

8、)；ll 前一页 休息lvoid invert(sqlist *a)l lint m=a-length/2,I；lelemtype temp；lfor (I=0；Ielem+i)= ; l =temp; ll(1)*(a-elem+i)(2)*(a-elem+a-length-1-i)(3) )*(a-elem+a-length-1-i) 前一页 休息lVoid disp(sqlist *a)l int I;lfor (i=0;ielem+i);l 前一页 休息lvoid main()llsqlist b,*a；la=&b;lcreate(a)；ldisp(a)；linvert(a)；ldis

9、p(a)；l 前一页 休息例题例题l有一个单链表的第一个结点指针为有一个单链表的第一个结点指针为head,编写一个函数将该单链表逆置编写一个函数将该单链表逆置,即最后一个结点变成第一个结点即最后一个结点变成第一个结点,原原来倒数第二个结点变成第二个结点。来倒数第二个结点变成第二个结点。 前一页 休息实验内容及要求实验内容及要求l4、7、13必做，其余老师选做几题必做，其余老师选做几题 l4、键盘输入学生信息（包括学号和成、键盘输入学生信息（包括学号和成绩），学号为绩），学号为0作为结束标志，建立其作为结束标志，建立其对应的线性表并输出各结点中的数据。对应的线性表并输出各结点中的数据。l注：试以

10、顺序表和单链表两种不同的注：试以顺序表和单链表两种不同的存储结构实现。存储结构实现。 前一页 休息l7、设计一个算法求、设计一个算法求A和和B两个单链表表示的集合的两个单链表表示的集合的并集。并集。l提示：将提示：将A和和B合并。合并。l9、用头插法把单链表、用头插法把单链表b中在单链表中在单链表a中未出现中未出现的结点合并到单链表的结点合并到单链表a中。中。 前一页 休息实验三实验三 栈和队列栈和队列 l教学目的与要求1.了解栈和队列的特性，以便灵活应用。2.熟练掌握栈和有关队列的各种操作和应用。 l教学的重点与难点 栈和有关队列的各种操作和应用 前一页 休息实验预习检查内容l1、栈顶指针是

11、栈顶元素的地址或是栈顶前、栈顶指针是栈顶元素的地址或是栈顶前一元素的地址一元素的地址,确定标准是什么确定标准是什么?答:由程序员自己确定,在压栈和弹栈操作时来实现2、在实际应用中，是采用一般队列还是、在实际应用中，是采用一般队列还是循环队列的依据是什么？循环队列的依据是什么？答：实际应用中，是否存在假溢出问题。 前一页 休息例题例题l设单链表中存放设单链表中存放n 个字符个字符,设计一个算法设计一个算法,使用使用栈判断该字符串是否中心对称栈判断该字符串是否中心对称,如如abccba即为即为中心对称字符串中心对称字符串. （根据题目填空完善程序）（根据题目填空完善程序）l提示：先用提示：先用cr

12、eate()函数从用户输入的字符串函数从用户输入的字符串创建相应的单链表，然后调用创建相应的单链表，然后调用judge ()函数函数判断是否为中心对称字符串。在判断是否为中心对称字符串。在 judge（）（）函数中先将字符串进栈，然后将栈中的字符函数中先将字符串进栈，然后将栈中的字符逐个与单链表中字符进行比较。逐个与单链表中字符进行比较。 前一页 休息实验内容及要求实验内容及要求l3、4必做，5选做l3、设一个算术表达式中包含圆括号、方括、设一个算术表达式中包含圆括号、方括号和花括号三种类型的括号，编写一个算号和花括号三种类型的括号，编写一个算法判断其中的括号是否匹配。法判断其中的括号是否匹配

13、。 l4、到医院看病的过程是，患者先排队等候，、到医院看病的过程是，患者先排队等候，排队过程中主要重复两件事：排队过程中主要重复两件事：l（1）病人到达诊室时，将病历交给护士，）病人到达诊室时，将病历交给护士，排到等候队列中候诊。排到等候队列中候诊。l（2）护士从等候队列中取出下一个患者的）护士从等候队列中取出下一个患者的病历，该患者进入诊室就诊。病历，该患者进入诊室就诊。 前一页 休息l5、设计一个程序，演示用算符优先法对算术、设计一个程序，演示用算符优先法对算术表达式求值的过程。表达式求值的过程。l基本要求：以字符序列的形式从终端输入语法基本要求：以字符序列的形式从终端输入语法正确的、不含

14、变量的整数表达式。利用教科正确的、不含变量的整数表达式。利用教科书表书表3.1给出的算符优先关系，实现对算术四给出的算符优先关系，实现对算术四则混合运算表达式的求值，并仿照教科书的则混合运算表达式的求值，并仿照教科书的例例3_1演示在求值中运算符栈、运算数栈、输演示在求值中运算符栈、运算数栈、输入字符和主要操作的变化过程。入字符和主要操作的变化过程。l测试数据：测试数据：3*（7-2）实验内容及要求实验内容及要求 前一页 休息讨论讨论l为了完成第3题，下列程序是否正确： 前一页 休息实验四实验四 串串 l教学目的与要求教学目的与要求1.掌握串的基本概念，存储方法及主要运算。2.将串的运算应用到

15、文本编辑中。l教学的重点与难点教学的重点与难点 子串的操作 前一页 休息实验预习检查内容串的顺序存储结构包括哪两种存储方式？答：静态分配和动态分配的顺序存储结构。静态分配：typedef struct char chmaxstrlen; int length sstring;动态分配：typedef struct char *ch; int length; hsring; 前一页 休息例题例题l下列是一个置换函数，采用顺序存储方式存下列是一个置换函数，采用顺序存储方式存储串，将串储串，将串s1中的第中的第I个字符开始的个字符开始的j个字符个字符（包括第（包括第I个字符）构成的子串用个字符）构成

16、的子串用s2串进行替串进行替换，函数名为换，函数名为replace(s1,I,j,s2)。例如：。例如：replace（“abcd”,1,3,xyz”）返回）返回”xyzd”。（填空）（填空）l提示：先提取提示：先提取s1中位置中位置I之前的所有字符构成之前的所有字符构成的子串的子串str1,再提取位置再提取位置I+j-1及之后的所有字及之后的所有字符构成的子串符构成的子串 str2，最后将，最后将str1,s2,str2连接连接起来便构成了结果串。起来便构成了结果串。 前一页 休息实验内容及要求实验内容及要求l3、4必做，5选做l3、采用顺序结构存储串，编写一个函数、采用顺序结构存储串，编写

17、一个函数index(s1,s2),用于用于s2是否是是否是s1的子串。若是，的子串。若是，返回其在主串中的位置；否则返回返回其在主串中的位置；否则返回-1。l4、利用串的基本运算，编写一个算法删除串、利用串的基本运算，编写一个算法删除串s1中所有中所有s2子串。子串。l提示：本题利用提示：本题利用3题的题的index()函数和删除子串函数和删除子串函数循环实现。函数循环实现。 前一页 休息l5、已知、已知s=“(xyz)+*”,t=“(x+z)*y”。试利。试利用连接、求子串和置换等操作，将用连接、求子串和置换等操作，将 s转转化为化为t。 实验内容及要求实验内容及要求 前一页 休息实验五实验

18、五 数组和广义表数组和广义表 l教学目的与要求教学目的与要求熟练掌握数组的存储表示和实现。熟悉广义表的存储结构的特性。l教学的重点与难点教学的重点与难点 数组的存储表示和常用操作的实现数组的存储表示和常用操作的实现 前一页 休息实验预习检查内容数组与一般线性表的区别？答：数组结构固定 数据元素同构为什么数组元素可以随机访问?答:可以通过地址计算公式来求得任意元素的地址 前一页 休息例题例题l设数组设数组R0.n-1的的n个元素中有多个个元素中有多个0元素，元素，设计一个算法，将设计一个算法，将R中所有的非中所有的非0元素依次移元素依次移动到动到R数组的前端。数组的前端。l提示：用提示：用I指向

19、不为指向不为0元素应放的下标，元素应放的下标，j遍历遍历R，当，当Rj不为不为0是，在是，在I与与j不相同时将不相同时将RI与与Rj交换。交换。 前一页 休息实验内容及要求实验内容及要求l3、6必做l3、试设计一个算法，将、试设计一个算法，将A0.n-1中所有中所有奇数移到偶数之前。要求不另增加存储奇数移到偶数之前。要求不另增加存储空间，且时间复杂度为空间，且时间复杂度为O(n)。l提示：提示：i从左向右遍历，指向从左向右遍历，指向A左边的一左边的一个偶数，个偶数，j从右向左遍历，指向从右向左遍历，指向A右边的右边的一个奇数，然后将一个奇数，然后将Ai 与与Aj交换。如交换。如此循环直到此循环

20、直到i大于等于大于等于j。 前一页 休息l6、稀疏矩阵运算器、稀疏矩阵运算器l基本要求：以基本要求：以“带行逻辑链接信息带行逻辑链接信息”的三的三元组顺序表表示稀疏矩阵，实现两个矩元组顺序表表示稀疏矩阵，实现两个矩阵相加、相减和相乘的运算。稀疏矩阵阵相加、相减和相乘的运算。稀疏矩阵的输入形式采用三元组表示，而运算结的输入形式采用三元组表示，而运算结果的矩阵则以通常的阵列形式列出。果的矩阵则以通常的阵列形式列出。实验内容及要求实验内容及要求 前一页 休息实验六实验六 树树 l教学目的与要求l1.掌握二叉树，二叉树排序数的概念及存储方法。l2.掌握二叉树的遍历算法。l3.熟练掌握编写实现树的各种运

21、算的算法。l教学的重点与难点 二叉树的遍历操作及其应用 前一页 休息实验预习检查内容l1、下列程序段的功能是什么？、下列程序段的功能是什么？l2、二叉树的遍历常用哪些方式？、二叉树的遍历常用哪些方式？答：1、建立排序树2、先序、中序、后序、层次 前一页 休息例题例题求二叉树的结点数和叶子数 前一页 休息实验内容及要求实验内容及要求l3、4必做l3、编写程序，实现按层次遍历二叉树。、编写程序，实现按层次遍历二叉树。l4、编写程序，对二叉树进行先序遍历，、编写程序，对二叉树进行先序遍历，并打印层号。并打印层号。 前一页 休息实验七实验七 图图 l教学目的与要求l1.熟悉图的各种存储方法。l2.掌握

22、遍历图的递归和非递归的算法。l3.理解图的有关算法。l教学的重点与难点 图的建立及图的常用操作的实现 前一页 休息实验预习检查内容l下列程序段的功能是什么？下列程序段的功能是什么？l图的存储结构是什么？图的存储结构是什么？答：1、建立图2、此程序段中，图的存储结构是邻接表 前一页 休息例题例题设计一个算法，判断无向图设计一个算法，判断无向图G是否连通。是否连通。若连通则返回若连通则返回1；否则返回；否则返回0。 前一页 休息实验内容及要求实验内容及要求l2、3必做l2、编写程序，实现无向图的深度优先搜索。l3、有一个邻接表存储的图G，分别设计实现以下要求的算法：求出图中每个顶点的出度；计算图中

23、出度为0的顶点数。 前一页 休息实验八实验八 查找查找l教学目的与要求l 1.掌握顺序查找，二分法查找和分块查找的算法。l 2.能运用线性表的查找方法解决实际问题。l教学的重点与难点 顺序查找、二分查找实现及应用 前一页 休息实验预习检查内容l顺序查找、二分查找顺序查找、二分查找 的对象有什么区别的对象有什么区别?答:顺序查找的对象可以是有序或无序表;二分查找的对象必须是有序表. 顺序查找、二分查找顺序查找、二分查找 的对象的存储结构的对象的存储结构分别是什么分别是什么?答:顺序查找对象可以是顺序表或链表; 二分查找的对象只能是顺序表 前一页 休息例题例题l给出在一个无序表给出在一个无序表A中

24、采用顺序查找中采用顺序查找算法查找值为算法查找值为x的元素的算法。的元素的算法。 前一页 休息实验内容及要求实验内容及要求l2必做，3选做l2、给出在一个递增有序表、给出在一个递增有序表A中采用二中采用二分查找算法查找值为分查找算法查找值为x的元素的递归算的元素的递归算法法 前一页 休息实验九实验九 排序排序l教学目的与要求l 1.掌握各种不同排序方法的基本思想和优缺点。l 2.了解各种排序方法依据的原则，以便根据不同的情况选择合适的排序方法。l教学的重点与难点 各种不同排序方法的实现及应用 前一页 休息实验预习检查内容l快速排序的基本思想是什么？快速排序的基本思想是什么？答:通过一趟排序，将

25、待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录进行排序，以达到整个序列有序。堆排序的基本思想是什么？堆排序的基本思想是什么？答:将无序序列建成一个堆，得到关键字最小（或最大）的记录；输出堆顶的最小（大）值后，使剩余的n-1个元素重又建成一个堆，则可得到n个元素的次小值；重复执行，得到一个有序序列。 前一页 休息例题例题l快速排序快速排序 算法算法 前一页 休息实验内容及要求实验内容及要求l2、3必做，4选做l2、编写程序，采用冒泡算法对一组无序数、编写程序，采用冒泡算法对一组无序数进行递增排序。进行递增排序。l3、用选择法对一组无序数进行递增排序。、用选择法对一组无序数进行递增排序。l4、编写程序，实现堆排序的算法。、编写程序，实现堆排序的算法。