《应用数据结构》实验指导书

《《应用数据结构》实验指导书》由会员分享，可在线阅读，更多相关《《应用数据结构》实验指导书（40页珍藏版）》请在金锄头文库上搜索。

1、应用数据结构应用数据结构实验指导书实验指导书课程编号：课程编号：课程名称：课程名称：应用数据结构/Applied Data Structure实验学时：实验学时：16适应专业：适应专业：工科类承担实验室：承担实验室：管理学院实验中心一、实验目的和任务一、实验目的和任务1 1实验教学的目的实验教学的目的 本课程的教学要求之一是训练学生进行复杂程序设计的技能和培养良好程序设计的习惯，其重要程度绝不亚于知识传授。实验的作用在于帮助学生深入理解教材内容，巩固基本概念，促使学生在动手过程中进一步体会 C 语言中数据结构的运用技巧，并锻炼学生在调试过程中分析和发现问题的能力。2 2实验教学的要求实验教学的

2、要求学生应掌握 C 语言基本编程能力并运用数据结构的原理和方法解决具体问题。除按时上机外，学生应具备构造算法并用程序实现的能力；在程序调试过程中，学生应能正确解读程序的错误提示并找到有效的解决办法。此外，规范书写算法也是一个值得高度重视的问题，教师有责任在教学过程中提醒学生，避免形成一系列难以纠正且贻害无穷的程序设计坏习惯。此外，本门课程设计的算法比较多，要求教师熟练掌握C 语言和数据结构各类算法，并能准确理解和回答学生提出的编程问题。二、实验项目及学时分配二、实验项目及学时分配序号序号实实 验验 项项 目目 名名 称称实验学时实验学时实验类型实验类型开出要求开出要求1线性数据结构算法验证4验

3、证及演示必做2非线性数据结构算法验证4验证及演示必做3查找及排序4验证及演示必做4综合算法设计4综合必做三、参考资料三、参考资料李业丽、郑良斌编著，数据结构（C）实验教程，北京理工大学出版社，2005 年 12 月出版 严蔚敏，吴伟民编著，数据结构习题集（C 语言版） ，清华大学出版社，1999 年 2 月出版。四、单项实验的内容和要求四、单项实验的内容和要求（包括实验所用的主要仪器设备，实验所需主要耗材）实验一实验一 线性数据结构算法验证线性数据结构算法验证1实验目的与意义实验目的与意义1) 熟悉 C 语言的上机环境，进一步掌握 C 语言的结构特点 2) 掌握线性表的顺序存储结构的定义及 C

4、 语言实现 3) 掌握线性表的链式存储结构单链表的定义及 C 语言实现 4) 掌握线性表在顺序存储结构即顺序表中的各种基本操作 5) 掌握线性表在链式存储结构单链表中的各种基本操作 6) 掌握栈的顺序表示和实现 7) 掌握栈的链式表示和实现 8) 掌握队列顺序表示和实现 9) 掌握队列链式表示和实现2基本原理和方法基本原理和方法本实验涉及各类线性数据结构线性表、栈和队列等。 单链表的各种操作，包括单链表的建立，结点的查找、插入、删除等基本运算。 链表中插入结点的指针变化和删除 p 所指结点的指针变化参见讲义。 栈的顺序存储结构简称为顺序栈，它是运算受限的顺序表。 对于顺序栈，入栈时，首先判断栈

5、是否为满，栈满的条件为 p-top=MAXNUM-1， 栈满时，不能入栈；否则出现空间溢出，引起错误，这种现象称为上溢。 出栈和读栈顶元素操作，先判栈是否为空，为空时不能操作，否则产生错误。通 常栈空作为一种控制转移的条件。 注意： 顺序栈中元素用向量存放。 栈底位置是固定不变的，可设置在向量两端的任意一个端点。 栈顶位置是随着进栈和退栈操作而变化的，用一个整型量 top（通常称 top 为 栈顶指针）来指示当前栈顶位置。 队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺序表。 入队时，将新元素插入 rear 所指的位置，然后将 rear 加 1，出队时，删去 front 所指的元

6、素，然后将 front 加 1 并返回被删除元素。 顺序队列中的溢出现象： “下溢”现象。当队列为空时，做出队运算产生的溢出现象。 “下溢”是正常 现象，常用作程序控制转移的条件。 “真上溢”现象。当队列满时，做进找运算产生空间溢出的现象。 “真上溢” 是一种出错状态，应设法避免。 “假上溢”现象。由于入队和出队操作中，头尾指针只增加不减小，致使被删 元素的空间永远无法重新利用。当队列中实际的元素个数远远小于向量空闻的 规模时，也可能由于尾指针己超越向量空间的上界而不能做入队操作。该现象称为“假上溢”现象。3主要仪器设备及耗材主要仪器设备及耗材安装有 Turbo C+ 3.0 运行环境的电脑，

