数据结构C语言版 实验报告.docx
- 文档编号:13968923
- 上传时间:2023-06-19
- 格式:DOCX
- 页数:20
- 大小:20.21KB
数据结构C语言版 实验报告.docx
《数据结构C语言版 实验报告.docx》由会员分享,可在线阅读,更多相关《数据结构C语言版 实验报告.docx(20页珍藏版)》请在冰点文库上搜索。
数据结构C语言版实验报告
数据结构(C语言版)实验报告
专业:
计算机科学与技术、软件工程
学号:
____201240703061___________________
班级:
_________软件二班______________
姓名:
________朱海霞______________
指导教师:
___刘遵仁________________
青岛大学信息工程学院
2013年10月
实验1
实验题目:
顺序存储结构线性表的插入和删除
实验目的:
了解和掌握线性表的逻辑结构和顺序存储结构,掌握线性表的基本算法及相关的时间性能分析。
实验要求:
建立一个数据域定义为整数类型的线性表,在表中允许有重复的数据;根据输入的数据,先找到相应的存储单元,后删除之。
实验主要步骤:
1、分析、理解给出的示例程序。
2、调试程序,并设计输入一组数据(3,-5,6,8,2,-5,4,7,-9),测试程序的如下功能:
根据输入的数据,找到相应的存储单元并删除,显示表中所有的数据。
程序代码:
#include
#include
#defineOK1
#defineERROR0
#defineOVERFLOW-2
#defineLIST_INIT_SIZE100
#defineLISTINCREMENT10
typedefstruct{
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;
if(L.length==L.listsize){
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");
return0;
}
实验结果:
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
实验题目:
单链表的插入和删除
实验目的:
了解和掌握线性表的逻辑结构和链式存储结构,掌握单链表的基本算法及相关的时间性能分析。
实验要求:
建立一个数据域定义为字符类型的单链表,在链表中不允许有重复的字符;根据输入的字符,先找到相应的结点,后删除之。
实验主要步骤:
3、分析、理解给出的示例程序。
4、调试程序,并设计输入数据(如:
A,C,E,F,H,J,Q,M),测试程序的如下功能:
不允许重复字符的插入;根据输入的字符,找到相应的结点并删除。
5、修改程序:
(1)增加插入结点的功能。
(2)建立链表的方法有“前插”、“后插”法。
程序代码:
#include
#include
#defineNULL0
#defineOK1
#defineERROR0
typedefstructLNode{
intdata;
structLNode*next;
}LNode,*LinkList;
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 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 p=p->next;++j; } if(! (p->next)||j 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); p=p->next; }//插入八个字符 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; } 实验结果: ACEFHJQU ABCEFHJQU ABEFHJQU 心得体会: 单链表是通过扫描指针P进行单链表的操作;头指针唯一标识点链表的存在;插入和删除元素快捷,方便。 实验3 实验题目: 栈操作设计和实现 实验目的: 1、掌握栈的顺序存储结构和链式存储结构,以便在实际中灵活应用。 2、掌握栈的特点,即后进先出和先进先出的原则。 3、掌握栈的基本运算,如: 入栈与出栈等运算在顺序存储结构和链式存储结构上的实现。 实验要求: 回文判断: 对于一个从键盘输入的字符串,判断其是否为回文。 回文即正反序相同。 如“abba”是回文,而“abab”不是回文。 实验主要步骤 (1)数据从键盘读入; (2)输出要判断的字符串; (3)利用栈的基本操作对给定的字符串判断其是否是回文,若是则输出“Yes”,否则输出“No”。 程序代码: #include #include #defineTRUE1 #defineFALSE0 #defineOK1 #defineERROR0 #defineOVERFLOW-2 #defineN100 #defineSTACK_INIT_SIZE100 #defineSTACKINCREMENT10 typedefstruct{ int*base;//在栈构造之前和销毁之后,base的值为NULL int*top;//栈顶指针 intstacksize;//当前已分配的存储空间,以元素为单位 }SqStack; intInitStack(SqStack&S) {//构造一个空栈S if(! (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,否则返回FALSE if(S.top==S.base) returnTRUE; else returnFALSE; } 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&S,int&e) {//若栈不空,则删除S的栈顶元素,用e返回其值,并返回OK;否则返回ERROR if(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 if(! StackEmpty(s)){//栈不空 Pop(s,e);//弹出栈顶元素 b[i]=e; } } for(i=0;i if(ch[i]! =b[i]) k=0; } if(k==0) printf("NO! "); else printf("输出: ") printf("YES! "); } return0; } 实验结果: 请输入表达式: abcba 输出: YES! 心得体会: 栈是仅能在表尾惊醒插入和删除操作的线性表,具有先进后出的性质,这个固有性质使栈成为程序设计中的有用工具。 实验4 实验题目: 二叉树操作设计和实现 实验目的: 掌握二叉树的定义、性质及存储方式,各种遍历算法。 实验要求: 采用二叉树链表作为存储结构,完成二叉树的建立,先序、中序和后序以及按层次遍历的操作,求所有叶子及结点总数的操作。 实验主要步骤: 1、分析、理解程序。 2、调试程序,设计一棵二叉树,输入完全二叉树的先序序列,用#代表虚结点(空指针),如ABD###CE##F##,建立二叉树,求出先序、中序和后序以及按层次遍历序列,求所有叶子及结点总数。 程序代码: 实验结果: 心得体会: 实验5 实验题目: 图的遍历操作 实验目的: 掌握有向图和无向图的概念;掌握邻接矩阵和邻接链表建立图的存储结构;掌握DFS及BFS对图的遍历操作;了解图结构在人工智能、工程等领域的广泛应用。 实验要求: 采用邻接矩阵和邻接链表作为图的存储结构,完成有向图和无向图的DFS和BFS操作。 实验主要步骤: 设计一个有向图和一个无向图,任选一种存储结构,完成有向图和无向图的DFS(深度优先遍历)和BFS(广度优先遍历)的操作。 1.邻接矩阵作为存储结构 #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 { scanf("%c",&a); G->vexs[i]=a;//读入顶点信息,建立顶点表 } for(i=0;i for(j=0;j G->edges[i][j]=0;//初始化邻接矩阵 printf("Inputedges,CreatAdjacencyMatrix\n"); for(k=0;k scanf("%d%d",&i,&j);//输入边(Vi,Vj)的顶点序号 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"); } 2.邻接链表作为存储结构 #include"stdio.h" #include"stdlib.h" #defineMaxVertexNum50//定义最大顶点数 typedefstructnode{//边表结点 intadjvex;//邻接点域 structnode*next;//链域 }EdgeNode; 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 { scanf("%c",&a); G->adjlist[i].vertex=a;//读入顶点信息 G->adjlist[i].firstedge=NULL;//边表置为空表 } printf("Inputedges,CreatAdjacencyList\n"); for(k=0;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) {//以Vi为出发点对邻接链表表示的图G进行DFS搜索 给出你的编码 //==========BFS: 广度优先遍历========= voidBFS(ALGraph*G,intk) {//以Vk为源点对用邻接链表表示的图G进行广度优先搜索 给出你的编码 //==========主函数=========== voidmain() { inti; ALGraph*G; G=(ALGraph*)malloc(sizeof(ALGraph)); CreatALGraph(G); printf("PrintGraphDFS: "); DFS(G); printf("\n"); printf("PrintGraphBFS: "); BFS(G,3); printf("\n"); } 实验结果: 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 实验题目: 排序 实验目的: 掌握各种排序方法的基本思想、排序过程、算法实现,能进行时间和空间性能的分析,根据实际问题的特点和要求选择合适的排序方法。 实验要求: 实现直接排序、冒泡、直接选择、快速、堆、归并排序算法。 比较各种算法的运行速度。 实验主要步骤: 程序代码 实验结果: 心得体会:
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构C语言版 实验报告 数据结构 语言版 实验 报告