顺序表示的栈和队列必须预先分配空间并且空... -

1、第二章 线性表教学目标l 掌握线性表的基本概念，ADT描述方法；l 掌握线性表的顺序存储结构和链式存储结构的描述方法，以及线性表的各种基本操作的实现；l 能够从时间和空间复杂度的角度，综合比较线性表两种存储结构的不同特点及其适用场合；l 会运用线性表解决实际问题。数据结构分线性结构和非线性结构。线性的数据结构有线性表、栈、队列、数组和串。线性结构的特点是数据元素存放在非空有限集合中，并且满足如下几个条件：·存在唯一的“第一个”数据元素；·存在唯一的“最后一个”数据元素； ·除第一个数据元素之外，集合中的每一个数据元素都只有一个前驱；·除最后一个数据元素之

2、外，集合中的每一个数据元素都只有一个后继。2.1 线性表的定义线性表是线性结构中最常用而又最简单的一种数据结构。简而言之，一个线性表是n个数据元素的有限序列。线性表中数据元素的具体含义在不同情况下各不相同，但同一线性表中的元素类型是相同的，也就是说，同一表中的元素必定具有相同的属性。例如，英文字母表（A，B，C，Z）是一个线性表，表中的数据元素是单个字母。又如（1，2，3，50）也是一个线性表，表中的数据元素是整数。这两个线性表的元素都是单个数据项组成。在比较复杂的线性表中，一个数据元素可以由若干个数据项组成。在图2.1所示的学生成绩表中，每一个学生的情况为一个元素，它由姓名、学号、班级、语文

3、成绩、数学成绩和英语成绩等六个数据项组成。表2.1 学生成绩表姓名学号班级离散高数英语陈强2002000102计科2929078胡大2002000202计科2807875周兵2002000302计科2959085李可2002000402计科2707065从上面的例子中可以看出，线性表中的数据元素可以是各种各样的，但任何表中的元素必定具有相同特性，即属同一数据类型，数据元素之间相对位置是线性的。通常，我们把非空线性表表示为（a0，a1，ai-1，ai，ai+1，an-1），其中a0是线性表的第一个元素，ai是第i-1个元素，an-1是最后一个元素。元素的个数n（n0）定义为线性表的长度，当n=0

4、时称为空表，空表中没有元素。线性表具有线性结构的特点，表中ai元素的直接前驱元素是ai-1，ai元素的直接后继元素是ai+1。除了a0和an-1之外，每个ai都有且仅有一个直接前趋和一个直接后继，a0没有前趋，an-1没有后继。线性表是一种非常灵活的数据结构，可以根据需要对表中的任何数据元素进行访问，元素的插入和删除可以在表中的任何位置进行，可以将两个表连接成一个表，还可以把一个表拆分成两个或多个表等。线性表的ADT描述如下：ADT List；数据元素 各种具有相同属性的数据对象（可以是基本数据类型，也可以是构造数据类型）；操作 InitList(L) 初始化操作，生成一个空的线性表L。Lis

5、tLength(L) 求表长度函数。求线性表L中数据元素的个数。GetElem(L，i) 获取表中元素的函数。当0iListLength(L)-1时，函数值为线性表L中第i个数据元素，否则返回空值null。i是该数据元素在线性表中的位置序号。IsEmpty(S) 判断空线性表函数。如果L是空表，返回“true”，否则返回“false”。LocateElem(L，x) 定位函数。返回L中第1个与x相等的数据元素的位置序号。若这样的元素不存在，则返回值为0。Insert(L，x，i) 插入操作。在给定线性表L中第i（0iListLength(L)）个数据元素之前插入一个新的数据元素x，线性表的长度

6、变成n+1。Delete(L，i) 删除操作。删除线性表L中第i（0iListLength(L)-1）个数据元素，线性表的长度减1。Clear(L) 表置空操作。无论线性表L是否为空表，操作结果将L表置空。2.2 线性表的顺序存储2.2.1 顺序表顺序表是指采用顺序存储结构的线性表，它利用内存中的一片起始位置确定的连续存储区域来存放线性表中的所有元素，如图2.1所示。它的特点是逻辑上相邻的数据元素，其物理存储位置也是相邻的，也就是说表中的逻辑关系和物理关系是一致的。在图2.1中，假设每个数据元素占用c个存储单元，表中第一个元素的存储地址作为线性表的存储起始地址LOC（a0），用b来表示。由于同

