《高考理综试题及答案(全国卷).ppt》由会员分享，可在线阅读，更多相关《高考理综试题及答案(全国卷).ppt（41页珍藏版）》请在金锄头文库上搜索。
1、2.3 线性表的链式表示和实现线性表的链式表示和实现 2.3.1 线性链表线性链表 链式存储链式存储 ：用：用一组任意的存储单元存储一组任意的存储单元存储线性表中的数据元线性表中的数据元素。用这种方法存储的线性表简称素。用这种方法存储的线性表简称线性链表线性链表。 存储链表中数据元素的一组任意的存储单元可以是连续的，存储链表中数据元素的一组任意的存储单元可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。也可以是不连续的，甚至是零散分布在内存中的任意位置上的。 链表中数据元素的逻辑顺序和物理顺序不一定相同。链表中数据元素的逻辑顺序和物理顺序不一定相同。 为了表示数据元素为了表
2、示数据元素aiai和和ai+1ai+1之间的逻辑关系，对数据元素之间的逻辑关系，对数据元素aiai来说，除了存储其本身的信息之外，还需存储一个指示其直接后来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（直接后继的存储位置）。这两部分信息组成数据元素继的信息（直接后继的存储位置）。这两部分信息组成数据元素aiai的存储映像，称为的存储映像，称为结点结点（nodenode）。）。 链表是通过每个结点的指针域将线性表的链表是通过每个结点的指针域将线性表的n个结点按其逻辑次序链接在一个结点按其逻辑次序链接在一起的。起的。 每一个结点只包含一个指针域的链表，称为单链表或线性链表。每一个
3、结点只包含一个指针域的链表，称为单链表或线性链表。 为操作方便，总是在链表的第一个结点之前附设一个头结点为操作方便，总是在链表的第一个结点之前附设一个头结点( (头指针头指针) )head指向第一个结点。头结点的数据域可以不存储任何信息指向第一个结点。头结点的数据域可以不存储任何信息( (或链表长度等或链表长度等信息信息) )。data next图图2-2 链表结点结构链表结点结构data ：数据域，存放数据元素信息。：数据域，存放数据元素信息。next ：指针域，存放结：指针域，存放结点的直接后继的地址，指针域中存储的信息称为指针或链。点的直接后继的地址，指针域中存储的信息称为指针或链。 2
4、.3.1 线性链表线性链表 结点包括两个域：数据域和指针域。结点包括两个域：数据域和指针域。n n个结点连接成个结点连接成一个链表，即为线性表的链式存储结构。一个链表，即为线性表的链式存储结构。 2.3.1 线性链表线性链表 单链表的存取必须从头指针开始，头指针指示链表中第一个结点。单链表的存取必须从头指针开始，头指针指示链表中第一个结点。例例1 1、线性表、线性表L=(ZHAO，QIAN，SUN，LI，zhou,wu,zheng,wang) 存储地址数据域指针域头指针H3117131925313743LIQIANSUNWANGWUZHAOZHENGZHOU43131NULL3771925HZ
5、HAOQIAN SUN LI ZHOU WU ZHENG WANG C语言中用结构指针来描述语言中用结构指针来描述( (线性表的单链表存储结构线性表的单链表存储结构) )typedef struct LNode ElemType data; /*数据域，保存结点的值数据域，保存结点的值 */struct Lnode *next; /*指针域指针域*/LNode，*LinkList; /*结点的类型结点的类型 */ 2.3.1 线性链表线性链表a1La2an带头结点的单链表 非空表L带头结点的单链表 空表在单链表中，每个元素的存储位置都包含在其直接前驱结点的信息之中。PP -next指向第2个元
6、素，p -data=a1,p -next -data=a2单链表是非随机存取的存储结构常见的指针操作常见的指针操作 q=p ;pa操作前paq操作后 q=p-next ;bpa操作前操作后qbpa p=p-next ;bpa操作前操作后pba q-next=p ;cpbqa操作前操作后qbacp(a) q-next=p-next ;(a)xypbqa操作前操作后qbaxyp操作前ypxbqa操作后ypxbqa(b)操作前ypxbqa操作后ypxbqa(b)2.3.2 单链表的基本操作单链表的基本操作取单链表中的第i个元素: 对于单链表，不能象顺序表中那样直接按序号i访问结点，而只能从链表的头结
7、点出发，沿链域next逐个结点往下搜索，直到搜索到第i个结点为止。因此，链表是非随机存取结构。 设单链表的长度为n，要查找表中第i个结点，仅当1in时，i的值是合法的。2.3.2 单链表的基本操作单链表的基本操作status GetElem_L(LinkList L ， int i, ElemType &e) /L为带头结点的单链表的头指针 /当第i个元素存在时，其值赋给e,并返回OK，否则返回ERROR p=L-next; j=1; / 使p指向第一个结点 while (p & jnext; +j; if (!p|ji) return error; e=p-data; / p为NULL 表示
8、i太大; ji表示i为0 算法2.8移动指针p的频度： in：n次。时间复杂度: O(n)。2.3.2 单链表的基本操作单链表的基本操作单链表的插入 插入运算是将值为e的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间。因此，必须首先找到ai-1所在的结点p，然后生成一个数据域为e的新结点q，q结点作为p的直接后继结点。算法描述（算法2.9）status ListInsert_L(LinkList &L，int i，ElemType e) / 在带头结点的单链表L的第i个位置插入值为e的结点 p=L; j=0;while ( p& jnext; +j; if (!p|ji-1)
9、return ERROR;s=(LinkList)malloc(sizeof(Lnode);s-data=e; s-next=p-next; p-next=s;return ok; 链表的长度为n，合法的插入位置是1in。算法的时间主要耗费移动指针p上，故时间复杂度亦为O(n)2.3.2 单链表的基本操作单链表的基本操作单链表的删除单链表的删除 删除单链表中的第删除单链表中的第i个结点。个结点。 为了删除第为了删除第i个结点个结点ai，必须找到结点的存储地址。该存储地址是在其直接前，必须找到结点的存储地址。该存储地址是在其直接前趋结点趋结点ai-1的的next域中，因此，必须首先找到域中，因此
10、，必须首先找到ai-1的存储位置的存储位置p，然后令，然后令pnext指指向向ai的直接后继结点，即把的直接后继结点，即把ai从链上摘下。最后释放结点从链上摘下。最后释放结点ai的空间。的空间。 设单链表长度为设单链表长度为n，则删去第，则删去第i个结点仅当个结点仅当1 i n时是合法的。则当时是合法的。则当i=n+1时，时，虽然被删结点不存在，但其前趋结点却存在，是终端结点。故判断条件之一是虽然被删结点不存在，但其前趋结点却存在，是终端结点。故判断条件之一是pnext!=NULL。显然此算法的时间复杂度也是。显然此算法的时间复杂度也是O(n)(n)。 算法描述算法描述( (算法算法2.10)
11、2.10)status LinkListDelete_ L(LinkList &L， int i, ElemType &e) /在带头结点的单链表在带头结点的单链表L中删除第中删除第i个元素，并由个元素，并由e返回其值返回其值 p=L; j=0;while ( p-next& jnext; +j; if (!(p-next)|ji-1) return error; q=pnext; pnext =qnext; free(q); return ok; 单链表是一种动态结构，建立线性表的链式存储结构的过程是一个动态生成链表的过程2.3.2 单链表的基本操作单链表的基本操作逆向建立单链表（算法逆向建
12、立单链表（算法2.112.11）Viod CreateList_L(LinkList &L , int n) /逆位序输入n个元素的值，建立带表头结点的单链线性表L。 L=(LinkList)malloc(sizeof(LNode); L-next=NULL; for( i=n; i0; -i) p=(LinkList)malloc(sizeof(LNode); scanf(&p-data); p-next=L-nxet; L-next=p; 时间复杂度为O（n）单链表的合并单链表的合并 设有两个有序的单链表，它们的头指针分别是设有两个有序的单链表，它们的头指针分别是La 、 Lb，将它们合并
13、为以，将它们合并为以Lc为为头指针的有序链表。合并头指针的有序链表。合并前的示意图如图前的示意图如图2-4所示。所示。15 图图2-4 两个有序的单链表两个有序的单链表La ，Lb的初始状态的初始状态-2 4 9 Lb pb-7 3 12 23 La Lcpapc pa ，pb分别是待考察的两个链表的当前结点，分别是待考察的两个链表的当前结点，pc指向指向Lc表中最后一个结点。表中最后一个结点。 合并了值为合并了值为-7，-2的结点后示意图如图的结点后示意图如图2-5所示。所示。图图2-5 合并了值为合并了值为-7 ，-2的结点后的状态的结点后的状态-2 4 9 15 Lb pcpbLc-7
14、3 12 23 La pa算法说明算法说明 算法中算法中pa ，pb分别是待考察的两个链表的当前结分别是待考察的两个链表的当前结点，点，pc指向指向Lc表中最后一个结点。表中最后一个结点。算法描述（算法算法描述（算法2.122.12）Void MergeList_L(LinkList &La， LinkList &Lb, LinkList &Lc) /已知单链线性表La和Lb的元素按非递减排列 /归并La和Lb得到新的单链线性表Lc也按值非递减排列 pa=La-next ; pb=Lb-next ; Lc=pc=La; while (pa & pb) if (pa-datadata) pc-n
15、ext=pa ; pc=pa ; pa=pa-next ; else pc-next=pb ; pc=pb ; pb=pb-next ; pc-next=pa?pa:pb;free(Lb); /释放Lb头结点2.3.3 循环链表循环链表 循环链表循环链表(Circular Linked List)：是一种头尾相是一种头尾相接的链表。其特点是最后一个结点的指针域指向链表的接的链表。其特点是最后一个结点的指针域指向链表的头结点，整个头结点，整个链表的指针域链接成一个环链表的指针域链接成一个环。 从循环链表的任意一个结点出发都可以找到链从循环链表的任意一个结点出发都可以找到链表中的其它结点，使得表处
16、理更加方便灵活。表中的其它结点，使得表处理更加方便灵活。 图图2-6是带头结点的单循环链表的示意图。是带头结点的单循环链表的示意图。空表空表图图2-6 单循环链表示意图单循环链表示意图非空表非空表a1 a2 anH H 有时，若在循环链表中设立尾指针而不设头指针，有时，若在循环链表中设立尾指针而不设头指针，可使某些操作简化。可使某些操作简化。循环链表的操作循环链表的操作 对于单循环链表，除链表的合并外，其它的操作和对于单循环链表，除链表的合并外，其它的操作和单线性链表基本上一致，仅仅需要在单线性链表操作算单线性链表基本上一致，仅仅需要在单线性链表操作算法基础上作以下简单修改：法基础上作以下简单
17、修改： 判断是否是空链表：判断是否是空链表：head-next=head ; ; 判断是否是表尾结点：判断是否是表尾结点：p-next=head ; ;ABB,A2.3.4 双向链表双向链表 双向链表双向链表(Double Linked List) : :指的是构成链指的是构成链表的每个结点中设立两个指针域：一个指向其直接前趋表的每个结点中设立两个指针域：一个指向其直接前趋的指针域的指针域prior，一个指向其直接后继的指针域，一个指向其直接后继的指针域next。这。这样形成的链表中有两个方向不同的链，故称为样形成的链表中有两个方向不同的链，故称为双向链表双向链表。 和单链表类似，双向链表一般
18、增加头指针也能使双和单链表类似，双向链表一般增加头指针也能使双链表上的某些运算变得方便。链表上的某些运算变得方便。 将头结点和尾结点链接起来也能构成循环链表，并将头结点和尾结点链接起来也能构成循环链表，并称之为双向循环链表。称之为双向循环链表。 双向链表是为了克服单链表的单向性的缺陷而引入双向链表是为了克服单链表的单向性的缺陷而引入的。的。1 双向链表的结点及其类型定义双向链表的结点及其类型定义 双向链表的结点的类型定义如下。其结点形式如双向链表的结点的类型定义如下。其结点形式如图图2-7所示所示，带头结点的双向链表的形式如图，带头结点的双向链表的形式如图2-8所示所示。typedef str
19、uct Dulnode ElemType data ;struct Dulnode *prior , *next ;DulNode，*DulinkList ;elementnextprior图图2-7 双向链表结点形式双向链表结点形式非空双向链表非空双向链表heada2a1an空双向链表空双向链表head图图2-8 带头结点的双向链表形式带头结点的双向链表形式2.3.4 双向链表双向链表非空双向循环链表链表非空双向循环链表链表heada2a1an空双向循环链表空双向循环链表head图图2-8 带头结点的双向循环链表形式带头结点的双向循环链表形式 双向链表结构具有对称性，设双向链表结构具有对称性
20、，设p指向双向链表中的指向双向链表中的某一结点，则其对称性可用下式描述：某一结点，则其对称性可用下式描述：p-prior-next=p=p-next-prior ; 结点结点p的存储位置存放在其的存储位置存放在其直接前趋结点直接前趋结点p-prior的的直接直接后继指针域后继指针域中，同时也存放在中，同时也存放在其直接后继结点其直接后继结点p-next的的直接直接前趋指针域前趋指针域中。中。2 双向链表的基本操作双向链表的基本操作(1) 双向链表的插入双向链表的插入 将值为将值为e的结点插入双向链表中。的结点插入双向链表中。插入前后链表的变化如图插入前后链表的变化如图2-9所示。所示。算法2.
21、18 status ListInsert_Dul(DuLinkList &L , int i , ElemType e) if(!(p=GetElemP_Dul(L , i) return error; if (!(s=(DuLinkList)malloc(sizeof(DuLNode) return error; s-data=e; s-prior=p-prior; p-prior-next=s; s-next=p; p-pror=s; return ok; Sepai-1ai图图2-9 双向链表的插入双向链表的插入1234 (2) 双向链表的结点删除双向链表的结点删除 设要删除设要删除的结
22、点为的结点为p ，删除时可以不引入新的辅助指针变量，可以直接先，删除时可以不引入新的辅助指针变量，可以直接先断链，再释放结点。断链，再释放结点。 Stutas ListDelete_Dul(DulLinkList &L, int i, ElemType &e) Stutas ListDelete_Dul(DulLinkList &L, int i, ElemType &e) / /删除带头结点的双链循环线性表删除带头结点的双链循环线性表L L的第的第i i个元素，个元素，1=i=1=idata; e=p-data; p-prior-next=p-next; p-next-prior=p-pri
23、or; free(p); return OK; 注意：注意： 与单链表的插入和删除操作不同的是，在双向链表中与单链表的插入和删除操作不同的是，在双向链表中插入插入和和删除删除必必须同时须同时修改两个方向上的指针域的指向修改两个方向上的指针域的指向。abcp12ac2.3.5 重新定义线性链表及其基本操作单链表存在以下缺点：单链表存在以下缺点：1.求线性表的长度时不如顺序存储结构；求线性表的长度时不如顺序存储结构；2.在链表中，在链表中，“位序位序”的概念淡化，被数据元素在线性表中的的概念淡化，被数据元素在线性表中的 “位置位置”代替。代替。typedef struct LNode/节点类型 E
24、lemType data; struct LNode *next; *Link,*PositionStatus MakeNode(Link &p, Elemtype e)viod FreeNode (Link &p)2.3.5 重新定义线性链表及其基本操作typedef struct /链表类型 Link head,tail; int len; LinkList链表的基本操作：1.结构的初始化和销毁结构： Status InitList(LinkList &L);/构造一个空的线性表 Status DestroyList(LinkList &L);/销毁线性链表L，L不再存在2.3.5 重新定
25、义线性链表及其基本操作2.引用型操作： ElemType GetCurElem(Link p); Status ListEmpty(LinkList L); int ListLength(LinkList L); Position GetHead(LinkList L); Position GetLast(LinkList L); Position PriorPos(LinkList L, Link p); Position NextPos(LinkList L, Link p); Status LocatePos(LinkList L, int i ,Link &p); Position L
26、ocateElem(LinkList L, ElemType e, Status(*compare)(ElemType, ElemType); Status ListTraverse(LinkList L, Status (*visit)(); 链表的基本操作：2.3.5 重新定义线性链表及其基本操作3.加工型操作： Status ClearList(LinkList &L); /将线性链表L重置为空表，并释放原链表的结点空间 Status InsFirst(Link h,Link s); /已知h指向线性链表的头结点，将s所指节点插入在第一个结点之前 Status DelFirst(Link
27、 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 ); Status InsAfter(LinkList &L , Link &p ,Link
28、 s ); Status SetCurElen(Link &p , ElemType e);2.3.5 重新定义线性链表及其基本操作算法算法2.20Status ListInsert_L(LinkList &L, int i , ElemType e) /在带头结点的单链线性表L的第i个位置之前插入元素e if(!LocatePos(L, i-1, h) return ERROR; if(!MakeNode(s , e) return ERROR; InsFirst(h,s); return OK; 2.3.5 重新定义线性链表及其基本操作算法算法2.21 Status MergeList_L
29、(LinkList &La, LinkList &Lb, LinkList &Lc, int (*compare)(ElemType, ElemType) /已知单链线性表La和Lb的元素按值非递减排序 /归并La和Lb得到新的单链线性表Lc，Lc的元素也按值非递减排序 if(!InitList(Lc) return ERROR; ha=GetHead(La); hb=GetHead(Lb); pa=NextPos(La , ha) ; pb=NextPos(Lb , hb) ; while(pa&pb) a=GetCurElem(pa) ; b= GetCurElem(pb); if(*co
30、mpare)(a,b)=0) DelFirst(ha, q); Append(Lc,q); pa=NextPos(La, ha); else DelFirst(hb, q); Append(Lc,q); pb=NextPos(Lb, hb); if(pa) Append(Lc, pa); else Append(Lc, pb ); FreeNode(ha); FreeNode(hb); return OK; 2.4 一元多项式的表示和相加一元多项式的表示和相加1 一元多项式的表示一元多项式的表示 一元多项式一元多项式 Pn(x)=p0+p1x+p2x2+ +pnxn ，由，由n+1个系数唯一确
31、定个系数唯一确定。则在计算机中可。则在计算机中可用线性表用线性表P=(p0 ，p1 ，p2 ， ，pn )表示表示。 Qm(x) Qm(x)是一元是一元m m次多项式，次多项式，Q=(qQ=(q0 0,q,q1 1, ,q,qm m) ) 设设mnmn，Rn(x)=Pn(x)+Qn(x)Rn(x)=Pn(x)+Qn(x)可用线性表可用线性表R=(R=(p0+q0 0,p1 1+q1 1,pm m+qm m,pm+1m+1,pn n) )表示表示S(x)=1+3x10000+2x20000顺序存储结构2.4 一元多项式的表示和相加一元多项式的表示和相加一般情况下的一元一般情况下的一元n次多项式可
32、写成次多项式可写成：若用一个长度为m且每个元素有两个数据项（系数项和指数项）的线性表便可唯一确定多项式Pn(x)。对应于线性表的两种存储结构，一元多项式也可以有两种存储结构表示方法。在实际的应用程序中取哪一种，则要视多项式作何种运算而定。2.4 一元多项式的表示和相加一元多项式的表示和相加抽象数据类型一元多项式的定义：2.4 一元多项式的表示和相加一元多项式的表示和相加-1A703198517B-181227-98如何实现用这种线性链表表示的多项式的加法运算？ 假设指针qa和qb分别指向多项式A和B中当前进行比较的某个节点，则比较两个节点的指数项有三种情况：1.指针qa所指节点的指数值指针qb
33、所指节点的指数值，应摘取指针qb所指节点插 到“和多项式”链表中去；3.指针qa所指节点的指数值=指针qb所指节点的指数值,则将两个节点的系数相加，若 和不为0，则修改qa所指节点的系数值，同时释放qb所指节点；反之，从多项式A 中的链表中删除相应节点，并释放qa和qb所指结点。2.4 一元多项式的表示和相加一元多项式的表示和相加-1A703198517B-181227-98qaqbC-1A703198517B-181227-98qaqbC-1A7011198517B-1227-98qaqbC释放2.4 一元多项式的表示和相加一元多项式的表示和相加-1A7011198517B-1227-98q
34、aqbC-1A7011198517B-1227-98qaqbC-1A70111517B-1227qaC2.4 一元多项式的表示和相加一元多项式的表示和相加有序链表的基本操作定义域线性链表有两处不同： 1. LocationEelem的职能不同 2. 需增加按有序关系进行插入的操作OrderInsert。Status LocateElem(LinkList L, ElemType e, Position &q, int (*compare)(ElemType, ElemType); /若有序链表L中存在与e满足判定函数compare()取值为0的元素，则q指示L /中第一个值为e的结点的位置，并
35、返回TURE；否则q指示第一个与e满足判 /定函数compare()取值0的元素的前驱的位置，并返回FALSE Status OederInsert(LinkList &L, ElemType e, int (*compare)(ElemType, ElemType) /按有序判定函数compare()的约定，将值为e的结点插入到有序链表L的适当 位置上2.4 一元多项式的表示和相加一元多项式的表示和相加抽象数据类型Polynomial的实现：typedef struct /项的表示，多项式的项作为LinkList的数据元素 float coef; /系数 int expn; /指数 term
36、,ElemType; /两个类型名：term用于本DAT,ElemType为Linklist的数据对象名typedef LinkList polynomial; /用带头结点的有序链表表示多项式/-基本操作的函数原型说明- void CreatPolyn(polynomial &P, int m); /输入m项的系数和指数，建立表示一元多项式的有序链表P void DestroyPolyn(polynomial &P) ; /销毁一元多项式P void PrintPolyn(polynomial P); /打印输出一元多项式P int PolynLength(polynomial P) ; /
37、返回一元多项式P中的项数 viod addPolyn(polynomial &Pa, polynomial &Pb); /完成多项式相加运算，即：Pa=Pa+Pb,并销毁一元多项式Pb viod SubtractPolyn(polynomial &Pa, polynomial &Pb); /完成多项式相减运算，即：Pa=Pa-Pb,并销毁一元多项式Pb viod MultiplyPolyn(polynomial &Pa, polynomial &Pb); /完成多项式相乘运算，即：Pa=Pa*Pb,并销毁一元多项式Pb2.4 一元多项式的表示和相加一元多项式的表示和相加viod CreatPo
38、lyn(Polnomail &P, int m) /输入m项的系数和指数，建立表示一元多项式的有序链表 InitList(P); h=GetHead(P); e.ceof=0.0; e.expn=-1; SetCurElem(h,e); for(i=1,i=m,+i) scanf( e.ceof, e.expn) ; if(!LocateElem(P,e,q,(*cmp)() if(MakeNode(s,e) InsFirst(q,s); 算法算法2.22int cmp (term a, term b) /依a的指数值)b的指数值，分表返回-1,0,+1A17(x)=7+3x+9x8+5x17
39、,假如用户输入的顺序为： (7,0) , (5,17) ,(3,1) , (9,8)-10.0h071751389void AddPolyn(polynomial &Pa, polynomial &Pb) /多项式加法：pa=pa+pb,利用两个多项式的结点构成“和多项式” ha = GetHead(Pa); hb = GetHead(Pb); qa = NextPos(Pa,ha); qb = NextPos(Pb,hb); while (qa & qb) a = GetCurElem (qa); b = GetCurElem (qb); switch (*Cmp(a,b) case -1:
40、 / 多项式PA中当前结点的指数值小 ha = qa; qa = NextPos (Pa, qa); break; case 0: / 两者的指数值相等 sum = a.coef + b.coef ; if (sum != 0.0) / 修改多项式PA中当前结点的系数值 SetCurElem(qa,sum) ; ha = qa; else / 删除多项式PA中当前结点 DelFirst(ha, qa)； FreeNode(qa); DelFirst(hb, qb); FreeNode(qb); qb = NextPos(Pb, hb); qa = NextPos(Pa, ha); break;
41、 case 1: / 多项式PB中当前结点的指数值小 DelFirst(hb, qb); InsFirst(ha, qb); qb = NextPos(Pb, hb); ha = NextPos(Pa, ha); break; if (!Empty(Pb) Append(Pa, qb); / 链接Pb中剩余结点 FreeNode(hb); / 释放Pb的头结点 算法算法2.23习题1.线性表的顺序存储结构是一种（）的存储结构。A.随机存取 B.顺序存取 C.索引存取 D.散列存取2.顺序表的插入算法中，当n个空间已满时，可再申请增加分配m个空间，若申请失败，则说明系统没有（ ）可分配的存储空间
42、。A.m个 B.m个连续的 C.n+m个 D.n+m个连续的3.在什么情况下线性表使用顺序存储结构比较好？4.设计一个高效算法，在顺序表中删除所有元素值为x的元素，要求空间复杂度为O(1)。习题1.链表不具有的特点是（） A. 可随机访问任一元素 B. 插入、删除不需要删除元素 C. 不必事先估计存储空间 D. 所需空间与线性表长度成正比2. 对于n个元素组成的线性表，建立一个有序单链表的时间复杂度是（） A. O(1) B.O(n) C.O(n2) D.O(nlogn)3. 在单链表中删除指针P所指结点的后继结点，则执行（） A. p-next=p-next-next B. p-next=p
43、-next C. p=p-next-next D. p=p-next; p-next=p-next-next4. 在一个单链表中，已知q所指结点是p所指结点的直接前驱，若在q和p之间插入 s所指结点，则执行 （） A. s-next=p-next; p-next=s; B. q-next=s; s-next=p; C. p-next=s-next; s-next=p; D. p-next=s; s-next=q5. 已知非空线性链表有list指出，结点结构为（data,link）。请编写算法，将链表中数据域值最小的结点移到链表的最前面。要求：不得额外申请新的结点。6.设计算法实现将双链表中结点p与其直接后继结点互换位置。
