搜档网
当前位置:搜档网 › 数据结构08图的基本操作

数据结构08图的基本操作

数据结构08图的基本操作
数据结构08图的基本操作

附录实验报告参考规范

《数据结构》实验报告

院系____________________ 专业____网络工程________________

姓名___林桢曦_________ 学号___106052010235_________ 电话____________

__________级__________班_______年____月____日

1.实验题目

图的基本操作

2.需求分析

编写图基本操作函数,建立图的邻接表,邻接矩阵。邻接表表示的图的递归深度优先遍历,邻接矩阵表示的图的递归深度优先遍历,邻接表表示的图的广度优先遍历,邻接矩阵表示的图的广度优先遍历。并调用上述函数实现相关操作。

3.概要设计

(1)为了实现上述程序功能,需要定义一个简化的线性表抽象数据类型:

ADT Graph{

数据对象V:V是具有相同特性的数据元素的集合,称为顶点集

数据关系R:R={VR}VR={|v,w∈V且P(v,w),表示从v到w的弧,

谓词P(v,w)定义了弧的意义或信息}

基本操作:

Create_Graph(LGraph lg,MGraph mg)

操作前提:lg是一个邻接表表示的图,mg是一个邻接矩阵表示的图

操作结果:建立图的邻接表,邻接矩阵

LDFS(LGraph g,int i)

操作前提:g是一个已初始化的邻接表表示的图

操作结果:对图g进行递归深度优先遍历

MDFS(MGraph g,int i,int vn)

操作前提:g是一个已初始化的邻接矩阵表示的图

操作结果:对图进行递归深度优先遍历

LBFS(LGraph g,int s,int n)

操作前提:g是一个已初始化的邻接表表示的图

操作结果:对图进行递归深度优先遍历

MBFS(MGraph g,int s,int n)

操作前提:g是一个已初始化的邻接矩阵表示的图

操作结果:对图进行递归深度优先遍历

}

(2)本程序包含6个函数:

?主函数main()

?建立图的邻接表,邻接矩阵函数Create_Graph()

?邻接表表示的图的递归深度优先遍历函数LDFS()

?邻接矩阵表示的图的递归深度优先遍历函数MDFS()

?邻接表表示的图的广度优先遍历LBFS()

?邻接矩阵表示的图的广度优先遍历MBFS()

各函数间调用关系如下:主函数调用其他函数

(3)主函数的伪码

main()

