数据结构实验报告全套汇编.doc

《数据结构实验报告全套汇编.doc》由会员分享，可在线阅读，更多相关《数据结构实验报告全套汇编.doc（33页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

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

2、态分配内存空间typedef int elemtype;/定义数据域的类型typedef struct linknode/定义结点类型 elemtype data;/定义数据域 struct linknode *next;/定义结点指针nodetype;2）创建单链表nodetype *create()/建立单链表，由用户输入各结点data域之值，/以0表示输入结束 elemtype d;/定义数据元素d nodetype *h=NULL,*s,*t;/定义结点指针 int i=1; cout建立一个单链表endl; while(1) cout 输入第 i d; if(d=0) break;/

3、以0表示输入结束 if(i=1)/建立第一个结点 h=(nodetype*)malloc(sizeof(nodetype);/表示指针h h-data=d;h-next=NULL;t=h;/h是头指针 else/建立其余结点 s=(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输出一个单链

4、表:endl ; if(p=NULL)cout空表; while(p!=NULL) coutdatanext; coutnext;i+; return i;5）寻找第i个节点nodetype *find(nodetype *h,int i)/返回第i个节点的指针 nodetype *p=h; int j=1; if(ilen(h)|i=0) return NULL;/i上溢或下溢c else while (p!=NULL&jnext; return p; 6）单链表的插入操作nodetype *ins(nodetype *h,int i,elemtype x)/在单链表head中第i个节点/（

5、i=0）之后插入一个data域为x的节点 nodetype *p,*s; s=(nodetype*)malloc(sizeof(nodetype);/创建节点s s-data=x;s-next=NULL; if(i=0)/i=0:s作为该单链表的第一个节点 s-next=h;h=s; else p=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 *p=h, *s; int j

6、=1; if(i=1)/删除第1个节点 h=h-next;free(p); else p=find(h,i-1);/查找第i-1个节点，并由p指向该节点 if(p!=NULL&p-next!=NULL) s=p-next;/s指向要删除的节点 p-next=s-next; free(s); else cout输入i的值不正确next; if(pb=NULL)/只有一个节点的情况 free(pa); else while (pb!=NULL)/有两个及以上节点的情况 free(pa);pa=pb;pb=pb-next; free(pa); 9)主程序模块:#includeslink.h/包含头文

7、件slinkvoid main() nodetype *head;/定义节点指针变量 head=create();/创建一个单链表 disp(head);/输出单链表 cout单链表长度:len(head)endl; ins(head, 2,0);/在第二个节点之后插入以0为元素的节点 disp(head);/输出新链表 del(head,2);/删除第二个节点 disp(head);/输出新链表5实验结果建立一个单链表：输入第1结点data域值：1输入第2结点data域值：2输入第3结点data域值：3输入第4结点data域值：4输入第5结点data域值：5输入第6结点data域值：6输入第

8、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.实验目的掌握顺序栈的基本操作：初始化栈、判栈空否、入栈、出栈、取栈顶数据元素等运算以及程序实现方法。2.实验要求（1） 认真阅读和掌握和本实验相关的教材内容。（2） 分析问题的要求，编写和调试完成程序。（3） 保存和打印出程序的运行结果，并分析程序的运行结果。3.实验内容利用栈的基本操作实现一个判断算术

9、表达式中包含圆括号、方括号是否正确配对的程序。具体完成如下：（1） 定义栈的顺序存取结构。（2） 分别定义顺序栈的基本操作（初始化栈、判栈空否、入栈、出栈等）。（3） 定义一个函数用来判断算术表达式中包含圆括号、方括号是否正确配对。其中，括号配对共有四种情况：左右括号配对次序不正确；右括号多于左括号；左括号多于右括号；左右括号匹配正确。（4） 设计一个测试主函数进行测试。（5） 对程序的运行结果进行分析。实验代码：#include #define MaxSize 100typedef struct int dataMaxSize; int top;SqStack;void InitStack(

10、SqStack *st) /初始化栈 st-top=-1;int StackEmpty(SqStack *st) /判断栈为空 return (st-top=-1);void Push(SqStack *st,int x) /元素进栈 if(st-top=MaxSize-1) printf(栈上溢出!n); else st-top+; st-datast-top=x; void Pop(SqStack *st) /退栈 if(st-top=-1) printf(栈下溢出n); else st-top-;int Gettop(SqStack *st) /获得栈顶元素 if(st-top=-1)

11、printf(栈空n); return 0; else return st-datast-top;void Display(SqStack *st) /打印栈里元素 int i; printf(栈中元素：); for(i=st-top;i=0;-i) printf(%d ,st-datai); printf(n);int main() /测试 SqStack L; SqStack *st=&L; InitStack(st); printf(栈空：%dn,StackEmpty(st); for(int i=1;i10;+i) Push(st,i); Display(st); printf(退一次

12、栈n); Pop(st); printf(栈顶元素:%dn,Gettop(st); Pop(st); Display(st); return 0;实验结果：实验三 串的基本操作和简程序1 实验目的掌握串基本操作：初始化、联接、替换、子串等运算在堆分配存储储结构上的程序设计方法。2 实验要求（1） 认真阅读和掌握和本实验相关的教材内容。（2） 认真阅读和掌握本章相关内容的算法并设计程序序。（3） 上机运行程序。（4） 保存和打印出程序的运行结果，并结合程序进行分析。实验代码：#include#define MaxSize 50typedef struct char dataMaxSize; /存

13、放字符串 int length; /字符串长度SqString;/将一个字符串常量赋给串svoid StrAssign(SqString &s,char cstr) int i; for(i=0;cstri!=0;i+) /这个0代表字符串结束标志,编译系统自动加上的 s.datai=cstri; s.length=i;/字符串的复制void StrCopy(SqString &s,SqString t) int i; for(i=0;it.length;i+) s.datai=t.datai; s.length=t.length; printf(字符串复制成功了n);/判断字符串是否相等vo

14、id StrEqual(SqString s,SqString t) int i,same=1; if(s.length!=t.length) same=0; else for(i=0;is.length;i+) if(s.datai!=t.datai) same=0; break; if(same=0) printf(这两个字符串不相等n); else printf(这两个字符串相等n);/字符串的长度void StrLength(SqString s) printf(此字符串长度为：%dn,s.length); /合并字符串SqString Concat(SqString s,SqStri

15、ng t) SqString str; int 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;/求子字符串void SubStr(SqString s,int i,int j) SqString str; int k; str.length=0; if(is.length|js.length) printf(子字符串复制失败n); for(k=i-1;ki+j-1;k+)

16、str.datak-i+1=s.datak; str.length=j; printf(子字符串复制成功 长度为：%dn,j); printf(下面输出此子字符串：n); for(i=0;ij;i+) printf(%c,str.datai); printf(n);/插入字符串SqString InserStr(SqString s1,int i,SqString s2) int j; SqString str; str.length=0; if(is1.length+1) printf(字符串插入失败n); return str; for(j=0;ji-1;j+) str.dataj=s1.

17、dataj; for(j=0;js2.length;j+) str.datai-1+j=s2.dataj; for(j=i-1;js1.length;j+) str.datas2.length+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(is.length|i+js.length+1) pr

18、intf(字符串删除失败n); return str; for(k=0;ki-1;k+) str.datak=s.datak; for(k=i+j-1;ks.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(is.length|i+j-1s.length)

19、printf(字符串替换失败了n); for(k=0;ki-1;k+) str.datak=s.datak; for(k=0;kt.length;k+) str.datai+k-1=t.datak; for(k=i+j-1;k0) printf(下面输出这个字符串n); for(i=0;is.length;i+) printf(%c,s.datai); printf(n); else printf(目前空字符串 无法输出n);void main() SqString s; char a=wen xian liang; /字符串常量a StrAssign(s,a); DispStr(s); St

20、rLength(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(下面判断字符串s1和字符串s是否相等n); StrEqual(s,s1); printf(下面将字符串s1和字符串s合并一起n); SqString str; str=Concat(s,s1); /合并字符串 DispStr(str); StrLength(str); SubS

21、tr(str,22,7); /求子字符串 str=DeleStr(str,15,4); /删除字符串 DispStr(str); StrLength(str); printf(请插入一个字符串s2n); scanf(%s,s2.data); StrAssign(s2,s2.data); str=InserStr(str,15,s2); /插入字符串 DispStr(str); StrLength(str); printf(顺序字符串的基本运算到此结束了n);实验结果：实验四 编程建立二叉树，对树进行插入删除及遍历的程序1.实验目的（1） 进一步掌握指针变量的用途和程序设计方法。（2） 掌握二叉

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

23、pedef struct bitnode char data; struct bitnode *lchild,*rchild;binode,*bitree;void createbitree(bitree *T) char ch; cinch; if(ch=0)(*T)=NULL; else(*T)=new bitnode;(*T)-data=ch;createbitree(&(*T)-lchild);createbitree(&(*T)-rchild);void inorderout(bitree T) if(T)inorderout(T-lchild);coutdatarchild);vo

24、id postorder(bitree T) if(T)postorder(T-lchild);postorder(T-rchild);coutdatalchild=NULL&bt-rchild=NULL)return 1; return (countleaf(bt-lchild)+countleaf(bt-rchild);void main() bitree bt; createbitree(&bt); inorderout(bt); cout endl; postorder(bt); countleaf(bt);实验五 建立有序表并进行折半查找1. 实验目的掌握递归算法求解问题的基本思想和

25、程序实现方法。2实验要求（1）认真阅读和掌握本实验的算法思想。（2）编写和调试完成程序。（3）保存和打印程序的运行结果，并对运行结果进行分析。3.实验内容（1） 分析掌握折半查找算法思想，在此基础上，设计出递归算法和循环结构两种实现方法的折半查找函数。（2） 编写程序实现：在保存于数组的1000个有序数据元素中查找数据元素x是否存在。数据元素x要包含两种情况：一种是数据元素x包含在数组中；另一种是数据元素x不包含在数组中（3） 数组中数据元素的有序化既可以初始赋值时实现，也可以设计一个排序函数实现。（4） 根据两种方法的实际运行时间，进行两种方法时间效率的分析对比。实验代码：#include#

26、include#define MAX_LENGTH 100typedef int KeyType; typedef structint key;ElemType; typedef structElemType elemMAX_LENGTH; / 0号单元空出 int length;SSTable;int Search_Bin(SSTable 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 m

27、id; else if(keyST.elemmid.key) high = mid-1; else low=mid+1; return 0;void main()int i,result;SSTable ST;KeyType key;printf(please 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_B

28、in(ST,key);if(result=0)printf(Dont findn);elseprintf(Find the key,the position is %dn,result);实验结果：实验六建立一组记录并进行插入排序1. 实验目的（1） 掌握插入排序算法的思想。（2） 掌握顺序队列下插入排序算法的程序设计方法。2. 实验要求（1） 认真阅读和掌握教材中插入排序算法的思想。（3） 编写基于顺序队列的插入排序排序算法并上机实现。3. 实验内容（1） 编写基于顺序队列的插入排序函数。（2） 设计一个测试主函数，实现对基于顺序队列结构的插入排序算法的测试。（3） 分析程序的运行结果。实验

29、代码：#include#include#define MAXSIZE 100typedef struct int key;sortkey;typedef struct sortkey elemMAXSIZE; int length;sortelem;void InsertSort(sortelem *p) int i,j; for(i=2;ilength;i+) if(p-elemi.keyelemi-1.key)/*小于时，需将elemi插入有序表*/ p-elem0.key=p-elemi.key; /*为统一算法设置监测*/ for(j=i-1;p-elem0.keyelemj.key;

30、j-) p-elemj+1.key=p-elemj.key;/*记录后移*/ p-elemj+1.key=p-elem0.key; /*插入到正确位置*/ void main() sortelem *p;int i;int b6=45,23,54,6,4,46;p=(sortelem *)malloc(sizeof(sortelem);p-length=0;for(i=1;ielemi.key=bi-1; p-length+;InsertSort(p);for(i=1;ielemi.key);system(pause);实验结果：实验七 建立一组记录并进行快速排序1. 实验目的（1） 掌握快速

31、排序算法的思想。（2） 掌握顺序队列下快速排序算法的程序设计方法。2. 实验要求（1） 认真阅读和掌握教材中快速排序算法的思想。（3） 编写基于顺序队列的快速排序排序算法并上机实现。3. 实验内容（1） 编写基于顺序队列的快速排序函数。（2） 设计一个测试主函数，实现对基于顺序队列结构的快速排序算法的测试。（3） 分析程序的运行结果。实验代码：#includevoid quick_sort(int a,int low, int high) int i,j,pivot; if (low high) pivot = alow; i = low; j = high; while (i j) /从顶端

32、开始比较值，如果小于标准值，停止 while (i = pivot) j-; /将比pivot小的元素移到低端，下标加加 if (i j) ai+ = aj; /从底端开始比较值，如果大于标准值，停止 while (i j & ai = pivot) i+; /将比pivot大的元素移到顶端，下标减减 if (i j) aj- = ai; /pivot移动到最终位置 ai = pivot; /对左区间进行递归排序 quick_sort(a, low, i-1); /对右区间进行递归排序 quick_sort(a, i+1, high); void print_array(int a, int n) for(int i = 0; i n; i+) cout ai ,; int main() int data9 = 54,38,96,23,15,72,60,45,83; quick_sort(data, 0, 8); print_array(data,9); return 0; 实验结果：