计算机软件技术基础第4章 数据结构

1、 计算机软件技术基础 计算机软件技术基础 计算机软件技术基础 信息管理与信息系统信息管理与信息系统 1 第四章第四章 数据结构数据结构 计算机软件技术基础 计算机软件技术基础 计算机软件技术基础 信息管理与信息系统信息管理与信息系统 2 4.1 数据结构概述数据结构概述 4.1.1 数据结构的定义数据结构的定义 1、数据数据(data)：数据是一些可以输入到计算机中的描述客观事物的符 号,即信息的载体。这些符号可以是数值、字符、图象等。在计算机领 域，人们把能够被计算机加工的对象，或者说能够被计算机输入、存储、 处理、输出的一切信息都叫做数据。 2、数据元素数据元素(element)：数据元素

2、是算法可以处理的最小数据单位，是 一个数据整体中相对独立的元素。数据元素可以是简单数据，也可以由 若干个简单数据（数据项）组成数据元素。数据和数据元素是相对而言 的，是整体和个体之间的关系。例如，对一个字符串来说，每个字符都 是它的数据元素；对一个数组来说，每个数组元素都是它的数据元素。 本书中，经常将数据元素、数据结点、结点、记录这些概念不加区别的 使用，它们表示的是同一概念。 计算机软件技术基础 计算机软件技术基础 计算机软件技术基础 信息管理与信息系统信息管理与信息系统 3 3、数据项：数据元素由更小的单位数据项数据项(item)（或成员）所组成，一 个记录一般包括一个或若干个数据项。

3、4、数据之间的联系：现实世界中的客观对象在计算机中是用数据来描述的， 在现实世界当中，客观对象是有联系的，因此数据之间也是有联系的，数据 联系是数据本身所具有的特性。 5、数据结构数据结构（data structure）：简单的说，数据结构就是研究数据和数据 之间联系的一门学科，它包括三个方面。 数据的逻辑结构 数据的物理结构 数据的运算 数据结构通常用二元组表示，其形式如下： Data_struct=(D,R) 其中D为数据元素的集合，R为数据元素之间关系的集合。即： D=ai | 1in,n0 R=rj | 1jm,m1 ai 为第i个数据元素，n为数据元素的个数，特别地，当n=0，D为空

4、集，则 无结构可言。rj表示第j个关系，m为关系的个数。 计算机软件技术基础 计算机软件技术基础 计算机软件技术基础 信息管理与信息系统信息管理与信息系统 4 4.1.2 数据结构的基本内容数据结构的基本内容 数据结构的基本内容包括数据的逻辑结构、数据的存储结构和数据的运算。 1、 数据的逻辑结构数据的逻辑结构 数据元素之间的逻辑关系就是数据的逻辑结构。 一般情况下，一组数据元素并不是杂乱无章的，而是具有某种联系形式。这 里的联系形式指数据元素与元素间的相互关系。数据之间的联系可以是固 有的，也可以是根据数据处理的需要人为定义的。数据元素之间的联系方 式可分为一对一、一对多和多对多三种，根据数

5、据元素之间联系的不同特 性，数据的逻辑结构通常有以下三种基本结构。 线性结构线性结构 数据结构中数据元素之间的联系方式是一对一的。 树形结构树形结构 数据结构中数据元素之间的联系方式是一对多的。 图形结构或网状结构图形结构或网状结构 数据结构中数据元素之间的联系方式是多对多一的。 通常我们也把数据的逻辑结构分为线性结构和非线性结构，树形结构和图形 结构统称为非线性结构。 研究数据结构的目的是为了在计算机上实现对它的操作，因此还需研究如何 在计算机中表示数据结构。 计算机软件技术基础 计算机软件技术基础 计算机软件技术基础 信息管理与信息系统信息管理与信息系统 5 2、 数据的物理结构数据的物理

6、结构 数据结构（包括数据及其数据之间的关系）在计算机存储器上的存储表示称为 数据的物理结构数据的物理结构或存储结构存储结构。数据结构研究的是数据及其数据之间联系的学科， 因此在研究数据的存储结构时，要求数据的存储方式既能表示数据又能表示数 据之间的联系。常用数据的存储结构有： 顺序存储 链式存储 索引存储 哈希存储 顺序存储结构的特点是借助元素在存储器中的相对位置存储器中的相对位置来表示数据元素之间的 关系；链式存储结构是借助指示元素存储位置的指针指针表示数据元素之间的关系； 索引存储结构是为存储的数据建立一个索引表，访问数据时先在索引表中查找， 再根据索引表的相关信息访问数据；哈希存储是建立

7、数据的关键字和存储地址 之间的对应关系（哈希函数），这样访问一个数据时，可根据哈希函数直接获 得该数据在计算机中的存储地址，到该地址访问数据。 计算机软件技术基础 计算机软件技术基础 计算机软件技术基础 信息管理与信息系统信息管理与信息系统 6 由于数据的存储结构有多种，所以一种数据的逻辑结构可以根据需要表示成 一种或多种存储结构，只要存储结构既能表示数据，也能表示数据之间的联 系或者存储结构能满足用户对数据的某种操纵要求即可。在后面的章节中， 读者可根据具体的存储实例了解到一种数据的逻辑结构可以采用不同的存储 方式进行存储。 数据的逻辑结构和物理结构是数据结构两个密切相关的方面，以后读者可看

