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

数 据 结 构实 验 报 告 专 业 计算机科学与技术 班 级 121班 姓 名 张航 学 号 1208010117 学 期 2013-2014第1学期 指导老师 刘勇 成绩：实验1234总分成绩教师评语： 数据结构 上机实验报告学号：1208010117 姓名： 张航 所在系：计算机科学与技术 班级：121班 实验名称： 线性结构基本算法的实现 实验日期 2013/11/6 实验指导教师 刘勇 实验机房 4号机房 -1. 实验目的：(1) 掌握线性表顺序存储结构的基本操作：插入、删除、查找；(2) 掌握线性表链式结构的基本操作：插入、删除、合并等运算；（3）掌握栈和队列基本运算的算法；（4）掌握稀疏矩阵的压缩存储的算法。2. 实验内容：（1）实现顺序表的创建、插入、删除和查找的操作；（2）实现单链表 插入、删除、合并的操作；（3）实现2个有序线性表的合并；（4）利用顺序栈实现括号匹配的算法；（5）实现顺序队列各种基本运算的算法；（6）实现链栈各种基本运算的算法；（选做）（7）实现链队列各种基本运算的算法；（选做）（8）实现稀疏矩阵压缩存储的算法。3算法设计（编程思路或流程图或源代码） 内容：1、 顺序表的插入和删除/SqList.h#include#include#include#define 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 (SqList *L,int n)int i;L-length = n;printf (请输入%d个整数：n,L-length);for (i=0;ilength;i+)scanf (%d,&L-elemi);return OK;void TravelList (SqList *L)int i;for (i=0;ilength;i+)printf (当前顺序表第%d个元素为：%dn,i+1,L-elemi);int InsertList (SqList *L,int i,ElemType e)ElemType *newbase,*p,*q;if (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=&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 (iL-length | L-length = 0)return ERROR;p=&L-elemi-1;x=*p;for (q=&L-elemL-length-1;qp;p+)*p = *(p+1);L-length-;return OK;/.cpp#include#include#include SqList.hvoid main ()int n,i;ElemType e,x;SqList sq;SqList *l = &sq;printf (* * * 顺 序 表 的 基 本 操 作 * * *n);printf ( 计算机12117张航nnn);printf (* * * 初始化顺序表 * * *n);InitList (l);printf (成功初始化顺序表！nn);printf (* * * 建立顺序表 * * *n);printf (输入要建立顺序表的长度：n);scanf (%d,&n);CreateList (l,n);printf (成功建立顺序表！n);TravelList (l);printf (nn);printf (* * * 顺序表的插入 * * * n);printf (输入插入位置及插入元素：n);scanf (%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、 有序单链表的合并/LinkList.h#include#include#include#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;idata);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)LinkList pa,pb,pc;pa = La-next;pb = Lb-next;Lc=pc=La;while (pa&pb)if (pa-data 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#include#include#includeLinkList.hvoid 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 (输入第一个单链表的长度：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,n2);printf (第二个单链表中的元素为：n);TravelList (Lb);printf (nn);printf (正在执行合并操作.nnn);Lc = La;MergeList (La,Lb,Lc);printf (合并后单链表的元素为：n);TravelList (Lc);3、 数制转换的算法实现/SqStack.h#include#include#include#define OK 1#define 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,ElemType 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-top = S-base)return ERROR;x = *(-S-top);return OK;/.cpp#include#include#include#includeSqStack.hvoid 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 (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 (10进制数%d转换成%d进制数为：n,n,m);conversion (n,m);printf (n);4、 快速转置算法的实现/.cpp#include#include#include#define OK 1#define ERROR 0#define OVERFLOW 0#define ElemType int#define MAXSIZE 12500typedef structint r,c;ElemType e;Triple;typedef structTriple 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;i5;i+)for (j=0;j5;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;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)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.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;i5;i+)for (j=0;jnext = 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还是一个指针，*(-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)运行一系列操作，形参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都是未知。经过长时间分析检查发现这个错误并改正。这说明写代码一定要认真仔细，这样才能尽可能避免话费大量的时间来发现小错误。另外写本算法时还有若干小错误。5讨论（通过实验的一些体会、学会的知识和技能等）见4.程序调试。 数据结构 上机实验报告学号： 1208010117 姓名： 张航 所在系： 计算机科学与技术 班级：121班 实验名称： 二叉树的基本应用 实验日期 2013/11/20 实验指导教师 刘勇 实验机房 4号机房 -2. 实验目的：(1) 理解树这种数据结构。(2)掌握二叉树二叉链表这种存储结构。(3)完成二叉树各种基本运算的算法。2. 实验内容：（1）实现二叉树创建的算法。（2）实现二叉树各种遍历算法。（3）实现二叉树其他操作的算法，包括：统计叶子结点的个数、求二叉树的深度、线索二叉树等。3算法设计（编程思路或流程图） 1、 二叉树创建的算法/BiTNode.h#include#include#include#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 CreateBiTree (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,rear;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#include#include#include#includeBiTNode.hvoid main ()BiTree T = NULL;printf ( * * * 二叉树的建立与输出 * * *n);printf ( 计算机12117张航nnn);printf (先序遍历顺序输入二叉树的字符序列：n);CreateBiTree (T);printf (层次遍历输出当前二叉树：n);LevelBiTree (T);printf (n);2、 叶子结点统计的算法/BiTNode/.cpp#include#include#includeBiTNode.hint 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-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,leafcount (T);3、 二叉树深度统计算法/BiTNode.h/.cpp#include#include#includeBiTNode.hint 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;printf ( * * * 二叉树深度的统计 * * *n);printf ( 计算机12117张航nnn);printf (先序遍历顺序输入二叉树的字符序列：n);CreateBiTree (T);printf (层次遍历输出当前二叉树：n);LevelBiTree (T);printf (n);printf (二叉树的深度是：%dn,depth (T); 4程序调试（实验数据记录根据程序要求输入几组不同数据，记录程序运行结果，并分析结果,分析程序运行中出现的主要错误。或对其他程序环境的使用情况的记录。注：必须认真书写）BiTNode.h中CreateBiTree函数最初定义为int CreateBiTree (BiTree T)，导致程序运行时对main()中T赋值后LevelBiTree (T)为空，原因是按值传递形参T和实参T占用不同内存单元，调用CreateBiTree ()时，形参发生变化然后所在内存空间被释放，而实参至始至终没发生变化。将函数按照按地址传递定义后，问题迎刃而解。5讨论（通过实验的一些体会、学会的知识和技能等）通过算法2、3，我对递归回溯有了更深的体会。 数据结构 上机实验报告学号：1208010117 姓名： 张航 所在系：计算机科学与技术 班级： 121班 实验名称： 图的基本实现与应用 实验日期 2012/12/04 实验指导教师 刘勇 实验机房 4号机房 -3. 实验目的：(1) 理解图这种数据结构。(2) 掌握邻接矩阵、邻接表这种存储结构的实现方法。(3) 完成图的遍历的算法。2. 实验内容：（1）实现图的邻接矩阵与邻接表结构的转换。（必做）（2）实现图遍历的算法。（必做）（3）实现图的拓扑排序的算法。（4）实现图的最短路径的算法3算法设计（编程思路或流程图）1、 图的邻接矩阵和邻接表创建的算法/.cpp#include#include#include#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;VNode;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;iG.vexnum;i+)printf (输入顶点%d的值：n,i+1);scanf (%d,&G.vexsi);fflush (stdin);for (i=0;iG.vexnum;i+)for (j=0;jG.vexnum;j+)G.arcsij = NULL; for (k=0;kG.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);for (i=0;iG.vexnum;i+)for (j=0;jG.vexnum;j+)printf (%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;iALG.vexnum;i+)ALG.verticsi.data = G.vexsi;ALG.verticsi.firstarc = NULL;for (j=0;jadjvex = j;p-nextarc = ALG.verticsi.firstarc;ALG.verticsi.firstarc = p;return OK;void OutALGraph (ALGRAPH ALG)int i;ArcNode *p;printf (图的邻接链表显示:n);for (i=0;iALG.vexnum;i+)printf (%d,i,ALG.verticsi.data);p = ALG.verticsi.firstarc;while (p)printf (-%d,p-adjvex);p = p-nextarc;printf (-NULLn);void main ()printf (* * * 图的邻接矩阵和邻接链表的建立 * * *n);printf ( 计算机12117张航nnn); MGRAPH mg;CreateMGraph (mg);OutMGraph (mg);printf (nn);ALGRAPH alg;mg_to_alg (mg,alg);OutALGraph (alg);2、 图的两种遍历算法#include#include#include#define VEXTYPE int#define ADJTYPE int#define NULL 0#define OK 1#define ERROR -1#define TRUE 1#define FALSE 0typedef struct VEXTYPE vexs20;ADJTYPE arcs2020;int vexnum,arcnum;int kind;MGRAPH;typedef struct ArcNodeint adjvex;struct ArcNode *nextarc;ArcNode;typedef struct VNodeVEXTYPE data;ArcNode *firstarc;VNode;typedef structVNode vertics20;int vexnum,arcnum;int kind;ALGRAPH;bool visited20;int CreateMGraph (MGRAPH &G)int i,j,k;printf (输入顶点数和边数：n);scanf (%d%d,&G.vexnum,&G.arcnum);for (i=0;iG.vexnum;i+)printf (输入顶点%d的值：n,i+1);scanf (%d,&G.vexsi);fflush (stdin);for (i=0;iG.vexnum;i+)for (j=0;jG.vexnum;j+)G.arcsij = NULL; for (k=0;kG.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);for (i=0;iG.vexnum;i+)for (j=0;jG.vexnum;j+)printf (%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;iALG.vexnum;i+)ALG.verticsi.data = G.vexsi;ALG.verticsi.firstarc = NULL;for (j=0;jadjvex = j;p-nextarc = ALG.verticsi.firstarc;ALG.verticsi.firstarc = p;return OK;void OutALGraph (ALGRAPH ALG)int i;ArcNode *p;printf (图的邻接链表显示：n);for (i=0;iALG.vexnum;i+)printf (%d,i,ALG.verticsi.data);p = ALG.verticsi.firstarc;while (p)printf (-%d,p-adjvex);p = p-nextarc;printf (-NULLn);void DFS (ALGRAPH ALG,int v)ArcNode *p;visitedv = 1;printf (%3d,v);p = ALG.verticsv.firstarc;while (p)if (!visitedp-adjvex)DFS (ALG,p-adjvex);p = p-