数据结构实验指导书样本.doc

资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。

《数据结构》

实验指导书

贵州大学
电子信息学院
通信工程

目 录

实验一 顺序表的操作 3
实验二 链表操作 8
实验三 集合、 稀疏矩阵和广义表 19
实验四 栈和队列 42
实验五 二叉树操作、 图形或网状结构 55
实验六 查找、 排序 88
贵州大学实验报告 109

实验一 顺序表的操作
实验学时: 2学时
实验类型: 验证
实验要求: 必修

一、 实验目的和要求
1、 熟练掌握线性表的基本操作在顺序存储和链式存储上的实现。
2、 以线性表的各种操作( 建立、 插入、 删除等) 的实现为重点。
3、 掌握线性表的动态分配顺序存储结构的定义和基本操作的实现。

二、 实验内容及步骤要求
1、 定义顺序表类型, 输入一组整型数据, 建立顺序表。
typedef int ElemType; //定义顺序表
struct List{
ElemType *list;
int Size;
int MaxSize;
};
2、 实现该线性表的删除。
3、 实现该线性表的插入。
4、 实现线性表中数据的显示。
5、 实现线性表数据的定位和查找。
6、 编写一个主函数, 调试上述算法。
7、 完成实验报告。

三、 实验原理、 方法和手段
1、 根据实验内容编程, 上机调试、 得出正确的运行程序。
2、 编译运行程序, 观察运行情况和输出结果。

四、 实验条件
运行Visual c++的微机一台

五、 实验结果与分析
对程序进行调试, 并将运行结果进行截图、 对所得到的的结果分析。

六、 实验总结
记录实验感受、 上机过程中遇到的困难及解决办法、 遗留的问题、 意见和建议等, 并将其写入实验报告中。

【附录----源程序】
#include<stdio.h>
#include<iostream>
using namespace std;

typedef int ElemType;
struct List
{
ElemType *list;
int Size;
int MaxSize;
};

//初始化线性表
bool InitList(List &L)
{
L.MaxSize=20;
L.list=new ElemType[L.MaxSize];
for(int i=0;i<20&&L.list==NULL;i++)
{
L.list=new ElemType[L.MaxSize];
}
if(L.list==NULL)
{
cout<<"无法分配内存空间, 退出程序"<<endl;
return false;
}
L.Size=0;
return true;
}

//向线性表中插入元素
bool InsertList(List &L,int pos,ElemType item)
{
if(pos>L.Size+1||pos<1)
{
cout<<"位置无效"<<endl;
return false;
}
else if(L.Size==L.MaxSize)
{
int k=sizeof(ElemType);
L.list=(ElemType*)realloc(L.list,2*L.MaxSize*k);
if(L.list==NULL)
{
cout<<"动态分配内存失败, 退出运行"<<endl;
return false;
}
L.MaxSize=2*L.MaxSize;
}

for(int i=L.Size-1;i>=pos-1;i--)
{
L.list[i+1]=L.list[i];
}
L.list[pos-1]=item;
L.Size++;
return true;
}

//删除线性表中的元素
bool DeleteList(List &L,ElemType &item,int pos)
{
if(L.Size==0)
{
cout<<"线性表中没有元素, 无法删除"<<endl;
return false;
}

if(pos<1||pos>L.Size)
{
cout<<"位置无效"<<endl;
return false;
}

item=L.list[pos-1];
for(int i=pos;i<L.Size;i++)
L.list[i-1]=L.list[i];
L.Size--;
if(float(L.Size)/L.MaxSize<0.4&&L.Size>10)
{
int k=sizeof(ElemType);
L.list=(ElemType*)realloc(L.list,L.MaxSize*k/2);
L.MaxSize=L.MaxSize/2;
}
return true;
}

//输出线性表
bool Print(List &L)
{
if(L.Size==0)
{
cout<<"线性表中无元素"<<endl;
return false;
}
cout<<"线性表为: "<<endl;
for(int i=0;i<L.Size;i++)
{
cout<<L.list[i]<<" ";
}
cout<<"线性表长度为"<<L.Size<<endl;
return true;
}

