大数据结构C语言版试验报告材料

1、标准文档数据结构 （C 语言版 ） 实验报告专业：计算机科学与技术、软件工程学号: 201240703061班级: 软件二班 姓名: 朱海霞 指导教师 : _刘遵仁青岛大学信息工程学院2013年 10月标准文档实验 1实验题目 ：顺序存储结构线性表的插入和删除实验目的 ：了解和掌握线性表的逻辑结构和顺序存储结构， 掌握线性表的基本算法及相关的时间性 能分析。实验要求： 建立一个数据域定义为整数类型的线性表， 在表中允许有重复的数据； 根据输入的数据， 先找到相应的存储单元，后删除之。实验主要步骤：1、分析、理解给出的示例程序。2、调试程序，并设计输入一组数据( 3，-5 ，6，8，2，-5 ，

2、4，7，-9 )，测试程序的如下功 能：根据输入的数据，找到相应的存储单元并删除，显示表中所有的数据。程序代码 :#include#include#define OK 1#define ERROR 0#define OVERFLOW -2#define LIST_INIT_SIZE 100#define LISTINCREMENT 10typedef structint* elem;int length;int listsize;Sqlist;int InitList_Sq(Sqlist &L) L.elem=(int*)malloc(LIST_INIT_SIZE*sizeof(int); i

3、f(!L.elem) return -1;L.length=0;L.listsize=LIST_INIT_SIZE;return OK;int 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+=L

4、ISTINCREMENT;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 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

5、(L);/ 初始化int i,a=3,-5,6,8,2,-5,4,7,-9; for(i=1;i10;i+)ListInsert_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); printf(n);/ 插入一个数 int e;ListDelete_Sq(L,2, e); for(i=0;i9;i+)printf( %d,L.elemi);/ 删除一个数 printf(n);return 0;标准

6、文档实验结果：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实验题目 ：单链表的插入和删除实验目的 ：了解和掌握线性表的逻辑结构和链式存储结构， 掌握单链表的基本算法及相关的时间性 能分析。实验要求

7、：建立一个数据域定义为字符类型的单链表， 在链表中不允许有重复的字符； 根据输入的 字符，先找到相应的结点，后删除之。实验主要步骤：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 LNodeint d

8、ata; 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 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;

9、return OK;int ListDelete_L(LinkList&L,int i,int &e)LinkList p,q;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;标准文档/

10、 插入八个字符 printf(n);i=2;int 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;实验结果：A C E F H J Q UA B C E F H J Q UA B E F H J Q U心得体会：单链表是通过扫描指针 P 进行单链表的操作；头指

11、针唯一标识点链表的存在； 插入和删除元素快捷，方便。实验 3实验题目 ：栈操作设计和实现实验目的 ：1、掌握栈的顺序存储结构和链式存储结构，以便在实际中灵活应用。2、掌握栈的特点，即后进先出和先进先出的原则。3、掌握栈的基本运算，如：入栈与出栈等运算在顺序存储结构和链式存储结构上的实现。实验要求：回文判断： 对于一个从键盘输入的字符串，判断其是否为回文。回文即正反序相同。如标准文档“ abba”是回文，而“ abab”不是回文。实验主要步骤（ 1）数据从键盘读入；（ 2）输出要判断的字符串；（ 3）利用栈的基本操作对给定的字符串判断其是否是回文，若是则输出“Yes”，否则输出“ No”。程序代

12、码 : #include #include #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define OVERFLOW -2#define N 100 #define STACK_INIT_SIZE 100typedef structint *base;int *top;int stacksize; SqStack;int InitStack(SqStack &S) / 构造一个空栈 S#define STACKINCREMENT 10/ 在栈构造之前和销毁之后， base的值为 NULL/ 栈顶指针/ 当前已分配的

13、存储空间，以元素为单位if(!(S.base=(int *)malloc(STACK_INIT_SIZE*sizeof(int)exit(OVERFLOW); / 存储分配失败S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;int StackEmpty(SqStack S) /若栈 S为空栈，则返回 TRUE，否则返回 FALSEif(S.top=S.base)return TRUE;elsereturn FALSE;int Push(SqStack &S, int e) / 插入元素 e 为新的栈顶元素标准文档if(S.top-S.bas

14、e=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)retu

15、rn 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(%c,&a);printf(Input Vertex stri

16、ng:);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 e

17、numFALSE,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(MGra

18、ph); /为图 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; /链域Edg

19、eNode;标准文档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;/ 定义边表结点prin

20、tf(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); / 读入边(

21、 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,in