2.7习题
1描述头指针、头结点、首元结点的区别，并说明头指针和头结点的作用。
2在顺序表中插入和删除一个结点需平均移动多少个元素？具体的移动次数取决于哪两个因素？
3在单链表和双向链表中，从当前结点出发是否能访问到任何一个结点？
4若较频繁地对一个线性表进行插入和删除操作，该线性表宜采用何种存储结构？为什么？
5有线性表(a1,a2,…,ai－1,ai,ai+1,…,an)，采用单链表存储，头指针为H，每个结点中存放线性表中的一个元素，现查找某个元素值为x的结点。分别写出下面三种情况的查找语句，要求查找时间尽量短。
（1）线性表中元素无序。
（2）线性表中元素递增有序。
（3）线性表中元素递减有序。
6下面是一个算法的核心部分，试说明该算法的功能。
pre=L->next;//L是一个带头结点的单链表，结点有数据域data和指针域next
if(pre!=NULL)
while(pre->next!=NULL){
p=pre->next;
if(p->data>=pre->data) pre=p;
else return(FALSE);
}
return(TUURE);
7设pa、pb分别指向两个带头结点的有序（从小到大）单链表。阅读下列程序，并回答以下问题：
（1）程序的功能。
（2）s1、s2中的值的含义。
（3）pa、pb中的值的含义。
void exam(LinkList pa,LinkList pa){
p1=pa->next;p2=pb->next;pa->next=NULL;s1=0;s2=0;
while(p1&&p2){
switch{
case(p1->datadata):p=p1;p1=p1->next;s2++;delete(p);
case(p1->data>p2->data):p2=p2->next;
case(p1->data=p2->data):p=p1;p1=p1->next;p->next=pa->next;
pa->next=p;p2=p2->next;s1++;
}
while(p1){p=p1;p1=p1->next;delete(p);s2++}
}
8假设长度大于1的循环单链表中，既无头结点也无头指针，p为指向该链表中某一结点的指针，编写算法删除该结点的前驱结点。
9已知两个单链表La和Lb分别表示两个集合，其元素递增排列。编写算法求其交集Lc，要求Lc以元素递减的单链表形式存储。
10已知单链表L是一个递增有序表，试编写一个高效算法，删除表中值大于min且小于max的结点（若表中有这样的结点），同时释放被删除的结点的空间，这里min和max是两个给定的参数。请分析你的算法的时间复杂度。
11已知非空单链表的头指针为L，试编写算法，交换p所指结点与其下一个结点在链表中的位置（设p指向的不是链表中的最后一个结点）。
12线性表中有n个元素，每个元素是一个字符，现存于数组R［n］中，试编写算法，使R中元素的字符按字母字符、数字字符和其他字符的顺序排列。要求利用原来的空间，元素移动次数最小。
13试编写在带头结点的单链表中删除（一个）最小值结点的（高效）算法。
14已知两个单链表La和Lb，其元素递增排列。编写算法，将La和Lb归并成一个单链表Lc，其元素递减排列（允许表中有相同的元素），要求不另辟新的空间。
15设以带头结点的双向循环链表表示的线性表L=(a1,a2,…,ai－1,ai,ai+1,…,an)。试编写一个时间复杂度为O(n)的算法，将L改造为L=(a1,a3,…,an,…,a4,a2)。
16设有一个双向循环链表，每个结点除有prior、data和next三个域外，还有一个访问频度域frep。在链表被启用之前，频度域frep的值为0，而每当对链表进行一次LocateElem(L，e)的操作后，被访问的结点的频度域frep的值增1，同时调整链表中结点之间的顺序，使其按发文频度非递增的次序顺序排列，以便始终保持被频繁访问的结点总是靠近表头结点。试写出符合上述要求的LocateElem操作的算法。