线性结构基本算法的实现-数据结构实验报告.docx

《线性结构基本算法的实现-数据结构实验报告.docx》由会员分享，可在线阅读，更多相关《线性结构基本算法的实现-数据结构实验报告.docx（36页珍藏版）》请在三一文库上搜索。

1、.数 据 结 构实 验 报 告 专 业 计算机科学与技术 班 级 121班 姓 名 张航 学 号 1208010117 学 期 2013-2014第1学期 指导老师 刘勇 成绩：实验1234总分成绩教师评语： 数据结构 上机实验报告学号：1208010117 姓名： 张航 所在系：计算机科学与技术 班级：121班 实验名称： 线性结构基本算法的实现 实验日期 2013/11/6 实验指导教师 刘勇 实验机房 4号机房 -1. 实验目的：(1) 掌握线性表顺序存储结构的基本操作：插入、删除、查找；(2) 掌握线性表链式结构的基本操作：插入、删除、合并等运算；（3）掌握栈和队列基本运算的算法；（4

2、）掌握稀疏矩阵的压缩存储的算法。2. 实验内容：（1）实现顺序表的创建、插入、删除和查找的操作；（2）实现单链表 插入、删除、合并的操作；（3）实现2个有序线性表的合并；（4）利用顺序栈实现括号匹配的算法；（5）实现顺序队列各种基本运算的算法；（6）实现链栈各种基本运算的算法；（选做）（7）实现链队列各种基本运算的算法；（选做）（8）实现稀疏矩阵压缩存储的算法。3算法设计（编程思路或流程图或源代码） 内容：1、 顺序表的插入和删除/SqList.h#include<stdio.h>#include<stdlib.h>#include<malloc.h>#de

3、fine ElemType int#define OK 1#define ERROR 0#define OVERFLOW 0typedef structElemType *elem;int length;int listsize;SqList;int InitList (SqList *L)L->elem = (ElemType *)malloc(100 * sizeof(ElemType);if (!L->elem)return OVERFLOW;L->listsize = 100;L->length =0;return OK;int CreateList (SqLi