7、一线性表中数据元素的类型相同，则线性表中任意相邻的两个数据元素ai与ai+1的存储首址LOC（ai）与LOC（ai+1）将满足下面的关系:MAXSIZE元素序号012in-1存储首址012in-1MAXSIZE-1bb+cb+2cb+i*cb+(n-1)*c线性表空闲图2.1 线性表的顺序存储结构。an-1a0a1a2。aiLOC（ai+1）= LOC（ai）+c一般来说，线性表的第i个数据元素ai的存储首址为LOC（ai）= b+ i*c（0in-1）也就是说，只要知道线性表的起始地址LOC（a0）b和一个元素所占用的存储单元c，表中的任意一个元素的存储地址均可由上面的公式求得，且计算所花费

8、的时间是一样的，所以，访问表中任意元素的时间相等，并且可以随机存取。由于高级程序设计语言中一维数组（即向量）也是采用顺序存储表示，因此可用一维数组elementsMAXSIZE来描述顺序表，其中MAXSIZE是一个预先设定的常数，表示线性表存储空间的大小，预设为100，实际使用时其值应有所选择，使得它既能满足线性表中的元素个数动态增加的需求，又不至于因预先定义得过大而浪费存储空间。至于顺序表的长度（即线性表中元素的数目）可用一个整型变量last来表示，所以我们可用结构类型来定义顺序表的类型。#define MAXSIZE 100 /* MAXSIZE 为线性表可能的最大长度 */#define

9、 ERROR -1typedef struct /* 线性表定义 */int elementsMAXSIZE;int last; /* last为线性表的长度 */ SqList;定义了线性表的顺序存储结构后，下面我们就在这种结构的基础之上讨论如何实现线性表的基本运算。void InitList(SqList *L) /*初始化操作，将线性表L置空*/L->last = 0;bool IsEmpty( SqList L) /*判断表是否为空。如果L是空表，返回true，否则返回false*/if( L.last = 0 ) return true;else return false;in

10、t GetElem(SqList L,int i) /* 取表中第i元素。*/if(i<0 | i>=L.last) return ERROR;else return L.elementsi; /*C语言中数组的下标从"0"开始*/int LocateElem(SqList L,int x) /*定位函数。返回L中第1个与x相等的数据元素的位置（从0算起）。*/ /*否则返回值为0。*/int k; k=0; while (k<L.last && L.elementsk!=x) k+; if(k<L.last) return k; e

11、lse return ERROR;int Insert(SqList *L,int x,int i) /*在线性表L中第i（0iL.last）个数据元素之前插入一个数据元素x*/int k; if(i<0 | i>L->last | L->last = MAXSIZE) return ERROR; else for( k=L->last; k>=i; k- ) L->elementsk= L->elementsk-1; L->elementsi=x; L->last=L->last+1;return true;int Dlete

12、(SqList *L,int i) /*删除线性表L中第i（0I<L.last）个数据元素*/int k;if( i<0 | i>=L->last ) /* 下标越界 */ return ERROR;else /* 移动后面的元素 */ for(k=i;k<L->last;k+) L->elementsk= L->elementsk+1; L->last-;return true;void Clear(SqList *L) /* 清空线性表L */InitList( L );对于插入和删除两个算法，其算法执行的时间都主要花费在元素的移动上。

13、而移动元素的次数不仅与具体位置上插入或删除的概率有关，而且还与插入或删除的位置本身有关。在表头附近进行插入或删除比在表尾附近进行插入或删除元素的移动数要多一些。所以，我们要讨论的是进行这些操作时元素的平均移动次数。设Pi是在第i个元素之前插入一个元素的概率，假定在顺序表中任何位置插入元素的机会相等，即设Pi，则在长度为n的线性表中插入一个元素时所需移动元素的平均次数为E（n）=设qi是删除第i个元素的概率，假定在顺序表中删除元素的机会相等，即设qi，则在长度为n的线性表中删除一个元素时所需移动元素的平均次数为E（n）=通过上述讨论可知，在顺序表中插入或删除一个数据元素，大约移动表中一半元素。当