//查找数据
bool GetList(List L,ElemType item,int pos)
{
if(pos<1||pos>L.Size)
{
cout<<"位置无效"<<endl;
return false;
}
int k;
cout<<"按位置查找选择1, 按元素查找选择0"<<endl;
cin>>k;
if(k==1)
{
cout<<"第"<<pos<<"个元素为"<<L.list[pos-1]<<endl;
return true;
}
else if(k==0)
{
for(int i=0;i<L.Size;i++)
{
if(L.list[i]==item)
cout<<"你要找的元素为"<<":"<<item<<"在第"<<i+1<<"个"<<endl;
if(i==L.Size)
{
cout<<"没有你要找的元素"<<endl;
return false;
}
}
}
else
{
cout<<"查找无效, 请选择0或1"<<endl;
return false;
}
}
void main()
{
List m;
InitList(m);//初始化线性表
Print(m);

cout<<"请输入十个数据"<<endl;
for(int i=0;i<10;i++)
{
cin>>m.list[i];
m.Size++;
}
Print(m);

cout<<"向线性表中第r个位置插入s"<<endl;
cout<<"请输入r, s"<<endl;
int r;
ElemType s;
cin>>r>>s;
cout<<"(m,r,s)"<<endl;//向线性表中插入元素
InsertList(m,r,s);
Print(m);

cout<<"查找数据s或者查找第r个数据"<<endl;
cin>>s>>r;
GetList(m,s,r);
Print(m);

ElemType f=0;
cout<<"删除第r个数据"<<endl;
cin>>r;
DeleteList(m,f,r);
Print(m);
cout<<"删除的数据是"<<f<<endl;
}
实验二 链表操作
实验学时: 2学时
实验类型: 验证
实验要求: 必修

一、 实验目的和要求
1、 掌握链表的概念, 了解线性表的链式存储结构, 学会定义线性表的链式存储结构。
2、 加深对链式存储数据结构的理解, 逐步培养解决实际问题的编程能力。

二、 实验内容及步骤要求
1、 简单链表的基本操作
(1) 编写链表基本操作函数。
①初始化链表 InitList(LIST *L,int ms)
②向链表指定位置插入元素 InsertList1(LIST *L,int item,int rc)
③向有序链表指定位置插入元素 InsertList2(LIST *L,int item,int rc)
④删除指定元素之的链表记录 DeleteList(LIST *L,int item)
⑤查找链表中的元素 FindList(LIST *L,int item)
(2) 调用上述函数实现下列操作, 操作步骤如下:
①从键盘输入一个数据元素x, 插入到线性表中第i( 包含1号位置) 个位置;
②从键盘输入一个数据元素关键字x或位置i( 包含1号位置) , 从线性表中删除相应数据元素。

2、 约瑟夫环问题
(1) 约瑟夫( Joeph) 问题的一种描述: 编号为1,2,…,n的n个人按顺时针方向围坐一圈, 每人持有一个密码( 正整数) 。一开始任选一个正整数作为报数上限值m, 从第一个人开始按顺时针方向自1开始顺序报数, 报到m时停止报数。报m的人出列, 将她的密码作为新的m值, 从她在顺时针方向上的下一个人开始重新从1报数, 如此下去, 直至所有人全部出列为止。
(2) 编程实现约瑟夫环问题, 利用单向循环链表存储结构模拟此过程, 按照出列的顺序印出各人的编号。
(3) 试设计一个程序求出出列顺序。并设m的初值为20; 密码: 3, 1, 7, 2, 4, 8, 4( 正确的结果应为6, 1, 4, 7, 2, 3, 5) 。

3、 完成实验报告。

三、 实验原理、 方法和手段
1、 根据实验内容编程, 上机调试、 得出正确的运行程序。
2、 编译运行程序, 观察运行情况和输出结果。

四、 实验条件
运行Visual c++的微机一台

五、 实验结果与分析
对程序进行调试, 并将运行结果进行截图、 对所得到的的结果分析。

六、 实验总结
记录实验感受、 上机过程中遇到的困难及解决办法、 遗留的问题、 意见和建议等, 并将其写入实验报告中。

【附录----简单链表的基本操作源程序】
/* 线性表实验程序--单链表*/
#include <stdio.h>
#include <malloc.h>

