数据结构链表实验报告

数据结构链表实验报告（通用5篇）

数据结构链表实验报告 篇1

西华数学与计算机学院上机实践报告

课程名称：数据结构 指导教师：唐剑梅 上机实践名称：

上机实践编号：1 年级： 2011 姓名：蒋俊 学

号

：

***

上机实践成绩：

上机实践日期：2012-11-6

上机实践时间：8:00-9:30

一、实验目的

1.了解线性表的逻辑结构特性，以及这种特性在计算机内的两种存储结构。

2.重点是线性表的基本操作在两种存储结构上的实现；其中以链表的操作为侧重点；并进一步学习程序设计方法。

3.掌握栈这种数据结构特性及其主要存储结构，并能在现实生活中灵活运用。

4.掌握队列这种数据结构特性及其主要存储结构，并能在现实生活中灵活运用。

5.了解和掌握递归程序设计的基本原理和方法。

6.掌握使用 C++面向对象的程序设计技术设计数据结构源程序的方法。

二、实验内容

1.熟悉前面的【程序示例2】，按照约瑟夫问题的方法2，试着不设头结点改写原来的程序，上机调试运行。

2.用链表建立通讯录。通讯录内容有：姓名、通讯地址、电话号码。

要求：（1）通讯录按姓名项的字母顺序排列；

（2）能查找通讯录中某人的信息；

[提示] 用链表来存放这个通讯录，一个人的信息作为一个结点。成链的过程可以这样考虑：先把头结点后面的

西华大学数计学院学生上机实践报告

char name[20];

// 姓名子域

NodeType *next;

// 指针域

};class Jose

//类声明

{ private: NodeType *Head;

public:

Jose(){};

~Jose(){ };

void creat();

void outs();

};void Jose::creat(){ int i=0, n;

NodeType *newp, *pre;

cout<<“n

输入总人数 n=”;cin>>n;

pre=new NodeType;

Head=new NodeType;

pre->num=1;

cout<<“n 编号”<<1<<“的人

姓名=”;

cin>>pre->name;

cout<<“n 密码”<<1<<“的人

密码=”;

cin>>pre->psw;

Head=pre;

Head->next=Head;

for(i=1;i

{ newp=new NodeType;

newp->num=i+1;

cout<<“n 编号”<

姓名=”;cin>>newp->name;

cout<<“n 密码”<

密码=”;

cin>>newp->psw;

newp->next=Head;

pre->next=newp;

pre=newp;

} }

void Jose::outs()

{ int m,i;

NodeType *q=Head, *p;

cout<<“n 输入m值(m>=2)”;cin>>m;

cout<<“n

根据m值，开始报数输出：”<

while(q->next!=q)

西华大学数计学院学生上机实践报告

{ for(i=1;inext;}

cout<<“编号为：”<num<<“ 的人的姓名：”<name<

cout<<“n 编号为:”<num<<“的人的密码：”<psw<

m=q->psw;

p->next=q->next;delete q;

q=p->next;

}

cout<<“编号为：”<num<<“的人的姓名：”<name<

cout<<“n 编号为:”<num<<“的人的密码：”<psw<

delete q;}

int main()

{

Jose h;

h.creat();

h.outs();

return 0;}

西华大学数计学院学生上机实践报告

{ char Add[20];

char name[20];

char tel[20];

};struct NodeType {

ElemType data;

NodeType *next;};class Sqlist

{ private:

NodeType *Head;

public:

Sqlist();

~Sqlist();

void creat();

void Insert(ElemType x);

void Delet(ElemType x);

void PrintOut();

};Sqlist::Sqlist(){

Head=new NodeType;Head->next=NULL;strcpy(Head->data.name,“姓名”);strcpy(Head->data.Add,“地址”);strcpy(Head->data.tel,“电话号码”);} Sqlist::~Sqlist(){

NodeType *p=Head->next;

while(p!=NULL)

{Head->next=p->next;

delete p;

p=Head->next;} } void Sqlist::creat()

//初步建立一个通讯录

{ NodeType*p,*s,*q;ElemType x;

西华大学数计学院学生上机实践报告

int a;q=Head;cout<<“n 输入姓名：”;cin>>x.name;cout<<“n 输入通讯地址：”;cin>>x.Add;cout<<“n 输入电话号码：”;cin>>x.tel;p=new NodeType;p->data=x;Head->next=p;p->next=NULL;cout<<“输入一个数。若为-1，结束输入:”<>a;

while(a!=-1){ cout<<“n 输入姓名：”;cin>>x.name;cout<<“n 输入通讯地址：”;cin>>x.Add;cout<<“n 输入电话号码：=”;cin>>x.tel;s=new NodeType;s->data=x;if(strcmp(s->data.name,p->data.name)>0){ p->next=s;s->next=NULL;

p=s;} else{ s->next=p;q->next=s;} q=q->next;

cout<<“输入一个数。若为-1，结束输入:”<>a;} } void Sqlist::Insert(ElemType x)//插入 { NodeType *p,*q,*s;s=new NodeType;

西华大学数计学院学生上机实践报告

s->data=x;q=Head;p=q->next;while(p!=NULL&&strcmp(p->data.name,x.name)<0){q=p;p=p->next;} s->next=p;q->next=s;} void Sqlist::Delet(ElemType x)//删除 { NodeType *p,*q;q=Head;p=Head->next;while(p!=NULL&&strcmp(p->data.name,x.name)!=0){q=p;p=p->next;} if(p!=NULL){ q->next=p->next;delete p;cout<<“删除结点成功”<

