数据结构实验报告全集_第1页
数据结构实验报告全集_第2页
数据结构实验报告全集_第3页
数据结构实验报告全集_第4页
数据结构实验报告全集_第5页
已阅读5页，还剩19页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

1、1 / 25数据结构实验报告全集实验一 线性表基本操作和简单程序1 实验目的1 掌握使用 Visual C+ 6.0上机调试程序的基本方法；2 掌握线性表的基本操作：初始化、插入、删除、取数据元素等运算在顺序存储结构和链表存储结构上的程序设计方法。2 实验要求1 认真阅读和掌握和本实验相关的教材内容。2 认真阅读和掌握本章相关内容的程序。3 上机运行程序。4 保存和打印出程序的运行结果 , 并结合程序进行分析。5 按照你对线性表的操作需要 , 重新改写主程序并运行 ,打印出文件清单和运行结果实验代码：头文件库头文件 动态分配内存空间定义数据域的类型定义结点类型定义数据域定义结点指针1 头文件模

2、块#include iostream.h>/ #include<malloc.h>/ typedef int elemtype;/ typedef struct linknode/ elemtype data;/struct linknode *next;/ nodetype;2 创建单链表nodetype *create<>/ 建立单链表 , 由用户输入各结点 data 域之值 , / 以 0 表示输入结束elemtype d;/定义数据元素 dnodetype *h=NULL,*s,*t;/ 定义结点指针 int i=1;cout<<"

3、建立一个单链表 "<<endl;while<1>输入第 "<< i <<" 结点 data 域值：cout <<"cin >> d;if<d=0> break;/ 以 0 表示输入结束if<i=1>/ 建立第一个结点 h=<nodetype*>malloc<sizeof<nodetype>>/ 表示指针 h h->data=d;h->next=NULL;t=h;/h 是头指针else/ 建立其余结点 s=<

4、nodetype*> malloc<sizeof<nodetype>> s->data=d;s->next=NULL;t->next=s;t=s;/t 始终指向生成的单链表的最后一个节点i+;return h;3 输出单链表中的元素void disp<nodetype*h>/ 输出由 h 指向的单链表的所有 data 域之值 nodetype *p=h;cout<<" 输出一个单链表 :"<<endl<<" " if<p=NULL>cout<

5、<" 空表 "while<p!=NULL>cout<<p->data<<" "p=p->next;cout<<endl;4 计算单链表的长度int len<nodetype *h>/返回单链表的长度int i=0;nodetype *p=h;while<p!=NULL> p=p->next;i+;return i;5 寻找第 i 个节点nodetype *find<nodetype *h,int i>/返回第 i 个节点的指针nodetype *p

6、=h;int j=1;if<i>len<h>|i<=0>return NULL;/i 上溢或下溢 celsewhile <p!=NULL&&j<1>/ 查找第 i 个节点 , 并由 p 指向该节点 j+;p=p->next;return p;6 单链表的插入操作nodetype *ins<nodetype *h,int i,elemtype x>/ 在单链表 head 中第 i 个节点 / i>=0 之后插入一个 data 域为 x 的节点nodetype *p,*s;s=<nodetype*&

7、gt;malloc<sizeof<nodetype>>/ 创建节点 s s->data=x;s->next=NULL;if<i=0>/i=0:s 作为该单链表的第一个节点s->next=h;h=s;elsep=find<h,i>/ 查找第 i 个节点 , 并由 p 指向该节点if<p!=NULL>s->next=p->next;p->next=s;return h;7 单链表的删除操作nodetype *del<nodetype *h,int i>/ 删除第 i 个节点nodetype

8、*p=h, *s;int j=1;if<i=1>/ 删除第 1 个节点h=h->next;free<p>elsep=find<h,i-1>/ 查找第 i-1 个节点 , 并由 p 指向该节点3 / 25if<p!=NULL&&p->next!=NULL>s=p->next;/s 指向要删除的节点 p->next=s->next;free<s>else cout<<" 输入 i 的值不正确 "<<endl;return h;8 释放节点空间void

9、 dispose<nodetype *h>/ 释放单链表的所有节点占用的空间 nodetype *pa=h,*pb;if<pa!=NULL>pb=pa->next;if<pb=NULL>/ 只有一个节点的情况 free<pa>else有两个及以上节点的情况while <pb!=NULL>/free<pa>pa=pb;pb=pb->next;free<pa>包含头文件 slink定义节点指针变量创建一个单链表9>主程序模块 :#include"slink.h"/ void m

