数据结构实验讲义课件

实验一C语言复习教学目的与要求

本实验的目的是帮助大家复习C语言的使用方法，特别是指针、结构体的内容，同时也为以后的各个实验做准备

教学的重点与难点

指针、结构体、数组三种数据类型的混合使用实验一C语言复习教学目的与要求1实验预习检查内容指针指向数组后，数组元素的访问有哪些形式？在下列类型定义后，表达式a[3].num的逻辑含义是什么？类型是什么？ structstudent {longnum； floatscore； structstudent*next； }a[5]；答:3号元素的num数据域

long类型实验预习检查内容指针指向数组后，数组元素的访问有哪些形式？答2例题#defineNULL0structstudent{longnum；floatscore；structstudent*next；}；main(){structstudenta,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.1f\n”,p->num,p->score

）；/*输出学号和成绩*/

p=p->next；}while(

)；}答：p!=NULL例题#defineNULL0head=&a；答：p!=N39、设计一个可进行复数运算的演示程序。要求：实现下列六种基本运算：1）由输入的实部和虚部生成一个复数；2）两个复数求和；3）两个复数求差；4）两个复数求积；5）从已知复数中分离出实部；6）从已知复数中分离出虚部。运算结果以相应的复数或实数的表示形式显示。10、设计一个可进行有理数运算的演示程序。要求：实现两个有理数相加、相减、相乘以及求分子或求分母的运算。实验内容及要求9、设计一个可进行复数运算的演示程序。要求：实现下列六种基本4有10个学生，每个学生的数据包括学号、姓名、3门课的成绩，从键盘输入10个学生数据，要求打印出3门课总平均成绩，以及最高分的学生的数据。要求：用input函数输入10个学生数据，用average函数求总平均分；用max函数找出最高分的学生数据；总平均分和最高分学生的数据都在主函数中输出。实验内容及要求有10个学生，每个学生的数据包括学号、姓名、3门课的成绩，从5讨论指出下列程序段的错误：structstudent{longnum；floatscore；structstudent*next；}a,b,c,*p；a.next=&b;b.next=&c;p=a;while(p){printf(“%ld%5.2f”,p->num,p->score);P++;}答：增加：c.next=NULL;p=a;=>P=&a;P++;=>P=p->next;讨论指出下列程序段的错误：答：6第二讲线性表教学目的与要求掌握数据结构中表的基本概念。熟练掌握线性表的基本操作，插入、删除、查找等运算在顺序存储结构和链接存储结构上的实现。熟练掌握链表的各种操作和应用。教学的重点与难点线性表的基本操作在链接存储结构上的实现。第二讲线性表教学目的与要求7实验预习检查内容完成下列程序，指出main的结构#include<stdio.h>#defineMaxLen50typedefintelemtype；structdatatype{elemtype*elem;intlength;}typedefstructdatatypesqlist；实验预习检查内容完成下列程序，指出main的结构8voidcreate(sqlist*a){inti,n；a->elem=(elemtype*)malloc(MaxLen*sizeof(elemtype));printf（“创建一个顺序表\n”）；printf（“输入元素个数：”）；scanf（“%d",&a->length)；for(i=0；i<a->length；i++){printf（“输入第%d个元素值：”,i）；scanf（“%d",a->elem+i)；}}voidcreate(sqlist*a)9voidinvert(sqlist*a){intm=a->length/2,I；elemtypetemp；for(I=0；I<m；I++){temp=

;*(a->elem+i)=

;

