数据结构实验报告全集

1、.wd.wd.wd.数据构造实验报告全集实验一 线性表 基本操作和简单程序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;/以0表示输

3、入完毕 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输出一个单链表:endl

4、 ; 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个节点/i=0之后插入一个

5、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=1; if(i=1)

6、/删除第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/包含头文件slinkvoid

7、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输入第7结点data域值：7

8、输入第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(SqStack *st) /初始化栈 st-top=

10、-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) printf(栈空n); return 0; els

11、e 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(退一次栈n); Pop(st); printf(栈顶元素:

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

13、/将一个字符串常量赋给串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);/判断字符串是否相等void StrEqual(SqString s,SqString

14、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,SqString t) SqString str; int i; str.l

15、ength=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+) str.datak-i+1=s.datak; str.lengt

16、h=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.dataj; for(j=0;js2.length;j+) st

17、r.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) printf(字符串删除失败n); return str; for(

18、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) printf(字符串替换失败了n); for(k=0;ki-1;

19、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); StrLength(s); SqString s1,s2,t; /s

20、1是待复制的字符串变量 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); SubStr(str,22,7); /求子字符串 str=DeleStr

21、(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 掌握二叉树的构造特征，以及链式存储构造的特点及程序设计方法。3 掌握构造二叉树

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

23、d,*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);void postorder(bitree T) if(T)postorder(T-lchild);posto

24、rder(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. 实验目的掌握递归算法求解问题的 基本思想和程序实现方法。2实验要求1认真阅读和掌握本实验的算法思想。2编写和调试完成程序。3保存和打印程序的运行结

25、果，并对运行结果进展分析。3.实验内容1 分析掌握折半查找算法思想，在此根基上，设计出递归算法和循环构造两种实现方法的折半查找函数。2 编写程序实现：在保存于数组的1000个有序数据元素中查找数据元素x是否存在。数据元素x要包含两种情况：一种是数据元素x包含在数组中；另一种是数据元素x不包含在数组中3 数组中数据元素的有序化既可以初始赋值时实现，也可以设计一个排序函数实现。4 根据两种方法的实际运行时间，进展两种方法时间效率的分析比照。实验代码：#include#include#define MAX_LENGTH 100typedef int KeyType; typedef structin

26、t 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 mid; else if(keyST.elemmid.key) high = mid-1; else low=mid+1; return

27、 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_Bin(ST,key);if(result=0)printf(Dont findn);elseprintf(Find the key,t

28、he position is %dn,result);实验结果：实验六建设一组记录并进展插入排序1. 实验目的1 掌握插入排序算法的思想。2 掌握顺序队列下插入排序算法的程序设计方法。2. 实验要求1 认真阅读和掌握教材中插入排序算法的思想。3 编写基于顺序队列的插入排序排序算法并上机实现。3. 实验内容1 编写基于顺序队列的插入排序函数。2 设计一个测试主函数，实现对基于顺序队列构造的插入排序算法的测试。3 分析程序的运行结果。实验代码：#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;j-) p-elemj+1.key=p-elemj.key;/*记录后移*/ p-elemj+1.key=p-elem0.key; /*插入