数据结构(C语言版)-实验报告

.数据结构(C语言版)-实验报告1/2.数据结构(C语言版)实验报告专业：计算机科学与技术、软件工程学号:____201240703061___________________班级:_________软件二班______________姓名:________朱海霞______________指导教师:___刘遵仁________________青岛大学信息工程学院2013年10月数据结构(C语言版)-实验报告全文共15页，当前为第1页。

数据结构(C语言版)-实验报告全文共15页，当前为第1页。实验1实验题目：顺序存储结构线性表的插入和删除实验目的：了解和掌握线性表的逻辑结构和顺序存储结构，掌握线性表的基本算法及相关的时间性能分析。实验要求：建立一个数据域定义为整数类型的线性表，在表中允许有重复的数据；根据输入的数据，先找到相应的存储单元，后删除之。实验主要步骤：分析、理解给出的示例程序。调试程序，并设计输入一组数据（3，-5，6，8，2，-5，4，7，-9），测试程序的如下功能：根据输入的数据，找到相应的存储单元并删除，显示表中所有的数据。程序代码:#include<stdio.h>#include<malloc.h>#defineOK1#defineERROR0#defineOVERFLOW-2#defineLIST_INIT_SIZE100#defineLISTINCREMENT10typedefstruct{ int*elem; intlength; intlistsize;}Sqlist;intInitList_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; returnOK;}intListInsert_Sq(Sqlist&L,inti,inte){ if(i<1||i>L.length+1)returnERROR;数据结构(C语言版)-实验报告全文共15页，当前为第2页。数据结构(C语言版)-实验报告全文共15页，当前为第2页。 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; returnOK;}intListDelete_Sq(Sqlist&L,inti,inte){ int*p,*q; if(i<1||i>L.length)returnERROR; 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; InitList_Sq(L);//初始化 inti,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",L.elem[i]); printf("\n");//插入9个数 ListInsert_Sq(L,3,24); for(i=0;i<10;i++) printf("%d",L.elem[i]); printf("\n");//插入一个数 inte; ListDelete_Sq(L,2,e); for(i=0;i<9;i++) printf("%d",L.elem[i]);//删除一个数 printf("\n");数据结构(C语言版)-实验报告全文共15页，当前为第3页。 r数据结构(C语言版)-实验报告全文共15页，当前为第3页。}实验结果：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实验题目：单链表的插入和删除实验目的：了解和掌握线性表的逻辑结构和链式存储结构，掌握单链表的基本算法及相关的时间性能分析。实验要求：建立一个数据域定义为字符类型的单链表，在链表中不允许有重复的字符；根据输入的字符，先找到相应的结点，后删除之。实验主要步骤：分析、理解给出的示例程序。调试程序，并设计输入数据（如：A，C，E，F，H，J，Q，M），测试程序的如下功能：不允许重复字符的插入；根据输入的字符，找到相应的结点并删除。修改程序：增加插入结点的功能。建立链表的方法有“前插”、“后插”法。程序代码:#include<stdio.h>#include<malloc.h>#defineNULL0#defineOK1#defineERROR0typedefstructLNode{ intdata; structLNode*next;数据结构(C语言版)-实验报告全文共15页，当前为第4页。}LNod数据结构(C语言版)-实验报告全文共15页，当前为第4页。intInitList_L(LinkList&L){ L=(LinkList)malloc(sizeof(LNode)); L->next=NULL; returnOK;}intListInsert_L(LinkList&L,inti,inte){ LinkListp,s; intj; p=L;j=0; while(p&&j<i-1){ p=p->next;++j; } if(!p||j>i-1) returnERROR; s=(LinkList)malloc(sizeof(LNode)); s->data=e; s->next=p->next; p->next=s; returnOK;}intListDelete_L(LinkList&L,inti,int&e){ LinkListp,q; intj; p=L;j=0; while(p->next&&j<i-1){ p=p->next;++j; } if(!(p->next)||j<i-1) returnERROR; q=p->next;p->next=q->next; e=q->data;free(q); returnOK;}intmain(){ LinkListL,p; chara[8]={'A','C','E','F','H','J','Q','U'}; inti,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\t",p->data);数据结构(C语言版)-实验报告全文共15页，当前为第5页。数据结构(C语言版)-实验报告全文共15页，当前为第5页。 }//插入八个字符 printf("\n"); i=2; inte; ListInsert_L(L,i,'B'); p=L->next; while(p!=NULL){ printf("%c\t",p->data); p=p->next; }//插入一个字符 printf("\n"); i=3; ListDelete_L(L,i,e); p=L->next; while(p!=NULL){ printf("%c\t",p->data); p=p->next; } printf("\n"); return0;}实验结果：ACEFHJQUABCEFHJQUABEFHJQU心得体会：单链表是通过扫描指针P进行单链表的操作；头指针唯一标识点链表的存在；插入和删除元素快捷，方便。实验3实验题目：栈操作设计和实现实验目的：1、掌握栈的顺序存储结构和链式存储结构，以便在实际中灵活应用。2、掌握栈的特点，即后进先出和先进先出的原则。3、掌握栈的基本运算，如：入栈与出栈等运算在顺序存储结构和链式存储结构上的实现。实验要求：数据结构(C语言版)-实验报告全文共15页，当前为第6页。数据结构(C语言版)-实验报告全文共15页，当前为第6页。实验主要步骤（1）数据从键盘读入；（2）输出要判断的字符串；（3）利用栈的基本操作对给定的字符串判断其是否是回文，若是则输出“Yes”，否则输出“No”。程序代码:#include<stdio.h>#include<stdlib.h>#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineOVERFLOW-2#defineN100#defineSTACK_INIT_SIZE 100 #defineSTACKINCREMENT 10 typedefstruct{int *base; //在栈构造之前和销毁之后，base的值为NULLint *top; //栈顶指针int stacksize; //当前已分配的存储空间，以元素为单位}SqStack;intInitStack(SqStack&S){//构造一个空栈Sif(!(S.base=(int*)malloc(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语言版)-实验报告全文共15页，当前为第7页。{//插入元素e为新的栈顶元素数据结构(C语言版)-实验报告全文共15页，当前为第7页。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&S,int&e){//若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERRORif(S.top==S.base)returnERROR;e=*--S.top;returnOK;}intmain(){SqStacks;inti,e,j,k=1;charch[N]={0},*p,b[N]={0};if(InitStack(s))//初始化栈成功{printf("请输入表达式:\n");gets(ch);p=ch;while(*p)//没到串尾Push(s,*p++); for(i=0;i<N;i++){ if(!StackEmpty(s)){//栈不空Pop(s,e);//弹出栈顶元素 b[i]=e; } } for(i=0;i<N;i++){ if(ch[i]!=b[i]) k=0;} if(k==0) printf("NO!"); else数据结构(C语言版)-实验报告全文共15页，当前为第8页。数据结构(C语言版)-实验报告全文共15页，当前为第8页。printf("YES!");} return0;}实验结果：请输入表达式：abcba输出：YES!心得体会：栈是仅能在表尾惊醒插入和删除操作的线性表，具有先进后出的性质，这个固有性质使栈成为程序设计中的有用工具。实验4实验题目：二叉树操作设计和实现实验目的：掌握二叉树的定义、性质及存储方式，各种遍历算法。实验要求：采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序以及按层次遍历的操作，求所有叶子及结点总数的操作。实验主要步骤：分析、理解程序。调试程序，设计一棵二叉树，输入完全二叉树的先序序列，用#代表虚结点（空指针），如ABD###CE##F##，建立二叉树，求出先序、中序和后序以及按层次遍历序列，求所有叶子及结点总数。程序代码:实验结果：心得体会：数据结构(C语言版)-实验报告全文共15页，当前为第9页。

