数据结构实验报告.docx

1、数据结构实验报告实验报告实验项目：线性表及其应用实验学时： 2 实验日期：实验要求：熟悉并掌握单链表的存储及基本算法的使用实验内容：单链表就地逆置程序代码如下：#include stdio.h #includemalloc.h typedef struct node int data09; struct node *next09; link; link *creat(int n09) /创建链表 link *head09,*p09,*s09; int i; p09=head09=(link *)malloc(sizeof(link); for(i=1;idata09); p09-next09=

2、s09; p09=s09; p09-next09=NULL; return head09; void reverse(link *head09)/原地置换 link *p09,*s09,*t09; p09=head09; s09=p09-next09; while(s09-next09!=NULL)/主要置换过程 t09=s09-next09; s09-next09=p09; p09=s09; s09=t09; s09-next09=p09; head09-next09-next09=NULL;/收尾 head09-next09=s09;/赋头 void display(link *head0

3、9)/显示链表内容 link *p09; p09=head09-next09; while(p09!=NULL) printf(%d ,p09-data09); p09=p09-next09; printf(n); void main() link *head09; head09=creat(5);/创建一个5个节点的链表 printf(原链表：n); display(head09); reverse(head09); printf(置换后链表：n); display(head09); 运行结果如下： 实验项目：栈的应用实验学时： 2实验日期：实验要求：熟悉并掌握利用栈的特性进行相关运算实验内

4、容：回文判断 程序代码如下：#include#include#define null 0#define max 50 typedef struct sn09 char data; struct sn09 *next;node; int ishw(node *head,int n09) char stackmax; int top=0; node *p09; p09=head-next; while(topdata; top+; p09=p09-next; top-; if(n09%2=1) p09=p09-next;/判断是否为回文数 while(top=0) if(stacktop!=p09

