数据结构第二章线性表课件.ppt

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

1、,1数据的逻辑结构,2、数据的存储结构,A线性结构,B非线性结构,A 顺序存储,B 链式存储,线性表,栈,队列,树,图,数据结构,(物理结构),数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。,逻辑结构：结构定义中的“关系”描述的是数据元素之间的逻辑关系，因此称为数据的逻辑结构。,存储结构：是数据结构在计算机中的表示（又称映像）。,前一章复习,线性结构的特点；线性表的相关概念；线性表上定义的基本运算和用基本运算构造出的较复杂的运算。,掌握顺序存储结构和链式存储结构的描述方法，以及各种基本操作的实现。,能够从时间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。,使用本章

2、所学的基本知识设计有效算法解决与线性表相关的应用问题。,本章知识点,2.1 线性表的类型定义,本章目录,2.2 线性表的顺序表示和实现,2.3 线性表的链式表示和实现,第2章 线性表,本节总结,2.4 一元多项式的表示及相加,线性结构的特点：在数据元素的非空有限集中，(1)存在唯一的一个被称为第一个的数据元素；(2)存在唯一的一个被称为最后一个的数据元素；(3)除第一个之外，集合中的每个数据元素均只有一个前驱；(4)除最后一个之外，集合中每个数据元素均只有一个后继。,第2章 线性表,线性表是一种最常用最简单的线性结构。,2.1 线性表的类型定义,线性表是n个数据元素的有限序列。,每个数据元素可

3、以是一个数或一个符号,也可是一页书,甚至更复杂的信息。如,26个英文字母的字母表(A,B,C,Z)是一个线性表,表中的数据元素是单个字母字符。又如,某校从1978年到1983年各种型号的计算机拥有量的变化情况,可用线性表的形式给出(6,17,28,50,92,188)表中的数据元素是整数。,在稍复杂的线性表中,一个数据元素可以由若干个数据项组成。这种情况下，把数据元素称为记录。含有大量记录的线性表称文件。,例如,一个学校的学生健康情况登记表,表中的每个学生的情况为一个记录,它由姓名,学号,性别,年龄,班级和健康状况等6个数据项组成.,图2.1 学生健康状况登记表,由上述例子可以看出，线性表中的

4、数据元素可以是各种各样的。但同一线性表中的元素具有相同特性，即属同一数据对象，相邻数据元素之间存在着序偶关系。,将线性表记为（a1,. ai-1,ai,ai+1.an）， ai+1是ai直接后继元素， ai-1是ai直接前驱元素。当i=1,2,.,n-1时, ai有且仅有一个直接后继，当i=2,3,.,n时, ai有且仅有一个直接前驱。,线性表中的元素个数n(n0)定义为线性表的长度，n=0称为空表。 在非空表中，每个数据元素都有一个确定的位置，如a1是第一个数据元素，an是最后一个数据元素，ai是第i个数据元素，称i为ai在线性表中的位序。,线性表是一个相当灵活的数据结构，长度可以增长或缩短

5、，即对线性表的数据元素不仅可以进行访问，还可以进行插入和删除。,ADT List 数据对象：Dai|aiElemSet,i=1,2,.,n, n0 称n为线性表的长度;称n=0时的线性表为空表。数据关系：R1|ai-1 ,aiD, i=2,.,n 设线性表为 (a1，a2,.，ai，.，an), 称i为ai在线性表中的位序。,抽象数据类型线性表的定义,类型一：结构初始化InitList(&L) 操作结果：构造一个空的线性表L。类型二：结构销毁DestroyList(&L) 初始条件：线性表L已存在。 操作结果：销毁线性表L。类型三：引用型操作ListLength(L) 初始条件：线性表L已存在

