数据结构课程的实验报告.doc

实 验 报 告实验课程： 学生姓名： 学 号： 专业班级： 2012年 6月 5日目录（1）线性表及其应用3（2）栈和队列11（3）数组18（4）二叉树及其应用28（5）图的应用33（6）查找 排序38计算机系数据结构实验报告 -（1）线性表及其应用学生姓名： 学 号： 专业班级： 实验类型： 验证 综合 设计 创新 实验日期： 2012/3/18 实验成绩： 一实验目的帮助学生掌握线性表的基本操作在顺序和链表这两种存储结构上的实现，尤以链表的操作和应用作为重点。二问题描述1 构造一个空的线性表L；2 在线性表L的第i个元素之前插入新的元素e；3 在线性表L中删除第i个元素，并用e返回其值。三实验要求1分别利用顺序和链表存储结构实现线性表的存储，并设计出在不同的存储结构中线性表的基本操作算法。2在实验过程中，对相同的操作在不同的存储结构下的时间复杂度和空间复杂度进行分析。四算法分析1插入操作：输入数据：L = ( ) ListInsert (L, 1, k), 正确结果：L = (k)输入数据：L = (EHIKMOP) ListInsert (L, 9, t),正确结果：return ERROR; L = (EHIKMOP)输入数据：L = (ABCEHKNPQTU) ListInsert(L, 4, u), 正确结果： L = (ABCuEHKNPQTU)2删除操作：输入数据：L = () ListDelete (L, 1, e)正确结果：ERROR, L = ()输入数据：L = (DEFILMNORU) ListDelete_Sq(L, 5, e)正确结果： L = (DEFIMNORU), e=L输入数据：L = (CD) ListDelete_Sq(L, 1, e)正确结果： L = (D), e = C3如线性表有n个结点，对两种存储结构下插入和删除的时间复杂度进行分析。五实验内容和过程顺序存储C程序：#include #include typedef int elemtype;typedef int status;#define ERROR -1#define OK 1#define OVERFLOW 2008#define LIST_INIT_SIZE 100#define LISTINCREMENT 10typedef structelemtype *elem;int length;int listsize;sqlist;status InitList_Sq(sqlist *L)/构造一个空的线性表Lelemtype *a=0;a=(elemtype *)malloc(LIST_INIT_SIZE*sizeof(elemtype);L-elem=a;if(!(*L).elem)return OVERFLOW;(*L).listsize=LIST_INIT_SIZE;(*L).length=0;return OK;status List_Insert(sqlist *L,int i,elemtype e)/在第i个元素之前插入元素eelemtype * p=0; elemtype *q=0;elemtype * newbase=0;if(i(*L).length+1) return ERROR;if(*L).length=(*L).listsize)newbase=(elemtype *)realloc(*L).elem,(*L).listsize+LISTINCREMENT)*sizeof(elemtype);if(!newbase)return(OVERFLOW);(*L).elem=newbase;(*L).listsize+=LISTINCREMENT;q=&(*L).elemi-1);for(p=&(*L).elem(*L).length-1);p=q;-p)*(p+1)=*p;*q=e;+(*L).length;return OK;status GetElem(sqlist *L,int i,elemtype *e)(*e)=(*L).elemi-1;return OK;status List_Delete(sqlist *L,int i)/删除线性表的第i个元素if(i(*L).length) return ERROR;elemtype *p; elemtype *q;p=&(*L).elemi);q=p-1;int num;for(num=1;num=(*L).length-i);num+)(*q)=(*p); p+;q+;(*L).length-;return OK;status List_Travel(sqlist *L,status (* visit)(elemtype e)/遍历线性表中的元素 int i=1;for (i=1;i=(*L).length);i+)/循环（*L）.LENGTH次printf(第%d个元素为：,i);(* visit)(*L).elemi-1); return OK;status Display(elemtype e)printf(%dn,e);return OK;status main() sqlist LIST;elemtype ELEM; elemtype * e=&(ELEM); sqlist * L=&(LIST); printf(执行操作：n); printf(InitList_Sq(L);nList_Insert(L,1,10);nList_Insert(L,2,20);nList_Insert(L,3,30);n); InitList_Sq(L); List_Insert(L,1,10); List_Insert(L,2,20); List_Insert(L,3,30); List_Travel(L,Display); printf(执行操作：n); printf(List_Delete(L,2);n); List_Delete(L,2); List_Travel(L,Display); printf(执行操作：n); printf(GetElem(L,2,e);nDisplay(ELEM);); GetElem(L,2,e); Display(ELEM); List_Travel(L,Display); getchar();链式存储C程序：#include #include typedef int elemtype;typedef int status;#define ERROR -1#define OK 1#define OVERFLOW 2008typedef struct Lnodeelemtype data;struct Lnode * next; * Linklist; /头指针status InitLinklist(Linklist & name)name=(Linklist)malloc(sizeof(Lnode); if(!name)return ERROR;name-next=0;/定义指针域为空return OK;status ListInsert(Linklist & name, int num, elemtype elem) /在带头节点的单链表name中第i个位置之前插入元素elemLinklist p;p= name; int i=0;while(p & inext;i+;/寻找第num-1个节点并将P指向他if(!p|inum-1) return ERROR; Linklist temp;temp=(Linklist)malloc(sizeof(Lnode);temp-data=elem;temp-next=p-next;p-next=temp;return OK;status ListDelete(Linklist & name,int num)/在带头结点的单链表name中删除第num个数据元素元素Linklist p;p=name; int i=0;while(p&inext;i+;if(!p|inum-1) return ERROR;Linklist temp=p-next;p-next=p-next-next;/即使是删除最后一个元素，空指针也能继承 free(temp);status GetElem(Linklist & name, int num, elemtype & elem)Linklist p;p=name-next; int i=1;while(p & inext;+i; if(!p|inum) return ERROR; elem=p-data;return OK;status ListChange(Linklist & name, int num, elemtype elem)Linklist p;p=name-next; int i=1;while(p&inext;p-data=elem; return OK;status ListTravel(Linklist name, status (* visit) (elemtype i)Linklist p;p=name;int i=1;dop=p-next;printf(第%d个元素为:,i);(* visit)(p-data);i+;/注意：先移动指针再调用显示函数，因为do while 循环的特点是，先执行循环体再判断while后的条件是否成立while(p-next);return OK;status Display(elemtype i)printf(%dn,i);return OK;status main()Linklist L; elemtype elem; int i;printf(执行操作：nInitLinklist(L)nfor(i=1;i=5;i+)nListInsert(L,i,i);n);InitLinklist(L);for(i=1;i, , , , , ,- , , , , , ,* , , , , , ,/ , , , , , ,( , , , , , , , , , , ,# , , , , , , =2以字符序列的形式从终端输入语法正确、不含变量的算术表达式，利用给出的算符优先级关系，实现对算术四则混合运算的求解过程。四算法分析顺序优先级队列触雷操作的实现方法是：首先在遍历队列数据元素的基础上找出优先级最高的数据元素，然后依次把从原队列中第二个元素到队尾的所有元素前移一个位置，最后把队列的数据元素个数减1。由于顺序优先级队列每次出列操作后，有一个前移数据结构元素过程，这样，数据元素都集中在顺序队列的前边部分，因此顺序优先级队列不存在像顺序队列那样的“假溢出”问题。五实验内容和过程测试数据1输入数据：20-3+（5-1）+8/4正确结果：232输入数据：2*9-6-（20+4）/（4-1）正确结果：4代码：C程序：#include #include /typedef char char;typedef int status;#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2#define stack_init_size 100#define stack_increament 50typedef structchar * base;char * top;int stacksize;int length;charstack;/-status InitStack(charstack & S)S.base=(char *)malloc(stack_init_size*sizeof(char);if(!S.base)return OVERFLOW;S.stacksize=100;S.length=0;S.top=S.base;status Push(charstack & S,char e)if(!&S)return ERROR;if(S.length=S.stacksize)/若存储空间不够则重新分配char * newbase;newbase=(char *)realloc(S.base,(S.stacksize+stack_increament);if(!newbase)return OVERFLOW;S.base=newbase;*(S.top)=e;S.top+;S.stacksize+;/元素带入return OK; status Pop(charstack &S,char &e)if(!&S)return ERROR;if(S.top =S.base)return ERROR;e=*(S.top-1);S.top-;S.stacksize-;return OK;status FreeStack(charstack &S)if(!&S)return ERROR;free(S.base);return OK;char GetTop(charstack &S)char e;if(S.top=S.base) return ERROR;e=*(S.top -1);return e;/gettop#include charstack.h#include intstack.h#include #include #include #include #define OPSETSIZE 7unsigned char Prior77 = /用二维数组表示表 , , , , , , , ,=;char OPOPSETSIZE=+ , - , * , / ,( , ) , #;/算符集合float Operate(float a,unsigned char theta, float b) switch(theta) case +: return a+b; case -: return a-b; case *: return a*b; case /: return a/b; default : return 0; /运算函数status In(char Test,char* TestOp) bool Find=false; for (int i=0; i OPSETSIZE; i+) if (Test = TestOpi) Find= true; return Find;/判断是否为运算符int ReturnOpOrd(char op,char* TestOp) int i; for(i=0; i OPSETSIZE; i+) if (op = TestOpi) return i; return 0;/返回算符位序char precede(char Aop, char Bop) return PriorReturnOpOrd(Aop,OP)ReturnOpOrd(Bop,OP);/判断优先级float EvaluateExpression(char* MyExpression) /主函数 / 算术表达式求值的算符优先算法。 / 设OPTR和OPND分别为运算符栈和运算数栈，OP为运算符集合。 charstack OPTR; / 运算符栈，字符元素 intstack OPND; / 运算数栈，实数元素 char TempData20; float Data,a,b; char theta,*c,x,Dr2; InitStack (OPTR); Push (OPTR, #); InitStack (OPND); c = MyExpression; strcpy(TempData,0);/把src所指由NULL结束的字符串复制到dest所指的数组中 TempData置0 while (*c!= # | GetTop(OPTR)!= #) if (!In(*c, OP) /不是运算符 Dr0=*c; Dr1=0; strcat(TempData,Dr);/把src所指字符串添加到dest结尾处(覆盖dest结尾处的0)并添加0。 c+; if(In(*c,OP) Data=(float)atof(TempData); Push(OPND, Data); strcpy(TempData,0);/清空TempData,最长位数不能超过20位 else / 不是运算符则进栈 switch (precede(GetTop(OPTR), *c) case : / 退栈并将运算结果入栈 Pop(OPTR, theta); Pop(OPND, b); Pop(OPND, a); Push(OPND, Operate(a, theta, b); break; / switch / while return GetTop(OPND); / EvaluateExpressionstatus main()float i=0;int j=0;char c;doprintf(Welcome，请输入算符表达式：(例如“3+2”，按E退出）n);char exp50;for(j=0;j1);/确保无限循环六实验结果截图：七总结和感想 通过这个实验，进一步了解了栈和队列的定义和特性，进一步学习了符优先级 ，了解了用算符优先级对算术表达式的求解过程。计算机系数据结构实验报告 -（3）数组学生姓名： 学 号： 专业班级： 实验类型： 验证 综合 设计 创新 实验日期： 2012/4/26 实验成绩： 一、实验目的深入研究数组的存储表示和实现技术，着重掌握对稀疏矩阵的表示方法及其运算的实现。二、问题描述稀疏矩阵是指那些多数元素为零的矩阵。利用稀疏特点进行存储和计算可以大大节省存储空间，提高效率。通过对稀疏矩阵的存储表示，实现矩阵的基本操作。三、实验要求1、 要求矩阵的输入形式采用三元组表示，以“带行逻辑链接信息”的三元组顺序表表示稀疏矩阵。2、 设计矩阵的逆置算法，实现矩阵的逆置。3、 实现两个稀疏矩阵的相加、相减和相乘等运算。4、 要求运算结果的矩阵则以通常的阵列形式出现。四、算法分析首先应输入矩阵的行数和列数、并判别给出的两个矩阵的行、列数对于所要求的运算是否相匹配；1、 以三元组的形式输入矩阵；2、 调用矩阵的逆置子函数、相加函数和相乘函数；3、 分析输出结果，并进行总结。五、实验内容和过程 输入数据：2 1 00 0 00 0 32 0 01 0 00 0 3-12 1 00 0 00 0 30 0 00 0 00 0 2+=2 1 00 0 00 0 52 1 00 0 30 00 00 2+=0 00 6程序：#include#include#include#includeusing namespace std;#define max 100#define datatype int typedef structint row,col;/行，列datatype v;/非0数值Node;typedef structNode datamax;/稀疏矩阵int m,n,t;/m行，n列，t非0数个数Matrix; /*求逆矩阵存储*/typedef struct /存储结构int m, n; /行、列数double *p; /矩阵基址nMatrix;void In(nMatrix a) /求逆输入 couta.ma.n;int m = a.m, n = a.n;int i, j;double *p = a.p = new doublem * n; /p是行指针cout请按行优先输入矩阵a的全部数值：n;for (i = 0; i m; p += n, i+)for (j = 0; j pj; /即a.pi*n+jvoid Out(nMatrix a) /求逆输出 int m = a.m, n = a.n;int i, j;double *p = a.p;for (i = 0; i m; p += n, i+)for (j = 0; j n; j+)coutpjt;cout(istream& input,Matrix &A)int i;coutA.m;coutA.n;coutA.t;for(i=1;i=A.t;i+)cout请输入行数，列数，非0值:(iA.datai.rowA.datai.colA.datai.v;return input;ostream& operator (ostream& output,Matrix &A)int i,j,t=1,k=0;for(i=1;i=A.m;i+)for(j=1;j=A.n;j+)if(A.datat.row=i&A.datat.col=j)outputA.datat.vt;t+;else outputkt;coutn;return output;Matrix operator +(Matrix A,Matrix B)/加法int i,j,k;Matrix C;if(A.m!=B.m|A.n!=B.n) cout这两个矩阵不能相加endl;exit(0);C.m=A.m;C.n=A.n;C.t=0;if(A.t=0&B.t=0) exit(0);i=j=k=1;while(i=A.t&j=B.t)if(A.datai.rowB.dataj.row)C.datak=B.dataj;j+;k+;elseif(A.datai.colB.dataj.col)C.datak=B.dataj;j+;k+;elseif(A.datai.v+B.dataj.v!=0)C.datak.row=A.datai.row;C.datak.col=A.datai.col;C.datak.v=A.datai.v+B.dataj.v;k+;i+;j+; while(iA.t)C.datak=A.datai;i+;k+;while(jB.t)C.datak=B.dataj;j+;k+;C.t=k; return C;Matrix operator -(Matrix A,Matrix B)Matrix C;int i,j,k; if(A.m!=B.m|A.n!=B.n) cout这两个矩阵不能相减;exit(0); C.m=A.m;C.n=A.n; C.t=0; if(A.t=0&B.t=0) exit(0); i=j=k=1; while(i=A.t&j=B.t) if(A.datai.rowB.dataj.row) C.datak=B.dataj; j+;k+; else if(A.datai.colB.dataj.col) C.datak=B.dataj; j+;k+; else if(A.datai.v-B.dataj.v!=0) C.datak.row=A.datai.row; C.datak.col=A.datai.col; C.datak.v=A.datai.v-B.dataj.v; k+; i+;j+; while(iA.t) C.datak=A.datai; i+;k+; while(jB.t) C.datak=B.dataj; j+;k+; C.t=k; return C;Matrix operator *(Matrix A,Matrix B)Matrix C;int k,p,crow,brow,q,ccol;int nummax,posmax,ctempmax;if (A.n=B.m)for(k=1;k=B.m;k+)numk=0;for(k=1;k=B.t;k+)numB.datak.row+;pos1=1;for(k=2;k=B.t;k+)posk=posk-1+numk-1;pos1+B.t=posB.t+1;C.m=A.m; C.n=B.n; C.t=0; p=1;while(p=A.t)crow=A.datap.row;for(k=1;k=C.n;k+)ctempk=0;while (p=A.t&A.datap.row=crow)brow=A.datap.col;for(q=posbrow;q=posbrow+1-1;q+)ccol=B.dataq.col;ctempccol=ctempccol+A.datap.v*B.dataq.v;p=p+1;for(ccol=1;ccol=B.n;ccol+)if(ctempccol!=0)C.t=C.t+1;C.dataC.t.row=crow;C.dataC.t.col=ccol;C.dataC.t.v=ctempccol;else cout这两个矩阵不能相乘;return C;Matrix operator (Matrix A)Matrix B;int col,i,p,q;int nummax,positionmax;B.t=A.t;B.m=A.n; B.n=A.m;if(B.t)for(col=1;col=A.n;col+)numcol=0;for(i=1;i=A.t;i+)numA.datai.col+;position1=1;for(col=2;col=A.n;col+)positioncol=positioncol-1+numcol-1;for(p=1;p=A.t;p+)col=A.datap.col;q=positioncol;B.dataq.row=A.datap.col;B.dataq.col=A.datap.row;B.dataq.v=A.datap.v;positioncol+;return B;nMatrix Trs(nMatrix a) /求逆矩阵的先转置nMatrix trs;trs.m = a.n;trs.n = a.m;trs.p = new doublea.m * a.n;for (int i = 0; i a.m; i+)for (int j = 0; j a.n; j+)trs.pj * a.m + i = a.pi * a.n + j;return trs;nMatrix Adjunct(nMatrix a, int indexm, int indexn) /求第indexm行indexn列元素的代数余子式nMatrix adj;adj.m=a.m - 1;adj.n=a.n - 1;adj.p = new double(a.n - 1) * (a.n - 1);for (int i = 0; i indexm; i+)for (int j = 0; j indexn; j+)adj.pi * (a.n - 1) + j = a.pi * a.n + j;for (int k = indexn + 1; k a.n; k+)adj.pi *(a.n - 1) + k -1 = a.pi * a.n + k;for (int m = indexm + 1; m a.n; m+)for (int j = 0; j a.n - 1; j+)adj.p(m - 1) * (a.n - 1) + j = a.pm * a.n + j;for (int k = indexn + 1; k a.n; k+)adj.p(m - 1) * (a.n - 1) + k - 1 = a.pm * a.n + k;return adj;double Det(nMatrix a) /递归求行列式double det = 0;if (a.m != a.n)cout不是方阵，没有行列式!endl;cout求行列式退出endl;if (a.n = 1)det = a.p0;return det;elsefor (int i = 0; i a.n; i+)if (i % 2 = 0)det += a.pi * a.n * Det(Adjunct(a, i, 0);else det -= a.pi * a.n * Det(Adjunct(a, i, 0);return det;nMatrix operator !(nMatrix a) /求矩阵的逆nMatrix temp;temp.m=a.n;temp.n=a.m;temp.p = new doublea.m * a.n;/矩阵的逆 = 伴随矩阵 / 行列式double det = Det(a);if (det = 0) /如果行列式的值为0，则没有逆cout此矩阵没有逆!endl;cout求矩阵逆退出!endl;for (int i = 0; i temp.m; i+)for (int j = 0; j A; couta=nB; coutb=nB;C=A+B;couta+b=nC;C=A-B;couta-b=nC;C=A*B;couta*b=nC;C=A;couta=nC;In(a);cout矩阵的行列式为:endl;coutDet(a)endl;cout矩阵的逆为:endl;temp=!a;cout!a=nTrsendl;六、实验结果7.总结和感想：这次实验使我对数据结构和C语言的理解更加深刻，也使我认识到了自己很多不足之处，加深了对数组的理解。计算机系数据结构实验报告 -（4）二叉树及其应用学生姓名： 学 号： 专业班级： 实验类型： 验证 综合 设计 创新 实验日期： 2012/5/13 实验成绩： 一实验目的树是数据结构中应用极为广泛的非线性结构，本单元的实验达到熟悉二叉树的存储结构的特性，以及如何应用树结构解决具体问题。二问题描述首先，掌握二叉树的各种存储结构和熟悉对二叉树的基本操作。其次，以二叉树表示算术表达式的基础上，设计一个十进制的四则运算的计算器。-+/a*b-efCd如算术表达式：a+b*(c-d)-e/f三实验要求1如果利用完全二叉树的性质和二叉链表结构建立一棵二叉树，分别计算1）统计叶子结点的个数；2）求二叉树的深度。2十进制的四则运算的计算器可以接收用户来自键盘的输入；3由输入的表达式字符串动态生成算术表达式所对应的二叉树；4自动完成求值运算和输出结果。四算法分析1、非递归的二叉树前序遍历算法如下。（1）初始化设置一个堆栈。（2）把根结点指针入栈。（3）当堆栈非空时，循环执行步骤到步骤出栈取得一个结点指针，访问该结点；若该结点的右子树非空，则将该结点的右子树指针入栈；若该结点的左子树非空，则将该结点的左子树指针入栈；（4）结束。2、二叉树的层序遍历算法如下。初始化设置一个队列。把根结点指针入队列。当队列非空时，循环执行