数据结构c语言版严蔚敏PPT .ppt

《数据结构c语言版严蔚敏PPT .ppt》由会员分享，可在线阅读，更多相关《数据结构c语言版严蔚敏PPT .ppt（814页珍藏版）》请在装配图网上搜索。

1、算法与数据结构 教材 ： 数据结构 (C语言版 ) 。严蔚敏，吴伟民 编 著。清华大学出版社。 参考文献 ： 1 数据结构 。张选平，雷咏梅 编， 严蔚敏 审。 机械工业出版社。 2 数据结构与算法分析 。 Clifford A. Shaffer著， 张 铭，刘晓丹 译。电子工业出版社。 3 数据结构习题与解析 (C语实言版 ) 。李春葆。 清华大学出版社。 4 数据结构与算法 。夏克俭 编著。国防工业出 版社。 第 1章 绪 论 目前，计算机已深入到社会生活的各个领域，其应 用已不再仅仅局限于科学计算，而更多的是用于控制， 管理及数据处理等非数值计算领域。计算机是一门研究 用计算机进行信息表

2、示和处理的科学。这里面涉及到两 个问题：信息的 表示 ，信息的 处理 。 信息的表示和组织又直接关系到处理信息的程序的 效率。随着应用问题的不断复杂，导致信息量剧增与信 息范围的拓宽，使许多系统程序和应用程序的规模很大， 结构又相当复杂。因此，必须分析待处理问题中的对象 的特征及各对象之间存在的关系，这就是数据结构这门 课所要研究的问题。 编写解决实际问题的程序的一般过程 ： 如何用数据形式描述问题 ?即由问题抽象出一个 适当的数学模型 ; 问题所涉及的数据量大小及数据之间的关系 ; 如何在计算机中存储数据及体现数据之间的关系 ? 处理问题时需要对数据作何种运算 ? 所编写的程序的性能是否良好

3、 ? 上面所列举的问题基本上由数据结构这门课程来回答。 计算机求解问题的一般步骤 1.1 数据结构及其概念 算法与数据结构 是计算机科学中的一门综合性 专业基础课。是介于数学、计算机硬件、计算机软件三 者之间的一门核心课程，不仅是一般程序设计的基础， 而且是设计和实现编译程序、操作系统、数据库系统及 其他系统程序和大型应用程序的重要基础。 1.1.1 数据结构的例子 姓名 电话号码 陈海 13612345588 李四锋 13056112345 。 。 例 1：电话号码查询系统 设有一个电话号码薄，它记录了 N个人的名字和其 相应的电话号码，假定按如下形式安排： (a1, b1)， (a2, b

4、2)， (a n, bn)， 其中 ai, bi(i=1， 2n) 分别表示某人的 名字和电话号码。 本问题是一种典型的表格问题 。 如 表 1-1，数据与数据成简单的一对一的 线性关系 。 表 1-1 线性表结构 例 2：磁盘目录文件系统 磁盘根目录下有很多子目录 及文件，每个子目录里又可以包 含多个子目录及文件，但每个子 目录只有一个父目录，依此类推 ： 本问题是一种典型的树型结 构问题，如图 1-1 ，数据与数据 成一对多的关系，是一种典型的 非线性关系结构 树形结构 。 图 1-1 树形 结构 例 3：交通网络图 从一个地方到另外一个地方可以有多条路径。本问 题是一种典型的 网状结构

5、问题，数据与数据成多对多的 关系，是一种非线性关系结构。 佛山 惠州 广州 中山 东莞 深圳 珠海 图 1-2 网状结构 数据 (Data) ：是客观事物的符号表示。在计算机科 学中指的是所有能输入到计算机中并被计算机程序处理 的符号的总称。 数据元素 (Data Element) ：是数据的基本单位，在 程序中通常 作为一个整体 来进行考虑和处理。 一个数据元素可由若干个 数据项 (Data Item)组成。 数据项是数据的不可分割的最小单位。数据项是对客观 事物某一方面特性的数据描述。 数据对象 (Data Object)：是性质相同的数据元素的集 合，是数据的一个子集。如字符集合 C=A

6、,B,C, 。 1.1.2 基本概念和术语 数据结构 (Data Structure)：是指相互之间具有 (存在 ) 一定联系 (关系 )的数据元素的集合。元素之间的相互联 系 (关系 )称为 逻辑结构 。数据元素之间的逻辑结构有四 种基本类型，如图 1-3所示。 集合 ：结构中的数据元素除了“同属于一个集合” 外，没有其它关系。 线性结构 ：结构中的数据元素之间存在一对一的 关系。 树型结构 ：结构中的数据元素之间存在一对多的 关系。 图状结构或网状结构 ：结构中的数据元素之间存 在多对多的关系。 数据结构的形式定义是一个二元组： Data-Structure=(D， S) 其中： D是数据

