数据结构实验讲义.ppt

例题 设数组R[0..n-1]的n个元素中有多个0元素，设计一个算法，将R中所有的非0元素依次移动到R数组的前端。 提示：用I指向不为0元素应放的下标，j遍历R，当R[j]不为0是，在I与j不相同时将R[I]与R[j]交换。 第三十页，共四十八页，2022年，8月28日 实验内容及要求 3、6必做 3、试设计一个算法，将A[0..n-1]中所有奇数移到偶数之前。要求不另增加存储空间，且时间复杂度为O(n)。 提示：i从左向右遍历，指向A左边的一个偶数，j从右向左遍历，指向A右边的一个奇数，然后将A[i] 与A[j]交换。如此循环直到i大于等于j。 第三十一页，共四十八页，2022年，8月28日 6、稀疏矩阵运算器 基本要求：以“带行逻辑链接信息”的三元组顺序表表示稀疏矩阵，实现两个矩阵相加、相减和相乘的运算。稀疏矩阵的输入形式采用三元组表示，而运算结果的矩阵则以通常的阵列形式列出。 实验内容及要求 第三十二页，共四十八页，2022年，8月28日 实验六 树 教学目的与要求 1.掌握二叉树，二叉树排序数的概念及存储方法。 2.掌握二叉树的遍历算法。 3.熟练掌握编写实现树的各种运算的算法。 教学的重点与难点 二叉树的遍历操作及其应用 第三十三页，共四十八页，2022年，8月28日 实验预习检查内容 1、下列程序段的功能是什么？ 2、二叉树的遍历常用哪些方式？ 答： 1、建立排序树 2、先序、中序、后序、层次 第三十四页，共四十八页，2022年，8月28日 前一页 休息 第一页，共四十八页，2022年，8月28日 实验一 C语言复习 教学目的与要求 本实验的目的是帮助大家复习C语言的使用方法，特别是指针、结构体的内容，同时也为以后的各个实验做准备 教学的重点与难点 指针、结构体、数组三种数据类型的混合使用 第二页，共四十八页，2022年，8月28日 实验预习检查内容 指针指向数组后，数组元素的访问有哪些形式？ 在下列类型定义后，表达式a[3].num的逻辑含义是什么？类型是什么？ struct student {long num； float score； struct student *next； }a[5]； 答:3号元素的num数据域 　long类型 第三页，共四十八页，2022年，8月28日 例题 #define NULL 0 struct student {long 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的后续为b b.next=c； c.next=NULL； p=head； do {printf（“%ld%5.1f\n”,p-num,p-score ）；/*输出学号和成绩*/ p=p-next； }while( )； } 答：p!=NULL 第四页，共四十八页，2022年，8月28日 9、设计一个可进行复数运算的演示程序。要求：实现下列六种基本运算：1）由输入的实部和虚部生成一个复数；2）两个复数求和；3）两个复数求差；4）两个复数求积；5）从已知复数中分离出实部；6）从已知复数中分离出虚部。运算结果以相应的复数或实数的表示形式显示。 10、设计一个可进行有理数运算的演示程序。要求：实现两个有理数相加、相减、相乘以及求分子或求分母的运算。 实验内容及要求 第五页，共四十八页，2022年，8月28日 有10个学生，每个学生的数据包括学号、姓名、3门课的成绩，从键盘输入10个学生数据，要求打印出3门课总平均成绩，以及最高分的学生的数据。 要求：用input函数输入10个学生数据，用average 函数求总平均分；用max函数找出最高分的学生数据；总平均分和最高分学生的数据都在主函数中输出。 实验内容及要求 第六页，共四十八页，2022年，8月28日 讨论 指出下列程序段的错误： struct student {long num； float score； struct student *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