4、st *L,int n)int i;L->length = n;printf ("请输入%d个整数：n",L->length);for (i=0;i<L->length;i+)scanf ("%d",&L->elemi);return OK;void TravelList (SqList *L)int i;for (i=0;i<L->length;i+)printf ("当前顺序表第%d个元素为：%dn",i+1,L->elemi);int InsertList (SqList

5、*L,int i,ElemType e)ElemType *newbase,*p,*q;if (i<0 | i>(L->length+1)return ERROR;if (L->length >= L->listsize)newbase = (ElemType *)realloc(L->elem,(100+50) * sizeof(ElemType);if (!newbase)return ERROR;L->elem = newbase;L->listsize = 100+50;p=&L->elemi-1;for (q=&am

6、p;L->elemL->length-1;q>=p;q-)*(q+1) = *q;*p = e;L->length+;return OK;int DelList (SqList *L,int i,ElemType &x)ElemType *p,*q;if (i<1 | i>L->length | L->length = 0)return ERROR;p=&L->elemi-1;x=*p;for (q=&L->elemL->length-1;q>p;p+)*p = *(p+1);L->lengt

7、h-;return OK;/.cpp#include<stdio.h>#include<stdlib.h>#include "SqList.h"void main ()int n,i;ElemType e,x;SqList sq;SqList *l = &sq;printf ("* * * 顺 序 表 的 基 本 操 作 * * *n");printf (" 计算机12117张航nnn");printf ("* * * 初始化顺序表 * * *n");InitList (l);pri

8、ntf ("成功初始化顺序表！nn");printf ("* * * 建立顺序表 * * *n");printf ("输入要建立顺序表的长度：n");scanf ("%d",&n);CreateList (l,n);printf ("成功建立顺序表！n");TravelList (l);printf ("nn");printf ("* * * 顺序表的插入 * * * n");printf ("输入插入位置及插入元素：n");s

9、canf ("%d%d",&i,&e);InsertList (l,i,e);printf ("成功插入顺序表！n");TravelList (l);printf ("nn");printf ("* * * 顺序表的删除 * * * n");printf ("输入删除位置：n");scanf ("%d",&i);DelList (l,i,x);printf ("成功删除顺序表第%d个元素%dn",i,x);2、 有序单链表的合并/L

10、inkList.h#include<stdio.h>#include<stdlib.h>#include<malloc.h>#define ElemType int#define NULL 0typedef struct LNodeElemType data;LNode *next;*LinkList;void CreateList (LinkList L,int n) int i;LinkList p,q;p = L;for (i=1;i<=n;i+)q = (LinkList)malloc(sizeof(LNode);printf ("输

11、入第%d个元素：n",i);scanf ("%d",&q->data);q->next = p->next;p->next = q;p = p->next;void TravelList (LinkList L)int i = 1;LinkList p;p = L->next;while (p)printf ("第%d个元素为：%dn",i,p->data);i+;p = p->next;void MergeList (LinkList La,LinkList Lb,LinkList Lc

12、)LinkList pa,pb,pc;pa = La->next;pb = Lb->next;Lc=pc=La;while (pa&&pb)if (pa->data <= pb->data)pc->next = pa;pc = pa;pa = pa->next;elsepc->next = pb;pc = pb;pb = pb->next;pc->next = pa? pa : pb; free(Lb); /.cpp#include<stdio.h>#include<stdlib.h>#incl

13、ude<malloc.h>#include"LinkList.h"void main ()LinkList La,Lb,Lc;int n1,n2;La = (LinkList)malloc(sizeof(LNode);La->next = NULL;Lb = (LinkList)malloc(sizeof(LNode);Lb->next = NULL;printf ("* * * 两个有序单链表的合并操作 * * *n");printf (" 计算机12117张航nnn");printf ("输入第一

14、个单链表的长度：n");scanf ("%d",&n1);printf ("非递减顺序输入%d个整数：n",n1);CreateList (La,n1);printf ("第一个单链表中的元素为：n");TravelList (La);printf ("nn");printf ("输入第二个单链表的长度：n");scanf ("%d",&n2);printf ("非递减顺序输入%d个整数：n",n2);CreateList (Lb

15、,n2);printf ("第二个单链表中的元素为：n");TravelList (Lb);printf ("nn");printf ("正在执行合并操作.nnn");Lc = La;MergeList (La,Lb,Lc);printf ("合并后单链表的元素为：n");TravelList (Lc);3、 数制转换的算法实现/SqStack.h#include<stdio.h>#include<stdlib.h>#include<malloc.h>#define OK 1#d

16、efine ERROR 0#define OVERFLOW 0#define ElemType inttypedef structElemType *base;ElemType *top;int stacksize;SqStack;int InitStack (SqStack *S)S->base = (ElemType *)malloc(20 * sizeof(ElemType);if (!S)return OVERFLOW;S->top = S->base;S->stacksize = 20;return OK;int Push (SqStack *S,ElemTy