/*抽象数据类型定义*/
typedef int ElemType;
typedef struct node
{
ElemType data;
struct node *next;
}*LKList,LNode;
void InitList(LKList *L); /*初始化线性表*/
void CreateList(LKList *L); /*创立线性表*/
int GetLength(LKList *L); /*获得线性表的长度*/
int GetElem(LKList *L,int i,ElemType *e); /*取线性表第i个表元素, 并放在e指向的的内存中*/
int SetElem(LKList *L,int i,ElemType *e); /*修改第i个表元素*/
int InsertElem(LKList *L,int i, ElemType *e); /*在第i个位置插入元素*/
int DeleteElem(LKList *L,int i); /*删除第i个元素*/
int SearchElem(LKList *L,ElemType *e); /*查找元素*e的位置i*/
int TraversList(LKList *L); /*遍历线性表*/
void ClearList(LKList *L); /*清除线性表*/
LKList FindElem(LKList *L,int i); /*取第i个元素的地址*/

/*抽象数据类型的操作实现*/
void InitList(LKList *L) /*初始化线性表*/
{
*L=NULL;
}

void CreateList(LKList *L) /*创立线性表*/
{
int i,ok;
ElemType e;

InitList(L);
i=0;
printf("input end while enter -9999!\n");
while(1)
{
scanf("%d",&e);
if(e!=-9999)
{ ok=InsertElem(L,++i,&e);
if(!ok) break;
}
else
break;
}
}

int GetLength(LKList *L) /*获得线性表的长度*/
{
int i=0;
LKList p=*L;
while(p)
{
i++;
p=p->next;
}
return i;
}

LKList FindElem(LKList *L,int i)
{
LKList p=*L;
int j=0;

if(p==NULL)
return 0;
while(p)
{
j++;
if(j==i) break;
p=p->next;
}
return p;
}

int GetElem(LKList *L,int i,ElemType *e) /*取线性表第i个表元素, 并放在e指向的的内存中*/
{
LKList p=FindElem(L,i);
int j=0;

if(p==NULL)
return 0;
*e=p->data;
return 1;
}

int SetElem(LKList *L,int i,ElemType *e) /*修改第i个表元素*/
{
LKList p=FindElem(L,i);
int j=0;

if(p) p->data=*e;
return 1;
}

int InsertElem(LKList *L,int i, ElemType *e) /*在第i个位置插入元素*/
{
LKList p=FindElem(L,i-1);
LNode *s;
s=(LNode*)malloc(sizeof(LNode));
s->data=*e;
s->next=NULL;
if(i==1)
{ s->next=*L;
*L=s;
return 1;
}
if(p==NULL){
printf("Invalid position to insert!\n");
return 0;
}
else
{ s->next=p->next;
p->next=s;
}
return 1;
}

int DeleteElem(LKList *L,int i) /*删除第i个元素*/
{
LKList p,q;
if(*L==NULL)return 0;
if(i==1)
{ p=*L;
*L=(*L)->next;
free(p);
return 1;
}
p=FindElem(L,i-1);
if(p)
{
q=p->next;
p->next=q->next;
if(q)free(q);
}
else{
printf("Invalid position to Delete!\n");
return 0;
}
return 1;
}

int SearchElem(LKList *L,ElemType *e) /*查找元素*e的位置i*/
{
LNode *p=*L;
int j=0;

while(p)
{
j++;
if(p->data==*e)break;
}
return p?j:0;
}

int TraversList(LKList *L) /*遍历线性表*/
{
LNode *p=*L;
ElemType e;

if(p==NULL)
{ printf("Lineast is Empty!!!\n");
return 0;
}
while(p)
{ e=p->data;
printf("%6d",e);
p=p->next;
}
return 1;
}

void ClearList(LKList *L) /*清除线性表*/
{
LNode *p,*q;
p=*L;
while(p)
{
q=p->next;
free(p);
p=q;
}
*L=NULL;
}
/***********测试数据结构的正确性*****************/
int displayMenu()
{
printf("\n1.CreateList\n");
printf("2.Display List\n");
printf("3.Delete a Element\n");
printf("4.Insert a Element\n");
printf("5.Display List length\n");
printf("6.Change i'st Element value\n");
printf("7.Get i'st Element Value\n");
printf("8.Clear your List\n");
printf("0.Exit my program!\n");
fflush(stdin);
return getchar();
}

