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

数据结构实验报告实验序号：5 实验项目名称：链式栈学号姓名罗维卿专业、班12物联网实验地点指导教师实验时间一、实验目的及要求1. 掌握栈的存储结构的表示和实现方法。二、实验设备（环境）及要求微型计算机；windows 操作系统；Microsoft Visual Studio 6.0集成开发环境。三、实验内容与步骤（1）根据输入的栈中元素个数和各元素值建立一个链栈，并输出链栈中各元素值, 观察输入的内容与输出的内容是否一致,特别注意栈顶元素的位置。（2）将数据元素x入栈，并输出入栈后的链栈中各元素值。（3）将链栈中的栈顶元素出栈，并输入出栈元素的值和出栈后链栈中各元素值。四、实验结果与数据处理五、分析与讨论对上机实践结果进行分析，上机的心得体会。六、教师评语签名：日期：成绩附源程序清单：1实验要求编程实现如下功能：（1）根据输入的栈中元素个数n和各元素值建立一个顺序栈，并输出栈中各元素值。（2）将数据元素e入栈，并输出入栈后的顺序栈中各元素值。（3）将顺序栈中的栈顶元素出栈，并输出出栈元素的值和出栈后顺序栈中各元素值。2. 实验相关原理：栈是一种插入和删除操作都限制在表的一端进行的特殊线性表，它的操作具有“先进后出”的特性。采用顺序存储结构的栈称为顺序栈。栈的存储结构描述如下：#define MAXSIZE 100; /*顺序栈的最大长度*/typedef struct Selemtype baseMAXSIZE; /*存储栈中数据元素的数组*/ int top; /*top为栈顶指针，它指示栈顶元素的存储空间的下一个存储单元*/ Sqstack;【核心算法提示】 1顺序栈入栈操作的基本步骤：首先判断顺序栈是否为满，如果满，则函数返回ERROR，否则将待入栈的数据元素存放在top所指示的存储单元中，再使top后移一个存储单元位置，即将top值加1，最后函数返回OK。2 顺序栈出栈操作的基本步骤：首先判断顺序栈是否为空，如果空，则函数返回ERROR，否则将栈顶指针前移一个存储单元位置，即将top值减1,再将top所指示的栈顶元素用e返回其值，并使函数返回OK。【核心算法描述】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-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 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; i<S.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 ");/*请求输入顺序栈中各个元素值*/ for(i=0;i<n;i+) scanf("%d",&S.basei); S.top=n; printf("the stack is:n"); Stack_display(S); printf("please input the insert node:");/*请求输入需要入栈的新元素*/ scanf("%d",&x); S=Push(S,x); printf("the stack after push is:n");/*提示输出入栈后栈中各个元素值*/ Stack_display(S); /*调用顺序栈的输出函数*/ S=Pop(S,&e); printf("the pop value is:%dn",e); /*输出出栈元素的值*/ printf("the stack after pop is:n");/*提示输出出栈后栈中各个元素值*/ Stack_display(S); /*调用顺序栈的输出函数*/ （1）根据输入的栈中元素个数和各元素值建立一个链栈，并输出链栈中各元素值, 观察输入的内容与输出的内容是否一致,特别注意栈顶元素的位置。（2）将数据元素x入栈，并输出入栈后的链栈中各元素值。（3）将链栈中的栈顶元素出栈，并输入出栈元素的值和出栈后链栈中各元素值。 核心算法提示采用链式存储结构的栈称为链栈，链栈的存储结构描述如下： typedef struct Snode Selemtype data;/*数据域*/ struct Snode *next;/*指针域*/SNODE,* LinkStack;/*其中SNODE为链栈中的结点类型名, LinkStack为指向结点的指针类型名*/如果栈中元素序列为a1,a2，,an，则链栈的存储结构如下图3-1所示：an-1anan-2a1 top图3-2： 链栈的存储结构示意图从图3-1可看出，栈的链式存储结构与单链表的存储结构相同，所有在链栈上进行入栈和出栈操作与单链表上的插入和删除操作的主要步骤相同。只不过要特别注意以下几点：（1）链栈中无需加头结点。（2）链栈中的指针是指向栈中元素序列的前驱结点。（3）链栈中的入栈和出栈操作都是在链表的表头进行。 核心算法描述status Push(LinkStack &top,int e) /*将数据元素e压入到链栈top中，使其成为新的栈项元素*/ LinkStack p; p=(LinkStack)malloc(sizeof(SNODE); /*生成一个新的结点*/ if (!p) /*如果分配空间失败，则函数返回"OVERFLOW"*/ return OVERFLOW; p->data=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; /*将被删的栈顶元素的值保存在e中*/ q=top; /*用q记下待删的栈顶元素*/top=q->next; /*修改链使待删结点从链中“卸下”，此时被删结点的后继成为新的栈顶元素结点*/ free(q); /*释放被删结点的存储空间*/ return OK;数据结构实验报告实验序号：7 实验项目名称：串学号31姓名罗维卿 专业、班12物联网实验地点指导教师实验时间一、实验目的及要求1. 掌握串的顺序表示和堆表示实现方法；二、实验设备（环境）及要求微型计算机；windows 操作系统；Microsoft Visual Studio 6.0集成开发环境。三、实验内容与步骤1、 根据串的三种实现方式，顺序、堆和链，选择其中一种分别实现串赋值、串合并、删除等操作。四、实验结果与数据处理五、分析与讨论对上机实践结果进行分析，上机的心得体会。六、教师评语签名：日期：成绩附源程序清单：#include<iostream.h>#include<stdio.h>#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,SqString t)int i;for(i=0;i<t.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;i<s.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;int i;str.length=s.length+t.length;for(i=0;i<s.length;i+)str.datai=s.datai;for(i=0;i<t.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(i<=0|i>s.length|j<0|i+j-1>s.length)cout<<"参数错误n"<<endl;return str;for(k=i-1;k<i+j-1;k+)str.datak-i+1=s.datak;str.length=j;return str;SqString InsStr(SqString s1,int i,SqString s2)int j;SqString str;str.length=0;if(i<=0|i>s1.length+1)cout<<"参数错误n"<<endl;return s1;for(j=0;j<i-1;j+)str.dataj=s1.dataj;for(j=0;j<s2.length;j+)str.datai+j-1=s2.dataj;for(j=i-1;j<s1.length;j+)str.length=s1.length+s2.length;return str;SqString DelStr(SqString s,int i,int j)int k;SqString str;str.length=0;if(i<=0|i>s.length|i+j>s.length+1)/参数不正确时返回空串printf("参数不正确n");return str;for(k=0;k<i-1;k+) /将s.data0.i-2复制到strstr.datak=s.datak;for(k=i+j-1;k<s.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,int i,int j, SqString t)/将串s的第i个字符开始的j个字符替换成串t产生新串int k;SqString str;str.length=0;if(i<=0|i>s.length|i+j-1>s.length)/参数不正确时返回空串printf("参数不正确n");return str;for(k=0;k<i-1;k+) /将s.data0.i-2复制到strstr.datak=s.datak;for(k=0;k<t.length;k+)str.datai+k-1=t.datak;for(k=i+j-1;k<s.length;k+)/将s.datai+j-1.s.length-1复制到strstr.datat.length+k-j=s.datak;str.length=s.length-j+t.length;return str;void DispStr(SqString s) /输出串s的所有元素int i;if(s.length>0)for(i=0;i<s.length;i+)printf("%c",s.datai);printf("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);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 实验项目名称：线性表学号姓名罗维卿专业、班12物联网实验地点1-516指导教师实验时间2014-3-17一、实验目的及要求1. 掌握线性表的顺序存储结构表示和实现方法；2. 掌握顺序表基本操作的算法实现；3了解顺序表的应用。二、实验设备（环境）及要求微型计算机；windows 操作系统；Microsoft Visual Studio 6.0集成开发环境。三、实验内容与步骤1、 根据输入顺序表的长度n和各数据元素建立顺序表，并输出顺序表中各元素值，观察输入的内容和输出的内容是否一致。2、在顺序表的第i个元素之前插入一值为x的元素，并输出插入后的顺序表中各元素值。3、删除顺序表中第i个元素，并输出删除后的顺序表中各元素值。4、在顺序表中查找第i个元素，如果成功就显示“查找成功”及位置，否则显示“查找失败”。四、实验结果与数据处理五、分析与讨论六、教师评语签名：日期：成绩附源程序清单： #include <stdio.h>#define MAXLEN 50 typedef structint elemMAXLEN; int length;Sqlist; Sqlist Sqlist_insert(Sqlist L,int i,int x) /*顺序表插入函数*/ int j; if(i<1|i>L.length+1) printf("ERROR!"); else if(L.length>=MAXLEN) printf("OLERFLOW!"); 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(i<1|i>L.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; for (i=0;i<L.length&&L.elemi!=x;i+); if (i<L.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");/*请求输入顺序表中各个元素*/ 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);/*调用顺序表删除函数*/ 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 实验项目名称：单链表学号姓名罗维卿专业、班12物联网实验地点指导教师实验时间2014-3-24一、实验目的及要求1. 建立单链表，并在单链表上实现插入、删除和查找操作（验证性内容）。二、实验设备（环境）及要求微型计算机；windows 操作系统；Microsoft Visual Studio 6.0集成开发环境。三、实验内容与步骤1、根据输入的一系列整数，以0标志结束，用头插法建立单链表，并输出单链表中各元素值，观察输入的内容与输出的内容是否一致。2、在单链表的第i个元素之前插入一个值为x的元素，并输出插入后的单链表中各元素值。3、删除单链表中第i个元素，并输出删除后的单链表中各元素值。4、在单链表中查找第i个元素，如果查找成功，则显示该元素的值，否则显示该元素不存在。四、实验结果与数据处理五、分析与讨论对上机实践结果进行分析，上机的心得体会。六、教师评语签名：日期：成绩附源程序清单：#include <stdio.h>#include <malloc.h>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 node(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&&j<i-1) p=p->next; +j; if (p=NULL|j>i-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&&j<i-1) p=p->next; +j; if(p->next=NULL|j>i-1) printf("n ERROE position!n"); else q=p->next; p->next=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&& j<i) p=p->next; j+; if (!p&& j>i) return 0; /*如果i值不合法，即i值小于1或大于表长，则函数返回0值*/ else return(p->data); /*否则函数返回第i个元素的值*/void display(Linklist L) /*单链表元素输出函数*/ 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 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 Linklist 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");数据结构实验报告实验序号：3 实验项目名称：顺序栈学号姓名罗维卿专业、班12物联网实验地点5指导教师实验时间2014-4-14一、实验目的及要求1. 掌握栈的存储结构的表示和实现方法。二、实验设备（环境）及要求微型计算机；windows 操作系统；Microsoft Visual Studio 6.0集成开发环境。三、实验内容与步骤1）根据输入的栈中元素个数n和各元素值建立一个顺序栈，并输出栈中各元素值。2）将数据元素e入栈，并输出入栈后的顺序栈中各元素值。3）将顺序栈中的栈顶元素出栈，并输出出栈元素的值和出栈后顺序栈中各元素值四、实验结果与数据处理。五、分析与讨论顺序栈的使用主要理解top为何不用数组定义六、教师评语签名：日期：成绩附源程序清单：#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的数组元素,并在完成后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; i<S.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 "); /