数据结构报告C语言上机操作.doc

《数据结构报告C语言上机操作.doc》由会员分享，可在线阅读，更多相关《数据结构报告C语言上机操作.doc（28页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构C语言上机操作学 部：信息科学与技术学部学 号：指导老师：姓 名: 专业班级: 一、 实验目的熟练C言语语法及操作，运用C语言实现数据结构中的具体过程。理解数据结构在计算机中的具体形式。学习数据结构中赫夫曼变法，表和图的实现过程。二、 实验环境及参考书籍Microsoft Visual C+ 6.0数据结构（C语言版），程序设计基础（C语言）。三、 实验内容赫夫曼编码：#include stdio.h#include string.h#include conio.h#include stdlib.h/* */*根据统计函数得到字符的种类数N和各自出现的次数，建立N个结点，由此构造一颗哈

2、夫曼树。 */#define N 30 /* 叶子结点数，即在信息中最多可出现30种字符 */typedef structchar data; /*编码对应的字符 */int weight; /* 结点的权值 */int lchild,rchild,parent; /* 左右孩子及双亲的下标 */HTNode;int Stat(char *st,int cnt,char str) /* 统计字符信息中出现的字符种类数和各字符出现的次数 */char *p;int i,j,k,num27;for(i=0;i=a&*p=z) /* */k=*p-96;numk+;j=0;for(i=0;i26;i

3、+)if(numi!=0)strj=i+96;cntj=numi;j+;return j;void CreatHufmTree(HTNode ht,int n) /* 建立哈夫曼树 */int i,k,m1,m2,l,r;for(i=0;i2*n-1;i+)hti.lchild=hti.rchild=hti.parent=0; /* 对所有结点的左右孩子及双亲指针域赋空值 */ for(i=n;i2*n-1;i+)m1=m2=10000; /* m1为最小值，m2为次小值 */l=r=0;for(k=0;k=i-1;k+)if(htk.parent=0&htk.weightm1) /* 在前面

4、i个结点中选择没有双亲且权值最小的两个结点 */m2=m1;r=l;m1=htk.weight;l=k;else if(htk.parent=0&htk.weightm2)m2=htk.weight;r=k;htl.parent=i; /* 下标为i的新结点成为权值最小的两个结点的双亲 */htr.parent=i;hti.weight=htl.weight+htr.weight; /* 新结点的权值为两个结点的权值之和 */hti.lchild=l; /* 权值最小的结点是新结点的左孩子 */hti.rchild=r; /* 权值次小的结点是新结点的右孩子 */typedef structc

5、har bitsN; /* 存放哈夫曼编码的字符数组 */int start; /* 记录编码的起始位置，因为每种字符的编码长度不同 */HCode; void HufmCode(HTNode ht,HCode hcd,int n) /* 利用哈夫曼树求出各字符的哈夫曼编码 */int i,f,c,k;HCode cd; /* 用于临时存放编码串*/for(i=0;in;i+)cd.start=n;c=i; /* 从叶子结点hti开始向上回溯 */f=hti.parent; /* 找到叶子结点hti的双亲结点htf */while(f!=0) /* 回溯到树根结点为止 */if(htf.lch

6、ild=c) /* 若htc是htf的左孩子，生成代码为0 */cd.bitscd.start-=0;else /* 若htc是htf的右孩子，生成代码为1 */cd.bitscd.start-=1;c=f;f=htf.parent;cd.start+;/*start指向哈夫曼编码最开始字符*/hcdi=cd; /*将得到的第i种字符的哈夫曼编码存入hcdi中 */printf(输出哈夫曼编码：n);for(i=0;in;i+)printf(%c:,hti.data);for(k=hcdi.start;k=n;k+)printf(%c,hcdi.bitsk);printf(n);void Ts

