数据结构第一次.docx

数据结构第一次.docx

《数据结构第一次.docx》由会员分享，可在线阅读，更多相关《数据结构第一次.docx（16页珍藏版）》请在冰点文库上搜索。

数据结构第一次

计算机专业类课程

实验报告

课程名称：

数据结构

学　　院：

计算机科学与工程学院

专　　业：

计算机科学与技术

学生姓名：

包馨宇

学　　号：

2012060080028

指导教师：

郝东

日　　期：

　　　2013　年　11　月　24　日

电子科技大学

实验报告

实验一

1、实验名称：

单链表中表头、表尾及表的中间插入删除元素。

2、实验学时：

2学时

3、实验内容和目的：

采用链式存储结构存储’a’,’b’,’c’,’d’,’e’,’f’六个字符，并完成如下操作：

（a）显示第3个数据；

（b）在第2个数据后插入’e’

（c）删除第3个数据并打印整个链表

（d）删除链表

4、实验原理：

链式线性表存储结构

5、实验器材（设备、元器件）：

PC机，Windows7操作平台，VisualC++6.0

6、实验步骤：

单链表操作：

1：

构建单链表，存储‘a’,‘b’,‘c’,‘d’,‘e’,‘f’六个字符（采用实例化）

2：

显示第3个数据，‘c’；

3：

在第2个数据后插入‘b’后插入‘e’；

4：

删除第3个数据‘e’；

5：

程序结束

7、实验数据及结果分析：

代码（附）：

#include"stdio.h"

#include"iostream"

usingnamespacestd;

structNode{

charc;

structNode*pNext;

};

//遍历打印链表

voidprintList（Node*list）{

if（list!

=NULL）{

Node*p=list;

cout<<"链表内元素为";

while（p）{

cout<c;

p=p->pNext;

}

cout<

}

else{

cout<<"表为空";

}

}

//删除指定位置元素

voidremoveList（Node*list,intpos）{

Node*p=list;

Node*q;

inti=1;

while（p）{

if（i

i++;

p=p->pNext;

}

if（i==pos-1）{

q=p->pNext;

p->pNext=q->pNext;

break;

}

}

}

//删除整个链表

/*voidfreeList（Node*list）{

Node*p=list,*q;

while（p）{

q=p->pNext;

deletep;

p=q;

}

}*/

//删除整个链表

voidfreeList（Node*list）{

Node*p=list;

while（p）{

removeList（p,1）;

}

}

//在指定位置插入元素

voidinsertList（Node*list,intpos,charc）{

Node*p=list;

Node*q=newNode;

q->c=c;q->pNext=NULL;

inti=1;

while（p）{

if（i

i++;

p=p->pNext;

}

if（i==pos）{

q->pNext=p->pNext;

p->pNext=q;

break;

}

}

}

//查找指定位置的元素

voidfindElem（Node*list,intpos）{

Node*p=list;

inti=1;

while（p）{

if（i

i++;

p=p->pNext;

}

if（i==pos）{

cout<<"第"<

"<c<

break;

}

}

}

voidmain（）{

Noden1,n2,n3,n4,n5,n6;

n1.c='a';n1.pNext=&n2;

n2.c='b';n2.pNext=&n3;

n3.c='c';n3.pNext=&n4;

n4.c='d';n4.pNext=&n5;

n5.c='e';n5.pNext=&n6;

n6.c='f';n6.pNext=NULL;

printList（&n1）;

findElem（&n1,3）;

insertList（&n1,2,'e'）;

cout<<"第二位插入元素后"<

printList（&n1）;

removeList（&n1,3）;

cout<<"删除第三个元素后"<

printList（&n1）;

//freeList（&n1）;

//printList（&n1）;

cout<<"程序结束"<

}

8、实验结论、心得体会和改进建议：

单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。

链表中的数据是以节点来表示，每个节点由元素和指针构成。

单链表是不断申请存储单元和改变链接关系而得到的一种特殊数据结构，将链表的一边称为链头，另一边称为链尾，将链表一端看成固定的，链表不断向另一侧延伸而得到的整体链表。

链表可进行动态生成，也可在实例化的同时进行生成，本实验采取的是实例化生成，其改进可生成一个链表类，进行返回指针的函数的构建，继而实现更好的代码可移植性及代码的重用性

本实验中注意的地方：

1：

若指针变量p的值为空（NULL），则它不指向任何结点。

此时，若通过指针访问结点就意味着访问一个不存在的变量，从而引起程序的错误。

应增加相应的安全系统。

2：

有关指针类型需明确注意，以防出现内存的溢出。

3：

在链表中插入结点只需要修改指针。

但同时，若要在第i个结点之前插入元素，修改的是第i-1个结点的指针。

因此，在单链表中第i个结点之前进行插入的基本操作为:

找到线性表中第i-1个结点，然后修改其指向后继的指针。

4：

本实验用的为静态输出，无用户进行的交互工作。

可构建函数进行改进，将其改为动态生成，并进行用户端的输入输出，实现系统的交互性。

电子科技大学

实验报告

实验二

1、实验名称：

循环链表中表头、表尾及表的中间插入删除元素（传递游戏）

2、实验学时：

2学时

3、实验内容和目的：

N个人围圆圈而坐，分别标以数字1到N。

从坐在1号的位置的人开始依次传递土豆。

M次传递之后，拿到土豆的人被排除，圆圈收缩，然后从离开圆桌的人后面的那个人开始继续游戏。

游戏一直进行，直到留下最后一个人，为赢家。

