数据结构(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(i<1||i>L.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(i<1||i>L.length)return ERROR; p=&(L.elem[i-1]); e=*p; q=L.elem+L.length-1; for(++p;p<=q;++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<10;i++)

ListInsert_Sq(L,i,a[i-1]); for(i=0;i<9;i++) printf(\" %d\ printf(\"\\n\");//插入9个数 ListInsert_Sq(L,3,24); for(i=0;i<10;i++) printf(\" %d\ printf(\"\\n\");//插入一个数 int e; ListDelete_Sq(L,2, e); for(i=0;i<9;i++) printf(\" %d\删除一个数 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&&jnext;++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&&jnext;++j; } if(!(p->next)||jnext;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<=8,j<8;i++,j++) ListInsert_L(L,i,a[j]); p=L->next; while(p!=NULL){ printf(\"%c\\ p=p->next;

精选范本

.

}

}//插入八个字符 printf(\"\\n\"); i=2; int e;

ListInsert_L(L,i,'B'); p=L->next;

while(p!=NULL){ printf(\"%c\\ p=p->next; }//插入一个字符 printf(\"\\n\"); i=3;

ListDelete_L(L,i,e); p=L->next;

while(p!=NULL){ printf(\"%c\\ 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;iprintf(\"输出:\")

精选范本

.

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\ //输入顶点数和边数 scanf(\"%c\ printf(\"Input Vertex string:\"); for(i=0;in;i++) { scanf(\"%c\ G->vexs[i]=a; //读入顶点信息，建立顶点表 }

for(i=0;in;i++) for(j=0;jn;j++) G->edges[i][j]=0; //初始化邻接矩阵 printf(\"Input edges,Creat Adjacency Matrix\\n\");

for(k=0;ke;k++) { //读入e条边，建立邻接矩阵 scanf(\"%d%d\ //输入边（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\ //读入顶点数和边数 scanf(\"%c\

printf(\"Input Vertex string:\");

for(i=0;in;i++) //建立边表 { scanf(\"%c\ G->adjlist[i].vertex=a; //读入顶点信息 G->adjlist[i].firstedge=NULL; //边表置为空表 }

printf(\"Input edges,Creat Adjacency List\\n\");

for(k=0;ke;k++) { //建立边表 scanf(\"%d%d\ //读入边（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); printf(\"\\n\"); }

实验结果：

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

实验题目：排序

实验目的：

掌握各种排序方法的基本思想、排序过程、算法实现，能进行时间和空间性能的分析，根据实际问题的特点和要求选择合适的排序方法。

实验要求：

实现直接排序、冒泡、直接选择、快速、堆、归并排序算法。比较各种算法的运行速度。

实验主要步骤：

程序代码

实验结果：

心得体会：

精选范本