数据结构-讲义new

《数据结构-讲义new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、前言缘起《数据结构》是一门计算机专业基础课，各类计算机考试都禁不住要考它，专升本考试自然也不例外。我给学生辅导这门课程已经有几个年头了，讲稿换了几次，逐渐丰富起来。加之看到学生们埋头记笔记时辛苦的样子，就产生了写一本小册子的想法。另外，还有一层意思就是对数次辅导进行总结，以便交流之用。说明首先，需要说明的是这本书在语言风格上不太讲究，常有些不严谨的表达，或调侃，或土得掉渣，难登大雅之堂，请勿在正规场合引用这些说法。这样做的目的，仅仅是为了更简练、更直接地描述思想，方便理解、记忆和使用。凡是这种情况，往往

2、都用引号括起来，并加以脚注说明。还有，本书需配合《数据结构》(严蔚敏)教材使用。由于篇幅有限，多数概念、术语没有详释。另外，每章之后都配有习题，或多或少，难度不一，并没有局限于专升本的要求。对所有习题都提供了参考答案。致谢我要感谢所有给予我帮助的人。张志老师的大力支持和帮助使得本书得以面世，他还提供了近年专升本试题。李永干老师的帮助使得本书顺利印刷。谭业武老师给了我很大支持，还提出了很多建议。最后，我要感谢隆坤，她总是给我最大的支持，使那些本来只在我想象中的事情变成现实。庄波于滨州学院2005年2月26

3、日-III-第0章复习提示1一、教材内容1二、复习提示11.经典算法12.绪论13.线性表14.栈和队列25.串26.树和二叉树27.图28.查找表39.内部排序3第1章绪论5一、基础知识5二、算法5三、习题6第2章线性表7一、基础知识和算法71.线性表及其特点72.顺序表——线性表的顺序存储结构73.单链表——线性表的链式存储结构之一104.循环链表155.双向循环链表156.顺序表与单链表的比较16二、习题16第3章栈和队列17一、基础知识和算法171.栈172.链栈173.顺序栈184.队列195

4、.链队列206.循环队列207.栈和队列比较228.简化的栈和队列结构239.栈和队列的应用23二、习题24第4章串25一、基础知识和算法251.概念252.串的基本操作253.串的存储结构25二、习题25第6章树和二叉树27一、基础知识和算法271.树及有关概念272.二叉树27-III-3.二叉树的性质274.二叉树的存储结构285.二叉树的五种基本形态286.遍历二叉树297.遍历二叉树的应用338.线索二叉树349.树和森林3510.赫夫曼树及其应用36二、习题37第7章图39一、基础知识和算法

5、391.图的有关概念392.图的存储结构393.图的遍历424.最小生成树445.拓扑排序466.关键路径467.最短路径47二、习题49第9章查找51一、基础知识和算法511.有关概念512.顺序查找513.折半查找524.索引顺序表545.二叉排序树546.平衡二叉树577.B-树和B+树588.键树599.哈希表59二、习题61第10章内部排序63一、基础知识和算法631.排序的有关概念632.直接插入排序633.折半插入排序644.希尔排序（缩小增量排序）645.起泡排序656.快速排序667.

6、简单选择排序678.堆排序689.归并排序7110.基数排序7211.各种排序方法比较73-III-www.juanjuantx.com11.各种排序方法比较第0章复习提示一、教材内容l使用教材《数据结构》C语言版严蔚敏，清华大学出版社。l章节去掉第5、8、11、12章去掉**部分去掉1.3，2.4，4.4二、复习提示1.经典算法单链表：遍历、插入、删除循环队列：队列空、队列满的条件二叉树：递归遍历及应用有序表的二分法查找快速排序简单选择排序2.绪论掌握几个重要概念数据结构、抽象数据类型、算法时间复杂度

7、的简单计算（C记号C，表示要求掌握计算方法，会计算。本节下同。）掌握几种说法数据元素是…，数据项是…数据结构中关系的四种基本结构数据结构的形式定义算法的五个特征-98-www.juanjuantx.com11.各种排序方法比较1.线性表线性表的概念和四个特征顺序表和单链表的类型定义在顺序表中查找、插入、删除，灵活运用在单链表中查找、插入、删除，灵活运用循环链表及双向链表的定义、插入、删除算法：单链表的算法，灵活运用、会编程（P记号P，要求达到编写算法和程序的能力。本节下同。）2.栈和队列栈和队列的概念、

8、特点入栈、出栈操作，灵活掌握了解栈的实现：链栈和顺序栈（A记号A，要求掌握算法思想，会演算。本节下同。算法，P）了解队列的实现，链队列和循环队列，注意链队列中的出队列操作算法：注意循环队列空和满的条件（A，P）会运用栈和队列3.串掌握相关概念会运用串的基本操作（C），特别是Concat()，Substring()，Index()和Replace()知道串的三种存储结构及其特点4.树和二叉树树和二叉树的有关概念二叉树的性质熟练掌握遍历二叉树的