《数据结构》实验教学大纲.docx

《数据结构》实验教学大纲.docx

《《数据结构》实验教学大纲.docx》由会员分享，可在线阅读，更多相关《《数据结构》实验教学大纲.docx（42页珍藏版）》请在冰点文库上搜索。

《数据结构》实验教学大纲

《数据结构》实验教学大纲

实验1线性表的基本操作

1实验目的

（1）熟练掌握线性表的逻辑特征。

（2）熟练掌握线性表的基本操作在两种存储结构上的实现。

2实验内容

（1）设计一个顺序表的基本操作的演示程序

（2）设计一个单链表的基本操作的演示程序

（3）设计一个双链表的基本操作的演示程序

【基本要求】

实现下列4种基本运算：

（1）初始化线性表；

（2）在第I个元素前插入一个元素e；（3）删除第I个元素；（4）遍历线性表；（5）将单链表逆置

【测试数据】自定

参考程序如下：

//顺序表的基本操作

#include

//顺序表的定义

#defineMAX15

typedefstruct{

intelem[MAX];

intlength;

}Sqlist;

voidInitlist_sq（Sqlist&L）;

voidListInsert_sq（Sqlist&L,inti,inte）;

voidListDel_sq（Sqlist&L,inti,int&e）;

voidprint_sq（SqlistL）;

//函数的定义

voidInitlist_sq（Sqlist&L）

{

L.length=0;

}

voidListInsert_sq（Sqlist&L,inti,inte）

{

int*p,*q;

if（i<1||i>L.length+1）return;

q=&L.elem[i-1];//插入位置

for（p=&L.elem[L.length-1];p>=q;--p）

*（p+1）=*p;

*q=e;

++L.length;

return;

}

voidListDel_sq（Sqlist&L,inti,int&e）

{

if（i<1||i>L.length）return;

e=L.elem[i-1];

for（intj=i;j

L.elem[j-1]=L.elem[j];

--L.length;

}

voidprint_sq（SqlistL）

{

int*p,*q=L.elem+L.length-1;

for（p=L.elem;p<=q;p++）

cout<<*p<<'';

cout<<"\n";

}

voidmain（）

{

inta[11]={10,20,30,40,50,60,70,80,90,100};

SqlistL;

//初始化顺序表

Initlist_sq（L）;

cout<<"现在的表长：

"<

//插入10个数据元素

for（inti=1;i<=10;++i）

ListInsert_sq（L,i,a[i-1]）;

cout<<"插入10个元素后的线性表：

"<

//遍历

print_sq（L）;

cout<<"现在的表长：

"<

//删除第5个元素

intx;

ListDel_sq（L,5,x）;

cout<<"删除的元素值是：

"<

cout<<"删除第5个元素后的表：

"<

print_sq（L）;

cout<<"现在的表长：

"<

}

//单链表的操作

#include

structNODE

{

intdata;

NODE*next;

};

voidprint（NODE*&head）;//遍历

intdata[6]={25,41,17,98,5,6};

voidSetup_L（NODE*&head,intn）;//生成单链表

voidInsert_L（NODE*&head,intI,inte）;//插入

voidDelete_L（NODE*&head,intI,int&e）;//删除

voidConvert_L（NODE*&head）；//逆序

voidmain（）

{

NODE*L;

Setup_L（L,6）;

print（L）;

//Insert_L（L,7,50）;

print（L）;

intx;

Delete_L（L,0,x）;

cout<<"X="<

print（L）;

Convert_L（L）;

print（L）;

}

voidprint（NODE*&head）

{

NODE*p;

p=head->next;

while（p）

{

cout<data<<",";//输出元素值

p=p->next;//后移指针

}

cout<

}

voidSetup_L（NODE*&head,intn）

{

NODE*q,*p;

head=（NODE*）newNODE;

head->next=NULL;//先建立一个带头结点的单链表

q=head;

for（inti=0;i

p=（NODE*）newNODE;//生成新结点

p->data=data[i];

q->next=p;q=p;//插入到表头

}

q->next=NULL;

}

voidInsert_L（NODE*&L,inti,inte）

{

NODE*p=L,*q;

intj=0;

while（p&&j

{p=p->next;

j++;

}

if（!

p||j>i-1）

{cout<<"插入值超出范围！

"<

return;

}

q=（NODE*）newNODE;

q->data=e;

q->next=p->next;

p->next=q;

}

voidDelete_L（NODE*&L,inti,int&e）

{

NODE*p=L,*q;

intj=0;

while（p&&j

{p=p->next;

j++;

}

if（!

p||j>i-1）

{cout<<"删除值超出范围！

"<

return;

}

q=p->next;

e=q->data;

p->next=q->next;

deleteq;

}

voidConvert_L（NODE*&L）

{

NODE*p,*q,*r;

p=L->next;

q=p->next;

p->next=NULL;

while（q）

{

r=q->next;

q->next=p;

L->next=q;

p=q;

q=r;

}

}

//双链表的基本操作

structNODE

{

intdata;

NODE*next;

NODE*prior;

};

intdata[6]={3,5,7,19,20,21};//测试用数据

