《数据结构》实验大纲答案.doc

《数据结构》实验教学大纲 开课单位： 宁德师范学院计算机系 设置类别： 非独立设课 学 时： 16学时 实验项目总数： 7 实验教材：《数据结构习题集与上机指导》，严蔚敏，清华大学出版社 主要设备（环境）：微机、C语言编程环境（VC++） 教学目的 《数据结构》是计算机科学与技术专业的一门重要的专业基础课，课程旨在使学生学会计算机加工的数据对象的特性，学会数据的组织方法，以便选择合适的数据的逻辑结构及存储结构，并进行相应的运算。实验是该课程实践教学的重要环节，目的是培养学生根据求解问题的性质选择合理的数据结构，提高分析、设计、编程以及控制求解算法的时间、空间复杂性的能力。 基本要求 《数据结构》是计算机专业的专业核心基础课程，其先修课程有至少一门高级语言。数据结构课程将覆盖计算机软件实现中的大部分的基本算法，并具有一定的深度和广度，使学生对计算机常用基础算法有一个全盘的了解；通过此课的学习，学生应该具有针对所给的问题设计和实现高效算法的能力。通过上机实验，将使学生熟悉、掌握课堂教学中所学的大部分算法。 同时，上机实习是对学生在软件设计方面的综合训练，包括问题分析，总体结构设计，用户界面设计，程序设计基本技能和技巧等，以培养良好的编程风格和科学作风。通过理论联系实际，以最终提高学生动手操作的能力以及分析问题的能力。 实验项目设置 实验 序号 实验名称 试验 学时 试验要求 试验类型 每组人数 1 顺序表 2 必修 设计 1 2 单链表 2 必修 设计 1 3 栈 2 必修 设计 1 4 队列 2 必修 验证 1 5 二叉树的遍历 2 必修 验证 1 6 查找 2 必修 设计 1 7 排序 4 必修 设计 1 四、实验项目说明 实验一：顺序表 一、目的： 熟练掌握线性表的基本操作在顺序存储结构上的实现 二、要求： 掌握顺序表的建立、查找、插入、删除等基本操作。 三、示例程序： #include<stdio.h> #include<stdlib.h> #define MAXSIZE 30 struct SqList { char datas[MAXSIZE]; int length; }; typedef struct SqList SqList; //建立顺序表L void creat_Sq(SqList *L) { char x; int j; //按要求建立顺序表 printf("按要求输入顺序表初始时的元素(切换用回车),以#结束：\n"); fflush(stdin); scanf("%c",&x); j=0; while( x!='#') { L->datas[j]=x; L->length++; j++; fflush(stdin); scanf("%c",&x); } } //查找操作 int LocateElem_Sq(SqList *L, char x) { //在顺序线性表L中查找第1个值与x相等的元素，若找到，则返回其在L中的位序，否则返回0 int k; k=1; //k的初值为第1个元素的位序 while(k<=L->length && L->datas[k-1]!=x) k++; if(k<=L->length) return k; else return 0; } //求顺序表长度 int Get_length(SqList *L) { return L->length; } //插入操作 void ListInsert_Sq (SqList *L,int i,char e) {//在顺序表L的第i个位置前插入一个新的元素e **************** } //删除操作 void ListDelete_Sq(SqList *L,int i) {//在顺序表L中删除第i个数据元素 int k; if((i<1)||(i>L->length)||(L->length==0))//出错处理，考虑算法的健壮性 printf("error"); //i值不合法或表已空则出错 else{ for (k=i; k<L->length; k++)//将第i+1至第n个元素逐一向前移一个位置 L->datas[k-1]=L->datas[k]; L->length=L->length-1; //将顺序表的长度减1 } } //输出顺序表 void PRINT(SqList *L) { int i; printf("顺序表的当前值为：\n"); for(i=0;i<L->length;