数据结构实验报告 代码.doc

《数据结构实验报告 代码.doc》由会员分享，可在线阅读，更多相关《数据结构实验报告 代码.doc（31页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构实验报告实验序号：5 实验项目名称：链式栈学号姓名罗维卿专业、班12物联网实验地点指导教师实验时间一、实验目的及要求1. 掌握栈的存储结构的表示和实现方法。二、实验设备（环境）及要求微型计算机；windows 操作系统；Microsoft Visual Studio 6.0集成开发环境。三、实验内容与步骤（1）根据输入的栈中元素个数和各元素值建立一个链栈，并输出链栈中各元素值, 观察输入的内容与输出的内容是否一致,特别注意栈顶元素的位置。（2）将数据元素x入栈，并输出入栈后的链栈中各元素值。（3）将链栈中的栈顶元素出栈，并输入出栈元素的值和出栈后链栈中各元素值。四、实验结果与数据处理五

2、、分析与讨论对上机实践结果进行分析，上机的心得体会。六、教师评语签名：日期：成绩附源程序清单：1实验要求编程实现如下功能：（1）根据输入的栈中元素个数n和各元素值建立一个顺序栈，并输出栈中各元素值。（2）将数据元素e入栈，并输出入栈后的顺序栈中各元素值。（3）将顺序栈中的栈顶元素出栈，并输出出栈元素的值和出栈后顺序栈中各元素值。2. 实验相关原理：栈是一种插入和删除操作都限制在表的一端进行的特殊线性表，它的操作具有“先进后出”的特性。采用顺序存储结构的栈称为顺序栈。栈的存储结构描述如下：#define MAXSIZE 100; /*顺序栈的最大长度*/typedef struct Selemt

3、ype baseMAXSIZE; /*存储栈中数据元素的数组*/ int top; /*top为栈顶指针，它指示栈顶元素的存储空间的下一个存储单元*/ Sqstack;【核心算法提示】 1顺序栈入栈操作的基本步骤：首先判断顺序栈是否为满，如果满，则函数返回ERROR，否则将待入栈的数据元素存放在top所指示的存储单元中，再使top后移一个存储单元位置，即将top值加1，最后函数返回OK。2 顺序栈出栈操作的基本步骤：首先判断顺序栈是否为空，如果空，则函数返回ERROR，否则将栈顶指针前移一个存储单元位置，即将top值减1,再将top所指示的栈顶元素用e返回其值，并使函数返回OK。【核心算法描述

4、】status Push(Sqstack &S,Selemtype e)/*将数据元素e压入到顺序栈S中，使其成为新的栈项元素*/ if (S.top =MAXSIZE) /*如果栈满，则函数返回ERROR*/ return ERROR; S.baseS.top+=e;/*将新元素e存放在top所指示的存储单元中,并使top值加1*/ return OK; status Pop(Sqstack &S,Selemtype &e)/*将顺序栈S中的栈顶元素从栈中删除，并用e返回其值*/ if (S.top=0) /*如果栈空，则函数返回ERROR*/ Return ERROR; e=S.base-

5、S.top;/*将top值减1,并用e保存top所指示的栈顶元素值*/ return OK; 3源程序代码参考#define MAXSIZE 100typedef struct int baseMAXSIZE; int top; /*top指示存储栈顶元素的下一存储单元*/ Sqstack; /*顺序栈的类型定义*/Sqstack Push(Sqstack S,int e) /*顺序栈的入栈操作函数*/ if (S.top=MAXSIZE) printf(Stack is Overflown);else S.baseS.top+=e; return S; Sqstack Pop(Sqstack