17、pe e)if (S->top - S->base >= S->stacksize)S->base = (ElemType *)realloc(S->base,(20+10) * sizeof(ElemType);if (!S->base)return OVERFLOW;S->top = S->base + S->stacksize;S->stacksize = 20 + 10;*(S->top+) = e;return OK;int Pop (SqStack *S,ElemType &x)if (S->to

18、p = S->base)return ERROR;x = *(-S->top);return OK;/.cpp#include<stdio.h>#include<stdlib.h>#include<malloc.h>#include"SqStack.h"void conversion (int n,int m)int e;SqStack sq;SqStack *s=&sq;InitStack (s);while (n)Push (s,n%m);n = n/m;while (sq.base != sq.top)Pop (

19、s,e);printf ("%d",e);void main ()int n,m;printf ("* * * 数 制 转 换 * * *n");printf (" 计算机12117张航nnn");printf ("输入一个10进制整数：n");scanf ("%d",&n);printf ("输入需要转换的数制：n");scanf ("%d",&m);printf ("正在进行转换.nn");printf ("

20、;10进制数%d转换成%d进制数为：n",n,m);conversion (n,m);printf ("n");4、 快速转置算法的实现/.cpp#include<stdio.h>#include<stdlib.h>#include<malloc.h>#define OK 1#define ERROR 0#define OVERFLOW 0#define ElemType int#define MAXSIZE 12500typedef structint r,c;ElemType e;Triple;typedef structT

21、riple dataMAXSIZE;int rows,cols,nums;TSMatrix;int CreateMatrix (TSMatrix &t,ElemType a55)int i,j;t.rows = 5;t.cols = 5;t.nums = 0;for (i=0;i<5;i+)for (j=0;j<5;j+)if (aij != 0)t.datat.nums+1.r = i+1;t.datat.nums+1.c = j+1;t.datat.nums+1.e = aij;t.nums+;t.data0.r = t.rows;t.data0.c = t.cols;

22、t.data0.e = t.nums;return OK;void DisplayMatrix (TSMatrix t)int i;for (i=0;i<=t.nums;i+)printf ("%dt%dt%dn",t.datai.r,t.datai.c,t.datai.e);int FastTransposeMatrix (TSMatrix t,TSMatrix &t1)int col,i,p,q;int num6;int cpot6;t1.rows = t.cols;t1.cols = t.rows;t1.nums = t.nums;if (t.nums)

23、for (col=1;col<=t.cols;col+)numcol = 0;for (i=1;i<=t.nums;i+)numt.datai.c+;cpot1 = 1;for (col=2;col<=t.cols;col+)cpotcol = cpotcol-1 + numcol-1;for (p=1;p<=t.nums;p+)col = t.datap.c;q = cpotcol;t1.dataq.r = t.datap.c;t1.dataq.c = t.datap.r;t1.dataq.e = t.datap.e;cpotcol+;t1.data0.r = t1.

24、rows;t1.data0.c = t1.cols;t1.data0.e = t1.nums;return OK;void main ()ElemType a55;TSMatrix t,t1;int i,j;printf ("* * * 5*5稀疏矩阵快速转置操作 * * *n");printf (" 计算机12117张航nnn");printf ("输入25个整数：n");for (i=0;i<5;i+)for (j=0;j<5;j+)scanf ("%d",&aij);CreateMatri

25、x (t,a);printf ("当前稀疏矩阵的三元组顺序表表示为：n");DisplayMatrix (t);printf ("nn正在进行快速转置操作.nn"); FastTransposeMatrix (t,t1);printf ("转置后矩阵的三元组顺序表表示为：n");DisplayMatrix (t1); 4程序调试（实验数据记录根据程序要求输入几组不同数据，记录程序运行结果，并分析结果,分析程序运行中出现的主要错误。或对其他程序环境的使用情况的记录。注：必须认真书写）算法1realloc函数原型是extern void

26、*realloc(void *mem_address, unsigned int newsize);算法2pc->next = pa? pa : pb;等价于if(pa) pc->next=pa else pc->next = pb; free(Lb); 这一句，返回的Lc 指向了La，所以不能free La。Lc中的Lb的数据是从 Lb->next 开始插入的pb = Lb->next。Lb这个指针还指向一个链表头，所以需要free。算法3x = *(-S->top);此句第一次写成x = -S->top;导致编译出错。S->top还是一个指针

27、，*(-S->top)才是指针所指的内容，才可以赋值给整形变量x。算法4调试过程中第一个大错误是将int CreateMatrix (TSMatrix &t,ElemType a55)写成int CreateMatrix (TSMatrix t,ElemType a55)，区别在于按值传递和按地址传递。按照错误的写法，导致程序DisplayMatrix (t)时，输出为空。因为在main()中CreateMatrix (t,a)时，按值传递不改变参数t的状态，t还是保持TSMatrix t时的未赋值状态，所以输出为空。修改为按地址传递后，CreateMatrix (t,a)运行一

28、系列操作，形参t发生变化就是实参t发生变化，进而输出正确结果。调试过程中int FastTransposeMatrix (TSMatrix t,TSMatrix &t1)函数中for (p=1;p<=t.nums;p+)语句本来写成for (p=1;p<=t.cols;p+),这是一个很微小的错误，误把变量搞错。但是这个小错误却导致FastTransposeMatrix (t,t1)运行结果不正确：执行DisplayMatrix (t1)，只有t1.data0t1.data5正确输出，其余t1.data都是未知。经过长时间分析检查发现这个错误并改正。这说明写代码一定要认真仔

29、细，这样才能尽可能避免话费大量的时间来发现小错误。另外写本算法时还有若干小错误。5讨论（通过实验的一些体会、学会的知识和技能等）见4.程序调试。 数据结构 上机实验报告学号： 1208010117 姓名： 张航 所在系： 计算机科学与技术 班级：121班 实验名称： 二叉树的基本应用 实验日期 2013/11/20 实验指导教师 刘勇 实验机房 4号机房 -2. 实验目的：(1) 理解树这种数据结构。(2)掌握二叉树二叉链表这种存储结构。(3)完成二叉树各种基本运算的算法。2. 实验内容：（1）实现二叉树创建的算法。（2）实现二叉树各种遍历算法。（3）实现二叉树其他操作的算法，包括：统计叶子结

30、点的个数、求二叉树的深度、线索二叉树等。3算法设计（编程思路或流程图） 1、 二叉树创建的算法/BiTNode.h#include<stdio.h>#include<stdlib.h>#include<malloc.h>#define OK 1#define ERROR 0#define OVERFLOW 0#define NULL 0#define ElemType chartypedef struct BiTNodeElemType data;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;int Creat

31、eBiTree (BiTree &T)ElemType ch;scanf ("%c",&ch);if (ch = '#')T = NULL;elseT = (BiTNode *)malloc(sizeof(BiTNode);if (!T)exit (OVERFLOW);T->data = ch;CreateBiTree (T->lchild);CreateBiTree (T->rchild);return OK;void LevelBiTree (BiTree T)BiTree Queue20,b;int front,rea

32、r;front = rear = 0;if (T)Queuerear = T;rear = (rear+1)%20;while (front != rear)b = Queuefront;printf ("%2c",b->data);front = (front+1)%20;if (b->lchild != NULL)Queuerear = b->lchild;rear = (rear+1)%20;if (b->rchild != NULL)Queuerear = b->rchild;rear = (rear+1)%20;/.cpp#inclu

33、de<stdio.h>#include<stdlib.h>#include<malloc.h>#include"BiTNode.h"void main ()BiTree T = NULL;printf (" * * * 二叉树的建立与输出 * * *n");printf (" 计算机12117张航nnn");printf ("先序遍历顺序输入二叉树的字符序列：n");CreateBiTree (T);printf ("层次遍历输出当前二叉树：n");Level

34、BiTree (T);printf ("n");2、 叶子结点统计的算法/BiTNode/.cpp#include<stdio.h>#include<stdlib.h>#include"BiTNode.h"int leafcount (BiTree T)int n;if (T = NULL)n = 0;else if (T->lchild = NULL && T->rchild = NULL)n =1;else n = leafcount (T->lchild) + leafcount (T-&g

35、t;rchild);return n;void main ()BiTree T = NULL;printf (" * * * 统计二叉树的叶子结点 * * *n");printf (" 计算机12117张航nnn");printf ("先序遍历顺序输入二叉树的字符序列：n");CreateBiTree (T);printf ("层次遍历输出当前二叉树：n");LevelBiTree (T);printf ("n");printf ("当前二叉树的叶子结点数是：%dn",lea

36、fcount (T);3、 二叉树深度统计算法/BiTNode.h/.cpp#include<stdio.h>#include<stdlib.h>#include"BiTNode.h"int depth (BiTree T)int dep1,dep2;if (T = NULL)return ERROR;elsedep1 = depth (T->lchild);dep2 = depth (T->rchild);return dep1 > dep2? dep1+1 : dep2+1;void main ()BiTree T = NULL

37、;printf (" * * * 二叉树深度的统计 * * *n");printf (" 计算机12117张航nnn");printf ("先序遍历顺序输入二叉树的字符序列：n");CreateBiTree (T);printf ("层次遍历输出当前二叉树：n");LevelBiTree (T);printf ("n");printf ("二叉树的深度是：%dn",depth (T); 4程序调试（实验数据记录根据程序要求输入几组不同数据，记录程序运行结果，并分析结果,分析程

38、序运行中出现的主要错误。或对其他程序环境的使用情况的记录。注：必须认真书写）BiTNode.h中CreateBiTree函数最初定义为int CreateBiTree (BiTree T)，导致程序运行时对main()中T赋值后LevelBiTree (T)为空，原因是按值传递形参T和实参T占用不同内存单元，调用CreateBiTree ()时，形参发生变化然后所在内存空间被释放，而实参至始至终没发生变化。将函数按照按地址传递定义后，问题迎刃而解。5讨论（通过实验的一些体会、学会的知识和技能等）通过算法2、3，我对递归回溯有了更深的体会。 数据结构 上机实验报告学号：1208010117 姓名

39、： 张航 所在系：计算机科学与技术 班级： 121班 实验名称： 图的基本实现与应用 实验日期 2012/12/04 实验指导教师 刘勇 实验机房 4号机房 -3. 实验目的：(1) 理解图这种数据结构。(2) 掌握邻接矩阵、邻接表这种存储结构的实现方法。(3) 完成图的遍历的算法。2. 实验内容：（1）实现图的邻接矩阵与邻接表结构的转换。（必做）（2）实现图遍历的算法。（必做）（3）实现图的拓扑排序的算法。（4）实现图的最短路径的算法3算法设计（编程思路或流程图）1、 图的邻接矩阵和邻接表创建的算法/.cpp#include<stdio.h>#include<stdlib.

40、h>#include<malloc.h>#define VEXTYPE int#define ADJTYPE int#define NULL 0#define OK 1#define ERROR 0typedef struct VEXTYPE vexs20;ADJTYPE arcs2020;int vexnum,arcnum;MGRAPH;typedef struct ArcNodeint adjvex;struct ArcNode *nextarc;ArcNode;typedef struct VNodeVEXTYPE data;ArcNode *firstarc;VNod

41、e;typedef structVNode vertics20;int vexnum,arcnum;ALGRAPH;int CreateMGraph (MGRAPH &G)int i,j,k;printf ("输入顶点数和边数：n");scanf ("%d%d",&G.vexnum,&G.arcnum);for (i=0;i<G.vexnum;i+)printf ("输入顶点%d的值：n",i+1);scanf ("%d",&G.vexsi);fflush (stdin);fo

42、r (i=0;i<G.vexnum;i+)for (j=0;j<G.vexnum;j+)G.arcsij = NULL; for (k=0;k<G.arcnum;k+)printf ("输入第%d条边的起始顶点和终止顶点：n",k+1);scanf ("%d%d",&i,&j);fflush (stdin);G.arcsi-1j-1 = 1;G.arcsj-1i-1 = 1;return OK;void OutMGraph (MGRAPH G)int i,j;printf ("图的邻接矩阵显示：n")

43、;for (i=0;i<G.vexnum;i+)for (j=0;j<G.vexnum;j+)printf ("<%d,%d>%d",i+1,j+1,G.arcsij);printf ("n");int mg_to_alg (MGRAPH G,ALGRAPH &ALG)int i,j;ArcNode *p;ALG.vexnum = G.vexnum;ALG.arcnum = G.arcnum;for (i=0;i<ALG.vexnum;i+)ALG.verticsi.data = G.vexsi;ALG.verticsi.firstarc = NULL;for (j=0;j<ALG.vexnum;j+)if (j!=i && G.arcsij=1)p = (ArcNode *)malloc (sizeof(ArcNode);p->adjvex = j;p->nextarc = ALG.verticsi.firstarc