第二章线性表第二章线性表作业评讲作业评讲2.12.1试描述头指针、头结点、开始结点的区别、并说明头指针试描述头指针、头结点、开始结点的区别、并说明头指针和头结点的作用。和头结点的作用。2.22.2何时选用顺序表、何时选用链表作为线性表的存储结构为何时选用顺序表、何时选用链表作为线性表的存储结构为宜宜??2.32.3在顺序表中插入和删除一个结点需平均移动多少个结点在顺序表中插入和删除一个结点需平均移动多少个结点??具体的移动次数取决于哪两个因素具体的移动次数取决于哪两个因素??2.42.4为什么在单循环链表中设置尾指针比设置头指针更好为什么在单循环链表中设置尾指针比设置头指针更好??2.52.5在单链表、双链表和单循环链表中，若仅知道指针在单链表、双链表和单循环链表中，若仅知道指针pp指向指向某结点，不知道头指针，能否将结点某结点，不知道头指针，能否将结点*p*p从相应的链表中删从相应的链表中删去去??若可以，其时间复杂度各为多少若可以，其时间复杂度各为多少??作业：2.5、2.7、2.9、2.11做在作业本上，交，其余堂下练习2.62.6设有一个双链表，每个结点中除有设有一个双链表，每个结点中除有priorprior、、datadata和和nextnext三个域外，还有一个访问频度三个域外，还有一个访问频度域域freqfreq，在链表被起用之前，其值均初始，在链表被起用之前，其值均初始化为零。每当在链表进行一次化为零。每当在链表进行一次LocateNodeLocateNode(L,s)(L,s)运算时，令元素值为运算时，令元素值为xx的结点中的结点中freqfreq域的值加域的值加11，并调整表中结点的次序，使其，并调整表中结点的次序，使其按访问频度的递减序排列，以便使频繁访问按访问频度的递减序排列，以便使频繁访问的结点总是靠近表头。试写一符合上述要求的结点总是靠近表头。试写一符合上述要求的的LocateNodeLocateNode运算的算法。运算的算法。2.72.7写一算法在单链表上实现线性表的写一算法在单链表上实现线性表的ListLListLength(L)ength(L)运算。运算。2.82.8已知由单链表表示的线性表中，含有三类已知由单链表表示的线性表中，含有三类字符的数据元素字符的数据元素((如：字母字符、数字字符和如：字母字符、数字字符和其它字符其它字符))，试编写算法构造三个以循环链表，试编写算法构造三个以循环链表表示的线性表，使每个表中只含同一类的字符，表示的线性表，使每个表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。空间，头结点可另辟空间。2.92.9假设在长度大于假设在长度大于11的单循环链表中，既无的单循环链表中，既无头结点也无头指针。头结点也无头指针。ss为指向链表中某个结点为指向链表中某个结点的指针，试编写算法删除结点的指针，试编写算法删除结点*s*s的直接前趋的直接前趋结点。结点。2.102.10设顺序表设顺序表LL是一个递增有序表，试写一算是一个递增有序表，试写一算法，将法，将xx插入插入LL中，并使中，并使LL仍是一个有序表。仍是一个有序表。2.112.11写出以下链表操作的算法写出以下链表操作的算法11）创建一个空的双向循环链表）创建一个空的双向循环链表•statusCreateList_Dul(DuLinkList&L);statusCreateList_Dul(DuLinkList&L);22）取得双向循环链表中第）取得双向循环链表中第ii个数据元素的个数据元素的位置指针位置指针•statusGetElemP_Dul(DuLinkListL,inti);statusGetElemP_Dul(DuLinkListL,inti);33）将单链表置逆）将单链表置逆statusReverseList_L(LinkList&L);statusReverseList_L(LinkList&L);2.12.1试描述头指针、头结点、开始结点的区别、并说明头指针和头试描述头指针、头结点、开始结点的区别、并说明头指针和头结点的作用。结点的作用。开始结点开始结点是指链表中的第一个结点，没有直接前趋是指链表中的第一个结点，没有直接前趋的那个结点。的那个结点。链表的链表的头指针头指针是一指向链表开始结点的指针是一指向链表开始结点的指针((没有没有头结点时头结点时))，单链表由头指针唯一确定，因此单，单链表由头指针唯一确定，因此单链表可以用...