void main( )
{
LKList L;
char ch;
ElemType e;
int i;

InitList(&L);
while((ch=displayMenu())!='0')
{
switch(ch)
{
case '1':printf("Now Create a List!\n");
CreateList(&L);
break;
case '2':printf("Your List is \n");
TraversList(&L);
break;
case '3':printf("Please Enter a No of Element you want to delete!\n");
scanf("%d",&i);
DeleteElem(&L,i);
TraversList(&L);
break;
case '4':printf("Please Enter a Elemnet value and Position you will Insert!(e,i)\n");
scanf("%d%d",&e,&i);
InsertElem(&L,i,&e);
TraversList(&L);
break;
case '5':printf("Length of List is %d\n",GetLength(&L));
break;
case '6':printf("Please Enter a Element value and position you will Change!(e,i)\n");
scanf("%d%d",&e,&i);
SetElem(&L,i,&e);
TraversList(&L);
break;
case '7':printf("Get i'st Element value\nPlease Enter i:\n");
scanf("%d",&i);
GetElem(&L,i,&e);
printf("data[%d]=%d\n",i,e);
break;
case '8':ClearList(&L);
if(GetLength(&L)==0)
printf("Now,you list has no element!!\n");
break;
case '0':
printf("your program is running is over!\n");
break;
default:
printf("Please Enter charactor between '0'and '8'!\n");
break;
}
}
}

【附录----约瑟夫环问题源程序】
/* Joseph cycle*/
#include <stdio.h>
#include <conio.h>
#include <alloc.h>
typedef int ElemType;
typedef struct LNode
{
ElemType data;
struct LNode *next;
} LNode,*POINTER,*LinkList;
void init_linklist(LinkList *l);
void release_linklist(LinkList *l);
void clear_linklist(LinkList l);
void crt_linklist(LinkList *l);
void disp_linklist(LinkList l);
void game(LinkList l);
void exitgame(void);
void init_linklist(LinkList *l)/*对循环单链表进行初始化*/
{
(*l)=(POINTER)malloc(sizeof(struct LNode));
(*l)->data=-1;
(*l)->next=(*l);
}
void clear_linklist(LinkList l)/*对循环单链表清空*/
{
POINTER p,useless;
p=l->next;
l->next=l;
while(p!=l)
{
useless=p;
p=p->next;
free(useless);
}
}
void crt_linklist(LinkList *l)/*输入数据创立约瑟夫环表*/
{
int num;
POINTER p;
clear_linklist(*l);
printf("\n\nInput some int numbers (ending with -1) :\n");
scanf("%d",&num);
while(num!=-1)
{
p=(POINTER)malloc(sizeof(struct LNode));
p->data=num;
p->next=(*l)->next;
(*l)->next=p;
scanf("%d",&num);
}
}
void disp_linklist(LinkList l)/*显示表中元素内容*/
{ int i=1,row=1;
POINTER p=l->next;
printf("\n\n");
while(p!=l)
{
if(row==7)
{
row=1;
printf("\n");
}
printf("%5d:%-5d|",i,p->data);
i++;
row++;
p=p->next;
}
}
void game(LinkList l)/*元素依次根据密码值出圈*/
{
int m,k=0;
POINTER p=l,pre,u;
printf("\n\nCount Number m==? ");
scanf("%d",&m);
printf("\n\n\n\n%40s\n\n","GAME START");
while(p->next!=p)
{
pre=p;
p=p->next;
if(p==l) { pre=p; p=p->next;}
++k;
if(k==m) { printf(" %d",p->data);
pre->next=p->next;
u=p;
free(u);
p=pre;
k=0;
}
}
printf("\n\n%40s","GAME OVER");
}
void exitgame()
{
printf("\n\n%40s","GOOD_BYE_GOOD !!");
}
void release_linklist(LinkList *l)/*销毁循环单链表( 约瑟夫环) */
{
clear_linklist(*l);
free(*l);
}
void main()/*主控函数*/
{
int select;
LinkList list;
init_linklist(&list);
do
{
printf("%s%15s%15s%15s%15s",
"\n\n\n\n\n\n",
"1:Create",
"2:Display",
"3:Game",
"4:Exit");
printf("\n\n%33c",' ');
select=getche();
switch(select)
{
case '1': crt_linklist(&list);
disp_linklist(list);
break;
case '2': disp_linklist(list);
break;
case '3': game(list);
break;
case '4': exitgame();
break;
default: printf("\nWrong select ! Try again. ");
}/*switch*/
}while(select!='4');
release_linklist(&list);
getch();
}

实验三 集合、 稀疏矩阵和广义表
实验学时: 2学时
实验类型: 验证
实验要求: 必修

