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

数据结构（C语言版）实验报告专业:计算机科学与技术、软件工程学号:班级:软件二班姓名:朱海霞指导教师:—刘遵仁青岛大学信息工程学院2023年10月“abba”是回文，而“abab”不是回文。实验重要环节(1)数据从键盘读入；(2)输出要判断的字符串；(3)运用栈的基本操作对给定的字符串判断其是否是回文，若是则输出“Yes”，否则输出“No”。程序代码：#include<stdio.h>#include<stdlib.h>defineTRUE1defineFALSE0defineOK1defineERROR0defineOVERFLOW-2defineN100#defineSTACKJNIT_SIZElOo0#defineSTACKINCREMENTl^0，typedefstruct{int*base;刈在栈构造之前和销毁之后,base的值为NULLint*top;//栈顶指针intstacksize;。〃当前已分派的存储空间,以元素为单位}SqStack；intInitStack(SqStack&S){//构造一个空栈Sif(!(S.base=(int*)mal1oc(STACK_INIT_SIZE*sizeof(int))))exit(OVERFLOW);//存储分派失败S.top=S.base；S.stacksize=STACKINITSIZE;returnOK;)intStackEmpty(SqStackS){//若栈S为空栈，则返回TRUE,否则返回FALSEif(S.top==S.base)returnTRUE；elsereturnFALSE;)intPush(SqStack&S,inte){//插入元素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;returnOK;intPop(SqStack&S9int&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(”请输入表达式：\nn)；gets(ch);P=ch；while(*p)//没到串尾Push(s,*p++);for(i=0；i<N；i++){if(!StackEmpty(s)){//栈不空Pop(s,e);//弹出栈顶元素b[i]=e;6)6for(i=0；i<N•i++){if(ch[i]!=b[i])38k=0；}oif(k==0)oprintf(”NO!”)；elseprintf(''输出:'')printf(uYES!n);)return0；}实验结果：请输入表达式:abcba输出：YES!心得体会:栈是仅能在表尾惊醒插入和删除操作的线性表，具有先进后出的性质,这个固有性质使栈成为程序设计中的有用工具。实验4实验题目：二叉树操作设计和实现实验目的：掌握二叉树的定义、性质及存储方式，各种遍历算法。实验规定:采用二叉树链表作为存储结构，完毕二叉树的建立，先序、中序和后序以及按层次遍历的操作，求所有叶子及结点总数的操作。实验重要环节：1、分析、理解程序。2、调试程序，设计一棵二叉树,输入完全二叉树的先序序列，用#代表虚结点（空指针）,如ABD###CE##F#建立二叉树，求出先序、中序和后序以及按层次遍历序列,求所有叶子及结点总数。程序代码：实验结果:心得体会:实验5实验题目：图的遍历操作实验目的：掌握有向图和无向图的概念;掌握邻接矩阵和邻接链表建立图的存储结构;掌握DFS及BFS对图的遍历操作;了解图结构在人工智能、工程等领域的广泛应用。实验规定：采用邻接矩阵和邻接链表作为图的存储结构，完毕有向图和无向图的DFS和BFS操作。实验重要环节：设计一个有向图和一个无向图，任选一种存储结构，完毕有向图和无向图的DFS（深度优先遍历）和BFS（广度优先遍历）的操作。1.邻接矩阵作为存储结构#includenstdio.hn#inc1udenstdlib.h"#defineMaxVertexNum100//定义最大顶点数typedefstruct{charvexs[MaxVertexNum];〃顶点表intedges[MaxVertexNum][MaxVertexNum]；〃邻接矩阵，可看作边表intn,e；〃图中的顶点数n和边数e}MGraph;//用邻接矩阵表达的图的类型II----=====建立邻接矩阵=======voidCreatMGraph（MGraph*G）inti,j,k;chara;printf(nInputVertexNum(n)andEdgesNum(e):")；scanf(n%d,%dM,&G->n,&G->e);//输入顶点数和边数seanf("％c“，&a);printf(nInputVertexstring:");for(i=0；i<G->n;i++){oscanf(n%cn,&a);3G->VeXs[i]=a;//读入顶点信息，建立顶点表}for(i=0;i<G->n;i++)。for(j=0;j<G->n;j++)3G->edges[i][j]=0;〃初始化邻接矩阵printf(nInputedges,CreatAdjacencyMatrix\nn);for(k=0;k<G->e;k++){//读入e条边,建立邻接矩阵。seanf(”％d%d”,&i,&j);〃输入边(Vi,Vj)的顶点序号oG->edges[i][j]=1;。G->edges[j]//若为无向图，矩阵为对称矩阵；若建立有向图，去掉该条语句))//=========定义标志向量，为全局变量=======typedefenum{FALSE,TRUE}Boo1ean；Booleanvisited[MaxVertexNum];//========DFS:深度优先遍历的递归算法======voidDFSM(MGraph*G,inti){〃以Vi为出发点对邻接矩阵表达的图G进行DFS搜索，邻接矩阵是0,1矩阵给出你的编码〃===========BFS:广度优先遍历=======voidBFS(MGraph*G,intk){//以Vk为源点对用邻接矩阵表达的图G进行广度优先搜索给出你的编码〃==========主程序main=====voidmain()(inti；MGraph*G；G=(MGraph*)malloc(sizeof(MGraph));〃为图G申请内存空间CreatMGraph(G);//建立邻接矩阵printf(nPrintGraphDFS:");DFS(G)；//深度优先遍历printf(H\nH);printf(nPrintGraphBFS:")；BFS(G,3)；〃以序号为3的顶点开始广度优先遍历printf(n\nn);}2.邻接链表作为存储结构#inc1udeMstdio.h"#includenstdlib.hn

