2023年数据结构C语言版实验报告

数据结构（C语言版）实验报告专业：计算机科学与技术、软件工程学号:班级:软件二班姓名:朱海霞指导教师:—刘遵仁青岛大学信息工程学院2023年10月bba”是回文,而“abab”不是回文。实验重要环节(1)数据从键盘读入；(2)输出要判断的字符串；⑶运用栈的基本操作对给定的字符串判断其是否是回文，若是则输出“Yes”，否则输出“N0”。程序代码：include<stdio.h>include<stdlib.h>defineTRUE1#defineFALSE0#defineOKIdefineERROR0deHneOVERFLOW-2deflneN100#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT。10typedefstruct{int*base;g"/在栈构造之前和销毁之后,base的值为NULLint*top；go〃栈顶指针intg，stacksize;。//当前已分派的存储空间，以元素为单位}SqStack;intInitStack(SqStack&S){//构造一个空栈Sif(!(S.basc=(int*)ma1loc(STACK_INIT_SIZE*sizeof(int))))exit(OVERFLOW);//存储分派失败S.top=S.base；S.stacksize=STACK_INIT_SIZE；returnOK;}intStackEmpty(SqStackS){〃若栈S为空栈，则返回TRUE,否则返回FALSEif(S.top==S.base)returnTRUE;elsereturnFALSE;}intPush(SqStack&S,inte){//插入元素c为新的栈顶元素if(S.top-S.base>=S.stacksize)//栈满,追加存储空间(S.base=(int*)rea1loc(S.base,(S.stacksize+STACKINCREMENT)*sieof(int));if(!S.base)exit(OVERFLOW)；//存储分派失败S.top=S.base+S.stacksize；S.stacksize+=STACKINCREMENT;*(S.top)++=e;returnOK;intPop(SqStack&S,int&e){//若栈不空，则删除S的栈顶元素，用e返回其值,并返回OK;否则返回ERRORif(S.top==S.base)returnERROR;e=*--S.top;returnOK；}intmain(){SqStacks;inti,ej,k=l；charch[N]={0},♦p,b[N]={0};if(InitStack(s))//初始化栈成功(printf("请输入表达式八n”)；gets(ch);P=ch;while(*p)//没到串尾Push(s,*p++);dfor(i=0;i<N;i++){®if(!StackEmpty(s)){〃栈不空Pop(s,e)；//弹出栈顶元素b[i]=e;for(i=0;i<N；i++){3if(ch[i]!=b[i])ak=0;}®if(k==0)。printf("NO!");elsePrintf(“输出:“)printf(MYES!0);}return0；}实验结果：请输入表达式：abcba输出:YES!心得体会:栈是仅能在表尾惊醒插入和删除操作的线性表，具有先进后出的性质,这个固有性质使栈成为程序设计中的有用工具。实验4实验题目:二叉树操作设计和实现实验目的：掌握二义树的定义、性质及存储方式，各种遍历算法。实验规定:采用二叉树链表作为存储结构，完毕二叉树的建立，先序、中序和后序以及按层次遍历的操作，求所有叶子及结点总数的操作。实验重要环节：1、分析-、理解程序。2、调试程序，设计一棵二叉树，输入完全二叉树的先序序列，用#代表虚结点（空指针）,如ABD###CE##F##,建立二叉树，求M光序、中序和后序以及按层次遍历序列，求所有叶子及结点总数。程序代码：实验结果：心得体会：'实验5实验题目：图的遍历操作实验目的：掌握有向图和无向图的概念；掌握邻接矩阵和邻接链表建立图的存储结构;掌握DFS及BFS对图的遍历操作；了解图结构在人工智能、工程等领域的广泛应用。实验规定：采用邻接矩阵和邻接链表作为图的存储结构，完毕有向图和无向图的DFS和BFS操作。

实验重要环节：设计一个有向图和一个无向图，任选一种存储结构，完毕有向图和无向图的DFS(深度优先遍历)和BFS(广度优先遍历)的操作。.邻接矩阵作为存储结构include"stdio.h"inc1udeHstdIib.h"defineMaxVertexNumI00〃定义最大顶点数typedefstruct{charvexsJMaxVertexNumJ;//顶点表intedges[MaxVertexNum][MaxVertexNum];//邻接矩阵，可看作边表intn,e;〃图中的顶点数n和边数e}MGraph;〃用邻接矩阵表达的图的类型//========建立邻接矩阵=======voidCrea(MGraph(MGraph*G)(inii,j,k;chara;printf("InputVertexNum(n)andEdgesNum(e)：");scanf("%d,%d",&G->n,&G->e);//输入顶点数和边数scanf("%c",&a);printf("InputVertexstring:");for(i=0;i<G->n：i++)(scanf("%cu,&a);G->vexs[i]=a;G->vexs[i]=a;G->vexs[i]=a;//G->vexs[i]=a;//读入顶点信息，建立顶点表for(i=0;i<G->n;i++)®for(j=0;j<G_>n；j++)。G->edges[il[j]=0；//初始化邻接矩阵printf("Inputedges,CrcatAdjacencyMatrix\n");for(k=0；k<G->e;k++){〃读入e条边，建立邻接矩阵seanf(”%d%d”,&i,&」)；//输入边(Vi,Vj)的顶点序号。G->edges[ij[j]=1；G->edges[j][i]=1;//若为无向图，矩阵为对称矩阵；若建立有向图，去掉该条语句))〃=========定义标志向量，为全局变量======:lypedefenum{FALSE,TRUE}Boolean；Booleanvisited[MaxVertexNum];//========DFS：深度优先遍历的递归算法======voidDFSM(MGraph*Ginli){〃以Vi为出发点对邻接矩阵表达的图G进行DFS搜索，邻接矩阵是0,1矩阵给出你的编码//===========BFS：广度优先遍历=======voidBFS(MGraph*G,intk){〃以Vk为源点对用邻接矩阵表达的图G进行广度优先搜索给出你的编码

