第二章线性表作业-答案

1、第二章 线性表,作业评讲,2.1 试描述头指针、头结点、开始结点的区别、并说明头指针和头结点的作用。 2.2 何时选用顺序表、何时选用链表作为线性表的存储结构为宜? 2.3 在顺序表中插入和删除一个结点需平均移动多少个结点?具体的移动次数取决于哪两个因素? 2.4 为什么在单循环链表中设置尾指针比设置头指针更好? 2.5 在单链表、双链表和单循环链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点*p从相应的链表中删去?若可以，其时间复杂度各为多少?,作业： 2.5、 2.7、2.9、2.11做在作业本上，交，其余堂下练习,2.6 设有一个双链表，每个结点中除有prior、data和ne

2、xt三个域外，还有一个访问频度域freq，在链表被起用之前，其值均初始化为零。每当在链表进行一次LocateNode(L,s)运算时，令元素值为x的结点中freq域的值加1，并调整表中结点的次序，使其按访问频度的递减序排列，以便使频繁访问的结点总是靠近表头。试写一符合上述要求的LocateNode运算的算法。 2.7 写一算法在单链表上实现线性表的ListLength(L)运算。,2.8 已知由单链表表示的线性表中，含有三类字符的数据元素(如：字母字符、数字字符和其它字符)，试编写算法构造三个以循环链表表示的线性表，使每个表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结

3、点可另辟空间。 2.9 假设在长度大于1的单循环链表中，既无头结点也无头指针。s为指向链表中某个结点的指针，试编写算法删除结点*s的直接前趋结点。 2.10设顺序表L是一个递增有序表，试写一算法，将x插入L中，并使L仍是一个有序表。,2.11 写出以下链表操作的算法 1）创建一个空的双向循环链表 status CreateList_Dul(DuLinkList ,2.1 试描述头指针、头结点、开始结点的区别、并说明头指针和头结点的作用。,开始结点是指链表中的第一个结点，没有直接前趋的那个结点。 链表的头指针是一指向链表开始结点的指针(没有头结点时)，单链表由头指针唯一确定，因此单链表可以用头指

4、针的名字来命名。 头结点在链表的开始结点之前附加的一个结点。有了头结点之后，头指针指向头结点，不论链表否为空，头指针总是非空。而且头指针的设置使得对链表的第一个位置上的操作与在表其他位置上的操作一致(都是在某一结点之后)。,2.2 何时选用顺序表、何时选用链表作为线性表的存储结构为宜? 1.基于空间的考虑。当要求存储的线性表长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表；反之，当线性表长度变化大，难以估计其存储规模时，采用动态链表作为存储结构为好。 2.基于时间的考虑。若线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜；反之， 若需要对线性表进行

5、频繁地插入或删除等的操作时，宜采用链表做存储结构。并且，若链表的插入和删除主要发生在表的首尾两端，则采用尾指针表示的单循环链表为宜。,2.3 在顺序表中插入和删除一个结点需平均移动多少个结点?具体的移动次数取决于哪两个因素? 在等概率情况下，顺序表中插入一个结点需平均移动n/2个结点。 删除一个结点需平均移动(n-1)/2个结点。 具体的移动次数取决于顺序表的长度n以及需插入或删除的位置i。i越接近n则所需移动的结点数越少。,2.4 为什么在单循环链表中设置尾指针比设置头指针更好? 尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便，设一带头结点的单循

6、环链表，其尾指针为rear，则开始结点和终端结点的位置分别是rear-next-next 和 rear, 查找时间都是O(1)。 若用头指针来表示该链表，则查找终端结点的时间为O(n)。,2.5 在单链表、双链表和单循环链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点*p从相应的链表中删去?若可以，其时间复杂度各为多少? 1. 单链表。当我们知道指针p指向某结点时，能够根据该指针找到其直接后继，但是由于不知道其头指针，所以无法访问到p指针指向的结点的直接前趋。因此无法删去该结点。 2. 双链表。由于这样的链表提供双向链接，因此根据已知结点可以查找到其直接前趋和直接后继，从而可以删除该

7、结点。其时间复杂度为O(1)。 3. 单循环链表。根据已知结点位置，我们可以直接得到其后相邻的结点位置(直接后继)，又因为是循环链表，所以我们可以通过查找，得到p结点的直接前趋。因此可以删去p所指结点。其时间复杂度应为O(n)。,2.6设有一个双链表，每个结点中除有prior、data和next三个域外，还有一个访问频度域freq，在链表被起用之前，其值均初始化为零。每当在链表进行一次LocateNode(L,s)运算时，令元素值为x的结点中freq域的值加1，并调整表中结点的次序，使其按访问频度的递减序排列，以便使频繁访问的结点总是靠近表头。试写一符合上述要求的LocateNode运算的算法

8、。,Status locatenode(dullinklist ,2.7 写一算法在单链表上实现线性表的ListLength(L)运算。 求单链表长只能用遍历的方法了，从头数到尾。算法如下： int ListLength ( LinkList L )int len=0 ;ListNode *p;p=L; /设该表有头结点while ( p-next )p=p-next;len+;return len;,2.8已知由单链表表示的线性表中，含有三类字符的数据元素(如：字母字符、数字字符和其它字符)，试编写算法构造三个以循环链表表示的线性表，使每个表中只含同一类的字符，且利用原表中的结点空间作为这三

9、个表的结点空间，头结点可另辟空间。,2.9 假设在长度大于1的单循环链表中，既无头结点也无头指针。s为指向链表中某个结点的指针，试编写算法删除结点*s的直接前趋结点。 status DeleteNode( ListNode *s)/删除单循环链表中指定结点的直接前趋结点ListNode *p, *q;p=s;while( p-next-next!=s) q=p; p=p-next;q-next=s; /删除结点free(p); /释放空间return OK; ,2.10 设顺序表L是一个递增有序表，试写一算法，将x插入L中，并使L仍是一个有序表。 void InsertIncreaseList( Seqlist *L , Datatype x )int i;for ( i=0 ; i length / 调用顺序表插入函数p24 ,2.11 写出以下链表操作的算法1）创建一个空的双向循环链表,status CreateList_Dul(DuLinkList /见图2.14(b) P36 ,2.11 写出以下链表操作的算法2）取得双向循环链表中第i个数据元素的位置指针,status GetElemP_Dul(DuLinkList L,