8、 到，一个算法的设计取决于选定的逻辑结构，而算法的实现依赖于采取的存 储结构。算法的设计取决于数据的逻辑结构，算法的实现依赖于采用的存储 结构，在不产生误解的情况下我们也将数据的逻辑结构称为数据结构 如何描述存储结构呢？虽然存储结构涉及数据元素及其关系在存储器中的存 储方式，但由于本书是在高级语言的层次上讨论数据结构的操作，因此可以 借助高级语言中提供的“数据类型”来描述它。例如可以用C语言中提供的 “数组类型”来描述顺序存储结构，用“指针”来构造链式存储结构。 计算机软件技术基础 计算机软件技术基础 计算机软件技术基础 信息管理与信息系统信息管理与信息系统 7 检索（查找）：检索（查找）：在

9、给定的数据结构中，找出满足一定条件的结点来，这个条件往 往是一个或几个数据项的值。 排序：排序：根据给定的条件，将数据结构中所有结点重新排列顺序 插入：插入：在给定的数据结构中，根据某些条件，将一个结点插入到一个合适的位置。 删除：删除：在给定的数据结构中，根据某些条件，将一个结点删除。 修改：修改：修改数据结构中某些结点的值。 运算的种类很多，同一种运算也存在各种各样的算法。在一种数据结构中要进行 那一种或那几种运算，往往取决于要解决的实际问题。完成一种指定的运算， 当然要选一种最好的算法。但对一种具体的数据结构来说，完成一种运算的 效率较高，完成另外一种则可能较低，对另一种数据结构来说，情

10、况可能正 好相反。因此，要解决一个实际问题，数据结构的设计和算法的选择要结合 起来考虑，对各种情况要反复比较，最终选择一个较好的数据结构和高效率 的算法。 3、数据的运算、数据的运算 研究数据结构，除了研究数据结构本身以外，还要研究与数据结构相关联的运 算。这里的运算是指对数据结构中的数据元素进行的操作处理，而这些操作与 数据的逻辑结构和物理结构有直接的关系，结构不同，则实现方法也不同。运 算的种类很多，但常用的有以下几种： 计算机软件技术基础 计算机软件技术基础 计算机软件技术基础 信息管理与信息系统信息管理与信息系统 8 4.2 线性表线性表 4.2.1 线性表的逻辑结构线性表的逻辑结构

11、线性表线性表（linear list）是具有相同特性的数据元素的一个有限序列。该序列中 所含元素的个数叫线性表的长度，用n表示，n0。当n=0时，线性表是一个 空表，即表中不包含任何元素。当n0时，设序列中的第i个元素为ai (1in)， 则线性表的一般表示为： （a1，a2，ai，an） 其中，a1为第一个元素，又称为表头元素，an为最后一个元素，又称为表尾 元素。每一个元素在表中的位置用其下标来表示。线性表具有如下特点： 计算机软件技术基础 计算机软件技术基础 计算机软件技术基础 信息管理与信息系统信息管理与信息系统 9 1）线性表的数据元素ai具有相同特性，在不同的情况下含义不同。可以为

12、一个数、 一个字符或更复杂的信息；在一个表中，ai类型必须相同。 2）表非空的情况下，除第一个元素以外，每个元素都有且仅有一个直接前驱；除 最后一个元素以外，每个元素都有且仅有一个直接后继。 线性表中的元素在逻辑上是有序的，即第i个元素处在第i-1和第i+1个元素的中 间，这种逻辑上的有序性就是一种线性关系，所以线性表的逻辑结构是线性结 构。 用二元组表示为： Linear_list=(D,R) D= ai | 1in,n0, aielemtype /* elemtype为任何数据类型 */ R=r|r=1in-1 下面给出几个线性表的例子： （0，1，2，3，4，5，5，6，7，8，9，-，

13、 =） （12，34，56，78，89，54，76，32，98） （“basic”, “fortran”, “pascal”, “cobol”）” 其中，第一个线性表数据元素为字符型，第二个线性表数据元素为数值型，第 三个线性表数据元素为字符串。 计算机软件技术基础 计算机软件技术基础 计算机软件技术基础 信息管理与信息系统信息管理与信息系统 10 4.2.2 线性表的存储结构线性表的存储结构 线性表的存储结构有两种，即顺序存储结构和链式存储结构。具有顺序存 储结构的线性表称为顺序表顺序表，具有链式存储结构的线性表称为线性链表线性链表。 根据不同的需要对线性表可以进行多种操作，其基本运算有：

14、清表 清除表中的结点使其成为空表。 排序 根据给定的条件，将表中结点重新排列顺序。 插入 根据条件在表中插入一个结点。 删除 根据某些条件，将一个结点删除。 修改 修改表中给定结点的值。 检索（查找） 查找表中某一特征的结点。 求长 求线性表的长度。 对线性表所采取的存储结构不同，其实现方法也不一样。下面分别介绍。 计算机软件技术基础 计算机软件技术基础 计算机软件技术基础 信息管理与信息系统信息管理与信息系统 11 1、 线性表的顺序存储结构及其算法线性表的顺序存储结构及其算法 线性表的顺序存储结构是线性表的一种最简单的存储结构，其存储方法是：在 内存中为线性表开辟一块连续的存储空间，该存储

