数据结构实训教材

数据库原理与应用实训教程崔海源主编大连理工大学出版社数据库原理与应用实训教程崔海源主编李橙李霞编著大连理工大学出版社内容简介本书共分七章，包含七个完整实训项目，分别涉及到数据结构中线性表、栈、串、树、查找和排序六个知识点。

每个章节都详细介绍一个实训项目得开发过程，并以“问题描述”、“输入与输出”、“需求分析”、“开发工具与环境”、“概要设计”、“详细设计”、“调试结果”为纲安排过程，使得读者能够清楚每一个项目实施的具体步骤，便于分析和解决问题。

这七个实训项目分成A、B两个等级。

B级项目在原有书本知识的基础之上进行拓展，是各知识的高级应用。

例如第三章的项目“基于栈结构的中缀表达式求职”，是应用栈结构的高级应用。

学生首先要会掌握与栈相关的各种基本运算，在此基础之上，应用栈的知识对输入的任意中缀表达式进行转换与求值。

A级难度最大，涉及到得内容是课本以外的，因此增加了“知识准备”，对于涉及到的知识进行简单讲解。

A级项目对学生的自学能力和创新能力有很高的要求，适合于学有余力和程序发烧友完成。

本书项目实例以C作为开发平台。

可以使用TURBO C或VC进行程序的编写。

C语言是目前世界上流行、使用最广泛的高级程序设计语言。

C语言对操作系统和系统使用程序以及需要对硬件进行操作的场合，用C语言明显优于其它高级语言，许多大型应用软件都是用C语言编写的。

而C语言是数据结构的先修课程，我们的学生在学数据结构之前都系统的学习过了C语言，因此对于编写C语言都有一定的基础。

本书可作为本、专科、高职层次数据库技术与应用的实训教材。

本书中出现的所有C语言或程序模块都在VC6.0系统环境下调试并通过，其正确性得到了实际的验证，从而增强了教材的实用性和科学性。

本书所有的源程序代码可通过以下地址下载（/drill）;也可以通过Email和李憕老师联系（cher7086@）。

本书由南京师范大学泰州学院李橙老师（编写1、2、3、5章）和李霞老师（编写4、6、7章），另外彭程和苏戴也参与了程序的编写和调试。

由于编者的水平有限，本书肯定会有不少缺点和不足，热切期望得到专家和读者的批评指正。

编者 2009年12月主编寄语一本好的教材，基本上奠定了一半的教学效果。

好的教学效果，就是满足市场对人才的需求。

但长期以来，高校批量培养出的计算机软件专业的学生，不能满足公司的用人标准，在技术基础、职业素养、独立工作能力等方面都有欠缺；同时，应用型本科高校既不是理论研究型也不是高级技工型，如何找到准确的定位，让毕业的学生能够高层次就业、“即插即用”，这一直是我们思考的问题。

鉴于我系承担的全国高等学校教学研究中心的国家级课题：“我国高校应用型人才培养模式研究”的计算机类子课题--“基于‘软件工厂’的软件开发人才培养模式”，在推动应用型教学改革的深入开展，启动优质教学资源的建设思想指导下，以提高学生的业务水平、动手能力，进而提高学生就业竞争力为目标，我们在软件人才培养的教学计划、教学大纲、教材建设等方面都有所研究和创新，并将“实训教学”作为实现应用型人才培养的重要模式和主要手段。

实训课程，也称大作业或小毕设，是不同于仅为验证的实验。

我们以此编写的实训教材以项目驱动为主导，模拟企业来运作。

每本教材有该门课程的总体概述、实用够用的内容介绍、还有6～8个不同层次的实训项目，分为A、B、C三个难易等级：C级为入门级，学生可自主完成；B级为中等层次，学生可根据上下文完成全部项目；A级为高级层次，学生可根据教材提示，实现一定程度的项目独创。

实训时间可选择期末或伴随课程进行。

实训模式可采用“分组考核，自主学习”相结合的组织模式。

学生可选择其中一个项目作为实训成果参加考核答辩，检验学习成果，每个项目可安排15课时左右。

所以本系列教材源于实践，可以满足不同层次学生的需求，由浅入深，循序渐进，难易随选。

