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

_数据结构(C语言版) 实验报告专业：计算机科学与技术学号:_班级:_姓名:_指导教师:_青岛大学信息工程学院2014年10月实验1实验题目：顺序存储结构线性表的插入和删除实验目的：了解和掌握线性表的逻辑结构和顺序存储结构，掌握线性表的基本算法及相关的时间性能分析。实验要求：建立一个数据域定义为整数类型的线性表，在表中允许有重复的数据；根据输入的数据，先找到相应的存储单元，后删除之。实验主要步骤：1、 分析、理解给出的示例程序。2、 调试程序，并设计输入一组数据（3，-5，6，8，2，-5，4，7，-9），测试程序的如下功能：根据输入的数据，找到相应的存储单元并删除，显示表中所有的数据。程序代码:#include#include #include#define OK 1#define ERROR 0#define OVERFLOW -2#define LIST_INIT_SIZE 100typedef int status;typedef int ElemType;typedef structElemType *elem;int length;int listsize;sqlist;status initlist_sq(sqlist &L)L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType);if(!L.elem)exit(OVERFLOW);L.length=0;L.listsize=LIST_INIT_SIZE;return OK;/initList.sqstatus getelem_sq(sqlist &L)int i=0,e,d;printf(please input how many number you want to initn);scanf(%d,&d);printf(please input the number you want to initn);while(1) scanf(%d,&e); L.elemi=e; L.length+;i+;if(i=d)break;return OK;status listdelet_sq(sqlist &L)int i=0,e;int *p;int *q;printf(please input the number you want to deleten);scanf(%d,&e);for(i=0;iL.length;i+)if(L.elemi=e)p=&L.elemi;q=L.elem+L.length-1;for(+p;p=q;+p) *(p-1)=*p;-L.length;break;return OK;main()int i=0;sqlist L;initlist_sq(L); getelem_sq(L);listdelet_sq(L);while(in,&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 Matrixn); for(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：广度优先遍历=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(n);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 Listn); for(k=0;ke;k+) /建立边表scanf(%d%d,&i,&j); /读入边（Vi，Vj）的顶点对序号s=(EdgeNode *)malloc(sizeof(EdgeNode); /生成边表结点s-adjvex=j; /邻接点序号为js-next=G-adjlisti.firstedge;G-adjlisti.firstedge=s; /将新结点*S插入顶点Vi的边表头部s=(EdgeNode *)malloc(sizeof(EdgeNode); s-adjvex=i; /邻接点序号为is-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(n); printf(Print Graph BFS: ); 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，并保持表的