《数据结构程序》doc版.doc

#include stdafx.h#include stdio.h#include malloc.h#include conio.htypedef char Elem;typedef struct Node Elem data; struct Node *lchild,*rchild;BiTree;BiTree *createBiTree(char *pre,char *in,int n)/先序和中序构造二叉树 BiTree *s; char *p; int k; if(ndata=*pre; for(p=in;plchild=createBiTree(pre+1,in,k); s-rchild=createBiTree(pre+k+1,p+1,n-k-1); return s;BiTree *createBiTree2(char *post,char *in,int n)/后序和中序构造二叉树 BiTree *s; char *p,r; int k; if(ndata=r; for(p=in;plchild=createBiTree(post,in,k); s-rchild=createBiTree(post+k,p+1,n-k-1); return s;void printBiTree(BiTree *T) /括号表示法输出 if(T) printf(%c,T-data); if(T-lchild|T-rchild) printf(); printBiTree(T-lchild); if(T-rchild) printf(,); printBiTree(T-rchild); printf(); void printBiTree2(BiTree *T) /凹入表示法输出 BiTree *s100,*p; int lev1002,top=-1,n,i,width=4; char type; if(T!=NULL) top+; stop=T; levtop0=width; levtop1=2; while(top-1) p=stop; n=levtop0; switch(levtop1) case 0:type=L;break; case 1:type=R;break; case 2:type=B;break; for(i=1;idata,type); for(i=n+1;irchild) top+; stop=p-rchild; levtop0=n+width; levtop1=1; if(p-lchild) top+; stop=p-lchild; levtop0=n+width; levtop1=0; void main() BiTree *T; Elem pre=ABDEHJKLMNCFGI; Elem in=DBJHLKMNEAFCGI; Elem post=DJLNMKHEBFIGCA; printf(先序:%sn,pre); printf(中序:%sn,in); printf(先序和中序构造二叉树：n); printf(括号法：n); T=createBiTree(pre,in,14); printBiTree(T); printf(n); printf(凹入法：n); T=createBiTree(pre,in,14); printBiTree2(T); printf(n); printf(后序:%sn,post); printf(中序:%sn,in); printf(后序和中序构造二叉树：n); printf(括号法：n); T=createBiTree2(post,in,14); printBiTree(T); printf(n); printf(凹入法：n); T=createBiTree2(post,in,14); printBiTree2(T); printf(n);#include #define MaxSize 100/*定义最大哈希表长度*/#define NULLKEY -1/*定义空关键字值*/#define DELKEY-2/*定义被删关键字值*/typedef int KeyType;/*关键字类型*/typedef char * InfoType;/*其他数据类型*/typedef structInfoType data;/*其他数据域*/KeyType key;/*关键字域*/int count;/*探查次数域*/ HashTableMaxSize;/*哈希表类型*/void InsertHT(HashTable ha,int &n,KeyType k,int p) /*将关键字k插入到哈希表中*/int i,adr;adr=k % p;if (haadr.key=NULLKEY | haadr.key=DELKEY)/*xj可以直接放在哈希表中*/haadr.key=k;haadr.count=1;else/*发生冲突时采用线性探查法解决冲突*/i=1;/*i记录xj发生冲突的次数*/do adr=(adr+1) % p;i+; while (haadr.key!=NULLKEY & haadr.key!=DELKEY);haadr.key=k;haadr.count=i;n+;void CreateHT(HashTable ha,KeyType x,int n,int m,int p) /*创建哈希表*/int i,n1=0;for (i=0;im;i+)/*哈希表置初值*/ hai.key=NULLKEY; hai.count=0; for (i=0;in;i+)InsertHT(ha,n1,xi,p);int SearchHT(HashTable ha,int p,KeyType k)/*在哈希表中查找关键字k*/int i=0,adr;adr=k % p;while (haadr.key!=NULLKEY & haadr.key!=k)i+;/*采用线性探查法找下一个地址*/adr=(adr+1) % p;if (haadr.key=k)/*查找成功*/return adr;else/*查找失败*/return -1;int DeleteHT(HashTable ha,int p,int k,int &n)/*删除哈希表中关键字k*/int adr;adr=SearchHT(ha,p,k);if (adr!=-1)/*在哈希表中找到该关键字*/haadr.key=DELKEY;n-;/*哈希表长度减1*/return 1;else/*在哈希表中未找到该关键字*/return 0;void DispHT(HashTable ha,int n,int m) /*输出哈希表*/float avg=0;int i;printf( 哈希表地址:t);for (i=0;im;i+) printf( %3d,i);printf( n); printf( 哈希表关键字:t);for (i=0;im;i+) if (hai.key=NULLKEY | hai.key=DELKEY)printf( );/*输出3个空格*/elseprintf( %3d,hai.key);printf( n);printf( 搜索次数:t);for (i=0;im;i+)if (hai.key=NULLKEY | hai.key=DELKEY)printf( );/*输出3个空格*/elseprintf( %3d,hai.count);printf( n); for (i=0;im;i+)if (hai.key!=NULLKEY & hai.key!=DELKEY)avg=avg+hai.count;avg=avg/n;printf( 平均搜索长度ASL(%d)=%gn,n,avg);void main()int x=16,74,60,43,54,90,46,31,29,88,77;int n=11,m=13,p=13,i,k=29;HashTable ha;CreateHT(ha,x,n,m,p);printf(n);DispHT(ha,n,m);i=SearchHT(ha,p,k);if (i!=-1)printf( ha%d.key=%dn,i,k);elseprintf( 未找到%dn,k);k=77;printf( 删除关键字%dn,k);DeleteHT(ha,p,k,n);DispHT(ha,n,m);i=SearchHT(ha,p,k);if (i!=-1)printf( ha%d.key=%dn,i,k);elseprintf( 未找到%dn,k);printf( 插入关键字%dn,k);InsertHT(ha,n,k,p);DispHT(ha,n,m);printf(n);#include stdafx.h#include stdio.h#include stdlib.htypedef int RecType;void Merge(RecType *R,int low,int m,int high)int i=low,j=m+1,p=0;RecType *R1;R1=(RecType*)malloc(high-low+1)*sizeof(RecType);if(!R1)return;while(i=m&j=high)R1p+=(Ri=Rj)?Ri+:Rj+;while(i=m)R1p+=Ri+;while(j=high)R1p+=Rj+;for(p=0,i=low;i=high;p+,i+)Ri=R1p;void MergeSort(RecType R,int low,int high) int mid; if(lowhigh) mid=(low+high)/2; MergeSort(R,low,mid); MergeSort(R,mid+1,high); Merge(R,low,mid,high); void main()int a8=18,2,20,34,12,32,6,16;int low=0,high=7;MergeSort(a,low,high);for(int i=low;ifront=q-rear=0;void ClearQueue (SqQueue*&q)free(q);int QueueLength(SqQueue*q)return (q-rear-q-front+Maxqsize)%Maxqsize;int QueueEmpty(SqQueue*q)return (q-front=q-rear);int enQueue(SqQueue*&q,ElemType e)if(q-rear+1)%Maxqsize=q-front)return 0;q-rear=(q-rear+1)%Maxqsize;q-elemq-rear=e;return 1;int deQueue(SqQueue *&q,ElemType&e)if(q-front=q-rear)return 0;q-front=(q-front+1)%Maxqsize;e=q-elemq-front;return 1;void main()ElemType e;SqQueue *q;printf(1)初始化队列Qn);InitQueue(q);printf(2)依次进队列元素A,B,Cn);if(enQueue(q,A)=0)printf(队满，不能进队n);if(enQueue(q,B)=0)printf(队满，不能进队n);if(enQueue(q,C)=0)printf(队满，不能进队n);printf(3)队列为%sn,(QueueEmpty(q)?空:非空);if(deQueue(q,e)=0)printf(队空，不能进队n);else printf(4)出对一个元素%cn,e);printf(5)队列Q的元素个数:%dn,QueueLength(q);printf(6)依次进队列元素D,E,Fn);if(e