数据结构实验源代码.doc

第2章#include#includetypedef struct data /定义一个结构体data int num; /用于存放人的序号 int val; /用于存放密码typedata;typedef struct node /定义一个结构体（结点），其中包含一个数据域和一个指针域 typedata data; /结构体的嵌套 struct node *next;listnode;typedef listnode *linklist;linklist head;int main(void)/ 进入主函数 int n,i,b,m,j; linklist head=(listnode *)malloc(sizeof(listnode); /申请一个空间（头结点 head） listnode *p,*q; /定义两个可以指向结点的指针 printf(输入总人数：); scanf(%d,&n); q=head; /用指针q指向头结点 for(j=1;jnext=(listnode *)malloc(sizeof(listnode); /将头结点的next域指向刚生成的一个结点 q=q-next; q-data.val=b; /输入密码 q-data.num=j; /输入序号 q-next=head-next; /将尾结点的next域指向第一个结点，构成循环链表 printf(请输入一个数m：); scanf(%d,&m); if(mnext; i+; p=q-next; /p指向输出结点 q-next=p-next; /将输出结点的前结点的next域指向输出结点的后结点 printf(num:%dtval:%dn,p-data.num,p-data.val); /输出 m=p-data.val; /取得输出结点的密码 free(p); while(q-next!=q); /只剩最后一个结点时结束 printf(num:%dtval:%dn,q-data.num,q-data.val); /输出最后一个结点 free(q); /释放最后一个结点 free(head); /释放头结点 system(pause);第3章（1）#include#include#include#define M 4#define N 6#define MaxSize 100using namespace std;int mgM+2N+2=1,1,1,1,1,1,1,1,1,0,0,1,0,0,0,1,1,1,0,0,0,0,0,1,1,0,0,1,0,1,0,1,1,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,;struct int i,j,di;StackMaxSize,PathMaxSize;int top=-1;int count=1;int minlen=MaxSize;void Print()for(int i = 0;i M+2;i+)for(int j = 0;j N+2;j+)if(mgij) cout1 ;else cout0 ;cout-1) i=Stacktop.i;j=Stacktop.j;di=Stacktop.di;if(i=M&j=N) coutcount+endl; for(k=0;k=top;k+) cout(Stackk.i,Stackk.j) ; if(k+1)%5=0)coutn; coutn; if(top+1minlen) for(k=0;k=top;k+) Pathk=Stackk; minlen=top+1; mgStacktop.iStacktop.j=0; top-; i=Stacktop.i; j=Stacktop.j; di=Stacktop.di;find=0;while(di4&find=0) di+; switch(di) case 1:i=Stacktop.i;j=Stacktop.j+1;break; case 2:i=Stacktop.i+1;j=Stacktop.j;break; if(mgij=0) find=1;if(find=1) Stacktop.di=di; top+; Stacktop.i=i; Stacktop.j=j; Stacktop.di=-1; mgij=-1;else mgStacktop.iStacktop.j=0; top-; cout最短路径如下：n; cout长度:minlenendl; cout路径:; for(k=0;kminlen;k+) cout(Pathk.i,Pathk.j) ;if(k+1)%5=0) coutn; coutn;int main() cout迷宫地图如下n; Print(); cout迷宫所有路径如下：n; mgpath(); getch();（2）#include#include#include #include #include #define LEN sizeof(STACK) typedef struct node int data; struct node *link;STACK50,*STLink;STLink top50; void init(STLink top,int m) /*初始化堆栈*/ topm=NULL; int empty( STLink top,int n) /*判断是否为空*/ return (topn=NULL); int push(STLink top,int A,int m) /*入栈*/ STLink p; if(!(p=(STLink)malloc(LEN) return 0; else p-data=A; p-link=topm; topm=p; return 1; int pop(STLink top,int m) /*出栈*/ int A; STLink p; p=topm; A=p-data; topm=topm-link; free(p); return A; int trainpush(int M,int A,STLink top) int m,k=0,l; topk=NULL; /* 初始化第一个堆栈 */ push(top,A0,0); /*把第一节车厢压入缓冲铁轨*/ printf(缓冲铁轨: 1 栈顶值:%dn,top0-data); for(m=1;mtopk-data) /*前面所有栈顶值最大值一定为最后一个栈的栈顶值，如果此次需 进栈的车厢号比前面所有栈顶值都大重新建立一个新的栈并把车厢号压入新的栈的栈底*/init(top,+k); push(top,Am,k);printf(缓冲铁轨：%d 栈顶值：%dn,k+1,topk-data);else /* 将此次需进栈的车厢号与所有栈顶值比较，插入到第一次遇到的栈顶值比将要入栈的车厢号要大的栈中，比如要插入10号车厢，缓冲铁轨的栈顶值排列如下：2、11、5、12，13，将10插在11所在的栈的栈顶*/ l=0;while(ltopl-data)l+; elsepush(top,Am,l);printf(缓冲铁轨: %d 栈顶值:%dn,l+1,topl-data);l=k+1; return k+1; void trainpop(int M,int A,STLink top,int N) int m,n=0,min,l=0,amin=0,bmin=0; /*把所有车厢都压出缓冲铁轨*/ min=topn-data;for(m=0;mM;m+) for(l=n+1;ldatadata; amin=l; /*将栈顶值最小的栈的栈号保存起来*/ Am=pop(top,amin); /*把最小的栈顶元素压出栈并赋值给A*/ printf(A%d=%dn,m,Am); if(topamin=NULL) min=topamin+1-data; n=amin+1; else min=topamin-data; n=amin; int main(void)int i,M,A100,N=0;printf(请输入火车车厢总长：); scanf(%d,&M);printf(请输入未转轨前车厢的排列顺序，不能输入重复相同数据且不可遗漏车厢号n);for(i=0;iM;i+)scanf(%d,&Ai); for(i=0;iM;i+) printf(A%d=%dn,i,Ai); N=trainpush(M,A,top); printf(所使用的缓冲铁轨数为:); printf(%dn,N); printf(火车转轨后，出轨顺序如下，请核对是否是所需顺序:n); trainpop(M,A,top,N); system(pause);第5章#include #includeint i,j,n,a1616; /*全局定义方阵行、列、阶数以及最大方阵容量*/void creat() /*建立魔方阵*/ int k; j=n/2+1; a1j=1; for(k=2;k=n*n;k+) i=i-1; j=j+1; if(in) i=i+2; j=j-1; else if(in) j=1; if(aij=0) aij=k; else i=i+2; j=j-1; aij=k; void print() /*输出魔方阵*/ for(i=1;i=n;i+) for(j=1;j=n;j+) printf(%5d,aij); printf(n); void main() int k,p,m; while(1) p=1; while(p=1) printf(请输入n(n=15,n是奇数)n); scanf(%d,&n); if(n!=0)&(n=15)&(n%2!=0) printf(矩阵阶数是:%dn,n); p=0; else printf(输入错误 请重新输入n); for(i=1;i=n;i+) for(j=1;j=n;j+) aij=0; creat(); print(); 第6章#include #include #include #define VERBOSEusing namespace std;short father512;unsigned short code256, heap_length;unsigned long compress_charcount, file_size, heap257;unsigned char code_length256;long frequency_count512;short decomp_tree512;FILE *ifile, *ofile;void build_decomp_tree (), decompress_image ();void decompress(char f1,char f2),compress(char f1,char f2);unsigned short generate_code_table ();void build_code_tree (), build_initial_heap ();void compress_image (), compression_report ();void get_frequency_count ();int main ()char ch,file212;coutendl;coutendl;cout 哈夫曼编码 endl;coutendl;cout *1. 压缩文件 *2. 解压文件 *3.退出endl;coutendl;coutch;while(ch)switch(ch)case 1:printf (nHUFF1: Huffman Code Compression Program.);printf (n 14-Aug-90 Bill Demas. Version 1.0nn);printf( 压缩文件名:);scanf(%s,&file0);printf( 生成文件名:);scanf(%s,&file1);compress(file0,file1);ch=0;break;case 2:printf (nDHUFF: Huffman Code Decompression Program.);printf (n 14-Aug-90 Bill Demas. Version 1.0nn);printf( 解压文件名:);scanf(%s,&file0);printf( 生成文件名:);scanf(%s,&file1);decompress(file0,file1);ch=0;break;case 3:exit(0);break;default:coutch;void compress(char *f1,char *f2)if (ifile = fopen (f1, rb) != NULL)fseek (ifile, 0L, 2);file_size = (unsigned long) ftell (ifile); #ifdef VERBOSE printf (1) Getting Frequency Counts.n); #endif fseek (ifile, 0L, 0); get_frequency_count (); #ifdef VERBOSE printf (2) Building Initial Heap.n); #endif build_initial_heap (); #ifdef VERBOSE printf (3) Building the Code Tree.n); #endif build_code_tree (); #ifdef VERBOSE printf (4) Generating the Code Table.n); #endif if (!generate_code_table () printf (ERROR! Code Value Out of Range. Cannot Compress.n); else #ifdef VERBOSE printf (5) Compressing & Creating the Output File.n); #endif if (ofile = fopen (f2, wb) != NULL) fwrite (&file_size, sizeof (file_size), 1, ofile); fwrite (code, 2, 256, ofile); fwrite (code_length, 1, 256, ofile); fseek (ifile, 0L, 0); compress_image (); fclose (ofile); else printf(nERROR: Couldnt create output file n); #ifdef VERBOSE compression_report (); #endiffclose (ifile); else printf (nERROR: - File not found!n);void decompress(char *f1,char *f2) /解压if (ifile = fopen (f1, rb) != NULL) fread (&file_size, sizeof (file_size), 1, ifile); fread (code, 2, 256, ifile); fread (code_length, 1, 256, ifile); #ifdef VERBOSE printf (1) Building the tree.n); #endif build_decomp_tree (); #ifdef VERBOSE printf (2) Decompressing & Creating the Output File.n); #endif if (ofile = fopen (f2, wb) != NULL) decompress_image(); fclose (ofile); else printf (nERROR: Couldnt create output file n); fclose (ifile); else printf (nERROR: - File not found!n);/decompressvoid build_decomp_tree () register unsigned short loop1; register unsigned short current_index; unsigned short loop; unsigned short current_node = 1; decomp_tree1 = 1; for (loop = 0; loop 0; loop1-) current_index = (decomp_treecurrent_index loop1) & 1); if (!(decomp_treecurrent_index) decomp_treecurrent_index = +current_node; decomp_tree(decomp_treecurrent_index 1) + (codeloop & 1) = -loop; void decompress_image () register unsigned short cindex = 1; register char curchar; register short bitshift; unsigned long charcount = 0L; while (charcount = 0; -bitshift) cindex = (cindex bitshift) & 1); if (decomp_treecindex = 0) putc (int) (-decomp_treecindex), ofile); if (+charcount) = file_size) bitshift = 0; else cindex = 1; else cindex = decomp_treecindex; /压缩void reheap (unsigned short heap_entry) register unsigned short index; register unsigned short flag = 1; unsigned long heap_value; heap_value = heapheap_entry; while (heap_entry 1) & (flag) index = heap_entry 1; if (index = frequency_countheapindex+1) index+; if (frequency_countheap_value frequency_countheapindex) flag-; else heapheap_entry = heapindex; heap_entry = index; heapheap_entry = heap_value;void compress_image () register unsigned int thebyte = 0; register short loop1; register unsigned short current_code; register unsigned long loop; unsigned short current_length, dvalue; unsigned long curbyte = 0; short curbit = 7; for (loop = 0L; loop = 0; -loop1) if (current_code loop1) & 1) thebyte |= (char) (1 curbit); if (-curbit 0) putc (thebyte, ofile); thebyte = 0; curbyte+; curbit = 7; putc (thebyte, ofile); compress_charcount = +curbyte;void compression_report () float savings; unsigned short header_charcount; unsigned long output_characters; header_charcount = 768 + sizeof (file_size); output_characters = (unsigned long) header_charcount +compress_charcount; printf (nRaw characters : %ldn, file_size); printf (Header characters : %dn, header_charcount); printf (Compressed characters : %ldn, compress_charcount); printf (Total output characters : %ldn, output_characters); savings = 100 - (float) output_characters / (float) file_size) * 100; printf (nPercentage savings : %3.2f%n, savings);unsigned short generate_code_table () register unsigned short loop; register unsigned short current_length; register unsigned short current_bit; unsigned short bitcode; short parent; for (loop = 0; loop 256; loop+) if (frequency_countloop) current_length = bitcode = 0; current_bit = 1; parent = fatherloop; while (parent) if (parent 0) bitcode += current_bit; parent = -parent; parent = fatherparent; current_bit 16) return (0); else code_lengthloop = (unsigned char) current_length; else codeloop = code_lengthloop = 0; return (1);void build_code_tree () register unsigned short findex; register unsigned long heap_value; while (heap_length != 1) heap_value = heap1; heap1 = heapheap_length-; reheap (1); findex = heap_length + 255; frequency_countfindex = frequency_countheap1 + frequency_countheap_value; fatherheap_value = findex; fatherheap1 = -findex; heap1 = findex; reheap (1); father256 = 0;void build_initial_heap () register unsigned short loop; heap_length=0; for (loop=0; loop0;loop-) reheap(loop);void get_frequency_count () register unsigned long loop; for (loop = 0; loop next=NULL; retu