数据与结构12235062胡耀心

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

2、nt data;struct 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->data<pb->data)ptmp=pa;pa=pa->next;else if(pa->

3、;data>pb->data)lnode*lr=(lnode*)malloc(sizeof(lnode);lr->data=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=

4、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;while(p&&j<i-1)p=p->next;j+;if(!p|j>j-1) return 0;s=(linklist)malloc(struct lnode);/*生成新结点*/s->data=e;/*插入l中*/s->next=p->next;p->next=s;return 1;int main

5、()linklist ha,hb;int n,i;int data;initlist(&ha);printf("请输入ha中的数据的个数:");scanf("%d",&n);printf("请依次输入ha中的数据:n");for(int i=1;i<=n;i+)scanf("%d",&data);listinser(ha,i,data);printf("ha=");linklist p=ha->next;while(p)printf("%d"

6、;,p->data);p=p->next;printf("n");initlist(&hb);printf("请输入hb中数据的个数：")；scanf("%d",&n);printf("请依次输入hb中的数据:n");for(i=1;i<=n;i+)scanf("%d",&data);listinsert(hb,i,data);printf("hb=");p=hb->next;while(p)printf("%d&qu

7、ot;,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. 因为表头没有节点，所以需要我们自己创建节点。实

8、验名称实验二实验题目假设称正读和反读都相同的字符序列为"回文"，例如，'abba'和'abcba'是回文，'abcde'和'ababab'则不是回文。试写一个算法判别读入的一个以''为结束符的字符序列是否是"回文"。主要实验记录及个人小结包括部分实验源程 序、流程 图、调试结果及实验结果分析等代码如下：#include <stdio.h>#include<stdlib.h>#define m 100typedef structchar stackm;i

9、nt top;stackstru; typedef struct char queuem;int front;int rear;queuestru;void main()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(que

10、uestru *q); char c;int flag=0;stackstru *s=(stackstru *)malloc(sizeof(stackstru); queuestru *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("

11、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 palindrome!n"); elseprintf("this string isn't palindrome!n");int stinit(stackstru *s)s->top=0;return 1; int stempty(stackstru *s)if(s->top=0

12、) 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(stackstru *s)char y;if(s->top=0) printf("the stack is empty!n"); return ' ' else

13、 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) printf("the queue is overflow!n"

14、;); 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;实验小结：实验名称实验三实验题目先序建立一棵二叉树，并对其分别以中序和后序进行遍历，打

15、印输出遍历结果。例如： abc defg（其中表示空格字符）则输出结果为 中序：cbegdfa 后序：cgefdba主要实验记录及个人小结包括部分实验源程 序、流程 图、调试结果及实验结果分析等实验代码：#include<stdio.h>#include<stdlib.h>typedef struct bitnodechar data;struct bitnode *lchild,*rchild;bitnode,*bitree;bitree createbitree()char p;bitree

16、60;t;scanf("%c",&p);if(p = '')t=null;elset=(bitnode*)malloc(sizeof(bitnode);t->data=p;t->lchild=createbitree();t->rchild=createbitree();return(t);void preorder(bitree t)if(t!=null)printf("%c",t->data);preorder(t->lchild);preorder(t-&

17、gt;rchild);void inorder(bitree t)if(t!=null)inorder(t->lchild);printf("%c",t->data);inorder(t->rchild);void postorder(bitree t)if(t!=null)postorder(t->lchild);postorder(t->rchild);printf("%c",t->data);void main()bitree ta;ta =&

18、#160;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");结果截图：实验小结：要特别注意对于递归的运用

19、，虽然只是一个小小的程序但是占用的空间却比我想象中的大的多。实验名称实验四实验题目输入一个英文字符串，对该字符串中各字符个数进行统计取得各字符的出现次数；以其出现次数作为关键字建立哈夫曼树并进行编码，最后输出各个字符对应的码值。主要实验记录及个人小结包括部分实验源程 序、流程 图、调试结果及实验结果分析等#include<stdio.h>#include<stdlib.h>#define maxvalue 10000#define maxbit 4#define maxn 10typedef struct unsigned int weight;unsigned int

20、 flag;unsigned int parent,lchild,rchild;haffnode;typedef structint bitmaxn;int strat;int weight;code;void haffman(int weight,int n,haffnode hafftree)int i,j,m1,m2,x1,x2;for(i=0;i<2*n-1;i+)if(i<n)hafftreei.weight=weighti;elsehafftreei.weight=0;hafftreei.parent=0; hafftreei.flag =0;hafftreei.lch

21、ild=-1;hafftreei.rchild=-1;for(i=0;i<n-1;i+)m1=m1=maxvalue;x1=x2=0;for(j=0;j<n+i;j+)if(hafftreej.weight<m1&&hafftreej.flag=0)m2=m1;x2=x1;m1=hafftreej.weight;x1=j;else if(hafftreej.weight<m2&&hafftreej.flag=0)m2=hafftreej.weight;x2=j;hafftreex1.parent=n+i;hafftreex2.parent

22、=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 hafftree,int n,code haffcode)code *cd;cd=(code*)malloc(sizeof(code);int i,j,child,parent;for(i=0;i<n;i+)cd->start=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 = haf