数据结构(C语言版)-实验报告全文共15页，当前为第9页。实验题目：图的遍历操作实验目的：掌握有向图和无向图的概念；掌握邻接矩阵和邻接链表建立图的存储结构；掌握DFS及BFS对图的遍历操作；了解图结构在人工智能、工程等领域的广泛应用。实验要求：采用邻接矩阵和邻接链表作为图的存储结构，完成有向图和无向图的DFS和BFS操作。实验主要步骤：设计一个有向图和一个无向图，任选一种存储结构，完成有向图和无向图的DFS（深度优先遍历）和BFS（广度优先遍历）的操作。邻接矩阵作为存储结构#include"stdio.h"#include"stdlib.h"#defineMaxVertexNum100//定义最大顶点数typedefstruct{charvexs[MaxVertexNum];//顶点表intedges[MaxVertexNum][MaxVertexNum];//邻接矩阵，可看作边表intn,e;//图中的顶点数n和边数e}MGraph;//用邻接矩阵表示的图的类型//=========建立邻接矩阵=======voidCreatMGraph(MGraph*G){inti,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("%c",&a); G->vexs[i]=a;//读入顶点信息，建立顶点表}for(i=0;i<G->n;i++) for(j=0;j<G->n;j++) G->edges[i][j]=0;//初始化邻接矩阵printf("Inputedges,CreatAdjacencyMatrix\n");for(k=0;k<G->e;k++){//读入e条边，建立邻接矩阵数据结构(C语言版)-实验报告全文共15页，当前为第10页。 scanf("%d%d",&i,&j);数据结构(C语言版)-实验报告全文共15页，当前为第10页。 G->edges[i][j]=1; G->edges[j][i]=1;//若为无向图，矩阵为对称矩阵；若建立有向图，去掉该条语句}}//=========定义标志向量，为全局变量=======typedefenum{FALSE,TRUE}Boolean;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("PrintGraphDFS:");DFS(G);//深度优先遍历printf("\n");printf("PrintGraphBFS:");BFS(G,3);//以序号为3的顶点开始广度优先遍历printf("\n");}邻接链表作为存储结构#include"stdio.h"#include"stdlib.h"#defineMaxVertexNum50//定义最大顶点数typedefstructnode{//边表结点intadjvex;//邻接点域structnode*next;//链域数据结构(C语言版)-实验报告全文共15页，当前为第11页。数据结构(C语言版)-实验报告全文共15页，当前为第11页。typedefstructvnode{//顶点表结点charvertex;//顶点域EdgeNode*firstedge;//边表头指针}VertexNode;typedefVertexNodeAdjList[MaxVertexNum];//AdjList是邻接表类型typedefstruct{AdjListadjlist;//邻接表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].vertex=a;//读入顶点信息 G->adjlist[i].firstedge=NULL;//边表置为空表}printf("Inputedges,CreatAdjacencyList\n");for(k=0;k<G->e;k++){//建立边表 scanf("%d%d",&i,&j);//读入边（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的边表头部}}//=========定义标志向量，为全局变量=======typedefenum{FALSE,TRUE}Boolean;Booleanvisited[MaxVertexNum];//========DFS：深度优先遍历的递归算法======voidDFSM(ALGraph*G,inti)数据结构