本书主要介绍了线性表、栈和队列、树、图等数据结构及相关操作，同时还介绍了查找、排序等算法。在介绍基本知识的基础上与实际应用相结合，加深学生对知识的理解。为了便于学生理解所学知识，本书还增加了对C语言中结构体知识的简单回顾。每章以实际例子引出知识点，每章最后综合应用全章知识解决一个实际问题。书中全部算法用C语言实现，且全都可编译执行。每章后面附有相关习题，配套实验指导中附有参考答案及解析，便于学生自己练习相关知识点。
“数据结构”课程是高等学校计算机及相关专业的一门重要的专业基础课程，熟练掌握这门课程中介绍的内容是学习计算机其他相关课程的必备条件。
“数据结构”课程主要研究计算机处理对象的逻辑结构、在计算机中的表示形式及各种基本操作的实现算法。其主要解决系统开发过程中设计阶段的问题，包括对实际问题建模，分析数据的逻辑结构及基本运算，将数据在计算机中存储并实现基本运算等。
本书是河北省高等学校人文社会科学研究项目“基于多学科的应用型‘数据结构’课程体系建设综合研究”项目成果，旨在培养学生的应用能力。本书是在深入研究国内外数据结构优秀教材和大量文献的基础上，结合各位编者多年的教学经验和科研成果编写而成。本书注重理论与实践相结合，每章导读中利用生活实例引出相关的知识点，在每种数据结构介绍完之后都会举一个应用案例，读者在学习知识点的基础上能够与实际相结合，达到学有所用的目的。
本书中所有算法都采用C语言函数的形式描述，同时对这些函数的关键语句都进行了详细注释，并已在Visual C++6.0运行环境下调试运行通过，便于读者理解算法，并方便读者对基本运算进行验证，从而在此基础上学会应用。
本书共分8章，系统介绍了线性表、栈和队列、串、树、图等基本数据结构及应用，并介绍了查找和排序的各种算法及应用。本书课后习题部分提供了各种类型的练习题，供读者练习，加深对各章知识的理解，并在配套教材《数据结构实验指导与习题解析》中提供了习题答案及解析。
本书由燕京理工学院孙丽云和马睿担任主编，由燕京理工学院邵兰洁和李珊、武汉工程科技学院刘艳担任副主编。其中，马睿编写了第1章、第6章和第7章的内容；孙丽云编写了第2章、第3章的内容，并完成了统稿、审稿工作；李珊编写了第4章的内容；邵兰洁编写了第5章的内容；孙丽云和刘艳编写了第8章的内容。课题组成员刘淑艳、刘佩贤、王慧、牛玉玲等老师提供了大量编写素材。
本书在编写过程中得到了燕京理工学院信息科学与技术学院各位领导的指导和帮助，同时得到了华中科技大学出版社的大力支持，在此一并表示感谢。
为了方便教学，本书还配有电子课件等教学资源包，任课教师和学生可以登录“我们爱读书”网（www.ibook4us.com）免费注册并浏览，或者发邮件至hustpeiit@163.com免费索取。
由于作者水平有限，书中难免有错误及疏漏之处，恳请同行专家及读者指正，以便进一步提高本书质量。作者电子邮箱：57025032@qq.com。
第2章线性表
第 2 章 线性表
线性表是最简单、最基本,也是最常用的数据结构。 幼儿园小朋友人数众多,有的幼儿园为便于管理,会给每个班级排一个固定顺序的队伍,如班级里有30个小朋友,会按照顺序给小朋友排学号1,2,3……30,不管是平时放学排队还是外出参加活动,小朋友都按照学号排队,让每个小朋友记住自己前后的小朋友,若发现前后小朋友不在马上报告老师,而老师只要记住第1个小朋友就可以了。班级中,只有1号前面没有小朋友,只有30号后面没有小朋友,其他每个学号都是前面只有一个小朋友,后面只有一个小朋友,这就是一个典型的线性表。 本章我们就要来学习线性表。 2.1线性表的逻辑结构 2.1.1线性表的定义 线性表L是n(n≥0)个具有相同属性的数据元素a1,a2,a3,…,an组成的有限序列。其中，序列中元素的个数n称为线性表的长度。 当n=0时称为空表,即不含有任何元素。 常常将非空的线性表L(n>0)记为：L=(a1,a2,…，ai-1,ai,ai+1,…，an)。 其中，ai-1为ai的直接前驱,ai＋1为ai的直接后继。a1为表头元素,an为表尾元素。线性表有以下特点。 (1) 在非空的线性表中,存在唯一的一个被称为“第一个”的数据元素,又称为表头元素；存在唯一的一个被称为“最后一个”的元素,又称为表尾元素。 (2) 线性表中数据的位置先后是有序的。除表头元素外,线性表中的每一个元素有且仅有一个前驱；除表尾元素外,线性表中的每一个元素有且仅有一个后继。表头元素只有一个后继而没有前驱,表尾元素只有一个前驱而没有后继。 (3) 线性表中的数据的类型是相同的。表的长度n的取值是有限数,最小为0。 在日常生活中,线性表的例子很多。例如，26个英文字母组成的字母表(A,B,C,…,Y,Z)就是一个典型的线性表,该表长度是26,每个字母是表中的一个元素。表21所示的学生信息表也构成了一个线性表。 表21学生信息表 学号姓名班级年龄宿舍 160210001崔雨计科160118星苑305 160210002丁洁计科160119星苑305 160210003樊辰计科160118松苑207 160210004冯波计科160119松苑207 160210005郭力计科160120松苑207 160210006胡志计科160120松苑207 该线性表表长为6,表中每个学生的信息为一个“数据元素”,包括学号、姓名、班级、年龄和宿舍等“数据项”信息。
2.1.2线性表的基本运算 数据结构的基本运算是定义在逻辑结构层次上的,而这些运算的具体实现是需要建立在存储结构上的,因此下面定义的线性表的基本运算作为逻辑结构的一部分,其具体实现却要在线性表的存储结构确定之后才能够完成。 线性表的基本操作有以下几项。 (1) 线性表L的初始化，其语句如下。 InitList(L) 构造一个空的线性表L，即表的初始化。 (2) 创建线性表L，其语句如下。 CreatList(L) (3) 求线性表L的长度，其语句如下。 GetLength(L) 求表中结点的个数,即求表的长度。 (4) 按序号取线性表L中的元素，其语句如下。 GetNode(L,i) 取线性表L中的第i个元素,这里1≤i≤Length(L)。 (5) 在线性表L中查找元素e，其语句如下。 LocateList(L,e) 在L中查找值为e 的结点,并返回该结点在L中的位置。若L中有多个结点的值和e 相同,则返回首次找到的结点位置；若L中没有结点的值为e,则返回一个特殊值(如-1),表示查找失败。 (6) 在线性表L中插入新元素，其语句如下。 InsertList(L,i,e) 在线性表L的第i个位置上插入一个值为x 的新结点,使得原编号为i,i+1,…,n的结点变为编号为i+1,i+2,…,n+1的结点。这里1≤i≤n+1,而n是原表L的长度。插入后,表L的长度加1。 (7) 在线性表L中删除元素，其语句如下。 DeleteList(L,i) 删除线性表L的第i个结点,使得原编号为i+1,i+2,…,n的结点变成编号为i,i+1,…,n-1的结点。这里1≤i≤n (n是原表L的长度),删除后表L的长度减1,为n-1。 (8) 将线性表中元素输出，其语句如下。 PrintList(L) 将线性表L中的元素打印输出,若对线性表进行了一些操作,如插入、删除等,需要将其打印输出查看操作结果。
2.2线性表的顺序存储及运算实现 线性表有两种基本的存储结构：顺序存储结构和链式存储结构。
2.2.1线性表的顺序存储结构 线性表的顺序存储是最简单、最直接的一种存储方式,即把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。这样的存储方式使线性表逻辑上相邻的元素存储在物理地址相邻的存储单元里,即以计算机内“物理位置相邻”来反映数据元素之间逻辑上的相邻关系,采用这种存储方式的线性表又称为顺序表。 顺序表有以下特征。 (1) 线性表的所有元素所占的空间是连续的。 (2) 线性表中各个数据元素在存储空间中是按照逻辑顺序依次存放的。 由于线性表中的所有数据元素都是同一数据类型,所以每个元素在存储器中占用的空间(字节数)相同。只要知道了第1个数据元素a1的存储地址和它所占有的存储单元个数,即可求得第i个数据元素ai的地址。假定第一个元素a1的地址为LOC(a1),每个数据元素占k个字节,则第i个数据元素ai的地址是： LOC(ai)=LOC(a1)+(i－1)×k(1≤i≤n) 例如：第2个数据元素a3的地址是LOC(a2)=LOC(a1)+k 第3个数据元素a3的地址是LOC(a3)=LOC(a1)+2k …… 第i个数据元素ai的地址是LOC(ai)=LOC(a1)+(i－1)×k 顺序表的顺序存储结构如图21所示。 图21顺序表的顺序存储示意图 由于线性表中的数据元素都是按照逻辑关系进行存储的，所以只要确定了顺序表的起始位置，线性表中的任一数据元素都可以随机存取，因此线性表的顺序存储结构是一种“随机存取”的存储结构。 顺序表在具体实现时,一般用高级语言中的数组来对应连续的存储空间。设最多可存储MaxSize个元素,在C语言中可用数组data\[MaxSize\]来存储数据元素,为保存线性表的长度需定义一个整型变量length。线性表的第l,2,…,n个元素分别存放在此数组下标为0,1,…,length-1数组元素中,如图21所示。 在C语言中,可用下述类型定义来描述线性表。 #defineMaxSize100/*顺序表的容量*/ typedefintDataType;/*在应用中,将实际数据类型定义成DataType */ typedefstruct{ DataTypedata\[MaxSize\];/*定义存储表元素的数组*/ intlength;/*顺序表的实际长度*/ }SeqList; /*顺序表数据类型说明*/ SeqList *L;/*定义一个顺序表类型的指针变量L*/ 在使用一维数组存放线性表时,通常定义的数组的空间要比实际表稍长大一些,以便对线性表进行各种运算,特别是对线性表的插入运算。一般情况下,应该尽可能考虑到使用的线性表可能达到的最大长度,如果定义的存储空间过小,则在线性表动态增长时可能会出现存储空间不够而无法插入新的元素的情况；如果存储空间过大,而实际又没有用到那么大的存储空间,则会造成存储空间的浪费。在实际应用中,可以根据线性表动态变化过程中的一般规模来决定开辟存储空间量,设置足够的数组长度,以备扩展。
2.2.2顺序表上基本运算的实现
1. 顺序表L的初始化 顺序表的初始化即构造一个空表,顺序表是否为空取决于其数据元素个数是否为0,因此,只要将表L的长度设置为0即可构造出一个空表。 算法21顺序表的初始化。 void InitList(SeqList *L)/*顺序表的初始化即将表的长度置为0*/ { L-＞length=0; } 该算法的时间复杂度为O(1)。
2. 创建一个顺序表L 算法22创建一个元素为整型数的顺序表,元素不包括0,遇到0时表示输入结束。顺序表长度由用户输入的数据来决定。 void CreatList(SeqList *L) { int k=0;/*计数*/ DataType x; scanf("%d",&x); while(x!=0)/*依次从键盘输入顺序表元素,遇到0结束。*/ { L->data\[k\]=x; k++; scanf("%d",&x); } L->length=k; } 该算法的时间复杂度为O(n),其中n为该顺序表中元素个数的规模。 思考： 若顺序表长度为固定值,如何创建顺序表？
书单推荐