本套丛书教材是“人才培养模式研究”课题结项成果的一部分，该项目得到南京师范大学泰州学院的资助，在此表示感谢；同时也感谢大连理工大学出版社给予的鼎力相助。

参加丛书《数据库原理与应用实训教程》、《数据结构实训教程》、《J2EE实训教程》、《软件工程实训教程》、《Internet 编程实训教程》、《C#程序设计实训教程》等六本教材编写的有南京师范大学泰州学院的史永、张国华、李橙、卫星、吉晓香、周巧扣、叶苗、李霞、陆霞、郭依正、孙秋凤、王自然等多年在一线教学的教师。

本教材既可以作为各门课程的配套实训教材、也可作为参考书、课后练习项目。

通过本系列实训教材的出版，我们希望能够得到广大读者更大范围的关注并取得合作，从而共同推进我国高校、特别是应用型本科计算机软件方向专业人才的培养建设。

计算机学科知识日新月异，加之编者水平有限，书中不当之处，希望读者、专家和同行勿吝指正。

2009-12目录实训一基于链表结构的学生记录管理程序 (7)1.1问题描述 (7)1.2输入与输出 (7)1.3 需求分析 (7)1.4 开发工具与环境 (7)1.5 概要设计 (7)1.7调试结果 (12)实训二基于链表结构的一元多项式相乘 (14)2.1问题描述 (14)2.2输入与输出 (14)2.3需求分析 (15)2.4开发工具与环境 (15)2.5概要设计 (15)2.6详细设计 (15)2.7调试结果 (19)实训三基于栈结构的中缀表达式求值 (21)3.1问题描述 (21)3.2输入与输出 (21)3.3需求分析 (21)3.4开发工具与环境 (21)3.5概要设计 (21)3.6详细设计 (23)3.7调试结果 (27)实训四文学研究助手 (27)4.1 问题描述 (27)4.2 输入与输出 (27)4.3 需求分析 (27)4.4 开发工具与环境 (27)4.5 概要设计 (27)4.6 详细设计 (28)4.7 调试结果 (31)实训五：压缩与解压缩系统 (33)5.1 问题描述 (33)5.2 输入与输出 (33)5.3 需求分析 (33)5.4 开发工具与环境 (33)5.5 概要设计 (33)5.6 详细设计 (34)5.7 调试结果 (38)实训六：hash技术统计词频 (38)6.1 问题描述 (38)6.2 输入与输出 (38)6.3 需求分析 (38)6.4 开发工具与环境 (38)6.5 概要设计 (38)6.6 详细设计 (39)6.7调试结果 (44)实训七：内部排序算法比较 (46)7.1 问题描述 (46)7.2 输入与输出 (46)7.3 需求分析 (46)7.4 开发工具与环境 (46)7.5 概要设计 (46)7.6 详细设计 (47)7.7 调试结果 (51)实训八：校园交通咨询系统设计（最短路径） (53)8.1 问题描述 (53)8.2 输入与输出 (53)8.3 需求分析 (53)8.4 开发工具与环境 (53)8.5 概要设计 (53)8.6 详细设计 (54)8.7调试结果 (58)实训一基于链表结构的学生记录管理程序1.1问题描述学生信息的管理是一项很大的工程。

设每个学生记录包含学号，姓名，成绩。

使用链表结构来存储学生信息，实现链表的创建，以及在其中插入，删除，遍历记录，对记录按关键字（学号）进行排序并实现文件读写。

1.2输入与输出输入：从键盘输入学生记录创建链表从文件读学生记录创建链表待插入学生记录，待删除记录的关键字输出：将处理完的记录内容输出到屏幕或文件中1.3 需求分析1.定义链表结构；2.编写主函数、菜单函数，确定函数之间的接口；3.编写简单创建链表函数、遍历函数、插入结点函数、创建链表函数、删除结点函数，排序函数；使用多套数据，进行系统调试。

4.编写文件读写函数，实现从文件读数据创建链表，以及将链表中的记录保存到文件中去。

