第二章 线性表(参考答案)
在以下习题解答中，假定使用如下类型定义：
（1）顺序存储结构：
#define MAXSIZE 1024
typedef int ElemType;// 实际上，ElemType可以是任意类型
typedef struct
{ ElemType data[MAXSIZE];
int
last; // last表示终端结点在向量中的位置
}sequenlist;
（2）链式存储结构（单链表）
typedef struct node
{ElemType data;
struct node *next；
}linklist;
（3）链式存储结构（双链表）
typedef struct node
{ElemType data;
struct
node *prior,*next；
}dlinklist;
（4）静态链表
typedef struct
{ElemType data;
int next;
}node;
node sa[MAXSIZE];
2.1 头指针：指向链表的指针。因为对链表的所有操均需从头指针开始，即头指针具有标识链表的作用，所以链表的名字往往用头指针来标识。如：链表的头指针是la，往往简称为“链表la”。
头结点：为了链表操作统一，在链表第一元素结点（称为首元结点，或首结点）之前增加的一个结点，该结点称为头结点，其数据域不无实际意义（当然，也可以存储链表长度，这只是副产品），其指针域指向头结点。这样在插入和删除中头结点不变。
开始结点：即上面所讲第一个元素的结点。
2.2 只设尾指针的单循环链表，从尾指针出发能访问链表上的任何结点。
2·3
void insert(ElemType A[],int
elenum,ElemType x)
// 向量A目前有elenum个元素，且递增有序，本算法将x插入到向量A中，并保持向量的递增有序。
{ int i=0,j;
while
(i<elenum &&
A[i]<=x) i++; // 查找插入位置
for (j= elenum-1;j>=i;j--)
A[j+1]=A[j];// 向后移动元素
A[i]=x; // 插入元素
} // 算法结束
2·4
void rightrotate(ElemType A[],int
n,k)
// 以向量作存储结构，本算法将向量中的n个元素循环右移k位，且只用一个辅助空间。
{ int num=0;
// 计数，最终应等于n
int start=0;
// 记录开始位置（下标）
while
(num<n)
{ temp=A[start]; //暂存起点元素值，temp与向量中元素类型相同
empty=start; //保存空位置下标
next=(start-K+n) %n; // 计算下一右移元素的下标
while (next
!=start)
{ A[empty]=A[next];// 右移
num++; // 右移元素数加1
empty=next;
next=(next-K+n)
%n; // 计算新右移元素的下标
}
A[empty]=temp; // 把一轮右移中最后一个元素放到合适位置
num++;
start++;
// 起点增1，若num<n则开始下一轮右移。
}
} // 算法结束
算法二
算法思想：先将左面n-k个元素逆置，接着将右面k个元素逆置，最后再将这n个元素逆置。
void rightrotate(ElemType
A[],int n,k)
// 以向量作存储结构，本算法将向量中的n个元素循环右移k位，且只用一个辅助空间。
{ ElemType temp;
for(i=0;i<(n-k)/2;i++) //左面n-k个元素逆置
{temp=A[i];
A[i]=A[n-k-1-i]; A[n-k-1-i]=temp; }
for(i=1;i<=k;i++) //右面k个元素逆置
{temp=A[n-k-i];
A[n-k-i]=A[n-i]; A[n-i]=temp; }
for(i=0;i<n/2;i++) //全部n个元素逆置
{temp=A[i];
A[i]=A[n-1-i]; A[n-1-i]=temp; }
} // 算法结束
2·5
void insert(linklist *L,ElemType
x)
// 带头结点的单链表L递增有序，本算法将x插入到链表中，并保持链表的递增有序。
{ linklist *p=L->next, *pre=L，*s;
// p为工作指针，指向当前元素，pre为前驱指针，指向当前元素的前驱
s=(linklist *)malloc(sizeof(linklist));//申请空间，不判断溢出
s->data=x;
while (p &&
p->data<=x) {pre=p; p=p->next;} // 查找插入位置
pre->next=s;
s->next=p; // 插入元素
} // 算法结束
2·6
void invert(linklist *L)
// 本算法将带头结点的单链表L逆置。
//算法思想是先将头结点从表上摘下，然后从第一个元素结点开始，依次前插入以L为头结点的链表中。
{ linklist *p=L->next,*s;
// p为工作指针，指向当前元素，s为p的后继指针
L->next=null;//头结点摘下，指针域置空。算法中头指针L始终不变
while (p)
{s=p->next; // 保留后继结点的指针
p->next=L->next; // 逆置
L->next=p;
p=s;
// 将p指向下个待逆置结点
}
} // 算法结束
2·7
(1) int length1(linklist *L)
// 本算法计算带头结点的单链表L的长度
{ linklist *p=L->next; int i=0;
// p为工作指针，指向当前元素，i 表示链表的长度
while (p)
{ i++; p=p->next; }
return(i);
} // 算法结束
(2) int length1(node sa[MAXSIZE])
// 本算法计算静态链表s中元素的个数。
{ int p=sa[0].next, i=0;
// p为工作指针，指向当前元素，i 表示元素的个数，静态链指针等于-1时链表结束
while (p！=-1)
{ i++; p=sa[p].next; }
return(i);
} // 算法结束
2·8
void union_invert(linklist *A,*B,*C)
// A和B是两个带头结点的递增有序的单链表，本算法将两表合并成
// 一个带头结点的递减有序单链表C，利用原表空间。
{ linklist *pa=A->next,*pb=B->next,*C=A,*r;
// pa,pb为工作指针，分别指向A表和B表的当前元素，r为当前逆置
//元素的后继指针, 使逆置元素的表避免断开。
//算法思想是边合并边逆置，使递增有序的单链表合并为递减有序的单链表。
C->next=null;//头结点摘下，指针域置空。算法中头指针C始终不变
while (pa && pb) // 两表均不空时作
if
(pa->data<=pb->data) // 将A表中元素合并且逆置
{
r=pa->next; // 保留后继结点的指针
pa->next=C->next; // 逆置
C->next=pa;
pa=r;
// 恢复待逆置结点的指针
}
else
// 将B表中元素合并且逆置
{ r=pb->next;
// 保留后继结点的指针
pb->next=C->next; // 逆置
C->next=pb;
pb=r;
// 恢复待逆置结点的指针
}
// 以下while
(pa)和while (pb)语句，只执行一个
while (pa)
// 将A表中剩余元素逆置
{
r=pa->next; // 保留后继结点的指针
pa->next=C->next; // 逆置
C->next=pa;
pa=r;
// 恢复待逆置结点的指针
}
while (pb)
// 将B表中剩余元素逆置
{
r=pb->next; // 保留后继结点的指针
pb->next=C->next; // 逆置
C->next=pb;
pb=r;
// 恢复待逆置结点的指针
}
free(B);//释放B表头结点
} // 算法结束
2·9
void deleteprior(linklist *L)
// 长度大于1的单循环链表，既无头结点，也无头指针，本算法删除*s 的前驱结点
{ linklist *p=s->next,*pre=s;
// p为工作指针，指向当前元素，
// pre为前驱指针，指向当前元素*p的前驱
while (p->next!=s) {pre=p;
p=p->next;} // 查找*s的前驱
pre->next=s;
free(p); //
删除元素
} // 算法结束
2·10
void one_to_three(linklist
*A,*B,*C)
// A是带头结点的的单链表，其数据元素是字符字母、字符、数字字符、其他字符。本算法//将A表分成
// 三个带头结点的循环单链表A、B和C，分别含有字母、数字和其它符号的同一类字符，利用原表空间。
{ linklist *p=A->next,r;
// p为工作指针，指向A表的当前元素，r为当前元素的后继指针,使表避免断开。
//算法思想是取出当前元素，根据是字母、数字或其它符号，分别插入相应表中。
B=(linklist *)malloc(sizeof(linklist));//申请空间，不判断溢出
B->next=null; // 准备循环链表的头结点
C=(linklist *)malloc(sizeof(linklist));//申请空间，不判断溢出
C->next=null; // 准备循环链表的头结点
while(p)
{ r=p->next;
// 用以记住后继结点
if (p->data>=’a’&&p->data<=’z’||p->data>=’A’&&
p->data<=’Z’)
{p-> next=A->next; A->next=p;} // 将字母字符插入A表
else if (p->data>=’0’&&p->data<=’9’)
{p->next=B->next; B->next=p;} // 将数字字符插入B 表
else {p->next=C->next;
C->next=p;}// 将其它符号插入C 表
p=r; // 恢复后继结点的指针
}//while
} // 算法结束
2·11
void locate(dlinklist *L)
// L是带头结点的按访问频度递减的双向链表，本算法先查找数据x,
// 查找成功时结点的访问频度域增1，最后将该结点按频度递减插入链表中适当位置。
{ linklist *p=L->next,*q;
//p为工作指针，指向L表的当前元素，q为p的前驱，用于查找插入位置。
while (p
&& p->data !=x) p=p->next; // 查找值为x的结点。
if (!p) return (“不存在值为x的结点”);
else { p->freq++; // 令元素值为x的结点的freq域加1 。
p->next->prir=p->prior;
// 将p结点从链表上摘下。
p->prior->next=p->next;
q=p->prior;
// 以下查找p结点的插入位置
while (q !=L
&& q->freq<p-freq) q=q->prior;
p->next=q->next; q->next->prior=p;// 将p结点插入
p->prior=q;
q->next=p；
}
} // 算法结束