第2章 线性表.ppt

1、2020/9/6,1,数据结构课件,西北大学计算机系,本演示文稿可能包含观众讨论和即席反应。使用 PowerPoint 可以跟踪演示时的即席反应， 在幻灯片放映中，右键单击鼠标 请选择“会议记录” 选择“即席反应”选项卡 必要时输入即席反应 单击“确定”撤消此框 此动作将自动在演示文稿末尾创建一张即席反应幻灯片，包括您的观点。,2020/9/6,2,第2章 线性表,2.1 线性表的概念及运算 2.2 线性表的顺序存储 2.3 线性表的链式存储 2.4 一元多项式的表示及相加,2020/9/6,3,2.1 线性表的概念及运算,2.1.1 线性表的逻辑结构 2.1.2 线性表的抽象数据类型定义,2

2、020/9/6,4,线性表的定义,线性表(Linear List)是由n (n0)个类型相同的 数据元素a1,a2,，an组成的有限序列，记做 （a1,a2,，ai-1，ai，ai+1， ，an）。 数据元素之间是一对一的关系，即每个数据元素 最多有一个直接前驱和一个直接后继。 线性表的逻辑结构图为：,2020/9/6,5,线性表的特点,同一性：线性表由同类数据元素组成，每一个ai必须属于同一数据对象。 有穷性：线性表由有限个数据元素组成，表长度就是表中数据元素的个数。 有序性：线性表中相邻数据元素之间存在着序偶关系。,2020/9/6,6,2.1.2 线性表的抽象数据类型定义,抽象数据类型定

3、义 ： ADT LinearList 数据元素：D=ai| aiD0, i=1,2,，n n0 ，D0为某一数据对象 关系： | ai, ai+1D0，i=1,2, ,n-1 基本操作： （1）InitList（L） 操作前提：L为未初始化线性表。 操作结果：将L初始化为空表。 （2）DestroyList(L) 操作前提：线性表L已存在。 操作结果：将L销毁。 （3）ClearList(L) 操作前提：线性表L已存在 。 操作结果：将表L置为空表。 ADT LinearList,2020/9/6,7,2.2 线性表的顺序存储,2.2.1 线性表的顺序存储结构 2.2.2 线性表顺序存储结构上

4、的基本运算,2020/9/6,8,顺序存储结构的定义,线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素，使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系。采用顺序存储结构的线性表通常称为顺序表。 假设线性表中每个元素占k个单元，第一个元素的地址为loc(a1)，则第k个元素的地址为： loc(ai) =loc(a1)+(i-1)k,2020/9/6,9,顺序存储结构示意图,2020/9/6,10,顺序存储结构的C语言定义,#definemaxsize=线性表可能达到的最大长度； typed

5、ef struct ElemType elemmaxsize； /* 线性表占用的数组空间*/ int last； /*记录线性表中最后一个元素在数组elem 中的位置（下标值），空表置为-1*/ SeqList； 注意区分元素的序号和数组的下标，如a1的序号为1，而其对应的数组下标为0。,2020/9/6,11,2.2.2 线性表顺序存储结构的基本运算,线性表的基本运算： 查找操作 插入操作 删除操作 顺序表合并算法 线性表顺序存储结构的优缺点分析,2020/9/6,12,查找操作,线性表的两种基本查找运算 按序号查找GetData(L,i)：要求查找线性表L中第i个数据元素，其结果是L.e

6、lemi-1或L-elemi-1。 按内容查找Locate（L,e）: 要求查找线性表L中与给定值e相等的数据元素，其结果是：若在表L中找到与e相等的元素，则返回该元素在表中的序号；若找不到，则返回一个“空序号”，如-1。 线性表的查找运算算法描述为：,2020/9/6,13,线性表的查找运算,int Locate(SeqList L，ElemType e) i=0 ; /*i为扫描计数器，初值为0，即从第一个元素开始比较*/ while (i=L.last) /*若没找到，则返回空序号*/ ,2020/9/6,14,插入操作,线性表的插入运算是指在表的第i (1in+1)个位置，插入一个新元