因此，如果M=0且N=5,所有的人依次被排除，5号最后胜利。

如果M=1且N=5,排除的顺序为2,4,1,5.

（a）请编程实现M和N为任意可能值的这个游戏，尽量做到程序高效。

（b）分析在N很大（N>10,000）时，程序运行速度怎样被影响？

得出算法的时间复杂度。

4、实验原理：

双向循环链表的插入删除和循环

5、实验器材（设备、元器件）

PC机，Windows7操作平台，VisualC++6.0

6、实验步骤：

1：

建立双向循环链表，设置头尾指针

2：

进行指针的设置，配合函数，实现指针的移动从而达到删除数据并构建链接作用

3：

通过用户的输入进行循环设置

4：

输出最终结果

7、实验数据及结果分析：

#include

#include

usingnamespacestd;

classNode{

public:

intnum;//储存编号

Node*front;

Node*next;

Node:

:

Node（）{

num=0;

front=NULL;

next=NULL;

}

};

classgame{

public:

intpersonN;//游戏当前人数

Node*hrp;//头指针

Node*brp;//为指针

Node*cNew;//创建用途指针

//构造函数

game:

:

game（）{

hrp=NULL;

brp=NULL;

cNew=NULL;

personN=0;

}

//新增人

voidCreateOnePerson（game*aGame）{

aGame->cNew=newNode（）;

aGame->personN++;

aGame->cNew->num=aGame->personN;

aGame->cNew->front=aGame->brp;

}

//创建游戏第一人

voidCreateGameBegin（game*aGame）{

if（aGame==NULL）{

cout<<"未创建游戏"<

}else{

CreateOnePerson（aGame）;

aGame->brp=aGame->cNew;

aGame->hrp=aGame->cNew;

aGame->hrp->next=aGame->cNew->next;

aGame->brp->next=aGame->hrp;

}

}

//创建第二人

voidCreateGameSecond（game*aGame）{

CreateOnePerson（aGame）;

aGame->brp->next=aGame->cNew;

aGame->brp=aGame->cNew;

aGame->brp->next=aGame->hrp;

aGame->hrp->next=aGame->cNew;

}

//创建新人节点

voidCreatGameNode（game*aGame）{

CreateOnePerson（aGame）;

aGame->brp->next=aGame->cNew;

aGame->cNew->next=aGame->hrp;

aGame->brp=aGame->cNew;

aGame->brp->next=aGame->hrp;

}

//创建N人游戏

voidCreateGame（intN,game*aGame）{

if（N==0）{

cout<<"无玩家"<

return;

}else{

CreateGameBegin（aGame）;

if（N==1）{cout<<"游戏成功开始"<

CreateGameSecond（aGame）;

if（N==2）{cout<<"游戏成功开始"<

for（inti=3;i<=N;i++）{

CreatGameNode（aGame）;

}

aGame->hrp->front=aGame->brp;

aGame->brp->next=aGame->hrp;

}

cout<<"游戏成功开始"<

}

//删除玩家

voidDeleteGameMember（Node*del,game*aGame）{

Node*temp;

temp=del;

del->front->next=del->next;

del->next->front=del->front;

cout<<"编号为"<num<<"的玩家出局"<

delete（temp）;

}

//删除第一个玩家

voidDeleteGameHeader（game*aGame）{

Node*temp;

temp=aGame->hrp;

aGame->hrp->next->front=aGame->brp;

aGame->brp->next=aGame->hrp->next;

aGame->hrp=aGame->hrp->next;

cout<<"编号为"<num<<"的玩家出局"<

delete（temp）;

}

//删除第最后一个玩家

voidDeleteGamebacker（game*aGame）{

Node*temp;

temp=aGame->brp;

aGame->brp->front->next=aGame->hrp;

aGame->hrp->next=aGame->brp->front;

aGame->brp=aGame->brp->front;

cout<<"编号为"<num<<"的玩家出局"<

delete（temp）;

}

//淘汰传递到M的玩家

voidDelGamePMember（intM,game*aGame）{

//当首尾指针重合，队列中只剩下一个人，游戏方可结束

Node*current=aGame->hrp;//当前删除的位置指针

while（aGame->hrp!

=aGame->brp）{

//确定删除位置，进行判断

for（inti=0;i

current=current->next;

}

//首位置

if（current==aGame->hrp）{

current=current->next;

DeleteGameHeader（aGame）;

}

//尾位置

elseif（current==aGame->brp）{

current=current->next;

game:

:

DeleteGamebacker（aGame）;

}

//普通位置

else{

current=current->next;

game:

:

DeleteGameMember（current->front,aGame）;

}

}

cout<<"剩余玩家为：

编号为"<hrp->num<<"的玩家"<

cout<<"游戏结束，谢谢参与"<

}

};

intmain（）{

gameaGame;

intN,M;

cout<<"请输入参与游戏人数"<

cin>>N;

cout<<"游戏玩家将进行传递。

请输入传递的位数"<

cin>>M;

aGame.CreateGame（N,&aGame）;

aGame.DelGamePMember（M,&aGame）;

return0;

}

8、实验结论、心得体会和改进建议：

1:

使用malloc的时候，在分配内存的时候一定要实现建立好与变量的链接

2：

对于scanf函数，当其输入的值与所设置的值不是同一类型的，系统将自动调用exit函数，退出程序

3：

进行循环的时候，由于玩家是逐一删除，则程序每次就需要全部循环，最坏的情况是n次的循环，算法的复杂度为O（n*m）