[理学]数据结构实验报告.doc

《[理学]数据结构实验报告.doc》由会员分享，可在线阅读，更多相关《[理学]数据结构实验报告.doc（31页珍藏版）》请在三一办公上搜索。

1、江 西 科 技 师 范 学 院实 验 报 告课 程 数据结构B系 别 通信与电子学院班 级 电气信息类二班学 号 20092118姓 名 徐车生 报告规格一、实验目的二、实验原理三、实验仪器四、实验方法及步骤五、实验记录及数据处理六、误差分析及问题讨论目 录 1、实验一 C语言编程32、实验二 顺序存储43、实验三 链式存储54、实验四 模式匹配算法应用65、实验五 特殊矩阵76、实验六 内排序87、实验七 树与二叉树98、实验八 图的遍历119、实验九 检索15每次实验课必须带上此本子，以便教师检查预习情况和记录实验原始数据。实验时必须遵守实验规则。用正确的理论指导实践袁必须人人亲自动手实验

2、，但反对盲目乱动，更不能无故损坏仪器设备。这是一份重要的不可多得的自我学习资料袁它将记录着你在大学生涯中的学习和学习成果。请你保留下来，若干年后再翻阅仍将感到十分新鲜，记忆犹新。它将推动你在人生奋斗的道路上永往直前！实验一 C语言编程实验名称：实验一 C语言编程实验目的：复习C语言程序设计，回顾C语言结构数据及指针数据的应用。实验原理：C语言结构化程序设计思想，结构数据类型，指针数据类型。实验设备：电脑，TURBO C2.0/WIN-TC/VISUAL C+实验内容：1. 某组有10个人，每个人有3门课的考试成绩。求该组单科的平均成绩和各科总平均成绩。2. 用指针变量输出结构数组，结构数组存放

3、了5个学生的信息，学生的信息包括学号、姓名、性别和入学分数。1.实验代码：#includevoid main()float a114,sum=0;int i,j;for(i=0;i10;i+)printf(请输入第%d个学生的3门课成绩：,i+1);for(j=0;j3;j+)scanf(%f,&aij);printf(各门课的平均成绩：n);for(j=0;j3;j+)sum=0;for(i=0;i10;i+)sum= sum+aij;a10j=sum/10.0;printf(第%d门课的平均成绩是：%6.2fn,j+1,a10j);for(i=0;i3;i+)sum=0;for(j=0;j

4、10;j+)sum+=aij;ai3=sum/3.0;printf(第%d个学生各科总平均成绩：%6.2fn,i+1,ai4);实验结果：2.实验代码：#includestruct studentint num;char name20;char sex;float score;struct student stu5=001,zhang san,M,98,002,li shi,F,72,003,wang wu,F,99,004,li lin,M,79,005,wang ming,M,80;void main()struct student *p;printf( No. Name sex scor