15、空间所包含的存储单元数要 大于等于线性表的长度（假定每个存储单元存储线性表中的一个元素）。 因为一个数组在内存中占据一段连续的存储单元，所以可以借助数组来为线性 表的顺序存储开辟空间，如图4.1所示。其中L为每个元素占据的字节数， Loc(a1)为线性表的起始地址。 存储地址 Loc(a1) Loc(a1)+L Loc(a1)+L*(i-1) Loc(a1)+L*(n-1) 数据元素序号 1 2 i n a1 a2 ai an 图4.1线性表的顺序存储结构示意图 内存状态 另外为了存储线性表的长度，还要定 义一个整型变量。若将线性表的顺序 存储结构定义为一个数组与一个整型 变量，则可将它们放在

16、一个结构体中， C语言定义形式为： #define N 1000 /* N为线性表的最 大元素个数 */ typedef struct list elemtype vN; int len; LIST; 其中，N为线性表开辟的存储单元数， 可以根据需要改变其大下。elemtype 为线性表中元素的类型。 计算机软件技术基础 计算机软件技术基础 计算机软件技术基础 信息管理与信息系统信息管理与信息系统 12 在线性表的顺序存储结构中，借助存储单元的顺序性在线性表的顺序存储结构中，借助存储单元的顺序性 表示数据元素逻辑上的顺序性表示数据元素逻辑上的顺序性，可以看到逻辑上相邻 的两个元素在物理位置上也

17、相邻，因此可以随机存取 表中的任一元素，它的存贮位置可以用一个直观、简 单的公式来表示(参看4.3特殊线性表)，我们称顺序我们称顺序 存储随机访问存储随机访问。下面是顺序存储的线性表的几个常用 的算法。 线性表顺序存储结构的几个常用算法 计算机软件技术基础 计算机软件技术基础 计算机软件技术基础 信息管理与信息系统信息管理与信息系统 13 插入运算 根据给定的条件不同，插入算法也不一样，如果要 在线性表L的第i(0iL.len)个位置上插入一个元素x， 那么只需要将第i个元素及其以后的所有元素后移 一位，第i个位置上存入x，线性表的长度加1，如 图4.2所示。 LIST inslist(LIS

18、T L,int i,elemtype x) if (L.len= =N) printf(“OVERFLOWn”); elseif (iL.len) printf(“position ERRORn”); else for(j=L.len-1;j=i;j-) L.vj+1=L.vj;L.vi=x;L.len+; return L 从算法中可见，当i的位置不 合适时，插入无法进行。当 表中有L.len个元素时，插入 位置可以是从0到L.len。当 插入位置在最后一个元素的 后边（即下标L.len）时，不 需要移动元素。 如果插入条件是：在线性表 中的某一元素之前（或之后） 插入一元素，则应先查找该

19、元素的位置，然后利用上述 方法实现即可。从图4.2读者 可以看到在数据x插入前后， 线性表的有效元素都是从下 表0到下标L.len-1。读者可 自行编写该算法。 计算机软件技术基础 计算机软件技术基础 计算机软件技术基础 信息管理与信息系统信息管理与信息系统 14 删除运算 将线性表中的第i个元素删除的情况，可以用图4.3所示的方法实现。 只要将从第i+1个元素到最后一个元素向前各移动 一个元素，表的长度减一即可。相应的算法为： LIST dellist(LIST L,int i) /* 删除线性表L中的第i 个元素 */ if (i=L.len) printf(“position ERROR

20、n”); else for(j=i+1;j=L.len-1;j+) L.vj-1=L.vj; L.len-; return L 从算法中可见，当i的位置不合 适时，删除无法进行。 从图4.3读者同样可以看到，在 第i个元素删除前后，线性表的 有效元素都是从下表0到下标 L.len-1。 如果删除条件是：删除线性表 中某一特定元素x，则应先查找 该元素x的位置，然后利用上述 方法实现即可。读者可自行编 写该算法。 计算机软件技术基础 计算机软件技术基础 计算机软件技术基础 信息管理与信息系统信息管理与信息系统 15 检索（查找） 在线性表中检索值为x的元素，检索的方法很多，有顺序检索、折半检 索