{

定义变量LGraph lg;

MGraph mg;

int n,i;

令n=Create_Graph(lg,mg);

For循环(i=0;i

visited[i]=0;

printf("\n邻接表表示的图的递归深度优先遍历\n");

调用LDFS(lg,0);

getch();

For循环(i=0;i

visited[i]=0;

printf("\n邻接矩阵表示的图的递归深度优先遍历\n");

调用MDFS(mg,0,n);

getch();

printf("\n邻接表表示的图的广度优先遍历\n");

调用LBFS(lg,0,n);

getch();

printf("\n邻接矩阵表示的图的广度优先遍历\n");

调用MBFS(mg,0,n); }

}

4.详细设计

(1)类型定义

typedef struct node {

int vno;

struct node *next;

}EdgeNode;

typedef EdgeNode *LGraph[MAX];

typedef int MGraph[MAX][MAX];

基本操作的伪码算法

1.建立图的邻接表,邻接矩阵

Create_Graph(LGraph lg,MGraph mg){

定义变量int vn,en,k,i,j;

EdgeNode *p;

While循环(1){

vn=en=0;

printf("输入图的顶点数[1-10]\n");

调用fflush(stdin);

scanf("%d",&vn);

如果(vn<1||vn>10)

continue;

printf("输入图的边数[0-%d]\n",vn*(vn-1)/2); scanf("%d",&en);

如果(en>=0&&en<=vn*(vn-1)/2)

break;

}

For循环(k=0;k

lg[k]=NULL;

For循环(k=0;k

For循环(i=0;i

mg[k][i]=0;

For循环(k=0;k

i=j=-1;

printf("输入一对相连的两条边[1-%d]的顶点:",vn); scanf("%d%d",&i,&j);

如果(i<1||j<1||i>vn||j>vn){

printf("输入错误,边范围为[1-%d]\n",vn);

继续;

}

k++;

i--;

j--;

p=(EdgeNode *)malloc(sizeof(EdgeNode));

p->vno=j;

p->next=lg[i];

lg[i]=p;

p=(EdgeNode *)malloc(sizeof(EdgeNode));

p->vno=i;

p->next=lg[j];

lg[j]=p;

mg[i][j]=mg[j][i]=1;

}

返回vn;}

2.递归深度优先遍历输出图的邻接表

LDFS(LGraph g,int i)

福建师范大学物光院计算机教学辅导讲义

定义变量EdgeNode *t;

printf("%4d",i+1);

visited[i]=1;

t=g[i];

While循环(t!=NULL){

如果(visited[t->vno]==0)

调用LDFS(g,t->vno);

t=t->next;

}

}

3.递归深度优先遍历输出图的邻接矩阵

MDFS(MGraph g,int i,int vn)

{

定义变量int j;

printf("%4d",i+1);

visited[i]=1;

For循环(j=0;j

如果(g[i][j]==1&&visited[j]==0)

调用MDFS(g,j,vn);

}

}

4.图的广度优先遍历输出图的邻接表

LBFS(LGraph g,int s,int n){

定义变量int i,v,w,head,tail;

EdgeNode *t;

For循环(i=0;i

visited[i]=0;

head=tail=0;

输出("%4d",s+1);

visited[s]=1;

queue[tail]=s;

While循环(head

v=queue[head++];

For循环(t=g[v];t!=NULL;t->next){

w=t->vno;

如果(visited[w]==0){

输出("%4d",w+1);

visited[w]=1;

queue[tail++]=w;

}

}

}

}

5.图的广度优先遍历输出图的邻接矩阵

MBFS(MGraph g,int s,int n){

定义变量int i,j,v,head,tail;

For循环(i=0;i

visited[i]=0;

head=tail=0;

输出("%4d",s+1);

visited[s]=1;

queue[tail++]=s;

While循环(head

v=queue[head++];

For循环(j=0;j

如果(g[v][j]==1&&visited[j]==0){

输出("%4d",j+1);

visited[j]=1;

queue[tail++]=j;

}

}

}

}

5.调试分析

调试中遇到分号在中文输入情况下输入,调试不通过,还有空指针问题。

(略)

6.使用说明

按要求输入图的顶点数,在输入图的边数,接着输入相连两条边的顶点,输入范围屏幕有显示,最后屏幕显示四种遍历结果。

7.测试结果

8. 参考文献

数据结构

9.附录

源程序文件如下:

#include "stdio.h"

#include "stdlib.h"

#include "conio.h"

#define MAX 10

typedef struct node {

int vno;

struct node *next;

}EdgeNode;

typedef EdgeNode *LGraph[MAX];

typedef int MGraph[MAX][MAX];

int visited[MAX];

int queue[MAX];

int Create_Graph(LGraph lg,MGraph mg)

{

int vn,en,k,i,j;

EdgeNode *p;

while(1){

vn=en=0;

printf("输入图的顶点数[1-10]\n");

fflush(stdin);

scanf("%d",&vn);

if(vn<1||vn>10)

continue;

printf("输入图的边数[0-%d]\n",vn*(vn-1)/2); scanf("%d",&en);

if(en>=0&&en<=vn*(vn-1)/2)

break;

}

for(k=0;k

lg[k]=NULL;

for(k=0;k

for(i=0;i

mg[k][i]=0;

for(k=0;k

i=j=-1;

printf("输入一对相连的两条边[1-%d]的顶点:",vn); scanf("%d%d",&i,&j);

if(i<1||j<1||i>vn||j>vn){

printf("输入错误,边范围为[1-%d]\n",vn); continue;

}

k++;

i--;

j--;

p=(EdgeNode *)malloc(sizeof(EdgeNode));

p->vno=j;

p->next=lg[i];

lg[i]=p;

p=(EdgeNode *)malloc(sizeof(EdgeNode));

p->vno=i;

p->next=lg[j];

lg[j]=p;

mg[i][j]=mg[j][i]=1;

}

return vn;

}

void LDFS(LGraph g,int i)

{

EdgeNode *t;

printf("%4d",i+1);

visited[i]=1;

t=g[i];

while(t!=NULL){

福建师范大学物光院计算机教学辅导讲义

if(visited[t->vno]==0)

LDFS(g,t->vno);

t=t->next;

}

}

void MDFS(MGraph g,int i,int vn)

{

int j;

printf("%4d",i+1);

visited[i]=1;

for(j=0;j

if(g[i][j]==1&&visited[j]==0)

MDFS(g,j,vn);

}

}

void LBFS(LGraph g,int s,int n)

{

int i,v,w,head,tail;

EdgeNode *t;

for(i=0;i

visited[i]=0;

head=tail=0;

printf("%4d",s+1);

visited[s]=1;

queue[tail]=s;

while(head

v=queue[head++];

for(t=g[v];t!=NULL;t->next){

w=t->vno;

if(visited[w]==0){

printf("%4d",w+1);

visited[w]=1;

queue[tail++]=w;

}

}

}

}

void MBFS(MGraph g,int s,int n)

{

int i,j,v,head,tail;

for(i=0;i

visited[i]=0;

head=tail=0;

printf("%4d",s+1);

visited[s]=1;

queue[tail++]=s;

while(head

v=queue[head++];

for(j=0;j

if(g[v][j]==1&&visited[j]==0){

printf("%4d",j+1);

visited[j]=1;

queue[tail++]=j;

}

}

}

}

void main()

{

LGraph lg;

MGraph mg;

int n,i;

n=Create_Graph(lg,mg);

for(i=0;i

visited[i]=0;

printf("\n邻接表表示的图的递归深度优先遍历\n");

LDFS(lg,0);

getch();

for(i=0;i

visited[i]=0;

printf("\n邻接矩阵表示的图的递归深度优先遍历\n");

MDFS(mg,0,n);

getch();

printf("\n邻接表表示的图的广度优先遍历\n");

LBFS(lg,0,n);

getch();

printf("\n邻接矩阵表示的图的广度优先遍历\n");

MBFS(mg,0,n);

}

注意事项:

●每位同学必须完成实验任务,并提交实验报告。杜绝抄袭和拷贝,一经发现该次实验雷同报告均以零分

计。

●请将实验报告以电子文档提交,“网络工程”专业请发送到fjsdwlgc@https://www.sodocs.net/doc/c815949245.html,信箱中,“电子信息”

专业请发送到fjsddzxx@https://www.sodocs.net/doc/c815949245.html, 信箱中,请附上程序清单.C源程序文件、和实验报告WORD文档两部分,以打包压缩文件形式提交,每次实验为一个文件夹的打包压缩文件,文件夹名统一为*⊙⊙⊙??.rar或*⊙⊙⊙??.zip,其中*为你的学号(全部号码),⊙⊙⊙为你中文姓名,??分别为01,02,03……11表示第几次实

验。

数据结构实验报告

数据结构实验报告 一.题目要求 1)编程实现二叉排序树,包括生成、插入,删除; 2)对二叉排序树进行先根、中根、和后根非递归遍历; 3)每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。 4)分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率,并说明在什么情况下二叉排序树效率高,为什么? 二.解决方案 对于前三个题目要求,我们用一个程序实现代码如下 #include #include #include #include "Stack.h"//栈的头文件,没有用上 typedefintElemType; //数据类型 typedefint Status; //返回值类型 //定义二叉树结构 typedefstructBiTNode{ ElemType data; //数据域 structBiTNode *lChild, *rChild;//左右子树域 }BiTNode, *BiTree; intInsertBST(BiTree&T,int key){//插入二叉树函数 if(T==NULL) { T = (BiTree)malloc(sizeof(BiTNode)); T->data=key; T->lChild=T->rChild=NULL; return 1; } else if(keydata){ InsertBST(T->lChild,key); } else if(key>T->data){ InsertBST(T->rChild,key); } else return 0; } BiTreeCreateBST(int a[],int n){//创建二叉树函数 BiTreebst=NULL; inti=0; while(i

数据结构与算法基础知识总结

数据结构与算法基础知识总结 1 算法 算法:是指解题方案的准确而完整的描述。 算法不等于程序,也不等计算机方法,程序的编制不可能优于算法的设计。 算法的基本特征:是一组严谨地定义运算顺序的规则,每一个规则都是有效的,是明确的,此顺序将在有限的次数下终止。特征包括: (1)可行性; (2)确定性,算法中每一步骤都必须有明确定义,不充许有模棱两可的解释,不允许有多义性; (3)有穷性,算法必须能在有限的时间内做完,即能在执行有限个步骤后终止,包括合理的执行时间的含义; (4)拥有足够的情报。 算法的基本要素:一是对数据对象的运算和操作;二是算法的控制结构。 指令系统:一个计算机系统能执行的所有指令的集合。 基本运算和操作包括:算术运算、逻辑运算、关系运算、数据传输。 算法的控制结构:顺序结构、选择结构、循环结构。 算法基本设计方法:列举法、归纳法、递推、递归、减斗递推技术、回溯法。 算法复杂度:算法时间复杂度和算法空间复杂度。 算法时间复杂度是指执行算法所需要的计算工作量。 算法空间复杂度是指执行这个算法所需要的内存空间。 2 数据结构的基本基本概念 数据结构研究的三个方面: (1)数据集合中各数据元素之间所固有的逻辑关系,即数据的逻辑结构; (2)在对数据进行处理时,各数据元素在计算机中的存储关系,即数据的存储结构;(3)对各种数据结构进行的运算。 数据结构是指相互有关联的数据元素的集合。 数据的逻辑结构包含: (1)表示数据元素的信息; (2)表示各数据元素之间的前后件关系。 数据的存储结构有顺序、链接、索引等。 线性结构条件:

(1)有且只有一个根结点; (2)每一个结点最多有一个前件,也最多有一个后件。 非线性结构:不满足线性结构条件的数据结构。 3 线性表及其顺序存储结构 线性表由一组数据元素构成,数据元素的位置只取决于自己的序号,元素之间的相对位置是线性的。 在复杂线性表中,由若干项数据元素组成的数据元素称为记录,而由多个记录构成的线性表又称为文件。 非空线性表的结构特征: (1)且只有一个根结点a1,它无前件; (2)有且只有一个终端结点an,它无后件; (3)除根结点与终端结点外,其他所有结点有且只有一个前件,也有且只有一个后件。结点个数n称为线性表的长度,当n=0时,称为空表。 线性表的顺序存储结构具有以下两个基本特点: (1)线性表中所有元素的所占的存储空间是连续的; (2)线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。 ai的存储地址为:adr(ai)=adr(a1)+(i-1)k,,adr(a1)为第一个元素的地址,k代表每个元素占的字节数。 顺序表的运算:插入、删除。(详见14--16页) 4 栈和队列 栈是限定在一端进行插入与删除的线性表,允许插入与删除的一端称为栈顶,不允许插入与删除的另一端称为栈底。 栈按照“先进后出”(filo)或“后进先出”(lifo)组织数据,栈具有记忆作用。用top表示栈顶位置,用bottom表示栈底。 栈的基本运算:(1)插入元素称为入栈运算;(2)删除元素称为退栈运算;(3)读栈顶元素是将栈顶元素赋给一个指定的变量,此时指针无变化。 队列是指允许在一端(队尾)进入插入,而在另一端(队头)进行删除的线性表。rear指针指向队尾,front指针指向队头。 队列是“先进行出”(fifo)或“后进后出”(lilo)的线性表。 队列运算包括(1)入队运算:从队尾插入一个元素;(2)退队运算:从队头删除一个元素。循环队列:s=0表示队列空,s=1且front=rear表示队列满

数据结构实验二_栈的基本操作

青岛理工大学课程实验报告

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; }

C语言数据结构串的基本操作

实验九串的基本操作 #include #include #include typedef char Status; int strlen(char *p) { int i=0; while(*p++)i++; return i; } typedef struct { char *ch; // 若是非空串,则按串长分配存储区,否则ch为NULL int length; // 串长度 }HString; // 初始化(产生空串)字符串T void InitString(HString *T) { (*T).length=0; (*T).ch=NULL; } // 生成一个其值等于串常量chars的串T Status StrAssign(HString *T, char *chars) { int i,j; if((*T).ch) free((*T).ch); // 释放T原有空间 i = strlen(chars); // 求chars 的长度i if(!i) { // chars的长度为0 (*T).ch = NULL; (*T).length = 0; } else { // chars的长度不为0 (*T).ch = (char*)malloc(i*sizeof(char)); // 分配串空间 if(!(*T).ch) // 分配串空间失败 exit(0); for(j = 0; j < i; j++) // 拷贝串 (*T).ch[j] = chars[j]; (*T).length = i; } return 1; } // 由串S复制得串T int StrCopy(HString *T,HString S) { int i; if((*T).ch) free((*T).ch); // 释放T原有空间 (*T).ch=(char*)malloc(S.lengt h*sizeof(char)); // 分配串空间if(!(*T).ch) // 分配串空间失 败 exit(0); for(i=0;i

数据结构实验十一:图实验

一,实验题目 实验十一:图实验 采用邻接表存储有向图,设计算法判断任意两个顶点间手否存在路径。 二,问题分析 本程序要求采用邻接表存储有向图,设计算法判断任意两个顶点间手否存在路径,完成这些操作需要解决的关键问题是:用邻接表的形式存储有向图并输出该邻接表。用一个函数实现判断任意两点间是否存在路径。 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.数据的基本单位是( B ) A.数据B.数据元素C.数据项D.数据结构 2.在数据结构中,构成数据元素的最小单位称为(D)A.字符B.关键字C.数据元素 D.数据项 3.数据在计算机内的存储形式称为数据的( D )A.算法描述B.数据类型 C.逻辑结构D.物理结构 4.数据的逻辑结构可分为(C) A.顺序结构和链式结构B.简单结构和复杂结构C.线性结构和非线性结构D.动态结构和静态结构5.顺序表中的每个元素占m个字节,第一个元素的存储地址为LOC(1),则任意1个元素i的地址为( B ) A.LOC(1)+i*m B.LOC(1)+(i-1)*m C.LCO(1)+(i+1)*m D.(i-1)*m 6.线性表若采用链表存储,其(D) A.所有结点的地址必须是连续的 B.部分结点的地址必须是连续的 C.所有结点的地址一定不连续 D.所有结点的地址连续、不连续都可以 7.线性表在采用链式存储时,其地址( C )A.必须是连续的B.一定是不连续的 C.连续不连续都可以D.部分是连续的

8.下列不属于线性结构的是( C )。 A.单链表B.队列 C.二叉树D.数组 9.链表不具有的特点是( A) A.可随机访问任一元素B.插入删除不需要移动元素 C.不必事先估计存储空间D.所需空间与线性表的长度成正比 10.数据结构反映了数据元素之间的结构关系,链表是一种( D)。 A.顺序存储线性表B.非顺序存储非线性表 C.顺序存储非线性表D.非顺序存储线性表 11.在单链表表示的线性表中,可以从( A )。 A.第一个结点访问到所有结点 B.某个结点访问到所有结点 C.某个结点访问到该结点的所有前趋结点 D.最后一个结点访问到所有结点 12.在一个单链表中,已知指针q所指向的结点是指针p所指向的结点的前驱结点,若在指针q和p所指向的两个结点之间插入指针s指向的结点,则执行( C )。 A.s->link=p->link; p->link=s; B.p->link=s->link; s->link=p; C.q->link=s; s->link=p; D.p->link=s; s->link=q; 13.长度为n的顺序存储的线性表,设在任何位置上删除一个元素的概率相等,则删除一个元素时平均要移动的元素

顺序栈的基本操作讲解

遼穿紳範大學上机实验报告 学院:计算机与信息技术学院 专 业 : 计算机科学与技术(师 范) 课程名称:数据结构 实验题目:顺序栈的基本操作 班级序号:师范1班 学号:201421012731 学生姓名:邓雪 指导教师:杨红颖 完成时间:2015年12月25号 一、实验目的: 1 ?熟悉掌握栈的定义、结构及性质; 2. 能够实现创建一个顺序栈,熟练实现入栈、出栈等栈的基本操作; 3?了解和掌握栈的应用。 二、实验环境: Microsoft Visual C++ 6.0

三、实验内容及要求: 栈是一种特殊的线性表,逻辑结构和线性表相同,只是其运算规则有更多的限制,故又称为受限的线性表。 建立顺序栈,实现如下功能: 1. 建立一个顺序栈 2. 输出栈 3. 进栈 4. 退栈 5. 取栈顶元素 6. 清空栈 7. 判断栈是否为空 进行栈的基本操作时要注意栈”后进先出”的特性。 四、概要设计: 1、通过循环,由键盘输入一串数据。创建并初始化一个顺序栈。 2、编写实现相关功能函数,完成子函数模块如下。 3、调用子函数,实现菜单调用功能,完成顺序表的相关操作

五、代码: #include #include #define maxsize 64 typedef int datatype; //定义结构体typedef struct { datatype data[maxsize]; int top; }seqstack; //建立顺序栈seqstack *SET(seqstack *s) { int i; s=(seqstack*)malloc(sizeof(seqstack)); s->top=-1; printf(" 请输入顺序栈元素(整型,以scanf("%d",&i); do{ s->top++; s->data[s->top]=i; scanf("%d",&i); 0 结束):"); }while(i!=0); printf(" 顺序栈建立成功\n"); return s; } //清空栈void SETNULL(seqstack *s) { s->top=-1;} //判断栈空 int EMPTY(seqstack *s) { if(s->top>=0) return 0; else return 1;} //进栈 seqstack *PUSH(seqstack *s) { int x; printf(" 你想要插入的数字:"); scanf("%d",&x); if(s->top==maxsize-1) { printf("overflow"); return NULL; } else {

数据结构实验---图的储存与遍历

数据结构实验---图的储存与遍历

学号: 姓名: 实验日期: 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 #include #include V0 V1 V4 V3 V2 ??? ? ??? ? ????????=010000000101010 1000100010A 1 0 1 0 3 3 4

#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;in;i++) scanf("%s",&(GA->vex[i][0]),&(GA->vex[i][1])); for (i = 0;in;i++) for (j = 0;jn;j++) GA->edge[i][j] = 0; for (k = 0;ke;k++) { printf ("请输入第%d条边的顶点位置(i,j)和权值(用逗号隔开):",k+1); scanf ("%d,%d,%d",&i,&j,&w); GA->edge[i][j] = w; } return(GA); } void dfs(Graph *GA, int v) { int i; printf("%c%c\n",GA->vex[v][0],GA->vex[v][1]); visited[v]=1;

数据结构栈的定义及基本操作介绍

北京理工大学珠海学院实验报告 ZHUHAI CAMPAUS OF BEIJING INSTITUTE OF TECHNOLOGY 班级软件工程3班学号 150202102309姓名郭荣栋 指导教师余俊杰成绩 实验题目栈的实现与应用实验时间 一、实验目的、意义 (1)理解栈的特点,掌握栈的定义和基本操作。 (2)掌握进栈、出栈、清空栈运算的实现方法。 (3)熟练掌握顺序栈的操作及应用。 二、实验内容及要求 1.定义顺序栈,完成栈的基本操作:建空栈、入栈、出栈、取栈顶元素(参见教材45页)。 2. 调用栈的基本操作,将输入的十进制数转换成十六进制数。 3. 调用栈的基本操作,实现表达式求值,如输入3*(7-2)#,得到结果15。 三、实验结果及分析 (所输入的数据及相应的运行结果,运行结果要有提示信息,运行结果采用截图方式给出。)

四、程序清单(包含注释) 1、2. #include #include #include using namespace std; #define OK 1 #define ERROR 0 #define OVERFLOW -2 #define MAXSIZE 100 #define INCREASEMENT 10 #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10

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); }

数据结构《第4章 串存储与基本操作的实现》

第四章串存储与基本操作的实现 本章学习要点 ◆熟悉串的相关概念以及串与线性表的关系 ◆重点掌握串的定长存储、堆分配存储的表示方法与基本操作的实现 ◆了解串的各种存储结构,能根据需要合理选用串的存储结构解决实际问题 “串”(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 class MGraph { public: MGraph(DataType a[], int n, int e); ~MGraph(){ void DFSTraverse(int v); void BFSTraverse(int v); private: DataType vertex[MaxSize]; int arc[MaxSize][MaxSize]; }

int vertexNum, arcNum; }; #endif MGraph.cpp #include using namespace std; #include "MGraph.h" extern int visited[MaxSize]; template MGraph::MGraph(DataType a[], int n, int e) { int i, j, k; vertexNum = n, arcNum = e; for(i = 0; i < vertexNum; i++) vertex[i] = a[i]; for(i = 0;i < vertexNum; i++) for(j = 0; j < vertexNum; j++) arc[i][j] = 0; for(k = 0; k < arcNum; k++) { cout << "Please enter two vertexs number of edge: " cin >> i >> j; arc[i][j] = 1; arc[j][i] = 1; } }

(完整版)非常实用的数据结构知识点总结

数据结构知识点概括 第一章概论 数据就是指能够被计算机识别、存储和加工处理的信息的载体。 数据元素是数据的基本单位,可以由若干个数据项组成。数据项是具有独立含义的最小标识单位。 数据结构的定义: ·逻辑结构:从逻辑结构上描述数据,独立于计算机。·线性结构:一对一关系。 ·线性结构:多对多关系。 ·存储结构:是逻辑结构用计算机语言的实现。·顺序存储结构:如数组。 ·链式存储结构:如链表。 ·索引存储结构:·稠密索引:每个结点都有索引项。 ·稀疏索引:每组结点都有索引项。 ·散列存储结构:如散列表。 ·数据运算。 ·对数据的操作。定义在逻辑结构上,每种逻辑结构都有一个运算集合。 ·常用的有:检索、插入、删除、更新、排序。 数据类型:是一个值的集合以及在这些值上定义的一组操作的总称。 ·结构类型:由用户借助于描述机制定义,是导出类型。 抽象数据类型ADT:·是抽象数据的组织和与之的操作。相当于在概念层上描述问题。 ·优点是将数据和操作封装在一起实现了信息隐藏。 程序设计的实质是对实际问题选择一种好的数据结构,设计一个好的算法。算法取决于数据结构。 算法是一个良定义的计算过程,以一个或多个值输入,并以一个或多个值输出。 评价算法的好坏的因素:·算法是正确的; ·执行算法的时间; ·执行算法的存储空间(主要是辅助存储空间); ·算法易于理解、编码、调试。 时间复杂度:是某个算法的时间耗费,它是该算法所求解问题规模n的函数。 渐近时间复杂度:是指当问题规模趋向无穷大时,该算法时间复杂度的数量级。 评价一个算法的时间性能时,主要标准就是算法的渐近时间复杂度。 算法中语句的频度不仅与问题规模有关,还与输入实例中各元素的取值相关。 时间复杂度按数量级递增排列依次为:常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O (n^2)、立方阶O(n^3)、……k次方阶O(n^k)、指数阶O(2^n)。

数据结构栈的基本操作,进栈,出栈

第五次实验报告—— 顺序栈、链栈的插入和删除一需求分析 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={|ai-1,ai ∈D, i=2,...,n } 基本操作: InitStack(SqStack &S) 操作结果:构造一个空栈 Push(L,e) 操作结果:插入元素e为新的栈顶元素

Status Pop(SqStack &S) 操作结果:删除栈顶元素 }ADT List; 2、链栈可能需要用到有序表的抽象数据类型定义: ADT List{ 数据对象:D={ai|ai∈ElemL, i=1,2,...,n, n≥0} 数据关系:R1={|ai-1,ai ∈D, i=2,...,n } 基本操作: LinkStack(SqStack &S) 操作结果:构造一个空栈 Status Push(L,e) 操作结果:插入元素e为新的栈顶元素 Status Pop(SqStack &S) 操作结果:删除栈顶元素 }ADT List; 3、顺序栈程序包含的主要模块: (1) 已给定的函数库: (2)顺序栈结构体: (3)顺序栈初始化及创建: (4)元素插入 (5)元素删除

数据结构实验报告3--链串

宁波工程学院电信学院计算机教研室 实验报告 课程名称:___ 数据结构 ___ __ 实验项目:链串的基本算法 指导教师: 实验位置:电子楼二楼机房姓名: 学号: 班级:计科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 main() { intn,m,i=0,j=0,k=0,a[5],b[5],c[10];/* 必须设个m做为数组的输入的计数器,不能用i ,不然进行到while 时i 直接为5*/ for(m=0;m<=4;m++)scanf("%d",&a[m]);// 输入数组a for(m=0;m<=4;m++)scanf("%d",&b[m]);// 输入数组b while(i<5&&j<5) {if(a[i]b[j]){c[k]=b[j];k++;j++;} else{c[k]=a[i];k++;i++;j++;}// 使输入的两组数组中相同的数只输出一 个 } if(i<5) for(n=i;n<5;n++) {c[k]=a[n];k++;} elseif(j<5) for(n=j;n<5;n++) {c[k]=b[n];k++;} for(i=0;i

求A QB #include main() { inti,j,k=0,a[5],b[5],c[5];//A=a[5],B=b[5],A n B=c[5] for(i=0;i<5;i++)scanf("%d",&a[i]);// 输入a 数组 for(i=0;i<5;i++)scanf("%d",&b[i]);〃输入b 数组 for(i=0;i<5;i++) {for(j=0;j<5;j++) if(a[i]==b[j]){c[k]=a[i];k++;}// 当有元素重复时,只取一个放入 c 中} for(i=0;i #defineN4 main() { inti,j,m,k,a[N+1];//k 为最后输出数组的长度变量

数据结构——顺序栈的基本操作

#include using namespace std; # define STACK_INIT_SIZE 100 # define STACKINCREMENT 10 typedef struct { int * base; int * top; int stacksize;//当前栈可使用的最大容量 } SqStack; void InitStack(SqStack &S)//构造一个空栈 { S.base=(int *)malloc(STACK_INIT_SIZE*sizeof(int)); if(!S.base) {cout<<"存储分配失败!!!"<=S.stacksize) { S.base=(int *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(int)); if(!S.base) cout<<"存储分配失败!!!"<

数据结构实现顺序表的各种基本运算(20210215233821)

实现顺序表的各种基本运算 一、实验目的 了解顺序表的结构特点及有关概念,掌握顺序表的各种基本操作算法思想及其实现。 二、实验内容 编写一个程序,实现顺序表的各种基本运算: 1、初始化顺序表; 2 、顺序表的插入; 3、顺序表的输出; 4 、求顺序表的长度 5 、判断顺序表是否为空; 6 、输出顺序表的第i位置的个元素; 7 、在顺序表中查找一个给定元素在表中的位置; 8、顺序表的删除; 9 、释放顺序表 三、算法思想与算法描述简图

主函数main

四、实验步骤与算法实现 #in clude #in clude #defi ne MaxSize 50 typedef char ElemType; typedef struct {ElemType data[MaxSize]; in t le ngth; void In itList(SqList*&L)〃 初始化顺序表 L {L=(SqList*)malloc(sizeof(SqList)); L->le ngth=0; for(i=0;ile ngth;i++) prin tf("%c ",L->data[i]); } void DestroyList(SqList*&L)〃 {free(L); } int ListEmpty(SqList*L)〃 {retur n( L->le ngth==O); } int Listle ngth(SqList*L)〃 {return(L->le ngth); } void DispList(SqList*L)〃 {int i; 释放顺序表 L

(完整word版)顺序栈基本操作实验报告

数据结构实验三 课程数据结构实验名称顺序栈基本操作第页 专业班级学号 姓名 实验日期:年月日评分 一、实验目的 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 using namespace std; #define STACK_INIT_SIZE 100 //存储空间初始分配量 #define STACKINCREMENT 10 //存储空间分配增量 #define OVERFLOW -1 #define OK 1 #define NO -1 #define NULL 0 typedef int Status; typedef char SElemType; typedef struct { SElemType *base; //在栈构造之前和销毁之后,base的值为NULL SElemType *top; //栈顶指针 int stacksize; //当前已分配的存储空间,以元素为单位 } SqStack; Status Initstack(SqStack &S)//构造一个空栈S { S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!S.base) exit(OVERFLOW); S.top=S.base; S.stacksize= STACK_INIT_SIZE; return OK; }//InitStack Status StackEmpty(SqStack &S) { if(S.base==S.top)

相关主题