第2章 线 性 表2.1 线性表逻辑结构 2.2 顺序存储结构 2.3 链式存储结构 2.4 单向循环链表 2.5 双向循环链表 2.6 一元多项式的存储与运算 线性结构：在数据元素的非空集中， 存在惟一的一个首元素； 存在惟一的一个末元素； 除首元素外每个元素均只有一个直接前驱； 除末元素外每个元素均只有一个直接后续。在许 多领域中都有线性结构的概念，在计 算机科学中，线性结构也被称为线性表。栈和 队列是线性表的特例。 2.1 线性表的逻辑结构1、定义：一个线性表是n 个数据元素的有限序列。 2、设Linear_list=(D，R)是一个数据结构，其中D=a0，a1，an-1D为同类型数据元素集合;i=0，1，n-1，并且n0;R为关系的集合R=N;N=|ai-1， ai D，i=1，2，n-1。线性结构中所有结点，按照它们之间的关系，可 以排成一个线性序列：a0，a1，ai-1， ai ，ai+1，an-13、术语：称a0为“起始结点”，an-1为“终止结点”。ai的 前驱为ai-1，后续为ai+1，n为线性表的长度，当n=0时称 为空表。4、例如：alphabet=(a,b,c,z) 和 prime=(2,3,5,7,11,97)alphabet是字母表，其结点是一个英文字母，prime是100以 内的素数表，结点是整型数。且只有一个域的线性表，有多个域的线性表学号姓名性别出生日期所在院系政治面貌9906201钱钢男81/06/01生科院团员9906202张俊强男80/12/21数科院团员9906203李梅女81/04/18地科院团员上表中，每一行作为一个结点，结点有六个域：学 号、姓名、性别，出生日期，所在院系，政治面貌。5、线性表的基本操作如下 ：(1)存取。存取表中第i个数据元素ai(0in-1)。(2)插入。在表中第i(0in-1)个数据元素ai之后插入 一个新的数据元素。(3)删除。删除表中第i个数据元素ai(0in-1)。(4)合并。将二个或二个以上的线性表合并成一个线 性表。(5)分解。将一个线性表拆分成多个线性表。(6)查找。在线性表中查找满足某种条件的数据元素 2.2 顺序存储结构 1、存储结构(1)定义：用一组地址连续的存储单元依次存放线性表 的所有元素。以元素在内存中位置的关系来表示元素之 间的逻辑关系，这就是线性表的顺序存储结构。每个数据元素需要占用t个存储单元，并且第一数据 元素的存储单元的地址作为连续存储单元的地址，则第 i个数据元素的存储位置为：LOC(ai)=LOC(a0)+ i*t只要有了第一个结点的起始地址，这对表中任意一 个结点i(0in-1)，都可按相同的速度进行访问，这种 存储结构称为“随机存取的数据结构” 存储地址内存状态元素在线性表中 位序 LOC(a0)a0 0 LOC(a0)+ta1 1 LOC(a0)+(i-1)tai i LOC(a0)+(n- 1)t an-1 n-1 图2.2 线性表顺序存储结构示意 (2)顺序存储结构的表示。可用C语言中的一维数组 来表示(但数组不是线性表，数组中存放的是线 性表) #define MAX 100struct sqlist int vMAX; /* 线性表的存储空间*/int length; /* 线性表的当前表长 */;typedef struct sqlist SqList;说明：SqList为线性表类型，它包含两个域， 其中： length=n 为表长，数组v有MAX个存储 单元，下标从0MAX-1，且nvi之后插入x，同时修改表的长度L-length */ int SqList_Insert(SqList *L,int i,int x) int j;if(i=L-length) return(0); /* 0表示操作失败 */for(j=L-length-1; j=i+1; j-) L-vj+1 = L-vj;L-vi+1=x; L-length+;return(1); /* 1表示操作成功 */2.删除delete(L,i)删除表L中第i个数据元素ai(0in-1)，删除前线性表 长度是n，线性表为(a0,ai-1,ai,ai+1,an-1) 删除后线性表长度为n-1，线性表为(a0,ai-1,ai+1,an-1) 下标01i-1ii+1n-1MAX-1a0a1ai-1aiai+1an-1下标01i-1in-2MAX-1a0a1ai-1ai+1an-1线性表中数据元素的删除前后如下图所示 算法2.2 顺序存储结构下线性表删除算法：删除线性表中第i个元素。/* 删除L-vi，同时修改表的长度 */int delete(SqList *L,int i) int j;if(i=L-length) return(0); /* 0表示操作失败 */for(j=i+1; jlength; j+) L-vj-1=L-vj;L-length-;return(1); /* 1表示操作成功 */3、 效率分析通过对算法2.1和2.2分析可知，在插入、删除时 ，算法执行时间的长短是由结点的移动次数决定的， 因此可以用结点移动次数度量这两个算法的时间复杂 度。而结点移动的次数取决于插入和删除的位置i。 最坏情况是i=0，即插入和删除是v0中的元素，结点 的移动次数是n和n-1，所以，插入和删除算法的最坏 时间复杂度是O(n)。最好情况是插入和删除的位置是 n-1，即插入和删除的是vn-1中的元素，这时，无需 移动结点，所以，在插入和删除中，平均移动结点的 次数是(n-1)/2，因而，它们的平均时间复杂度也是 O(n)，这里假定线性表在任何位置上插入和删除是等 概率的。2.3 链式存储结构1、 概念线性表的顺序存储结构中，当进行插入和删除 操作时，存在大量数据元素移动。为此考虑采用另 一种存储结构链式存储结构。在链式存储结构中，数据元素的存储单元是不 连续的。每个元素除存储自身信息外，还需存储其 后继元素的信息。每个元素的存储映象称为结点。 表示数据元素内容的部分被称为数据域(data)；表示直接后继元素存储地址的部分被称为指针 或指针域（next）。在C语言中，存储每个数据元素的结点结构描述如下：struct lnode int data;struct lnode *next;typedef struct lnode LNode;例如，一个线性表： (a,b,c,d),存储结构如图2.6所示。headd cba链表从首指针head开始，指向链表中第一个结点的存储 位置。同时，由于最后一个元素没有直接后继，所以线性 表中最后一个结点的指针为“空”(NULL，用表示 ) ，而 当head为NULL时，head所指向的线性表为空表，其表长 n=0。带头结点的单链表为了简化对链表的操作，人们经常在链表的第一个 结点之前附加一个结点，并称为头结点。这样可以免去 对链表第一个结点的特殊处理。例如，一个线性表：(a0，ai-1，ai，ai+1，an-1)带头结点的链表（空表）如下图所示：2 、链式存储结构下的操作 注意：在链式存储结构下，增加一个结点需要向系 统申请，申请方法为p=(LNode *)malloc(sizeof(LNode)； 删除一个结点时，要将已删除的结点的存储空间释放 ，释放的方法为： free(p) (1)建立链表生成一个结点p，将其作为头结点(head=p)。然后 ，依次建立新结点p，将其数据域置入相应的值，并将 其链接到链表的尾部，且tail始终指向链表最后一个结 点。最后，将尾指针所指结点的指针域赋“空” (NULL)。 用C语言描述的算法如下。算法2.3 建立有n个结点的线性单链表的算法。 /* 建立带有头接点，且数据元素为1到n的单链表，首指针 为head */LNode * LinkList_Create(int n) LNode *head, *p, *tail; /* tail指向尾节点 */int i;head=tail=(LNode *)malloc(sizeof(LNode);for(i=1,jdata=i;tail-next=p; tail=p; tail-next=NULL;return(head)；(2)插入结点要在如图2.9所示线性表的两个数据元素y和z之间插入一 个数据元素a，已知p指向线性链表的结点y，q指向要插入 的新结点，插入的过程如下：q=(LNode *)malloc(sizeof(LNode)；q-data=a；q-next=p-next；p-next=q； 插入前后的线性链表变化如下：算法2.4 在具有头结点的线性单链表中插入算法。/* 在线性链表的第i个结点之前插入一个结点x */int LinkList_Insert(LNode *head，int x，int i) LNode *q，*p; int j；if(inext; if(p=NULL) return(0); /* i越界 */q=(LNODE *)malloc(sizeof(LNODE);q-data=x；/* 在结点*p之后插入结点*newp */q-next=p-next； p-next=q；return(1)3.删除结点在图2.8所示的线性表中，删除y所在的结点，删除的方 法是：使指针p指向要删除结点的前驱(y所在的结点)；将p 的指针域指向要删除结点的后继结点；将要删除的结点释 放。删除过程如下：q=p-link; p-link=q-link; free(q);只要修改指针域的指针，就可实现删除操作。删除前后 的线性链表变化如图2.10所示。 图2.10算法2.5 在具有头结点的线性单链表中删除算法。/* 在线性链表中，删除第i个结点 */int LinkList_Delete(LNode *head，int i) LNODE *p,*q； int j；if(inext; if(p=NULL) return(0); /* i越界 */* 删除结点*p之后的结点*q */q=p-next； p-next=q-next； free(q)；return(1)；(3)应用例2.1 对给定的两个递增有序线性表a和b进行合并，要求 合并后仍然是一个递增有序表，并要求算法的时间复杂 度为O(n+m)，n与m分别为线性表的长度，可采用“平移 指针，一次扫描”的方法。 分析：设两个指针La和Lb分别指向两个线性表开始，对 指针所指结点的数据域作比较，并选出较小的一个，将 其从原链表中取出插入到新表Lc的表尾，然后该指针后 移；重复直到其中一个表结束。最后，将尚未结束表直 接链接到新表的尾部。链表带有头结点，算法如下。 算法2.6 将两个递增有序单链表合并成递增单链表的算法/* 依次比较La和Lb中的各个结点，卸下数据元素较小的结点，将其增 添为Lc的末结点 */LNode *LinkList_Merge(LNode *La,LNode *Lb) LNode *pa,*pb,*pc,*Lc; /* pc指向链表Lc中的尾结点 */Lc=La; /* Lc的头结点是原La的头结点 */pa=La-next; pb=Lb-next; pc=Lc;while(pa!=NULL pc=pa; pa=pa-