7、Code(char *bit,HTNode ht,int n) /* 哈夫曼树的译码 */int i;i=2*n-2; /* 将树根节点的下标赋值i，从根结点出发向下搜索 */while(*bit!=0) /* 若编码没有结束 */if(*bit=0)i=hti.lchild; /* 走向左孩子结点 */elsei=hti.rchild; /* 走向右孩子结点 */if(hti.lchild=0&hti.rchild=0) /* 判断是否已经走向叶子结点 */printf(%c,hti.data); /*输出此编码对应的字符 */i=2*n-2; /* 重新回到根结点，准备下一次搜索 */bi

8、t+; /* 取编码中的下一个代码 */void main()int i,j,k,n,t,x,cnt27;char st50,sr27,bm200;HTNode ht2*N-1; /* 用于存放树中的所有结点 */HCode hcdN; /* 用于存放字符的哈夫曼编码 */while(1)printf(1-输出待传送的字符信息 2-编码 3-发送 4-接受并译码 0-退出n);scanf(%d,&x);switch(x)case 1:printf(请输入要发送的字符串信息：);scanf(%s,st);break;case 2:n=Stat(st,cnt,sr);for(i=0;in;i+)

9、hti.data=sri; hti.weight=cnti;CreatHufmTree(ht,n);HufmCode(ht,hcd,n);break;case 3:t=0;for(j=0;stj!=0;j+)for(i=0;in;i+)if(hti.data=stj)for(k=hcdi.start;k=n;k+)bmt=hcdi.bitsk;t+;break;bmt=0;printf(发送完毕！n);break;case 4:printf(接收到的编码信息为：);puts(bm);printf(译码后的结果为：);TsCode(bm,ht,n);printf(n);break;case 0:

10、exit(0);链表建立#include ;typedef struct char num8;/*学号*/ char name9;/*姓名*/ char gender3;/*性别*/ int score;/*成绩*/DataType;typedef struct node DataType data; struct node *next;ListNode;typedef ListNode *LinkList;LinkList head;/*函数说明*/int menu_select();LinkList createList(void);void printList(LinkList head

