2022年数据结构算法源代码 .pdf

《2022年数据结构算法源代码 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构算法源代码 .pdf（17页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、#include#include#include#include#include/*声明两种链表结构-start*/struct node_a/*链表 1-作用：用来统计文件中字符的个数和种类（通过count）*/char data;int count;struct node_a*next;typedef struct node_a node,*list;list head=NULL;struct nodeb/*链表 2-作用：用来建立用相应的编码代替字符的新文件*/char data;struct nodeb*next;typedef struct nodeb node_b,*list_b;

2、/*jiang bianma xieru wenjian*/list_b head_b=NULL;/*声明两种链表结构-end*/*哈夫曼算法种相关的3 种结构的声明-start*/struct forest float weight;int root;struct alphabet char symbol;float probability;int leaf;char*bianma;struct tree int lchild;int rchild;int parent;typedef struct tree*tree_ptr,tree_node;typedef struct forest*

3、forest_ptr,forest_node;typedef struct alphabet*alphabet_ptr,alphabet_node;tree_ptr tree1;forest_ptr forest1;名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 17 页 -alphabet_ptr alphabet1;int lasttree,lastnode;int least,second;/*哈夫曼算法种相关的3 种结构的声明-end*/*stack difination start*/struct stacknode char*bian_ma;struct stackn