7、素e，使长度为n的线性表 (e1，ei-1，ei，en) 变成长度为n+1的线性表（e1，,ei-1，e，ei，en）。 线性表的插入运算算法。,2020/9/6,15,插入算法示意图,已知：线性表 (4,9,15,28,30,30,42,51,62)，需在第4个元素之前插入一个元素“21”。则需要将第9个位置到第4个位置的元素依次后移一个位置，然后将“21”插入到第4个位置，,2020/9/6,16,插入运算,int InsList(SeqList *L,int i,ElemType e) int k; if( (iL-last+2) ) /*首先判断插入位置是否合法*/ printf(“插

8、入位置i值不合法”)；return(ERROR); if(L-last=maxsize-1) printf(“表已满无法插入”)； return(ERROR); for(k=L-last;k=i-1;k-) /*为插入元素而移动位置*/ L-elemk+1=L-elemk; L-elemi-1=e; /*在C语言中数组第i个元素的下标为i-1*/ L-last+; return(OK); ,2020/9/6,17,插入运算算法分析,当i=L-last+2时，语句L-elemk+1=L-elemk将不会执行，因为循环的终值大于初值，此时不需要移动元素， 可直接在表尾插入e。 当i=1时，语句L-

9、elemk+1=L-elemk需执行n次，即将表中已存在的n个元素依次后移一个位置才能将e插入。 结论：语句L-elemk+1=L-elemk的频度与插入位置i有关。 设Pi为在第i个元素之前插入元素的概率，并假设在任何位置上插入的概率相等，即Pi=1/(n+1), i=1, 2, ，n+1。设Eins为在长度为n的表中插入一元素所需移动元素的平均次数， 则：,2020/9/6,18,删除操作,线性表的删除运算是指将表的第i(1in)个元素删去，使长度为n的线性表 (e1，,ei-1，ei，ei+1，en)，变成长度为n-1的线性表(e1，,ei-1， ei+1，en)。 算法思路示意 算法实

10、现,2020/9/6,19,删除算法示意,将线性表(4,9,15,21,28,30,30,42,51,62)中的第5个元素删除。,2020/9/6,20,删除算法,int DelList(SeqList *L,int i,ElemType *e) /*在顺序表L中删除第i个数据元素，并用指针参数e返回其值*/ int k; if(iL-last+1) printf(“删除位置不合法！”)； return(ERROR)； *e= L-elemi-1; /* 将删除的元素存放到e所指向的变量中*/ for(k=i;ilast;k+) L-elemk-1= L-elemk; /*将后面的元素依次前移

11、*/ L-last-; return(OK); ,2020/9/6,21,删除运算算法分析,在顺序表上实现删除运算必须移动结点，才能反映出结点间的逻辑关系的变化。 若i=L-last+1，则移位语句L-elemk-1=L-elemk不执行，因为循环变量的初值大于终值，此时不需要移动元素，仅将表长度减1即可。 删除算法中移位语句L-elemk-1=L-elemk的执行频度与删除位置i有关。 设Qi为删除第i个元素的概率，并假设在任何位置上删除的概率相等，即Qi=1/n, i=1, 2, ，n。删除一个元素所需移动元素的平均次数Edel为： 在顺序表中插入或删除一个数据元素时，其时间主要耗费在移动

12、数据元素上。,2020/9/6,22,合并算法,已知：有两个顺序表LA和LB，其元素均为非递减有序排列，编写一个算法，将它们合并成一个顺序表LC，要求LC也是非递减有序排列。 算法思想 ：设表LC是一个空表，为使LC也是非递减有序排列，可设两个指针i、j分别指向表LA和LB中的元素，若LA.elemiLB.elemj，则当前先将LB.elemj插入到表LC中，若LA.elemiLB.elemj ，当前先将LA.elemi插入到表LC中，如此进行下去，直到其中一个表被扫描完毕，然后再将未扫描完的表中剩余的所有元素放到表LC中。 算法实现 此处连接算法演示,2020/9/6,23,顺序表合并算法实

