《第2章-线性表》由会员分享，可在线阅读，更多相关《第2章-线性表（107页珍藏版）》请在金锄头文库上搜索。
1、上节课内容回顾上节课内容回顾l数据结构、抽象数据类型数据的逻辑结构数据的逻辑结构 数据的存储结构数据的存储结构 定义其上的运算集合定义其上的运算集合 线性结构（线性表、栈、队列、字符串、数组、广义表）线性结构（线性表、栈、队列、字符串、数组、广义表） 非线性结构非线性结构 顺序存储顺序存储 非顺序存储非顺序存储 9/17/20241第第2章章 线性表线性表 l2.1 线性表的概念及运算 l2.2 线性表的顺序存储 l2.3 线性表的链式存储 l2.4 一元多项式的表示及相加l2.5 顺序表和链表的比较9/17/202422.1 2.1 线性表的概念及运算线性表的概念及运算l2.1.1 2.1.
2、1 线性表的逻辑结构线性表的逻辑结构 l2.1.2 2.1.2 线性表的抽象数据类型定义线性表的抽象数据类型定义 9/17/202432.1.1 2.1.1 线性表的逻辑结构线线性性表表(Linear List)是由n (n0)个类型相同的数据元素a1,a2,，an组成的有限序列，记做（a1,a2,，ai-1，ai，ai+1， ，an）。 数据元素之间是一对一的关系，即每个数据元素最多有一个直接前驱和一个直接后继。 线性表的逻辑结构图为：9/17/20244线性表的特点线性表的特点同一性：线性表由同类数据元素组成，每一个ai必须属于同一数据对象。有穷性：线性表由有限个数据元素组成，表长度就是表
3、中数据元素的个数。有序性：线性表中相邻数据元素之间存在着序偶关系。9/17/20245线性表举例线性表举例 A = (a1，a2，a3， . . , an)99001 张华张华 女女17 99002 李军李军 男男18 99003 王小明王小明 男男17 学号学号 姓名姓名性别性别年龄年龄其他其他99050 刘末刘末 女女19 a1a2a3 a50数据文件：数据文件： a1 a2 a3 a4, a5 a6 数列：数列： ( 25， 12， 78， 34， 100， 88) a1 a2 a3 a24, a25 a26 字母表：字母表： ( A， B， C， , X, Y, Z)9/17/2024
4、62.1.2 抽象数据类型定义ADT 数据对象: 结构关系: 基本操作:ADT 基本操作的定义格式为： (参数表) 操作前提: 操作结果:9/17/20247线性表的抽象数据类型定义ADT LinearList数据元素数据元素：D=ai|aiD0,i=1,2,，nn0，D0为某一数据对象 结构关系结构关系：|ai,ai+1D0，i=1,2,n-1 基本操作基本操作： （1）InitList（L） 操作前提：L为未初始化线性表。 操作结果：将L初始化为空表。 （2）DestroyList(L)操作前提：线性表L已存在。 操作结果：将L销毁。 （3）ClearList(L)操作前提：线性表L已存在
5、。 操作结果：将表L置为空表。 （4）ListLength(L)操作前提：线性表L已存在。 操作结果：L为空返回0，否则返回表中数据元素的个数。 ADTLinearList9/17/202482.2 2.2 线性表的顺序存储线性表的顺序存储l2.2.1 线性表的顺序存储结构线性表的顺序存储结构l2.2.2 线性表顺序存储结构上的基本运算线性表顺序存储结构上的基本运算9/17/202492.2.1 2.2.1 顺序存储结构的定义 线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素，使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关
6、系来反映数据元素之间逻辑上的相邻关系。采用顺序存储结构的线性表通常称为顺序表顺序表。 假设线性表中每个元素占k个单元，第一个元素的地址为loc(a1)，则第i个元素的地址为： loc(ai) =loc(a1)+(i-1)k 9/17/202410顺序存储结构示意图顺序存储结构示意图存储地址内存空间状态逻辑地址Loc(a1)a11Loc(a1)+(2-1)ka22loc(a1)+(i-1)kaiiloc(a1)+(n-1)kann.loc(a1)+(maxlen-1)k 空闲9/17/202411顺序存储结构的顺序存储结构的C语言定义语言定义#definemaxsize=线性表可能达到的最大长度
7、；typedefstructElemTypeelemmaxsize；/*线性表占用的数组空间*/intlast；/*记录线性表中最后一个元素在数组elem 中的位置（下标值），空表置为-1*/SeqList；注意区分元素的序号和数组的下标，如a1的序号为1，而其对应的数组下标为0。 9/17/2024122.2.2线性表顺序存储结构的基本运算l线性表的基本运算：1.查找操作2.插入操作3.删除操作4.顺序表合并算法l线性表顺序存储结构的优缺点分析9/17/202413查找操作查找操作线性表的两种基本查找运算1.1.按序号查找按序号查找GetData(L,i)：要求查找线性表L中第i个数据元素，
8、其结果是L.elemi-1 。2.2.按内容查找按内容查找Locate（L,e）: : 要求查找线性表L中与给定值e相等的数据元素，其结果是：若在表L中找到与e相等的元素，则返回该元素在表中的序号；若找不到，则返回一个“空序号”，如-1。 线性表的查找运算算法描述为：9/17/202414线性表的查找运算线性表的查找运算 int Locate(SeqListL，ElemTypee)i=0;/*i为扫描计数器，初值为0，即从第一个元素开始比较*/while(i=L.last)&(L.elemi!=e) )i+;/*顺序扫描表，直到找到值为key的元素,或扫描到表尾而没找到*/if(i=L.las
9、t)return(i);/*若找到值为e的元素，则返回其序号*/ elsereturn(-1);/*若没找到，则返回空序号*/9/17/202415插入操作插入操作 线性表的插入运算是指在表的第i (1in+1)个位置，插入一个新元素e，使长度为n的线性表 (e1，ei-1，ei，en) 变成长度为n+1的线性表（e1，,ei-1，e e，ei，en） n n个数据元素个数据元素n+1n+1个数据元素个数据元素9/17/202416插入算法示意图插入算法示意图已知：已知：线性表(4,9,15,28,30,30,42,51,62)，需在第4个元素之前插入一个元素“21”。则需要将第9个位置到第4
10、个位置的元素依次后移一个位置，然后将“21”插入到第4个位置，序号移动元素插入元素12345678109491528303042516249152830304262514915212830304262519/17/202417插入运算插入运算intInsList(SeqList*L,inti,ElemTypee)intk;if(iL-last+2)/*首先判断插入位置是否合法*/printf(“插入位置i值不合法”)；return(ERROR);if(L-last=maxsize-1)printf(“表已满无法插入”)；return(ERROR);for(k=L-last;k=i-1;k-)/
11、*为插入元素而移动位置*/L-elemk+1=L-elemk;L-elemi-1=e;/*在C语言中数组第i个元素的下标为i-1*/L-last+;return(OK);9/17/202418时间复杂度分析时间复杂度分析 若若设设pi为为插插入入一一个个元元素素于于线线性性表表第第i个个位位置置的的概概率率( (概概率率相相等等) )，则则在在长长度度为为n的的线线性性表表中中插插入入一一个个元元素素需需要要移移动其他的元素的平均次数为动其他的元素的平均次数为： Tins= pi(n-i+1) = (n-i+1)/(n+1) = n/2称该算法的时间复杂度是称该算法的时间复杂度是O(n)。ni
12、=1ni=19/17/202419删除操作删除操作线性表的删除运算是指将表的第i(1in)个元素删去，使长度为n的线性表(e1，,ei-1，ei，ei+1，en) 变成长度为n-1的线性表(e1，,ei-1，ei+1，en)n n个数据元素个数据元素n-1n-1个数据元素个数据元素9/17/202420删除算法示意删除算法示意将线性表(4,9,15,21,28,30,30,42,51,62)中的第5个元素删除。序号123456781094915212830304262514915213030425162删除28后9/17/202421删除算法删除算法intDelList(SeqList*L,i
13、nti,ElemType*e)/*在顺序表L中删除第i个数据元素，并用指针参数e返回其值*/intk;if(iL-last+1)printf(“删除位置不合法！”)；return(ERROR)；*e=L-elemi-1; /*将删除的元素存放到e所指向的变量中*/for(k=i;ilast;k+) L-elemk-1=L-elemk;/*将后面的元素依次前移*/L-last-;return(OK);9/17/202422时间复杂度分析时间复杂度分析 在在长长度度为为n的的线线性性表表中中删删除除第第i个个数数据据元元素素需需要要移移动动其他的元素的平均次数为：其他的元素的平均次数为： Tdel
14、= Pi(n-i) = (n-i)/n = (n-1)/2称该算法的时间复杂度为称该算法的时间复杂度为O(n)。 ni=1ni=19/17/202423合并算法合并算法l已知：有两个顺序表LA和LB，其元素均为非递减有序排列，编写一个算法，将它们合并成一个顺序表LC，要求LC也是非递减有序排列。l例如例如：LA = 2,2,3, LB= 1，3，3，4，合并之后得到LC = 1，2，2，3，3，3，4。9/17/202424算法思想算法思想l设表LC是一个空表，为使LC也是非递减有序排列，可设两个计数器i、j分别指向表LA和LB中的元素，然后，若LA.elemiLB.elemj，则当前先将LB
15、.elemj插入到表LC中，LC的计数器k增加1，同时j+；若LA.elemiLB.elemj，当前先将LA.elemi插入到表LC中， LC的计数器k增加1，同时i+。l如此进行下去，直到其中一个表被扫描完毕，然后再将未扫描完的表中剩余的所有元素放到表LC中。9/17/202425顺序表顺序表合并算法实现合并算法实现voidmerge(SeqList*LA,SeqList*LB,SeqList*LC)i=0;j=0;k=0;while(ilast&jlast)if(LA-elemielemj) LC-elemk=LA-elemi;i+;k+;elseLC-elemk=LB-elemj;j+;
16、k+;while(ilast)/*当表LA长则将表LA余下的元素赋给表LC*/LC-elemk=LA-elemi;i+;k+;while(jlast)/*当表LB长则将表LB余下的元素赋给表LC*/LC-elemk=LB-elemj;j+;k+;LC-last=LA-last+LB-last;9/17/202426顺序存储结构的优点和缺点顺序存储结构的优点和缺点优点：1.无需为表示结点间的逻辑关系而增加额外的存储空间；2.可方便地随机存取表中的任一元素。缺点：1.插入或删除运算不方便，除表尾的位置外，在表的其它位置上进行插入或删除操作都必须移动大量的结点，其效率较低；2.由于顺序表要求占用连续
17、的存储空间，存储分配只能预先进行静态分配。因此当表长变化较大时，难以确定合适的存储规模。9/17/202427练习练习如如:（1，2，2，3，3，4）-(1, 2, 3, 4 ) 已知长度为已知长度为n 的线性表的线性表A采用顺序存储结构，并且数据采用顺序存储结构，并且数据元素按值大小非递减排列。元素按值大小非递减排列。 写一算法，删除线性表中值相写一算法，删除线性表中值相同的多余元素。同的多余元素。9/17/202428伪代码伪代码 procedure DEL( A, n ) i1 /从第一个元素开始查从第一个元素开始查 while (inext = H-next; H-next =s;9/
18、17/202438头插法建表算法头插法建表算法Linklist CreateFromHead() LinkList L; Node *s; int flag=1; /* 设置一个标志，初值为1，当输入“$”时，flag为0，建表结束*/ L=(Linklist)malloc(sizeof(Node)；/*为头结点分配存储空间*/ L-next=NULL; while(flag) c=getchar(); if(c!=$) /*为读入的字符分配存储空间*/ s=(Node*)malloc(sizeof(Node); s-data=c; s-next=L-next; L-next=s; else
19、flag=0; 9/17/202439r=s; sc2 Lc1 r尾插法建表尾插法建表r-next=s; l尾插法建表算法描述：算法描述：从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表尾结点之后，直至读入结束标志为止。Lrc1 sLc1 sr9/17/202440尾插法建表算法尾插法建表算法Linklist CreateFromTail() /*将新增的字符追加到链表的末尾*/ LinkList L; Node *r, *s; int flag =1; L=(Node * )malloc(sizeof(Node);/*为头结点分配存储
20、空间*/ L-next=NULL; r=L; /*r指针始终动态指向链表的当前表尾*/ while(flag)/*标志，初值为1。输入“$”时flag为0，建表结束*/ c=getchar(); if(c!=$) s=(Node*)malloc(sizeof(Node); s-data=c; r-next=s; r=s; else flag=0; r-next=NULL; 9/17/202441单链表查找单链表查找l按序号查找目标：目标：设带头结点的单链表的长度为n，要查找表中第i个结点. 算法描述：算法描述：从单链表的头指针L出发，从头结点开始顺着指针域扫描，用指针p指向当前扫描到的结点。初
21、值指向头结点（p=L），用j做记数器，累计当前扫描过的结点数（初值为0），当j=i时，指针p所指的结点就是要找的第i个结点。9/17/202442按序号查找算法实现按序号查找算法实现/ * 在带头结点的单链表L中查找第i个结点，若找到(1in)，则返回该结点的存储位置; 否则返回NULL * /Node * Get(LinkList L, int i) Node *p； p=L；j=0； / * 从头结点开始扫描 * / while (p-next!=NULL)&(jnext； / * 扫描下一结点 * / j+； / * 已扫描结点计数器 * / if（i= =j）return p； / *
22、 找到了第i个结点 * / else return NULL； / * 找不到，i0或in * /比较返回9/17/202443l按值查找 目标：目标：在单链表中查找是否有结点值等于e的结点。 算法描述：算法描述：从单链表的头指针指向的头结点出发，顺着链逐个将结点的值和给定值e作比较。如果相等，则返回结点的存储位置，否则返回NULL。单链表查找单链表查找9/17/202444按值查找算法实现按值查找算法实现/ * 在带头结点的单链表L中查找其结点值等于key的结点，若找到则返回该结点的位置p，否则返回NULL * /Node *Locate( LinkList L,ElemType key)
23、Node *p; p=L-next; / * 从表中第一个结点比较 * / while (p!=NULL) if (p-data!=key) p=p-next; else break; / * 找到结点key，退出循环 * / return p;While (p!=NULL) if (p-data=key) break; p = p-next;9/17/202445单链表插入操作单链表插入操作l算法描述： 要在带头结点的单链表L中第i个数据元素之前插入一个数据元素e，需要首先在单链表中找到第i-1个结点并由指针pre指示，然后申请一个新的结点并由指针s指示，其数据域的值为e，并修改第i-1个结
24、点的指针使其指向s，然后使s结点的指针域指向第i个结点。espres-next=pre-nextpre-next=sa1an ai-1aiL9/17/202446单链表插入操作算法实现单链表插入操作算法实现void InsList(LinkList L,int i,ElemType e) /*在带头结点的单链表L中第i个结点之前插入值为e的新结点。 */ Node *pre,*s; pre=L; int k=0; while(pre!=NULL&knext;k=k+1; if(k!=i-1) printf(“插入位置不合理！”)； return; s=(Node*)malloc(sizeof(
25、Node); /*为e申请一个新的结点*/ s-data=e; /*将待插入结点的值e赋给s的数据域*/ s-next=pre-next; pre-next=s;比较 返回9/17/202447单链表删除单链表删除l算法描述： 欲在带头结点的单链表L中删除第i个结点，则首先要通过计数方式找到第i-1个结点并使p指向第i-1个结点，而后删除第i个结点并释放结点空间。 a1Lan ai-1aiai+1prr=p-next;p-next=r-next;free(r);9/17/202448单链表删除算法实现单链表删除算法实现void DelList(LinkList L,int i)/*在带头结点的
26、单链表L中删除第i个元素*/ Node *p,*r; p=L; int k =0;while(p-next!=NULL&knext; k=k+1; if(k!=i-1) /* 即while循环是因为p-next=NULL而跳出的*/ printf(“删除结点的位置i不合理！”); return ERROR; r=p-next; p-next=r-next /*保持链接关系*/ free(r); /*释放被删除的结点所占的内存空间*/比较9/17/202449求单链表的长度求单链表的长度算法描述：算法描述：可以采用“数”结点的方法来求出单链表的长度，用指针p依次指向各个结点,从第一个元素开始“数
27、”，一直“数”到最后一个结点（p-next=NULL）。int ListLength(LinkList L) /*L为带头结点的单链表*/ Node *p; p=L-next; /从第一个节点开始 j=0; /*用来存放单链表的长度*/ while(p!=NULL) p=p-next; j +; return j;9/17/202450两个有序单链表的合并两个有序单链表的合并l有两个单链表LA和LB，其元素均为非递减有序排列，编写一个算法，将它们合并成一个单链表LC，要求LC也是非递减有序排列。要求：利用新表LC利用现有的表LA和LB中的元素结点空间，而不需要额外申请结点空间。l例如LA=(2
28、,2,3),LB=(1,3,3,4),则LC=(1,2,2,3,3,3,4)。 9/17/202451算法思想算法思想l设表LC是一个空表，为使LC也是非递减有序排列，可设两个指针pa、pb分别指向表LA和LB中的元素，然后，若pa-datapb-data，则当前先将pb插入到表LC中，同时LC的计数指针r=pb，并且pb更新为pb-next；若pa-datapb-data，当前先将pa插入到表LC中，同时LC的计数指针r=pa，并且pa更新为pa-next。l如此进行下去，直到其中一个表被扫描完毕，然后再将未扫描完的表中剩余的所有元素放到表LC中。9/17/202452两个有序单链表的合并的
29、算法实现两个有序单链表的合并的算法实现LinkListMergeLinkList(LinkListLA,LinkListLB)/*将递增有序的单链表LA和LB合并成一个递增有序的单链表LC*/Node*pa,*pb;LinkListLC；/*将LC初始置空表。pa和pb分别指向两个单链表LA和LB中的第一个结点,r初值为LC*/pa=LA-next;pb=LB-next;LC=LA;LC-next=NULL；r=LC;/*初始化操作*/9/17/202453两个有序单链表的合并的算法实现（续）两个有序单链表的合并的算法实现（续）/*当两个表中均未处理完时，比较选择将较小值结点插入到新表LC中。
30、*/while(pa!=NULL&pb!=NULL)if(pa-datadata)r-next=pa;r=pa;pa=pa-next;elser-next=pb;r=pb;pb=pb-next;if(pa)/*若表LA未完，将表LA中后续元素链到新表LC表尾*/r-next=pa;else/*否则将表LB中后续元素链到新表LC表尾*/r-next=pb;free(LB);return(LC);9/17/202454练习练习题目：题目： 若已知非空线性链表第一个结点的指针为若已知非空线性链表第一个结点的指针为list，请写一请写一个算法，个算法， 将该链表中数据域值最小的那个结点移到链表将该链表
31、中数据域值最小的那个结点移到链表的最前端。的最前端。L356718658271521014L356718658271521014qsqpprq=p;rq=p; s=r;qs9/17/202455伪代码伪代码 procedure MOVE( LinkList L ) qL pL-next rL while (p NULL) do /查到最小值，得到结点指针查到最小值，得到结点指针 s 和和q if (p-datadata) then sr qp rp pp-next end /把最小值结点放在首位把最小值结点放在首位 if (q list) then / 若值最小的结点不是链表最前面那个结点若值
32、最小的结点不是链表最前面那个结点 / link(s)link(q) link(q)list listq end9/17/2024562.3.3循环链表l循环链表(CircularLinkedList) 是一个首尾相接的链表。l特点特点：将单链表最后一个结点的指针域由NULL改为指向头结点或线性表中的第一个结点，就得到了单链形式的循环链表，并称为循环单链表。在循环单链表中，表中所有结点被链在一个环上。9/17/202457带头结点的循环单链表示意图带头结点的循环单链表示意图a1ai-1aian L带头头结点的一般形式 L空链表L-next=L;与单链表相比，循环链表判断表尾结点的条件不同：p-n
33、ext = NULL p-next = L9/17/202458采用尾指针的循环链表采用尾指针的循环链表rearrear-nextrear-next-nexta1ai-1aian 带尾尾结点的一般形式 L查找开始结点和终端结点都很方便9/17/202459循环单链表合并为一个循环单链表循环单链表合并为一个循环单链表已知已知：有两个带头结点的循环单链表LA、LB，编写一个算法，将两个循环单链表合并为一个循环单链表，其头指针为LA。算法思想算法思想：先找到两个链表的尾，并分别由指针p、q指向它们，然后将第一个链表的尾与第二个表的第一个结点链接起来，并修改第二个表的尾Q，使它的链域指向第一个表的头结
34、点。 9/17/202460循环单链表合并算法实现循环单链表合并算法实现LinkList merge_1(LinkList LA, LinkList LB)/*此算法将两个链表的首尾连接起来*/ Node *p, *q; p=LA; q=LB; while (p-next!=LA) p=p-next;/*找到表LA的表尾*/ while (q-next!=LB) q=q-next;/*找到表LB的表尾*/ p-next=LB-next;/*修改表LA的尾指针，使之指向表LB 中的第一个结点*/ q-next=LA;/*修改表LB 的尾指针，使之指向表LA 的头结点*/free(LB); ret
35、urn(LA);若采用尾指针表示的循环链表，若采用尾指针表示的循环链表，该如何实现？该如何实现？9/17/2024612.3.4双向链表l单链表的缺陷：LC1 Cn-1 Cn l无论是单链表还是循环单链表，很方便找一个结点的后继结点，但找到其前驱结点需要从头指针进行遍历a1ai-1aian L9/17/202462双向链表的结点 data next指针域数据域后继指针域Prior data next前驱指针域数据域l双向链表：双向链表：在单链表的每个结点里再增加一个指向其前趋的指针域prior。这样形成的链表中就有两条方向不同的链，我们称之为双双 ( 向向) 链表链表(DoubleLinked
36、List)。单链表：双链表：9/17/202463双链表的结构定义双链表的结构定义typedefstructDNodeElemTypedata；structDNode*prior，*next；DNode,*DoubleList；9/17/202464双向循环链表示意图双向循环链表示意图 a1 a2 a3L非空的双向循环链表 L空的双向循环链表 L-next = LL-prior = Lp-prior-next = = pP= = p-next-prior9/17/202465双向链表的运算双向链表的运算l建立双链表（头插/尾插法）l求表长度、l查找（按序号/值）l前插操作（回顾单链表的前插）l
37、删除操作（回顾单链表的删除）9/17/202466双向链表的前插操作双向链表的前插操作l算法描述：欲在双向链表第i个结点之前插入一个的新的结点，则指针的变化情况如图所示。 esp ai ai-1 9/17/202467双向链表的前插操作算法实现双向链表的前插操作算法实现void 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;
38、 p-prior-next=s; s-next=p; p-prior=s; return TRUE; else return FALSE;9/17/202468双向链表的删除操作双向链表的删除操作l算法描述：欲删除双向链表中的第i个结点，则指针的变化情况如图所示。p ai-1 ai ai+1free9/17/202469双向链表的删除操作算法实现双向链表的删除操作算法实现Int DlinkDel(DoubleList L, int i, ElemType *e)DNode *p; /*首先检查待插入的位置i是否合法*/ /*若位置i合法，则让指针p指向它*/ *e=p-data; p-prio
39、r-next=p-next; p-next-prior=p-prior; free(p); return TRUE; 9/17/202470*2.3.5静态链表l动态链表：malloc，freel静态链表基本概念：采用顺序存储结构数组模拟实现链表，采用游标模拟指针，并由程序员自己编写从数组中“分配结点”和“回收结点”，这种方式就被称为静态单链表静态单链表(StaticLinkedList)9/17/202471采用游标实现链表采用游标实现链表l定义一个较大的结构数组结构数组作为备用结点空间（即存储池）。当申请结点时，每个结点应含有两个域：data域和next域。data域存放结点的数据信息，n
40、ext域为游标指示器，指示后继结点在结构数组中的相对位置（即数组下标）。数组的第0个分量可以设计成表的头结点，头结点的next域指示了表中第一个结点的位置，为-1表示静态单链表的结束。9/17/202472静态链表的结构定义静态链表的结构定义#define Maxsize= 链表可能达到的最大长度typedef struct ElemType data; int cursor; /类似于类似于nextnext指针域指针域 Component, StaticListMaxsize;9/17/202473静态链表的插入和删除操作示例静态链表的插入和删除操作示例已知已知：线性表a，b，c，d，f，g
41、，h，i），Maxsize=110123456789100123456789101a 2b 3c 4d 9f 6g 8h 8i 0e 51a 2b 3c 4d 9f 6g 7h 8i 0e 51a 2b 3c 4d 5f 6g 7h 8i -1012345678910(a)初始化(b)在第4个元素后插入e(c)删除h 9/17/202474备用静态链表备用静态链表l“假满”l如何解决“加满”：将所有未分配的结点以及因删除操作等回收的结点也采用游标组成另一个链表，称为备用静态链表备用静态链表。里面的结点随着已用静态链表的操作而对应更新。l基本操作：初始化、分配结点与结点回收9/17/202475
42、静态链表初始化初始化l算算法法描描述述：初始化操作是指将这个静态单链表初始化为一个备用静态单链表。设space为静态单链表的名字，av为备用单链表的头指针，其算法如下：void initial(StaticList space, int *av) int k; space0-cursor=-1;/*设 置 静 态 单 链 表 的 头 指 针 指 向 位置-1*/ for(k=1;kcursor=k+1; /*连链*/ spaceMaxsize-1 .cursor=0; /*标记链尾*/ *av=1; /; /*设置备用链表头指针初值*/ 9/17/202476静态链表分配结点分配结点/*从备用
43、链表摘下一个结点空间，分配给待插入静态链表中的元素*/int getnode(StaticList space，int *av) int i=*av; *av=space*av.cur; return i; 9/17/202477静态链表的结点回收的结点回收/*将下标为 k的空闲结点插入到备用链表*/void freenode(int *av,int k) spacek.cursor=*av; *av=k; 9/17/2024782.4 2.4 一元多项式的表示及相加一元多项式的表示及相加l一元多项式可按升幂的形式写成：lPn(x)=p0+p1xe1+p2xe2+pnxen，l其中ei为第i项
44、的指数，pi是指数ei的项的系数，(且1e1e2en)l假设Qm(x)是一个一元多项式，则它也可以用一个线性表Q来表示。即：lQ=(q0，q1，q2，qm)l若假设mcoef=c;s-exp=e;rear-next=s;/*在当前表尾做插入*/rear=s;scanf(“%d,%d”,&c,&e);rear-next=NULL;/*将表最后一个结点的next置NULL，以示表结束*/return(head);9/17/202485一元多项式的单链表表示示意图一元多项式的单链表表示示意图说明：图示分别为多项式A(x)=7+3x+9x8+5x17B(x)=8x+22x7-9x8-17 03 15
45、17 9 88 1 -122 7 -9 8 polyapolyb9/17/202486两个一元多项式相加多项式相加l运运算算规规则则：两个多项式中所有指数相同的项的对应系数相加，若和不为零，则构成“和多项式”中的一项；所有指数不相同的项均复抄到“和多项式”中。若p-expexp，则结点p所指的结点应是“和多项式”中的一项，令指针p后移；若p-expq-exp，则结点q所指的结点应是“和多项式”中的一项，将结点q插入在结点p之前，且令指针q在原来的链表上后移；若p-exp=q-exp，则将两个结点中的系数相加，当和不为零时修改结点p的系数域，释放q结点；若和为零，则和多项式中无此项，从A中删去p
46、结点，同时释放p和q结点。9/17/202487两个多项式相加算法实现多项式相加算法实现void polyadd(Polylist polya, Polylist polyb) Polynode *p, *q, *tail, *temp; int sum; p = polya-next; q = polyb-next; tail = polya; while p!=NULL & q!=NULL） if (p-exp exp） tail-next = p; tail = p; p = p-next; /将p结点加入到和多项式中 else if ( p-exp= =q-exp） sum = p-c
47、oef+q-coef; if(sum!=0) /若指数相等，则相应的系数相加。若系数为0则删除p，q节点 p-coef = sum; tail-next = p; tail=p; p=p-next; temp=q; q=q-next; free(temp); 9/17/202488两个多项式相加算法实现（续）多项式相加算法实现（续） else temp = p; p=p-next; free(temp); temp = q; q=q-next; free(temp); else /将q结点加入到和多项式中 tail-next = q, tail = q; q=q-next; /将多项式poly
48、a或polyb中剩余的结点加入到和多项式中 if(p != NULL) tail-next = p; else tail-next = q;9/17/2024892.5顺序表和链表的比较 l1基于空间的考虑l2基于时间的考虑l3基于语言的考虑9/17/202490基于空间的考虑基于空间的考虑l顺序表的存储空间是静态分配，问题规模难以估计，容易照成空间浪费或溢出；l链表是动态分配存储空间，难以估计问题规模时，宜用链表；l存储密度：结点数据本身所占存储量/结点结构所占的存储总量。顺序表的存储空间利用率为100%，单链表为50%，双链表33.3%。9/17/202491基于时间的考虑基于时间的考虑l
49、顺序表对表中任一结点都可以在O(1)的时间内直接存取，而链表则需从头指针顺着链才能找到；l在链表中任意位置上进行插入和删除，只需修改指针，而在顺序表中进行插入和删除时，平均需移动一半的结点。9/17/202492基于语言的考虑基于语言的考虑lC语言l没有提供指针类型的高级语言环境中，若想采用链表结构，就需使用游标实现的静态链表。9/17/202493线性表链式存储方式的比较线性表链式存储方式的比较 操作名称链表名称找表头结点找表尾结点找P结点前驱结点带头结点单链表LL-next时间耗费O(1)一重循环时间耗费O(n)顺P结点的next域无法找到P结点的前驱带头结点循环单链表（头指针）LL-ne
50、xt时间耗费O(1)一重循环时间耗费O(n)顺P结点的next域可以找到P结点的前驱时间耗费O(n)带尾指针的循环单链表R R-next O(1)R时间耗费O(1)顺P结点的next域可以找到P结点的前驱时间耗费O(n)带头结点双向循环链表L L-next O(1)L-prior时间耗费O(1)P-prior时间耗费O(1)9/17/2024942.6小结与提高（1）主要知识点主要知识点：l1、线性表的特征、线性表的特征：线性表中每个数据元素有且仅有一个直接前驱和一个直接后继，第一个结点无前驱，最后一个结点无后继。l2、线性表存储方式线性表存储方式：线性表顺序存储（顺序表）：采用静态分配方式，
51、借助于C语言的数组类型，申请一组连续的地址空间，依次存放表中元素，其逻辑次序隐含在存储顺序之中。9/17/202495小结与提高（2）线性表链式存储（链表）：采用动态分配方式，借助于C语言的指针类型，动态申请与动态释放地址空间，故链表中的各结点的物理存储可以是不连续的。当表长度变化时仅需适当变化指针的联接，适合于表中元素个数动态变化。l3、单链表的操作特点、单链表的操作特点：顺链操作技术指针保留技术9/17/202496小结与提高（3）l4、链表处理中的相关技术链表处理中的相关技术单链表与多链表区别在于指针域的个数一般单链表与循环单链表区别在于是否首尾相连(3)尾端结点的判断(4)链表的表长度
52、n并未显示保存9/17/202497典型题例典型题例1l l例例例例1 1：已知顺序表L中的数据元素类型为int。设计算法将其调整为左右两部分，左边的元素（即排在前面的）均为奇数，右边所有元素（即排在后面的）均为偶数，并要求算法的时间复杂度为O(n)，空间复杂度为O（1）。9/17/202498例例1【问题分析问题分析】l初见此题，可能会想到额外申请1个顺序表空间，之后依次从顺序表L中选择奇数放入新表前部分，选择偶数放在新表的后半部分。但是题目要求空间复杂度为O(1),很显然上述方法是不可行的。既然要求空间复杂度为O(1)，说明只能借助1个辅助空间。分析题目要求，其实我们只需要将位于表左半部分
53、的偶数与位于表右半部分的奇数通过一个辅助变量进行交换即可，为此我们可以设置两个位置指示器i和j,i初值为0，j初值为L-last,当L-elemi为偶数，L-elemj为奇数时，则将L-elemi与L-elemj交换；否则，L-elemi为奇数,i+,L-elemj为偶数，j+。这样既可以保证算法的时间复杂度为O(n),亦可保证空间复杂度为O（1）。9/17/202499【算法实现算法实现】AdjustSqlist(SeqList*L)inti=0,j=L-last;while(ielemi%2!=0&ielemj%2=0&ij)j-；/*从表的右半部分开始检测，若为偶数，则j减1,直到找到奇
54、数为止*/if(ielemi;L-elemi=L-elemj;L-elemj=t;/*交换*/9/17/2024100典型题例典型题例2l例2：算法实现带头结点单链表的就地逆置问题。l【问题分析】逆置就是使得表中内容由原来的（a1,a2,，ai-1，ai，ai+1，an）变为（an,an-1,，ai+1，ai，ai-1，a1）。就地逆置就是不需要额外申请结点空间，只需要利用原有的表中的节点空间。若对顺序表中的元素进行逆置，可以借助于“交换”前后相应元素；对单链表中的元素进行逆置，则不能按“交换”思路，因为对于链表中第i个结点需要顺链查找第n-i+1(链表长度为n)个结点，逆置链表的时间复杂度将
55、达O（n2）。9/17/2024101算法思路算法思路l l算法思路：算法思路：算法思路：算法思路：逆置后的单链表初始为空，表中的结点不是新生成的，而是从原链表中依次“删除”，再逐个头插入到逆置表中（类同算法2.5头查法创建链表）。设逆置链表的初态为空表，“删除”已知链表中的第一个结点，然后将它“插入”到逆置链表的“表头”，即使它成为逆置链表中“新”的第一个结点，如此循环，直至原链表为空表止。l根据单链表的特点，通过头指针L我们可以顺着每个结点的next域，依次访问到a1,a2,a3an-1,an；2）我们可以借鉴前面讲到过的头插入法建链表的方法，因为头插入法建链表又称为逆序建表法3）唯一不同
56、的是，我们不需要重新申请结点空间，而只需要从原有单链表上依次“摘下”结点，之后插入到单链表头结点和表中第一个结点之间即可。如图所示9/17/2024102a1an a2ai(a)初 始 状态Lp为原链表当前处理结点断开L-next, 使逆置表初始为空表 (b)将单链表L初始为空表a1an a2aiLpqq指向原链表当前处理结点的下一个paia2a1 Lan a3q(c)将p指向的结点插入到逆置表L的表头9/17/2024103例例2【算法实现算法实现】voidReverseList(LinkListL)/*逆置带头结点的单链表L*/p=L-next;/*P为原链表的当前处理结点*/L-next
57、=NULL;/*逆置单链表初始为空表*/while(p!=NULL)/*当原链表未处理完*/q=p-next;/*q指针保留原链表当前处理结点的下一个结点*/p-next=L-next;L-next=p;/*将当前处理结点p插入到逆置表L的表头*/p=q;/*p指向下一个待插入的结点*/*endofwhile*/*endofReverstList*/【思考思考】已知一个带头结点的单链表L，设计算法实现：以表中第一个元素作为标准，将单链表中所有值小于第一个元素的结点均放在第一个元素结点之前，所有值大于第一个元素的结点均放在第一个元素结点之后。（提示：此题可以利用头插法）9/17/2024104典
58、型题例典型题例3l例3、建立一个带头结点的线性链表，用以存放输入的二进制数，链表中每个结点的data域存放一个二进制位。并在此链表上实现对二进制数加1的运算。l l【问题分析问题分析问题分析问题分析】建链表建链表：带二进制数可用带头结点的单链表存储，第一个结点存储二进制数的最高位，依次存储，最后一个结点存储二进制数的最低位。二进制加法规则二进制加法规则：实现二进制数加1运算，方向从低位往高位找到第一个值为0的位，从该位开始，对后面所有低位进行求反运算。链表实现二进制加1时，从高位往低位与运算方向正好相反，从第一个结点开始找，找出最后一个值域为0的结点，把该结点值域赋为1，其后所有结点的值域赋为
59、0。若在链表中未找到值域为0的结点，则表示该二进制数各位均为1，此时，申请一新结点，值域为1，插入到头结点与原链表的第一个结点之间，成为新链表的第一个结点，其后所有结点的值域赋为0。9/17/2024105【算法描述算法描述】voidBinAdd(LinkListl)/*用带头结点的单链表L存储二进制数，实现加1运算*/Node*q,*r,*temp,*s;q=l-next;r=l;while(q!=NULL)/*查找最后一个值域为0的结点*/if(q-data=0)r=q;q=q-next;9/17/2024106【算法描述算法描述】续续if(r!=l)r-data=1;/*将最后一个值域为0的结点的值域赋为1*/else/*未找到值域为0的结点*/temp=r-next;s=(Node*)malloc(sizeof(Node);/*申请新结点*/s-data=1;/*值域赋为1*/s-next=temp;r-next=s;/*插入到头结点之后*/r=s;r=r-next;while(r!=NULL)/*将后面的所有结点的值域赋为0*/r-data=0;r=r-next;/*BinAdd结束*/9/17/2024107
