数据结构课程chap02线性表.ppt

《数据结构课程chap02线性表.ppt》由会员分享，可在线阅读，更多相关《数据结构课程chap02线性表.ppt（127页珍藏版）》请在三一办公上搜索。

1、第二章线性表,线性结构的基本特征为:,1集合中必存在唯一的一个“第一元素”；,2集合中必存在唯一的一个“最后元素”；,3除最后元素在外，均有 唯一的后继；,4除第一元素之外，均有 唯一的前驱。,线性结构 是 一类数据元素的有序（次序）集,线性表是一种最简单的线性结构,表头元素,表尾元素,2.1 线性表的类型定义,2.3 线性表类型的实现 链式映象,2.4 一元多项式的表示,2.2 线性表类型的实现 顺序映象,2.1线性表的类型定义,抽象数据类型线性表的定义如下：,ADT List,数据对象：,D ai|ai ElemSet,i=1,2,.,n,n0 称 n 为线性表的表长;称 n=0 时的线性

2、表为空表。,数据关系：,R1|ai-1,aiD,i=2,.,n,设线性表为(a1，a2,.，ai，.，an),称 i 为 ai 在线性表中的位序。,基本操作：,结构初始化操作,结构销毁操作,引用型操作,加工型操作,ADT List,InitList(&L),操作结果：,构造一个空的线性表L。,初始化操作,结构销毁操作,DestroyList(&L),初始条件：操作结果：,线性表 L 已存在。,销毁线性表 L。,ListEmpty(L),ListLength(L),PriorElem(L,cur_e,&pre_e),NextElem(L,cur_e,&next_e),GetElem(L,i,&e

3、),LocateElem(L,e,compare(),ListTraverse(L,visit(),引用型操作:,ListEmpty(L),初始条件：操作结果：,线性表L已存在。,若L为空表，则返回TRUE，否则FALSE。,（线性表判空）,ListLength(L),初始条件：操作结果：,线性表L已存在。,返回L中元素个数。,（求线性表的长度）,PriorElem(L,cur_e,&pre_e),初始条件：操作结果：,线性表L已存在。,若cur_e是L的元素，但不是第一个，则用pre_e 返回它的前驱，否则操作失败，pre_e无定义。,（求数据元素的前驱）,NextElem(L,cur_e,

4、&next_e),初始条件：操作结果：,线性表L已存在。,若cur_e是L的元素，但不是最后一个，则用next_e返回它的后继，否则操作失败，next_e无定义。,（求数据元素的后继）,GetElem(L,i,&e),初始条件：操作结果：,线性表L已存在，且 1iLengthList(L)。,用 e 返回L中第 i 个元素的值。,（求线性表中某个数据元素）,LocateElem(L,e,compare(),初始条件：操作结果：,线性表L已存在，e为给定值，compare()是元素判定函数。,返回L中第1个与e满足关系compare()的元素的位序。若这样的元素不存在，则返回值为0。,（定位函数

5、）,LocateElem(L,e,compare(),（定位函数）,ListTraverse(L,visit(),初始条件：操作结果：,线性表L已存在，Visit()为某个访问函数。,依次对L的每个元素调用函数visit()。一旦visit()失败，则操作失败。,（遍历线性表）,加工型操作,ClearList(&L),PutElem(&L,i,&e),ListInsert(&L,i,e),ListDelete(&L,i,&e),ClearList(&L),初始条件：操作结果：,线性表L已存在。,将L重置为空表。,（线性表置空）,PutElem(&L,i,&e),初始条件：操作结果：,线性表L已

6、存在，且 1iLengthList(L)。,L中第i个元素赋值同e的值。,（改变数据元素的值）,ListInsert(&L,i,e),初始条件：操作结果：,线性表L已存在，且 1iLengthList(L)+1。,在L的第i个元素之前插入新的元素e，L的长度增1。,（插入数据元素）,ListDelete(&L,i,&e),初始条件：操作结果：,线性表L已存在且非空，1iLengthList(L)。,删除L的第i个元素，并用e返回其值，L的长度减1。,（删除数据元素）,利用上述定义的线性表 可以实现其它更复杂的操作,例 2-2,例 2-3,例 2-1,假设:有两个集合 A 和 B 分别用两个线性

7、表 LA 和 LB 表示，即：线性表中的数据元素即为集合中的成员。现要求一个新的集合AAB。,例 2-1,要求对线性表作如下操作：扩大线性表 LA，将存在于线性表LB 中而不存在于线性表 LA 中的数据元素插入到线性表 LA 中去。,上述问题可演绎为：,1从线性表LB中依次察看每个数据元素;,2依值在线性表LA中进行查访;,3若不存在，则插入之。,GetElem(LB,i)e,LocateElem(LA,e,equal(),ListInsert(LA,n+1,e),操作步骤：,GetElem(Lb,i,e);/取Lb中第i个数据元素赋给e if(!LocateElem(La,e,equal()

8、ListInsert(La,+La_len,e);/La中不存在和 e 相同的数据元素，则插入之,void union(List,for(i=1;i=Lb_len;i+),/union,已知一个非纯集合 B，试构造一个纯集合 A，使 A中只包含 B 中所有值各不相 同的数据元素。,仍选用线性表表示集合。,例 2-2,从集合 B 取出物件放入集合 A要求集合A中同样物件不能有两件以上,因此，算法的策略应该和例2-1相同,void union(List/union,GetElem(Lb,i,e);/取Lb中第 i 个数据元素赋给 e if(!LocateElem(La,e,equal()ListI

9、nsert(La,+La_len,e);/La中不存在和 e 相同的数据元素，则插入之,for(i=1;i=Lb_len;i+),InitList(La);/构造(空的)线性表LA,若线性表中的数据元素相互之间可以比较，并且数据元素在线性表中依值非递减或非递增有序排列，即 aiai-1 或 aiai-1(i=2,3,n)，则称该线性表为有序表(Ordered List)。,试改变结构，以有序表表示集合。,例如：（2，3，3，5，6，6，6，8，12）,对集合 B 而言，值相同的数据元素必定相邻；,对集合 A 而言，数据元素依值从小至大的顺序插入。,因此，数据结构改变了，解决问题的策略也相应要改

10、变。,void purge(List i+)/purge,GetElem(Lb,i,e);/取Lb中第i个数据元素赋给 eif(ListEmpty(La)|!equal(en,e)ListInsert(La,+La_len,e);en=e;/La中不存在和 e 相同的数据元素，则插入之,/La 和 Lb 均非空，i=j=1,k=0 GetElem(La,i,ai);GetElem(Lb,j,bj);if(ai=bj)/将 ai 插入到 Lc 中 ListInsert(Lc,+k,ai);+i;else/将 bj 插入到 Lc 中 ListInsert(Lc,+k,bj);+j;,void Me

11、rgeList(List La,List Lb,List&Lc)/本算法将非递减的有序表 La 和 Lb 归并为 Lc/merge_list,while(i=La_len)&(j=Lb_len)/La 和 Lb 均不空 while(i=La_len)/若 La 不空while(j=Lb_len)/若 Lb 不空,InitList(Lc);/构造空的线性表 Lci=j=1;k=0;La_len=ListLength(La);Lb_len=ListLength(Lb);,while(i=La_len)/当La不空时 GetElem(La,i+,ai);ListInsert(Lc,+k,ai);/插

12、入 La 表中剩余元素,while(j=Lb_len)/当Lb不空时 GetElem(Lb,j+,bj);ListInsert(Lc,+k,bj);/插入 Lb 表中剩余元素,2.2 线性表类型的实现-顺序映象,最简单的一种顺序映象方法是：令 y 的存储位置和 x 的存储位置相邻。,顺序映象,以 x 的存储位置和 y 的存储位置之间某种关系表示逻辑关系。,用一组地址连续的存储单元 依次存放线性表中的数据元素,a1 a2 ai-1 ai an,线性表的起始地址称作线性表的基地址,以“存储位置相邻”表示有序对 即：LOC(ai)=LOC(ai-1)+C 一个数据元素所占存储量,所有数据元素的存储位

13、置均取决于 第一个数据元素的存储位置 LOC(ai)=LOC(a1)+(i-1)C 基地址,顺序映像的 C 语言描述,typedef struct SqList;/俗称 顺序表,#define LIST_INIT_SIZE 80/线性表存储空间的初始分配量#define LISTINCREMENT 10/线性表存储空间的分配增量,ElemType*elem;/存储空间基址,int length;/当前长度,int listsize;/当前分配的存储容量/(以sizeof(ElemType)为单位),线性表的基本操作在顺序表中的实现,InitList(&L)/结构初始化,LocateElem(L

14、,e,compare()/查找,ListInsert(&L,i,e)/插入元素,ListDelete(&L,i)/删除元素,Status InitList_Sq(SqList&L)/构造一个空的线性表/InitList_Sq,算法时间复杂度：,O(1),L.elem=(ElemType*)malloc(LIST_ INIT_SIZEsizeof(ElemType);if(!L.elem)exit(OVERFLOW);,L.length=0;L.listsize=LIST_INIT_SIZEreturn OK;,例如：顺序表,e=,38,i,1,2,3,4,1,8,50,可见，基本操作是：将顺序

15、表中的元素逐个和给定值 e 相比较。,int LocateElem_Sq(SqList L,ElemType e,Status(*compare)(ElemType,ElemType)/在顺序表中查询第一个满足判定条件的数据元素，/若存在，则返回它的位序，否则返回 0/LocateElem_Sq,O(ListLength(L),算法的时间复杂度为：,i=1;/i 的初值为第 1 元素的位序p=L.elem;/p 的初值为第 1 元素的存储位置,while(i=L.length,if(i=L.length)return i;else return 0;,(*compare)(*p+,e),线性表

16、操作 ListInsert(&L,i,e)的实现：,首先分析:,插入元素时，线性表的逻辑结构发生什么变化？,(a1,ai-1,ai,an)改变为(a1,ai-1,e,ai,an),Status ListInsert_Sq(SqList&L,int i,ElemType e)/在顺序表L的第 i 个元素之前插入新的元素e,/i 的合法范围为 1iL.length+1/ListInsert_Sq,算法时间复杂度为:,O(ListLength(L),q=,元素右移,考虑移动元素的平均情况:,假设在第 i 个元素之前插入的概率为，则在长度为n 的线性表中插入一个元素所需移动元素次数的期望值为：,若假定

17、在线性表中任何一个位置上进行插入的概率都是相等的，则移动元素的期望值为：,if(L.length=L.listsize)/当前存储空间已满，增加分配 newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType);if(!newbase)exit(OVERFLOW);/存储分配失败 L.elem=newbase;/新基址 L.listsize+=LISTINCREMENT;/增加存储容量,if(i L.length+1)return ERROR;/插入位置不合法,例如：ListInsert_Sq(L,5

18、,66),L.length-1,0,87,56,42,66,q=,线性表操作 ListDelete(&L,i,&e)的实现：,首先分析：,删除元素时，线性表的逻辑结构发生什么变化？,(a1,ai-1,ai,ai+1,an)改变为(a1,ai-1,ai+1,an),ai+1,an,表的长度减少,Status ListDelete_Sq(SqList&L,int i,ElemType&e)/ListDelete_Sq,for(+p;p=q;+p)*(p-1)=*p;/被删除元素之后的元素左移-L.length;/表长减1return OK;,算法时间复杂度为:,O(ListLength(L),p=

19、/表尾元素的位置,if(i L.length)return ERROR;/删除位置不合法,元素左移,考虑移动元素的平均情况:,假设删除第 i 个元素的概率为,则在长度为n 的线性表中删除一个元素所需移动元素次数的期望值为：,若假定在线性表中任何一个位置上进行删除的概率都是相等的，则移动元素的期望值为：,L.length-1,0,87,56,p=,例如：ListDelete_Sq(L,5,e),2.3 线性表类型的实现-链式映象,一、单链表,二、结点和单链表的 C 语言描述,三、线性表的操作在单链表中的实现,四、一个带头结点的单链表类型,五、其它形式的链表,六、有序表类型,用一组地址任意的存储单

20、元存放线性表中的数据元素。,一、单链表,以元素(数据元素的映象)+指针(指示后继元素存储位置)=结点(表示数据元素 或 数据元素的映象),以“结点的序列”表示线性表 称作链表,以线性表中第一个数据元素 的存储地址作为线性表的地址，称作线性表的头指针。,头结点,头指针,头指针,有时为了操作方便，在第一个结点之前虚加一个“头结点”，以指向头结点的指针为链表的头指针。,空指针,线性表为空表时，头结点的指针域为空,Typedef struct LNode ElemType data;/数据域 struct Lnode*next;/指针域 LNode,*LinkList;,二、结点和单链表的 C 语言描

21、述,LinkList L；/L 为单链表的头指针,三、单链表操作的实现,GetElem(L,i,e)/取第i个数据元素,ListInsert(&L,i,e)/插入数据元素,ListDelete(&L,i,e)/删除数据元素,ClearList(&L)/重置线性表为空表,CreateList(&L,n)/生成含 n 个数据元素的链表,线性表的操作 GetElem(L,i,&e)在单链表中的实现:,j,1,2,3,因此，查找第 i 个数据元素的基本操作为：移动指针，比较 j 和 i。,单链表是一种顺序存取的结构，为找第 i 个数据元素，必须先找到第 i-1 个数据元素。,令指针 p 始终指向线性表

22、中第 j 个数据元素。,Status GetElem_L(LinkList L,int i,ElemType&e)/L是带头结点的链表的头指针，以 e 返回第 i 个元素/GetElem_L,算法时间复杂度为:,O(ListLength(L),p=L-next;j=1;/p指向第一个结点，j为计数器,while(p/顺指针向后查找，直到 p 指向第 i 个元素/或 p 为空,if(!p|ji)return ERROR;/第 i 个元素不存在e=p-data;/取得第 i 个元素return OK;,线性表的操作 ListInsert(&L,i,e)在单链表中的实现：,有序对 改变为 和,因此，

23、在单链表中第 i 个结点之前进行插入的基本操作为:找到线性表中第i-1个结点，然后修改其指向后继的指针。,可见，在链表中插入结点只需要修改指针。但同时，若要在第 i 个结点之前插入元素，修改的是第 i-1 个结点的指针。,Status ListInsert_L(LinkList L,int i,ElemType e)/L 为带头结点的单链表的头指针，本算法/在链表中第i 个结点之前插入新的元素 e/LinstInsert_L,算法的时间复杂度为:,O(ListLength(L),p=L;j=0;while(p/i 大于表长或者小于1,s=(LinkList)malloc(sizeof(LNod

24、e);/生成新结点s-data=e;s-next=p-next;p-next=s;/插入return OK;,s,p,线性表的操作ListDelete(&L,i,&e)在链表中的实现:,有序对 和 改变为,在单链表中删除第 i 个结点的基本操作为:找到线性表中第i-1个结点，修改其指向后继的指针。,q=p-next;p-next=q-next;e=q-data;free(q);,p,q,Status ListDelete_L(LinkList L,int i,ElemType&e)/删除以 L 为头指针(带头结点)的单链表中第 i 个结点/ListDelete_L,算法的时间复杂度为:,O(L

25、istLength(L),p=L;j=0;while(p-next/删除位置不合理,q=p-next;p-next=q-next;/删除并释放结点e=q-data;free(q);return OK;,操作 ClearList(&L)在链表中的实现:,void ClearList(/ClearList,free(p);,算法时间复杂度：,O(ListLength(L),如何从线性表得到单链表？,链表是一个动态的结构，它不需要予分配空间，因此生成链表的过程是一个结点“逐个插入”的过程。,例如：逆位序输入 n 个数据元素的值，建立带头结点的单链表。,操作步骤：,一、建立一个“空表”；,二、输入数据

26、元素an，建立结点并插入；,三、输入数据元素an-1，建立结点并插入；,an,an,an-1,四、依次类推，直至输入a1为止。,void CreateList_L(LinkList&L,int n)/逆序输入 n 个数据元素，建立带头结点的单链表/CreateList_L,算法的时间复杂度为:,O(Listlength(L),L=(LinkList)malloc(sizeof(LNode);L-next=NULL;/先建立一个带头结点的单链表,for(i=n;i 0;-i)p=(LinkList)malloc(sizeof(LNode);scanf(/插入,回顾 2.1 节中三个例子的算法，看

27、一下当线性表分别以顺序存储结构和链表存储结构实现时，它们的时间复杂度为多少？,void union(List/for/union,控制结构：基本操作：,for 循环GetElem,LocateElem 和 ListInsert,当以顺序映像实现抽象数据类型线性表时为:O(ListLength(La)ListLength(Lb),当以链式映像实现抽象数据类型线性表时为:O(ListLength(La)ListLength(Lb),例2-1,算法时间复杂度,void purge(List/for/purge,控制结构：基本操作：,for 循环GetElem 和 ListInsert,当以顺序映像实

28、现抽象数据类型线性表时为:O(ListLength(Lb),当以链式映像实现抽象数据类型线性表时为:O(ListLength2(Lb),例2-2,算法时间复杂度,void MergeList(List La,List Lb,List,控制结构：基本操作：,三个并列的while循环GetElem,ListInsert,当以顺序映像实现抽象数据类型线性表时为:O(ListLength(La)+ListLength(Lb),当以链式映像实现抽象数据类型线性表时为:O(ListLength 2(La)+ListLength 2(Lb),例2-3,算法时间复杂度,用上述定义的单链表实现线性表的操作时，存

29、在的问题：,改进链表的设置：,1单链表的表长是一个隐含的值；,1增加“表长”、“表尾指针”和“当前位置的 指针”三个数据域；,2在单链表的最后一个元素之后插入元素时，需遍历整个链表；,3在链表中，元素的“位序”概念淡化，结点的“位置”概念加强。,2将基本操作中的“位序 i”改变为“指针 p”。,四、一个带头结点的线性链表类型,typedef struct LNode/结点类型 ElemType data;struct LNode*next;*Link,*Position;,Status MakeNode(Link/分配由 p 指向的值为e的结点，并返回OK，/若分配失败，则返回 ERROR,v

30、oid FreeNode(Link/释放 p 所指结点,typedef struct/链表类型 Link head,tail;/分别指向头结点和/最后一个结点的指针 int len;/指示链表长度 Link current;/指向当前被访问的结点/的指针，初始位置指向头结点 LinkList;,链表的基本操作:,结构初始化和销毁结构,Status InitList(LinkList/构造一个空的线性链表 L，其头指针、/尾指针和当前指针均指向头结点，/表长为零。,Status DestroyList(LinkList/销毁线性链表 L，L不再存在。,O(1),O(n),引用型操作,Status

31、 ListEmpty(LinkList L);/判表空,int ListLength(LinkList L);/求表长,Status Prior(LinkList L);/改变当前指针指向其前驱,Status Next(LinkList L);/改变当前指针指向其后继,ElemType GetCurElem(LinkList L);/返回当前指针所指数据元素,O(1),O(1),O(n),O(1),O(1),Status LocatePos(LinkList L,int i);/改变当前指针指向第i个结点,Status LocateElem(LinkList L,ElemType e,Stat

32、us(*compare)(ElemType,ElemType);/若存在与e 满足函数compare()判定关系的元/素，则移动当前指针指向第1个满足条件的/元素的前驱，并返回OK;否则返回ERROR,Status ListTraverse(LinkList L,Status(*visit)();/依次对L的每个元素调用函数visit(),O(n),O(n),O(n),加工型操作,Status ClearList(LinkList/重置 L 为空表,Status SetCurElem(LinkList/更新当前指针所指数据元素,Status Append(LinkList/在表尾结点之后链接一

33、串结点,Status InsAfter(LinkList/将元素 e 插入在当前指针之后,Status DelAfter(LinkList/删除当前指针之后的结点,O(1),O(n),O(s),O(1),O(1),Status InsAfter(LinkList/否则返回ERROR。/InsAfter,if(!L.current)return ERROR;if(!MakeNode(s,e)return ERROR;s-next=L.current-next;L.current-next=s;if(L.tail=L.current)L.tail=s;L.current=s;return OK;,

34、Status DelAfter(LinkList 否则返回ERROR。/DelAfter,if(!(L.current,Status MergeList_L(LinkList&Lc,LinkList&La,LinkList&Lb，int(*compare)(ElemType,ElemType)/归并有序表 La 和 Lb,生成新的有序表 Lc,/并在归并之后销毁La 和 Lb,/compare 为指定的元素大小判定函数/MergeList_L,例二,if(!InitList(Lc)return ERROR;/存储空间分配失败,while(!(a=MAXC&b=MAXC)/La 或 Lb 非空,

35、LocatePos(La,0);LocatePos(Lb,0);/当前指针指向头结点,if(DelAfter(La,e)a=e;/取得 La 表中第一个元素 aelse a=MAXC;/MAXC为常量最大值if(DelAfter(Lb,e)b=e;/取得 Lb 表中第一个元素 belse b=MAXC;/a 和 b 为两表中当前比较元素,DestroyList(La);DestroyList(Lb);/销毁链表 La 和 Lbreturn OK;,if(*compare)(a,b)=0)/ab InsAfter(Lc,a);if(DelAfter(La,e1)a=e1;else a=MAXC;

36、,else/ab InsAfter(Lc,b);if(DelAfter(Lb,e1)b=e1;else b=MAXC;,1.双向链表,五、其它形式的链表,typedef struct DuLNode ElemType data;/数据域 struct DuLNode*prior;/指向前驱的指针域 struct DuLNode*next;/指向后继的指针域 DuLNode,*DuLinkList;,最后一个结点的指针域的指针又指回第一个结点的链表,a1 a2.an,2.循环链表,和单链表的差别仅在于，判别链表中最后一个结点的条件不再是“后继是否为空”，而是“后继是否为头结点”。,双向循环链表,

37、空表,非空表,a1 a2.an,双向链表的操作特点：,“查询”和单链表相同。,“插入”和“删除”时需要同时修改两个方向上的指针。,s-next=p-next;p-next=s;s-next-prior=s;s-prior=p;,p,s,插入,删除,p-next=p-next-next;p-next-prior=p;,p,六、有序表类型,ADT Ordered_List 数据对象:S=xi|xi OrderedSet，i=1,2,n,n0,集合中任意两个元素之间均可以进行比较,数据关系:R=|xi-1,xi S,xi-1 xi,i=2,3,n,回顾例2-2的两个算法,LocateElem(L,e

38、,&q,int(*compare)(ElemType,ElemType)初始条件：有序表L已存在。操作结果：若有序表L中存在元素e，则 q指示L中第一个值为 e 的元素的位置，并返回函数值TRUE；否则 q 指示第一个大于 e 的元素的前驱的位置，并返回函数值FALSE。,基本操作：,Compare是一个有序判定函数,(12,23,34,45,56,67,78,89,98,45),例如:,若 e=45,则 q 指向,若 e=88,则 q 指向,表示值为 88 的元素应插入在该指针所指结点之后。,void union(List/La中不存在和 e 相同的数据元素，则插入之/union,算法时间复

39、杂度：O(n2),void purge(List i+)/purge,GetElem(Lb,i,e);/取Lb中第i个数据元素赋给 eif(ListEmpty(La)|!equal(en,e)ListInsert(La,+La_len,e);en=e;/La中不存在和 e 相同的数据元素，则插入之,算法时间复杂度：O(n),2.4 一元多项式的表示,在计算机中，可以用一个线性表来表示:P=(p0,p1,，pn),一元多项式,但是对于形如 S(x)=1+3x10000 2x20000的多项式，上述表示方法是否合适？,一般情况下的一元稀疏多项式可写成 Pn(x)=p1xe1+p2xe2+pmxem

40、其中：pi 是指数为ei 的项的非零系数，0 e1 e2 em=n,可以下列线性表表示：（p1,e1）,(p2,e2),(pm,em)）,P999(x)=7x3-2x12-8x999,例如:,可用线性表(7,3),(-2,12),(-8,999)表示,ADT Polynomial 数据对象：数据关系：,抽象数据类型一元多项式的定义如下：,D ai|ai TermSet,i=1,2,.,m,m0 TermSet 中的每个元素包含一个 表示系数的实数和表示指数的整数,R1|ai-1,aiD,i=2,.,n 且ai-1中的指数值ai中的指数值,CreatPolyn(&P,m)DestroyPolyn

41、(&P)PrintPolyn(&P),基本操作：,操作结果：输入 m 项的系数和指数，建立一元多项式 P。,初始条件：一元多项式 P 已存在。操作结果：销毁一元多项式 P。,初始条件：一元多项式 P 已存在。操作结果：打印输出一元多项式 P。,PolynLength(P)AddPolyn(&Pa,&Pb)SubtractPolyn(&Pa,&Pb)ADT Polynomial,初始条件：一元多项式 P 已存在。操作结果：返回一元多项式 P 中的项数。,初始条件：一元多项式 Pa 和 Pb 已存在。操作结果：完成多项式相加运算，即：Pa=PaPb，并销毁一元多项式 Pb。,一元多项式的实现：,t

42、ypedef struct/项的表示 float coef;/系数 int expn;/指数 term,ElemType;,typedef OrderedLinkList polynomial;/用带表头结点的有序链表表示多项式,结点的数据元素类型定义为:,Status CreatPolyn(polynomail&P,int m)/输入m项的系数和指数，建立表示一元多项式的有序链表P/CreatPolyn,InitList(P);e.coef=0.0;e.expn=-1;SetCurElem(h,e);/设置头结点的数据元素,for(i=1;i=m;+i)/依次输入 m 个非零项return

43、OK;,scanf(e.coef,e.expn);if(!LocateElem(P,e,(*cmp)()if(!InsAfter(P,e)return ERROR;,注意:1.输入次序不限;2.指数相同的项只能输入一次。,Status AddPolyn(polynomial while(!(a=MAXE&b=MAXE)/AddPolyn,switch(*cmp(e1,e2)case-1:/多项式PA中当前结点的指数值小 break;case 0:/两者的指数值相等 e1.coef=a.coef+b.coef;if(a.coef!=0.0)InsAfter(Pc,e1);break;case 1

44、:/多项式PB中当前结点的指数值小 break;,本章小结,1.了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。用前者表示的线性表简称为顺序表，用后者表示的线性表简称为链表。,2.熟练掌握这两类存储结构的描述方法，以及线性表的各种基本操作的实现。,3.能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。,已知单链表A长度为m，单链表B长度为n，若将B联接在A的末尾，其时间复杂度应为()。AO(1)BO(m)CO(n)DO(m+n)链表不具有的特点是（）。A可随机访问任一元素B插入删除不需要移

45、动元素C不必事先估计存储空间D所需空间与线性表长度成正比,练习,练习,在需要经常查找结点的前驱与后继的场合中，使用()比较合适。A单链表 B双链表C顺序表 D循环链表在一个单链表HL中，若要删除由指针q所指向结点的后继结点，则执行（）。Ap=q-next;p-next=q-next;Bp=q-next;q-next=p;Cp=q-next;q-next=p-next;Dq-next=q-next-next;q-next=q;,练习,若要在单链表中的结点p之后插入一个结点s，则应执行的语句是()。As-next=p-next;p-next=s;Bp-next=s;s-next=p-next;Cp

46、-next=s-next;s-next=p;Ds-next=p;p-next=s-next;,练习,在()运算中，使用顺序表比链表好。A插入 B删除 C根据序号查找 D根据元素值查找带头结点的单链表head为空的判断条件是()。Ahead=NULL Bhead-next=NULL Chead-next=head Dhead!=NULL,练习,在单链表、双链表和单循环链表中，若仅知道指针P指向某结点，不知道头指针，能否将结点P从相应的链表中删去?若可以，其时间复杂度各为多少?,练习,函数功能：对以带头结点的单链表作为存储结构的两个递增有序表（表中不存在值相同的数据元素）进行如下操作：将所有在Lb

47、表中存在而La表中不存在的结点插入到La中，其中La和Lb分别为两个链表的头指针。要求：请在空缺处填入合适内容，使其成为一个完整的算法。,voidunion(LinkListLa,LinkListLb)/本算法的功能是将所有Lb表中存在而La表中不存在的结点插入到La表中LinkListpre=La,q;LinkListpa=La-next;LinkListpb=Lb-next;free(Lb);,while(pa,作业二,设n个人，围坐在一个圆桌周围，现在从第s个人开始报数，数到第m个人，让他出局；然后从出局的下一个人重新开始报数，数到第m个人，再让他出局，如此反复直到所有的人全部出局为止。

48、要解决的Josephus问题是：对于任意给定的n,s和m，求出这n个人的出局序列。使用n=9,s=1,m=5，以及n=9,s=1,m=0，或者n=9,s=1,m=10作为输入数据，检查程序的正确性和健壮性，分析所完成算法的时间复杂度。使用链表完成。,作业二（续）,设n个人，围坐在一个圆桌周围，现在从第s个人开始报数，数到第m个人，让他出局；然后反转方向，从出局的下一个人重新开始报数，数到第m个人，再让他出局，再反转方向，如此反复直到所有的人全部出局为止。要解决的Josephus问题是：对于任意给定的n,s和m，求出这n个人的出局序列。使用n=9,s=1,m=5，以及n=9,s=1,m=0，或者n=9,s=1,m=10作为输入数据，检查程序的正确性和健壮性，分析所完成算法的时间复杂度。使用双链表完成。,