〃边表结点〃边表结点〃边表结点//定义最大顶点数intadjvex；structnode*next;〃邻接点域//链域}EdgeNode;typedefstructvnode{charvertex;//顶点表结点〃顶点域EdgeNode*firstedge;〃边表结点//定义最大顶点数intadjvex；structnode*next;〃邻接点域//链域}EdgeNode;typedefstructvnode{charvertex;//顶点表结点〃顶点域EdgeNode*firstedge;〃边表头指针}VertexNode；typedefVertexNodeAdjList[MaxVertexNum];类型//AdjList是邻接表typedefstruct{AdjListadjlist；intn,e;}ALGraph;//邻接表//图中当前顶点数和边数//图类型〃=========建立图的邻接表=======voidCreatALGraph(ALGraph*G)rinti,j,k;chara;EdgeNode*s；//定义边表结点printf(nInputVertexNum(n)andEdgesNum(e):")；scanf(H%d,%dM,&G->n,&G->e);//读入顶点数和边数scanf("%c\&a);printf(nInputVertexstring：");for(i=0;i<G->n;i++)//建立边表scanf(n%cn,&a)；G->adjlist[i].vertex=a;〃读入顶点信息G—>adjlist[i].firstedge=NULL；〃边表置为空表}printf(nInputedges,CreatAdjacencyList\n");for(k=0；k<G->e；k++){〃建立边表oscanfC%d%d\&i,&j);〃读入边(Vi,Vj)的顶点对序号°s=(EdgeNode*)malloc(sizeof(EdgeNode));〃生成边表结点os->adjvex=j；//邻接点序号为ji»s->next=G—>adjlist[i].firstedge；^>G->adj1ist[i].firstedge=s;〃将新结点*S插入顶点Vi的边表头部s=(EdgeNode*)malloc(sizeof(EdgeNode));^s—>adjvex=i；〃邻接点序号为is->next=G—>adjlist[j].firstedge；G—>adjlist[j].firstedge=s;//将新结点*S插入顶点Vj的边表头部))//=========定义标志向量，为全局变量=======typedefenum{FALSE,TRUE}Boolean;Booleanvisited[MaxVertexNum];//========dfs：深度优先遍历的递归算法======voidDFSM(ALGraph*G,inti){〃以Vi为出发点对邻接链表表达的图G进行DFS搜索给出你的编码实验1实验题目：顺序存储结构线性表的插入和删除实验目的：了解和掌握线性表的逻辑结构和顺序存储结构，掌握线性表的基本算法及相关的时间性能分析。实验规定：建立一个数据域定义为整数类型的线性表，在表中允许有反复的数据;根据输入的数据,先找到相应的存储单元，后删除之。实验重要环节：1、分析、理解给出的示例程序。2、调试程序，并设计输入一组数据(3,—5,6,82-5,4,7,-9),测试程序的如下功能:根据输入的数据，找到相应的存储单元并删除，显示表中所有的数据。程序代码：#include<stdio.h>include<mal1oc.h>defineOK1defineERROR0defineOVERFLOW-2defineLIST_INIT_SIZE100defineLISTINCREMENT10typedefstruct{

