数据结构实验指导书new.doc

数据结构实验指导书实验一 线性表的创建与应用一、 实验目的1、掌握线性表的定义2、 掌握线性表的基本操作：插入、删除、查找以及线性表合并等运算在链接存储结构上的运算。二、实验内容1、阅读并运行本实验程序（有序顺序表实现）2、用单链表方式实现本程序相应功能（有序单链表）3、利用有序单链表实现一元多项式的加法的功能。三、 实验要求1、 认真阅读和掌握本实验的参考程序（有序顺序表）。2、 上机运行该程序。3、 保存和打印出程序的运行结果，并结合程序进行分析。4、 按照有序顺序表功能，重新改写程序并运行，打印出文件清单和运行结果5、创建有序单链表时，要用头插法和尾插法同时实现。6、实现一元多项式的加法的功能，并输出结果。7、最好能将结果写入到文本文件中。四、 注意事项：1、实验学时：4学时2、实验完成一周内提交实验报告（实验报告本）3、实验结果要求抓图打印4、严禁抄袭五、 实验附件程序（有序顺序表）Odsqlist.h文件：#define LIST_INIT_SIZE 8 /线性表存储空间的初始分配量#define LISTINCREMENT 10 /线性表存储空间的分配增量#define OVERFLOW -2#define ERROR 0#define OK 1#define TRUE 1#define FALSE 0typedef int Status;typedef int ElemType;typedef struct ElemType *elem; / 存储空间基址int length; / 当前长度int listsize; / 当前分配的存储容量(以sizeof(ElemType)为单位)SqList; / 俗称 顺序表typedef SqList OdSqList; /有序顺序表Status InitList(OdSqList&); / 结构初始化void Destroy(OdSqList&); /销毁有序顺序表void ClearList(OdSqList&);/清空有序表Status ListEmpty(OdSqList);/判有序表为空int ListLength(OdSqList);/求表长int LocateElem(OdSqList,ElemType); / 查找void ListInsert(OdSqList&,ElemType); / 插入元素Status ListDelete(OdSqList&, int,ElemType& ); / 删除元素int ListDeletem(OdSqList&L, ElemType e); / 删除所有值为e的元素,返回删除的元素个数int ListDeletemn(OdSqList&, ElemType, ElemType ); / 删除所有值界于minkmaxk的元素，并返回删除的元素个数void ListTraverse(OdSqList);/遍历非递减有序线性表odsqlist.cpp文件：#include#include#include odsqlist.hStatus InitList( OdSqList& L ) / 构造一个空的线性表 L.elem = (ElemType*) malloc (LIST_INIT_SIZE*sizeof(ElemType);if (!L.elem) exit(OVERFLOW);L.length = 0;L.listsize = LIST_INIT_SIZE;return OK; / InitListvoid ListTraverse(OdSqList L)/遍历线性表int i;printf(listsize is %d.n,L.listsize);printf(listlength is %d.n,L.length);printf(the list is:();for(i=1;i=L.length;i+)printf(%d ,L.elemi-1);printf()n);int LocateElem(OdSqList L, ElemType e)/ 在顺序表中查询第一个满足判定条件的数据元素，若存在，则返回它的位序，否则返回 0int i;i = 1; / i 的初值为第 1 元素的位序ElemType *p;p = L.elem; / p 的初值为第 1 元素的存储位置while (i = L.length & *p+!=e) +i;if (i = L.listsize) / 当前存储空间已满，增加分配newbase = (ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof (ElemType);if (!newbase) exit(OVERFLOW);/ 存储分配失败L.elem = newbase; / 新基址L.listsize += LISTINCREMENT; / 增加存储容量q = &(L.elem0); / q 指示第1个元素位置for (p = &(L.elemL.length-1);p=q&*pe; -p) *(p+1) = *p; / 插入位置及之后的元素右移*(p+1) = e; / 插入e+L.length; / 表长增1Status ListDelete(OdSqList &L, int i, ElemType &e) ElemType *p,*q;if (i L.length) return ERROR;/ 删除位置不合法p = &(L.elemi-1); / p 为被删除元素的位置e = *p; / 被删除元素的值赋给 eq = L.elem+L.length-1; / 表尾元素的位置for (+p; p = q; +p) *(p-1) = *p; / 被删除元素之后的元素左移-L.length; / 表长减1return OK;void Destroy(OdSqList& L)/销毁有序顺序表free(L.elem);void ClearList(OdSqList& L)/清空有序表L.length=0;Status ListEmpty(OdSqList L)/判有序表为空if(L.length=0)return TRUE;else return FALSE;int ListLength(OdSqList L)/求表长return L.length;int ListDeletem(OdSqList& L, ElemType e)/ 删除所有值为e的元素,返回删除的元素个数ElemType *p,*q,*r;int i=0;/删除的元素个数p=&L.elem0;/扫描指针for(q=&L.elemL.length-1;*pe&p=q;p+);if(p=q&*p=e)i+;for(r=p+1;*r=e&r=q;r+,i+);if(r=q)for(;r=q;r+,p+)*p=*r;L.length-=i;return i;int ListDeletemn(OdSqList& L, ElemType mink, ElemType maxk)/ 删除所有值界于minkmaxk的元素，并返回删除的元素个数ElemType *p,*q,*r,temp;int i=0;if(maxkmink)temp=maxk;maxk=mink;mink=temp;p=&L.elem0;for(q=&L.elemL.length-1;*pmink&p=q;p+);/p指针指向第1个大于等于mink的元素if(p=q&*p=maxk)/若*p小于等于maxki+;for(r=p+1;*r=maxk&r=q;r+,i+);/r指针指向第1个大于maxk的元素if(r=q)for(;r=q;r+,p+)*p=*r;L.length-=i;return i;app.cpp文件:#include#include#include odsqlist.hvoid main()OdSqList L;int k;char i;ElemType e,mink,maxk;printf(OdSqList is initn);i=InitList(L);ListTraverse(L);while(1)printf(nnplease select:n);printf(1-insertn);printf(2-traversen);printf(3-deletein);printf(4-deletekn);printf(5-deletemink-maxkn);printf(6-locaten);printf(7-isemptyn);printf(8-lengthn);printf(9-clearlistn);printf(0-quitn);scanf(%d,&k);switch(k)case 1:printf(please input e:);scanf(%d,&e);ListInsert(L,e);ListTraverse(L);scanf(%c,&i);printf(please press any key to continue);scanf(%c,&i);break;case 2:ListTraverse(L);scanf(%c,&i);printf(please press any key to continue);scanf(%c,&i);break;case 3:while(1)printf(please input delete i:);scanf(%d,&i);if(ListDelete(L,i,e)=ERROR)printf(delete positon is error!n);else printf(Deleted elem is %dn,e);break;ListTraverse(L);scanf(%c,&i);printf(please press any key to continue);scanf(%c,&i);break;case 4:printf(please input delete e:);scanf(%d,&e);ListTraverse(L);printf(%d elem is deleted.n,ListDeletem(L,e);ListTraverse(L);scanf(%c,&i);printf(please press any key to continue);scanf(%c,&i);break;case 5:printf(please input delete mink and maxk:);scanf(%d%d,&mink,&maxk);ListTraverse(L);printf(%d elem is deleted.n,ListDeletemn(L,mink,maxk);ListTraverse(L);scanf(%c,&i);printf(please press any key to continue);scanf(%c,&i);break;case 6:printf(please input locate e:);scanf(%d,&e);i=LocateElem(L,e);if(i=0)printf(locate Defaulted!n);else printf(located no. is %dn,i);ListTraverse(L);scanf(%c,&i);printf(please press any key to continue);scanf(%c,&i);break;case 7:if(ListEmpty(L)printf(the orderlist is empty!n);elseprintf(the orderlist is not empty!n);scanf(%c,&i);printf(please press any key to continue);scanf(%c,&i);break;case 8:printf(length is %d.n,ListLength(L);scanf(%c,&i);printf(please press any key to continue);scanf(%c,&i);break;case 9:ClearList(L);printf(the orderlist is empty!n);scanf(%c,&i);printf(please press any key to continue);scanf(%c,&i);break;case 0:Destroy(L);exit(1);break;实验二 栈（队列）的创建与应用一、 实验目的1. 掌握栈（队列）的基本操作：初始化栈（队列）、判栈（队列）为空、出栈（队列）、入栈（队列）等运算。2. 掌握栈（队列）的应用方法，应用特点。二、实验要求1 认真阅读和掌握本实验提供的参考算法程序。2 上机实现实验内容算法。 3 保存和打印出程序的运行结果，并结合程序进行分析。三、实验内容1.表达式求值：已提供的表达式求值程序结构不好，请改进，要求用多文件方式实现，并将中序表达式变为后序表达式的结果写入文件。2.迷宫问题：已提供的迷宫问题算法程序有栈和队列实现两种方式，请你分别改进，要求用多文件方式实现，并将最终的路径写入文件。（以上提供的源码已随课件发给大家了）四、实验学时实验学时：2学时实验三 树的创建与应用一、实验目的1 掌握二叉树的二叉链表的定义方法。2 掌握基于二叉链表的二叉树的创建和遍历。3 掌握用线索二叉树的创建和遍历。二、实验要求 1 认真阅读和掌握本实验提供的参考算法程序。2 上机实现实验内容算法。 3保存和打印出程序的运行结果，并结合程序进行时空复杂度分析。三、实验学时四、实验学时实验学时：4学时四、实验步骤及内容1.创建二叉树和实现二叉树的三种遍历。a.创建二叉树：根据提示输入字符型数据创建二叉树，输入值为所有字符型数据。b.并能实现二叉树的先序、中序、后序的递归遍历：输出的结果为遍历后的每个结点的值的顺序。 2.在步骤1的基础上分别按照先序、中序、后序添加线索，再实现基于线索二叉树的遍历。实验四 图的存储与遍历一实验目的1 掌握图的基本存储方法。2 掌握有关图的操作算法并用高级语言编程实现；3 熟练掌握图的两种搜索路径的遍历方法。二实验要求1 认真阅读和掌握本实验的算法 。2 上机将本算法实现。3 保存和打印出程序的运行结果，并结合程序进行分析。4 按照你对图的操作需要，重新改写主程序并运行，打印出文件清单和运行结果三、实验学时实验学时：4学时四实验内容以邻接矩阵和邻接表的方式存储连通图。然后分别用深度优先算法遍历邻接矩阵方式存储的图和邻接表方式存储的图。算法 如下：深度优先遍历的递归算法 （1） 深度优先遍历算法 int visitedMaxVertexNum； /访问标志向量是全局量void DFSTraverse(ALGraph *G) /深度优先遍历以邻接表表示的图G，而以邻接矩阵表示G时，算法完全与此相同int i；for(i=0;in;i+)visitedi=FALSE； /标志向量初始化for(i=0;in；i+)if(!visitedi) /vi未访问过DFS(G，i)； /以vi为源点开始DFS搜索/DFSTraverse（2） 邻接表表示的深度优先搜索算法void DFS(ALGraph *G，int i) /以vi为出发点对邻接表表示的图G进行深度优先搜索EdgeNode *p；printf(visit vertex：c，G-adjlisti.vertex)；/访问顶点vivisitedi=TRUE； /标记vi已访问p=G-adjlisti.firstedge； /取vi边表的头指针while(p)/依次搜索vi的邻接点vj，这里j=p-adjvexif (!visitedp-adjvex)/若vi尚未被访问DFS(G，p-adjvex);/则以Vj为出发点向纵深搜索p=p-next； /找vi的下一邻接点/DFS#define MaxVertexNum 5#define m 5#define NULL 0typedef struct node int adjvex;struct node *next;JD;typedef struct tnode int vexdata; JD *firstarc;TD;typedef structTD agm;int n;ALGRAPH;void DFS(ALGRAPH *G,int i);void creat(ALGRAPH *G)int i,m1,j;JD *p,*p1;printf(please input the number of graphn);scanf(%d,&G-n);for(i=0;in;i+)printf(please input the info of node %d,i);scanf(%d,&G-agi.vexdata);printf(please input the number of arcs which adj to %d,i);scanf(%d,&m1);printf(please input the adjvex position of the first arcn);p=(JD *)malloc(sizeof(JD);scanf(%d,&p-adjvex);p-next=NULL;G-agi.firstarc=p;p1=p;for(j=2 ;jadjvex);p-next=NULL;p1-ne