数据结构课后习题参考答案
第一章 绪论 1.3 (1) O(n)
(2) (2) O(n) (3) (3) O(n)
(4) (4) O(n12
)
(5) (5) 执行程序段的过程中，x,y值变化如下：
循环次数 x y
0（初始） 91 100 1 92 100 2 93 100 …… …… …… 9 100 100 10 101 100 11 91 99 12 92 100 …… …… …… 20 101 99 21 91 98 …… …… …… 30 101 98 31 91 97
到y=0时，要执行10*100次，可记为O（10*y）=O（n）1.5 2100 , (23)n , log2n , n12 , n32 , (32)n , nlog2n , 2 n , n! 第二章 线性表(参考答案)
在以下习题解答中，假定使用如下类型定义： （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;
1 , n n
}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
void rightrotate(ElemType A[],int n,k)
以向量作存储结构，本算法将向量中的n个元素循环右移k位，且只用一个辅助空间。 { int num=0; 计数，最终应等于n int start=0; 记录开始位置（下标） while (num { 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-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 {temp=A[i]; A[i]=A[n-1-i]; A[n-1-i]=temp; } 2 } 算法结束 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为当前逆 3 置 元素的后继指针, 使逆置元素的表避免断开。 算法思想是边合并边逆置，使递增有序的单链表合并为递减有序的单链表。 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 的前驱结点 4 { 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->next=q->next; q->next->prior=p; 将p结点插入 p->prior=q; q->next=p； } } 算法结束 第三章 栈和队列(参考答案) 从数据结构角度看，栈和队列是操作受限的线性结构，其顺序存储结构 和链式存储结构的定义与线性表相同，请参考教材，这里不再重复。 5