5、en);for(p=stu;pnum,p-name,p-sex,p-score); 实验结果：实验心得： 本次试验，利用数据结构及指针计算十个学生的单科平均成绩和总的平均成绩。试验中定义二维变量a【11】【4】，输入十个学生的成绩，分别存储在数组变量a中，通过语句sum=0;for(i=0;isize=0;void append(list *s,datatype x) if(s-size=MAXSIZE) printf(overflow.n); else s-as-size=x; s-size+; void display(list*s) int i; if(s-size!=0) for(i=

6、0;isize;i+) printf(%5d,s-ai); else printf(list is null.n);void merge(list*la,list*lb,list*lc) int i=0,j=0,k=0; while(isize&jsize) if(la-aiaj) (*lc)-ak+=la-ai+; else (*lc)-ak+=lb-aj+; while(isize) (*lc)-ak+=la-ai+; while(jsize) (*lc)-ak+=lb-aj+; (*lc)-size=la-size+lb-size;void main() list s,h,*k,d; d

7、atatype x; init(&s); k=&d; init(&h); init(k); printf(请输入表S的内容：n); scanf(%d,&x); while(x!=0) append(&s,x); scanf(%d,&x); printf(请输入表h的内容：n); scanf(%d,&x); while(x!=0) append(&h,x);/原该处h表写成了s表 scanf(%d,&x); merge(&s,&h,&k); display(k); printf(n);实验结果实验心得：本次实验很好的体现了函数调用技术，先通过函数init（）初始化，然后利用merge(list*

8、la,list*lb,list*lc)进行排列，最后display函数显示输出结果。通过本次实验了解了顺序存储的方式以及如何实现数据的大小排列，很好掌握了函数调用的技巧。实验三 链式存储实验名称：实验三 链式存储实验目的：掌握线性表链式存储结构的描述，学会针对链式存储线性表的基本操作。实验原理：C语言结构化程序设计思想，结构体及指针的应用。实验设备：电脑，TURBO C2.0/WIN-TC/VISUAL C+实验内容：1、已知两个依元素值递增有序排列的链表A和B，且同一表中的元素值各不相同。构造一个单链表C，其元素为A和B中元素的交集，且表C中的元素也依值递增有序排列。实验代码：#includ

9、e #include malloc.h#define MAXSIZE 100typedef int datatype;typedef struct lindnodedatatype info;struct lindnode *next;node;node *init()return NULL;void creat(node *head)node *r,*s;datatype x;*head=r=(node*)malloc(sizeof(node);printf(n创建链表:n);scanf(%d,&x);while(x)s=(node*)malloc(sizeof(node);s-info=x

10、;r-next=s;r=s;scanf(%d,&x);r-next=NULL;void display(node *head)node *p;p=head-next;if(!p)printf(kong n);elsewhile(p)printf(%5d,p-info);p=p-next;void inter(node *A,node *B,node *C)node *pa=A-next,*pb=B-next,*s,*r;(*C)=(node*)malloc(sizeof(node);(*C)-next=NULL;r=(*C);while(pa!=NULL&pb!=NULL)if(pa-info

11、info)pa=pa-next;else if(pa-infopb-info)pb=pb-next;elses=(node*)malloc(sizeof(node);s-info=pa-info;s-next=NULL;r-next=s;r=s;pa=pa-next;pb=pb-next;r-next=NULL;void main()node *head,*p,*q;head=init();p=init();q=init();creat(&head);creat(&p);inter(head,p,&q);display(q);实验结果：实验心得：本次实验很好的体现了链式排列的方式，通过本次实验

12、，很好的掌握了链式排列的方法，并且加深了指针变量的使用方法。实验四 模式匹配算法应用实验名称：实验四 模式匹配算法应用实验目的：掌握字符串存储结构的描述，学会字符串的模式匹配算法的应用。实验原理：C语言结构化程序设计思想，结构体及指针和字符数组的应用。实验设备：电脑，TURBO C2.0/WIN-TC/VISUAL C+实验内容：1、朴素模式匹配算法2、快速模式匹配算法实验代码：1、朴素模式匹配算法#include stdio.h#define MAXSIZE 100typedef structchar dataMAXSIZE;int length;string;void init(strin

13、g *s)s-length=0;void input(string *s)char c;int i;i=0;scanf(%c,&c);while(c!=n)s-datai+=c;scanf(%c,&c);s-length=i;int pipei(string s,string t)int i,j;i=0;j=0;while(is.length&j=t.length)return i-t.length;elsereturn -1;void main()string s,t;init(&s);init(&t);printf(please input string s:);input(&s);pri

14、ntf(please input string t:);input(&t);int k=pipei(s,t);if(k=-1)printf(string t is not in string s.n);elseprintf(string t is in string s.%dn,k);2、快速模式匹配算法#include stdio.h#define MAXSIZE 100typedef structchar dataMAXSIZE;int length;string;void init(string *s)s-length=0;void input(string *s)char c;int

15、i;i=1;scanf(%c,&c);while(c!=n)s-datai+=c;scanf(%c,&c);s-length=i-1;void get_next(string T,int next)int i,j; i=1;j=0;next1=0; while(i=T.length) if(j=0 | T.datai=T.dataj)+i;+j; nexti=j;/*(2)*/ else j=nextj; int Index_KMP(string S,string T,int next)int i,j; i=0;j=1;/这里的串的第1个元素下标是1 while(i=S.length & jT

16、.length) return i-T.length;/匹配成功 else return 0;void main()string s,t;int nextMAXSIZE;init(&s);init(&t);printf(please input string s:);input(&s);printf(please input string t:);input(&t);get_next(t,next);int k=Index_KMP(s,t,next);if(k=0)printf(string t is not in string s.n);elseprintf(string t is in s

17、tring s.%dn,k);实验结果实验心得：实验中程序一为朴素模式匹配算法，程序二为快速模式匹配算法，两者都使用了指针变量以及数组变量，利用字符串方式实现功能。朴素模式匹配算法和快速模式匹配算法各有自己的特点，在本次实验中充分体现里两者不同之处。通过本次实验较好的掌握了两种匹配算法的方法，加深了数组变量的应用。实验五 特殊矩阵实验名称：实验五 特殊矩阵实验目的：掌握特殊矩阵存储结构的描述，学会针对特殊矩阵的基本操作。实验原理：C语言结构化程序设计思想，结构体及数组的应用。实验设备：电脑，TURBO C2.0/WIN-TC/VISUAL C+实验内容：1、稀疏矩阵的存储及转置运算实验代码：/

18、稀疏矩阵的三元组顺序表存储表示及其转置算法.cpp #include #define ERROR 0#define OK 1typedef int status;typedef int ElemType;/稀疏矩阵的三元组顺序表存储表示#define MAXSIZE 100 /非零元个数最大为100typedef struct int i,j; /非零元的行下标和列下标 ElemType e; /非零元Triple;typedef struct Triple dataMAXSIZE+1; /非零元三元组表,data0不用 int mu,nu,tu; /矩阵的总行数,总列数,非零元总个数TSMa

19、trix;status CreateTriplTable(TSMatrix &M)/建立三元组表 int k; printf(请输入稀疏矩阵行数 列数 非零元个数: ); scanf(%d%d%d,&M.mu,&M.nu,&M.tu); if (M.tuMAXSIZE) return ERROR; printf(行 列 非零元n); for (k=1;k=M.tu;k+) scanf(%d%d%d,&M.datak.i,&M.datak.j,&M.datak.e); return OK;void OutputTripleTable(TSMatrix M)/输出三元组表 int k; print

20、f(行数 列数 非零元个数: ); printf(%d %d %dn,M.mu,M.nu,M.tu); printf(行 列 非零元n); for (k=1; k=M.tu; k+) printf(%2d%3d%5dn, M.datak.i, M.datak.j, M.datak.e);void outputMatrix(TSMatrix M)/将三元组表M转换为对应的mu*nu阶稀疏矩阵并输出 int i, j, k=1; printf(三元组表对应的稀疏矩阵:n); for (i=0; iM.mu; i+) for (j=0; jM.nu; j+) if (i=M.datak.i-1&j=

21、M.datak.j-1) printf(%5d,M.datak.e); k+;else printf(%5d,0); printf(n); status TransposeSMatrix(TSMatrix M,TSMatrix &T)/采用三元组表存储表示,求稀疏矩阵M的转置矩阵T. 算法5.1 int col,p,q; T.mu=M.nu; T.nu=M.mu; T.tu=M.tu; if (T.tu) q=1; /首先置目标结点(即T)的序号为1,即q=1 for (col=1;col=M.nu;+col) /按M的列序col转置:col从1至M的列数M.tufor (p=1;p=M.tu

22、;+p) /*每次对M的结点进行扫描.p从1至M的非零元个数M.tu*/ if (M.datap.j=col) /若在M中找到M.datap.j=col的结点pT.dataq.i=M.datap.j; /*则将M中序号为p的结点赋给T中序号为q的结点*/ T.dataq.j=M.datap.i; T.dataq.e=M.datap.e; +q; /且将目标结点q往下移即q+ return OK;#define MAXCOL 50status FastTransposeSMatrix(TSMatrix M,TSMatrix &T)/采用三元组表存储表示,求稀疏矩阵M的转置矩阵T. 算法5.2 i

23、nt numMAXCOL, cpotMAXCOL, col, t, p, q; T.mu=M.nu; T.nu=M.mu; T.tu=M.tu; if (T.tu) for (col=1;col=M.nu;+col) numcol=0; for (t=1;t=M.tu;+t) +numM.datat.j; /求M中每一列含非零元个数 cpot1=1; /求第col列中第一个非零元在T.data中的序号 for (col=2;col=M.nu;+col) /后一列第一个非零元在T.data中的序号等于 cpotcol=cpotcol-1+numcol-1; /前一列的序号+前一列非零元个数 fo

24、r (p=1;p=M.tu;+p) col=M.datap.j; /M中第p行的列号域值赋给col q=cpotcol; /M中的第col列非零元在T.data中的恰当位置赋给q T.dataq.i=M.datap.j; /M中的第p行复制到T中的第q行 T.dataq.j=M.datap.i; T.dataq.e=M.datap.e; +cpotcol; /M中第col列下一个非零元在T.data中的位置应增1 return OK; void main()TSMatrix a,b; CreateTriplTable(a); outputMatrix(a); TransposeSMatrix(

25、a,b); printf(转置矩阵:); OutputTripleTable(b); outputMatrix(b); FastTransposeSMatrix(a,b); printf(快速)转置矩阵:); OutputTripleTable(b);实验结果：实验心得：熟悉了特殊矩阵存储结构的描述，掌握了针对特殊矩阵的基本操作，对计算机的操作更加熟练，加强了自己的实践动手能力。所有理论都必须经过实验的论证来检验它的正确性。实验六 内排序实验名称：实验六 内排序实验目的：通过本次实验，掌握线性表的排序方法，并分析时间复杂度。实验原理：C语言结构化程序设计思想，数组的应用。实验设备：电脑，TUR

26、BO C2.0/WIN-TC/VISUAL C+实验内容：1、将快速排序算法写成完整的程序上机通过，并统计递归深度。实验代码：#includetypedefintnode;nodeafile20;node x;intd,dl,n;intl,r,i,j;voidq(intl,intr)intp;d+;if(dld)dl=d;printf(dl=%d,dl);printf(d=%dn,d);if(lx)&(ji)j-;if(ij)afilei+=afilej;while(afileii)i+;if(ij)afilej-=afilei;afilei=x;for(p=1;p=n;p+)printf(%

27、d,afilep);printf(n);q(l,i-1);q(i+1,r);d-;printf(*%d*n,d);void main()intp;printf(nPleaseinputn:n); scanf(%d,&n); printf(Please input astring:); for(p=1;p=n;p+) scanf(%d,&(afilep); d=0; dl=0;l=1; r=n; q(l,r); for(p=1;pdata=ch; T-lchild=Create(T-lchild); T-rchild=Create(T-rchild); return T; void Preord

28、er(BiTree T) if(T) printf(%c,T-data); Preorder(T-lchild); Preorder(T-rchild); int Sumleaf(BiTree T) int sum=0,m,n; if(T) if(!T-lchild)&(!T-rchild) sum+; m=Sumleaf(T-lchild); sum+=m; n=Sumleaf(T-rchild); sum+=n; return sum; void zhongxu(BiTree T) if(T) zhongxu(T-lchild); printf(%c,T-data); zhongxu(T-

29、rchild); void houxu(BiTree T) if(T) houxu(T-lchild); houxu(T-rchild); printf(%c,T-data); int Depth(BiTree T) int dep=0,depl,depr; if(!T) dep=0; else depl=Depth(T-lchild); depr=Depth(T-rchild); dep=1+(depldepr?depl:depr); return dep; main() BiTree T; int sum,dep; T=Create(T); Preorder(T); printf(n);

30、zhongxu(T); printf(n); houxu(T); printf(n); sum=Sumleaf(T); printf(%d,sum); dep=Depth(T); printf(n%d,dep);实验结果：实验心得：了解了树与二叉树的建立、三种遍历方法及用广义表进行输入与输出，进一步了解树的结构及非线性特点，递归特点和动态性。了解了树与二叉树与线性表的区别。实验八 图的遍历实验名称：实验八 图的遍历实验目的：熟悉图的存储结构，掌握有关算法的实现，了解图在计算机科学及其他工程技术中的应用。实验原理：C语言结构化程序设计思想，图的应用。实验设备：电脑，TURBO C2.0/WIN-

31、TC/VISUAL C+实验内容：1、给定一个图，设计一个程序，找出一条从某一顶点A到另一顶点B边数最少的一条路径。实验代码：#includeint number;typedef struct int q20; int f,r;queue;int nodelist2020;queue Q;int z20;int a,b,n,i,j,x,y;int finished;void enq(queue *Q,int x) Q-qQ-r=x; if(Q-r=19) Q-r=0; else Q-r+; if(Q-r=Q-f) printf(Overflow!n);front(queue *Q) if(Q-

32、r=Q-f) printf(Underflow!n); else return(Q-qQ-f);void deq(queue *Q) if(Q-r=Q-f) printf(Underflow!n); else if(Q-f=19) Q-f=0; else Q-f+; int qempty(queue Q) if(Q.f=Q.r) return 1; else return 0;void readgraph() printf(nPlease input n:); scanf(%d,&n); printf(Please input nodelistij:n); for(i=1;i=n;i+) for(j=1;j=n;j+) scanf(%d,&nodelistij); printf(n); printf(List-link is bulitn); for(i=1;i=n;i+) for(j=1;j=n;j+) printf(%3d,nodelistij); prin