数据结构实验四五六

实验日期：_______________ 实验指导老师：
实验4 无向图的深度优先搜索
一、实验目的和实验环境
【实验目的】
1、了解图的定义、特点，区分无向图和有向图的概念；
2、了解图的数据结构和搜索方法；
3、掌握无向图的邻接矩阵、邻接表的表示方法；
4、写出无向图的深度优先搜索程序。

【实验环境】ＶＣ＋＋６.０
二、理论依据
邻接多重表是无向图的一种很有效链式存储结构，在邻接表中容易求得顶点和边的各种信息。

除了在边结点中增加一个标志域外，邻接多重表所需的存储量和邻接表相同。

三、实验内容
设无向图G有n个点e条边，写一算法建立G的邻接多表，并按照深度优先搜索输出顶点，要求该算法时间复杂性为O（n+e），且除邻接多表本身所占空间之外只用O（1）辅助空间。

四、实验步骤
1、了解图的定义、特点，区分无向图和有向图的概念；
2、了解图的数据结构和搜索方法；
3、掌握无向图的邻接矩阵、邻接表的表示方法；
４、写出无向图的深度优先搜索程序
五、实验结果
1.源代码如下：
实验日期：_______________ 实验指导老师：
2.运行界面截图如下：
六、小结
1、在创建邻接多重表时，由于邻接多重表的数据类型为字符型，键盘输入总是很难控制。

这时可以通过人为设置函数过滤去键盘输入中的空格。

2、在邻接多重表上，各种基本操作的实现和邻接表相似。

3、在邻接多重表中，所有依附于同一顶点的边串联在同一链表中。

《数据结构》实验报告目录一、实验概述 (2)二、实验原理 (2)2.1 数据结构基本概念 (3)2.2 选择的数据结构类型 (4)2.3 实验原理说明 (5)三、实验步骤 (6)3.1 实验准备 (7)3.2 数据结构选择与实现 (7)3.2.1 数据结构类型选择 (9)3.2.2 数据结构实现细节 (9)3.3 实验功能实现 (10)3.3.1 功能一 (11)3.3.2 功能二 (12)四、实验结果与分析 (13)4.1 实验数据 (15)4.2 结果展示 (16)4.2.1 结果一展示 (17)4.2.2 结果二展示 (17)4.3 结果分析 (18)4.3.1 结果一分析 (19)4.3.2 结果二分析 (20)五、实验总结与讨论 (22)5.1 实验总结 (23)5.2 实验中遇到的问题及解决方法 (24)5.3 对数据结构的认识与体会 (25)5.4 对实验教学的建议 (27)一、实验概述本次实验旨在通过实际操作，加深对《数据结构》课程中所学理论知识的理解和掌握。

实验内容围绕数据结构的基本概念、常用算法以及在实际应用中的实现进行设计。

通过本次实验，学生将能够：理解并掌握线性表、栈、队列、链表、树、图等基本数据结构的特点和适用场景。

掌握常用的数据结构操作算法，如插入、删除、查找等，并能够运用这些算法解决实际问题。

学习使用C++、或其他编程语言实现数据结构的操作，提高编程能力和算法设计能力。

本次实验报告将对实验的目的、内容、步骤、结果及分析等方面进行详细阐述，旨在通过实验过程的学习，提高学生对数据结构理论知识的理解和应用能力。

二、实验原理数据结构的基本概念：介绍数据结构的基本定义，包括数据元素、数据集合、数据关系等基本概念，以及数据结构的三要素：逻辑结构、存储结构和运算。

栈和队列：介绍栈和队列的定义、特点、基本运算及其在算法设计中的重要性。

树和二叉树：讲解树的基本概念、二叉树的结构特点、遍历方法、二叉搜索树及其在数据检索中的应用。

数据结构实验报告想必学计算机专业的同学都知道数据结构是一门比较重要的课程，那么，下面是小编给大家整理收集的数据结构实验报告，供大家阅读参考。

数据结构实验报告1一、实验目的及要求1)掌握栈和队列这两种特殊的线性表，熟悉它们的特性，在实际问题背景下灵活运用它们。

本实验训练的要点是“栈”和“队列”的观点;二、实验内容1) 利用栈，实现数制转换。

2) 利用栈，实现任一个表达式中的语法检查(选做)。