4、ode*next;typedef struct stacknode stack_node;typedef stack_node*link;link top=NULL;void push(char*item)link p;if(top!=NULL)p=(link)malloc(sizeof(stack_node);if(p=NULL)printf(Memory allocation error!);return;p-bian_ma=item;p-next=top;top=p;else top=(link)malloc(sizeof(stack_node);if(!top)printf(Memor

5、y allocation error!);return;top-bian_ma=item;top-next=NULL;void pop(void)link p;p=top;top=top-next;free(p);名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 17 页 -void makenull(void)while(top!=NULL)pop();int empty()if(top=NULL)return 1;else return 0;char*tops(void)return(top-bian_ma);void display_stack(link s)/*显示栈重的内

6、容*/link ptr;ptr=s;while(ptr!=NULL)printf(%s,ptr-bian_ma);ptr=ptr-next;/*stack_difination is end*/void display(list h)/*显示链表1*/list ptr;int i=1;ptr=h-next;while(ptr!=NULL)printf(%d,%c,%dn,i,ptr-data,ptr-count);i+;ptr=ptr-next;void display_b(list_b h)/*显示链表2*/list_b ptr;int i=1;ptr=h-next;while(ptr!=N

7、ULL)printf(%d,%cn,i,ptr-data);i+;ptr=ptr-next;名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 17 页 -void insert(char item)/*用于插入元素以建立链表1*/list temp,ptr;int flag;ptr=head-next;if(ptr=NULL)head-next=(list)malloc(sizeof(node);head-next-data=item;head-next-count=1;head-next-next=NULL;else while(ptr!=NULL)if(ptr-data=ite

8、m)ptr-count=ptr-count+1;flag=1;ptr=ptr-next;ptr=head;if(flag=1)return;else temp=ptr-next;ptr-next=(list)malloc(sizeof(node);ptr-next-data=item;ptr-next-count=1;ptr-next-next=temp;void insert_b(char item)/*插入元素以建立链表2*/list_b ptr_b,temp_b;ptr_b=head_b;if(ptr_b-next=NULL)head_b-next=(list_b)malloc(size

9、of(node_b);head_b-next-data=item;head_b-next-next=NULL;else while(ptr_b-next!=NULL)名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 17 页 -ptr_b=ptr_b-next;ptr_b-next=(list_b)malloc(sizeof(node_b);ptr_b-next-data=item;ptr_b-next-next=NULL;void search(void)/*搜索文件并将文件中的数据分别存入作用不同的链表中*/FILE*fp;list ptr;char ch;if(fp=fope

10、n(test.txt,r)=NULL)printf(Reading error!n);while(!feof(fp)ch=getc(fp);if(ferror(fp)printf(error!n);break;if(ch=EOF)break;insert(ch);/*插入元素进链表1*/insert_b(ch);/*插入元素进链表2*/printf(n);fclose(fp);void display_struct(int n)/*显示哈夫曼算法中的3 个结构树组*/int i=0;printf(nn=nn);printf(FOREST_STRUCT_ARRY:nnn);for(i=0;i=n

11、;i+)printf(%f,%dn,forest1i.weight,forest1i.root);getch();printf(nnALPHABET_STRUCT_ARRY:nnn);for(i=0;i=n;i+)printf(%f,%d,%cn,alphabet1i.probability,alphabet1i.leaf,alphabet1i.symbol);getch();printf(nnTREE_STRUCT_ARRY:nnn);for(i=0;inext;while(ptr!=NULL)count=ptr-count+count;n+;ptr=ptr-next;ptr=head-ne

12、xt;forest1=(forest_ptr)malloc(sizeof(forest_node)*n+sizeof(forest_node);alphabet1=(alphabet_ptr)malloc(sizeof(alphabet_node)*n+sizeof(alphabet_node);tree1=(tree_ptr)malloc(sizeof(tree_node)*n*2-sizeof(tree_node);forest10.weight=alphabet10.probability=0.0;forest10.root=alphabet10.leaf=0;alphabet10.sy

13、mbol=0;while(ptr!=NULL)forest1i.weight=alphabet1i.probability=ptr-count/count;forest1i.root=alphabet1i.leaf=i;alphabet1i.symbol=ptr-data;i+;ptr=ptr-next;for(i=0;i=2*n-1;i+)tree1i.lchild=0;tree1i.rchild=0;tree1i.parent=0;return n;void creat(void)/*创建正文文件test.txt*/FILE*fp,*out;char ch;if(fp=fopen(test

14、.txt,r+)=NULL)printf(Creat error!n);printf(Input the data:n);ch=getch();名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 17 页 -putch(ch);while(ch!=#)putc(ch,fp);ch=getch();putch(ch);fclose(fp);void creat_bianma(int number)/*根据哈夫曼算法建立文件中各种字符对应的编码*/int i,j,n;int p;char*bm=malloc(sizeof(char)*number);for(n=1;nnext;if(fp

15、=fopen(bianma.txt,w)=NULL)printf(Write in a new file error!);else while(ptr!=NULL)for(i=1;idata=alphabet1i.symbol)strcpy(ch,alphabet1i.bianma);fputs(ch,fp);ptr=ptr-next;fclose(fp);void main(void)int i,num;char ch;void huffman(void);void lightones();head=(list)malloc(sizeof(node);head-next=NULL;head-

16、data=0;head-count=0;head_b=(list_b)malloc(sizeof(node_b);head_b-data=0;head_b-next=NULL;do system(cls);creat();search();printf(nlianbiao1:n);display(head);/*显示链表1*/getch();printf(nlianbiao2:n);display_b(head_b);getch();名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 17 页 -num=init_struct();printf(n);printf(The 3 ini

17、t_struct of huffman?n);display_struct(num);/*显示初始化的哈夫曼书的相关3 个结构数组*/lastnode=num;lasttree=num;huffman();printf(Now the 3 struct through huffman shuanfan);display_struct(num);/*显示哈夫曼树中相关的3 种结构（经过哈夫曼算法处理）*/printf(nThe bian_ma is:n);creat_bianma(num);write_new_file(num);printf(nDo you want to re_try(y/n

18、)?);ch=getchar();while(ch=y);/*哈夫曼算法-defination_start*/void lightones(void)int i;if(forest11.weight=forest12.weight)least=1;second=2;else least=2;second=1;for(i=3;i=lasttree;i+)if(forest1i.weightforest1least.weight)second=least;least=i;else if(forest1i.weight1)lightones();i=least;j=second;newroot=cr

19、eat_tree(i,j);forest1i.weight=forest1i.weight+forest1j.weight;forest1i.root=newroot;forest1j=forest1lasttree;lasttree=lasttree-1;#include#include#include#define n 6#define m 2*n-1 typedef struct float weight;int lchild,rchild,parent;codenode;typedef codenode huffmantreem;typedef struct char ch;char

20、bitsn+1;code;typedef code huffmancoden;void inithf(huffmantree T)/哈夫曼树的初始化 int i;for(i=0;im;i+)Ti.weight=0;Ti.parent=-1;Ti.lchild=-1;Ti.rchild=-1;名师资料总结-精品资料欢迎下载-名师精心整理-第 10 页，共 17 页 -void inputhf(huffmantree T)/输入哈夫曼树的树据 int i;float k;for(i=0;in;i+)scanf(%f,&k);Ti.weight=k;void selectmin(huffmantre

21、e T,int k,int*p1,int*p2)int i;float small1=10000,small2=10000;for(i=0;i=k;i+)if(Ti.parent=-1)if(Ti.weightsmall1)small2=small1;small1=Ti.weight;*p2=*p1;*p1=i;else if(Ti.weightsmall2)small2=Ti.weight;*p2=i;void creathftree(huffmantree T)/建哈夫曼树 int i,p1,p2;inithf(T);inputhf(T);for(i=n;im;i+)selectmin(T

22、,i-1,&p1,&p2);Tp1.parent=Tp2.parent=i;Ti.lchild=p1;Ti.rchild=p2;Ti.weight=Tp1.weight+Tp2.weight;void creathfcode(huffmantree T,huffmancode H)/哈夫曼编码表 int i,c,p,start;char cdn+1;cdn=0;for(i=0;i=0)cd-start=(Tp.lchild=c)?0:1;c=p;strcpy(Hi.bits,&cdstart);void zip(huffmancode H,char*ch,char*s)/编码 int j=0;

23、char*pn;unsigned int i;for(i=0;istrlen(ch);i+)while(chi!=Hj.ch)j+;pi=Hj.bits;strcpy(s,p0);for(i=1;in;i+)strcat(s,pi);puts(s);void uzip(huffmancode H,char*s,huffmantree T)/解码 int j=0,p;unsigned int i;char chn+1;while(istrlen(s)p=m-1;while(Tp.lchild!=-1)if(s i=0)p=Tp.lchild;i+;else p=Tp.rchild;i+;chj=

24、Hp.ch;j+;chj=0;puts(ch);main()char ch=abcdef,s36;huffmantree T;huffmancode H;creathftree(T);getchar();creathfcode(T,H);名师资料总结-精品资料欢迎下载-名师精心整理-第 12 页，共 17 页 -zip(H,ch,s);uzip(H,s,T);/*这是我在这里帮落尘改写的程序，今天又吧它改写成了c 的借鉴一下吧*/#include#include typedef struct node int data;struct node*lchild,*rchild;*treetp,tr

25、ee;treetp create(treetp t,int c);void print1(treetp);void print2(treetp);void print3(treetp);int number=0;void main()treetp t=0,r;r=create(t,0);printf(前序排列：);print1(r);printf(n 中序排列：);print2(r);printf(n 后序排列：);print3(r);treetp create(treetp t,int c)treetp p,di;do scanf(%d,&c);if(t=0)t=(treetp)malloc

26、(sizeof(tree);t-lchild=t-rchild=0;t-data=c;else p=t;while(p!=0)名师资料总结-精品资料欢迎下载-名师精心整理-第 13 页，共 17 页 -di=p;if(cdata)p=p-lchild;else p=p-rchild;if(cdata)treetp NEWdi=(treetp)malloc(sizeof(tree);NEWdi-lchild=NEWdi-rchild=0;NEWdi-data=c;di-lchild=NEWdi;else treetp NEWdi=(treetp)malloc(sizeof(tree);NEWdi

27、-lchild=NEWdi-rchild=0;NEWdi-data=c;di-rchild=NEWdi;+number;while(c!=0);printf(叶子的数量：%d,number);return t;void print1(treetp t)if(t!=0)printf(%d,t-data);print1(t-lchild);print1(t-rchild);void print2(treetp t)if(t!=0)print2(t-lchild);printf(%d,t-data);print2(t-rchild);名师资料总结-精品资料欢迎下载-名师精心整理-第 14 页，共 1

28、7 页 -void print3(treetp t)if(t!=0)print3(t-lchild);print3(t-rchild);printf(%d,t-data);#include#include#define MAX 20#define ELEMTP int#define v(*p)struct sequnce ELEMTP elemMAX;int len;main()struct sequnce*pz;int i,y,cord;void outlin(struct sequnce s);void create(struct sequnce*p);void insert(struct

29、 sequnce*p,int i,int x);void deletes(struct sequnce*p,int i);do printf(n 主菜单n);printf(1 建立线性表n);printf(2 插入一个元素n);printf(3 删除一个元素n);printf(4 结束程序运行n);printf(-n);printf(请输入您的选择(1,2,3,4);scanf(%d,&cord);switch(cord)case 1:名师资料总结-精品资料欢迎下载-名师精心整理-第 15 页，共 17 页 -pz=(struct sequnce*)malloc(sizeof(struct s

30、equnce);create(pz);outlin(*pz);break;case 2:printf(请输入插入的位置i:);scanf(%d,&i);printf(请输入插入的数据y:);scanf(%d,&y);insert(pz,i,y);outlin(*pz);break;case 3:scanf(%d,&i);deletes(pz,i);outlin(*pz);break;case 4:exit(0);while(cord=4);void outlin(struct sequnce s)int i;for(i=1;i=s.len;i+)printf(%2d%6dn,i,s.elemi

31、);void deletes(struct sequnce*p,int i)int j;if(iv.len)printf(i,位置不存在);else for(j=i;jv.len;j+)v.elemj=v.elemj+1;v.len-;名师资料总结-精品资料欢迎下载-名师精心整理-第 16 页，共 17 页 -void insert(struct sequnce*p,int i,int x)int j;if(iv.len+1)printf(i 位置不存在。);else for(j=v.len;j=i;j-)v.elemj+1=v.elemj;v.elemi=x;v.len+;void create(struct sequnce*p)int i;printf(n=);scanf(%d,&(v.len);for(i=1;i=v.len;i+)printf(data=);scanf(%d,&(v.elemi);名师资料总结-精品资料欢迎下载-名师精心整理-第 17 页，共 17 页 -