《2022年数据结构实验报告 2》由会员分享，可在线阅读，更多相关《2022年数据结构实验报告 2（17页珍藏版）》请在金锄头文库上搜索。
1、数据结构 (C 语言版 ) 实验报告专业：计算机科学与技术、软件工程学号:_201240703061_ 班级:_软件二班 _ 姓名:_朱海霞_ 指导教师 :_刘遵仁 _ 青岛大学信息工程学院2013 年 10 月名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 17 页 - - - - - - - - - 实验 1实验题目：顺序存储结构线性表的插入和删除实验目的：了解和掌握线性表的逻辑结构和顺序存储结构，掌握线性表的基本算法及相关的时间性能分析。实验要求：建立一个数据域定义
2、为整数类型的线性表，在表中允许有重复的数据；根据输入的数据，先找到相应的存储单元，后删除之。实验主要步骤：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*
3、elem; int length; int listsize; Sqlist; int InitList_Sq(Sqlist &L) L.elem=(int*)malloc(LIST_INIT_SIZE*sizeof(int); if(!L.elem) return -1; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 17 页 - - - - - - - - - L.length=0; L.listsize=LIST_INIT_SIZE; return OK; int
4、 ListInsert_Sq(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
5、) *(p+1)=*p; *q=e; +L.length; return OK; int ListDelete_Sq(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; InitList_Sq(L);/初始化int i,a=3,-5,6,8,2,-5,4,7,-9; for(i=1;i10;i+) Lis
6、tInsert_Sq(L,i,ai-1); for(i=0;i9;i+) printf( %d,L.elemi); printf(n);/插入 9个数ListInsert_Sq(L,3,24); for(i=0;i10;i+) printf( %d,L.elemi); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 17 页 - - - - - - - - - printf(n);/插入一个数int e; ListDelete_Sq(L,2, e); for(i=0;i9
7、;i+) printf( %d,L.elemi);/删除一个数printf(n); 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实验题目：单链表的插入和删除实验目的：了解和掌握线性表的
8、逻辑结构和链式存储结构，掌握单链表的基本算法及相关的时间性能分析。实验要求：建立一个数据域定义为字符类型的单链表，在链表中不允许有重复的字符；根据输入的名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 17 页 - - - - - - - - - 字符，先找到相应的结点，后删除之。实验主要步骤：3、 分析、理解给出的示例程序。4、 调试程序，并设计输入数据（如：A，C，E，F，H，J，Q，M） ，测试程序的如下功能：不允许重复字符的插入；根据输入的字符，找到相应的结点并删除
9、。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) L=(LinkList)malloc(sizeof(LNode); L-next=NULL; return OK; int ListInsert_L(LinkList &L,int
10、i,int e) LinkList p,s; int j; p=L;j=0; while(p&jnext;+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&L,int i,int &e) LinkList p,q; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5
11、 页，共 17 页 - - - - - - - - - int j; p=L;j=0; while(p-next&jnext;+j; if(!(p-next)|jnext;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; InitList_L(L); for(i=1,j=0;i=8,jnext; while(p!=NULL) printf(%ct,p-data); p=p-next; / 插入八个字符printf(n); i=2; int
12、e; ListInsert_L(L,i,B); p=L-next; while(p!=NULL) printf(%ct,p-data); p=p-next; / 插入一个字符printf(n); i=3; ListDelete_L(L,i,e); p=L-next; while(p!=NULL) printf(%ct,p-data); p=p-next; printf(n); return 0; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 17 页 - - - - -
13、 - - - - 实验结果：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 ”不是回
14、文。实验主要步骤（ 1）数据从键盘读入；（ 2）输出要判断的字符串；（ 3）利用栈的基本操作对给定的字符串判断其是否是回文，若是则输出“Yes ”，否则输出“No”。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 17 页 - - - - - - - - - 程序代码 : #include #include #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define OVERFLOW -2 #de
15、fine N 100 #define STACK_INIT_SIZE 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(STACK_INIT_SIZE*sizeof(int) exit(OVERFLOW); / 存储分配失败S.top=
16、S.base; S.stacksize=STACK_INIT_SIZE; 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)*sizeo
17、f(int); if(!S.base) exit(OVERFLOW); / 存储分配失败S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 17 页 - - - - - - - - - *(S.top)+=e; return OK; int Pop(SqStack &S,int &e) / 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK ；否则返回 ERROR
18、 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(请输入表达式 :n); gets(ch); p=ch; while(*p) / 没到串尾Push(s,*p+); for(i=0;iN;i+) if(!StackEmpty(s) / 栈不空Pop(s,e); / 弹出栈顶元素bi=e; for(i=0;in,&G-e); /输入顶点数和边数scanf(%
19、c,&a); printf(Input Vertex string:); for(i=0;in;i+) scanf(%c,&a); G-vexsi=a; / 读入顶点信息，建立顶点表 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 17 页 - - - - - - - - - for(i=0;in;i+) for(j=0;jn;j+) G-edgesij=0; / 初始化邻接矩阵printf(Input edges,Creat Adjacency Matrixn); f
20、or(k=0;ke;k+) / 读入 e 条边，建立邻接矩阵scanf(%d%d,&i,&j); /输入边（ Vi ，Vj ）的顶点序号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：
21、广度优先遍历= 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(n); printf(Print Graph BFS: ); BFS(G,3); /以序号为 3 的顶点开始广度优先遍历printf(
22、n); 2 邻接链表作为存储结构#includestdio.h 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 17 页 - - - - - - - - - #includestdlib.h #define MaxVertexNum 50 /定义最大顶点数typedef struct node /边表结点int adjvex; /邻接点域struct node *next; / 链域EdgeNode; typedef struct vnode /顶点表结点char ve
23、rtex; / 顶点域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):
24、); 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 Listn); for(k=0;ke;k+) / 建立边表scanf(%d%d,&i,&j); / 读入边（ Vi ，Vj ）的顶点对序号s=(EdgeNode *)m
25、alloc(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 的边表头部 名师资料总结 - - -精品资料欢迎下载 - - - - - - - -
26、- - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 17 页 - - - - - - - - - /=定义标志向量，为全局变量= 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 进行广
27、度优先搜索给出你的编码/=主函数 = void main() int i; ALGraph *G; G=(ALGraph *)malloc(sizeof(ALGraph); CreatALGraph(G); printf(Print Graph DFS: ); DFS(G); printf(n); printf(Print Graph BFS: ); BFS(G,3); printf(n); 实验结果：1.邻接矩阵作为存储结构2.邻接链表作为存储结构心得体会：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - -
28、- - - - - 第 14 页，共 17 页 - - - - - - - - - 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 17 页 - - - - - - - - - 实验 6实验题目：二分查找算法的实现实验目的：掌握二分查找法的工作原理及应用过程，利用其工作原理完成实验题目中的内容。实验要求：编写程序构造一个有序表L，从键盘接收一个关键字key ，用二分查找法在L 中查找key ，若找到则提示查找成功并输出key 所在的位置，否则提示没有找到信息。实验主要步
29、骤：1.建立的初始查找表可以是无序的，如测试的数据为 3，7，11 ，15 ，17 ，21 ，35 ，42 ，50 或者 11 ，21 ，7，3，15 ， 50 ，42 ，35 ，17 。2.给出算法的递归和非递归代码；3.如何利用二分查找算法在一个有序表中插入一个元素x，并保持表的有序性？程序代码实验结果：心得体会：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 17 页 - - - - - - - - - 实验 7实验题目：排序实验目的：掌握各种排序方法的基本思想、排序过程、算法实现，能进行时间和空间性能的分析，根据实际问题的特点和要求选择合适的排序方法。实验要求：实现直接排序、 冒泡、 直接选择、 快速、 堆、归并排序算法。 比较各种算法的运行速度。实验主要步骤：程序代码实验结果：心得体会：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 17 页 - - - - - - - - -
