线性结构基本算法的实现-数据结构实验报告.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-nextarc;void BFS (ALGRAPH ALG,int v)ArcNode *p;int queue20,rear=0,front=0;int i,w;for (i=0;iadjvex)printf (%3d,p-adjvex);visitedp-adjvex = 1;rear = (rear+1)%20;queuerear = p-adjvex;p = p-nextarc;void main ()printf (* * *图的遍历* * *n);printf ( 计算机12117张航n);MGRAPH mg;CreateMGraph (mg);OutMGraph (mg);printf (nn);ALGRAPH alg;mg_to_alg (mg,alg);OutALGraph (alg);printf (nnDFS遍历：n);DFS (alg,0);printf (nnBFS遍历：n);BFS (alg,0);printf (nn);4程序调试（实验数据记录根据程序要求输入几组不同数据，记录程序运行结果，并分析结果,分析程序运行中出现的主要错误。或对其他程序环境的使用情况的记录。注：必须认真书写）算法1mg_to_alg ()中语句p-nextarc = ALG.verticsi.firstarc; ALG.verticsi.firstarc = p;设计简洁有效：是先将新建表结点nextarc指针指向头结点firstarc指针所指的地址，然后将头结点firstarc指针指向新建表结点。对于不考虑链表中结点顺序，只将关联结点链接在一起，上述两条语句再合适不过了。5讨论（通过实验的一些体会、学会的知识和技能等）通过本实验，我了解到图的邻接矩阵的建立实则是用一个一维数组记录图中各结点信息，用一个二维数组记录各结点之间关系（边或弧的信息），然后对两数组赋值的过程；图的邻接链表的建立实则是定义一个表示图中各结点的头结点结构体，定义一个表示与图中各结点关联结点的表结点结构体，定义一个囊括图总体信息的结构体，然后对各头结点赋值（链接关联表结点）的过程。 数据结构 上机实验报告学号： 1208010117 姓名： 张航 所在系： 计算机科学与技术 班级： 121班 实验名称： 查找与排序 实验日期 2013/12/18 实验指导教师 刘勇 实验机房 4号机房 -4. 实验目的：(1) 理解查找与排序的各种算法。(2) 掌握二叉排序树、哈希表查找、简单排序、快速排序的算法2. 实验内容：（1）顺序查找的设计与实现。（2）折半查找的设计与实现。（3）直接插入排序的设计与实现。（4）快速排序的设计与实现。3算法设计（编程思路或流程图） （1） 顺序查找的算法#include#include#include#define ElemType int#define TRUE 1typedef struct ElemType *elem;int length;SqList;int CreateSqList (SqList &s_l,int n)int i;s_l.elem = (ElemType *)malloc (n+1)*sizeof(ElemType);printf (请输入%d个关