数据与结构12235062胡耀心

1、 数据结构实验报告学 号： 201312235062 姓 名： 胡耀心 学 院： 信息科学与工程学院 专 业： 电子信息工程（db） 班 级： 1302班 实验名称实验一实验题目设有两个无头结点的单链表，头指针分别为ha，hb，链中有数据域data，链域next，两链表的数据都按递增序存放，现要求将hb表归到ha表中，且归并后ha仍递增序，归并中ha表中已有的数据若hb中也有，则hb中的数据不归并到ha中，hb的链表在算法中不允许破坏。主要实验记录及个人小结包括部分实验源程 序、流程 图、调试结果及实验结果分析等代码如下：#includestruct lnodeint data;struct

2、lnode*next;typedef struct lnode*linklist;linklist union(linklist ha,linklist hb)linklist head=(lnide*)malloc(sizeof(lnode);head-next=ha;lnode*pa,*pb,*ptmp;pa=ha-next;pb=hb-next;ptmp=ha;while(pa&pb)if(pa-datadata)ptmp=pa;pa=pa-next;else if(pa-datapb-data)lnode*lr=(lnode*)malloc(sizeof(lnode);lr-data=

3、pb-data;lr-data=pa;ptmp-next=lr;ptmp=lr;pb=pb-next;elseptmp=pa;pa=pa-next;pb=pb-next;if(pa)ptmp-next=pa;elsewhile(pb)lnode*lr=(lnode*)malloc(sizeof(lnode);lr-data=pb-data;ptmp-next=lr;ptmp=lr;pb=pb-next;ptmp-next=null;free(head);return ha;int listinser(linklist l,int i,int e)int j=0;linklist p=l,s;w

4、hile(p&jnext;j+;if(!p|jj-1) return 0;s=(linklist)malloc(struct lnode);/*生成新结点*/s-data=e;/*插入l中*/s-next=p-next;p-next=s;return 1;int main()linklist ha,hb;int n,i;int data;initlist(&ha);printf(请输入ha中的数据的个数:);scanf(%d,&n);printf(请依次输入ha中的数据:n);for(int i=1;inext;while(p)printf(%d,p-data);p=p-next;printf

5、(n);initlist(&hb);printf(请输入hb中数据的个数：)；scanf(%d,&n);printf(请依次输入hb中的数据:n);for(i=1;inext;while(p)printf(%d,p-data);p=p-next;printf(n);printf(hb归并到ha后，新的ha=);p=union(ha,hb)-next;while(p)printf(%d,p-data);p=p-nect;printf(n);system(pause);return 0;运行截图如下：实验小结：1. hb不能被破坏所以不能直接直接将hb的节点插入到ha，需要新的空间来完成。2. 因

6、为表头没有节点，所以需要我们自己创建节点。实验名称实验二实验题目假设称正读和反读都相同的字符序列为回文，例如，abba和abcba是回文，abcde和ababab则不是回文。试写一个算法判别读入的一个以为结束符的字符序列是否是回文。主要实验记录及个人小结包括部分实验源程 序、流程 图、调试结果及实验结果分析等代码如下：#include #include#define m 100typedef structchar stackm;int top;stackstru; typedef struct char queuem;int front;int rear;queuestru;void main

7、()int stinit(stackstru *s); int stempty(stackstru *s); int stpush(stackstru *s,char x); char stpop(stackstru *s); int quinit(queuestru *q); int quempty(queuestru *q); int enqueue(queuestru *q,char e); char dequeue(queuestru *q); char c;int flag=0;stackstru *s=(stackstru *)malloc(sizeof(stackstru); q

8、ueuestru *q=(queuestru *)malloc(sizeof(queuestru); stinit(s); quinit(q); printf(input a string:n);while(c=getchar()!=); putchar(c); stpush( s,c); enqueue(q,c); printf(n);printf(end input!n); while(stempty(s) if(stpop(s)=dequeue(q) flag=1; continue; else flag=0;break; if(flag=1)printf(this string is

9、palindrome!n); elseprintf(this string isnt palindrome!n);int stinit(stackstru *s)s-top=0;return 1; int stempty(stackstru *s)if(s-top=0) return 0;elsereturn 1; int stpush(stackstru *s,char x)if(s-top=m) printf(the stack is overflow!n); return 0; else s-top=s-top+1; s-stacks-top=x; return 1;char stpop

10、(stackstru *s)char y;if(s-top=0) printf(the stack is empty!n); return ; else y=s-stacks-top; s-top=s-top-1; return y; int quinit(queuestru *q)q-front=0; q-rear=0;return 1; int quempty(queuestru *q)if(q-front=q-rear) return 0;elsereturn 1; int enqueue(queuestru *q,char e)if(q-rear+1)%m=q-front) print

11、f(the queue is overflow!n); return 0;elseq-queueq-rear=e;q-rear=(q-rear+1)%m; return 1;char dequeue(queuestru *q)char f;if(q-front=q-rear)printf(the queue is empty!n);return 0;elsef=q-queueq-front;q-front=(q-front+1)%m; return f;实验小结：实验名称实验三实验题目先序建立一棵二叉树，并对其分别以中序和后序进行遍历，打印输出遍历结果。例如： abc defg（其中表示空格字

12、符）则输出结果为 中序：cbegdfa 后序：cgefdba主要实验记录及个人小结包括部分实验源程 序、流程 图、调试结果及实验结果分析等实验代码：#include#includetypedefstructbitnodechardata;structbitnode*lchild,*rchild;bitnode,*bitree;bitreecreatebitree()charp;bitreet;scanf(%c,&p);if(p=)t=null;elset=(bitnode*)malloc(sizeof(bitnode);t-data=p;t-lchild=createbitree();t-rc

13、hild=createbitree();return(t);voidpreorder(bitreet)if(t!=null)printf(%c,t-data);preorder(t-lchild);preorder(t-rchild);voidinorder(bitreet)if(t!=null)inorder(t-lchild);printf(%c,t-data);inorder(t-rchild);voidpostorder(bitreet)if(t!=null)postorder(t-lchild);postorder(t-rchild);printf(%c,t-data);voidma

14、in()bitreeta;ta=createbitree();printf(preorder);printf(n);preorder(ta);printf(n);printf(inorder);printf(n);inorder(ta);printf(n);printf(postorder);printf(n);postorder(ta);printf(n);结果截图：实验小结：要特别注意对于递归的运用，虽然只是一个小小的程序但是占用的空间却比我想象中的大的多。实验名称实验四实验题目输入一个英文字符串，对该字符串中各字符个数进行统计取得各字符的出现次数；以其出现次数作为关键字建立哈夫曼树并进行

15、编码，最后输出各个字符对应的码值。主要实验记录及个人小结包括部分实验源程 序、流程 图、调试结果及实验结果分析等#include#include#define maxvalue 10000#define maxbit 4#define maxn 10typedef struct unsigned int weight;unsigned int flag;unsigned int parent,lchild,rchild;haffnode;typedef structint bitmaxn;int strat;int weight;code;void haffman(int weight,int

16、 n,haffnode hafftree)int i,j,m1,m2,x1,x2;for(i=0;i2*n-1;i+)if(in)hafftreei.weight=weighti;elsehafftreei.weight=0;hafftreei.parent=0; hafftreei.flag =0;hafftreei.lchild=-1;hafftreei.rchild=-1;for(i=0;in-1;i+)m1=m1=maxvalue;x1=x2=0;for(j=0;jn+i;j+)if(hafftreej.weightm1&hafftreej.flag=0)m2=m1;x2=x1;m1=

17、hafftreej.weight;x1=j;else if(hafftreej.weightm2&hafftreej.flag=0)m2=hafftreej.weight;x2=j;hafftreex1.parent=n+i;hafftreex2.parent=n+i;hafftreex1.flag =1;hafftreex2.flag =1;hafftreen+i.weignt=haftreex1.weight+hafftreex2.weight;hafftreen+i.lchild =x1;hafftreen+i.rchild =x2;void hffmancode(haffnode ha

18、fftree,int n,code haffcode)code *cd;cd=(code*)malloc(sizeof(code);int i,j,child,parent;for(i=0;istart=n-1;cd-weight=hafftreei.weight;child = i;parent = hafftreechild.parent;while(parent!=0)if(hafftreeparent.lchild=child)cd-bitcd-start=0;elsecd-bitcd-start=1;cd-start-;child = parent;parent = hafftreechild.parent;for(j=cd-start+1;jbitj;haffcodei.start=cd-start;haffcodei.weig