數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)

1、#define MaxSize 10 #include #include typedef char ElemType;typedef structElemType dataMaxSize; int length;SqList;void InitList(SqList * &L)L=(SqList * )malloc(sizeof(SqList); L-length=0;bool ListInsert(SqList * &L,int i,ElemType e)int j; if(iL-length+1) return false;i-; for(j=L-length;ji;j-)L-datai=

2、L-dataj-1; L-datai=e; L-length+; return true;void DispList(SqList * L) int i;for(i=0;ilength;i+) printf(%c,L-datai);printf(n);int ListLength(SqList * L) return(L-length);bool ListEmpty(SqList * L)return(L-length=0);bool GetElem(SqList * L,int i,ElemType &e) if(iL-length) return false;e=L-datai-1; re

3、turn true;int LocateElem(SqList *L,ElemType e)int i=0; while(ilength&L-datai!=e) i+;if(iL-length)return 0;else return i+1;bool ListDelete(SqList *&L,int i,ElemType &e)int j; if(iL-length) return false;i-; e=L-datai;for(j=i;jlength-1;j+) L-length-;return true;void DestroyList(SqList *&L) free(L);void

4、 main()SqList *h;int i=1;ElemType e;printf(1) 初始化順序表 n);InitList(h);printf(2) 依次采用尾插法插入 a b c d en);ListInsert(h,1,a);ListInsert(h,2,b);ListInsert(h,3,c);ListInsert(h,4,d);ListInsert(h,5,e); printf(3) 輸出循環(huán)單鏈表 h:n);DispList(h);printf(4) 循環(huán)單鏈表 h 的長(zhǎng)度為 %dn,ListLength(h); printf(5)單鏈表 h 為 sn,(ListEmpty(h

5、)?空:非空); GetElem(h,3,e);printf(6) 循環(huán)單鏈表 h 的第 3 個(gè)元素是 %cn,e); GetElem(h,3,e);printf(7) 元素 a 的位置 =%dn,LocateElem(h,a); printf(8) 在第 4 個(gè)元素位置上插入元素 fn); ListInsert(h,4,f);printf(9) 輸出循環(huán)單鏈表表 h:);DispList(h);printf(10)刪除L的第3個(gè)元素n);ListDelete(h,3,e); printf(11) 輸出循環(huán)單鏈表 h:); DispList(h);printf(12) 釋放順序表 hn);De

6、stroyList(h);printf(雷志超 電信1301班n”)；/ 文件名 :exp 實(shí)驗(yàn)二 7-4.cpp/ 數(shù)據(jù)元素/ 指向左孩子/ 指向右孩子#include #include #define MaxSize 100 #define MaxWidth 40 typedef char ElemType; typedef struct node ElemType data; struct node *lchild; struct node *rchild; BTNode;void DestroyBTNode(BTNode *&b)if (b!=NULL)DestroyBTNode(b-