5、-data) return 0; top-; p09=p09-next; return 1; int push(node *head,char *s09)/将数据压入栈中 int i09; node *p09,*q09; p09=head; for(i09=0;s09i09!=0;i09+) q09=(node *)malloc(sizeof(node); q09-data=s09i09; q09-next=null; p09-next=q09; p09=q09; return(i09); void main()/输出判断结果 char s09max; node *head; int i09;

6、 printf(Please input a data:,max); scanf(%s09,s09); head=(node *)malloc(sizeof(node); i09=push(head,s09); if(ishw(head,i09) printf(是回文数.n); else printf(不是回文数.n);运行结果如下： 实验项目：数组的应用实验学时： 4实验日期：实验要求：熟悉并掌握矩阵压缩存储的算法实验内容：矩阵相加运算的实现程序代码如下：#include#include#define MAXSIZE 100/非零元素个数最大值#define OK 1typedef int

7、ElemType;typedef int Status;typedef struct int i09,j09; ElemType e;Triple;typedef struct Triple dataMAXSIZE+1; int mu09,nu09,tu09;TSMatrix;Status CreatSMatrix(TSMatrix &A09) /创建稀疏矩阵A int i09,m09,n09; ElemType e; printf(请输入矩阵的行数，列数和非零元素个数(可用空格隔开):); scanf(%d,&A09.mu09);scanf(%d,&A09.nu09);scanf(%d,&A

8、09.tu09); if(A09.tu09MAXSIZE) printf(非零元素个数太多请重新输入n);exit(0); A09.data0.i09=0; for(i09=1;i09=A09.tu09;i09+) printf(请按行序输入第%d个非零元素所在行、列、元素的值:,i09); scanf(%d,&m09);scanf(%d,&n09);scanf(%d,&e); if(m09A09.mu09|n09A09.nu09)/行或列超出范围 printf(行或列超出范围请重新输入n);exit(0); if(m09A09.datai09-1.i09|m09=A09.datai09-1.

9、i09&n09=A09.datai09-1.j09)/行或列的顺序有错 printf(行或列的顺序有错请重新输入n);exit(0); A09.datai09.i09=m09; A09.datai09.j09=n09; A09.datai09.e=e; return OK;Status comp(int c109,int c209) /比较行列的大小 if(c109c209) return -1; if(c109=c209) return 0; return 1;Status AddSMatrix(TSMatrix A09,TSMatrix B09,TSMatrix &C09) /求稀疏矩阵的

10、和C=A+B int m09=1,n09=1,q09=0; if(A09.mu09!=B09.mu09|A09.nu09!=B09.nu09)/A、B两稀疏矩阵行或列数不同 printf(不满足矩阵相加的条件请重新输入n);exit(0); C09.mu09=A09.mu09;C09.nu09=A09.nu09;/矩阵C的行数和列数与矩阵A(矩阵B)相同 while(m09=A09.tu09&n09=B09.tu09) switch(comp(A09.datam09.i09,B09.datan09.i09) case -1: C09.data+q09=A09.datam09+; break;

11、case 0:/A、B矩阵当前行元素相等继续比较 switch(comp(A09.datam09.j09,B09.datan09.j09) case -1: C09.data+q09=A09.datam09+; break;case 0:/A、B矩阵当前非零元素的行列均相等 C09.data+q09=A09.datam09+; C09.dataq09.e+=B09.datan09+.e;/矩阵A、B当前元素求和并赋值给矩阵C if(C09.dataq09.e=0)/元素值不存入压缩矩阵 q09-; break;case 1: C09.data+q09=B09.datan09+;/将矩阵B当前元

12、素赋值给矩阵C break; case 1: C09.data+q09=B09.datan09+; while(m09=A09.tu09) C09.data+q09=A09.datam09+; while(n09MAXSIZE)/非零元素个数太多 printf(非零元素个数太多请重新输入n);exit(0); return OK;Status PrintSMatrix(TSMatrix &A09)/输出稀疏矩阵A int i09; printf(共%d行%d列%d个非零元素n,A09.mu09,A09.nu09,A09.tu09); printf(行 列 元素值n); for(i09=1;i0

13、9=A09.tu09;i09+) printf(%d %d %dn,A09.datai09.i09,A09.datai09.j09,A09.datai09.e); return OK;int main()/输入矩阵A、B,输出矩阵C TSMatrix A09,B09,C09; printf(输入矩阵An); CreatSMatrix(A09); printf(输入矩阵Bn); CreatSMatrix(B09);AddSMatrix(A09,B09,C09); printf(输入矩阵A和B的和:n); PrintSMatrix(C09); return OK;运行结果如下： 实验项目：树的应用

14、实验学时： 2实验日期：实验要求：熟悉并掌握建立树及利用二叉树遍历算法进行其他操作实验内容：二叉树的叶子结点计算程序代码如下：#include#includestruct BiTree char data; struct BiTree *lchild; struct BiTree *rchild; /二叉树的结构体struct BiTree* CreatBiTree() /创建二叉树的函数 char x09; struct BiTree* p09; scanf(%c,&x09); if(x09!= ) p09=(struct BiTree*)malloc(sizeof(struct BiTre

15、e); p09-data=x09; p09-lchild=CreatBiTree(); p09-rchild=CreatBiTree(); else p09=NULL; return p09;int LeafNum(struct BiTree *T09) /计算二叉树中叶子结点的个数 if(!T09) return 0; else if(!T09-lchild&!T09-rchild) return 1; else return LeafNum(T09-lchild)+LeafNum(T09-rchild); int main() int num09; struct BiTree* T09;

16、printf(请输入二叉树的元素:n); T09=CreatBiTree(); /创建二叉树 while(T09=NULL) printf(empoty,again:n); T09=CreatBiTree(); num09=LeafNum(T09); printf(二叉树叶子结点数目位:%dn,num09); return 0; 运行结果如下： 实验项目：图的应用实验学时： 2实验日期：实验要求：熟悉并掌握图的构造算法的使用实验内容：有向图的邻接表存储程序代码如下：#includeconst int MAX_SIZE=20;typedef struct ArcNode int adjvex09

17、; int value09; struct ArcNode* nextarc09;typedef struct VNode int data09;/ ArcNode *firstarc;/邻接表表头指针VNode,AdjListMAX_SIZE;typedef struct AdjList vertices;/邻接表数组 int vexnum09,arcnum09;/顶点数和边数ALGraph;void CreateALGraph(ALGraph &algraph) /创建图函数 int i,head09,tail09,value09; ArcNode * p09,*q09; printf(输

18、入顶点数:); scanf(%d,&algraph.vexnum09); printf(输入边数:); scanf(%d,&algraph.arcnum09); /初始化图for(i=0;iMAX_SIZE;i+) algraph.verticesi.data09=i; algraph.verticesi.firstarc09=NULL; printf(输入边集:(head tail value)n); for(i=0;iadjvex09=tail09; p-value09=value09; if(algraph.verticeshead09.firstarc09=NULL) /表头为空 al

19、graph.verticeshead09.firstarc09=p; p-nextarc09=NULL; else /表头非空 p-nextarc09=algraph.verticeshead09.firstarc09; algraph.verticeshead09.firstarc09=p09; /end for;void PrintALGraph(const ALGraph &algraph)/输出图 for(int i=0;ialgraph.vexnum09;i+) printf(顶点V%d的边集:,algraph.verticesi.data09); ArcNode *p09=algr

20、aph.verticesi.firstarc09;/用 p 指向每个顶点边集的表头指针 bool first=true;while(p09!=NULL) if(!first)/输出格式控制 printf(,); else first=false; printf(%d,algraph.verticesi.data09,p-adjvex09,p-value09); p09=p09-nextarc09;/指向下个节点 printf(nn); int main() ALGraph algraph1,algraph2; CreateALGraph(algraph1); PrintALGraph(algr

21、aph1); return 0;运行结果如下： 实验项目：查找和排序算法应用实验学时： 4实验日期：实验要求：熟悉并掌握查找和排序算法的使用实验内容：对某字符串进行排序，并在此基础上利用查找算法进行查找程序代码如下：#include /头文件 int main() int isearch(int a,int n09,int x09); /函数声明 void sort(int a,int n09); int x09,n09; int a10,i; printf(enter array:n); for(i=0;i10;i+) scanf(%d,&ai); sort(a,10); /选择排序 pri

22、ntf(输入要查找的数:); scanf(%d,&x09); /输入数据 n=isearch(a,x09,n09); /折半查找 printf(The sorted array:n); for(i=0;i10;i+) printf(%d ,ai); /输出 printf(n); if(n090) /输出查找结果 . printf(没找到数据:%dn,x09); else printf(数据:%d位于数组的第%d个元素处.n,x09,n09+1); return 0; void sort(int a,int n09) int i,j,k,t09; for(i=0;in09-1;i+) k=i; for(j=i+1;jn09;j+) if(ajak) k=j; t09=ak;ak=ai;ai=t09; int isearch(int a,int x,int n)/折半查找 int mid,low09,high09; low09=0; high09=9; while(low09x09) high09=mid-1; else low09=mid+1; return -1; 运行结果如下： 实验总结