线性表作业答案市公开课一等奖百校联赛获奖课件.pptx

第二章 线性表作业评讲作业评讲第1页 2.1 2.1 试描述头指针、头结点、开始结点区分、并说明头指针和试描述头指针、头结点、开始结点区分、并说明头指针和头结点作用。头结点作用。2.2 2.2 何时选取次序表、何时选取链表作为线性表存放结构为宜何时选取次序表、何时选取链表作为线性表存放结构为宜?2.3 2.3 在次序表中插入和删除一个结点需平均移动多少个结点在次序表中插入和删除一个结点需平均移动多少个结点?详细移动次数取决于哪两个原因详细移动次数取决于哪两个原因?2.4 2.4 为何在单循环链表中设置尾指针比设置头指针更加好为何在单循环链表中设置尾指针比设置头指针更加好?2.5 2.5 在单链表、双链表和单循环链表中，若仅知道指针在单链表、双链表和单循环链表中，若仅知道指针p p指向指向某结点，不知道头指针，能否将结点某结点，不知道头指针，能否将结点*p*p从对应链表中删去从对应链表中删去?若能够，其时间复杂度各为多少若能够，其时间复杂度各为多少?作业：作业：2.5、2.7、2.9、2.11做在作业本上，交，其余堂下练习做在作业本上，交，其余堂下练习第2页2.6 设有一个双链表，每个结点中除有prior、data和next三个域外，还有一个访问频度域freq，在链表被起用之前，其值均初始化为零。每当在链表进行一次LocateNode(L,s)运算时，令元素值为x结点中freq域值加1，并调整表中结点次序，使其按访问频度递减序排列，方便使频繁访问结点总是靠近表头。试写一符合上述要求LocateNode运算算法。2.7 写一算法在单链表上实现线性表ListLength(L)运算。第3页 2.8 已知由单链表表示线性表中，含有三类字符数据元素(如：字母字符、数字字符和其它字符)，试编写算法结构三个以循环链表表示线性表，使每个表中只含同一类字符，且利用原表中结点空间作为这三个表结点空间，头结点可另辟空间。2.9 假设在长度大于1单循环链表中，既无头结点也无头指针。s为指向链表中某个结点指针，试编写算法删除结点*s直接前趋结点。2.10设次序表L是一个递增有序表，试写一算法，将x插入L中，并使L仍是一个有序表。第4页2.11 写出以下链表操作算法1）创建一个空双向循环链表）创建一个空双向循环链表 status CreateList_Dul(DuLinkList&L);status CreateList_Dul(DuLinkList&L);2）取得双向循环链表中第）取得双向循环链表中第i个数据元素位置个数据元素位置指针指针 status GetElemP_Dul(DuLinkList L,int i);status GetElemP_Dul(DuLinkList L,int i);3）将单链表置逆）将单链表置逆status ReverseList_L(LinkList&L);status ReverseList_L(LinkList&L);第5页2.1 2.1 试描述头指针、头结点、开始结点区分、并说明头指针和头结试描述头指针、头结点、开始结点区分、并说明头指针和头结点作用。点作用。开始结点开始结点是指链表中第一个结点，没有直接前趋那是指链表中第一个结点，没有直接前趋那个结点。个结点。链表链表头指针头指针是一指向链表开始结点指针是一指向链表开始结点指针(没有头结点没有头结点时时)，单链表由头指针唯一确定，所以单链表能，单链表由头指针唯一确定，所以单链表能够用头指针名字来命名。够用头指针名字来命名。头结点头结点在链表开始结点之前附加一个结点。有了头在链表开始结点之前附加一个结点。有了头结点之后，头指针指向头结点，不论链表否为结点之后，头指针指向头结点，不论链表否为空，头指针总是非空。而且头指针设置使得对空，头指针总是非空。而且头指针设置使得对链表第一个位置上操作与在表其它位置上操作链表第一个位置上操作与在表其它位置上操作一致一致(都是在某一结点之后都是在某一结点之后)。第6页2.2 2.2 何时选取次序表、何时选取链表作为线性表存放结何时选取次序表、何时选取链表作为线性表存放结构为宜构为宜?1.1.基于空间考虑。当要求存放线性表基于空间考虑。当要求存放线性表长度改变不大长度改变不大，易，易于事先确定其大小时，为了节约存放空间，宜采取于事先确定其大小时，为了节约存放空间，宜采取次序次序表表；反之，当线性表长度改变大，难以预计其存放规模；反之，当线性表长度改变大，难以预计其存放规模时，采取动态链表作为存放结构为好。时，采取动态链表作为存放结构为好。2.基于时间考虑。若线性表操作主要是进行基于时间考虑。若线性表操作主要是进行查找，极少查找，极少做插入和删除做插入和删除操作时，采取操作时，采取次序表次序表做存放结构为宜；反做存放结构为宜；反之，之，若需要对线性表进行频繁地插入或删除等操作时，若需要对线性表进行频繁地插入或删除等操作时，宜采取链表做存放结构。而且，若链表插入和删除主要宜采取链表做存放结构。而且，若链表插入和删除主要发生在表首尾两端，则采取尾指针表示单循环链表为宜。发生在表首尾两端，则采取尾指针表示单循环链表为宜。第7页2.3 2.3 在次序表中插入和删除一个结点需平均移动多少在次序表中插入和删除一个结点需平均移动多少个结点个结点?详细移动次数取决于哪两个原因详细移动次数取决于哪两个原因?在等概率情况下，次序表中插入一个结点需平均在等概率情况下，次序表中插入一个结点需平均移动移动n/2个结点。个结点。删除一个结点需平均移动删除一个结点需平均移动(n-1)/2个结点。个结点。详细移动次数取决于次序表长度详细移动次数取决于次序表长度n以及需插入或以及需插入或删除位置删除位置i。i越靠近越靠近n则所需移动结点数越少。则所需移动结点数越少。第8页2.4 2.4 为何在单循环链表中设置尾指针比设置头指针更加为何在单循环链表中设置尾指针比设置头指针更加好好?尾指针是指向终端结点指针，用它来表示单循环链尾指针是指向终端结点指针，用它来表示单循环链表能够使得表能够使得查找链表开始结点和终端结点都很方便查找链表开始结点和终端结点都很方便，设一带头结点单循环链表，其尾指针为设一带头结点单循环链表，其尾指针为rearrear，则开始结，则开始结点和终端结点位置分别是点和终端结点位置分别是rear-next-next rear-next-next 和和 rear,rear,查查找时间都是找时间都是O(1)O(1)。若用头指针来表示该链表，则查找终端结点时间若用头指针来表示该链表，则查找终端结点时间为为O(n)。第9页2.5 2.5 在单链表、双链表和单循环链表中，若仅知道指针在单链表、双链表和单循环链表中，若仅知道指针p p指指向某结点，不知道头指针，能否将结点向某结点，不知道头指针，能否将结点*p*p从对应链表中删去从对应链表中删去?若能够，其时间复杂度各为多少若能够，其时间复杂度各为多少?1.1.单链表。当我们知道指针单链表。当我们知道指针p p指向某结点时，能够依据该指指向某结点时，能够依据该指针找到其直接后继，不过因为不知道其头指针，所以无法访针找到其直接后继，不过因为不知道其头指针，所以无法访问到问到p p指针指向结点直接前趋。所以指针指向结点直接前趋。所以无法删去该结点无法删去该结点。2.2.双链表。因为这么链表提供双向链接，所以依据已知结点双链表。因为这么链表提供双向链接，所以依据已知结点能够查找到其直接前趋和直接后继，从而能够查找到其直接前趋和直接后继，从而能够能够删除该结点。删除该结点。其时间复杂度为其时间复杂度为O(1)O(1)。3.单循环链表。依据已知结点位置，我们能够直接得到其单循环链表。依据已知结点位置，我们能够直接得到其后相邻结点位置后相邻结点位置(直接后继直接后继)，又因为是循环链表，所以我们，又因为是循环链表，所以我们能够经过查找，得到能够经过查找，得到p结点直接前趋。所以结点直接前趋。所以能够能够删去删去p所指所指结点。其时间复杂度应为结点。其时间复杂度应为O(n)。第10页2.62.6设有一个双链表，每个结点中除有设有一个双链表，每个结点中除有priorprior、datadata和和nextnext三个域外，还有一个访问三个域外，还有一个访问频度域频度域freqfreq，在链表被起用之前，其值均初始化为零。每当在链表进行一次，在链表被起用之前，其值均初始化为零。每当在链表进行一次LocateNode(L,s)LocateNode(L,s)运算时，令元素值为运算时，令元素值为x x结点中结点中freqfreq域值加域值加1 1，并调整表中结点次序，并调整表中结点次序，使其按访问频度递减序排列，方便使频繁访问结点总是靠近表头。试写一符合上使其按访问频度递减序排列，方便使频繁访问结点总是靠近表头。试写一符合上述要求述要求LocateNodeLocateNode运算算法。运算算法。Status locatenode(dullinklist&L,elemtype x)Status locatenode(dullinklist&L,elemtype x)dulnode*p,*q;dulnode*p,*q;p=q=L-next;p=q=L-next;while(p)while(p)if(p-data!=x)p=p-next;if(p-data!=x)p=p-next;else p-freq+;break;else p-freq+;break;while(q)while(q)if(q-freqp-freq)q=q-next;if(q-freqp-freq)q=q-next;else p-prior-next=p-next;p-next-prior=p-prior;else p-prior-next=p-next;p-next-prior=p-prior;p-next=q;p-prior=q-prior;p-next=q;p-prior=q-prior;q-prior-next=p;q-prior=p q-prior-next=p;q-prior=p return ok;return ok;第11页2.7 2.7 写一算法在单链表上实现线性表写一算法在单链表上实现线性表ListLength(L)ListLength(L)运算。运算。求单链表长只能用遍历方法了，从头数到尾。算法以下：求单链表长只能用遍历方法了，从头数到尾。算法以下：int ListLength(LinkList L)int len=0;ListNode*p;p=L;/设该表有头结点设该表有头结点while(p-next)p=p-next;len+;return len;第12页2.82.8已知由单链表表示线性表中，含有三类字符数据元素已知由单链表表示线性表中，含有三类字符数据元素(如：字母字符、数字字符和其如：字母字符、数字字符和其它字符它字符)，试编写算法结构三个以循环链表表示线性表，使每个表中只含同一类字符，试编写算法结构三个以循环链表表示线性表，使每个表中只含同一类字符，且利用原表中结点空间作为这三个表结点空间，头结点可另辟空间。且利用原表中结点空间作为这三个表结点空间，头结点可另辟空间。第13页 2.9 2.9 假设在长度大于假设在长度大于1 1单循环链表中，既无头结点也无头指针。单循环链表中，既无头结点也无头指针。s s为指向为指向链表中某个结点指针，试编写算法删除结点链表中某个结点指针，试编写算法删除结点*s*s直接前趋结点。直接前趋结点。status DeleteNode(ListNode*s)status DeleteNode(ListNode*s)/删除单循环链表中指定结点直接前趋结点删除单循环链表中指定结点直接前趋结点ListNode*p,*q;ListNode*p,*q;p=s;p=s;while(p-next-next!=s)while(p-next-next!=s)q=p;q=p;p=p-next;p=p-next;q-next=s;/q-next=s;/删除结点删除结点free(p);/free(p);/释放空间释放空间return OK;return OK;第14页 2.10 2.10 设次序表设次序表L L是一个递增有序表，试写一算法，将是一个递增有序表，试写一算法，将x x插入插入L L中，中，并使并使L L仍是一个有序表。仍是一个有序表。void InsertIncreaseList(Seqlist*L,Datatype x)void InsertIncreaseList(Seqlist*L,Datatype x)int i;int i;for(i=0;i length&L-data i x;i+);/for(i=0;i length&L-data i next=L;L-next=L;L-prior=L;L-prior=L;return(OK);return(OK);/见图见图见图见图2.14(b)P362.14(b)P36 第16页2.11 2.11 写出以下链表操作算法写出以下链表操作算法2 2）取得双向循环链表中第）取得双向循环链表中第）取得双向循环链表中第）取得双向循环链表中第i i个数据元素位置指针个数据元素位置指针个数据元素位置指针个数据元素位置指针status GetElemP_Dul(DuLinkList L,int i)status GetElemP_Dul(DuLinkList L,int i)elemtype*p;int a=1;elemtype*p;int a=1;if(i0)return ERROR;if(inext;p=L;p=p-next;while(anext;a+;while(anext;a+;If(a=i)return(p);else return(ERROR);If(a=i)return(p);else return(ERROR);第17页2.11 2.11 写出以下链表操作算法写出以下链表操作算法3 3）将单链表置逆）将单链表置逆）将单链表置逆）将单链表置逆status ReverseList_L(LinkList&L)status ReverseList_L(LinkList&L)Lnode*p1,*p2,*p3;Lnode*p1,*p2,*p3;If(L-next=NULL)return OK;If(L-next=NULL)return OK;else else p1=L;p1-next=NULL;p1=L;p1-next=NULL;P2=L-next;P2=L-next;P3=p2-next;P3=p2-next;While(p2!=NULL)While(p2!=NULL)p2-next=p1;p2-next=p1;p1=p2;p2=p3;p1=p2;p2=p3;if(p2!=NULL)p3=p3-next;if(p2!=NULL)p3=p3-next;L=p1;L=p1;return OK;return OK;第18页