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

数据结构C语言上机操作学 部：信息科学与技术学部学 号：指导老师：姓 名: 专业班级: 一、 实验目的熟练C言语语法及操作，运用C语言实现数据结构中的具体过程。理解数据结构在计算机中的具体形式。学习数据结构中赫夫曼变法，表和图的实现过程。二、 实验环境及参考书籍Microsoft Visual C+ 6.0数据结构（C语言版），程序设计基础（C语言）。三、 实验内容赫夫曼编码：#include "stdio.h"#include "string.h"#include "conio.h"#include "stdlib.h"/* */*根据统计函数得到字符的种类数N和各自出现的次数，建立N个结点，由此构造一颗哈夫曼树。 */#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<26;i+)numi=0;for(p=st;*p!='0'p+)/*p=tolower(*p); /* 若字符信息中有大写字母，则将其转换成小写字母 */if(*p>='a'&&*p<='z') /* */k=*p-96;numk+;j=0;for(i=0;i<26;i+)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;i<2*n-1;i+)hti.lchild=hti.rchild=hti.parent=0; /* 对所有结点的左右孩子及双亲指针域赋空值 */ for(i=n;i<2*n-1;i+)m1=m2=10000; /* m1为最小值，m2为次小值 */l=r=0;for(k=0;k<=i-1;k+)if(htk.parent=0&&htk.weight<m1) /* 在前面i个结点中选择没有双亲且权值最小的两个结点 */m2=m1;r=l;m1=htk.weight;l=k;else if(htk.parent=0&&htk.weight<m2)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 structchar bitsN; /* 存放哈夫曼编码的字符数组 */int start; /* 记录编码的起始位置，因为每种字符的编码长度不同 */HCode; void HufmCode(HTNode ht,HCode hcd,int n) /* 利用哈夫曼树求出各字符的哈夫曼编码 */int i,f,c,k;HCode cd; /* 用于临时存放编码串*/for(i=0;i<n;i+)cd.start=n;c=i; /* 从叶子结点hti开始向上回溯 */f=hti.parent; /* 找到叶子结点hti的双亲结点htf */while(f!=0) /* 回溯到树根结点为止 */if(htf.lchild=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;i<n;i+)printf("%c:",hti.data);for(k=hcdi.start;k<=n;k+)printf("%c",hcdi.bitsk);printf("n");void TsCode(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; /* 重新回到根结点，准备下一次搜索 */bit+; /* 取编码中的下一个代码 */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;i<n;i+) 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;i<n;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:exit(0);链表建立#include <stdio.h>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);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("*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"); printf("查询学生信息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: printf("*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");printf("=n");printf("请选择0-5:n");for(;)scanf("%d",&sn);if (sn<0 | sn>5) 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");scanf("%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,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)!=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(j<=i-1)&&(p1!=NULL)/*找到第i-1个结点，p1指向该结点*/ p1=p1->next; j+;if(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 <stdio.h># include <stdlib.h># include <conio.h># 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 arcsmaxlenmaxlen;/*邻接矩阵*/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;/*邻接表的头结点集合*/ 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 *t;/*拓扑序列顶点栈*/stackstru *s;/*零入度顶点栈*/linkqueue *q;graph printf_adjmatrix(graph g)/*输出邻接矩阵*/ int i,j; printf("邻接矩阵:n"); printf("vertext"); for (i=0;i<g.vexnum;i+) printf("%4c",g.vexsi); printf("n"); for(i=0;i<g.vexnum;i+) printf("% 4c t",g.vexsi); for(j=0;j<g.vexnum;j+) printf("%4d",g.arcsij); printf("n"); return g;void create_1(graph g) int i,j,k,c=0; for (i=0;i<g.vexnum;i+) for(j=0;j<g.vexnum;j+) g.arcsij=c; for(k=0;k<g.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;i<g.vexnum;i+) for(j=0;j<g.vexnum;j+) g.arcsij=c; for(k=0;k<g.arcnum;k+) g.arcsg.ak-1g.bk-1=1; g.arcsg.bk-1g.ak-1=1; printf_adjmatrix(g);graph create_3(graph g) int i,j,k,c=999; for (i=0;i<g.vexnum;i+) for(j=0;j<g.vexnum;j+) g.arcsij=c; for(k=0;k<g.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;i<g.vexnum;i+) for(j=0;j<g.vexnum;j+) g.arcsij=c; for (k=0;k<g.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 createlist (graph g ,adjlist adjl)/*邻接表*/ int i; edgenode *p; if(g.kind=1|g.kind=3) for(i=0;i<adjl.arcnum;i+) p=(edgenode*)malloc(sizeof(edgenode); p->adjvex=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;i<adjl.arcnum;i+) p=(edgenode*)malloc(sizeof(edgenode); p->info=g.hi; p->adjvex=g.bi; p->next=adjl.adjsg.ai-1.link; adjl.adjsg.ai-1.link=p; p=(edgenode*)malloc(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<g.vexnum;i+) printf("%d,%c=>",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->front=(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; 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)/*深度优先搜索*/edgenode *p; int j; int visitedmaxlen;/*访问标志数组,访问过为1,未访问过为0*/ for(j=0;j<adjl.vexnum;j+) visitedj=0;/*初始化,所有点都未访问*/ printf("%4c->",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.vexnum;j+) visitedj=0;/*初始化所有点*/ initqueue(q); printf("%4c->",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;/*权值*/