//函数声明

voidprint（NODE*&head）;

voidSetup_L（NODE*&head,intn）;

voidInsert_L（NODE*&L,inti,inte）;

voidDelete_L（NODE*&L,inti,int&e）;

voidConvert_L（NODE*&L）;

//主函数和各函数的定义

voidmain（）

{

NODE*L;

Setup_L（L,6）;

print（L）;

Insert_L（L,7,50）;

print（L）;

intx;

Delete_L（L,1,x）;

cout<<"X="<

print（L）;

}

voidprint（NODE*&head）

{//从头开始顺序输出双链表中的数据

NODE*p;

p=head->next;

while（p）

{cout<data<<",";

p=p->next;

}

cout<

}

voidSetup_L（NODE*&head,intn）

{//创建一个带头结点的双链表

NODE*q,*p;

head=（NODE*）newNODE;

head->next=NULL;

q=head;

for（inti=0;i

p=（NODE*）newNODE;

p->data=data[i];

//cin>>p->data;

p->prior=q;q->next=p;q=p;

}

q->next=NULL;

//return（head）;

}

voidInsert_L（NODE*&L,inti,inte）

{//在带头结点的双链表中第i个位置插入元素e

NODE*p=L,*q;

intj=0;//j为计数器

while（p&&j

{p=p->next;

j++;

}//寻找第i-1个结点

if（!

p||j>i-1）//i小于1或大于表长

{cout<<"插入值超出范围!

"<

return;

}

q=（NODE*）newNODE;//生成新结点

q->data=e;

if（p->next==NULL）

{q->next=p->next;p->prior=q;p->next=q;}

else

{q->next=p->next;p->next->prior=q;p->next=q;q->prior=p;}//插入L中

}

voidDelete_L（NODE*&L,inti,int&e）

{//在带头结点的双链表L中，删除第i个元素，并由e返回其值

NODE*p=L,*q;

intj=0;

while（p&&j

{p=p->next;

j++;

}

if（!

p||j>i-1）

{cout<<"删除值超出范围!

"<

return;

}

q=p->next;

e=q->data;

q->next->prior=p;

p->next=q->next;

deleteq;

}//删除并释放结点

3实验要求

按要求编写实验程序，将实验程序上机调试运行，并提交实验报告。

实验2栈和队列的基本操作

1实验目的

（1）深入了解栈和队列的基本特性

（2）熟练掌握栈的基本操作在两种存储结构上的实现。

（3）熟练掌握循环队列的基本操作

（4）熟练掌握链队列的基本操作

2实验内容

（1）设计一个顺序栈的基本操作的演示程序

（2）设计一个链栈的基本操作的演示程序

（3）设计一个循环队列的基本操作的演示程序

（4）设计一个链队列的基本操作的演示程序

【基本要求】

实现下列6种基本运算：

（1）初始化；

（2）入栈（队列）；（3）出栈（队列）；（4）遍历；（5）求栈（队列）的长度

【测试数据】自定

参考程序如下：

//顺序栈的基本操作

#include

#defineMAX10

typedefstruct{

intbase;

inttop;

intst[MAX];

}SqStack;

//基本操作说明

voidInitStack（SqStack&S）;

voidpush（SqStack&S,inte）;

voidpop（SqStack&S,int&e）;

//基本操作的算法描述

voidInitStack（SqStack&S）

{

S.base=S.top=0;

}

voidpush（SqStack&S,inte）

{

if（S.top==MAX）

{cout<<”栈满\n”;

return;

}

S.st[S.top]=e;

S.top+=1;

}

voidpop（SqStack&S,int&e）

{

if（S.top==0）

{cout<<”栈空\n”;return;}

S.top-=1;

e=S.st[S.top];

}

voidprint（SqStackS）

{

cout<<”栈的各个元素如下：

\n”;

for（intI=0;I

cout<

cout<

}

voidmain（）

{

SqStackS;

//初始化

cout<<”初始化栈\n”;

InitStack（S）;

cout<<”栈底和栈顶：

”<

//入栈

cout<<”5个元素入栈\n”;

for（intI=0;I<5;I++）

{

push（S,2*I+1）;

cout<<”栈顶为：

”<

}

print（S）;

//出栈

intx;

pop（S,x）;

cout<<”出栈元素为：

”<

print（S）;

}

//循环队列的基本操作

#include

#defineMAX8

typedefstruct

{

intbase[MAX];

intfront;

intrear;

}SqQueue;

/***********初始化**************/

voidInitQueue（SqQueue&Q）

{

Q.front=Q.rear=0;

}

//******求队列长度******//

intQueueLength（SqQueueQ）

{

return（Q.rear-Q.front+MAX）%MAX;

}

//*****入队列****************//

voidEnQueue（SqQueue&Q,inte）

{

if（（Q.rear+1）%MAX==Q.front）

cout<<”队列满！

”<

else

{Q.base[Q.rear]=e;

Q.rear=（Q.rear+1）%MAX;}

}

//*******遍历队列******//

voidtraverse（SqQueue&Q）

