c数据结构实验报告_数据结构实验报告
c数据结构实验报告由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“数据结构实验报告”。
c数据结构实验报告
数据结构(C语言版)实验报告;专业：计算机科学与技术、软件工程;学号:____XX40703061_____;班级:_________软件二班________;姓名:________朱海霞__________;指导教师:___刘遵仁_____________;青岛大学信息工程学院;XX年10月;实验1;实验题目：顺序存储结构线性表的插入和删除;实验目
数据结构(C语言版)实验报告
专业：计算机科学与技术、软件工程
学号:____XX40703061___________________
班级:_________软件二班______________
姓名:________朱海霞______________
指导教师:___刘遵仁________________
青岛大学信息工程学院
XX年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){
=(int*)malloc(LIST_INIT_SIZE*sizeof(int));
if(!)return-1;
=0;
=LIST_INIT_SIZE;
return OK;
}
int ListInsert_Sq(Sqlist&L,int i,int e){
if(i+1)return ERROR;
if(==){
int *newbase;
newbase=(int*)realloc(,(+LISTINCREMENT)*sizeof(int));
if(!newbase)return-1;
=newbase;
+=LISTINCREMENT;
}
int *p,*q;
q=&();
for(p=&();p>=q;--p)
*(p+1)=*p;
*q=e;
++;
return OK;
}
int ListDelete_Sq(Sqlist &L,int i,int e){
int *p,*q;
if(i)return ERROR;
p=&();
e=*p;
q=+;
for(++p;p *(p-1)=*p;
--;
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);
for(i=0;i printf(“ %d”,);
printf(“ ”);//插入9个数
ListInsert_Sq(L,3,24);
for(i=0;i printf(“ %d”,);
printf(“ ”);//插入一个数
int e;
ListDelete_Sq(L,2, e);
for(i=0;i printf(“ %d”,);//删除一个数
printf(“ ”);
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={'A','C','E','F','H','J','Q','U'};int i,j;
InitList_L(L);
for(i=1,j=0;i p=L->next;
while(p!=NULL){
printf(“%c ”,p->data);p=p->next;}//插入八个字符
printf(“;实验结果：;ACEFHJQU;ABCEFHJQU;ABEFHJQU;心得体会：;单链表是通过扫描指针P进行单链表的操作;头指针唯;实验3;实验题目：栈操作设计和实现;实验目的：;
1、掌握栈的顺序存储结构和链式存储结构，以便在实;
2、掌握栈的特点，即后进先出和先进先出的原则;
3、掌握栈的基本运算，如：入栈与出栈
}
}//插入八个字符 printf(” “);i=2;int e;ListInsert_L(L,i,'B');
p=L->next;while(p!=NULL){ printf(”%c “,p->data);p=p->next;}//插入一个字符 printf(” “);i=3;ListDelete_L(L,i,e);p=L->next;while(p!=NULL){ printf(”%c “,p->data);p=p->next;} printf(” “);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(!(=(int *)malloc(STACK_INIT_SIZE*sizeof(int))))
exit(OVERFLOW);// 存储分配失败
=;
=STACK_INIT_SIZE;
return OK;
}
int StackEmpty(SqStack S)
{ // 若栈S为空栈，则返回TRUE，否则返回FALSE
if(==)
return TRUE;
else
return FALSE;
}
int Push(SqStack &S, int e)
{ // 插入元素e为新的栈顶元素
if(>=)// 栈满，追加存储空间
{
=(int *)realloc(,(+STACKINCREMENT)*sizeof(int));if(!)
exit(OVERFLOW);// 存储分配失败
=+;
+=STACKINCREMENT;
}
*()++=e;
return OK;
}
int Pop(SqStack &S,int &e)
{ // 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK;否则返回ERROR if(==)
return ERROR;
e=*--;
return OK;
}
int main(){
SqStack s;
int i,e,j,k=1;
char ch = {0},*p,b = {0};
if(InitStack(s))// 初始化栈成功
{
printf(”请输入表达式: “);
gets(ch);
p=ch;
while(*p)// 没到串尾
Push(s,*p++);
for(i=0;i
if(!StackEmpty(s)){// 栈不空
Pop(s,e);// 弹出栈顶元素
b=e;
}
}
for(i=0;i
if(ch!=b)
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”“
#include”“
#define MaxVertexNum 100 //定义最大顶点数
typedef struct{
char vexs;//顶点表
int edges;//邻接矩阵，可看作边表 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=a;//读入顶点信息，建立顶点表
}
for(i=0;in;i++)
for(j=0;jn;j++)
G->edges=0;//初始化邻接矩阵
printf(”Input edges,Creat Adjacency Matrix “);
for(k=0;ke;k++){ //读入e条边，建立邻接矩阵
scanf(”%d%d“,&i,&j);//输入边(Vi，Vj)的顶点序号
G->edges=1;;G->edges=1;//若为;//=========定义标志向
量，为
全
局
变
量=;typedefenum{FALSE,TRUE}B;Booleanvisited=1;
G->edges=1;//若为无向图，矩阵为对称矩阵;若建立有向图，去掉该条语句 }
}
//=========定义标志向量，为全局变量=======
typedef enum{FALSE,TRUE} Boolean;
Boolean visited;
//========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(” “);
printf(”Print Graph BFS: “);
BFS(G,3);//以序号为3的顶点开始广度优先遍历
printf(” “);
}
2.邻接链表作为存储结构
#include”“
#include”“
#define MaxVertexNum 50 //定义最大顶点数
typedef struct node{ //边表结点
int adjvex;//邻接点域
struct node *next;//链域
申
}EdgeNode;
typedef struct vnode{ //顶点表结点
char vertex;//顶点域
EdgeNode *firstedge;//边表头指针
}VertexNode;
typedef VertexNode AdjList;//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.vertex=a;//读入顶点信息
G->adjlist.firstedge=NULL;//边表置为空表
}
printf(”Input edges,Creat Adjacency List “);
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.firstedge;
G->adjlist.firstedge=s;//将新结点*S插入顶点Vi的边表头部
s=(EdgeNode *)malloc(sizeof(EdgeNode));
s->adjvex=i;//邻接点序号为i
s->next=G->adjlist.firstedge;
G->adjlist.firstedge=s;//将新结点*S插入顶点Vj的边表头部
}
}
//=========定义标志向量，为全局变量=======
typedef enum{FALSE,TRUE} Boolean;
Boolean visited;
//========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(” “);
printf(”Print Graph BFS: “);
BFS(G,3);
printf(” “);
}
实验结果：
1.邻接矩阵作为存储结构
2.邻接链表作为存储结构
心得体会：
实验6
实验题目：二分查找算法的实现
实验目的：
掌握二分查找法的工作原理及应用过程，利用其工作原理完成实验题目中的内容。
实验要求：
编写程序构造一个有序表L，从键盘接收一个关键字key，用二分查找法在L中查找key，若找到则提示查找成功并输出key所在的位置，否则提示没有找到信息。
实验主要步骤：
1.建立的初始查找表可以是无序的，如测试的数据为{3，7，11，15，17，21，35，42，50｝或者{11，21，7，3，15，50，42，35，17｝。
2.给出算法的递归和非递归代码;
3.如何利用二分查找算法在一个有序表中插入一个元素x，并保持表的有序性?
程序代码
实验结果：
心得体会：
实验7
实验题目：排序
实验目的：
掌握各种排序方法的基本思想、排序过程、算法实现，能进行时间和空间性能的分析，根据实际问题的特点和要求选择合适的排序方法。
实验要求：
实现直接排序、冒泡、直接选择、快速、堆、归并排序算法。比较各种算法的运行速度。
实验主要步骤：
程序代码
实验结果：
心得体会：
