C语言数据结构实验报告

1、江 西 科 技 师 范 学 院实 验 报 告课 程： 数据结构系 别： 数计学院班 级： 09计算机（1）班学 号： 张 抗姓 名： 报告规格一实验目的二实验原理三实验设备里面所有的实验的代码都在VC+上调试通过，可以直接复制运行。我的QQ是：。有其它问题的或者想要实验的代码的可以联系我。四实验内容五实验代码六实验结果1. 实验一：C语言编程2. 实验二：顺序存储3. 实验三：链式存储4. 实验四：模式匹配算法运用5. 实验五：特殊矩阵6. 实验六：内排序7. 实验七：内排序8. 实验八：图的遍历9. 实验九：检索10.11.12.13.14.15.目录每次实验课必须带上此本子，以便教师检查预

2、习情况和记录实验原始数据。实验时必须遵守实验规则。用正确的理论指导实践必须人人亲自动手实验，但反对盲目乱动，更不能无故损坏设备。这是一份重要的不可多得的自我学习资料，它将记录着你在大学生涯中的学习和学习成果。请你保留下来，若干年后再翻阅仍将感到十分新鲜，记忆犹新。它将推动你在人生奋斗的道路上永往直前！实验一 C语言编程实验名称：实验一 C语言编程实验目的：复习C语言程序设计，回顾C语言结构数据及指针数据的应用。实验原理：C语言结构化程序设计思想，结构数据类型，指针数据类型。实验设备：电脑，TURBO C2.0/WIN-TC/VISUAL C+实验内容：求两个复数相加之和。实验代码：#inclu

3、destruct comp /定义复数的类型结构 float x; float y;struct comp a,b,sum,jian1,mul1;int z;void main() void creat(struct comp*c); /声明所用到的函数 void output(struct comp a); struct comp add(struct comp k,struct comp h); struct comp jian(struct comp k,struct comp h); struct comp mul(struct comp k,struct comp h); creat

4、(&a);output(a); creat(&b);output(a); sum=add(a,b); printf(sum=); output(sum); jian1=jian(a,b); printf(jian=); output(jian1); mul1=mul(a,b); printf(mul=); output(mul1); getch();void creat(struct comp*c) /输入 float c1,c2; printf(please enter the record:);scanf(%f,&c1); printf(please enter the image:);s

5、canf(%f,&c2); c-x=c1;c-y=c2;void output(struct comp a) /输出 printf(%f+%finn,a.x,a.y);struct comp add(struct comp k,struct comp h) /相加 struct comp c; c.x=k.x+h.x; c.y=k.y+h.y; return(c);struct comp jian(struct comp k,struct comp h) /相减 struct comp c; c.x=k.x-h.x; c.y=k.y-h.y; return(c);struct comp mul

6、(struct comp k,struct comp h) /相乘 struct comp c; c.x=k.x*h.x-k.y*h.y; c.y=h.x*k.y+k.x*h.y; return(c);实验结果：实验心得：计算机事实上只能完成较简单的运算，不能完成较复杂的运算。但人们往往根据一些基本的法则和定理，通过转化，可以通过这些基本的加减乘除运算完成复杂的科学计算。这就像本实验，通过简单的加法和乘法对复数的实部和虚部分别计算，然后用特殊的方法将结果表示出来，完成了两个复数的各种运算。使会用者感觉就好像是直接进行了复数的运算。 实验二 顺序存储实验名称：实验二 顺序存储实验目的：掌握线性表

7、顺序存储结构的描述，学会针对顺序存储线性表的基本操作。实验原理：C语言结构化程序设计思想，结构体及数组的应用。实验设备：电脑，TURBO C2.0/WIN-TC/VISUAL C+实验内容：线性表的顺序存储表示及基本操作。实验代码：#include#include#define MAXSIZE 20typedef int ElemType; /定义所需的类型typedef struct ElemType aMAXSIZE; int length;SqList;SqList a,b,c; /定义所需的类型并声明所用到的函数void creat_list(SqList*L);void out_li