3) 编程实现队列在两种存储结构中的基本操作(队列的初始化、判队列空、入队列、出队列);三、实验流程、操作步骤或核心代码、算法片段顺序栈：Status InitStack(SqStack &S){S.base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemTyp e));if(!S.base)return ERROR;S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;}Status DestoryStack(SqStack &S){free(S.base);return OK;}Status ClearStack(SqStack &S){S.top=S.base;return OK;}Status StackEmpty(SqStack S){if(S.base==S.top)return OK;return ERROR;}int StackLength(SqStack S){return S.top-S.base;}Status GetTop(SqStack S,ElemType &e){if(S.top-S.base>=S.stacksize){S.base=(ElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemTyp e));if(!S.base) return ERROR;S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*S.top++=e;return OK;Status Push(SqStack &S,ElemType e){if(S.top-S.base>=S.stacksize){S.base=(ElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemTyp e));if(!S.base)return ERROR;S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*S.top++=e;return OK;}Status Pop(SqStack &S,ElemType &e){if(S.top==S.base)return ERROR;e=*--S.top;return OK;}Status StackTraverse(SqStack S){ElemType *p;p=(ElemType *)malloc(sizeof(ElemType));if(!p) return ERROR;p=S.top;while(p!=S.base)//S.top上面一个...p--;printf("%d ",*p);}return OK;}Status Compare(SqStack &S){int flag,TURE=OK,FALSE=ERROR; ElemType e,x;InitStack(S);flag=OK;printf("请输入要进栈或出栈的元素："); while((x= getchar)!='#'&&flag) {switch (x){case '(':case '[':case '{':if(Push(S,x)==OK)printf("括号匹配成功!\n\n"); break;case ')':if(Pop(S,e)==ERROR || e!='('){printf("没有满足条件\n");flag=FALSE;}break;case ']':if ( Pop(S,e)==ERROR || e!='[')flag=FALSE;break;case '}':if ( Pop(S,e)==ERROR || e!='{')flag=FALSE;break;}}if (flag && x=='#' && StackEmpty(S)) return OK;elsereturn ERROR;}链队列：Status InitQueue(LinkQueue &Q) {Q.front =Q.rear=(QueuePtr)malloc(sizeof(QNode));if (!Q.front) return ERROR;Q.front->next = NULL;return OK;}Status DestoryQueue(LinkQueue &Q) {while(Q.front){Q.rear=Q.front->next;free(Q.front);Q.front=Q.rear;}return OK;}Status QueueEmpty(LinkQueue &Q){if(Q.front->next==NULL)return OK;return ERROR;}Status QueueLength(LinkQueue Q){int i=0;QueuePtr p,q;p=Q.front;while(p->next){i++;p=Q.front;q=p->next;p=q;}return i;}Status GetHead(LinkQueue Q,ElemType &e) {QueuePtr p;p=Q.front->next;if(!p)return ERROR;e=p->data;return e;}Status ClearQueue(LinkQueue &Q){QueuePtr p;while(Q.front->next ){p=Q.front->next;free(Q.front);Q.front=p;}Q.front->next=NULL;Q.rear->next=NULL;return OK;}Status EnQueue(LinkQueue &Q,ElemType e) {QueuePtr p;p=(QueuePtr)malloc(sizeof (QNode));if(!p)return ERROR;p->data=e;p->next=NULL;Q.rear->next = p;Q.rear=p; //p->next 为空return OK;}Status DeQueue(LinkQueue &Q,ElemType &e) {QueuePtr p;if (Q.front == Q.rear)return ERROR;p = Q.front->next;e = p->data;Q.front->next = p->next;if (Q.rear == p)Q.rear = Q.front; //只有一个元素时(不存在指向尾指针) free (p);return OK;}Status QueueTraverse(LinkQueue Q){QueuePtr p,q;if( QueueEmpty(Q)==OK){printf("这是一个空队列!\n");return ERROR;}p=Q.front->next;while(p){q=p;printf("%d<-\n",q->data);q=p->next;p=q;}return OK;}循环队列：Status InitQueue(SqQueue &Q){Q.base=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType)); if(!Q.base)exit(OWERFLOW);Q.front=Q.rear=0;return OK;}Status EnQueue(SqQueue &Q,QElemType e){if((Q.rear+1)%MAXQSIZE==Q.front)return ERROR;Q.base[Q.rear]=e;Q.rear=(Q.rear+1)%MAXQSIZE;return OK;}Status DeQueue(SqQueue &Q,QElemType &e){if(Q.front==Q.rear)return ERROR;e=Q.base[Q.front];Q.front=(Q.front+1)%MAXQSIZE;return OK;}int QueueLength(SqQueue Q){return(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;}Status DestoryQueue(SqQueue &Q){free(Q.base);return OK;}Status QueueEmpty(SqQueue Q) //判空{if(Q.front ==Q.rear)return OK;return ERROR;}Status QueueTraverse(SqQueue Q){if(Q.front==Q.rear)printf("这是一个空队列!");while(Q.front%MAXQSIZE!=Q.rear){printf("%d<- ",Q.base[Q.front]);Q.front++;}return OK;}数据结构实验报告2一.实验内容：实现哈夫曼编码的生成算法。

数据结构实验报告实验5一、实验目的本次实验的主要目的是深入理解和掌握常见的数据结构，如链表、栈、队列、树和图等，并通过实际编程实现，提高对数据结构的操作和应用能力。

同时，培养解决实际问题的思维和编程能力，提高代码的可读性、可维护性和效率。

二、实验环境本次实验使用的编程语言为C+＋，开发环境为Visual Studio 2019。

三、实验内容1、链表的基本操作创建链表插入节点删除节点遍历链表2、栈的实现与应用用数组实现栈用链表实现栈栈的应用：括号匹配3、队列的实现与应用用数组实现队列用链表实现队列队列的应用：排队模拟4、二叉树的遍历前序遍历中序遍历后序遍历5、图的表示与遍历邻接矩阵表示法邻接表表示法深度优先遍历广度优先遍历四、实验步骤1、链表的基本操作创建链表：首先定义一个链表节点结构体，包含数据域和指向下一个节点的指针域。

然后通过动态内存分配创建链表节点，并将节点逐个连接起来，形成链表。

插入节点：根据插入位置的不同，分为在表头插入、在表尾插入和在指定位置插入。

在指定位置插入时，需要先找到插入位置的前一个节点，然后进行节点的连接操作。

删除节点：同样需要根据删除位置的不同进行处理。

删除表头节点时，直接将头指针指向下一个节点；删除表尾节点时，找到倒数第二个节点，将其指针置为空；删除指定位置节点时，找到要删除节点的前一个节点，然后调整指针。

遍历链表：通过从链表头开始，依次访问每个节点，输出节点的数据。

2、栈的实现与应用用数组实现栈：定义一个固定大小的数组作为栈的存储空间，同时用一个变量记录栈顶位置。

入栈操作时，先判断栈是否已满，如果未满则将元素放入栈顶位置，并更新栈顶位置；出栈操作时，先判断栈是否为空，如果不空则取出栈顶元素，并更新栈顶位置。

用链表实现栈：与链表的操作类似，将新元素添加在链表头部作为栈顶。

括号匹配：输入一个包含括号的字符串，使用栈来判断括号是否匹配。

遇到左括号入栈，遇到右括号时与栈顶的左括号进行匹配，如果匹配成功则出栈，否则括号不匹配。

数据结构实验实验四、图遍历的演示。

【实验学时】 5 学时【实验目的】（1）掌握图的基本存储方法。

（2）熟练掌握图的两种搜索路径的遍历方法。

【问题描述】很多涉及图上操作的算法都是以图的遍历操作为基础的。

试写一个程序，演示连通的无向图上，遍历全部结点的操作。

【基本要求】以邻接多重表为存储结构，实现连通无向图的深度优先和广度优先遍历。

以用户指定的结点为起点，分别输出每种遍历下的结点访问序列和相应生成树的边集。

【测试数据】教科书图7.33 。

暂时忽略里程，起点为北京。

【实现提示】设图的结点不超过30个，每个结点用一个编号表示（如果一个图有n 个结点，则它们的编号分别为1, 2,…，n）。

通过输入图的全部边输入一个图，每个边为一个数对，可以对边的输入顺序作出某种限制。

注意，生成树的边是有向边，端点顺序不能颠倒。

【选作内容】（1）借助于栈类型（自己定义和实现），用非递归算法实现深度优先遍历。

（2）以邻接表为存储结构，建立深度优先生成树和广度优先生成树，再按凹入表或树形打印生成树。

（3）正如习题7。

8 提示中分析的那样，图的路径遍历要比结点遍历具有更为广泛的应用。

再写一个路径遍历算法，求出从北京到广州中途不过郑州的所有简单路径及其里程。

【源程序】#include<iostream.h>#include <stdio.h>#include <stdlib.h>#define MAX_VERTEX_NUM 20#define STACK_INIT_SIZE 100#define STACKINCREMENT 10#define TRUE 1#define OK 1#define FALSE 0#define ERROR 0#define OVERFLOW -2typedef enum{DG,DN,UDG,UDN}GraphKind;//{ 有向图, 有向网, 无向图,无向网} bool visited[MAX_VERTEX_NUM];typedef struct ArcNode{int adjvex;// 该弧所指向的顶点在数组中的下标struct ArcNode *nextarc;int *info;// 该弧相关信息的指针}ArcNode;typedef struct VNode{int data;// 顶点信息ArcNode *firstarc;// 指向第一条依附该顶点的弧的指针}VNode,AdjList[MAX_VERTEX_NUM];typedef struct{AdjList vertices;int vexnum,arcnum;// 图的当前顶点数和弧数int kind;// 图的种类标志}ALGraph;typedef struct{int *base;int *top;int stacksize;}SqStack;typedef struct QNode{int data;struct QNode *next;}QNode,*QueuePtr;typedef struct{QueuePtr front;QueuePtr rear;}LinkQueue;int LocateVex(ALGraph G,int v){// 返回数组下标值int i;for(i=0;i<MAX_VERTEX_NUM;++i) if(G.vertices[i].data==v) return i; return -1;}void CreateDN(ALGraph &G){// 采用邻接表存储表示, 构造有向图G(G.kind=DN) int i,j,k;ArcNode *p;int v1,v2; G.kind=DN; printf(" 输入顶点数:"); scanf("%d",&G.vexnum); printf(" 输入弧数:"); scanf("%d",&G.arcnum); printf(" 输入顶点:\n");for(i=0;i<G.vexnum;++i) {// 构造表头向量scanf("%d",&G.vertices[i].data);G.vertices[i].firstarc=NULL;// 初始化指针} for(k=0;k<G.arcnum;++k){ printf(" 第％d条弧:",k+1);scanf("%d",&v1); scanf("%d",&v2);// 输入一条弧的始点和终点i=LocateVex(G,v1);j=LocateVex(G,v2);〃确定v1 和v2 在G 中位置p=(ArcNode*)malloc(sizeof(ArcNode));// 假定有足够空间p->adjvex=j;p->nextarc=G.vertices[i].firstarc;G.vertices[i].firstarc=p; scanf("%d",&p->info);}//for }int Push(SqStack &S,int e){// 插入元素e 为新的栈顶元素if(S.top-S.base>=S.stacksize) {// 栈满，追加存储空间S.base=(int*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(int))Jif(!S.base)exit(OVERFLOW); // 存储分配失败S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*S.top++=e;return OK;}int InitStack(SqStack &S) // 栈的初始化{S.base=(int*)malloc(STACK_INIT_SIZE*sizeof(int));if(!S.base)exit(OVERFLOW); // 存储分配失败S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;}int Pop(SqStack &S,int &e) // 删除栈顶元素{//若栈不空，则删除S的栈顶元素，用e返回其值if(S.top==S.base)return ERROR;e=*--S.top;return OK;}int GetTop(SqStack S,int &e) // 取栈顶元素{//若栈不空，则用e返回S的栈顶元素if(S.top==S.base)return ERROR;e=*(S.top-1);return OK;}int StackEmpty(SqStack S) // 栈空{if(S.top==S.base)return TRUE;elsereturn FALSE;}int InitQueue(LinkQueue &Q) // 队列初始化{Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode)); if(!Q.front)exit(OVERFLOW); Q.front->next=NULL;return OK;int EnQueue(LinkQueue &Q,int e) // 插入{//插入元素e为Q的新的队尾元素QueuePtr p=(QueuePtr)malloc(sizeof(QNode)); if(!p)exit(OVERFLOW);p->data=e;p->next=NULL;Q.rear->next=p;Q.rear=p;return OK;}int DeQueue(LinkQueue &Q,int &e){//若队列不空，则删除Q的队头元素，用e返回其值if(Q.front==Q.rear) return ERROR;QueuePtr p=Q.front->next;e=p->data;Q.front->next=p->next; if(Q.rear==p)Q.rear=Q.front; free(p);return OK;}int QueueEmpty(LinkQueue Q) // 队列空{if(Q.front==Q.rear) return TRUE;elsereturn FALSE;}int FirstAdjVex(ALGraph G,int u){if(!G.vertices[u].firstarc)return -1;return LocateVex(G,G.vertices[u].firstarc->adjvex); }int NextAdjVex(ALGraph G,int u,int w){ArcNode *p=G.vertices[u].firstarc; while(p&&LocateVex(G,p->adjvex)!=w)p=p->nextarc;if(!p)return FirstAdjVex(G,u); p=p->nextarc;if(!p)return -1;return LocateVex(G,p->adjvex);}void Visit(ALGraph G,int v){ printf("%2d",G.vertices[v].data);}void DFSTraverse(ALGraph G){//按深度优先非递归遍历图G,使用辅助栈S和访问标志数组visited int v,w;SqStack S;for(v=0;v<G.vexnum;v++) visited[v]=FALSE;InitStack(S); for(v=0;v<G.vexnum;++v)if(!visited[v]){//v 尚未被访问visited[v]=TRUE;Visit(G,v);Push(S,v);//v 进栈while(!StackEmpty(S)){ for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w)){ if(!visited[w]){Visit(G,w); visited[w]=TRUE;Push(S,w);GetTop(S,v);}//if}//forPop(S,v);GetTop(S,v);}//while}//ifprintf("\n");}void BFSTraverse(ALGraph G){//按广度优先非递归遍历图G,使用辅助队列Q和访问标志数组visited int v,u,w;LinkQueue Q;for(v=0;v<G.vexnum;++v) visited[v]=FALSE;InitQueue(Q); for(v=0;v<G.vexnum;++v)if(!visited[v]){//v 尚未被访问visited[v]=TRUE;Visit(G,v);EnQueue(Q,v);//v 入队列while(!QueueEmpty(Q)){DeQueue(Q,u);// 队头元素出队并置为ufor(w=FirstAdjVex(G,u);w>=0;w=NextAdjVex(G,u,w)) if(!visited[w]){//w 为u 的尚未访问的邻接顶点visited[w]=TRUE;Visit(G,w);EnQueue(Q,w);}//if}//while}//ifprintf("\n");}void PrintDN(ALGraph G) // 图的显示{int i;ArcNode *p; printf(" 顶点:\n");for(i=0;i<G.vexnum;++i) printf("%2d",G.vertices[i].data);prin tf("\n 弧:\n");for(i=0;i<G.vexnum;++i){ p=G.vertices[i].firstarc;if(p){ while(p){prin tf("%d —%d(%d)\t",i,p->adjvex,p->i nfo);p=p->nextarc;}printf("\n");}//if}//for }void main(){ALGraph G;printf(" f************ 题目：图的遍历***************\n\n");CreateDN(G);PrintDN(G);printf(" 深度优先遍历:");DFSTraverse(G);printf("\n 广度优先遍历:");BFSTraverse(G);}【运行结果】实验五查找算法实现【实验学时】 5 学时【实验目的】熟练掌握顺序查找、折半查找及二叉排序树、平衡二叉树上的查找、插入和删除的方法，比较它们的平均查找长度。

数据结构实验报告专业：信科10-4姓名：纵兆丹学号：08103575一、实验目的1 熟练掌握顺序搜索、折半搜索和索引搜索等基本搜索算法，熟悉这些算法适合在何种存储结构下实现；2 熟练掌握二叉排序树的特性、建立方法以及动态搜索算法；3 熟练掌握散列表的特点及构造方法。

二、实验内容基本题1、实现基于有序顺序表的折半搜索。

2、设单链表的结点是按关键字的值从小到大排列的，试写出对此表的搜索程序并调试。

三、实验过程和方法1、程序代码基础题1#include <iostream.h>#include <conio.h>int Search_Bin(int *a,int key,int n){//在有序表a中折半查找其关键字等于key的数据数据元素，若找到，则函数值为//该元素在表中的位置，否则为0int low=1;int high=n;int mid;while(low<=high){mid = (low+high)/2;if(key==a[mid])return mid;else if(key<a[mid])high=mid-1;elselow=mid+1;}return 0;}//Search_Binvoid main(){int a[11];int x;for(int i=1;i<=10;i++){a[i]=i;}cout<<"请输入您想查找的元素值（请在1—10中选择）："<<endl;cin>>x;cout<<"您输入的元素的位置为："<<endl;cout<<Search_Bin(a,x,10)<<endl;getch();}基础题2#include <iostream>#include <conio.h>#include <list>using namespace std;void disp(list<int> List){list<int>::iterator a;for(a=List.begin(); a != List.end(); a++)cout<<*a<<" ";cout<<endl;}//dispint Search(list<int> List,int key){list<int>::iterator b;int i=1;for(b=List.begin(); b!= List.end(); b++){if(key==*b){return i;}i++;}return 0;}//Searchvoid main(){list<int> L;int m[100];int i=0;cout<<"请输入您要建立的链表的各个节点的关键字，以0为结束！"<<endl; do{cin>>m[i++];}while(m[i-1]!=0);for(int j=0;j<i-1;j++){L.push_back(m[j]);cout<<"插入成功！"<<endl;}L.sort();cout<<"单链表节点顺序为："<<endl;disp(L);int n,x;do{cout<<"1,查找；2，退出。

2009级数据结构实验报告实验名称：实验四——排序学生姓名：班级：班内序号：学号：日期：2010/12/171．实验要求实验目的：通过选择下面两个题目之一，学习、实现、对比各种排序算法，掌握各种排序算法的优劣，以及各种算法使用的情况。

实验内容：使用简单数组实现下面各种排序算法，并进行比较。

排序算法：1、插入排序2、希尔排序3、冒泡排序4、快速排序5、简单选择排序6、堆排序7、归并排序8、基数排序（选作）9、其他要求：1、测试数据分成三类：正序、逆序、随机数据2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为3次移动）。

3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒（选作）4、对2和3的结果进行分析，验证上述各种算法的时间复杂度编写测试main()函数测试线性表的正确性。

2. 程序分析2.1 存储结构使用最简单的一维数组存储待排序的数据。

共使用两个数组，一个用来存储原始数据，一个用来存储待排序数据。

每次排序完毕，用原始数据更新一次待排序数据，保证每一次都对同一组数据排序。

（图略）2.2 关键算法分析1.直接插入的改进：在一般的直接插入中，关键码每移动一次就需要比较一次。

在移动的方面，优化是比较困难的，因为对静态线性表的插入必然要带来大量的移动。

但是，我们可以在比较上进行一些优化。

在查找技术一张曾学过的“折半查找法”，在这里就可以照葫芦画瓢地运用。

一趟排序的伪代码如下：1.如果该元素大于处于其左侧相邻的元素则跳过该元素；2.low=0，high=i；3.循环直至low==high3.1 mid=(low+high)/2；3.2如果当前元素大于中值high=mid；3.3否则low=mid+1；4.当前元素赋值给临时变量；5.将有序区中处于low位置及其右侧的元素右移；6.临时变量置于low位置简单说一下这里的折半查找与一般查找算法的区别。

这里的查找，尤其是对无重复数据和大量数据的处理中，更多的时候是找不到完全相等的项的。

《数据结构》实验报告年级_2012级__ 学号_ 姓名 __ 成绩______专业_计算机科学与技术实验地点___指导教师__实验项目实验四串实验性质设计性实验日期：一、实验目的：1、掌握串的定义及其基本操作的实现。

2、掌握链表及其基本操作的实现。

3、通过上机实践进一步加深对串的顺序存储方式及链式存储方式的理解。

4、通过上机实践加强利用数据结构解决实际应用应用问题的能力。

二、实验内容与要求：1、实验题目一：顺序串的定义及其操作算法的实现要求：编程实现串的类型定义及串的初始化操作、插入操作、删除操作、取元素操作、输出操作等，并对其进行验证。

2、实验题目二：文本加密和解密要求：掌握每一种串操作的一般函数的实现及其应用。

三、实验问题描述一个文本串可用事先给定的字母映射表进行加密。

例如，设字母映射表为：abcdefghijklmnopqrstuvwxyzngzqtcobmuhelkpdawxfyivrsj则字符串“encrypt”被加密为“tkzwsdf”。

设计一个程序将输入的文本串进行加密后输出，然后进行解密输出。

四、实验步骤1．实验问题分析这里用到了c语言里的while 语句、for语句、if语句以及指针2．功能（函数）设计void Encrypt(char *pszSrc, char *pszEncrypt){char *p1;char *p2;int i=0;int j=0;p1=(char *)CharArray1;p2=(char *)CharArray2;cout<<"请输入要加密的字符串\n";fflush(stdin);cin.getline(pszSrc, 100);}五、实验结果（程序）及分析#include<iostream>using namespace std;const char CharArray1[26]={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};const char CharArray2[26]={'n','g','z','q','t','c','o','b','m','u','h','e','l','k','p','d','a','w','x','f','y','i','v','r','s','j'};void Encrypt(char*pszSrc,char*pszEncrypt){char*p1;char*p2;int i=0;int j=0;p1=(char*)CharArray1;p2=(char*)CharArray2;cout<<"请输入要加密的字符串\n";fflush(stdin);cin.getline(pszSrc,100);i=0;j=0;while(*(pszSrc+i)!='\0'){for(j=0;j<26;j++){if(*(pszSrc+i)==*(p1+j)){*(pszEncrypt+i)=*(p2+j);break;}else{;}}i++;}*(pszEncrypt+i)='\0';}void Decrypt(char*pszSrc,char*pszDecrypt) {char*p1;char*p2;int i=0;int j=0;p1=(char*)CharArray1;p2=(char*)CharArray2;cout<<"请输入一行已加密的字符串:\n"; fflush(stdin);cin.getline(pszSrc,100);i=0;j=0;while(*(pszSrc+i)!='\0'){for(j=0;j<26;j++){if(*(pszSrc+i)==*(p2+j)){*(pszDecrypt+i)=*(p1+j);break;}else{;}}i++;}*(pszDecrypt+i)='\0';}int main(){char*pszSrc;char*pszDest;int select;int i=0;int j=0;if((pszSrc=new char[100])==NULL){cout<<"申请内存空间失败,程序退出!\n";exit(1);}if((pszDest=new char[100])==NULL){cout<<"申请内存空间失败,程序退出!\n";exit(1);}while(1){cout<<"请选择加密或解密(1.加密2.解密0.退出):";cin>>select;if(1==select){Encrypt(pszSrc,pszDest);cout<<"加密后的字符串\n";i=0;while(*(pszDest+i)!='\0'){cout<<*(pszDest+i);i++;}cout<<endl;}else if(2==select){Decrypt(pszSrc,pszDest);cout<<"解密后的字符串\n";i=0;while(*(pszDest+i)!='\0'){cout<<*(pszDest+i);i++;}cout<<endl;}else if(0==select){break;}else{cout<<"你没有输入正确的选择,请重新选择:";}}delete[]pszSrc;delete[]pszDest;return0;}六、结论与分析在本次实验中掌握了串的各种操作，以及其实际作用，掌握串的定义及其基本操作的实现和掌握链表及其基本操作的实现。

数据结构实验报告第 6 次实验一、实验目的1．理解栈是操作受限（插入push, 删除pop）的线性表, 受限的是插入删除的位置。

2．在链式存储结构下实现：StackEmpty, Push,Pop, 几个基本操作。

3．通过调用基本操作实现括号匹配算法。

二、实验内容（问题）写一个算法, 识别依次读入的一个字符序列是否为形如‘序列1&序列2’模式的字符序列。

其中序列1和序列2中都不含字符‘&’, 且序列2是序列1的逆序列。

例如, ‘a+b&b+a’是属该模式的字符序列, 而’1+3&3-1’则不是。

测试数据: ’1+3&3-1’; ’a+b+c&c+b+a’; ’a+b+c&c+b’; ’b+c&c+b+a’;提示：利用栈 , 利用已实现的基本操作三、算法描述（给出自然语言描述的算法）1.向后依次扫描字符序列, 如果考察的字符不等于‘&’则入栈, 遇到‘&’则停止。

2.从‘&’后继续扫描, 考察字符的时候, 栈顶元素出栈, 若二者相等, 继续扫描；不等, 模式不成立。

3.扫描结束后, 栈空则模式成立四、详细设计（画流程图）五、程序代码#include<stdio.h>#include<stdlib.h>#define True 1#define False 0#define OK 1#define ERROR 0typedef int status;typedef char ElemType;typedef struct SNode{ElemType data;struct SNode *next;}SNode, *LinkStack;status InitStack(LinkStack &S);int StackEmpty(LinkStack S);status Push(LinkStack &S, ElemType e);status Pop(LinkStack &S, ElemType &e);status Is_Match(ElemType f[20]);main(){ElemType formula[20];int i;for(i=0;i<=3;i++){printf("\n请输入一个字符序列表达式: ");scanf("%s",formula);if(Is_Match(formula)==1) printf(" \n这个表达式符合‘序列1&序列2’模式！\n"); else printf("\n 这个表达式不符合‘序列1&序列2’模式！\n");}return(1);}status InitStack(LinkStack &S){S=NULL;return(OK);}int StackEmpty(LinkStack S){if(S==NULL) return(True);else return(False);}status Push(LinkStack &S, ElemType e){LinkStack p;p=(LinkStack)malloc(sizeof(SNode));if(!p) return(ERROR);p->data=e;p->next=S;S=p;return(OK);}status Pop(LinkStack &S, ElemType &e){LinkStack p;if(!S) return(ERROR);e=S->data;p=S;S=S->next;free(p);return(OK);}status Is_Match(ElemType f[20]){LinkStack St; ElemType *p,c;InitStack(St);p=f;for(;*p!='&';p++){ Push(St,*p);if(!Push(St, *p)) return(ERROR);}p++;for(;*p!='\0';p++){Pop(St,c);if(!Pop(St,c)) return(ERROR);else if(c!=*p) return(ERROR);}if(StackEmpty(St)) return(OK);else return(ERROR);}七、用户手册（教用户怎么用这个程序）用途: 判断字符串是否是“序列1&序列2’模式”用法：启动此程序, 屏幕会提示你输入数据, 输入数据并按下回车键即可。

一、实验目的本次实验旨在让学生掌握数据结构的基本概念、逻辑结构、存储结构以及各种基本操作，并通过实际编程操作，加深对数据结构理论知识的理解，提高编程能力和算法设计能力。

二、实验内容1. 线性表（1）顺序表1）初始化顺序表2）向顺序表插入元素3）从顺序表删除元素4）查找顺序表中的元素5）顺序表的逆序操作（2）链表1）创建链表2）在链表中插入元素3）在链表中删除元素4）查找链表中的元素5）链表的逆序操作2. 栈与队列（1）栈1）栈的初始化2）入栈操作3）出栈操作4）获取栈顶元素5）判断栈是否为空（2）队列1）队列的初始化2）入队操作3）出队操作4）获取队首元素5）判断队列是否为空3. 树与图（1）二叉树1）创建二叉树2）遍历二叉树（前序、中序、后序）3）求二叉树的深度4）求二叉树的宽度5）二叉树的镜像（2）图1）创建图2）图的深度优先遍历3）图的广度优先遍历4）最小生成树5）最短路径三、实验过程1. 线性表（1）顺序表1）初始化顺序表：创建一个长度为10的顺序表，初始化为空。

2）向顺序表插入元素：在顺序表的第i个位置插入元素x。

3）从顺序表删除元素：从顺序表中删除第i个位置的元素。

4）查找顺序表中的元素：在顺序表中查找元素x。

5）顺序表的逆序操作：将顺序表中的元素逆序排列。

（2）链表1）创建链表：创建一个带头结点的循环链表。

2）在链表中插入元素：在链表的第i个位置插入元素x。

3）在链表中删除元素：从链表中删除第i个位置的元素。

4）查找链表中的元素：在链表中查找元素x。

5）链表的逆序操作：将链表中的元素逆序排列。

2. 栈与队列（1）栈1）栈的初始化：创建一个栈，初始化为空。

2）入栈操作：将元素x压入栈中。

3）出栈操作：从栈中弹出元素。

4）获取栈顶元素：获取栈顶元素。

5）判断栈是否为空：判断栈是否为空。

（2）队列1）队列的初始化：创建一个队列，初始化为空。

2）入队操作：将元素x入队。

3）出队操作：从队列中出队元素。