{ NodeType *p;p=Head->next;while(p!=NULL){ cout<

data.name<<“ ”;cout<

data.tel<<“ ”;cout<

data.Add<<“ ”;p=p->next;} cout<

Sqlist as;

cout<<“n

通讯录演示”;

do{

cout<<“nn”;

cout<<“nn

1.初步建立一个通讯录（单链表）

”;

西华大学数计学院学生上机实践报告

cout<<“nn

2.插入新的电话记录 ”;

cout<<“nn

3.删除一个电话记录”;

cout<<“nn

4.结束程序”;

cout<<“n******************************** ”;

cout<<“n

请输入你的选择(1,2,3,4)”;cin>>k;switch(k){ case 1:{ as.creat();as.PrintOut();}break;

case 2:{

cout<<“n 插入的数据 姓名”;cin>>e.name;

cout<<“n 插入的数据 电话号”;cin>>e.tel;

cout<<“n 插入的数据 地址”;cin>>e.Add;

as.Insert(e);as.PrintOut();

}break;

case 3:{

cout<<“n 被删除的姓名= ”;

cin>>e.name;

as.Delet(e);

as.PrintOut();

}break;

default:break;

}

}while(k>=1&&k<4);

cout<<“n

再见!”;

return 0;}

西华大学数计学院学生上机实践报告

西华大学数计学院学生上机实践报告

西华大学数计学院学生上机实践报告

const int MAXSIZE=100;

// 数组的容量 class SqStack