14、线性表的长度较大，且插入和删除操作的频度较高时，则花费时间较多，不宜采用顺序存储结构。但是顺序表存储结构简单，便于顺序存储，存储空间的利用率高。2.2.2 顺序表的应用举例例1 已知顺序表la和lb中的数据元素依值非递减有序排列，现将la和lb归并为一个新的的顺序表lc，且lc中的数据元素也依值非递减有序排列。例如:la=(2,4,6,8,9)lb=(3,5,7,9,11,13,18)则lc=(2,3,4,5,6,7,8,9,9,11,13,18)具体算法的实现思路是：设三个指针i，j，k初始值均为0，其中i，j分别指向la和lb顺序表中第一个数据元素，k指向lc中元素即将存放的序号。分别取l

15、a和lb中i、j所指的数据元素进行比较，当la的元素不大于lb的元素时，将la的当前元素放入lc中，同时i，k指针增1，否则将lb的当前元素放入lc中，同时j，k指针增1。对应的算法如下：void MergeList(SqList la, SqList lb, SqList *lc) /* 合并表有序表la和lb到表lc中，使得lc依然有序 */int i,j,k;i = j = k = 0;while(i<la.last && j<lb.last) /* la和lb均不空 */if( la.elementsi < lb.elementsj ) lc->

16、elements k+ = la.elementsi+; else if( la.elementsi > lb.elementsj )lc->elementsk+=lb.elementsj+;else /* la和lb中的当前元素相等时，同时移动指针 */lc->elementsk+=lb.elementsj+; i+;while(i < la.last) /* la非空,lb己空 */lc->elementsk+=la.elementsi+;while(j < lb.last) /* la己空,lb非空 */lc->elementsk+=la.ele

17、mentsj+;lc->last=k;例2 清除顺序表中的重复数据元素。例如，顺序表（2，3，3，4，3，5，4）清除后变为（2，3，4，5）。清除重复元素是指删除重复元素，只保留序号最小的一个。具体的算法实现思路是：从顺序表中依次取出每一个元素ai，并检查ai+1到an-1中是否有元素与ai值相等，有就删除重复元素。void ClearList(SqList *L) /* 清除顺序表中的重复数据元素 */int i = 0, j;while( i < L->last ) j = i + 1;while(j<=L->last) /* 找重复数据元素并删除 */if

18、( L->elementsi = L->elementsj ) Dlete(L,j); /* 下一个元素自动向前移动过来 */else j+; /* 指针向下移动一个位置 */ i+; 2.3 线性表的链式存储由上节的讨论可知，线性表的顺序存储结构的特点是借助于元素物理位置上的邻接关系来表示元素间的逻辑关系，这一特点使我们可以随机地存取表中任何一个元素，但它的缺点也很明显。如元素的插入、删除需要移动大量的数据元素，操作效率极低,而且由于顺序表要求连续的存储空间，存储空间必须预先分配，表的最大长度却很难确定。最大长度估计过小会出现表满溢出，估计过大又会造成存储空间的浪费。本节将介绍线

19、性表的另一种存储方法，称为链式存储结构。该方法可以克服顺序表的上述缺点，但随之而来的却是随机存取性能的消失。我们通常把链式存储的线性表简称为链表。2.3.1 单链表2.3.1.1单链表的基本概念链表是用一组任意的存储单元来依次存储线性表中的各个数据元素，这些存储单元可以是连续的，也可以是不连续的。为了能正确反映数据元素之间的逻辑关系，我们可以用指向直接后继的指针来表示。用链接存储结构表示线性表的一个元素时至少要有两部分信息:一是这个数据元素的值，二是这个数据元素的直接后继的存储地址。这两部分信息一起组成了链表的一个结点。链表中结点的结构如下:datanext其中，data域是数据域，用来存放数