6、。 操作结果：返回L中元素个数。,基本操作：,GetElem(L,i,&e) 初始条件：线性表L已存在， 1iListLength(L) 操作结果：用e返回L中第i个元素的值。LocateElem(L,e,compare( ) 初始条件：线性表L已存在，compare( )是元素判 定函数。 操作结果：返回L中第1个与e满足关系compare( )的元素的位序。若这样的元素不存在，则返回值为0。ListEmpty(L) 初始条件：线性表L已存在。 操作结果：若L为空表，则返回TRUE，否则返回FALSE。,PriorElem(L,cur_e,&pre_e) 初始条件：线性表L已存在。 操作结果

7、：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱，否则操作失败，pre_e无定义。NextElem(L,cur_e,&next_e) 初始条件：线性表L已存在。 操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继，否则操作失败， next_e无定义。,类型四：加工型操作ListInsert(&L,i,e) 初始条件：线性表L已存在，1iListLength(L)+1 操作结果：在L的第i个位置之前插入新的元素e，L的长度增1。ListDelete(&L,i,&e) 初始条件：线性表L已存在且非空，1iListLength(L) 操作结果：删

8、除L的第i个元素，并用e返回其值，L的长度减1。ClearList(&L) 初始条件：线性表L已存在。 操作结果：将L重置为空表。,例 2-1 假设:有两个集合 A 和 B 分别用两个线性表 LA 和 LB 表示，即：线性表中的数据元素即为集合中的成员。现要求一个新的集合AAB。,利用上述定义的线性表,可以实现其它更复杂的操作,上述问题可演绎为要求对线性表作如下操作： 扩大线性表 LA，将存在于线性表LB 中而不存在于线性表 LA 中的数据元素插入到线性表 LA 中去。,1从线性表LB中依次取得每个数据元素;,2依值在线性表LA中进行查访;,3若不存在（上述函数返回0），则插入之。,GetEl

9、em(LB, i,e),LocateElem(LA, e, equal（）),ListInsert(LA, +LA_len, e),操作步骤：,GetElem(Lb, i, e); /取Lb中第i个数据元素赋给eif (!LocateElem(La, e, equal( ) ) ListInsert(La, +La_len, e);/ La中不存在和 e 相同的数据元素，则插入之,void union(List / 求线性表的长度,for (i = 1; i = Lb_len; i+) , / union,时间复杂度 O(ListLength(LA)*ListLength(LB),例 2-2

10、已知线性表LA和LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的数据元素仍按值非递减有序排列。,若线性表中的数据元素相互之间可以比较，并且数据元素在线性表中依值非递减或非递增有序排列，即aiai-1或 aiai-1(i = 2,3, n)，则称该线性表为有序表(Ordered List)。,非递减有序线性表举例：LA=（3，5，8，11）；LB（2，6，8，9，11，15，20）LC？,void MergeList(List La, List Lb, List &Lc) / 本算法将非递减的有序表 La 和 Lb 归并为 Lc,while (i = L

11、a_len) ,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); / 插入 La 表中剩余元素,while (j = Lb_len) / 当Lb不空时 GetElem(Lb, j+, bj); ListInsert(Lc, +k, bj); / 插入 Lb 表中剩余元素 / merge_list,时间复杂度o(List

12、Length(LA)+ListLength(LB),线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素。,an,.,ai,.,a2,a1,b,b+L,b+(i-1)*L,b+（n-1)*L,存储地址,内存状态,图 2.2 线性表的顺序存储结构示意图设每个元素需占L个存储单元，以所占的第一个单元的存储地址作为数据元素的存储位置。,2.2 线性表的顺序表示和实现,Loc(ai)=Loc(a1)+（i-1）*L,每个元素所占用的存储单元个数,LOC（a1）是线性表的起始地址或基地址。,线性表中第i+1个数据元素的存储位置Loc（ai+1）和第i个数据元素的存储位置Loc（ai）之

13、间满足下列关系： Loc(ai+1)=Loc(ai)+L 线性表的第i个数据元素ai的存储位置为：,线性表的这种机内表示称作线性表的顺序存储结构或顺序映象，称这种存储结构的线性表为顺序表。 以元素在计算机内的物理位置相邻来表示线性表中数据元素之间的逻辑关系。每个数据元素的存储位置都和线性表的起始位置相差一个和数据元素在线性表中的位序成正比的常数。因此，只要确定了线性表的起始位置，线性表中任一数据元素都可随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。,#define LIST_INIT_SIZE 100 / 线性表存储空间的初始分配量#define LISTINCREMENT 10

14、 / 线性表存储空间的分配增量typedef struct /定义一个SqList这样的类型(结构体类型)ElemType *elem; / 存储空间基址,指示线性表基地址int length; / 当前长度int listsize; / 当前分配的存储容量(以sizeof(ElemType)为单位) SqList;,/-线性表的动态分配顺序存储结构-,线性表的基本操作在顺序表中的实现,InitList_Sq(&L) / 结构初始化,LocateElem_Sq(L, e, compare() / 查找,ListInsert_Sq(&L, i, e) / 插入元素,ListDelete_Sq(&

15、L, i) / 删除元素,Status InitList_Sq( SqList / InitList_Sq,算法1：构造一个空的线性表,算法思想：检查i值是否超出所允许的范围（1in+1），若超出，则进行“超出范围”错误处理；将线性表的第i个元素和它后面的所有元素均向后移动一个位置；将新元素写入到空出的第i个位置上；使线性表的长度增1。,算法2：在线性表中指定位置前插入一个元素,插入元素时，线性表的逻辑结构由(a1, , ai-1, ai, , an)改变为(a1, , ai-1, e, ai, , an),在第i-1个数据元素和第i个数据元素之间插入新的数据元素。,(a1, , ai-1,

16、ai, , an) 改变为 (a1, , ai-1, e, ai, , an), ,表的长度增加,图2.3 线性表插入前后的状况(a)插入前n=8; (b)插入后n=9,插入25,Status ListInsert_Sq(SqList ,在线性表中指定位置前插入一个元素,if (!newbase) exit(OVERFLOW); / 存储分配失败L.elem = newbase; / 新基址L.listsize += LISTINCREMENT; / 增加存储容量q = /ListInsert_Sq,realloc可以对给定的指针所指的空间进行扩大或者缩小，无论是扩大或是缩小，原有内存中的内容

17、将保持不变。当然，对于缩小，则被缩小的那一部分的内容会丢失。 realloc 并不保证调整后的内存空间和原来的内存空间保持同一内存地址。相反，realloc返回的指针很可能指向一个新的地址。所以，在代码中，我们必须将realloc返回的值，重新赋值给p。,例如：ListInsert_Sq(L, 5, 66),L.length-1,0,87,56,42,66,q = ,一般情况下，在第i(1in)个元素之前插入一个元素时，需将第n至第i(共n-i+1个)元素向后移动一个位置。Pi是在第i个数据元素之前插入一个元素的概率。 在长度为n的线性表中插入一个元素时所需移动元素次数的期望值（平均次数）为,

18、插入时移动次数的期望值（平均次数）,算法思想:检查i值是否超出所允许的范围（1in），若超出，则进行“超出范围”错误处理；将线性表的第i个元素后面的所有元素均向前移动一个位置；使线性表的长度减1。,算法3：在线性表中删除第i个元素,删除元素时，线性表的逻辑结构由(a1, , ai-1, ai, ai+1, , an)改变为(a1, , ai-1, ai+1, , an)。,(a1, , ai-1, ai, ai+1, , an) 改变为 (a1, , ai-1, ai+1, , an),ai+1,an, ,表的长度减少,图2.4 线性表删除前后的情况(a)删除前n=8; (b)删除后n=7,删

19、除24,Status ListDelete_Sq(SqList / 删除位置不合法,在顺序线性表L中删除第i个元素,p =/ListDelete_Sq,L.length-1,0,87,56,p = ,例如：ListDelete_Sq(L, 5, e),一般情况下，删除第i(1in)个元素时，需将第i+1至第n(共n-i个)元素依次向前移动一个位置。qi是删除第i个元素的概率。 在长度为n的线性表中删除一个元素时所需移动元素次数的期望值（平均值）为,删除第i个元素的移动次数的期望值（平均值）,例如：顺序表,23 75 41 38 54 62 17,L.length,L.listsize,e =,

20、38,i,1,2,3,4,1,8,50,可见，基本操作是：将顺序表中的元素逐个和给定值 e 相比较。,算法4：在顺序表中查找是否存在和e相同的数据元素,int LocateElem_Sq(SqList L, ElemType e, Status (*compare)(ElemType, ElemType) / 在顺序表中查询第一个满足判定条件的数据元素， / 若存在，则返回它的位序，否则返回 0i = 1; / i 的初值为第 1 元素的位序p = L.elem; / p 的初值为第 1 元素的存储位置while (i = L.length / LocateElem_Sq,算法思想：分别从LA

21、和LB中取得当前元素ai和bj；若aibj，则将ai插入到LC中，否则将bj插入到LC中。,算法5：线性表合并,已知线性表LA和LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，求得线性表LC中的数据元素仍按值非递减有序排列。设 LA=(a1,ai,an)，LB=(b1,bj,bm)。LC=(c1,ck,cm+n),void MergeList_Sq(SqList La,SqList Lb,SqList /存储分配失败,接下页,a_last=La.elem+La.length-1;pb_last=Lb.elem+Lb.length-1;while(pa=pa_la

22、st /插入Lb的剩余元素/MergeList_Sq,作业： 设顺序表va中的数据元素递增有序，试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。顺序表结构的定义遵从教材P22“线性表动态分配存储结构”,2.3 线性表的链式表示和实现,线性表的链式存储结构特点：用一组任意的存储单元(可以是连续的,也可以是不连续的)存放线性表的数据元素。,为了表示每个数据元素与其直接后继之间的逻辑关系，对数据元素ai来说,除了存储其本身的信息之外，还需存储一个指示其直接后继的信息(即直接后继的存储位置)。这两部分信息组成数据元素ai的存储映象，称为结点。它含有两个域：存储数据元素信息的域称为数据域。

23、存储直接后继存储位置的域称为指针域。指针域中存储的信息称作指针或链。,数据域 指针域,结点,2.3.1 线性链表,n个结点链成一个链表，即为线性表（a1,a2,an）的链式存储结构。由于链表的每个结点中只包含一个指针域，又称线性链表或单链表。 整个链表的存取需从头指针开始进行，头指针指示链表中第一个结点（即第一个数据元素的存储映象）的存储位置。由于最后一个数据元素没有直接后继，则线性表中最后一个结点的指针为空(NULL)。 指针为数据之间逻辑关系的映像，则逻辑上相邻的两个数据元素其存储的物理位置不要求紧邻，这种存储结构为非顺序映像或链式映像。,typedef struct LNode Elem

24、Type data； struct Lnode *next； LNode，*LinkList；,线性表的单链表存储结构,假设p是指向第i个元素ai的指针，则pnext是指向第i+1个数据元素ai+1的指针。若pdata= ai则 p next data= ai+1,下图为(ZHAO，QIAN，SUN，LI，ZHOU，WU，ZHENG，WANG)线性表的线性链表存储结构，存储从头指针开始进行。,43,13,1,NULL,37,7,19,25,图2.6 线性链表的逻辑状态,图2.5 线性链表示例,头指针,空指针,图2.7 带头结点的单链表,L,(a)非空表,(b)空表,在单链表的第一个结点之前附设

25、一个结点，称之为头结点。头结点的数据域可以不存储任何信息，也可存储如线性表的长度等类的附加信息，头结点的指针域存储指向第一个结点的指针。 单链表的头指针指向头结点。 若线性表为空表，则头结点的指针域为空。,L,单链表操作的实现,GetElem_L(L, i, &e) / 取第i个数据元素,ListInsert_L(&L, i, e) / 插入数据元素,ListDelete_L(&L, i, &e) / 删除数据元素,CreateList_L(&L, n) / 生成含 n 个数据元素的链表,线性表的操作GetElem_L(L, 3, &e)在单链表中的实现:,j,1,2,3,单链表是一种顺序存取

26、的结构，为找第 i 个数据元素，必须先找到第 i-1 个数据元素。因此，查找第 i 个数据元素的基本操作为：移动指针，比较 j 和 i。令指针 p 始终指向线性表中第 j 个数据元素。,Status GetElem_L(LinkList L, int i, ElemType / GetElem_L,算法时间复杂度为:,O(ListLength(L),线性表的操作 ListInsert(&L, i, e) 在单链表中的实现：,有序对 改变为 和,因此，在单链表中第i个结点之前进行插入的基本操作为:找到线性表中第i-1个结点，然后修改其指向后继的指针。,可见，在链表中插入结点只需要修改指针。但同时

27、，若要在第i个结点之前插入元素，修改的是第i-1个结点的指针。,Status ListInsert_L(LinkList L, int i, ElemType e) / L 为带头结点的单链表的头指针，本算法 / 在链表中第i 个结点之前插入新的元素 e p = L; j = 0;while (p / i 大于表长或者小于1,算法的时间复杂度为:,O(ListLength(L), / LinstInsert_L,s = (LinkList) malloc ( sizeof (LNode); /生成新结点s-data = e; s-next = p-next; p-next = s; /插入re

28、turn OK;,s,p,线性表的操作ListDelete_L (&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 / ListDelete_L,算法的时间复杂度为:,O(ListLength(L),如何从线性表得到单链表？,链表是一个动态结构。整个可用存储空间可为多个链表共用，每个链表占用

29、的空间不需预先分配划定，可由系统应需求即时生成。因此生成链表的过程是一个结点“逐个插入”的过程。,例如：逆位序输入 n 个数据元素的值，建立带头结点的单链表。,操作步骤：,一、建立一个“空表”；,二、输入数据元素an，建立结点并插入；,三、输入数据元素an-1，建立结点并插入；,an,an,an-1,四、依次类推，直至输入a1为止。,创建带头结点的单链线性表,void CreateList_L(LinkList / 插入到表头 / CreateList_L,算法的时间复杂度为:,O(Listlength(L),线性表合并,将两个有序链表合并为一个有序链表。 设立三个指针pa、pb和pc分别用来

30、指向两个有序链表和合并表的当前元素。比较两个表的当前元素的大小，将小的元素链接到pc所指结点之后，即，让pc指向该元素，然后，修改指针。 在归并两个链表为一个链表时，不需要另建新表的结点空间，而只需将原来两个链表中结点之间的关系解除，重新建立关系。,Void MergeList_L(LinkList /释放Lb的头结点/MergeList_L,条件赋值 变量名条件表达式？表达式T：表达式F；,if(pa) pc-next = pa; else pc-next = pb;,2,5,3,8,La,Lb,pa,pb,Lc,pc,pa=La-next;pb=Lb-next;Lc=pc=La;,2,5,

31、3,8,La,Lb,pa,pb,Lc,pc,While(pa,2,5,3,8,La,Lb,pa,pb,Lc,pc,While(pa ,2,5,3,8,La,Lb,pb,Lc,pc,While(pa ,pa=null,2,5,3,8,La,Lb,pb,Lc,pc,pc-next=pa?pa:pb; free(Lb);,用上述定义的单链表实现线性表的操作时，存在的问题：,1单链表的表长是一个隐含的值；,2在单链表的最后一个元素之后插入元素时， 需遍历整个链表；,a1 a2 . an,和单链表的差别仅在于，判别链表中最后一个结点的条件不再是“后继是否为空”，而是“后继是否为头结点”。,循环单链表,特

32、点：最后一个结点的指针域指向头结点，整个链表形成一个环。由此，从表中任一结点出发均可找到其它结点。,空表,2.3.2 循环链表,在每个结点中有两个指针域，一个指向直接后继，一个指向直接前驱。,typedef struct DuLNodeElemType data;struct DuLNode *prior;struct DuLNode *next;DuLNode, *DuLinkList;,线性表的双向链表存储结构,2.3.3 双向链表,双向循环链表,空表,非空表,a1 a2 . an,双向链表有循环表，链表中有两个环，在双向链表中，若d为指向表中某一结点的指针（即d为DuLinkList型变

33、量），则显然有d-next-prior=d-prior-next=d,双向链表的操作特点：,“查询”和单链表相同。,“插入”和“删除”时需要同时修改两个方向上的指针。,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,一个带头结点的线性链表类型,typedef struct LNode / 结点类型 ElemType data; struct LNode *next; *Link, *Position;typedef stru

34、ct / 链表类型 Link head, tail; / 分别指向头结点和最后一个结点的指针 int len; / 指示链表长度 LinkList;,Status MakeNode( Link / 分配由p 指向的值为e的结点，并返回OK，若分配失败，则返回 ERROR,void FreeNode( Link / 释放p 所指结点,链表的基本操作:,Status InitList( LinkList / 构造一个空的线性链表L,Status DestroyList( LinkList / 销毁线性链表L，L不再存在。,Status Append(LinkList / 将指针s所指的一串结点链接

35、在线性链表L的最后一个结点,Status InsFirst(Link h,Link s); /h指向头结点，将s所指结点插入在第一个结点之前,Status DelFirst(Link h,Link / h指向头结点，删除第一个结点并以q返回,Status NextPos( LinkList L,Link p ); / p指向一个结点，返回p所指结点的直接后继的位置，若无后继，则返回NULL,Status SetCurElem(Link / p指向一个结点，用e更新p所指结点中数据元素的值,ElemType GetCurElem ( Link p ); / p指向一个结点，返回p所指结点中数据元

36、素的值,Position GetHead(LinkList L);/返回线性链表L中头结点的位置,Status LocatePos( LinkList L, int i ,Link / 返回p指示线性链表L中第i个结点的位置并返回OK，i值不合法时返回ERROR。,Status ListInsert_L(LinkList L, int i, ElemType e) / 在带头结点的单链线性表 L 的第 i 个元素之前插入元素 e / ListInsert_L,利用上述定义的线性链表如何完成线性表的其它操作 ？,if (!LocatePos (L, i-1,h) return ERROR; /

37、i 值不合法。/ LocatePos (L, i-1,h)中h指示第i-1个结点的位置，并返回OK,不合法时返回ERROR。if (!MakeNode(s, e) return ERROR; /结点存储分配失败InsFirst(h,s);/对于从第i个结点开始的链表，第i-1个结点是它的头结点。h指向头结点，s所指结点插入在第一个结点之前return OK;,例1,Status MergeList_L(LinkList /a和b为两表中当前比较元素,例2,接下页,if(*compare)(a,b)=0)/a=bDelFirst(ha,q);Append(Lc,q);/ha是头指针pa=Next

38、Pos(La,pa); /返回pa所指结点直接后继ElseDelFirst(hb,q);Append(Lc,q); /hb是头指针pb=NextPos(Lb,pb);/返回pb所指结点直接后继if(pa)Append(Lc,pa);/链接La中剩余结点else Append(Lc,pb); /链接Lb中剩余结点FreeNode(ha);FreeNode(hb);/释放La和Lb的头结点Return OK;/MergeList_L,在计算机中，可以用一个线性表来表示: P = (p0, p1, ，pn),一元多项式,2.4 一元多项式的表示,但是对于形如 S(x) = 1 + 3x10000 2

39、x20000的多项式，上述表示方法是否合适？,一般情况下的一元n次多项式可写成 Pn(x) = p1xe1 + p2xe2 + + pmxem其中：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,

40、m0 TermSet 中的每个元素包含一个表示系数的实数和表示指数的整数 ,R1 |ai-1 ,aiD, 且ai-1中的指数值ai中的指数值 i=2,.,n,CreatPolyn ( &P, m )DestroyPolyn ( &P ) PrintPolyn ( &P ),基本操作：,操作结果：输入 m 项的系数和指数，建立一元多项式 P。,初始条件：一元多项式 P 已存在。操作结果：销毁一元多项式 P。,初始条件：一元多项式 P 已存在。操作结果：打印输出一元多项式 P。,PolynLength( P ) AddPolyn ( &Pa, &Pb )SubtractPolyn ( &Pa, &

41、Pb ) MultiplyPolyn(&Pa, &Pb ) ADT Polynomial,初始条件：一元多项式 P 已存在。操作结果：返回一元多项式 P 中的项数。,初始条件：一元多项式 Pa 和 Pb 已存在。操作结果：完成多项式相加运算，即： Pa = PaPb，并销毁一元多项式 Pb。,抽象数据类型一元多项式的实现：,typedef struct / 项的表示,多项式的项作为LinkList的数据元素 float coef; / 系数 int expn; / 指数 term, ElemType; /两个类型名：term用于本ADT, ElemType为LinkList的数据对象名,typ

42、edef struct LNode ElemType data； struct Lnode *next； LNode，*LinkList；,线性表的单链表存储结构,typedef LinkList polynomial; / 用带表头结点的有序链表表示多项式,A(x)=7+3x+9x8+5x17,核心算法AddPolyn是把分别由pa和pb所指的两个多项式相加，结果为pa所指的多项式。相加时，首先设两个指针变量qa和qb分别从多项式的首项开始扫描，比较qa和qb所指结点指数域的值，可能出现下列三种情况之一：,（1）qa-exp大于qb-exp,摘取qb指针所指结点插入到“和多项式”链表中去（2

43、）qa-exp小于qb-exp,摘取qa指针所指结点插入到“和多项式”链表中去。,扫描过程一直进行到qa或qb有一个为空为止，然后将有剩余结点的链表接在结果链表上。所得pa指向的链表即为两个多项式之和。,（3）qa-exp等于qb-exp,则将其系数相加。若相加结果不为零，修改qa所指结点的系数值，并释放qb所指结点。否则同时释放qa和qb所指结点。然后qa、qb继续向后扫描。,Void CreatPolyn (polynomail /生成结点并插入 / CreatPolyn,Void AddPolyn(polynomial ,elseDelFirst(ha,qa);FreeNode(qa);

44、DelFirst(hb,qb);FreeNode(qb);qb=NextPos(Pb,hb);qa=NextPos(Pa,ha);break;Case 1:DelFirst(hb,qb);InsFirst(ha,qb);qb=NextPos(Pb,hb);ha=NextPos(Pa,ha);break;/switch/whileif(!ListEmpty(Pb) Append(Pa,qb);FreeNode(hb);,1.了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。用前者表示的线性表简称为顺序表，用后者表示的线性

45、表简称为链表。,2.熟练掌握这两类存储结构的描述方法，以及线性表的各种基本操作的实现。,3. 综合比较线性表两种存储结构的不同特点及其适用场合。,本章总结,线性表链式存储结构的特点：优点：空间合理利用，插入和删除不需要移动。缺点：实现某些操作不如顺序存储结构。线性表顺序存储结构特点：优点：关系上相邻的两个元素在物理位置上也相邻，因此可随机存取表中任一元素，存储位置可用一个简单，直观的公式来表示。缺点：插入或删除操作时，需大量移动元素。分析讨论：（1）在表很长时，采用顺序方式时插入和删除元素的效率很低，只有在很少进行插入和删除运算的情况下，采用顺序表才是合适的。而线性链表的插入和删除运算效率总是

46、很高，与表长无关。（2）对线性表的长度或存储规模难以估计时，不宜采用顺序表 （3）顺序表所占存储空间少，但要求是连续的存储单元；线性链表因为有指针域，所占存储空间大，但可以利用非连续单元。,试描述头指针、头结点、开始结点的区别、并说明头指针和头结点的作用。答：开始结点（首元结点）是指链表中的第一个结点，也就是没有直接前趋的那个结点。 链表的头指针是一指向链表开始结点的指针(没有头结点时)，单链表由头指针唯一确定，因此单链表可以用头指针的名字来命名。 头结点是我们人为地在链表的开始结点之前附加的一个结点。有了头结点之后，头指针指向头结点。不论链表是否为空，头指针总是非空。而且头指针的设置使得对链

47、表的第一个位置上的操作与在表其他位置上的操作一致(都是在某一结点之后)。,习题,已知单链表H，写一算法将其倒置。即实现如图的操作。(a)为倒置前，(b)为倒置后。,图 单链表的倒置,(a),(b),p,q,void reverse (Linklist H) LNode *p; p=H-next; /p指向第一个结点 H-next=NULL; /将原链表置为空表H while (p) q=p; p=p-next;/q始终指向当前插入结点，p指向下一插入结点 q-next=H-next; /将当前结点插到头结点的后面 H-next=q; ,该算法只是对链表中顺序扫描一边即完成了倒置，所以时间复杂度

48、为O(n)。,算法思路：依次取原链表中的每个结点，将其作为第一个结点插入到新链表中去，指针p用来指向当前结点，p为空时结束。算法如下：,线性表的链接存储，表中元素的逻辑顺序与物理顺序一定相同。（ ）,向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（ ）个元素。（A）64（B）63 （C）63.5（D）7,线性表是具有n个（ ）的有限序列（n0) （A）表元素 （B）字符 （C）数据元素 （D）数据项,B,错误,C,C,一个线性表第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址是( ) （A）110 （B）108（C）100 （D）120,已知P为单链表中的非首尾结点，在P结点后插入S结点的语句为：( ) 。顺序表中逻辑上相邻的元素物理位置( )相邻， 单链表中逻辑上相邻的元素物理位置( )相邻。线性表L（a1，a2，.，an）采用顺序存储，假定在不同的n1个位置上插入的概率相同，则插入一个新元素平均需要移动的元素个数是( ),S-next=P-next;P-next=S;,不一定,n/2,一定,本节结束,