{ private:

ElemType elem[MAXSIZE];

int top;

public:

SqStack();

~SqStack(){};

void SqStack::push(ElemType e);

ElemType SqStack::pop();

void SqStack::PrintOut();

int SqStack::IsEmpty();

void f(ElemType N,ElemType M);};void SqStack::f(ElemType N,ElemType M){ SqStack s;

ElemType e;while(N){

s.push(N%M);

N=N/M;} while(!s.IsEmpty()){

e=s.pop();

if(e>=10)

{

e=e%10;

switch(e)

{

case 1:cout<<“b”<

case 2:cout<<“c”<

case 3:cout<<“d”<

case 4:cout<<“e”<

case 5:cout<<“f”<

default:cout<<“a”<

}

} else

cout<

西华大学数计学院学生上机实践报告

} cout<

{cout<<“栈满溢出”<

return;

}

else{top++;

elem[top]=e;} } ElemType SqStack::pop(){ElemType x;

if(top==0)

{ cout<< “ 栈为空，不能出栈操作”<

else { x=elem[top];

top--;

return x;} } void SqStack::PrintOut()

{int k;

cout<<“n PrintOut Data:n”;

for(k=top;k>=1;k--)cout<

cout<

else return 0;} void main(){ ElemType a,m;cout<<“请输入一个正整数:”<>a;cout<<“请输入要转换的进制:”<>m;SqStack as;as.f(a,m);}

西华大学数计学院学生上机实践报告

五、总结

通过本次实验，我熟悉了链表的操作，了解了线性表在现实生活中的运用，认识了顺序存储和链式存储这两种结构。本次上机实践基本完成了实验内容，但完成的不是很好，以后需要更加努力地掌握基本的知识。实验内容对于队列的运用没有涉及，希望以后有所涉及。

最平价三日链表款揭秘 篇2

目前，一般机械表的动力是42小时，在未持续上链的情况下，走不到2天就停了。能走72小时的3日链机芯，则都是高级款，最少也要人民币3万元起跳。

但天梭此表，定价才人民币6000多元。怎么可能这么便宜？

其中秘密，在此揭开。

3日链的好处在哪里？

3日链功能的奥妙之处，就在于发条盒动力足够让机芯撑过一个周末，保持精准走时，不用在周一上班时还得麻烦再上链与调校。目前，许多高级表都把3日链视为最基础实用的功能。例如日本精工表的高级机芯9S65系列以及沛纳海的自制机芯系列，其最平价表款定价都在人民币3万元以上。

也因此，天梭表这次推出人民币3万元买得到的“平价3日链”，可真的是破坏行情！SWATCH集团近来挟着优势，屡屡打破市场游戏规则。继之前的四逆跳、导柱轮计时，如今再来3日链，也算是表迷之福。

天梭表这款新机芯能够获得3日动能的最大关键，其实是从降低机芯震频换来的。震频从原本的四赫兹降为3赫兹，耗能即大幅降低。同时缩小发条盒轴心的直径，争取多一些空间容纳更长的发条。这两个改变，对机芯稳定度不能说没有影响。不过，天梭表又增加摆轮螺丝微调与无卡度游丝结构，来微调出精准度，并获天文台认证，也算是在牺牲与改进中取得最大平衡。

“一分钱一分货”这句话在表坛虽然未必适用。但最重要是，深入了解奥秘所在，就比较能根据自己的需求去做选择了。

便宜的秘密

这就是天梭表的Powermatic 80天文台认证表，拥有达80小时的动力，比原本的42小时增加近一倍。它以ETA 2824机芯进行改良，将摆轮震频从每小时2.88万次降至2.16万次，同时缩小发条盒中轴结构以增加发条长度，并改进齿轮系节省动能，在未增加机芯尺寸厚度下，成为表坛最平价的自动上链3日链表款。

★TISSOT Powermatic 80

功能：时、分、秒显示；日历窗口

机芯：自动上链机芯

双发条动能

沛纳海的自制机芯P. 9000系列，采用的是“双发条盒”结构来增加动能，以确保在每小时2.88万次震频下也拥有72小时动能，虽然机芯厚度较厚，但沛纳海表款造型诉求原本就硕大阳刚。同时，它也有棘轮双向上链接构与秒针归零校正功能。图片此表为42mm的PAM00392，其尺寸更适合东方人手腕配戴。

★PANERAI Luminor 1950 42mm PAM00392

功能：时、分、小秒针显示；日历窗口

机芯：自动上链机芯

大尺寸动能

IWC的大飞行员表拥有达46mm的尺寸，其51111机芯也是目前全世界最大的自动上链机芯，因此它能装载超大尺寸的发条盒。同时，其摆轮震频为耗能较少的每小时2.16万次（3Hz）。在这两个条件之下，也就能达到长达168小时的7日动力储存。而其专利“比勒顿”上链系统的上链效率也非常高。

★IWC Big Pilot Watch

功能：時、分、秒显示；日历窗口；动力储存显示

机芯：自动上链机芯

高频长动能

日本精工表的Grand Seiko机械表系列所采用的9S65机芯，单一发条盒在2.88万次高震频精准计时的条件下，仍拥有72小时动能，主要是他们采用特殊合金“SPRON510”，比一般合金更薄更长又拥有稳定弹力，加上双向齿轮的高效率上链接构，使发条盒随时补足动能，正常使用下撑过一个周末不成问题。

★SEIKO Grand Seiko Automatic

功能：时、分、秒显示；日历窗口

机芯：自动上链机芯

（陈哲民）

数据结构 队列实验报告 篇3

小组成员：xxxxxxxx日期：xxxxxxxx

一、需求分析（xxx）

1.链队列

1）在本演示程序中，首先要链队列添加一个头结点，并判断队列是否为空，它只允许在表的一端进行插入，而在另一端删除元素，允许插入的一段叫队尾，允许删除的一端则为对头，接着访问队列中所有元素，并输出，输出是每个元素之间用空格来完成。最后销毁队列，释放空间。2）演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“欢迎来到链队列”“元素入队”“元素出队”“销毁队列”“清空队列”之后。由用户在键盘上输入演示程序中规定的运算命令，相应的运算数据和显示结果显示在其后。3）程序执行的命令包括： 欢迎来到链队列 1输出队列长度 2元素入队 3元素出队 4销毁队列 5清空队列 6对头元素 7退出链队列 4）测试数据 入队 1 2 3 4 5 分别执行“元素入队”“元素出队”“销毁队列”“清空队列”等操作。2.顺序队列

1）在本演示程序中，首先要顺序队列添加一个头结点，并判断队列是否为空，它只允许在表的一端进行插入，而在另一端删除元素，允许插入的一段叫队尾，允许删除的一端则为对头，接着访问队列中所有元素，并输出，输出是每个元素之间用空格来完成。2）演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“欢迎来到链队列”“元素入队”“元素出队”“取得头结点”“输出显示”之后。由用户在键盘上输入演示程序中规定的运算命令，相应的运算数据和显示结果显示在其后。3）程序执行的命令包括： 欢迎来到顺序队列 1入队 2出队

3判断是否为空 4取得头结点 5输出显示 6退出顺序队列 4）测试数据 入队 1 2 3 4 5 分别执行“元素入队”“元素出队”等操作。3循环队列

1）在本演示程序中，首先要顺序队列添加一个头结点，并判断队列是否为空，初始化建空队列时，令front=rear=0,每当插入新的队列尾元素时，“尾指针增1”；每当删除队列头元素时，“头指针增1”。接着访问队列中所有元素，并输出，输出是每个元素之间用空格来完成。2）演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“欢迎来到链队列”“元素入队”“元素出队”“取得头结点”“输出显示”之后。由用户在键盘上输入演示程序中规定的运算命令，相应的运算数据和显示结果显示在其后。3）程序执行的命令包括： 欢迎来到循环队列 1入队 2出队

3判断是否为空 4取得头结点 5输出显示 6退出顺序队列 4）测试数据 入队 1 2 3 4 5 分别执行“元素入队”“元素出队”等操作。

二．概要设计(xxxx)

⒈ 为实现上述算法，需要顺序表的抽象数据类型，抽象数据类型定义如下：

ADT Queue { 数据对象：D={ ai|ai∈ElemSet, i=1,2,3...,n, n>=0 } 数据关系: R={ |ai-1,ai∈D,i=2,...,n } 基本操作： InitQueue(&Q)操作结果：构造一个空队列。DestroyQueue(&Q)初始条件：队列Q已存在。

操作结果：队列Q已被销毁。ClearQueue(&Q)初始条件：队列Q已存在。

操作结果：将Q清为空队列。QueueEmpty(Q)初始条件：队列Q已存在。

操作结果：若Q为空队列，则返回TRUE,否则FALSE。QueueLength(Q)初始条件：队列Q已存在。

操作结果：返回Q元素的个数，即队列的长度。GetHead(Q,&e)初始条件:Q为非空队列。

操作结果：用e返回Q的队头元素。EnQueue(&Q,e)初始条件：队列Q已存在。

操作结果：插入e返回Q的新的队尾元素。DeQueue(&Q，&e)初始条件：Q为非空队列。

操作结果：删除Q的队头元素，并用e返回其值。}ADT Queue

2.单链队列

typedefstructQNode { QElemType;structQNode *next;//指针域 }QNode,*QueuePtr;Typedefstruct{ QueuePtr front;QueuePtr rear;}LinkQueue;Status InitQueue(LinkQueue&Q)//构造一个空队列。

Status DestroyQueue(LinkQueue&Q)//销毁队列Q，Q不存在。

Status ClearQueue(LinkQueue&Q)//将Q清为空队列。

Status QueueEmpty(LinkQueueQ)//若Q为空队列，则返回TRUE,否则FALSE。intQueueLength(LinkQueueQ)//返回Q元素的个数，即队列的长度。

Status GetHead(LinkQueueQ,QElemType&e)//若队列不为空，则用e返回Q的队头元素，并返回OK;否则返回ERROR。

Status EnQueue(LinkQueue&Q,QElemType e)//插入e返回Q的新的队尾元素。

Status DeQueue(LinkQueue&Q,QElemType&e)//若队列不空，则删除Q的队头元素，并用e返回其值，并返回OK;否则返回ERROR。

三．详细设计（xxx）

1.顺序队列的实现和运算

1）元素的类型 typedefstruct { Datatypedata[MAXSIZE];intfront,rear;}Squeue;2）空的队列的构造

void InitSqueue(Squeue *p)/*初始化队列*/ { p->front=0;p->rear=0;} 3）元素的入队

int Ensqueue1(Squeue1 *q, Datatype e)/*入队*/ { if((q->rear+1)% MAXSIZE == q->front){ printf(“n队列已满n”);return 0;} 4）元素的出队

int DeSqueue1(Squeue1 *q,Datatype *e)/*出队*/ { if(q->front==q->rear){ printf(“队列已空,无法出队!”);return 0;} *e=q->data[q->front];q->front=(q->front+1)%MAXSIZE;return 1;} 5）判断队列是否为空

int QueueEmpty1(Squeue1 q)// 判断是否为空 { if(q.front==q.rear)return 1;else return 0;} 6）队头元素的取值的算法

int Gethead1(Squeue1 *q,Datatype *e)// 取对头元素 { if(q->front==q->rear){ printf(“队列已空，无法出队!”);return 0;} else *e=q->data[q->front];return 1;} 7）遍历顺序队列的算法

void display1(Squeue1 q)//遍历顺序对列 { printf(“此队列数据为:n”);if(q.front==q.rear)printf(“此队列为空!”);else { while(q.front

void InitQueue2(LinkQueue *q){ // 构造一个空队列Q q->front=q->rear=malloc(sizeof(QNode));if(!q->front)exit(1);q->front->next=NULL;} 2）元素的入队算法

void EnQueue2(LinkQueue *q, QElemType e)//将元素e进队 { QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode));//创建新节点

if(!p)//如果内存分配成功

exit(1);

p->data=e;//初始化新节点数据为e p->next=NULL;

q->rear->next=p;

q->rear=p;} 3）元素的出队的算法

int DeQueue2(LinkQueue *q,QElemType e)//队头结点出队,将出队的元素存入e { QueuePtr p;if(q->front==q->rear)//队列为空

return 0;p=q->front->next;//初始化temp为要出队的结点指针

if(q->front->next==q->rear)//要出队的结点为最后一个结点

q->rear=q->front;e=p->data;//要出队的数据元素为e q->front->next=p->next;//使下一个结点变为对头

free(p);//删除要出队的结点

return e;} 4）队列的长度算法

void QueueLength2(LinkQueue *q)//返回队列长度 { QueuePtr p;int i=0;p=q->front->next;while(p){

++i;

p=p->next;} printf(“链队列长度为:%dn”,i);} 5）队列的销毁