13、现,void merge(SeqList *LA, SeqList *LB, SeqList *LC) i=0;j=0;k=0; while(ilast ,2020/9/6,24,顺序存储结构的优点和缺点,优点： 1.无需为表示结点间的逻辑关系而增加额外的存储空间； 2.可方便地随机存取表中的任一元素。 缺点： 1.插入或删除运算不方便，除表尾的位置外，在表的其它 位置上进行插入或删除操作都必须移动大量的结点，其 效率较低； 2.由于顺序表要求占用连续的存储空间，存储分配只能预 先进行静态分配。因此当表长变化较大时，难以确定合 适的存储规模。,2020/9/6,25,2.3 线性表的链式存储,

14、链表定义： 采用链式存储结构的线性表称为链表 。 现在我们从两个角度来讨论链表： 1.从实现角度看，链表可分为动态链表和静态链表； 2.从链接方式的角度看，链表可分为单链表、循环链表和双链表。,2020/9/6,26,2.3.1 单链表 2.3.2 单链表上的基本运算 2.3.3 循环链表 2.3.4 双向链表 *2.3.5 静态链表 2.3.6 顺序表和链表的比较,链表,2020/9/6,27,2.3.1 单链表,结点（Node）为了正确地表示结点间的逻辑关系，必须在存储线性表的每个数据元素值的同时，存储指示其后继结点的地址（或位置）信息，这两部分信息组成的存储映象叫做结点（Node）。 单

15、链表：链表中的每个结点只有一个指针域，我们将这种链表称为单链表。 单链表包括两个域：数据域用来存储结点的值；指针域用来存储数据元素的直接后继的地址（或位置）。 头指针 ：指向链表头结点的指针。,2020/9/6,28,单链表的结点结构,2020/9/6,29,单链表的示例图,2020/9/6,30,带头结点的单链表示意图,有时为了操作的方便，还可以在单链表的第一个 结点之前附设一个头结点。 带头结点的空单链表 带头结点的单链表,2020/9/6,31,单链表的存储结构描述,typedef struct Node /*结点类型定义*/ ElemType data； struct Node * n

16、ext； Node, *LinkList；/*LinkList为结构指针类型*/,2020/9/6,32,2.3.2 单链表上的基本运算,线性表的基本运算： 建立单链表 单链表查找 单链表插入操作 单链表删除 算法应用示例： 求单链表的长度 求两个集合的差,2020/9/6,33,建立单链表,头插法建表 算法描述：从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头结点之后，直至读入结束标志为止。,2020/9/6,34,建立单链表,2020/9/6,35,头插法建表算法,Linklist CreateFromHead() LinkLis

17、t 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; elseflag=0; ,2020/9/6,36,尾插法建表,2020/9/6,37,尾插法建表算法,Linklist Cr

18、eateFromTail() /*将新增的字符追加到链表的末尾*/ LinkList L; Node *r, *s; int flag =1; L=(Node * )malloc(sizeof(Node);/*为头结点分配存储空间*/ 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

19、; r-next=NULL; ,2020/9/6,38,单链表查找,按序号查找 算法描述：设带头结点的单链表的长度为n，要查找表中第i个结点，则需要从单链表的头指针L出发，从头结点（L-next）开始顺着链域扫描，用指针p指向当前扫描到的结点,初值指向头结点（p=L-next），用j做记数器，累计当前扫描过的结点数（初值为0），当j = i 时，指针p所指的结点就是要找的第i个结点 。算法实现，算法演示。,2020/9/6,39,按序号查找算法实现,Node * Get(LinkList L, int i) /*在带头结点的单链表L中查找第i个结点，若找到(1in)，则返回该结点的存储位置;否

20、则返回NULL*/ Node *p； if(in) return NULL; p=L；j=0； /*从头结点开始扫描*/ while (p-next!=NULL) p=L-next; /*从表中第一个结点比较*/ while (p!=NULL) if (p-data!=key) p=p-next; else break; /*找到结点key，退出循环*/ return p; ,2020/9/6,42,算法描述： 要在带头结点的单链表L中第i个数据元素之前插入一个数据元素e，需要首先在单链表中找到第i-1个结点并由指针pre指示，然后申请一个新的结点并由指针s指示，其数据域的值为e，并修改第i-

21、1个结点的指针使其指向s，然后使s结点的指针域指向第i个结点。,单链表插入操作,2020/9/6,43,单链表插入操作,2020/9/6,44,单链表插入操作算法实现,void InsList(LinkList L,int i,ElemType e) /*在带头结点的单链表L中第i个结点之前插入值为e的新结点。*/ Node *pre,*s; pre=L; int k=0; while(pre!=NULL ,2020/9/6,45,单链表删除,算法描述： 欲在带头结点的单链表L中删除第i个结点，则首先要通过计数方式找到第i-1个结点并使p指向第i-1个结点，而后删除第i个结点并释放结点空间。,

22、2020/9/6,46,单链表删除,2020/9/6,47,单链表删除算法实现,void DelList(LinkList L,int i,ElemType *e) /*在带头结点的单链表L中删除第i个元素，并保存其值到变量*e中*/ Node *p,*r; p=L; int k =0; while(p-next!=NULL /*释放被删除的结点所占的内存空间*/ ,2020/9/6,48,求单链表的长度,算法描述：可以采用“数”结点的方法来求出单链表的长度，用指针p依次指向各个结点,从第一个元素开始“数”，一直“数”到最后一个结点（p-next=NULL）。 intListLength(Li

23、nkList L) /*L为带头结点的单链表*/ Node *p; p=L-next; j=0; /*用来存放单链表的长度*/ while(p!=NULL) p=p-next; j+; return j; ,2020/9/6,49,两个有序单链表的合并,有两个单链表LA和LB，其元素均为非递减有序排列，编写一个算法，将它们合并成一个单链表LC，要求LC也是非递减有序排列。要求：利用新表LC利用现有的表LA和LB中的元素结点空间，而不需要额外申请结点空间。例如LA=(2, 2, 3), LB=(1, 3, 3, 4), 则LC=(1, 2, 2, 3, 3, 3, 4)。 【算法描述】要求利用现

24、有的表LA和LB中的结点空间来建立新表LC,可通过更改结点的next域来重建新的元素之间的线性关系，为保证新表仍然非递减有序，可以利用尾插入法建立单链表的方法，只是新建表中的结点不用malloc，而只需要从表LA和LB中选择合适的点插入到新表LC中即可。,2020/9/6,50,两个有序单链表的合并的算法实现,LinkList MergeLinkList(LinkList LA, LinkList LB) /*将递增有序的单链表LA和LB合并成一个递增有序的单链表LC*/ Node *pa,*pb; LinkList LC； /*将LC初始置空表。pa和pb分别指向两个单链表LA和LB中的第一

25、个结点,r初值为LC*/ pa=LA-next; pb=LB-next; LC=LA; LC-next=NULL；r=LC;/*初始化操作*/,2020/9/6,51,两个有序单链表的合并的算法实现（续）,/*当两个表中均未处理完时，比较选择将较小值结点插入到新表LC中。*/ while(pa!=NULL /* MergeLinkList */,2020/9/6,52,2.3.3 循环链表,循环链表(Circular Linked List) 是一个首尾相接的链表。 特点：将单链表最后一个结点的指针域由NULL改为指向头结点或线性表中的第一个结点，就得到了单链形式的循环链表，并称为循环单链表。

26、在循环单链表中，表中所有结点被链在一个环上。 带头结点循环单链表示意图。,2020/9/6,53,带头结点的循环单链表示意图,空链表,带头结点的一般形式,带尾结点的一般形式,2020/9/6,54,循环单链表合并为一个循环单链表,已知：有两个带头结点的循环单链表LA、LB，编写一个算法，将两个循环单链表合并为一个循环单链表，其头指针为LA。 算法思想：先找到两个链表的尾，并分别由指针p、q指向它们，然后将第一个链表的尾与第二个表的第一个结点链接起来，并修改第二个表的尾Q，使它的链域指向第一个表的头结点。,2020/9/6,55,循环单链表合并算法实现(1),LinkList merge_1(L

27、inkList 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的表尾*/ q-next=LA; /*修改表LB的尾指针，使之指向表LA的头结点*/ p-next=LB-next; /*修改表LA的尾指针，使之指向表LB中的第一个结点*/ free(LB); return(LA); ,2020/9/6,56,循环单链表合并算法实现(2),采用上面的方法，需要遍历链表，

28、找到表尾，其执行时间是O(n)。 若在尾指针表示的单循环链表上实现，则只需要修改指针，无需遍历，其执行时间是 O(1)。,2020/9/6,57,循环单链表合并算法实现(2),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的头结点链到链表R

29、B的终端结点之后 */ return RB; /* 返回新循环链表的尾指针 */ ,2020/9/6,58,2.3.4 双向链表,双向链表：在单链表的每个结点里再增加一个指向其前趋的 指针域prior。这样形成的链表中就有两条方向不同的链，我 们称之为双 ( 向) 链表 (Double Linked List)。 双向链表的结构定义： typedef struct Dnode ElemType data； struct DNode *prior，*next； DNode,* DoubleList；,2020/9/6,59,双链表的结构定义,双链表的结点结构,2020/9/6,60,双向循环链表

30、示意图,2020/9/6,61,双向链表的前插操作,算法描述：欲在双向链表第i个结点之前插入一个的新的结点，则指针的变化情况如图所示。,2020/9/6,62,双向链表的前插操作算法实现,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; p-prior-next=s; s-next=p; p-prior=s; retur

31、n TRUE; else return FALSE; 算法演示连接。,2020/9/6,63,双向链表的删除操作,算法描述：欲删除双向链表中的第i个结点，则指针的变化情况如图所示。,a,b,c,p,2020/9/6,64,双向链表的删除操作算法实现,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; ,202

32、0/9/6,65,*2.3.5 静态链表,基本概念： 游标实现链表的方法：定义一个较大的结构数组作为备用结点空间（即存储池）。当申请结点时，每个结点应含有两个域：data域和next域。data域存放结点的数据信息，next域为游标指示器，指示后继结点在结构数组中的相对位置（即数组下标）。数组的第0个分量可以设计成表的头结点，头结点的next域指示了表中第一个结点的位置，为0表示静态单链表的结束。我们把这种用游标指示器实现的单链表叫做静态单链表(Static Linked List)。静态链表的结构定义，静态链表的插入和删除操作示例。 基本操作： 初始化、分配结点与结点回收、前插操作、删除。,

33、2020/9/6,66,静态链表的结构定义,#define Maxsize=链表可能达到的最大长度 typedef struct ElemType data; int cursor; Component, StaticListMaxsize;,2020/9/6,67,静态链表的插入和删除操作示例,已知：线性表 a，b，c，d，f，g，h，i），Maxsize=11,2020/9/6,68,静态链表初始化,算法描述：初始化操作是指将这个静态单链表初始化为一个 备用静态单链表。设space为静态单链表的名字，av为备用 单链表的头指针，其算法如下： void initial(StaticList

34、space,int *av) int k; space0-cursor=0; /*设置静态单链表的头指针指向位置0*/ for(k=0;kcursor=k+1; /*连链*/ spaceMaxsize-1 . cursor =0; /*标记链尾*/ *av=1; /*设置备用链表头指针初值*/ ,2020/9/6,69,静态链表分配结点与结点回收,分配结点 int getnode(int *av) /*从备用链表摘下一个结点空间，分配给待插入静态链表中的元素*/ int i=*av; *av=space*av.cur; return i; 结点回收 void freenode(int *av,

35、int k) /*将下标为 k的空闲结点插入到备用链表*/ spacek.cursor=*av;*av=k; ,2020/9/6,70,2.4 一元多项式的表示及相加,一元多项式可按升幂的形式写成： Pn(x) = p0+p1xe1+p2xe2+pnxen， 其中ei为第i项的指数，pi是指数ei的项的系数，(且1e1e2en) 假设Qm(x)是一个一元多项式，则它也可以用一个线性表Q来表示。即： Qm= (q0，q1，q2， ，qm ) 若假设mn，则两个多项式相加的结果Rn(x)= Pn(x) + Qm(x)，也可以用线性表R来表示： R=(p0+q0，p1+ q1，p2+ q2，pm+

36、qm，pm+1，pn),2020/9/6,71,一元多项式的存储,一元多项式的顺序存储表示 一元多项式的链式存储表示,2020/9/6,72,一元多项式的顺序存储表示1,一元多项式Pn(x)的顺序表示有两种。 法1:只存储该一元多项式各项的系数，每个系数所对应的指数项则隐含在存储系数的顺序表的下标中。即p0存系数p0，对应为x0的系数，p1存系数p1，对应为x1的系数，pn存系数pn，对应为xn的系数。采用这种存储方法使得多项式的相加运算的算法定义十分简单，只需将下标相同的单元的内容相加即可。适合于存储表示非零系数多的多项式。,2020/9/6,73,一元多项式的顺序存储表示2,图2.19 一

37、元多项式只存非零项存储示意图,法2：采用只存储非零项的方法，此时每个非零项需要存储：非零项系数和非零项指数。适合存储表示非零项少的多项式。,2020/9/6,74,一元多项式的链式存储表示,在链式存储中，对一元多项式只存非零项，则该多项式中每一非零项由两部分构成（指数项和系数项），用单链表存储表示的结点结构为： 用单链表存储多项式的结点结构如下： struct Polynode int coef; int exp; Polynode *next; Polynode , * Polylist;,2020/9/6,75,建立一元多项式链式存储的算法,【算法思想】通过键盘输入一组多项式的系数和指数，

38、用尾插法建立一元多项式的链表。以输入系数0为结束标志，并约定建立多项式链表时，总是按指数从小到大的顺序排列。,2020/9/6,76,建立一元多项式链式存储的算法,Polylist polycreate() Polynode *head, *rear, *s; int c,e; rear=head=(Polynode *)malloc(sizeof(Polynode); /*建立多项式的头结点， rear 始终指向单链表的尾*/ scanf(“%d,%d”, ,2020/9/6,77,一元多项式的单链表表示示意图,说明：图示分别为多项式 A(x)=7+3x+9x8+5x17 B(x)=8x+2

39、2x7-9x8,2020/9/6,78,两个一元多项式相加,运算规则：两个多项式中所有指数相同的项的对应系数相加，若和不为零，则构成“和多项式”中的一项；所有指数不相同的项均复抄到“和多项式”中。算法实现，算法演示 若p-expexp，则结点p所指的结点应 是“和多项式”中的一项，令指针p后移； 若p-expq-exp，则结点q所指的结点应是“和多项式”中的一项，将结点q插入在结点p之前，且令指针q在原来的链表上后移； 若p-exp=q-exp，则将两个结点中的系数相加，当和不为零时修改结点p的系数域，释放q结点；若和为零，则和多项式中无此项，从A中删去p结点，同时释放p和q结点。,2020/

40、9/6,79,两个多项式相加算法实现（1）,void polyadd(Polylist polya; Polylist polyb) /*此函数用于将两个多项式相加，然后将和多项式存放在多项式polya 中，并将多项式ployb删除*/ Polynode *p, *q, *tail; *temp; int sum; p=polya-next ; q=polyb-next ; /* 令p和q分别指向polya和polyb多项式链表中的第一个结点 */ tail=polya; /* tail指向和多项式的尾结点 */,2020/9/6,80,while （p! =NULL /* 将q结点加入到和多

41、项式中 */ ,两个多项式相加算法实现（2）,2020/9/6,81,if(p! =NULL) tail-next=p; /*多项式A中还有剩余，则将剩余的结点加入到和多项式中*/ else tail-next=q; /* 否则， 将B中的结点加入到和多项式中 */ ,2020/9/6,82,2.5 顺序表和链表的比较,1基于空间的考虑 2基于时间的考虑 3基于语言的考虑,2020/9/6,83,1.基于空间的考虑,顺序表的存储空间是静态分配的，在程序执行之前必须明确规定它的存储规模。 适合于线性表长度变化不大，且容易估计长度的情况下。 在静态链表中，初始存储池虽然也是静态分配的，但若同时存在

42、若干个结点类型的链表，则它们可以共享空间，使各链表之间能够相互调节余缺，减少溢出机会。 存储密度(Storage Density), 是指结点数据本身所占的存储量和整个结点结构所占的存储量之比， 即：存储密度=结点数据本身所占的存储量/结点结构所占的存储总量。若不考虑顺序表中的备用结点空间， 则顺序表的存储空间利用率为100%，而单链表的存储空间利用率为50% 结论：当线性表的长度变化不大， 易于事先确定其大小时，为了节约存储空间，宜采用顺序表作为存储结构。 ,2020/9/6,84,2.基于时间的考虑,顺序表是由向量实现的，它是一种随机存取结构，对表中任一结点都可以在O(1)时间内直接地存取

43、，而链表中的结点， 需从头指针起顺着链找才能取得。 若线性表的操作主要是进行查找，很少做插入和删除时，宜采用顺序表做存储结构。 在链表中的任何位置上进行插入和删除，都只需要修改指针。而在顺序表中进行插入和删除，平均要移动表中近一半的结点，尤其是当每个结点的信息量较大时，移动结点的时间开销就相当可观。 对于频繁进行插入和删除的线性表，宜采用链表做存储结构。若表的插入和删除主要发生在表的首尾两端，则宜采用尾指针表示的单循环链表。,2020/9/6,85,3.基于语言的考虑,对于没有提供指针类型的高级语言，若要采用链表结构，则可以使用光标实现的静态链表。虽然静态链表在存储分配上有不足之处，但它和动态

44、链表一样，具有插入和删除方便的特点。 使是对那些具有指针类型的语言，静态链表也有其用武之地。特别是当线性表的长度不变，仅需改变结点之间的相对关系时，静态链表比动态链表可能更方便。,2020/9/6,86,线性表链式存储方式的比较,2020/9/6,87,2.6 总结与提高,主要知识点 1、线性表的特征：线性表中每个数据元素有且仅有一个直接前驱和一个直接后继，第一个结点无前驱，最后一个结点无后继。 2、线性表存储方式： 线性表顺序存储（顺序表）：采用静态分配方式，借助于C语言的数组类型，申请一组连续的地址空间，依次存放表中元素，其逻辑次序隐含在存储顺序之中。,2020/9/6,88,2.6 总结

45、与提高,线性表链式存储（链表）：采用动态分配方式，借助于C语言的指针类型，动态申请与动态释放地址空间，故链表中的各结点的物理存储可以是不连续的。当表长度变化时仅需适当变化指针的联接，适合于表中元素个数动态变化。 3、单链表的操作特点： 顺链操作技术 指针保留技术 4、链表处理中的相关技术,2020/9/6,89,典型题例,例1：已知顺序表L中的数据元素类型为int。设计算法将其调整为左右两部分，左边的元素（即排在前面的）均为奇数，右边所有元素（即排在后面的）均为偶数，并要求算法的时间复杂度为O(n)，空间复杂度为O（1）。,2020/9/6,90,例1【问题分析】,法1：额外申请1个顺序表空间

46、，之后依次从顺序表L中选择奇数放入新表前部分，选择偶数放在新表的后半部分。但是题目要求空间复杂度为O(1),很显然不可行。 空间复杂度为O(1)，说明只能借助1个辅助空间。 法2：要将位于表左半部分的偶数与位于表右半部分的奇数通过一个辅助变量进行交换即可，可设置两个位置指示器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)。,2020/9/6,91,【算法描述】,AdjustSqli

47、st(SeqList *L) int i=0,j=L-last; while(ielemi%2!=0) i+; /*从表的左半部分开始检测，若为奇数，则i加1,直到找到偶数为止*/ while(L-elemj%2= =0) j-； /*从表的右半部分开始检测，若为偶数，则j减1,直到找到奇数为止*/ if(ielemi; L-elemi= L-elemj; L-elemj=t; /*交换*/ /*end of AdjustSqlist*/,2020/9/6,92,逆置就是使得表中内容由原来的(a1,a2,ai-1,ai,ai+1, ,an）变为（an,an-1,ai+1,ai，ai-1, ,a1)。就地逆置就是不需要额外申请结点空间，只需要利用原有的表中的节点空间。若对顺序表中的元素进行逆置，可以借助于“交换”前后相应元素；对单链表中的元素进行逆置，则不能按“交换”思路，因为对于链表中第i个结点需要顺链查找第n-i+1(链表长度为n)个结点，逆置链表的时间复杂度将达O(n2)。,例2：算法实现带头结点单链表的就地逆置问题。,2020/9/6,93,算法思路：逆置后