7、无耗材要求。4实验方案或技术路线实验方案或技术路线本实验含有三部分内容线性表、栈和队列。 A线性表部分 采取建立学生成绩表的方法实现。即建立学生成绩单链表，链表中每个结点由 4 个域组成，分别为：学号、姓名、成绩、存放下一个结点地址的 next 域、要求完成的 四项功能可写成四个函数，登记学生成绩对应建立学生单链表的功能，后三个功能分 别对应单链表的查询、插入与删除三大基本操作。 该系统中的数据采用线性表中的链式存储结构即单链表来存储，用结构体类型定 义每个学生记录，故该单链表中每个结点的结构可描述为： #define MAXLEN 100 typedef struct node int nu

8、m；/学号char nameMAXLEN；/姓名float score；/成绩struct node *next; linklist; B栈部分 此部分的算法独立性较强，因此可直接采用教材或讲义上的算法实现，但教材或 讲义上的算法并非可执行的算法，故学生须自行进行算法上的转换。 C队列部分 本实验主要由教师课堂演示，以一个具体的实例机场事件模拟来实现。5实验内容及步骤实验内容及步骤A线性表部分学生成绩管理是学校教务管理的重要组成部分，其处理信息量 很大，本实验是对学生的成绩管理作一个简单的模拟，用菜单选择操作方式完成下列 功能： 登记学生成绩 查询学生成绩 插入学生成绩 删除学生成绩 【参考程

9、序】 /*头文件 hh.h 的内容*/ #include #include #include #define MAXLEN 100 typedef struct node int num;char nameMAXLEN;int score;struct node *next; list; /*头文件 creat.h 的内容*/ #include“hh.h“ list *create() list *head, *p, *r;int i, n;head=(list *)malloc(sizeof(list);head-next=NULL;r=head;printf(“请输入学生人数:n“);sc

10、anf(“%d“,for(i=l; inum);printf(“输入学生的姓名:n“);scanf(“%s“, p-name);printf(“输人李生的成绩:n“);scanf(“%d“, p-next=NULL;r-next=p;r=r-next; return(head); /*以下是头文件 insert.h 的内容*/ list *insert(list *h) list *p,*q,*r,*head;head=r=h;p=h-next;q=(list *)malloc(sizeof(list);printf(“输入待插入学生的学号:n“);scanf(“%d“,printf(“输入姓

11、名:n);scanf(“%s“, q-name);printf(“输入成绩:n“);scanf(“%d, q-next=NULL;while(p) r=p;p=p-next; r-next=q;r=r-next;return(head); /*以下是头文件 find.h 的内容*/ void find(list *h) int k;list *p;p=h-next;printf(“输入要查找学生的学号:n“);scanf(“%d“, while(pif(p) printf(“学号t 姓名t 成绩n“);printf(“%dt%st%dn“,p-num,p-name,p-score); else

12、 printf(“没找到!n“); /*以下是头文件 del.h 的内容*/ list *del(list *h) int k;list *p, *q;q=h;p=h-next;printf(“请输入待删除学生的学号:n“);scanf(“%d“,while(pp=p-next; if(p) q-next=p-next;free(p); else printf(“没有这个学生成绩，无法删除!n“);return(h); /*以下是头文件 output.h 的内容*/ void output(list *h) list *p;p=h-next;while(p!=NULL) printf(“学号t

13、 姓名t 成绩tn“);printf(“%dt%st%dn“,p-num,p-name,p-score);p=p-next; /*以下是主程序*/ #include“creat.h“ #include“find.h“ #include“insert.h“ #include“output.h“ #include“del.h“ main() list *p;int k; /*控制循环的标志*/while(1) printf(“ -n“);printf(“ | 学生成绩管理 |n“);printf(“ |n“);printf(“ | 1.登记成绩 |n“);printf(“ | 2.查询成绩 |n“

14、);printf(“ | 3:插入成绩 |n“);printf(“ | 4.删除成绩 |n“);printf(“ | 5.输出所有学生成绩 |n“);printf(“ | 0.退出程序 |n“);printf(“ -n“);printf(“ 请输入你的选择n“);scanf(“%d“,switch(k) case 1: p=create(); break;case 2: find(p); break;case 3: p=insert(p); break;case 4: p=del(p); break;case 5: output(p); break;case 0: exit(0);defaul

15、t: printf(“选择错误，重新开始!n“); B栈部分编写一个程序实现顺序栈的各种基本运算，并在此基础上设计一个 主程序，完成如下功能： 初始化顺序栈 插入元素 删除栈顶元素 取栈顶元 遍历顺序栈 置空顺序栈 【参考程序】 #include #include #define MAXNUM 20 #define ElemType int /*定义顺序栈的存储结构*/ typedef struct ElemType stackMAXNUM;int top; SqStack; /*初始化顺序栈*/void InitStack(SqStack *p) if(!p) printf(“Error“);p-top=-l; /*入栈*/ void Push(SqStack *p, ElemType x) if(p-