void DestroyQueue2(LinkQueue *q){ while(q->front){

q->rear=q->front->next;

free(q->front);

q->front=q->rear;

if(!q->rear)

free(q->rear);} free(q->front);} 6）队列的输出算法

void output2(LinkQueue *q)//输出队列 { QueuePtr p;p=q->front->next;printf(“链队列元素依次为:”);while(p){

printf(“%d->”,p->data);

p=p->next;} printf(“n”);} 7）队列的清空的算法 void Clear2(LinkQueue *q)//清空队列 { QueuePtr temp=q->front->next;while(temp){

QueuePtrtp=temp;

temp=temp->next;

free(tp);} temp=q->front;

q->front=q->rear=NULL;free(temp);} 8）返回对头元素的算法

int GetHead2(LinkQueue *q, int *e)//返回对头结点元素，存入e { if(q->front==q->rear)

return 0;*e=q->front->next->data;return 1;} 3.循环队列的实现和运算 1）队列的初始化算法

void InitSqueue3(Squeue3 *p)/*初始化队列*/ { p->base=(Datatype *)malloc(sizeof(Datatype)* MAXSIZE);p->front=0;p->rear=0;} 2）入队的算法

int Ensqueue3(Squeue3 *q, Datatype e)/*入队*/ { if((q->rear+1)% MAXSIZE == q->front){ printf(“n队列已满n”);return 0;} else q->base[q->rear]=e;/*将接收到得值付给队尾所指的节点*/ q->rear=(q->rear+1)% MAXSIZE;/*队尾向后移一位完成入队*/ return 1;} 3）出队的算法

int DeSqueue3(Squeue3 *q,Datatype *e)/*出队*/ { if(q->front==q->rear){ printf(“队列已空,无法出队!”);return 0;} *e=q->base[q->front];q->front=(q->front+1)%MAXSIZE;return 1;} 4判断队列是否为空的算法

int QueueEmpty3(Squeue3 q)// 判断是否为空 { if(q.front==q.rear)return 1;else return 0;} 5）对头元素的返还的算法

int Gethead3(Squeue3 *q,Datatype *e)// 取对头元素 { if(q->front==q->rear){ printf(“队列已空，无法出队!”);return 0;} else *e=q->base[q->front];return 1;} 6）遍历循环队列的算法

void display3(Squeue3 *q)//遍历循环对列 { int tail;tail=q->front;printf(“此队列数据为:n”);if(q->front==q->rear)printf(“此队列为空!”);else { while(tail!=q->rear){ printf(“%dt”, q->base[tail]);tail=(tail+1)%MAXSIZE;} printf(“n”);} } 4.主函数的算法 void main(){

int choice;Datatype e1;int i1,a1,x1,s1,j1;//顺序队列定义的量 int e2,i2,n2,s2,a2;//链队列定义的量

int i3,a3,x3,s3,j3;//循环队列定义的量 Datatype e3;

Squeue1 Q1;

//******************************* LinkQueue q;

//******************************** Squeue3 Q;

//**************************** choice=-1;Begin();while(choice!=0){ scanf(“%d”,&choice);switch(choice){ case 1://顺序队列

{

system(“cls”);InitSqueue1(&Q1);printf(“创建队列完成!n”);printf(“请输入数据个数j1=”);scanf(“%d”,&j1);for(i1=1;i1<=j1;i1++)//输入的数据个数不要超过MAXSIZE,多了的部分没有插入队列

{ printf(“请输入第%d个数据:”,i1);scanf(“%d”,&a1);Ensqueue1(&Q1,a1);

} printf(“对头为:%dn”,Q1.data[Q1.front]);printf(“队尾为:%dn”,Q1.data[Q1.front+j1-1]);display1(Q1);s1=-1;start1();while(s1!=0)

{

scanf(“%d”,&s1);switch(s1)

{ case 0:

system(“cls”);

choice=-1;

Begin();

break;case 1:

{

system(“cls”);printf(“请输入入队元素:n ”);scanf(“%d”,&x1);Ensqueue1(&Q1,x1);display1(Q1);

s1=-1;

start1();break;

} case 2:

{ system(“cls”);DeSqueue1(&Q1,&e1);display1(Q1);s1=-1;

start1();break;

} case 3:

{

system(“cls”);if(QueueEmpty1(Q1))printf(“此队列为空!n”);else printf(“此队列不为空!n”);

}

s1=-1;

start1();break;case 4:

{ system(“cls”);

Gethead1(&Q1,&e1);printf(“对头元素为:%dn”,e1);

s1=-1;

start1();break;

} case 5:

{ system(“cls”);display1(Q1);s1=-1;

start1();break;

}

}//switch

} //while

}//case1

