c++数据结构实验报告.docx

c+数据结构实验报告 算法与数据结构;实验报告;实验一：栈与队列;一、实 验目的;1、掌握栈和队列特点、逻辑结构和存储结构;2、 熟悉对栈和队列的一些基本操作和具体的函数定义;3、利 用栈和队列的基本操作完成一定功能的程序;二、实验任务; 1.出顺序栈的类定义和函数实现，利用栈的基本操作;的转 换;2.给出顺序队列的类定义和函数实现，并利用队列计; 容;3.给出链栈的类定义和函数实现，并设计 算法与数据结构 实验报告 实验一：栈与队列 一、实验目的 1、掌握栈和队列特点、逻辑结构和存储结构 2、熟悉对栈和队列的一些基本操作和具体的函数定 义。 3、利用栈和队列的基本操作完成一定功能的程序。 二、实验任务 1. 出顺序栈的类定义和函数实现，利用栈的基本操 作完成十进制数 N 与其它 d 进制数 的转换。(如 N=1357,d=8) 2. 给出顺序队列的类定义和函数实现，并利用队列 计算并打印杨辉三角的前 n 行的内 容。(n=8) 3. 给出链栈的类定义和函数实现，并设计程序完成 如下功能：读入一个有限大小的整 数 n，并读入 n 个数，然后按照与输入次序相反的次 序输出各元素的值。 三、实验原理 1、将十进制数 N 转化为 d 进制时，用除去余数法， 用 d 除 N 所得余数作为 d 进制当前 个位，将相除所得的商 的整数部分作为新的 N 值重复上述计算，直到 N 为 0 为止。 将 前所得到的各余数反过来连接便得到最终结果。将每 次求出的余数入栈，求解结束后， 再依次出栈。 2、在杨 辉三角中可用上一行的数来求出对应位置的下一行的内容。 用队列保存上行内容， 每当由上行的两个数求出下行的一 个数时，其中的前一个便需要删除，而求出的数就 入队。 为便于求解，在每行的第一个位置添加一个 0 作为辅助。 3、输出操作应在读入所有输入的整数后才能进行， 用栈来存储这些数据，调用入栈出栈 函数实现相关功能。 四、程序清单 第一题 #include #ifndef STACK_H #define STACK_H const int maxlen=256; typedef int elementtype; enum error_codesuccess, underflow, overflow; class stack public: stack(); bool empty() const; bool full() const; error_code get_top(elementtype error_code push(const elementtype x); error_code pop(); private: int count; elementtype data; ; stack:stack()count=0; bool stack:empty() const if(count=0) return true; return false; error_code stack:get_top(elementtype elsex=data; return success; error_code stack:push(const elementtype x) if(full() return overflow; data=x; count+; return success; error_code stack:pop() if(empty() return underflow; count-; return success; bool stack:full() const if(count=maxlen) return true; return false; #endif void Dec_to_Ocx(int N, int d) stack S; int Mod,x; while(N!=0) Mod=N%d; 第二题 #include const int maxlen=256; typedef int elementtype; enum error_codesuccess, underflow, overflow; class queue public: queue(); bool empty()const; bool full()const; error_code get_front(elementtype error_code append(const elementtype x); error_code serve(); private: int count; int front,rear; elementtype data; ; queue:queue()count=0; front=rear=0; bool queue:empty()const if(count=0) return true; return false; bool queue:full()const if(count=maxlen-1) return true; return false; (Mod); N=N/d; while(!() _top(x); (); coutN; cind; Dec_to_Ocx(N,d); error_code queue:get_front(elementtype x=data; return success; error_code queue:append(const elementtype x) if(full() return overflow; rear=(rear+1)%maxlen; data=x; count +; return success; error_code queue:serve() if(empty() return underflow; front=(front+1)%maxlen; count-; return success; void Out_Number(int n) int s1,s2; queue Q; int i,j; error_code Ec; cout for(i=2; in; s1=s2; Out_Number(n); 第三题 #include #ifndef STACK_H #define STACK_H const int maxlen=256; typedef struct linklist int data; struct linklist *next; node; typedef int elementtype; enum error_codesuccess, underflow, overflow; class stack public: stack(); stack(); bool empty() const; bool full() const; error_code get_top(elementtype error_code push(const elementtype x); error_code pop(); private: int count; node*top; ; stack:stack() count = 0; top = NULL; bool stack:empty( )const return count = 0; bool stack:full( )const return false; error_code stack:get_top(elementtype x = top - data; return success; stack:stack( ) while ( !empty() ) pop( ); error_code stack:push(const elementtype x )node* s; s = new node; s - data = x; s-next=top; top = s; count +; return success; error_code stack:pop( ) if ( empty() ) return underflow;node* u; u = top; top=top-next; u; count -; return success; #endif void read_write() stack S; int x,n,i; coutn; for(i=1;ix; (x); while()!=true) _top(x); (); cout void main() read_write(); 五、运行结果 1、 2、 3、 实验二：单链表 一、实验目的： 1、理解线性表的链式存储结构。 2、熟练掌握动态链表结构及有关算法的设计。 3、根据具体问题的需要，设计出合理的表示数据的 链表结构，并设计相关算法。 二、实验任务： 1、在一个递增有序的链表 L 中插入一个值为 x 的元 素，并保持其递增有序特性。 实验数据：链表元素为 (10,20,30,40,50,60,70,80,90,100),x 分别为 25，85，110 和 8。 2、 将单链表 L 中的奇数项和偶数项 结点分解开，并分别连成一个带头结点的单链表，然后 再将这两个新链表同时输出在屏幕上，并保留原链表 的显示结果，以便对照求解结果。 实验测试数据基本要求： 第一组数据：链表元素为(1,2,3,4,5,6,;3.求两个递 增有序链表 L1 和 L2 中的公共元素，并;第一个链表元素为 (1，3，6，10，15，16，;第二个链表元素为 (1，2，3，4，5，6，7，8;第一个链表元素为 (1，3，6，10，15，16，;三、实验原理;1、给定了递增的 插入条件，需要搜索满足条件的插入;2、从链表 A 第一项 开始，第一项插入链表 B，第二 第一组数据：链表元素为 (1,2,3,4,5,6,7,8,9,10,20,30,40,50,60) 第二组数据： 链表元素为 (10,20,30,40,50,60,70,80,90,100) 3.求两个递增有序链表 L1 和 L2 中的公共元素，并以 同样方式连接成链表 L3。 实验测试数据基本要求： 第一 组数据： 第一个链表元素为 (1，3，6，10，15，16，17，18，19，20) 第二个链表元素为 (1，2，3，4，5，6，7，8，9，10，18，20，30) 第二组 数据： 第一个链表元素为 (1，3，6，10，15，16，17，18，19，20) 第二个链表元 素为 (2，4，5，7，8，9，12，22) 三、实验原理 1、给定了递增的插入条件，需要搜索满足条件的插 入位置的前驱结点。从原表的第一个 元素开始，直到某一 元素 A 的值大于要插入元素的值为止，A 的前驱结点便是插 入 位置。 2、从链表 A 第一项开始，第一项插入链表 B，第二项 插入链表 C，依次类推，奇数项 插入链表 B，偶数项插入 链表 C，直到无元素为止。 3、从 AB 表的第一项开始，若 A 第一项大于 B 第一项， B 向后搜索，如果找到共同元 就将其插入表 C，如无共同 元素，表 A 从第二项搜索，依次类推。若 A 的第一项小 于 B 的第一项，则该元素没有公共项，A 从第二项搜索，依次 类推。若 AB 第一项相 同，则该数就是公共元素，插入表 C，AB 都从第二项搜索，依次类推。 四、程序清单 第一、二题 #include struct node int data; node *next; ; class list public: list(); list(); int length(); void input_elem(const int n); void print(); node *get_head(); void set_(node *L,int data); void jiou_list(node *P,node *Q,node *R); private: int count; node *head; ; list:list() head=new node; head-next=NULL; count=0; list:list() node *p,*q; p = head-next; while(p!=NULL) q = p; p = p-next; q; int list:length() int n=0; node *p=head-next; while(p!=NULL) n+; p=p-next; return n; void list:input_elem(const int n) node *p,*pre; pre = head; for(int i=0;i p=new node; cinp-data; pre-next=p; pre=p; count+; pre-next=NULL; void list:print() node *p; p=head; p=p-next; while (p!=NULL) cout cout coutm; cout case 1: cout coutn; _elem(n); coutdata; _(_head(),data); (); cout 第三题 #include #include typedef int elementtype; struct Node elementtype data; Node*next; ; class list private: Node*head; Node*real; public: cout case 2: cout coutn; _elem (n); _list (_head(),_head(),_head(); cout cout cout cout list(); void common(list void create(); friend ostream real=head; ; void list:create() Node*u; elementtype x; cinx; while(x!=-1) u=new Node; u-data=x; real-next=u; real=u; cinx; real-next=NULL; ostream while(p!=NULL) outnext; out void list:common(list pa=next; pb=next; while(pa!=NULL else if(pa-datapb-data)pb=pb-next; else u=new Node; u-data=pa-data; real-next=u; real=u; pa=pa-next; pb=pb-next; real-next=NULL; void main() list L1,L2,L3; int i;elementtype x; cout 五、运行结果 1、 2、 3、 实验三：二叉树 一、实验目的： 1. 掌握二叉树的动态链表存储结构及表示。 2. 掌握二叉树的三种遍历算法(递归和非递归两类)。 3. 运用二叉树三种遍历的方法求解有关问题。 二、实验任务： 1. 建立一棵采用二叉链表结构存储的二叉树。 2. 分别采用递归和非递归两种方式对该二叉树进行 先序、中序和后序遍历。 3.求二叉树的高度以及二叉树中叶子结点的数目;三、 实验原理;1、按先序遍历的方法建立二叉树，结点的空孩 子用#;非递归中序遍历：遇到一个结点，就把它推入栈中， 并;非递归后序遍历：遇到一个结点，把它推入栈中，遍历; 3、求高度时，若 T 为空，则其高度为 0，结束，否则;四、 程序清单;递归并求叶子节点数和深度;#include 3. 求二叉树的高度以及二叉树中叶子结点的数目。 三、实验原理 1、按先序遍历的方法建立二叉树，结点的空孩子用# 代替输入，先建立根结点在建立左 右子树，依次类推。 2、对二叉树的遍历是在对各子树分别遍历的基础上进行的， 借助对整个二叉树的遍历算 法实现对左右子树的遍历。在 先序遍历以 T 为根的二叉树时，访问根结点后，分别 对根 结点*T 的左右孩子为根的子树进行遍历，中序后序递归遍 历也采用此思想。 非递归前序遍历：遇到一个结点，就访 问该结点，并把此结点入栈，然后下降去遍历 它的左子树。 遍历完它的左子树后，从栈顶托出这个结点，并按照它的 右链接指示的 地址再去遍历该结点的右子树结构。 非递归中序遍历：遇到一个结点，就把它推入栈中， 并去遍历它的左子树。遍历完左 子树后，从栈顶托出这个 结点并访问之，然后按照它的右链接指示的地址再去遍历 该 结点的右子树。 非递归后序遍历：遇到一个结点，把它推入栈中，遍 历它的左子树。遍历结束后，还 不能马上访问处于栈顶的 该结点，而是要再按照它的右链接结构指示的地址去遍历 该 结点的右子树。遍历遍右子树后才能从栈顶托出该结点 并访问之。另外，需要给栈中 的每个元素加上一个特征位， 以便当从栈顶托出一个结点时区别是从栈顶元素左边回 来 的(则要继续遍历右子树)，还是从右边回来的(该结点的左、 右子树均已周游)。特 征为 left 表示已进入该结点的左子 树，将从左边回来;特征为 right 表示已进入该结 点的右 子树，将从右边回来。 3、求高度时，若 T 为空，则其高度为 0，结束，否则， T 不为空时，可采用递归的方式， T 的左右子树的高度分 别能求出来，则二叉树的高度是其左右子树高度的最大值 加 1. 四、程序清单 递归并求叶子节点数和深度 #include typedef struct BiTNode char data; int bit; struct BiTNode *lchild,*rchild,*parent; BiTNode; void InitBT(BiTNode * int EmptyBT(BiTNode *t) if(t=0) return 1; else return 0; BiTNode *creatBT(BiTNode *t,int b) BiTNode *p; char ch; cinch; if(ch=#)return 0; else p=new BiTNode; p-data=ch; p-parent=t; p-bit=b; t=p; t-lchild=creatBT(t,0); t-rchild=creatBT(t,1); return t; void preorder(BiTNode *t) if(!EmptyBT(t) coutlchild); preorder(t-rchild); void inorder(BiTNode *t)/中序遍历 if(!EmptyBT(t) inorder(t-lchild); coutrchild); void postorder(BiTNode *t)/后序遍历 if(!EmptyBT(t) postorder(t-lchild); postorder(t-rchild); cout void coutBT(BiTNode *t,int /叶 子结点 非递归遍历 #include coutBT(t-lchild,m); coutBT(t-rchild,m); int BTdepth(BiTNode *t)/求二叉树的深度 int i,j; if(EmptyBT(t) return 0; else i=BTdepth(t-lchild); j=BTdepth(t-rchild); return (ij?i:j)+1; void main() BiTNode *t; int m,n,i,d,q,k; char x; InitBT(t); cout cout cout cout coutBT(t,m); cout d=BTdepth(t); cout const int MaxSize = 256; template struct BiNode T data; BiNode *lchild,*rchild; BiNode *btr; int flag; ; template class BiTree private: BiNode *root; BiNode *Create(); void Release(BiNode *root); public: BiTree(); BiTree(); BiNode *GetRoot(); void PreOrder(BiNode *root); void InOrder(BiNode *root); void PostOrder(BiNode *root); ; template BiTree:BiTree() this-root = Create(); template BiNode *BiTree:Create() BiNode *root; T ch; cinch; if(ch = #) root = NULL; else root = new BiNode; root-data = ch; root-lchild = Create(); root-rchild = Create(); return root; template BiNode *BiTree:GetRoot() return root; template BiTree:BiTree(void) Release(root); template void BiTree:PreOrder(BiNode *root) int top = -1; BiNode *Stack; while(root != NULL | top != -1) while(root != NULL) cout cout cout 2、非递归遍历结果 实验四:图 一、实验目的 1、掌握图的基本概念。 2、掌握图的存储结构的设计与实现，基本运算的实 现。 3、掌握图的两种遍历算法，以及遍历算法的应用。 二、实验任务 1、分别以邻接矩阵和邻接表的存储结构建立图。 2、分别对图进行深度优先遍历和广度优先遍历。 3、求图 中边的数目。 4、求顶点 0 到图中其余每个顶点的最短路径。 三、实验原理 1、邻接矩阵是表示图中顶点之间邻接关系的矩阵， 即表示各顶点之间是否有边关系的 矩阵。两点间若存在边 用 1 表示，不存在用 0 表示。邻接表将每个顶点的邻接点 连 成链表，并将各链表的表头指针合在一起，其中每个头 指针与该结点的信息合为一 个整体结点。 2、深度优先遍历，从顶点 v0 出发深度优先搜索遍历 图 G 的 dfs (v0)描述如下： (1) 访问 v0; (2) 依次从 v0 的未被访问过的邻接点出发深度遍历。 广度优先遍历，从顶点 v0 出发广度优先搜索遍历图 的算法 bfs(v0): (1)访问 v0 (2)依次访问 v0 的各邻接点。 (3)设最近一层访问序列为 vi1，vi2，vik， 则依次访问 vi1，vi2，vik 的未被访问过的邻 接点。 (4)重复上述操作(3)，直到所有可达的邻接点被访 问完为止。 4、用 bfs 生成树以 v0 为根的 bfs 生成树能给出 v0 到每个顶点的最短路径。 四、程序清单 第一题 邻接矩阵 #include #include #define INFINITY 0 #define MAX_VERTEX_NUM 10 #define MAX_EDGE_NUM 40 typedef enum DG,DN,UDG,UDNGraphkind; typedefcharVertexType;ty;intadj;/int*info;ArcCel l,AdjMatrix; typedef struct VertexType vexs; AdjMatrix arcs; int vexnum,arcnum; Graphkind kind; MGraph; int LocateVex(MGraph G,VertexType v1) int i; for(i=0;i int CreatUDN(MGraph int w,j; cout; cout cin; 邻接表 #include #include #define MAX_VERTEX_NUM 20 #define MAX_EDGE_NUM 40 int visited; typedef int VertexType ; typedef struct ArcNode int adjvex; for(i=0;i .adj=INFINITY; cout for(int k=0;k cinv1v2w; i=LocateVex(G,v1); j=LocateVex(G,v2); .adj=w; .adj=.adj; return 1; void dispMGraph(MGraph G) cout for(int j=0;j cout; cout; for(i=0;i .data=i; .firstarc=NULL; for(k=0;k coutij; p=(ArcNode*)malloc(sizeof(ArcNode); p- adjvex=j; p-nextarc=.firstarc; .firstarc=p; 第二题 #include #define MaxVerNum 50 struct edgenode int endver; int inform; edgenode* edgenext; ; struct vexnode char vertex; edgenode* edgelink; void Disp(ALGraph G) int i,j; ArcNode *p; cout p=.firstarc; j=0; while(p!=NULL) cout if(j=1) cout void main() ALGraph G; CreateDG(G); int v; Disp(G); cout ; struct Graph vexnode adjlists; int vexnum; int arcnum; ; struct QueueNode int nData; QueueNode* next; ; struct QueueList QueueNode* front; QueueNode* rear; ; void EnQueue(QueueList* Q,int e) QueueNode *q=new QueueNode; q-nData=e; q-next=NULL; if(Q=NULL) return; if(Q-rear=NULL) Q-front=Q- rear=q; else Q-rear-next=q; Q-rear=Q-rear- next; void DeQueue(QueueList* Q,int* e) if (Q=NULL) return; if (Q-front=Q-rear) *e=Q- front-nData; Q-front=Q-rear=NULL; else *e=Q-front-nData; Q-front=Q-front-next; void CreatAdjList(Graph* G) int i,j,k; edgenode* p1; edgenode* p2; coutG-vexnumG- arcnum; coutij; p1=new edgenode; p1-endver=j; p1-edgenext=G-adjlists.edgelink; G- adjlists.edgelink=p1; p2=new edgenode; p2- endver=i; p2-edgenext=G-adjlists.edgelink; G- adjlists.edgelink=p2; void DFS(Graph *G,int i,int visit) cout if (G-adjlists.vertex=c) m=i; DFS(G,i,visit); break; for(i=0;ivexnum;i+) if(visit=0) DFS(G,i,visit); cout void BFS(Graph* G,int v,int visit) QueueList *Q=new QueueList; Q-front=Q-rear=NULL; EnQueue(Q,v); while(Q-rear!=NULL) int e=0; DeQueue(Q, coutadjlists.vertex=c) m=i; BFS(G,i,visited); break; for(i=0;ivexnum;i+) if(visited=0) BFS(G,i,visited); cout void main() Graph * G=new Graph; CreatAdjList(G); char ch; coutch; DFStraversal(G,ch); BFStraversal(G,ch); #include #include #include using namespace std; #define MaxVertexNum 100 #define INF 32767 typedef struct char vertex; int edges; int n,e; MGraph; void CreateMGraph(MGraph cout; cout cin; for (i=0;i for (j=0;j =INF; if (i=j) =0; for (k=0;k cout cinijp; =p; void Dispath(int A,int path,int n); void lg(MGraph G) int A,path; int i,j,k; for (i=0;iA+A) A=A+A; path=k; Dispath(A,path,); void Ppath(int path,int i,int j) int k; k=path; if (k=-1) return; Ppath(path,i,k);printf(&;voidDispath(intA,int path,int n) int i,j; for (i=0;i 五、运行结果 1、建立图 邻接矩阵 else printf(“ 从%d 到%d=路径长度:%d 路径:“,i,j,A); printf(“%d,“,i); Ppath(path,i,j); printf(“%d “,j); int main() / freopen(“, “r“, stdin); MGraph G; CreateMGraph(G); lg(G); return 0; 2、遍历 邻接表 4、最短路径 实验五：查找 一、实验目的 1、掌握顺序表的查找方法，尤其是二分查找方法。 2、掌握二叉排序树的建立及查找。 二、实验任务 1、对下列数据表，分别采用二分查找算法实现查找， 给出查找过程依次所比较的元素 (的下标)，并以二分查找 的判定树来解释。 实验测试数据： 数据表为 (1,2,3,4,6,7,8,9,10,11,12,13,17,18,19,20,24,25,26,3 0,35,40,45,50,100) 查找的元素分别为： 2，8，20, 30，50，5，15，33，110 2、设计出在二叉排序树中插入结点的算法，在此基 础上实现构建二叉排序树的算法， 并给出其中序遍历序列。 实验测试数据： 构建二叉排序树的输入序列如下： 100，150，120，50，70，60，80，170，180，160， 110，30，40，35，175 设计算法在二叉排序树中查找指定值的结点： 在任务 2 所建立的二叉排序树中分别查找下列元素: 150,70,160,190,10,55,175 设计算法在二叉排序树中删除 特定值的结点。(选做) 在任务 2 所建立的二叉排序树中依次删除下列元素: 30,150,100,并给出中序遍历结 果。 三、实验原理 1、设查找区域的首尾下标分别用变量 low 和 high 表 示，将待查关键字 x 和该区域的中 间元素下标(low+high) /2，的关键字进行比较，若 x=A.key 查找成功，返回 mid 的值。若 xA.key 待查元素在右边区域，在此区域继续查找。 若 lowhigh，查找失败。 2、二叉排序树的构造：从空树 出发，依次插入各结点(作为叶子结点)。 二叉排序树中插入结点：(1)若结点的值小于根结点 的值，则往左子树中插入(2)若结 点的值大于等于根结点 的值，则往右子树中插入可通过递归调用插入算法来实现。 按 此方式递归调用若干次后，可以搜索到一个空子树位置， 即要插入的位置。 四、程序清单 第一题 #include #define elemtype int int binsearch(elemtype a,int n,elemtype x); int binsearch2(elemtype a,int n,elemtype x); void printarray(elemtype a,int n); int main() int i,x; const int n=26; elemtype a=1,2,3,4,5,6,7,8,9,10,11,12,13,17,18,19,20,24,25, 26,30,35,40,45,50,100; cout cinx; if(i=binsearch(a,n,x)0) cout int binsearch2(elemtype a,int n,elemtype x) int mid,low=1,high=n; while(low return mid; else if(x“ void printarray(int a,int n) int i; cout public: BiSortTree(void); void desplayTree(void); Tree(int key); treeNode* searchTree(int key); BiSortTree(); private: treeNode* buildTree(treeNode* head,int number); treeNode* search(treeNode* head ,int key); treeNode* BiSortTree:searchParent(treeNode* head,treeNode* p); treeNode* BiSortTree:searchMinRight(treeNode* head); treeNode* BiSortTree:searchTree(int key) return search(Head,key); treeNode* BiSortTree:search(treeNode* head ,int key) if(head=NULL) void showTree(treeNode* head); void destroyTree(treeNode* head); treeNode *Head; ; BiSortTree:BiSortTree() coutnumber; while(number!=-1) Head=buildTree(Head,number); cinnumber; treeNode* BiSortTree:buildTree(treeNode* head,int number) treeNode *p; p=new treeNode; p-key=number; p-left =p-right=NULL; if(head=NULL) return p; else if(p-key key) head-left=buildTree(head-left,number); else head-right=buildTree(head-right,number); return head; return NULL; if(head-key=key) return head; else if(keykey ) return search( head-left,key); else return search(head-right,key); BiSortTree:Tree(int key) treeNode *p; p=NULL; p=search(Head,key); if(p=NULL) cout if(p=Head) Head=NULL; else treeNode* parent; parent=searchParent(Head,p); if(p-left=NULL else parent-right=NULL;if(p- right=NULL);if(parent-left=p);parent-left=p- le;parent-right=p- l;treeNode*rightMinSon,*se;secondParent- left=ri;p-ri parent-right=NULL; else if(p-right=NULL) if(parent-left=p) parent-left=p-left ; else parent-right=p-left; else