8、st(SqList L);void insert_sq(SqList*L,int i,ElemType e);ElemType delete_sq(SqList*L,int i);int locat_sq(SqList L,ElemType e);void main() int i,k,loc;ElemType e,x;char ch; /供用户选择所需的操作 do printf(*主菜单*);printf(n1.create list);printf(n2.insert e at the i position element);printf(n3.delete i position elem

9、ent and return it);printf(n4.find the element and return it);printf(n5.end the program); printf(n请输入您的选择(以输入5表结束:);scanf(%d,&k);switch(k) case 1: creat_list(&a);out_list(a); break;case 2: printf(n i,e=?);scanf(%d,%d,&i,&e);insert_sq(&a,i,e);out_list(a); break;case 3: printf(n please enter the i:);sc

10、anf(%d,&i);x=delete_sq(&a,i);out_list(a); break;case 4: printf(n e=?);scanf(%d,&e);loc=locat_sq(a,e);if (loc=-1) printf(n not find %d,loc);else printf(have found,position at %d,loc); break;printf(n*nnn); while(k!=5); printf(n GoodBye!); printf(n enter the enter , return n);ch=getchar();void creat_li

11、st(SqList*L) /生成顺序表int i;printf(nplease enter the length:n=);scanf(%d,&(L-length);for(i=1;ilength;i+)printf(data %d=,i);scanf(%d,&L-ai);void out_list(SqList L) /输出所生成的顺序表int i;for(i=1;ilength=MAXSIZE) printf(n ERROR! overflow!);else if(iL-length) printf(n error i);elsefor(j=L-length;j=i;j-)L-aj+1=L-

12、aj;L-ai=e;L-length+;ElemType delete_sq(SqList*L,int i) /删除第i个元素，并返回它的值ElemType x;int j;if(L-length=0) printf(n ERROR! the list is empty!);elseif(iL-length) printf(n ERROR! overflow!);elsefor(j=i;j=L-length;j+)L-aj=L-aj+1;L-length-;int locat_sq(SqList L,ElemType e) /查找值为e的元素，并返回它的位置int i=1;while(i=L.

13、length)if(i=L.length) return(i);else return(-1);实验结果：实验心得：在做插入删除等操作时要注意先后顺序，要明确是先行动在进行插入删除等操作，还是先进行插入删除等。注意不要使元素被元素被其它元素覆盖而得不到所需的结果。要注意增加程序的重复使用性，使程序一次就能完成各种操作，尽量使程序的使用者自己选择所需的操作。要尽量完善自己的代码，经过不断的测试找出其中考虑不足的地方。实验三 链式存储实验名称：实验三 链式存储实验目的：掌握线性表链式存储结构的描述，学会针对链式存储线性表的基本操作。实验原理：C语言结构化程序设计思想，结构体及指针的应用。实验设备：

14、电脑，TURBO C2.0/WIN-TC/VISUAL C+实验内容：线性表的链式存储表示及基本操作。实验代码：#include#include#define NULL 0typedef int DataType;typedef struct LNode /*定义结点*/DataType data;struct LNode*next;LNode,*LinkList;LinkList L;LinkList creat_List(); /*声明所用到的函数*/void out_List(LinkList L);void insert_List(LinkList L,int i,DataType e

15、);DataType delete_LinkList(LinkList L,int i);int locat_LinkList(LinkList L,DataType e);void main()int i,k,loc; DataType e,x; char ch;doprintf(*主菜单*);printf(n1.建立线性链表);printf(n2.在i位置插入元素e);printf(n3.删除第i个元素,返回其值);printf(n4.查找值为e的元素);printf(n5.结束程序运行);printf(n请输入您的选择(1,2,3,4,5);scanf(%d,&k);switch(k)c

16、ase 1: L=creat_List(); out_List(L);break;case 2: printf(n please enter the i and e:); scanf(%d%d,&i,&e); insert_List(L,i,e); out_List(L); break;case 3: printf(n please enter the location i you want to delete:i=); scanf(%d,&i); x=delete_LinkList(L,i-1); if(x!=-1) out_List(L); if(x!=-1) printf(n the e

17、lement at the %d location: x=%dn,i,x); break;case 4: printf(n please enter the element e you want to find:); scanf(%d,&e); loc=locat_LinkList(L,e); if(loc=-1) printf(n can not find); else printf(n have found,the element is at: location=%d,loc); break;printf(n*nnn);while(k=1 & kdata=0;head-next=NULL;

18、p=head;printf(please enter the data(end by -1000):);scanf(%d,&x);while(x!=-1000)s=(LinkList)malloc(sizeof(LNode);s-data=x;s-next=NULL;p-next=s;p=s;printf(please enter the data(-1000 to end):);scanf(%d,&x);return(head);void out_List(LinkList L) /*输出线性表*/LinkList p;p=L-next;while(p!=NULL)printf(%6d,p-

19、data);p=p-next;void insert_List(LinkList L,int i,DataType e) /在i位置插入元素eLinkList s,p;int j;p=L;j=0; /*找第i-1个结点*/while(p!=NULL & jnext;j+;if(p=NULL | ji-1)printf(n i ERROR!);else s=(LinkList)malloc(sizeof(LNode);s-data=e;s-next=p-next;p-next=s;DataType delete_LinkList(LinkList L,int i) /删除在i位置的元素 Link

20、List p,q;int j=0;DataType x;p=L;while(p!=NULL & jnext;j+;if(p=NULL)printf(ERROR!);return(-1);elseq=p-next;x=q-data;p-next=q-next;free(q);return(x);int locat_LinkList(LinkList L,DataType e) / 查找值为e的元素LinkList p;int j=1;p=L-next;while(p!=NULL & p-data!=e)p=p-next;j=j+1;if(p!=NULL) return j;else return

21、 -1;实验结果：实验心得：链式存储插入和删除操作比较方便，不需要大量移到数据，而不能随机的输出任一个元素，只能通过从头开始找到所需要的该元素。但一定要注意在建立和插入时一定要先申请地址空间。并且在删除减少元素时要记得将空间释放掉。如果可以的话要尽量使运行界面简单，并且让使用者很容易就知道怎么用。实验四 模式匹配算法应用实验名称：实验四 模式匹配算法应用实验目的：掌握字符串存储结构的描述，学会字符串的模式匹配算法的应用。实验原理：C语言结构化程序设计思想，结构体及指针和字符数组的应用。实验设备：电脑，TURBO C2.0/WIN-TC/VISUAL C+实验内容：1、朴素模式匹配算法2、快速模

22、式匹配算法实验代码： #include#include#define MAXSIZE 100int Index_BF ( char S , char T , int pos );int KMP(char *Text,char* Pattern,int pos);void main()int k,pos,n;char s11MAXSIZE;char s22MAXSIZE;doprintf(*主菜单*);printf(n1.输入待匹配的两个字符串);printf(n2.模式匹配的朴素算法进行匹配);printf(n3.模式匹配的KMP算法进行匹配);printf(n4.结束程序);printf(n

23、请输入您的选择(以输入10表结束:);scanf(%d,&k);switch(k)case 1:printf(please input the MAINLY string :);scanf(%s,s11);printf(please input the MODE string :);scanf(%s,s22);printf(please enter the position you want to start:);scanf(%d,&pos);break; case 2:n=Index_BF(s11,s22,pos);if(n!=-1) printf(normal mode:have foun

24、d ,at the position:%d.,n);else printf(normal mode:have NOT found!);break; case 3:n=KMP(s11,s22,pos);if(n!=-1) printf(KMP:have found ,at the position:%d.,n);else printf(KMP:have NOT found!);break; case 4:printf(感谢使用，GOODBYE!n);break;printf(n*nnn);while(k!=4);int Index_BF ( char S , char T , int pos )

25、 /模式匹配的朴素算法 int i=pos,j=0;while (Si+j!=0&Tj!=0) if(Si+j=Tj) j +; / 继续比较后一字符else i+; j=0; if ( Tj = 0) return i; / 匹配成功 返回下标else return -1; void getNext(const char* pattern,int next) /用于求nextj的值 next0=-1; int k=-1,j=0; while(patternj != 0) if(k!= -1 & patternk!= patternj ) k=nextk; +j;+k; if(patternk

26、= patternj) nextj=nextk; else nextj=k; int KMP(char *Text,char* Pattern,int pos) /模式匹配的KMP算法 if( !Text|!Pattern| Pattern0=0 | Text0=0 ) return -1;/空指针或空串，返回-1。 int len=0; char * c=Pattern; while(*c+!=0) +len;int *next=new intlen+1; getNext(Pattern,next); int index=0,i=pos-1,j=0; while(Texti!=0 & Pat

27、ternj!=0 ) if(Texti= Patternj) +i;/ 继续比较后继字符 +j; else index += j-nextj; if(nextj!=-1) j=nextj;/ 模式串向右移动 else j=0;+i; /while if(Patternj=0) return(index+pos-1);/ 匹配成功 else return -1; 实验结果：实验心得：从这两个算法的比较可知，一般较简单常见的算法不是最好的算法，这需要大量的人的总结。对于前人的算法都是已经很完美和精辟，在短时间内我们想要靠自己的能力去想出更好的算法是似乎是很难的。我们所能和应该做的就是学会它并运用它

28、即可，这些经典的算法在以后的程序中将会使我们的程序有很大的优化和快速，这些在目前以时间就是金钱的社会里是很有必要的。实验五 特殊矩阵实验名称：实验五 特殊矩阵实验目的：掌握特殊矩阵存储结构的描述，学会针对特殊矩阵的基本操作。实验原理：C语言结构化程序设计思想，结构体及数组的应用。实验设备：电脑，TURBO C2.0/WIN-TC/VISUAL C+实验内容：稀疏矩阵的存储及转置运算实验代码：#include#includetypedef int DataType;typedef struct OLNodeint i,j;DataType e;struct OLNode *right ,*dow

29、n;OLNode;typedef structOLNode *rh5,*ch5;int mu,nu,tu;Crosslist;void creatMatrix(Crosslist *M);void out_M(Crosslist M);Crosslist ma ;int z; void main() /*main函数*/creatMatrix(&ma); out_M(ma);void out_M(Crosslist M)int i;OLNode *p;char ch;printf(n m=%d n=%d t=%d n,M.mu,M.nu,M.tu);for(i=1;i=M.mu ;i+)p=M

30、.rhi;if(p)printf(n i=%d,i);while (p) printf(,p-i,p-j,p-e);p=p-right;printf(n);printf(n按enter 键,返回.);ch=getchar();void creatMatrix(Crosslist *M)int m,n,t,row,col,i,j;DataType va;OLNode *p,*q,*s;printf(请输入m,n,t的值：);printf(n m,n,t=?);scanf(%d,%d,%d,&m,&n,&t);for (i=1;irhi=NULL;for (j=1;jchj=NULL;M-mu=m

31、;M-nu=n;M-tu=t;for(i=1;itu;i+)printf( i,j,e=?); scanf(%d,%d,%d,&row,&col,&va);p=(OLNode *)malloc(sizeof(OLNode);p-i=row;p-j=col;p-e=va;q=M-rhrow;s=q;while(q!=NULL&q-jright;p-right=q;if(q=M-rhrow) M-rhrow=p;else s-right =p;q=M-chcol;while(q & q-idown;p-down=q;if(q=M-chcol) M-chcol=p;else s-down=p;实验结

32、果：实验心得：虽然，稀疏矩阵比较麻烦，但对于元素不多的矩阵，使用稀疏矩阵可以明显的节省大量的空间。并且对于一些矩阵常见的基本运算也很快速和方便。实验六 内排序实验名称：实验六 内排序实验目的：通过本次实验，掌握线性表的排序方法，并分析时间复杂度。实验原理：C语言结构化程序设计思想，数组的应用。实验设备：电脑，TURBO C2.0/WIN-TC/VISUAL C+实验内容：将快速排序算法写成完整的程序上机通过。实验代码：#include#include#define N 100typedef struct /定义数据元素结点类型int key;int point;node;int creat(n

33、ode a) ; /输入关键字，返回实际所含的关键字的个数 void print(node a,int n); /输出数组元素中所存的所有的元素void stinsort(node a,int n); /直接插入排序，n用来存放实际所存在的个数void binasort(node a,int n); /折半插入排序，n用来存放实际的元素个数void shellsort(node a,int n); /希尔排序void bubblesort(node a,int n); /冒泡排序int hoare(node a,int l,int h); /用于快速排序的分区处理函数（霍尔函数）,返回中间项所

34、在的位置void quicksort(node a,int l,int h); /递归法快速排序（调用霍尔函数）void simplesort(node a,int n); /简单选择排序void main()node rN;int k,n,l=1; doprintf(*主菜单*);printf(n1.输入关键字);printf(n2.直接插入排序);printf(n3.折半插入排序);printf(n4.希尔排序);printf(n5.冒泡排序);printf(n6.快速排序);printf(n7.简单选择排序);printf(n8.结束程序);printf(n请输入您的选择(以输入10表结

35、束:);scanf(%d,&k);switch(k)case 1:n=creat(r); print(r,n); /用n实际所含的关键字的个数 break; case 2:stinsort(r,n);print(r,n); /直接插入排序break;case 3:binasort(r,n);print(r,n); /折半插入排序break;case 4:hellsort(r,n);print(r,n); /希尔排序break;case 5:bubblesort(r,n);print(r,n); /冒泡排序break;case 6:quicksort(r,l,n); /递归法快速排序printf

36、(经过快速排序后,);print(r,n); break;case 7:simplesort(r,n);print(r,n);break;case 8:printf(感谢使用，GOODBYE!n);printf(*nnn);while(k8);int creat(node a) /输入关键字，返回实际所含的关键字的个数 int i=1;printf(请输入关键字(以输入-1表示结束)：);for(i=1;i=N-1;i+)scanf(%d,&ai.key);if(ai.key=-1)return(i-1); /返回实际所含的关键字的个数 void print(node a,int n) /输出

37、数组元素中所存的所有的元素int i;printf(此时数组中所存的元素序列是：n);for(i=1;i=n;i+)printf(%5d,ai.key);printf(n);void stinsort(node a,int n) /直接插入排序，n用来存放实际所存在的个数int i,j;for(i=2;ia0.key) /从后面开始比aj+1=aj;j-;aj+1=a0;printf(经过直接插入排序后,);void binasort(node a,int n) /折半插入排序，n用来存放实际的元素个数int i,j,l,h,mid;for(i=2;i=n;i+)a0=ai;l=1;h=i-1

38、;while(l=h)mid=(l+h)/2;if(a0.key=l;j-)aj+1=aj;al=a0;printf(经过折半插入排序后,);void shellsort(node a,int n) /希尔排序int k,i,j;k=n/2;while(k=1)for(i=k+1;ia0.key & j=0)aj+k=aj;j=j-k;aj+k=a0;k=k/2;printf(经过希尔排序后,);void bubblesort(node a,int n) /冒泡排序int j,tag,x,i=1;dotag=0;for(j=n;ji;j-)if(aj.keyaj-1.key)x=aj.key;

39、aj.key=aj-1.key;aj-1.key=x;tag=1;i+;while(tag=1 & in);printf(经过冒泡排序后,);int hoare(node a,int l,int h) /用于快速排序的分区处理函数（霍尔函数）,返回中间项在的位置int i=l,j=h,x=ai.key;dowhile(i=x) j-; /找到在右边（左边小于右边的位置）将其它的关键字向后移if(ij) ai=aj;i+; while(ij & ai.key=x) i+; /找到在左边（左边大于右边的位置）将其它的关键字向前移 if(ij)aj=ai;j-;ai.key=x;return i;while(ij);void quicksort(node a,int l,int h) /递归法快速排序（调用霍尔函数）int i;if(lh)i=hoare(a,l,h);quicksort(a,l,i-1);quicksort(a,i+1,h);void simplesort(node a,int n) /简单选择排序int i,j,min;for(i=1;in;i+)min=i;fo