7、元素的有限集， S是 D上关系的有限集。 例 2：设数据逻辑结构 B=（ K， R） K=k1, k2, , k 9 R= ， ， ， ， ， ， ， ， ， ， 画出这逻辑结构的图示，并确定那些是起点，那些是终点 1.1.3 数据结构的形式定义 图 1-3 四类基本 结构图 1.1.4 数据结构的存储方式 数据元素之间的关系可以是元素之间代表某种含义 的自然关系，也可以是为处理问题方便而人为定义的 关系，这种 自然或人为定义的 “关系” 称为数据元素 之间的 逻辑关系 ，相应的 结构 称为 逻辑结构 。 数据结构在计算机内存中的存储包括 数据元素的 存储 和 元素之间的关系的表示 。 元素之

8、间的关系在计算机中有两种不同的表示方法： 顺序表示和非顺序表示 。 由此得出两种不同的存储结构： 顺序存储结构 和 链式存储结构 。 顺序存储结构 ： 用数据元素在存储器中的相对位 置来表示数据元素之间的逻辑结构 (关系 )。 链式存储结构 ： 在每一个数据元素中增加一个存 放另一个元素地址的指针 (pointer )，用该指针来表 示数据元素之间的逻辑结构 (关系 )。 例： 设有数据集合 A=3.0,2.3,5.0,-8.5,11.0 ，两种不同 的存储结构。 顺序结构：数据元素存放的 地址是连续的 ； 链式结构：数据元素存放的 地址是否连续没有要 求 。 数据的逻辑结构和物理结构是密不可

9、分的两个方面， 一个 算法的设计取决于 所选定的 逻辑结构 ，而 算法的实 现依赖于 所采用的 存储结构 。 在 C语言中，用 一维数组 表示顺序存储结构 ； 用 结 构体类型 表示链式存储结构。 数据结构的三个组成部分： 逻辑结构 ： 数据元素之间逻辑关系的描述 D_S=（ D， S） 存储结构 ： 数据元素在计算机中的存储及其逻辑 关系的表现称为数据的存储结构或物理结构。 数据操作 ： 对数据要进行的运算。 本课程中将要讨论的三种逻辑结构及其采用的存储 结构如图 1-4所示。 数据的逻辑结构 非线性结构 集合 图状结构 有向图 无向图 树形结构 一般树 二叉树 线性结构 一般线性表 线性表

10、推广 广义表 数组 串 受限线性表 栈和队列 图 1-5 数据逻辑结构层次关系图 图 1-4 逻辑结构与所采用的存储结构 线性表 树 图 顺序存储结构 链式存储结构 复合存储结构 逻辑结构 物理结构 数据类型 (Data Type)：指的是 一个值的集合 和定 义在 该值集上的一组操作 的总称。 数据类型是和数据结构密切相关的一个概念。 在 C 语言中数据类型有：基本类型和构造类型。 数据结构不同于数据类型，也不同于数据对象，它 不仅要描述数据类型的数据对象，而且要描述数据对象 各元素之间的相互关系。 1.1.5 数据类型 数据结构的主要运算包括： 建立 (Create)一个数据结构； 消除

11、(Destroy)一个数据结构； 从一个数据结构中删除 (Delete)一个数据元素； 把一个数据元素插入 (Insert)到一个数据结构中； 对一个数据结构进行访问 (Access)； 对一个数据结构 (中的数据元素 )进行修改 (Modify)； 对一个数据结构进行排序 (Sort)； 对一个数据结构进行查找 (Search)。 1.1.6 数据结构的运算 抽象数据类型 (Abstract Data Type ，简称 ADT)：是 指一个数学模型以及定义在该模型上的一组操作。 ADT的定义仅是一组逻辑特性描述， 与其在计算 机内的表示和实现无关。因此，不论 ADT的内部结构如 何变化，只要

12、其数学特性不变，都不影响其外部使用。 ADT的形式化定义是三元组： ADT=(D， S， P) 其中： D是 数据对象 ， S是 D上的 关系集 ， P是对 D的 基 本操作集 。 1.2 抽象数据类型 ADT的一般定义形式是： ADT 数据对象： 数据关系： 基本操作： ADT 其中数据对象和数据关系的定义用伪码描述。 基本操作的定义是： () 初始条件： 操作结果： 初始条件：描述操作执行之前数据结构和参数应 满足的条件 ;若不满足，则操作失败，返回相应的出 错信息。 操作结果：描述操作正常完成之后，数据结构的 变化状况和 应返回的结果。 1.3.1 算法 算法 (Algorithm)：是

