第2章线性表.ppt

从第2章至第4章将讨论线性结构。线性结构的特点是：在数据元素的非空有限集中， (1)存在唯一的一个被称做“第一个”的数据元素； (2)存在唯一的一个被称做“最后一个”的数据元素； (3)除第一个之外，集合中的每个数据元素均只有一个前驱； (4)除最后一个之外，集合中每个数据元素均只有一个后继。 2.1 线性表的类型定义 2.2 线性表的顺序表示和实现2.3 线性表的链式表示和实现 2.4 一元多项式的表示及相加2.1 线性表的类型定义(1学时） 线性表(Linear_List)是最常用且最简单的一种数据结构。简言之，一个线性表是n个数据元素的有限序列。至于每个数据元素的具体含义，在不同的情况下各不相同，它可以是一个数、或一个符号，也可以是一页书，甚至其它更复杂的信息。 例如，26个英文字母的字母表： (A，B，C，Z) 是一个线性表，表中的数据元素是单个字母字符。又如，某校从1978年到1983年各种型号的计算机拥有量的变化情况，可以用线性表的形式给出： (6，17，28，50，92，188) 表中的数据元素是整数。 在稍复杂的线性表中，一个数据元素可以由若干个数据数据项项(Item)组成。在这种情况下，常把数据元素称为记录记录(Record)，含有大量记录的线性表又称文件文件(File)。 例如，一个学校的学生健康情况登记表如图21所示，表中每个学生的情况为一个记录，它由姓名、学号、性别、年龄、班级和健康状况等六个数据项组成。 图21 学生健康情况登记表 姓 名 学 号 性 别 年 龄 班 级健康状况王小林790631 男 18 计98 健康陈 红790631 女 20 计98 一般刘键平790633 男 21 计98 健康张立立790634 男 17 计98神经衰弱 综合上述三个例子可见，线性表中的数据元素可以是各种各样的，但同一线性表中的元素必定具有相同特性，即属同一数据对象，相邻数据元素之间存在着序偶关系。若将线性表记为 (a1, , ai-1, ai, ai+1, , an) (21) 线性表中元素的个数n(n0)定义为线性表的长度，n=0时称为空表。在非空表中的每个数据元素都有一个确定的位置，如a1是第一个数据元素。an是最后一个数据元素， ai是第i个数据元素，称i为数据元素ai在线性表中的位序。 线性表是一个相当灵活的数据结构，它的长度可根据需要增长或缩短，即对线性表的数据元素不仅可以进行访问，还可进行插入和删除等。 抽象数据类型线性表的定义如下： ADT List 数据对象：D=ai | ai ElemSet, i = 1,2,3,n, n0 数据关系：R1= | ai-1 ,ai D, i = 2,n 基本操作： InitList(&L) 操作结果：构造一个空的线性表L。 DestroyList(&L) 初始条件：线性表L已存在。 操作结果：销毁线性表。 ClearList(L) 初始条件：线性表L已存在。 操作结果：将L重置为空表。 ListEmpty(L) 初始条件：线性表L已存在。 操作结果：若L为空表，则返回TRUE， 否则返回FALSE。 ListLength(L) 初始条件：线性表L已存在。 操作结果：返回L中数据元素个数。 GetElem(L，i，&e) 初始条件：线性表L已存在，1iListLength(L)。 操作结果：用e返回L中第i数据个元素的值。 LocateElem(L，e，compare( ) 初始条件：线性表L已存在， compare( )是数据元素判定函数。 操作结果：返回L中第1个与e满足关系compare( ) 的数据元素的位序。不存在，则返回 值为0。 PriorElem(L， cur_e， &pre_e) 初始条件：线性表L已存在。 操作结果：若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已存在且非空， 1i ListLength(L)。 操作结果：删除L的第i个数据元素，并用e返回 其值，L的长度减1。 ListTraverse(L，visit( ) 初始条件：线性表L已存在。 操作结果：依次对L的每个数据元素调用函数 visit( )。ADT List 例21 假设利用两个线性表LA和LB分别表示两个集合A和B(即：线性表中的数据元素即为集合中的成员)，现要求一个新的集合A=AUB。 vold union ( List &La，List Lb) /将所有在线性表Lb中但不在La中的数据元素插入到La中 La_len=ListLength (La)； Lb_len=ListLength (Lb)； for ( i = 1；i=Lb_len；i+) GetElem (Lb，i，e)； / / La中不存在和e相同的数据元素，则插入 if(!LocateElem (La ， e ， equal) ListInsert (La， +La_len， e)； /union 算法 2.1 例2-2 已知线性表LA和LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的数据元素仍按值非递减有序排列。例如，设 LA=(3，5，8，11) LB=(2，6，8，9，11，15，20) 则 LC=(2，3，5，6，8，8，9，11，11，15，20) void MergeList (List La，List Lb，List & Lc) /已知线性表La和Lb中的数据元素按值非递减排列。归并La /和Lb得到新的线性表Lc，Lc的数据元素也按值非递减排列。 InitList(Lc)； i = j = 1；k = 0； La_len=ListLength(La)；Lb_len=ListLehgth(Lb)； while(i=La_len)&(j=Lb_len) GetElem(La，i，&ai)； GetElem(Lb，j，&bj)； if (ai = bj) Listlnsert(Lc, +k, ai )；+i； else Listlnsert (Lc, +k, bj)； +j； while(i=La_len) GetElem(La，i+，ai)； Listlnsert(Lc，+k，ai )； while(j=Lb_len) GetElem(Lb，j+，bj)； Listlnsert(Lc，+k，bj)； 算法 2.2 上述两个算法的时间复杂度分析： 假如GetElem和ListInsert这两个操作的执行时间和表长无关，LocateElem的执行时间和表长成正比，则 算法2.1的时间复杂度为 O(ListLength(LA)*ListLength(LB)， 算法 2.2的时间复杂度则 O(ListLength(LA)+ListLength(LB)。 虽然算法2.2中含三个 (while)循环语句，但只有当i和j均指向表中实际存在的数据元素时，才能取得数据元素的值并进行相互比较；并且当其中一个线性表的数据元素均已插入到线性表LC中后，只要将另外一个线性表中的剩余元素依次插入即可。因此，对于每一组具体的输入(LA和 LB)，后两个(while)循环语句只执行一个循环体。2.2 线性表的顺序表示和实现(1学时) 线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素。 假设线性表的每个元素需占用L个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。则线性表中第i+1个数据元素的存储位置LOC(ai+1)和第i个数据元素的存储位置LOC(ai)之间满足下列关系： LOC(ai+1)=LOC(ai)+L 一般来说，线性表的第i个数据元素ai的存储位置为 LOC(ai) = LOC(a1)+(i-1) * L 式中LOC(a1)是线性表的第一个数据元素a1的存储位置，通常称做线性表的起始位置或基地址。 线性表的这种机内表示称做线性表的顺序存储结构或顺序映象(Sequential Mapping)，反之，称这种存储结构的线性表为顺序表。 它的特点是，为表中相邻的元素ai和ai+1赋以相邻的存储位置LOC(ai)和LOC(ai+1)。换句话说，以元素在计算机内“物理位置相邻”来表示线性表中数据元素之间的逻辑关系。 (见图2.2)。由此，只要确定了存储线性表的起始位置，线性表中任一数据元素都可随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。 存储地址 内存状态 数据元素在线 性表中的位序 b 1 b+l 2 . . . . . . b+(i-1)*L i . . . . . . b+(n-1)*L na1a2 . . . ai . . .an 由于高级程序设计语言中的数组类型也有随机存取的特性，因此，通常都用数组来描述数据结构中的顺序存储结构。在此，由于线性表的长度可变，且所需最存储空间随问题不同而不同，则在C语言中可用动态分配的一维数组，如下描述。 / 线性表的动态分配顺序存储结构 #define LIST_INIT_SIZE 100 /线性表存储空间的初始分配量 #define LISTINCREMENT 10 /线性表存储空间的分配增量 typedef struct ElemType * elem ; /存储空间基址 int length; /当前长度 int listsize; /当前分配的存储容量(以sizeof(ElemType)为单位) SqList；Status InitList_Sq (SqList &L) /构造一个空的线性表L。 L.elem = (ElemType * )malloc(LIST_INIT_SIZE*sizeof(E1emType) if(!L.elem)exit(OVERFLOW)； /存储分配失败 L.length = 0； /空表长度为0 L.listsize = LIST_INIT_SIZE； /初始存储容量 return OK； / InitList_Sq 算法 23 在这种存储结构中，容易实现线性表的某些操作，如随机存取第i个数据元素等。只是要特别注意的是，C语言中数组的下标从“0”开始，因此，若L是SqList类型的顺序表，则表中第i个数据元素是L.Elemi-1。下面重点讨论线性表的插入和删除两种操作在顺序存储表示时的实现方法。 序号 数据 序号 数据 元素 元素 1 1 2 2 3 3插入 4 4 25 5 5 6 6 7 7 8 8 9 9 （a) (b) 图2.3 线性表插入前后的状况 （a)插入前 n=8; (b)插入后 n=9; 例如，图2.3表示一个线性表在进行插入操作的前、后，其数据元素在存储空间中的位置变化。为了在线性表的第4和第5个元素之间插入一个值为25的数据元素，则需将第5个至第8个数据元素依次往后移动一个位置。 一般情况下，在第i(1in)个元素之前插入一个元素时，需将第n至第i(共n-i+1)个元素向后移动一个位置，如算法2.4所示。 12 13 21 24 28 30 42 77121321242528304277Status ListInsert_Sq (SqList &L，int i，ElemType e) / 在顺序线性表L中第i个位置之前插入新的元素e， / i的合法值为1iListLength_Sq(L)+1 if( iL.length+1) return ERROR； /i值不合法 if(L.length =L.listsize) /当前存储空间已满，增加分配 newbase = (ElemType *)realloc(L.elem， (L.1istsize+LISTINCREMENT)*sizeof(ElemType) if(!newbase)exit(OVERFLOW)； /存储分配失败 L.elem = newbase； /新基址 L.listsize+ =LISTINCREMENT； /增加存储容量 q = &(L.Elemi-1)； /q为插入位置 for(p = &(L.elemL.length-1)；p= q；-p) *(p+1) = *p; /插入位置及之后的元素右移 *q = e； /插入 e +L.length； /表长增1 return OK； /ListInsert _Sq 算法 2.4 Status ListDelete_Sq( SqList &L，int i，ElemTypee) /在顺序线性表l中删除第i个元素，并用e返回 /其值，i的合法值为 1iListLength_Sq(L) if(iL.length) return ERROR； 反之，线性表的删除操作是使长度为n的线性表变成长度为n-1的线性表。 一般情况下，删除第i (1in)个元素时需将从第i+1至第n(共n-i)个元素依次向前移动一个位置，如算法2.5所示。 p = &(L.elemi-1)； /p为被删除元素的位置 e = *p； /被删除元素的值赋给e q=L.elem+L.1ength-1；/表尾元素的位置 for(+p；pnext； j=1; /初始化，p指向第一个元素结点，j为计数器 while( p & jnext；+j； if(!p | ji) return ERROR； /第i个元素不存在 e = pdata； /取第i个元素 return OK； /GetElem_L 算法 2.8 在单链表中，又如何实现“插入”和“删除”操作呢? 为插入数据元素x，首先要生成一个数据域为x的结点，然后插入在单链表中。根据插入操作的逻辑定义，还需要修改结点 a中的指针域，令其指向结点x，而结点x中的指针域应指向结点b，从而实现三个元素a， b和x之间逻辑关系的变化。插入后的单链表如图2.8(b)所示。假设s为指向结点x的指针，则上述指针修改用语句描述即为： snext = pnext； pnext = s； xabps(b)插入后。abxps(a)插入前；图2.8 在单链表中插入 结点时指针变化状况 反之，如图2.9所示在线性表中删除元素b时，为在单链表中实现元素a、b和c之间逻辑关系的变化，仅需修改结点a中的指针域即可。假设p为指向结点a的指针，则修改指针的语句为： pnext=pnextnext； 可见，在已知链表中元素插入或删除的确切位置的情况下，在单链表中插入或删除一个结点时，仅需修改指针而不需要移动元素。 图 2.9 在单链表中删除结 点时指针变化状况abcp 算法2.9和算法2.10分别为Listlnsert和ListDelete在单链表中的实现。 Status ListInsert_L (LinkList &L，int i，ElemType e) /在带头结点的单链线性表L中第i个 /位置之前插入元素e p = L； j = 0； while ( p & jnext；+j； /寻找第i-1个结点 if( !p | ji-1) return ERROR；s = ( LinkList ) malloc (sixeof(LNode)； sdata=e； snext=pnext； pnext = s； return OK; /ListInsert_L 算法 2.9Status ListDelete_L( LinkList &L , int i, ElemType e) /在带头结点的单链线性表L中，删 /除第i个元素，并由e返回其值 p = L ；j = 0 ； while (pnext & j next ；+ j； if(!(pnext)| ji-1)return ERROR； /删除位置不合理 q = pnext； pnext=qnext； /删除并释放结点 e =qdata； free(q)； return OK； /ListDelete_L 算法 2.10 单链表和顺序存储结构不同，它是一种动态结构。整个可用存储空间可为多个链表共同享用，每个链表占用的空间不需预先分配划定，而是可以由系统应需求即时生成。因此，建立线性表的链式存储结构的过程就是一个动态生成链表的过程。即从“空表”的初始状态，依次建立各元素结点，并逐个插入链表。 void CreateList_L (LinkList &L，int n) /逆位序输入n个元素的值，建立带表头结点的单链线性表L。 L=(LinkList)malloc(sizeof(LNode)； Lnext = NULL； /先建立一个带头结点的单链表 for( i = n；i0；-i) p=(LinkList)malloc(sizeof(LNode)； scanf( &pdata)； /输入元素值 pnext = Lnext； Lnext=p； /插入至表头 算法2.11（其时间复杂度为O(n)。） 下面讨论如何将两个有序链表并为一个有序链表? 假设头指针为La和Lb的单链表分别为线性表LA和LB的存储结构，现要归并La和Lb得到单链表Lc，按照2.1节中算法MergeList的思想，需设立三个指针pa、pb和pc，其中pa和pb分别指向La表和Lb表中当前待比较插入的结点，而pc指向Lc表中当前最后一个结点，若pa-data pb-data，则将pa所指结点链接到pc所指结点之后，否则将pb所指结点链接到pc所指结点之后。pcLcpaLapbLb void MergeList_L (LinkList &La， LinkList &Lb，LinkList &Lc) /已知单链线性表La和Lb的元素按值非递减排列。 /归并La和Lb得到新的单链线性表Lc， /Lc的元素也按值非递减排列。 pa = Lanext； pb =Lbnext； Lc = pc = La； /用La的头结点作为Lc的头结点 while (pa & pb) if (padatadata) pcnext = pa；pc = pa；pa = panext； else pcnext = pb；pc = pb；pb = pbnext pcnext = pa ? pa : pb /插入剩余段 free(Lb)； /释放Lb的头结点 /MerqeList_L 算法 2.12 有时，也可借用一维数组来描述线性链表，其类型说明，如下所示： /线性表的静态单链表存储结构 #define MAXSIZE l000 /链表的最大长度 typedef struct ElemTyPe data； int Cur； component，SLinkList MAXSIZE； 这种描述方法便于在不设“指针”类型的高级程序设计语言中使用链表结构。在如上描述的链表中，数组的一个分量表示一个结点，同时用游标(指示器cur)代替指针指示结点在数组中的相对位置。数组的第零分量可看成头结点，其指针域指示链表的第一个结点。 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 910 10(a)修改前的状态； (b)修改后的状态 图210 静态链表示例 例如，图2.10(b)展示了图2.10(a)所示线性表在插入数据元素“SHI和删除数据元素ZHENG之后的状况。为了和指针型描述的线性链表相区别，我们给这种用数组描述的链表起名叫静态静态链表链表 1ZHAO2QIAN3SUN4LI5ZHOU6WU7ZHENG8WANG01ZHAO2QIAN3SUN4LI9ZHOU6WU8ZHENG8WANG0SHI5 假设S为SLinkList型变量，则S0.Cur指示第一个结点在数组中的位置，若设i=S0.cur，则Si.data存储线性表的第一个数据元素，且si.cur指示第二个结点在数组中的位置。一般情况，若第i个分量表示链表的第k个结点，则Si.cur指示第k+1个结点的位置。因此在静态链表中实现线性表的操作和动态链表相似，以整型游标i代替动态指针p，i=Si.Cur的操作实为指针后移(类似于p=pnext)。 例如，在静态链表中实现的定位函数LocateElem如算法2.13所示。 int LocateElem_SL (SLinkList S，ElemType e) /在静态单链线性表L中查找第1个值为e的元素。 /若找到，则返回它在L中的位序，否则返回0。 i=S0.cur； /i指示表中第一个结点 while(i&Si.data!=e) i = Si.cur；/在表中顺链查找 return i； /LocateElem_SL 算法 2.13 类似地可写出在静态链表中实现插入和删除操作的算法。从图2.10的例子可见，指针修改的操作和前面描述的单链表中的插入和删除的算法2.9，2.10类似，所不同的是，需由用户自己实malloc和free这两个函数。为了辨明数组中哪些分量未被使用，解决的办法是将所有未被使用过以及被删除的分量用游标链成一个备用的链表，每当进行插入时便可从备用链表上取得第一个结点作为待插入的新结点；反之，在删除时将从链表中删除下来的结点链接到备用链表上。 循环链表（Circular linked List)是另一种形式的链式存储结构。它的特是点表中最后一个结点的指针域指向头结点，整个链表形成一个环。由此从表中任一结点出发均可找到表中其它结点，如图2.12所示为单链的循环链表。2.3.2 循环链表(a)非空表(b) 空表图2.12 单循环链表HH 循环链表的操作和线性表基本一致，差别仅在于算法中的循环条件不是p或者pnext是否为空，而是它们是否等于头指针。 但有的时候，若在循环链表中设置尾指针而不设头指针（如图(a)所示）可使某些操作简化。例如将两个线性表合并成一个表时，仅需将一个表的表尾和另一个表的表头相接。仅需改变两个指针即可，运算时间为O(1)。合并后的表如图(b)所示。 AB(a)BA(b)2.3.3 双向链表 以上讨论的链式存储结构的结点中只有一个指示直接后继的指针域，因此从某个结点出发只能顺时针往后寻查其它结点。若要寻查结点的直接前趋，则须从表头指针出发。 在单链表中，NextElem的执行时间为O(1)，而PriorElem的执行时间为O(n)。为了克服单链表这种单向性的缺点，可利用双向链表双向链表（Double Linked List) 。/ -线性表的双向链表存储结构-typedef struct DuLNode ElemType data; struct DuLNode *prior; struct DuLNode *next; DuLNode, *DuLinkList; (a)结点结构priorelementnextL(b)空的双向循环链表abcL(c)非空的双向循环链表 若p为指向表中某结点的指针，则p-next-prior = p-prior-next = p 在双向链表中，有些操作如：ListLength、GetElem和LocateElem等仅需涉及一个方向的指针，则它们的算法描述和线性表的操作相同，但在插入、删除时有很大的不同，在双向链表中需同时修改两个方向的指针。cbapaabps1423图2.15 在双向链表中删除结点时指针变化状况 图2 .16 在双向链表中插入一个结点时指针变化状况 Status ListInsert_DuL (DuLinkList &L, int i, ElemType e) /在带头结点的双链循环线性表中第i个位置之前插入元素e, /i的合法值为= i data = e; s -prior = p-prior; p -prior -next = s; s -next = p; p-prior = s; return OK; / ListInsert_DuL; 算法2.18 Status ListDelete_DuL(DuLinkList &L， int i，ElemType &e) /删除带头结点的双链循环线性表L的第i个元素， / i的合法值为1i表长 if( !(p=GetElemP_DuL(L，i) /在L中确定第i个元素的位置指针p return ERROR； / p=NULL，即第i个元素不存在 e=pdata； ppriornext = pnext; pnextprior = pprior; free(p)； return 0K /ListDelete_DuL 算法 2.19 从本节(2.3)的讨论中可见，由于链表在空间的合理利用上和插入、删除时不需要移动等的优点，因此在很多场合下，它是线性表的首选存储结构。然而，它也存在着实现某些基本操作如求线性表的长度时不如顺序存储结构的缺点；另一方面，由于在链表中，结点之间的关系用指针来表示，则数据元素在线性表中的“位序”的概念已淡化，而被数据元素在线性链表中的“位置”所代替。为此，从实际应用角度出发重新定义线性链表及其基本操作。一个带头结点的线性链表类型定义如下: typedef struct LNode /结点类型 ElemType data; struct Lnode *next; *Link, *position; typedef struct /链表类型 Link head，tail; /分别指向线性链表中的头结点和最后一个结点 int len；/指示线性链表中数据元素的个数 LinkList； Status MakeNode(Link &p，ElemType e)； /分配由p指向的值为e的结点，并返回OK； /若分配失败 ，则返回ERROR； void FreeNode (Link p)； /释放p所指结点 Status InitList (LinkList &L)； /构造一个空的线性链表L Status DestroyList(LinkList &L)； /销毁线性链表L，L不再存在 Status ClearList (LinkList &L)； /将线性链表L重置为空表，并释放原链表的结点空间 Status InsFirst (Link h，Link s)； /已知h指向线性链表的头结点， /将s所指结点插入在第一个结点之前 Status DelFirst(Link h， Link &q)； /已知h指向线性链表的头结点 , /删除链表中的第一个结点并以q返回 Status Append (LinkList &L，Link s) /将指针s所指(彼此以指针相链)的串结点链接在线性链表L的 /最后一个结点之后，并改变链表L的尾指针指向新的尾结点 Status Remove (LinkList&L，Link&q)； /删除线性链表L中的尾结点并以q返回， /改变链表L的尾指针指向新的尾结点 Status InsBefore(LinkList &L，Link &p，Link s)； /已知p指向线性链表L中的一个结点，将s所指结点插入在 /p所指结点之前，并修改指针p指向新插入的结点 Status InsAfter (LinkList &L，Link &p，Link s)； /已知p指向线性链表L中的一个结点，将s所指结点插入在 /p所指结点之后并修改指针p指向新插入的结点 Status SetCurElem(Link &p，ElemType e)； /已知p指向线性链表中的一个结点， /用e更新p所指结点中数据元素的值 ElemType GetCurElem (Link p)； /已知p指向线性链表中的一个结点， /返回p所指结点中数据元素的值 Status ListEmpty (LinkList L)； /若线性链表L为空表，则返回TRUE， /否则返回FALSE int ListLength (LinkList L)； /返回线性链表L中元素个数 Position GetHead (LinkList L)； /返回线性链表L中头结点的位置Position GetLast (LinkList L)； /返回线性链表L中最后一个结点的位置Position PriorPos (LinkList L， Link p)； / 已知p指向线性链表L中的一个结点，返回p所指结点的 /直接前驱的位置，若无前驱，则返回 NULL Position NextPos (LinkList L，Link p)； /已知p指向线性链表L中的一个结点， /返回p所指结点的直接后继的位置，若无后继，则返回NULLStatus LocatePos (LinkList L，int i，Link &p)； /返回p指示线性链表L中第i个结点的位置并返回OK， /i值不合法时返回ERROR Position LocateElem (LinkList L，ElemType e， Status (*compare)(ElemType，ElemType) /返回线性链表L中第1个与e满足 /函数compare()判定关系的元素的 /位置，若不存在这样的元素，则返回NULL Status ListTraverse (LinkList L，Status (*visit) ( ) )； /依次对L的每个元素调用函数visit()，一旦visit()失败，则操作失败。 在 上 述 定 义 的 线 性 链 表 的 基 本 操 作 中 ， 除 了DestroyList， ClearList，Remove，InsBefore，PriorPos，LocatePos，LocateElem和ListTraverse的时间复杂度和表长成正比之外，其它操作的时间复杂度都和表长无关，Append操作的时间复杂度则和插入的结点数成正比。利用这些基本操作，容易实现诸如在第i个元素之前插入元素或删除第i个元素或合并两个线性表等操作。 Status ListInsert_L(LinkList &L，int i，ElemType e) /在带头结点的单链线性表L的第i个元素之前插入元素e if( ! LocatePos(L，i-1，h) return ERROR； /i值不合法 if( ! MakeNode(s，e) return ERROR； /结点存储分配失败 InsFirst(h，s)； return OK； /ListInsert_L 算法 2.202.4 一元多项式的表示及相加 (1学时） 符号多项式的操作，已经成为表处理的典型用例。在数学上，一个一元多项式Pn(x)可按升幂写成：Pn(x) = p0+ p1x+ p2x2+.+ pnxn，它由n+1个系数唯一确定。因此，在计算机里，它可用一个线性表 P来表示： P = (p0 ,p1 ,p2 , pn) 每一项的指数i隐含在其系数pi的序号里。 假设Qm(x)是一元m次多项式，同样可用线性表Q来表示 Q = (q0 ,q1 ,q2 , qm) 不失一般性，设mn，则两个项式相加的结果 Rn(x) = Pn(x)+Qm(x) 可用线性表R表示： R = (p0+q0 , p1+q1 , p2 +q2 , , pm +qm , pm+1 , pn) 显然，我们可以对P、Q和R采用顺序存储结构，使得多项式相加的算法定义十分简洁。 然而在通常的应用中，多项式的次数可能很高且变化很大，使得顺序存储结构的最大长度很难决定。特别是在处理形如 S(x) = 1+3x10000+2x20000 的多项式时，就要用一长度为20001的线性表来表示，表中仅有三个非零元素，这种对内存空间的浪费是应当避免的，但是如果只存储非零系数项则显然必须同时存储相应的指数。 一般情况下的一元n次多项式可写成 Pn(x) = p1xe1+ p2xe2+.+ pmxem (2-7) 其中pi，是指数为ei的项的非零系数，且满足 0 e1 e2 =0 TermSet中的每个元素包含一个表示系 数的实数和表示指数的整数 数据关系数据关系： R1= | ai-l, ai D，且ai-l中的指数值 0的元素的前驱的位置，并返回FALSEStatus OrderInsert(LinkList &L，ElemType e， int(*compare)(ElemType，ElemType)； / 按有序判定函数compare()的约定， /将值为e的结点插入到有序链表L的适当位置 例24 抽象数据类型Polynomial的实现。 typedef struct /项的表示，多项式的 /项作为LinkList的数据元素 float coef； /系数 int expn； /指数 term，ElemType； /两个类型名：term用于本ADT，ElemType为LinkList的数据对象名 typedef struct ElemType e； Lnode *next； Lnode，*LinkList； typedef LinkList polynomial； /用带表头结点的有序链表表示多项式/基本操作的函数原型说明 void CreatPolyn (polynomail &P，int m) /输入m项的系数和指数，建立表示一元多项式的有序链表P void DestroyPolyn (polynomail &P)； /销毁一元多项式P void PrintPolyn (polynomail P)； /打印输出一元多项式P int PolynLength (polymomail P)； /返回一元多项式P中的项数 void AddPolyn (polynomail &Pa，polynomail &Pb)； /完成多项式相加运算，即：Pa=Pa+Pb，并销毁一元多项式Pb void SubtractPolyn (polynomail &Pa，polynomail &Pb)； /完成多项式相减运算，即：Pa=Pa-Pb，并销毁一元多项式Pb void MultiplyPolyn (polynomail &Pa，polynomail &Pb)； /完成多项式相乘运算，即：Pa= Pa * Pb，并销毁一元多项式Pb/ 基本操作的算法描述(部分) int cmp (term a，term b)； /依a的指数值)b的指数值， /分别返回-1,0和1； 算法2.22 void CreatPolyn (polynomail &P，int m) /输入m项的系数和指数，建立表示一元多项式的有序链表P InitList(P)； h = GetHead(P)； e.coef = 0.0； e.expn = -1； SetCurElem (h，e)； /设置头结点的数据元素 for( i=1；inext; 2) L =P-next;3) R-data = P-data; 4) R-data = P-next -data5) P-next-next-next-data = P-data;6) T = P while (T!=NULL) T-data = T-data*2; T = T-next7) T = P while (T-next!=NULL)T-data = T-data*2; T = T-next257382.3 简述以下算法的功能。1) Status A(LinlList L) /L是无表头结点的单链表 if ( L&L-next) Q = L; L = L-next; P = L; while( P-next ) P=P-next; P-next = Q; Q-next = NULL; return OK; /A2)void BB(LNode *s , LNode *q) p = s; while (p-next!=q) p = p-next; p-next = s; /BB void AA(LNode