break;//************************************************* case 2:

{

system(“cls”);

InitQueue2(&q);printf(“创建队列完成!n”);printf(“输入将建立链队列元素的个数:n2=”);scanf(“%d”,&n2);printf(“请输入队列的元素：n”);for(i2=1;i2<=n2;i2++)

{

printf(“请输入第%d个元素:”,i2);

scanf(“%d”,&e2);

EnQueue2(&q,e2);

} a2=-1;start2();while(a2!=0)

{

scanf(“%d”,&a2);

switch(a2)

{

case 1:system(“cls”);

QueueLength2(&q);

a2=-1;start2();

break;

case 2:{

system(“cls”);

printf(“请输入入队元素:”);

scanf(“%d”,&e2);EnQueue2(&q,e2);

output2(&q);a2=-1;start2();

}break;

case 3:

system(“cls”);

e2=DeQueue2(&q,e2);

output2(&q);

printf(“出队元素为:%dn”,e2);a2=-1;start2();

break;

case 4:DestroyQueue2(&q);printf(“队列已销毁!n”);

a2=0;system(“cls”);

choice=-1;

Begin();

break;

case 5:

Clear2(&q);printf(“队列已清空n”);

a2=0;system(“cls”);

choice=-1;

Begin();

break;

case 6:

system(“cls”);GetHead2(&q,&e2);

printf(“队头元素为:%dn”,e2);s2=-1;

start2();

break;

case 0: system(“cls”);

choice=-1;

Begin();

break;

}//switch }//while

}//case2

break;//**************************************************

case 3:

{

system(“cls”);

InitSqueue3(&Q);printf(“创建队列完成!n”);printf(“请输入数据个数j3=”);scanf(“%d”,&j3);for(i3=1;i3<=j3;i3++)//输入的数据个数不要超过MAXSIZE,多了的部分没有插入队列

{ printf(“请输入第%d个数据:”,i3);scanf(“%d”,&a3);Ensqueue3(&Q,a3);

} printf(“对头为:%dn”,Q.base[Q.front]);printf(“队尾为:%dn”,Q.base[Q.front+j3-1]);display3(&Q);s3=-1;start3();while(s3!=0)

{

scanf(“%d”,&s3);switch(s3)

{ case 0:

system(“cls”);

choice=-1;

Begin();

break;case 1:

{

system(“cls”);printf(“请输入入队元素:n ”);scanf(“%d”,&x3);Ensqueue3(&Q,x3);display3(&Q);

s3=-1;

start3();break;

} case 2:

{ system(“cls”);DeSqueue3(&Q,&e3);display3(&Q);s3=-1;

start3();break;

} case 3:

{ system(“cls”);if(QueueEmpty3(Q))printf(“此队列为空!n”);else printf(“此队列不为空!n”);

}

s3=-1;

start3();break;case 4:

{ system(“cls”);

Gethead3(&Q,&e3);printf(“对头元素为:%dn”,e3);

s3=-1;

start3();break;

} case 5:

{ system(“cls”);display3(&Q);s3=-1;

start3();break;

}

}//switch

} //while

}//case 3

break;

case 0:

printf(“ 谢谢使用！！n”);

break;

//***************************

}//switch }//while }//main

四．调试分析（xxx）

顺序队列

1.编译并调试，运行程序。

2.设计测试用例，分析测试结果，以验证所完成的系统是否达到预期效果。3.判断队列是否为空。队列是否为空的标志就是队头指针和队尾指针是否同时指向队列中的同一个位置，即队头指针和队尾指针是否相等。

4.队列满时候不能入队列，否则会出现溢出现象。即先要判断队列是否已经已满，因为队尾指针的最大值是MAXQSIZE，所以通过检查队尾指针rear是否等于MAXQSIZE来判断队列是否已满。在删除队首元素时，应首先通过队头指针和队尾指针是否相等判断队列是否已空。

5.在元素出队操作，先通过队头指针和队尾指针是否相等判断队列是否已空，空时不能操作，这是要注意的。

6.程序满足了本次试验的目的和任务要求，可以进行人机交互，在后来的程序中将会做些改进，以增强人机交互性。

7.本程序存在较多不足，如有问题，参考用户手册。

8.在程序语句中，原本使用了大量的生僻的函数名，经过改进，目前使用都是通俗易懂的函数名称，方便用户理解。

链队列

1.编译并调试，运行程序。2.设计测试用例，分析测试结果，以验证所完成的系统是否达到预期效果。

3.要注意设定一个在链队列添加一个头结点并令指针指向头结点。同时，删除不可以在最后面进行删除，但是插入可以最后一个进行插入，这点需要注意 4.需要分别指向队头和队尾的指针。

5.程序满足了本次试验的目的和任务要求，可以进行人机交互，在后来的程序中将会做些改进，以增强人机交互性。

6.本程序存在较多不足，如有问题，参考用户手册。

7.在程序语句中，原本使用了大量的生僻的函数名，经过改进，目前使用都是通俗易懂的函数名称，方便用户理解。

循环队列

1.编译并调试，运行程序。

2.设计测试用例，分析测试结果，以验证所完成的系统是否达到预期效果。

3.为了避免顺序队列造成的“假溢出”现象，我们通常采用顺序循环队列实现队列的顺序存储。4.队头指针和对尾指针与队列元素之间关系和顺序队列一样，不变。5.先判断队列是否为空。就是看队头指针和队尾指针是否同时指向队列中的同一个位置，即队头指针和队尾指针是否相等，空时不能操作，这是要注意的。

