第二章线性表

1、 第二章第二章 线性表线性表 线性表的特点是：在数据元素的非空有限集中，（1）存在唯一的一个被称为“第一个”的数据元素；（2）存在唯一的一个被称为“最后一个”的数据元素；（3）除第一个以外，集合中的每一个数据元素均有且只有一个前驱；（4）除最后一个以外，集合中每一个数据元素均有且只有一个后继。 2.1 2.1 线性表的逻辑结构线性表的逻辑结构w 线性表是最简单的一种数据结构。简单地说，一个线性表是n(n)个具有相同属性的数据元素的有限序列，其中各个数据元素有着依次相邻（串接）的逻辑关系。w 线性表中数据元素的个数n称为线性表的长度。n=0 时，该线性表为空表。n0时该线性表可记为：（A0,A1

2、,Ai,An-1）其中，A0称为起点，An-1称为终点，每个元素的序号代表它在该线性表中的逻辑位置减1（与数组下标对应），除了起点（A0）和终点(An-1)外，每个数据元素都有且只有一个直接前趋和一个直接后继。Ai+1是Ai的直接前驱，Ai+1是Ai的直接后继。w线性表中的数据元素可以是各式各样的，但同一线性表中的元素必定有相同的特性，即属同数据对象，相邻数据元素辶间存在着有序关系。w线性表是一个相当灵活的数据结构，其表长可根据不同的操作增长或缩短。对线性表进行的基本操作有：存取、插入、删除、合并、分解、查找、排序、求线性表的长度等。 2.2 2.2 线性表的顺序存储结构线性表的顺序存储结构2

3、.2.1 顺序分配w线性表的顺序存储结构是用一组地址连续的存储单元依次存储该线性表中的各个元素。假设线性表的每个数据元素占用L个存储单元，并以所占的第一个单元的存储地址为数据元素的存储位置，则第i+1个数据元素的存储位置为： loc(Ai)=Loc(A0)+i*L.w因此，在内存中可以通过地址计算直接存取线性表中的任一元素，所以，线性表的顺序存储结构可以随机存取。这种结构的特点是逻辑上相邻的元素物理上也相邻（如图2-1所示）。顺序表可用语言的一维数组实现，数组的类型随数据元素的属性而定。2.2.2 线性表的操作w 线性表结构简单、易于实现，但插入或删除一个元素时需对其后继的全部元素逐个进行移动

4、（平均需移动表中的一半元素）操作不方便，需花费较多时间，特别是当插入元素而需动态扩大连续存储时，线性表后面的存储区可能已被占用从而无法扩大。所以，这种结构仅适用于数据元素个数不经常变动或只需在顺序存取设备上做成批处理的场合。下面我们分情况讨论线性表的插入和删除操作。 (一)线性表插入操作(1)w 1、在数组中下标为i的元 素前插入一个新元素。w例2.1 某语言程序中，整型数组的个元数组成一个线性表。为了在i位置前插入一个新元素b，可用如下函数inst1来实现，当插入成功时返回1，否则返回0，所以该函数的返回值类型是整型。插入前后的线性表的示意图如右： 举例（续）w分析：w初始条件V,i,bw执

5、行条件：0i98w执行结果：1 成功w0 不成功wN-S流程图如右： 图举例（续） w用函数实现算法如下： wint ins1( int V , int i, int b)w int j；wif(i98) w printf(“The value of i is out of rangen”)；w return 0; /*插入失败*/w wfor (j=99；ji；j-)w vj=vj-1;/*后移*/w vi=b； /*插入*/wreturn 1； /*插入成功 */w线性表的插入操作（2）2、在有序表中插入一个新元素 例2.2 设有一个有序线性表，用数组结构实现，最大元素个数为n。设当前元素

