数据结构实验

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) 输出循环单链表 h:n);DispList(h);printf(4) 循环单链表 h 的长度为 %dn,ListLength(h); printf(5)单链表 h 为 sn,(ListEmpty(h

5、)?空:非空); GetElem(h,3,e);printf(6) 循环单链表 h 的第 3 个元素是 %cn,e); GetElem(h,3,e);printf(7) 元素 a 的位置 =%dn,LocateElem(h,a); printf(8) 在第 4 个元素位置上插入元素 fn); ListInsert(h,4,f);printf(9) 输出循环单链表表 h:);DispList(h);printf(10)删除L的第3个元素n);ListDelete(h,3,e); printf(11) 输出循环单链表 h:); DispList(h);printf(12) 释放顺序表 hn);De

6、stroyList(h);printf(雷志超 电信1301班n”)；/ 文件名 :exp 实验二 7-4.cpp/ 数据元素/ 指向左孩子/ 指向右孩子#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) / /以括号表示法输出二叉树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 中最右边的那个字符 for (q=post;qmaxpost) maxpost=k; maxp=p; maxin=p-in; s=(BTNode *)malloc(sizeof(BTNode); / 创建二叉树节点 *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、 以凹入表表示法输出一棵二叉树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;/ 根节点入栈/2 表示是根/ 退栈并凹入显示该节点值/ 左节点之后输出 (L)/ 右节点之后输出 (R)/ 根节点之后前输出 (B)/ 其中 n 为显示场宽 ,字符以右对齐显示/ 将右子树根节点入栈/ 显示场宽增 width/1 表示是右子树/ 将左子树根节点入栈/ 显示场宽增 width/0 表示是左子树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( 构造一棵二叉树 b:n);printf( 括号表示法 :);DispBTNode(b);printf(n);printf( 凹入表示法 :n);DispBTNode1(b);printf(nn);printf( 中序序列 :%sn,in);printf( 后序序列 :%sn,post

13、); b=CreateBT2(post,in,14,14);printf( 构造一棵二叉树 b:n);printf( 括号表示法 :);DispBTNode(b);printf(n); printf( 凹入表示法 :n);DispBTNode1(b);printf(n); DestroyBTNode(b);printf( 雷志超 电信 1301);/ 文件名 :实验三 9-8.cpp#include #define MaxSize 100/ 定义最大哈希表长度#define NULLKEY -1#define DELKEY -2 typedef int KeyType;/ 定义空关键字值/ 定

14、义被删关键字值/ 关键字类型typedef char * InfoType; / 其他数据类型typedef structKeyType key;/ 关键字域InfoType data;/ 其他数据域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

15、;haadr.count=1;else / 发生冲突时采用线性探查法解决冲突i=1; /i 记录 xj 发生冲突的次数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) / 创建哈希表/ 哈希表置初值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) / 在哈希表中查找关键字 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) / 采用线性探查法找下一个地址/ 查找成功/ 查找失败int DeleteHT(HashTable ha,int p,int k,int &n) / 删除哈希表中关键字 k int adr;

17、adr=SearchHT(ha,p,k); if (adr!=-1)/ 在哈希表中找到该关键字haadr.key=DELKEY;n-;/ 哈希表长度减 1return 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=DE

18、LKEY) 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);DispHT(ha,n,m); i=SearchHT(ha,p,k);if (i!=