2022年数据结构实验报告 3.pdf

《2022年数据结构实验报告 3.pdf》由会员分享，可在线阅读，更多相关《2022年数据结构实验报告 3.pdf（15页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 .1/15 数据结构(C 语言版)实验报告专业：计算机科学与技术、软件工程学号:_201240703061_ 班级:_软件二班 _ 姓名:_朱海霞 _ 指导教师:_刘遵仁_ 青岛大学信息工程学院2013 年 10 月名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 15 页 -.2/15 实验 1实验题目：顺序存储结构线性表的插入和删除实验目的：了解和掌握线性表的逻辑结构和顺序存储结构，掌握线性表的基本算法及相关的时间性能分析。实验要求：建立一个数据域定义为整数类型的线性表，在表中允许有重复的数据；根据输入的数据，先找到相应的存储单元，后删除之。实验主要步骤：1、分析、理解给出的

2、示例程序。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*)mallo

3、c(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)名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 15 页 -.3/15 int*newbase;newbase=(int*)realloc(L.elem,(L.listsize+LISTINCREMENT)*siz

4、eof(int);if(!newbase)return-1;L.elem=newbase;L.listsize+=LISTINCREMENT;int*p,*q;q=&(L.elemi-1);for(p=&(L.elemL.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.elemi-1);e=*p;q=L.elem+L.length-1;for(+p;p=q;+p)*(p-1)=*p

5、;-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;i10;i+)ListInsert_Sq(L,i,ai-1);for(i=0;i9;i+)printf(%d,L.elemi);printf(n);/插入 9个数ListInsert_Sq(L,3,24);for(i=0;i10;i+)printf(%d,L.elemi);printf(n);/插入一个数int e;ListDelete_Sq(L,2,e);for(i=0;i9;i+)printf(%d,

6、L.elemi);/删除一个数printf(n);return 0;名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 15 页 -.4/15 实验结果：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实验题目：单链表

7、的插入和删除实验目的：了解和掌握线性表的逻辑结构和链式存储结构，掌握单链表的基本算法及相关的时间性能分析。实验要求：建立一个数据域定义为字符类型的单链表，在链表中不允许有重复的字符；根据输入的字符，先找到相应的结点，后删除之。实验主要步骤：3、分析、理解给出的示例程序。4、调试程序，并设计输入数据（如：A，C，E，F，H，J，Q，M），测试程序的如下功能：不允许重复字符的插入；根据输入的字符，找到相应的结点并删除。5、修改程序：（1）增加插入结点的功能。（2）建立链表的方法有“前插”、“后插”法。程序代码:#include#include#define NULL 0#define OK 1#d

8、efine ERROR 0 typedef struct LNode int data;struct LNode*next;LNode,*LinkList;名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 15 页 -.5/15 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|ji-1)ret

9、urn 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 a8=A,C,E,F,H,J,Q,U;int i,j;InitList_L(

10、L);for(i=1,j=0;i=8,jnext;while(p!=NULL)printf(%ct,p-data);p=p-next;名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 15 页 -.6/15/插入八个字符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;p

11、rintf(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、掌握栈的基本运算，如：入栈与出栈等运算在顺序存储结构和链式存储结构上的实现。实验要求：回文判断：对于一个从键盘输入的字符串，判断其是否为回文。回文即正反序相同。如名师资料总结-精品资料欢迎下载

12、-名师精心整理-第 6 页，共 15 页 -.7/15“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 struc

13、t 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，否则返回 FALS

14、E if(S.top=S.base)return TRUE;else return FALSE;int Push(SqStack&S,int e)/插入元素 e为新的栈顶元素名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 15 页 -.8/15 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.st

15、acksize+=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 chN=0,*p,bN=0;if(InitStack(s)/初始化栈成功 printf(请输入表达式:n);gets(ch);p=ch;while(*p)/没到串尾Push(s,*p+);for(i=0;

16、iN;i+)if(!StackEmpty(s)/栈不空Pop(s,e);/弹出栈顶元素bi=e;for(i=0;in,&G-e);/输入顶点数和边数scanf(%c,&a);printf(Input Vertex string:);for(i=0;in;i+)scanf(%c,&a);G-vexsi=a;/读入顶点信息，建立顶点表 for(i=0;in;i+)for(j=0;jn;j+)G-edgesij=0;/初始化邻接矩阵printf(Input edges,Creat Adjacency Matrixn);for(k=0;ke;k+)/读入 e 条边，建立邻接矩阵scanf(%d%d,&

17、i,&j);/输入边（Vi，Vj）的顶点序号名师资料总结-精品资料欢迎下载-名师精心整理-第 10 页，共 15 页 -.11/15 G-edgesij=1;G-edgesji=1;/若为无向图，矩阵为对称矩阵；若建立有向图，去掉该条语句 /=定义标志向量，为全局变量=typedef enumFALSE,TRUE Boolean;Boolean visitedMaxVertexNum;/=DFS：深度优先遍历的递归算法=void DFSM(MGraph*G,int i)/以 Vi 为出发点对邻接矩阵表示的图G 进行 DFS 搜索，邻接矩阵是0，1 矩阵给出你的编码/=BFS：广度优先遍历=vo

18、id 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 邻接链表作为存储结构#includestdio.h#

19、includestdlib.h#define MaxVertexNum 50/定义最大顶点数typedef struct node/边表结点int adjvex;/邻接点域struct node*next;/链域EdgeNode;名师资料总结-精品资料欢迎下载-名师精心整理-第 11 页，共 15 页 -.12/15 typedef struct vnode/顶点表结点char vertex;/顶点域EdgeNode*firstedge;/边表头指针VertexNode;typedef VertexNode AdjListMaxVertexNum;/AdjList 是邻接表类型typedef

20、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-adjlisti.vertex=

21、a;/读入顶点信息G-adjlisti.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-adjlisti.firstedge;G-adjlisti.firstedge=s;/将新结点*S 插入顶点Vi 的边表头部s=(EdgeNode*)malloc(sizeof

22、(EdgeNode);s-adjvex=i;/邻接点序号为i s-next=G-adjlistj.firstedge;G-adjlistj.firstedge=s;/将新结点*S 插入顶点Vj 的边表头部 /=定义标志向量，为全局变量=typedef enumFALSE,TRUE Boolean;Boolean visitedMaxVertexNum;/=DFS：深度优先遍历的递归算法=void DFSM(ALGraph*G,int i)/以 Vi 为出发点对邻接链表表示的图G 进行 DFS 搜索名师资料总结-精品资料欢迎下载-名师精心整理-第 12 页，共 15 页 -.13/15 给出你的

23、编码/=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.邻接链表作为存储结构心得体会：名师资料总结-精品资料欢迎下载-名师精心整

24、理-第 13 页，共 15 页 -.14/15 实验 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，并保持表的有序性？程序代码实验结果：心得体会：名师资料总结-精品资料欢迎下载-名师精心整理-第 14 页，共 15 页 -.15/15 实验 7实验题目：排序实验目的：掌握各种排序方法的基本思想、排序过程、算法实现，能进行时间和空间性能的分析，根据实际问题的特点和要求选择合适的排序方法。实验要求：实现直接排序、冒泡、直接选择、快速、堆、归并排序算法。比较各种算法的运行速度。实验主要步骤：程序代码实验结果：心得体会：名师资料总结-精品资料欢迎下载-名师精心整理-第 15 页，共 15 页 -