Download presentation
Presentation is loading. Please wait.
1
第2章 线性表 2.1 线性表的概念及运算 2.2 线性表的顺序存储 2.3 线性表的链式存储 2.4 一元多项式的表示及相加
2
2.1 线性表的概念及运算 2.1.1 线性表的逻辑结构 图2.1 线性表的逻辑结构
3
例如： 英文字母表(A, B, …, Z)就是一个简单的线性表，表中的每一个英文字母是一个数据元素， 每个元素之间存在唯一的顺序关系，如在英文字母表字母B的前面是字母A， 而字母B的后面是字母C。 在较为复杂的线性表中，数据元素(data elements) 可由若干数据项组成，如学生成绩表中，每个学生及其各科成绩是一个数据元素，它由学号、姓名、各科成绩及平均成绩等数据项(item) 组成， 常被称为一个记录(record) ，含有大量记录的线性表称为文件(file)。数据对象（data object）是性质相同的数据元素集合。
4
表2-1 车辆登记表
5
线性表(Linear List)是由n (n≥0)个类型相同的数据元素a1, a2, …， an组成的有限序列，记作（a1, a2, …，ai-1，ai，ai+1， …，an）。这里的数据元素ai(1≤i≤n)只是一个抽象的符号，其具体含义在不同情况下可以不同， 它既可以是原子类型，也可以是结构类型但同一线性表中的数据元素必须属于同一数据对象。此外，线性表中相邻数据元素之间存在着序偶关系，即对于非空的线性表（a1, a2, …，ai-1, ai, ai+1, …, an）， 表中ai-1 领先于ai，称ai-1 是ai的直接前驱，而称ai是 ai-1的直接后继。除了第一个元素a1外，每个元素ai有且仅有一个被称为其直接前驱的结点ai-1，除了最后一个元素an外，每个元素ai有且仅有一个被称为其直接后继的结点ai+1。 线性表中元素的个数n被定义为线性表的长度，n=0时称为空表。
6
线性表的特点可概括如下： 同一性：线性表由同类数据元素组成，每一个ai必须属于同一数据对象。 有穷性：线性表由有限个数据元素组成， 表长度就是表中数据元素的个数。 有序性：线性表中表中相邻数据元素之间存在着序偶关系<ai, ai+1>。 由此可看出，线性表是一种最简单的数据结构，因为数据元素之间是由一前驱一后继的直观有序的关系确定；线性表又是一种最常见的数据结构，因为矩阵、数组、字符串、堆栈、 队列等都符合线性条件。
7
2.1.2 线性表的抽象数据类型定义 ADT LinearList{
线性表的抽象数据类型定义 ADT LinearList{ 数据元素： D={ai| ai∈D0, i=1, 2, …，n, n≥0 ， D0为某一数据对象} 关系：Ｓ＝｛<ai, ai+1> | ai, ai+1∈D0，i=1, 2, …, n-1｝ 基本操作： （1） InitList（L） 操作前提： L为未初始化线性表。 操作结果： 将L初始化为空表。
8
（2） DestroyList(L) 操作前提： 线性表L已存在。 操作结果： 将L销毁。 （3） ClearList(L) 操作前提： 线性表L已存在 。 操作结果： 将表L置为空表。 （4） EmptyList（L） 操作结果： 如果L为空表则返回真， 否则返回假。
9
（5） ListLength（L） 操作前提： 线性表L已存在。 操作结果： 如果L为空表则返回0， 否则返回表中的元素个数。 （6） Locate(L, e) 操作前提： 表L已存在， e为合法元素值。 操作结果： 如果L中存在元素e， 则将“当前指针”指向元素e所在位置并返回真， 否则返回假。 （7） GetData(L, i) 操作前提： 表L存在， 且i值合法， 即1≤i≤ListLength（L）。 操作结果： 返回线性表L中第i个元素的值。
10
（8） InsList(L, i, e) 操作前提：表L已存在，e为合法元素值且1≤i≤ListLength(L)+1。 操作结果：在L中第i个位置插入新的数据元素e，L的长度加1。 （9） DelList(L, i, &e) 操作前提： 表L已存在且非空， 1≤i≤ListLength(L)。 操作结果： 删除L的第i个数据元素， 并用e返回其值， L的长度减1。 } ADT LinearList
11
2.2 线性表的顺序存储 2.2.1 线性表的顺序存储结构 线性表的顺序存储是指用一组地址连续的存储单元依
2.2 线性表的顺序存储 2.2.1 线性表的顺序存储结构 线性表的顺序存储是指用一组地址连续的存储单元依 次存储线性表中的各个元素，使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系。 采用顺序存储结构的线性表通常称为顺序表。
12
loc(ai) =loc(a1)+(i-1)×k
假设线性表中有n个元素，每个元素占k个单元，第一个元素的地址为loc(a1)，则可以通过如下公式计算出第i个元素的地址loc(a -i)： loc(ai) =loc(a1)+(i-1)×k 其中loc(a -1)称为基地址。
13
图2.2 顺序表存储示意图
14
顺序存储结构可以借助于高级程序设计语言中的一堆数组来表示，一维数组的下标与元素在线性表中的序号相对应。线性表的顺序存储结构可用C语言定义如下：
＃define MAXSIZE=线性表可能达到的最大长度 typedef struct { ElemType elem［MAXSIZE］； /* 线性表占用的数组空间 */ int last； /* 记录线性表中最后一个元素在数组elem［ ］中 的位置（下标值）， 空表置为-1 */ } SeqList；
15
2.2.2 线性表顺序存储结构上的基本运算 1. 查找操作 线性表有两种基本的查找运算。
线性表顺序存储结构上的基本运算 1. 查找操作 线性表有两种基本的查找运算。 按序号查找GetData(L, i): 要求查找线性表L中第i个数据元素，其结果是L.elem［i-1］或L->elem［i-1］。 按内容查找Locate（L, e）: 要求查找线性表L中与给定值e相等的数据元素，其结果是：若在表L中找到与e相等的元素，则返回该元素在表中的序号；若找不到， 则返回一个“空序号”， 如-1。 查找运算可采用顺序查找法实现，即从第一个元素开始，依次将表中元素与e相比较， 若相等，则查找成功，返回该元素在表中的序号； 若e与表中的所有元素都不相等，则查找失败，返回“-1”。
16
算法描述： int Locate(SeqList L， ElemType e)
/* 在顺序表L中依次存放着线性表中的元素， 在表中查找与e相等的元素， 若 L［i］=e，则找到该元素， 并返回i值， 若找不到， 则返回“-1” */ { i=0 ; /* i为扫描计数器， 初值为0， 即从第一个元素开始比较 */ while ((i<=L.last)&&(L.elem［i］! =e) ) /* 顺序扫描表， 直到找到值为key 的元素, i++; 或扫描到表尾而没找到 */ if (i<=L.last) return(i); /* 若找到值为e的元素， 则返回其序号 */ else return(-1); /* 若没找到， 则返回空序号 */ }
17
【算法 线性表的查找运算】 2. 插入操作 线性表的插入运算是指在表的第i (1≤i≤n+1)个位置，插入一个新元素e，使长度为n的线性表 (e1，…，ei-1，ei，…，en) 变成长度为n+1的线性表（e1，…, ei-1，e，ei，…，en）。 用顺序表作为线性表的存储结构时， 由于结点的物理顺序必须和结点的逻辑顺序保持一致，因此我们必须将原表中位置n， n-1，…， i上的结点， 依次后移到位置n+1，n，…，i+1上，空出第i个位置，然后在该位置上插入新结点e。当i=n+1时， 是指在线性表的末尾插入结点，所以无需移动结点，直接将e插入表的末尾即可。
18
例如：已知线性表 (4, 9, 15, 28, 30, 30, 42, 51, 62)， 需在第4个元素之前插入一个元素“21”，则需要将第9个位置到第4个位置的元素依次后移一个位置，然后将“21”插入到第4个位置，如图2.3所示。请注意区分元素的序号和数组的下标。 图2.3 顺序表中插入元素
19
算法实现： ＃define OK 1 ＃define ERROR 0
int InsList(SeqList *L, int i, ElemType e) /* 在顺序表L中第i个数据元素之前插入一个元素e。 插入前表长n=L->last+1， i的合法取值范围是 1≤i≤L->last+2 */ { int k; if((i<1) || (i>L->last+2)) /* 首先判断插入位置是否合法 */ { printf(″插入位置i值不合法″)； return(ERROR); }
20
if(L->last>=maxsize-1)
{ printf(″表已满无法插入″)； return(ERROR); } for(k=L->last; k>=i-1; k--) /* 为插入元素而移动位置 */ L->elem［k+1］=L->elem［k］; L->elem［i-1］=e; /* 在C语言数组中， 第i个元素的下标为i-1 */ L->last++; return(OK); }
21
【算法2.2 线性表的插入运算】 可以看出，当i= L->last+2时，语句L->elem［k+1］=L->elem［k］将不会执行，因为循环的终值大于初值，此时不需要移动元素， 可直接在表尾插入e。 当i= 1时， 语句L->elem［k+1］=L->elem［k］需执行n次，即将表中已存在的n个元素依次后移一个位置才能将e插入。因此，语句L->elem［k+1］=L->elem［k］的频度与插入位置i有关。
22
3. 删除操作 线性表的删除运算是指将表的第i(1≤i≤n)个元素删去， 使长度为n的线性表(e1，…, ei-1，ei，ei+1，…，en)变成长度为n-1的线性表(e1，…, ei-1， ei+1，…，en)。 例如：线性表(4, 9, 15, 21, 28, 30, 30, 42, 51, 62)删除第5个元素， 则需将第6个元素到第10个元素依次向前移动一个位置，如图2.4所示。
23
图2.4 顺序表中删除元素
24
算法描述： int DelList(SeqList *L, int i, ElemType *e)
/*在顺序表L中删除第i个数据元素，并用指针参数e返回其值。i的合法取值为1≤i≤L.l ast+1*/ { int k; if((i<1)||(i>L->last+1)) printf(″删除位置不合法！″)； return(ERROR); }
25
*e=L->elem［i-1］; /* 将删除的元素存放到e所指向的变量中 */
for(k=i; i<=L->last; k++) L->elem［k-1］=L->elem［k］; /* 将后面的元素依次前移 */ L->last--; Return(OK); }
26
【算法2.3 线性表的删除运算】 与插入运算类似，在顺序表上实现删除运算也必须移动结点，这样才能反映出结点间的逻辑关系的变化。若i=L->last+1， 则移位语句L->elem［k-1］= L->elem［k］不执行，因为循环变量的初值大于终值，此时不需要移动元素，仅将表长度减1即可。显然，删除算法中移位语句L->elem［k-1］= L->elem［k］的执行频度也与删除位置i有关。
27
在顺序表中插入或删除一个数据元素时，其时间主要耗费在移动数据元素上。对于插入算法而言，设Pi为在第i个元素之前插入元素的概率，并假设在任何位置上插入的概率相等，即Pi=1/(n+1), i=1, 2, …，n+1。设Eins为在长度为n的表中插入一元素所需移动元素的平均次数， 则 同理，设Qi为删除第i个元素的概率，并假设在任何位置上删除的概率相等， 即Q i=1/n, i=1, 2, …，n。删除一个元素所需移动元素的平均次数Edel为
28
例2-1 有两个顺序表LA和LB，其元素均为非递减有序排列， 编写一个算法，将它们合并成一个顺序表LC， 要求LC也是非递减有序排列。例如LA=(2, 2, 3), LB=(1, 3, 3, 4), 则LC=(1, 2, 2, 3, 3, 3, 4)。 算法思想：设表LC是一个空表，为使LC也是非递减有序排列，可设两个指针i、 j分别指向表LA和LB中的元素， 若LA.elem［i］>LB.elem［j］， 则当前先将LB.elem［j］插入到表LC中; 若LA.elem［i］≤LB.elem［j］，则当前先将LA.elem［i］插入到表LC中，如此进行下去，直到其中一个表被扫描完毕，然后再将未扫描完的表中剩余的所有元素放到表LC中。
29
void merge(SeqList *LA, SeqList *LB, SeqList *LC)
{ int i, j, k, l; i=0; j=0; k=0; while(i<=LA->last&&j<=LB->last) if(LA->elem［i］<=LB->elem［j］) LC->elem［k］=LA->elem［i］; i++; k++; } else
30
LC->elem［k］=LB->elem［j］;
j++; k++; } while(i<=LA->last) /* 当表LA比表LB长时， 则将表LA余下的元素赋给表LC */ { LC->elem［k］=LA->elem［i］; i++; k++; while(j<=LB->last) /* 当表LB比表LA长时， 则将表LB余下的元素赋给表LC */ j++; k++; LC->last=LA->last+LB->last; }
31
【算法2.4 线性表的合并运算】 由上面的讨论可知， 线性表顺序表示的优点是： (1）无需为表示结点间的逻辑关系而增加额外的存储空间（因为逻辑上相邻的元素其存储的物理位置也是相邻的）； (2）可方便地随机存取表中的任一元素。 其缺点是： (1） 插入或删除运算不方便，除表尾的位置外，在表的其它位置上进行插入或删除操作都必须移动大量的结点，其效率较低； (2) 由于顺序表要求占用连续的存储空间，存储分配只能预先进行静态分配，因此当表长变化较大时，难以确定合适的存储规模。若按可能达到的最大长度预先分配表空间，则可能造成一部分空间长期闲置而得不到充分利用；若事先对表长估计不足，则插入操作可能使表长超过预先分配的空间而造成溢出。
32
2.3 线性表的链式存储 2.3.1 单链表 图2.5 单链表的结点结构
33
单链表包括两个域：数据域用来存储结点的值；指针域用来存储数据元素的直接后继的地址（或位置）。链表正是通过每个结点的指针域将线性表的n个结点按其逻辑顺序链接在一起。由于链表的每个结点只有一个指针域，故将这种链表又称为单链表。 由于单链表中每个结点的存储地址是存放在其前趋结点的指针域中的，而第一个结点无前趋，因而应设一个头指针H指向第一个结点。同时，由于表中最后一个结点没有直接后继，则指定线性表中最后一个结点的指针域为“空”（NULL）。这样对于整个链表的存取必须从头指针开始。
34
例如：图2.6所示为线性表（A, B, C, D, E, F, G, H）的单链表存储结构，整个链表的存取需从头指针开始进行，依次顺着每个结点的指针域找到线性表的各个元素。
图2.6 单链表的示例图
35
图2.7 单链表的逻辑状态 图2.8 带头结点单链表图示
36
单链表可以由头指针唯一确定。 单链表的存储结构描述如下：
typedef struct Node / * 结点类型定义 * / { ElemType data； struct Node *next； }Node, *LinkList； /* LinkList为结构指针类型*/ 假设L是LinkList型的变量，则L是一个结构指针，即单链表的头指针，它指向表中第一个结点（对于带头结点的单链表，则指向单链表的头结点），若L=NULL（对于带头结点的单链表为L->next=NULL），则表示单链表为一个空表，其长度为0。若不是空表，则可以通过头指针访问表中结点，找到要访问的所有结点的数据信息。对于带头结点的单链表L，p=L->next指向表中的第一个结点a1，即p->data=a1，而p->next->data=a2。 其余依此类推。
37
单链表上的基本运算 1. 建立单链表 图2.9 头插法建立单链表图示
38
用头插法建立单链表的算法： Linklist CreateFromHead() { LinkList L; Node *s;
char c; int flag=1; /* 设置一个标志变量flag，初值为1，当输入“$”时，将flag置为0， 建表结束 */ L=(Linklist)malloc(sizeof(Node)); /* 为头结点分配存储空间*/ L->next=NULL; While(flag) {
39
c=getchar(); if(c! =′$′) { s=(Node*)malloc(sizeof(Node)); /* 为读入的字符分配存储空间 */ s->data=c; s->next=L->next; L->next=s; } else flag=0; } return L; = }
40
【算法2.5 用头插法建立单链表】 2） 尾插法建表 图2.10 尾插法建表图示
41
该算法的实现与头插法建表的不同之处在于指针的变化， 其具体实现如下：
Linklist CreateFromTail() { /*将新增的字符追加到链表的末尾*/ LinkList L; Node *r, *s; int flag=1; /* 设置一个标志， 初值为1，当输入“$”时，flag为0，建 表结束 */ L=(Node *)malloc(sizeof(Node)); /* 为头结点分配存储空间 */ L->next=NULL; r=L; /* r指针始终动态指向链表的当前表尾， 以便于做尾插入， 其初值指向头结点 */ while(flag) {
42
c=getchar(); if(c! =′$′) { s=(Node*)malloc(sizeof(Node)); s->data=c; r->next=s; r=s； } else flag=0; r->next=NULL; /* 将最后一个结点的next链域置为空， 表示链表 的结束 */ } /*while*/ return L; } /*CreateFromTail*/
43
【算法2.6 尾插法建表】 2. 查找 1） 按序号查找 在单链表中，由于每个结点的存储位置都放在其前一结点的next域中，因而即使知道被访问结点的序号i，也不能像顺序表那样直接按序号i访问一维数组中的相应元素，实现随机存取，而只能从链表的头指针出发，顺链域next逐个结点往下搜索，直至搜索到第i个结点为止。
44
算法描述：设带头结点的单链表的长度为n，要查找表中第i个结点，则需要从单链表的头指针L出发，从头结点（L->next）开始顺着链域扫描， 用指针p指向当前扫描到的结点, 初值指向头结点，用j做计数器，累计当前扫描过的结点数（初值为0）， 当j = i 时， 指针p所指的结点就是要找的第i个结点。
45
Node *Get (LinkList L, int i)
/* 在带头结点的单链表L中查找第i个结点， 若找到(1≤i≤n)， 则返回该结点的存储位置; */ /* 否则返回NULL */ { int j； Node *p； p=L； j=0； /* 从头结点开始扫描 */ while (p->next! =NULL&&j<i) { p=p->next； /* 扫描下一结点 */ j++； /* 已扫描结点计数器 */ } if（i==j） return p； /* 找到了第i个结点 */ else return NULL； /* 找不到， i≤0或i>n */ } /* Get */
46
【算法2.7 在单链表L中查找第i个结点】 2) 按值查找 算法描述：按值查找是指在单链表中查找是否有结点值等于e的结点，若有的话， 则返回首次找到的其值为e的结点的存储位置，否则返回NULL。查找过程从单链表的头指针指向的头结点出发，顺着链逐个将结点的值和给定值e作比较。
47
Node *Locate( LinkList L, ElemType key)
/* 在带头结点的单链表L中查找其结点值等于key的结点， 若找到则返回该结点的位置p；否则返回NULL */ { Node *p; p=L->next; /* 从表中第一个结点比较 */ while (p![KG-*2]=NULL) if (p->data![KG-*2]=key) p=p->next; else break; /* 找到结点key， 退出循环 */ return p; } /* Locate */
48
【算法2.8 在单链表L中查找值等于key的结点】
3. 单链表插入操作 算法描述：要在带头结点的单链表L中第i个位置插入一个数据元素e，需要首先在单链表中找到第i-1个结点并由指针pre指示，然后申请一个新的结点并由指针s指示，其数据域的值为e，并修改第i-1个结点的指针使其指向s，然后使s结点的指针域指向原第i个结点。 插入结点的过程如图2.11所示。
49
int InsList(LinkList L, int i, ElemType e)
{ /*在带头结点的单链表L中第i个位置插入值为e的新结点 */ Node *pre, *s; int k; pre=L; k=0; while(pre![KG-*2]=NULL&&k<i-1) /* 在第i个元素之前插入， 则先找到第i-1个数据元素的存储位置, 使指针pre指向它 */ {pre=pre->next; k=k+1; }
50
if(k! =i-1) /* 即while循环是因为pre=NULL或i<1而跳出的， 所以一定是插入位置不合理所致 */ { printf(″插入位置不合理！″)； return ERROR; } s=(Node*)malloc(sizeof(Node)); /* 为e申请一个新的结点并由s指向它 */ s->data=e; /* 将待插入结点的值e赋给s的数据域 */ s->next=pre->next; /* 完成插入操作 */ pre->next=s; return OK; }
51
【算法2.9 单链表插入操作】 图2.11 在单链表第i个结点前插入一个结点的过程
52
4. 删除 图2.12 单链表的删除过程
53
int DelList(LinkList L, int i, ElemType *e)
/* 在带头结点的单链表L中删除第i个元素， 并将删除的元素保存到变量*e中 */ { Node *p, *r; int k; p=L; k=0; while(p->next![KG-*2]=NULL&&k<i-1) /* 寻找被删除结点i的前驱结点i-1使p指向它 */ {p=p->next; k=k+1; 〖ZK)〗 }
54
if(k! =i-1) /* 即while循环是因为p->next=NULL或i<1而跳出的 */
{ printf(″删除结点的位置i不合理！″); return ERROR; } r=p->next; p->next=p->next->next; /* 删除结点r */ free(r); /* 释放被删除的结点所占的内存空间 */ return OK; }
55
【算法2.10 单链表删除操作】 说明：删除算法中的循环条件（p->next! =NULL && k<i-1）与前插算法中的循环条件（p! =NULL && k<i-1）不同，因为前插时的插入位置有m+1个（m为当前单链表中数据元素的个数）。i=m+1是指在第m+1个位置前插入，即在单链表的末尾插入。而删除操作中删除的合法位置只有m个，若使用与前插操作相同的循环条件，则会出现指针指空的情况， 使删除操作失败。
56
例 编写一个算法，求单链表的长度。 算法描述：可以采用“数”结点的方法来求出单链表的长度，用指针p依次指向各个结点, 从第一个元素开始“数”， 一直“数”到最后一个结点（p->next=NULL）。 int ListLength(LinkList L) /* 本算法用来求带头结点的单链表L的长度 */ {Node *p; p=L->next; j=0; /* 用来存放单链表的长度 */ while(p![KG-*2]=NULL) { p=p->next; j ++; } return j; } /* End of function ListLength */
57
【算法2.11 求单链表的长度】 例2-3 如果以单链表表示集合，假设集合A用单链表LA表示， 集合B用单链表LB表示，设计算法求两个集合的差，即A-B。 算法思想：由集合运算的规则可知，集合的差A-B中包含所有属于集合A而不属于集合B的元素。具体做法是，对于集合A中的每个元素e，在集合B的链表LB中进行查找，若存在与e相同的元素，则从LA中将其删除。
58
void Difference (LinkList LA, LinkList LB)
{ /*此算法求两个集合的差集*/ Node *pre; *p, *r; pre=LA; p=LA->next; /* p指向LA表中的某一结点， 而pre始终指向p 的前驱 */ while(p! =NULL) { q=LB->next; /* 依次扫描LB中的结点， 看是否有与LA中*p结点的值相同的结点 */ while (q! =NULL&&q->data! =p->data) q=q->next; if (q![KG-*2]=NULL)
59
r=p; pre->next=p->next; p=p->next; free(r); } else { pre=p; p=p->next; } } /* while(p! =NULL)*/ }
60
【算法2.12 用单链表求两个集合的差集】 2.3.3 循环链表 循环链表(Circular Linked List)是单链表的另一种形式，它是一个首尾相接的链表。其特点是将单链表最后一个结点的指针域由NULL改为指向头结点或线性表中的第一个结点，就得到了单链形式的循环链表，并称为循环单链表。类似地，还有多重链的循环链表。 在循环单链表中，表中所有结点都被链在一个环上，多重循环链表则是将表中的结点链在多个环上。为了使某些操作实现起来方便，在循环单链表中也可设置一个头结点。 这样，空循环链表仅由一个自成循环的头结点表示。
61
图2.13 带头结点循环单链表
62
例2-4 有两个带头结点的循环单链表LA、LB，编写一个算法，将两个循环单链表合并为一个循环单链表，其头指针为LA。
算法思想：先找到两个链表的尾，并分别由指针p、q指向它们，然后将第一个链表的尾与第二个表的第一个结点链接起来，并修改第二个表的尾Q，使它的链域指向第一个表的头结点。
63
LinkList merge --1(LinkList LA, LinkList LB)
{ /* 此算法将两个链表的首尾连接起来 */ Node *p, *q; p=LA; q=LB; while (p->next! =LA) p=p->next; /* 找到表LA的表尾， 用p指向它 */ while (q->next! =LB) q=q->next; /* 找到表LB的表尾， 用q指向它 */ q->next=LA; /* 修改表LB 的尾指针， 使之指向表LA 的头结点 */ p->next=LB->next; /* 修改表LA的尾指针， 使之指向表LB 中的第一个结点 */ free(LB); return(LA); }
64
【算法2.13 循环单链表的合并算法(1)】 采用上面的方法，需要遍历链表，找到表尾，其执行时间是O(n)。 若在尾指针表示的单循环链表上实现，则只需要修改指针，无需遍历，其执行时间是 O(1)。 LinkList merge --2（LinkList RA, LinkList RB) { /* 此算法将两个链表首尾连接起来 */ Node *p; p=RA->next; /* 保存链表RA的头结点地址 */ RA->next=RB->next->next; /*链表RB的开始结点链到链表RA的终端结点之后 */ free(RB->next); /* 释放链表RB的头结点 */ RB->next=p; /* 链表RA的头结点链到链表RB的终端结点之后 */ return RB; /* 返回新循环链表的尾指针 */ }
65
【算法2.14 循环单链表的合并算法(2)】 2.3.4 双向链表
循环单链表的出现，虽然能够实现从任一结点出发沿着链能找到其前驱结点，但时间耗费是O(n) 。如果希望从表中快速确定某一个结点的前驱，另一个解决方法就是在单链表的每个结点里再增加一个指向其前驱的指针域prior。 这样形成的链表中就有两条方向不同的链，我们可称之为双(向)链表(Double Linked List)。双链表的结构定义如下 typedef struct DNode { ElemType data； struct DNode *prior， *next； }DNode, *DoubleList；
66
图2.14 双链表的结点结构
67
p->prior->next = p = p->next->prior
68
图2.15 双向循环链表图示
69
1. 双向链表的前插操作 图2.16 双向链表插入操作
70
int DlinkIns(DoubleList L, int i, ElemType e)
{ DNode *s, *p; ... /* 先检查待插入的位置i是否合法（实现方法同单链表的前插操作）*/ /* 若位置i合法， 则让指针p指向它 */ s=(DNode*)malloc(sizeof(DNode)); if (s) s->data=e; s->prior=p->prior; p->prior->next=s; s->next=p; p->prior=s; return TRUE; } else return FALSE; }
71
【算法2.15 双向链表的插入操作】 2. 双向链表的删除操作 算法描述： 图2.17 双向链表的删除操作
72
int DlinkDel(DoubleList L, int i, ElemType *e)
{ DNode *p; ... /* 首先检查待插入的位置i是否合法（实现方法同单链表的删除 操作） */ ... /* 若位置i合法， 则让指针p指向它 */ *e=p->data; p->prior->next=p->next; p->next->prior=p->prior; free(p); return TRUE; }
73
【算法2.16 双向链表的删除操作】 例2-5 设一个循环双链表L=（a, b, c, d）, 编写一个算法, 将链表转换为L=（b, a, c, d）。 算法思想： 本题实际上是交换表中前两个元素的次序。
74
void swap(DLinkList L)
{ DNode *p, *q, *h; h=L->next; /* h指向表中的第一个结点， 即a */ p=h->next; /* p指向b结点 */ q=h->prior; /* 保存a 结点的前驱 */ h->next=p->next; /* a结点的后继指向c结点 */ p->next->prior=h; /* c结点的前驱指向a结点 */ p->prior=q; /* 将b结点插入， 作为表的第一个结点 */ p->next=h; L->next=p; /* 将表的头结点的next 域指向b结点 */ }
75
*2.3.5 静态链表 【算法2.17 交换循环双链表中前两个元素的次序】 静态链表同样可以借助一维数组来描述：
* 静态链表 静态链表同样可以借助一维数组来描述： ＃define Maxsize= 链表可能达到的最大长度 typedef struct {ElemType data; int cursor; }Component, StaticList［Maxsize］;
76
图2.18 静态链表的插入和删除操作示例
77
所谓初始化操作, 是指将这个静态单链表初始化为一个备用静态单链表。设space为静态单链表的名字，av为备用单链表的头指针，其算法如下：
1. 初始化 所谓初始化操作, 是指将这个静态单链表初始化为一个备用静态单链表。设space为静态单链表的名字，av为备用单链表的头指针，其算法如下： void initial(StaticList space, int *av) { int k; space［0］->cursor=0; /* 设置已用静态单链表的头指针指向位置0 */ for(k=0; k<Maxsize-1; k++) space［k］->cursor=k+1; /* 连链 */ space［Maxsize-1］=0; /* 标记链尾 */ *av=1; /* 设置备用链表头指针初值 */ }
78
【算法2.18 静态单链表初始化】 2. 分配结点 int getnode(int *av) /* 从备用链表摘下一个结点空间， 分配给待插入静态链表中的元素 */ { int i; i=*av; *av=space［*av］.cur; return i; }
79
【算法2.19 分配结点】 3. 结点回收 void freenode(int *av, int k) /* 将下标为 k的空闲结点插入到备用链表 */ { space［k］.cursor=*av; *av=k; }
80
【算法2.20 空闲结点回收】 4. 前插操作 在已用静态单链表space的第i个数据元素之前插入一个数据元素x。 算法描述： ① 先从备用单链表上取一个可用的结点； ② 将其插入到已用静态单链表第i个元素之前。
81
void insbefore(StaticList space, int i, int *av)
{ int j, k, m; j=*av ; /* j为从备用表中取到的可用结点空间的下标 */ av=space［av］->cursor; /* 修改备用表的头指针 */ space［j］->data=x; k=space［0］->cursor ; /* k 为已用静态单链表的第一个元素的下标值 */ for([ZK(]m=1; m<i-1; m++) /* 寻找第i -1个元素的位置k */ k=space［k］->cursor ; space［j］->cursor=space［k］->cursor; /* 修改游标域， 实现插入操作 */ space［k］->cursor=j; }
82
【算法2.21 在已用静态单链表的第i个元素之前插入元素x】
5. 删除 删除已用静态单链表中第i个元素。 算法描述： ① 寻找第i-1个元素的位置， 然后通过修改相应的游标域进行删除； ② 将被删除的结点空间链到可用静态单链表中，实现回收。
83
void delete(StaticList space; int i; int *av )
{ int j, k, m; k=space［0］->cursor; for(m=1, m<i-1; m++) /* 寻找第i-1个元素的位置k */ k=space［k］->cursor ; j=space［k］->cursor ; space［k］->cursor=space［j］->cursor ; /* 从已用表中删除第i 个 元素 */ space［j］->cursor=*av; /* 将第i 个元素占据的空间回收， 即将其链 入备用表 */ av=j ; /* 置备用表头指针以新值 */ }
84
2.3.6 顺序表和链表的比较 【算法2.22 删除已用静态单链表中的第i个元素】 1. 基于空间的考虑
顺序表和链表的比较 1. 基于空间的考虑 在链表中的每个结点，除了数据域外，还要额外设置指针（或光标）域， 从存储密度来讲，这是不经济的。所谓存储密度(Storage Density), 是指结点数据本身所占的存储量和整个结点结构所占的存储量之比， 即 存储密度=结点数据本身所占的存储量/结点结构所占的存储总量
85
一般地，存储密度越大，存储空间的利用率就越高。显然，顺序表的存储密度为1，而链表的存储密度小于1。例如单链表的结点的数据均为整数，指针所占空间和整型量相同，则单链表的存储密度为50%。因此若不考虑顺序表中的备用结点空间， 则顺序表的存储空间利用率为100%，而单链表的存储空间利用率为50%。由此可知，当线性表的长度变化不大， 易于事先确定其大小时，为了节约存储空间，宜采用顺序表作为存储结构。
86
2. 基于时间的考虑 顺序表是由向量实现的，它是一种随机存取结构，对表中任一结点都可以在O(1)时间内直接地存取，而链表中的结点， 需从头指针起顺着链找才能取得。 因此， 若线性表的操作主要是进行查找，很少做插入和删除时，宜采用顺序表做存储结构。 在链表中的任何位置上进行插入和删除，都只需要修改指针。而在顺序表中进行插入和删除，平均要移动表中近一半的结点，尤其是当每个结点的信息量较大时，移动结点的时间开销就相当可观。因此，对于频繁进行插入和删除的线性表， 宜采用链表做存储结构。若表的插入和删除主要发生在表的首尾两端， 则宜采用尾指针表示的单循环链表。
87
3. 基于语言的考虑 对于没有提供指针类型的高级语言，若要采用链表结构， 则可以使用光标实现的静态链表。虽然静态链表在存储分配上有不足之处，但它和动态链表一样，具有插入和删除方便的特点。 值得指出的是，即使是对那些具有指针类型的语言，静态链表也有其用武之地。特别是当线性表的长度不变，仅需改变结点之间的相对关系时，静态链表比动态链表可能更方便。
88
2.4 一元多项式的表示及相加 对于符号多项式的各种操作，实际上都可以利用线性表来处理。比较典型的是关于一元多项式的处理。在数学上，一个一元多项式Pn(x)可按升幂的形式写成： 它实际上可以由n+1个系数唯一确定。因此，在计算机内， 可以用一个线性表P来表示：
89
假设Qm(x)是一个一元多项式， 则它也可以用一个线性表Q来表示， 即
若假设m<n，则两个多项式相加的结果Rn(x)=Pn(x)+Qm(x)， 也可以用线性表R来表示：
90
我们可以采用顺序存储结构来实现顺序表的方法，使得多项式的相加的算法定义十分简单，即p［0］存系数p0，p［1］存系数p1, …, p［n］存系数p -n， 对应单元的内容相加即可。但是在通常的应用中，多项式的指数有时可能会很高并且变化很大。 例如： 若采用顺序存储，则需要20001个空间，而存储的有用数据只有三个，这无疑是一种浪费。 若只存储非零系数项， 则必须存储相应的指数信息才行。
91
假设一元多项式Pn(x)=p1xe1+p2xe2+…+pmxem，其中pi是指数为ei的项的系数(且0≤e1≤e2≤…≤em=n)， 若只存非零系数，则多项式中每一项由两项构成（指数项和系数项），用线性表来表示， 即 采用这样的方法存储，在最坏情况下，即n+1个系数都不为零， 则比只存储系数的方法多存储1倍的数据。但对于非零系数多的多项式则不宜采用这种表示。
92
（1） 用单链表存储多项式的结点结构如下：
struct Polynode { int coef; int exp; Polynode *next; } Polynode, * Polylist;
93
（2） 通过键盘输入一组多项式的系数和指数，以输入系数0为结束标志，并约定建立多项式链表时，总是按指数从大到小的顺序排列。
算法描述：从键盘接受输入的系数和指数； 用尾插法建立一元多项式的链表。 Polylist polycreate() { Polynode *head, *rear, *s; int c, e; h=(Polynode *)malloc(sizeof(Polynode)); /*建立多项式的头结点*/ rear=head; /* rear 始终指向单链表的尾， 便于尾插法建表*/
94
scanf(″%d, %d″, &c, &e); /*键入多项式的系数和指数项*/
while(c! =0) /*若c=0， 则代表多项式的输入结束*/ { s=(Polynode*)malloc(sizeof(Polynode)); /*申请新的结点*/ s->coef=c ; s->exp=e ; rear->next=s ; /*在当前表尾做插入*/ rear=s; scanf(″%d, %d″, &c, &e); } rear->next=NULL; /*将表的最后一个结点的next置NULL， 以示表结束*/ return(head); }
95
【算法2.23 用尾插法建立一元多项式的链表】 （3） 图2.19 所示为两个多项式的单链表， 分别表示多项式A（x）=7+3x+9x8+5x17和多项式B(x)=8x+22x7-9x8。 图2.19 多项式的单链表表示法
96
多项式相加的运算规则是：两个多项式中所有指数相同的项的对应系数相加， 若和不为零，则构成“和多项式”中的一项；所有指数不相同的项均复抄到“和多项式”中。 以单链表作为存储结构，并且 “和多项式“中的结点无需另外生成， 则可看成是将多项式B加到多项式A中，由此得到下列运算规则（设p、q分别指向多项式A、 B的一项，比较结点的指数项）： 若p->exp<q->exp， 则结点p所指的结点应是“和多项式”中的一项， 令指针p后移；
97
若p->exp>q->exp，则结点q所指的结点应是“和多项式”中的一项， 将结点q插入在结点p之前，且令指针q在原来的链表上后移；
若p->exp=q->exp， 则将两个结点中的系数相加， 当和不为零时修改结点p的系数域， 释放q结点；若和为零，则和多项式中无此项， 从A中删去p结点， 同时释放p和q结点。
98
void polyadd(Polylist polya; Polylist polyb)
/*此函数用于将两个多项式相加，然后将和多项式存放在多项式polya中，并将多项式ployb删除*/ { Polynode *p, *q, *pre; *temp; int sum; p=polya->next ; /* 令p和q分别指向polya和polyb多项式链表中的第一个结点 */ q=polyb->next ; pre=polya; /* pre指向和多项式的尾结点 */ while （p! =NULL && q! =NULL） /* 当两个多项式均未扫描结束时 */ {
99
if （p->exp< q->exp）
/* 如果p指向的多项式项的指数小于q的指数， 将p结点加入到和多项式中 */ { pre->next=p; pre=pre->next; p=p->next； } else if ( p->exp==q->exp）/* 若指数相等， 则相应的系数相加 */ {sum=p->coef + q->coef ; if (sum![KG-*2]=0) {p->coef=sum; pre->next=p; pre=pre->next; p=p->next; } else
100
{ temp=p->next ; free(p); p=temp ;
/* 若系数和为零， 则删除结点p与q， 并将指针指向下一个结点 */ temp=q->next; free(q); q=temp ; } } else {pre->next=q; pre=pre->next; /* 将q结点加入到和多项式中 */ q =q->next; } } if(p! =NULL) /* 多项式A中还有剩余， 则将剩余的结点加入到和多 项式中 */ pre->next=p; else /* 否则， 将B中的结点加入到和多项式中 */ pre->next=q; }
101
【算法2.24 多项式相加】 图2.20 多项式相加得到的多项式和
Similar presentations
