c数据结构实验报告.doc

c数据构造实验报告 数据构造(C语言版)实验报告;专业：计算机科学与技术、软件工程;学号:xx40703061;班级:软件二班;姓名:朱海霞;指导教师:刘遵仁;青岛大学信息工程学院;xx年10月;实验1;实验题目：顺序存储构造线性表的插入和删除;实验目 数据构造(C语言版) 实验报告 专业：计算机科学与技术、软件工程 学号:xx40703061 班级:软件二班 姓名:朱海霞 指导教师:刘遵仁 青岛大学信息工程学院 xx年10月 实验1 实验题目：顺序存储构造线性表的插入和删除 实验目的： 了解和掌握线性表的逻辑构造和顺序存储构造，掌握线性表的根本算法及相关的时间性能分析。 实验要求： 建立一个数据域定义为整数类型的线性表，在表中允许有重复的数据;根据输入的数据，先找到相应的存储单元，后删除之。 实验主要步骤： 1、分析、理解给出的例如程序。 2、调试程序，并设计输入一组数据(3，-5，6，8，2，-5，4，7，-9)，测试程序的如下功能：根据输入的数据，找到相应的存储单元并删除，显示表中所有的数据。 程序代码: #include #include #define OK 1 #define ERROR 0 #define OVERFLOW -2 #define LISTINITSIZE 100 #define LISTINCREMENT 10 typedef struct int* elem; int length; int listsize; Sqlist; int InitListSq(Sqlist &L) L.elem=(int*)malloc(LISTINITSIZE*sizeof(int); if(!L.elem) return -1; L.length=0; L.listsize=LISTINITSIZE; return OK; int ListInsertSq(Sqlist&L,int i,int e) if(iL.length+1) return ERROR; 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.elemi-1); for(p=&(L.elemL.length-1);p=q;-p) *(p+1)=*p; *q=e; +L.length; return OK; int ListDeleteSq(Sqlist &L,int i,int e) int *p,*q; if(iL.length)return ERROR; p=&(L.elemi-1); e=*p; q=L.elem+L.length-1; for(+p;p=q;+p) *(p-1)=*p; -L.length; return OK; int main() Sqlist L; InitListSq(L);/初始化 int i,a=3,-5,6,8,2,-5,4,7,-9; for(i=1;i10;i+) ListInsertSq(L,i,ai-1); for(i=0;i9;i+) printf( %d,L.elemi); printf( );/插入9个数 ListInsertSq(L,3,24); for(i=0;i10;i+) printf( %d,L.elemi); printf( );/插入一个数 int e; ListDeleteSq(L,2, e); for(i=0;inext=NULL; return OK; int ListInsertL(LinkList &L,int i,int e) LinkList p,s; int j; p=L;j=0; while(p&j p=p-next;+j; if(!p|ji-1) return ERROR; s=(LinkList)malloc(sizeof(LNode); s-data=e; s-next=p-next; p-next=s; return OK; int ListDeleteL(LinkList&L,int i,int &e) LinkList p,q; int j; p=L;j=0; while(p-next&j p=p-next;+j; if(!(p-next)|j return ERROR; q=p-next;p-next=q-next; e=q-data;free(q); return OK; int main() LinkList L,p; char a8=A,C,E,F,H,J,Q,U; int i,j; InitListL(L); for(i=1,j=0;i=8,jnext; while(p!=NULL) printf(%c ,p-data); p=p-next; /插入八个字符printf( ;实验结果：;ACEFHJQU;ABCEFHJQU;ABEFHJQU;心得体会：;单链表是通过扫描指针P进展单链表的操作;头指针唯;实验3;实验题目：栈操作设计和实现;实验目的：;1、掌握栈的顺序存储构造和链式存储构造，以便在实;2、掌握栈的特点，即后进先出和先进先出的原那么;3、掌握栈的根本运算，如：入栈与出栈 /插入八个字符 printf( ); i=2; int e; ListInsertL(L,i,B); p=L-next; while(p!=NULL) printf(%c ,p-data); p=p-next; /插入一个字符 printf( ); i=3; ListDeleteL(L,i,e); p=L-next; while(p!=NULL) printf(%c ,p-data); p=p-next; printf( ); return 0; 实验结果： A C E F H J Q U A B C E F H J Q U A B E F H J Q U 心得体会： 单链表是通过扫描指针P进展单链表的操作;头指针唯一标识点链表的存在;插入和删除元素快捷，方便。 实验3 实验题目：栈操作设计和实现 实验目的： 1、掌握栈的顺序存储构造和链式存储构造，以便在实际中灵活应用。 2、掌握栈的特点，即后进先出和先进先出的原那么。 3、掌握栈的根本运算，如：入栈与出栈等运算在顺序存储构造和链式存储构造上的实现。 实验要求： 回文判断：对于一个从键盘输入的字符串，判断其是否为回文。回文即正反序相同。如 “abba”是回文，而“abab”不是回文。 实验主要步骤 (1)数据从键盘读入; (2)输出要判断的字符串; (3)利用栈的根本操作对给定的字符串判断其是否是回文，假设是那么输出“Yes”，否那么输出“No”。 程序代码: #include #include #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define OVERFLOW -2 #define N 100 #define STACKINITSIZE 100 #define STACKINCREMENT 10 typedef struct int *base; / 在栈构造之前和销毁之后，base的值为NULL int *top; / 栈顶指针 int stacksize; / 当前已分配的存储空间，以元素为单位 SqStack; int InitStack(SqStack &S) / 构造一个空栈S if(!(S.base=(int *)malloc(STACKINITSIZE*sizeof(int) exit(OVERFLOW); / 存储分配失败 S.top=S.base; S.stacksize=STACKINITSIZE; return OK; int StackEmpty(SqStack S) / 假设栈S为空栈，那么返回TRUE，否那么返回FALSE if(S.top=S.base) return TRUE; else return FALSE; int Push(SqStack &S, int e) / 插入元素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; return OK; int Pop(SqStack &S,int &e) / 假设栈不空，那么删除S的栈顶元素，用e返回其值，并返回OK;否那么返回ERROR if(S.top=S.base) return ERROR; e=*-S.top; return OK; int main() SqStack s; int i,e,j,k=1; char chN = 0,*p,bN = 0; if(InitStack(s) / 初始化栈成功 printf(请输入表达式: ); gets(ch); p=ch; while(*p) / 没到串尾 Push(s,*p+); for(i=0;i if(!StackEmpty(s) / 栈不空 Pop(s,e); / 弹出栈顶元素 bi=e; for(i=0;i if(chi!=bi) k=0; if(k=0) printf(NO!); else printf(输出:) printf(YES!); return 0; 实验结果： 请输入表达式： abcba 输出：YES! 心得体会：栈是仅能在表尾惊醒插入和删除操作的线性表，具有先进后出的性质，这个固有性质使栈成为程序设计中的有用工具。 实验4 实验题目：二叉树操作设计和实现 实验目的： 掌握二叉树的定义、性质及存储方式，各种遍历算法。 实验要求： 采用二叉树链表作为存储构造，完成二叉树的建立，先序、中序和后序以及按层次遍历的操作，求所有叶子及结点总数的操作。 实验主要步骤： 1、分析、理解程序。 2、调试程序，设计一棵二叉树，输入完全二叉树的先序序列，用#代表虚结点(空指针)，如ABD#CE#F#，建立二叉树，求出先序、中序和后序以及按层次遍历序列，求所有叶子及结点总数。 程序代码: 实验结果： 心得体会： 实验5 实验题目：图的遍历操作 实验目的： 掌握有向图和无向图的概念;掌握邻接矩阵和邻接链表建立图的存储构造;掌握DFS及BFS对图的遍历操作;了解图构造在人工智能、工程等领域的广泛应用。 实验要求： 采用邻接矩阵和邻接链表作为图的存储构造，完成有向图和无向图的DFS和BFS操作。 实验主要步骤： 设计一个有向图和一个无向图，任选一种存储构造，完成有向图和无向图的DFS(深度优先遍历)和BFS(广度优先遍历)的操作。 1. 邻接矩阵作为存储构造 #includestdio.h #includestdlib.h #define MaxVertexNum 100 /定义最大顶点数 typedef struct char vexsMaxVertexNum; /顶点表 int edgesMaxVertexNumMaxVertexNum; /邻接矩阵，可看作边表 int n,e; /图中的顶点数n和边数e MGraph; /用邻接矩阵表示的图的类型 /=建立邻接矩阵= void CreatMGraph(MGraph *G) int i,j,k; char a; printf(Input VertexNum(n) and EdgesNum(e): ); scanf(%d,%d,&G-n,&G-e); /输入顶点数和边数 scanf(%c,&a); printf(Input Vertex string:); for(i=0;in;i+) scanf(%c,&a); G-vexsi=a; /读入顶点信息，建立顶点表 for(i=0;in;i+) for(j=0;jn;j+) G-edgesij=0; /初始化邻接矩阵 printf(Input edges,Creat Adjacency Matrix ); for(k=0;ke;k+) /读入e条边，建立邻接矩阵 scanf(%d%d,&i,&j); /输入边(Vi，Vj)的顶点序号 G-edgesij=1;G-edgesji=1;/假设为;/=定义标志向量，为全局变量=;typedefenumFALSE,TRUEB;BooleanvisitedMaxVertex;/=DFS：深度优先遍历的递归算;voidDFSM(MGraph*G,inti);/以Vi为出发点 G-edgesij=1; G-edgesji=1; /假设为无向图，矩阵为对称矩阵;假设建立有向图，去掉该条语句 /=定义标志向量，为全局变量= typedef enumFALSE,TRUE Boolean; Boolean visitedMaxVertexNum; /=DFS：深度优先遍历的递归算法= void DFSM(MGraph *G,int i) /以Vi为出发点对邻接矩阵表示的图G进展DFS搜索，邻接矩阵是0，1矩阵 给出你的编码 /=BFS：广度优先遍历= void BFS(MGraph *G,int k) /以Vk为源点对用邻接矩阵表示的图G进展广度优先搜索 给出你的编码 /=主程序main = void main() int i; MGraph *G; G=(MGraph *)malloc(sizeof(MGraph); /为图G申请内存空间 CreatMGraph(G); /建立邻接矩阵 printf(Print Graph DFS: ); DFS(G); /深度优先遍历 printf( ); printf(Print Graph BFS: ); BFS(G,3); /以序号为3的顶点开始广度优先遍历 printf( ); 2. 邻接链表作为存储构造 #includestdio.h #includestdlib.h #define MaxVertexNum 50 /定义最大顶点数 typedef struct node /边表结点 int adjvex; /邻接点域 struct node *next; /链域 EdgeNode; typedef struct vnode /顶点表结点 char vertex; /顶点域 EdgeNode *firstedge; /边表头指针 VertexNode; typedef VertexNode AdjListMaxVertexNum; /AdjList是邻接表类型 typedef struct AdjList adjlist; /邻接表 int n,e; /图中当前顶点数和边数 ALGraph; /图类型 /=建立图的邻接表= void CreatALGraph(ALGraph *G) int i,j,k; char a; EdgeNode *s; /定义边表结点 printf(Input VertexNum(n) and EdgesNum(e): ); scanf(%d,%d,&G-n,&G-e); /读入顶点数和边数 scanf(%c,&a); printf(Input Vertex string:); for(i=0;in;i+) /建立边表 scanf(%c,&a); G-adjlisti.vertex=a; /读入顶点信息 G-adjlisti.firstedge=NULL; /边表置为空表 printf(Input edges,Creat Adjacency List ); for(k=0;ke;k+) /建立边表 scanf(%d%d,&i,&j); /读入边(Vi，Vj)的顶点对序号 s=(EdgeNode *)malloc(sizeof(EdgeNode); /生成边表结点 s-adjvex=j; /邻接点序号为j s-next=G-adjlisti.firstedge; G-adjlisti.firstedge=s; /将新结点*S插入顶点Vi的边表头部 s=(EdgeNode *)malloc(sizeof(EdgeNode); s-adjvex=i; /邻接点序号为i s-next=G-adjlistj.firstedge; G-adjlistj.firstedge=s; /将新结点*S插入顶点Vj的边表头部 /=定义标志向量，为全局变量= typedef enumFALSE,TRUE Boolean; Boolean visitedMaxVertexNum; /=DFS：深度优先遍历的递归算法= void DFSM(ALGraph *G,int i) /以Vi为出发点对邻接链表表示的图G进展DFS搜索 给出你的编码 /=BFS：广度优先遍历= void BFS(ALGraph *G,int k) /以Vk为源点对用邻接链表表示的图G进展广度优先搜索 给出你的编码 /=主函数= void main() int i; ALGraph *G; G=(ALGraph *)malloc(sizeof(ALGraph); CreatALGraph(G); printf(Print Graph DFS: ); DFS(G); printf( ); printf(Print Graph BFS: ); BFS(G,3); 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.