数据结构(C语言版) 实验报告_数据结构实验c语言版

2020-02-28 其他范文下载本文

数据结构(C语言版) 实验报告由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“数据结构实验c语言版”。

数据结构(C语言版)实验报告

专业：计算机科学与技术、软件工程

学号:____201240703061___________________

班级:_________软件二班______________ 姓名:________朱海霞______________ 指导教师:___刘遵仁________________

青岛大学信息工程学院

2013年10月

实验1

实验题目：顺序存储结构线性表的插入和删除

实验目的：

了解和掌握线性表的逻辑结构和顺序存储结构，掌握线性表的基本算法及相关的时间性能分析。

实验要求：

建立一个数据域定义为整数类型的线性表，在表中允许有重复的数据；根据输入的数据，先找到相应的存储单元，后删除之。

实验主要步骤：

1、分析、理解给出的示例程序。

2、调试程序，并设计输入一组数据（3，-5，6，8，2，-5，4，7，-9），测试程序的如下功能：根据输入的数据，找到相应的存储单元并删除，显示表中所有的数据。

程序代码:

#include #include #define OK 1 #define ERROR 0 #define OVERFLOW-2 #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef struct{ int* elem;int length;int listsize;}Sqlist;int InitList_Sq(Sqlist &L){ L.elem=(int*)malloc(LIST_INIT_SIZE*sizeof(int));if(!L.elem)return-1;L.length=0;L.listsize=LIST_INIT_SIZE;return OK;} int ListInsert_Sq(Sqlist&L,int i,int e){ if(iL.length+1)return ERROR;if(L.length==L.listsize){

int *newbase;

newbase=(int*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(int));

if(!newbase)return-1;

L.elem=newbase;

L.listsize+=LISTINCREMENT;} int *p,*q;q=&(L.elem[i-1]);for(p=&(L.elem[L.length-1]);p>=q;--p)

