手册之数据结构.pdf

数据结构数据结构 目录目录第第 1 章章 数据结构基本概念数据结构基本概念.4 1.1 基本概念.4 1.2 算法和算法复杂性分析.4 第第 2 章章 线性表线性表.5 2.1 线性表的定义.5 2.2 线性表的实现.5 第第 3 章章 栈、队列和数组栈、队列和数组.13 3.1 栈.13 3.2 队列.14 3.3 特殊矩阵的压缩存储.16 第第 4 章章 树与二叉树树与二叉树.18 4.1 树的概念.18 4.2 二叉树.19 4.3 树和森林.23 4.4 树的应用.25 第第 5 章章 图图.29 5.1 图的概念.29 5.2 图的存储及基本操作.31 5.3 图的遍历.32 5.4 图的基本应用.32 5.4.3 拓扑排序.34 第第 6 章章 查找查找.366.1 查找的基本概念.366.2 顺序查找法.366.3 折半查找法.366.4 B 树及其基本操作、B-、B+树的基本概念.376.5 散列表.38第第 7 章章 排序排序.397.1 排序的基本概念.39 7.2 插入排序.40 7.4 简单选择排序.41 7.5 希尔排序.41 7.6 快速排序.41 7.7 堆排序.42 7.8 二路归并排序.42 7.9 基数排序.43 7.10 外部排序.43 7.11 各种内部排序算法的比较.44 第第 8 章章 总结总结.45 第第 1 章章 数据结构基本概念数据结构基本概念 1.1 基本概念基本概念1、数据结构 数据结构是指互相之间存在着一种或多种关系的数据元素的集合。数据结构是一个二元组 Data_Structure（D，R），其中，D 是数据元素的有限集，R 是 D 上关系的有限集。2、逻辑结构：是指数据之间的相互关系。通常分为四类结构：（1）集合：结构中的数据元素除了同属于一种类型外，别无其它关系。（2）线性结构：结构中的数据元素之间存在一对一的关系。（3）树型结构：结构中的数据元素之间存在一对多的关系。（4）图状结构：结构中的数据元素之间存在多对多的关系。3、存储结构：是指数据结构在计算机中的表示，又称为数据的物理结构。通常由四种基本的 存储方法实现：（1）顺序存储方式。数据元素顺序存放，每个存储结点只含一个元素。存储位置反映数据元 素间的逻辑关系。存储密度大。但有些操作（如插入、删除）效率较差。（2）链式存储方式。每个存储结点除包含数据元素信息外还包含一组（至少一个）指针。指针反映数据元素间的逻辑关系。这种方式不要求存储空间连续，便于动态操作（如插入、删 除等），但存储空间开销大（用于指针），另外不能折半查找等。（3）索引存储方式。除数据元素存储在一组地址连续的内存空间外，还需建立一个索引表，索引表中索引指示存储结点的存储位置（下标）或存储区间端点（下标）。（4）散列存储方式。通过散列函数和解决冲突的方法，将关键字散列在连续的有限的地址空 间内，并将散列函数的值解释成关键字所在元素的存储地址。其特点是存取速度快，只能按关键字随机存取，不能顺序存取，也不能折半存取。1.2 算法和算法复杂性分析算法和算法复杂性分析1、算法是对特定问题求解步骤的一种描述，是指令的有限序列。其中每一条指令表示一个或 多个操作。算法具有下列特性：有穷性确定性可行性输入输出。2、算法的时间复杂度：以基本运算的原操作重复执行的次数作为算法的时间度量。一般情况下，算法中基本运算次数 T(n)是问题规模 n（输入量的多少，称之为问题规模）的某个函数 f(n)，记作：T(n)(f(n)也可表示 T(n)m(f(n)，其中 m 为常量。记号“O”表示随问题规模 n 的增大，算法执行时间 T(n)的增长率和 f(n)的增长率相同。常见的渐进时间复杂度有：(1)(log2n)(n)(nlog2n)(n2)(n3)(2n)O(n!)O(nn)。3、算法的空间复杂度：是对一个算法在运行过程中临时占用的存储空间大小的量度。原地工作：若所需额外空间相对于输入数据量来说是常数，则称此算法为原地工作，空间复杂度为O(1)。第第 2 章章线性表线性表2.1 线性表的定义线性表的定义线性表定义如下：线性表是具有相同数据类型的 n(n0)个数据元素的有限序列，通常记为：(a1，a2，ai-1，ai，ai+1，an)其中 n 为表长，n0时称为空表。ai为序号为 i的数据元素（i=1,2,n），通常将它的数据类型抽象为 ElemType，ElemType 根据具体问题而定。2.2 线性表的实现线性表的实现2.2.1 线性表的顺序存储结构1、顺序表 线性表的顺序存储是指在内存中用地址连续的一块存储空间顺序存放线性表的各元素，称其为顺序表。2、顺序表上基本运算的实现（1）顺序表的初始化 顺序表的初始化即构造一个空表，将 L 设为引用参数，首先动态分配存储空间，然后，将 length 置为 0，表示表中没有数据元素。Status Init_SqList(SqList*L)L-elem_array=(ElemType*)malloc(MAX_SIZE*sizeof(ElemType);if(!L-elem_array)return ERROR;else L-lengreturn OK;th=0;（2）插入运算线性表的插入是指在表的第 i(i 的取值范围：1in+1)个位置上插入一个值为 x 的新元素，插入后使原表长为 n 的表:(a1，a2，.，ai-1，ai，ai+1，.，an)成为表长为 n+1 表:顺序表上的插入运算，时间主要消耗在了数据的移动上，在第 i 个位置上插入 x，从 ai到 an都要向下移动一个位置，共需要移动 ni1 个元素。Status Insert_SqList(Sqlist*L，int i，ElemType e)int j;if (iL-length-1)return ERROR;if (L-length=MAX_SIZE)printf(“线性表溢出!n”);return ERROR;for (j=L-length1;j=i-1;-j)L-Elem_arrayj+1=L-Elem_arrayj;/*i-1 位置以后的所有结点后移*/L-Elem_arrayi-1=e;/*在 i-1 位置插入结点*/L-length+;returnOK;（3）删除运算线性表的删除运算是指将表中第 i（i的取值范围为：1 in）个元素从线性表中去掉，删除后使原表长为 n的线性表：(a1，a2，.，ai-1，ai，ai+1，.，an)成为表长为 n1的线性表。顺序表的删除运算与插入运算相同，删除第 i 个元 素时，其后面的元素 ai+1an都要向上移动一个位置，共移动了 n-i 个元素，在尾端插入、删除效率高 O(1)。ElemType Delete_SqList(Sqlist*L，int i)int k;ElemType x;if (L-length=0)printf(“线性表 L 为空!n”);return ERROR;else if(iL-length)printf(“要删除的数据元素不存在!n”);return ERROR;else x=L-Elem_arrayi-1;/*保存结点的值*/for(k=i;klength;k+)L-Elem_arrayk-1=L-Elem_arrayk;/*i 位置以后的所有结点前移 */L-length-;return(x);2.2.2 线性表的链式存储结构 2.2.2.1 单链表 1、链表表示 链表是通过一组任意的存储单元来存储线性表中的数据元素。单链表的结点结构：SP1234每个结点除了存储数据元素本身信息的数据域外，只有一个指针域用来存放其直接后继数据元素的存储地址。通常用“头指针”来标识一个单链表，头指针为“NULL”则表示一个空表。2、单链表上基本运算的实现(1)建立单链表头插法在链表的头部插入结点建立单链表 链表一种动态管理的存储结构，链表中的每个结点占用的存储空间 不是预先分，建立单链表从空表开始，每读入一 个数据元素则申请一个结点，然后插在链表的头部。LNode *create_LinkList(void)/*头插入法创建单链表 链表的头结点 head 作为返回值*/,int data;LNode*head,*p;head=(LNode *)malloc(sizeof(LNode);head-next=NULL;/*创建链表的表头结点 head */while(1)“”scanf(%d,&data);if(data=32767)break;p=(LNode *)malloc(sizeof(LNode);pdata=data;/*数据域赋值*/pnext=headnext;headnext=p;/*钩链，新创建的结点总是作为第一个结点*/return(head);尾插法在单链表的尾部插入结点建立单链表。每次是将新结点插入到链表的尾部，加入 一个指针 r 用来始终指向链表中的尾结点，以便能够将新结点插入到链表的尾部。初始状态，头指针 L=NULL，尾指针 r=NULL;按线性表中元素的顺序依次读入数据元素，不是结束标志时，申请结点，将新结点插入到 r 所指结点的后面，然后 r 指向新结点。LNode*create_LinkList(void)/*尾插入法创建单链表 链表的头结点 head 作为返回值*/,int data;LNode*head,*p,*q;head=p=(LNode *)malloc(sizeof(LNode);p-/*next=NULL;创建单链表的表头结点 head */while(1)“”scanf(%d,&data);if(data=32767)break;q=(LNode *)malloc(sizeof(LNode);qdata=data;/*数据域赋值*/qnext=pnext;pnext=q;p=q;/*钩链，新创建的结点总是作为最后一个结点*/return(head);(2)查找操作按序号查找从链表的第一个元素结点起，判断当前结点是否是第 i 个，若是，则返回该结点的指针，否则继续后一个，表结束为止，没有第个结点时返回空。ElemType Get_Elem(LNode*L，int i)int j;LNode*p;p=L-next;j=1;/*使 p 指向第一个结点*/while (p!=NULL&jnext;j+;/*移动指针 p,j 计数*/if (j!=i)return(-32768);else return(p-data);/*p 为 NULL 表示 i 太大;ji 表示 i 为 0 */(3)插入运算后插结点：设 p 指向单链表中某结点，s 指向待插入的值为 x 的新结点，将*s 插入到*p 的后面。void Insert_LNode(LNode*L，int i，ElemType e)/*在以 L 为头结点的单链表的第 i 个位置插入值为 e 的结点*/int j=0;LNode*p，*q;p=Lnext;while (p!=NULL&jnext;j+;if (j!=i-1)printf(“i 太大或 i 为 0!n”);else q=(LNode*)malloc(sizeof(LNode);qdata=e;qnext=pnext;pnext=q;(4)删除运算删除结点 设 p 指向单链表中某结点，删除*p。要实现对结点*p 的删除，首先要找到*p 的前驱结点*q，然后完成指针的操作即可。void Delete_LinkList(LNode*L，int key)/*删除以 L 为头结点的单链表中值为 key 的第一个结点*/LNode*p=L,*q=Lnext;while (q!=NULL&qdata!=key)p=q;q=qnext;if (qdata=key)p-next=q-next;free(q);else printf(“所要删除的结点不存在!n”);（5）单链表的合并设有两个有序的单链表，它们的头指针分别是 La、Lb，将它们合并为以 Lc