第一篇：数据结构实训心得体会范文
这次课程设计的心得体会通过实习我的收获如下
1、巩固和加深了对数据结构的理解，提高综合运用本课程所学知识的能力。
2、培养了我选用参考书，查阅手册及文献资料的能力。培养独立思考，深入研究，分析问题、解决问题的能力。
3、通过实际编译系统的分析设计、编程调试，掌握应用软件的分析方法和工程设计方法。
4、通过课程设计，培养了我严肃认真的工作作风，逐步建立正确的生产观念、经济观念和全局观念。从刚开始得觉得很难，到最后把这个做出来，付出了很多，也得到了很多，以前总以为自己对编程的地方还不行，现在，才发现只要认真做，没有什么不可能。编程时要认真仔细，出现错误要及时找出并改正，（其中对英语的要求也体现出来了，因为它说明错误的时候都是英语）遇到问题要去查相关的资料。反复的调试程序，最好是多找几个同学来对你的程序进行调试并听其对你的程序的建议，在他们不知道程序怎么写的时候完全以一个用户的身份来用对你的用户界面做一些建议，正所谓当局者迷旁观者清，把各个注意的问题要想到；同时要形成自己的编写程序与调试程序的风格，从每个细节出发，不放过每个知识点，注意与理论的联系和理论与实践的差别。另外，要注意符号的使用，注意对字符处理，特别是对指针的使用很容易出错且调试过程是不会报错的，那么我们要始终注意指针的初始化不管它怎么用以免不必要麻烦。通过近两周的学习与实践，体验了一下离开课堂的学习，也可以理解为一次实践与理论的很好的连接。特别是本组所做的题目都是课堂上所讲的例子，在实行之的过程中并不是那么容易事让人有一种纸上谈兵的体会，正所谓纸上得来终觉浅绝知此事要躬行。实训过程中让我们对懂得的知识做了进一步深入了解，让我们的理解与记忆更深刻，对不懂的知识与不清楚的东西也做了一定的了解，也形成了一定的个人做事风格。
通过这次课程设计，让我对一个程序的数据结构有更全面更进一步的认识，根据不同的需求，采用不同的数据存储方式，不一定要用栈，二叉树等高级类型，有时用基本的一维数组，只要运用得当，也能达到相同的效果，甚至更佳，就如这次的课程设计，通过用for的多重循环，舍弃多余的循环，提高了程序的运行效率。在编写这个程序的过程中，我复习了之前学的基本语法，哈弗曼树最小路径的求取，哈弗曼编码及译码的应用范围，程序结构算法等一系列的问题它使我对数据结构改变了看法。在这次设计过程中，体现出自己单独设计模具的能力以及综合运用知识的能力，体会了学以致用、突出自己劳动成果的喜悦心情，也从中发现自己平时学习的不足和薄弱环节，从而加以弥补。篇二：数据结构试验心得
数据结构课程设计心得体会（专业：计算机科学与技术 姓名：朱文 学号：2011220137）
通讯录管理系统是基于双向循环链表设计而成的信息管理系统。该系统通过对程序进行模块化，建立添加、显示、查找和删除功能的函数，各函数中运用双向循环链表存储数据。为存储通讯录信息，需定义一个结构体类型，成员包括姓名、街道、城市、邮编、国家等，并建立双向循环链表，定义该结构体类型的指针，用于指向各结点。分别建立具有添加、删除、修改、查询等功能的子函数，完成相应功能，对程序实现模块化。这其中要用到对链表的删除、插入等知识。为实现存储功能，需用到文件的相关函数
开发一个通讯录管理系统，借助计算机可以方便、快捷、灵活的管理个人的朋友及相关人员的通讯信息，了解友人相关信息，帮助与友人保持联络。所以设计一个通讯录管理系统管理各人的通讯信息是非常必要的，同时，通过用循环双向链表设计通讯录管理系统可以让我们更好的去理解循环双向链表，更好的学好数据结构这门课程。本次实验中，我们使用分工合作的方式，首先定义了函数的结构体部分，剩下的根据函数所要实现的功能进行分工合作，我实现的是通讯录中删除功能的子函数，删除信息（void delete(dnode *head)）的功能是按照用户输入的姓名首先进行按姓名查询功能，查找成功，则执行删除信息的功能，查询不成功，则提示错误信息。定义结点p，输入要删除的信息的姓名，按姓名查找结点，如果找到匹配的结点p，就进行相关的删除操作，否则就是没找到要删除的数据，最后返回到主函数。
这次实验中我深刻认识到合作的重要性。例如：我所编写的按名删除功能的实现中，应用了章林霞同学所编写写的按名搜索查询功能的那部分函数，在这次实验中，我学到很多东西，加强了我的动手能力，并且培养了我的独立思考能力。我们坚持理论联系实际的思想，以实践证实理论，从实践中加深对理论知识的理解和掌握。实验是我们快速认识和掌握理论知识的一条重要途径。通过这次课程设计，我们对c语言以及数据结构有了更深刻的了解，增强了程序的编写能力，巩固了专业知识，对程序的模块化观念也又模糊逐渐变的清晰了。在程序的运行与调试过程中出现了很多错误，通过反复地复习课本上的相关知识，不停地修改与调试，我们终于完成了这段程序。在调试过程中，我们认识到了数据结构的灵活性与严谨性，同一个功能可以由不同的语句来实现，但编写程序时要特别注意细节方面的问题，因为一个小小的疏忽就能导致整个程序不能运行。我们也认识到了自己的薄弱之处，如对链表相关知识的欠缺，文件运用的不熟练，在以后的学习中我们要集中精力、端正态度，争取把知识学得更扎实、更全面。
经过这次的实验，我们整体对各个方面都得到了不少的提高，希望以后学校和系里能够开设更多类似的实验，能够让我们得到更好的锻炼。也让我们深深感受到讨论交流很重要，遇到困难时，大家一起讨论，加强我们的团队合作精神，同时通过这次的课程设计，我们对 数据结构中双向链表结构有了更深刻的理解。篇三：数据结构综合实验心得体会
心得体会：
做了一个星期的程序设计终于做完了，在这次程序设计课中，真是让我获益匪浅。对大一学习的c语言和这学期开的数据结构，并没有掌握，很多知识都不太懂，突然让自己独立完成一个程序让我手忙脚乱，起码在我认为那真的特别难，看了老师给的题目以及上网查找了一些相关的知识，简单的编了几行就告一段落了，第一天等于只完成了老师要求写的需求分析和概要设计，后来查找了关于哈希表的相关知识，了解了如何创建哈希表，如何合适的构建哈希函数，（选取合适的表长，合适的余数，使得查找时间以及平均查找长度最短）以及什么是除留余数法，和怎样用除留余数法创建哈希表，看懂了之后，我又看了处理冲突的方法，有三种线性探测再散列法法，二次探测再散列法，伪随机数序列法三种，而我所要做的是第一种线性探测再散列的方法，相较后两种要简单很多，在遇到冲突的时候地址加一，知道冲突解决。
在了解这些概念以后，我就开始着手编程序了，在遇到问题的时候请教我们班擅长的同学，慢慢把不能不会不理解的地方给弄明白了，在经过很多次调试以后，一些基本功能已经可以实现了，为了使平均查找长度越小越好，我不断尝试新的表长以及除数，在没有出现错误的基础上，将功能实现，最后，终于在周四的时候将所有的程序调试完全。这次的综合性实验使我了解到，平时对知识的积累相当重要，同时也要注重课上老师的讲解，老师在课上的延伸是课本上所没有的，这些知识对于我们对程序的编写有很大的作用，同时，编程也要求我们有足够的耐心，细细推敲。越着急可能就越无法得到我们想要的结果，遇到不会的问题要多多请教，知识是在实践与向别人请教的过程中积累的，所以问是至关重要的，只要肯下功夫很多东西都是可以完成的。篇四：数据结构实验报告及心得体会 2011~2012第一学期数据结构实验报告
班级：信管一班
学号：201051018 姓名：史孟晨 实验报告题目及要求
一、实验题目 设某班级有m（6）名学生，本学期共开设n（3）门课程，要求实现并修改如下程 序（算法）。
1.输入学生的学号、姓名和 n 门课程的成绩（输入提示和输出显示使用汉字系统），输出实验结果。（15分）
2.计算每个学生本学期 n 门课程的总分，输出总分和n门课程成绩排在前 3 名学
生的学号、姓名和成绩。
3.按学生总分和 n 门课程成绩关键字升序排列名次，总分相同者同名次。
二、实验要求 1．修改算法。将奇偶排序算法升序改为降序。（15分）2．用选择排序、冒泡排序、插入排序分别替换奇偶排序算法,并将升序算法修改为
降序算法。（45分））3．编译、链接以上算法，按要求写出实验报告（25）。4.修改后算法的所有语句必须加下划线，没做修改语句保持按原样不动。5．用a4纸打印输出实验报告。
三、实验报告说明
实验数据可自定义，每种排序算法数据要求均不重复。(1)实验题目：《n门课程学生成绩名次排序算法实现》；(2)实验目的：掌握各种排序算法的基本思想、实验方法和验证算法的准确性；(3)实验要求：对算法进行上机编译、链接、运行；(4)实验环境（windows xp-sp3,visual c++)；(5)实验算法（给出四种排序算法修改后的全部清单）；(6)实验结果（四种排序算法模拟运行后的实验结果）；(7)实验体会（文字说明本实验成功或不足之处）。
三、实验源程序（算法）score.c #include stdio.h #include string.h #define m 6 #define n 3 struct student { char name[10];int number;int score[n+1];
/*score[n]为总分,score[0]-score[2]为学科成绩*/ }stu[m];void changesort(struct student a[],int n,int j){int flag=1,i;struct student temp;while(flag){ flag=0;for(i=1;i /*对所有奇数项进行一遍比较*/ if(a[i].score[j]>a[i+1].score[j]) { temp=a[i];a[i]=a[i+1];a[i+1]=temp;flag=1;} for(i=0;i a[i]=a[i+1]; a[i+1]=temp;flag=1;} } } void print_score(struct student a[],int n,int j){ int i,k;printf(“ 奇偶交换 成绩 %d 排序表,j+1);printf(n);printf(名 次 学 号 姓 名 分 数n);k=1;for(i=0;k printf(%4d,a[i].number);printf（%s,a[i].name); printf(%6d,a[i].score[j]);printf(n);} } main(){ int i,j,k;for(i=0;i 名:);scanf(%s,stu[i].name);printf(编 号:);scanf(%4d,&stu[i].number);printf(数据结构:);scanf(%4d,&stu[i].score[0]);printf(离散数学:);scanf(%4d,&stu[i].score[1]);printf(大学英语:);scanf(%4d,&stu[i].score[2]);} for(i=0;i { stu[i].score[n]=0;for(j=0;j 山东科技大学泰山科技学院 课程实训说明书 课程： 数据结构项目实训 题目： 院 系： 信息工程系 2014年 5月 25日 专业班级： 学 号： 学生姓名： 指导教师： 目 录 一、设计题目..........................................................3 1.1 顺序表操作.........................................................3 1.2 链表操作..........................................................3 1.3 二叉树的基本操作..................................................3 二、运行环境（软、硬件环境）.......................................3 2.1 软件环境..........................................................3 2.2 硬件环境..........................................................3 三、数据结构及算法设计的思想.......................................3 3.1 顺序表设计构思.....................................................3 3.2 链表设计构思......................................................4 3.3 二叉树设计构思....................................................4 四、源代码............................................................5 5.1 顺序表源代码......................................................5 5.2 链表源代码........................................................6 5.3 二叉树源代码......................................................8 五、运行结果分析.....................................................11 6.1 顺序表运行结果...................................................11 6.2 链表运行结果.....................................................13 6.3 二叉树运行结果...................................................15 七、实习总结........................................................18 一、设计题目 1.1链表操作 1.1.1 设计目的 ? 掌握线性表的在顺序结构和链式结构实现。? 掌握线性表在顺序结构和链式结构上的基本操作。1.1.2 设计内容和要求 利用顺序表链表的插入运算建立线性链表，然后实现链表的查找、插入、删除、计数、输出、排序、逆置等运算（查找、插入、删除、查找、计数、输出、排序、逆置要单独写成函数），并能在屏幕上输出操作前后的结果。1.2二叉树的基本操作 1.2.1 设计目的 ? 掌握二叉树的概念和性质 ? 掌握任意二叉树存储结构。? 掌握任意二叉树的基本操作。 1.2.2 设计内容和要求(1)对任意给定的二叉树（顶点数自定）建立它的二叉链表存储结构，并利用栈的五种基本运算（置空栈、进栈、出栈、取栈顶元素、判栈空）实现二叉树的先序、中序、后序三种遍历，输出三种遍历的结果。(2)求二叉树高度、结点数、度为1的结点数和叶子结点数。 题目：在火车货场车皮编解场，2条轨道连接到2条侧轨道，形成2个铁路转轨栈，其中左边轨道为车皮入口，编号为A；右边轨道为出口，编号为D；2个铁路转轨栈分别编号为C和D如下图所示。编号为a, b, c, ┅, n的各车皮依序停放在车皮的入口处，调度室要安排个车皮进出栈次序，使得在出口处各车皮按照预先制定的顺序依次出站。车皮移动时只能按照从左到右的方向移动。组织与指导老师： 组长：* 成员：*** 指导教师：* 完成时间、地点： 时间：第16周（6月6日～6月10日） 地点：南校区东教学楼2楼机房。 一、需求分析 1、问题描述 掌握队列、栈、树的结构以及基本操作，熟悉for循环语句，if条件语句的嵌套，结构体函数等，从而实现程序的功能。 例如： typedef struct Stack { Data *data; Data *end; }Stack; …… 2、实现功能 （1）对于给定的车皮数n，以及各车皮的出站顺序，编程计算最优调度方案，使得移动车皮的次数最少。 （2）数据输入：由文件input.txt给出数据。第一行有1个正整数n，表示车皮数；接下来的1行是一个字符串，表示预先确定的车皮的出站顺序。 （3）数据输出：将计算得到的最优调度方案输出到文件output.txt，文件的第一行使最少移动次数m，接下来的m行使对于最优方案的m次移动。每次移动用“cXY”的3个字符表示，其中c表示车皮编号，X表示其时栈号，Y表示目标栈号。如果无法调度则输出“No Solution!” 二、概要设计 1、抽象数据类型 void ReadData(void) { int i; FILE *fp; fp = fopen(“input.txt”, “r”); if(fp == NULL) exit(__COUNTER__); fscanf(fp, “%d”, &total); if(total < 1) { fclose(fp); exit(__COUNTER__); } ……、void Show(Stack a, char *s) { char *tmp, *pc; char *p =(char*)a.data; pc = tmp =(char*)malloc(total + 1); while(p <= a.end) *pc++ = *p++; *pc = 0; printf(“%s%s”, tmp, s); } …… if(d == end) { if(min > count) { min = count; strcpy(res, tmp); return; } } count++; if(A.end >= A.data) a = *A.end; else a = EOD; …… 2、程序中包含功能模块及模块间的调用关系 各个基本操作都通过公有成员函数实现，然后通过主程序调用来实现程序的功能。 例如： void Init(Stack *a, int len) { a->data =(Data*)malloc(len * sizeof(Data)); memset(a->data, 0, len * sizeof(Data)); a->end = a->data-1; } …… void main(void) { ReadData(); Calc(head); End(); } 三、调试分析 完成情况说明： 编译程序的过程中发现了许多漏洞，调试起来很不方便，经过我和同学的共同努力，终于有了突破性的进展，程序按照预定的时间调试出来了，虽然当中还存在不少的漏洞，但不会影响程序的正常运行。 程序的性能分析：各个操作都是通过公有函数的调用来实现的，其中用到结构体函数，for循环，If语句的嵌套等，通过测试可以实现其预定的功能。出现的问题及解决方案： 缺失头文件导致的定义无效错误，通过添加头文件即可解决问题；定义字符类型错误，使用正确的函数类型定义即可，for循环的循环语句语法使用不当，导致函数无法实现循环，if条件语句的应用还存在问题，以上所述的编译错误都通过我很同学的认真分析后纠正了。 四、用户使用说明 了解程序的执行过程，输入合法的数值是程序正常运行的关键，输入的数值和开始需要的字符的长度要符合五、心得体会： 通过多次编写程序，我总结出来一条心得，程序不能写完才调试，而是应该写一个函数调试一个函数，这样才能缩小调试的范围，提高编程的效率，程序编完后在进行一次综合调试，将不完善的函数和功能处理好，才能将程序做到最好！而且，很多时候，一个大的工程并不是一个人就能完成，这就要求我们有团队精神。让我感受最深的是在我调试程序的时候，一个很细微的错误就可能导致程序的出错，正所谓的“细节决定成败”，不管是在学习中，生活中，我们都要有一颗善于发现问题，解决问题的新，除此之外，还要有乐于助人的精神。 （数据结构实训报告） 目录 一、实训目的...........................................................1 二、实训题目...........................................................1 三、实训步骤...........................................................2 四、实训内容...........................................................2 五、实训心得..........................................................19 六、参考文献..........................................................19 吉林工业职业技术学院 数据结构实训 一、实训目的 通过实训，对所学数据结构和程序设计的基本知识和基本理论有更进一步的了解和认识，将理论和实际相结合，能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来。主要是培养学生综合利用C语言进行程序设计的能力和创新能力以及综合解决问题的能力。运用算法分析与程序设计的一般方法进行实际项目的开发。本次实训尽量选取与实际结合紧密或学生比较感兴趣的项目，本次实训学生需要具备熟练的程序设计基础、数据结构和计算机应用基础知识，具备程序编写、调试的基本能力，具有一定的文字表达和报告撰写能力，具备办公软件使用能力。 通过实训，考查语言基本概述掌握是否牢固，并考查与后续课程较为密切的结构体，链表，文件的运用熟练程度，加强对基本概念的理解和复习，最重要的是了解基本软件的设计步骤，还有对软件调试的掌握。能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养基本的、良好的程序设计技能。 二、实训题目 （一）单项题目 1、二叉树遍历 【问题描述】建立二叉树，实现二叉树的先序遍历、中序、后序和层序遍历（用递归或非递归的方法都可以）。 【要 求】编写菜单程序。能够输入二叉树的各个结点，并能够输出用不同方法遍历的遍历序列；分别建立二叉树存储结构的输入函数、输出先序遍历序列的函数；输出中序遍历序列的函数；输出后序遍历序列的函数；输出层序遍历序列的函数。 （二）综合题目 1、图书管理系统 吉林工业职业技术学院 数据结构实训 【问题描述】建立一个图书信息文件，包括书号（num）、书名（bookname）、作者（name）、出版社（publish）、价格（price）等。 【要 求】建立一个图书信息文件，包括书号（num）、书名（bookname）、作者（name）、出版社（publish）、价格（price）等。 三、实训步骤 1、问题分析 正确理解问题，分析问题究竟“做什么”，分析问题已知的信息及其作用，分析在解决中对信息处理的规则、要求、限制条件，分析问题解决后应该输出什么样的结果（输出形式、格式、内容）。并分析得出判定结果是否正确的标准。 2、设计分析 得出解决问题的思路、主要流程、采用的数据结构类型的说明、主要算法的思想。 3、设计方案 采用的数据结构类型的定义、主要算法的描述及说明。 4、详细设计 根据问题要求和已得到的算法编写程序。 5、调试程序 发现程序中存在的语法错误和一些逻辑错误，并修改，使程序能够运行。 6、运行程序 选择若干具有代表性的输入数据（包括合理数据和不合理数据），进行测试，尽量使程序的各语句和分支都被检查到，以便发现程序中的错误和漏洞，以便改进算法和程序。 7、使用说明 包括程序源代码、算法（程序）流程图、开发过程中各阶段的有关记录、算法的正确性证明、程序的测试结果、对输入输出要求及格式的详细描述。 四、实训内容 （一）个人题目 1、二叉树遍历 【问题描述】建立二叉树，实现二叉树的先序遍历、中序、后序和层序遍历（用递归或非递归的方法都可以）。吉林工业职业技术学院 数据结构实训 【要 求】编写菜单程序。能够输入二叉树的各个结点，并能够输出用不同方法遍历的遍历序列；分别建立二叉树存储结构的输入函数、输出先序遍历序列的函数；输出中序遍历序列的函数；输出后序遍历序列的函数；输出层序遍历序列的函数。 【设计分析】 1、总体设计(基本概念)树的概念 树（Tree）是n（n>=0）个结点的有限集。在任意一棵非空树中： 1)有且仅有一个特定的称为根的结点； 2)当n>1时，其余结点可分为m（m>0）个互不相交的有限集T1，T2......Tm，其中每一个集合又是一棵树，并且称为根的子树（SubTree）。 【例】如图1所示： 图1 图1是有8个结点的树，其中A是根，其余结点分成2个互不相交的子集：T1={B，D}，T2={C，E，F，G，H}；T1和T2都是根A的子树，且本身也是一棵树。 【设计方案】1．创建二叉树（可从键盘输入各结点的值）2．按某种方式对二叉树进行遍历 3．树型结构是一种非常重要的非线性结构。树在客观世界是广泛存在的，在计算 机领域里也得到了广泛的应用。在编译程序里，也可用树来表示源程序的语法结构，在数据库系统中，数形结构也是信息的重要组织形式。 4．节点的有限集合（N大于等于0）。在一棵非空数里：（1）、有且仅有 吉林工业职业技术学院 数据结构实训 一个特定的根节点；（2）、当N大于1时，其余结点可分为M（M大于0）个互不相交的子集，其中每一个集合又是一棵树，并且称为根的子树。树的定义是以递归形式给出的。 5．二叉树是另一种树形结构。它的特点是每个结点最多有两棵子树，并且，二叉 树的子树有左右之分，其次序不能颠倒。 从二叉树的递归定义可知，一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此，在任一给定结点上，可以按某种次序执行三个操作：（1）访问结点本身(N)，（2）遍历该结点的左子树(L)，（3）遍历该结点的右子树(R)。以上三种操作有六种执行次序： NLR、LNR、LRN、NRL、RNL、RLN。【详细设计】本程序源代码如下： /*源程序*/ /* Note:Your choice is C IDE */ #include “stdio.h” #include typedef char DataType;#define MaxStackSize 50 using namespace std; typedef struct Node { DataType data; struct Node *leftChild; struct Node *rightChild; }BiTreeNode;typedef BiTreeNode* DataType2;typedef struct { DataType2 stack[MaxStackSize];吉林工业职业技术学院 数据结构实训 int top;} SeqStack;typedef struct { DataType2 quene[MaxStackSize]; int front; int rear;}Quene;void StackInitiate(SeqStack *S) { S->top = 0;} int StackNotEmpty(SeqStack S){ if(S.top <= 0)return 0; else return 1;} int StackPush(SeqStack *S, DataType2 x){ if(S->top >= MaxStackSize) { printf(“堆栈已满无法插入!n”); return 0; } else { S->stack[S->top] = x; S->top ++; return 1; } } int StackPop(SeqStack *S, DataType2 *d){ if(S->top <= 0) { printf(“堆栈已空无数据元素出栈!n”); return 0; } else { S->top--; *d = S->stack[S->top]; return 1;吉林工业职业技术学院 数据结构实训 } } int StackTop(SeqStack S, DataType2 *d){ if(S.top <= 0) { printf(“堆栈已空!n”); return 0; } else { *d = S.stack[S.top-1]; return 1; } } typedef struct node{ char data;struct node *lchild;struct node *rchild;}BTNode; typedef BTNode *BTree; int NodeNum,leaf; BTree CreatBTree(void){BTree T;char ch;if((ch=getchar())=='*')return(NULL); else{ T=(BTNode *)malloc(sizeof(BTNode));T->data=ch;T->lchild=CreatBTree();T->rchild=CreatBTree();return(T);} } void Preorder(BTree T)吉林工业职业技术学院 数据结构实训 { if(T){ printf(“%c”,T->data); Preorder(T->lchild); Preorder(T->rchild);} } void Inorder(BTree T){ if(T){ Inorder(T->lchild); printf(“%c”,T->data); Inorder(T->rchild);} } void Postorder(BTree T){ if(T){ Postorder(T->lchild); Postorder(T->rchild); printf(“%c”,T->data);} } int TreeDepth(BTree T){ int hl,hr,max;if(T){ hl=TreeDepth(T->lchild); hr=TreeDepth(T->rchild); max=hl>hr?hl:hr; NodeNum=NodeNum+1; if(hl==0&&hr==0) leaf=leaf+1; return(max+1);} 吉林工业职业技术学院 数据结构实训 else return(0);} void Levelorder(BTree T){ int front=0,rear=1;BTNode *cq[Max],*p;cq[1]=T;while(front!=rear){ front=(front+1)%NodeNum; p=cq[front]; printf(“%c”,p->data); if(p->lchild!=NULL) { rear=(rear+1)%NodeNum; cq[front]=p->lchild; cq[rear]=p->lchild; } if(p->rchild!=NULL) { rear=(rear+1)%NodeNum; cq[front]=p->rchild; cq[rear]=p->rchild; } } } void main(){ BTree root;int i,depth;printf(“n”);printf(“创建二叉树，请输入完全二叉树的先序序列，用*代表虚结点:”);root=CreatBTree();//返回根结点 do{ 吉林工业职业技术学院 数据结构实训 printf(“t1:先序遍历n”);printf(“t2:中序遍历n”);printf(“t3:后序遍历n”);printf(“t4:深度、结点数、叶子数n”);printf(“t5:层次遍历n”);printf(“备注：选择层次遍历之前，需要先选择4，求出该树的结点数。”); printf(“t0:Exitn”); scanf(“%d”,&i);//输入菜单序号 switch(i) { case 1:printf(“先序遍历结果为:”); Preorder(root); break; case 2:printf(“中序遍历结果为:”); Inorder(root); break; case 3:printf(“后序遍历结果为:”); Postorder(root); break; case 4:depth=TreeDepth(root); printf(“深度=%d 结点数=%d”,depth,NodeNum); printf(“叶子数=%d”,leaf); break; case 5:printf(“层次遍历为:”); Levelorder(root); break; default:exit(1); } printf(“n”);} while(i!=0);} 吉林工业职业技术学院 数据结构实训 【使用说明】本程序在turboc 2.0环境下运行，迷宫大小为20×20，需要修改迷宫大小时，可以修改程序中N值的大小。迷宫图由系统自动随机生成，每次生成的迷宫图是不同的。按enter健显示最终搜索结果。按Q健退出程序。 【运行调试】 图（1）二叉树遍历主界面 图（2） （二）综合题目 1、图书管理系统 【问题描述】建立一个图书信息文件，包括书号（num）、书名（bookname）、作者（name）、出版社（publish）、价格（price）等。 【要 求】编写菜单程序，功能包括：建立图书信息、插入记录，删除记录、修改记录、按照书号或书名查询记录、显示记录、根据图书价格进行排序。定义图书信息结构体名称为book。书号（num）、书名（bookname）、作者（name）、出版社（publish）均为字符型数组。价格（price）为单精度型数据。 吉林工业职业技术学院 数据结构实训 【设计分析】系统目标分析 每个学校都有图书馆，最初由于图书数量和种类较少，人工手动管理比较方便和灵活。随着社会的发展，图书的数量和种类越来越多，人工手动管理会降低工作的效率，希望建立一个图书馆图书信息管理系统，是为了解决了人工手动管理图书信息在实践的问题，从而达到系统化、规范化、标准化的水平。该系统的建立不但给管理者带来了方便，也节省了工作时间从而提高了工作效率。 在构造系统时，首先从需求出发构造数据库表，然后再由数据库表结合需求划分系统功能模块。这样，就把一个大的系统分解成了几个小系统。这里把系统的层次划分为了三个部分：一个自由态：即面向任何用户的界面，提供登录功能，以便不同身份的用户登录子系统；一个是一般用户态：即图书有服务子系统；还有一个是管理员界面：提供图书的管理和维护功能。对于不同子系统之间的功换，采用了登录功能和用户注销功能。系统划分了子系统后，下一步的工作是继续划分子系统的小模块。先考虑在进入子系统时应该做什么，进入系统之后又应该做什么，提供那些服务等。例如，对于图书信息服务子系统，在用户进入时首先得调用相关数据库表，找出用户的图书借阅情况；进入系统后，子系统得提供图书查询、图书借阅和还书功能。另外，针对本系统的特殊情况，同时也考虑系统的可移植性，在系统中增加了数据库路径的维护部分。最后，考虑到系统的安全性，还在系统中特别增加了“加密界面”的功能。 【设计方案】本数据库管理系统主要由图书检索、图书管理、数据维护、图书统计、打印输出、系统维护六大模块组成, 如图1 所示。各模块功能如下： 1、主控模块主控模块的功能是控制各个分支模块,它是实现各模块功能的总控制台 2、图书检索模块是图书管理系统的重要模块之一,是读者快速查询图书的途径 本模块的功能是按书名、书号、作者、出版社、图书分类查询 数据维护模块是由图书管理员控制的模块,它由增加、修改和删除读者,增加、修改删除图书,浏览修改读者、浏览修改图书等程序组成。在软件设计时考虑到读者编号、书名、书号是唯一的,因此,在修改读者或图书中,读者记录或图书记录一经登记“读者编号”和“姓名”便不能修改,在删除读者或图书时只要读者有借出图书未还或库存图书原有数量与现有库存量不符便不能删除。 5、数据统计模块由读者统计、图书统计、借出图书分类统计、到期未归还图书读者统计几部分组成 吉林工业职业技术学院 数据结构实训 我们小组的信息系统开发课程设计题目是：图书管理系统开发。系统开发的总的设计目标是实现图书管理的系统化、规范化和自动化，实现对图书资料的集中统一的管理。 本系统主要实现对图书馆信息的管理，主要功能为管理有关读者，书籍，借阅和管理者的信息等。本系统结构分为读者信息管理模块，书籍信息管理模块，借阅信息管理模块，管理者信息管理模块。读者信息管理部分有两方面的功能，可以浏览读者的信息，可以对读者信息进行维护。书籍信息管理可以浏览书籍的信息，可以对书籍信息进行维护。借阅信息管理可以显示当前数据库中书籍借阅情况，可以对借阅信息进行维护。管理者信息管理可以显示数据库中管理者的情况，可以对管理者信息进行维护。可见，本系统并不复杂，主要解决的问题是利用关键字对数据库进行查询。 【详细设计】本程序源代码如下： /*源程序*/ /* Note:Your choice is C IDE */ /* Note:Your choice is C IDE */ #include struct books_list { char author[20]; /*作者名*/ char bookname[20]; /*书名*/ char publisher[20]; /*出版单位*/ char pbtime[15]; /*出版时间*/ char loginnum[10]; /*登陆号*/ float price; /*价格*/ char classfy[10]; /*分类号*/ struct books_list * next;/*链表的指针域*/ };吉林工业职业技术学院 数据结构实训 struct books_list * Create_Books_Doc(); /*新建链表*/ void InsertDoc(struct books_list * head);/*插入*/ void DeleteDoc(struct books_list * head , int num);/*删除*/ void Print_Book_Doc(struct books_list * head);/*浏览*/ void search_book(struct books_list * head);/*查询*/ void info_change(struct books_list * head);/*修改*/ void save(struct books_list * head);/*保存数据至文件*/ /*浏览操作*/ void Print_Book_Doc(struct books_list * head){ struct books_list * p;if(head==NULL || head->next==NULL)/*判断数据库是否为空*/ { printf(“n ━━━━ 没有图书记录!━━━━nn”); return;} p=head;printf(“┏━━━┳━━━┳━━━┳━━━┳━━━━┳━━━┳━━━┓n”);printf(“┃登录号┃书名 ┃ 作者 ┃出版单位┃出版时间┃分类号┃价格┃n”); printf(“┣━━━╋━━━╋━━━╋━━━╋━━━━╋━━━╋━━━┫n”);/*指针从头节点开始移动，遍历至尾结点，依次输出图书信息*/ while(p->next!= NULL){ p=p->next; printf(“┃%-6.6s┃%-10.10s┃%-10.10s┃%-10.10s┃%-12.12s┃%-6.6s┃%.2f ┃n”,p->loginnum,p->bookname,p->author,p->publisher,p->pbtime,p->classfy,p->price);/*循环输出表格*/ } printf(“┗━━━┻━━━┻━━━┻━━━┻━━━━┻━━━┻━━━┛n”);printf(“n”);吉林工业职业技术学院 数据结构实训 } /*删除操作*/ void DeleteDoc(struct books_list * head){ struct books_list *s,*p; /*s为中间变量，p为遍历时使用的指针*/ char temp[20];int panduan;/*此变量用于判断是否找到了书目*/ panduan=0;p=s=head;printf(“ [请输入您要删除的书名]:”);scanf(“%s”,temp);/*遍历到尾结点*/ while(p!= NULL) { if(strcmp(p->bookname,temp)==0) { panduan++; break; } p=p->next;} if(panduan==1){ for(;s->next!=p;) /*找到所需删除卡号结点的上一个结点*/ { s=s->next; } s->next=p->next;/*将后一节点地址赋值给前一节点的指针域*/ free(p); printf(“n ━━━━ 删除成功!━━━━n”);} else /*未找到相应书目*/ 吉林工业职业技术学院 数据结构实训 { printf(“ 您输入的书目不存在，请确认后输入!n”);} return;} int main(void){ struct books_list * head; char choice;head=NULL;for(;;)/*实现反复输入选择*/ { printf(“ ┏━━━━━━━━━━━━━━━━━━━┏━┓n”); printf(“ ┃ ┃ socat 图书管理系统 ┃ ┃n”); printf(“ ┃ ┗━━━━━━━━━━━━━━━━━━━┛ ┃n”); printf(“ ┃ ●[1]图书信息录入 ┃n”); printf(“ ┃ ┃n”); printf(“ ┃ ●[2]图书信息浏览 ┃n”); printf(“ ┃ ┃n”); printf(“ ┃ ●[3]图书信息查询 ┃n”); printf(“ ┃ ┃n”); printf(“ ┃ ●[4]图书信息修改 ┃n”); printf(“ ┃ ┃n”); printf(“ ┃ ●[5]图书信息删除 ┃n”); printf(“ ┃ ┃n”); printf(“ ┃ ●[6]退出系统 ┃n”); printf(“ ┗━━━━━━━━━━━━━━━━━━━━━━━┛ 15 吉林工业职业技术学院 数据结构实训 n”); printf(“ 请选择:”); fflush(stdin); scanf(“%c”,&choice); if(choice=='1') { if(head==NULL) { head=Create_Books_Doc(); } InsertDoc(head); } else if(choice=='2') { Print_Book_Doc(head); } else if(choice=='3') { search_book(head); } else if(choice=='4') { info_change(head); } else if(choice=='5') { struct books_list *s,*p; /*s为中间变量，p为遍历时使用的指针*/ char temp[20];int panduan;/*此变量用于判断是否找到了书目*/ panduan=0;p=s=head;printf(“ [请输入您要删除的书名]:”);吉林工业职业技术学院 数据结构实训 scanf(“%s”,temp);/*遍历到尾结点*/ while(p!= NULL) { if(strcmp(p->bookname,temp)==0) { panduan++; break; } p=p->next;} if(panduan==1){ for(;s->next!=p;) /*找到所需删除卡号结点的上一个结点*/ { s=s->next; } s->next=p->next;/*将后一节点地址赋值给前一节点的指针域*/ free(p); printf(“n ━━━━ 删除成功!━━━━n”);} else /*未找到相应书目*/ { printf(“ 您输入的书目不存在，请确认后输入!n”);} return; } else if(choice=='6') { printf(“n”); printf(“ ━━━━━━━━ 感谢使用图书管理系统 ━━━━━━━━n”);吉林工业职业技术学院 数据结构实训 break; } else { printf(“ ━━━━ 输入错误，请重新输入！━━━━”); break; } } } 【使用说明】本程序在turboc 2.0环境下运行，迷宫大小为20×20，需要修改迷宫大小时，可以修改程序中N值的大小。迷宫图由系统自动随机生成，每次生成的迷宫图是不同的。按enter健显示最终搜索结果。按Q健退出程序。 【运行调试】 图（3）图书管理系统主界面 吉林工业职业技术学院 数据结构实训 图（4）图书信息浏览 五、实训心得 六、参考文献 实验一 线性表 1.实验要求 1.1 掌握数据结构中线性表的基本概念。 1.2 熟练掌握线性表的基本操作：创建、插入、删除、查找、输出、求长度及合并并运算在顺序存储结构上的实验。1.3 熟练掌握链表的各种操作和应用。2.实验内容 2.1 编写一个函数，从一个给定的顺序表A中删除元素值在x到y之间的所有元素，要求以较高效率来实现。 2.2 试写一个算法，在无头结点的动态单链表上实现线性表插入操作 2.3 设计一个统计选票的算法，输出每个候选人的得票结果。 3.实验代码 2.1代码： #include A[i-k]=A[i];i++;} return(n-k);} void main(){ int i,j;int a[maxsize];printf(“输入%d个数:n”,maxsize);for(i=0;i scanf(“%d,”,&a[i]); 数据结构实验报告 j=del(a,maxsize,1,3); printf(“输出删除后剩下的数:n”); for(i=0;i ”n,a[i]);} 2.2代码： INSERT(L,i,b)。 void Insert(Linklist &L,int i,elemtype x){ if(!L){ L=(Linklist)malloc(sizeof(Lnode)); (*L).data=x;(*L).next=NULL;} else { if(i==1) { s=(Linklist)malloc(sizeof(Lnode)); s->data=x;s->next=L;L=s; } else { p=L;j=1; while(p&&j {j++;p=p->next;} if(p||j>i-1) return error; s=(Linklist)malloc(sizeof(Lnode)); s->data=x;s->next=p->next;p->next=s; } } } 2.3代码： typedef int elemtype typedef struct linknode { elemtype data;struct linknode *next;}nodetype; 数据结构实验报告 nodetype *create(){ elemtype d;nodetype h=NULL,*s,*t;int i=1;printf(“建立单链表:n”);while(1){ printf(“输入第%d个结点数据域”,i); scanf(“%d”,&d); if(d==0)break; if(i==1) { h=(nodetype *)malloc(sizeof(nodetype)); h->data=d;h->next=NULL;t=h; } else { s=(nodetype *)malloc(sizeof(nodetype)); s->data=d;s->next=NULL;t->next=s; t=s; } i++;} return h;} void sat(nodetype *h,int a[]){ nodetype *p=h;while(p!=NULL){ a[p->data]++; p=p->next;} } void main(){ int a[N+1],i;for(i=0;i a[i]=0;nodetype *head;head=create();sat(head,a); 数据结构实验报告 } printf(“候选人:”);for(i=1;i<=N;i++)printf(“%3d”,i);printf(“n得票数n”);for(i=1;i<=N;i++)printf(“%3d”,a[i]);printf(“n”);4.实验小结 线性表是最简单的、最常用的一种数据结构，是实现其他数据结构的基础。 实验二 栈与队列 1.实验要求 1.1 了解栈和队列的特性，以便灵活运用。1.2 熟练掌握栈和有关队列的各种操作和应用。 2.实验内容 2.1 设一个算术表达式包括圆括号，方括号和花括号三种括号，编写一个算法判断其中的括号是否匹配。 3.实验代码 2.1代码： #include 数据结构实验报告 gets(str);deal(str);printf(“正确!”);getchar();return 0;} void deal(char *str){ list *L;L=(list *)malloc(sizeof(list));if(!L){ printf(“错误!”);exit(-2);} L->next=NULL;while(*str){ if(*str=='('||*str=='['||*str=='{') push(*str,L);else if(*str==')'||*str==']'||*str=='}') if(pop(*str,L)) {puts(“错误,请检查!”); puts(“按回车键退出”); getchar();exit(-2); } str++;} if(L->next){ puts(“错误,请检查!”);puts(“按任意键退出”);getchar();exit(-2);} } void push(char c,list *L){ list *p;p=(list *)malloc(sizeof(list));if(!p){ printf(“错误!”);exit(-2); 数据结构实验报告 } p->str=c;p->next=L->next;L->next=p;} #define check(s)if(L->next->str==s){p=l->next;L->next=p->next;free(p);return(0);} int pop(char c,list *L){ list *p;if(L->next==NULL)return 1;switch(c){ case')':check('(')break;case']':check('[')break;case'}':check('{')break;} return 1; 4.实验小结 栈和队列是最基础的一种数据结构之一，为实现其他数据结构的奠定基石。 实验三 树 1.实验要求 1.1 掌握二叉树，二叉树排序数的概念和存储方法。1.2 掌握二叉树的遍历算法。 1.3 熟练掌握编写实现树的各种运算的算法。 2.实验内容 2.1 编写程序，求二叉树的结点数和叶子数。 2.2 编写递归算法，求二叉树中以元素值为X的结点为根的子数的深度。2.3 编写程序，实现二叉树的先序，中序，后序遍历，并求其深度。 数据结构实验报告 3.实验代码 2.1代码： #include bt=(struct node *)malloc(sizeof(bnode)); bt->data=ch; bt->lchild=creat(); bt->rchild=creat();} return bt;} int n=0,n1=0;void preorder(blink bt){ if(bt){ n++; if(bt->lchild==NULL&&bt->rchild==NULL) n1++; preorder(bt->lchild); preorder(bt->rchild);} } void main(){ blink root;root=creat();preorder(root);printf(“此二叉数的接点数有:%dn”,n);printf(“此二叉数的叶子数有:%dn”,n1);} 数据结构实验报告 2.2代码： int get_deep(bitree T,int x){ if(T->data==x){ printf(“%dn”,get_deep(T));exit 1;} else { if(T->lchild)get_deep(T->lchild,x);if(T->rchild)get_deep(T->rchild,x);} int get_depth(bitree T){ if(!T)return 0;else { m=get_depth(T->lchild);n=get_depth(T->rchild);return(m>n?m:n)+1;} } 2.3代码： #include 数据结构实验报告 bt->lchild=creat();bt->rchild=creat();} return bt;} void preorder(blink bt){ if(bt){ printf(“%c”,bt->data);preorder(bt->lchild);preorder(bt->rchild);} } void inorder(blink bt){ if(bt){ inorder(bt->lchild);printf(“%c”,bt->data);inorder(bt->rchild);} } void postorder(blink bt){ if(bt){ postorder(bt->lchild);postorder(bt->rchild);printf(“%c”,bt->data);} } int max(int x,int y){ if(x>y)return x;else return y;} int depth(blink bt){ if(bt)return 1+max(depth(bt->lchild),depth(bt->rchild));else 数据结构实验报告 } { return 0;void main()blink root; root=creat();printf(“n”);printf(“按先序排列:”); preorder(root);printf(“n”); printf(“按中序排列:”);inorder(root);printf(“n”);printf(“按后序排列:”); postorder(root);printf(“n”); } printf(“此二叉数的深度是:”);printf(“depth=%dn”,depth(root));4.实验小结 通过本章学习实验，对树有了初步的认识。树就是一种非线性的数据结构，描述了客观世界中事物之间的层次关系。这种结构有着广泛的应用，一切具有层次关系的问题都可以用树来表示。 实验四 图 1.实验要求 1.1 熟悉图的各种存储方法。 1.2 掌握遍历图的递归和非递归的算法。1.3 理解图的有关算法。 2.实验内容 2.1 写出将一个无向图的邻接矩阵转换成邻接表的算法。 数据结构实验报告 2.2 以邻接表作存储结构，给出拓扑排序算法的实现。 3.实验代码 2.1代码： void mattolist(int a[][],adjlist b[],int n)/*n为图的结点个数*/ { for(i=0;i /*邻接表置空*/ for(i=0;i /*逐行进行*/ } 2.2代码： typedef struct vexnode { VertexType vertex;int in;/*增加一个入度域*/ ArecNodeTp * fristarc;for(j=n-1;j>=0;j--) if(a[i][j]!=0){p=(arcnodetp *)malloc(sizeof(arcnodetp));/*产生邻接点*/ p->adjvex=j; p->nextare=b[i].firstare;b[i].firstarc=p;} }AdjList[vnum];typedef struct graph { AdjList adjlist;int vexnum,arcnum;}GraphTp;Top_Sort(GraphTp g) 数据结构实验报告 { LstackTp *p;/*建立入度为0的顶点栈S*/ int m,i,v; initStack(S); } for(i=0;i } if(m 通过本章学习实验，对图有了具体的认识。图也是一种非线性的数据结构，这种结构有着广泛的应用，一切具有关系的问题都可以用图来表示。 数据结构实验报告 实验五 查找 1.实验要求 1.1 掌握顺序查找、二分法查找、分块查找和哈希表查找的算法。1.2 能运用线性表的查找方法解决实际问题。2.实验内容 2.1 编写一个算法，利用二分查找算法在一个有序表中插入一个元素X，并保持表的有序性。 2.2 根据给定的数据表，先建立索引表，然后进行分块查找。3.实验代码 2.1代码： #include int data[MAXNUM],m;int insert=1;m=input(data);printf(“Input the insert num:”);scanf(“%d”,data);insert=search(data,1,m);/*返回插入位置*/ plug(data,insert,m);for(insert=1;insert<=m+1;insert++)/*显示数据*/ printf(“%3d”,*(data+insert)); 数据结构实验报告 getch();} int input(int *data){ int i,m; printf(“nInput the max num:”);scanf(“%d”,&m);printf(“input datan”);for(i=1;i<=m;i++)scanf(“%d”,data+i);return m;} int search(int *data,int low,int high)/*递归查找插入位置*/ { int mid;if(low>high)return low;/*没有找到插入数据，返回low*/ else{ } search(data,low,high);} void plug(int *data,int insert,int m) { int i;for(i=m;i>insert;i--)*(data+i+1)=*(data+i);mid=(low+high)/2;if(*(data+mid)==*data)retun mid;/*找到插入数据，返回mid*/ else if(*(data+mid)<*data)else if(*()data+mid)>*data)*(data+insert)=*data 数据结构实验报告 } 2.2代码： #include /*元素个数*/ #definr Blocknum 3 /*分块数*/ typedef struct indexterm { int key;/*最大关键字*/ int addr;/*块的起始地址*/ }index;/*索引表数据类型*/ index * CreateList(int data[],int n)/*建索引表*/ { index *p;int m,j,k;m=n/BlockNum;/*分为BlockNum块，每块有m个元素*/ p=(index *)malloc(BlockNum *sizeof(index));for(k=0;k } return p;} int BlockSearch(index *list,int rectab[],int n,int m,int k)/*分块查找*/ { int low=0,high=m-1,mid,i;(p+k)->key=dat a[m*k];(p+k)->addr=m*k;for(j=m*k;j 数据结构实验报告 int b=n/m;/*每块有b个元素*/ while(low<=high){/*块间折半查找*/ } if(low } return-1;} void main(){ int record[N]={22,12,13,8,9,20,33,42,44,38,24,48,60,58,74,49,86,53};int key;index *list;printf(“please input key:n”);scanf(“%d”,&key);list=CreateList(record,N);printf(“data postion id %dn”,BlockSearch(list,record,N,BlockNum,key));} if(i<=(list+low)->addr+b-1)return i;mid=(low+high)/2;if((list+mid)->key>=k)high=mid+1;else low=mid+1;else return-1;4.实验小结 通过本章的学习，对排序有较高层次的理解与认识，从平时的练习中可以看出排序是数据处理中经常用到的重要运算。有序的顺序表可以采用查找效率较高的折半查找法，而无序的顺序表只能用效率较低的顺序查找法。 注意：第5题和第7题有改动，第6题加了一句提示 一、停车场管理 仅仅认识到栈和队列是两种特殊的线性表是远远不够的，本次实习的目的在于使读者深入了解栈和队列的特征，以便在实际问题背景下灵活运用它们；同时还将巩固这两种结构的构造方法，接触较复杂问题的递归算法设计。 [问题描述] 设停车场内只有一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后开入的车辆必须先退出车场为它让路，待该辆车开出大门外，其它车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。 [测试数据] 设n=2,输入数据为：（‘A’，1，5），（‘A’，2，10），（‘D’，1，15），（‘A’，3，20），（‘A’，4，25），（‘A’，5，30），（‘D’，2，35），（‘D’，4，40），（‘E’，0，0）。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，其中，‘A’表示到达；‘D’表示离去，‘E’表示输入结束。 [基本要求] 以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，对每一组输入数据进行操作后的输出数据为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车离去；则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表实现。 [实现提示] 需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车，也用顺序存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包含两个数据项：汽车的牌照号码和进入停车场的时刻。 [选作内容] （1）两个栈共享空间，思考应开辟数组的空间是多少？ （2）汽车可有不同种类，则它们的占地面积不同，收费标准也不同，如1辆客车和1.5辆小汽车的占地面积相同，1辆十轮卡车占地面积相当于3辆小汽车的占地面积。 （3）汽车可以直接从便道上开走，此时排在它前面的汽车要先开走让路，然后再依次排到队尾。 （4）停放在便道上的汽车也收费，收费标准比停放在停车场的车低，请思考如何修改结构以满足这种要求。 二、员工管理系统 综合运用线性表、查找、排序的相关知识，解决一个实际应用问题。通过本次实习，要求熟练掌握线性表的存储结构，能在对应的存储结构上进行各种操作，并能分析不同的查找和排序方法的时空性能。[问题描述] 每个员工的信息包括：编号、姓名、性别、出生年月、学历、职务、电话、住址等。系统能够完成员工信息的查询、更新、插入、删除、排序等功能。 [基本要求] （1）排序：按不同关键字，对所有员工的信息进行排序。（2）查询：按特定条件查找员工。 （3）更新：按编号对某个员工的某项信息进行修改。（4）插入：加入新员工的信息。 （5）删除：按编号删除已离职的员工的信息。 [选作内容] 实现图形用户界面。 三、校园导游程序 [问题描述] 用无向网表示你所在学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介 等信息，图中的边表示景点间的道路，存放路径长度等信息。要求能够回答有关景点介绍、游览路径等问题。 [基本要求] （1）查询各景点的相关信息； （2）查询图中任意两个景点间的最短路径。（3）查询图中任意两个景点间的所有路径。（4）增加、删除、更新有关景点和道路的信息。 [选作内容] （1）求多个景点的最佳（最短）游览路径。（2）区分机动车道和人行道。（3）实现导游图的仿真界面。 四、编写一个杂货店排队模拟程序。 该模拟程序中包含多个队列，可以使用队列数组来模拟这些队列。假设杂货店共5条收银线，顾客可随机进入支付。顾客会进入最短的队伍，如果队伍一样长，那么选择最靠近的一个队伍。每次交易完成所消耗的时间也是随机的。 完成一些额外工作，扩展杂货店排队程序，使得客户可以： 如果所有队伍都一样长，可以选择不排队。 如果等待超过了某个时间，可以离开队伍。 在给定的时间间隔内，检查另一个队伍是否更短。 如果另一个队伍更短，则切换队伍。 五、猜动物 猜动物：假设你是一个动物，程序问问题试图猜出你是哪种动物。如果程序的猜测正确，就开始另一轮游戏。如果程序不能断定你是哪种动物，你就提供一些信息给程序以使下次再玩游戏时，程序会聪明一点儿。 举例：假设你现在是一只浣熊（raccoon）。游戏开始 ***** 猜动物游戏 ***** 程序： 请在心里想好一种动物,让我来猜一猜 你是哺乳动物吗？' 用户：y 程序：你比猫大吗？ 用户：y 程序：我猜是袋鼠，我猜的对吗 用户：Y 程序：我猜对了！程序：继续玩吗？ 用户：Y （再完一次） 程序：你是哺乳动物吗？'用户：Y 程序：你比猫大吗？ 用户：Y 程序：我猜是袋鼠，我猜的对吗 用户：N 程序：我认输了,你是什么？ 用户：浣熊 程序：请键入一个问题,便得通过此问题可以将袋鼠和浣熊区分开.用户：你有大口袋吗？ 程序：对于浣熊你有大口袋吗？(Y/N)用户：N 程序：噢,我明白了 程序：退出游戏吗?„„ 这样你就给程序提供了一个以后可以区分袋鼠和浣熊的问题。 程序使用的数据存储在一棵二叉树中，每个非叶子结点包含一个问题。当程序开始后，它只知道4种动物。 根结点的问题是“是哺乳动物吗？”。如果是，左子树的问题是“比猫大吗？”，如果是，答案是袋鼠，否则，答案是老鼠 否则，不是哺乳动物，问“生活在水中吗？”如果是，答案是鳟鱼，否则，答案是知更鸟 如果叶子结点包含正确的动物，一切都好。如果猜的不对，程序将从用户那里引出信息，并用这些信息改进二叉树。 主要功能函数： （1）建立初始状态的二叉树（2）猜策过程 （3）学习过程，若猜测失败，扩展叶结点 六、硬币游戏 在游戏开始之前，在桌上将三个硬币放置成一条直线。游戏开始的时候，中间一个硬币是背面朝上，其他两个硬币是正面朝上。游戏目标是改变硬币的摆放形式，让中间一个硬币正面朝上，其他两个硬币背面朝上。具体规则如下： （1）任何时候都能翻转中间的硬币（从正面翻成背面或相反） （2）当另外两个硬币都是正面或都是背面的时候能够翻转一端的硬币（从 正面翻成背面或相反）； 不能通过任何其他方式翻转硬币，如平移它们。但是，只要满足这些规则，你就能够翻转硬币。 （提示：使用无向图，图中每个顶点代表三个硬币的一种状态（8种状态对应8个顶点，一个状态可用一个字符串表示，如”+-+”表示了一个中间一个硬币是背面朝上，其他两个硬币是正面朝上的状态）；当使用其中一条规则能在两个状态之间来回移动时，就通过一个边连接无向图的两个顶点。 该游戏使三个硬币从一种状态改变成另外一种状态，其实就是查找相应两个顶点之间路径的问题，该路径只能沿着边进行。） 七、编写程序帮助旅游者找出从一个城市到另一个城市的最短旅行 路径。 该程序应该读取一个包含了一个城市列表和一个连接城市的路径列表的数据文件。每个城市信息包含城市名称、城市级别（首都、直辖市、省会、地极市、县级市），每条路径包含两城市之间的距离、最低费用、最少花费时间。 程序功能要求： （1）能进行城市信息的修改（2）能进行城市之间路径的修改 （3）能按满足不同用户的查询，如自费旅游的人希望费用最省，因公出差的人希望花费时间最少等。 某两地之间的最低费用路线（自费旅游的人）某两地之间的花费时间最少路线（因公出差的人）某两地之间的距离最短的路线（自己开车出行的人） 八 问题描述： 设计哈希表实现电话号码查询系统。基本要求： 1、设每个记录有下列数据项：电话号码、用户名、地址； 2、从键盘输入各记录，分别以电话号码和用户名为关键字建立哈希表； 3、采用再哈希法解决冲突； 4、查找并显示给定电话号码的记录； 5、查找并显示给定用户名的记录。 6、在哈希函数确定的前提下，尝试各种不同类型处理冲突的方法（至少两种），考察平均查找长度的变化。九 哈夫曼编码/译码器 设字符集为26个英文字母，其出现频度如下表所示。先建哈夫曼树，再利用此树对报文“This program is my favorite”进行编码和译码。 字符 频度 字符 频度 字符 频度 空格 186 j 1 t 80 a 64 k 5 u 23 b 13 l 32 v 8 c 22 m 20 w 18 d 32 n 57 x 1 e 103 o 63 y 16 f 21 p 15 z 1 g 15 q 1 h 47 r 48 i 57 s 51第二篇：数据结构实训报告
第三篇：数据结构实训报告样本
第四篇：《数据结构》实训报告
第五篇：数据结构实训题目(2010年)
点击咨询 