c数据结构实验报告.docx

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 LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef struct int* elem; int length; int listsize; Sqlist; int InitList_Sq(Sqlist if(!) return -1; =0; =LIST_INIT_SIZE; return OK; int ListInsert_Sq(Sqlist if(=) int *newbase; newbase=(int*)realloc(,(+LISTINCREMENT)*sizeof(int); if(!newbase) return -1; =newbase; +=LISTINCREMENT; int *p,*q; q= for(p=p=q;-p) *(p+1)=*p; *q=e; +; return OK; int ListDelete_Sq(Sqlist if(i)return ERROR; p= e=*p; q=+; for(+p;p *(p-1)=*p; -; return OK; int main() Sqlist L; InitList_Sq(L);/初始化 int i,a=3,-5,6,8,2,-5,4,7,-9; for(i=1;i ListInsert_Sq(L,i,a); for(i=0;i printf(“ %d“,); printf(“ “);/插入 9 个数 ListInsert_Sq(L,3,24); for(i=0;i printf(“ %d“,); printf(“ “);/插入一个数 int e; ListDelete_Sq(L,2, e); for(i=0;i printf(“ %d“,);/删除一个数 printf(“ “); return 0; 实验结果： 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 #define NULL 0 #define OK 1 #define ERROR 0 typedef struct LNode int data; struct LNode *next; LNode,*LinkList; int InitList_L(LinkList L- next=NULL; return OK; int ListInsert_L(LinkList int j; p=L;j=0; while(p+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 ListDelete_L(LinkList int j; p=L;j=0; while(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 a=A,C,E,F,H,J,Q,U; int i,j; InitList_L(L); for(i=1,j=0;i p=L-next; while(p!=NULL) printf(“%c “,p-data); p=p-next; /插入八个字符 printf(“ ;实验结果： ;ACEFHJQU;ABCEFHJQU;ABEFHJQU;心得体会：;单链表是通 过扫描指针 P 进行单链表的操作;头指针唯;实验 3;实验题 目：栈操作设计和实现;实验目的：;1、掌握栈的顺序存储 结构和链式存储结构，以便在实;2、掌握栈的特点，即后 进先出和先进先出的原则;3、掌握栈的基本运算，如：入 栈与出栈 /插入八个字符 printf(“ “); i=2; int e; ListInsert_L(L,i,B); p=L-next; while(p!=NULL) printf(“%c “,p-data); p=p-next; /插入一个字符 printf(“ “); i=3; ListDelete_L(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 STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef struct int *base; / 在栈构造之前和销毁之后，base 的值 为 NULL int *top; / 栈顶指针 int stacksize; / 当前已分配的存储空间，以元素 为单位 SqStack; int InitStack(SqStack / 存储分配失败 =; =STACK_INIT_SIZE; return OK; int StackEmpty(SqStack S) / 若栈 S 为空栈，则返回 TRUE，否则返回 FALSE if(=) return TRUE; else return FALSE; int Push(SqStack if(!) exit(OVERFLOW); / 存储分配失败 =+; +=STACKINCREMENT; *()+=e; return OK; int Pop(SqStack 否则返回 ERROR if(=) return ERROR; e=*-; return OK; int main() SqStack s; int i,e,j,k=1; char ch = 0,*p,b = 0; if(InitStack(s) / 初始化栈成功 printf(“请输入表达式: “); gets(ch); p=ch; while(*p) / 没到串尾 Push(s,*p+); for(i=0;i if(!StackEmpty(s) / 栈不空 Pop(s,e); / 弹出栈顶元素 b=e; for(i=0;i if(ch!=b) 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. 邻接矩阵作为存储结构 #include“ #include“ #define MaxVertexNum 100 /定义最大顶点数 typedef struct char vexs; /顶点表 int edges; /邻接矩阵，可看作边表 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“, /输入顶点数和边数 scanf(“%c“, printf(“Input Vertex string:“); for(i=0;in;i+) scanf(“%c“, G-vexs=a; /读入顶点信息，建立顶点表 for(i=0;in;i+) for(j=0;jn;j+) G-edges=0; /初始化邻接矩阵 printf(“Input edges,Creat Adjacency Matrix “); for(k=0;ke;k+) /读入 e 条边，建立邻接矩阵 scanf(“%d%d“, /输入边(Vi，Vj)的顶点序 号 G-edges=1;G-edges=1;/若为;/=定义 标志向量，为全局变量=;typedefenumFALSE,TRUE B;Booleanvisited=1; G-edges=1; /若为无向图，矩阵为对称矩阵;若建 立有向图，去掉该条语句 /=定义标志向量，为全局变量= typedef enumFALSE,TRUE Boolean; Boolean visited; /=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. 邻接链表作为存储结构 #include“ #include“ #define MaxVertexNum 50 /定义最大顶点数 typedef struct node /边表结点 int adjvex; /邻接点域 struct node *next; /链域 EdgeNode; typedef struct vnode /顶点表结点 char vertex; /顶点域 EdgeNode *firstedge; /边表头指针 VertexNode; typedef VertexNode AdjList; /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“, /读入顶点数和边数 scanf(“%c“, printf(“Input Vertex string:“); for(i=0;in;i+) /建立边表 scanf(“%c“, G-adjlist.vertex=a; /读入顶点信息 G-adjlist.firstedge=NULL; /边表置为空表 printf(“Input edges,Creat Adjacency List “); for(k=0;ke;k+) /建立边表 scanf(“%d%d“, /读入边(Vi，Vj)的顶点对 序号 s=(EdgeNode *)malloc(sizeof(EdgeNode); /生成 边表结点 s-adjvex=j; /邻接点序号为 j s-next=G-adjlist.firstedge; G-adjlist.firstedge=s; /将新结点*S 插入顶点 Vi 的边表头部 s=(EdgeNode *)malloc(sizeof(EdgeNode); s-adjvex=i; /邻接点序号为 i s-next=G-adjlist.firstedge; G-adjlist.firstedge=s; /将新结点*S 插入顶点 Vj 的边表头部 /=定义标志向量，为全局变量= typedef enumFALSE,TRUE Boolean; Boolean visited; /=DFS：深度优先遍历的递归算法= void DFSM(ALGraph *G,int i) /以 Vi 为出发点对邻接链表表示的图 G 进行 DFS 搜索 给出你的编码