=temp;}}(1)*(a->elem+i)(2)*(a->elem+a->length-1-i)(3))*(a->elem+a->length-1-i)voidinvert(sqlist*a)(1)*(a->10Voiddisp(sqlist*a){intI;for(i=0;i<n;i++)printf(“%5d:%d\n”,i+1,*(a->elem+i));}Voiddisp(sqlist*a)11voidmain(){sqlistb,*a；a=&b;;create(a)；disp(a)；invert(a)；disp(a)；}voidmain()12例题有一个单链表的第一个结点指针为head,编写一个函数将该单链表逆置,即最后一个结点变成第一个结点,原来倒数第二个结点变成第二个结点。

例题有一个单链表的第一个结点指针为head,编写一个函数将该13实验内容及要求4、7、13必做，其余老师选做几题4、键盘输入学生信息（包括学号和成绩），学号为0作为结束标志，建立其对应的线性表并输出各结点中的数据。注：试以顺序表和单链表两种不同的存储结构实现。实验内容及要求4、7、13必做，其余老师选做几题147、设计一个算法求A和B两个单链表表示的集合的并集。提示：将A和B合并。9、用头插法把单链表b中在单链表a中未出现的结点合并到单链表a中。7、设计一个算法求A和B两个单链表表示的集合的并集。15实验三栈和队列教学目的与要求了解栈和队列的特性，以便灵活应用。熟练掌握栈和有关队列的各种操作和应用。

教学的重点与难点栈和有关队列的各种操作和应用

实验三栈和队列教学目的与要求16实验预习检查内容1、栈顶指针是栈顶元素的地址或是栈顶前一元素的地址,确定标准是什么?答:由程序员自己确定,在压栈和弹栈操作时来实现2、在实际应用中，是采用一般队列还是循环队列的依据是什么？答：实际应用中，是否存在假溢出问题。实验预习检查内容1、栈顶指针是栈顶元素的地址或是栈顶前一元素17例题设单链表中存放n个字符,设计一个算法,使用栈判断该字符串是否中心对称,如abccba即为中心对称字符串.（根据题目填空完善程序）提示：先用create()函数从用户输入的字符串创建相应的单链表，然后调用judge()函数判断是否为中心对称字符串。在judge（）函数中先将字符串进栈，然后将栈中的字符逐个与单链表中字符进行比较。例题设单链表中存放n个字符,设计一个算法,使用栈判断该字符18实验内容及要求3、4必做，5选做3、设一个算术表达式中包含圆括号、方括号和花括号三种类型的括号，编写一个算法判断其中的括号是否匹配。4、到医院看病的过程是，患者先排队等候，排队过程中主要重复两件事：（1）病人到达诊室时，将病历交给护士，排到等候队列中候诊。（2）护士从等候队列中取出下一个患者的病历，该患者进入诊室就诊。实验内容及要求3、4必做，5选做195、设计一个程序，演示用算符优先法对算术表达式求值的过程。基本要求：以字符序列的形式从终端输入语法正确的、不含变量的整数表达式。利用教科书表3.1给出的算符优先关系，实现对算术四则混合运算表达式的求值，并仿照教科书的例3_1演示在求值中运算符栈、运算数栈、输入字符和主要操作的变化过程。测试数据：3*（7-2）实验内容及要求5、设计一个程序，演示用算符优先法对算术表达式求值的过程。实20讨论为了完成第3题，下列程序是否正确：讨论为了完成第3题，下列程序是否正确：21实验四串教学目的与要求掌握串的基本概念，存储方法及主要运算。将串的运算应用到文本编辑中。教学的重点与难点子串的操作实验四串教学目的与要求22实验预习检查内容串的顺序存储结构包括哪两种存储方式？答：静态分配和动态分配的顺序存储结构。静态分配：typedefstruct{charch[maxstrlen];

intlength}sstring;动态分配：typedefstruct{char*ch;intlength;}hsring;实验预习检查内容串的顺序存储结构包括哪两种存储方式？答：静态23例题下列是一个置换函数，采用顺序存储方式存储串，将串s1中的第I个字符开始的j个字符（包括第I个字符）构成的子串用s2串进行替换，函数名为replace(s1,I,j,s2)。例如：replace（“abcd”,1,3,’xyz”）返回”xyzd”。（填空）提示：先提取s1中位置I之前的所有字符构成的子串str1,再提取位置I+j-1及之后的所有字符构成的子串str2，最后将str1,s2,str2连接起来便构成了结果串。例题下列是一个置换函数，采用顺序存储方式存储串，将串s1中的24实验内容及要求3、4必做，5选做3、采用顺序结构存储串，编写一个函数index(s1,s2),用于s2是否是s1的子串。若是，返回其在主串中的位置；否则返回-1。4、利用串的基本运算，编写一个算法删除串s1中所有s2子串。提示：本题利用3题的index()函数和删除子串函数循环实现。实验内容及要求3、4必做，5选做255、已知s=“(xyz)+*”,t=“(x+z)*y”。试利用连接、求子串和置换等操作，将s转化为t。实验内容及要求5、已知s=“(xyz)+*”,t=“(x+z)*y”。试利26实验五数组和广义表教学目的与要求熟练掌握数组的存储表示和实现。熟悉广义表的存储结构的特性。教学的重点与难点

数组的存储表示和常用操作的实现

实验五数组和广义表教学目的与要求27实验预习检查内容数组与一般线性表的区别？答：数组结构固定数据元素同构为什么数组元素可以随机访问?答:可以通过地址计算公式来求得任意元素的地址实验预习检查内容数组与一般线性表的区别？答：数组结构固定28例题设数组R[0..n-1]的n个元素中有多个0元素，设计一个算法，将R中所有的非0元素依次移动到R数组的前端。提示：用I指向不为0元素应放的下标，j遍历R，当R[j]不为0是，在I与j不相同时将R[I]与R[j]交换。例题设数组R[0..n-1]的n个元素中有多个0元素，设计一29实验内容及要求3、6必做3、试设计一个算法，将A[0..n-1]中所有奇数移到偶数之前。要求不另增加存储空间，且时间复杂度为O(n)。提示：i从左向右遍历，指向A左边的一个偶数，j从右向左遍历，指向A右边的一个奇数，然后将A[i]与A[j]交换。如此循环直到i大于等于j。实验内容及要求3、6必做306、稀疏矩阵运算器基本要求：以“带行逻辑链接信息”的三元组顺序表表示稀疏矩阵，实现两个矩阵相加、相减和相乘的运算。稀疏矩阵的输入形式采用三元组表示，而运算结果的矩阵则以通常的阵列形式列出。实验内容及要求6、稀疏矩阵运算器实验内容及要求31实验六树教学目的与要求1.掌握二叉树，二叉树排序数的概念及存储方法。2.掌握二叉树的遍历算法。3.熟练掌握编写实现树的各种运算的算法。教学的重点与难点二叉树的遍历操作及其应用实验六树教学目的与要求32实验预习检查内容1、下列程序段的功能是什么？2、二叉树的遍历常用哪些方式？答：1、建立排序树2、先序、中序、后序、层次实验预习检查内容1、下列程序段的功能是什么？答：33例题求二叉树的结点数和叶子数

例题求二叉树的结点数和叶子数34实验内容及要求3、4必做3、编写程序，实现按层次遍历二叉树。4、编写程序，对二叉树进行先序遍历，并打印层号。实验内容及要求3、4必做35实验七图教学目的与要求1.熟悉图的各种存储方法。2.掌握遍历图的递归和非递归的算法。3.理解图的有关算法。教学的重点与难点图的建立及图的常用操作的实现实验七图教学目的与要求36实验预习检查内容下列程序段的功能是什么？图的存储结构是什么？答：1、建立图2、此程序段中，图的存储结构是邻接表实验预习检查内容下列程序段的功能是什么？答：37例题设计一个算法，判断无向图G是否连通。若连通则返回1；否则返回0。

例题设计一个算法，判断无向图G是否连通。若连通则返回1；否则38实验内容及要求2、3必做2、编写程序，实现无向图的深度优先搜索。3、有一个邻接表存储的图G，分别设计实现以下要求的算法：求出图中每个顶点的出度；计算图中出度为0的顶点数。实验内容及要求2、3必做39实验八查找教学目的与要求1.掌握顺序查找，二分法查找和分块查找的算法。2.能运用线性表的查找方法解决实际问题。教学的重点与难点顺序查找、二分查找实现及应用

实验八查找教学目的与要求40实验预习检查内容顺序查找、二分查找的对象有什么区别?答:顺序查找的对象可以是有序或无序表;二分查找的对象必须是有序表.

顺序查找、二分查找的对象的存储结构分别是什么?答:顺序查找对象可以是顺序表或链表