*(p+1)=*p;*q=e;++L.length;return OK;} int ListDelete_Sq(Sqlist &L,int i,int e){ int *p,*q;if(iL.length)return ERROR;p=&(L.elem[i-1]);e=*p;q=L.elem+L.length-1;for(++p;p

*(p-1)=*p;--L.length;return OK;} int main(){ Sqlist L;InitList_Sq(L);//初始化

int i,a[]={3,-5,6,8,2,-5,4,7,-9};for(i=1;i

ListInsert_Sq(L,i,a[i-1]);for(i=0;i

printf(“ %d”,L.elem[i]);

printf(“n”);//插入9个数

ListInsert_Sq(L,3,24);for(i=0;i

printf(“ %d”,L.elem[i]);

printf(“n”);//插入一个数

int e;ListDelete_Sq(L,2, e);for(i=0;i

printf(“ %d”,L.elem[i]);//删除一个数

printf(“n”);

return 0;}

实验结果：

3，-5,6,8,2，-5,4,7，-9 3，-5,24,6,8,2，-5,4,7，-9 3,24,6,8,2，-5,4,7，-9

心得体会：

顺序存储结构是一种随机存取结构，存取任何元素的时间是一个常数，速度快；结构简单，逻辑上相邻的元素在物理上也相邻；不使用指针，节省存储空间；但是插入和删除元素需要移动大量元素，消耗大量时间；需要一个连续的存储空间；插入元素可能发生溢出；自由区中的存储空间不能被其他数据共享

实验2

实验题目：单链表的插入和删除

实验目的：

了解和掌握线性表的逻辑结构和链式存储结构，掌握单链表的基本算法及相关的时间性能分析。

实验要求：

建立一个数据域定义为字符类型的单链表，在链表中不允许有重复的字符；根据输入的字符，先找到相应的结点，后删除之。

实验主要步骤：

3、分析、理解给出的示例程序。

4、调试程序，并设计输入数据（如：A，C，E，F，H，J，Q，M），测试程序的如下功能：不允许重复字符的插入；根据输入的字符，找到相应的结点并删除。

5、修改程序：

（1）增加插入结点的功能。

（2）建立链表的方法有“前插”、“后插”法。

程序代码: #include #include #define NULL 0 #define OK 1 #define ERROR 0 typedef struct LNode{

int data;

struct LNode *next;}LNode,*LinkList;int InitList_L(LinkList &L){ L=(LinkList)malloc(sizeof(LNode));L->next=NULL;return OK;} int ListInsert_L(LinkList &L,int i,int e){ LinkList p,s;int j;p=L;j=0;while(p&&j

p=p->next;++j;} if(!p||j>i-1)

return ERROR;s=(LinkList)malloc(sizeof(LNode));s->data=e;s->next=p->next;p->next=s;return OK;} int ListDelete_L(LinkList&L,int i,int &e){ LinkList p,q;int j;p=L;j=0;while(p->next&&j

p=p->next;++j;} if(!(p->next)||j

return ERROR;q=p->next;p->next=q->next;e=q->data;free(q);return OK;} int main(){ LinkList L,p;char a[8]={'A','C','E','F','H','J','Q','U'};int i,j;InitList_L(L);for(i=1,j=0;i

ListInsert_L(L,i,a[j]);p=L->next;while(p!=NULL){

printf(“%ct”,p->data);

p=p->next;

}

}//插入八个字符 printf(“n”);i=2;int e;ListInsert_L(L,i,'B');p=L->next;while(p!=NULL){ printf(“%ct”,p->data);p=p->next;}//插入一个字符 printf(“n”);i=3;ListDelete_L(L,i,e);p=L->next;while(p!=NULL){ printf(“%ct”,p->data);p=p->next;} printf(“n”);return 0;实验结果：

A C E F H J Q U A B C E F H J Q U A B E F H J Q U

心得体会：

单链表是通过扫描指针P进行单链表的操作；头指针唯一标识点链表的存在；插入和删除元素快捷，方便。

实验3

实验题目：栈操作设计和实现

实验目的：

1、掌握栈的顺序存储结构和链式存储结构，以便在实际中灵活应用。

2、掌握栈的特点，即后进先出和先进先出的原则。

3、掌握栈的基本运算，如：入栈与出栈等运算在顺序存储结构和链式存储结构上的实现。

实验要求：

回文判断：对于一个从键盘输入的字符串，判断其是否为回文。回文即正反序相同。如“abba”是回文，而“abab”不是回文。

实验主要步骤

（1）数据从键盘读入；（2）输出要判断的字符串；

（3）利用栈的基本操作对给定的字符串判断其是否是回文，若是则输出“Yes”，否则输出“No”。

程序代码: #include #include #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define OVERFLOW-2 #define N 100 #define STACK_INIT_SIZE 100

#define STACKINCREMENT 10

typedef struct{

int *base;

// 在栈构造之前和销毁之后，base的值为NULL

int *top;

// 栈顶指针

int

stacksize;

// 当前已分配的存储空间，以元素为单位

} SqStack;

int InitStack(SqStack &S){ // 构造一个空栈S

if(!(S.base=(int *)malloc(STACK_INIT_SIZE*sizeof(int))))

exit(OVERFLOW);

// 存储分配失败

S.top=S.base;

S.stacksize=STACK_INIT_SIZE;

return OK;

}

int StackEmpty(SqStack S){ // 若栈S为空栈，则返回TRUE，否则返回FALSE

if(S.top==S.base)

return TRUE;

else

return FALSE;}

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

if(!S.base)

exit(OVERFLOW);// 存储分配失败

S.top=S.base+S.stacksize;

S.stacksize+=STACKINCREMENT;

}

*(S.top)++=e;

return OK;}

int Pop(SqStack &S,int &e){ // 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR

if(S.top==S.base)

return ERROR;

e=*--S.top;

return OK;} int main(){

SqStack s;

int i,e,j,k=1;

char ch[N] = {0},*p,b[N] = {0};

if(InitStack(s))// 初始化栈成功

{

printf(“请输入表达式:n”);

gets(ch);

p=ch;

while(*p)// 没到串尾

Push(s,*p++);

for(i=0;i

if(!StackEmpty(s)){// 栈不空

Pop(s,e);// 弹出栈顶元素

b[i]=e;

}

for(i=0;i

if(ch[i]!=b[i])

k=0;}

if(k==0)

printf(“NO!”);

else

printf(“输出:”)printf(“YES!”);

}

return 0;

}

实验结果：

请输入表达式： abcba 输出：YES!心得体会：栈是仅能在表尾惊醒插入和删除操作的线性表，具有先进后出的性质，这个固有性质使栈成为程序设计中的有用工具。

实验4

实验题目：二叉树操作设计和实现

实验目的：

掌握二叉树的定义、性质及存储方式，各种遍历算法。

实验要求：

采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序以及按层次遍历的操作，求所有叶子及结点总数的操作。

实验主要步骤：

1、分析、理解程序。

2、调试程序，设计一棵二叉树，输入完全二叉树的先序序列，用#代表虚结点（空指针），如ABD###CE##F##，建立二叉树，求出先序、中序和后序以及按层次遍历序列，求所有叶子及结点总数。

程序代码:

实验结果：

心得体会：

实验5

实验题目：图的遍历操作

实验目的：

掌握有向图和无向图的概念；掌握邻接矩阵和邻接链表建立图的存储结构；掌握DFS及BFS对图的遍历操作；了解图结构在人工智能、工程等领域的广泛应用。

实验要求：

采用邻接矩阵和邻接链表作为图的存储结构，完成有向图和无向图的DFS和BFS操作。

实验主要步骤：

设计一个有向图和一个无向图，任选一种存储结构，完成有向图和无向图的DFS（深度优先遍历）和BFS（广度优先遍历）的操作。

1．邻接矩阵作为存储结构 #include“stdio.h” #include“stdlib.h” #define MaxVertexNum 100

//定义最大顶点数 typedef struct{

char vexs[MaxVertexNum];

//顶点表

int edges[MaxVertexNum][MaxVertexNum];

//邻接矩阵，可看作边表

int n,e;

//图中的顶点数n和边数e }MGraph;

//用邻接矩阵表示的图的类型 //=========建立邻接矩阵======= void CreatMGraph(MGraph *G){

int i,j,k;

char a;

printf(“Input VertexNum(n)and EdgesNum(e): ”);

scanf(“%d,%d”,&G->n,&G->e);

//输入顶点数和边数

scanf(“%c”,&a);

printf(“Input Vertex string:”);

for(i=0;in;i++)

{

scanf(“%c”,&a);

G->vexs[i]=a;

//读入顶点信息，建立顶点表

}

for(i=0;in;i++)

for(j=0;jn;j++)

G->edges[i][j]=0;

//初始化邻接矩阵

printf(“Input edges,Creat Adjacency Matrixn”);

for(k=0;ke;k++){

//读入e条边，建立邻接矩阵

scanf(“%d%d”,&i,&j);

//输入边（Vi，Vj）的顶点序号

G->edges[i][j]=1;

G->edges[j][i]=1;//若为无向图，矩阵为对称矩阵；若建立有向图，去掉该条语句

} } //=========定义标志向量，为全局变量======= typedef enum{FALSE,TRUE} Boolean;Boolean visited[MaxVertexNum];//========DFS：深度优先遍历的递归算法====== void DFSM(MGraph *G,int i){ //以Vi为出发点对邻接矩阵表示的图G进行DFS搜索，邻接矩阵是0，1矩阵

给出你的编码

//===========BFS：广度优先遍历======= void BFS(MGraph *G,int k){ //以Vk为源点对用邻接矩阵表示的图G进行广度优先搜索

给出你的编码

//==========主程序main ===== void main(){

int i;

MGraph *G;

G=(MGraph *)malloc(sizeof(MGraph));

//为图G申请内存空间

CreatMGraph(G);

//建立邻接矩阵

printf(“Print Graph DFS: ”);

DFS(G);

//深度优先遍历

printf(“n”);

printf(“Print Graph BFS: ”);

BFS(G,3);

//以序号为3的顶点开始广度优先遍历

printf(“n”);}

2．邻接链表作为存储结构 #include“stdio.h” #include“stdlib.h” #define MaxVertexNum 50

//定义最大顶点数 typedef struct node{

//边表结点

int adjvex;

//邻接点域

struct node *next;

//链域 }EdgeNode;typedef struct vnode{

//顶点表结点

char vertex;

//顶点域

EdgeNode *firstedge;

//边表头指针 }VertexNode;typedef VertexNode AdjList[MaxVertexNum];

//AdjList是邻接表类型 typedef struct {

AdjList adjlist;

//邻接表

int n,e;

//图中当前顶点数和边数 } ALGraph;

//图类型 //=========建立图的邻接表======= void CreatALGraph(ALGraph *G){

int i,j,k;

char a;

EdgeNode *s;

//定义边表结点

printf(“Input VertexNum(n)and EdgesNum(e): ”);

scanf(“%d,%d”,&G->n,&G->e);

//读入顶点数和边数

scanf(“%c”,&a);

printf(“Input Vertex string:”);

for(i=0;in;i++)

//建立边表

{ scanf(“%c”,&a);G->adjlist[i].vertex=a;

//读入顶点信息

G->adjlist[i].firstedge=NULL;//边表置为空表

}

printf(“Input edges,Creat Adjacency Listn”);

for(k=0;ke;k++){

//建立边表

scanf(“%d%d”,&i,&j);

//读入边（Vi，Vj）的顶点对序号

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

//生成边表结点

s->adjvex=j;

//邻接点序号为j s->next=G->adjlist[i].firstedge;G->adjlist[i].firstedge=s;

//将新结点*S插入顶点Vi的边表头部

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

s->adjvex=i;

//邻接点序号为i s->next=G->adjlist[j].firstedge;

G->adjlist[j].firstedge=s;

//将新结点*S插入顶点Vj的边表头部

} } //=========定义标志向量，为全局变量======= typedef enum{FALSE,TRUE} Boolean;Boolean visited[MaxVertexNum];//========DFS：深度优先遍历的递归算法====== void DFSM(ALGraph *G,int i){ //以Vi为出发点对邻接链表表示的图G进行DFS搜索给出你的编码

//==========BFS：广度优先遍历========= void BFS(ALGraph *G,int k){ //以Vk为源点对用邻接链表表示的图G进行广度优先搜索

给出你的编码

//==========主函数=========== void main(){

int i;

ALGraph *G;

G=(ALGraph *)malloc(sizeof(ALGraph));

CreatALGraph(G);

printf(“Print Graph DFS: ”);

DFS(G);

printf(“n”);

printf(“Print Graph BFS: ”);

BFS(G,3);