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

第二章线性表(参考答案)在以下****题解答中,假定使用如下类型定义:(1)顺序存储结构:#defineMAXSIZE1024typedefintElemType;//实际上,ElemType可以是任意类型typedefstruct{ElemTypedata[MAXSIZE];intlast;//last表示终端结点在向量中的位置}sequenlist;(2)链式存储结构(单链表)typedefstructnode{ElemTypedata;structnode*next;}linklist;(3)链式存储结构(双链表)typedefstructnode{ElemTypedata;structnode*prior,*next;}dlinklist;(4)静态链表typedefstruct{ElemTypedata;intnext;}node;nodesa[MAXSIZE];:指向链表的指针。因为对链表的所有操均需从头指针开始,即头指针具有标识链表的作用,所以链表的名字往往用头指针来标识。如:链表的头指针是la,往往简称为“链表la”。头结点:为了链表操作统一,在链表第一元素结点(称为首元结点,或首结点)之前增加的一个结点,该结点称为头结点,其数据域不无实际意义(当然,也可以存储链表长度,这只是副产品),其指针域指向头结点。这样在插入和删除中头结点不变。开始结点:即上面所讲第一个元素的结点。,从尾指针出发能访问链表上的任何结点。2·3voidinsert(ElemTypeA[],intelenum,ElemTypex)//向量A目前有elenum个元素,且递增有序,本算法将x插入到向量A中,并保持向量的递增有序。{inti=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·4voidrightrotate(ElemTypeA[],intn,k)//以向量作存储结构,本算法将向量中的n个元素循环右移k位,且只用一个辅助空间。{intnum=0;//计数,最终应等于nintstart=0;//记录开始位置(下标)while(num<n){temp=A[start];//暂存起点元素值,temp与向量中元素类型相同empty=start;//保存空位置下标next=(start-K+n)%n;//计算下一右移元素的下标while(next!=start){A[empty]=A[next];//右移num++;//右移元素数加1empty=next;next=(next-K+n)%n;//计算新右移元素的下标}A[empty]=temp;//把一轮右移中最后一个元素放到合适位置num++;start++;//起点增1,若num<n则开始下一轮右移。}}//算法结束算法二算法思想:先将左面n-k个元素逆置,接着将右面k个元素逆置,最后再将这n个元素逆置。voidrightrotate(ElemTypeA[],intn,k)//以向量作存储结构,本算法将向量中的n个元素循环右移k位,且只用一个辅助空间。{ElemTypetemp;for(i=0;i<(n-k)/2;i++