21、、分块检索、散列检索等。下面仅介绍顺序检索，方法是，从线 性表的第一个元素起，依次使每一个元素与值为x的元素进行比较， 直到某个元素与x 相等（既查找成功）或查完所有元素都找不到值 为x的元素（查找失败）为止。算法为： int searchlist(LIST L,elemtype x) for(i=0;inext= =NULL 链表加上头结点以后将空表和非空表的处理统一起来，因而简化了单链表的 实现算法。 下面介绍在这种存储结构上链表的几个主要操作。 带头结点单链表的查找带头结点单链表的查找 设H为一带头结点的单链表的头指针，在线性表中查找第i（i0）个元素所在的结点。 要查找单链表中的某一结

22、点，必须从头指针出发，沿结点的指针域往后找直到找到 所要结点为止。算法如下： NODE *get(NODE *H,int i) NODE *p; int j=1; p=H-next; while(p!=NULL) j+; if (p!=NULL) return p; /*返回指向待查找结点的指针*/ else return NULL; /* 查找的位置不合适 */ 查找元素的时间复杂度为O(n)。 计算机软件技术基础 计算机软件技术基础 计算机软件技术基础 信息管理与信息系统信息管理与信息系统 20 带头结点单链表的插入带头结点单链表的插入 设H为一带头结点的单链表的头指针，在线性表的两个元素

23、a和c之间插入一个 元素b，设p为存储数据元素a结点地址的指针变量，设q为存储数据元素b结 点地址的的指针变量，如图4.6(a)所示 p q p ac b q (a) 插入前 (b) 插入后 图4.6单链表的插入示意图 ac b 在一个以链式存储的线性表的某个位置上插入一个结点，只需要改变其链 接关系就可以。从图中可以看出插入结点b时，需要修改两个指针，将a结 点的指针域的值由指向结点c改为指向结点b，再使结点b的指针域的值指 向结点c，从而实现改变a，b和c之间的链接关系，插入后各元素的关系如 图4.6(b)所示。修改指针关系的语句为： q-next=p-next; p-next=q; 计算

24、机软件技术基础 计算机软件技术基础 计算机软件技术基础 信息管理与信息系统信息管理与信息系统 21 下面的算法是在链表H中第 i个位置上插入一元素为x的结点： void insnode(NODE *H,int i,int x) NODE *p,*q; if (i= =1)p=H; else p=get(H,i-1); /* 查找插入元素的位置 */ if (p!=NULL) q=(NODE*)malloc(sizeof(NODE); q-date=x; q-next=p-next; p-next=q; /* 实现插入 */ else printf(“ i表长，插入位置错误n”); 与顺序表的插

25、入比较，链表的插入更容易实现，不需要移动元素，只须修改 两个指针，时间复杂度为O(1)。但是为了找到插入位置，需花费的时间复杂 度为O(n)。 计算机软件技术基础 计算机软件技术基础 计算机软件技术基础 信息管理与信息系统信息管理与信息系统 22 带头结点单链表的删除带头结点单链表的删除 删除操作和插入基本相同，应先找到待删结点的前驱结点的位置后再完成删 除。如图4.7（a）所示，设b为待删除的元素，p为指向待删元素的前一结点 的指针，删除结束后元素a的后继由b改为c，操作中将b所在结点的地址记为q， 以便处理和回收结点，如图4.7（b）所示。 p p ac b q (a) 删除前 (b) 删

26、除后 图4.7单链表的删除示意图 p ac b q 删除语句为： q=p-next; p-next=q-next; free(q); 计算机软件技术基础 计算机软件技术基础 计算机软件技术基础 信息管理与信息系统信息管理与信息系统 23 下面的算法是在头指针为H的带头结点的单链表中删除第i个结点： void delnode(NODE *H,int i) NODE *p,*q; if (i= =1)p=H; else p=get(H,i-1); /* 查找删除元素的位置 */ if (p=NULL)|(p-next=NULL) printf(“表中无此结点n”); else q=p-next;

27、p-next=q-next; free(q); 与顺序表的删除比较，链表的删除也更容易实现，不需要移动元素， 只须修改几个指针，时间复杂度为O(1)。同样为了找到删除位置，需 花费的时间复杂度为O(n)。 计算机软件技术基础 计算机软件技术基础 计算机软件技术基础 信息管理与信息系统信息管理与信息系统 24 4.2.3算法评价及改进算法的各种策略 在前面两节我们讲解了线性表的两中存储方式，在这两种存储方式中我 们采用了不同的方式将线性表表示到计算机中。用这两种存储方式存储 线性表时，既表示了数据，也表示了数据之间的联系，同时我们看到， 在实现线性表的相关运算（查找、插入、删除）时，两种存储结构

28、采用 的算法完全不同，正如我们在4.1.1.中所讲：算法的设计取决于数据的 逻辑结构，算法的实现依赖于采用的存储结构。下面我们分析线性表的 顺序存储和链式存储在完成线性表的插入和删除算法的时间复杂度和空 间复杂度。 1、算法评价 时间复杂度时间复杂度 前面在2.2.3节中,我们讲到算法的时间复杂度的估算通常有两中方法： 平均运算量和最坏的情况，对于具有n个元素的线性表的插入算法，在线 性表第1,2,i,i+1,n+1个位置任意一个位置进行插入在实际运行时都有 可能，一个算法在实际使用的过程中，运行的次数很大，因此在任意一 个位置的插入运算可以看做是一个随机量，在进行平均运算量的估算时， 按在每

29、个位置插入的概率是均等的。 计算机软件技术基础 计算机软件技术基础 计算机软件技术基础 信息管理与信息系统信息管理与信息系统 25 下面我们估算线性表的顺序存储结构和链式存储结构的时间复杂度。 顺序存储结构顺序存储结构：顺序存储的线性表在第i个位置进行插入时,应将i到n个位置上的 元素依次向后移动，将要插入的元素存储到第i个存储单元，实现在线性表的第i 个位置插入元素的运算。 计算机软件技术基础 计算机软件技术基础 计算机软件技术基础 信息管理与信息系统信息管理与信息系统 26 链式存储结构：链式存储结构：在链式存储的线性表的第i个位置插入元素，只要能够获得一个 指向第i-1个元素的指针，插入

30、运算只需要进行下列面的两个基本运算： q-next=p-next; p-next=q; 换句话说，线性表的链式存储结构的插入运算的基本运算量，和插入的位置 无关，在线性表的任意位置插入元素的基本运算量均为2，基本运算量不随数 据规模的增长而变化，其时间复杂度为：O（1） 空间复杂度空间复杂度 假设线性表的每个元素存储到计算机中，向系统申请的字节数为k，线性 表长度为n。 用顺序存储结构存储线性表，则相应的算法运行时，向系统申请的临时 空间字节数为： k*n 用链式存储结构存储线性表，每个结点的指针域向系统申请的字节数为2， 则相应的算法在运行时向系统申请的临时空间字节数为： （k+2）*n 计

31、算机软件技术基础 计算机软件技术基础 计算机软件技术基础 信息管理与信息系统信息管理与信息系统 27 用线性表两种不同的存储方式设计算法时，从向系统申请的总的字节数来说， 链式存储结构由于每个结点除存储线性表的元素外，还需开辟存储下一个结点 地址的指针，因此链式存储结构向系统申请的总字节数比顺序存储结构多 （k+2）*n k*n），但是，顺序存储的线性表向系统申请的是连续的存储单 元（地址号连续的k*n个字节），而链式存储的线性表向系统申请的是随机的 存储单元（n个随机的（k+2）字节单元），从这一点上说，顺序存储的线性 表比链式存储的线性表对系统存储空间的要求高，链式存储的线性表的空间复 杂

32、度比顺序存储的线性表的空间复杂度小，即从空间复杂度上讲，链式存储的 线性表优于顺序存储的线性表。 比较线性表的链式存储结构和顺序存储结构编写的线性表的插入算法，我们可 以看到，链式存储的线性表的算法的编写对编程者有更高的要求。 综上所述，线性表的链式存储和顺序存储各有自己的特点，程序设计者在实际 编程中可根据实际情况选择相应的存储方式存储线性表、操纵线性表。 查找算法的复杂度读者可自行分析。 计算机软件技术基础 计算机软件技术基础 计算机软件技术基础 信息管理与信息系统信息管理与信息系统 28 2、算法的策略 不带头结点的单链表和带头结点的单链表不带头结点的单链表和带头结点的单链表 通过前面的

33、研究我们知道，链接存储结构是线性表的一种存储方式。在构造 链式存储时我们采用的是将线性表的第1个元素存放放在单链表的第2个结点， 线性表的第2个元素存放放在单链表的第3个结点，线性表的第i个元素存 放放在单链表的第i+1个结点,这样构造的单链表我们称为带头结点的单链带头结点的单链 表表，当然在构造单链表时我们也可以将线性表的第1个元素存放在单链表的第 1个结点，线性表的第2个元素存放放在单链表的第2个结点，线性表的第 i个元素存放放在单链表的第i个结点，这样构造的单链表我们称为不带头不带头 结点的单链表结点的单链表，因此我们说在构造线性表的链式存储结构时，是否带头结点 是一种构造存储的策略，在

34、4.2.2线性表的插入、删除、查找运算中，链式 存储的线性表采用的是带头结点的单链表，下面我们给出用不带头结点的单 链表存储线性表插入运算的算法。用此算法和上面带头结点的单链表中删除 第i个元素的算法进行比较，读者可发现两种方法的不同之处。 在不带头结点的单链表中进行操作时，要区分第一个结点和表中结点，因 为第一个结点的地址值发生变化后，表示链表的头指针H的值也会发生变化 （参考图4.4），比如删除操作，若删除的元素为a1，则删除后H的值为a2 的地址，若是在带头结点的单链表中进行操作则不同（参考图4.5（a）， 此时即使删除的元素为a1，删除后H的值也不会发生变化。 计算机软件技术基础 计算

35、机软件技术基础 计算机软件技术基础 信息管理与信息系统信息管理与信息系统 29 void del(NODE *H,int i) /*将H为头指针的链表中第i个结点删除 */ NODE *p,*q; int m=1; if(H!=NULL) q=H; if(i= =1) H=H-next; /* 删除表头结点 */ free(q); else while(q!=NULL m+; if(q=NULL) printf(%d not been foundn,i); /* 没找到待删结点 */ else p-next=q-next; /* 删除结点q */ free(q); else printf(th

36、e list emptyn); /* 表空 */ 通过带头结点和不带头结点两种不同的存储线性表的策略，我们明显地看到， 在线性表的插入、删除运算中，带头结点的单链表比不带头结点的单链表算法 思路简洁、结构简单。 计算机软件技术基础 计算机软件技术基础 计算机软件技术基础 信息管理与信息系统信息管理与信息系统 30 循环单链表和双向链表循环单链表和双向链表 采用链式存储的线性表在算法设计中，对线性表的操作我们总是利用头指针 找到被访问的结点，对该结点进行访问，而且这种访问是单方向的（如果我 们需要访问该结点的前一个结点，又必须从头结点开始），这种情况下采用 单链表的存储方式，运算的效率低。如果我

37、们构建循环单链表和双向链表来 存储线性表，这样对上述情况将会有所改观。 循环单链表循环单链表 如果有一个单链表其表尾元素的指针域的值不为NULL，而让它指向头结点， 这样的链表叫循环单链表或环形链表。图4.8为带头结点的循环链表示意 图： Ha1an (a) 循环单链表循环单链表a2空的表循环单链表空的表循环单链表 图图4.8循环单链表示意图循环单链表示意图 H Ha1an (a) 循环单链表 a2 (空的表循环单链表 图4.8循环单链表示意图 H 计算机软件技术基础 计算机软件技术基础 计算机软件技术基础 信息管理与信息系统信息管理与信息系统 31 循环单链表与单链表的大部分操作相同，如插入

38、、删除、查找等。与单链表比较有 以下不同点。 判断链表结束的条件不同。设p为链表中任意一结点的指针，在单链表中当某 一结点p的next域指向NULL时，则说明链表操作结束（p-next= =NULL）。而 在循环单链表中没有指向NULL的指针，链表操作结束的条件应为：某一结点p 的next域指向表头结点（p-next= =H）。 b)从单链表的某一结点出发只能访问到其后继结点，所需的时间复杂度为O(1)， 而循环单链表除了能访问结点p的后继结点外，也能访问其前驱结点，其方 法是从此结点出发，找到满足条件（q-next= =p）的结点q，则q为p的前驱 结点，时间复杂度为O(n)。 c)采用单链

39、表的形式存储一个线性表，从一个结点出发只能够访问到该结点 的后继结点，而采用循环单链表的形式存储一个线表，从一个结点出发既 可以访问到该结点的后继结点，也可以访问到该结点的前驱结点，也就是 说，从循环单链表的任意一个结点出发，可以访问该链表的任意一个结点。 计算机软件技术基础 计算机软件技术基础 计算机软件技术基础 信息管理与信息系统信息管理与信息系统 32 如果一个链表为循环链表，则许多操作可只对链表设一个尾指针，而没有头指 针，因为这样更利于链表的操作，如链表的合并等。 上面我们我们对循环单链表存储线性表进行了分析，我们看到采用循环单链表 的形式存储线性表，从一个结点出发，可以访问到线性表

40、的任意一个结点，但 如果从一个结点出发访问该结点的前一个结点，则算法的运算量最大（需要将 线性表中的所有结点均扫描一遍），如果我们采用双向链表的形式存储线表， 这种情况可以得到改观。 双向链表双向链表 如果在每个结点上再增加一个指向线性表中每个元素的前驱结点的指针 prior，就可以很方便的找到前驱结点（p-prior）或后继结点（p- next），这样组织的链表可以使得我们从一个结点出发，既可以向后 访问该结点的后继结点，也可以向前访问该结点的前驱结点，因此我们 称这样的链表为双向链表。有时为了满足需要，也为了操作的方便，用 双向链表对线性表进行定义和操作。 计算机软件技术基础 计算机软件技

41、术基础 计算机软件技术基础 信息管理与信息系统信息管理与信息系统 33 双向链表的定义如下。 typedef struct dnode elemtype num; struct node *prior, *next; DNODE 其中prior为指向前趋结点的指针，next为指向后继结点的指针。 图4.9(a)为双向链表的示意图，图4.9(b)为空的双向链表的示意图， a1an NULL (a) 双向链表 a2H (空表 图4.9双向链表示意图 NULL NULLH NULL 与循环单链表相同，也可以定义循 环双链表。如图4.10(a)为循环双链 表，图4.10(b)为空的循环双链表。 (a)

42、 循环双链表 ( b) 空表 图4.10 循环双链表示意图 H H a1an a2 计算机软件技术基础 计算机软件技术基础 计算机软件技术基础 信息管理与信息系统信息管理与信息系统 34 在双向链表中凡涉及一个方向的操作与单链表一样。只是在做插入和删除时的操 作不同。 1)定位删除定位删除 设p为待删结点的指针，如图4.11所示， p （b）删除后 （a） 删除前 x y z x y z 图4.11 双向链表中结点删除情况删除语句为： p-prior-next=p-next; p-next-prior=p-prev; free(p); 计算机软件技术基础 计算机软件技术基础 计算机软件技术基础

43、 信息管理与信息系统信息管理与信息系统 35 2)定位插入定位插入 设p为待插入结点的位置，待插结点指针为q,在p结点之前或之后 插入均可。如图4.12为在p结点之前插入q结点的示意图。 在p结点之前插入的语句可描述为： q-prior=p-prior; p-prior-next=q; p-prior=q; q-next=p; p （b）插入后 （a） 插入前 x y z x y z 图4.12 双向链表中结点删除情况 sq sq p 同样的，也可以在p结点之 后插入q结点，插入语句可 描述为： q-next=p-next; p-next-prior=q; p-next=q; q-prior=

44、p; 计算机软件技术基础 计算机软件技术基础 计算机软件技术基础 信息管理与信息系统信息管理与信息系统 36 3、算法举例算法举例： 例1 写出在带有头结点的循环链表L中查找第i个元素的算法。 #include typedef struct node int data; struct node *next; NODE; NODE *search(NODE *H, int i) /*在带头结点的循环单链表 中查找第i个元素*/ NODE *p=H-next; int j=1; while(jnext!=H) p=p-next; j+; if(i=j) return p; else return

45、NULL; NODE creat(int n) /*创建带头 结点的循环单链表*/ int num; NODE *head,*s,*p; head=(NODE *) malloc (sizeof(NODE); head-next=head; p=head; while (n0) printf(Please input the datas:); scanf (%d, s=(NODE *) malloc (sizeof(NODE); s-data=num; s-next=p-next; p-next=s; p=s; n=n-1; return head; main() /*主函数*/ NODE *

46、p,*q; int i,n; char t=y; printf(Pleae input the length of the List :); scanf (%d, p=creat (n); while(t=y) printf(n Please input i = ); scanf(%d, while(in|idata); printf(nContinue Or Not ? (y/n) ); scanf(n%c, 计算机软件技术基础 计算机软件技术基础 计算机软件技术基础 信息管理与信息系统信息管理与信息系统 37 例2 写出一个将链表进行逆转的算法。 #include typedef stru

47、ct node int data; struct node *next; NODE; NODE turn(NODE H) /*逆转 函数*/ NODE *p=H,*q=H,*head; head=(NODE *)malloc(sizeof(NODE); while(p-next!=NULL) p=p-next ; head-next=p; while(p-next!=H) while(q-next!=p) q=q-next; p-next=q; p=p-next; q=H; p-next=NULL; return head; free(H); NODE creat(int n) /*创建带头

48、结点的单链表*/ int num; NODE *head,*s,*p; head=(NODE *) malloc (sizeof(NODE); head-next=NULL; p=head-next; while (n0) printf(Please input the datas:); scanf (%d, s=(NODE *) malloc (sizeof(NODE); s-data=num; s-next=p-next; p-next=s; p=s; n=n-1; return head; main() NODE *p,*q,*t; int n,s; printf(Pleae input

49、 the length of the List :); scanf (%d, t=creat (n); p=t; printf(The lists data is:n); while(p-next!=NULL) p=p-next; printf(%dt,p-data); q=turn(t); printf(nThe turned list is :n); while(q-next!=NULL) q=q-next; printf(%dt,q-data); printf(nPress any key to quit.); getch(); printf(nn); 计算机软件技术基础 计算机软件技术

50、基础 计算机软件技术基础 信息管理与信息系统信息管理与信息系统 38 4.3 特殊线性表特殊线性表 4.3.1 栈栈 栈又称堆栈（Stack），是在程序设计中广泛应用的一种数据结构， 就其逻辑结构而言，是一种特殊的线性表，其特殊性主要体现在做插 入和删除时受限制。 1、栈的定义、栈的定义 栈栈是允许在一端进行插入和删除操作的特殊线性表，其中，允许进行 插入和删除的一端叫栈顶栈顶，另一端叫栈底栈底。向栈顶插入元素叫入栈、 进栈或压栈，从栈顶删除元素叫出栈或退栈。 由于栈的插入和删除仅在栈顶一端进行，后进栈的元素必先删除，所 以栈又叫后进先出（Last In First Out 简称LIFO）表。

51、 计算机软件技术基础 计算机软件技术基础 计算机软件技术基础 信息管理与信息系统信息管理与信息系统 39 设有三个元素，入栈序列为a、b、c，则可能的出栈序列有以下五种，如图 4.13所示，其中s代表入栈，p代表出栈。 不可能得到的出栈序列为cab。 对于栈常进行的运算有以下几种。 初始化初始化 初始化栈为空。 判空判空 判断栈是否为空，若为空，则返回真，否则返回假。 入栈入栈 向栈顶插入一个元素。 出栈出栈 删除栈顶元素。 读栈读栈 取出栈顶元素。 图4.13 计算机软件技术基础 计算机软件技术基础 计算机软件技术基础 信息管理与信息系统信息管理与信息系统 40 2、 栈的存储结构栈的存储结

52、构 栈是一种特殊的线性表，其特殊性体现在操作受限，前面我们讨论了线性表， 我们看到线性表有顺序存储和链式存储两种存储方式，那么栈也有顺序和链 式两种存储方式。 栈的顺序存储结构及顺序栈的运算栈的顺序存储结构及顺序栈的运算 栈的顺序存储结构栈的顺序存储结构 栈的顺序存储结构是利用一组地址连续的存储单 元依次存储栈中元素，顺序存储的栈我们称为顺 序栈。利用C语言中的结构体和数组对栈定义如 下： #define N 1000 /* 设N为栈的最大元素个 数 */ typedef struct stack elemtype vN; /*为栈申请的存储单元的 个数，栈的最大容量*/ int top； /

53、*栈顶指针，标注栈顶的位 置*/ 其中top中存储栈顶元素的编号，又称栈顶指针。 elemtype为栈中元素的类型。v数组用来存储栈 的实际元素。图4.14展示了顺序栈中元素与栈顶 指针之间的关系。 计算机软件技术基础 计算机软件技术基础 计算机软件技术基础 信息管理与信息系统信息管理与信息系统 41 顺序栈的运算顺序栈的运算 1） 初始化栈空初始化栈空 初始化栈时只须将栈顶指针设为-1即可。 void inistack(STACK *s)s-top= -1; 2）入栈）入栈 在栈中插入元素时，若top已指向下标为N-1的分量，则栈满，不可入栈。算法如下： void push(STACK *s

54、,elemtype x) /* 将值为x的元素入栈*/ if (s-top= =N-1) printf(“栈满,overflown”); exit(1); else s-top=s-top+1; s-vs-top=x; 算法的时间复杂度为O(1)。 3） 出栈出栈 当在栈顶删除元素时，首先要判断栈是否为空，若为空，则不能删除，否则将栈顶 指针减1，原栈顶元素返回即可，算法如下： elemtype pop(STACK *s) if (s-top= = -1) printf(“栈空,downflown”); exit(1); else s-top=s-top-1; return s-vs-top+

55、1; 算法的时间复杂度为O(1)。 计算机软件技术基础 计算机软件技术基础 计算机软件技术基础 信息管理与信息系统信息管理与信息系统 42 4）栈的操作策略）栈的操作策略双栈操作双栈操作 当在一个程序中需要同时使用具有相同类型的两个栈时，一种最直接的方法是为两个 栈开辟一段存储空间，此时如果栈顶位置设置不当，会出现当一个栈满时，另一 个栈还有许多空间的情况。较好的方法是将两个栈的栈顶的初始位置设在空间的 两端，两个栈的入栈操作各自向中间延伸，当两个栈的栈顶相遇时栈满，如图 4.15所示 下面是两个栈共享空间时的定义和出入 栈算法。 #define N 1000 /* 设N为两个栈 总的最大元素

56、个数 */ typedef struct stack elemtype vN; int top1，top2; LSTACK; 计算机软件技术基础 计算机软件技术基础 计算机软件技术基础 信息管理与信息系统信息管理与信息系统 43 入栈算法： void push(LSTACK *s,int i, elemtype x) /* 将值为x的元素 入栈*/ if (s-top1+1= =s-top2) printf(“栈满,overflown”); exit(1); else switch (i) 1: s-top1=s-top1+1; s-vs- top1=x; break; 2: s-top2=s

57、-top2-1; s-vs- top2=x; break; default : printf(“i不合法n”); 出栈算法： elemtype pop(LSTACK *s,int i) elemtype x; switch ( i ) 1: if (s-top1= =-1) printf(“栈空,downflown”); exit(1); else x=s-vs-top1;s-top1-; break; 2: if (s-top2= =N-1) printf(“栈空,downflown”); exit(1); else x=s-vs-top2;s-top2+; break; default :

58、 printf(“i不合法n”); return x; 计算机软件技术基础 计算机软件技术基础 计算机软件技术基础 信息管理与信息系统信息管理与信息系统 44 栈的链式存储结构及链栈的运算栈的链式存储结构及链栈的运算 由于栈的实际容量是动态变化的，使用顺序栈时，当一个程序中同时使用多个栈时， 为了防止栈满溢出，需要为每个栈分配较大的空间，此时往往会出现这样的情况， 当一个栈已溢出，其它的栈还有很多的存储空间。这时就要讨论多个栈共享存储 空间的问题。因为栈的容量不好事先估计，使用顺序栈时会有存储空间的浪费， 如果把一个链表做栈用，可以避免事先估计栈的容量，在使用过程中根据需要向 系统申请存储单元

59、，存储栈中的元素。链式存储结构的栈也叫链栈。 链栈是只允许在表头进行插入和删除的单链表，表头指针可以作为栈顶指针。 图4.16为链栈的存储结构示意图。top为栈顶指针。 top a1a2an NULL 图4.16链栈示意图 链栈的定义如下： typedef struct node /*定义链表的结点，与入栈元素的类型一致*/ elemtype data; struct node *next; SNODE; SNODE top; /*栈顶指针，指向栈顶的位置*/ 栈空的条件为top= =NULL.。 计算机软件技术基础 计算机软件技术基础 计算机软件技术基础 信息管理与信息系统信息管理与信息系统

60、 45 使用链栈时，程序设计者可以使用不带头结点的单链表、带头结点的单链表、不 带头结点的循环单链表、带头结点的循环单链表等做为栈，只是在进行栈的操作 时，要本着怎样组织、怎样操作的原则。下面给出使用不带头结点和带头结点的 单链表栈，进行入栈和出栈操作的算法，使读者对程序设计中栈的使用有一个更 深的理解。 1）不带头结点的单链表栈的入栈操作）不带头结点的单链表栈的入栈操作 首先申请一结点new，若申请成功才可入栈，否则结束操作。 入栈时将new结点插入栈顶指针之前即可。算法如下： void push(SNODE *top,elemtype x) SNODE *new; new=(SNODE *