数据结构实验报告
学号：1410122583 姓名：王佳斌 诚信声明签字：
实验一
实验题目：数据集合的表示及运算
实验目的：构造一个非递减数列，然后在该数列中新加入一个数，并保持该数列非递减有序性的特征。用一维数组存储数列。 实验中遇到的问题：
实验小结：
数据结构：
主要算法：
//插入法排序
void sort(int p[])
{
int m,l,key;
for(l=1;l<n;l++)
{
key=p[l];
m=l-1;
while(m>=0&&p[m]>key)
{
p[m+1]=p[m];
m=m-1;
}
p[m+1]=key;
}
}
//主函数
void main()
{
int i,j,a;
int *data;
data=(int*) malloc (DSIZE*sizeof(int));
//calloc也可以用来申请内存块
//与malloc不同的是，calloc函数会将申请到的内存区域初始化为0 //用法示例：ptr=(int)calloc(DSIZE,sizeof(int));
if(!data)//申请失败，程序终止
return;
} for(i=0;i<n;i++) *(data+i)=rand(); //调用随机函数产生数据 sort(data); for(i=0;i<n;i++) //循环输出非递减数列 { if(i==(n-1)) printf("%d\n",data[i]); else printf("%d,",data[i]); } printf("Please input a num:"); scanf("%d",&a); //从键盘输入一个要插入的数 i=0; while(i<n)//执行插入操作 { if(a<data[i]) { for(j=n;j>i;j--) { data[j]=data[j-1]; } data[i]=a; break; } else i++; } data[i]=a; printf("The new array is:\n"); for(i=0;i<n+1;i++) //循环输出插入数据后的新非递减序列 { if(i==(n)) printf("%d\n",data[i]); else printf("%d,",data[i]); }
第二篇：数据结构实验报告--图
数据结构实验报告
图
一、实验目的
1、熟悉图的结构和相关算法。
二、实验内容及要求
1、编写创建图的算法。
2、编写图的广度优先遍历、深度优先遍历、及求两点的简单路径和最短路径的算法。
三、算法描述
1、图的邻接表存储表示：
对图的每个顶点建立一个单链表，第i个单链表表示所有依附于第i个点的边（对于有向图表示以该顶点为尾的弧）；链表的每个节点存储两个信息，该弧指向的顶点在图中的位置（adjvex）和指向下一条弧的指针（nextarc）。每个连表的头结点存储顶点的数据：顶点信息（data）和指向依附于它的弧的链表域。
存储表示如下：
typedef struct ArcNode {
int adjvex; // 该弧所指向的顶点的位置
struct ArcNode *nextarc;
// 指向下一条弧的指针
// InfoType *info; // 该弧相关信息的指针
} ArcNode;
typedef struct VNode {
char data; // 顶点信息
int data2;
int sngle;
ArcNode *firstarc;
// 指向第一条依附该顶点的弧
} VNode, AdjList[MAX_NUM];
typedef struct {
AdjList vertices;
int vexnum, arcnum;
int kind; // 图的种类标志
} ALGraph;
2、深度优先搜索：
假设初始态是图中所有定点未被访问，从图中的某个顶点v开始，访问此顶点，然后依次从v的未访问的邻接点出发深度优先遍历，直至途中所有和v有相同路径的点都被访问到；若图中仍有点未被访问，则从图中另选一个未被访问的点作为起点重复上述过程，直到图中所有点都被访问到。为了便于区分途中定点是否被访问过，需要附设一个访问标致数组visited [0..n-1]，将其初值均设为false，一旦某个顶点被访问，将对应的访问标志赋值为true。
2、广度优先搜索：
假设初始态是图中所有顶点未被访问，从图中的某个顶点v开始依次访问v的各个未被访问的邻接点，然后分别从这些邻接点出发以此访问他们的邻接点，并使“先被访问的邻接顶点”先于“后被访问的邻接顶点”被访问，直至图中所有已被访问过的顶点的邻接顶点都被访问。若图中仍有未被访问的顶点，选择另一个未被访问的顶点开始，重复上述操作，直到图中所有顶点都被访问。为了使“先被访问的邻接顶点”先于“后被访问的邻接顶点”被访问，在次算法中加入一个队列，queue暂时存储被访问的顶点。
3、搜索简单路径：
利用深度优先搜索，以一个要搜索的起点v顶点为起始点，搜索到要找的终点s结束。为了方便记录路径，此算法中加入栈。访问第v个顶点时将v入栈，以v为顶点进行深度优先搜索，分别将其邻接点vi入栈，若找到s，将s入栈，若没有找到，将vi出栈；对vi+1深度优先搜索，直到找到s，或者图中所有顶点都被访问。
4、搜索最短路径：
搜索最短路径时，要记录被访问的顶点的上一个顶点在图中的位置，所以添加一个上一个顶点的标识single；访问v时将其标识置为-1；搜索从v到s的最短路径，从v开始进行广度优先搜索，直到找到s，将s以及它的之前的顶点依次入栈，直到将v入栈，然后将栈内元素输出。
四、程序代码：
#include<stdio.h>
#include<stdlib.h>
#include <conio.h>
#define MAX_NUM 20
bool visited[MAX_NUM];//访问标致数组
bool found;
int fomer=0;
char v1,v2;
int tfind;
typedef struct ArcNode {
int adjvex; // 该弧所指向的顶点的位置
struct ArcNode *nextarc;
// 指向下一条弧的指针
// InfoType *info; // 该弧相关信息的指针
} ArcNode;
typedef struct VNode {
char data; // 顶点信息
int data2;
int sngle;
ArcNode *firstarc;
// 指向第一条依附该顶点的弧
} VNode, AdjList[MAX_NUM];
typedef struct {
AdjList vertices;
int vexnum, arcnum;
int kind; // 图的种类标志
} ALGraph;
void DFS(ALGraph G,int v);
typedef struct qnode //队列类型
{
int data;
qnode *next;
}qnode,*queueptr;
typedef struct
{
queueptr front;
queueptr rear;
}linkqueue;
typedef struct stack//用栈存储路径
{
char *base;
char *top;
int stacksize;
int size;
}Stack;
Stack s;
int initstack(Stack &s)
{
s.base=(char*)malloc(40*sizeof(char));
s.top=s.base;
s.stacksize=40;
s.size=0;
return 1;
}
int push(Stack &s,char e)
{
*s.top++=e;
s.size++;
return 1;
}
int pop(Stack &s,char &e)
{
if(s.base==s.top)
e=*--s.top;
else {
e=*--s.top;
s.size--;
}
return 1;
}
void printstack(Stack s)
{
while(s.base!=s.top)
{
printf("%c ",*s.base);
s.base++;
}
printf("\n");
}
void printstack2(Stack s)
{
while(s.base!=s.top)
{
printf("%c ",*--s.top);
}
printf("\n");
}
int intitqueue(linkqueue &q)//初始化队列
{
q.front=q.rear=(queueptr)malloc(sizeof(qnode));
q.front->next=NULL;
return 1;
}
int emptyqueue(linkqueue q)//判断对了是否为空
{
if (q.front==q.rear)
return 1;
return 0;
}
int enqueue(linkqueue &q,int e)//元素入队
{
queueptr p;
p=(queueptr)malloc(sizeof(qnode));
if(!p) exit(0);
p->data=e; p->next=NULL;
q.rear->next=p;
q.rear=p;
return 1;
}
int dequeue(linkqueue &q,int &e)//元素出队
{
queueptr p;
if(q.front==q.rear) return 0;
p=q.front->next;
e=p->data;
q.front->next=p->next;
if(q.rear==p) q.rear=q.front;
free(p);
return 1;
}
int LocateVex(ALGraph &G,char v)
{
int i;
for(i=0;i<G.vexnum;i++)
if(G.vertices[i].data==v)
return i;
return -1;
}
int FirstAdjVex(ALGraph G,int v)
{
if(G.vertices[v].firstarc!=NULL)
return G.vertices[v].firstarc->adjvex;
return -1;
}
int NextAdjVex(ALGraph G,int v,int w)
{
while (G.vertices[v].firstarc->nextarc!=NULL)
{
if(G.vertices[v].firstarc->adjvex==w)
return G.vertices[v].firstarc->nextarc->adjvex;
else G.vertices[v].firstarc=G.vertices[v].firstarc->nextarc;
}
return -1;
}
void Create(ALGraph &G)
{
int i,j,k;
char v1,v2;
ArcNode *p,*q,*h;
q=NULL;
h=NULL;
printf("输入节点个数和弧的个数:\n");
scanf("%d%d",&G.vexnum,&G.arcnum);
for(i=0;i<G.vexnum;i++)
{
fflush(stdin);
printf("输入节点名称:\n");
scanf("%c",&G.vertices[i].data);
G.vertices[i].firstarc=NULL;
G.vertices[i].data2=i;
}
for(k=0;k<G.arcnum;k++)
{
printf("输入弧：a,b:\n");
fflush(stdin);
scanf("%c,%c",&v1,&v2);
i=LocateVex(G,v1);
j=LocateVex(G,v2);
p=(ArcNode*)malloc(sizeof(ArcNode));
p->adjvex=j;
p->nextarc=NULL;
if (G.vertices[i].firstarc==NULL)
G.vertices[i].firstarc=p;
else
{
q=G.vertices[i].firstarc;
while(q->nextarc!=NULL)
q=q->nextarc;
q->nextarc=p;
}
}
}
void DFSTraverse(ALGraph G)//深度遍历
{
int v;
for(v=0;v<G.vexnum;v++)
if(!visited[v]) DFS(G,v);
printf("\n");
}
void DFS(ALGraph G,int v)//深度遍历
{
int w;
visited[v]=true;
printf("%c ",G.vertices[v].data);
for(w=FirstAdjVex(G,v);(w>=0)&&(tfind==0);w=NextAdjVex(G,v,w))
{
if(!visited[w]) DFS(G,w);
}
}
void DFSTree(ALGraph G)//广度遍历
{
int w,u,v;
linkqueue q;
intitqueue(q);
for (v=0;v<G.vexnum;v++)
{
if (!visited[v])
{
visited[v]=true;
printf("%c ",G.vertices[v].data);
enqueue(q,v);
}
while (!emptyqueue(q))
{
dequeue(q,u);
for (w=FirstAdjVex(G,u);w>0;w=NextAdjVex(G,u,w))
if (!visited[w])
{
visited[w]=true;
printf("%c ",G.vertices[w].data);
if(w>0)
enqueue(q,w);
}
}
}
printf("\n");
}
void DFS2(ALGraph G,int v)//用深度遍历算法实现搜索简单路径
{
int w;
char e;
visited[v]=true;
push(s,G.vertices[v].data);
for(w=FirstAdjVex(G,v);(w>=0)&&(!found);w=NextAdjVex(G,v,w))
{
if(G.vertices[w].data==v2)
{
found=true;
push(s,G.vertices[w].data);
}
else if(!visited[w]) DFS2(G,w);
}
if(!found) pop(s,e);
}
void Simplepath(ALGraph G)//搜索简单路径
{
printf("输入要搜索路径的两点：\n");
fflush(stdin);
scanf("%c",&v1);
fflush(stdin);
scanf("%c",&v2);
DFS2(G,LocateVex(G,v1));
if (!found)
{
printf("can not found zhe path!\n");
}
else printstack(s);
}
void DFSTree2(ALGraph G,int v)//用广度优先求最短路径
{
int w,u;
linkqueue q;
intitqueue(q);
if (!visited[v])
{
visited[v]=true;
G.vertices[v].sngle=-1;
enqueue(q,v);
}
while (!emptyqueue(q))
{
dequeue(q,u);
for (w=FirstAdjVex(G,u);(w>0)&&(!found);w=NextAdjVex(G,u,w))
if (!visited[w])
{
visited[w]=true;
G.vertices[w].sngle=u;
if(w>0)
enqueue(q,w);
if(G.vertices[w].data==v2)
{
found=true;
while (G.vertices[w].sngle!=-1)
{
push(s,G.vertices[w].data);
w=G.vertices[w].sngle;
}
}
}
}
printf("\n");
}
void shortcut(ALGraph G)//搜索最短路径
{
printf("输入要搜索路径的两点：\n");
fflush(stdin);
scanf("%c",&v1);
fflush(stdin);
scanf("%c",&v2);
DFSTree2(G,LocateVex(G,v1));
push(s,v1);
printstack2(s);
printf("\n");
}
void main()
{
int v;
ALGraph G;
found=false;
initstack(s);
Create(G);
while(1)
{
for(v=0;v<G.vexnum;v++)
{
visited[v]=false;
G.vertices[v].sngle=-2;
}
tfind=0;
system("cls");
printf("---------------------\n");
printf("1、深度优先遍历\n");
printf("2、广度优先遍历\n");
printf("3、搜索简单路径\n");
printf("4、搜索最短路径\n");
printf("---------------------\n");
switch (getch())
{
case'1':DFSTraverse(G);break;
case'2': DFSTree(G);break;
case'3':Simplepath(G);break;
case'4':shortcut(G);break;
case'0':exit(0);
}
system("pause");
}
}
五、运行结果：
1、深度优先搜索：
2、广度优先搜索：
3、简单路径：
4、最短路径：
