数据结构教材勘误表.doc

数据结构（c语言版）清华大学出版社 秦锋主编勘误（红色字体为修改后的内容） 1. 教材30页 算法描述如下(假定顺序表A和B的存储空间足够)：void Inter_sec (PSeqList A, PSeqList B ) /*求集合A和B的交集，入口参数：指向顺序表的指针，返回值：无，结果存放在顺序表A中*/ int i=0; while(ilength) if(!Location_Seqlist(B,A-datai)/*B中无A-datai*/ Delete_SeqList(A,i+1); else i+;/*考察下一个元素*/ 2. 教材43页 算法如下：（考虑m1的特殊情况）int josephus_ LinkList (LinkList josephus_Link, int s, int m) /*求约瑟夫问题的出列元素序列，入口参数：已经存放数据的链表头指针，起始位置s，从1报数到m,出口参数：1表示成功，0表示表中没有元素*/LinkList p,pre； /*p指向当前结点，pre指向其前驱结点*/ int count； if ( ! josephus_Link) printf(“表中无元素”)； return (0)； /*找第s个元素*/ p= josephus_Link； for(count=1；countnext； printf(“输出约瑟夫序列：”)；while ( p!=p-next) /*输出 n-1个结点*/ pre=p-next; while(pre-next!=p)pre=pre-next;/*pre指针初始化，pre是p的前驱指针*/for(count=1；countnext； /*for*/printf(“%dt”, p-data)；pre-next=p-next；free(p)；p=pre-next；/*while*/printf(“%dt”,p-data)； /*输出最后一个结点*/ free(p)；return 1； 算法2.17该算法时间复杂度是O(n*m )。3. 教材45页 算法如下：void Add_Polynomial(P_Polynomial P1, P_Polynomial P2)/*两个一元多项式P1，P2求和，求和的结果保存到P1中*/P_Polynomial Pre_Item,Cur_Item1, Cur_Item2;/*分别保存扫描过程中的P1的前一分量，当前分量及P2的当前分量*/Pre_Item=P1; Cur_Item1=P1-next; Cur_Item2=P2-next;while(Cur_Item1&Cur_Item2) /*多项式P1,P2没有扫描完*/if(Cur_Item1-e = Cur_Item2-e) Cur_Item1-p= Cur_Item1-p+ Cur_Item2-p; if(Cur_Item1-p = 0) Pre_Item-next= Cur_Item1-next;free(Cur_Item1);Cur_Item1=Pre_Item-next;/*合并后系数为零，释放当前分量*/Cur_Item2= Cur_Item1-next; else Pre_Item=Cur_Item1; Cur_Item1=Cur_Item1-next;Cur_Item2=Cur_Item2-next;/*同时扫描下一项*/ /*第一种情形，P1和P2当前项的指数相等*/ elseif(Cur_Item1-e e)Pre_Item=Cur_Item1;Cur_Item1=Cur_Item1-next; /*第二种情形，P1当前项的指数小于P2的当前项指数*/ else /* 第三种情形:Cur_Item1-e Cur_Item2-e 时将多项式P2的当前分量加入到P1中*/ P_Polynomial temp; if(! (temp=( P_Polynomial)malloc(sizeof(Polynomial)printf(“内存不足！n”);exit(0); temp-p=Cur_Item2-p; temp-e=Cur_Item2-e; /*复制P2当前分量*/ temp-next=Cur_Item1; Pre_Item-next=temp; Pre_Item=Pre_Item-next; /*复制的当前分量插入P1中*/ Cur_Item2=Cur_Item2-next;/*end else*/ /*end while*/while(Cur_Item2) /*如果P2没有扫描完*/ P_Polynomial temp; if(!( temp=( P_Polynomial)malloc(sizeof(Polynomial)printf(“内存不足！n”);exit(0); temp-p=Cur_Item2-p; temp-e=Cur_Item2-e; temp-next=NULL; Pre_Item-next=temp; /*将复制的当前分量加到P1的尾部*/ Pre_Item=Pre_Item-next; Cur_Item2=Cur_Item2-next; /*end Add_Polynomial */算法2.184. 教材197页 算法如下：#define m 6 /* 迷宫的实际行 */#define n 8 /* 迷宫的实际列 */int path(int mazem+2m+2，item *move) /* maze 迷宫数组，move指向坐标增量数组的指针，item见【例3.2】(m,n)为迷宫出口点*/sqtype sqNUM+1;int front,rear；int x,y,i,j,v;front=rear=0;sq.x=1; sq.y=1; sq.pre=-1; rear+; /*入口点入队*/maze11=-1; /*走过的位置做标记*/while (frontrear) /*队列不空*/ x=sqfront.x ; y=sqfront .y ; /*取队头元素,但不出队列*/ for (v=0;v4;v+) /*向四个方向探测*/ i=x+movev.x; j=y+movev.y; if (mazeij=0) /*判断当前方向能走通?*/ /*能走通,将新的点进队列*/sqrear.x=i;sqrear.y=j; sqrear.pre=front;rear+;mazeij= -1; /*走过的位置做标记*/ if (i=m&j=n) /*到出口?*/ printpath(sq,rear); /*打印迷宫*/ return 1; /*for v*/ front+; /*当前点四个方向搜索完，取下一个点搜索*/ /*while*/return 0; /*path*/算法 7.115. 教材228页 int BinSearch(Sqlist s , KeyType k) /* 在表s中用折半查找法查找关键字k，若查找成功，则函数值为该元素在表中的位置，若查找失败，返回-1。*/ int low,mid,high； low=0；high=s.length-1； while(lowk) high=mid-1； /* 在左区间中查找 */ else low=mid+1； /* 在右区间中查找 */ return(-1)； /* 查找失败 */算法8.3 折半查找算法6. 教材301页 bool check3()/*检查第三题答案是否正确*/ bool ok=0； int i； i=question2； /*取第3题答案*/ switch (i) case 1: if(i=question0) ok=true； break； /*第1题是A吗？*/ case 2: if(i=question1) ok=true； brea