数据结构实验

1#defineMaxSize10#includestdio.h#includemalloc.htypedefcharElemType;typedefstruct{ElemTypedata[MaxSize];intlength;}SqList;voidInitList(SqList*&L){L=(SqList*)malloc(sizeof(SqList));L-length=0;}boolListInsert(SqList*&L,inti,ElemTypee){intj;if(i1||iL-length+1)returnfalse;i--;for(j=L-length;ji;j--)L-data[i]=L-data[j-1];L-data[i]=e;L-length++;returntrue;}voidDispList(SqList*L){inti;for(i=0;iL-length;i++)printf(%c,L-data[i]);printf(\n);}intListLength(SqList*L){return(L-length);}boolListEmpty(SqList*L){2return(L-length==0);}boolGetElem(SqList*L,inti,ElemType&e){if(i1||iL-length)returnfalse;e=L-data[i-1];returntrue;}intLocateElem(SqList*L,ElemTypee){inti=0;while(iL-length&&L-data[i]!=e)i++;if(iL-length)return0;elsereturni+1;}boolListDelete(SqList*&L,inti,ElemType&e){intj;if(i1||iL-length)returnfalse;i--;e=L-data[i];for(j=i;jL-length-1;j++)L-length--;returntrue;}voidDestroyList(SqList*&L){free(L);}voidmain(){SqList*h;inti=1;ElemTypee;3printf((1)初始化顺序表\n);InitList(h);printf((2)依次采用尾插法插入abcde\n);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的长度为%d\n,ListLength(h));printf((5)单链表h为%s\n,(ListEmpty(h)?空:非空));GetElem(h,3,e);printf((6)循环单链表h的第3个元素是%c\n,e);GetElem(h,3,e);printf((7)元素a的位置=%d\n,LocateElem(h,'a'));printf((8)在第4个元素位置上插入元素f\n);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)释放顺序表h\n);DestroyList(h);printf(雷志超电信1301班\n);}4//文件名:exp实验二7-4.cpp#includestdio.h#includemalloc.h#defineMaxSize100#defineMaxWidth40typedefcharElemType;typedefstructnode{ElemTypedata;//数据元素structnode*lchild;//指向左孩子structnode*rchild;//指向右孩子}BTNode;voidDestroyBTNode(BTNode*&b){if(b!=NULL){DestroyBTNode(b-lchild);DestroyBTNode(b-rchild);free(b);}}voidDispBTNode(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());}}}externvoidDispBTNode(BTNode*b);externvoidDestroyBTNode(BTNode*&b);BTNode*CreateBT1(char*pre,char*in,intn){BTNode*s;char*p;intk;if(n=0)returnNULL;5s=(BTNode*)malloc(sizeof(BTNode));//创建二叉树节点*ss-data=*pre;for(p=in;pin+n;p++)//在中序序列中找等于*ppos的位置kif(*p==*pre)break;k=p-in;s-lchild=CreateBT1(pre+1,in,k);s-rchild=CreateBT1(pre+k+1,p+1,n-k-1);returns;}BTNode*CreateBT2(char*post,char*in,intn,intm){BTNode*s;char*p,*q,*maxp;intmaxpost,maxin,k;if(n=0)returnNULL;maxpost=-1;for(p=in;pin+n;p++)//求in中全部字符中在post中最右边的那个字符for(q=post;qpost+m;q++)//在in中用maxp指向这个字符,用maxin标识它在in中的下标if(*p==*q){k=q-post;if(kmaxpost){maxpost=k;maxp=p;maxin=p-in;}}s=(BTNode*)malloc(sizeof(BTNode));//创建二叉树节点*ss-data=post[maxpost];s-lchild=CreateBT2(post,in,maxin,m);s-rchild=CreateBT2(post,maxp+1,n-maxin-1,m);returns;}voidDispBTNode1(BTNode*b)//以凹入表表示法输出一棵二叉树{BTNode*St[MaxSize],*p;intlevel[MaxSize][2],top=-1,n,i,width=4;chartype;if(b!=NULL){6top++;St[top]=b;//根节点入栈level[top][0]=width;level[top][1]=2;//2表示是根while(top-1){p=St[top];//退栈并凹入显示该节点值n=level[top][0];switch(level[top][1]){case0:type='L';break;//左节点之后输出(L)case1:type='R';break;//右节点之后输出(R)case2:type='B';break;//根节点之后前输出(B)}for(i=1;i=n;i++)//其中n为显示场宽,字符以右对齐显示printf();printf(%c(%c),p-data,type);for(i=n+1;i=MaxWidth;i+=2)printf(--);printf(\n);top--;if(p-rchild!=NULL){//将右子树根节点入栈top++;St[top]=p-rchild;level[top][0]=n+width;//显示场宽增widthlevel[top][1]=1;//1表示是右子树}if(p-lchild!=NULL){//将左子树根节点入栈top++;St[top]=p-lchild;level[top][0]=n+width;//显示场宽增widthlevel[top][1]=0;//0表示是左子树}}}}voidmain(){BTNode*b;ElemTypepre[]=ABDEHJKLMNCFGI;ElemTypein[]=DBJHLKMNEAFCGI;7ElemTypepost[]=DJLNMKHEBFIGCA;b=CreateBT1(pre,in,14);printf(先序序列:%s\n,pre);printf(中序序列:%s\n,in);printf(构造一棵二叉树b:\n);printf(括号表示法:);DispBTNode(b);printf(\n);printf(凹入表示法:\n);DispBTNode1(b);printf(\n\n);printf(中序序列:%s\n,in);printf(后序序列:%s\n,post);b=CreateBT2(post,in,14,14);printf(构造一棵二叉树b:\n);printf(括号表示法:);DispBTNode(b);printf(\n);printf(凹入表示法:\n);DispBTNode1(b);printf(\n);DestroyBTNode(b);printf(雷志超电信1301);}8//文件名:实验三9-8.cpp#includestdio.h#defineMaxSize100//定义最大哈希表长度#defineNULLKEY-1//定义空关键字值#defineDELKEY-2//定义被删关键字值typedefintKeyType;//关键字类型typedefchar*InfoType;//其他数据类型typedefstruct{KeyTypekey;//关键字域InfoTypedata;//其他数据域intcount;//探查次数域}HashTable[MaxSize];//哈希表类型voidInsertHT(HashTableha,int&n,KeyTypek,intp)//将关键字k插入到哈希表中{inti,adr;adr=k%p;if(ha[adr].key==NULLKEY||ha[adr].key==DELKEY)//x[j]可以直接放在哈希表中{ha[adr].key=k;ha[adr].count=1;}else//发生冲突时采用线性探查法解决冲突{i=1;//i记录x[j]发生冲突的次数do{adr=(adr+1)%p;i++;}while(ha[adr].key!=NULLKEY&&ha[adr].key!=DELKEY);ha[adr].key=k;ha[adr].count=i;}n++;}voidCreateHT(HashTableha,KeyTypex[],intn,intm,intp)//创建哈希表{inti,n1=0;for(i=0;im;i++)//哈希表置初值{ha[i].key=NULLKEY;ha[i].count=0;}for(i=0;in;i++)9InsertHT(ha,n1,x[i],p);}intSearchHT(HashTableha,intp,KeyTypek)//在哈希表中查找关键字k{inti=0,adr;adr=k%p;while(ha[adr].key!=NULLKEY&&ha[adr].key!=k){i++;//采用线性探查法找下一个地址adr=(adr+1)%p;}if(ha[adr].key