10、ain<>nodetype *head;/ head=create<>/disp<head>/ 输出单链表cout<<" 单链表长度 :"<<len<head><<endlins<head, 2,0>/ 在第二个节点之后插入以 0 为元素的节点 disp<head>/ 输出新链表del<head,2>/ 删除第二个节点 disp<head>/ 输出新链表5实验结果建立一个单链表： 输入第 1 结点 data 域值： 1输入第 2 结点 data

11、 域值： 2输入第 3 结点 data 域值： 3输入第 4 结点 data 域值： 4输入第 5 结点 data 域值： 5输入第 6 结点 data 域值： 6输入第 7 结点 data 域值： 7输入第 8 结点 data 域值： 8输入第 9 结点 data 域值： 9输入第 10 结点 data 域值 0： 输出一个单链表：1 2 3 4 5 6 7 8 9 单链表长度： 9 输出一个单链表：1 0 2 3 4 5 6 7 8 9输出一个单链表：1 2 3 4 5 6 7 8实验二 顺序栈的实现1. 实验目的掌握顺序栈的基本操作：初始化栈、判栈空否、入栈、出栈、取栈顶数据元素等运算以

12、及程序实现方法。2. 实验要求1 认真阅读和掌握和本实验相关的教材内容。2 分析问题的要求 ,编写和调试完成程序。3 保存和打印出程序的运行结果 , 并分析程序的运行结果。3. 实验内容利用栈的基本操作实现一个判断算术表达式中包含圆括号、方括号是否正确配对的程序。具体完成如下：1 定义栈的顺序存取结构。2 分别定义顺序栈的基本操作初始化栈、判栈空否、入栈、出栈等。3 定义一个函数用来判断算术表达式中包含圆括号、方括号是否正确配对。其中, 括号配对共有四种情况：左右括号配对次序不正确； 右括号多于左括号； 左括号多于右括号； 左右 括号匹配正确。4设计一个测试主函数进行测试。5对程序的运行结果进

13、行分析。 实验代码：#i nclude vstdio.h >#defi ne MaxSize 100 typedef structint dataMaxSize;int top;SqStack;void In itStackvSqStack *st> /初始化栈st->top=-1;int StackEmptyvSqStack *st> / 判断栈为空retur n <st->top=-1>void PushvSqStack *st,i nt x> / 元素进栈 if<st->top=MaxSize-1>printf<&q

14、uot;栈上溢出!n">elsest->top+; st->datast->top=x;void PopvSqStack *st> / 退栈if<st->top=-1> printfv"栈下溢出 n">elsest->top-;int GettopvSqStack *st> / 获得栈顶元素if<st->top=-1>prin tf<"栈空 n">return 0;elsereturn st->datast->top;void Displ

15、ayvSqStack *st> /打印栈里元素int i;printfv"栈中元素：">for<i=st->top;i>=0;-i>prin tf<"%d ",st->datai>prin tf<"n">int mai n<> / 测试SqStack L;SqStack *st=&L;In itStack<st>printf<"栈空：dn",StackEmpty<st>>forvint i=1;

16、i<10;+i>Push<st,i>Display<st>printfv"退一次栈 n">Pop<st>printf<"栈顶元素:%dn",Gettop<st>>Pop<st>Display<st>return 0;实验结果：实验三串的基本操作和简程序1. 实验目的掌握串基本操作：初始化、联接、替换、子串等运算在堆分配存储储结构上的程序设计方法。2. 实验要求1认真阅读和掌握和本实验相关的教材内容。2认真阅读和掌握本章相关内容的算法并设计程序序。3上机运

17、行程序。4保存和打印出程序的运行结果，并结合程序进行分析。实验代码：#include<stdio.h>#define MaxSize 50typedef structchar dataMaxSize; / 存放字符串int length; /字符串长度SqString;/ 将一个字符串常量赋给串 svoid StrAssign<SqString &s,char cstr>int i;for<i=0;cstri!='0'i+> / 这个 '0' 代表字符串结 束标志 , 编译系统自动加上的s.datai=cstri;s.

