《2022年数据结构算法源代码借鉴》由会员分享，可在线阅读，更多相关《2022年数据结构算法源代码借鉴（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 stru
2、ct nodeb node_b,*list_b; /*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
3、tree *tree_ptr,tree_node; typedef struct forest *forest_ptr,forest_node; typedef struct alphabet *alphabet_ptr,alphabet_node; tree_ptr tree1; forest_ptr forest1; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 17 页 - - - - - - - - - alphabet_ptr alphabet1; int l
4、asttree,lastnode; int least,second; /*哈夫曼算法种相关的3 种结构的声明-end*/ /*stack difination start*/ struct stacknode char *bian_ma; struct stacknode *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_nod
5、e); 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(Memory allocation error!); return; top-bian_ma=item; top-next=NULL; void pop(void) link p; p=top; top=top-next; free(p); 名师资料总结 - - -精品资料欢迎下载 - - - -
6、- - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 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) /*显示栈重的内容*/ link ptr; ptr=s; while(ptr!=NULL) printf(%s,ptr-
7、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!=NULL) printf(%d,%cn,i,ptr-data);
8、 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; h
9、ead-next-next=NULL; else while(ptr!=NULL) if(ptr-data=item) 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_
10、b, temp_b; ptr_b=head_b; if(ptr_b-next=NULL) head_b-next=(list_b)malloc(sizeof(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
11、=(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=fopen(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(
12、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;i+) printf(%f,%dn,forest1i.weight,forest1i.root); getch(); printf(nnALPHABET_STRUCT_ARRY :nnn); for(i=0;i=n;i+) p
13、rintf(%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-next; forest1=(forest_ptr)malloc(sizeof(forest_node)*n+sizeof(forest_node); alphabet1=(alphabet_ptr)m
14、alloc(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.symbol=0; while(ptr!=NULL) forest1i.weight=alphabet1i.probability=ptr-count/count; forest1i.roo
15、t=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.txt,r+)=NULL) printf(Creat error!n); printf(Input the data:n); ch=getch();
16、 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 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=
17、1;nnext; if(fp=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
18、(node); head-next=NULL; head-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(); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - -
19、- - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 17 页 - - - - - - - - - num=init_struct(); printf(n); printf(The 3 init_struct of huffman?n); display_struct(num);/* 显示初始化的哈夫曼书的相关3 个结构数组 */ lastnode=num; lasttree=num; huffman(); printf(Now the 3 struct through huffman shuanfan); display_struct(num);/
20、* 显示哈夫曼树中相关的3 种结构（经过哈夫曼算法处理）*/ printf(nThe bian_ma is:n); creat_bianma(num); write_new_file(num); printf(nDo you want to re_try(y/n)?); 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; fo
21、r(i=3;i=lasttree;i+) if(forest1i.weightforest1least.weight) second=least; least=i; else if(forest1i.weight1) lightones(); i=least; j=second; newroot=creat_tree(i,j); forest1i.weight=forest1i.weight+forest1j.weight; forest1i.root=newroot; forest1j=forest1lasttree; lasttree=lasttree-1; #include #inclu
22、de #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 bitsn+1; code; typedef code huffmancoden; void inithf(huffmantree T) /哈夫曼树的初始化 int i; for(i=0;im;i+) Ti.weight=0; Ti.parent=-1; Ti.lchi
23、ld=-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(huffmantree T,int k,int *p1,int *p2) int i;float small1=10
24、000,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,i-1,&p1,&p2); Tp1.parent=Tp2
25、.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;char *pn; uns
26、igned 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.rchil
27、d;i+; chj=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); /*这是我在这里帮落尘改写的程序，今天又吧它改
28、写成了c 的借鉴一下吧 */ #include #include typedef struct node int data; struct node *lchild,*rchild; *treetp,tree; 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 中序排列：)
29、; 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(sizeof(tree); t-lchild=t-rchild=0; t-data=c; else p=t; while(p!=0) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 17 页 - - - - - -
30、- - - 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-lchild=NEWdi-rchild=0; NEWdi-data=c; di-rchild=NEWdi; +number; while(c!=0); printf
31、( 叶子的数量：%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 页，共 17 页 -
32、- - - - - - - - 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(str
33、uct sequnce *p); void insert(struct 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: 名师资料总结 - - -精品资料欢迎下载
34、- - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 17 页 - - - - - - - - - pz=(struct sequnce *)malloc(sizeof(struct sequnce); 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: sca
35、nf(%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); 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-; 名师资料总结 - - -精
36、品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 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 页 - - - - - - - - -