6.在将元素插入到队列之前首先要判断队列是否已经已满，根据顺序循环队列队满条件front==(rear+1)%MAXQSIZE来判断队列是否已满。在删除队首元素时，应首先通过队头指针和队尾指针是否相等判断队列是否已空。

6.程序满足了本次试验的目的和任务要求，可以进行人机交互，在后来的程序中将会做些改进，以增强人机交互性。

7.本程序存在较多不足，如有问题，参考用户手册。

8.在程序语句中，原本使用了大量的生僻的函数名，经过改进，目前使用都是通俗易懂的函数名称，方便用户理解。

五、用户手册(xx)1.链队列

(1)本程序的运行环境为DOS操作系统，执行文件名为：j.exe.(2)进入演示程序后即显示文本方式的用户界面，输入元素1,2,3,4,5创建队列。

（3）根据提示，选择操作2执行元素入队操作。回车，输入入队元素0，回车，将0插入到队列中。

（4）选择操作3执行元素出队操作，回车，队首元素1出队。

（5）选择操作1执行输出队列长度操作，回车，输出队列长度为5.（6）选择操作5执行清空队列操作，回车，清空。

（7）选择操作6执行输出队头元素操作，回车，输出元素2。

2.顺序队列

（1）创建队列，输入数据

1,2,3,4,5.（2）选择操作1，执行入队操作.输入入队元素0

（3）选择操作2，执行出队操作。

队首元素1出队.（4）选择操作3，判断对是否为空

（5）选择操作4，输出对头元素2.（6）选择操作5，显示队列元素

3、循环队列

（1）创建队列，输入数据 1,2,3,4,5.（2）选择操作1，执行入队操作.输入入队元素0

（3）选择操作2，执行出队操作。队首元素1出队.（3）选择操作3，判断对是否为空

（5）选择操作4，输出对头元素2.（6）选择操作5，显示队列元素为,2,3,4,5,0

六．测试结果（xxx）1.顺序队列的实现和运算

1）输入1即可进行进入到顺序队列

2）顺序队列的建立，输入元素的个数为5，输入的数据分别为1，2，3，4，5，对头为1，队尾为5，此时队列的数据为1 2 3

3）输入2即可进行入队运算，输入的入队元素为0，此时的队列的数据为1 2 3 4 5 0

4）输入3即可进行判断队列的是否为空，如下图：

5）输入4即可进行去的对头元素的算法，如下图所示：

6）此时的队列的数

据

为

0，如

下

图

：

7）输入0即可退出顺序队列，如下图：

8）输入3即可进行顺序队列的算法，如下图所示：

9）输入1即可进

行

相

应的入

队

运

算，如

下

10）输入2即可进行队列的出队运算，如下图所示：

所

示

图

：11）输入3

即可判断顺序队列是否为空的算法，如下图所示：

12）输入4即可进行去的头结点的运算，如下图所示：

13）输入5即可进行队列的输出显示的运算，如

14）输入0即可进行退出顺序队列的算法，如下图所示：

下图所示：2.链式队列的实现和运算

1）队列的建立以及队列的个数输入为5，输入的数据分别为1，2，3，4，5.如下图：

2）输入2即可进入到元素的入队运算，输入入队的元素的为0，输入3即可进行相应的元素的出队运算，出队元素为1.如下图：

3）则此时的队列的长度为5，输入4即可进行队列的销毁以及输入5即可进行队列的清空运算，如下图：

4）输入6即可进行输出队列的对头元素，输入0即可进行退出链队列的运算

3．循环队列的实现和运算

1）输入3即可进行循环队列的操作，输入5个数据，它们分别为1 2 3 4 5，输入1，即可进行入队操作，输入入队的元素为0，则此时的数据为1 2 3 4 5 0，如下图所示：

2）输入2即可进行出队运算，如下图所示：

3）输入3即可进行判断队列的是否为空，如下图所示：

4）输入4即可进行取得对头元素，如

下

5)输入5即可进行输出所有的数据显示，如下图所示：

所示图：

七．心得体会（xx）

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。

数据结构实验报告2.3 篇4

题目三：舞伴问题

【实验目的】

1、掌握栈和队列的顺序存储结构和链式存储结构，以便在实际中灵活应用。

2、掌握栈和队列的特点，即后进先出和先进先出的原则。

3、掌握栈和队列的基本运算，如：入栈与出栈，入队与出队等运算在顺序存储结构和链式存储结构上的实现。【问题描述】

假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队。跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴。若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。现要求写一算法模拟上述舞伴配对问题。

【实验要求】

利用队列实现，存储结构采用顺序或链式均可

【编程思路】

男女配对问题的原则是先入先出进行配对，因此该问题具体有典型的先进先出特性，可用队列作为算法的数据结构。在算法中，假设男士和女士的记录存放在一个数组中作为输入，然后依次扫描该数组的各元素，并根据性别来决定是进入男队还是女队。当这两个队列构造完成之后，依次将两队当前的队头元素出队来配成舞伴，直至某队列变空为止。如果某组有剩余则参与第二轮的配对，并将第一个需要配对学生的信息返回；如果完全配对，则返回信息，不再进行下一轮的配对。

开始时男士和女士的记录存放在一个结构体数组中作为输入，另外需要构建两个队列来保存男队和女队。无论是结构体数组还男女队列的元素或结点都采取结构体类型。作为输入的结构体数组可以事先创建即初始化时便将数据保存进去，也可以在程序运行时创建。

男女队列的存储类型可以采取顺序或链式结构。二者的原理基本一致，但在操作上却有所不同：

1、顺序存储结构的长度确定，存储容量有限。开辟空间很大的话又浪费存储空间，一种解决方案是采用循环队列，可是本题目是将所用元素都存储完成以后才进行删除，采用循环队列便失去了意义。

2、链式存储结构长度不固定，输入数据可以不固定。相比于顺序存储结构操作简单。由于，输入数据是放在结构体数组中的，其最大长度已确定，间接限制了队列的最大长度，故采用顺序存储结构。确定好存储的类型之后，将结点的类型定义如下：