7、lchild);DestroyBTNode(b-rchild);free(b);void DispBTNode(BTNode *b) / /以括號(hào)表示法輸出二叉樹(shù)if (b!=NULL)printf(%c,b-data);if (b-lchild!=NULL | b-rchild!=NULL)printf();DispBTNode(b-lchild);if (b-rchild!=NULL) printf(,);DispBTNode(b-rchild);printf();extern void DispBTNode(BTNode *b); extern void DestroyBTNode(BT

8、Node *&b); BTNode *CreateBT1(char *pre,char *in,int n) BTNode *s;char *p;int k;if (ndata=*pre;for (p=in;plchild=CreateBT1(pre+1,in,k); s-rchild=CreateBT1(pre+k+1,p+1,n-k-1);return s;BTNode *CreateBT2(char *post,char *in,int n,int m)BTNode *s;char *p,*q,*maxp;int maxpost,maxin,k;if (n=0) return NULL;

9、maxpost=-1;for (p=in;pin+n;p+) / 求 in 中全部字符中在 post 中最右邊的那個(gè)字符 for (q=post;qmaxpost) maxpost=k; maxp=p; maxin=p-in; s=(BTNode *)malloc(sizeof(BTNode); / 創(chuàng)建二叉樹(shù)節(jié)點(diǎn) *s s-data=postmaxpost;s-lchild=CreateBT2(post,in,maxin,m); s-rchild=CreateBT2(post,maxp+1,n-maxin-1,m);return s;void DispBTNode1(BTNode *b) /

10、 以凹入表表示法輸出一棵二叉樹(shù)BTNode *StMaxSize,*p;int levelMaxSize2,top=-1,n,i,width=4;char type;if (b!=NULL)top+;Sttop=b;leveltop0=width;leveltop1=2;while (top-1)p=Sttop; n=leveltop0; switch(leveltop1)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!=NULL) top+;

11、 Sttop=p-rchild; leveltop0=n+width; leveltop1=1;if (p-lchild!=NULL) top+; Sttop=p-lchild; leveltop0=n+width; leveltop1=0;/ 根節(jié)點(diǎn)入棧/2 表示是根/ 退棧并凹入顯示該節(jié)點(diǎn)值/ 左節(jié)點(diǎn)之后輸出 (L)/ 右節(jié)點(diǎn)之后輸出 (R)/ 根節(jié)點(diǎn)之后前輸出 (B)/ 其中 n 為顯示場(chǎng)寬 ,字符以右對(duì)齊顯示/ 將右子樹(shù)根節(jié)點(diǎn)入棧/ 顯示場(chǎng)寬增 width/1 表示是右子樹(shù)/ 將左子樹(shù)根節(jié)點(diǎn)入棧/ 顯示場(chǎng)寬增 width/0 表示是左子樹(shù)void main()BTNode *b;Ele

12、mType pre=ABDEHJKLMNCFGI;ElemType in=DBJHLKMNEAFCGI;ElemType post=DJLNMKHEBFIGCA; b=CreateBT1(pre,in,14);printf( 先序序列 :%sn,pre);printf( 中序序列 :%sn,in);printf( 構(gòu)造一棵二叉樹(shù) b:n);printf( 括號(hào)表示法 :);DispBTNode(b);printf(n);printf( 凹入表示法 :n);DispBTNode1(b);printf(nn);printf( 中序序列 :%sn,in);printf( 后序序列 :%sn,post

13、); b=CreateBT2(post,in,14,14);printf( 構(gòu)造一棵二叉樹(shù) b:n);printf( 括號(hào)表示法 :);DispBTNode(b);printf(n); printf( 凹入表示法 :n);DispBTNode1(b);printf(n); DestroyBTNode(b);printf( 雷志超 電信 1301);/ 文件名 :實(shí)驗(yàn)三 9-8.cpp#include #define MaxSize 100/ 定義最大哈希表長(zhǎng)度#define NULLKEY -1#define DELKEY -2 typedef int KeyType;/ 定義空關(guān)鍵字值/ 定

14、義被刪關(guān)鍵字值/ 關(guān)鍵字類(lèi)型typedef char * InfoType; / 其他數(shù)據(jù)類(lèi)型typedef structKeyType key;/ 關(guān)鍵字域InfoType data;/ 其他數(shù)據(jù)域int count;/ 探查次數(shù)域 HashTableMaxSize;/ 哈希表類(lèi)型void InsertHT(HashTable ha,int &n,KeyType k,int p) / 將關(guān)鍵字 k 插入到哈希表中 int i,adr; adr=k % p; if (haadr.key=NULLKEY | haadr.key=DELKEY) /xj 可以直接放在哈希表中 haadr.key=k

15、;haadr.count=1;else / 發(fā)生沖突時(shí)采用線性探查法解決沖突i=1; /i 記錄 xj 發(fā)生沖突的次數(shù)doadr=(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) / 創(chuàng)建哈希表/ 哈希表置初值int i,n1=0; for (i=0;im;i+) hai.key=NULLKEY;hai.count=0;for (i=0;in;i+)

16、InsertHT(ha,n1,xi,p);int SearchHT(HashTable ha,int p,KeyType k) / 在哈希表中查找關(guān)鍵字 kint i=0,adr; adr=k % p;i+;adr=(adr+1) % p;if (haadr.key=k) return adr;elsereturn -1;while (haadr.key!=NULLKEY & haadr.key!=k) / 采用線性探查法找下一個(gè)地址/ 查找成功/ 查找失敗int DeleteHT(HashTable ha,int p,int k,int &n) / 刪除哈希表中關(guān)鍵字 k int adr;

17、adr=SearchHT(ha,p,k); if (adr!=-1)/ 在哈希表中找到該關(guān)鍵字haadr.key=DELKEY;n-;/ 哈希表長(zhǎng)度減 1return 1;else/ 在哈希表中未找到該關(guān)鍵字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( 哈希表關(guān)鍵字 :t);for (i=0;im;i+)if (hai.key=NULLKEY | hai.key=DE

18、LKEY) printf( ); / 輸出 3 個(gè)空格 elseprintf( %3d,hai.key);printf(n);printf( 搜索次數(shù) :t);for (i=0;im;i+)if (hai.key=NULLKEY | hai.key=DELKEY) printf( ); / 輸出 3 個(gè)空格 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( 平均搜索長(zhǎng)度 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);DispHT(ha,n,m); i=SearchHT(ha,p,k);if (i!=