唐策善数据结构答案-用c语言描述原版

《唐策善数据结构答案-用c语言描述原版》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章线性表(参考答案) 2.1头指针：指向链表的指针。因为对链表的所有操均需从头指针开始，即头指针具有标识链表的作用，所以链表的名字往往用头指针来标识。如：链表的头指针是la，往往简称为“链表la”。头结点：为了链表操作统一，在链表第一元素结点（称为首元结点，或首结点）之前增加的一个结点，该结点称为头结点，其数据域不无实际意义（当然，也可以存储链表长度，这只是副产品），其指针域指向头结点。这样在插入和删除中头结点不变。开始结点：即上面所讲第一个元素的结点。2.2只设尾指针的单循环链表，从尾指针出发能访问链表上的任何结点。2·3设线性表存放在向量A[]的前elenum个分量中，且递

2、增有序。协议算法将X插入适当位置、voidinsert(ElemTypeA[],intelenum,ElemTypex)//向量A目前有elenum个元素，且递增有序，本算法将x插入到向量A中，并保持向量的递增有序。{inti=0,j;while(i=i;j--)A[j+1]=A[j];//向后移动元素A[i]=x;//插入元素}//算法结束 2·4voidrightrotate(ElemTypeA[],intn,k)//以向量作存储结构，本算法将向量中的n个元素循环右移k位，且只用一个辅助

3、空间。{intnum=0;//计数，最终应等于nintstart=0;//记录开始位置（下标）while(num

4、+;//起点增1，若numnext,*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->nex

5、t=p;//插入元素}//算法结束 2·6voidinvert(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)intlength

6、1(linklist*L)//本算法计算带头结点的单链表L的长度{linklist*p=L->next;inti=0;//p为工作指针，指向当前元素，i表示链表的长度while(p){i++;p=p->next;}return(i);}//算法结束(2)intlength1(nodesa[MAXSIZE])//本算法计算静态链表s中元素的个数。{intp=sa[0].next,i=0;//p为工作指针，指向当前元素，i表示元素的个数，静态链指针等于-1时链表结束while(p！=-1){i++;p=sa[p].next;}return(i);}//算法结束 2·8voidunion

7、_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;//头结点摘下，指针