还剩19页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
c数据结构实验报告数据结构C语言版实验报告;专业计算机科学与技术、软件工程;学号:xx40703061;班级:软件二班;姓名:朱海霞;指导教师:刘遵仁;青岛大学信息工程学院;xx年10月;实验1;实验题目顺序存储结构线性表的插入和删除;实验目数据结构C语言版实验报告专业计算机科学与技术、软件工程学号:xx40703061班级:软件二班姓名:朱海霞指导教师:刘遵仁青岛大学信息工程学院xx年10月实验1实验题目顺序存储结构线性表的插入和删除实验目的了解和掌握线性表的逻辑结构和顺序存储结构,掌握线性表的根本算法及相关的时间性能分析实验要求建立一个数据域定义为整数类型的线性表,在表中允许有重复的数据;根据输入的数据,先找到相应的存储单元,后删除之实验主要步骤
1、分析、理解给出的例如程序
2、调试程序,并设计输入一组数据3,-5,6,8,2,-5,4,7,-9,测试程序的如下功能根据输入的数据,找到相应的存储单元并删除,显示表中所有的数据程序代码:#include#include#defineOK1#defineERROR0#defineOVERFLOW-2#defineLISTINITSIZE100#defineLISTINCREMENT10typedefstruct{int*elem;intlength;intlistsize;}Sqlist;intInitListSqSqlistL{L.elem=int*mallocLISTINITSIZE*sizeofint;if!L.elemreturn-1;L.length=0;L.listsize=LISTINITSIZE;returnOK;}intListInsertSqSqlistLintiinte{ifi1||iL.length+1returnERROR;ifL.length==L.listsize{int*newbase;newbase=int*reallocL.elemL.listsize+LISTINCREMENT*sizeofint;if!newbasereturn-1;L.elem=newbase;L.listsize+=LISTINCREMENT;}int*p*q;q=L.elem[i-1];forp=L.elem[L.length-1];p=q;--p*p+1=*p;*q=e;++L.length;returnOK;}intListDeleteSqSqlistLintiinte{int*p*q;ifi1||iL.lengthreturnERROR;p=L.elem[i-1];e=*p;q=L.elem+L.length-1;for++p;p=q;++p*p-1=*p;--L.length;returnOK;}intmain{SqlistL;InitListSqL;//初始化intia[]={3-5682-547-9};fori=1;i10;i++ListInsertSqLia[i-1];fori=0;i9;i++printf%dL.elem[i];printf;//插入9个数ListInsertSqL324;fori=0;i10;i++printf%dL.elem[i];printf;//插入一个数inte;ListDeleteSqL2e;fori=0;i9;i++printf%dL.elem[i];//删除一个数printf;return0;}实验结果3,-5682,-547,-93,-524682,-547,-9324682,-547,-9心得体会顺序存储结构是一种随机存取结构,存取任何元素的时间是一个常数,速度快;结构简单,逻辑上相邻的元素在物理上也相邻;不使用指针,节省存储空间;但是插入和删除元素需要移动大量元素,消耗大量时间;需要一个连续的存储空间;插入元素可能发生溢出;自由区中的存储空间不能被其他数据共享实验2实验题目单链表的插入和删除实验目的了解和掌握线性表的逻辑结构和链式存储结构,掌握单链表的根本算法及相关的时间性能分析实验要求建立一个数据域定义为字符类型的单链表,在链表中不允许有重复的字符;根据输入的字符,先找到相应的结点,后删除之实验主要步骤
3、分析、理解给出的例如程序
4、调试程序,并设计输入数据如A,C,E,F,H,J,Q,M,测试程序的如下功能不允许重复字符的插入;根据输入的字符,找到相应的结点并删除
5、修改程序1增加插入结点的功能2建立链表的方法有“前插”、“后插”法程序代码:#include#include#defineNULL0#defineOK1#defineERROR0typedefstructLNode{intdata;structLNode*next;}LNode*LinkList;intInitListLLinkListL{L=LinkListmallocsizeofLNode;L-next=NULL;returnOK;}intListInsertLLinkListLintiinte{LinkListps;intj;p=L;j=0;whilepjp=p-next;++j;}if!p||ji-1returnERROR;s=LinkListmallocsizeofLNode;s-data=e;s-next=p-next;p-next=s;returnOK;}intListDeleteLLinkListLintiinte{LinkListpq;intj;p=L;j=0;whilep-nextjp=p-next;++j;}if!p-next||jreturnERROR;q=p-next;p-next=q-next;e=q-data;freeq;returnOK;}intmain{LinkListLp;chara
[8]={ACEFHJQU};intij;InitListLL;fori=1j=0;i=8j8;i++j++ListInsertLLia[j];p=L-next;whilep!=NULL{printf%cp-data;p=p-next;}//插入八个字符printf;实验结果;ACEFHJQU;ABCEFHJQU;ABEFHJQU;心得体会;单链表是通过扫描指针P进行单链表的操作;头指针唯;实验3;实验题目栈操作设计和实现;实验目的;
1、掌握栈的顺序存储结构和链式存储结构,以便在实;
2、掌握栈的特点,即后进先出和先进先出的原那么;
3、掌握栈的根本运算,如入栈与出栈}}//插入八个字符printf;i=2;inte;ListInsertLLiB;p=L-next;whilep!=NULL{printf%cp-data;p=p-next;}//插入一个字符printf;i=3;ListDeleteLLie;p=L-next;whilep!=NULL{printf%cp-data;p=p-next;}printf;return0;实验结果ACEFHJQUABCEFHJQUABEFHJQU心得体会单链表是通过扫描指针P进行单链表的操作;头指针唯一标识点链表的存在;插入和删除元素快捷,方便实验3实验题目栈操作设计和实现实验目的
1、掌握栈的顺序存储结构和链式存储结构,以便在实际中灵活应用
2、掌握栈的特点,即后进先出和先进先出的原那么
3、掌握栈的根本运算,如入栈与出栈等运算在顺序存储结构和链式存储结构上的实现实验要求回文判断对于一个从键盘输入的字符串,判断其是否为回文回文即正反序相同如“abba”是回文,而“abab”不是回文实验主要步骤1数据从键盘读入;2输出要判断的字符串;3利用栈的根本操作对给定的字符串判断其是否是回文,假设是那么输出“Yes”,否那么输出“No”程序代码:#include#include#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineOVERFLOW-2#defineN100#defineSTACKINITSIZE100#defineSTACKINCREMENT10typedefstruct{int*base;//在栈构造之前和销毁之后,base的值为NULLint*top;//栈顶指针intstacksize;//当前已分配的存储空间,以元素为单位}SqStack;intInitStackSqStackS{//构造一个空栈Sif!S.base=int*mallocSTACKINITSIZE*sizeofintexitOVERFLOW;//存储分配失败S.top=S.base;S.stacksize=STACKINITSIZE;returnOK;}intStackEmptySqStackS{//假设栈S为空栈,那么返回TRUE,否那么返回FALSEifS.top==S.basereturnTRUE;elsereturnFALSE;}intPushSqStackSinte{//插入元素e为新的栈顶元素ifS.top-S.base=S.stacksize//栈满,追加存储空间{S.base=int*reallocS.baseS.stacksize+STACKINCREMENT*sizeofint;if!S.baseexitOVERFLOW;//存储分配失败S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*S.top++=e;returnOK;}intPopSqStackSinte{//假设栈不空,那么删除S的栈顶元素,用e返回其值,并返回OK;否那么返回ERRORifS.top==S.basereturnERROR;e=*--S.top;returnOK;}intmain{SqStacks;intiejk=1;charch[N]={0}*pb[N]={0};ifInitStacks//初始化栈成功{printf请输入表达式:;getsch;p=ch;while*p//没到串尾Pushs*p++;fori=0;iif!StackEmptys{//栈不空Popse;//弹出栈顶元素b[i]=e;}}fori=0;iifch[i]!=b[i]k=0;}ifk==0printfNO!;elseprintf输出:printfYES!;}return0;}实验结果请输入表达式abcba输出YES!心得体会栈是仅能在表尾惊醒插入和删除操作的线性表,具有先进后出的性质,这个固有性质使栈成为程序设计中的有用工具实验4实验题目二叉树操作设计和实现实验目的掌握二叉树的定义、性质及存储方式,各种遍历算法实验要求采用二叉树链表作为存储结构,完成二叉树的建立,先序、中序和后序以及按层次遍历的操作,求所有叶子及结点总数的操作实验主要步骤
1、分析、理解程序
2、调试程序,设计一棵二叉树,输入完全二叉树的先序序列,用#代表虚结点空指针,如ABD###CE##F##,建立二叉树,求出先序、中序和后序以及按层次遍历序列,求所有叶子及结点总数程序代码:实验结果心得体会实验5实验题目图的遍历操作实验目的掌握有向图和无向图的概念;掌握邻接矩阵和邻接链表建立图的存储结构;掌握DFS及BFS对图的遍历操作;了解图结构在人工智能、工程等领域的广泛应用实验要求采用邻接矩阵和邻接链表作为图的存储结构,完成有向图和无向图的DFS和BFS操作实验主要步骤设计一个有向图和一个无向图,任选一种存储结构,完成有向图和无向图的DFS深度优先遍历和BFS广度优先遍历的操作
1.邻接矩阵作为存储结构#includestdio.h#includestdlib.h#defineMaxVertexNum100//定义最大顶点数typedefstruct{charvexs[MaxVertexNum];//顶点表intedges[MaxVertexNum][MaxVertexNum];//邻接矩阵,可看作边表intne;//图中的顶点数n和边数e}MGraph;//用邻接矩阵表示的图的类型//=========建立邻接矩阵=======voidCreatMGraphMGraph*G{intijk;chara;printfInputVertexNumnandEdgesNume:;scanf%d%dG-nG-e;//输入顶点数和边数scanf%ca;printfInputVertexstring:;fori=0;in;i++{scanf%ca;G-vexs[i]=a;//读入顶点信息,建立顶点表}fori=0;in;i++forj=0;jn;j++G-edges[i][j]=0;//初始化邻接矩阵printfInputedgesCreatAdjacencyMatrix;fork=0;ke;k++{//读入e条边,建立邻接矩阵scanf%d%dij;//输入边Vi,Vj的顶点序号G-edges[i][j]=1;;G-edges[j][i]=1;//假设为;//=========定义标志向量,为全局变量=;typedefenum{FALSETRUE}B;Booleanvisited[MaxVertex;//========DFS深度优先遍历的递归算;voidDFSMMGraph*Ginti;{//以Vi为出发点G-edges[i][j]=1;G-edges[j][i]=1;//假设为无向图,矩阵为对称矩阵;假设建立有向图,去掉该条语句}}//=========定义标志向量,为全局变量=======typedefenum{FALSETRUE}Boolean;Booleanvisited[MaxVertexNum];//========DFS深度优先遍历的递归算法======voidDFSMMGraph*Ginti{//以Vi为出发点对邻接矩阵表示的图G进行DFS搜索,邻接矩阵是0,1矩阵给出你的编码//===========BFS广度优先遍历=======voidBFSMGraph*Gintk{//以Vk为源点对用邻接矩阵表示的图G进行广度优先搜索给出你的编码//==========主程序main=====voidmain{inti;MGraph*G;G=MGraph*mallocsizeofMGraph;//为图G申请内存空间CreatMGraphG;//建立邻接矩阵printfPrintGraphDFS:;DFSG;//深度优先遍历printf;printfPrintGraphBFS:;BFSG3;//以序号为3的顶点开始广度优先遍历printf;}
2.邻接链表作为存储结构#includestdio.h#includestdlib.h#defineMaxVertexNum50//定义最大顶点数typedefstructnode{//边表结点intadjvex;//邻接点域structnode*next;//链域}EdgeNode;typedefstructvnode{//顶点表结点charvertex;//顶点域EdgeNode*firstedge;//边表头指针}VertexNode;typedefVertexNodeAdjList[MaxVertexNum];//AdjList是邻接表类型typedefstruct{AdjListadjlist;//邻接表intne;//图中当前顶点数和边数}ALGraph;//图类型//=========建立图的邻接表=======voidCreatALGraphALGraph*G{intijk;chara;EdgeNode*s;//定义边表结点printfInputVertexNumnandEdgesNume:;scanf%d%dG-nG-e;//读入顶点数和边数scanf%ca;printfInputVertexstring:;fori=0;in;i++//建立边表{scanf%ca;G-adjlist[i].vertex=a;//读入顶点信息G-adjlist[i].firstedge=NULL;//边表置为空表}printfInputedgesCreatAdjacencyList;fork=0;ke;k++{//建立边表scanf%d%dij;//读入边Vi,Vj的顶点对序号s=EdgeNode*mallocsizeofEdgeNode;//生成边表结点s-adjvex=j;//邻接点序号为js-next=G-adjlist[i].firstedge;G-adjlist[i].firstedge=s;//将新结点*S插入顶点Vi的边表头部s=EdgeNode*mallocsizeofEdgeNode;s-adjvex=i;//邻接点序号为is-next=G-adjlist[j].firstedge;G-adjlist[j].firstedge=s;//将新结点*S插入顶点Vj的边表头部}}//=========定义标志向量,为全局变量=======typedefenum{FALSETRUE}Boolean;Booleanvisited[MaxVertexNum];//========DFS深度优先遍历的递归算法======voidDFSMALGraph*Ginti{//以Vi为出发点对邻接链表表示的图G进行DFS搜索给出你的编码//==========BFS广度优先遍历=========voidBFSALGraph*Gintk{//以Vk为源点对用邻接链表表示的图G进行广度优先搜索给出你的编码//==========主函数===========voidmain{inti;ALGraph*G;G=ALGraph*mallocsizeofALGraph;CreatALGraphG;printfPrintGraphDFS:;DFSG;printf;printfPrintGraphBFS:;BFSG3;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实验题目排序实验目的掌握各种排序方法的根本思想、排序过程、算法实现,能进行时间和空间性能的分析,根据实际问题的特点和要求选择适宜的排序方法实验要求实现直接排序、冒泡、直接选择、快速、堆、归并排序算法比拟各种算法的运行速度实验主要步骤程序代码实验结果心得体会
1.
2.
3.
4.
5.
6.
7.
8.模板内容仅供参考 。