数据结构实验报告全集
实验一 线性表基本操作和简单程序
1． 实验目的
（1）掌握使用Visual C++ 6.0上机调试程序的基本方法；
（2）掌握线性表的基本操作：初始化、插入、删除、取数据元素等运算在顺序存储结构和链表存储结构上的程序设计方法。
2． 实验要求
（1） 认真阅读和掌握和本实验相关的教材内容。
（2） 认真阅读和掌握本章相关内容的程序。
（3） 上机运行程序。
（4） 保存和打印出程序的运行结果，并结合程序进行分析。
（5） 按照你对线性表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果
实验代码：
1）头文件模块
#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;//定义数据元素d
nodetype *h=NULL,*s,*t;//定义结点指针
int i=1;
cout<<"建立一个单链表"<<endl;
while(1)
{
cout <<" 输入第"<< i <<"结点data域值：";
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=(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<<"空表";
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=h;
int j=1;
if(i>len(h)||i<=0)
return NULL;//i上溢或下溢c
else
{
while (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*)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)//删除第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的值不正确"<<endl;
}
return h;
}
8）释放节点空间
void 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);
}
}
}
9)主程序模块:
#include"slink.h"//包含头文件slink
void 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结点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.实验内容
利用栈的基本操作实现一个判断算术表达式中包含圆括号、方括号是否正确配对的程序。具体完成如下：
（1） 定义栈的顺序存取结构。
（2） 分别定义顺序栈的基本操作（初始化栈、判栈空否、入栈、出栈等）。
（3） 定义一个函数用来判断算术表达式中包含圆括号、方括号是否正确配对。其中，括号配对共有四种情况：左右括号配对次序不正确；右括号多于左括号；左括号多于右括号；左右括号匹配正确。
（4） 设计一个测试主函数进行测试。
（5） 对程序的运行结果进行分析。
实验代码：
#include <stdio.h >
#define MaxSize 100
typedef struct
{
int data[MaxSize];
int top;
}SqStack;
void InitStack(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->data[st->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;
}
else
return st->data[st->top];
}
void Display(SqStack *st) //打印栈里元素
{
int i;
printf("栈中元素：");
for(i=st->top;i>=0;--i)
printf("%d ",st->data[i]);
printf("\n");
}
int main() //测试
{
SqStack L;
SqStack *st=&L;
InitStack(st);
printf("栈空：%d\n",StackEmpty(st));
for(int i=1;i<10;++i)
Push(st,i);
Display(st);
printf("退一次栈\n");
Pop(st);
printf("栈顶元素:%d\n",Gettop(st));
Pop(st);
Display(st);
return 0;
}
实验结果：
实验三 串的基本操作和简程序
1． 实验目的
掌握串基本操作：初始化、联接、替换、子串等运算在堆分配存储储结构上的程序设计方法。
2． 实验要求
（1） 认真阅读和掌握和本实验相关的教材内容。
（2） 认真阅读和掌握本章相关内容的算法并设计程序序。
（3） 上机运行程序。
（4） 保存和打印出程序的运行结果，并结合程序进行分析。
实验代码：
#include<stdio.h>
#define MaxSize 50
typedef struct
{
char data[MaxSize]; //存放字符串
int length; //字符串长度
}SqString;
//将一个字符串常量赋给串s
void StrAssign(SqString &s,char cstr[])
{
int i;
for(i=0;cstr[i]!='\0';i++) //这个'\0'代表字符串结束标志,编译系统自动加上的
s.data[i]=cstr[i];
s.length=i;
}
//字符串的复制
void StrCopy(SqString &s,SqString t)
{
int i;
for(i=0;i<t.length;i++)
s.data[i]=t.data[i];
s.length=t.length;
printf("字符串复制成功了\n");
}
//判断字符串是否相等
void StrEqual(SqString s,SqString t)
{
int i,same=1;
if(s.length!=t.length)
same=0;
else
{
for(i=0;i<s.length;i++)
if(s.data[i]!=t.data[i])
{
same=0;
break;
}
}
if(same==0)
printf("这两个字符串不相等\n");
else
printf("这两个字符串相等\n");
}
//字符串的长度
void StrLength(SqString s)
{
printf("此字符串长度为：%d\n",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.data[i]=s.data[i];
for(i=0;i<t.length;i++)
str.data[s.length+i]=t.data[i];
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("子字符串复制失败\n");
for(k=i-1;k<i+j-1;k++)
str.data[k-i+1]=s.data[k];
str.length=j;
printf("子字符串复制成功 长度为：%d\n",j);
printf("下面输出此子字符串：\n");
for(i=0;i<j;i++)
printf("%c",str.data[i]);
printf("\n");
}
//插入字符串
SqString InserStr(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.data[j]=s1.data[j];
for(j=0;j<s2.length;j++)
str.data[i-1+j]=s2.data[j];
for(j=i-1;j<s1.length;j++)
str.data[s2.length+j]=s1.data[j];
str.length=s1.length+s2.length;
printf("插入字符串成功 长度为：%d\n",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(k=0;k<i-1;k++)
str.data[k]=s.data[k];
for(k=i+j-1;k<s.length;k++)
str.data[k-j]=s.data[k];
str.length=s.length-j;
printf("删除子字符串成功 剩余长度为：%d\n",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>s.length||i+j-1>s.length)
printf("字符串替换失败了\n");
for(k=0;k<i-1;k++)
str.data[k]=s.data[k];
for(k=0;k<t.length;k++)
str.data[i+k-1]=t.data[k];
for(k=i+j-1;k<s.length;k++)
str.data[t.length+k-j]=s.data[k];
str.length=s.length-j+t.length;
printf("替换字符串成功 新字符串长度为：%d\n",str.length);
}
//字符串的输出
void DispStr(SqString s)
{
int i;
if(s.length>0)
{
printf("下面输出这个字符串\n");
for(i=0;i<s.length;i++)
printf("%c",s.data[i]);
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; //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);
SubStr(str,22,7); //求子字符串
str=DeleStr(str,15,4); //删除字符串
DispStr(str);
StrLength(str);
printf("请插入一个字符串s2\n");
scanf("%s",s2.data);
StrAssign(s2,s2.data);
str=InserStr(str,15,s2); //插入字符串
DispStr(str);
StrLength(str);
printf("顺序字符串的基本运算到此结束了\n");
}
实验结果：
实验四 编程建立二叉树，对树进行插入删除及遍历的程序
1.实验目的
（1） 进一步掌握指针变量的用途和程序设计方法。
（2） 掌握二叉树的结构特征，以及链式存储结构的特点及程序设计方法。
（3） 掌握构造二叉树的基本方法。
（4） 掌握二叉树遍历算法的设计方法。
3． 实验要求
（1）认真阅读和掌握和本实验相关的教材内容。
（2）掌握一个实际二叉树的创建方法。
（3）掌握二叉链存储结构下二叉树操作的设计方法和遍历操作设计方法。
4． 实验内容
（1）定义二叉链存储结构。
（2）设计二叉树的基本操作（初始化一棵带头结点的二叉树、左结点插入、右结点插入、中序遍历二叉树等）。
（3）按照建立一棵实际二叉树的操作需要，编写建立二叉树、遍历二叉树的函数。
（4）编写测试主函数并上机运行。打印出运行结果，并结合程序运行结果进行分析。
实验代码：
#include<iostream.h>
typedef struct bitnode{
char 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(&(*T)->rchild);
}
}
void inorderout(bitree T){
if(T){
inorderout(T->lchild);
cout<<T->data<<endl;
inorderout(T->rchild);
}
}
void postorder(bitree T){
if(T){
postorder(T->lchild);
postorder(T->rchild);
cout<<T->data<<endl;
}
}
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<<" "<<endl;
postorder(bt);
countleaf(bt);
}
实验五建立有序表并进行折半查找
1. 实验目的
掌握递归算法求解问题的基本思想和程序实现方法。
2．实验要求
（1）认真阅读和掌握本实验的算法思想。
（2）编写和调试完成程序。
（3）保存和打印程序的运行结果，并对运行结果进行分析。
3.实验内容
（1） 分析掌握折半查找算法思想，在此基础上，设计出递归算法和循环结构两种实现方法的折半查找函数。
（2） 编写程序实现：在保存于数组的1000个有序数据元素中查找数据元素x是否存在。数据元素x要包含两种情况：一种是数据元素x包含在数组中；另一种是数据元素x不包含在数组中
（3） 数组中数据元素的有序化既可以初始赋值时实现，也可以设计一个排序函数实现。
（4） 根据两种方法的实际运行时间，进行两种方法时间效率的分析对比。
实验代码：
#include<stdio.h>
#include<stdlib.h>
#define MAX_LENGTH 100
typedef int KeyType;
typedef struct
{
int key;
}ElemType;
typedef struct
{
ElemType elem[MAX_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.elem[mid].key)
return mid;
else
if(key<ST.elem[mid].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.elem[i]);
}
printf("please input keyword:");
scanf("%d",&key);
result=Search_Bin(ST,key);
if(result==0)
printf("Don't find\n");
else
printf("Find the key,the position is %d\n",result);
}
实验结果：
实验六
建立一组记录并进行插入排序
1. 实验目的
（1） 掌握插入排序算法的思想。
（2） 掌握顺序队列下插入排序算法的程序设计方法。
2. 实验要求
（1） 认真阅读和掌握教材中插入排序算法的思想。
（3） 编写基于顺序队列的插入排序排序算法并上机实现。
3. 实验内容
（1） 编写基于顺序队列的插入排序函数。
（2） 设计一个测试主函数，实现对基于顺序队列结构的插入排序算法的测试。
（3） 分析程序的运行结果。
实验代码：
#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 100
typedef struct
{
int key;
}sortkey;
typedef struct
{
sortkey elem[MAXSIZE];
int length;
}sortelem;
void InsertSort(sortelem *p)
{
int i,j;
for(i=2;i<=p->length;i++)
{
if(p->elem[i].key<p->elem[i-1].key)/*小于时，需将elem[i]插入有序表*/
{
p->elem[0].key=p->elem[i].key; /*为统一算法设置监测*/
for(j=i-1;p->elem[0].key<p->elem[j].key;j--)
p->elem[j+1].key=p->elem[j].key;/*记录后移*/
p->elem[j+1].key=p->elem[0].key; /*插入到正确位置*/
}
}
}
void main()
{
sortelem *p;
int i;
int b[6]={45,23,54,6,4,46};
p=(sortelem *)malloc(sizeof(sortelem));
p->length=0;
for(i=1;i<7;i++)
{
p->elem[i].key=b[i-1];
p->length++;
}
InsertSort(p);
for(i=1;i<7;i++)
{
printf("%d ",p->elem[i].key);
}
system("pause");
}
实验结果：
实验七 建立一组记录并进行快速排序
1. 实验目的
（1） 掌握快速排序算法的思想。
（2） 掌握顺序队列下快速排序算法的程序设计方法。
2. 实验要求
（1） 认真阅读和掌握教材中快速排序算法的思想。
（3） 编写基于顺序队列的快速排序排序算法并上机实现。
3. 实验内容
（1） 编写基于顺序队列的快速排序函数。
（2） 设计一个测试主函数，实现对基于顺序队列结构的快速排序算法的测试。
（3） 分析程序的运行结果。
实验代码：
#include<iostream.h>
void quick_sort(int a[],int low, int high)
{
int i,j,pivot;
if (low < high)
{
pivot = a[low];
i = low;
j = high;
while (i < j)
{
//从顶端开始比较值，如果小于标准值，停止
while (i < j && a[j] >= pivot)
{
j--;
}
//将比pivot小的元素移到低端，下标加加
if (i < j)
a[i++] = a[j];
//从底端开始比较值，如果大于标准值，停止
while (i < j && a[i] <= pivot)
{
i++;
}
//将比pivot大的元素移到顶端，下标减减
if (i < j)
a[j--] = a[i];
}
//pivot移动到最终位置
a[i] = 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 << a[i] << ",";
}
}
int main()
{
int data[9] = {54,38,96,23,15,72,60,45,83};
quick_sort(data, 0, 8);
print_array(data,9);
return 0;
}
实验结果：
