数据结构课程设计报告_二叉树_哈弗曼_链表.doc

北京xx大学数据结构课程设计(报告)院 （系）：计算机与信息工程学院班 级:软件082学 号:xxxxxxx姓 名:xxxxxxx同组学生：_指导教师_成 绩_实践地点：_实践时间：2010年5月1日至2010年5月20日二叉树的操作：实验目的：建立二叉树，建立后的先序。中序。后序。的遍历，及输出。思路：用递归的方法建立二叉树，用先序建立，然后调整建立时左右孩子，和根结点的顺序，就完成了，三种顺序的遍历。遇到的困难：在先序建立时忘记了用#符号表示该节点没有孩子。如何解决的：用if(ch=#) t=null;语句解决。收获：明白了，二叉树的三种建立，和他们之间的区别以及递归的一些简单的应用。运行结果：输入数字元素用#表示结点没有左孩子或右孩子。然后屏幕上显示出三种顺序的遍历。#include#include#define null 0#define overflow -2#define ok 1typedef int status;typedef struct treenode char data; treenode *lchild,*rchild;*diaotree;status creat_tree(diaotree &t);status preorder_traversal(diaotree &t);status inorder_traversal(diaotree &t);status postorder_traverse(diaotree &t);void main() diaotree t; cout先序建立:;coutendl;cout输入元素: ;creat_tree(t); cout先序遍历: ;preorder_traversal(t); coutendl;cout中序遍历: ;inorder_traversal(t); coutendl; cout后续遍历: ;postorder_traverse(t); coutch; if(ch=#) t=null; else t=(diaotree)malloc(sizeof(treenode);if(!t) exit(overflow); t-data=ch;creat_tree(t-lchild);creat_tree(t-rchild); return ok;status preorder_traversal(diaotree &t) if(t) coutdatalchild); preorder_traversal(t-rchild);return ok;status inorder_traversal(diaotree &t) if(t) inorder_traversal(t-lchild); coutdatarchild); return ok;status postorder_traverse(diaotree &t)if(t) postorder_traverse(t-lchild); postorder_traverse(t-rchild); coutdata ; return ok;哈夫曼编码：实验目的：给出各节点权值的大小，然后建立哈弗曼树，然后根据哈弗曼树给对应的权值生成对应的不等长的二进制编码。思路：先输入权值的个数，然后输入权值的大小，再输入对应权值的英文字母，然后对每个结点的父亲，左右孩子进行初始化赋0，然后用select函数建立哈弗曼树，然后存储根据求出的哈弗曼表建立哈弗曼码，选用左孩子为零右孩子为一，最后得出各个英文字母所对应的不等长的二进制编码。遇到的难点：如何编写select选择函数。如何解决的：先判断所有结点的父亲是否为零，然后把父亲为零的权值放入一个新建立的int行数组中，然后在数组中进行大小排序，先两个树是两个权值最小的。然后再把原数组中两个最小的权值的数组下标给新的结点当左右孩子，新节点就是这两个节点的父亲。收获：了解了哈弗曼树的建立，以及怎样自己编写select函数。运行结果：先输入权值的个数，再输入对应权值的英文字母，再输入对应英文字母的权值的大小，会显示各节点权值的大小，也就是哈弗曼树的建立，在输出各英文字母对应的不等长的二进制编码 #include#include#include#include#define ok 1#define overflow -1 #define null 0typedef struct diaochar data;int weight;int parent;int lchild;int rchild;diao,* dt;typedef char * *hc;int select(dt &tree,int i,int &m1,int &m2);void main()int n,m,i;cout请输入权值的个数n;m=2*n-1;dt tree;tree=(dt)malloc(m+1)*sizeof(diao);cout请输入英文字母endl;for(i=1;itreei.data;coutendl;cout请输入对应权值的大小endl;for(i=1;ix;treei.weight=x;for(i=1;i=n;i+)treei.parent=0;static int s1,s2;for(i=n+1;i=m;i+) select(tree,i,s1,s2);trees1.parent=i;trees2.parent=i;treei.lchild=s1;treei.rchild=s2;treei.weight=trees1.weight+trees2.weight;treei.parent=0;cout各结点的权值endl;int h=0; for(h=1;h=m;h+)couttreeh.weight ; coutendl;hc diaocode;int start,c,f;diaocode=(hc)malloc(m+1)*sizeof(char *);char *cd;cd=(char *)malloc(n*sizeof(char);cdn-1=0;for(i=1;i=n;i+)start=n-1;for(c=i,f=treei.parent;f!=0;c=f,f=treef.parent)if(treef.lchild=c) cd-start=0;else cd-start=1;diaocodei=(char *)malloc(n-start)*sizeof(char);strcpy(diaocodei,&cdstart);free(cd);cout个英文字母的编码为endl;for(i=1;i=n;i+)couttreei.data的编码为diaocodeiendl;int select(dt &tree,int i,int &m1,int &m2)int t,m,temp;int p=0;for(t=0;ti-1;t+)if(treet+1.parent=0)p=p+1;int a100;int j=0;for(t=0;ti-1;t+)if(treet+1.parent=0)aj=treet+1.weight;j=j+1;for(t=0;t=p-1;t+)for(m=t+1;mam)temp=at;at=am;am=temp;for(t=0;ti-1;t+)if(treet+1.weight=a0)&(treet+1.parent=0)break;m1=t+1;treet+1.parent=i; for(t=0;ti-1;t+)if(treet+1.weight=a1)&(treet+1.parent=0)break;m2=t+1;treet+1.parent=i;return ok;链表的操作：实验目的：先建立单链表，然后进行链表的添加，删除操作，最后进行约瑟夫环的形成。思路：用正序建立单链表，然后进行添加，删除，操作，在把单链表改成循环链表，罪行约瑟夫环，我的约瑟夫环本质上和递归类似。遇到的难点：如何建立约瑟夫环。怎么解决的：先把单链表变成循环链表，然后用while循环判断元素是否为一个，当不为一个时继续循环，在while函数中有一个for循环次数为约瑟夫环要进行到第几个删除的次数，在for循环后面加一个删除函数来删掉刚才循环倒的树，知道最后剩一个。收获：知道了单链表的建立，以及添加，删除等操作，知道了怎样把单链表变成循环链表，以及约瑟夫环的建立。运行结果：先输入链表的长度，再输入个元素的大小，显示结果，爱输入添加到第几项，添加项的大小，显示链表，再输入要删除第几项，显示结果。再输入约瑟夫环中以几为一个循环，也就是数到几杀人，然后显示最后一个剩下的元素大小。#include#include#define ok 1 #define null 0#define overflow -1typedef struct diaoint data;struct diao *next;diao, * diaoinit;int diaolist(diaoinit &l,int n);int adddiao(diaoinit &l,int n,int e);int deletediao(diaoinit &l,int n);int delete2(diaoinit &l);void main()diaoinit l;int n;cout请输入链表的长度n;cout请输入各元素的大小next; int i;cout链表的结果为endl;for(i=0;in;i+)coutdatanext;coutendl;int x,e;cout请输入添加第几项x;cout请输入添加数的大小e;adddiao(d,x,e);diaoinit m;m=d;d=d-next;cout链表的结果为endl;for(i=0;in+1;i+)coutdatanext;coutendl;cout请输入删除链表的第几项o;deletediao(m,o);cout链表的结果为endl;for(i=0;in;i+)coutnext-datanext;cout约瑟夫环的循环数r;while(!(n=1)for(i=0;inext;delete2(m);n-;cout最后剩下的数字是endl;coutdata;int diaolist(diaoinit &l,int n)l=(diaoinit)malloc(sizeof(diao);l-next=null;diaoinit tail;tail=l;int i;diaoinit p;for(i=0;ip-data;tail-next=p;tail=p;tail-next=l-next;return ok;int adddiao(diaoinit &l,int n,int e)diaoinit p;diaoinit s;s=(diaoinit)malloc(sizeof(diao);p=(diaoinit)malloc(sizeof(diao);s-next=null;s-data=e;p=l;int i;for(i=0;inext;s-next=p-next; p-next=s;return ok;int deletediao(diaoinit &l,int n)int x;diaoinit q;q=l;for(x=0;xnext;q-next=q-next-next;return ok ;int delete2(diaoinit &l)l-next=l-next-next;return ok;顺序表的操作：实验目的：顺序表的建立，以几添加删除的操作。思路：建立顺序表。遇到的困难：再添加删除早做事，经常显示没有添加，lenght在添加，删除后没有进行对应的加或者减。解决的方法：对lenght进行加或减。收获：知道了顺序表的建立，添加删除操作，以几必须改变lenght的值。运行结果：先输入表长的大小，再输入对应各个数字，显示结果，再输入添加的位置，添加数的大小，显示结果，再输入删除的位置，显示结果。#include#include#define ok 1#define null 0#define overflow -1#define list_init_size 100#define increamlist 20typedef struct dingint *elem;int listsize;int length;diao;int initlist(diao &l);int addlist(diao &l,int m,int k);int deletelist(diao &l,int m);void main()cout顺序表的操作endl;diao l;initlist(l);int i,n;cout请输入数字的数量n;cout请输入个数字的大小endl;for(i=0;il.elemi;cout显示个数字的大小endl;for(i=0;in;i+)coutl.elemi ;coutendl;l.length=n;cout请输入加入数字的位置o;cout请输入加入数字的大小u;addlist(l,o,u);cout各数字的大小为endl;for(i=0;in+1;i+)coutl.elemi ;l.length+;coutendl;cout请输入删除数字的位置m1;deletelist(l,m1);cout个数字的大小为endl;for(i=0;in;i+)coutl.elemi ; int initlist(diao &l)l.elem=(int *)malloc(list_init_size*sizeof(int);if(!l.elem) exit(overflow);l.length=0;l.listsize=list_init_size;return ok ;int addlist(diao &l,int m,int k)if(ml.length+1) exit(overflow);if(l.length=l.listsize)int *newbase;newbase=(int *)realloc(l.elem,(l.listsize+increamlist)*sizeof(int);l.elem=newbase;l.listsize=l.listsize+increamlist;int *q,*p;q=&l.elemm-1;for(p=&l.eleml.length-1;p=q;p-)*(p+1)=*p;*q=k;l.length+;return ok;int deletelist(diao &l,int m)if(ml.length+1) exit(overflow);int *p,*q;p=&l.elemm-1;q=&l.eleml.length-1;for(p+;pq;p+)*(p-1)=*p;return ok;无向图邻接表实验目的：无向图邻接表的建立。思路：把每个头结点的后面都链成用表结点做结点的链表。遇到的难点：如何把头结点和表结点连起来。解决的方法：用头结点中指向标结点的指针指向表结点，然后表结点再指向头结点，周而复始循环下去。收获：明白了图的建立，以及头结点，表结点还之间的连接。运行结果：输入头结点的个数的大小，然后依次输入节电元素的大小，输入边的个数，然后输入各条边的大小，如1 2, 3 4,算两条边。最后输出的是每个结点后面链表元素的数组下标#include#include#define maxvex 20#define ok 1#define null 0typedef struct arcnodeint dajvex;struct arcnode *nextarc;int weight;arcnode;typed