〃==========主程序mainvoidmain()MGraph*G;G=(MGr叩h*)malloc(sizeof(MGraph));〃为图G申请内存空间CrcatMGraph(G);〃建立邻接矩阵printf("PrintGraphDFS:");DFS(G);//深度优先遍历princf("\n");printf("PrintGmphBFS:")：BFS(G3);printf("\n");)2.邻接链表作为存储结构#include"stdio.h"BFS(G3);printf("\n");)2.邻接链表作为存储结构#include"stdio.h"#inelude"std1ib.h"#defineMaxVertexNum50typedefstructnode{intadjvex;structnode*next：}EdgeNode;typedefstructvnode{charvertex；//以序号为3的顶点开始广度优先遍历EdgeNode*firstedge;//定义最大顶点数〃边表结点//邻接点域〃链域//顶点表结点//顶点域//边表头指针}VertexNode；}VertexNode；typedefVertexNodeAdjList[MaxVertexNiim]；//AdjList是邻接表类typedefstruct{AdjListadj1ist;}VertexNode；typedefVertexNodeAdjList[MaxVertexNiim]；//AdjList是邻接表类typedefstruct{AdjListadj1ist;intn,e;}ALGraph；〃邻接表〃图中当前顶点数和边数〃图类型voidCreatALGraph(ALGraph*G)(inti,j,k;chara;EdgeNode*s;〃定义边表结点printf("InputVertexNum(n)andEdgesNum(e)：")；scanf(',%d,%d",&G->n.&G->e);//读入顶点数和边数scanf("%c",&a);printf("InputVertexstring:");for(i=0;i<G—>n;i++)〃建立边表{scanf("%c",&a);G->adjlist[i].veriex=a;〃读入顶点信息G->adj1ist[i].firstedge=NULL;〃边表置为空表)printf("Inputedges,CreatAdjacencyList\n")；for(k=0;k<G->e；k++){//建立边表oscanf("％d%d”,&i,&j);oscanf("％d%d”,&i,&j);oscanf("％d%d”,&i,&j);〃读入边oscanf("％d%d”,&i,&j);〃读入边（Vi,Vj）的顶点对序号s=(EdgeNode*)mal1oc(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;〃邻接点序号为is->ncxt=G->adjlist|j].firstedge;G—>adjlist[j].firstedge=s;〃将新结点*S插入顶点Vj的边表头部1)//=========定义标志向量，为全局变量=======typedefenum{FALSE,TRUE}Boolean;Booleanvisited[MaxVertexNum];//========DFS：深度优先遍历的递归算法======voidDFSM(ALGraph*Ginti){〃以Vi为出发点对邻接链表表达的图G进行DFS搜索给出你的编码//==========BFS：广度优先遍历=========voidBFS(ALGraph*G,intk)j{〃以Vk为源点对用邻接链表表达的图G进行广度优先搜索给出你的编码//==========主函数===========voidmain()实验1实验题目:顺序存储结构线性表的插入和删除实验目的：了解和掌握线性表的逻辑结构和顺序存储结构，掌握线性表的基本算法及相关的时间性能分析。实验规定：建立一个数据域定义为整数类型的线性表，在表中允许有反复的数据;根据输入的数据,先找到相应的存储单元，后删除之。实验重要环节：1、分析、理解给出的示例程序。2、调试程序，并设计输入一组数据(3,-5,6,8,2,—547,-9),测试程序的如下功能：根据输入的数据,找到相应的存储单元并删除，、显示表中所有的数据。程序代码：#include<sIdio.h>#include<maHoc.h>#defineOK1defineERROROdcfineOVERFLOW-2defineLIST_INIT_SIZE100defineLISTINCREMENT10typedefstruct{int*e1em;inti;ALGraph*G;G=(ALGraph*)malloc(sizeof(ALGraph));CreatALGraph(G);printfCPrintGraphDFS:")；DFS(G)；printf("\n");printf('TrintGraphBFS：");BFS(G,3)；Primf(”\n")；)实验结果：.邻接矩阵作为存储结构.邻接链表作为存储结构心得体会：♦实验6实验题目:二分查找算法的实现实验目的：掌握二分查找法的工作原理及应用过程，运用其工作原理完毕实验题目中的内容。。实验规定:编写程序构造一个有序表L,从键盘接受一个关键字key,用二分查找法在L中查找key,若找到则提醒查找成功并输出key所在的位置,否则提醒没有找到信息。。实验重要环节：.建立的初始查找表可以是无序的，如测试的数据为⑶7,11,15,17,21,35,50｝或者｛11,21,7,3,15,50,42,35,17｝。.给出算法的递归和非递归代码；.如何运用二分查找算法在一个有序表中插入一个元素x,并保持表的有序性？程序代码实验结果：心得体会：4实验7实验题目：排序实验目的：掌握各种排序方法的基本思想、排序过程、算法实现，能进行时间和空间性能的分析,根据实际问题的特点和规定选择合适的排序方法。实验规定：'实现直接排序、冒泡、直接选择、快速、堆、归并排序算法。比较各种算法的运营速度。实验重要环节：程序代码实验结果:心得体会:ntlength;«int1istsize;}Sqlist;intInitList_Sq(Sqlist&L){oL.elem=(int*)mal1oc(LIST」NIT_SIZE*sizeof(int));“f(!L.e1em)return-1；Liength=O;L.listsize=LIST_INIT_SIZE;orcturnOK；)intListInsert_Sq(Sqlist&L,inti,inte){if(i<1||i>L.length+1)returnERROR;aif(L.length==L.listsize){«int*newbase;newbase=(int*)real1oc(L.e1em,(L.listsize+LISTINCREMENT)*sizeof(int));oqf(Jnewbase)return-1;«L.elem=newbase；4.listsize+=LISTINCREMENT;°)int*p,*q;q=&(L.elem[i-l]);9for(p=&(L.elcm[LJength-1])；p>=q;-p)*(p+l)=*p;*q=e;«++L.Iength;returnOK：intListDelete_Sq(Sqlist&L,inti,inte){int*p,*q;if(i<l|Ii>L.Iength)returnERROR;p=&(L.elem[i—1])；oe=*p；sq=L.e1em+L.length_1;Mor(++p；p<=q;++p)«*(p-I)=*p;o--L.length;areturnOK;}intmain(){aSqlistL;InitList_Sq(L)；〃初始化inti,a[]={3,-5,6,82-547,-9};®for(i=l;i<10；i++)Listlnsert_Sq(L,i,a[i-1]);°for(i=0；i<9；i++)oPrintf("%d",L.elemii]);。printf("\nu)"/插入9个数oListinsert_Sq(L,3,24);®for(i=0;i<10；i++)叩rintf("%dn,L.elem[i]);gprintf("\n");//插入一个数inte；ListDe1ete_Sq(L,2,e)；for(i=0;i<9；i++)。printf(0%d"，L.elem[i]);//删除一个数printf("\nH)；8return0;I实验结果：3,-5,6,8,2,-5,4,7,-93,-5,24,6,8,2,-5,4，7,-93,24,6,8,2,-5,4,7,-9心得体会：顺序存储结构是一种随机存取结构，存取任何元素的时间是一个常数，速度快；结构简朴，逻辑上相邻的元素在物理上也相邻；不使用指针，节省存储空间;但是插入和删除元素需要移动大量元素，消耗大量时间；需要一个连续的存储空间；插入元素也许发生溢出；自由区中的存储空间不能被其他数据共享实验2实验题目:单链表的插入和删除实验目的：了解和掌握线性表的逻辑结构和链式存储结构，掌握单链表的基本算法及相关的时间性能分析。实验规定:建立一个数据域定义为字符类型的单链表，在链表中不允许有反复的字符；根据输入的字符,先找到相应的结点，后删除之。实验重要环节：3、分析、理解给出的示例程序。4、调试程序，并设计输入数据(如：A,C,E,F,HJQ,M),测试程序的如下功能:不允许反复字符的插入;根据输入的字符，找到相应的结点并删除。5、修改程序：(1)增长插入结点的功能。(2)建立链表的方法有“前插”、“后插”法。程序代码：#include<stdio.h>#include<malloc.h>defineNULL0defineOK1defineERROR0typedefstructLNode{ntdata;structLNode*next;}LN0de,*LinkList;intInitList_L(LinkList&L){L=(LinkList)mal1oc(sizeof(LNode));&L->ncxt=NULL;returnOK;}intListlnsert_L(LinkList&L,inti,inte){HJnkListp,s;"ntj；，p=L;j=O;dwhile(p&&j<i-1){p=p->next；++j；)if(!pIIj>i—1)叶eturnERR0R;®s=(LinkList)malloc(sizeof(LNode))；s->data=e;®s->next=p->next;p->next=s;returnOK;)intListDe1e