13、对特定问题求解方法 (步骤 )的一种 描述，是指令的有限序列，其中每一条指令表示一个或 多个操作。 算法具有以下五个特性 有穷性 ： 一个算法必须总是在执行有穷步之后结 束，且每一步都在有穷时间内完成。 确定性 ：算法中每一条指令必须有确切的含义。 不存在二义性。且算法只有一个入口和一个出口。 可行性 ： 一个算法是能行的。即算法描述的操作 都可以通过已经实现的基本运算执行有限次来实现。 1.3 算法分析初步 输入 ： 一个算法有零个或多个输入，这些输入 取自于某个特定的对象集合。 输出 ： 一个算法有一个或多个输出，这些输出 是同输入有着某些特定关系的量。 一个算法可以用多种方法描述，主要有

14、：使用自然 语言描述；使用形式语言描述；使用计算机程序设计语 言描述。 算法和程序是两个不同的概念 。一个计算机程序是 对一个算法使用某种程序设计语言的具体实现。算法必 须可终止意味着不是所有的计算机程序都是算法。 在本门课程的学习、作业练习、上机实践等环节， 算法都用 C语言来描述。在上机实践时，为了检查算法 是否正确，应编写成完整的 C语言程序。 评价一个好的算法有以下几个标准 正确性 (Correctness )： 算法应满足具体问题的 需求。 可读性 (Readability)： 算法应容易供人阅读和交 流。可读性好的算法有助于对算法的理解和修改。 健壮性 (Robustness)：

15、算法应具有容错处理。当 输入非法或错误数据时，算法应能适当地作出反应 或进行处理，而不会产生莫名其妙的输出结果。 通用性 (Generality)： 算法应具有一般性 ，即算 法的处理结果对于一般的数据集合都成立。 1.3.2 算法设计的要求 算法执行时间需通过依据该算法编制的程序在计算 机上运行所消耗的时间来度量。其方法通常有两种： 事后统计 ：计算机内部进行执行时间和实际占用空间的 统计。 问题：必须先运行依据算法编制的程序；依赖软硬 件环境，容易掩盖算法本身的优劣；没有实际价值。 事前分析 ：求出该算法的一个时间界限函数。 1.3.3 算法效率的度量 效率与存储量需求 ： 效率指的是算法