6、 S,int *e) /*顺序栈的出栈操作函数*/ if (S.top=0) printf(Stack is Emptyn);else *e=S.base-S.top; return S; void Stack_display(Sqstack S) /*顺序栈的输出函数*/ int i; for(i=0; iS.top;i+) /*依次输出栈中各元素的值，栈顶元素在表的尾部*/ printf(%4d, S.basei); printf(n); main() Sqstack S; int i,j,n,x,e; printf(please input the length:);/*请求输入顺序栈中

7、元素个数*/ scanf(%d,&n); printf(please input the Value:n );/*请求输入顺序栈中各个元素值*/ for(i=0;idata=e; /*新结点的数据域赋值*/ p-next=top; /*修改链使新结点插入到链表的头部,并成为新的栈顶元素*/ top=p; return OK; status Pop(LinkStack &top,int &e) /*将链栈top中的栈顶元素从栈中删除，并用e返回其值*/ LinkStack q; if (!top) /*如果栈空，则函数返回ERROR*/ return ERROR; e=top-data; /*将

8、被删的栈顶元素的值保存在e中*/ q=top; /*用q记下待删的栈顶元素*/top=q-next; /*修改链使待删结点从链中“卸下”，此时被删结点的后继成为新的栈顶元素结点*/ free(q); /*释放被删结点的存储空间*/ return OK;数据结构实验报告实验序号：7 实验项目名称：串学号31姓名罗维卿 专业、班12物联网实验地点指导教师实验时间一、实验目的及要求1. 掌握串的顺序表示和堆表示实现方法；二、实验设备（环境）及要求微型计算机；windows 操作系统；Microsoft Visual Studio 6.0集成开发环境。三、实验内容与步骤1、 根据串的三种实现方式，顺序

9、、堆和链，选择其中一种分别实现串赋值、串合并、删除等操作。四、实验结果与数据处理五、分析与讨论对上机实践结果进行分析，上机的心得体会。六、教师评语签名：日期：成绩附源程序清单：#include#include#define MaxSize 100typedef structchar dataMaxSize;int length;SqString;void StrAssign(SqString &str,char cstr)int i;for(i=0;cstri!=0;i+)str.datai=cstri;str.length=i;void StrCopy(SqString &s,SqStrin

10、g t)int i;for(i=0;it.length;i+)s.datai=t.datai;s.length=t.length;int StrEqual(SqString s,SqString t)int same=1,i;if(s.length!=t.length)same=0;elsefor(i=0;is.length;i+)if(s.datai!=t.datai)same=0;return same;int StrLength(SqString s)return s.length;SqString Concat(SqString s,SqString t)SqString str;in

11、t i;str.length=s.length+t.length;for(i=0;is.length;i+)str.datai=s.datai;for(i=0;it.length;i+)str.datas.length+i=t.datai;return str;SqString SubStr(SqString s,int i,int j)SqString str;int k;str.length=0;if(is.length|js.length)cout参数错误nendl;return str;for(k=i-1;ki+j-1;k+)str.datak-i+1=s.datak;str.leng

12、th=j;return str;SqString InsStr(SqString s1,int i,SqString s2)int j;SqString str;str.length=0;if(is1.length+1)cout参数错误nendl;return s1;for(j=0;ji-1;j+)str.dataj=s1.dataj;for(j=0;js2.length;j+)str.datai+j-1=s2.dataj;for(j=i-1;js1.length;j+)str.length=s1.length+s2.length;return str;SqString DelStr(SqSt

13、ring s,int i,int j)int k;SqString str;str.length=0;if(is.length|i+js.length+1)/参数不正确时返回空串printf(参数不正确n);return str;for(k=0;ki-1;k+) /将s.data0.i-2复制到strstr.datak=s.datak;for(k=i+j-1;ks.length;k+)/将s.datai+j-1.s.length-1 str.datak-j=s.datak;str.length=s.length-j;return str;SqString RepStr(SqString s,i

14、nt i,int j, SqString t)/将串s的第i个字符开始的j个字符替换成串t产生新串int k;SqString str;str.length=0;if(is.length|i+j-1s.length)/参数不正确时返回空串printf(参数不正确n);return str;for(k=0;ki-1;k+) /将s.data0.i-2复制到strstr.datak=s.datak;for(k=0;kt.length;k+)str.datai+k-1=t.datak;for(k=i+j-1;k0)for(i=0;is.length;i+)printf(%c,s.datai);pri

15、ntf(n);/主程序void main()SqString s,s1,s2,s3,s4;printf(1)建立串s和串s1n);StrAssign(s,abcdefghijklmn);StrAssign(s1,xyz);printf(2)输出串s:);DispStr(s);printf(3)串s的长度:%dn,StrLength(s);printf(4)在串的第九个字符位置插入串s1而产生串s2n);s2=InsStr(s,9,s1);printf(5)输出串s2:);DispStr(s2);printf(6)删除串s第二个字符开始的个字符而产生串s2n);s2=DelStr(s,2,3);

16、printf(7)输出串s2：);DispStr(s2);printf(8)将串s第二个字符开始的个字符替换成串s1而产生串s2n); s2=RepStr(s,2,5,s1);printf(9)输出串s2：);DispStr(s2);printf(10)提取串s的第二个字符开始的个字符而产生串s3n); s3=SubStr(s,2,10);printf(11)输出串s3：);DispStr(s3);printf(12)将串s1和串s2连接起来而产生串s4n);s4=Concat(s1,s2);printf(13)输出串s4:);DispStr(s4);数据结构实验报告实验序号：2 实验项目名称

