数据结构心得体会（精选多篇）

推荐第1篇：数据结构心得体会

心得体会

数据结构是一门纯属于设计的科目，它需用把理论变为上机调试。在学习科目的第一节课起，鲁老师就为我们阐述了它的重要性。它对我们来说具有一定的难度。它是其它编程语言的一门基本学科。 很多同学都说，数据结构不好学，这我深有体会。刚开始学的时候确实有很多地方我很不理解，每次上课时老师都会给我们出不同的设计题目，对于我们一个初学者来说，无疑是一个具大的挑战。

我记得有节课上遍历二叉树的内容，先序遍历、中序遍历、后序遍历。鲁老师说：这节课的内容很重要，不管你以前听懂没有，现在认真听。说实在的，以前上的内容确实没大听懂，不过听了老师的话，我听得很认真。先序遍历很简单，是三个遍历中，最简单的。而中序遍历听得有点模糊，后序遍历也半懂半懂，我心想如果老师再讲一遍，我肯定能听懂。后来老师画了一个二叉树，抽了同学到黑板上去排序，这个二叉树看似复杂，不过用先序遍历来排，并不难。于是我在下面排好了先序，先序遍历很简单，我有点得意，老师到位置上点了我上去排中序，上去之后排得一塌糊涂。后来老师又讲了一遍，我这才听懂了，鲁老师又安慰我们说，这个二叉树有点难，中序和后序都不好排，要学懂的确要花点功夫才行。我听了老师的话，认真做了笔记，回去再看了当天学的内容。第二堂课，老师还是先讲的先前的内容，画了一个简单的二叉树，让我们排序，又叫同学上去分别排出来，老师又点了我的名，叫我起来辨别排中序那两个同学的答案哪个排正确了，我毫不犹豫的答对了。因为这次的内容，先序遍历二叉树、中序遍历二叉树、后序遍历二叉树，我的确真的懂了，第一次上这个课这么有成就感。渐渐的对这门课有了兴趣。我以为永远都听不懂这个课，现在，我明白了，只要认真听，肯下功夫，这个课也没有什么难的。而数据结构学习的难易程度很大程度上决定于个人的兴趣，把一件事情当做任务去做会很痛苦，当做兴趣去做会很快乐。也希望老师能看到我的改变，在此也感谢老师的辛勤教导。老师没有放弃我，几次点我的名上去，老师一定看得到我的进步。

后来，我每节课都认真听课，老师虽然没有点名，但我还是很认真的听。双亲表示法孩子表示法和孩子兄弟表示法，这些内容我都听得很明白，差不多每节课都认真听课。有时我也会在上课空余时间看看以前的内容，所以，第一遍看课本的时候要将概念熟记于心，然后构建知识框架。数据结构包括线性结构、树形结构、图状结构或网状结构。线性结构包括线性表、栈、队列、串、数组、广义表等，栈和队列是操作受限的线性表，串的数据对象约束为字符集，数组和广义表是对线性表的扩展：表中的数据元素本身也是一个数据结构。除了线性表以外，栈是重点，因为栈和递归紧密相连，递归是程序设计中很重要的一种工具。

其中我了解到：栈 (Stack)是只能在某一端插入和删除的特殊线性表。它按照后进先出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据; 队列一种特殊的线性表，它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。进行插入的操作端称为队尾，进行删除的操作端称为队头。队列中没有元素时，称为空队列;链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

想着自己报考自考的专业，也会考数据结构这门，这学期就结束了，或多或少都收获了一些知识。尽管学得还不是很透彻，我相信这对自己的自考会有很大的帮助，所以，即使是结束了这科的内容，我也不会放弃去学习它。

推荐第2篇：数据结构心得体会

Experience The data structure design subject, it needs to change the theory to the computer debugging.At the beginning of the first leon of the subject, Mr.Lu explained the importance of it for us.It has some difficulty for us.It is a basic subject of other programming languages.Many students say that the data structure is not good to learn, I deeply understand this.When I first started learning, there were a lot of places I didn\'t understand.Every time I was in cla, the teacher gave us different design questions.It was a big challenge for us as a beginner.I remember walking through the contents of two trees in a cla, preorder, preorder, and preorder.Teacher Lu said, \"the content of this leon is very important.No matter whether you have understood it or not, listen carefully now.\".To tell the truth, I didn\'t really understand what I had done before, but I listened to the teacher carefully.Preorder traversal is very simple, is the three traversal, the simplest.And in order to traverse, listen to a little fuzzy, after the order traversal, also half understand, half understand, I thought, if the teacher once again, I certainly can understand.Later, the teacher drew a two tree, smoked the students to the blackboard sorting, this two fork tree seems complex, but with first order traversal to row, not difficult.So I lined up in the following, first order, first order traversal, very simple, I am a little complacent, the teacher to the location of the point, I went up the row in the order, go up after a row in a me.Then the teacher spoke again, I just understand, Lu teacher and aured us that the two tree is hard, the order and post order are not good, want to learn that we sort, and ask the students to row out respectively, the teacher also had my name, call me up in order to distinguish the two row row which students answer correctly, I did not hesitate to answer.Because of this content, the first traversal of the two fork tree, the sequence traversal two fork tree, after the order traversal two fork tree, I really understand, for the first time on this cla so succeful sense.Gradually interested in the course.I thought I would never understand the leon.Now I see, and if I listen carefully and try my best, this leon is not difficult.The degree of difficulty of data structure learning depends largely on personal interest.It\'s painful to make a task as a task, and it will be fun to do it.Also hope that the teacher can see my change, in this also thank the teacher\'s hard teaching.The teacher did not give up on me, several times my name go up, the teacher must see my progre.Later, I listened carefully every cla, although the teacher did not call the roll, but I still listened very seriously.The parents expre the children and the children and the brothers.I can understand them very well.I listen to the lectures almost every cla.Sometimes I also take claes in my spare time to read what I\'ve been doing before.So, when I first read the textbooks, I memorize the concepts in mind, and then build a knowledge framework.The data structure includes linear structure, tree structure, graph structure or network structure.Linear structure including linear list, stack, queue, string, array, generalized list, stack and queue is a linear scale is limited, the data object constraint string for character set, and an array of generalized list of linear table: data element in the table is a data structure.In addition to linear tables, the stack is the focus, because the stack is closely related to recursion, and recursion is an important tool in programming.I\'ve learned that Stack is a special linear list that can only be inserted and deleted at one end.It stores data in accordance with the principle of \"first in, first out\".The incoming data is pushed to the bottom of the stack, and the last data pops up from the top of the stack at the top of the stack when it is neceary to read data; A special linear table that allows only deleting operations at the front of the table (front) and inserting operations at the back of the table (rear).The inserted operation end is called the queue tail, and the deleted operation end is called the header.When there is no element in the queue, it is called an empty queue.The list is a discontinuous and non sequential storage structure on the physical storage unit, and the logical order of the data elements is achieved by the order of pointer linking in the linked list.A linked list consists of a series of nodes that can be dynamically generated at run time.Each node consists of two parts: one is the data domain that stores the data elements, and the other is the pointer domain that stores the addre of the next node.Think oneself enter oneself for an examination of the profeional, but also the data structure of this gate, this semester is over, more or le have gained some knowledge.Although the study is not very thorough, I believe that this will help a lot of self exams, so even if I finish the subject, I will not give up learning it.

推荐第3篇：数据结构课程设计心得体会

心得体会

通过本次课程设计，对图的概念有了一个新的认识，在学习离散数学的时候，总觉得图是很抽象的东西，但是在学习了《数据结构与算法》这门课程之后，我慢慢地体会到了其中的奥妙，图能够在计算机中存在，首先要捕捉他有哪些具体化、数字化的信息，比如说权值、顶点个数等，这也就说明了想要把生活中的信息转化到计算机中必须用数字来完整的构成一个信息库，而图的存在，又涉及到了顶点之间的联系。图分为有向图和无向图，而无向图又是有向图在权值双向相等下的一种特例，如何能在计算机中表示一个双向权值不同的图，这就是一件很巧妙的事情，经过了思考和老师同学的帮助，我用edges[i][j]=up和edges[j][i]=up就能实现了一个双向图信息的存储。

对整个程序而言，Dijkstra算法始终都是核心内容，其实这个算法在实际思考中并不难，也许我们谁都知道找一个路径最短的方法，及从顶点一步一步找最近的路线并与其直接距离相比较，但是，在计算机中实现这么一个很简单的想法就需要涉及到很多专业知识，为了完成设计，在前期工作中，基本都是以学习C语言为主，所以浪费了很多时间，比如说在程序中，删除顶点和增加顶点的模块中都有和建图模块相互重复的函数，但是由于技术的原因，只能做一些很累赘的函数，可见在调用知识点，我没有掌握好。不过，有了这次课程设计的经验和教训，我能够很清楚的对自己定一个合适的水平，而且在这次课程设计中我学会了运用两个新的函数sprintf()和包涵在#include 头文件中的输入函数。 因为课程设计的题目是求最短路径，本来是想通过算法的实现把这个程序与交通情况相连，但是因为来不及查找各地的信息，所以，这个计划就没有实现，我相信在以后有更长时间的情况下，我会做出来的。

1、巩固和加深了对数据结构的理解，提高综合运用本课程所学知识的能力。

2、培养了我选用参考书，查阅手册及文献资料的能力。培养独立思考，深入研究，分析问题、解决问题的能力。

3、通过实际编译系统的分析设计、编程调试，掌握应用软件的分析方法和工程设计方法。

4、通过课程设计，培养了我严肃认真的工作作风，逐步建立正确的生产观念、经济观念和全局观念。

根据我在实习中遇到得问题，我将在以后的学习过程中注意以下几点：

1、认真上好专业实验课，多在实践中锻炼自己。

2、写程序的过程中要考虑周到，严密。

3、在做设计的时候要有信心，有耐心，切勿浮躁。

4、认真的学习课本知识，掌握课本中的知识点，并在此基础上学会灵活运用。

5、在课余时间里多写程序，熟练掌握在调试程序的过程中所遇到的常见错误，以便能节省调试程序的时间。

这是一门纯属于设计的科目，它需用把理论变为上机调试。在学习科目的第一节课起，李老师就为我们阐述了它的重要性。它对我们来说具有一定的难度。它是其它编程语言的一门基本学科。

刚开始学的时候确实有很多地方我很不理解，每次上课时老师都会给我们出不同的设计题目，对于我们一个初学者来说，无疑是一个具大的挑战，撞了几次壁之后，我决定静下心来，仔细去写程序。老师会给我们需要编程的内容一些讲解，顺着老师的思路，来完成自己的设计，我们可以开始运行自己的程序，可是好多处的错误让人看的可怕，还看不出到底是哪里出现了错误，但是程序还是得继续下去，我多次请教了老师和同学，逐渐能自己找出错误，并加以改正。TC里检查错误都是用英文来显示出来的，经过了这次课程设计，现在已经可以了解很多错误在英文里的提示，这对我来说是一个突破性的进步，眼看着一个个错误通过自己的努力在我眼前消失，觉得很是开心。此次的程序设计能够成功，是我和我的同学三个人共同努力作用的结果。在这一段努力学习的过程中，我们的编程设计有了明显的提高。 其实现在想起来，收获还真是不少，虽然说以前非常不懂这门语言，在它上面花费了好多心血，觉得它很难，是需用花费了大量的时间编写出来的。现在真正的明白了一些代码的应用，每个程序都有一些共同点，通用的结构，相似的格式。只要努力去学习，就会灵活的去应用它。

推荐第4篇：数据结构心得体会（材料）

数据结构学习体会及教学建议

时间过的很快，一转眼一学期的数据结构课程就已经快要告一段落了，在接触这么课以前，我觉得编程无非就是会写代码就好了。然而事实上数据结构对于程序来说，有着非常重要的地位。随着计算机应用领域的不断扩大，非数值计算的问题占据了当今计算机应用的绝大部分，简单的数据类型已经远远不能满足需要，个数据元素之间的复杂关系已经不是普通数学方程式能够表达的了，所以数据结构就扮演了十分重要的角色。 在学期初，我觉得数据结构还是比较简单的，但可能由于之前c语言学习对指针掌握的不够熟练，导致在数据结构中接触到与指针有关的问题，例如线性表，堆栈，队列，二叉树等问题的时候，都会显得有些吃力。但是在不断学习数据结构的过程中我也不断加强了对指针的学习，现在我已经能够基本掌握指针的相关知识并且能够熟练运用了。这一学期的学习下来我发现想要学好数据结构有以下几点经验{虽然可能我的数据结构学的并不是很好} 1.初步了解算法思想、原理

想要弄清楚一个算法的实现，首先要知道这个算法的大致原理，这是最简单的一步，也是最基础的一步，只有明白算法想要干什么，才能弄清楚相应的代码段是为什么 2.钻研课本代码段

对于书上的算法代码，我们一定要仔细钻研每一步的具体含义和目的，在此基础上深入的了解算法的实现过程，而不是一味的四级硬背，不仅无聊，而且效率低下。 3.查找各种算法资料

例如排序算法，其实历史上有很多不同的排序算法，书上只列举出了一部分，我们通过查阅资料可以发现很多其他不同的排序算法，而且就算是同一个算法，也有很多不同的实现方法，这个过程是一个十分有趣的过程，同时也增长了自己的知识储备，我们可以根据已有的知识储备，从而稍加创新，对某个算法可以有自己不同的见解，从而写出一个“自己”的算法。这对于数据结构的学习是十分重要的 4.坚持上级操作，用实践检验

和所有计算机相关知识的学习一样，数据结构也是一项需要动手的课程，一味的学习书本知识，埋头拿笔演算，还不如在电脑上把代码敲进去自己亲自跑一遍，只有这样才能够最直接最深入的了解一个代码，这也是我这个学期也来最深刻的感受。只有多动手，才能找到写代码的感觉，才能将各种算法烂熟于心。 5.勤于练习，寻找感觉

算法是为了问题服务的，我们在掌握了书本上的算法以后，要去找一些综合性的题目来锻炼自己，这些问题通常融合了不同的知识点，例如同时蕴含了排序，二叉树，堆栈的相关知识，只有在解决问题的过程中，灵活运用所学知识，才能真正检验我们是否牢固掌握了书本上的内容。 教学建议： 其实李老师您是我大学以来第一个普通话如此标准的老师，所以我已经十分庆幸了，而且我觉得您的讲课思路严谨，只不过有的时候，您似乎刻意追求语句的严谨性，逻辑性，科学性，导致课堂上一句话往往说的很长，很绕，慢慢的都是专业名词，有时候还稍有些舌头打结，这会让我们的思绪无法连贯。比如有一次我在qq上问您希尔排序里面的gap这个点，您给我发了一段26秒的语音，然后我听了好多遍理了好多次思绪才想明白，当然了这可能和我自己的理解能力较弱有关。我希望老师上课的时候能够尽量把内容说的再通俗易懂简单粗暴一些。

以上学习经验以及教学建议仅仅是个人观点，老师您教的已经很好了，是我的水平不够，如有得罪还望见谅

推荐第5篇：数据结构课程设计心得体会

程序设计心得体会

做了一个星期的程序设计终于做完了，在这次程序设计课中，真是让我获益匪浅，我突然发现写程序还挺有意思的。

由于上学期的C语言跟这学期的数据结构都算不上真正的懂，对于书上的稍微难点的知识就是是而非的，所以我只是对老师的程序理解，我也试着去改变了一些变量，自己也尽量多的去理解老师做程序的思路。当我第一天坐在那里的时候，我就不知道该做些什么，后来我只有下来自己看了一遍书来熟悉下以前学过的知识。

通过这次的程序设计，发现一个程序设计就是算法与数据结构的结合体，自己也开始对程序产生了前所未有的兴趣，以前偷工减料的学习也不可能一下子写出一个程序出来，于是我就认真看老师写的程序，发现我们看懂了一个程序其实不难，难的是对于一个程序的思想的理解，我们要掌握一个算法，不仅仅限于读懂，主要的是要理解老师的思路，学习老师的解决问题的方法。

这次试验中，我发现书本上的知识是一个基础，但是我基础都没掌握，更别说写出一个整整的程序了。自己在写程序的时候，也发现自己的知识太少了，特别是基础知识很多都是模模糊糊的一个概念，没有落实到真正的程序，所以自己写的时候也感到万分痛苦，基本上涉及一个知识我就会去看看书，对于书本上的知识没掌握好。在饭后闲暇时间我也总结了一下，自己以前上课也认真的听了，但是还是写不出来，这主要归结于自己的练习太少了，而且也总是半懂就不管了。在改写老师的程序中也出现了很多的问题，不断的修改就是不断的学习过程，当我们全身心的投入其中时，实际上是一件很有乐趣的事情。对于以后的学习有了几点总结：第

一、熟记各种数据结构类型，定义、特点、基本运算（分开点一点也没多少东西，难度不大，但是基本）；第

二、各种常用的排序算法，如冒泡排序、堆排序……，这些是必考的内容，分数不会少于20%；第三，多做习题，看题型，针对题型来有选择复习；数据结构看上去很复杂，但你静下心来把书扫上几遍，分解各个知识点，这一下来，学数据结构的思路就会很清晰了。

推荐第6篇：数据结构课程设计报告心得体会

心得体会

接近两个星期的课程设计课让我学到了很多，单从我的任务来说，求先序序列并不是很难再加上数据结构课上老师也讲了很多类似的知识，所以，算法思想上我是十分清楚的，不过在用c语言写代码的时候也遇到了大大小小的问题，并且c语言的运用不是十分好，但是后来还是顺利完成了，老师后来又叫我改编我的程序，就是已知中序和先序序列求后序序列，由于算法思想有很多相似的地方，再加上经过了一段时间的c语言编码，运用c语言的熟练度也高了，很快就回答出了老师的问题，老师也很满意，然后就是树的打印，老师要求我把得到的二叉树打印出来，由于书上没有相关知识，我就上网查了一些资料，经过学习，完成了打印树的函数的编写void PrintTree(btree *bt,int nlayer)。在课后给完成了！

两个星期的学习，在最后要给老师一个满意的答案还是不容易的，但是经过我的努力，我做到了，我不仅学到了新的知识，而且也把旧的知识复习了，更加强了对C语言的应用度与熟练度，虽然很辛苦，但能够得到这些我很满足，也很快乐，最后谢谢胡老师的指导很帮助，谢谢老师！

推荐第7篇：数据结构综合实验心得体会

心得体会：

做了一个星期的程序设计终于做完了，在这次程序设计课中，真是让我获益匪浅。 对大一学习的C语言和这学期开的数据结构，并没有掌握，很多知识都不太懂，突然让自己独立完成一个程序让我手忙脚乱，起码在我认为那真的特别难，看了老师给的题目以及上网查找了一些相关的知识，简单的编了几行就告一段落了，第一天等于只完成了老师要求写的需求分析和概要设计，后来查找了关于哈希表的相关知识，了解了如何创建哈希表，如何合适的构建哈希函数，（选取合适的表长，合适的余数，使得查找时间以及平均查找长度最短）以及什么是除留余数法，和怎样用除留余数法创建哈希表，看懂了之后，我又看了处理冲突的方法，有三种线性探测再散列法法，二次探测再散列法，伪随机数序列法三种，而我所要做的是第一种线性探测再散列的方法，相较后两种要简单很多，在遇到冲突的时候地址加一，知道冲突解决。

在了解这些概念以后，我就开始着手编程序了，在遇到问题的时候请教我们班擅长的同学，慢慢把不能不会不理解的地方给弄明白了，在经过很多次调试以后，一些基本功能已经可以实现了，为了使平均查找长度越小越好，我不断尝试新的表长以及除数，在没有出现错误的基础上，将功能实现，最后，终于在周四的时候将所有的程序调试完全。

这次的综合性实验使我了解到，平时对知识的积累相当重要，同时也要注重课上老师的讲解，老师在课上的延伸是课本上所没有的，这些知识对于我们对程序的编写有很大的作用，同时，编程也要求我们有足够的耐心，细细推敲。越着急可能就越无法得到我们想要的结果，遇到不会的问题要多多请教，知识是在实践与向别人请教的过程中积累的，所以问是至关重要的，只要肯下功夫很多东西都是可以完成的。

推荐第8篇：数据结构 课程设计 心得体会（优秀）

数据结构 课程设计 心得体会

经过一个星期的课程设计，过程曲折可谓一语难尽。整天都是对着电脑，不然就是翻阅资料。在此期间我失落过，也曾一度热情高涨。点点滴滴令我回味无长。这次课程设计使我体会到只有做到细心耐心，恒心才能做好事情。 这次的课程设计，加强了我们动手、思考和解决问题的能力。巩固和加深了对数据结构的理解，提高综合运用本课程所学知识的能力。培养了我选用参考书，查阅手册及文献资料的能力。培养独立思考，深入研究，分析问题、解决问题的能力。通过实际编译系统的分析设计、编程调试，掌握应用软件的分析方法和工程设计方法。通过课程设计，培养了我严肃认真的工作作风，逐步建立正确的生产观念、经济观念和全局观念。而且做课程设计同时也是对课本知识的巩固和加强，平时看课本时，有些问题就不是很能理解，做完课程设计，那些问题就迎刃而解了。而且还可以记住很多东西。认识来源于实践，实践是认识的动力和最终目的，实践是检验真理的唯一标准。所以这个期末测试之后的课程设计对我们的作用是非常大的。

这次的课程设计使我懂得了理论与实际相结合是很非常重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，才能真正为社会服务，从而提高自己的实际动手能力和独立思考的能力。在整个设计过程中，构思是很花费时间的。调试时经常会遇到这样那样的错误，有的是因为粗心造成的语法错误。当然，很多也时用错了方法，总是实现不了。同时在设计的过程中发现了自己的不足之处，对以前所学过的知识理解得不够深刻，掌握得不够牢固。

根据我在课程设计中遇到得问题，我将在以后的学习过程中注意以下几点：

1、认真上好专业实验课，多在实践中锻炼自己。

2、写程序的过程中要考虑周到，严密。

3、在做设计的时候要有信心，有耐心，切勿浮躁。

4、认真的学习课本知识，掌握课本中的知识点，并在此基础上学会灵活运用。

5、在课余时间里多写程序，熟练掌握在调试程序的过程中所遇到的常见错误，以便能节省调试程序的时间。每个实验通常都要花费很久的时间才能理清一个程序的思路，而且要不断的调试程序才能把程序调试正确，同时还要做到界面的输出也是需要美化的。这次课程设计终于顺利完成了，在设计中遇到了很多专业知识问题，最后在老师的辛勤指导下，也完成了课程设计。

