数据结构-C 语言描述

数据结构——C语言描数据结构——C语言描 主 C91的综述；第2章至第7章分别介绍了线性表、栈、队列、串、多维数组广义表、树和图等几种基本的数据结构；第8章和第9章分别介绍了查找图书在版编目（CIP）数据结构：C语言描述/王国钧主编.—北京：科学出（面向21世纪高等院校计算机系列规划教材ISBN7-03-016077-Ⅰ.数… Ⅱ.王… Ⅲ.数据结构-高等学校-教材Ⅳ.TP311.12中国版本图书馆CIP数据核字（2005）第088632号责任编辑：吕建 赵卫江／责任校对：刘彦责任印制：吕春珉／封面设计：飞天创出版北京东黄城根北街16双青印刷厂印科学出版社发行各地新华书店经*2005年8月第一 开本：787×10922006年8月第二次印 印张：16印数：3501－5 字数：376定价：22.00（如有印装质量问题，我社负责调换<环伟销售部电辑部电 本书共91章为概论2章至第4章分别介绍了线性表、栈、队列和串几种基本的数据结构，它们都属于线性结构5章至第7章分别介绍了多维数组义表、树和图等非线性结构；第8章和第9章分别介绍了查找和排序，它们都是数据处和详尽的注释，自始至终使用C语言来描述算法和数据结构，各章的程序都在TurboC或VisualC++6.0中调试通过，以方便读者在计算机上进行实践，有助于理解算法的实另外，本书也可供从事计算机应用的工程技术人员参考，读者只需掌握C语言编程为了方便教学，本书配有教学课件，可在科学出版社网站wcecm）载。由于编者水平有限，因此书中错误难免，殷切希望广大读者批评指正若需与编者交换意见，或索要部分习题参考解答，请发函至下列E-mail信箱 20055 第1 数据和数据元 数据对象和数据类 数据结 学习数据结构的重要 数据结构的应用举 什么是算 算法的描述和设 算法分 第2 线性表的定 线性表的基本操 顺序 顺序表的基本操 一个完整的例子 单链表的基本概 单链表的基本操 一个完整的例子 循环链 双向链 双向循环链 静态链 约瑟夫问 多项式加 电文加 数据结构——C 第3 栈的定义与基本操 顺序栈的存储结构和操作的实 链栈的存储结构和操作的实 数制转 括号匹配问 子程序的调 利用一个栈逆置一个带头结点的单链 队列的定义与基本操 链队列的存储结构和操作的实 顺序队列的存储结构和操作的实 打印杨辉三角 迷宫问题：寻找一条从迷宫入口到出口的最短路 *第4章 串的定 串的基本操 串的定长顺序存 串的堆存储结 串的块链存储结 基本的模式匹配算 模式匹配的改进算法——KMP算 第5 多维数组的定 数组的存储结 目录v目录v特殊矩 稀疏矩 第6 树的定 树的一些基本慨 树的基本操 二叉树的定义和基本操 二叉树的性 二叉树的存储结 二叉树的遍 线索二叉 基于遍历的应用与线索二叉树的应 树的存储结 树、森林和二叉树之间的转 树和森林的遍 与哈夫曼树相关的基本概 哈夫曼树的应 哈夫曼编码算法的实 第7 图的定 图的相关术 邻接矩阵表示 邻接表表示 深度优先搜索 数据结构——C广度优先搜索 非连通图的遍 生成树的概 构造最小生成树的普里姆（Prim）算 构造最小生成树的克鲁斯卡尔(Kruskal)算 从某个源点到其余各顶点的最短路 每一对顶点之间的最短路 第8 查找表和查 查找表的数据结构表 平均查找长度 顺序查 二分查 分块查 二叉排序 B- B-树上的基本运 散列表的概 散列函数的构造方 处理冲突的方 散列表上的运 第9 关键字与排 排序的稳定 排序方法的分 排序算法性能评 不同存储方式的排序过 目录目录直接插入排 希尔排 冒泡排 快速排 直接选择排 堆排 多关键字的排 链式基数排 第1 本章要 什么是数据结 为什么要学习数据结 算法和算法分本章学习目 了解数据结构的基本概念，理解常用术 掌握数据元素间的4类结构关 掌握算法的定义及特性，掌握算法设计的要 初步掌握分析算法的时间复杂度和空间复杂度的方 数据结构——C语言描数据和数据元数据（da）是信息的载体，是对客观事物的符号表示，它能够被计算机识别、存数据的范畴。数据元素（dataelement）是数据的基本单位，通常在计算机程序中作为一个整体进数据对象和数据类数据对象（dataobjec）是性质相同的数据元素的集合，它是数据的一个子集。例如，整数数据对象是集合N={01，±2，±3，…；大写字母字符数据对象是集合C=N1应该是上述集NN1={012±xntxint是依赖于所使用的计算机和语言的最大整数。数据类型（datatype）是计算机程序中的数据对象以及定义在这个数据对象集合上的一组操作的总称。例如，C语言中的整数类型是区间-maxint，maxint]上的整数，在提供的，如C语言中的整型、实型、字符型等；结构数据类型是利用计算机语言提供的一种描述数据元素之间逻辑关系的机制由用户自己定义而成的C语言中的数组类数据结数据结构（datastructure）是指数据对象以及该数据对象集合中的数据元素之间的数据元素的组织形式一般包含下列内容列4类（见图1.1）。①集合：其中的数据元素之间除了“属于同一个集合”的关系以外，别无其他②线性结构：其中的数据元素之间存在一对一的关系第1 图 4类基本逻辑结构关③树型结构：其中的数据元素之间存在一对多的关系④图状结构（或称网状结构）：其中的数据元素之间存在多对多的关系由于数据的逻辑结构是从逻辑关系上描述数据，它独立于计算机，与数据的存储C语言描述的算法来实现。例 学生成绩表（见表1.1）是一个数据结构学生成绩学姓高等普通平均陈小马丽林春王澄######张吉表1.1（或记录），由学号、姓名、（或字段（又称直接前驱（又称直接后继 数据结构——C语言描“马丽丽”所在结点的直接前驱结点是“陈小洁”结点，其后继结点是“林春英”结点，上述结点之间的关系构成了这张学生成绩表的逻辑结构。其次，表1.1的存储结构是指用计算机语言如何表示各结点之间的这种关系，也就第三，在表1.1中，经常要查看一些学在不会产生混淆的前提下，可以将数据的逻辑结构简称为数据结构。本书的第2到第4章介绍的都是线性结构，第5章到第7章介绍的都是非线性结构数据的存储结构可采用以下4种基本的存储方法得到顺序存储方该方法主要应用于线性的数据结构，而非线性的数据结构可以通过某种线性化的法来实现顺序存储链接存储方索引存储方称为索引项。索引项的一般形式是：（关键字，地址），所谓关键字（ky）是指能够组结点的起始存储位置。散列存储方该方法的基本思想是根据结点的关键字直接计算出该结点的存储地址上述4种基本的存储方法，既可以单独使用，也可以组合起来对数据结构进行存储第1 需需要指出的是，不管怎样定义数据结构，都应该将数据的逻辑结构、数据的存储学习数据结构的重要数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之要想更有效地使用计算机，就必须学习数据结构的有关知识。约占用了90%以上的计算机时间。由于非数值计算问题所涉及的数据结构更为复杂，数Nrh数据结构的应用举例 电话号码的查询问题66数据结构——C序，另外构造一张姓氏索引表，存储结构如图.2更为有效。在第8章中将进一步讨论查找策略。图 电话号码查询问题的索引存例 n个城市之间铺设光缆的问题假设需要在nnn1n数学模型是如图1.（图n中选取n1n“求图的最小生成树”的问题，见图1.3（b），将在第7图 图及其最小生成树示第1 什么是算算法（algorithm）是对特定问题求解步骤的一种描述，它是指令的有限序列，其每一条指令表示一个或多个操作。此外，一个算法还具有下列5个特性有穷性。一个算法必须在执行有穷步之后结束，即算法必须在有限时间内完成确定性。算法中每一步必须有确切的含义，不会产生二义性。并且，在任何条件下，算法只有唯一的一条执行路径，即对于相同的输入只能得出相同的输出。可行性。一个算法是可行的，即算法中的每一步都可以通过已经实现的基本运算执行有限次得以实现。输入。一个算法有零个或多个输入，它们是算法开始时对算法给出的初始量输出。一个算法有一个或多个输出，它们是与输入有特定关系的量算法的描述和设算法是一个十分古老的研究课题，然而计算机的出现为这个课题注入了青春和活助，许多过去靠人工无法计算的复杂问题都有了解决的希望。一个算法可以采用自然语言、数学语言或者约定的符号语言（如伪码、框图等）88数据结构——C描述。为了方便读者的阅读和实践，本书中的算法和数据结构均使用C语言来描述。C语言遵照NICroC或Vsual++6.0中调试通过。对书中采用的一些预定义常量，简要说明如下#defineTRUE1#defineFALSE#defineOK#defineERROR其他有关C语言的知识，请参考专门介绍C语言的书籍在例1.2中，我们介绍了电话号码的查询问题的两种算法，那么如何来评价这些算正确性——算法应当满足具体问题的需求健壮性——当输入数据非法时，算法也能适当地做出反应或进行处理，而不会产生莫明其妙的输出结果或出错信息，并中止程序的执行。可读性——算法主要是为了方便人们的阅读和交流，其次才是机器执行执行算法所耗费的时间执行算法所耗费的存储空间，其中主要考虑辅助存储空间算法分的就是程序所用算法在运行时所要花费的时间代价和程序中使用的数据结构所占有的空间代价。通常就称为时间复杂度（时间代价）和空间复杂度（空间代价）。算法的时间复杂度分当需要解决的问题的规模（以某种单位计算）由1增至n时，解决问题的算法所耗费的时间也以某种单位由f(1)增至f(n)，这时就称该算法的时间代价为f(n)。型的操作（或算法类型“原该语句重复执行的次数。1.4有下列三个程序段（2）for(i=1;i<=n;i++){x=x+1;（3）for(j=1;j<=n;for(k=1;k<=n;k++){x=x+1;第1 它们含基本操作“x加1”的语句的频度分别为1、n和n2例1.5对n个记录进行升序排序的问题，采用最简单的选择排序方法每次处理时，先从n个未排序的记录中选出一个最小记录，则第一次要经过n-1次比较，才能选出最小记录；第二次再从剩下的n-1个记录中经过n-2次比较，选出次小记录……如此反复，直到只剩两个记录时，经过1次比较就可以确定它们的大小。整个(n-1)+(n-2)+…+1=n×(n-在同一个算法处理两个规模相同的问题，所花费的时间和空间代价也不一定相同。（即对同样规模的问题所花费的人们通常采用大O表示法来描述算法分析的结果。如果存在正的常数M和n0，当问题的规模n≥n0后，算法的时间量度T(n)≤Mf(n)那么就称该算法的时间复杂度为O(f(n))。这种说法意味着：当n充分大时，该算法的时间复杂度不大于f(n)的一个常对于例1.4的程序段（1）来说，其时间复杂度为O(1)，程序段（2）的时间复杂度为O(n)，程序段（3）的时间复杂度为O(n2)；而对于例1.5的选择排序方法来说，其时间复杂度为O(n2)。算法另外还可能呈现的时间复杂度有：O(log2n)和O(2n)等。通常c<log2n<n<nlog2n<n2<n3<10其中，c是与n无关的任意常数。上述函数排序与数学中对无穷大的分级完全一致，因为考虑的也是n值变化过程中的趋势，参见图1.4。图 常见函数曲线变化速度的比较数据结构——C1.6要交换变量xy中的内容，其程序段为temp=x;x=y;由于以上3条语句的频度均为1，说明该程序段的执行时间是一个与问题规模n无关的常数，因此，算法的时间复杂度为O(1)。1.7程序段如下for((i=1;i<=n;i++)for(j=1;j<=n;j++)for(k=1;k<=n;k++)在此程序段中，因为含基本操作“x加1”的语句“x++;”的频度是n3，所以该序段的时间复杂度为O(n3)算法的空间复杂度分与算法的时间复杂度类似，可以定义算法的空间复杂度如下：如果存在正的常数M和n0，当问题的规模n≥n0后，算法的空间量度S(n)M·f(n)那么就称该算法的空间复杂度为O(f(n))。数据的表示形式有关（见第8章1.8求例1.5中选择排序方法的空间复杂度一个中间变量（temp）的存储空间，这是与问题规模n无关的常数，因此，选择排序方法的空间复杂度为O(1)。够区分算法与程序的异同，了解怎样的算法才是一个“好”的算法，并学会利用时间本章小结的内容：数据的逻辑结构，数据的存储结构，数据的运算。讨论了数据逻辑结构的4第1 基本结构关系，以及数据存储的4种基本方法。读者学习这些内容后，希望能对数据结算法和数据结构密切相关，不可分割。本章介绍了算法的定义和5个特性，讨论了本书使用C语言来描述算法和数据结构，以方便读者在计算机上进行实践活动 一、填空数据的逻辑结构是数据元素之间的逻辑关系，通常有下列4类 数据的存储结构是数据在计算机存储器里的表示，主要有4种基本存储方法 二、选择一个算法必须在执行有穷步之后结束，这是算法的 ）正确 B.有穷C.确定 D.可行也就是说对于每步需要执行的动作必须严格、清楚地给出规定，这是算法的（ ）。正确 B.有穷C.确定 D.可行序列”，其中的每一步都是我们力所能及的一个动作，这是算法的（ ）。正确 B.有穷C.确定 D.可行三、简答算法与程序有何异同什么是数据结构？试举一个简单的例子说明什么是数据的逻辑结构？什么是数据的存储结构什么是算法？算法有哪些特性四、算法分析将下列复杂度由小到大重新排序：2n、n!、n2、10000、log2n、nlog2n用大O表示法描述下列复杂度 （2）6（3）3n4+n （4）nlog2n+n数据结构——C设n为正整数，请用大O表示法描述下列程序段的时间复杂度（1）i=1;k=0; （2）i=0;k=0; {k=k+10*i; （3）i=1;j=0; {if(i>j) else}（5）for((i=1;i<=n;i++) for(j=1;j<=i;j++) for(k=1;k<=j;k++) {if(x>100){x-=10;y--;}x+=c;(c为常数) elsex++;}第2 线性本章要令线性表的基本概念令线性表的顺序存储令线性表的链式存令线性表两种不同存储结构的比令线性表的应本章学习目 掌握单链表上的基本运 掌握循环链表、双向链表和静态链表的概 学会利用线性表来解决问 数据结构——C线性结构是指结构中的数据元素之间存在一对一的关系。线性结构的基本特征是①有而且只有一个“第一元素”②有而且只有一个“最后元素”③除第一元素之外，其他元素都有唯一的直接前驱④除最后元素之外，其他元素都有唯一的直接后继线性表是一种常用的简单的数据结构，它属于线性结构的范畴例2.1 26个大写英文字母表（A,B,C,…,Z）就是一个线性表，表中的每一个字母例2.2 第1章例1.1中的学生成绩表（表1.1），也是一个线性表，其中每个学生综上所述，线性表可以描述如下线性表的定(a1,a2,…,ai-1,ai,ai+1,…,其中，数据元素的个数n称为线性表的长度。当n＝0时称为空表始结点（第一元素）a1，它没有直接前驱，只有一个直接后继a2；有而且只有一个终端结点（最后元素）an，它没有直接后继，只有一个直接前驱an-1；而除了a1和an外，其他的每一个结点ai（2≤i≤n-1）都有而且只有一个直接前驱ai-1和一个直接后继ai+1。例2.3例2.1中介绍的26个大写英文字母表（A,B,C,…,Z）的表长是26，在该表中，起始结点A没有直接前驱，A的唯一直接后继是B；终端结点Z没有直接后继，Z的唯一直接前驱是Y；而对于B,C,D,…,Y中的任意一个字母，都有一个唯一的直接前线性表的基本操设线性表L=(a1,a2,…,an)，则可以定义以下基本操作：1）InitList(L)：初始化操作，置L为空线性表。ClearList(L)：清除线性表的内容，将L置为空表ListLength(L)：求表长Ins(L，i，Item)：插入数据。把Item插入到表L的第i个位置，表长加1；如果i<1或i>ListLength(L)+1，则插入不成功。Del(L，i)：删除数据。如果1≤i≤ListLength(L)，则删除第i个数据，线性表的长度减1，返回TRUE；否则，删除不成功，返回FALSE第2 线性 GetNode(L，i)：获取表L中第i(1≤i≤ListLength)个结点的值。7）Loc(L，Item)：定位(按值查找)。如果表L中存在一个值为Item的结点，则返该结点的位置；若表L中存在多个值为Item的结点，则返回第一次找到的结点位置；若表L中不存在值为Item的结点，则返回0。8）GetNext(L，Item，p)：获取后继结点。首先找到Item所在的位置，然后把的后继结点的值赋给p；若成功，则返回TRUE；否则，返回FALSE。9）GetPrior(L，Item，p)：获取前驱结点。首先找到Item所在的位置，然后把Item顺序C组来描述顺序表的。例2.4一个顺序存储结构的线性表（顺序表）的示例typedef{charname[20];charno[10];floatscore;STUDENT则s就是一个以STUDENT类型为数据元素的线性表假设线性表L的每个元素需占用m个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置，则线性表中第i+1个数据元素的存储位置LOC(ai+1)和第i个数据元素的存储位置LOC(ai)之间满足如下关系： 线性表L的第i个元素的存储位置和第一个元素的存储位置的关系为LOC(ai)=LOC(a1)+(i-1) 其中LOC(a1)是线性表的第一个数据元素a1的存储位置，通常称为线性表的起始位顺序表的特点是以元素在计算机内部存储的物理位置相邻来表示线性表中数据元2.2地址，就能计算出该数据元素的直接前驱和直接后继的地址，计算公式见式（2.1）。 数据结构——C例2.5 在例2.4的线性表s中，如果设第一个数据元素的地址为b，则可以得出如图2.1所示的存储结构图。注意：s中每一个数据元素所占的存储单元为20+10+4=34图 线性表s的顺序存储结构顺序表的基本操现在利用C语言来描述一个顺序表，由于表的长度通常是可变的，因此需要定义一typedefintdatatype; /*定义数据元素的类型，这里假设为int*/#definemaxsize1024 /*线性表的最大长度，这里假设为1024*/typedefstruct datatypeint /*表长其中，数据域data是存放线性表结点的一个数组，数组下标范围为0～maxsize-1。length是线性表的长度。顺序表的初始算法 构造一个空的顺序表voidInitList(sequenlist*L/*构造一个空的顺序表，只需要把表长度置为0{/*L是sequenlist类型的指针变量L /*0}存取第i个数据元素，只需要知道线性表的基地址就可以了。需要注意的是，在C语言第第2 线性 其中，m是数据元素所占的单元数目。清除线性表的内长置为0。算法 清除一个已经存在的线性表的内容voidClearList(sequenlist{L-}本算法时间复杂度为O(1)定位(按值查找则返回。算法 定位（按值查找）intLoc(sequenlistL，datatype{intj=L.length;/*取出线性表的长度*/ /*空表*/returnFALSE;{if(L.data[i]==Item)/*找到Item*/returni; /*返回找到的位置*/}printf(″找不到该return0;/*没有找到0}本算法中，可能找到Item，这时平均比较次数为O(n/2)，其中，n是线性表的长度；也可能找不到Item，这时算法的比较次数为O(n)。因此，本算法的时间复杂度为O(n)插入数要在线性表中第i个位置插入一个数据元素Item，需要考虑以下因素i是否在1和L.length之间，如果是，则先将原来的第i个位置及以后的数据元素向后移动一个位置，然后把Item插入到第i个位置，再将线性表长度加1，返回TRUE；如果i不在1和L.length之间，则说明插入位置不合适，返回FALSE，如图2.2所示。 数据结构——C插入…ai……插入…ai……图 在顺序表中插入结点的示意算法 插入数据intIns(sequenlist*L，inti，datatype{/*在顺序表*L的第i个位置插入新结点*/intj;if(i<1||i>L-returnFALSE； /*位置不合适*/L->data[j]=L->data[j-1];/*结点后移L->data[i- /*1*/returnTRUE;}数为(n/2)，其中，n是线性表的长度。因此，本算法的时间复杂度为O(n)。注意:本算法最直观的思考方法是从前向后移动数据，也就是用语句for(j=i;j<=L-L->data[j+1]=L-这个算法是不正确的，因为前面的值会把后面的值覆盖删除数删除数据和插入数据很相似，都要求判断i的值是否合适，如果位置合适，则把后面的数据向前移动，删除成功，表的长度减1，返回TRUE，否则，返回FALSE。如所示图 在顺序表中删除结点的示意第第2 线性算法 删除数据intDel(sequenlist*L，int{/*删除顺序表*L中的第i个结点*/intj;if(i<1||i>L->length)/*位置不合适returnFALSE；L->data[j]=L->data[j+1];/*结点前移 /*表长减1*/returnTRUE；}一个完整的例子例6 编制C程序，利用顺序存储方式来实现下列功能：根据键盘输入数据建立一个线性表并输出该线性表然后根据屏幕菜单的选择可以进行数据的插入或删除并在插入或删除数据后再输出线性表最后在屏幕菜单中选择Q或q的运行。程序如下：#include"stdio.h" #include"malloc.h"#definemaxsize1024typedefchardatatype;typedefstruct datatypedata[maxsize];intlast;/*在第i个元素前插入元素x（注意：元素从0始计数）*/intinsert(sequenlist*L,datatypex,inti) intif(L->last==maxsize- /*如果原线性表已满{printf("overflow");return0;}elseif(i<0)||(i>L /*如果输入的i值超出范围{printf("error,pleaseinputtheright'i'");return0;}{for(j=L->last;j>=i;j--)/*从第i个元素起,