17、：线性表学号姓名罗维卿专业、班12物联网实验地点1-516指导教师实验时间2014-3-17一、实验目的及要求1. 掌握线性表的顺序存储结构表示和实现方法；2. 掌握顺序表基本操作的算法实现；3了解顺序表的应用。二、实验设备（环境）及要求微型计算机；windows 操作系统；Microsoft Visual Studio 6.0集成开发环境。三、实验内容与步骤1、 根据输入顺序表的长度n和各数据元素建立顺序表，并输出顺序表中各元素值，观察输入的内容和输出的内容是否一致。2、在顺序表的第i个元素之前插入一值为x的元素，并输出插入后的顺序表中各元素值。3、删除顺序表中第i个元素，并输出删除后的顺序

18、表中各元素值。4、在顺序表中查找第i个元素，如果成功就显示“查找成功”及位置，否则显示“查找失败”。四、实验结果与数据处理五、分析与讨论六、教师评语签名：日期：成绩附源程序清单： #include #define MAXLEN 50 typedef structint elemMAXLEN; int length;Sqlist; Sqlist Sqlist_insert(Sqlist L,int i,int x) /*顺序表插入函数*/ int j; if(iL.length+1) printf(ERROR!); else if(L.length=MAXLEN) printf(OLERFLOW

19、!); else for(j=L.length-1;j=i-1;j-) L.elemj+1=L.elemj; L.elemi-1=x; L.length+; return L; Sqlist Sqlist_delete(Sqlist L,int i) /*顺序表删除函数*/ int j; if(iL.length) printf(ERROR!); else for(j=i;j=L.length-1;j+) L.elemj-1=L.elemj; L.length-; return L; int Sqlist_search(Sqlist L,int x)/* 顺序表查找函数*/ int i; fo

