数据机构作业.ppt

1、作业2.4,int Insert_SeqList(SeqList *L, int x) /*把x插入递增有序表L中*/ if(Llast+1MAXSIZE) return ERROR; for(i=Llast; Lelemix /*Insert_SeqList */,作业2.7 顺序表的就地逆置,void reverse(SeqList *L)/顺序表的就地逆置 for(i=0,j=Llast; inext; L-next=NULL; while(p) q=p; p=p-next; q-next=Lnext; /*把L的元素逐个插入新表表头之后*/ Lnext=q; /*LinkList_re

2、verse*/ 分析:本算法的思想是,逐个地把L的当前元素q插入新的链表头部,p为新表表头.,Int del_node(Linklist s,elemtype *e) Node *p,*pre; if(s-next=s)return error; pre=s;p=s-next; while(p-next!=s) pre=p;p=p-next; pre-next=s; *e=p-data; free(p); return ok; ,作业2.9循环链表的删除,作业2.11 A表和B表合并为C表,void merge1(LinkList *A,LinkList *B,LinkList *C) /*链

3、表A和B合并为C,A和B的元素间隔排列,且用原空间*/ Node *p, *q; p=A-next; q=B-next; C=A; while(p /*while*/ /*merge1 */,int IsReverse() SeqStack s; char e; InitStack( /IsReverse,3-5判断输入的字符串中 int front, rear,tag; SeqQueue;,注意：tag域的值为0表示“空”,1表示“非空,3-8带tag域的循环队列入队算法,int EnterQueue(SeqQueue *Q,int x) if(Qtag=1 /EnterQueue,3.8带

4、tag域的循环队列出队算法,int DeleteQueue(SeqQueue *Q, int *x) if(Q-tag=0) return FALSE; * x=Q-element Q-front; Q-front=(Q-front+1)%MAXSIZE; if(Q-front=Q-rear) Q-tag=0; /队列空 return TRUE; /DeleteQueue 分析:当循环队列容量较小而队列中每个元素占的空间较多时,此种表示方法可以节约较多的存储空间,较有价值。,4.3题参考答案 /串结点定义 typedef struct snode char ch; struct snode *

5、next; SNode; /链串定义 typedef struct SNode *head; SNode *tail; int len; LinkString;,/将串常量chars赋值给串S int StriAsign(LinkString *S,char *chars) SNode *new,*p; int i=0; /初始化串S为空链串 new=(SNode *)malloc(sizeof(SNode); if(!new) return(ERROR); new-next=null; S-head=new; S-tail=p=new; /建立链串S，并将串chars复制到S中 while(

6、charsi!=0) new=(SNode *)malloc(sizeof(SNode); new-ch=charsi; p-next=new; p=new; i+; p-next=null; /链表的表尾 S-tail=p; S-len=i; /串长度 return(OK); ,/两个串的比较 int StrCompare(LinkString *S,LinkString *T) SNode *q,*p; p=S-head-next; q=T-head-next; /p,q分别指向两个串的开始 while(p /如果对应位置的字符都相等，返回串的长度差 ,5.1,5.3,5.1(1) 6*8

7、*6=288 (2) 1000+(5*8+7)*6=1282 (3) 1000+(2*8+5)*6=1126 (4) 1000+(5*6+2)*6=1192 5.3(1) k=(i-1)*3-1+(j-i+1)+1=2*(i-1)+j (2) i=k/3+1; j=,(k/3+1)+(k%3-1)=k/3+k%3,5.4利用一个辅助向量空间的矩阵快速转置法,FastTransposeMatrix( TSMatrix A , TSMatrix *B) /* 利用一个辅助向量空间的矩阵快速转置法 */ int col, t, p, q, posMAXSIZE; B-len=A.len; B-n=A

8、.m; B-m=A.n; if( B-len) for( t=1; t=1; t-) post=post-1;,for( p=1; pdataq.row=A.datap.col; B-dataq.col=A.datap.row; B-dataq.e=A.datap.e; poscol+; ,FastTransposeMatrix( TSMatrix A , TSMatrix *B) /* 利用一个辅助空间的矩阵快速转置法 */ int col, p, q, pos; B-len=A.len; B-n=A.m; B-m=A.n; if( B-len) for( p=1; pdatapos.row

9、=A.datap.col; B-datapos.col=A.datap.row; B-datapos.e=A.datap.e; ,6.4,6.5(1)右单枝树 (2)左单枝树 (3)单根树或者空树,6.9,0,0,0,0,0,0,0,1,1,6.24交换左右子树算法,void exchangechild(BiTree t) BiTNode *p; if(t) p=t-lchild; t-lchild=t-rchild; t-rchild=p; exchangechild(t-lchild); exchangechild(t-rchild); /*注意：不能用中序遍历来交换*/,7.3用Dijk

10、stra算法求顶点1到其余顶点的最短路径的过程： 初始状态：S=V1； 第一步：v1到v3的路径v1,v3；长度15；新 S=V1，v3； 第二步： v1到v2的路径v1,v3,v2；长度19；新 S=V1，v3，v2；,第三步： v1到v5的路径v1,v3,v5；长度25；新 S=V1，v3，v2，v5；,第四步： v1到v4的路径v1,v3,v2,v4；长度29；新 S=V1，v3，v2，v5,v4；,第五步： v1到v6的路径v1,v3,v2,v4,v6；长度44；新 S=V1，v3，v2，v5,v4,v6；,7.14,普里姆算法：,7.12,A: V1,V2,V3,V8,V4,V5,V

11、7,V6; V1,V2,V3,V8, V5,V7, V4,V6; B: V1,V2,V4,V6,V5,V3,V7,V8; V1,V2,V4,V6,V3,V5,V7,V8; C: V1,V2,V4,V6,V5,V3,V7,V8; D: V1,V2,V5,V7,V8; E: V1,V6,V5,V7,V8; (97),8.1,若对大小均为N的有序表和无序表分别进行顺序查找。在等 概率查找时，讨论两者在下列情况下的平均查找长度： （1）查找不成功，两者ASL不相等；,（2）查找成功且表中只有一个关键字等于给定值K的记录时，平均查找长度相同：（n+1）/2；,（3）查找成功且表中有若干个关键字等于给定值

12、K的记录，一次查找要求找出所有记录时，平均查找长度不相同：,8.2,ASL= (1+2*2+3*4+4*3)/10 = 2.9,ASLsucc=(1+1+2+2+1+1+2+6)/8 = 16/8=2 ASLunsucc = (2+1+8+7+6+5+4+3+2+1+1)/11 = 40/11,8.5,8.12（1）,ASLsucc = (1+2*2+3*3+4*3+5*2+6*1)/12 = 42/12,（2）长度为12的有序表在等概率时： ASLsucc = （1223445)/12 =37/12,ASLsucc = （1223444+5)/12 =38/12,(3),一趟结果：（170，

13、087，275，061，426，503，897，512，653，908）,第二躺： d2=4 （170， 087， 275， 061， 426， 503， 897， 512， 653， 908）,二躺结果： （170， 087， 275， 061， 426， 503， 897， 512， 653， 908）,三躺结果：d3=3 （170， 087， 275， 061， 426， 503， 897， 512， 653， 908） （ 061 ， 087， 275， 170 ， 426， 503， 897， 512， 653， 908） 四躺结果：d4=2 （ 061 ， 087， 275， 17

14、0 ， 426， 503， 653 ， 512， 897 ， 908） 五躺结果：d5=1 （ 061 ， 087， 170 ， 275 ， 426， 503， 512， 653 ， 897 ， 908）,快速排序: 一趟: 426,087,275,061,170 503 897,908,653,512 二趟：170,087,275,061 426 512,653 897 908 三趟：061,087 170 275 512 653 四趟：061 087,堆排序：,初始序列： （503，087，512，061，908，170，897，275，653，426） 第一躺：426，653，897，5

15、03，87，170，512，275，61，908 第二躺：61，653，512，503，87，170，426，275，897，908 第三躺：61，503，512，275，87，170，426，653，897，908 第四躺：61，503，426，275，87，170，512，653，897，908 第五躺：170，275，426，61，87，503，512，653，897，908 第六躺：87，275，170，61，426，503，512，653，897，908 第七躺：61，87，170，275，426，503，512，653，897，908 第八躺：61，87，170，275，426，503，512，653，897，908 第九趟：61，87，170，275，426，503，512，653，897，908,9.8,void Bubble_So