16、执行的时 间；存储量需求指算法执行过程中所需要的最大存 储空间。一般地，这两者与问题的规模有关。 与此相关的因素有： 依据算法选用何种策略； 问题的规模； 程序设计的语言； 编译程序所产生的机器代码的质量； 机器执行指令的速度； 撇开软硬件等有关部门因素，可以认为一个特定算 法“ 运行工作量 ”的大小，只依赖于问题的规模（通 常用 n表示），或者说，它 是问题规模的函数 。 算法分析应用举例 算法中 基本操作重复执行的次数 是问题规模 n的某 个函数，其时间量度记作 T(n)=O(f(n)，称作算法的 渐近时间复杂度 (Asymptotic Time complexity)，简称 时 间复杂度

17、 。 一般地，常用 最深层循环内 的语句中的原操作的 执 行频度 (重复执行的次数 )来表示。 “ O的定义： 若 f(n)是正整数 n的一个函数，则 O(f(n) 表示 M0 ，使得当 n n0时， | f(n) | M | f(n0) | 。 表示 时间复杂度 的阶有： O(1) ：常量时间阶 O (n)：线性时间阶 O( n) ：对数时间阶 O(n n) ：线性对数时间阶 O (nk)： k2 ， k次方时间阶 例 两个 n阶方阵的乘法 for(i=1， i=n; +i) for(j=1; j=n; +j) cij=0 ; for(k=1; k=n; +k) cij+=aik*bkj ;

18、 由于是一个三重循环，每个循环从 1到 n，则总次数为： n n n=n3 时间复杂度为 T(n)=O(n3) 例 +x; s=0 ; 将 x自增看成是基本操作，则语句频度为，即时 间复杂度为 (1) 。 如果将 s=0也看成是基本操作，则语句频度为，其时 间复杂度仍为 (1)，即常量阶。 例 for(i=1; i=n; +i) +x; s+=x ; 语句频度为： 2n，其时间复杂度为： O(n) ，即为线性 阶。 例 for(i=1; i=n; +i) for(j=1; j=n; +j) +x; s+=x ; 语句频度为： 2n2 ，其时间复杂度为： O(n2) ，即为平 方阶。 定理 ：

19、若 A(n)=a m n m +a m-1 n m-1 +a 1n+a0是一个 m 次多项式，则 A(n)=O(n m) 例 for(i=2;i=n;+i) for(j=2;j=i-1;+j) +x; ai,j=x; 语句频度为： 1+2+3+ +n-2=(1+n-2) (n-2)/2 =(n-1)(n-2)/2 =n2-3n+2 时间复杂度为 O(n2)，即此算法的时间复杂度为平方 阶。 一个算法时间为 O(1)的算法，它的基本运算执行 的次数是固定的。因此，总的时间由一个常数（即 零次多项式）来限界。而一个时间为 O(n2)的算法则 由一个二次多项式来限界。 以下六种计算算法时间的多项式是

20、最常用的。其 关系为： O(1)O( n)O(n)O(n n)O(n2)O(n3) 指数时间的关系为： O(2n)O(n!)O(nn) 当 n取得很大时，指数时间算法和多项式时间算法 在所需时间上非常悬殊。因此，只要有人能将现有指 数时间算法中的任何一个算法化简为多项式时间算法， 那就取得了一个伟大的成就。 有的情况下，算法中基本操作重复执行的次数还 随问题的输入数据集不同而不同。 例 1： 素数的判断算法。 Void prime( int n) /* n是一个正整数 */ int i=2 ; while ( (n% i)!=0 else printf( 嵌套的最深层语句是 i+；其频度由条件

21、 ( (n% i)!=0 -i) for (j=0; jaj+1) aj aj+1 ; change=TURE ; 最好情况： 0次 最坏情况： 1+2+3+n-1=n(n-1)/2 平均时间复杂度为： O(n2) 1.3.4 算法的空间分析 空间复杂度 (Space complexity) ：是指算法编写成 程序后，在计算机中运行时所需存储空间大小的度量。 记作： S(n)=O(f(n) 其中： n为问题的规模 (或大小 ) 该存储空间一般包括三个方面： 指令常数变量所占用的存储空间 ; 输入数据所占用的存储空间 ; 辅助 (存储 )空间。 一般地，算法的 空间复杂度 指的是 辅助空间 。

22、一维数组 an： 空间复杂度 O(n) 二维数组 anm： 空间复杂度 O(n*m) 习 题 一 1 简要回答术语：数据，数据元素，数据结构，数据 类型。 2 数据的逻辑结构？数据的物理结构？逻辑结构与物 理结构的区别和联系是什么？ 3 数据结构的主要运算包括哪些？ 4 算法分析的目的是什么？算法分析的主要方面是什 么？ 5 分析以下程序段的时间复杂度，请说明分析的理由 或原因。 Sum1( int n ) int p=1, sum=0, m ; for (m=1; m=n; m+) p*=m ; sum+=p ; return (sum) ; Sum2( int n ) int sum=0,

23、 m, t ; for (m=1; m=n; m+) p=1 ; for (t=1; t=m; t+) p*=t ; sum+=p ; return (sum) ; 递归函数 fact( int n ) if (n0时，将非空的线性表记作： (a1， a2， a n) a1称为线性表的 第一个 (首 )结点， an称为线性表的 最后 一个 (尾 )结点。 2.1.1 线性表的定义 a1， a2， a i-1都是 ai(2 i n)的 前驱 ，其中 ai-1是 ai的 直 接前驱 ; ai+1， ai+2， a n都是 ai(1 i n-1)的 后继 ，其中 ai+1是 ai 的 直接后继 。

24、2.1.2 线性表的逻辑结构 线性表中的数据元素 ai所代表的具体含义随具体应 用的不同而不同，在线性表的定义中，只不过是一个抽 象的表示符号。 线性表中的 结点 可以是 单值元素 (每个元素只有一 个数据项 ) 。 例 1: 26个英文字母组成的字母表： (A， B， C、 、 Z） 例 2 ： 某校从 1978年到 1983年各种型号的计算机拥有量 的变化情况： (6， 17， 28， 50， 92， 188） 例 3 ： 一副扑克的点数 (2， 3， 4， ， J， Q， K， A) 线性表中的 结点 可以是 记录型 元素，每个元素含 有多个数据项 ，每个项称为结点的一个域 。每个元 素

25、有一个可以唯一标识每个结点的 数据项组 ，称为 关键字 。 例 4 ： 某校 2001级同学的基本情况： (2001414101， 张里户，男， 06/24/1983)， (2001414102， 张化司，男， 08/12/1984) ， (2001414102， 李利辣，女， 08/12/1984) 若线性表中的结点是 按值 (或按关键字值 )由小到 大 (或由大到小 )排列 的，称线性表是有序的。 2.1.3 线性表的抽象数据类型定义 ADT List 数据对象： D = ai | ai ElemSet, i=1,2,n, n 0 数据关系： R = | ai-1, ai D, i=2,3

26、,n 基本操作： InitList( 数据元素之间的关系是以元素在计算机内“ 物理 位置相邻 ”来体现。 设有非空的线性表： (a1， a2， a n) 。顺序存储如图 2-1所示。 2.2.1 线性表的顺序存储结构 在具体的机器环境下 ：设线性表的每个元素需占用 l个存储单元，以所占的第一个单元的存储地址作为数 据元素的存储位置。则线性表中第 i+1个数据元素的存 储位置 LOC(ai+1)和第 i个数据元素的存储位置 LOC(ai)之 间满足下列关系： LOC(ai+1)=LOC(ai)+l 线性表的第 i个数据元素 ai的存储位置为： LOC(ai)=LOC(a1)+(i-1)*l a

27、1 a2 a i a n Loc(a1) Loc(ai)+(i-1)* l 图 2-1 线性表的顺序存储表示 在高级语言 (如 C语言 )环境下 ：数组具有随机存取 的特性 ，因此，借助数组来描述顺序表。除了用数组来 存储线性表的元素之外，顺序表还应该有表示线性表的 长度属性，所以用结构类型来定义顺序表类型。 #define OK 1 #define ERROR -1 #define MAX_SIZE 100 typedef int Status ; typedef int ElemType ; typedef struct sqlist ElemType Elem_arrayMAX_SIZE

28、 ; int length ; SqList ; 2.2.2 顺序表的基本操作 顺序存储结构中，很容易实现线性表的一些操作： 初始化、赋值、查找、修改、插入、删除、求长度等 。 以下将对几种主要的操作进行讨论 。 1 顺序线性表初始化 Status Init_SqList( SqList *L ) L-elem_array=( ElemType * )malloc(MAX_SIZE*sizeof( ElemType ) ) ; if ( !L - elem_array ) return ERROR ; else L-length= 0 ; return OK ; 2 顺序 线性表的插入 在线性

29、表 L= (a1， a i-1， ai， ai+1， ， an) 中 的 第 i(1 i n)个位置上插入一个新结点 e，使其成为线性 表 ： L=(a1， a i-1， e， ai， ai+1， ， an) 实现步骤 (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 ; if (L-length=MAX_SIZE)

30、 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+ ; return OK ; 时间复杂度分析 在线性表 L中的 第 i个 元素之前插入新结点，其时间 主要耗费在表中结点的移动操作上，因此，可用结点的 移动来估计算法的时间复杂度。 设 在线性表 L中的 第 i个 元素之前插入结点的概率 为 Pi，不失一般性，设各个位置插入

31、是等概率，则 Pi=1/(n+1)，而插入时移动结点的次数为 n-i+1。 总的平均移动次数： Einsert=pi*(n-i+1) (1 i n) Einsert=n/2 。 即 在顺序表上做插入运算，平均要移动表上一半结 点。当表长 n较大时，算法的效率相当低。因此算法的 平均时间复杂度为 O(n)。 3 顺序线性表的删除 在线性表 L=(a1， a i-1， ai， ai+1， ， an) 中删除 结点 ai(1 i n)，使其成为线性表 ： L= (a1， a i-1， ai+1， ， an) 实现步骤 (1) 将线性表 L中的 第 i+1个至第 n个结点依此向前移 动一个位置。 (2

32、) 线性表长度减 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位置以后的所有结点前移

33、 */ L-length-; return (x); 时间复杂度分析 删除线性表 L中的 第 i个 元素，其时间主要耗费在表 中结点的移动操作上，因此，可用结点的移动来估计算 法的时间复杂度。 设 在线性表 L中 删除第 i个 元素的概率为 Pi，不失 一般性，设删除各个位置是等概率，则 Pi=1/n，而删除 时移动结点的次数为 n-i。 则总的平均移动次数： Edelete=pi*(n-i) (1 i n) Edelete=(n-1)/2 。 即 在顺序表上做删除运算，平均要移动表上一半结 点。当表长 n较大时，算法的效率相当低。因此算法的 平均时间复杂度为 O(n)。 4 顺序线性表的查找

34、定位删除 在线性表 L= (a1， a2， ， an) 中删除值为 x的第一 个结点 。 实现步骤 (1) 在线性表 L查找值为 x的第 一个数据元素。 (2) 将从找到的位置至最后一 个结点依次向前移动一 个位置。 (3) 线性表长度减 1。 算法描述 Status Locate_Delete_SqList(Sqlist *L， ElemType x) /* 删除线性表 L中值为 x的 第 一个 结点 */ int i=0 , k ; while (ilength) /*查找值为 x的 第 一个 结点 */ if (L-Elem_arrayi!=x ) i+ ; else for ( k=i

35、+1; klength; k+) L-Elem_arrayk-1=L-Elem_arrayk; L-length-; break ; if (iL-length) printf(要删除的数据元素不存在 !n) ; return ERROR ; return OK; 时间复杂度分析 时间主要耗费在数据元素的比较和移动操作上。 首先， 在线性表 L中查找值为 x的 结点是否存在 ; 其次，若 值为 x的 结点存在，且在 线性表 L中的位置为 i ， 则在 线性表 L中删除 第 i个 元素。 设 在线性表 L删除 数据元素概率为 Pi，不失一般性， 设各个位置是等概率，则 Pi=1/n。 比较的平均

36、次数 ： Ecompare=pi*i (1 i n) Ecompare=(n+1)/2 。 删除时平均移动次数 ： Edelete=pi*(n-i) (1 i n) Edelete=(n-1)/2 。 平均时间复杂度： Ecompare+Edelete=n ， 即为 O(n) 2.3 线性表的链式存储 2.3.1 线性表的链式存储结构 链式存储 ： 用 一组任意的存储单元存储 线性表 中的数据元素。用这种方法存储的线性表简称 线性链 表 。 存储链表中结点的一组任意的存储单元可以是连 续的，也可以是不连续的，甚至是零散分布在内存中 的任意位置上的。 链表中结点的逻辑顺序和物理顺序不一定相同。

37、为了正确表示结点间的逻辑关系，在存储每个结点 值的同时，还必须存储指示其直接后继结点的地址 (或 位置 )，称为指针 (pointer)或链 (link)，这两部分组成了 链表中的结点结构，如图 2-2所示。 链表是通过每个结点的指针域将线性表的 n个结点 按其逻辑次序链接在一起的。 每一个结只包含一个指针域的链表，称为单链表。 为操作方便，总是在链表的第一个结点之前附设一 个头结点 (头指针 )head指向第一个结点。头结点的数据 域可以不存储任何信息 (或链表长度等信息 )。 data next 图 2-2 链表结点结构 data ：数据域，存放结点的值。 next ：指针 域，存放结点的

38、直接后继的地址。 3695 head fat 1100 bat 1300 cat 1305 eat 3700 hat NULL 1100 3700 1300 1305 bat cat eat fat hat head 图 2-3 带头结点的单链表的逻辑状态、物理存储方式 单链表是由表头唯一确定，因此单 链表可以用头指针的名字来命名。 例 1、线性表 L=(bat， cat， eat， fat， hat) 其 带头结点的单 链表的逻辑状态和物理 存储方式如图 2-3所示。 1 结点的描述与实现 C语言中用 带指针的结构体类型 来描述 typedef struct Lnode ElemType d

39、ata; /*数据域，保存结点的值 */ struct Lnode *next; /*指针域 */ LNode; /*结点的类型 */ 2 结点的实现 结点是通过动态分配和释放来的实现 ，即需要时分 配，不需要时释放。实现时是分别使用 C语言提供的标 准函数： malloc() ， realloc()， sizeof() ， free() 。 动态分配 p=(LNode*)malloc(sizeof(LNode); 函数 malloc分配了一个类型为 LNode的结点变量的空间， 并将其首地址放入指针变量 p中。 动态释放 free(p) ; 系统回收由指针变量 p所指向的内存区。 P必须是最

40、近一 次调用 malloc函数时的返回值。 3 最常用的基本操作及其示意图 结点的赋值 LNode *p; p=(LNode*)malloc(sizeof(LNode); p-data=20; p-next=NULL ; p 20 NULL 常见的指针操作 q=p ; p a 操作前 p a q 操作后 q=p-next ; b p a 操作前 操作后 q b p a p=p-next ; b p a 操作前 操作后 p b a q-next=p ; c p b q a 操作前 操作后 q b a c p (a) q-next=p-next ; (a) x y p b q a 操作前 操作后

41、q b a x y p 操作前 y p x b q a 操作后 y p x b q a (b) 操作前 y p x b q a 操作后 y p x b q a (b) 2.3.2 单线性链式的基本操作 1 建立单链表 假设线性表中结点的数据类型是整型，以 32767作 为结束标志。动态地建立单链表的常用方法有如下两种： 头插入法 ， 尾插入法 。 头插入法建表 从一个空表开始，重复读入数据，生成新结点， 将读入数据存放到新结点的数据域中，然后将新结点插 入到当前链表的表头上，直到读入结束标志为止。即 每 次插入的结点都作为链表的第一个结点 。 算法描述 LNode *create_LinkLi

42、st(void) /* 头插入法创建单链表 ,链表的头结点 head作为返回值 */ int data ; LNode *head, *p; head= (LNode *) malloc( sizeof(LNode); head-next=NULL; /* 创建链表的表头结点 head */ while (1) scanf(%d, if (data=32767) break ; p= (LNode *)malloc(sizeof(LNode); pdata=data; /* 数据域赋值 */ pnext=headnext ; headnext=p ; /* 钩链 ，新创建 的结点总是作为第一个

43、结点 */ return (head); (2) 尾插入法建表 头插入法建立链表虽然算法简单，但生成的链表 中结点的次序和输入的顺序相反。若希望二者次序一致， 可采用尾插法建表。该方法是将 新结点插入到当前链表 的表尾，使其成为当前链表的尾结点 。 算法描述 LNode *create_LinkList(void) /* 尾插入法创建单链表 ,链表的头结点 head作为返回值 */ int data ; LNode *head, *p, *q; head=p=(LNode *)malloc(sizeof(LNode); p-next=NULL; /* 创建单链表的表头结点 head */ wh

44、ile (1) scanf(%d, if (data=32767) break ; q= (LNode *)malloc(sizeof(LNode); qdata=data; /* 数据域赋值 */ qnext=pnext; pnext=q; p=q ; /*钩链 ，新创建 的结点总是作为最后一个结点 */ return (head); 无论是哪种插入方法，如果要插入建立的单线性 链表的结点是 n个，算法的时间复杂度均为 O(n)。 对于单链表，无论是哪种操作，只要涉及到钩链 (或重新钩链 )，如果 没有明确给出直接后继 ，钩链 (或 重新钩链 )的次序必须是 “先右后左”。 2 单链表的查找

45、 (1) 按序号查找 取单链表中的第 i个元素。 对于单链表，不能象顺序表中那样直接按序号 i访 问结点，而只能从链表的头结点出发，沿链域 next逐个 结点往下搜索，直到搜索到第 i个结点为止。因此， 链 表不是随机存取结构 。 设单链表的长度为 n，要查找表中第 i个结点，仅 当 1 i n时， i的值是合法的。 算法描述 ElemType Get_Elem(LNode *L ， int i) int j ; LNode *p; p=L-next; j=1; /* 使 p指向第一个结点 */ while (p!=NULL j+; /* 移动指针 p , j计数 */ if (j!=i) r

46、eturn(-32768) ; else return(p-data); /* p为 NULL 表示 i太大 ; ji表示 i为 0 */ 移动指针 p的频度： in： n次。 时间复杂度 : O(n)。 (2) 按值查找 按值查找是在链表中，查找是否有结点值等于给定 值 key的结点 ? 若有，则返回首次找到的值为 key的结点 的存储位置；否则返回 NULL。查找时从开始结点出发， 沿链表逐个将结点的值和给定值 key作比较。 算法描述 LNode *Locate_Node(LNode *L， int key) /* 在以 L为头结点的单链表中查找值为 key的第一个结点 */ LNode

47、 *p=Lnext; while ( p!=NULL if (pdata=key) return p; else printf(所要查找的结点不存在 !n); retutn(NULL); 算法的执行与形参 key有关，平均时间复杂度为 O(n)。 3 单链表的插入 插入运算是将值为 e的新结点插入到表的第 i个结 点的位置上，即插入到 ai-1与 ai之间。因此，必须首先找 到 ai-1所在 的结点 p，然后生成一个数据域为 e的新结点 q， q结点作为 p的直接后继结点。 算法描述 void Insert_LNode(LNode *L， int i， ElemType e) /* 在以 L为

48、头结点的单链表的第 i个位置插入值为 e的结点 */ int j=0; LNode *p， *q; p=Lnext ; while ( p!=NULL j+; if (j!=i-1) printf(i太大或 i为 0!n ); else q=(LNode *)malloc(sizeof(LNode); qdata=e; qnext=pnext; pnext=q; 设链表的长度为 n，合法的插入位置是 1 i n。算 法的时间主要耗费 移动指针 p上，故时间复杂度亦为 O(n)。 4 单链表的删除 按序号删除 删除单链表中的第 i个结点。 为了删除第 i个结点 ai，必须找到结点的存储地址。 该

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

50、t j=1; LNode *p， *q; p=L; q=L-next; while ( p-next!=NULL j+; if (j!=i) printf(i太大或 i为 0!n ); else pnext=qnext; free(q); 按值删除 删除单链表中值为 key的第一个结点。 与按值查找相类似，首先要查找值为 key的结点是 否存在 ? 若存在，则删除；否则返回 NULL。 算法描述 void Delete_LinkList(LNode *L， int key) /* 删除以 L为头结点的单链表中值为 key的第一个结点 */ LNode *p=L, *q=Lnext; while

51、 ( q!=NULL q=qnext; if (qdata=key) p-next=q-next; free(q); else printf(所要删除的结点不存在 !n); 算法的执行与形参 key有关，平均时间复杂度为 O(n)。 从上面的讨论可以看出，链表上实现插入和删除运 算，无需移动结点，仅需修改指针。解决了顺序表的插 入或删除操作需要移动大量元素的问题。 变形之一： 删除单链表中值为 key的所有结点。 与按值查找相类似，但比前面的算法更简单。 基本思想 ： 从单链表的第一个结点开始，对每个结点 进行检查，若结点的值为 key，则删除之，然后检查下 一个结点，直到所有的结点都检查。

52、算法描述 void Delete_LinkList_Node(LNode *L， int key) /* 删除以 L为头结点的单链表中值为 key的第一个结点 */ LNode *p=L, *q=Lnext; while ( q!=NULL) if (qdata=key) p-next=q-next; free(q); q=p-next; else p=q; q=qnext; 变形之二： 删除单链表中所有值重复的结点，使得所有结点的 值都不相同。 与按值查找相类似，但比前面的算法更复杂。 基本思想 ： 从单链表的第一个结点开始，对每个结点 进行检查：检查链表中该结点的所有后继结点，只要有 值和

53、该结点的值相同，则删除之；然后检查下一个结点， 直到所有的结点都检查。 算法描述 void Delete_Node_value(LNode *L) /* 删除以 L为头结点的单链表中所有值相同的结点 */ LNode *p=L-next, *q, *ptr; while ( p!=NULL) /* 检查链表中所有结点 */ *q=p, *ptr=pnext; /* 检查结点 p的所有后继结点 ptr */ while (ptr!=NULL) if (ptrdata=p-data) q-next=ptr-next; free(ptr); ptr=q-next; else q=ptr; ptr=p

54、trnext; p=p-next ; 5 单链表的合并 设有两个有序的单链表，它们的头指针分别是 La 、 Lb，将它们合并为以 Lc为 头指针的有序链表。合并前 的示意图如图 2-4所示。 15 图 2-4 两个有序的单链表 La ， Lb的初始状态 -2 4 9 Lb pb -7 3 12 23 La Lc pa pc 合并了值为 -7， -2的结点后示意图如图 2-5所示。 图 2-5 合并了值为 -7 ， -2的结点后的状态 -2 4 9 15 Lb pc pb Lc -7 3 12 23 La pa 算法说明 算法中 pa ， pb分别是待考察的两个链表的当前结 点， pc是合并过程

55、中合并的链表的最后一个结点。 算法描述 LNode *Merge_LinkList(LNode *La， LNode *Lb) /* 合并以 La, Lb为头结点的两个有序单链表 */ LNode *Lc, *pa , *pb , *pc, *ptr ; Lc=La ; pc=La ; pa=La-next ; pb=Lb-next ; while (pa!=NULL pc=pa ; pa=pa-next ; /* 将 pa所指的结点合并， pa指向下一个结点 */ if (pa-datapb-data) pc-next=pb ; pc=pb ; pb=pb-next ; /* 将 pa所指的

56、结点合并， pa指向下一个结点 */ if (pa-data=pb-data) pc-next=pa ; pc=pa ; pa=pa-next ; ptr=pb ; pb=pb-next ; free(ptr) ; /* 将 pa所指的结点合并， pb所指结点删除 */ if (pa!=NULL) pc-next=pa ; else pc-next=pb ; /*将剩余的结点链上 */ free(Lb) ; return(Lc) ; 算法分析 若 La ， Lb两个链表的长度分别是 m， n，则链表合 并的时间复杂度为 O(m+n) 。 2.3.3 循环链表 循环链表 (Circular Li

57、nked List)： 是一种头尾相 接的链表。其特点是最后一个结点的指针域指向链表的 头结点，整个 链表的指针域链接成一个环 。 从循环链表的任意一个结点出发都可以找到链表中 的其它结点，使得表处理更加方便灵活。 图 2-6是带头结点的单循环链表的示意图。 空表 图 2-6 单循环链表示意图 非空表 a1 a2 an head head 循环链表的操作 对于单循环链表，除链表的合并外，其它的操作和 单线性链表基本上一致，仅仅需要在单线性链表操作算 法基础上作以下简单修改： 判断是否是空链表： head-next=head ; 判断是否是表尾结点： p-next=head ; 2.4 双向链表

58、 双向链表 (Double Linked List) :指的是构成链表 的每个结点中设立两个指针域：一个指向其直接前趋的 指针域 prior，一个指向其直接后继的指针域 next。这样 形成的链表中有两个方向不同的链，故称为 双向链表 。 和单链表类似，双向链表一般增加头指针也能使双 链表上的某些运算变得方便。 将头结点和尾结点链接起来也能构成循环链表，并 称之为双向循环链表。 双向链表是为了克服单链表的单向性的缺陷而引入 的。 1 双向链表的结点及其类型定义 双向链表的结点的类型定义如下。其结点形式如 图 2-7所示 ，带头结点的双向链表的形式如图 2-8所示 。 typedef struc

59、t Dulnode ElemType data ; struct Dulnode *prior , *next ; DulNode ; data next prior 图 2-7 双向链表结点形式 非空双向链表 head a2 a1 an 空双向链表 head 图 2-8 带头结点的双向链表形式 双向链表结构具有对称性，设 p指向双向链表中的 某一结点，则其对称性可用下式描述： (p-prior)-next=p=(p-next)-prior ; 结点 p的存储位置存放在其 直接前趋结点 p-prior的 直接后继指针域 中，同时也存放在 其直接后继结点 p- next的 直接前趋指针域 中。

60、2 双向链表的基本操作 (1) 双向链表的插入 将值为 e的结点插入双向链表中。 插入前后链表的变化如图 2-9所示。 S e p ai ai+1 S e p ai ai+1 图 2-9 双向链表的插入 插入时仅仅指出直接前驱结点 ，钩链时必须注意 先后次序是 ： “先右后左” 。部分语句组如下： 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); 注意： 与单链表的插入和删除操作不同的是，在双向链 表中 插入 和 删除 必须同时