《线性表作业-答案.ppt》由会员分享，可在线阅读，更多相关《线性表作业-答案.ppt（18页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第二章 线性表作业评讲作业评讲 2.1 2.1 试描述头指针、头结点、开始结点的区别、并说明头指针试描述头指针、头结点、开始结点的区别、并说明头指针和头结点的作用。和头结点的作用。2.2 2.2 何时选用顺序表、何时选用链表作为线性表的存储结构为何时选用顺序表、何时选用链表作为线性表的存储结构为宜宜?2.3 2.3 在顺序表中插入和删除一个结点需平均移动多少个结点在顺序表中插入和删除一个结点需平均移动多少个结点?具体的移动次数取决于哪两个因素具体的移动次数取决于哪两个因素?2.4 2.4 为什么在单循环链表中设置尾指针比设置头指针更好为什么在单循环链表中设置尾指针比设置头指针更好?2.5 2.
2、5 在单链表、双链表和单循环链表中，若仅知道指针在单链表、双链表和单循环链表中，若仅知道指针p p指向指向某结点，不知道头指针，能否将结点某结点，不知道头指针，能否将结点*p*p从相应的链表中删去从相应的链表中删去?若可以，其时间复杂度各为多少若可以，其时间复杂度各为多少?作业：作业：2.5、2.7、2.9、2.11做在作业本上，交，其余堂下练习做在作业本上，交，其余堂下练习2.6 设有一个双链表，每个结点中除有prior、data和next三个域外，还有一个访问频度域freq，在链表被起用之前，其值均初始化为零。每当在链表进行一次LocateNode(L,s)运算时，令元素值为x的结点中fr
3、eq域的值加1，并调整表中结点的次序，使其按访问频度的递减序排列，以便使频繁访问的结点总是靠近表头。试写一符合上述要求的LocateNode运算的算法。2.7 写一算法在单链表上实现线性表的ListLength(L)运算。2.8 已知由单链表表示的线性表中，含有三类字符的数据元素(如：字母字符、数字字符和其它字符)，试编写算法构造三个以循环链表表示的线性表，使每个表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。2.9 假设在长度大于1的单循环链表中，既无头结点也无头指针。s为指向链表中某个结点的指针，试编写算法删除结点*s的直接前趋结点。2.10设顺序表L
4、是一个递增有序表，试写一算法，将x插入L中，并使L仍是一个有序表。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 Reve
5、rseList_L(LinkList&L);status ReverseList_L(LinkList&L);2.1 2.1 试描述头指针、头结点、开始结点的区别、并说明头指针和头试描述头指针、头结点、开始结点的区别、并说明头指针和头结点的作用。结点的作用。开始结点开始结点是指链表中的第一个结点，没有直接前趋是指链表中的第一个结点，没有直接前趋的那个结点。的那个结点。链表的链表的头指针头指针是一指向链表开始结点的指针是一指向链表开始结点的指针(没有头没有头结点时结点时)，单链表由头指针唯一确定，因此单链，单链表由头指针唯一确定，因此单链表可以用头指针的名字来命名。表可以用头指针的名字来命名。头
6、结点头结点在链表的开始结点之前附加的一个结点。有在链表的开始结点之前附加的一个结点。有了头结点之后，头指针指向头结点，不论链表了头结点之后，头指针指向头结点，不论链表否为空，头指针总是非空。而且头指针的设置否为空，头指针总是非空。而且头指针的设置使得对链表的第一个位置上的操作与在表其他使得对链表的第一个位置上的操作与在表其他位置上的操作一致位置上的操作一致(都是在某一结点之后都是在某一结点之后)。2.2 2.2 何时选用顺序表、何时选用链表作为线性表的存储何时选用顺序表、何时选用链表作为线性表的存储结构为宜结构为宜?1.1.基于空间的考虑。当要求存储的线性表基于空间的考虑。当要求存储的线性表长
7、度变化不大长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用易于事先确定其大小时，为了节约存储空间，宜采用顺顺序表序表；反之，当线性表长度变化大，难以估计其存储规；反之，当线性表长度变化大，难以估计其存储规模时，采用动态链表作为存储结构为好。模时，采用动态链表作为存储结构为好。2.基于时间的考虑。若线性表的操作主要是进行基于时间的考虑。若线性表的操作主要是进行查找，查找，很少做插入和删除很少做插入和删除操作时，采用操作时，采用顺序表顺序表做存储结构为宜；做存储结构为宜；反之，反之，若需要对线性表进行频繁地插入或删除等的操作若需要对线性表进行频繁地插入或删除等的操作时，宜采用链表做存储
8、结构。并且，若链表的插入和删时，宜采用链表做存储结构。并且，若链表的插入和删除主要发生在表的首尾两端，则采用尾指针表示的单循除主要发生在表的首尾两端，则采用尾指针表示的单循环链表为宜。环链表为宜。2.3 2.3 在顺序表中插入和删除一个结点需平均移动多少在顺序表中插入和删除一个结点需平均移动多少个结点个结点?具体的移动次数取决于哪两个因素具体的移动次数取决于哪两个因素?在等概率情况下，顺序表中插入一个结点需平均在等概率情况下，顺序表中插入一个结点需平均移动移动n/2个结点。个结点。删除一个结点需平均移动删除一个结点需平均移动(n-1)/2个结点。个结点。具体的移动次数取决于顺序表的长度具体的移
9、动次数取决于顺序表的长度n以及需插以及需插入或删除的位置入或删除的位置i。i越接近越接近n则所需移动的结点数越少。则所需移动的结点数越少。2.4 2.4 为什么在单循环链表中设置尾指针比设置头指针更为什么在单循环链表中设置尾指针比设置头指针更好好?尾指针是指向终端结点的指针，用它来表示单循环尾指针是指向终端结点的指针，用它来表示单循环链表可以使得链表可以使得查找链表的开始结点和终端结点都很方查找链表的开始结点和终端结点都很方便便，设一带头结点的单循环链表，其尾指针为，设一带头结点的单循环链表，其尾指针为rearrear，则，则开始结点和终端结点的位置分别是开始结点和终端结点的位置分别是rear
10、-next-next rear-next-next 和和 rear,rear,查找时间都是查找时间都是O(1)O(1)。若用头指针来表示该链表，则查找终端结点的时若用头指针来表示该链表，则查找终端结点的时间为间为O(n)。2.5 2.5 在单链表、双链表和单循环链表中，若仅知道指针在单链表、双链表和单循环链表中，若仅知道指针p p指指向某结点，不知道头指针，能否将结点向某结点，不知道头指针，能否将结点*p*p从相应的链表中删从相应的链表中删去去?若可以，其时间复杂度各为多少若可以，其时间复杂度各为多少?1.1.单链表。当我们知道指针单链表。当我们知道指针p p指向某结点时，能够根据该指指向某结
11、点时，能够根据该指针找到其直接后继，但是由于不知道其头指针，所以无法访针找到其直接后继，但是由于不知道其头指针，所以无法访问到问到p p指针指向的结点的直接前趋。因此指针指向的结点的直接前趋。因此无法删去该结点无法删去该结点。2.2.双链表。由于这样的链表提供双向链接，因此根据已知结双链表。由于这样的链表提供双向链接，因此根据已知结点可以查找到其直接前趋和直接后继，从而点可以查找到其直接前趋和直接后继，从而可以可以删除该结点。删除该结点。其时间复杂度为其时间复杂度为O(1)O(1)。3.单循环链表。根据已知结点位置，我们可以直接得到其单循环链表。根据已知结点位置，我们可以直接得到其后相邻的结点
12、位置后相邻的结点位置(直接后继直接后继)，又因为是循环链表，所以我，又因为是循环链表，所以我们可以通过查找，得到们可以通过查找，得到p结点的直接前趋。因此结点的直接前趋。因此可以可以删去删去p所指结点。其时间复杂度应为所指结点。其时间复杂度应为O(n)。2.62.6设有一个双链表，每个结点中除有设有一个双链表，每个结点中除有priorprior、datadata和和nextnext三个域外，还有一个访问三个域外，还有一个访问频度域频度域freqfreq，在链表被起用之前，其值均初始化为零。每当在链表进行一次，在链表被起用之前，其值均初始化为零。每当在链表进行一次LocateNode(L,s)L
13、ocateNode(L,s)运算时，令元素值为运算时，令元素值为x x的结点中的结点中freqfreq域的值加域的值加1 1，并调整表中结点，并调整表中结点的次序，使其按访问频度的递减序排列，以便使频繁访问的结点总是靠近表头。的次序，使其按访问频度的递减序排列，以便使频繁访问的结点总是靠近表头。试写一符合上述要求的试写一符合上述要求的LocateNodeLocateNode运算的算法。运算的算法。Status locatenode(dullinklist&L,elemtype x)Status locatenode(dullinklist&L,elemtype x)dulnode*p,*q;d
14、ulnode*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
15、-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;2.7 2.7 写一算法在单链表上实现线性表的写一算法在单链表上实现线性表的ListLength(L)ListLength(L)运算。运算。求单链表长只能用遍历的方法了，从头数到尾。算法如下：求单链表长只能用遍历的方法了，从头数到尾。算法如下：int ListLength(LinkList L)int len=0;ListNode*p;p=L;/设该表有头结点设该表有头结点wh
16、ile(p-next)p=p-next;len+;return len;2.82.8已知由单链表表示的线性表中，含有三类字符的数据元素已知由单链表表示的线性表中，含有三类字符的数据元素(如：字母字符、数字字符如：字母字符、数字字符和其它字符和其它字符)，试编写算法构造三个以循环链表表示的线性表，使每个表中只含同一类，试编写算法构造三个以循环链表表示的线性表，使每个表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。2.9 2.9 假设在长度大于假设在长度大于1 1的单循环链表中，既无头结点
17、也无头指针。的单循环链表中，既无头结点也无头指针。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-nex
18、t=s;/q-next=s;/删除结点删除结点free(p);/free(p);/释放空间释放空间return OK;return OK;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=
19、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 2.11 2.11 写出以下链表操作的算法写出以下链表操作的算法2 2）取得双向循环链表中第）取得双向循环链表中第）取得双向循环链表中第）取得双向循环链表中第i i个数据元素的位置指针个数据元素的位置指针个数据元素的位置指针个数据元素的位置指针status GetElemP_Dul(DuLinkList L,int i)status GetElemP_Dul(DuLinkList
20、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);2.11 2.11 写出以下链表操作的算法写出以下链表操作的算法3 3）将单链表置逆）将单链表置逆）将单链表置逆）将单链表置逆status ReverseList_L(LinkList&L)status ReverseLi
21、st_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;