通过这次的课程设计，让我更加了解到数据结构的重要性。以及它对我们专业的发展发挥的作用。对我们而言，知识上的收获很重要，但精神上的丰收更加可喜。让我知道了学无止境的道理。我们每一个人永远不能满足于现有的成就，人生就像在爬山，一座山峰的后面还有更高的山峰在等着你。挫折是一份财富，经历是一份拥有。这次课程设计必将成为我人生旅途上一个非常美好的回忆！同时在做课程设计时要能够从多方面去考虑，去研究，用多种算法去实现要求。此次课程设计，学到了很多课内学不到的东西，比如独立思考解决问题，出现差错的随机应变，这些都让我受益非浅，今后的制作应该能够更轻松，自己也都能够解决并高质量的完成项目。

推荐第9篇：数据结构实训心得体会

这次课程设计的心得体会通过实习我的收获如下

1、巩固和加深了对数据结构的理解，提高综合运用本课程所学知识的能力。

2、培养了我选用参考书，查阅手册及文献资料的能力。培养独立思考，深入研究，分析问题、解决问题的能力。

3、通过实际编译系统的分析设计、编程调试，掌握应用软件的分析方法和工程设计方法。

4、通过课程设计，培养了我严肃认真的工作作风，逐步建立正确的生产观念、经济观念和全局观念。从刚开始得觉得很难，到最后把这个做出来，付出了很多，也得到了很多，以前总以为自己对编程的地方还不行，现在，才发现只要认真做，没有什么不可能。 编程时要认真仔细，出现错误要及时找出并改正，（其中对英语的要求也体现出来了，因为它说明错误的时候都是英语）遇到问题要去查相关的资料。反复的调试程序，最好是多找几个同学来对你的程序进行调试并听其对你的程序的建议，在他们不知道程序怎么写的时候完全以一个用户的身份来用对你的用户界面做一些建议，正所谓当局者迷旁观者清，把各个注意的问题要想到；同时要形成自己的编写程序与调试程序的风格，从每个细节出发，不放过每个知识点，注意与理论的联系和理论与实践的差别。另外，要注意符号的使用，注意对字符处理，特别是对指针的使用很容易出错且调试过程是不会报错的，那么我们要始终注意指针的初始化不管它怎么用以免不必要麻烦。 通过近两周的学习与实践，体验了一下离开课堂的学习，也可以理解为一次实践与理论的很好的连接。特别是本组所做的题目都是课堂上所讲的例子，在实行之的过程中并不是那么容易事让人有一种纸上谈兵的体会，正所谓纸上得来终觉浅绝知此事要躬行。实训过程中让我们对懂得的知识做了进一步深入了解，让我们的理解与记忆更深刻，对不懂的知识与不清楚的东西也做了一定的了解，也形成了一定的个人做事风格。

通过这次课程设计，让我对一个程序的数据结构有更全面更进一步的认识，根据不同的需求，采用不同的数据存储方式，不一定要用栈，二叉树等高级类型，有时用基本的一维数组，只要运用得当，也能达到相同的效果，甚至更佳，就如这次的课程设计，通过用for的多重循环，舍弃多余的循环，提高了程序的运行效率。在编写这个程序的过程中，我复习了之前学的基本语法，哈弗曼树最小路径的求取，哈弗曼编码及译码的应用范围，程序结构算法等一系列的问题它使我对数据结构改变了看法。在这次设计过程中，体现出自己单独设计模具的能力以及综合运用知识的能力，体会了学以致用、突出自己劳动成果的喜悦心情，也从中发现自己平时学习的不足和薄弱环节，从而加以弥补。篇2：数据结构试验心得

数据结构课程设计心得体会 （专业：计算机科学与技术 姓名：朱文 学号：2011220137）

通讯录管理系统是基于双向循环链表设计而成的信息管理系统。该系统通过对程序进行模块化，建立添加、显示、查找和删除功能的函数，各函数中运用双向循环链表存储数据。为存储通讯录信息，需定义一个结构体类型，成员包括姓名、街道、城市、邮编、国家等，并建立双向循环链表，定义该结构体类型的指针，用于指向各结点。分别建立具有添加、删除、修改、查询等功能的子函数，完成相应功能，对程序实现模块化。这其中要用到对链表的删除、插入等知识。为实现存储功能，需用到文件的相关函数

开发一个通讯录管理系统，借助计算机可以方便、快捷、灵活的管理个人的朋友及相关人员的通讯信息，了解友人相关信息，帮助与友人保持联络。所以设计一个通讯录管理系统管理各人的通讯信息是非常必要的，同时，通过用循环双向链表设计通讯录管理系统可以让我们更好的去理解循环双向链表，更好的学好数据结构这门课程。 本次实验中，我们使用分工合作的方式，首先定义了函数的结构体部分，剩下的根据函数所要实现的功能进行分工合作，我实现的是通讯录中删除功能的子函数，删除信息（void delete(dnode *head)）的功能是按照用户输入的姓名首先进行按姓名查询功能，查找成功，则执行删除信息的功能，查询不成功，则提示错误信息。定义结点p，输入要删除的信息的姓名，按姓名查找结点，如果找到匹配的结点p，就进行相关的删除操作，否则就是没找到要删除的数据，最后返回到主函数。

这次实验中我深刻认识到合作的重要性。例如：我所编写的按名删除功能的实现中，应用了章林霞同学所编写写的按名搜索查询功能的那部分函数，在这次实验中，我学到很多东西，加强了我的动手能力，并且培养了我的独立思考能力。我们坚持理论联系实际的思想，以实践证实理论，从实践中加深对理论知识的理解和掌握。实验是我们快速认识和掌握理论知识的一条重要途径。 通过这次课程设计，我们对c语言以及数据结构有了更深刻的了解，增强了程序的编写能力，巩固了专业知识，对程序的模块化观念也又模糊逐渐变的清晰了。在程序的运行与调试过程中出现了很多错误，通过反复地复习课本上的相关知识，不停地修改与调试，我们终于完成了这段程序。在调试过程中，我们认识到了数据结构的灵活性与严谨性，同一个功能可以由不同的语句来实现，但编写程序时要特别注意细节方面的问题，因为一个小小的疏忽就能导致整个程序不能运行。我们也认识到了自己的薄弱之处，如对链表相关知识的欠缺，文件运用的不熟练，在以后的学习中我们要集中精力、端正态度，争取把知识学得更扎实、更全面。

经过这次的实验，我们整体对各个方面都得到了不少的提高，希望以后学校和系里能够开设更多类似的实验，能够让我们得到更好的锻炼。也让我们深深感受到讨论交流很重要，遇到困难时，大家一起讨论，加强我们的团队合作精神，同时通过这次的课程设计，我们对 数据结构中双向链表结构有了更深刻的理解。篇3：数据结构综合实验心得体会

心得体会：

做了一个星期的程序设计终于做完了，在这次程序设计课中，真是让我获益匪浅。 对大一学习的c语言和这学期开的数据结构，并没有掌握，很多知识都不太懂，突然让自己独立完成一个程序让我手忙脚乱，起码在我认为那真的特别难，看了老师给的题目以及上网查找了一些相关的知识，简单的编了几行就告一段落了，第一天等于只完成了老师要求写的需求分析和概要设计，后来查找了关于哈希表的相关知识，了解了如何创建哈希表，如何合适的构建哈希函数，（选取合适的表长，合适的余数，使得查找时间以及平均查找长度最短）以及什么是除留余数法，和怎样用除留余数法创建哈希表，看懂了之后，我又看了处理冲突的方法，有三种线性探测再散列法法，二次探测再散列法，伪随机数序列法三种，而我所要做的是第一种线性探测再散列的方法，相较后两种要简单很多，在遇到冲突的时候地址加一，知道冲突解决。

在了解这些概念以后，我就开始着手编程序了，在遇到问题的时候请教我们班擅长的同学，慢慢把不能不会不理解的地方给弄明白了，在经过很多次调试以后，一些基本功能已经可以实现了，为了使平均查找长度越小越好，我不断尝试新的表长以及除数，在没有出现错误的基础上，将功能实现，最后，终于在周四的时候将所有的程序调试完全。 这次的综合性实验使我了解到，平时对知识的积累相当重要，同时也要注重课上老师的讲解，老师在课上的延伸是课本上所没有的，这些知识对于我们对程序的编写有很大的作用，同时，编程也要求我们有足够的耐心，细细推敲。越着急可能就越无法得到我们想要的结果，遇到不会的问题要多多请教，知识是在实践与向别人请教的过程中积累的，所以问是至关重要的，只要肯下功夫很多东西都是可以完成的。篇4：数据结构实验报告及心得体会 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;ia[i+1].score[j]) { temp=a[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;k0&&a[i].score[j]!=a[i-1].score[j]) k++; printf( %4d ,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;j0&&stu[i].score[n]!=stu[i-1].score[n]) k++; printf(%4d,k); printf( %4d,stu[i].number); printf( %s,stu[i].name); 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的结点数和叶子结点数。

推荐第10篇：数据结构

实验：线性表的基本操作

【实验目的】

学习掌握线性表的顺序存储结构、链式存储结构的设计与操作。对顺序表建立、插入、删除的基本操作，对单链表建立、插入、删除的基本操作算法。

【实验内容】

1.顺序表的实践

1) 建立4个元素的顺序表s=sqlist[]={1，2，3，4，5}，实现顺序表建立的基本操作。

2) 在sqlist []={1，2，3，4，5}的元素4和5之间插入一个元素9，实现顺序表插入的基本操作。

3) 在sqlist []={1，2，3，4，9，5}中删除指定位置（i=5）上的元素9，实现顺序表的删除的基本操作。 2.单链表的实践

3.1) 建立一个包括头结点和4个结点的（5，4，2，1）的单链表，实现单链表建立的基本操作。

2) 将该单链表的所有元素显示出来。

3) 在已建好的单链表中的指定位置（i=3）插入一个结点3，实现单链表插入的基本操作。

4) 在一个包括头结点和5个结点的（5，4，3，2，1）的单链表的指定位置（如i=2）删除一个结点，实现单链表删除的基本操作。 5) 实现单链表的求表长操作。

【实验步骤】

1.打开VC++。

2.建立工程：点File->New，选Project标签，在列表中选Win32 Console Application，再在右边的框里为工程起好名字，选好路径，点OK->finish。至此工程建立完毕。

3.创建源文件或头文件：点File->New，选File标签，在列表里选C++ Source File。给文件起好名字，选好路径，点OK。至此一个源文件就被添加到了你刚创建的工程之中。

4．写好代码

5．编译－＞链接－＞调试

【实验心得】

线性是我们学习数据结构中，碰到的第一个数据结构。学习线性表的重点掌握顺序表和单链表的各种算法和时间性能分析。线性表右两种存储方式即顺序存储结构和链式存储结构。通过学习我知道了对线性表进行建立、插入、删除，同时单链表也是进行建立、插入、删除。而对于顺序表的插入删除运算，其平均时间复杂度均为0（n）.通过这次的学习，掌握的太熟练，主要是课本上的知识点没有彻底的理解，回去我会多看书，理解重要的概念。总之，这次实验我找到了自己的不足之处，以后会努力的。

实验二：栈的表示与实现及栈的应用

【实验目的】

（1） 掌握栈的顺序存储结构及其基本操作的实现。 （2） 掌握栈后进先出的特点，并利用其特性在解决实际问题中的应用。 （3） 掌握用递归算法来解决一些问题。 【实验内容】

1.编写程序，对于输入的任意一个非负十进制整数，输出与其等值的八进制数。

2.编写递归程序，实现N！的求解。3.编写递归程序，实现以下函数的求解。

n,n0,1Fib(n) Fib(n1)Fib(n2),n1

4.编写程序，实现Hanoi塔问题。【实验步骤】 1.打开VC++。

2.建立工程：点File->New，选Project标签，在列表中选Win32 Console Application，再在右边的框里为工程起好名字，选好路径，点OK->finish。至此工程建立完毕。

3.创建源文件或头文件：点File->New，选File标签，在列表里选C++ Source File。给文件起好名字，选好路径，点OK。至此一个源文件就被添加到了你刚创建的工程之中。

4．写好代码

5．编译－＞链接－＞调试

【实验心得】

通过这次的学习我掌握了栈这种抽象数据类型的特点，并能在相应的应用任务中正确选用它；总的来说，栈是操作受限的线性表，是限定仅在表尾进行插入或删除操作的线性表。因此，对栈来说，表尾端有其特殊含义，称为栈顶（top），相应地，表头端称为栈底（botton）；栈又称为后进先出（Last In First Out）的线性表,简称LIFO结构，因为它的修改是按后进先出的原则进行的。

加上这个实验，我已经学了线性表（顺序表，单链表）和栈，知道它们都是线性表，而且对以后的学习有很大的作用，可以说这是学习以后知识的总要基础。

实验三：二叉树的建立及遍历

【实验目的】

（1） 掌握利用先序序列建立二叉树的二叉链表的过程。 （2） 掌握二叉树的先序、中序和后序遍历算法。 【实验内容】

1.编写程序，实现二叉树的建立，并实现先序、中序和后序遍历。如：输入先序序列abc###de###，则建立如下图所示的二叉树。

并显示其先序序列为：abcde 中序序列为：cbaed 后序序列为：cbeda 【实验步骤】 1.打开VC++。

2.建立工程：点File->New，选Project标签，在列表中选Win32 Console Application，再在右边的框里为工程起好名字，选好路径，点OK->finish。至此工程建立完毕。

3.创建源文件或头文件：点File->New，选File标签，在列表里选C++ Source File。给文件起好名字，选好路径，点OK。至此一个源文件就被添加到了你刚创建的工程之中。

4．写好代码

5．编译－＞链接－＞调试

【实验心得】

这次试验是关于二叉树的常见操作，主要是二叉树的建立和遍历，在这次实验中我按先序方式建立二叉树的，而遍历方式则相对要多一些，有递归的先序、中序、后序遍历，和非递归的先序、中序、后序遍历，此外还有层次遍历.二叉树高度和叶子个数的计算和遍历相差不大，只是加些判断条件，总体来说，本次试验不太好做，期间出现了很多逻辑错误，变量初始化的问题等，不过经过仔细排查最后都一一解决了。

实验四：查找与排序

【实验目的】

（1） 掌握折半查找算法的实现。 （2） 掌握冒泡排序算法的实现。 【实验内容】

1.编写折半查找程序，对以下数据查找37所在的位置。5，13，19，21，37，56，64，75，80，88，92 2.编写冒泡排序程序，对以下数据进行排序。 49，38，65，97，76，13，27，49 【实验步骤】 1.打开VC++。

2.建立工程：点File->New，选Project标签，在列表中选Win32 Console Application，再在右边的框里为工程起好名字，选好路径，点OK->finish。至此工程建立完毕。

3.创建源文件或头文件：点File->New，选File标签，在列表里选C++ Source File。给文件起好名字，选好路径，点OK。至此一个源文件就被添加到了你刚创建的工程之中。

4．写好代码

5．编译－＞链接－＞调试

（1）查找算法的代码如下所示： #include \"stdio.h\" #include \"malloc.h\" #define OVERFLOW -1 #define OK 1 #define MAXNUM 100 #define N 10 typedef int Elemtype; typedef int Status; typedef struct {

Elemtype *elem;

int length; }SSTable; Status InitList(SSTable &ST ) { int i,n;

ST.elem =

(Elemtype*)

malloc (Elemtype));

if (!ST.elem) return(OVERFLOW);