一、 实验目的及要求:
1、 掌握集合的基本运算
2、 掌握稀疏矩阵的简单运算
3、 掌握广义表的基本操作

二、 实验内容及步骤要求
1、 集合的运算
①存储结构采用顺序表或链表;
②主函数设计一个菜单, 经过菜单进入各模块测试
③在集合并运算时, 检索两个集合, 将第二个集合中与第一个集合中不
同的元素, 插入第一个集合。
④集合交运算时, 检索两个集合, 将第一个集合中与第二个集合不同元素, 删除。
⑤集合差运算时, 检索两个集合, 将第一个集合中与第二个集合中相同元素删除。

2、 稀疏矩阵
①创立稀疏矩阵
②在主程序设计一个菜单, 经过菜单进入各模块测试
③实现矩阵的加、 减、 乘功能。

3、 广义表
①创立广义表
②在主程序设计一个菜单, 经过菜单选择要完成的操作
③输入正确格式的广义表, 如 (a,b,c)
④选择任意键继续, 课继续操作, 可退出

三、 实验原理、 方法和手段
1、 根据实验内容编程, 上机调试、 得出正确的运行程序。
2、 编译运行程序, 观察运行情况和输出结果。

四、 实验条件
运行Visual c++的微机一台

五、 实验结果与分析
对程序进行调试, 并将运行结果进行截图、 对所得到的的结果分析。

六、 实验总结
记录实验感受、 上机过程中遇到的困难及解决办法、 遗留的问题、 意见和建议等, 并将其写入实验报告中。

【附录----源程序】
1、 集合的运算
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>

#define MAXSIZE 100
typedef int DataType;
typedef struct node
{
int length;
DataType data[MAXSIZE];
} SeqList,*PSeqList;

PSeqList Init_SeqList(void)//初始化
{
PSeqList PL;
PL=(PSeqList)malloc(sizeof(SeqList));
if(PL)
PL->length=0;
return (PL);
}

int Location_SeqList(PSeqList L, DataType x)//检索
{
int i=0;
while (i<L->length && L->data[i]!=x)
i++;
if(i>=L->length) return 0;
else return (i+1);
}

int Insert_SeqList(PSeqList PL,int i,DataType x)//插入
{
int j;
if(!PL)
{
printf("表不存在");
return(-2);
}
if(PL->length>=MAXSIZE)
{
printf("表溢出");
return(-1);
}
if(i<0||i>PL->length+1)
{
printf("插入位置不合法");
return(0);
}
for(j=PL->length-1; j>=i-1; j--)

PL->data[i]=x;

PL->length++;
return(1);
}

int Delete_SeqList(PSeqList PL, int i)//删除
{
int j;
if(!PL)
{
printf("表不存在");
return(-1);
}
if(i<1||i>PL->length)
{
printf("删除位置不合法");
return(0);
}
for(j=i;j<PL->length;j++)
PL->data[j-1]=PL->data[j];
PL->length--;
return(1);
}

void Inter_sec(PSeqList A,PSeqList B)//交集
{
int i,j;

for (i=0;i<A->length;++i)
{
if(!Location_SeqList(B, A->data[i]))
{
Delete_SeqList(A, i+1);

}
}
for (j = 0; j < A->length; j++)
{

printf("%d ",A->data[j]);
}
}

void Merge_sec (PSeqList A, PSeqList B)//并集
{
int i,j;
for (i=0; i<B->length; i++)
if(!Location_SeqList(A, B->data[i]))
{
Insert_SeqList(A,A->length,B->data[i]);
}

for (j = 0; j < A->length; j++)
{
printf("%d ",A->data[j]);
}

}

void cha_sec (PSeqList A, PSeqList B)//差集
{
int i,j,k;
for (i=0;i<B->length;i++)
{
if(k = Location_SeqList(A, B->data[i]))
Delete_SeqList(A, k);
}
for (j = 0; j < A->length; j++)
{
printf("%d ",A->data[j]);
}
}

void main ()
{
PSeqList A,B;
int i, k, m, x, y, menu, a[MAXSIZE], b[MAXSIZE];

char re;

A = Init_SeqList();
B = Init_SeqList();
printf("1 存入两个集合\n");
printf("2 集合的交集\n");
printf("3 集合的并集\n");
printf("4 集合的差集\n");
printf("0 退出\n");
pri