高考理综试题及答案(全国卷2).ppt

2.3 线性表的链式表示和实现线性表的链式表示和实现 线性链表线性链表 链式存储链式存储：用：用一组任意的存储单元存储一组任意的存储单元存储线性表中的数据元线性表中的数据元素。用这种方法存储的线性表简称素。用这种方法存储的线性表简称线性链表线性链表。存储链表中数据元素的一组任意的存储单元可以是连续的，存储链表中数据元素的一组任意的存储单元可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。也可以是不连续的，甚至是零散分布在内存中的任意位置上的。链表中数据元素的逻辑顺序和物理顺序不一定相同。链表中数据元素的逻辑顺序和物理顺序不一定相同。为了表示数据元素为了表示数据元素aiai和和ai+1ai+1之间的逻辑关系，对数据元素之间的逻辑关系，对数据元素aiai来说，除了存储其本身的信息之外，还需存储一个指示其直接后来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（直接后继的存储位置）。这两部分信息组成数据元素继的信息（直接后继的存储位置）。这两部分信息组成数据元素aiai的存储映像，称为的存储映像，称为结点结点（nodenode）。）。链表是通表是通过每个每个结点的指点的指针域将域将线性表的性表的n个个结点按其点按其逻辑次序次序链接在一接在一起的。起的。每一个每一个结点只包含一个指点只包含一个指针域的域的链表，称表，称为单链表或表或线性性链表。表。为操作方便，操作方便，总是在是在链表的第一个表的第一个结点之前附点之前附设一个一个头结点点(头指指针)head指向第一个指向第一个结点。点。头结点的数据域可以不存点的数据域可以不存储任何信息任何信息(或或链表表长度等度等信息信息)。data next图图2-2 链表结点结构链表结点结构data：数据域，存放数据元素信息。：数据域，存放数据元素信息。next：指针域，存放结：指针域，存放结点的直接后继的地址，指针域中存储的信息称为指针或链。点的直接后继的地址，指针域中存储的信息称为指针或链。线性链表线性链表 结点包括两个域：数据域和指针域。结点包括两个域：数据域和指针域。n n个结点连接成个结点连接成一个链表，即为线性表的链式存储结构。一个链表，即为线性表的链式存储结构。线性链表线性链表 单链表的存取必须从头指针开始，头指针指示链表中第一个结点。单链表的存取必须从头指针开始，头指针指示链表中第一个结点。例例1 1、线性表、线性表L=(ZHAO，QIAN，SUN，LI，zhou,wu,zheng,wang)存储地址数据域指针域头指针H3117131925313743LIQIANSUNWANGWUZHAOZHENGZHOU43131NULL3771925HZHAOQIAN SUN LI ZHOU WU ZHENG WANG C语言中用结构指针来描述语言中用结构指针来描述(线性表的单链表存储结构线性表的单链表存储结构)typedef struct LNode ElemType data;/*数据域，保存结点的值数据域，保存结点的值*/struct Lnode *next;/*指针域指针域*/LNode，*LinkList;/*结点的类型结点的类型*/线性链表线性链表a1La2an带头结点的单链表 非空表L带头结点的单链表 空表在单链表中，每个元素的存储位置都包含在其直接前驱结点的信息之中。PP-next指向第2个元素，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)单链表的基本操作单链表的基本操作取单链表中的第i个元素:对于单链表，不能象顺序表中那样直接按序号i访问结点，而只能从链表的头结点出发，沿链域next逐个结点往下搜索，直到搜索到第i个结点为止。因此，链表是非随机存取结构。设单链表的长度为n，要查找表中第i个结点，仅当1in时，i的值是合法的。单链表的基本操作单链表的基本操作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 表示i太大;ji表示i为0 算法2.8移动指针p的频度：in：n次。时间复杂度:O(n)。单链表的基本操作单链表的基本操作单链表的插入 插入运算是将值为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)return ERROR;s=(LinkList)malloc(sizeof(Lnode);s-data=e;s-next=p-next;p-next=s;return ok;链表的长度为n，合法的插入位置是1in。算法的时间主要耗费移动指针p上，故时间复杂度亦为O(n)单链表的基本操作单链表的基本操作单链表的删除单链表的删除 删除单链表中的第删除单链表中的第i个结点。个结点。为了删除第为了删除第i个结点个结点ai，必须找到结点的存储地址。该存储地址是在其直接前，必须找到结点的存储地址。该存储地址是在其直接前趋结点趋结点ai-1的的next域中，因此，必须首先找到域中，因此，必须首先找到ai-1的存储位置的存储位置p，然后令，然后令pnext指指向向ai的直接后继结点，即把的直接后继结点，即把ai从链上摘下。最后释放结点从链上摘下。最后释放结点ai的空间。的空间。设单链表长度为设单链表长度为n，则删去第，则删去第i个结点仅当个结点仅当1 i n时是合法的。则当时是合法的。则当i=n+1时，时，虽然被删结点不存在，但其前趋结点却存在，是终端结点。故判断条件之一是虽然被删结点不存在，但其前趋结点却存在，是终端结点。故判断条件之一是pnext!=NULL。显然此算法的时间复杂度也是。显然此算法的时间复杂度也是O(n)(n)。算法描述算法描述(算法算法2.10)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.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，将它，将它们合并合并为以以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 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-next=pa;pc=pa;pa=pa-next ;else pc-next=pb;pc=pb;pb=pb-next ;pc-next=pa?pa:pb;free(Lb);/释放Lb头结点 循环链表循环链表 循循环链表表(Circular Linked List)：是一种是一种头尾相接的尾相接的链表。其特点是最后一个表。其特点是最后一个结点的指点的指针域指向域指向链表的表的头结点，整个点，整个链表的指表的指针域域链接成一个接成一个环。从循从循环链表的任意一个表的任意一个结点出点出发都可以找到都可以找到链表中表中的其它的其它结点，使得表点，使得表处理更加方便灵活。理更加方便灵活。图2-6是是带头结点的点的单循循环链表的示意表的示意图。空表空表图图2-6 单循环链表示意图单循环链表示意图非空表非空表a1 a2 anH H 有时，若在循环链表中设立尾指针而不设头指针，有时，若在循环链表中设立尾指针而不设头指针，可使某些操作简化。可使某些操作简化。循环链表的操作循环链表的操作 对于单循环链表，除链表的合并外，其它的操作和对于单循环链表，除链表的合并外，其它的操作和单线性链表基本上一致，仅仅需要在单线性链表操作算单线性链表基本上一致，仅仅需要在单线性链表操作算法基础上作以下简单修改：法基础上作以下简单修改：判断是否是空链表：判断是否是空链表：head-next=head;判断是否是表尾结点：判断是否是表尾结点：p-next=head;ABB,A 双向链表双向链表 双向双向链表表(Double Linked List):指的是构成指的是构成链表的表的每个每个结点中点中设立两个指立两个指针域：一个指向其直接前域：一个指向其直接前趋的指的指针域域prior，一个指向其直接后，一个指向其直接后继的指的指针域域next。这样形形成的成的链表中有两个方向不同的表中有两个方向不同的链，故称，故称为双向双向链表表。和和单链表表类似，双向似，双向链表一般增加表一般增加头指指针也能使双也能使双链表上的某些运算表上的某些运算变得方便。得方便。将将头结点和尾点和尾结点点链接起来也能构成循接起来也能构成循环链表，并表，并称之称之为双向循双向循环链表。表。双向双向链表是表是为了克服了克服单链表的表的单向性的缺陷而引入向性的缺陷而引入的。的。1 双向链表的结点及其类型定义双向链表的结点及其类型定义 双向双向链表的表的结点的点的类型定型定义如下。其如下。其结点形式如点形式如图2-7所示所示，带头结点的双向点的双向链表的形式如表的形式如图2-8所示所示。typedef struct Dulnode ElemType data;struct Dulnode *prior,*next;DulNode，*DulinkList;elementnextprior图图2-7 双向链表结点形式双向链表结点形式非空双向链表非空双向链表heada2a1an空双向链表空双向链表head图图2-8 带头结点的双向链表形式带头结点的双向链表形式 双向链表双向链表非空双向循环链表链表非空双向循环链表链表heada2a1an空双向循环链表空双向循环链表head图图2-8 带头结点的双向循环链表形式带头结点的双向循环链表形式 双向双向链表表结构具有构具有对称性，称性，设p指向双向指向双向链表中的某一表中的某一结点，点，则其其对称性可用下式描述：称性可用下式描述：p-prior-next=p=p-next-prior;结点点p的存的存储位置存放在其位置存放在其直接前直接前趋结点点p-prior的的直接直接后后继指指针域域中，同中，同时也存放在也存放在其直接后其直接后继结点点p-next的的直接直接前前趋指指针域域中。中。2 双向链表的基本操作双向链表的基本操作(1)双向双向链表的插入表的插入 将将值为e的的结点插入双向点插入双向链表中。插表中。插入前后入前后链表的表的变化如化如图2-9所示。所示。算法2.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)双向双向链表的表的结点点删除除 设要要删除除的的结点点为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-prior;free(p);return OK;注意：注意：与单链表的插入和删除操作不同的是，在双向链表中与单链表的插入和删除操作不同的是，在双向链表中插入插入和和删除删除必必须同时须同时修改两个方向上的指针域的指向修改两个方向上的指针域的指向。abcp12ac 重新定义线性链表及其基本操作单链表存在以下缺点：单链表存在以下缺点：1.求线性表的长度时不如顺序存储结构；求线性表的长度时不如顺序存储结构；2.在链表中，在链表中，“位序位序”的概念淡化，被数据元素在线性表中的的概念淡化，被数据元素在线性表中的 “位置位置”代替。代替。typedef struct LNode/节点类型 ElemType data;struct LNode *next;*Link,*PositionStatus MakeNode(Link&p,Elemtype e)viod FreeNode(Link&p)重新定义线性链表及其基本操作typedef struct /链表类型 Link head,tail;int len;LinkList链表的基本操作：1.结构的初始化和销毁结构：Status InitList(LinkList&L);/构造一个空的线性表 Status DestroyList(LinkList&L);/销毁线性链表L，L不再存在 重新定义线性链表及其基本操作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 LocateElem(LinkList L,ElemType e,Status(*compare)(ElemType,ElemType);Status ListTraverse(LinkList L,Status(*visit)();链表的基本操作：重新定义线性链表及其基本操作3.加工型操作：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);Status InsAfter(LinkList&L,Link&p,Link s);Status SetCurElen(Link&p,ElemType e);重新定义线性链表及其基本操作算法算法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.21 Status MergeList_L(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(*compare)(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个系个系数唯一确定数唯一确定。则在在计算机中可算机中可用用线性表性表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次多项式可写成次多项式可写成：若用一个长度为m且每个元素有两个数据项（系数项和指数项）的线性表便可唯一确定多项式Pn(x)。对应于线性表的两种存储结构，一元多项式也可以有两种存储结构表示方法。在实际的应用程序中取哪一种，则要视多项式作何种运算而定。2.4 一元多项式的表示和相加一元多项式的表示和相加抽象数据类型一元多项式的定义：2.4 一元多项式的表示和相加一元多项式的表示和相加-1A703198517B-181227-98如何实现用这种线性链表表示的多项式的加法运算？假设指针qa和qb分别指向多项式A和B中当前进行比较的某个节点，则比较两个节点的指数项有三种情况：1.指针qa所指节点的指数值指针qb所指节点的指数值，应摘取指针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-98qaqbC-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的结点的位置，并返回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,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);/返回一元多项式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 CreatPolyn(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,假如用户输入的顺序为：(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:/多项式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;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个空间，若申请失败，则说明系统没有（）可分配的存储空间。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-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与其直接后继结点互换位置。