1.4 开发工具与环境硬件设备：微型计算机系统软件环境：操作系统Windows，开发工具VC6.0或TC2.01.5 概要设计数据结构定义typedef struct student{ int code; //学号char name[10]; //姓名int score; //分数struct student *next; //指向下一个学生记录的指针域}stu;2．各函数模块void show_menu();操作结果：显示菜单void scan(stu *p,stu*head);操作结果：从键盘输入学生记录void create(stu *head);操作结果：根据学生记录，创建链表void print(stu *head);操作结果：在屏幕上打印学生记录void printfile(stu *head);操作结果：将学生记录写到文件中void insert(stu *head);操作结果：插入学生记录void del(stu *head);操作结果：根据学号删除学生记录void sort(stu *head);操作结果：根据学号对学生记录进行排序void search(stu *head);操作结果：根据学号对学生记录进行查找1.6详细设计void main(){int no;stu *head;head=(stu *)malloc(sizeof(stu));do{show_menu();scanf("%d",&no);switch(no){case 1:create(head);break;case 2:print(head);break;case 3:insert(head);break;case 4:del(head);break;case 5:sort(head);printf("排序成功！结果为：\n");print(head);break;case 6:search(head);break;case 0:break;default:printf("输入错误！\n");break;}}while(no!=0);printfile(head);}void show_menu(){printf("\n*********主菜单*************\n");printf("*1.新建学生数据*\n");printf("*2.输出学生数据*\n");printf("*3.添加一个学生*\n");printf("*4.删除一个学生*\n");printf("*5.排序*\n");printf("*6.查找*\n");printf("*0.退出*\n");printf("****************************\n");printf("请选择序号：\n");}void scan(stu *p,stu *head){do{printf("\n请输入学号（大于0，退出循环请输0：）\n");scanf("%d",&p->code);if(p->code<0)printf("学号%d:输入错误！\n",p->code);if(p->code==0)return;} while(p->code<0);printf("请输入姓名：\n");scanf("%s",p->name);printf("请输入分数：\n");scanf("%d",&p->score);}void create(stu *head){stu *p,*tail;tail=head;p=(stu *)malloc(sizeof(stu));scan(p,head);while(p->code!=0){tail->next=p;tail=p;p=(stu *)malloc(sizeof(stu));scan(p,head);}tail->next=NULL;}void print(stu *head){stu *p;sort(head);printf("\n学号\t姓名\t\t成绩\n");for(p=head->next;p!=NULL;p=p->next)printf("%-8d%-16s%-8d\n",p->code,p->name,p->score); }void insert(stu *head)//插入学生记录{……}void del(stu *head){int code;stu *p,*q;printf("请输入要删除学生的学号：\n");scanf("%d",&code);p=head;while(p->next!=NULL && p->next->code!=code)p=p->next;if(p->next!=NULL && p->next->code==code){q=p->next;p->next=q->next;printf("学号为%d的学生已被删除！\n",code);}elseprintf("学号为%d的学生不存在！\n",code);}void sort(stu *head)//按照学号对学生记录进行排序{……}void search(stu *head){int code;stu *p;printf("请输入要查找的学号：\n");scanf("%d",&code);p=head->next;while(p!=NULL && p->code<code)p=p->next;if(p!=NULL && p->code==code){printf("\n学号\t姓名\t成绩\n");printf("%d\t%s\t%d\t\n",p->code,p->name,p->score);}elseprintf("学号为%d的学生不存在!\n",code);}void printfile(stu *head){FILE *fp;stu *p;fp=fopen("D:\\student.dat","w+");if(fp!=NULL){fprintf(fp,"学号\t\姓名\t\t成绩\n");for(p=head->next;p!=NULL;p=p->next){fprintf(fp,"%-8d%-16s%-8d\n",p->code,p->name,p->score);}fclose(fp);}else{printf("文件没有打开！\n");}}1.7调试结果在循环菜单提示下选择新建学生数据见图1－1：图1－1在屏幕上输出学生记录见图1－2：图1－2 添加学生记录见图1－3：图1－3按照学号删除学生记录（学号不存在，删除不成功）见图1－4：图1－4根据学号删除学生记录（删除成功）见图1－5：图1－5按照学号对学生记录进行排序见图1－6：图1－6根据学号查找学生记录见图1－7：图1－7实训二基于链表结构的一元多项式相乘2.1问题描述实现将一元多项式从文件读入并以链表结构存储到计算机中，将读入的两个一元多项式相乘，并将相乘结果保存到文件中。