1.实验目的
通过上机实验进一步掌握图的存储结构及基本操作的实现。
2.实验内容与要求
要求：
⑴能根据输入的顶点、边/弧的信息建立图；
⑵实现图中顶点、边/弧的插入、删除；
⑶实现对该图的深度优先遍历；
⑷实现对该图的广度优先遍历。
备注：单号基于邻接矩阵，双号基于邻接表存储结构实现上述操作。
3.数据结构设计
逻辑结构：图状结构
存储结构：顺序存储结构、链式存储结构
4.算法设计
#include
#include
#include
#define MAX_VERTEX_NUM 20
typedef struct ArcNode
{
int adjvex;
struct ArcNode *nextarc;
}ArcNode;
typedef struct VNode
{
char data[2]; //顶点就设置和书上V1等等一样吧
ArcNode *firstarc;
}VNode,AdjList[MAX_VERTEX_NUM]; typedef struct
{
AdjList vertices;
int vexnum,arcnum;
}ALGraph;
typedef struct
{
int data[MAX_VERTEX_NUM+10];
int front;
int rear;
}queue;
int visited[MAX_VERTEX_NUM];
queue q; int main()
{
ALGraph G;
int CreateUDG(ALGraph &G);
int DeleteUDG(ALGraph &G);
int InsertUDG(ALGraph &G);
void BFSTraverse(ALGraph G, int (*Visit)(ALGraph G,ArcNode v));
int PrintElement(ALGraph G,ArcNode v);
void menu();
void depthfirstsearch(ALGraph *g,int vi);
void travel(ALGraph *g);
void breadfirstsearch(ALGraph *g);
int i;
G.arcnum = G.vexnum = 0;
while(1)
{
menu();
do
{
printf ( "请输入要进行的操作\n" );
scanf ("%d",&i);
if (i<1||i>6)
printf("错误数字，请重新输入\n");
}while (i<1||i>6);
switch (i)
{
case 1: CreateUDG(G); system("pause"); system("cls"); break;
case 2: DeleteUDG(G); system("pause"); system("cls"); break;
case 3: InsertUDG(G); system("pause"); system("cls"); break;
case 4: travel(&G); system("pause"); system("cls"); break;
case 5: breadfirstsearch(&G); system("pause"); system("cls"); break;
case 6: exit(0); break;
}
}
return 1;
}
void enterqueue(int v)
{
q.data[q.rear]=v;
q.rear++;
}
int deletequeue()
{
int t;
t=q.data[q.front];
q.front++;
return(t);
}
int empty()
{
if(q.front==q.rear)
return 1;
return 0;
}
int LocateVex(ALGraph G,char node[2])
{
int i;
for(i = 0 ; i < G.vexnum ; i++)
{
if(strcmp(G.vertices[i].data,node)==0)
return i;
}
return -1;
}
int CreateUDG(ALGraph &G)
{
int LocateVex(ALGraph G,char node[2]);
void PrintUDG(ALGraph G);
int i,j,k;
char node1[2],node2[2];
ArcNode *p,*q;
printf("请输入顶点数和弧数\n");
printf("例如:5,6\n");
scanf("%d,%d",&G.vexnum,&G.arcnum) ;
printf("请输入各顶点\n");
for(i = 0 ; i < G.vexnum ; i++)
{
printf("第%d个\n",i+1);
scanf("%s",&G.vertices[i]);
G.vertices[i].firstarc = NULL;
}
//这里开始构造边
printf("请输入边的信息\n");
printf("例如:v1 v2\n");
for(i = 0 ; i < G.arcnum ; i++)
{
printf("第%d条边\n",i+1);
scanf("%s %s",&node1,&node2);
j = LocateVex(G,node1);
k = LocateVex(G,node2);
p = (ArcNode *)malloc(sizeof(ArcNode));
q = (ArcNode *)malloc(sizeof(ArcNode));
p->adjvex = k;
q->adjvex = j;
p->nextarc = G.vertices[j].firstarc;
G.vertices[j].firstarc = p;
q->nextarc = G.vertices[k].firstarc;
G.vertices[k].firstarc = q;
}
PrintUDG(G);
return 1;
}
int DeleteUDG(ALGraph &G)
{
int i,j;
ArcNode *p,*q;
char node[2];
int LocateVex(ALGraph G,char node[2]);
void PrintUDG(ALGraph G);
if(G.arcnum == 0)
{
printf("请先生成图\n");
return 0;
}
printf("请输入要删除的节点\n");
scanf("%s",&node);
i = LocateVex(G,node);
if(i == -1)
{
printf("无此节点\n");
return 0;
}
else
{
G.vexnum--;
if((p = q = G.vertices[i].firstarc) != NULL)
{
G.arcnum--;
p = p->nextarc;
G.vertices[i].firstarc = p;
free(q);
q = p;
while(p != NULL)
{
G.arcnum--;
p = p->nextarc;
G.vertices[i].firstarc = p;
free(q);
q = p;
}
}
for(j = 0 ; j < G.vexnum ; j++ )
{
if(j >= i)
{
strcpy(G.vertices[j].data , G.vertices[j+1].data);
G.vertices[j].firstarc = G.vertices[j+1].firstarc;
}
if(G.vertices[j].firstarc->nextarc != NULL)
{
p = G.vertices[j].firstarc;
q = p->nextarc;
if(p->adjvex == i)
{
G.vertices[j].firstarc = q;
p = q;
q = q->nextarc;
continue;
}
else if(p->adjvex > i)
p->adjvex--;
while(q != NULL)
{
if(q->adjvex == i)
{
p->nextarc = q->nextarc;
free(q);
q = p->nextarc;
}
else if(q->adjvex > i)
q->adjvex--;
else
{
p = p->nextarc;
q = q->nextarc;
}
}
}
else
if( (G.vertices[j].firstarc->nextarc == NULL) && (G.vertices[j].firstarc != NULL) )
if( G.vertices[j].firstarc->adjvex == i )
{
G.vertices[j].firstarc = NULL;
}
}
}
PrintUDG(G);
return 1;
}
int InsertUDG(ALGraph &G)
{
//默认一次插入一个节点吧,不然太麻烦
int i,j,k,l;
char node1[2],node2[2];
ArcNode *p,*q;
int LocateVex(ALGraph G,char node[2]);
void PrintUDG(ALGraph G);
if(G.arcnum == 0)
{
printf("请先生成图\n");
return 0;
}
printf("请输入插入节点的名称\n");
printf("WARNING:绝不可以和之前的节点重名!\n");
scanf("%s",&G.vertices[G.vexnum].data);
G.vertices[G.vexnum].firstarc = NULL;
printf("请输入需要插入的边的数目\n");
scanf("%d",&i);
G.arcnum += i;
G.vexnum++;
printf("请输入边的信息\n");
printf("例如:v6 v2\n");
printf("WARNING:一定要包含刚加入的节点名称!\n");
for(j = 0 ; j < i ; j++)
{
printf("第%d条边\n",j+1);
scanf("%s %s",&node1,&node2);
l = LocateVex(G,node1);
k = LocateVex(G,node2);
p = (ArcNode *)malloc(sizeof(ArcNode));
q = (ArcNode *)malloc(sizeof(ArcNode));
p->adjvex = k;
q->adjvex = l;
p->nextarc = G.vertices[l].firstarc;
G.vertices[l].firstarc = p;
q->nextarc = G.vertices[k].firstarc;
G.vertices[k].firstarc = q;
}
PrintUDG(G);
return 1;
}
void depthfirstsearch(ALGraph *g,int vi) {
ArcNode *rear;
printf("%s\t",g->vertices[vi].data);
visited[vi]=1;
rear=g->vertices[vi].firstarc;
while((rear!=NULL)&&(!visited[rear->adjvex ]))
{
depthfirstsearch(g,rear->adjvex);
rear=rear->nextarc;
}
}
void travel(ALGraph *g)
{
int v;
for(v=0;v
if(!visited[v])
depthfirstsearch(g,v);
}
void breadfirstsearch(ALGraph *g)
{
int v,t,i;
ArcNode *rear;
for(i = 0 ; i
visited[i] = 0;
for(v=0;v
{
if(!visited[v])
{
printf("%s",g->vertices[v].data);
visited[v]=1;
enterqueue(v);
}
while(!empty())
{
t=deletequeue();
rear=g->vertices[t].firstarc;
while((rear!=NULL)&&(!visited[rear->adjvex ]))
{
printf("%s\t",g->vertices[rear->adjvex].data);
visited[rear->adjvex]=1;
enterqueue(rear->adjvex);
rear=rear->nextarc;
}
}
}
}
void menu()
{
printf("******************************* **************\n");
printf("* 作者：Dick *\n");
printf("* 信计1001 xxxxxxxxxx *\n");
printf("*********************MENU**** ****************\n");
printf("1 建立无向图\n");
printf("2 删除图中节点\n");
printf("3 插入节点\n");
printf("4 深度优先遍历图\n");
printf("5 广度优先遍历图\n");
printf("6 退出程序\n");
}
void PrintUDG(ALGraph G)
{
int i;
ArcNode *p;
for(i = 0 ; i < G.vexnum ; i++)
{
if(G.vertices[i].firstarc != NULL)
{
printf("与节点%s相邻的节点为:\n",G.vertices[i].data);
p = G.vertices[i].firstarc;
while(p != NULL)
{
printf("%s\t",G.vertices[p->adjvex].data);
p = p->nextarc;
}
printf("\n");
}
else
printf("无与节点%s相邻的节点\n",G.vertices[i].data);
}
}
5.测试结果
图一：菜单项
图三：插入节点
图二：建立图图二：建立图
遍历图
遍历图
数据结构实验报告 一．题目要求 1）编程实现二叉排序树，包括生成、插入，删除； 2）对二叉排序树进行先根、中根、和后根非递归遍历； 3）每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。 4）分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率，并说明在什么情况下二叉排序树效率高,为什么? 二．解决方案 对于前三个题目要求，我们用一个程序实现代码如下 #include 青岛理工大学课程实验报告 s->top=s->base; s->stacksize=stack_init_size; return 1; } int Push(sqstack *s,int e) { if(s->top-s->base>=s->stacksize) { s->base=(int *)realloc(s->base,(s->stacksize+stackincrement)*sizeof(int)); if(!s->base) return 0; s->top=s->base+s->stacksize; s->stacksize+=stackincrement; } *(s->top++)=e; return e; } int Pop(sqstack *s,int e) { if(s->top==s->base) return 0; e=*--s->top; return e; } int stackempty(sqstack *s) { if(s->top==s->base) { return 1; } else Push(s,n%flag); n=n/flag; } while(!stackempty(s)) { e=Pop(s,e); switch(e) { case 10: printf("A"); break; case 11: printf("B"); break; case 12: printf("C"); break; case 13: printf("D"); break; case 14: printf("E"); break; case 15: printf("F"); break; default: printf("%d",e); } } printf("\n"); return 0; } int main() { sqstack s; StackInit(&s); conversion(&s); return 0; } 2007 C C C 语言的特点，简单的C 程序介绍，C 程序的上机步骤。1 、算法的概念2、简单的算法举例3、算法的特性4、算法的表示（自然语言、流程图、N-S 图表示） 1 、 C 的数据类型、常量与变星、整型数据、实型数据、字符型数据、字符串常量。2、 C 的运算符运算意义、优先级、结合方向。3、算术运算符和算术表达式，各类数值型数据间的混合运算。4、赋值运算符和赋值表达式。5、逗号运算符和逗号表达式。 1 、程序的三种基本结构。2、数据输入输出的概念及在C 语言中的实现。字符数据的输入输出，格式输入与输出。 1 、关系运算符及其优先级，关系运算和关系表达式。2、逻辑运算符及其优先级，逻辑运算符和逻辑表达式。3、if语句。if语句的三种形式，if语句的嵌套，条件运算符。4、switch 语句. 1 、while 语句。2、do/while 语句。3、for 语句。4、循环的嵌套。5、break 语句和continue 语句。1 、一维数组的定义和引用。2、二维数组的定义和引用。3、字符数组。4、字符串与字符数组。5、字符数组的输入输出。6、字符串处理函数1 、函数的定义。2、函数参数和函数的值，形式参数和实际参数。3、函数的返回值。4、函数调用的方式，函数的声明和函数原型。5、函数的嵌套调用。 6、函数的递归调用。 7、数组作为函数参数。 8、局部变量、全局变量的作用域。 9、变量的存储类别，自动变星，静态变量。1 、带参数的宏定义。2、“文件包含”处理。1 、地址和指针的概念。2、变量的指针和指向变量的指针变量。3、指针变量的定义 和引用。4、指针变量作为函数参数。5、数组的指针和指向数组的指针变量。6、指向数组元素的指针。7、通过指针引用数组元素。8、数组名作函数参数。9、二维数组与指针。 1 0、指向字符串的指针变星。字符串的指针表示形式，字符串指针作为函数参数。11 、字符指针变量和字符数组的异同。1 2、返回指针值的函数。1 3、指针数组。1 、定义结构体类型变星的方法。2、结构体变量的引用。3、结构体变量的初始化。4、结构体数组5、指向结构体类型数据的指针。6、共用体的概念，共用体变量的定义和引用，共用体类型数据的特点。typedef 1 、数据结构的逻辑结构、存储结构及数据运算的含义及其相互关系。2、数据结构的两大类逻辑结构和常用的存储表示方法。3、算法描述和算法分析的方法，对于一般算法能分析出时间复杂度。 1 、线性表的逻辑结构特征。2、线性表上定义的基本运算。3、顺序表的特点，即顺序表如何反映线性表中元素之间的逻辑关系。4、顺序表上的插入、删除操作及其平均时间性能分析。5、链表如何表示线性表中元素之间的逻辑关系。6、链表中头指针和头结点的使用。7、单链表上实现的建表、查找、插入和删除等基本算法，并分析其时间复杂度。8、顺序表和链表的主要优缺点。9、针对线性表上所需的主要操作，选择时空性能优越的存储结构。 1 、栈的逻辑结构特点．栈与线性表的异同。2、顺序栈和链栈实现的进栈、退栈等基本算法。3、栈的空和栈满的概念及其判定条件。4、队列的逻辑结构特点，队列与线性表的异同。5、顺序队列(主要是循 实验九串的基本操作 #include 一，实验题目 实验十一：图实验 采用邻接表存储有向图，设计算法判断任意两个顶点间手否存在路径。 二，问题分析 本程序要求采用邻接表存储有向图，设计算法判断任意两个顶点间手否存在路径，完成这些操作需要解决的关键问题是：用邻接表的形式存储有向图并输出该邻接表。用一个函数实现判断任意两点间是否存在路径。 1，数据的输入形式和输入值的范围：输入的图的结点均为整型。 2，结果的输出形式：输出的是两结点间是否存在路径的情况。 3，测试数据：输入的图的结点个数为：4 输入的图的边得个数为：3 边的信息为：1 2，2 3，3 1 三，概要设计 （1）为了实现上述程序的功能，需要： A，用邻接表的方式构建图 B，深度优先遍历该图的结点 C，判断任意两结点间是否存在路径 （2）本程序包含6个函数： a，主函数main（） b，用邻接表建立图函数create_adjlistgraph() c，深度优先搜索遍历函数dfs() d，初始化遍历数组并判断有无通路函数dfs_trave() e，输出邻接表函数print() f，释放邻接表结点空间函数freealgraph() 各函数间关系如右图所示： 四，详细设计 （1）邻接表中的结点类型定义： typedef struct arcnode{ int adjvex; arcnode *nextarc; }arcnode; （2）邻接表中头结点的类型定义： typedef struct{ char vexdata; arcnode *firstarc; }adjlist; （3）邻接表类型定义： typedef struct{ adjlist vextices[max]; int vexnum,arcnum; }algraph; （4）深度优先搜索遍历函数伪代码： int dfs(algraph *alg,int i,int n){ arcnode *p; visited[i]=1; p=alg->vextices[i].firstarc; while(p!=NULL) { if(visited[p->adjvex]==0){ if(p->adjvex==n) {flag=1; } dfs(alg,p->adjvex,n); if(flag==1) return 1; } p=p->nextarc; } return 0; } （5）初始化遍历数组并判断有无通路函数伪代码： void dfs_trave(algraph *alg,int x,int y){ int i; for(i=0;i<=alg->vexnum;i++) visited[i]=0; dfs(alg,x,y); } 五，源代码 #include "stdio.h" #include "stdlib.h" #include "malloc.h" #define max 100 typedef struct arcnode{ //定义邻接表中的结点类型 int adjvex; //定点信息 arcnode *nextarc; //指向下一个结点的指针nextarc }arcnode; typedef struct{ //定义邻接表中头结点的类型 char vexdata; //头结点的序号 arcnode *firstarc; //定义一个arcnode型指针指向头结点所对应的下一个结点}adjlist; typedef struct{ //定义邻接表类型 adjlist vextices[max]; //定义表头结点数组 遼穿紳範大學上机实验报告 学院:计算机与信息技术学院 专 业 ： 计算机科学与技术（师 范） 课程名称：数据结构 实验题目：顺序栈的基本操作 班级序号：师范1班 学号:201421012731 学生姓名：邓雪 指导教师：杨红颖 完成时间：2015年12月25号 一、实验目的： 1 ?熟悉掌握栈的定义、结构及性质； 2. 能够实现创建一个顺序栈，熟练实现入栈、出栈等栈的基本操作； 3?了解和掌握栈的应用。 二、实验环境： Microsoft Visual C++ 6.0 三、实验内容及要求： 栈是一种特殊的线性表，逻辑结构和线性表相同，只是其运算规则有更多的限制，故又称为受限的线性表。 建立顺序栈，实现如下功能： 1. 建立一个顺序栈 2. 输出栈 3. 进栈 4. 退栈 5. 取栈顶元素 6. 清空栈 7. 判断栈是否为空 进行栈的基本操作时要注意栈”后进先出”的特性。 四、概要设计： 1、通过循环，由键盘输入一串数据。创建并初始化一个顺序栈。 2、编写实现相关功能函数，完成子函数模块如下。 3、调用子函数，实现菜单调用功能，完成顺序表的相关操作 五、代码： #include 数据结构实验---图的储存与遍历 学号： 姓名： 实验日期： 2016.1.7 实验名称： 图的存贮与遍历 一、实验目的 掌握图这种复杂的非线性结构的邻接矩阵和邻接表的存储表示，以及在此两种常用存储方式下深度优先遍历(DFS)和广度优先遍历(BFS)操作的实现。 二、实验内容与实验步骤 题目1：对以邻接矩阵为存储结构的图进行DFS 和BFS 遍历 问题描述：以邻接矩阵为图的存储结构，实现图的DFS 和BFS 遍历。 基本要求：建立一个图的邻接矩阵表示，输出顶点的一种DFS 和BFS 序列。 测试数据：如图所示 题目2：对以邻接表为存储结构的图进行DFS 和BFS 遍历 问题描述：以邻接表为图的存储结构，实现图的DFS 和BFS 遍历。 基本要求：建立一个图的邻接表存贮，输出顶点的一种DFS 和BFS 序列。 测试数据：如图所示 V0 V1 V2 V3 V4 三、附录： 在此贴上调试好的程序。 #include #define M 100 typedef struct node { char vex[M][2]; int edge[M ][ M ]; int n,e; }Graph; int visited[M]; Graph *Create_Graph() { Graph *GA; int i,j,k,w; GA=(Graph*)malloc(sizeof(Graph)); printf ("请输入矩阵的顶点数和边数(用逗号隔开)：\n"); scanf("%d,%d",&GA->n,&GA->e); printf ("请输入矩阵顶点信息：\n"); for(i = 0;i 北京理工大学珠海学院实验报告 ZHUHAI CAMPAUS OF BEIJING INSTITUTE OF TECHNOLOGY 班级软件工程3班学号 150202102309姓名郭荣栋 指导教师余俊杰成绩 实验题目栈的实现与应用实验时间 一、实验目的、意义 （1）理解栈的特点，掌握栈的定义和基本操作。 （2）掌握进栈、出栈、清空栈运算的实现方法。 （3）熟练掌握顺序栈的操作及应用。 二、实验内容及要求 1.定义顺序栈，完成栈的基本操作：建空栈、入栈、出栈、取栈顶元素（参见教材45页）。 2. 调用栈的基本操作，将输入的十进制数转换成十六进制数。 3. 调用栈的基本操作，实现表达式求值，如输入3*（7-2）#，得到结果15。 三、实验结果及分析 （所输入的数据及相应的运行结果，运行结果要有提示信息，运行结果采用截图方式给出。） 四、程序清单(包含注释) 1、2. #include typedef int SElemType; typedef int Status; typedef struct{ SElemType *base; SElemType *top; int stacksize; }Sqstack; void StackTraverse(Sqstack S) { while (S.top != S.base) { cout << *(S.top-1) << endl; S.top--; } } Status InitStack(Sqstack &S){ S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!S.base){ exit(OVERFLOW); } 第四章串存储与基本操作的实现 本章学习要点 ◆熟悉串的相关概念以及串与线性表的关系 ◆重点掌握串的定长存储、堆分配存储的表示方法与基本操作的实现 ◆了解串的各种存储结构，能根据需要合理选用串的存储结构解决实际问题 “串”(string)，是字符串的简称，它是一种特殊的线性表，其特殊性在于组成线性表的数据元素是单个字符。字符串在计算机处理实际问题中使用非常广泛，比如人名、地名、商品名、设备名等均为字符串。同样在文字编辑、自然语言理解和翻译、源程序的编辑和修改等方面，都离不开对字符串的处理。 4.1串的基本概念 4.1.1串的概念 1．串的定义 串（string）是由n个字符组成的有限序列，记为：S=”a0a1a2…a n-1” (n≥0)。 其中，S是串的名字，字符序列a0a1a2…a n-1是串的值，a i(0≤i≤n-1)可以是字母、数字或其他字符元素；由于在C语言系统中数组元素的下标是从0开始的，所以串中所含元素的序号等于该元素的下标值加1；串中所含字符的个数n称为该串的长度，长度为0的字符串称为空串（null string）。 从串的定义可以看出，串实际上是数据元素为字符的特殊的线性表。 例如： （1）A=“X123” (长度为4的串) （2）B=“12345654321” (长度为11的串) （3）C=“Bei Jing” (长度为8的串) （4）D=“” (长度为0的空串) （5）E=“This is a string” (长度为16的串) （6）F=“ is a ” (长度为6的串) 2．子串、主串和位置 串中任意连续的字符组成的子序列称为该串的子串；相应地，包含子串的串称为主串。串中的字符在串序列中的序号称为该字符在该串中的位置；子串的第一个字符在主串中的位置称为子串在主串中的位置。显然，串为其自身的子串，并规定空串为任何串的子串。显然，在不考虑空子串的情况下，一个长度为n的字符串具有n(n+1)/2个子串。 例如： 在上例的(6)中串F就是(5)中串E的子串，且子串F在主串E中的位置是5。由于空格符也是一个字符，所以在串G=“abc defghne”中包含有子串“c def”,而串“cdef”不是串G的子串。串G中第一个字符…e?的位置是6，第二个字符…e?的位置是11。 3．串的比较 如果两个串的长度相等且对应位置上的字符相同，则称这两个串相等。两个串A、B的比较过程是：从前往后逐个比较对应位置上的字符的ASCII码值，直到不相等或有一个字符串结束为止，此时的情况有以下几种： （1）两个串同时结束，表示A等于B； （2）A中字符的ASCII码值大于B中相应位置上字符的ASCII码值或B串结束，表示A大于B；（3）B中字符的ASCII码值大于A中相应位置上字符的ASCII码值或A串结束，表示A小于B。 邻接矩阵的实现 1. 实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现2. 实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历3．设计与编码MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template int vertexNum, arcNum; }; #endif MGraph.cpp #include 第五次实验报告—— 顺序栈、链栈的插入和删除一需求分析 1、在演示程序中，出现的元素以数字出现定义为int型， 2、演示程序在计算机终端上，用户在键盘上输入演示程序中规定的运算命令，相应的输入数据和运算结果显示在终端上 3、顺序栈的程序执行的命令包括如下： （1）定义结构体 （2）顺序栈的初始化及创建 （3）元素的插入 （4）元素的删除 （5）顺序栈的打印结果 3、链栈的程序执行的命令包括如下： （1）定义结构体 （2）链栈的初始化及创建 （3）元素的插入 （4）元素的删除 （5）链栈的打印结果 二概要设计 1、顺序栈可能需要用到有序表的抽象数据类型定义： ADT List{ 数据对象:D={ai|ai∈ElemL, i=1,2,...,n, n≥0} 数据关系:R1={ Status Pop(SqStack &S) 操作结果：删除栈顶元素 }ADT List； 2、链栈可能需要用到有序表的抽象数据类型定义： ADT List{ 数据对象:D={ai|ai∈ElemL, i=1,2,...,n, n≥0} 数据关系:R1={ 宁波工程学院电信学院计算机教研室 实验报告 课程名称：___ 数据结构 ___ __ 实验项目：链串的基本算法 指导教师： 实验位置：电子楼二楼机房姓名： 学号： 班级：计科102 日期： 2011/10/13 一、实验目的 1）熟悉串的定义和串的基本操作。 2）掌握链串的基本运算。 3）加深对串数据结构的理解，逐步培养解决实际问题的编程能力。 二、实验环境 装有Visual C＋＋6.0的计算机。 三、实验内容 编写一个程序，实现链串的各种基本运算，并在此基础上设计一个主程序。具体如下： 编写栈的基本操作函数 链串类型定义如下所示： typedef struct snode{ char data; struct snode *next; }listring; （1）串赋值Assign(s,t) 将一个字符串常量赋给串s,即生成一个其值等于t的串s （2）串复制StrCopy(s,t) ?将串t赋给串s （3）计算串长度StrLength(s) ?返回串s中字符个数 （4）判断串相等StrEqual(s,t) ?若两个串s与t相等则返回1；否则返回0。 （5）串连接Concat(s,t) ?返回由两个串s和t连接在一起形成的新串。 （6）求子串SubStr(s,i,j) ?返回串s中从第i(1≤i≤StrLength(s))个字符开始的、由连续j 个字符组成的子串。 （7）插入InsStr (s,i,t) ?将串t插入到串s的第i(1≤i≤StrLength(s)+1)个字符中,即将t 的第一个字符作为s的第i个字符,并返回产生的新串（8）串删除DelStr (s,i,j) ?从串s中删去从第i(1≤i≤StrLength(s))个字符开始的长度为j 的子串,并返回产生的新串。 （9）串替换RepStr (s,s1,s2) ?在串s中,将所有出现的子串s1均替换成s2。 （10）输出串DispStr(s) ?输出串s的所有元素值 （11）判断串是否为空IsEmpty(s) 编写主函数 调用上述函数实现下列操作： （1）建立串s=“abcdefghijklmn”，串s1=“xyz”，串t＝“hijk” （2）复制串t到t1，并输出t1的长度 （3）在串s的第9个字符位置插入串s1而产生串s2，并输出s2 （4）删除s第2个字符开始的5个字符而产生串s3，并输出s3 （5）将串s第2个字符开始的3个字符替换成串s1而产生串s4，并输出s4 （6）提取串s的第8个字符开始的4个字符而产生串s5，并输出s5 （7）将串s1和串t连接起来而产生串s6，并输出s6 （8）比较串s1和s5是否相等，输出结果 程序清单： #include 实验1 (C语言补充实验) 有顺序表A和B,其元素值均按从小到大的升序排列，要求将它们合并成一 个顺序表C,且C的元素也是从小到大的升序排列。 #include 求A QB #include #include 一、实验目的 掌握图这种复杂的非线性结构的邻接矩阵和邻接表的存储表示，以及在此两种常用存储方式下深度优先遍历(DFS)和广度优先遍历(BFS)操作的实现。 二、实验内容与实验步骤 题目1：对以邻接矩阵为存储结构的图进行DFS 和BFS 遍历 问题描述：以邻接矩阵为图的存储结构，实现图的DFS 和BFS 遍历。 基本要求：建立一个图的邻接矩阵表示，输出顶点的一种DFS 和BFS 序列。 测试数据：如图所示 题目2：对以邻接表为存储结构的图进行DFS 和BFS 遍历 问题描述：以邻接表为图的存储结构，实现图的DFS 和BFS 遍历。 基本要求：建立一个图的邻接表存贮，输出顶点的一种DFS 和BFS 序列。 测试数据：如图所示 三、附录： 在此贴上调试好的程序。 #include #define M 100 typedef struct node { char vex[M][2]; int edge[M ][ M ]; int n,e; }Graph; int visited[M]; Graph *Create_Graph() { Graph *GA; int i,j,k,w; GA=(Graph*)malloc(sizeof(Graph)); printf ("请输入矩阵的顶点数和边数(用逗号隔开)：\n"); scanf("%d,%d",&GA->n,&GA->e); printf ("请输入矩阵顶点信息：\n"); for(i = 0;i 数据结构实验三 课程数据结构实验名称顺序栈基本操作第页 专业班级学号 姓名 实验日期：年月日评分 一、实验目的 1．熟悉并能实现栈的定义和基本操作。 2．了解和掌握栈的应用。 二、实验要求 1．进行栈的基本操作时要注意栈"后进先出"的特性。 2．编写完整程序完成下面的实验内容并上机运行。 3．整理并上交实验报告。 三、实验内容 1．编写程序任意输入栈长度和栈中的元素值，构造一个顺序栈，对其进行清空、销毁、入栈、出栈以及取栈顶元素操作。 2．编写程序实现表达式求值，即验证某算术表达式的正确性，若正确，则计算该算术表达式的值。 主要功能描述如下： （1）从键盘上输入表达式。 （2）分析该表达式是否合法： ?a) 是数字，则判断该数字的合法性。若合法，则压入数据到堆栈中。 ?b) 是规定的运算符，则根据规则进行处理。在处理过程中，将计算该表达式的值。 ?c) 若是其它字符，则返回错误信息。 （3）若上述处理过程中没有发现错误，则认为该表达式合法，并打印处理结果。 程序中应主要包含下面几个功能函数： ?l void initstack()：初始化堆栈 ?l int Make_str()：语法检查并计算 ?l int push_operate(int operate)：将操作码压入堆栈 ?l int push_num(double num)：将操作数压入堆栈 ?l int procede(int operate)：处理操作码 ?l int change_opnd(int operate)：将字符型操作码转换成优先级 ?l int push_opnd(int operate)：将操作码压入堆栈 ?l int pop_opnd()：将操作码弹出堆栈 ?l int caculate(int cur_opnd)：简单计算+，-，*，/ ?l double pop_num()：弹出操作数 四、实验步骤 （描述实验步骤及中间的结果或现象。在实验中做了什么事情，怎么做的，发生的现象和中间结果） 第一题： #include #include int OutputStack(Sqstack s) { while(s.stacksize!=0) { printf("%d ",*s.base); s.base++; s.stacksize--; } return 0; }//输出栈元素 void main() { Sqstack L; int i,j,k; IntSqstack(L); printf("输入你要的栈的大小\n"); scanf("%d",&j); for(k=01;k<=j;k++) { printf("请输入第%d个栈元素\n",k); scanf("%d",&i); Push(L,i); } OutputStack(L); printf("栈顶元素是%d",*--L.top); printf("输入你要删除的元素\n"); scanf("%d",&j); Pop(L,j); OutputStack(L); }数据结构实验二_栈的基本操作
数据结构的逻辑结构、存储结构及数据运算的含义及其相互关系
C语言数据结构串的基本操作
数据结构实验十一：图实验
顺序栈的基本操作讲解
数据结构实验---图的储存与遍历
数据结构栈的定义及基本操作介绍
数据结构《第4章 串存储与基本操作的实现》
数据结构实验报告图实验
数据结构栈的基本操作,进栈,出栈
数据结构实验报告3--链串
数据结构实验
数据结构——顺序栈的基本操作
数据结构实验 - 图的储存与遍历
(完整word版)顺序栈基本操作实验报告
数据结构栈的基本操作
相关主题
文本预览