18、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;printf<" 字符串复制成功了 n">/ 判断字符串是否相等void StrEqual<SqString s,SqString t>int i,same=1;if<s.length!=t.length> same=0;elsefor<i=0;i<s.lengt

19、h;i+> if<s.datai!=t.datai> same=0;break; if<same=0> printf<" 这两个字符串不相等 n">elseprintf<" 这两个字符串相等 n">/ 字符串的长度void StrLength<SqString s>printf<" 此字符串长度为： %dn",s.length>/ 合并字符串SqString Concat<SqString s,SqString t>SqString str;in

20、t 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;/ 求子字符串void 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> printf<

21、;" 子字符串复制失败 n"> for<k=i-1;k<i+j-1;k+> str.datak-i+1=s.datak;str.length=j;printf<" 子字符串复制成功 长度为： %dn",j> printf<" 下面输出此子字符串： n">for<i=0;i<j;i+> printf<"%c",str.datai> printf<"n">/ 插入字符串SqString InserStr<

22、SqString s1,int i,SqString s2> int j;SqString str;str.length=0; if<i<=0|i>s1.length+1> printf<" 字符串插入失败 n">return str;for<j=0;j<i-1;j+>str.dataj=s1.dataj;for<j=0;j<s2.length;j+>str.datai-1+j=s2.dataj;for<j=i-1;j<s1.length;j+> str.datas2.lengt

23、h+j=s1.dataj; str.length=s1.length+s2.length;printf<" 插入字符串成功 长度为： %dn",str.length> return str;/ 删除字符串SqString DeleStr<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<

24、k=0;k<i-1;k+>str.datak=s.datak;for<k=i+j-1;k<s.length;k+>str.datak-j=s.datak;str.length=s.length-j;printf<" 删 除 子 字 符 串 成 功 剩 余 长 度 为： %dn",str.length>return str;/ 替换字符串void RepStr<SqString s,int i,int j,SqString t>int k;SqString str;str.length=0;if<i<=0|i&

25、gt;s.length|i+j-1>s.length>printf<" 字符串替换失败了 n">for<k=0;k<i-1;k+>str.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+>str.datat.length+k-j=s.datak; str.length=s.length-j+t.length;printf<" 替 换 字 符 串 成 功 新 字 符

26、串 长 度 为： %dn",str.length>/ 字符串的输出void DispStr<SqString s>int i;if<s.length>0>printf<" 下面输出这个字符串 n">for<i=0;i<s.length;i+>printf<"%c",s.datai>printf<"n">elseprintf<" 目前空字符串 无法输出 n">void main<>SqStrin

27、g s;字符串常量 achar a="wen xian liang" /StrAssign<s,a>DispStr<s>StrLength<s>SqString s1,s2,t; /s1是待复制的字符串变量printf<" 请输入一个字符串 t:n"> scanf<"%s",t.data>StrAssign<t,t.data>StrCopy<s1,t> / 复制字符串StrLength<s1>DispStr<s1>printf&

28、lt;" 下面判断字符串 s1 和字符串 s 是否相等 n"> StrEqual<s,s1>printf<" 下面将字符串SqString str;s1 和字符串 s 合并一起 n">str=Concat<s,s1> /合并字符串DispStr<str>StrLength<str>SubStr<str,22,7> /求子字符串str=DeleStr<str,15,4> /删除字符串DispStr<str>StrLength<str>print

29、f<" 请插入一个字符串 s2n"> scanf<"%s",s2.data>StrAssign<s2,s2.data>str=InserStr<str,15,s2> / 插入字符串 DispStr<str>StrLength<str>printf<" 顺序字符串的基本运算到此结束了 n"> 实验结果： 实验四 编程建立二叉树 ,对树进行插入删除及遍历的程序1. 实验目的1 进一步掌握指针变量的用途和程序设计方法。2 掌握二叉树的结构特征 , 以及链式存

30、储结构的特点及程序设计方法。3 掌握构造二叉树的基本方法。4 掌握二叉树遍历算法的设计方法。3 实验要求1 认真阅读和掌握和本实验相关的教材内容。2 掌握一个实际二叉树的创建方法。3 掌握二叉链存储结构下二叉树操作的设计方法和遍历操作设计方法。4 实验内容1 定义二叉链存储结构。2 设计二叉树的基本操作初始化一棵带头结点的二叉树、左结点插入、右结点插入、中 序遍历二叉树等。15 / 253 按照建立一棵实际二叉树的操作需要,编写建立二叉树、遍历二叉树的函数。16 / 254 编写测试主函数并上机运行。打印出运行结果 , 并结合程序运行结果进行分析。 实验代码：#include<iostr