printf(\"输入元素个数和各元素的值:\");

scanf(\"%d\\n\",&n);

for(i=1;i

(MAXNUM*sizeof

scanf(\"%d\",&ST.elem[i]); }

ST.length = n;

return OK; } int Seq_Search(SSTable ST,Elemtype key) {

int i;

ST.elem[0]=key;

for(i=ST.length;ST.elem[i]!=key;--i);

return i; } int BinarySearch(SSTable ST,Elemtype key) {

int mid,low,high,i=1;

low=1;

high=ST.length;

while(low

{

mid=(low+high)/2;

if(ST.elem[mid]==key)

return mid;

else if(key

high=mid-1;

else

}

return 0; } void main() { SSTable ST; InitList(ST);

Elemtype key; int n; printf(\" key= \");

scanf(\"%d\",&key);

printf(\"\\n\\n\");

/*printf(\"After SeqSearch:: \");

n=Seq_Search(ST,key);

printf(\"position is in %d \\n\\n\",n);*/

printf(\"After Binary Search::\");

n=BinarySearch(ST,key);

low=mid+1; if(n) printf(\"position is in %d \\n\\n\",n); else

} 实验结果如下所示：

（2）排序算法的代码如下所示： #include \"stdio.h\" #include \"malloc.h\" #define OVERFLOW -1 #define OK 1 #define MAXNUM 100 #define N 10 typedef int Elemtype; typedef int Status; typedef struct {

Elemtype *elem;

int length; }SSTable; Status InitList(SSTable &ST ) printf(\"not in \\n\\n\"); { int i,n;

ST.elem (Elemtype));

if (!ST.elem) return(OVERFLOW);

printf(\"输入元素个数和各元素的值:\");

scanf(\"%d\\n\",&n);

for(i=1;i

scanf(\"%d\",&ST.elem[i]); }

ST.length = n;

return OK; } void Sort(SSTable ST) {

int i,j,t;

for(i=1;i

for(j=i+1;j

if(ST.elem[i]>ST.elem[j]) { t=ST.elem[i]; =

(Elemtype*)

malloc

(MAXNUM*sizeof

}

} ST.elem[i]=ST.elem[j]; ST.elem[j]=t; void display(SSTable ST) { int i;

for(i=1;i

printf(\"%d

\",ST.elem[i]); }

} void main() {

SSTable ST; InitList(ST); int n; printf(\"before sort::\\n\"); display(ST); Sort(ST); printf(\"\\nafter sort::\\n\"); display(ST); } 实验结果如下所示：

【实验心得】

通过这次实验,我明白了程序里的折半查找和冒泡查找.其实排序可以有很多种，但是其目的应该都是为了能够在海量的数据里迅速查找到你要的数据信息，折半查找是种比较快的方式，但前提是要是有 序的排序才可以。对于有序表，查找时先取表中间位置的记录关键字和所给关键字进行比较，若相等，则查找成功；如果给定值比该记录关键字大，则在后半部分继续进行折半查找；否则在前半部分进行折半查找，直到查找范围为空而查不到为止。折半查找的过程实际上死先确定待查找元素所在的区域，然后逐步缩小区域，直到查找成功或失败为止。算法中需要用到三个变量，low表示区域下界，high表示上界，中间位置mid=(low+high)/2.而冒泡查找则是从小到大的排序.

第11篇：数据结构

数据结构】二叉排序树的建立，查找，插入和删除实践题 /*sy53.c*/

#include

#include

typedef int KeyType;

typedef struct node{

KeyType key;

struct node *lchild,*rchild;

}BSTNode;

typedef BSTNode *BSTree;

BSTree CreateBST(void);

void SearchBST(BSTree T,KeyType Key);

void InsertBST(BSTree *Tptr,KeyType Key);

void DelBSTNode(BSTree *Tptr,KeyType Key);

void InorderBST(BSTree T);

main()

{BSTree T;

char ch1,ch2;

KeyType Key;

printf(\"建立一棵二叉排序树的二叉链表存储\\n\");

T=CreateBST();

ch1=\'y\';

while (ch1==\'y\' || ch1==\'Y\')

{printf(\"请选择下列操作：\\n\");

printf(\"1------------------更新二叉排序树存储\\n\");

printf(\"2------------------二叉排序树上的查找\\n\");

printf(\"3------------------二叉排序树上的插入\\n\");

printf(\"4------------------二叉排序树上的删除\\n\");

printf(\"5------------------二叉排序树中序输出\\n\");

printf(\"6------------------退出\\n\");

scanf(\"\\n%c\",&ch2);

switch (ch2)

{case \'1\':T=CreateBST();break;

case \'2\':printf(\"\\n请输入要查找的数据：\");

scanf(\"\\n%d\",&Key);

SearchBST(T,Key);

printf(\"查找操作完毕。\\n\");break;

case \'3\': printf(\"\\n请输入要插入的数据：\");

scanf(\"\\n%d\",&Key);

InsertBST(&T,Key);

printf(\"插入操作完毕。\\n\");break;

case \'4\': printf(\"\\n请输入要删除的数据：\");

scanf(\"\\n%d\",&Key);

DelBSTNode(&T,Key);

printf(\"删除操作完毕。\\n\");break;

case \'5\': InorderBST(T);

printf(\"\\n二叉排序树输出完毕。\\n\");break;

case \'6\':ch1=\'n\';break;

default:ch1=\'n\';

}

}

}

BSTree CreateBST(void)

{BSTree T;

KeyType Key;

T=NULL;

printf(\"请输入一个关键字(输入0时结束输入)：\\n\"); scanf(\"%d\",&Key);

while (Key)

{InsertBST(&T,Key);

printf(\"请输入下一个关键字(输入0时结束输入)：\\n\"); scanf(\"\\n%d\",&Key);

}

return T;

}

void SearchBST(BSTree T, KeyType Key)

{ BSTNode *p=T;

while(p)

{if(p->key==Key)

{printf(\"已找到\\n\");

return;

}

p=(Keykey) ? p->lchild:p->rchild;

}

printf(\"没有找到\\n\");

}

void InsertBST(BSTree *T,KeyType Key)

{BSTNode *f,*p;

p=(*T);

while(p)

{if(p->key==Key)

{printf(\"树中已有Key不需插入\\n\");

return;

}

f=p;

p=(Keykey)?p->lchild:p->rchild;

}

p=(BSTNode*)malloc(sizeof(BSTNode));

p->key=Key;

p->lchild=p->rchild=NULL;

if ((*T)==NULL) (*T)=p;

else if (Keykey) f->lchild=p;

else f->rchild=p;

}/*InsertBST*/

void DelBSTNode(BSTree *T,KeyType Key)

{BSTNode *parent=NULL, *p, *q,*child;

p=*T;

while(p)

{if(p->key==Key) break;

parent=p;

p=(Keykey)?p->lchild:p->rchild;

}

if (!p) {printf(\"没有找到要删除的结点\\n\");return;}

q=p;

if (q->lchild && q->rchild)

for (parent=q,p=q->rchild; p->lchild; parent=p,p=p->lchild); child=(p->lchild)?p->lchild:p->rchild;

if (!parent) *T=child;

else {if (p==parent->lchild)

parent->lchild=child;

else parent->rchild=child;

if (p!=q)

q->key=p->key;

}

free(p);

}

void InorderBST(BSTree T) { if(T!=NULL)

{InorderBST(T->lchild); printf(\"%5d\",T->key); InorderBST(T->rchild); }

}

第12篇：《数据结构与算法》课程设计的心得体会

课程设计的心得体会

在两周的学习和实践过程中，通过解决学生搭配问题这一实际问题，让我对循环队列有了更深的了解，对数据结构也产生了更加浓厚的兴趣，同时也是对我解决实际问题能力的一次提升。

记得王教授给我们上课时就要不断的通过走算法的方式，掌握所学习的数据结构、算法等，而上机则能进一步巩固自己所学的知识、提高自己的学习能力。在上机的同时也改正了自己对某些算法的错误使用，使自己能在通过程序解决问题时抓住关键算法，能够很好的够造出解决问题的数据结构、算法的设计思想和流程图，并用C语言描绘出关键算法。

首先对于这次的课程设计题目而言，主要是对队列这一知识点的运用。首先是对问题的分析，明白题目的具体要求，即将现实生活中的舞会搭配问题，用链队列这一数据结构描绘出来。用两个链队列boy和girl分别代表男生和女生，当播放每一首歌曲时，便可使两队各有一元素出队列，这样就可以模拟出搭配情况。同时，由于题目要求系统能模拟动态地显示出上述过程，所以就考虑调用一个延迟函数sleep( )，使歌曲之间有一段时间间隔，即模拟了显示中的那一动态过程。其次便是在实现过程中遇到的具体细节问题，比如一开始设计了两个出对函数DeQueue( )，让首元素结点出队，然后调用入队函数Add( )，使其入队到队尾，但在测试时发现，如果输入的人数为2，那么在到第三首歌曲时程序便会终止；经过分析发现是这两个函数的调用，使数据出错，所以就将这两个出对函数用一个函数change( )代替，这个函数能实现将首元素结点移到队尾的功能。这样不仅没有了之前的问题，而且使程序更加易懂。在这些细节方面的具体设计，是对个人分析问题、解决问题能力的一个很好的锻炼。通过这个过程的锻炼，不仅能对所学的知识点有很好的掌握，而且还是对个人能力的很好的训练。

其次，以前我对数据结构（C语言描述）的一些标准库函数不太了解，还有对函数调用的正确使用不够熟悉，还有对C语言中经常出现的错误也不了解，通过实践，使我在这几个方面的认识有所提高。让自己有一定的能力去改正一些常见的错误语法，很高兴这两周的学习让我对数据结构（C语言描述）有了新的认识，所以后在学习过程中，我会更加注视实践操作，使自己便好地学好计算机。 在这次课程设计的实验中，我收获了许多知识，通过查找大量资料，请教老师，以及不懈的努力，也培养了独立思考、动手操作的能力。我也学会了许多学习和解决实际问题的方法，让我受益匪浅。课程设计对我来说，趣味性强，不仅锻炼能力，而且可以学到很多东西，在与老师和同学的交流过程中，互动学习，将知识融会贯通，也增强了我和同学之间的团队合作的能力。让我们知道只要努力，集中精力解决问题，一定会有收获的，过程也是很重要的。

在这次课程设计中我们要学会利用时间，在规定的时间内完成我们的任务，要逐渐养成用C语言编写程序的良好习惯。这些对我来说都是一种锻炼，一个知识积累的过程，一种能力的提高。要打好基础，才能用更好的办法，更简洁明了的程序解决实际问题，只有这样才能进一步的取得更好的成绩。我们会更加努力，努力的去弥补自己的缺点，发展自己的优点，去充实自己，只有在了解了自己的长短之后，我们会更加珍惜拥有的，更加努力的去完善它，增进它。

当然我现在的水平还是很有限，但我还会继续努力的，在解决实际问题时如果遇到了难题，我们要学会去查找大量的有关这方面的资料，还要借助于网络不断扩大自己的知识面和阅读量。这样也可以锻炼我们的自主学习能力和解决问题的能力，学到了许多以前没学到的东西。

在课程设计中的程序都比较复杂，所以需要我们要更加地细心，认真的完成每一步的操作，修改语法，按照老师的指导思想来完成。还记得一开始拿到题目时我们的一脸茫然，而现在是收获满满的自信，每个人都或多或少有所收获，也让我们对程序设计和算法有了进一步理解、认识。

第13篇：数据结构与算法课程设计 心得体会 学习体会

课程设计的心得体会

每一次课程设计，都有不一样的感受，通过课程设计，对我而言，得到的不仅仅是知识，更是获得知识的方法，这显得更加的重要。

本次课程设计，我的设计题目是校园导游程序，本程序主要用到的是课本中图的知识，以校园中的景点作为顶点，以景点间的路径作为边，就构成了图。我用到的时临界表存储结构，这样对空间的浪费不至于很大。主要完成的功能是最短路径和所有路径的算法，最短路径用的是书上的Dijkstra算法，原来我对这个算法的只是出于一个对大致的过程知道的程度，课程设计之后，我对该算法可以说是很熟悉了，不管是算法思想还是代码。另一个主要功能是求两个景点间的所有路径，这个算法书上没有提到，我一步步的摸索，用了一个递归的思想，再经过不断的修改，一次次的单步运行，通过查看相应变量的变化情况，将此算法实现的。最后完成整个程序。

课程设计，本人感觉对于写程序，首先要要的是思想，即完成每个功能需要的算法思想，在想好思想后，就要具体到代码，计算机能够识别的代码，代码写好后，大多情况下是有错误的，首先要排除语法错误，然后时语义错误，在排错的过程中，我用到的最多的是单步运行，感觉单步运行这种方式很管用，通过一步步的运行，通过每一步的运行，观察其中变量的变化情况，可以很容易的知道代码是哪一步出了错误，这样对排错有很大的帮助。 在课程设计的过程中，曾遇到过很多的问题，如对路径字符串的处理，整个递归一步步的往下调用和返回过程，还有很多细节的问题。在遇到问题时，首先想到的是自己思考，分析过程，查找资料，上网百度，通过自己的努力还没有解决时，这是首先需要问的是自己旁边的同学，和同学讨论，有时还争得面红耳赤，如果最后将此不下，就向老师提问。这课程设计的过程中，我几乎所有的问题处理流程就是这个样子的。我感觉这就是一种学习的方法，在学习中遇到难题时的学习方法，要把这种学习的方法变成一种习惯，这才是每次课程设计应达到的一种效果。

课程设计提供了这样一种学习的机会，可以随时随地向老师请教，和老师交流的一个机会，和同学互相讨论的机会。课程设计教会了我，如何用计算机程序来处理现实中的实际问题。将现实中的实际问题先转化为数学模型，然后将数学模型用程序解决的一种能力。

第14篇：数据结构与算法课程设计 心得体会 学习体会

课程设计的心得体会

班级：计算机科学与技术08计科2班学号：0804012031姓名：杨松

对于本课程设计《算术表达式求值问题》，在起初分析题目时，只有一个大概的轮廓，包括算术表达式的运算规则，算术表达式所用到的数据结构，即栈，知道并会使用栈的基本运算，了解算术表达式求值的基本算法思想，操作数栈和算符栈的结合使用。

于是开始着手编写程序，将上述已经明白的知识点通过程序展现出来，包括两种栈的定义，涉及到的栈的功能函数的设计，以及基本的算术表达式的简单计算，才发现，虽然上述基本工作已经完成，但对于具体处理算术表达式时，出现了很多的语法问题，逻辑问题，包括：怎样区分算术表达式中的算符和操作数的问题，怎样进行优先级的判断和比较问题，怎样处理非法算符的问题；怎样处理非法操作数的问题，怎样处理括号匹配的问题，怎样处理操作数为多位数的问题，怎样处理当操作数从正整数范围扩充到实数范围时的问题，怎样处理具体调用功能函数时出现的问题，怎样编辑菜单方便用户的问题，等等；这些问题困扰了我一部分时间，之后，经反复思考，反复查阅资料，反复浏览网络，同时与同学交流讨论，请教老师，上述问题均得到了解决。

在解决算法设计过程中出现的难题之后，程序初步完成，但并不是到此为止，如何改进算法，如何提高算法的时间复杂度、空间复杂度，如何处理一些意想不到的错误和特有情况，也花了一部份时间。

在进行课程设计过程中，我发现，独立思考起到了很关键的作用，在遇到问题时，首先想到的并不是去请教老师，而是回忆所学的知识点、查阅书本和参考资料，网络也起到了一定的辅助作用；在必要时，与同学交流、讨论，交换思想和方法，同时巩固了知识点；与此同时，请教老师，指导程序的设计思想和方法。另外，本人的上机操作能力和动手能力明显提高，思考问题、分析问题的方式得到了改进，解决问题的能力得到了提升，同时在与同学的交流和积极讨论的过程中，不仅巩固了所学的知识点，而且设计算法和程序的方法也有一定程度的提高。

谈谈不足之处，本次课程设计中，在遇到问题和错误时，有时显得很浮躁，无从下手时，更急于解决问题，浏览网络资源，却忘记怎样结合所学知识点来进行思考问题、分析错误。所以独立思考的能力和分析问题、解决问题的能力还有待于提高，知识点的巩固还需要进一步加强。

第15篇：数据结构与算法 课程设计的心得体会

课程设计的心得体会

这次课程设计抽到了一个不太好的题目，是“国王与骑士”问题。乍一看是完全没有头绪，甚至连题目要求都感觉有些晦涩难懂。虽然很羡慕那些抽到了简单题目的同学，但既已成为事实，也没有办法，于是我便静下心来思考“国王与骑士”。

仔细钻研了一天，终于有了些思路，但都只是泛泛而谈，根本不能转化为具体的算法。就比如说骑士的走法问题吧，骑士是以“马”字形行走的，要判断两点间的最短路径，虽然肉眼判断比较简单，但转化成计算机问题时就出现了一系列问题。于是我又不得不停下程序的思考，去查询各种资料。我首先吧整个问题分裂开来，分解成了多个细小的问题，然后再分别查询每一个小问题，这样就轻松多了。就像上面的例子，我只需要查询有关最短路径的算法，就可以解决，这节省了我很多时间。但是。即使是一个简单问题也有多种算法可以解决，这就要求我根据题设条件进行判断，从中寻找最优算法。比如，在球巨额骑士的最短路径时就有弗洛伊得算法，迪杰斯特拉算法，还可以通过广度优先探测的方法等等。但就这一问题而言，我觉得在这里应用广度优先搜索应该是最简单易行的，而且使得算法的时间复杂度会大大降低。就这样，通过问题的分解，以及每个小问题的查询资料与询问老师，我逐步解决着这个问题。

在这一个星期的上机实践学习中，我对C语言有了更进一步的认识和了解，我明白了要想学好它要重在实践，要通过不断的上机操作才能更好地学习它。通过实践，我也发现我的好多不足之处，首先就是自己的经验还很匮乏，在设计算法思路时总是以自然的语言去理解分析，而不能把自己放在机器的角度去看问题，这就导致了许多问题看似可以解决，但真正到了上机编程敲代码是却无从下手。再有对C语言的一些标准库函数以及对函数调用的正确使用不够熟悉，另外，我还对C语言中经常出现的错误也不太了解，也不够敏感，这使得我在程序的调试过程中花费了太多多余的时间。通过实践，使我在这几个方面的认识有所提高。

通过实践的学习，我认到学好计算机要重视实践操作，不仅仅是学习C语言，还是其它的语言，以及其它的计算机方面的知识都要重在实践，所以后在学习过程中，我会更加注视实践操作，使自己便好地学好计算机。

第16篇：数据结构讲稿

云淡风清 http://gsqls.blog.163.com/

第1章 数据结构概述

1.1概述

以下为某市部分院校的交通地图情况，要求找出从出发点到目的地之间的最短路径及其长度。

对于此问题，如果手工去做，速度慢(特别地，现实中实际地图信息要比此例复杂许多)，还容易出错，此时可借助于计算机完成。

计算机进行此类信息的处理时，涉及到两个问题：一是现实当中的信息在计算机中如何表示，二是如何对信息进行处理。

信息的表示和组织又直接关系到处理信息的程序的效率。随着应用问题不断复杂化，导致信息量剧增与信息范围的拓宽，使许多系统程序和应用程序的规模很大，结构又相当复杂。因此，必须分析待处理问题中的对象的特征及各对象之间存在的关系，这就是数据结构这门课所要研究的问题。

1.1.1编写解决实际问题的程序的一般流程

如何通过编写程序，以比手工更为高效精确的方式解决实际问题呢？一般流程如下：

1、由具体问题抽象出一个适当的数学模型；

2、分析问题所涉及的数据量大小及数据之间的关系；

3、确定如何在计算机中存储数据及体现数据之间的关系？

4、确定处理问题时需要对数据作何种运算？

5、确定算法并编写程序；

5、分析所编写的程序的性能是否良好？若性能不够好则重复以上步骤。

云淡风清 http://gsqls.blog.163.com/ 上面所列举的问题基本上由数据结构这门课程来回答。

《数据结构》是计算机科学中的一门综合性专业基础课，是介于数学、计算机硬件、计算机软件三者之间的一门核心课程，不仅是一般程序设计的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序和大型应用程序的重要基础。

1.1.2数据结构的例子

1、电话号码查询系统

设有一个电话号码薄，它记录了N个人的名字和其相应的电话号码。要求设计一个算法，当给定任何一个人的名字时，该算法能够打印出此人的电话号码，如果该电话簿中根本就没有这个人，则该算法也能够报告没有这个人的标志。

姓名

电话号码

陈伟海 13612345588 李四锋 13056112345 。。。

这是一种典型的线性结构。

2、磁盘目录文件系统

磁盘根目录下有很多子目录及文件，每个子目录里又可以包含多个子目录及文件，但每个子目录只有一个父目录，依此类推。

。。。

本问题中各目录从上到小形成了一种一对多的关系，是一种典型的树形结构。

云淡风清 http://gsqls.blog.163.com/

3、交通网络图

下图表明了若干个城市之间的联系：

从图中可看出，一个地方到另外一个地方可以有多条路径，是一种典型的网状结构，数据与数据成多对多的关系。

4、排序问题

对100000个整数进行降序排序。 冒泡法程序： #include #include #include #define N 100000 void main() { int i,j; int a[N+1]; srand(time(NULL)); for(i=1;i

a[i]=rand(); printf("\n按原序输出：\n"); for(i=1;i

printf("%8d",a[i]); system("pause"); for(j=1;j

for(i=N;i>j;i--)

if(a[i]>a[i-1])

{

a[0]=a[i];

a[i]=a[i-1];

a[i-1]=a[0];

} printf("\n按新次序输出：\n");

云淡风清 http://gsqls.blog.163.com/ for(i=1;i

printf("%8d",a[i]); printf("\n"); } 快速排序程序： #include #include #include #define N 100000

void quick_sort(int a[N+1],int left,int right) { int j,last,temp; if(left

{

//将划分子集的元素(此处选中间元素)移动到最左边

temp=a[left];

a[left]=a[(left+right)/2];

a[(left+right)/2]=a[left];

last=left;//用last记录比关键字小的元素的最右位置

for(j=left+1;j

if(a[j]>a[left])

{

temp=a[last];

a[last]=a[j];

a[j]=temp;

last++;

}

//对形成的新子集递归进行快速排序

quick_sort(a,left,last-1);

quick_sort(a,last+1,right); } } void main() { int i; int a[N+1]; srand(time(NULL)); for(i=1;i

a[i]=rand(); printf("\n按原序输出：\n"); for(i=1;i

printf("%8d",a[i]); system("pause");

云淡风清 http://gsqls.blog.163.com/ quick_sort(a,1,N); printf("\n按新次序输出：\n"); for(i=1;i

printf("%8d",a[i]); printf("\n"); } 运行可知，两者速度差异非常明显，主要是排序所花的时间差别很大。可看出，同样的问题，采用不同方法进行处理，有可能呈现出非常大的性能方面的差异。

还可以找到许多其它例子，如图书馆的书目检索系统自动化问题，教师资料档案管理系统，多叉路口交通灯的管理问题等。

1.2基本概念和术语 1.2.1数据(Data)：

是客观事物的符号表示。在计算机科学中指的是所有能输入到计算机中并被计算机程序处理的符号的总称。

1.2.2数据元素(Data Element)：

是数据的基本单位，在程序中通常作为一个整体来进行考虑和处理。一个数据元素可由若干个数据项(Data Item)组成。数据项是数据的不可分割的最小单位。数据项是对客观事物某一方面特性的数据描述。

1.2.3数据对象(Data Object)：

是性质相同的数据元素的集合，是数据的一个子集，其中的数据元素可以是有限的，也可以是无限的。如整数集合：N={0，±1，±2，…}，是无限集，而字符集合：C={ˊAˊ，Bˊ，…，ˊZˊ}则为有限集。

1.2.4数据的逻辑结构：

指对数据元素之间逻辑关系的描述。

数据元素之间的关系可以是一种或多种。

数据元素之间的关系可以是元素之间代表某种含义的自然关系，也可以是为处理问题方便而人为定义的关系，这种自然或人为定义的“关系”称为数据元素之间的逻辑关系，相应的结构称为逻辑结构。其要点有两个方面：一是元素本身，二是元素之间的关系。数据元素之间的逻辑结构有四种基本类型，如下：

云淡风清 http://gsqls.blog.163.com/

①集合：结构中的数据元素除了“同属于一个集合”外，没有其它关系。 ②线性结构：结构中相邻的数据元素之间存在一对一的关系。 ③树型结构：结构中相邻的数据元素之间存在一对多的关系。

④图状结构或网状结构：结构中相邻的数据元素之间存在多对多的关系。 数据结构数学形式的定义是一个二元组： DataStructure=(D，S) 其中：D是数据元素的有限集，S是D上关系的有限集。 例：设数据逻辑结构B=(K，R)，其中： K={k1, k2, …, k9}

R={，，，，，，，，，，} 画出这逻辑结构的图示，并确定哪些是起点，哪些是终点。

1.2.5数据的物理结构：

又称存储结构，指数据结构在计算机内存中的存储方式。

数据结构在计算机内存中的存储包括数据元素的存储和元素之间的关系的存储。 元素之间的关系在计算机中有两种不同的表示方法：顺序表示和非顺序表示。由此得出两种不同的存储结构：顺序存储结构和链式存储结构。

顺序存储结构：用数据元素在存储器中的相对位置来表示数据元素之间的逻辑结构(关系)。 链式存储结构：在每一个数据元素中增加一个存放另一个元素地址的指针(pointer)，用该指针来表示数据元素之间的逻辑结构(关系)。

例：设有数据集合A={3.0,2.3,5.0,-8.5,11.0}，两种不同的存储结构。 顺序结构：数据元素存放的地址是连续的；

链式结构：数据元素存放的地址是否连续没有要求。

数据的逻辑结构和物理结构是密不可分的两个方面，一个算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采用的存储结构。

在C语言中，用一维数组表示顺序存储结构；通过结构体类型实现的链表来表示链式存储结构。

1.2.6数据结构(Data Structure)：

按某种逻辑关系组织起来的一批数据，按一定的映象方式把它存放在计算机存贮器中，并在这些数据上定义了一个运算的集合，就叫做数据结构。

1.2.7数据结构的三个组成部分：

逻辑结构：数据元素之间逻辑关系的描述：D_S=(D，S)。

存储结构：数据元素在计算机中的存储及其逻辑关系的表现称为数据的存储结构或物理结构。 数据操作：对数据要进行的运算。

本课程中将要讨论的三种逻辑结构及其采用的存储结构如下图所示。

云淡风清 http://gsqls.blog.163.com/

逻辑结构与所采用的存储结构

数据逻辑结构层次关系图

1.2.8数据类型(Data Type)：

指的是一个值的集合和定义在该值集上的一组操作的总称。

数据类型是和数据结构密切相关的一个概念。在C语言中数据类型有：基本类型(如int，float，double，char等)和构造类型(如数组，结构体，共用体等)。

数据结构不同于数据类型，也不同于数据对象，它不仅要描述数据类型的数据对象，而且要描述数据对象各元素之间的相互关系。

1.3数据结构的运算

数据结构的主要运算包括： ⑴建立(Create)一个数据结构； ⑵消除(Destroy)一个数据结构；

⑶从一个数据结构中删除(Delete)一个数据元素； ⑷把一个数据元素插入(Insert)到一个数据结构中； ⑸对一个数据结构进行访问(Acce)；

⑹对一个数据结构(中的数据元素)进行修改(Modify)； ⑺对一个数据结构进行排序(Sort)； ⑻对一个数据结构进行查找(Search)。

以上只列举了一些常见运算，实际应用当中可能会遇到许多其它运算。

云淡风清 http://gsqls.blog.163.com/ 1.4抽象数据类型(Abstract Data Type) 1.4.1抽象数据类型简介：

简称ADT，是指一个数学模型以及定义在该模型上的一组操作。ADT的定义仅是一组逻辑特性描述，与其在计算机内的表示和实现无关。因此，不论ADT的内部结构如何变化，只要其数学特性不变，都不影响其外部使用。

ADT的形式化定义是三元组：ADT=(D，S，P) 其中：D是数据对象，S是D上的关系集，P是对D的基本操作集。 说明：

⑴ADT和数据类型实质上是一个概念，其区别是：ADT的范畴更广,它不再局限于系统已定义并实现的数据类型，还包括用户自己定义的数据类型。

⑵ADT的定义是由一个值域和定义在该值域上的一组操作组成。包括定义，表示和实现三个部分。 ⑶ADT的最重要的特点是抽象和信息隐蔽。抽象的本质就是抽取反映问题本质的东西，忽略非本质的细节，使所设计的结构更具有一般性，可以解决一类问题。信息隐蔽就是对用户隐藏数据存储和操作实现的细节，使用者了解抽象操作或界面服务，通过界面中的服务来访问这些数据。

ADT不考虑物理结构以及算法的具体实现。

例：整数的数学概念和对整数所能进行的运算构成一个ADT，C语言中的变量类型int就是对这个抽象数据类型的一种物理实现。

1.4.2ADT的一般定义形式：

ADT的一般定义形式是： ADT { 数据对象： 数据关系： 基本操作： }ADT 其中数据对象和数据关系的定义用伪码描述。 基本操作的定义是： () 初始条件： 操作结果： 说明：

初始条件：描述操作执行之前数据结构和参数应满足的条件；若不满足，则操作失败，返回相应的出错信息。

操作结果：描述操作正常完成之后，数据结构的变化状况和应返回的结果。

1.5算法(Algorithm) 1.5.1算法基本概念：

算法是对特定问题求解方法(步骤)的一种描述，是指令的有限序列，其中每一条指令表示一个或

云淡风清 http://gsqls.blog.163.com/ 多个操作。

1.5.2算法的基本特征：

算法具有以下五个特性

①有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。

②确定性：算法中每一条指令必须有确切的含义。不存在二义性。且算法只有一个入口和一个出口。

③可行性：一个算法是能行的。即算法描述的操作都可以通过已经实现的基本运算执行有限次来实现。

④输入：一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。

⑤输出：一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。

1.5.3算法的基本描述方法：

一个算法可以用多种方法描述，主要有：使用自然语言描述；使用形式语言描述；使用计算机程序设计语言描述等。

1.5.4算法与程序的异同比较：

算法和程序是两个不同的概念。一个计算机程序是对一个算法使用某种程序设计语言的具体实现。算法必须可终止意味着不是所有的计算机程序都是算法。

1.5.5评价算法好坏的几个标准：

评价一个好的算法有以下几个标准

①正确性(Correctne)：算法应满足具体问题的需求。

②可读性(Readability)：算法应易于供人阅读和交流。可读性好的算法有助于对算法的理解和修改。

③健壮性(Robustne)：算法应具有容错处理。当输入非法或错误数据时，算法应能适当地做出反应或进行处理，而不会产生莫名其妙的输出结果。

④通用性(Generality)：算法应具有一般性，即算法的处理结果对于一般的数据集合都成立。 ⑤效率与存储容量需求：效率指的是算法执行的时间；存储容量需求指算法执行过程中所需要的最大存储空间。一般地，这两者与问题的规模有关。

1.6算法效率的度量

解决同一个问题的算法可能有多种，如何选择一个效率高的算法呢？应该来讲，与算法效率相关的因素有很多，如下：

云淡风清 http://gsqls.blog.163.com/

1、算法选用何种策略；

2、问题的规模；

3、程序设计的语言；

4、编译程序所产生的机器代码的质量；

5、内存的大小；

6、外存的大小；

7、机器执行指令的速度；

8、其它。

而确定算法效率的方法通常有两种：

1.6.1事后统计：

先实现算法，然后运行程序，测算其时间和空间的消耗。 缺点：

1、必须先依据算法编制程序并运行程序，耗费人力物力；

2、依赖软硬件环境，容易掩盖算法本身的优劣。由于算法的运行与计算机的软硬件等环境因素有关，不容易发现算法本身的优劣。同样的算法用不同的编译器编译出的目标代码数量不同，完成算法所需的时间也不同；若计算机的存储空间较小，算法运行时间也就会延长；

3、没有实际价值。测试花费不少时间但并没有解决现实中的实际问题。

1.6.2事前分析：

仅仅通过比较算法本身的复杂性来评价算法的优劣，不考虑其它的软硬件因素，通常考查算法所用的时间和所需的存储空间。

算法复杂性的度量可以分为时间复杂度和空间复杂度。

1.6.3算法的时间复杂度(Time complexity)

1、算法的时间复杂度

算法的时间复杂度用于度量一个算法所用的时间。

算法所用的时间主要包括程序编译时间和运行时间。由于一个算法一旦编译成功可以多次运行，因此可以忽略编译时间，只讨论算法的运行时间。

算法的运行时间依赖于加、减、乘、除、等基本的运算以及参加运算的数据量的大小，另外，与计算机硬件和操作环境等也有关系。要想准确地估算时间是不可行的，而影响算法时间最为主要的因素是问题的规模，即输入量的多少。同等条件下，问题的规模越大，算法所花费的时间也就越长。例如，求1+2+3+„+n的算法，即n个整数的累加求和，这个问题的规模为n。因此，运行算法所需的时间T是问题规模n的函数，记作T(n)。

同等条件下，相同或类似的基本操作在真正程序运行过程中所花费的时间也差不多，这样，如果两个不同算法中一个所含基本操作多而另一个所含基本操作少，则包含基本操作少的算法其花费时间也就较少。因此，通常用算法中基本语句的执行次数来作为度量算法速度快慢的依据，而这种度量时间复杂度的方法得出的不是时间量，而是一种增长趋势的度量，即当问题规模n增大时，T(n)也随之变大。换言之，当问题规模充分大时，算法中基本语句的执行次数为在渐进意义下的阶，称为算法的渐进时间复杂度，简称时间复杂度，通常用大O记号表示。用数学语言通常描述为：若当且仅当存在正整数n和n0，对于任意n≥n0，都有T(n)≤c×f(n)，则称该算法的渐进时间复杂度为T(n)=O(f(n))。

一般地，常用最内层循环内的语句中的原操作的执行频度(重复执行的次数)来表示时间复杂度。

2、时间复杂度分析举例： 例：两个n阶方阵的乘法。

云淡风清 http://gsqls.blog.163.com/ for(i=1;i

c[i][j]=0;

for(k=1;k

c[i][j]+=a[i][k]*b[k][j]; } 分析：由于是一个三重循环，每个循环从1到n，则总次数为： n×n×n=n3，时间复杂度为T(n)=O(n3)。

例： { ++x; s=0; } 分析：将x自增看成是基本操作，则语句频度为1，即时间复杂度为O(1) 。

如果将s=0也看成是基本操作，则语句频度为2，其时间复杂度仍为O(1)，即常量阶。 只要T(n)不是问题规模n的函数，而是一个常数，它的时间复杂度则均为O(1)。 例：以下程序段： for(i=1;i

++x;

s+=x; } 分析：基本语句的语句频度为：n2 ，其时间复杂度为：O(n2)，即为平方阶。

定理：若T(n)=amnm+am-1nm-1+„+a1n+a0是一个m次多项式，则T(n)=O(nm)，即复杂度表达式只取一个n趋向于无穷大时的同阶无穷小表达式即可。

通过对算法复杂度的分析，总结出这样一条结论，在计算任何算法的复杂度时，可以忽略所有低次幂和最高次幂的系数，这样可以简化算法分析，并使注意力集中在增长率上。

从本质上来讲，此种策略也就是只考虑对算法复杂度影响最大的因素而忽略次要因素。 例：以下程序段：

for(i=2;i

for(j=2;j

{

++x;

a[i,j]=x;

}

云淡风清 http://gsqls.blog.163.com/ 分析：基本语句的语句频度为： 1+2+3+„+n-2 =(1+n-2)×(n-2)/2

=(n-1)×(n-2)/2 =(n2-3n+2)/2 按上述定理，时间复杂度为O(n2)，即此算法的时间复杂度为平方阶。

一个算法时间复杂度为O(1)的算法，它的基本运算执行的次数是固定的。因此，总的时间由一个常数(即零次多项式)来界定。而一个时间为O(n2)的算法则由一个二次多项式来界定。

3、常见表示时间复杂度的阶： O(1)：常量时间阶 O(n)：线性时间阶 O(㏒n)：对数时间阶

O(n㏒n)：线性对数时间阶 O(nk)：k≥2，k次方时间阶

4、常见时间复杂度大小关系分析：

以下六种计算算法时间复杂度的多项式是最常用的，其大小关系通常为： O(1)

当n取得很大时，指数时间算法和多项式时间算法在所需时间上非常悬殊。因此，只要有人能将现有指数时间算法中的任何一个算法化简为多项式时间算法，那就取得了一个伟大的成就。

有的情况下，算法中基本操作重复执行的次数还随输入数据集的不同而不同。 例：素数的判断算法。

void prime(int n)//n是一个正整数 { int i=2; while((n%i)!=0 && i*1.0

i++; if(i*1.0>sqrt(n))

printf("&d 是一个素数\n",n); else

printf("&d 不是一个素数\n",n); } 此例中执行频率最高的语句为i++;，此语句最少执行0次，最多执行sqrt(n)次，对于不同的n，执行次数不确定。

对于此类算法，如果输入数据不同，则算法运行时间也不同，因此要全面分析一个算法，需要考虑算法在最好、最坏、平均情况下的时间消耗。由于最好情况出现的概率太小，因此不具代表性，但是，当最好情况出现的概率大时，应该分析最好情况；虽然最坏情况出现的概率也太小，不具代表性，但是分析最坏情况能够让人们知道算法的运行时间最坏能到什么程度，这一点在实时系统中很重要；分析平均情况是比较普遍的，特别是同一个算法要处理不同的输入时，通常假定输入的数据是等概率分布的。

例：冒泡排序法。

void bubble_sort(int a[],int n)

云淡风清 http://gsqls.blog.163.com/ { int temp; change=false; for(i=n-1;change=TURE;i>1 && change;--i)

for(j=0;j

if(a[j]>a[j+1])

{

temp=a[j];

a[j]=a[j+1];

a[j+1]=temp;

change=TURE;

} } 最好情况：0次

最坏情况：1+2+3+⋯+n-1=n(n-1)/2平均时间复杂度为：O(n2) 1.6.4算法的空间复杂度(Space complexity)

1、算法的空间复杂度

算法的空间复杂度是指在算法的执行过程中需要的辅助空间数量。辅助空间数量指的不是程序指令、常数、指针等所需要的存储空间，也不是输入数据所占用的存储空间，辅助空间是除算法本身和输入输出数据所占据的空间外，算法临时开辟的存储空间。算法的空间复杂度分析方法同算法的时间复杂度相似，设S(n)是算法的空间复杂度，通常可以表示为：

S(n)=O(f(n)) 其中：n为问题的规模(或大小)。 该存储空间一般包括三个方面： 指令常数变量所占用的存储空间； 输入数据所占用的存储空间； 辅助(存储)空间。

一般地，算法的空间复杂度指的是辅助空间。 如：

一维数组a[n]：空间复杂度O(n) 二维数组a[n][m]：空间复杂度O(n*m) 例：数组a中有10000个数，要求将所有数据逆置(即顺序倒过来存放)。 为达到逆置目的，有以下两种方案： 方案一：

int a[10000],b[10000],i; for(i=0;i

int a[10000],t,i; for(i=0;i

云淡风清 http://gsqls.blog.163.com/ { t=a[i]; a[i]=a[10000-i-1]; a[10000-i-1]=t; } 很明显，方案二中的辅助空间数量为1，而方案一中的辅助空间数量为10000，方案二的空间复杂度优于方案一。

在算法的时间复杂度和空间复杂度中，我们更注重算法的时间性能。因此，在对算法性能的分析当中，通常均主要针对算法时间性能进行分析。

1.6.5学习算法的原因

讲述了这么多关于算法的基础知识，究竟为什么要学习算法呢？

首先，算法无处不在。算法不仅出现在数学和计算机程序中，更普遍地出现在我们的生活中，在生活中做什么事情都要有一定的顺序，然而不同的顺序带来的效率和成果可能都会不同，只有学好了算法，才能让生活更有趣、更有效率。

其次，算法是程序的灵魂。学习计算机编程，必须要掌握好其灵魂，否则，写出来的程序就像是没有灵魂的躯体。

再次，算法是一种思想。掌握了这种思想，能够拓展思维，使思维变得清晰、更具逻辑性，在生活以及编程上的很多问题，也就更易解决。

最后，算法的乐趣。学习算法不仅仅是为了让它帮助人们更有效地解决各种问题，算法本身的趣味性很强，当通过烦琐的方法解决了一个问题后会感觉到有些疲惫，但是面对同一个问题，如若学会使用算法，更简单有效地解决了这个问题，会发现很有成就感，算法的速度、思想会让人觉得很奇妙。每一个奇妙的算法都是智慧的结晶。

学习算法的理由成千上万，不同的人可能出于不同的目的去学习算法，希望大家能够通过对课程的学习对算法有进一步的理解。

习题一

1、简要回答术语：数据，数据元素，数据结构，数据类型。

2、数据的逻辑结构？数据的物理结构？逻辑结构与物理结构的区别和联系是什么？

3、数据结构的主要运算包括哪些？

4、算法分析的目的是什么？算法分析的主要方面是什么？

云淡风清 http://gsqls.blog.163.com/

第2章 线性表

下表为某电台提供给听众的若干首英文歌曲名及相关点播情况统计信息：

由于实际的歌曲库可能很大，手工管理效率低，不方便，现请设计一个软件系统实现对此类歌曲库的管理。

分析：

此例中相邻的两首歌之间是一种一对一的关系，属于典型的线性结构，可按线性结构进行组织及管理。

2.1线性结构与线性表 2.1.1线性结构

如果一个数据元素序列满足：

⑴除第一个和最后一个数据元素外，每个数据元素只有一个直接前驱数据元素和一个直接后继数据元素；

⑵第一个数据元素没有前驱数据元素； ⑶最后一个数据元素没有后继数据元素。 则称这样的数据结构为线性结构。

线性表、栈、队列、串和数组都属于线性结构。 如下图：

云淡风清 http://gsqls.blog.163.com/ 2.1.2线性表

线性表(Linear List)是一种最简单、最常用的线性结构，是一种可以在任意位置进行插入和删除数据元素操作的、由n(n≥0)个相同类型数据元素a1，a2，„，an组成的线性结构。在这种结构中：

⑴存在一个唯一的被称为“第一个”的数据元素； ⑵存在一个唯一的被称为“最后一个”的数据元素； ⑶除第一个元素外，每个元素均有唯一一个直接前驱； ⑷除最后一个元素外，每个元素均有唯一一个直接后继。 线性表中的数据元素的个数n称为线性表的长度。 当n=0时，称为空表。空线性表用符号()表示。

当n>0时，将非空的线性表记作：(a1，a2，„an)，其中符号ai(1≤i≤n)表示第i个抽象数据元素。

a1称为线性表的第一个(头)结点，an称为线性表的最后一个(尾)结点。 a1，a2，„ai-1都是ai(2≤i≤n)的前驱，其中ai-1是ai的直接前驱；

ai+1，ai+2，„an都是ai(1≤i ≤n-1)的后继，其中ai+1是ai的直接后继。

线性结构是最常用、最简单的数据结构，而线性表是一种典型的线性结构，其基本特点是可以在任意位置进行插入和删除等操作，且数据元素是有限的。

线性表可以用顺序存储结构或链式存储结构实现。用顺序存储结构实现的线性表称为顺序表，用链式存储结构实现的线性表称为链表。链表主要有单链表、循环单链表和循环双链表三种。顺序表和链表各有优缺点，并且优缺点刚好相反，在实际应用中要根据情况选择对操作及性能有利的存储结构。

线性表中的数据元素ai所代表的具体含义随实际应用领域的不同而不同，在线性表的定义中，只不过是一个抽象的表示符号。

◆线性表中的结点可以是单值元素(每个元素只有一个数据项) 。 例1：26个英文字母组成的字母表：(A，B，C、„、Z) 例2：某校从1978年到1983年各种型号的计算机拥有量的变化情况：(6，17，28，50，92，188) 例3：一副扑克的点数：(2，3，4，„，J，Q，K，A) ◆线性表中的结点可以是记录型元素，每个元素含有多个数据项 ，每个项称为结点的一个域 。每个元素有一个可以唯一标识每个结点的数据项组，称为关键字。

例4：某校2001级同学的基本情况：{(‘2001414101’，‘张里户’，‘男’，06/24/1983)， (‘2001414102’，‘张化司’，‘男’，08/12/1984) „， (‘2001414102’，‘李利辣’，‘女’，08/12/1984) } ◆若线性表中的结点是按值(或按关键字值)由小到大(或由大到小)排列的，称线性表是有序的。 ◆线性表是一种相当灵活的数据结构，其长度可根据需要增长或缩短。

◆对线性表的基本操作如下(实际应用中要根据需要选择相应操作或者添加未列出的操作)： ⑴建立空表L ⑵返回表L的长度，即表中元素个数 ⑶取线性表L中位置i处的元素(1≤i≤n) ⑷取i的直接前驱元素 ⑸取i的直接后继元素

⑹查询元素x在L中的逻辑位置

⑺在线性表L的位置i处插入元素x，原位置元素后移一个位置 ⑻从线性表L中删除位置i处的元素 ⑼判断线性表是否为空 ⑽清空已存在的线性表 ⑾遍历所有元素

云淡风清 http://gsqls.blog.163.com/ ⑿根据所给关键字查询元素并返回其详细信息 ⒀修改表中元素

⒁对所有元素按条件排序

2.1.3线性表的抽象数据类型定义

ADT List { 数据对象：D = { ai | ai∈ElemSet, i=1,2,„,n, n≥0 } 数据关系：R = { | ai-1, ai∈D, i=2,3,„,n } 基本操作： InitList(&L) 初始条件：无

操作结果：构造一个空的线性表L； ListLength(L) 初始条件：线性表L已存在；

操作结果：返回线性表中的元素个数； GetElem(L,i,e) 初始条件：线性表L已存在，1≤i≤ListLength(L)； 操作结果：用e返回L中第i个数据元素的值； ListInsert(L,i,e) 初始条件：线性表L已存在，1≤i≤ListLength(L)+1，线性表未满；

操作结果：在线性表L中的第i个位置插入元素e，原来位置及以后的元素都后移； ListLocate(L,e) 初始条件：线性表L已存在；

操作结果：返回元素e在L中的逻辑位置，不存在则返回0； ListDelete(L,i) 初始条件：线性表L已存在，1≤i≤ListLength(L)； 操作结果：从表L中删除位置i处的元素； ListClear(L) 初始条件：线性表L已存在； 操作结果：清空已存在的表； ListTraverse(L) 初始条件：线性表L已存在； 操作结果：遍历输出所有元素； ListUpdate(L,i,e) 初始条件：线性表L已存在,1≤i≤ListLength(L)； 操作结果：将线性表L中第i个位置的值置为e； ListSort(L) 初始条件：线性表L已存在；

操作结果：按一定条件对所有元素重新排序； ListDestroy(L) 初始条件：线性表L已存在； 操作结果：释放线性表空间； …

云淡风清 http://gsqls.blog.163.com/ } ADT List 2.2线性表的顺序存储 2.2.1线性表的顺序存储结构

顺序存储：把线性表的结点按逻辑顺序依次存入地址连续的一组存储单元里。用这种方法存储的线性表简称顺序表。

顺序存储的线性表的特点：

◆线性表的逻辑顺序与物理顺序一致；

◆数据元素之间的关系是以元素在计算机内“物理位置相邻”来体现的。 设有非空的线性表：(a1，a2，„an) 。顺序存储如下图所示。

在具体的机器环境下，设线性表的每个元素需占用len个存储单元，以所占的第一个单元的存储地址作为数据元素的存储位置，则线性表中第i+1个数据元素的存储位置Loc(ai+1)和第i个数据元素的存储位置Loc(ai)之间满足下列关系：

Loc(ai+1)=Loc(ai)+l 线性表的第i个数据元素ai的存储位置为： Loc(ai)=Loc(a1)+(i-1)*len 高级语言中同一个数组的各个元素占用连续存储单元，具有随机存取(指存取同一数组各元素的时间开销相同，不受所处位置的限制)的特性，故而在高级语言中通常用数组来存储顺序表。除了用数组来存储线性表的元素之外，顺序表还应该表示线性表的长度属性以方便某些操作，所以用结构体类型来定义顺序表类型。

#include #include #define OK

1 #define ERROR

-1 #define MAX_SIZE 100 //最大长度 typedef int Status; //状态

typedef int ElemType;//元素类型，可根据实际需要更改 typedef struct Sqlist { ElemType *Elem_Array;//线性表存储空间地址

int Length;//线性表长度 } SqList; 注意：C语言中数组的下标值是从0开始，第i个元素的下标值是i-1 。

2.2.2顺序表的基本操作

顺序存储结构中，很容易实现线性表的一些操作：初始化、赋值、查找、修改、插入、删除、求长度等。

以下将对几种主要的操作进行讨论。 #include

云淡风清 http://gsqls.blog.163.com/ #include #define OK

1 #define ERROR

-1 #define MAX_SIZE 100 //最大长度 typedef int Status; //状态

typedef int ElemType;//元素类型，可根据实际需要更改 typedef struct Sqlist { ElemType Elem_Array[MAX_SIZE];//线性表存储空间地址

int Length;//线性表长度 } SqList; /*

1、初始化

构造一个空的线性表 */ Status Init_SqList(SqList *L) { L->Length=0; return OK; } /*

2、测长度

返回线性表中的元素个数 */ int Length_SqList(SqList *L) { return L->Length; } /*

3、取元素

用e返回L中第i个数据元素的值，1≤i≤ListLength(L) */ Status Get_SqList(SqList *L,int i,ElemType *e) { if((i>=1)&&(iLength)) {

*e=L->Elem_Array[i-1];//i位置对应的元素下标为i-1

return OK; } else

return ERROR; }

云淡风清 http://gsqls.blog.163.com/ /*

4、顺序线性表的插入

在线性表L中的第i个位置插入元素e，原来位置及以后的元素都后移。 要求1≤i≤ListLength(L)+1，线性表未满。 实现步骤：

(1)将线性表L中的第i个至第n个结点后移一个位置。 (2)将结点e插入到结点ai-1之后。

(3)线性表长度加1。 */ Status Insert_SqList(Sqlist *L,int i,ElemType e) { int j; if((iL->Length+1))//位置错误

return ERROR; else

if(L->Length>=MAX_SIZE)//线性表上溢

//实际开发中达到空间上限时可用remalloc()函数重新分配空间，扩大空间容量

return ERROR;

else

{

//i-1位置以后的所有结点后移

for(j=L->Length-1;j>=i-1;--j)

L->Elem_Array[j+1]=L->Elem_Array[j];

L->Elem_Array[i-1]=e;//在i-1位置插入结点

L->Length++;//线性表长度增1

return OK;

} } /* 时间复杂度分析：

在线性表L中的第i个位置插入新结点，其时间主要耗费在表中结点的移动操作上，因此，可用结点的移动来估计算法的时间复杂度。

设在线性表L中的第i个位置插入结点的概率为Pi，不失一般性，设各个位置插入是等概率，则Pi=1/(n+1)，而插入时移动结点的次数为n-i+1。

总的平均移动次数：Einsert=∑pi*(n-i+1) (1≤i≤n) 计算得：Einsert=n/2。

即在顺序表上做插入运算，平均要移动表上一半结点，当表长n较大时，算法的效率相当低。因此算法的平均时间复杂度为O(n)。

*/ /*

5、线性表元素位置查询

返回元素e在L中的逻辑位置，不存在则返回0

云淡风清 http://gsqls.blog.163.com/ */ int Locate_SqList(Sqlist *L,ElemType e) { int i,found=0;//found用于表示是否找到，0：未找到 1：找到

i=0;//从第一个开始查询

while((iLength)&&(found==0))

if(L->Elem_Array[i]==e)

found=1;

else

i++; if(found==1)

return i+1;//返回逻辑位置编号

else

return 0;//未找到，返回0 } /*

6、删除指定位置元素 在线性表：

L=(a1，„ai-1，ai， ai+1，„，an) 中删除结点ai(1≦i≦n)，使其成为线性表： L= (a1，„ai-1，ai+1，„，an) 要求1≤i≤ListLength(L)，线性表未空。 实现步骤：

(1)将线性表L中的第i+1个至第n个结点依此向前移动一个位置。 (2)线性表长度减1。 */ Status Delete_SqList(Sqlist *L,int i) { int k; if(L->Length==0)//线性表空

{

printf("线性表L为空!\n");

return ERROR; } else

if(iL->Length)//指定位置不合适

{

printf("要删除的数据元素不存在!\n");

return ERROR;

}

else

{

//i位置以后的所有结点前移

for(k=i;kLength;k++)

L->Elem_Array[k-1]=L->Elem_Array[k];

云淡风清 http://gsqls.blog.163.com/

L->Length--;//线性表长度减1

return (OK);

} } /* 时间复杂度分析：

删除线性表L中的第i个元素，其时间主要耗费在表中结点的移动操作上，因此，可用结点的移动来估计算法的时间复杂度。

设在线性表L中删除第i个元素的概率为Pi，不失一般性，设删除各个位置是等概率，则Pi=1/n，而删除时移动结点的次数为n-i。

则总的平均移动次数：Edelete=∑Pi*(n-i)

(1≤i≤n) 计算得：Edelete=(n-1)/2 即在顺序表上做删除运算，平均要移动表上一半结点，当表长n较大时，算法的效率相当低，因此算法的平均时间复杂度为O(n)。

*/ /*

7、清空 */ Status Clear_SqList(Sqlist *L) { L->Length=0; return OK; } /*

8、遍历 以输出为例 */ Status Traverse_SqList(Sqlist *L) { int i; printf("共有%d个元素，以下为具体内容：\n",L->Length); for(i=0;iLength;i++)

printf("%8d",L->Elem_Array[i]); printf("\n------------------END------------------\n"); return OK; } /*

9、修改

将线性表L中第i个位置的值置为e。要求线性表L已存在且1≤i≤ListLength(L)。 */ Status Update_SqList(Sqlist *L,int i,ElemType e) { if((iL->Length))//位置错误

云淡风清 http://gsqls.blog.163.com/

return ERROR; else {

L->Elem_Array[i-1]=e;//放置新数据

return OK; } } /*

10、排序

按要求对线性表中元素排序。 */ Status Sort_SqList(Sqlist *L) { int i,j; ElemType temp; for(i=1;iLength-1;i++)

for(j=0;jLength-i-1;j++)

{

if(L->Elem_Array[j]Elem_Array[j+1])

{

temp=L->Elem_Array[j];

L->Elem_Array[j]=L->Elem_Array[j+1];

L->Elem_Array[j+1]=temp;

}

} return OK; } /* 主函数 */ void main() { int xz=1,i; SqList L; ElemType e; while(xz!=0) {

printf("

1、初始化\n

2、测长度\n

3、取元素\n

4、插入\n

5、查询\n

6、删除\n

7、清空\n

8、遍历\n

9、修改\n

10、排序\n 0、结束\n请选择：");

scanf("%d",&xz);

switch(xz)

{

case 1:

if(Init_SqList(&L)==OK)

云淡风清 http://gsqls.blog.163.com/

printf("初始化成功！\n"); else

printf("初始化未成功！\n"); break; case 2: printf("线性表长度为：%d\n",Length_SqList(&L)); break; case 3: printf("请输入要取元素的位置："); scanf("%d",&i); if(Get_SqList(&L,i,&e)==OK)

printf("指定位置上的元素为：%d\n",e); else

printf("Error！\n"); break; case 4: printf("请输入要插入的位置："); scanf("%d",&i); printf("请输入要插入的元素内容：\n"); scanf("%d",&e); if(Insert_SqList(&L,i,e)==OK)

printf("插入成功\n"); else

printf("Error！\n"); break; case 5: printf("请输入要查询的元素内容："); scanf("%d",&e); printf("此元素逻辑位置为：%d(0表示未找到)。\n",Locate_SqList(&L,e)); break; case 6: printf("请输入要删除元素的位置："); scanf("%d",&i); if(Delete_SqList(&L,i)==OK)

printf("删除成功\n"); else

printf("Error！\n"); break; case 7: Clear_SqList(&L); break; case 8: Traverse_SqList(&L); break;

云淡风清 http://gsqls.blog.163.com/

case 9:

printf("请输入要修改的元素位置：");

scanf("%d",&i);

printf("请输入元素的新内容：\n");

scanf("%d",&e);

if(Update_SqList(&L,i,e)==OK)

printf("修改成功\n");

else

printf("Error！\n");

break;

case 10:

Sort_SqList(&L);

printf("排序完成！\n");

break;

case 0:

printf("谢谢使用，再见！\n");

break;

default:

printf("输入错误！\n");

break;

} } } 需要说明的是，本例没有实现空间的动态分配，若要实现动态分配，可参照第三章“栈的动态顺序存储结构”的做法。

2.2.3顺序存储线性表的特点

优点：表中任意一个结点的存取很方便，可以进行随机存取，处于不同位置上的结点的存取时间从理论上来说相同，也能进行插入和删除操作。

缺点：

(1)插入和删除不方便。为保持连续存放，操作中需要移动大量元素。

(2)会造成空间的浪费以及不易扩充。所占空间通常情况下大小固定，处理长度变化较大的线性表时，分配空间大小不够，会造成溢出；分配空间太大，会造成浪费。

2.3线性表的链式存储 2.3.1线性表的链式存储结构

链式存储：用一组任意(即不必要连续)的存储单元存储线性表中的数据元素。用这种方法存储的线性表简称线性链表。

链表中结点所占用的存储单元可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的，链表中结点的逻辑顺序和物理顺序不一定相同。

为了正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其直接后继结点的

云淡风清 http://gsqls.blog.163.com/ 地址(或位置)，称为指针(pointer)或链(link)，这两部分组成了链表中的结点结构，如下图所示。

data：数据域，存放结点的值。

next：指针域，存放结点的直接后继的地址。

链表通过每个结点的指针域将线性表的n个结点按其逻辑次序链接在一起。每一个结点只包含一个指针域的链表，称为单链表。

为操作方便，总是在链表的第一个结点之前附设一个头指针变量head指向第一个结点。头结点的数据域可以不存储任何信息(或存放链表长度等辅助信息)，此时通常称为带头结点的单链表。当然，也可以让头结点的数据域存放有效数据，此时称为不带头结点的单链表。相对而言，带头结点的单链表浪费了一个结点的数据域，但会给编程带来一定方便。

带头结点的单链表其基本结构如下：

说明：

(1)整个链表由若干个结点组成，一个结点占用一个内存块，而每个结点又分为两大部分：数据域和指针域，其中数据域存放用户数据，指针域用于存放后一个结点的地址，通过指针域将逻辑上前后相邻的结点连接起来，这样，通过前一个结点指针域中存放的地址就可以找到后一个结点。可看出，每个结点的指针域实际上充当了指针变量的角色，只要结点数可变，则意味着指针变量数也可变，而事实上结点所对应的这些内存块完全可以多次动态分配，这也就意味着指针域(相当于指针变量)的个数可以根据需要动态调整，这就解决了前述的“程序中变量个数固定，但问题本身所需变量个数不定”的矛盾。

(2)设置一个头指针变量指向首结点，在带头结点的单链表中，此结点不存放有效数据。 (3)末尾结点的指针域设置为空“NULL”表示链表的结束，相当于字符串中的'\0'。

(4)在没有用户数据的情况下，此链表只有一个结点，此结点既是首结点，又是末结点，结点的指针域为“NULL”，此时表示链表为逻辑“空”，也就是说，链表的初始状态应该如下图所示。

单链表是由表头唯一确定的，因此单链表可以用头指针的名字来命名。 例

1、线性表L=(bat，cat，eat，fat，hat) 其带头结点的单链表的逻辑状态和物理存储方式如下图所示。

云淡风清 http://gsqls.blog.163.com/

1、结点的描述与实现

C语言中用带指针的结构体类型来描述 typedef int ElemType; typedef struct Lnode { ElemType

data;//数据域，保存结点的值

struct

Lnode *next;//指针域，保存后继结点地址 }LNode;

//结点的类型

2、结点空间分配及回收的实现

结点存储空间是通过动态内存分配和释放来实现的，即需要时分配，不需要时释放。在C语言中可通过标准函数：malloc() ，realloc()，sizeof()，free()等来实现分配。

动态分配：p=(LNode*)malloc(sizeof(LNode)); 函数malloc分配了一个类型为LNode的结点变量的空间，并将其首地址放入指针变量p中。 动态释放：free(p) ; 系统回收由指针变量p所指向的内存区。p必须是最近一次调用malloc()函数时的返回值。 动态重新分配：p= (LNode*)realloc(p,newsize); 先判断当前的指针是否有足够的连续空间，如果有，扩大p指向的地址，并且将p返回，如果空间不够，先按照newsize指定的大小分配空间，将原有数据从头到尾拷贝到新分配的内存区域，而后释放原来p所指内存区域，同时返回新分配的内存区域的首地址，即重新分配存储器块的地址。返回值：如果重新分配成功则返回指向被分配内存的指针，否则返回空指针NULL。

3、最常用的基本操作 ⑴ 结点的赋值 LNode *p; p=(LNode*)malloc(sizeof(LNode)); p->data=20; p->next=NULL;讲课时板书教案上的几种常见的指针操作。 效果如下图。

⑵常见的指针操作 ①q=p;

云淡风清 http://gsqls.blog.163.com/ ②q=p->next;

③p=p->next;

④q->next=p;

⑤q->next=p->next;

云淡风清 http://gsqls.blog.163.com/

2.3.2单链式的基本操作

以带头结点的单链表为例。 #define OK

1 #define ERROR

-1 typedef int Status; //状态 #include "stdlib.h" #include "stdio.h" typedef int ElemType; typedef struct Lnode { ElemType

data;//数据域，保存结点的值

struct

Lnode *next;//指针域，保存后继结点地址 }LNode;

//结点的类型

/*

1、链表初始化(建立空链表) */ LNode * Init_LinkList(void) { LNode *L; L=(LNode *)malloc(sizeof(LNode));//给头结点分配空间

if(L!=NULL)

L->next=NULL;//指针域置为空以作为结束标记

return L; } /*

2、头插入法建表

从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直到读入结束标志为止，每次插入的结点都作为链表的第一个数据结点。

*/

云淡风清 http://gsqls.blog.163.com/ Status Create1_LinkList(LNode *L) { ElemType data; char sfjx=1;//0：结束 1：继续

LNode *p; while(sfjx!=0) {

p=(LNode *)malloc(sizeof(LNode));//给新结点分配空间

if(p==NULL)

return ERROR;//空间分配不成功

else

{

printf("请输入元素内容：");

scanf("%d",&data);//读入值

p->data=data;//数据域赋值

//钩链，新创建的结点总是作为第一个数据结点

p->next=L->next;

L->next=p;

}

printf("是否继续(0：结束 1：继续)：");

scanf("%d",&sfjx); } return OK; } /*

3、尾插入法建表

头插入法建立链表虽然算法简单，但生成的链表中结点的次序和输入的顺序相反。若希望二者次序一致，可采用尾插法建表。

该方法是将新结点插入到当前链表的表尾，使其成为当前链表的尾结点。 */ Status Create2_LinkList(LNode *L) { ElemType data; char sfjx=1;//0：结束 1：继续

LNode *p,*q; //找到已有链表的末结点

q=L; while(q->next!=NULL)

q=q->next; while(sfjx!=0) {

p=(LNode *)malloc(sizeof(LNode));//给新结点分配空间

if(p==NULL)

云淡风清 http://gsqls.blog.163.com/

return ERROR;//空间分配不成功

else

{

printf("请输入元素内容：");

scanf("%d",&data);//读入值

p->data=data;//数据域赋值

//钩链，新创建的结点总是作为最后一个结点

q->next=p;

q=p;//q重新指向末结点

}

printf("是否继续(0：结束 1：继续)：");

scanf("%d",&sfjx); } q->next=NULL;//重设链表结束标记

return(OK); } /*

4、按序号查找，取单链表中的第i个元素。

对于单链表，不能象顺序表中那样直接按序号i访问结点，而只能从链表的头结点出发，沿链域next逐个结点往下搜索，直到搜索到第i个结点为止。因此，链表不是随机存取结构。

设单链表的长度为n，要查找表中第i个结点，仅当1≦i≦n时，i的值是合法的。 */ Status Get_LinkList(LNode *L,int i,ElemType *e) {

int j=1; LNode *p; p=L->next;//使p指向第一个结点

while((p!=NULL)&&(j

p=p->next;//移动指针p

j++;

//j计数

} if(p==NULL)//找不到

return(ERROR); else {

*e=p->data;

return(OK); } } /*

云淡风清 http://gsqls.blog.163.com/

5、按值查找

按值查找是在链表中，查找是否有结点值等于给定值key的结点? 若有，则返回首次找到的值为key的结点的存储位置；否则返回NULL。

*/ LNode *Locate_LinkList(LNode *L,ElemType key) { LNode *p; p=L->next; while((p!=NULL)&&(p->data!=key))

p=p->next; if(p!=NULL)//找到了

return p; else//找不到

return(NULL); } /*

6、单链表的插入，插入到指定位置

在以L为头结点的单链表的第i个位置插入值为e的结点。

插入运算是将值为e的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间。因此，必须首先找到ai-1所在的结点p，然后生成一个数据域为e的新结点q，q结点作为p的直接后继结点。

*/ Status Insert_LinkList(LNode *L,int i,ElemType e) { int j=0; LNode *p,*q; p=L;//找待插入位置的前一个结点位置

while((p!=NULL)&&(j

p=p->next;

j++; } if((j!=i-1)||(p==NULL))//位置不合适

{

printf("位置不合适，无法插入！\n");

return ERROR; } else {

q=(LNode *)malloc(sizeof(LNode));//给新结点分配空间

if(q==NULL)

return ERROR;

else

云淡风清 http://gsqls.blog.163.com/

{

//实现插入

q->data=e;

q->next=p->next;

p->next=q;

return OK;

} } } /*

7、按序号删除

删除单链表中的第i个结点。

为了删除第i个结点ai，必须找到结点的存储地址。该存储地址是在其直接前趋结点ai-1的next域中，因此，必须首先找到ai-1的存储位置p，然后令p->next指向ai的直接后继结点，即把ai从链上摘下。最后释放结点ai的空间，将其归还给"存储池"。设单链表长度为n，则删去第i个结点仅当1≤i≤n时是合法的。则当i=n+1时，虽然被删结点不存在，但其前趋结点却存在，是终端结点。故判断条件之一是p->next!=NULL。显然此算法的时间复杂度也是O(n)。

*/ Status Delete1_LinkList(LNode *L,int i) { int j=1; LNode *p,*q; p=L; q=L->next;//找待删除位置的前一个结点位置

while(q!=NULL && j

p=q;

q=q->next;

j++; } if((q==NULL)||(i

printf("位置不合适，无法删除！\n ");

return ERROR; } else {

//实现删除

p->next=q->next;

free(q);

return OK; } }

云淡风清 http://gsqls.blog.163.com/ /*

8、按值删除

删除单链表中值为key的第一个结点。

与按值查找相类似，首先要查找值为key的结点是否存在? 若存在，则删除；否则返回NULL。 */ Status Delete2_LinkList(LNode *L,int key) { LNode *p=L,*q=L->next; //找待删除结点位置，q指向其位置，p指向其前驱结点

while(q!=NULL && q->data!=key) {

p=q;

q=q->next; } if(q!=NULL)//找到了

{

//实现删除

p->next=q->next;

free(q);

return OK; } else {

printf("所要删除的结点不存在!!\n");

return ERROR; } } /*

9、删除单链表中值为key的所有结点

与按值查找相类似，但比前面的算法更简单。

基本思想：从单链表的第一个结点开始，对每个结点进行检查，若结点的值为key，则删除之，然后检查下一个结点，直到所有的结点都检查。

*/ void Delete3_LinkList(LNode *L,int key) { LNode *p=L,*q=L->next; //p始终指向q的前驱，以方便删除操作的实现

while(q!=NULL) {

if(q->data==key)

{

p->next=q->next;

云淡风清 http://gsqls.blog.163.com/

free(q);

q=p->next;

}

else

{

p=q;

q=q->next;

} } } /*

10、删除单链表中所有值重复的结点，使得所有结点的值都不相同 与按值查找相类似，但比前面的算法更复杂。

基本思想：从单链表的第一个结点开始，对每个结点进行检查：检查链表中该结点的所有后继结点，只要有值和该结点的值相同，则删除之；然后检查下一个结点，直到所有的结点都检查。

*/ void Delete4_LinkList(LNode *L) { LNode *p=L->next,*q,*ptr; while(p!=NULL)//检查链表中所有结点

{

q=p;

ptr=p->next;

while(ptr!=NULL)//检查结点p的所有后继结点ptr

{

if(ptr->data==p->data)

{

q->next=ptr->next;

free(ptr);

ptr=q->next;

}

else

{

q=ptr;

ptr=ptr->next;

}

}

p=p->next; } } /*

云淡风清 http://gsqls.blog.163.com/

11、修改指定位置的数据 */ Status Modify_LinkList(LNode *L,int i,ElemType e) { int j=1; LNode *p; p=L->next;//找待修改结点位置

while(p!=NULL && j

p=p->next;

j++; } if((p==NULL)||(i

{

printf("位置不合适，无法修改！\n ");

return ERROR; } else {

p->data=e;

return OK; } } /*

12、单链表遍历 以输出为例 */ void Traverse_LinkList(LNode *L) { LNode *p; p=L->next; while(p!=NULL) {

printf("%8d",p->data);

p=p->next; } printf("\n"); } /*

13、单链表的合并

设有两个有序的单链表，它们的头指针分别是La、Lb，将它们合并为以Lc为头指针的有序链表。 算法说明：算法中pa，pb分别是待考察的两个链表的当前结点，pc是合并过程中合并的链表的最后一个结点。

云淡风清 http://gsqls.blog.163.com/

合并了值为-7，-2的结点后示意图如下图所示。

*/ LNode *Merge_LinkList(LNode *La,LNode *Lb) { LNode *Lc,*pa,*pb,*pc,*ptr; Lc=La; pc=La;//指向新链表的末结点

pa=La->next; pb=Lb->next; while(pa!=NULL && pb!=NULL) {

if(pa->datadata)//将pa所指的结点合并，pa指向下一个结点

{

pc->next=pa;

pc=pa;

pa=pa->next;

}

else

if(pa->data>pb->data) //将pb所指的结点合并，pb指向下一个结点

{

pc->next=pb;

pc=pb;

pb=pb->next;

云淡风清 http://gsqls.blog.163.com/

}

else//将pa所指的结点合并，pb所指结点删除

{

pc->next=pa;

pc=pa;

pa=pa->next;

ptr=pb;

pb=pb->next;

free(ptr);

} } //将剩余的结点链上

if(pa!=NULL)

pc->next=pa; else

pc->next=pb;

free(Lb); return(Lc); } /*

14、单链表的排序

采用插入排序方法，以升序为例 */ void Sort_LinkList(LNode *L) { LNode *p,*q,*r,*s; p=L->next; L->next=NULL; while(p!=NULL) {

q=L->next;

r=L;

while((q!=NULL)&&(p->data>q->data))

{

q=q->next;

r=r->next;

}

s=p->next;

r->next=p;

p->next=q;

p=s; } }

云淡风清 http://gsqls.blog.163.com/ /*

15、单链表的释放 */ void Release_LinkList(LNode *L) { LNode *p,*q; p=L;//指向头结点，从此结点开始释放

while(p!=NULL) {

q=p->next;

free(p);

p=q; } } void main() { int xz=1,i; LNode *L,*L1,*L2; ElemType e; while(xz!=0) {

printf("

1、链表初始化\n

2、头插入法建表\n

3、尾插入法建表\n

4、按序号查找\n

5、按值查找\n

6、单链表的插入\n");

printf("

7、按序号删除\n

8、按值删除\n

9、删除单链表中指定值的所有结点\n

10、删除单链表中所有值重复的结点\n");

printf("

11、修改指定位置的数据\n

12、单链表遍历\n

13、单链表的合并\n

14、单链表的排序\n

15、单链表的释放\n 0、结束\n请选择：");

scanf("%d",&xz);

switch(xz)

{

case 1:

L=Init_LinkList();

if(L!=NULL)

printf("初始化成功！\n");

break;

case 2:

if(Create1_LinkList(L)==OK)

printf("建立成功！\n");

else

printf("建立不成功！\n");

break;

case 3:

if(Create2_LinkList(L)==OK)

printf("建立成功！\n");

云淡风清 http://gsqls.blog.163.com/

else

printf("建立不成功！\n"); break; case 4: printf("请输入要查找元素的序号："); scanf("%d",&i); if(Get_LinkList(L,i,&e)==OK)

printf("%d\n",e); else

printf("找不到！\n"); break; case 5: printf("请输入要查找元素的关键字："); scanf("%d",&e); L1=Locate_LinkList(L,e); if(L1!=NULL)

printf("%d\n",L1->data); else

printf("找不到！\n"); break; case 6: printf("请输入要插入元素的内容："); scanf("%d",&e); printf("请输入插入位置："); scanf("%d",&i); if(Insert_LinkList(L,i,e)==OK)

printf("插入成功！\n"); else

printf("插入不成功！\n"); break; case 7: printf("请输入要删除元素的位置："); scanf("%d",&i); if(Delete1_LinkList(L,i)==OK)

printf("成功删除！\n"); else

printf("未成功删除！\n"); break; case 8: printf("请输入要元素的内容："); scanf("%d",&e); if(Delete2_LinkList(L,e)==OK)

printf("成功删除！\n"); else

云淡风清 http://gsqls.blog.163.com/

printf("未成功删除！\n"); break; case 9: printf("请输入要元素的内容："); scanf("%d",&e); Delete3_LinkList(L,e); printf("成功删除！\n"); break; case 10: Delete4_LinkList(L); printf("成功删除！\n");

break; case 11: printf("请输入修改位置："); scanf("%d",&i); printf("请输入元素的新内容："); scanf("%d",&e); if(Modify_LinkList(L,i,e)==OK)

printf("修改成功！\n"); else

printf("修改不成功！\n"); break; case 12: Traverse_LinkList(L);

break; case 13: L1=Init_LinkList(); L2=Init_LinkList(); if((L1==NULL)||(L2==NULL))

printf("初始化不成功！\n"); else {

printf("请建立第一个链表：\n");

Create2_LinkList(L1);

printf("请建立第二个链表：\n");

Create2_LinkList(L2);

Sort_LinkList(L1);

Sort_LinkList(L2);

L=Merge_LinkList(L1,L2);

printf("合并后的结果如下：\n");

Traverse_LinkList(L); } break; case 14:

云淡风清 http://gsqls.blog.163.com/

}

} Sort_LinkList(L); break; case 15: Release_LinkList(L);

break; case 0: printf("谢谢使用，再见！\n"); break; default: printf("输入错误！\n"); break; } 2.4循环链表

循环链表(Circular Linked List)：是一种头尾相接的链表，其特点是最后一个结点的指针域指向链表的头结点，整个链表的指针域链接成一个环，这样，从循环链表的任意一个结点出发都可以找到链表中的其它结点，使得表处理更加方便灵活。

下图是带头结点的单循环链表的示意图。

循环链表的操作：

对于带头结点的单循环链表，除链表的合并外，其它操作和单线性链表基本上一致，仅仅需要在单线性链表操作算法基础上做以下简单修改：

1、判断是否是空链表 head->next==head;

2、判断是否是表尾结点 p->next==head; 例：有m个人围成一圈，顺序排号。从第一个人开始报数，凡报到3的人退出圈子，问最后留下的那位是原来的第几号？

根据问题描述可知，该问题中m个人围坐在一起形成首尾相接的环，比较自然的一种思路是用循环链表模拟这个环。从第3个人开始出圈，相当于从链表中删除一个结点。该程序主要由三个模块组成：

1、建立循环单链表存放初始各人编号；

2、报数并按顺序输出出圈人的编号；

3、输出剩下的人的编号。具体步骤如下：

云淡风清 http://gsqls.blog.163.com/ 第一步：输入人员总数；

第二步：创建循环链表并向单链表中填入人员编号； 第三步：找第一个开始报数的人；

第四步：数到3让此人出圈(删除对应结点)；

第五步：接着开始报数，重复第四步，直到圈中剩余一个为止； 第六步：输出剩下结点中的编号，即为最终所要求的编号。 程序源代码： #include "stdio.h" #include "stdlib.h" #define MAXN 100 //最大个数 struct Node { int data; struct Node *next; }; void main() { struct Node *head, *s, *q, *t; int n, m, count=0, i; do//输入总个数

{ printf("请输入总个数(1－%d)：",MAXN); scanf("%d",&m); }while((mMAXN)); do//输入出圈时要数到的个数

{ printf("要数到的个数(1--%d)：",m); scanf("%d",&n); }while((nm)); for(i=0;i

{ s=(struct Node *)malloc(sizeof(struct Node)); s->data=i+1; s->next=NULL; if(i==0) { head=s; q=head; } else

{ q->next=s; q=q->next; }

云淡风清 http://gsqls.blog.163.com/ } q->next=head;//形成圈

//以下代码输出原始状态

printf("原始状态：\n"); q=head; while(q->next!=head) { printf("%4d",q->data); q=q->next; } printf("%4d\n",q->data); q=head;//以下代码实现出圈

printf("出圈顺序：\n"); do { count++; if(count==n-1) { t=q->next; q->next=t->next; count=0; printf("%4d",t->data); free(t); } q=q->next; }while(q->next!=q); printf("\n剩下的是%4d\n",q->data); } 注意：此程序采用的是不带头结点的单链表，以免在循环链表中由于不存放有效数据的头结点的存在而影响计数。

2.5双向链表

双向链表是为了克服单链表的单向性的缺陷而引入的。单链表只能从头到尾单向访问各结点，对操作的限制极大。双向链表(Double Linked List)指构成链表的每个结点中设立两个指针域，一个指向其直接前趋结点，一个指向其直接后继结点，这样形成的链表中有两个方向不同的链，故称为双向链表。

和单链表类似，双向链表一般也增加一个不存放实际有效数据的头结点，从而使某些操作更方便。下面为带头结点的双向链表示意图：

云淡风清 http://gsqls.blog.163.com/ 将头结点和尾结点链接起来也能构成循环链表，并称之为双向循环链表。

2.5.1双向链表的结点及其类型定义

双向链表的结点的类型定义如下。 typedef struct Dulnode { ElemType data; struct Dulnode *prior,*next; }DulNode; 双向链表结构具有对称性，设p指向双向链表中的某一结点，则其对称性可用下式描述： (p->prior)->next=p=(p->next)->prior ; 结点p的存储位置存放在其直接前趋结点p->prior的直接后继指针域中，同时也存放在其直接后继结点p->next的直接前趋指针域中。

2.5.2双向链表的基本操作

1、双向链表结点的插入

将值为e的结点插入双向链表中。插入前后链表的变化如下图所示。

①若插入时仅仅指出直接前驱结点，钩链时必须注意先后次序是：“先右后左”，部分语句组如下： S=(DulNode *)malloc(sizeof(DulNode)); S->data=e; S->next=p->next;//先右 p->next->prior=S; //后左 p->next=S; //先右 S->prior=p; //后左

②若插入时同时指出直接前驱结点p和直接后继结点q，钩链时无须注意先后次序，部分语句组如下：

S=(DulNode *)malloc(sizeof(DulNode)); S->data=e; p->next=S; S->next=q; S->prior=p; q->prior=S;

2、双向链表结点的删除

设要删除的结点为p ，删除时可以不引入新的辅助指针变量，先直接断链，再释放结点。部分语句组如下：

p->prior->next=p->next; p->next->prior=p->prior; free(p);

云淡风清 http://gsqls.blog.163.com/ 注意：

与单链表的插入和删除操作不同的是，在双向链表中插入和删除必须同时修改两个方向上的指针域的指向。

2.6一元多项式的表示和相加 2.6.1一元多项式的表示

一元多项式如下：

p(x)=p0+p1x+p2x2+ „ +pnxn ，由n+1个系数唯一确定。则在计算机中可用线性表(p0 ，p1 ，p2 ，„ ，pn)表示。既然是线性表，就可以用顺序表和链表来实现。两种不同实现方式的元素类型定义如下：

1、顺序存储结构表示的类型 typedef struct { float

coef;

//系数部分

int

expn; //指数部分 } ElemType;

2、链式存储结构表示的类型 typedef struct ploy { float coef;

//系数部分

int

expn;

//指数部分

struct ploy *next; }Ploy; 2.6.2一元多项式的相加

不失一般性，设有两个一元多项式： P(x)=p0+p1x+p2x2+ „ +pnxn ，

Q(x)=q0+q1x+q2x2+ … +qmxm

(m

1、顺序存储表示的相加 线性表的定义： typedef struct { ElemType a[MAX_SIZE]; int

length; }Sqlist; 用顺序表示的相加非常简单，访问第i项可直接访问：L.a[i-1].coef，L.a[i-1].expn

2、链式存储表示的相加

当采用链式存储表示时，根据结点类型定义，凡是系数为0的项不在链表中出现，从而可以大大减少链表的长度。

云淡风清 http://gsqls.blog.163.com/ 一元多项式相加的实质是： 指数不同：是链表的合并。

指数相同：系数相加，和为0，去掉结点，和不为0，修改结点的系数域。 算法一：

就在原来两个多项式链表的基础上进行相加，相加后原来两个多项式链表不再存在，当然就不再允许对原来两个多项式进行其它操作了。

算法描述：

Ploy *add_ploy(ploy *La,ploy *Lb) //将以La ，Lb为头指针表示的一元多项式相加 { ploy *Lc,*pc,*pa,*pb,*ptr; float x; Lc=pc=La; pa=La->next; pb=Lb->next; while (pa!=NULL&&pb!=NULL) {

if(pa->expnexpn)//将pa所指的结点合并，pa指向下一个结点

{

pc->next=pa;

pc=pa;

pa=pa->next;

}

else

if(pa->expn>pb->expn)//将pb所指的结点合并，pb指向下一个结点

{

pc->next=pb;

pc=pb;

pb=pb->next;

}

else

{

x=pa->coef+pb->coef;

if(abs(x)

{

ptr=pa;

pa=pa->next;

free(ptr);

ptr=pb;

pb=pb->next;

free(ptr);

}

else//如果系数和不为0，修改其中一个结点的系数域，删除另一个结点

{

云淡风清 http://gsqls.blog.163.com/

pc->next=pa;

pa->coef=x;

pc=pa;

pa=pa->next;

ptr=pb;

pb=pb->next;free(pb);

}

} }//end of while if(pa==NULL)

pc->next=pb; else pc->next=pa; return (Lc); } 算法之二：

对两个多项式链表进行相加，生成一个新的相加后的结果多项式链表，原来两个多项式链表依然存在，不发生任何改变，如果要再对原来两个多项式进行其它操作也不影响。

算法描述：

Ploy *add_ploy(ploy *La,ploy *Lb) //将以La ，Lb为头指针表示的一元多项式相加，生成一个新的结果多项式 { ploy *Lc,*pc,*pa,*pb,*p; float x; Lc=pc=(ploy *)malloc(sizeof(ploy)); pa=La->next; pb=Lb->next; while (pa!=NULL&&pb!=NULL) {

if(pa->expnexpn)

{

p=(ploy *)malloc(sizeof(ploy));//生成一个新的结果结点并赋值

p->coef=pa->coef;

p->expn=pa->expn;

p->next=NULL;//生成的结点插入到结果链表的最后，pa指向下一个结点

pc->next=p;

pc=p;

pa=pa->next;

}

else

if(pa->expn>pb->expn)

{

p=(ploy *)malloc(sizeof(ploy));//生成一个新的结果结点并赋值

p->coef=pb->coef;p->expn=pb->expn;

p->next=NULL;

云淡风清 http://gsqls.blog.163.com/

pc->next=p;//生成的结点插入到结果链表的最后，pb指向下一个结点

pc=p;

pb=pb->next;

}

else

{

x=pa->coef+pb->coef;

if(abs(x)

{

pa=pa->next;

pb=pb->next;

}

else//若系数和不为0，生成的结点插入到结果链表的最后，pa, pb分别指向直接后继结点

{

p=(ploy *)malloc(sizeof(ploy));//生成一个新的结果结点并赋值

p->coef=x;p->expn=pb->expn;

p->next=NULL;

pc->next=p;

pc=p;

pa=pa->next;

pb=pb->next;

}

} }//end of while if(pb!=NULL)

while(pb!=NULL)

{

p=(ploy *)malloc(sizeof(ploy));//生成一个新的结果结点并赋值

p->coef=pb->coef;

p->expn=pb->expn;

p->next=NULL;

pc->next=p;

pc=p;

pb=pb->next;

} if(pa!=NULL)

while(pa!=NULL)

{

p=(ploy *)malloc(sizeof(ploy));//生成一个新的结果结点并赋值

p->coef=pb->coef;

p->expn=pa->expn;

p->next=NULL;

pc->next=p;

云淡风清 http://gsqls.blog.163.com/

}

pc=p;

pa=pa->next; } return (Lc);习题 二

1、简述下列术语：线性表，顺序表，链表。

2、何时选用顺序表，何时选用链表作为线性表的存储结构合适？各自的主要优缺点是什么？

3、在顺序表中插入和删除一个结点平均需要移动多少个结点？具体的移动次数取决于哪些因素？

4、链表所表示的元素是否有序？如有序，则有序性体现于何处？链表所表示的元素是否一定要在物理上是相邻的？有序表的有序性又如何理解？

5、设顺序表L是递增有序表，试写一算法，将x插入到L中并使L仍是递增有序表。

6、写一算法从一给定的向量A删除值在x到y(x≤y)之间的所有元素(注意：x和y是给定的参数，可以和表中的元素相同，也可以不同)。

7、设A和B是两个按元素值递增有序的单链表，写一算法将A和B归并为按按元素值递减有序的单链表C，试分析算法的时间复杂度。

第17篇：数据结构实验教学

数据结构实验指导

说明：课内上机要求完成实验一到实验四的内容，并完成实验报告，实验报告在十七周星期三之前交，其他实验请大家课外抽时间完成。给出的示例程序供大家参考，大家实验的时候要自己动手编写程序，切不可完全照抄，每个实验具体的实验题目大家可以做示例的题目，也可以自己定一题目，只需用到该实验的知识点即可，编程语言大家可以选用自己熟悉的语言。

一．实验要求： 书写类C语言的算法，并将算法转变为程序实现。正确理解各种数据结构的逻辑特性和存储表示和基本操作的算法实现。针对问题的不同选择合适的数据结构，提高算法设计的能力和动手实验的技能。。 二．主要仪器设备：（所开实验的主要仪器设备）

硬件要求：在多媒体教室讲解及演示。为保证教学顺利进行，要求实验室提供PⅢ及以上的微机。

三、实验项目内容简介

为了达到实验目的，本课程安排了四个实习单元，训练的重点在于基本的数据结构，而不是强调面面俱到。各实习单元与教科书的各章只具有粗略的对应关系，一个实习题常常涉及到几部分教学内容。

1、线性表基本操作

（1) 熟悉线性表的基本运算在两种存储结构（顺序结构和链式结构）上的实现 （2)以线性表的各种操作（建立、插入、删除等）的实现为重点

（3) 通过本次实习帮助学生加深对高级语言C语言的使用（特别是函数参数、指针类型、链表的使用）。

2、栈、队列以及递归算法的设计

（1)掌握栈和队列这两种特殊的线性表，熟悉它们的特性，在实际问题背景下灵活运用它们 （2) 训练的要点是“栈”的观点及其典型用法；问题求解的状态表示及其递归算法；由递归程序到非递归程序的转化方法

3、树、图及其应用

（1) 树和图是两种非线性数据结构，广义表的实质是树结构，而稀疏矩阵的十字链表存储结构也是图的一种存储结构，故本单元是本课的实习重点。

（2) 要求学生熟悉各种存储结构的特性，以及如何应用树和图结构求解具体问题。 （3) 训练的要点是：递归算法的设计方法；表达式的求值技术；哈夫曼方法及其编译码技术；完整的应用系统的用户界面设计和操作定义方法；矩阵乘法的特殊操作顺序；路径遍历（树、图的遍历）技术。

4、查找和排序

本次实习旨在集中对几个专门的问题做较为深入的探讨和理解

重点在掌握各种内部排序算法、查找算法的思想和实现。学生在实习中体会查找和内部排序算法思想，理解开发高效算法的可能性和寻找、构造高效算法的方法。

四、主要参考书

1、《数据结构题集》（C语言版）实习题部分，清华大学出版社,1999.11

2、《数据结构习题与解析》（C语言篇），李春葆 编著，清华大学出版社，2000.1

3、宁正元《数据结构习题解析与上机实验指导》

水利水电出版社（2003年）

实验一

线性表的操作

一、实验目的

1．熟悉C语言的上机环境，掌握C语言的基本结构。 2．会定义线性表的顺序存储结构。（链式存储结构） 3．熟悉对顺序表（单链表）的一些基本操作。

二、实验要求

1．认真阅读和掌握本实验内容所给的全部程序。 2．保存和打印出程序运行结果，并结合程序进行分析。 注意事项

在做第一次“数据结构”课程实验之前，要在硬盘上建立好自己的工作目录，专门来存储你所做的实验程序及相关信息，以后每次做实验都采用这个目录。

三、实验内容

1、示例（以顺序表为示例，同学们也可以编程实现单链表的创建、查找、插入、删除等功能）

以输入整形数据为主，输入后按“？”结束输入。

程序所能表达到的功能为：实现顺序表的创建、查找、插入、删除等功能。 程序运行后，输入数据并执行。 #include \"stdio.h\" #include \"conio.h\" #define MaxSize 50 typedef char elemtype; typedef struct node { elemtype data[MaxSize]; int len; }lnode,*List; void init(List L){ L->len=0;} int length(List L) { return L->len;} elemtype getnode(List L,int pos) { if(posL->len) printf(\"error\"); else return L->data[pos-1]; } int locate(List L,elemtype x) { int i=0; while(ilen && L->data[i]!=x) i++; if(i==L->len) return -1; else return(i+1); } void insert(List L,int pos,elemtype x) { int j; if(posL->len+1) printf(\"insert error\\n\"); else { L->len++; for(j=L->len;j>=pos;j--) L->data[j]=L->data[j-1]; L->data[pos-1]=x; }; } void delnode(List L,int pos) { int j; if(posL->len)printf(\"del error\\n\"); else { for(j=pos;jlen;j++) L->data[j-1]=L->data[j]; L->len--;} } void print(List L) { int i; for(i=1;ilen;i++) printf(\"%c->\",L->data[i-1]); printf(\"%c\",L->data[L->len-1]); } main() { int i=1,n; lnode L; char ch,x; init(&L); printf(\"\\n\\n\\n*******************************顺序表演示程序***********\\n\"); printf(\"请输入你想建立的顺序表的元素，以？结束:\"); ch=getchar(); while(ch!=\'?\') {insert(&L,i,ch); i++; ch=getchar(); }; printf(\"你建立的顺序表为:\"); print(&L); printf(\"\\n顺序表的长度为:%d\",L.len); printf(\"\\n输入你想查找的元素：\"); fflush(stdin); scanf(\"%c\",&x); printf(\"你查找的元素为%c序位为%d\",x,locate(&L,x)); printf(\"\\n输入你想查找的元素序位:\"); scanf(\"%d\",&n); printf(\"\\n你查找的元素为：%c\",getnode(&L,n)); printf(\"\\n输入你想插入的元素以及序位:\"); fflush(stdin); scanf(\"%c,%d\",&x,&n); insert(&L,n,x); printf(\"\\n插入后顺序表为：\"); print(&L); fflush(stdin); printf(\"\\n请输入你想删除的元素序位：\"); scanf(\"%d\",&n); delnode(&L,n); printf(\"\\n删除后的顺序表为：\"); print(&L); getch(); }

四、测试结果

运行程序，屏幕显示：“请输入你想建立的顺序表的元素，以？结束:” 输入：54381 你建立的顺序表为:5—>4—>3—>8—>1 顺序表的长度为:5 输入你想查找的元素：4 你查找的元素为4序位为2 输入你想查找的元素序位:4 你查找的元素为：8

输入你想插入的元素以及序位:\"：6，3 插入后顺序表为：5—>4—>6—>3—>8—>1 请输入你想删除的元素序位：5 删除后的顺序表为：5—>4—>6—>3—>1

实验二 二叉树的操作 一．实验目的

理解并熟悉掌握创建二叉树和实现二叉树的三种遍历 二．实验内容

创建二叉树和实现二叉树的三种遍历

根据提示输入字符型数据创建二叉树，输入值为所有字符型数据 输出为遍历后的每个结点的值的顺序

创建二叉树并能实现二叉树的先序、中序、后序遍历 如果输入数据为：a b c 输出结果为：a b c

b a c

b c a

程序流程：main()clrscr()createtree()preorder()inorder()postorder 源程序

#include \"stdlib.h\" struct tnode {char data; struct tnode*lchild; struct tnode*rchild; }; struct tnode tree;

void createtree(struct tnode*t) {struct tnode*p=t;

char check; if(p->lchild==NULL||p->rchild==NULL) /*判断左右子树是否为空*/

{printf(\"please enter the data:\");

scanf(\"%c\",&(p->data));

getchar();

}

/*输入根结点数据*/

/*创建函数*/

/*定义二叉树指针*/

/*引入头文件*/ /*定义二叉树存储结构*/

/*把二叉树指针给p*/ if(p->lchild==NULL)

{printf(\"%c leftchild is null.Add? y/n\\n\",p->data); /*左子树空，询问是否创建*/

scanf(\"%c\",&check);

getchar();

if(check==\'y\')

{struct tnode*q=(struct tnode*)malloc(sizeof(struct tnode)); /*开辟空间*/

q->lchild=NULL;

q->rchild=NULL;

p->lchild=q;

createtree(q);

}

} if(p->rchild==NULL)

{printf(\"%c rightchild is NULL.Add? y/n\\n\",p->data); /*右子树空，询问是否创建*/

scanf(\"%c\",&check);

getchar();

if(check==\'y\')

{struct tnode*q=(struct tnode*)malloc(sizeof(struct tnode)); /*开辟空间*/

q->lchild=NULL;

q->rchild=NULL;

p->rchild=q;

createtree(q);

}

} }

void preorder(struct tnode*t) {if(t)

{printf(\"%c \",t->data);

/*输出根结点数据*/

/*先序遍历函数*/

/*连到二叉树上*/

preorder(t->lchild);

preorder(t->rchild);

} }

void inorder(struct tnode*t) {if(t)

{inorder(t->lchild);

printf(\"%c \",t->data);

inorder(t->rchild);

} } void postorder(struct tnode*t) /*后序遍历函数*/ {if(t)

{

postorder(t->lchild);

postorder(t->rchild);

printf(\"%c \",t->data);

} }

void main() { clrscr();

/*清屏函数*/

/*左子树*/ /*右子树*/ /*创建二叉树*/

/*中序遍历函数*/ tree.lchild=NULL; tree.rchild=NULL; createtree(&tree);

preorder(&tree);

printf(\"\\n\"); inorder(&tree);

/*先序遍历*/

/*中序遍历*/ printf(\"\\n\"); postorder(&tree); }

三．使用说明

程序运行：

先输入根结点数据，例如：a 输入y或n判断是否创建左子树。输入y然后输入左子树数据 输入y或n判断是否创建右子树。输入y然后输入右子树数据 按回车可查看遍历结果并退出程序。

四．测试结果

运行程序，屏幕提示：

please enter the data:a

/*首先输入根结点，为a*/ a leftchild is null.add?y/n

/*询问是否输入a结点的左结点*/ y

/*输入*/ please enter the data:b

/*输入结点a的左结点，为b*/ b leftchild is null.add?y/n

/*询问是否输入b结点的左结点*/ n

/*不输入*/ b rightchild is null.add?y/n

/*询问是否输入b结点的右结点*/ n

/*不输入*/ a rightchild is null.add?y/n

/*询问是否输入a结点的右结点*/ y

/*输入*/ please enter the data:c

/*输入结点a的右结点，为c*/ c leftchild is null.add?y/n

/*询问是否输入c结点的左结点*/ n

/*不输入*/ c rightchild is null.add?y/n

/*询问是否输入c结点的右结点*/ n

/*不输入*/ 程序退出，显示结果应为：

a b c

/*先序*/

/*后序遍历*/

b a c

/*中序*/

b c a

/*后序*/

实验三

图的遍历操作

一．实验目的：

该实验主要完成对图的创建，并实现图的深度优先遍历和广度优先遍历 二．实验内容：

所输入的数据要为整形数据

输出的形式为：每按一次回车，遍历一个结点

能创建最大结点树为30的任意图，实现对无向图的两种遍历 程序流程：

main()clrscr()visited()DFS()visited()BFS() 源程序： #include #define maxvex 30 struct edgenode {int adjvex; char info; struct edgenode*next; }; struct vexnode {char data; struct edgenode*link; }; typedef struct vexnode adjlist[maxvex]; /*自定义adjlist为结构体数组类型*/ adjlist tu1;

void creategraph(adjlist g,int n) {int e,i,s,d;

/*图创建函数*/

/*定义存储边、点的变量*/ /*定义边的结构体指针*/ /*显示提示输入点，边*/

/*定义结构体数组变量tu1*/

/*定义点的结构体*/

/*引用两个头文件*/ /*定义MAXVEX=30*/

/*定义边的结构体*/ struct edgenode*p,*q;

printf(\"the point(n) and edge(e):\"); scanf(\"%d,%d\",&n,&e); for(i=1;i

{getchar();

/*接收点、边存入n,e中*/

/*提示输入结点信息*/ /*存储信息*/ /*最后指针为空*/

printf(\"\\tthe %d information:\",i);

scanf(\"%c\",&g[i].data);

g[i].link=NULL;

}

for(i=1;i

{printf(\"\\nthe%d edges=>\\n\\t :\",i);

scanf(\"%d,%d\",&s,&d);

/*提示输入边信息*/ /*接收边的信息*/

p=(struct edgenode*)malloc(sizeof(struct edgenode));

q=(struct edgenode*)malloc(sizeof(struct edgenode)); /*开辟两个存储边的空间*/

p->adjvex=d;

p->info=g[d].data;

q->adjvex=s;

q->info=g[s].data;

p->next=g[s].link;

g[s].link=p;

q->next=g[d].link;

g[d].link=q;

} }

int visited[maxvex];

/*定义访问数组*/

/*q和s的link指针连接起来*/ /*完成一个边的创建*/

/*p和s的link指针连接起来*/

/*把另一个点存储下来*/

/*把其中一个点存储下来*/ void dfs(adjlist adj,int v) {int i; struct edgenode*p; visited[v]=1;

/*深度优先遍历函数*/

/*定义边指针*/

/*把开始遍历的点在访问数组中标识*/

/*输出正访问的点*/ printf(\"now is at point %d\",v);

p=adj[v].link; printf(\"the data is %c \\n\",adj[v].data); getch(); while(p)

{if(visited[p->adjvex]==0)

dfs(adj,p->adjvex);

p=p->next;

} }

int quene[maxvex]; void bfs(adjlist adj,int vi) {int m=maxvex;

/*输出点的信息*/

/*没有访问的再调用DFS函数*/

/*访问过的判断下一个*/

/*广度优先遍历函数*/ /*定义一个队列*/ int front=0,rear=1,v; struct edgenode*p; visited[vi]=1;

/*定义边指针*/

/*开始访问的点标识一下*/

/*输出正访问的点*/ printf(\"now visit the point:%d\\n\",vi);

getch();quene[rear]=vi; while(front!=rear)

{front=(front+1)%m;

v=quene[front];

p=adj[v].link;

while(p)

{if(visited[p->adjvex]==0)

{visited[p->adjvex]=1;

/*把访问过的点放入数组中*/

/*判断p->adjvex点是否访问过*/ /*访问没有访问过的结点*/ printf(\"now visit the point:%d\\n\",p->adjvex); /*输出正访问的结点*/ getch();

rear=(rear+1)%m;

quene[rear]=p->adjvex;

}

p=p->next;

/*指向下一个*/

/*放入数组中*/

}

} }

void main() {int i;clrscr(); creategraph(tu1,0); for(i=1;i

visited[i]=0;

dfs(tu1,1);

getch();

/*访问数组初始化*/

/*调用DFS*/

/*创建图*/

/*等待输入*/

for(i=1;i

visited[i]=0; bfs(tu1,1);

} 三．使用说明：

根据屏幕上的英文提示先输入结点的个数和边数。然后输入各结点存储的信息，再输入定义的边，形成图。最后分别按照DFS深度优先遍历和BFS广度优先遍历实现对图的遍历。 四．测试结果： 运行程序，屏幕提示：

the point(n) and edge(e):4,3 /*输入顶点和边的数目*/ the 1 information:a

/*各个顶点的信息*/ the 2 information:b the 3 information:c the 4 information:d the 1 edges=>

/*各个边的连接情况*/ :1,2 the 2 edges=>:1,3 the 3 edges=>

/*调用BFS*/ :3,4

now is at point 1 the data is a /*深度优先遍历结果*/

now is at point 3 the data is c now is at point 4 the data is d now is at point 2 the data is b now visit the point:1

/*广度优先遍历结果*/ now visit the point:3 now visit the point:2 now visit the point:4

a b c d 实验四

栈的基本操作

一、实验目的：

1．熟练掌握栈的结构，以及这种数据结构的特点；

2． 能够在两种存储结构上实现栈的基本运算，特别注意栈满和栈空的判断条件及描述方法；

二、实验内容： 计算表达式的值 【问题描述】

计算用运算符后缀法表示的表达式的值。后缀表达式也称逆波兰表达式，比中缀表达式计算起来更方便简单些，中缀表达式要计算就存在着括号的匹配问题，所以在计算表达式值时一般都是先转换成后缀表达式，再用后缀法计算表达式的值。如：表达式(a+b*c)/d-e用后缀法表示应为abc*+d/e-。只考虑四则算术运算，且假设输入的操作数均为1位十进制数（0—9），并且输入的后缀形式表达式不含语法错误。 【数据描述】 #define add 43 /*运算符加号„+‟的ASCII码*/ #define subs 45 /*运算符减号„-‟的ASCII码*/ #define mult 42 #define div 47 /*运算符乘号„*‟的ASCII码*/ /*运算符除号„/‟的ASCII码*/ #define MAXSIZE 100 typedef struct{ { int stkdata[MAXSIZE];//用数组来表示栈空间，定义长度为MAXSIZE的栈

int top;

}STKzone; typedef STKzone *STK; typedef enum{true=1,false=0} bool; typedef enum{ok,error} status;

【C源程序】 #include #define add 43

/*运算符加号„+‟的ASCII码*/ //栈顶指针 #define subs 45

/*运算符减号„-‟的ASCII码*/ #define mult 42

/*运算符乘号„*‟的ASCII码*/ #define div 47

/*运算符除号„/‟的ASCII码*/ #define MAXSIZE 100 typedef struct { int stkdata[MAXSIZE];/*用数组来表示栈空间，定义长度为MAXSIZE的堆栈*/

int top; /*栈顶*/ }STKzone; typedef STKzone *STK; typedef enum{true=1,false=0} bool; typedef enum{ok,error} status; STKzone expSTKzone; STK expSTK; STK initSTK(STKzone *stack_zone){

/*执行栈初始化，建栈指针*/

STK p;

p=stack_zone;

p->top=0; } status push(int *term,STK pstk){ /*将一结构型数据送入栈中*/ if(pstk->top==MAXSIZE)

return error; /*栈满，进栈失败*/ pstk->stkdata[pstk->top] =*term; (pstk->top)++;/*栈顶指针移动*/ return ok; }/*push*/ bool emptySTK(STK pstk){ /*判断栈是否为空栈*/ return(pstk->top==0); } status pop(int *pdata, STK pstk){

/*从栈中取出一结构型数据*/ if(emptySTK(pstk))

return error; (pstk->top)--;/*退栈*/ *pdata =pstk->stkdata[pstk->top]; return ok; } void synerror() { printf(\"\\n表达式语法错！\"); exit(); } int eval(char tag,int a1,int a2) { switch(tag)

{ case add:return(a1+a2); case subs:return(a1-a2); case mult:return(a1*a2); case div:return(a1/a2); } } main() { char c;

int opd1,opd2,temp,c1;

expSTK=initSTK(&expSTKzone);

printf(\"\\n后置表达式: \");

while((c=getchar())!=\'\\n\')

{ if(c== \' \') continue; if((c>47)&&(c

{ putchar(c);

/*判断是否是0—9的字符*/ c1=c-48;

/*把输入的字符型数字转换成数字*/

if(push(&c1,expSTK)==error)/*运算分量进栈*/

{ printf(\"\\n表达式太长\\n\");

exit();} } else if((c==add)||(c==subs)||(c==mult)||(c==div))

{ putchar(c); if(pop(&opd1,expSTK)==error) /*将运算量1出栈*/ synerror();

if(pop(&opd2,expSTK)==error) /*将运算量2出栈*/ synerror();

}

else synerror();/*出现非法字符*/ }/*while*/ if(pop(&opd1,expSTK)==error) synerror(); if(!(emptySTK(expSTK))) synerror(); printf(“=%-3d\\n”,opd1); }/*main_end*/ 【测试数据】 输入: 23+↙

输出: =5

(即求2+3的结果) 输入: 145*+3/3-↙

输出: 4 (即求(1+4*5)/3-3的结果) 【说明】

本算法中对后置法表示的表达式求值按如下规则进行：自左向右扫描，每遇到一个`n+1元组（opd1,opd2,…,opdn,opr）(其中opd为操作数，opr为n元运算符)，就计算一次opr（opd1,opd2,…,opdn）的值，其结果取代原来表达式中n+1元组的位置，再从表达式开头重复上述过程，直到表达式中不含运算符为止。 temp=eval(c,opd2,opd1);/*计算得到结果*/ push(&temp,expSTK);/*将运算结果进栈*/ 【实验题】

1.假设一个算术表达式中包含零对到多对圆括弧，括弧对之间允许嵌套但不允许交叉，编写一个算法并上机实现：判断输入的表达式是否正确配对。Status correct(string expre)；//括弧配对正确，返回ok，否则返回error 2.3. 用栈实现一般表达式（即中缀表达式）到后缀表达式的转换。 数制转换。

实验五 数据查找

一．实验目的：

理解各种查找的思想，实现对数据的查找。例如用：直接查找法和折半查找法。 二．实验内容：

任意输入10个整形数据，然后再输入一个数据进行查找。 该程序能对输入的数据进行查找，然后把数据所在的位置输出。 例如：输入10个数据：12 3 4 5 6 7 8 9 1 2

输入查找数据：5 输出为：the 5 is at 4 position 源程序：

#include #include void seqsearch(int*,int); void binsearch(int*,int); void bubblesort(int*,int);

void menu() { printf(\" 1.seqsearch()\\n\"); printf(\" 2.binsearch()\\n\"); printf(\" 3.exit()\\n\"); printf(\"please select the method:\"); }

void main() {int i,j=1; int ch; int a[10];

/*声明插入查找函数*/ /*声明折半查找函数*/

/*声明起泡排序函数*/

/*引入头文件*/ clrscr(); printf(\"please input 10 data:\"); for(i=0;i

scanf(\"%d\",&(a[i]));

menu(); while(j)

/*接收输入*/

/*提示输入10个数据*/

/*显示菜单*/ /*循环一次*/ {scanf(\"%d\",&ch);

switch(ch)

{case 1:seqsearch(a,10);break;

case 2:binsearch(a,10);break;

case 3:j=0;break;

default:break;

}

printf(\"\\n\");

menu();

} }

void seqsearch(int*r,int n)

{int i=0,data; printf(\"please input find data:\");

scanf(\"%d\",&data);

while(r[i]!=data)

i++; if(i>n)

printf(\"the data is not found\");

else printf(\"the %d position is %d\",data,i+1); getch(); }

/*选择执行程序*/

/*直接查找函数*/

/*提示输入查找数据*/ /*接收数据*/

/*循环查找*/

/*输出数据没有找到*/

/*如果找到，输出位置*/

void binsearch(int *r,int n)

{int j,data,low=0,high=n,mid,find=0; bubblesort(r,n);

for(j=0;j

printf(\"%d \",r[j]);

printf(\"please input find data:\");

scanf(\"%d\",&data); while(low

{mid=(low+high)/2;

if(data

high=mid-1;

else if(data>r[mid])

low=mid+1; else find=1;

} if(!find)

printf(\"the data is not found!\\n\");

else printf(\"the data position is %d\",mid+1); getch(); }

void bubblesort(int *r,int n)

{int i,j,k,temp; k=n-1; for(j=0;j

{for(i=0;i

{if(r[i]>r[i+1])

{temp=r[i];

r[i]=r[i+1];

r[i+1]=temp;

/*折半查找函数*/

/*起泡法排序*/

/*排序后输出*/

/*提示输入查找数据*/

/*循环查找*/

/*置mid指针*/

/*判断数据大小，移动指针*/

/*显示数据没有找到*/

/*输出数据位置*/

/*起泡排序函数*/

/*比较大小*/

/*交换数据的位置*/

}

}

k=k-1;

} }

三．使用说明：

按提示输入10个任意的整形数据；输入要查找的数据；

可以看到所要查找的数据的位置。

四．测试结果： 运行程序，屏幕提示

please input 10 data:12 3 4 5 6 seqsearch()

binsearch()

exit please select the method:1

please input find data:5

the 5 is at 4 position

please select the method:2 please input find data:5 the 5 is at 4 position

7 8 9

2 /*输入10个数据*/ /*顺序查找*/ /*折半查找*/

/*选择顺序查找*/

/*输入要查找的数据*/

/*输出正确结果，并返回提示*/

实验六 哈希表设计

一．实验目的：

熟练掌握哈希表的构造方法，深刻理解哈希表与其他结构表的实质性差别。 二．实验内容：

程序的功能是对一批关键字集合采用除留余数法和线性探测再散列的方法解决冲突来建立相应的哈希表和完成查找过程及平均查找长度的计算。 【问题描述】

研究哈希（HAXI）表查找技术的两个重要问题是：构造HAXI函数和处理冲突。现在要求针对某个数据集合中的关键字设计一个哈希表（选择合适的哈希函数和处理冲突的方法），完成HAXI表的建立、查找，并计算HAXI表查找成功的平均查找长度。HAXI函数的构造方法有多种，其中除留余数法是一种最简单和最常用的方法。

考虑具体问题的关键字集合，如{19，14，23，1，68，20，84，27，55，11，10，79}这样一组数据和给定的哈希表长m 或哈希表的装填因子a，选用除留余数法和线性探测再散列技术解决冲突所形成的哈希表以及该哈希表在查找成功时的平均查找长度ASL。

【数据描述】

HAXI表是根据设定的HAXI函数和处理冲突的方法将一组关键字映射到一个有限的连续的地址区间上，并以关键字在地址区间的“象”作为记录在表中的存储位置。因此我们可以采用动态分配的顺序存储结构表示HAXI表。

typedef struct {

KeyType key ; }ElemType;

//元素类型的定义

ElemType *HAXI;//动态分配的哈希表的首地址

【算法描述】

1、选择合适的哈希函数H（ key）=key % p（P为小于或等于HAXI 表长的最大质数）；

2、计算各个关键字的直接哈希函数值；

3、根据处理冲突的方法建立哈希表，并输出；

4、在哈希表中进行查找，输出查找的结果，以及所需和记录关键字比较的次数，并计算和输出在等概率情况下查找成功的平均查找长度。

三、源程序 #include #include #define NULL 0 typedef int KeyType; typedef struct {

KeyType key ; }ElemType; int haxi(KeyType key,int m){ /*根据哈希表长m, 构造除留余数法的哈希函数haxi*/

int i,p,flag;

for (p=m ; p>=2 ; p--)

/*p为不超过m的最大素数*/

{ for (i=2,flag=1;i

if (p %i==0) flag=0;

if (flag==1) break;

} return key%p;

/*哈希函数*/ }

void inputdata(ElemType **ST,int n ){ /*从键盘输入n个数据，存入数据表ST（采用动态分配的数组空间）*/

KeyType key;

int i;

(*ST)=(ElemType*)malloc(n*sizeof(ElemType));

printf(\"\\nPlease input %d data:\",n);

for (i=0;i

scanf(\"%d\",&((*ST)[i].key)); }

void createhaxi(ElemType **HAXI,ElemType *ST,int n,int m){

/*根据数据表ST，构造哈希表HAXI*，n,m分别为数据集合ST和哈希表的长度*/ int i,j;

(*HAXI)=(ElemType*)malloc(m*sizeof(ElemType));

for (i=0;i

for (i=0;i

j=haxi(ST[i].key,m);

/*获得直接哈希地址*/

while ((*HAXI)[j].key!=NULL) j=(j+1)%m;/*用线性探测再散列技术确定存放位置*/

(*HAXI)[j].key=ST[i].key;

/*将元素存入哈希表的相应位置*/

} }

int search(ElemType *HAXI,KeyType key,int m,int *time){

/*在表长为m的哈希表中查找关键字等于key的元素，并用 time记录比较次数，

若查找成功，函数返回值为其在哈希表中的位置，否则返回-1*/ int i;

*time=1;

i=haxi(key,m);

while (HAXI[i].key!=0 && HAXI[i].key!=key) {i++; ++*time;}

if (HAXI[i].key==0) return -1;

else return i; } main(){

ElemType *ST,*HAXI;

KeyType key;

int i,n,m,stime,time;

char ch;

printf(\"\\nPlease input n && m(n

/*输入关键字集合元素个数和HAXI表长*/

scanf(\"%d%d\",&n,&m);

inputdata(&ST,n);

/*调用函数，输入n个数据*/

createhaxi(&HAXI,ST,n,m);

/*建立哈希表*/ /*输出已建立的哈希表*/

printf(\"\\nThe haxi Table is\\n\");

for (i=0;i

printf(\"\\n\");

for (i=0;i

/*哈希表的查找，可进行多次查找*/ do {

printf(\"\\nInput the key you want to search:\");

scanf(\"%d\",&key);

i=search(HAXI,key,m,&time);

if (i!=-1) {printf(\"\\nSucce,the position is %d \",i);/*查找成功*/

printf(\"\\nThe time of compare is %d\",time);

}

else{ printf(\"\\nUnsucce\");

/*查找失败*/

printf(\"\\nThe time of compare is %d\",time);

}

printf(\"\\nContinue(y/n):\\n\");

/*是否继续查找yes or no*/

ch=getch();

} while (ch==\'y\' || ch==\'Y\') ;

/*计算表在等概率情况下的平均查找长度，并输出*/

for (stime=0,i=0;i

search(HAXI,ST[i].key,m,&time);

stime+=time;

};

printf(\"\\nThe Average Search Length is%5.2f\",(float)stime/n);

ch=getch(); }

四、测试数据

按运行提示输入数据(关键字集合)ST，建立HAXI表，然后进行多次查找。 Please input n && m(n

0 1

7 14

68 27 55 19 20 84 Input the key you want to search:27 Succe,the position is 4 The time of compare is 4; Continue(y/n):y

Input the key you want to search:68 Succe,the position is 3 The time of compare is 1; Continue(y/n):n

The Average Search Length is 2.5

10 79 23

11 12

10 实验七 排序 一．实验目的：

理解各种排序的思想，实现对数据的排序。例如用：起泡排序和插入排序。 二．实验内容：

按提示输入10个整形数据。 每个数据中间一空格输出

程序达到的功能要求对输入的10个数据进行排序 例如：输入2 4 3 5 6 8 9 11 15 0

输出 0 2 3 4 5 6 8 9 11 15 源文件： #include #include void bubblesort(int[],int); void insertsort(int[],int);

void menu() {printf(\"

1.bubblesort()\\n\"); printf(\"

2.insertsort()\\n\"); printf(\"please select the method:\"); }

void main() {int i,j=1; int ch; int a[10]; clrscr(); printf(\"please input 10 data:\"); for(i=0;i

scanf(\"%d\",&a[i]);

/*显示提示输入10个数据*/ menu();

while(j--) {ch=getchar();

ch=getchar();

switch(ch)

{case\'1\':bubblesort(a,10);break;

case\'2\':insertsort(a,10);break;

} } for(i=0;i

printf(\"%d \",a[i]);

} void insertsort(int r[],int n)

{int i,j,temp1,temp2;

for(i=1;i

{temp1=r[i];j=i-1;

while(temp1=0)

{temp2=r[j+1];

r[j+1]=r[j];

r[j]=temp2;j--;

}

r[j+1]=temp1;

} }

void bubblesort(int r[],int n)

{int i,j,change,temp; for(i=n-1,change=1;i>=0&&change;--i)

{change=0;

for(j=0;j

/*显示菜单*/

/*选择排序方法*/

/*输出排序结果*/

/*插入排序函数定义*/ /*定义控制循环及中间变量*/

/*数据交换位置*/

/*起泡排序法函数定义*/

{if(r[j]>r[j+1])

/*数据交换位置*/

{temp=r[j+1]; r[j+1]=r[j]; r[j]=temp; change=1; }

}

} }

三．使用说明：

按提示输入10个整形数据 在菜单中选择排序的方法 查看排序结果

四．测试结果：

运行程序，屏幕提示

please input 10 data: 2 4 3 5 bubblesort() insertsort()

please select the method:1

0 2 3 4 5 6 8 9

please select the method:2

0 2 3 4 5 6 8 9

6 8 9 11 15 11 15 11 15 0

第18篇：数据结构课程设计

数据结构课程设计

1.赫夫曼编码器

设计一个利用赫夫曼算法的编码和译码系统，重复地显示并处理以下项目，直到选择退出为止。 要求：

1) 将权值数据存放在数据文件(文件名为data.txt，位于执行程序的当前目录中)

2) 初始化：键盘输入字符集大小

26、26个字符和26个权值（统计一篇英文文章中26个字母），建立哈夫曼树；

3) 编码：利用建好的哈夫曼树生成哈夫曼编码；

4) 输出编码（首先实现屏幕输出，然后实现文件输出）； 5) 界面优化设计。

代码如下：

#include #include #include #include #define N 200

typedef struct HTNode

//结构体 { int Weight;

char ch; int Parent,Lchild,Rchild; }HTNode; typedef char * * HCode;

void Save(int n,HTNode *HT)

//把权值保存到文件 {

FILE * fp;

int i;

if((fp=fopen(\"data.txt\",\"wb\"))==NULL)

{

printf(\"cannot open file\\n\");

return;

}

for(i=0;i

if(fwrite(&HT[i].Weight,sizeof(struct HTNode),1,fp)!=1)

printf(\"file write error\\n\");

fclose(fp);

system(\"cls\");

printf(\"保存成功！\");

}

void Create_H(int n,int m,HTNode *HT)

//建立赫夫曼树，进行编码 {

int w,k,j; char c; for(k=1;k

if(k

{

printf(\"\\n请输入权值和字符(用空格隔开): \");

scanf(\"%d\",&w);

scanf(\" %c\",&c); HT[k].ch=c;

HT[k].Weight=w;

}

else HT[k].Weight=0;

HT[k].Parent=HT[k].Lchild=HT[k].Rchild=0; }

int p1,p2,w1,w2;

for(k=n+1;k

p1=0;p2=0;

w1=32767;w2=32767;

for(j=1;j

{

if(HT[j].Parent==0)

{

if(HT[j].Weight

{

w2=w1;p2=p1;

w1=HT[j].Weight;

p1=j;

}

else if(HT[j].Weight

{

w2=HT[j].Weight;

p2=j;

}

}

} HT[k].Lchild=p1;HT[k].Rchild=p2; HT[k].Weight=HT[p1].Weight+HT[p2].Weight;

HT[p1].Parent=k;HT[p2].Parent=k;

} printf(\"输入成功！\"); }

void Coding_H(int n,HTNode *HT)

//对结点进行译码 { int k,sp,fp,p; char *cd; HCode HC;

HC=(HCode)malloc((n+1)*sizeof(char *));

cd=(char *)malloc(n*sizeof(char)); cd[n-1]=\'\\0\';

printf(\"************************\\n\"); printf(\"Char Coding\\n\");

for(k=1;k

{

sp=n-1;p=k;fp=HT[k].Parent;

for(;fp!=0;p=fp,fp=HT[fp].Parent)

if(HT[fp].Lchild==p)

cd[--sp]=\'0\';

else

cd[--sp]=\'1\';

HC[k]=(char *)malloc((n-sp)*sizeof(char));

strcpy(HC[k],&cd[sp]);

printf(\"%c

%s\\n\",HT[k].ch,HC[k]);

}

printf(\"************************\\n\"); free(cd) ; } void Read(int n,HTNode *HT)

//从文件中读出数据 {

int i; FILE * fp; if((fp=fopen(\"data.txt\",\"rb\"))==NULL) {

printf(\"cannot open file\\n\");

exit(0); } for(i=0;i

fread(&HT[i].Weight,sizeof(struct HTNode),1,fp); // printf(\"%d \\n\",HT[i].Weight);

} Coding_H(n,HT);

fclose(fp); }

void Print_H(int m,HTNode *HT)

//输出赫夫曼造树过程 { int k; printf(\"************************\\n\"); printf(\"Num Weight

Par LCh RCh \\n\"); for(k=1;k

printf(\"%d \",k);

printf(\"

%d\",HT[k].Weight);

printf(\"

%d\",HT[k].Parent);

printf(\"

%d\",HT[k].Lchild);

printf(\"

%d\\n\",HT[k].Rchild);

} printf(\"************************\\n\"); }

void Decode(int m,HTNode *HT)

//对输入的电文进行译码 { int i,j=0; char a[10]; char endflag=\'2\'; i=m; printf(\"输入发送的编码，以‘2’结束:\"); scanf(\"%s\",&a); printf(\"译码后的字符：\"); while(a[j]!=\'2\') {

if(a[j]==\'0\')

i=HT[i].Lchild;

else i=HT[i].Rchild;

if(HT[i].Lchild==0)

//HT[i]是叶结点

{

printf(\"%c\",HT[i].ch);

i=m;

//回到根结点

}

j++; } printf(\"\\n\"); if(HT[i].Lchild!=0&&a[j]!=\'2\')

printf(\"ERROR\"); }

int main()

//主函数 { int n,m,c; HTNode HT[N]; do {

system(\"color 2f\");

//运行环境背景颜色.

printf(\"\\n\\n\\t\\t*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=\\n\\t\\t\");

printf(\"\\n\\t\\t\\t 赫夫曼编译码系统 \\t\\t\\t\");

printf(\"\\n\\n\\t\\t*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=\\n\\t\\t\");

printf(\"\\n\\t\\t\\t1.输入权值、字母\\n\\t\\t\\t2.把数据写入文件\\n\\t\\t\\t3.输出赫夫曼编码表\\n\\t\\t\\t\");

printf(\"4.输出赫夫曼译码表\\n\\t\\t\\t5.输入编码并译码.\\n\\t\\t\\t6.从文件中读出数据\\n\\t\\t\\t7.退出\");

printf(\"\\n\\n\\t\\t\\t请选择:\");

scanf(\"%d\",&c);

switch(c)

{

case 1:system(\"cls\");printf(\"输入多少结点:\");

scanf(\"%d\",&n);m=2*n-1;Create_H(n,m,HT);break;

case 2:system(\"cls\");Save(n,HT);break;

case 3:system(\"cls\");Print_H(m,HT);break;

case 4:system(\"cls\");Coding_H(n,HT);break;

case 5:system(\"cls\");Decode(m,HT);break;

case 6:system(\"cls\");Read(n,HT);break;

case 7:system(\"cls\");exit(0);

}

}while(1); return 0; }

运行界面如下：

2.学生成绩管理（链表实现） 要求：

实现如下功能：增加、查找、删除、输出、退出。

代码如下：

#include #include #include typedef struct score

//定义成绩信息结构体 {

char Number[20]; char Name[20]; char Chinese[20]; char English[20]; char Math[20]; }score; typedef struct node_score

//定义成绩信息链表结点，包括数据域和指针域 {

score data; struct node_score *next; }node_score,*p_node_score; p_node_score headScore;//定义链表的头指针为全局变量 void PrintScore(score s) //输出信息函数 { printf(\" %10s\",s.Number); printf(\" |

%-6s\",s.Name); printf(\"

|

%-3s\",s.Chinese); printf(\"

|

%-3s\",s.English);

printf(\" |

%-3s\\n\",s.Math); } void View()//输出函数 {

p_node_score pNodeScore;

pNodeScore=headScore; printf(\"

学号

|

姓名

| 语文成绩

| 英语成绩| 高数成绩\\n\"); while(pNodeScore != NULL) {

PrintScore(pNodeScore->data);//输出学生信息和成绩信息

pNodeScore=pNodeScore->next; } } void Add() {

p_node_score pNodeScore; // 定义一个节点

pNodeScore=(p_node_score)malloc(sizeof(node_score));//为节点分配存储空间

printf(\"请输入学号：\"); scanf(\"%s\",pNodeScore->data.Number); printf(\"请输入姓名：\"); scanf(\"%s\",pNodeScore->data.Name); printf(\"请输入语文成绩：\"); scanf(\"%s\",pNodeScore->data.Chinese); printf(\"请输入英语成绩：\"); scanf(\"%s\",pNodeScore->data.English); printf(\"请输入高数成绩：\"); scanf(\"%s\",pNodeScore->data.Math); if(headScore==NULL) { //如果头结点为空

headScore=pNodeScore;

pNodeScore->next=NULL; } else

{ //如果头结点不为空

pNodeScore->next=headScore;

headScore=pNodeScore;//将头结点新结点

} } void Input() { int n,i; printf(\"输入几个学生的数据：\"); scanf(\"%d\",&n); for(i=0;i

Add(); printf(\"输入成功！\"); } int Delete() { p_node_score pNodeScore,p1; //p1为pNodeScore的前驱

p1=headScore; if(p1==NULL) {

printf(\"成绩表中没有数据！请先添加数据！\\n\");

return 0; } char DeleteNumber[20];

printf(\"请数入要删除的学生学号:\"); scanf(\"%s\",DeleteNumber); if(strcmp(p1->data.Number,DeleteNumber)==0)

{ //如果要删除的结点在第一个

headScore=p1->next;

pNodeScore=p1;

printf(\"学号为%s的学生信息已经删除！\\n\",DeleteNumber);

return 0; } else

{

pNodeScore=p1->next;

while(pNodeScore!=NULL)

{

if(strcmp(pNodeScore->data.Number,DeleteNumber)==0)

{

p1->next=pNodeScore->next;

printf(\"学号为%s的学生信息已经删除！\\n\",DeleteNumber);

return 0;

}

else

{ //否则，结点向下一个，p1仍为pNodeScore的前驱

p1=pNodeScore;

pNodeScore=pNodeScore->next;

}

} } printf(\"没有此学号的学生！\"); } int Change() {

p_node_score pNodeScore;

pNodeScore=headScore; if(pNodeScore==NULL) {

printf(\"成绩表中没有数据！请先添加数据！\\n\");

return 0; } char EditNumber[20]; printf(\"请输入你要修改的学生学号：\"); scanf(\"%s\",EditNumber); while(pNodeScore!=NULL) {

if(strcmp(pNodeScore->data.Number,EditNumber)==0)

{ //用strcmp比较两字符串是否相等，相等则返回0

printf(\"原来的学生成绩信息如下：\\n\"); //输出原来的成绩信息

printf(\"

学号

|

姓名

| 语文成绩

| 英语成绩| 高数成绩\\n\");

PrintScore(pNodeScore->data);

printf(\"语文新成绩:\");

scanf(\"%s\",pNodeScore->data.Chinese);

printf(\"英语新成绩:\");

scanf(\"%s\",pNodeScore->data.English);

printf(\"高数新成绩:\");

scanf(\"%s\",pNodeScore->data.Math);

printf(\"成绩已经修改！\");

return 0;

}

pNodeScore=pNodeScore->next; //如果不相等，pNodeScore则指向下一个结点

} printf(\"没有此学号的学生！\\n\"); //如果找到最后都没有，则输出没有此学号的学生

} int Find() {

p_node_score pNodeScore;

pNodeScore=headScore; if(pNodeScore==NULL) {

printf(\"成绩表中没有数据！请先添加数据！\\n\");

return 0; } char FindNumber[20]; printf(\"请输入你要查找的学生学号：\"); scanf(\"%s\",FindNumber); while(pNodeScore!=NULL) {

if(strcmp(pNodeScore->data.Number,FindNumber)==0)

{

printf(\"你要查找的学生成绩信息如下：\\n\");

printf(\"

学号

|

姓名

| 语文成绩

| 英语成绩| 高数成绩\\n\");

PrintScore(pNodeScore->data);

return 0;

}

pNodeScore=pNodeScore->next; } printf(\"没有此学号的学生！\\n\"); } int main()

//主函数 { int choice=0; headScore=NULL; int c; do {

system(\"color 2f\");

//运行环境背景颜色.

printf(\"\\n\\n\\t\\t*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=\\n\\t\\t\");

printf(\"\\n\\t\\t\\t 学生成绩管理系统 \\t\\t\\t\");

printf(\"\\n\\n\\t\\t*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=\\n\\t\\t\");

printf(\"\\n\\t\\t\\t1.输入成绩信息\\n\\t\\t\\t2.输出成绩信息\\n\\t\\t\\t3.添加成绩信息\\n\\t\\t\\t\");

printf(\"4.修改成绩信息\\n\\t\\t\\t5.删除成绩信息\\n\\t\\t\\t6.查询成绩信息\\n\\t\\t\\t7.退出\");

printf(\"\\n\\n\\t\\t\\t请选择:\");

scanf(\"%d\",&c);

switch(c)

{

case 1:system(\"cls\");Input();break;

case 2:system(\"cls\");View();break;

case 3:system(\"cls\");Add();break;

case 4:system(\"cls\");Change();break;

case 5:system(\"cls\");Delete();break;

case 6:system(\"cls\");Find();break;

case 7:system(\"cls\");exit(0);

}

}while(1); return 0; }

运行界面如下：

第19篇：《数据结构》说课稿

《数据结构》“最短路径”问题说课稿

一、教材分析

1、特点与地位：

重点中的重点。本课是教材《数据结构》第六章第五节的内容。图是一种典型的非线性数据结构，应用十分广泛。求两结点之间的最短路径问题是图最常见的应用的之一，在交通运输、通讯网络等方面具有一定的实用意义。

2、重点与难点：

根据高职数据结构教育要求，理论“必需，够用”，侧重于某项技术的理论依据，重点放在技能培养上。结合学生现有抽象思维能力水平，已掌握基本概念等学情，以及求解最短路径问题的自身特点，确立本课的重点和难点如下：

（1）重点：如何将现实问题抽象成求解最短路径问题，以及该问题的解决方案。 （2）难点：求解最短路径算法的程序实现。

3、教学安排：

最短路径问题包含两种情况：一种是求从某个源点到其他各结点的最短路径，另一种是求每一对结点之间的最短路径。根据教学大纲安排，重点讲解第一种情况问题的解决。安排一个课时讲授。教材直接分析算法，考虑实际应用需要，补充旅游景点线路选择的实例，实例中问题解决与算法分析相结合，逐步推动教学过程。

二、教学目标分析

1、知识目标：掌握最短路径概念、能够求解最短路径。

2、能力目标：

（1）通过将旅游景点线路选择问题抽象成求最短路径问题，培养学生的数据抽象能力。

（2）通过旅游景点线路选择问题的解决，培养学生的独立思考、分析问题、解决问题的能力。 （3）通过算法的程序实现，提高学生的编程能力。

3、素质目标：培养学生讲究工作方法、与他人合作，提高工作效率的职业素质。

三、教法分析

课前充分准备，研读教材，查阅相关资料，制作多媒体课件。教学过程中除了使用传统的“讲授法”以外，主要采用“案例教学法”，同时辅以多媒体课件，以启发的方式展开教学。由于本节课的内容属于图这一章的难点，考虑学生的接受能力，注意与学生沟通，根据学生的反应控制好教学进度是本节课成功的关键。

四、学法指导

1、课前

上次课结课时给学生布置任务，使其有针对性的预习。

2、课中

指导学生讨论任务解决方法，引导学生分析本节课知识点。

3、课后

给学生布置同类型任务，加强练习。

五、教学过程分析

（一）课前复习（3~5分钟）

回顾“路径”的概念，为引出“最短路径”做铺垫。 教学方法及注意事项：

（1）采用提问方式，注意及时小结，提问的目的是帮助学生回忆概念。 （2）提示学生“温故而知新”，养成良好的学习习惯。

（二）导入新课（3~5分钟）

以城市公路网为例，基于求两个点间最短距离的实际需要，引出本课教学内容“求最短路径问题”。 教学方法及注意事项：

（1）先讲实例，再指出概念，既可以吸引学生注意力，激发学习兴趣，又可以实现教学内容的自然过渡。

（2）此处使用案例教学法，不在于问题的求解过程，只是为了说明问题的存在，所以这里的例子只需要概述，能够说明问题即可。

（三）讲授新课（25~30分钟）

1、求某一结点到其他各结点的最短路径（重点）

主要采用案例教学法，提出旅游景点选择的例子，解决如何选择代价小、景点多的路线。 （1）将实际问题抽象成图中求任一结点到其他结点最短路径问题。（3~5分钟） 教学方法及注意事项：

①

主要采用讲授法，将实际问题用图形表示出来。语言描述转换的方法（用圆圈加标号表示某一景点，用箭头表示从某景点到其他景点是否存在旅游线路，并且将旅途费用写在箭头的旁边。）一边用语言描述，一边在黑板上画图。

②

注意示范画图只进行一部分，让学生独立思考、自主完成余下部分的转化。

③

及时总结，原型抽象（景点作为图的结点，景点间的线路作为图的边，旅途费用作为边的权值），将案例求解问题抽象成求图中某一结点到其他各结点的最短路径问题。 ④

利用多媒体课件，向学生展示一张带权有向图，并略作解释，为后续教学做准备。 （2）迪杰斯特拉算法（难点）（17~20分钟） 先讲算法思想，主要采用多媒体教学。 教学方法及注意事项：

① 充分利用课件。将教材中的算法思想细化，分步解释给学生。用投影仪演示给学生看，在有限的时间内，学生一边看投影仪上的文字，一边听教师的分析，提高教学效率。注意讲解后给学生留出适当的思考时间。

② 利用FLASH动画，结合第一步案例中抽象出的有向带权图、算法思想，求解答案。帮助学生进一步理解算法思想。 再讲算法实现，主要采用启发式教学。 教学方法及注意事项：

① 启发式教学，如何在计算机中实现上述算法呢？如何实现按路径长度递增产生最短路径？如何记录求解过程中每一步当前的V0到Vi的最短路径呢？引入dist[ ]数组。 ② 结合案例分析求解最短路径过程中dist[ ]数组的变化过程。（重点）注意此处最好借助黑板，按照算法思想的步骤，逐步修改dist[ ]数组。同样，也是只示范一部分，余下部分由学生独立思考完成。 ③ 程序代码的讲解，注重思路，淡化语言。本课程不是语言课 ，对于实现语言不做要求，鼓励学生自己动手将教材提供程序做适当修改，用C++实现，培养他们的编程能力。

2、求每一对结点之间的最短路径（5~6分钟）

两种思路：一种重复执行n次Dijkstra算法，另一种弗洛伊德（Floyed）算法。

教学方法及注意事项：此处只介绍算法思想，算法实现给学生作为拓展内容，自由把握。

（四）课堂小结（3~5分钟）

1、明确本节课重点Dijkstra算法，及算法实现的辅助数组dist[ ]的变化过程。

2、提示学生，在案例中数据抽象时，用结点表示活动，用有向边便是活动之间的优先关系，这种方式形成的图又可以解决哪类实际问题呢？引导学生预习，为下次课的学习埋下伏笔。

（五）布置作业（1~2分钟）

1、书面作业：P174 6.7

2、复习本次课内容，预习下次课内容。

至此，整个教学过程结束，注意留出1~3分钟机动时间，准备一道备用习题，灵活把握时间安排。

六、教学特色

以旅游路线选择为主线，灵活采用案例教学、示范教学、多媒体课件等多种手段辅助教学，使枯燥的理论讲解生动起来。在顺利开展教学的同时，体现所讲内容的实用性，提高学生的学习兴趣。

第20篇：课程设计(数据结构)

课程设计题目

1、运动会分数统计

任务：参加运动会有n个学校，学校编号为1……n。比赛分成m个男子项目，和w个女子项目。项目编号为男子1……m，女子m+1……m+w。不同的项目取前五名或前三名积分；取前五名的积分分别为：

7、

5、

3、

2、1，前三名的积分分别为：

5、

3、2；哪些取前五名或前三名由学生自己设定。（m=10 , w=8 , n=15） 功能要求：

1).可以输入各个项目的前三名或前五名的成绩； 2).能统计各学校总分（用链表）；

3).可以按学校编号、学校总分、男女团体总分排序输出（快速、基数）；

4).可按学校编号查询学校某个项目的情况；可按项目编号查询取得前三或前五名的学校。

界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。

存储结构：学生自己根据系统功能要求自己设计，但是要求运动会的相关数据要存储在数据文件中。

测试数据：要求使用

1、全部合法数据；

2、局部非法数据。进行程序测试，以保证程序的稳定。测试数据及测试结果请在上交的资料中写明；

2、迷宫求解

任务：可以读入一个任意大小的迷宫数据，分别用广度和深度搜索的方法求出一条走出迷宫的路径，并将路径输出（最佳路径）； 要求：以较为直观的方式显示结果

3、Huffman编码

任务 ：对一篇英文文章，统计各字符出现的次数，实现Huffman编码； 要求：输出每个字符出现的次数和编码，其中求最小权值要求用堆实现；

4、营业窗口队列模拟

任务：实现具有n（n=3）个窗口的现实队列模拟，统计每人的等待时间。 要求：

1).随机产生顾客的到达时间和服务时间存盘。 2).利用存盘数据实现队列的插入和删除。 2).当有顾客离开时，根据队列长度调整队尾。 3).考虑顾客中途离队的情况。 4).考虑顾客具有优先级的情况。

5、公交线路提示

任务：建立南京主要公交线路图。 要求：输入任意两站点，给出最佳的乘车线路和转车地点。

6、家谱管理系统

任务：实现具有下列功能的家谱管理系统 功能要求：

1).输入文件以存放最初家谱中各成员的信息，成员的信息中均应包含以下内容：姓名、出生日期、婚否、地址、健在否、死亡日期（若其已死亡），也可附加其它信息、但不是必需的。

2).实现数据的存盘和读盘。 3).以图形方式显示家谱。

4).显示第n 代所有人的信息。

5).按照姓名查询，输出成员信息（包括其本人、父亲、孩子的信息）。 6).按照出生日期查询成员名单。 7).输入两人姓名，确定其关系。 8).某成员添加孩子。

9).删除某成员（若其还有后代，则一并删除）。 10).修改某成员信息。

11).按出生日期对家谱中所有人排序。

12).打开一家谱时，提示当天生日的健在成员。

要求：建立至少30个成员的数据，以较为直观的方式显示结果，并提供文稿形式以便检查。

界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。

存储结构：学生自己根据系统功能要求自己设计，但是要求相关数据要存储在数据文件中。测试数据：要求使用

1、全部合法数据；

2、局部非法数据。进行程序测试，以保证程序的稳定。测试数据及测试结果请在上交的资料中写明；

7、排序算法比较

设计要求：利用随机函数产生10个样本，每个样本有50000随机整数，利用直接插入排序、折半插入排序，表插入排序，希尔排序，起泡排序、快速排序、选择排序、堆排序，归并排序，基数排序十种排序方法进行排序（结果为由小到大的顺序），并统计每一种排序所耗费的平均时间（统计为图表坐标形式）。

8、算术表达式求值 [问题描述]

一个算术表达式是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。假设操作数是正整数，运算符只含加减乘除等四种运算符，界限符有左右括号和表达式起始、结束符“#”，如：#（7+15）*（23-28/4）#。引入表达式起始、结束符是为了方便。编程利用“算符优先法”求算术表达式的值。 [基本要求] （1） 从键盘读入一个合法的算术表达式，输出正确的结果。 （2） 显示输入序列和栈的变化过程。

9、电子小字典

基本要求：建立一个微型电子字典，实现生词的加入，单词的查找、删除，修改等操作。

数据结构：键树

10、校园导游程序

[问题描述]用无向网表示你所在学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。要求能够回答有关景点介绍、游览路径等问题。 [基本要求] （1） 查询各景点的相关信息；

（2） 查询图中任意两个景点间的最短路径。 （3） 查询图中任意两个景点间的所有路径。

（4） 增加、删除、更新有关景点和道路的信息。

11、稀疏矩阵相乘

任务：以三元组形式存储稀疏矩阵，实现矩阵相乘。

12、平衡二叉树

任务：平衡二叉树的建立、结点的插入和删除。

13、B-树

任务：3阶B-树的结点的插入和删除。

14、HASH表

任务：以班级学生姓名（拼音）为关键字，建立HASH涵数，实现HASH表存储，用链地址方法解决冲突。

15、„„（自选合适的题目）

成绩评定细则：

1.正确性：程序是否可以运行，结果是否正确（20分） 2.功能的完备性：是否实现要求的所有子功能（20分）

3.课程设计报告中的算法说明的清晰程度，课程设计报告中总结的深刻程度（20分） 4.独立完成情况( 40分） 总计：100分

加分项目：

1.健壮性：异常处理的情况

2.可读性：代码编写是否规范，是否便于阅读。如函数、变量命名，‘{ }’的缩进，关键位置适量注释等

3.功能的完善：除要求实现的功能外，完成了其它的功能，实现了功能的完善 4.界面的设计：可视化界面，或者交互良好的DOS界面 5.……（自荐加分项目）

代码量要求：>=1000行。

代码总量 = 课设题目1 代码量 + 课设题目2 代码量…… 若代码总量低于1000行，则成绩按比例打折。

编程语言：C或C++语言

编程环境：Microsoft Visual C++ 6.0

检查方式: 1.总体上检查程序的代码量，正确性，可读性，健壮性，功能的完备性,代码量，程序的结构是否合理；局部检查三个以上函数块 2.检查程序时同时检查课程设计报告的电子文档

时间安排：

1 上机时间安排

2 课程设计报告上交时间 3 课程设计检查时间

课程设计报告要求：

1.所有的课程设计报告，均要有封面，包括：课题名称、班级、学号、学生姓名、成绩和指导教师；

2.给出自己采用的数据结构；3.给出算法设计思想；

4.给出实现的源程序，并在必要的代码处给出注释；5.给出测试数据和结果；

6.给出算法的时间复杂度、另外可以提出算法的改进方法；

7.给出结束语：说明完成课程设计的情况，心得体会；课程设计报告的电子文档在上机检查程序时一并检查；书面文档在指定的时间内上交。

《数据结构心得体会.doc》

将本文的Word文档下载到电脑，方便编辑。

推荐度：

点击下载文档