数据结构实用教程(C语言版).ppt

数据结构实用教程（C语言版 ） 第第1 1章章 概论概论 本章主要介绍以下内容：本章主要介绍以下内容： 数据结构中涉及的相关概念数据结构中涉及的相关概念 数据结构研究的主要内容数据结构研究的主要内容 算法的概念、描述方法以及评价标准算法的概念、描述方法以及评价标准 本章目录本章目录 1.1 1.1 什么是数据结构什么是数据结构 1 1.2 1.2 算法和算法分析算法和算法分析 2 5.5 5.5 哈夫曼树哈夫曼树5 1.31.3本章小结本章小结3 结束 1.1 什么是数据结构 v1.1.1 基本概念及术语 v1.1.2 数据的逻辑结构 v1.1.3 数据的存储结构 v1.1.4 抽象数据类型 返回到本节目录返回到总目录返回到总目录 1.1.1 基本概念及术语 在系统的学习数据结构知识之前，先了解一些相 关概念和术语。 1数据（Data） 指所有能输入到计算机中并被计算机程序处理的 符号的总称。例如，整数、实数、字符、图像 、声音等都是数据。 2数据元素（Data Element） 数据元素（也称为结点）是数据的基本单位，在 计算机程序中通常作为一个整体进行考虑和处 理。一个数据元素可以由若干个数据项组成。 数据项是数据处理中不可分割的最小单位。 返回到本节目录 3数据结构（Data Structure） 是相互之间存在一种或多种特定关系的数据元 素的集合。这些数据元素不是孤立存在的， 而是有着某种关系，这种关系称为结构。 数据结构一般包括以下三个方面内容： （1）数据元素之间的逻辑关系，也称数据的 逻辑结构。 （2）数据元素及其关系在计算机存储器内的 表示，称为数据的存储结构。 （3）数据的运算，即对数据施加的操作。 返回到本节目录 1.1.1 基本概念及术语 数据结构定义：按某种逻辑关系组织起来的一批数据 ，按一定的映像方式把它存放在计算机存储器中， 并在这些数据上定义了一个运算的集合，就叫做数 据结构。 简言之，数据结构= 逻辑结构+存储结构+运算集合 。 4数据类型(Data Type) 数据类型是一组性质相同的值集合以及定义在这个值 集合上的一组操作的总称。 如在高级语言中，整型类型的取值范围为：-32768 +32767，运算符集合为加、减、乘、除、取模 ，即+、-、*、/、%。 返回到本节目录 1.1.1 基本概念及术语 返回到本节目录 1.1.1 基本概念及术语 1.1.2 数据的逻辑结构 1定义 数据的逻辑结构是指数据元素之间逻辑关系描 述。可以用一个二元组表示，其形式化描述 为： Data_Structure=（D，R） 其中D是数据元素的有限集合，R是D上关系 的有限集合。数据的逻辑结构是从逻辑关系 上描述数据，与数据的存储无关，是独立于 计算机的。 返回到本节目录 2数据的逻辑结构的分类 根据数据元素之间的逻辑关系的不同特性，分 为下列四类基本结构，如图1-1所示。 （a）集合结构 （b）线性结构 （c）树型结构 （d）图形结构 图1-1 数据结构的四种基本逻辑结构 返回到本节目录 1.1.2 数据的逻辑结构 （1）集合 结构中的数据元素之间除了“同属于一个集合” 的关系外，别无其他关系，这是一种最简单 的数据结构。 （2）线性结构 结构中的数据元素之间存在着“一对一”的关系 。 【例1.1】学籍档案管理 假设一个学籍档案管理系统应包含如表1-1所 示的学生信息。 返回到本节目录 1.1.2 数据的逻辑结构 特点： 表中的每一行是一个数据元素（或记录、结点），它 由学号、姓名、性别及出生年月等数据项组成。 表中数据元素之间是一种先后关系，对于表中任一结 点，与它相邻且在它前面的结点（称为直接前驱） 最多只有一个；与表中任一结点相邻且在其后的结 点（称为直接后继）也最多只有一个。我们将这种 关系称为“线性结构”。 返回到本节目录 1.1.2 数据的逻辑结构 （3）树型结构 结构中的数据元素之间存在着“一对多”的关系 。 【例1.2】人机对弈 人与计算机进行对弈的部分图如图1-2为所示 。 图1-2 人机对弈图 返回到本节目录 1.1.2 数据的逻辑结构 特点： 图中将每一个棋盘看作一个数据元素，则数据 元素之间的关系要比表1-1要复杂许多。 图中数据元素之间是一对多关系，即一个数据 元素向上和一个数据元素相连（称为双亲结 点），向下和多个数据元素相连（称为孩子 结点）。我们将这种关系称为“树型结构”。 4）图形结构或网状结构 结构中的任意数据元素之间都可以有关系，元 素之间存在着“多对多”的关系。 返回到本节目录 1.1.2 数据的逻辑结构 返回到本节目录 1.1.2 数据的逻辑结构 教学计划的关系图如图1-3所示。 图1-3 教学计划关系图 特点： 图中数据元素存在着多对多的任意关系。一个 结点可能有多个直接前驱和直接后继。 返回到本节目录 1.1.2 数据的逻辑结构 1.1.3 数据的存储结构 数据在计算机中的存储表示称为数据的存储结 构，也称为物理结构。数据的存储结构是逻 辑结构在计算机存储器中的实现。本书将介 绍常用的两种基本的存储结构：顺序存储结 构和链式存储结构。 数据的逻辑结构和存储结构的关系是：存储结 构是逻辑关系的映像与元素本身映像，是数 据结构的实现；逻辑结构是数据结构的抽象 。 返回到本节目录 1. 顺序存储结构 顺序存储结构：借助元素在存储器中的相对位 置来表示数据元素间的逻辑关系。 【例1.4】对于表1-1提出的学生信息登记表 进行存储，假定每个元素占用50个存储单 元，数据从1000号单元开始由低地址向高 地址存放，对应的顺序存储结构如表1-3所 示。 返回到本节目录 1.1.3 数据的存储结构 顺序存储结构的主要特点： v可实现对各数据元素的随机访问。这是因为 只要知道存储的首地址以及每个数据元素所 占的存储单元，就可以计算出各数据元素的 存储地址。 v不利于修改，在对数据元素进行插入、删除 运算时可能要移动一系列的数据元素。 返回到本节目录 1.1.3 数据的存储结构 2. 链式存储结构 链式存储结构：借助指示元素存储地址的指针 表示数据元素间的逻辑关系。 【例1.5】对于表1-1学生信息登记表进行链 式存储时，在每个数据元素后方附加一个指 向“下一个结点地址”的指针字段，用于存放 后继数据元素的存储地址，每个数据元素的 地址是随机的，可以不连续。对应的链式存 储结构见表1-4所示。 返回到本节目录 1.1.3 数据的存储结构 链式存储结构的主要特点： v利于修改，在对数据元素进行插入、删除运 算时，仅需修改数据元素的指针字段值，而 不必移动数据元素。 v由于逻辑上相邻的数据元素在存储位置中不 一定相邻，因此，链式存储结构不能对数据 元素进行随机访问。 返回到本节目录 1.1.3 数据的存储结构 1.1.4 抽象数据类型 1抽象数据类型的定义 抽象数据类型（Abstract Data Type，简 称ADT）是指一个数学模型以及定义在该模 型上的一组操作。 2抽象数据类型的表示 抽象数据类型实际上就是对该数据结构的定义 。因为它定义了一个数据的逻辑结构以及在 此结构上的一组算法。可以用一个三元组表 示： ADT=（，） 其中，D是数据对象，S是D上的关系集，P是 对D的基本操作集。 返回到本节目录 抽象数据类型通常是指由用户定义，用以表示应用问 题的数据类型，抽象数据类型由基本的数据类型组 成，并包括一组相关的服务（或称操作）。 抽象数据类型有些类似于pascal语言中的记录（ record）类型和c语言中的构造（struct）类型， 但它增加了相关的服务。 3ADT的两个重要特征 （1）数据抽象用ADT描述程序处理的实体时，强调 的是其本质的特征、其所能完成的功能以及它和外 部用户的接口（即外界使用它的方法）。 （2）数据封装将实体的外部特性和其内部实现细节分 离，并且对外部用户隐藏其内部实现细节。 返回到本节目录 1.1.4 抽象数据类型 1.2 算法和算法分析 v1.2.1 算法的概念 v1.2.2 算法分析 v1.2.3 相关C语言知识回顾 返回到总目录返回到总目录 1.2.1 算法的概念 1算法的定义 瑞士著名的计算机科学家N.Wirth所提出的著 名公式“程序=算法+数据结构”，所谓算法 ，就是为解决特定问题而采取的步骤和方法 。 2算法的特性 一个算法应该具有下列特性： （1）有穷性：一个算法必须（对任何合法的 输入值）在执行有限步之后结束。 （2）确定性：算法中的每一条指令必须有确 切的含义，不会产生二义性。 返回到本节目录 （3）可行性：算法中描述的操作都可以通过 执行有限次基本操作来实现。 （4）输入：一个算法有零个或多个输入。 （5）输出：一个算法必有一个或多个输出。 3算法的评价 要设计一个好的算法通常需要考虑以下几方面 的要求： （1）正确性：要求算法能够正确地执行预先 规定的功能，并达到所期望的性能要求。 （2）可读性：为了便于理解、测试和修改算 法，算法应该具有良好的可读性。返回到本节目录 1.2.1 算法的概念 （3）健壮性：当输入非法的数据时，算法应 能恰当地做出反应或进行相应处理，而不是 产生莫名奇妙的输出结果。并且处理出错的 方法不应是中断程序的执行，而是返回一个 表示错误或错误性质的值，以便在更高的抽 象层次上进行处理。 （4）高效性：对同一个问题，执行时间越短 ，算法的效率越高。 （5）低存储量：完成相同的功能，执行算法 所占用的存储空间应尽可能的少。 返回到本节目录 1.2.1 算法的概念 4算法的描述 为了表示一个算法，可以用多种不同的方法， 常用的有自然语言、传统流程图、结构化流 程图、N-S流程图等表示。本书采用C的描 述语言实现对各种数据结构及算法的操作描 述，算法是以函数形式描述，描述如下： 类类型标识标识 符 函数名(形式参数表) /*算法说说明*/ 语语句序列 返回到本节目录 1.2.1 算法的概念 1.2.2 算法分析 在算法满足正确性的前提下，如何评价不同算法的优 劣呢？通常主要考虑算法的时间复杂度和空间复杂 度这两方面。一般情况下，鉴于运算空间（内存） 较为充足，所以把算法的时间复杂度作为重点分析 。 1. 时间复杂度（Time Complexity） 一个算法所需的运算时间通常与所解决问题的规模大 小有关。问题规模是一个和输入有关的量，用n 表 示问题规模的量，把算法运行所需的时间T表示为n 的函数，记为T(n)。不同的T(n)算法，当n增长 时，运算时间增长的快慢很不相同。一个算法所需 的执行时间就是该算法中所有语句执行次数之和。 当n逐渐增大时T(n)的极限情况，一般简称为时间 复杂度。 返回到本节目录 当讨论一个程序的运行时间时，注重的不是 T(n)的具体值，而是它的增长率。T(n)的 增长率与算法中数据的输入规模紧密相关， 而数据输入规模往往用算法中的某个变量的 函数来表示，通常是f(n)。随着数据输入规 模的增大，f(n)的增长率与T(n)的增长率 相近，因此T(n)同f(n)在数量级上是一致 的。记作： T(n)=O(f(n) 其中，大写字母O为Order(数量级)的字头， f(n)为函数形式，如T(n)=O(n2)。 返回到本节目录 1.2.2 算法分析 返回到本节目录 1.2.2 算法分析 【例1.6】分析以下算法的时间复杂度。 x=0;y=0; for(k=1;k成员名 等价于：(*指针名).成员名 等价于：结构体变量名.成员名 在本书中，在程序内大量使用结构体类型的指 针，所以大都采用第一种写法。 返回到本节目录 1.2.3 相关C语言知识回顾 （4）用typedef定义类型 除了可以直接使用C提供的标准类型名和自己 声明的结构体类型外，还可以用typedef声 明新的类型名来代替已有的类型名。其基本 定义格式如下： 【格式】typedef 原类型名 新类型名; 其中，typedef为关键字，表示重定义。原类 型名是C语言提供的任意一种数据类型，可 以是简单数据类型，也可以是构造数据类型 。新类型名为原类型名的一个别名。使用新 类型名就像使用原类型名那样定义变量。 返回到本节目录 1.2.3 相关C语言知识回顾 2动态存储分配函数 C语言提供了动态分配函数来实现动态存储分配。最常 用的动态存储分配函数有以下两个。 （1）分配内存空间函数malloc() 【格式】(类型名 *)malloc(要分配的内存字节数 size) 【功能】在内存中分配一个长度为size的连续存储空 间，返回值是新分配存储空间的首地址，若内存不 足，则返回NULL。其中，类型名表示把该存储空 间用于何种数据类型。（类型名 *）表示把 malloc函数返回值强制转换为该类型指针。 返回到本节目录 1.2.3 相关C语言知识回顾 （2）释放内存空间函数free() 【格式】free(指向要释放单元的指针名) 【功能】释放该指针所指的一块存储空间，该 空间系统可另作它用。注意这个指针所指的 空间必须是由malloc()函数和calloc()函 数分配的才行。free函数无返回值。例如： int *pt; pt=(int *)malloc(sizeof(int); free(pt); 程序段表示释放pt指向的存储空间。 返回到本节目录 1.2.3 相关C语言知识回顾 3函数的定义与调用 在本书中，绝大多数的算法都是编写成C语言的函数， 这些函数需要通过编写相应的主函数才能被执行。 （1）函数的定义 函数的定义如下： 【格式】 函数类类型 函数名（形参表） 内部变变量定义义 函数主体语语句 返回语语句 返回到本节目录 1.2.3 相关C语言知识回顾 （2）函数的调用 【格式】函数类型 函数名（实参表）; 【说明】 1实参表中各参数应与形参表中各参数类型 及个数相符。 2在调用函数时，表达式应与该函数的类型 相符，如果该函数有返回值时，在调用时要 将该函数的返回值赋给相同类型的变量。 返回到本节目录 1.2.3 相关C语言知识回顾 4 Turbo C 2.0中的汉字显示 在TurboC 2.0中，如果想输入和显示汉字， 需要使用UCDOS汉字系统。但现在的 Windows操作系统不支持UCDOS汉字系 统的16位显示。下面介绍一种能在 Windows XP系统环境下，在TurboC 2.0中使用UCDOS的汉字系统的方法。 返回到本节目录 1.2.3 相关C语言知识回顾 （1）将UCDOS的核心文件进行兼容性设置 （有的机器可省略这步，直接执行（2） 。 点“开始”菜单-“所有程序”-“附件”-“程 序兼容性向导”-“我想手动定位程序”-“ 浏览”--win98- 256色，640X480-程序工作正确吗？ 选“是，设置此程序为一直使用兼容性设置 。”完成。有的UCDOS版本的核心文件是 knlvga.exe，也要照此进行兼容性设置。 返回到本节目录 1.2.3 相关C语言知识回顾 （2）运行UCDOS系统文件的方法。 进入到命令提示符（MS-DOS状态）（“开始 ”-“程序”-“附件”-“命令提示符”）切 换到UCDOS目录。（带下划线文字为输入 的命令信息，“”表示回车键。假设 UCDOS文件夹在C盘根目录内，可输入如 下命令：） C:Documents and Settingscd （回到C盘根目录下） C:cd Ucdos （进入UCDOS的目录 ） 返回到本节目录 1.2.3 相关C语言知识回顾 这时不要运行UCDOS.BAT，分别一项一项 命令运行。如： C:UDOS C:UDOS C:UDOS C:UDOS C:UDOS （五笔输入，如不 用五笔可省略此步） （注：可直接输入命令名，如输入 “rd16”，省略扩展名“.com”） 返回到本节目录 1.2.3 相关C语言知识回顾 就可以顺利进入ucdos。然后，退出UCDOS 目录，再进入tc目录运行tc.exe文件就可 以在TurboC 2.0中顺利的输入和显示汉字 了。如： C:UDOScd C:cd tc （假定TurboC 2.0的文 件夹名称为TC） C:TCtc.exe (可直接输入tc即可) 即可进行TurboC 2.0输入并运行C语言源程 序了。 返回到本节目录 1.2.3 相关C语言知识回顾 （3）常用的Turbo C2.0快捷键 Alt+F：文件菜单 Load 打开文件 Save 保存 Write to 另存为 Quit 退出 Alt+R：运行菜单 Run（或Ctrl+F9） 运行程序 User Screen (或Alt+F5) 查看运行结果 Alt+E：编辑（显示光标，有时调试有错时可 将光标重新显示在编辑区） F9：编译系统查错 返回到本节目录 1.2.3 相关C语言知识回顾 （4）更改汉字输入法 Alt+F1 区位 Alt+F2 全拼 Alt+F3 双拼 Alt+F5 五笔（必须在UCDOS中输入wb命 令才能用此项） Alt+F6 英文 单次按右shift键 可显示或隐藏中文输入法 返回到本节目录 1.2.3 相关C语言知识回顾 1.3本章小结 本章主要介绍了有关数据结构的以下几方面： （1）数据结构主要研究数据的逻辑结构、存 储结构和运算方法。 （2）数据的逻辑结构包括：集合、线性结构 、树型结构、图形结构四种基本类型。 （3）数据的存储结构包括：顺序存储结构和 链式存储结构。 （4）算法是对特定问题求解步骤的一种描述 ，是指令的有限序列。算法具有：有穷性、 确定性、正确性、输入、输出等特性。 （5）算法的时间复杂度与空间复杂度。 返回到总目录返回到总目录 数据结构实用教程（C语言版） 中国水利水电出版社 第第2 2章章 线性表线性表 本章主要介绍下列内容本章主要介绍下列内容 线性表的定义和基本操作线性表的定义和基本操作 线性表的顺序存储结构线性表的顺序存储结构 线性表的链式存储结构线性表的链式存储结构 线性表的应用举例线性表的应用举例 本章目录本章目录 2.1 2.1 线性表的基本概念线性表的基本概念 1 2.2 2.2 顺序表顺序表 2 2.3 2.3 链表链表 3 2.4 2.4 线性表的应用举例线性表的应用举例 4 2.5 2.5 本章小结本章小结5 结束 2.1 线性表的基本概念 v2.1.1 线性表的定义 v2.1.2 线性表的基本操作 返回到总目录 2.1.1 线性表的定义 1. 线性表的定义 线性表是具有相同数据类型的n（n=0）个 数据元素的有限序列，通常记为： （a1，a2， ai-1，ai，ai+1，an） 其中n为表长，当n=0时称为空表。 在线性表中相邻元素之间存在着顺序关系。如 对于元素ai 而言，ai-1 称为 ai 的直接前驱 ，ai+1 称为 ai 的直接后继。 返回到本节目录 2. 线性表的特点 （1）有且仅有一个开始结点（a1），它没有 直接前驱； （2）有且仅有一个终端结点（an），它没有 直接后继； （3）除了开始结点和终端结点以外，其余的 结点都有且仅有一个直接前驱和一个直接后 继。 2.1.1 线性表的定义 返回到本节目录 2.1.2 线性表的基本操作 数据结构的运算是定义在逻辑结构层次上的， 而运算的具体实现是建立在存储结构上的。 下面定义的线性表的基本操作仅是定义在逻 辑结构上的，每一个操作的具体实现只有在 确定了线性表的存储结构之后才能完成。 线性表的基本操作有： （1）初始化线性表InitList(L)。 其作用是建立一个空表L（即建立线性表的构 架，但不包含任何数据元素）。 返回到本节目录 2.1.2 线性表的基本操作 返回到本节目录 （5）插入操作InsElem(L,i,x)。其作用是在线性表L 的第i个位置上插入一个值为 x 的新元素，使线性表L 由（a1，a2， ai-1，ai，ai+1，an）变为（a1， a2， ai-1，x，ai，ai+1，an）。其中 1iGetLength(L)+1。 （6）删除操作DelElem(L,i,x)。其作用是删除线性表 L的第i个位置的数据元素并用x将其存储，使线性表L 由（a1，a2， ai-1，ai，ai+1，an）变为（a1， a2， ai-1，ai+1，an）。其中 1iGetLength(L)。 （7）输出元素值DispList(L)。其作用是依次扫描线性 表L，并输出各元素的值。 2.1.2 线性表的基本操作 返回到本节目录 2.2 顺序表 v2.2.1 顺序表 v2.2.2 顺序表的基本操作实现 返回到总目录 1. 顺序表的定义 数据结构在内存中的表示通常有两种形式，即顺序存 储表示和链式存储表示。线性表的顺序存储表示又 称为顺序表。线性表的顺序存储是指用一组地址连 续的存储单元依次存储线性表的数据元素，我们把 用这种存储形式存储的线性表称为顺序表。 假设顺序表(a1，a2， ai-1，ai，ai+1，an)，每 个数据元素占用d个存储单元，则元素ai的存储位置 为： Loc(ai)= Loc(a1)+(i-1)d 1in 2.2.1 顺序表 返回到本节目录 其中，Loc(a1)是顺序表第一个元素a1的存储位置， 通称为顺序表的起始地址。顺序存储结构示意图如 图2-1所示。 顺序表的存储特点： （1）顺序表的逻辑顺序和物理顺序是一致的。 （2）顺序表中任意一个数据元素都可以随机存取，所 以顺序表是一种随机存取的存储结构。 2.2.1 顺序表 返回到本节目录 2. 顺序表的类型定义 #define MAXLEN 100 /*定义常量MAXLEN为100表示存 储空间总量*/ #define OK /*定义常量OK为1表示成功*/ #define ERROR 0 /*定义常量ERROR为0表示失败*/ #define OVER -1 /*定义常量OVER为-1表示结束*/ typedef int ElemType; /*定义ElemType为int类型*/ typedef struct /*顺序表存储类型*/ ElemType dataMAXLEN; /*存放线性表的数组*/ int Length; /*Length是顺序表的长度*/ SeqList; 2.2.1 顺序表 返回到本节目录 2.2.2 顺序表的基本操作实现 返回到本节目录 2顺序表的建立 初始化顺序表后向表中输入n个元素建立表L，算法描 述见算法2.2。 算法2.2 void CreateList(SeqList *L,int n) int i; printf(“请输入各个元素值：n“); for(i=0;idatai); L-Length=i; 2.2.2 顺序表的基本操作实现 返回到本节目录 3求顺序表的长度操作 返回顺序表L的Length值，算法描述见算法2.3。 算法2.3 int GetLength(SeqList *L ) return L-Length ; 4查找操作 顺序表的查找分为按值与按序号查找，下面将分别介 绍这两种方法的实现，读者可根据具体的问题相应 选择所需的查找方法。 2.2.2 顺序表的基本操作实现 返回到本节目录 （1）按号查找 查找顺序表中第i个元素的值，在i无效时返回出错，有 效时返回成功，并用x存储第i个元素的值，算法描述 见算法2.4。 算法2.4 int GetElem(SeqList *L, int i, ElemType *x) if (iL-Length) return ERROR; else *x = L-datai-1; return OK; 2.2.2 顺序表的基本操作实现 返回到本节目录 2）按值查找操作 顺序表中的按值查找是指在顺序表中查找与给定值x相等的数据 元素的所在位置，算法描述见算法2.5。 算法2.5 int Locate(SeqList *L, ElemType x) int i=0; while(i Length if (iL-Length) return ERROR; else return i+1; /*返回的是元素位置*/ 2.2.2 顺序表的基本操作实现 返回到本节目录 2.2.2 顺序表的基本操作实现 5插入操作 线性表的插入是指在表的第i个位置上插入一个值为 x 的新元素，插入后使原表长增1，原顺序表如图2 -2所示。 返回到本节目录 5插入操作 步骤如下： (1) 将anai 之间的所有结点依次后移， 为新元素让出第i个位置，如图2-3所示。 返回到本节目录 5插入操作 步骤如下： (2) 将新结点x插入到第i个位置，如图2-4所示。 (3) 顺序表的长度增1，插入成功，并返回，算法描 述见算法2.6。 返回到本节目录 5插入操作 算法2.6 int InsElem(SeqList *L, int i, ElemType x) int j; if (L-Length=MAXLEN) printf (“顺序表已满！“); return OVER; /*表满，不能插入*/ if (iL-Length+1) /*检查给定的插入位置的正确性*/ printf(“插入位置出错！“); return ERROR; if (i = L-Length+1) L-datai-1=x; L-Length+; return OK; /*插入的位置为表尾，则不需移动直接插入即可*/ for (j=L-Length-1; j=i-1; j-) /*结点移动*/ L-dataj+1=L-dataj; L-datai-1=x; /*新元素插入*/ L-Length+; /*顺序表长度增1 */ return OK; /*插入成功，返回*/ 返回到本节目录 5插入操作 插入算法的时间性能分析： 顺序表插入操作大约需移动表中一半数据元 素，其时间复杂度为(n)。 返回到本节目录 2.2.2 顺序表的基本操作实现 6. 删除操作 线性表的删除操作是指将第 i 个元素从顺序表中去 掉，删除后顺序表表长减1，原顺序表如图2-5所 示。 返回到本节目录 6. 删除操作 步骤如下： (1) 将要删除的元素值赋给指针变量*x，如图 2-6所示 返回到本节目录 6. 删除操作 步骤如下： (2) 将ai+1an 之间的结点依次顺序向前移 动，如图2-7所示。 (3) 顺序表的长度减1，删除成功，并返回，算 法描述见算法2.7。 返回到本节目录 6. 删除操作 算法2.7 int DelElem (SeqList *L, int i, ElemType *x) int j; if (L-Length=0) printf (“顺序表为空！“); return ERROR; /*表空，不能删除*/ if (iL-Length) /*检查是否空表及删除位置的合法性*/ printf (“不存在第i个元素“); return ERROR; *x= L-datai-1; /*用指针变量*x返回删除的元素值*/ for(j=i;jLength-1;j+) /*结点移动*/ L-dataj-1=L-dataj; L-Length-; /*顺序表长度减1*/ return OK; /*删除成功，返回*/ 返回到本节目录 6. 删除操作 删除算法的时间性能分析： 与插入操作相同，其时间主要消耗在了移动表 中元素上，（大约需要移动表中一半的元素 ），显然该算法的时间复杂度为(n)。 返回到本节目录 2.2.2 顺序表的基本操作实现 7 顺序表的输出操作 扫描顺序表L，输出各元素的值，算法描述见 算法2.8。 算法2.8 void DispList(SeqList *L) int i; for(i=0;iLength;i+) printf(“%5d “, L-datai); 返回到本节目录 2.3 链表 v2.3.1 单链表 v2.3.2 单链表的基本操作实现 v2.3.3 链表的变形 返回到总目录 2.3.1 单链表 1. 单链表的定义 线性表的链式存储结构是指用一组任意的存储单元 （可以连续，也可以不连续）存储线性表中的数 据元素。为了反映数据元素之间的逻辑关系，对 于每个数据元素不仅要表示它的具体内容，还要 附加一个表示它的直接后继元素存储位置的信息 ，这样构成的链表称为线性单向链接表，简称单 链表，其结点结构如图2-8所示。 数据域后继指针域 datanext 图2-8 单链表的结点示意图 其中，data部分称为数据域，用于存储一个数据元素（ 结点Node）的信息。next部分称为指针域，用于存储其 直接后继的存储地址的信息。 返回到本节目录 2.3.1 单链表 v 单链表分为带头结点（其next域指向链表第一个结点的存储地址）和 不带头结点两种类型。在许多情况下，带头结点的链表中每个结点的 存储地址均放在其前驱结点中，这样算法对所有的结点处理可一致化 ，因此，本节讨论的单链表均指带头结点的单链表。带头结点的单链 表如图2-9所示。 图2-9 带头结点的单链表 其中，头结点的数据域可以不存储任何信息，也可以存放特殊的信息 ；头结点的指针域存储链表中第一个结点的地址。当头结点的指针域 为空（即NULL或用表示），则此表为空表。在非空表中，当某个 结点的指针域为空，表示它为链表的最后一个结点。 返回到本节目录 2.3.1 单链表 v链式存储特点：线性表的链式存储结构是通 过指针来表示元素之间的逻辑关系，不再有 逻辑顺序与物理存储顺序一致的特点，是非 顺序存储结构。 返回到本节目录 2.3.1 单链表 2. 单链表的类型定义 #define OK 1 #define ERROR 0 #define OVER -1 typedef char ElemType; /*定义ElemType为char类型*/ typedef struct node /*单链表存储类型*/ ElemType data; /*定义结点的数据域*/ struct node *next; /*定义结点的指针域*/ LinkList; 返回到本节目录 2.3.2 单链表的基本操作实现 1. 单链表的初始化 单链表的初始化即构造一个仅包含头结点的空单链表L ，算法描述见算法2.9。 算法2.9 LinkList *InitList() /*申请一块LinkList类型的存储单元的操作，并 将其地址赋值给头指针变量L*/ LinkList *L; L=(LinkList*)malloc(sizeof(LinkList); L-next=NULL; return L; /*头结点L指针域为空， 表示空链表*/ 返回到本节目录 2.3.2 单链表的基本操作实现 2单链表的建立 （1）头插法建表 在初始化链表后，每读取有效的数据都为其生成新结点s，并将读取的数 据存放到新结点s的数据域中，然后将新结点插入到当前链表L的表 头上，直到循环结束为止，算法描述见算法2.10。 算法2.10 void CreateList(LinkList *L) LinkList *s; char ch; while(ch=getchar()!=#) /*判断输入数据是 否有效*/ s=(LinkList *)malloc(sizeof(LinkList); /*生成新结点 */ s-data=ch; /*将数据放入新结点的数据域*/ s-next=L-next; /*将新结点的指针域存放头结点的指 针域*/ L-next=s; /*将新结点插入头结点之后*/ 返回到本节目录 2.3.2 单链表的基本操作实现 （2）尾插法建表 头插法建立链表虽然算法简单易理解，但生成的链表中结点的次序和原 输入的次序相反。而尾插法建立链表可实现次序的一致，该算法依旧 在初始化链表后，但需增加一个尾指针last，使其指向当前链表的尾 结点，算法描述见算法2.11。 算法2.11 void CreateList(LinkList *L) LinkList *s,*last; char ch; last=L; /*last始终指向尾结点，开始时指向头结点 */ while(ch=getchar()!=#) /*判断输入数据是否有效*/ s=(LinkList *) malloc(sizeof(LinkList); /*生成新结点 */ s-data=ch; /*将数据放入新结点的数据域*/ s-next=NULL; /*将新结点的指针域为空*/ last-next=s; /*将新结点插入表尾*/ last=s; /*将last指针指向表尾结点*/ 返回到本节目录 2.3.2 单链表的基本操作实现 3求单链表的长度 求长度就是求单链表中数据元素的个数。求带头结点的单链表L的长度需 设一个动态指针p指向头结点，计数器j初始值为0，p指针所指结点 后面若还有结点，p就向后移动，每次移动一次，计数器j值增1，直 到p所指结点后面为空结束，则计数器j的值即为表的长度，算法描述 见算法2.12。 算法2.12 int GetLength (LinkList *L) LinkList *p; int j=0; p=L; /*p指向链表的头结点*/ while(p-next!=NULL) /*判断p所指结点后面是否为空*/ p=p-next; /*p向所指结点的后面移动*/ j+; /*计数器值增1*/ return j; /*计数器j的值为表长度*/ 返回到本节目录 2.3.2 单链表的基本操作实现 4查找操作 单链表的查找分为按值与按序号查找，下面将分别介绍这两种方法的实 现，读者可根据具体的问题相应选择所需的查找方法。 （1）按值查找 算法思路：从链表的第一个元素结点开始，由前向后依次比较单链表中 各结点数据域中的值，若某结点数据域中的值与给定的值x相等，则 返回该结点的指针值p；否则继续向后比较直到表结束。若整个单链 表中没有这样的结点，则返回空NULL值，算法描述见算法2.13。 算法2.13 LinkList *Locate(LinkList *L,ElemType x) LinkList *p; p=L-next; /*p指向链表的第一个结点*/ while(p!=NULL return p; 返回到本节目录 2.3.2 单链表的基本操作实现 （2）按序号查找 算法思路：从链表的头结点开始，判断当前结点序号是否是第i个，若是，则返回 该结点指针值p；否则继续向后查找直到表结束。若没有第i个结点，则返回 空NULL值，算法描述见算法2.14。 算法2.14 LinkList *GetList(LinkList *L,int i) LinkList *p; int j=0; p=L; /*p指向链表的头结点*/ while(p-next!=NULL j+; if(j=i) /*判断与给定的序号是否相等*/ return p; else return NULL; 返回到本节目录 2.3.2 单链表的基本操作实现 5插入操作 顺序表的插入操作需要移动大量的数据元素， 而链表的插入只需修改指针而无需移动原表 元素，那链表的插入操作是如何实现呢？ （1）在已知结点p之后插入一新结点s 已知结点p为链表中任意结点，先创建一个以x 为值的新结点s，则插入操作步骤如下： 先将结点s的指针域指向结点p的下一个结点（ 执行语句s-next=p-next）。 再将结点p的指针域改为指向新结点s（执行语 句p-next=s）。 返回到本节目录 5插入操作 插入结点的过程如图2-10所示，算法描述见算法2.15。 注：插入操作的与语句执行顺序不能颠倒，否则原p指针其后的链表将丢失。 算法2.15 void Ins_Elem(LinkList *p,ElemType x) LinkList *s; s=(LinkList *)malloc(sizeof(LinkList); /*生成新结点s*/ s-data=x; /*将数据x放入新结点的数据域*/ s-next=p-next; /*将新结点s的指针域与p结点后面元素相连*/ p-next=s; /*将p与新结点s链接*/ 返回到本节目录 5插入操作 （2）在第i个位置插入新结点s 由于单链表的结点结构是单向后指的，因此要完成此操作需要找到第i结 点的前驱结点即第i1结点的指针p，此时可调用按序号查找 GetList()函数求出p指针地址，然后在调用在已知结点p后方插入 新结点Ins_Elem()函数操作即可，算法描述见算法2.16。 算法2.16 int InsElem(LinkList *L, int i, ElemType x) LinkList *p; p=GetList(L,i-1); /*调用按序号查找函数GetList()，求出第i-1 个元素地址p*/ if(p!=NULL) /*判断查找的元素地址p是否存在*/ Ins_Elem(p,x); /*调用在已知结点p后插入结点函数 Ins_Elem()*/ return OK; else return ERROR; 返回到本节目录 5插入操作 插入算法的时间性能分析： 链表插入操作主要时间耗费在查找操作 上，其时间复杂度为(n)。 返回到本节目录 2.3.2 单链表的基本操作实现 6删除操作 顺序表的删除操作同样需要移动大量的数据元素，而 链表的删除只需修改指针而无需移动原表元素，那 链表的删除操作是如何实现呢？ （1）删除已知结点p之后结点s 已知结点p为链表中除终端结点以外的任意结点，先将 结点s中的数据域中的值赋给指针变量*x，则删除 操作步骤如下： 结点p指针域指向结点s下一个结点（执行语句p- next=s-next）。 释放s结点空间（执行语句free(s)）。 返回到本节目录 6删除操作 删除结点的过程如图2-11所示，算法描述见算法2.17。 图2-11 在结点p之后删除结点s 算法2.17 void Del_Elem(LinkList *p,ElemType *x) LinkList *s; s=p-next; /*s为要删除结点*/ *x=s-data; /*将要删除的数据放入指针变量*x中*/ p-next=s-next; /*将p结点的指针域与s结点后面元素 相连*/ free(s); /*释放结点s*/ 返回到本节目录 6删除操作 （2）删除未知结点（如第i个结点）s 首先求出第i结点的前驱结点（第i-1结点）p的地址，可调用按序号查找 GetList()函数求出p指针地址，然后再调用删除已知结点p之后结点s的 DelList()函数操作即可。算法中注意if(p!=NULL p=GetList(L, i-1); /*调用按序号查找第i-1个元素地址p函数*/ if (p!=NULL /*调用删除已知结点p之后结点函数*/ return OK; else return ERROR; 返回到本节目录 6删除操作 v删除算法的时间性能分析： 链表删除操作也主要时间耗费在查找操作上， 其时间复杂度为(n)。 返回到本节目录 2.3.2 单链表的基本操作实现 7单链表的输出操作 扫描单链表L，输出各元素的值，算法描述见算法 2.19。 算法2.19 void DispList(LinkList *L) LinkList *p; p=L-next; while(p!=NULL) printf(“%c“,p-data); p=p-next; 返回到本节目录 2.3.3 链表的变形 1循环单链表 循环链表是另一种形式的链式存储结构。对于单链表而言，最后一个结 点的指针域为空，如果将该链表中最后一个结点的指针域指向头结点 ，整个链表形成一个环，就构成了循环单链表，如图2-12所示。由 此，从表中的任意结点出发均可找到表中的其他结点。在循环单链表 上的操作基本上与非循环的单链表相同，只是将原来判断指针是否为 NULL，改为是否是头指针L即可。 图2-12 带头结点的循环单链表 返回到本节目录 2.3.3 链表的变形 2双链表 （1）双链表的定义 在单链表结点中只有一个指向直接后继的指针域next，这样从某个结点 出发只能顺指针方向寻找它的后继结点。若要寻找结点的直接前驱， 则需从头指针出发查找前驱。若希望能够快速查找一个结点的直接前 驱，则可以再增加一个指向其直接前驱的指针域prior，这样就构成 了双向链接表，简称双链表，其结点结构如图2-13所示。 图2-13 双链表的结点示意图 其中，data部分称为数据域，用于存储一个数据元素（结点 Node）的信息。prior部分称为前驱指针域，用于存储其直 接前驱的存储地址的信息。next部分称为后继指针域，用于 存储其直接后继的存储地址的信息。 前驱指针域数据域后继指针域 priordatanext 返回到本节目录 2双链表 （2）双链表的类型定义 typedef char ElemType; /*定义 ElemType为char类型*/ typedef struct dunode /*双链表存储类 型*/ ElemType data; /*定义结点的数据 域*/ struct dunode *prior; /*定义结点的前驱指 针域*/ struct dunode *next