6、个数是m。要求在该有序表中插入一个值为x的元素。当x=63时，插入前后的有序表的示意图如右： 举例（续）w分析：初始条件：a,n,m,xw插入条件：m=n) printf(“插入失败”);wreturn 0; w /*插入失败*/wfor(i=m-1; i=0& aix ;i-)w ai+1=ai; /*后移*/wai+1=x; m+; /*插入*/wreturn 1; /*插入成功 */w（二）线性表的删除(1)1删除下标为i的 数据元素例2.3 为在V0到V99中删除一个元素Vi,引用del1函数。删除前后的线性表的示意图如右 举例（续）分析：初始条件： 数组V，删除下标i删除条件：0i9

7、9执行结果：1成功,0不成功N-S流程图如右: 举例（续）Del1函数定义如下：int del1 (int v ,int i )int j;if (i99) printf(“the value of I is out of rangen”);return 0; /*删除失败*/for (j=i; j99; j+) Vj=Vj+1; /*从vI+1到v99逐个前移*/ V99=0; /*数组最后一个元素清0或某种结束标记*/return 1; /*删除成功 */线性表的删除操作(2)w2在有序顺序表中删除一个数据元素w例2.4 在有序表中删除一个值为x的数据元素。当x的值为78时删去前后的线性表

8、的w示意图如右：举例（续）w分析：w初始条件：数组a, 数组元素个数n,删除元素值 xw查找a中是否有x值的元素：有x,则删除成功，返回1；无x,则删除不成功，返回0。wNS流程图如右：举例（续）w对应算法实现函数如下：wint del2(int a,int n,int x)wint i,j;wfor(j=0;jn;j+)w if(aj= =x)i=j;break;wif (j= =n) wprintf(“找不到x，删除不成功”);wreturn 0; /*找不到x，删除不成功*/wwfor(;idata=ai； -link-data=ai+1。 2.3.2 线性链表的运算w设p链表中某一结点

9、的指针，可以说明如下：wNODE *p；w申请一个结点可用C语言的标准存储分配库函数malloc。调用如下：wp = (NODE * ) malloc ( sizeof (NODE);w当用完后释放结点占用空间时调用函数freew free(p); （一）线性链表的建立w例.5 建立一个如图所示的链表。例2.5 函数定义如下wNODE * create_linklist(NODE * head,int x,int y,int z)w NODE * p, *q;wp=(NODE *)malloc(sizeof(NODE);whead=p;wp-data=x;wq=(NODE *)malloc(s

10、izeof(NODE);wp-link=q;wp=q;wp-data=y;wq=(NODE *)malloc(sizeof(NODE);wp-link=q;wp=q;wp-data=z;wp-link=NULL;wreturn (head);w（二）线性链表的插入操作w设链表结点类型的定义为：wtypedef struct nodew int data;w struct node *link;wNODE;w在链接存储的线性表中插入一个键值为x的新结点，分以下四种不同情况：w1、在某指针P所指结点之后插入；w2、插入首结点之前，使新结点为新的首结点；w3、接在线性表的末尾；w4、在有序链表中插入

11、，使新的线性表依旧有序。 分情况讨论（1）1、在线性链表中某指针p所指结点之后插入值为x的结点算法的NS流程图 插入结点的函数w函数定义如下：wvoid lq_insl(p,x)wNODE *p; /; /*新结点在P所指结点之后*/wint x; /*新结点的键值*/w NODE *u;wu=(NODE *)malloc(sizeof(NODE);wu-data=x;wu-link=p-link;wp-link=u;w 分情况讨论（2）2、首结点之前插入键值为x的新结点 算法的NS流程图 算法的NS流程图 首结点之前插新结点函数定义wvoid lq_ins2(hpt,x)wNODE *hpt

12、; /*链表头指针*/wint x; /*新结点的键盘值*/wNODE *u;wu=(NODE *)malloc(sizeof(NODE);wu-data=x;wu-link=hpt;whpt=u;w 分情况讨论（3）3、在链式存储的线性表的末尾接上一个键值为x的新结点算法的NS流程图 线性表末尾接上新结点函数定义 wvoid lq_ins3(hpt,x)wNODE *hpt; /*链表头指针*/wint x; /*新结点的键盘值*/w NODE* *u,*p;wu=(NODE)*malloc(sizeof(NODE);wu-data=x;wu-link=null;wif (hpt=null)

13、 /*如链表为空链表*/whpt=u;return;ww/*x以链表首结点开始顺序走向末尾结点*/wfor( p=hpt; p-link!=null;p= p-link);wp-link=u;w分情况讨论（4）4、在有序链式存储线性表中插入一键值为X的新结点(假设x=8)算法的NS流程图 有序链式线性表中插入新结点函数wvoikd lq_ins4 (hpt,x) /*设链表从小到大有序*/wNODE *hpt; /*链表头指针*/wint x; /*新结点的键值*/wNODE *u,*q,*p;wu=(NODE *)malloc(sizeof(NODE);wu-data=x; /*从链表首结点

14、开始顺序寻找*/wfor(p=htp;p&p-datalink);wif(p= =hpt) hpt=u;welse q-link=u;wu-link=pw （三）线性链表的删除操作完成删除算法可有以下几个步骤组成： 1、如链表为空链表，则不执行删除操作 2、若链表的首结点的值为指定值，更改链表的头指针为指向首结点的后继结点； 3、在链表中找到指定值的结点； 4、将找到的结点删除删除操作示意图算法的NS流程图 链表中删除指定值的结点的函数定义 wint lq_delete(hpt,a)wNODE *hpt; /*链表头指针的指针*/wint a; /*要删除的结点键值*/wNODE p,q; w

15、if(q=hpt)=NULL) return 1; /*链表已为空链表*/wif(q-data=a) /*要删除链表的首结点*/w hpt=q-link; /*更改链表头指针*/wfree(q); /*释放被删除结点的空间*/wreturn 0; /*删除成功*/wfor( ; q-data!=a&q-link!=NULL;p=q,q=q-link); /*寻找*/wif(q-data=a) /*找到*/w p-link=q-link; /被删除的结点从链表脱钩*/wfree(q); /*释放被删除结点的空间*/wreturn 0; /*删除成功*/wreturn 1; /*没有指定值勤的结点

16、，未执行删除操作*/w2.3.3 循环链表w1.单向循环链表w 循环链表是另一种形式的链式存储结构，将单链表的形式稍加改，让表中最后一个结点的指针域指向单链表的首结点，这样就形成了一个环。如图2-26所示。这种结构从表中任一结点出发均可找到其它结点。w 单向循环链表的基本操作类似于普通链表，差别在于算法中循环条件不在是p或p-link是否为空，而是它们是否等于头指针。 2.双向链表w在单链表中，从任何一个结点能通过指针域找到它的一继结点，但要找它的前趋结点，则需从表头出发顺链查找。w双向链表克服了这个缺点。双向链表的每一个结点除数据域外，还包括两个指针域，一个指向该结点的后继结点，另一个指向它

17、的前趋结点，结点结构如图2-27所示。双向链表也可以是循环链表，其结构如图2-28所示示意图双向链表的结点类型可描述如下 struct nodewint data;wstruct node *ulink,*rlink;wwtypedef struct node DNODE;w在循环双向链表中，若P先指向表中结点的指针，则有：w(p-rlink)-llink=(p-link)-rlink=p1、插入w在双向链表中的p结点后插入一个q结点。假设q结点已生成，如图2-29所示 w主要操作步骤如下：wq-rlink=p-rlink;wq-llink=p;wp-rlink=q;w(q-rlink)-llink=q; 2、删除w在双向链表中删除p结点w主要操作步骤如下：w（p-llink）-rlink=p-link;w(p-rlink)-llink=p-llink;wfree(p); 例 2-7(1)whead是一个链表的头指针，该链表结点的域由小到大排列。函数insert(head,data)将一个值为data新结点插入到链表中，且保证插入后的链表仍是有序的。请在每组中选择正确答案填空。w #includew#include w#include w typedef struct nodewwint data;wstruct nod