{

intI,k;

if（Q.front<=Q.rear）

k=0;

else

k=1;

switch（k）

{

case0:

for（I=Q.front;I

cout<

break;

case1:

for（I=Q.front;I

cout<

for（I=0;I

cout<

break;

}

}

/**************出队************/

intDeQueue（SqQueue&Q,int&e）

{

if（Q.rear==Q.front）return–1;

e=Q.base[Q.front];

Q.front=（Q.front+1）%MAX;

return1;

}

voidmain（）

{

SqQueueQ;

InitQueue（Q）;

intj,m,x;

for（j=0;j<7;j++）

EnQueue（Q,2*j）;

traverse（Q）;

m=QueueLength（Q）;

cout<<”\n长度”<

EnQueue（Q,500）;

traverse（Q）;

DeQueue（Q,x）;

m=QueueLength（Q）;

cout<<”\n长度”<

traverse（Q）;

EnQueue（Q,500）;

m=QueueLength（Q）;

cout<<”\n长度”<

traverse（Q）;

DeQueue（Q,x）;

m=QueueLength（Q）;

cout<<”\n长度”<

traverse（Q）;

EnQueue（Q,600）;

m=QueueLength（Q）;

cout<<”\n长度”<

traverse（Q）;

}

3实验要求

按要求编写实验程序，将实验程序上机调试运行，并提交实验报告。

实验3二叉树的基本操作

1实验目的

（1）掌握二叉树的非线性和递归特点。

（2）熟练掌握二叉树的存储结构。

（3）熟练掌握二叉树的各种遍历操作和其它操作的实现方法。

2实验内容

设计一个可进行二叉树基本操作的演示程序。

【基本要求】

实现下列六种基本运算：

（1）创建二叉树；

（2）先序遍历二叉树；（3）中序遍历二叉树；（4）后序遍历二叉树；（5）层序遍历二叉树；（6）求度为1的结点的个数；（7）求叶子结点的个数；（8）求度为2的结点的个数。

二叉树以链式结构表示，主程序以菜单方式的用户界面。

【测试数据】自定

//二叉树的基本操作

#include

typedefstructnode//定义结点

{

chardata;

structnode*lchild,*rchild;

}BinTNode;

typedefBinTNode*BinTree;//定义二叉树

voidCreateBinTree（BinTree&T）;//先序创建二叉树

voidPreOrder（BinTreeT）;//先序遍历二叉树

voidInOrder（BinTreeT）;//中序遍历二叉树

voidPostOrder（BinTreeT）;//后序遍历二叉树

intonechild（BinTreeT）;//求度为1的结点的个数

intleafs（BinTreeT）;//求叶子结点的个数

inttwochild（BinTreeT）;//度为2的结点的个数

voidtranslevel（BinTreeb）//层序遍历二叉树

voidmain（）

{

intn;

BinTreeT;

charch1,ch2;

cout<<"Welcometoenterthetestingprogramforbintreebasicoperator"<

cout<<"PleaseChose"<

ch1='y';

while（ch1=='y'||ch1=='Y'）

{

cout<<"A--------building\n";

cout<<"B------PreOrder\n";

cout<<"C------InOrder\n";

cout<<"D-------PostOrder\n";

cout<<”E-------translevel\n”;

cout<<"F------onechild\n";

cout<<"G-----twochild\n";

cout<<"H------leafs\n";

cout<<"X-------Quit\n";

cin>>ch2;

switch（ch2）

{

case'a':

case'A':

cout<<"请输入按先序建立二叉树的结点序列：

\n";

CreateBinTree（T）;

break;

case'b':

case'B':

cout<<"二叉树的先序遍历序列：

\n";

PreOrder（T）;

break;

case'c':

case'C':

cout<<"二叉树的中序遍历序列：

\n";

InOrder（T）;

break;

case'd':

case'D':

cout<<"二叉树的后序遍历序列：

\n";

PostOrder（T）;

break;

case'f':

case'F':

cout<<"二叉树的单孩子结点数：

\n";

n=onechild（T）;

cout<

break;

case'g':

case'G':

cout<<"二叉树的双孩子结点数：

\n";

n=twochild（T）;

cout<

break;

case'h':

case'H':

cout<<"二叉树的叶子结点数：

\n";

n=leafs（T）;

cout<

break;

case‘e’:

case‘E’:

cout<<"二叉树的层序遍历序列：

\n";

translevel（T）;

break;

case'x':

case'X':

ch1='x';

break;

}

}

}

voidCreateBinTree（BinTree&T）

{

charch;

cin>>ch;

if（ch=='0'）T=NULL;

else

{

T=（BinTNode*）newBinTNode;

T->data=ch;

CreateBinTree（T->lchild）;

CreateBinTree（T->rchild）;

}

}

voidInOrder（BinTreeT）

{

if（T）

{

InOrder（T->lchild）;

cout<data<

InOrder（T->rchild）;

}

}

voidPostOrder（BinTreeT）

{

if（T）

{

PostOrder（T->lchild）;

PostOrder（T->rchild）;

cout<data<

}

}

voidPreOrder（BinTreeT）

{

if（T）

{

cout<data<

PreOrder（T->lchild）;

PreOrder