结点类型：结构体Node

结构体的数据成员：string型变量Name用来保存姓名

Char型变量Sex用来保存性别

typedef struct

计科101 冯康 201000814128 { Node*base;int Front;int Rear;}LinkQueue;用此结构体创建结构体变量来完成队列的各项操作。接下来进行队列的创建、出队列和判断队列是否为空等，具体操作将在代码解析中介绍。【代码解析】

男女队列创建函数：void Creat(LinkQueue&p,LinkQueue&q,Node s[])

注：p、q分别是操纵男女队列的结构体，s[]为保存男女学生信息的数组

通过 p.base=new Node[n]和q.base=new Node[n]分别为为男女队列开辟数组空间，空间大小n由主函数中输入。为了程序的健壮性，需要判空。代码如下：

if(!p.base&&!q.base){

cout<<“操作失败！”<

exit(1);} 如果开辟内存空间成功，则将队列中的各个元素进行赋初值：

p.Front=p.Rear=0;q.Front=q.Rear=0;根据性别信息将n个男女学生对号入座放入上面开辟的空间中: for(int i=0;i

if(s[i].Sex==0)

{

p.base[p.Rear].Name=s[i].Name;

p.base[p.Rear].Sex=s[i].Sex;

p.Rear++;

}

else

{

q.base[q.Rear].Name=s[i].Name;

q.base[q.Rear].Sex=s[i].Sex;

q.Rear++;

} } 进行男女学生配对及确定下一轮要进行跳舞学生信息。其函数为：LinkQueue*Dance(LinkQueue&p,LinkQueue&q)一直进行循环，将男女生进行配对。最后的结束条件是至少有一个队列为空：

while(p.Front!=p.Rear&&q.Front!=q.Rear)//循环结束条件 {

cout<

p.Front++;q.Front++;//进行学生配对 }

if(p.Front!=p.Rear)

return &p;//如果男生队列有剩余则将男生队列返回

计科101 冯康 201000814128

} else if(q.Front!=q.Rear)

return &q;//如果女生队列有剩余则将女生队列返回

else return NULL;//如果男女学生刚好配对则返回空指针

【测试数据】

【实验体会】

对于面向过程编程而言，程序=数据+算法，在编写程序之前首先要对题目要求进行分析和思考。等把问题弄明白后，就要根据事件发展过程，依靠程序来模仿事件，进而形成编程思路，最后确定算法。一般而言，在编程思路路形成以后，根据程序执行过程选择最优算法，当这些都完成以后，编写代码及调试就没有太大麻烦了，所以首先要形成编程思路。刚开始的时候我直接在开发环境下一边看题一边写代码，瞪了半天什么也没写出来，于是我便先开始在纸上画画写写，将事件的整个过程画下来，然后考虑怎么才能运用代码来实现，一边思考一边写一些粗略的代码，最后从上到下执行代码看看是不是符合题目要求。有没有什么漏 3

计科101 冯康 201000814128 洞。等这些完成以后，再在开发环境下将代码完善、编译和调试。虽然说代码还有许多要改进的的地方，有的功能还不够完善，可毕竟是自己亲自写出来的，对于程序的条理有了一个清晰的了解，对编程也有了更加深刻的认识。【附录代码】

#include #include using namespace std;static int n=0;struct Node { string Name;int Sex;};typedef struct { Node*base;int Front;int Rear;}LinkQueue;void Creat(LinkQueue&p,LinkQueue&q,Node s[]){ p.base=new Node[n];q.base=new Node[n];if(!p.base&&!q.base){

cout<<“操作失败！”<