H-H-H-=BFS:H-=BFS:广度优先遍历voidBFS(ALGraph*G,intk)//以Vk为源点对用邻接链表表达的图G进行广度优先搜索给出你的编码voidmain()inti;ALGraph*G;G=(ALGraph*)malloc(sizeof(ALGraph))；CreatALGraph(G)；printfC'PrintGraphDFS:”);DFS(G);printfC\nn)；Printf("PrintGraphBFS:")；BFS(G,3)；printf(H\n")；实验结果:.邻接矩阵作为存储结构.邻接链表作为存储结构心得体会:承验6实验题目：二分查找算法的实现实验目的：掌握二分查找法的工作原理及应用过程，运用其工作原理完毕实验题目中的内容。。实验规定：编写程序构造一个有序表L,从键盘接受一个关键字key,用二分查找法在L中查找key,若找到则提醒查找成功并输出key所在的位置,否则提醒没有找到信息。。实验重要环节：.建立的初始查找表可以是无序的，如测试的数据为｛3,7,11,15,17,21,35,42,50｝或者｛11,21,7,3,15,50,42,35,17｝。.给出算法的递归和非递归代码；.如何运用二分查找算法在一个有序表中插入一个元素x,并保持表的有序性？程序代码实验结果：心得体会:实验7实验题目:排序实验目的：掌握各种排序方法的基本思想、排序过程、算法实现，能进行时间和空间性能的分析，根据实际问题的特点和规定选择合适的排序方法。实验规定：实现直接排序、冒泡、直接选择、快速、堆、归并排序算法。比较各种算法的运营速度。实验重要环节：程序代码实验结果：心得体会:Ant*elem；“ntlength;intlistsize;JSqlist;intInitList_Sq(Sqlist&L){?L.elem=(int*)mal1oc(LIST_INIT_SIZE*sizeof(int));(!L.e1em)return-1;L.length=0;Llistsize=LIST_INIT_SIZE;^return0K;}intListInsert_Sq(Sqlist&L,inti,inte){Af(i<1||i>L.length+1)returnERROR；“f(L.length==L.listsize){Mnt*newbase;。newbase=(int*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(int));。if(!newbase)return-1；6L.elem=newbase；L.listsize+=LISTINCREMENT;int*p,*q;oq=&(L.elem[i—1]);efor(p—&(L.e1em[L.length-l])；p>=q;—p)*(p+l)=*p;o*q=e;o++L.1ength；returnOK;intListDelete_Sq(Sqlist&L,inti,inte){int*p,*q;if(i<l||i>L.length)returnERR0R;p=&(L.elem[i-1]);oe=*p;q=L.e1em+L.length—1；ofor(++p;P<=q；++p)°*(p-l)=*p；L.1ength;veturnOK;)intmain(){SqlistL;4nitList_Sq(L);//初始化inti,a[]={3,-5,6,8,2,-5,4,7,—9};0for(i=1;i<10;i++)Listlnsert_Sq(L,i,a[i-1])；for(i=0;i<9;i++)。printf(n%d",L.e1em[i]);叩rintf("\n")；//插入9个数。Listlnsert_Sq(L,3,24);。for(i=0;i<10;i++)printf("%dn,L.elem[i]);»printf("\n")；//插入一个数ginte;ListDelete_Sq(L,2,e);for(i=0;i〈9;i++)叩rintf("%d"，L.elem[i])；//删除一个数printf(”\n)。return0;}实验结果：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,H,J,Q,M),测试程序的如下功能:不允许反复字符的插入；根据输入的字符，找到相应的结点并删除。5、修改程序：增长插入结点的功能。建立链表的方法有“前插”、“后插”法。程序代码：inc1ude<stdio.h>include<malloc,h>defineNULL0defineOK1defineERROROtypedefstructLNode{intdata;structLNode*next;}LNode产LinkList;intInitList_L(LinkList&L){L=(LinkList)malloc(sizeof(LNode));，L->next=NULL;returnOK;}intListInsert_L(LinkList&L,inti,inte){LinkListp9s；intj;dP=L;j=0;owhile(p&&j<i-1){，p=p—>next；++j;nf(!pIU>i-1)ddreturnERROR;。s=(LinkList)mal1oc(sizeof(LNode))；s->data=e；s->next=p->next;叩・>next=s;dreturnOK;)intListDe1