数据结构课后习题答案第二章.doc

第二章线性表(参考答案)
 
在以下****题解答中,假定使用如下类型定义:
(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];
 
头指针:指向链表的指针。因为对链表的所有操均需从头指针开始,即头指针具有标识链表的作用,所以链表的名字往往用头指针来标识。如:链表的头指针是la,往往简称为“链表la”。
头结点:为了链表操作统一,在链表第一元素结点(称为首元结点,或首结点)之前增加的一个结点,该结点称为头结点,其数据域不无实际意义(当然,也可以存储链表长度,这只是副产品),其指针域指向头结点。这样在插入和删除中头结点不变。
开始结点:即上面所讲第一个元素的结点。
只设尾指针的单循环链表,从尾指针出发能访问链表上的任何结点。
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; // 把一轮右移