exit(1);} p.Front=p.Rear=0;q.Front=q.Rear=0;for(int i=0;i

if(s[i].Sex==0)

{

p.base[p.Rear].Name=s[i].Name;

p.base[p.Rear].Sex=s[i].Sex;

p.Rear++;

}

else

{

q.base[q.Rear].Name=s[i].Name;

q.base[q.Rear].Sex=s[i].Sex;

q.Rear++;

计科101 冯康 201000814128

} } } LinkQueue*Dance(LinkQueue&p,LinkQueue&q){ while(p.Front!=p.Rear&&q.Front!=q.Rear){

cout<

p.Front++;

q.Front++;}

if(p.Front!=p.Rear)

return &p;

else if(q.Front!=q.Rear)

return &q;

else

return NULL;} int main(){ Node s[100];cout<<“输入性别:0表示男生，表示女生”<>n;for(int i=0;i

cout<<“No”<

cin>>s[i].Name;

cout<<“No”<

cin>>s[i].Sex;} LinkQueue p,q;Creat(p,q,s);LinkQueue*t=Dance(p,q);if(t!=NULL)

cout<<“下一轮开始人员的名字是：”<base[t->Front].Name<

cout<<“男女搭配刚好完成！”<

数据结构链表实验报告 篇5

数据结构实验教学实例“数据结构”课程是高等院校理工科专业的一门必修课程，是计算机科学领域中的一门重要基础课。该课程主要介绍如何利用算法实现各种数据在计算机中的存储和处理，其重点学习内容包括：顺序表、链表、栈和队列、数组、树与森林、图、查找、排序等。通过本课程的学习，使学生深透地理解数据结构的基本概念和基础算法，培养学生良好的程序设计技能，锻炼学生通过编程解决实际问题的能力。为后续相关专业课程的学习打下坚实的基础，为从事计算机科学领域的研究和开发打下理论和实验的基础。

“数据结构”的课程实验不仅帮助学生理解数据结构的基本概念和基础算法，而且培养学生良好的算法技能，锻炼学生通过编程解决实际问题的能力。

一、“数据结构”实验教学中存在的问题

在大多数院校，按照教学大纲和实验大纲安排，“数据结构”课程一般在大学期间的第三学期或者第四学期开设，并且前期已开设一门程序设计基础课程。其总教学学时72学时，其中理论教学54学时，实验教学18学时。目前，在实验教学的整个过程中存在以下几个问题。

1.学生对实验教学重视程度不够。“数据结构”课程的理论知识多是用伪代码写的，学生往往侧重于算法的理解，忽略了算法的实现。教材中的算法往往是伪代码或者是程序段，学生要想将算法实现，就需要把伪代码或者程序段放到带有数据的实例中，用正确的、可执行的程序实现，然后调试运行，查看算法结果。而这一过程，一方面，比较复杂；另一方面，不是“数据结构”课程的重点，所以往往会被老师和学生忽略。但是这一过程恰恰是帮助学生透彻理解算法，帮助学生把算法与实际应用结合。

2.实验项目设置关联性。每一个实验项目对应一定的理论知识，实验项目之间不相关，学生做完做不完都不会影响下次实验，导致很多学生对一些实验不够重视，主动性不高。有一些学生在个别实验项目没有做完的情况下，没有主动的在课下完成，在下次实验课上也没有主动积极的补做，时间久了，越积越多，最终导致这门课程学得不好，也必然影响后续课程的学习。

3.实验项目内容设置缺乏与实例的结合。实验不仅仅是理论知识巩固，更是知识总结和能力的提高。实验内容的设置不能仅仅考虑理论知识体现，更应考虑如何让学生在理解理论的同时和实际应用相结合，培养学生把理论应用于实际的主动性。目前，大多数学生学习态度是被动的，不愿意去多想，不愿意去扩展。教师在设计实验项目时要引导他们去联系实际，去扩展内容。这样持续下去，学生才会在掌握理论知识的同时，和实际应用相结合，掌握算法的精髓。

针对以上存在的问题，在“数据结构”实验教学中我们设计了与实例紧密结合的分层次的实验教学模式。这一教学模式由易到难、由单一到综合，逐步培养学生的算法编写能力。我们将整个实验教学分成基础篇、提高篇、专项篇等三个阶段，每个阶段完成一定的知识目标和理论目标。

二、“数据结构”实验教学模式

多数高校的教学计划中，“数据结构”课程的实验教学是18学时，我们将18学时分为9个实验项目，分别为：顺序表的操作、单链表的操作、栈的操作、队列的操作、数组的操作、二叉树的操作、图的操作、查找操作、排序操作。不同实验项目结合不同的实例，划分到不同的层次，具体实施如下。

1.基础篇。“数据结构”实验教学的初级阶段属于基础篇的内容，是对教材的理论知识点的简单实现。实验项目中顺序表的操作、单链表的操作、栈的操作、队列的操作等属于基础篇的实验，这一阶段的实验实例相对简单，重点在于让学生掌握基本的数据结构类型。这一阶段的顺序表实验和单链表实验用的实例是学生成绩管理系统，这里对学生的信息只存储学号和姓名，成绩信息可以存储一门到三门课程的成绩。这样数据比较简单，着重让学生掌握线性表的顺序存储和链式存储。对于栈的操作采用的是火车车厢重排问题的案例，这里要求学生也要通过顺序和链式两种存储方式实现。对于队列操作的实验采用的实例是银行排队叫号系统。在银行排队叫号系统这一实例中要求学生不能仅仅使用一个队列，一次简单的先进先出操作实现，需要学生考虑到一个排号队列，多个叫号队列的情况，让学生有所思考，从而实现对队列操作的深入理解。

2.提高篇。通过基础篇实验的学习，学生对线性表、栈、队列等基本数据结构有了深刻的认识，对顺序存储结构和链式存储结构的使用有了一定的基础。接下来要学习的是较为复杂的数据结构：数组、树和图。数组的操作、二叉树的操作、图的操作等实验就是提高篇要完成的实验内容。这一阶段接触的是复杂的数据结构，但核心还是运用基础篇学习的基本数据结构，实例的选择也会较为复杂。数组操作的实验选择的实例是超市物品购买数据存储系统。这个实例中要处理的数据不是简单的数组，其需要的数组较大，但存储的数据较少，这就是典型的系数矩阵。在现实生活中这类数据经常遇到，对这类数据的存储和操作就要通过数组操作的实验进行学习和掌握。树操作通过二叉树实现的，所以树这一章节的实验设置的是二叉树的操作，结合的实例是磁盘文件的记录系统，着重是运用线索二叉树的知识。图操作的实验用的实例是高速公路交通网这一经典案例。这一实例不仅运用了图的遍历操作，还用了最短路径等经典算法。通过这些提高篇的实验项目学生对复杂的数据结构有所掌握，也对数据结构的复杂应用有所了解。

3.专项篇。对于大多数数据的处理都会用到两种典型的操作：查找和排序。数据结构课程的后期都会讲到这两项内容，同样也会有两项专门的实验来对应。查找操作和排序操作采用的实例分别是奥运会奖牌的排行榜的查询和排名，着重让学生掌握不同的查找方法和排序方法。需要学生熟记一些经典的查找算法和排序算法，会对不同的算法比较优劣，同时也对时间复杂度和空间复杂度有所了解。

基础篇、提高篇、专项篇这三个实验阶段，由易到难，相辅相承，让学生逐步掌握不同数据结构的定义和使用，进而培养学生的算法编写能力。具体在实施过程中根据学生的实际接受情况和掌握情况对具体实验内容进行增减。

三、实验效果

我们在2012级学生的“数据结构”课程教学中开始探索这一实验教学模式，在2013级学生的“数据结构”课程教学中进一步完善，效果很好。学生学习的积极性明显提高，学习效果也有了明显的提高。

经过一系列的实验教学实践，我们针对“数据结构”课程，探索出了由基础篇、提高篇、专项篇这个三个阶段组成的与实例紧密结合的实验教学模式。这一教学模式由易到难，逐步培养学生的算法编写能力。今后，我们将继续结合教学实际进一步完善实验教学文件、丰富“数据结构”课程实验内容和课程设计的内容，从而提升“数据结构”课程的教学效果。

参考文献：

[1]黄贤英.计算机专业实验教学体系建设思考[J].实验技术与管理，2009，（10）：94-100.

[2]马彬.三维一体化的计算机实验教学建设体系[J].实验室研究与探索，2013，（10）：163-165.