20、r (i=0;iL.length&L.elemi!=x;i+); if (iL.length) return i+1; else return 0; void Sqlist_display(Sqlist L) /*顺序表元素输出函数*/ int j; for(j=0;j=L.length-1;j+) printf(%4d ,L.elemj); printf(n); main() /*主函数 */ Sqlist L; int i,x,j; printf(n请输入链表长度:);/*请求输入顺序表中元素个数*/ scanf(%d,&L.length); printf(输入顺序表中各个元素:n);/*

21、请求输入顺序表中各个元素*/ for(j=0;j=L.length-1;j+) scanf(%d,&L.elemj); printf(输入插入操作位置:); /*请求输入插入操作位置*/ scanf(%d,&i); printf(输入需要插入的新元素:);/*请求输入需要插入的新元素*/ scanf(%d,&x); L=Sqlist_insert(L,i,x);/*调用顺序表插入函数*/ Sqlist_display(L);/*调用顺序表元素输出函数*/ printf(输入删除操作位置:);/*请求输入删除操作位置*/ scanf(%d,&i); L=Sqlist_delete(L,i);/*

22、调用顺序表删除函数*/ Sqlist_display(L);/*调用顺序表元素输出函数*/ printf(please input the search node:); scanf(%d,&x); if (Sqlist_search(L,x) /*如果查找成功，则显示查找成功和找到的元素位置，否则显示查 找不成功*/ printf( search is success and %d is %d positionn,x,Sqlist_search(L,x); else printf( search is unsuccessn); 数据结构实验报告实验序号：3 实验项目名称：单链表学号姓名罗维卿专

23、业、班12物联网实验地点指导教师实验时间2014-3-24一、实验目的及要求1. 建立单链表，并在单链表上实现插入、删除和查找操作（验证性内容）。二、实验设备（环境）及要求微型计算机；windows 操作系统；Microsoft Visual Studio 6.0集成开发环境。三、实验内容与步骤1、根据输入的一系列整数，以0标志结束，用头插法建立单链表，并输出单链表中各元素值，观察输入的内容与输出的内容是否一致。2、在单链表的第i个元素之前插入一个值为x的元素，并输出插入后的单链表中各元素值。3、删除单链表中第i个元素，并输出删除后的单链表中各元素值。4、在单链表中查找第i个元素，如果查找成功

24、，则显示该元素的值，否则显示该元素不存在。四、实验结果与数据处理五、分析与讨论对上机实践结果进行分析，上机的心得体会。六、教师评语签名：日期：成绩附源程序清单：#include #include typedef struct Lnode int data; struct Lnode *next; LNODE,*Linklist;Linklist creat(Linklist L) /*单链表建立函数 */int node; Linklist p; L=(Linklist)malloc(sizeof(LNODE); L-next=NULL; printf(nplease input the no

25、de(end with 0):n ); /*请求输入线性表中各个元素，以0结束*/ scanf(%d,&node); while(node!=0) p=(Linklist)malloc(sizeof(LNODE); if (!p) exit(); p-data=node; p-next=L-next; L-next=p; scanf(%d,&node); return L;Linklist insert(Linklist L,int i,int x) /*单链表插入函数*/ int j;Linklist p,s; p=L; j=0; while (p!=NULL&jnext; +j; if (

26、p=NULL|ji-1) printf(n ERROR position!n); else s=(Linklist)malloc(sizeof(LNODE); s-data=x; s-next=p-next; p-next=s; return L;Linklist delete(Linklist L,int i) /*单链表删除函数*/ int j,x; Linklist p,q; p=L; j=0; while(p-next!=NULL&jnext; +j; if(p-next=NULL|ji-1) printf(n ERROE position!n); else q=p-next; p-n

27、ext=q-next; x=q-data; printf(the delete data is:%dn,x); free(q); return L;int search(Linklist L, int i) /*单链上的查找函数*/ Linklist p; int j; p=L-next; j=1; while (p& jnext; j+; if (!p& ji) return 0; /*如果i值不合法，即i值小于1或大于表长，则函数返回0值*/ else return(p-data); /*否则函数返回第i个元素的值*/void display(Linklist L) /*单链表元素输出函数

28、*/ Linklist p; p=L-next; while(p!=NULL) printf(%4d,p-data); p=p-next; printf(n);main()/*主函数*/ Linklist L=NULL; int i,x; L=creat(L);/*调用单链表建立函数*/ printf(the Linklist is:n); display(L); /*调用单链表元素输出(遍历)函数*/ printf(please input the position you want to insert:);/*请求输入插入操作位置*/ scanf(%d,&i); printf(please

29、 input the node you want to insert:);/*请求输入需要插入的元素*/ scanf(%d,&x); L=insert(L,i,x);/*调用单链表插入函数*/ printf(the Linklist after inserted is:n); display(L);/*调用单链表元素输出(遍历)函数*/ printf(please input the node position you want to delete:); /*请求输入删除操作位置*/ scanf(%d,&i); L=delete(L,i); /*调用单链表删除函数*/ printf(the L

30、inklist after deleted is:n); display(L); /*调用单链表元素输出(遍历)函数*/ printf(please input the position you want to search:); /*请求输入待查找元素的位置*/ scanf(%d,&i); x=search(L,i); /*调用单链表查找函数*/ if (x) /*如果查找成功，则显示第i个元素的值，否则显示第i个元素不存在*/ printf( the %dth elem is %dn,i,x); else printf( the %dth elem is not exsitn);数据结构实

31、验报告实验序号：3 实验项目名称：顺序栈学号姓名罗维卿专业、班12物联网实验地点5指导教师实验时间2014-4-14一、实验目的及要求1. 掌握栈的存储结构的表示和实现方法。二、实验设备（环境）及要求微型计算机；windows 操作系统；Microsoft Visual Studio 6.0集成开发环境。三、实验内容与步骤1）根据输入的栈中元素个数n和各元素值建立一个顺序栈，并输出栈中各元素值。2）将数据元素e入栈，并输出入栈后的顺序栈中各元素值。3）将顺序栈中的栈顶元素出栈，并输出出栈元素的值和出栈后顺序栈中各元素值四、实验结果与数据处理。五、分析与讨论顺序栈的使用主要理解top为何不用数组

32、定义六、教师评语签名：日期：成绩附源程序清单：#define MAXSIZE 100; /*顺序栈的最大长度*/typedef struct Selemtype baseMAXSIZE; /*存储栈中数据元素的数组*/ int top; /*top为栈顶指针，它指示栈顶元素的存储空间的下一个存储单元*/ Sqstack;Sqstack Push(Sqstack S,int e) if (S.top=MAXSIZE) /判断栈满 printf(Stack is Overflown); else S.baseS.top+=e; /访问S结构体的base这个数组成员的下标为top的数组元素,并在完成

33、后top加一 return S;Sqstack Pop(Sqstack S.int *e) /出栈函数操作 if (S.top=0) printf(Stack is Emptyn); /判断栈空 else *e=S.base-s.top; /访问并转移top指向 return S;void Stack _display(Sqstack S) /输出函数int i; for(i=0; iS.top; i+) /依次输出栈中元素的值，栈顶元素在表的尾部 printf(%4d, S.basei); printf(n);main() Sqstack S; int i,j,n,x,e; printf(please input the length:); /输入栈中元素个数 scanf(%d,&n); printf(please input the Value:n ); /