20、据元素的值；next域称指针域（又称链域）用来存放该数据元素的直接后继结点的地址。链表正是通过每个结点的指针域将线性表的n个结点按其逻辑次序链接成为一个整体。由于这种链表的每个结点只有一个指针域，故称这种链表为单链表。由于我们只注重链表中结点的逻辑顺序，并不关心每个结点的实际存储位置，通常用箭头表示链域中的指针，于是单链表就可以直观地画成用箭头链接起来的结点序列，如图2.2所示。从图中可见，单链表中每个结点的存储地址存放在其直接前驱的指针域中，因此访问单链表的每一个结点必须从表头指针开始进行，这表明单链表在逻辑上依然是顺序结构的。a0a1a2an-1图2.2 一般单链表图示head 用C语言描

21、述单链表的结点结构如下：typedef struct node /* 单链表结点结构 */DataType data; /*DataType可以是任何相应的数据类型如int,char等*/struct node *next; LinkList;指针变量和结点变量是两个容易混淆而又必须搞清楚的概念。定义指针变量后，要使它有确定的指向必须给它赋值或者使用标准函数调用来完成，如：p=( LinkList *) malloc(sizeof(LinkList)函数malloc分配一个类型为LinkList的结点空间，并将起始地址放入p中。这就是说指针变量所指向的结点变量的存储空间只是在程序的执行过程中，

22、当需要时才产生的，故称动态变量。一旦所指向的结点变量不再需要了，又可通过标准函数free(p)释放p所指向的结点变量占用的空间。结点变量的访问是通过指向它的指针p来实现的，即用*p作为该结点变量的名字来访问。在C语言中，对指针所指向结点的成员进行访问时，通常用运算符“->”来表示。例如取上面结构中的两个分量，可以写成（*p）.data和（*p）.next，也可以写成p->data和p->next。它们之间的关系如图2.3所示。图2.3 指针变量与结点变量head*p*(p->next)p->datap->nextp下面我们将讨论用单链表表示线性表时，如何实现

23、它的几种基本运算。2.3.1.2 单链表的基本运算1建立单链表假设线性表中结点的数据类型为整型，有效值域为非负整数，那么我们可以依次输入这些整数，并以0作为输入结束标志符，动态地建立单链表。建表的方法通常有两种：一种是头插入法，也就是每输入一个不为零整数就建立结点，把结点插入到当前链表的表头之前；另外一种是尾插入法，它是把新生成的结点插入到当前链表的表尾结点之后。这两种方法的区别是生成链表的结点的次序和输入的顺序不一样。（a） 非空链表heada0a1an-1head头结点(b) 空链表图2.4 带头结点的单链表头结点为了使链表上有些操作实现起来简单、清晰，通常在链表的第一个结点之前增设一个类

24、型相同的附加结点，称之为头结点，如图2.4所示。在单链表中引入头结点通常有两个好处：首先，线性表中的第一个元素结点的地址被存放在头结点的指针域中，这样对第一个元素结点的处理与其他结点处理一致，无需特殊处理，简化了算法；其次，无论链表是否为空，头指针总指向头结点，除初始化外，任何操作都不会改变头指针，给算法的处理带来方便。不带头结点的头插入算法如下：void InitList1( LinkList *head ) /* 初始化不带头结点的链表头指针 */*head = NULL;void AddHead1(LinkList *head, int x )/* 向头指针为head的链表中插入一个结点

25、，其值为x */LinkList *p;p=( LinkList *)malloc(sizeof(LinkList);p->data = x;p->next = *head;*head = p; /* 调整链表头指针head */带头结点的尾插入算法的执行过程如图2.5所示，其算法如下：头结点qhead1232p图2.5 尾插入法建立单链表的插入过程void InitList( LinkList *head ) /* 初始化带头结点的链表头指针 */*head = ( LinkList *)malloc(sizeof(LinkList);(*head)->next=NULL;

26、void AddHead( LinkList *head, int x ) /* 建立一个带头结点的单链表，返回表头指针 */LinkList *p,*q=head; while( q->next ) q = q->next; /* q指向链表的尾结点 */p=( LinkList *)malloc(sizeof(LinkList);p->data = x; /* 填充数据 */p->next = q->next; /* 调整指针 */q->next = p; /* 挂到链表上 */2按序号查找单链表是一种顺序存取结构，如果要访问表中第i个结点必须从头结点出

27、发开始搜索，直到第i个结点为止。设单链表的长度为n，从头结点开始，头结点上指向的结点看成第0个结点，其他结点编号依次顺序编号。从头结点开始顺着链搜索，用指针p指向当前扫描到的结点，用j作计数器。p的初值指向头结点，j的初值为0，当p扫描下一个结点时，计数器j相应地加1。当j=i时，p所指的结点就是要找的第i个结点。算法如下：LinkList *GetNode( LinkList *head, int i )/* 在带头结点的单链表中查找第i个结点，找到返回该结点指针，否则返回NULL */LinkList *p = head; int j=0;while( p->next &&a

28、mp; j<i ) j+; p=p->next; /* p右移一个结点 */if(j=i) return p;else return NULL;3按值查找按值查找是在带头结点的查找单链表中查找第一个和给定值x相等的结点，若查到则返回指向该结点的指针，否则返回NULL。查找过程从头结点开始，依次将每个结点的值与x作比较，直到查找成功或到达表尾为止。算法如下：LinkList *LocateNode(LinkList *head, int x)/* 在带头结点的单链表中查找值为x的结点，找到返回结点指针，否则返回NULL */LinkList *p = head->next;wh

29、ile( p && p->data != x ) p=p->next;return p;4插入插入运算是将值为x的新结点插入到表中第i（0in-1）个位置上，n为插入前表的长度。具体方法是先找第i-1个结点，若找到则把新结点插入作为该结点的直接后继。其插入过程如图2.6所示。其算法如下：x图2.6 在*p结点后插入*q结点ai-1aiqpvoid InsertNode(LinkList *head, int i, int x)/* 在带头结点的单链表中第i个结点位置上插入值为x的结点 */LinkList *p, *q; p=GetPrior(head, i); /

30、*找到第i个结点的前驱 */if(p!=NULL) q=( LinkList *)malloc(sizeof(LinkList);q->data=x;q->next=p->next; /*对应图2.6 */p->next=q; /*对应图2.6 */ else /* 插入到最后一个结点之后 */AddHead( head, x );5删除ai+1图2.7 删除*p结点的后继结点ai-1aiqp删除操作是指删除单链表中第i（0in-1）个结点。具体方法是先找第i-1个结点，然后删除该结点的直接后继（即第i个结点）。另外，由于被删除结点已经毫无用处，所以要向系统申请释放该结

31、点的空间。其删除过程如图2.7所示。其算法如下：void DeleteNode（LinkList *head, int i）/* 在带头结点的单链表中删除第i个结点 */LinkList *p,*q； p=GetNode(head,i-1); /*找到第i-1个结点 */if（(p!=NULL)&&(p->next!=NULL)） q=p->next; /*对应图2.8 */p->next=q->next; /*对应图2.8 */ free(q); /*对应图2.8 */else printf(“结点未找到！n”);6求表长求表长就是求表中除头结点外的结

32、点的个数。具体方法是从头结点开始顺着链搜索，用指针p指向当前扫描到的结点，用j作计数器。p的初值指向头结点，j的初值为0，当p扫描下一个结点时，计数器j相应地加1。当p到达尾结点时，j的值就是表的长度。其算法如下：int Length(LinkList *head)/* 在带头结点的单链表中求表的长度 */LinkList *p=head; int j=0;while (p->next!=NULL) j+;p=p->next; /* p右移一个结点 */return j;2.3.2 循环链表单链表的最后一个结点的指针域的值是NULL，如果将这个域改为指向单链表的第一个结点，那么整个

33、链表就形成了一个环形结构，故称为单链形式的循环链表，并简称为单循环链表。类似地还有多重链形式的循环链表，如双向循环链表。单循环链表中所在结点被链在一个环上，多重循环链表则是把表中结点链在多个环上。为了使空表与非空表的处理一致，循环链表也经常设置头结点。空循环链表仅由一个头结点组成，自成循环。带头结点的单循环链表如图2.8所示。（a） 非空循环链表heada1a2anhead头结点(b) 空循环链表图2.8 带头结点的单循环链表头结点循环链表的特点是从表中任一结点出发均可访问其他所有结点。用头指针表示的单循环链表找尾结点时同单链表一样要从头结点搜索到尾结点，没有任何优势。在许多实际问题中，链表的

34、操作经常在表的首尾两端进行，此时用头指针表示的单循环链表就显得不够方便。如果改用尾指针rear来表示单循环链表，则头结点的指针为rear->next，第一个结点的指针为rear->next->next，访问第一个结点和尾结点都很方便，有利于在两端进行操作。用尾指针rear表示的单循环链表如图2.9所示。（a） 非空循环链表a1a2anrear头结点(b) 空循环链表图2.9 用尾指针rear表示的单循环链表头结点rear2.3.3 双向链表在单链表中，给定一个p指向的结点，可以沿着指针方向立即访问到该结点的直接后继结点*（p->next），却无法访问到该结点的直接前驱结

35、点。唯一的办法是从表头开始顺链查找，直到当前结点的指针域（存放的是后继结点的指针）与p相等，那么这个结点就是p所指结点的直接前驱。同样在单循环链表中，虽然从任一结点出发可访问到表中所有结点，但要找到某个结点的直接前驱同样要遍历整个表，原因是表中每个结点只有指向其直接后继的指针。若希望快速找到一个结点的前驱结点地址，可以在每个结点内再增加一个指向其直接前驱的链域，这样形成的链表中就有两条方向不同的链，故称为双向链表（Double linked list）。用C语言描述双向链表的结点结构如下：typedef struct dnode /* 双向链表结点结构 */DataType data; /*D

36、ataType可以是任何相应的数据类型如int,char等*/struct dnode *prior,*next; DLinkList;和单链表类似，为了使得某些运算方便一些，双链表也可附加头结点。同样也可以把双链表的头结点与尾结点链接起来构成循环链表，称之为双向循环链表。带头结点的双向循环链表如图2.10所示。图2.10带头结点的双向循环链表a1head头结点head（a）非空双向循环链表（b）空双向循环链表a0an-1pq图2.11 在双链表的*p结点之前插入新结点*q在双链表中每个结点既有指向直接前驱结点的指针又有指向直接后继结点的指针，这就使得原本在单链表上很困难的操作在双链表上很容易

37、就实现，如在p指向的结点之前插入一个新结点，删除p指向的结点等。这些操作均要找到该结点的直接前驱，在双链表中本身就有一个指向其直接前驱的链域，所以操作的实现很简单，仅仅修改相应的指针即可。在双单链表的*p结点之前插入值为x的结点插入的过程如图2.11所示。其算法如下：void InsertDNode(DLinkList *p, int x)/* 在双链表的*p结点之前插入值为x的结点 */DLinkList *q; q=( DLinkList *)malloc(sizeof(DLinkList);q->data=x;q->prior=p->prior; /*对应图2.11 *

38、/q->next=p; /*对应图2.11 */p->prior->next=q; /*对应图2.11 */p->prior=q; /*对应图2.11 */在双链表中删除p指针指向的结点的过程如图2.12所示。其算法如下：p图2.12 在双链表中删除p指针指向的结点 void DeleteDNode(DLinkList *p)/* 在双链表中删除p指针指向的结点 */p->prior->next=p->next; /*对应图2.12 */p->next->prior=p->prior; /*对应图2.12 */free(p);2.3.

39、4 链表的应用举例例1头结点 有一个不带头结点的单链表L（至少有1个结点），第一个结点指针为head，编写算法将L逆置，即最后一个结点变成第一个结点，倒数第二个结点变成第二个结点，如此等等。逆置的方法是：从头到尾扫描单链表L，将第一个结点的next域设置为NULL，将第二个结点的next域指向第一个结点，将第三个结点的next域指向第二个结点，如此进行直到最后一个结点，用head指向它。其算法如下：void Invert1( LinkList *head ) /* 将不带头指针的单链表倒置 */LinkList *p = *head, *r;LinkList *q = NULL;/* q始终指

40、向当前插入点 */while( p ) /* 还有剩余元素时 */r = p->next; /* r缓存下一个待插入元素指针 */p->next = q; /* 插入当前的待插元素到新表中 */q = p; p = r; /* 调整 */*head = q;/* 更新头指针 */例2有一个带头结点的非递减有序单链表L，头结点指针为head，编写算法向L中插入一个值为x的元素，使插入后仍为非递减有序。解决本题的具体方法是：先建立一个待插入的结点，结点的data域赋值为x，然后链表中各结点的数据域依次与x比较大小，直到找到插入的位置，最后插入该结点。其算法如下：void InsertO

41、rder(LinkList *head,int x) /* 在有序单链表L中插入值为x的结点，插入后仍然有序 */LinkList *p,*q,*s; s=( LinkList *)malloc(sizeof(LinkList); /* 建立待插入的结点 */s->data=x;p=head;q=p->next; /* q指向p的后继结点 */while(q!=NULL && q->data<x) p=q; q=q->next;s->next=q; /*将s插入到p和q之间*/p->next=s;例3有两个带头结点的单循环链表L1和L2

42、，编写算法将链表L2链接到链表L1之后成为一个单循环链表。解决本题的具体方法是：如果在用头指针指向的单循环链表上做这个操作，都需要先找到两链表的尾指针，要找尾指针就必须遍历整个链表，找到后将第二个链表的尾指针与第一个链表的头结点链接起来，使之成为循环的链表。若在用尾指针指向的单循环链表上做这个操作，则只需修改指针，操作过程如图2.13所示。其算法如下：a1a2anrear1a1a2anrear2图2.13 两单循环链表链接为一个单循环链表pqLinkList *InsertOrder(LinkList *rear1, Node *rear2) /* 在有序单链表L中插入值为x的结点，插入后仍然

43、有序 */LinkList *p = rear1->next; /*对应图2.13中的*/LinkList *q = rear2->next; /*对应图2.13中的*/rear1->next = q->next; /*对应图2.13中的*/rear2->next = p; /*对应图2.13中的*/free(q);return( rear2 );例4 有一个不带头结点的双向循环链表，其中已知一结点的指针为p，编写算法将p与其右边的一个结点进行交换。解决本题的具体方法是：利用双向循环的特点先找到p结点的右边结点q，然后将p与q进行交换。其算法如下：void Swa

44、p(DLinkList *p) /* 将双向循环链表的已知结点与其右边结点互换 */DLinkList *q; q=p->next;if(q=p) printf("只有一个结点，不能进行交换！n");else p->next=q->next;p->next->prior=p;p->prior->next=q;q->prior=p->prior;p->prior=q;q->next=p;2.4 线性表的顺序和链式存储结构的比较以上介绍了线性表的两种存储结构：顺序存储结构和链式存储结构。下面我们从时间性能和空间性

45、能两方面对两种存储结构分别进行比较。（1）时间性能的比较顺序表是利用内存中的一片起始位置确定的连续存储区域来存放线性表中的所有元素，它的特点是逻辑上相邻的数据元素，其物理存储位置也是相邻的。它是一种随机存取结构，存取速度快，存取表中任一元素都可以通过计算直接得到地址进行存取，与元素的位置和表长n无关，时间复杂度为O(1)。而链表是用一组任意的存储单元来依次存储线性表中的各个数据元素，这些存储单元可以是连续的，也可以是不连续的。为了能正确反映数据元素之间的逻辑关系，必须附加指针来表示。存取链表中的数据元素需要从头指针起顺着链扫描才能取得，与数据元素在表中所处的位置有关，时间复杂度为O(n)。因此

46、，若线性表上的操作主要是查找、求表长、读取而很少做插入和删除操作时，采用顺序表结构为宜。在顺序表中进行元素的插入和删除时，平均要移动近一半的元素，而在链表中插入和删除元素只需要修改指针。因此，线性表上若频繁进行插入和删除操作时，采用链表结构为宜。（2）空间性能的比较顺序表的存储空间是静态分配的，即在编译时分配其存储空间。顺序表的最大长度很难确定，最大长度估计过小会出现表满溢出，估计过大又会造成存储空间的浪费。而链表的存储空间是动态分配的，即在运行时分配，只要内存空间有空闲，操作系统就会给它分配。因此，在线性表的长度变化较大，频繁进行插入和删除操作，在表长难以确定的情况下，最好采用链表作为存储结

47、构。链表的存储空间利用率不高。线性表的存储空间利用率可以用存储密度来衡量。存储密度定义为线性表中的数据元素本身所占的存储量和整个线性表结构所占的存储量之比。显然，顺序表的存储密度为1，由于链表中的结点除了数据域外还要有存放后继结点地址的链域，所以链表的存储密度小于1。因此，当线性表的长度变化不大，顺序表的最大长度很容易确定时，采用顺序存储结构比较节省存储空间。总之，实际应用中选用哪种存储结构要根据具体问题的要求综合平衡来选择。2.5 线性表的应用本节以一元多项式相加作为线性表应用的一个例子。数学上，一个一元多项式Pn（x）可按升幂写成:Pn（x）=p0p1xp2x2Pnxn它由n+1个系数唯一

48、确定。因此，它可以用一个线性表P表示:P=（p0，p1，p2，Pn）每一项的指数i隐含在其系数Pi的序号里。一般情况下，多项式的次数很高且变化很大，例如多项式A（x）=12x1003x10004x10000如果用上述方法表示则线性表有10001个元素，但是却只有四个非零元素，浪费了大量的存储空间。在这种情况下，可用系数和指数的组合表示多项式的一个项，则多项式A（x）可表示成如下线性表的形式：A（1，0），（2，100），（3，1000），（4，10000）至于线性表的存储结构是顺序存储结构还是链接存储结构，要视其作何种运算以及是否有利于这种运算的实现而定。如只对多项式求值，由于不会改变多项式的

49、系数和指数，用顺序表即可。如需对多项式作求和运算，则插入、删除操作不可避免，而且线性表的长度变化比较大，故宜用链表结构。多项式A（x）用带头结点的单链表表示如图2.14所示。2100head头结点1031000410000图2.14 多项式的单链表表示多项式的链式存储结构描述如下：typedef struct pnode /* 多项式结点结构 */float coef; /*表示多项式的系数*/int exp; /*表示多项式的指数*/struct pnode *next; *Poly;对两个多项式A和B相加，按照多项式相加的原则，我们可以这样实现多项式加法运算：设指针p,q分别指向多项式A和

50、多项式B中当前进行比较的某个结点，则比较两个结点中的exp指数域，有下列三种情况:p->exp<q->exp，*p应为多项式的一项；p->exp=q->exp，则将两个结点中的系数相加，若相加为零，则释放指针p和q所指结点，否则修改*p结点的coef系数域，并释放指针q所指结点；p->exp > q->exp，*q 应为多项式的一项，把*q插入到*p之前。操作过程如图2.15所示。其算法如下：Poly PolyAdd(Poly pa, Poly pb) /* 求两多项式之和，多项式用带头结点的单链表表示，pa,pb为头指针 */Poly p,q,

51、r,s;int x;p=pa->next;r=pa; /* r为p的前驱指针 */q=pb->next; free(pb);while(p!=NULL && q!=NULL)if(p->exp<q->exp) /* 指针顺链向后移动 */r=p; p=p->next;else if (p->exp=q->exp) x=p->coef+q->coef;if (x=0) r->next=p->next; free(p); /* 释放p所指结点 */else p->coef=x; r=p;p=r->next;s=q->next; /* s为辅助指针，指向q的后继结点 */free(q); /* 释放q所指结点 */q=s;else /