11、);ListNode *findList(LinkList head);int insertNode(LinkList head,ListNode *p,int i);void delNode(LinkList head);void main() ListNode *p; int i; while(1) switch(menu_select() case 1: printf(*n); printf( 学生信息链表的建立 n); printf(*n); head = createList(); break; case 2: printf(*n); printf(添加学生信息n); printf(

12、*n);printf(n学号（8） 姓名（8） 性别 成绩n); printf(*n); p=(ListNode *)malloc(sizeof(ListNode); scanf(%s%s%s%d,p-data.num,p-data.name,p-data.gender,&p-data.score); printf(请输入要插入的位置：n); fflush(stdin); scanf(%d,&i); if(insertNode(head,p,i)=-1) printf(没有合适的插入点！n); else printf(结点已经插入n); break; case 3: printf(*n); p

13、rintf(查询学生信息n); printf(*n); p=findList(head); if(p!=NULL) printf(n学号（8） 姓名（8） 性别 成绩n); printf(-n); printf(%s,%s,%s,%dn,p-data.num,p-data.name,p-data.gender,p-data.score); printf(-n); else printf(没查到要查询的学生信息！); break; case 4: printf(*n); printf(删除学生信息n); printf(*n); delNode(head); break; case 5: prin

14、tf(*n); printf(输出所有学生信息n); printf(*n); printList(head); break; case 0:printf(再见！n);getch(); return; int menu_select()int sn;printf(n 学生信息管理系统n);printf(=n);printf( 1.学生信息链表的建立n);printf( 2.插 入 学 生 信 息n);printf( 3.查 询 学 生 信 息n);printf( 4.删 除 学 生 信 息n);printf( 5.输 出 所有学生信息n);printf( 0.退 出 管 理 系 统n);prin

15、tf(=n);printf(请选择0-5:n);for(;)scanf(%d,&sn);if (sn5) printf(nt输入错误，重选0-5n);else break;return sn;LinkList createList(void)ListNode *p,*rear;char flag = y;head = (ListNode *)malloc(sizeof(ListNode);rear = head;while(flag=y | flag=Y)p=(ListNode *)malloc(sizeof(ListNode);printf(n学号（8） 姓名（8） 性别 成绩n);scan

16、f(%s%s%s%d,p-data.num,p-data.name,p-data.gender,&p-data.score);rear-next = p;rear = p;printf(继续输入吗？（y/n）:);flag = getch();rear-next = NULL;return head;void printList(LinkList head)ListNode *p;p=head-next;printf(n学号（8） 姓名（8） 性别 成绩n);printf(-n);while(p!=NULL) printf(%s,%s,%s,%dn,p-data.num,p-data.name

17、,p-data.gender,p-data.score); printf(-n); p=p-next;ListNode *findList(LinkList head)ListNode *p;char num8;char name9;int xz;printf(=n);printf(1、按学号查询n);printf(2、按姓名查询n);printf(=n);printf( 请选择： );p=head-next;scanf(%d,&xz);if (xz=1) printf(请输入要查找学生的学号：); scanf(%s,num); while(p & strcmp(p-data.num,num)

18、!=0) p=p-next;else if (xz=2) printf(请输入要查找学生的姓名：); scanf(%s,name); while (p & strcmp(p-data.name,name)!=0) p=p-next;return p;int insertNode(LinkList head,ListNode *p,int i)ListNode *p1;int j=1;p1=head;if(p1-next=NULL)/*空表：插入作为第一个结点*/ if(i=0) p1-next=p; p-next=NULL; else return -1;while(jnext; j+;if(

19、p1=NULL)/*没有合适的插入点*/ return -1;p-next=p1-next;p1-next=p;return 0;void delNode(LinkList head)ListNode *p,*q;printf(请先查找您要删除的学生信息：n);p=findList(head);if(p=NULL) printf(没有查到要删除的学生信息); return;q=head;while(q!=NULL & q-next!=p) q=q-next;q-next=p-next;free(p);printf(该学生信息已被删除！n);图：# include # include # inc

20、lude # define maxlen 10# define large 999# define true 1# define false 0# define ok 1# define error 0# define overflow -2# define null 0typedef int status;typedef struct int amaxlen,bmaxlen,hmaxlen;/*第K边的起点,终点,权值*/ char vexsmaxlen;/*顶点信息集合*/ int vexnum,arcnum;/*顶点数和边数*/ int kind;/*图的类型*/ int arcsmax

21、lenmaxlen;/*邻接矩阵*/graph;typedef struct node/*表结点结构*/ int adjvex;/*存放与头结点相邻接的顶点在数组中的序号*/ int info;/*权值*/ struct node *next;/*指向与头结点相邻接下一个顶点的表结点*/edgenode;typedef struct/*头结点结构*/ int id;/*顶点入度*/ char data;/*顶点信息*/ edgenode *link;/*指向头结点对应的单链表中的表结点*/vexnode;typedef struct/*邻接表结构*/ vexnode adjsmaxlen;/*

22、邻接表的头结点集合*/ int vexnum,arcnum;/*顶点数,边数*/ int kind;adjlist;typedef struct qnode/*队列存储结构*/int data; struct qnode *next;linkqlist;typedef structlinkqlist *front;/*队头指针*/ linkqlist *rear;/*队尾指针*/linkqueue;typedef struct/*栈结构*/int stackmaxlen; int top;stackstru;int cnull=-1;graph g;adjlist adjl;stackstru

23、 *t;/*拓扑序列顶点栈*/stackstru *s;/*零入度顶点栈*/linkqueue *q;graph printf_adjmatrix(graph g)/*输出邻接矩阵*/ int i,j; printf(邻接矩阵:n); printf(vertext); for (i=0;ig.vexnum;i+) printf(%4c,g.vexsi); printf(n); for(i=0;ig.vexnum;i+) printf(% 4c t,g.vexsi); for(j=0;jg.vexnum;j+) printf(%4d,g.arcsij); printf(n); return g;

24、void create_1(graph g) int i,j,k,c=0; for (i=0;ig.vexnum;i+) for(j=0;jg.vexnum;j+) g.arcsij=c; for(k=0;kg.arcnum;k+) g.arcsg.ak-1g.bk-1=1; printf_adjmatrix(g); void create_2(graph g) int i,j,k,c=0; for (i=0;ig.vexnum;i+) for(j=0;jg.vexnum;j+) g.arcsij=c; for(k=0;kg.arcnum;k+) g.arcsg.ak-1g.bk-1=1; g

25、.arcsg.bk-1g.ak-1=1; printf_adjmatrix(g);graph create_3(graph g) int i,j,k,c=999; for (i=0;ig.vexnum;i+) for(j=0;jg.vexnum;j+) g.arcsij=c; for(k=0;kg.arcnum;k+)g.arcsg.ak-1g.bk-1=g.hk; printf_adjmatrix(g); return g;graph create_4(graph g) int i,j,k,c=999; for (i=0;ig.vexnum;i+) for(j=0;jg.vexnum;j+)

26、 g.arcsij=c; for (k=0;kg.arcnum;k+) g.arcsg.ak-1g.bk-1=g.hk; g.arcsg.bk-1g.ak-1=g.hk; printf_adjmatrix(g); return g;void creategraph(graph g)/*邻接矩阵*/ switch(g.kind) case 1:create_1(g);break; case 2:create_2(g);break; case 3:create_3(g);break; case 4:create_4(g);break; default:printf(Errorn); adjlist

27、 createlist (graph g ,adjlist adjl)/*邻接表*/ int i; edgenode *p; if(g.kind=1|g.kind=3) for(i=0;iadjvex=g.bi; p-info=g.hi; p-next=adjl.adjsg.ai-1.link; adjl.adjsg.ai-1.link=p; if(g.kind=2|g.kind=4) for(i=0;iinfo=g.hi; p-adjvex=g.bi; p-next=adjl.adjsg.ai-1.link; adjl.adjsg.ai-1.link=p; p=(edgenode*)mall

28、oc(sizeof(edgenode); p-info=g.hi; p-adjvex=g.ai; p-next=adjl.adjsg.bi-1.link; adjl.adjsg.bi-1.link=p; printf(邻接表为:n);for(i=0;i,i+1,adjl.adjsi.data); p=adjl.adjsi.link; while(p!=cnull) printf(%c,%d-,adjl.adjs(p-adjvex)-1.data,p-info); p=p-next; printf(n);return adjl; void initqueue(linkqueue *p) p-fr

29、ont=(linkqlist *)malloc(sizeof(linkqlist); p-rear=p-front; (p-front)-next=null; status empty(linkqueue *q)int v; if(q-front=q-rear) v=true; else v=false; return v;status addqueue(linkqueue *q,int e)/*入队列*/ q-rear-next=(linkqlist *)malloc(sizeof(linkqlist); q-rear=q-rear-next; if(!q-rear) return -1;

30、q-rear-data=e; q-rear-next=null;status delqueue(linkqueue *q)/*出队列*/ linkqlist *p; int e; if (q-front=q-rear) printf(the linklist is overflow); else p=(q-front)-next; (q-front)-next=p-next; e=p-data; if(q-rear=p) q-rear=q-front; free(p);/*释放P所指的内存区*/ return(e);void DFS(int i, adjlist adjl)/*深度优先搜索*/

31、edgenode *p; int j; int visitedmaxlen;/*访问标志数组,访问过为1,未访问过为0*/ for(j=0;j,adjl.adjsi-1.data); visitedi-1=1; p=adjl.adjsi-1.link; while(p!=cnull) if (visited(p-adjvex)-1!=1) DFS(p-adjvex),adjl); p=p-next; void BFS(int i,adjlist adjl)/*广度优先搜索*/ edgenode *p; int j; int visitedmaxlen; for (j=0;j,adjl.adjsi-1.data); visitedi-1=1; addqueue(q,i); while(!empty(q) i=delqueue(q); p=adjl.adjsi-1.link; while(p!=cnull) if (visited(p-adjvex)-1=0) printf(%4c-,adjl.adjsp-adjvex-1.data); visited(p-adjvex)-1=1; addqueue(q,p-adjvex); p=p-next; void prim(graph g)/*最小生成树*/ int i,j,k,min; int lowcostmaxlen;/*权值*/