31、eam.h>typedef struct bitnodechar data;struct bitnode *lchild,*rchild;binode,*bitree;void createbitree<bitree *T>char ch;cin>>ch;if<ch='0'><*T>=NULL;else<*T>=new bitnode;<*T>->data=ch; createbitree<&<*T>->lchild> createbitree<&am

32、p;<*T>->rchild>void inorderout<bitree T>if<T># / 25inorderout<T->lchild>cout<<T->data<<endl;inorderout<T->rchild>void postorder<bitree T>if<T>postorder<T->lchild>postorder<T->rchild>cout<<T->data<<e

33、ndl;int countleaf<bitree bt>if<!bt>return 0;if<bt->lchild=NULL&&bt->rchild=NULL>return 1;return<countleaf<bt->lchild>+countleaf<bt->rchild>>void main<>bitree bt;createbitree<&bt>inorderout<bt>cout<<" "<&

34、lt;endl;postorder<bt>countleaf<bt>实验五 建立有序表并进行折半查找1. 实验目的 掌握递归算法求解问题的基本思想和程序实现方法。2 实验要求1 认真阅读和掌握本实验的算法思想。 2 编写和调试完成程序。3 保存和打印程序的运行结果 , 并对运行结果进行分析。3. 实验内容1 分析掌握折半查找算法思想 , 在此基础上 ,设计出递归算法和循环结构两种实现方法的 折半查找函数。2 编写程序实现：在保存于数组的 1000 个有序数据元素中查找数据元素 x 是否存在。 数据元素 x 要包含两种情况：一种是数据元素 x 包含在数组中；另一种是数据元

35、素 x 不包 含在数组中3 数组中数据元素的有序化既可以初始赋值时实现, 也可以设计一个排序函数实现。4 根据两种方法的实际运行时间 , 进行两种方法时间效率的分析对比。 实验代码：#include<stdio.h>#include<stdlib.h>#define MAX_LENGTH 100typedef int KeyType;typedef structint key;ElemType;typedef structElemType elemMAX_LENGTH;/ 0 号单元空出int length;SSTable;int Search_Bin<SSTab

36、le ST,KeyType key>int low,high,mid;low = 1;high = ST.length; while<low <=high>mid = <low+high>/2;if<key =ST.elemmid.key>return mid;else if<key<ST.elemmid.key> high = mid-1;else low=mid+1;return 0;void main<>int i,result;SSTable ST;KeyType key; printf<"p

37、lease input length:"> scanf<"%d",&ST.length> for<i=1;i<=ST.length;i+> printf<"please input ST.elem:"> scanf<"%d",&ST.elemi> printf<"please input keyword:"> scanf<"%d",&key> result=Search_Bin&

38、lt;ST,key> if<result=0>printf<"Don't findn">elseprintf<"Find the key,the position is %dn",result> 实验结果：实验六建立一组记录并进行插入排序1. 实验目的1 掌握插入排序算法的思想。2 掌握顺序队列下插入排序算法的程序设计方法。2. 实验要求1 认真阅读和掌握教材中插入排序算法的思想。 3 编写基于顺序队列的插入排序排序算法并上机实现。3. 实验内容 1 编写基于顺序队列的插入排序函数。2 设计一个测试主函数

39、 , 实现对基于顺序队列结构的插入排序算法的测试。3 分析程序的运行结果。实验代码：#include<stdio.h>#include<stdlib.h>#define MAXSIZE 100typedef structint key;sortkey;typedef structsortkey elemMAXSIZE;int length;sortelem;void InsertSort<sortelem *p>int i,j;for<i=2;i<=p->length;i+>21 / 25# / 25if<p->elemi.key<p->elemi-1.key>/*p->elem0.key=p->elemi.key; /*小于时 , 需将 elemi为统一算法设置监测 */插入有序表 */# / 25# / 25for<j=i-1;p->elem0.key<p->elemj.key;j->记录后移 */插入到正确位置 */p->elemj+1.key=p->el

人人文库> 全部分类> 行业资料 > 管理策划

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论