ch2部分习题解答

1、 Chapter 2 线性表线性表练习：练习：找出以下算法中的错误和低效之处，并将它改写为一个找出以下算法中的错误和低效之处，并将它改写为一个 既正确又高效的算法。既正确又高效的算法。 int Deletek(SeqList *L, int i, int k) /*从顺序表从顺序表L中删除第中删除第i个元素起的个元素起的k个元素个元素*/ int count,j; if (i0|kL-size) printf(“n参数不合法！参数不合法！”); return 0; else for (count=1;countsize;j=i+1;j-) L-listj-1=L-listj; L-size-;

2、 return 1; 改进：改进：int Deletek(SeqList *L, int i, int k) /*从顺序表从顺序表L中删除第中删除第i个元素起的个元素起的k个元素个元素*/ int count,j; if (i0|kL-size) printf(“n参数不合法！参数不合法！”); return 0; else /*删除删除k个元素个元素*/ for(j=i+k;jsize;j+) L-listj-k=L-listj; L-size-=k; return 1; 2010考研题：考研题： 设将设将n(n1)个整数存放到一维数组个整数存放到一维数组R中。试设计一个在中。试设计一个在

3、时间和空间两方面尽可能高效的算法，将时间和空间两方面尽可能高效的算法，将R中的序列循环左中的序列循环左 移移P（0Pn）个位置，即将）个位置，即将R中的数据由（中的数据由（x0,x1,xn-1）变）变 换为（换为（xp,xp+1,xn-1,x0,x1,xp-1）。）。 (1) (1)算法设计思想算法设计思想 先将先将n个数（个数（x0,x1,xp,xn-1）原地逆置，得到）原地逆置，得到 （xn-1,xp,xp-1, x0），然后再将前），然后再将前n-p个和后个和后p个元素分个元素分 别原地逆置，得到最终结果：别原地逆置，得到最终结果：xp,xp+1,xn-1,x0,x1,xp-1。 算法可

4、以用两个函数实现。一个是逆置函数算法可以用两个函数实现。一个是逆置函数reverse()， 它将给定的数据逆置。另一个是循环左移函数它将给定的数据逆置。另一个是循环左移函数leftShift()， 它调用它调用reverse()函数三次，实现相应功能。函数三次，实现相应功能。(2)(2)算法实现算法实现 void reverse(int r, int left, int right) int i=left, j=right, temp; /*i等于左边界等于左边界left，j等于右边界等于右边界right*/ while(i0 & pnext!=NULL) s=p-next; if (s-da

5、ta=x) p-next=s-next; /*删除值为删除值为x的结点的结点*/ free(s); else p=s; 补充：补充：已知一个带头结点的递增有序单链表已知一个带头结点的递增有序单链表L，试编写一高效，试编写一高效 算法：删除该链表中所有元素值大于算法：删除该链表中所有元素值大于x且小于且小于y的结点。的结点。补充：补充： 已知两个带表头结点的非递减有序单链表，头指针分别已知两个带表头结点的非递减有序单链表，头指针分别 为为la和和lb，试编写算法，先将两个表合并为一个带表头结点，试编写算法，先将两个表合并为一个带表头结点 的非递减有序单链表，然后删除表中结点值（的非递减有序单链表

6、，然后删除表中结点值（data值）相同值）相同 的冗余结点，最后返回新单链表的头指针。的冗余结点，最后返回新单链表的头指针。 要求新单链表利用原来两个链表的结点空间，不另外生要求新单链表利用原来两个链表的结点空间，不另外生 成新结点。成新结点。void ListMergeDelete(SLNode *la, SLNode *lb, SLNode *lc) SLNode *pa,*pb,*pc; /*归并两个有序表归并两个有序表*/ (*lc)=la; pa=la-next; pb=lb-next; pc=la； while(pa&pb) if (pa-datadata) pc-next=pa;

7、 pc=pa; pa=pa-next; else pc-next=pb; pc=pb; pb=pb-next; if(pa) pc-next=pa; else pc-next=pb; free(lb); /*删除冗余结点删除冗余结点*/ pa=(*lc)-next; while(pa) pb=pa-next; while(pb&pb-data=pa-data) pc=pb; pb=pb-next; free(pc); pa-next=pb; pa=pb; 书书P46. 2-21（判断两个集合是否存在包含关系）（判断两个集合是否存在包含关系） int ListSetInclude(SLNode

8、*L1, SLNode *L2) /*判断带头结点的单链表判断带头结点的单链表L1中的数据元素是否都是单链表中的数据元素是否都是单链表L2 中的数据元素中的数据元素*/ SLNode *p1,*p2; p1=L1-next; while(p1!=NULL) p2=L2-next; while(p2!=NULL& p2-data!=p1-data) p2=p2-next; if(p2=NULL) return 0; p1=p1-next; return 1; 补充作业补充作业1：创建单链表（从表头创建单链表（从表头-表尾）表尾） int ListCreate(SLNode *la, int n)

9、 /*从键盘输入从键盘输入n个数，建立以个数，建立以la为头指针的带头结点的单链表为头指针的带头结点的单链表*/ int i; SLNode *p, *q; if (*la)=(SLNode*)malloc(sizeof(SLNode)=NULL) printf(“内存空间不足！内存空间不足！n”); return 0; q=*la; for (i=0; idata); q-next=p; q=p; /*新结点新结点p插入在表尾插入在表尾*/ q-next=NULL; return 1; 补充作业补充作业2： 已知一个带头结点的循环双向链表，从第二个结点已知一个带头结点的循环双向链表，从第二个

10、结点 至表尾递增有序。编写一个算法，将第一个结点删除并至表尾递增有序。编写一个算法，将第一个结点删除并 插入表中适当位置，使整个链表递增有序。插入表中适当位置，使整个链表递增有序。 void ListDIDL(DLNode *h) DLNode *p,*s; p=h-next; if (p!=h) h-next=p-next; p-next-prior=h; /*删除链表中的第一个结点，删除链表中的第一个结点， else return; 并用并用p指针保存指针保存*/ s=h-next; while(s!=h&p-datas-data) s=s-next; /*查找查找p结点的插入位置结点的插

11、入位置*/ p-prior=s-prior; s-prior-next=p; p-next=s; s-prior=p; /*p结点插入在结点插入在s结点之前结点之前*/ 2009考研题：考研题：已知一个带头结点的单链表，假设该链表只给已知一个带头结点的单链表，假设该链表只给出了头指针，在不改变链表的前提下，请设计一个尽可能高效出了头指针，在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第的算法，查找链表中倒数第k个结点（个结点（k为正整数），若查找成为正整数），若查找成功，算法输出该结点的功，算法输出该结点的data域的值，并返回域的值，并返回1，否则，只返回，否则，只返回0。 int Locatek(SLNode *h, in