数据结构实验报告

发布时间：2024-11-25

线性表、链表、链栈、循环队列实验报告(含程序代码及截图)

数据结构实验报告

姓名： 学号： 专业： 班 级： 指导教师： 实验时间： 实验地点：

（实验题目）

1. 实验内容和要求

实验一 顺序表实验

实验要求 1、顺序表结构定义，算法的实现以库文件方式实现，库文件名统一为seqList.h； 2、实验程序有较好可读性，各运算和变量的命名直观易懂，符合软件工程要求； 3、程序有适当的注释。 实验任务

编写算法实现下列问题的求解。

<1>求顺序表中第i个元素（函数），若不存在，报错。 实验测试数据基本要求：

第一组数据：顺序表长度n≥10，i分别为5，n，0，n+1，n+2 第二组数据：顺序表长度n=0，i分别为0，2

<2>在第i个结点前插入值为x的结点。 实验测试数据基本要求：

第一组数据：顺序表长度n≥10，x=100, i分别为5,n,n+1,0,1,n+2 第二组数据：顺序表长度n=0，x=100，i=5

<3>删除顺序表中第i个元素结点。 实验测试数据基本要求：

第一组数据：顺序表长度n≥10，i分别为5,n,1,n+1,0 第二组数据：顺序表长度n=0， i=5

<4>在一个递增有序的顺序表L中插入一个值为x的元素，并保持其递增有序特性。

实验测试数据基本要求：

顺序表元素为 （10,20,30,40,50,60,70,80,90,100）, x分别为25，85，110和8

<5>将顺序表Ｌ中的奇数项和偶数项结点分解开（元素值为奇数、偶数），分别放入新的顺序表中，然后原表和新表元素同时输出到屏幕上，以便对照求解结果。 实验测试数据基本要求：

第一组数据：顺序表元素为 （1,2,3,4,5,6,7,8,9,10,20,30,40,50,60） 第二组数据：顺序表元素为 （10,20,30,40,50,60,70,80,90,100）

线性表、链表、链栈、循环队列实验报告(含程序代码及截图)

<6>求两个递增有序顺序表L1和L2中的公共元素，放入新的顺序表L3中。 实验测试数据基本要求： 第一组

第一个顺序表元素为 （1，3，6，10，15，16，17，18，19，20）

第二个顺序表元素为 （1，2，3，4，5，6，7，8，9，10，18，20，30） 第二组

第一个顺序表元素为 （1，3，6，10，15，16，17，18，19，20） 第二个顺序表元素为 （2，4，5，7，8，9，12，22） 第三组

第一个顺序表元素为 （）

第二个顺序表元素为 （1，2，3，4，5，6，7，8，9，10）

实验二 单链表实验

实验要求

1、本次实验中的链表结构均为带头结点的单链表； 2、链表结构定义，算法实现放入库文件“linkList.h”； 3、运算和变量命名直观易懂，并有相应的注释。 实验任务

编写算法实现下列问题的求解。

<1>求链表中第i个结点的指针（函数），若不存在，则返回NULL。 实验测试数据基本要求：

第一组数据：链表长度n≥10，i分别为5，n，0，n+1，n+2 第二组数据：链表长度n=0，i分别为0，2

<2>在第i个结点前插入值为x的结点。 实验测试数据基本要求：

第一组数据：链表长度n≥10，x=100, i分别为5,n,n+1,0,1,n+2 第二组数据：链表长度n=0，x=100，i=5

<3>删除链表中第i个元素结点。 实验测试数据基本要求：

第一组数据：链表长度n≥10，i分别为5,n,1,n+1,0 第二组数据：链表长度n=0， i=5

<4>在一个递增有序的链表L中插入一个值为x的元素，并保持其递增有序特性。 实验测试数据基本要求：

链表元素为 （10,20,30,40,50,60,70,80,90,100）, x分别为25，85，110和8

<5>将单链表Ｌ中的奇数项和偶数项结点分解开（元素值为奇数、偶数），申请2

线性表、链表、链栈、循环队列实验报告(含程序代码及截图)

个头结点，把分开的奇数项和偶数项分别链接到这2个头结点上，然后再将这两个新链表同时输出在屏幕上，并保留原链表的显示结果，以便对照求解结果。 实验测试数据基本要求：

第一组数据：链表元素为 （1,2,3,4,5,6,7,8,9,10,20,30,40,50,60） 第二组数据：链表元素为 （10,20,30,40,50,60,70,80,90,100）

<6>求两个递增有序链表L1和L2中的公共元素，并以同样方式连接成链表L3。 实验测试数据基本要求： 第一组

第一个链表元素为 （1，3，6，10，15，16，17，18，19，20）

第二个链表元素为 （1，2，3，4，5，6，7，8，9，10，18，20，30） 第二组

第一个链表元素为 （1，3，6，10，15，16，17，18，19，20） 第二个链表元素为 （2，4，5，7，8，9，12，22） 第三组

第一个链表元素为 （）

第二个链表元素为 （1，2，3，4，5，6，7，8，9，10）

实验三 链栈实验

实验要求

1、本次实验中，链栈使用带头结点的单链表实现。

2、链栈结构定义，算法实现全部放入库函数“linkStack.h”中； 3、各运算和变量命名直观易懂，并有相应的注释。 实验任务

编写算法实现下列问题的求解。 <1>初始化一个链栈。 <2>判断是否空栈。 <3>入栈

第一组数据：10，13，5，8，20，55 第二组数据：a, b, c, d, e, f, g <4>取栈顶元素 <5>出栈

<6>将10进制数转换为16进制数 第一组数据：4 第二组数据：11 第三组数据：254 第四组数据：1357

实验四 循环队列实验

实验要求

1、本次实验中，队列使用顺序结构循环队列；

2、结构定义和运算实验放入库文件“seqQueue.h”中；

线性表、链表、链栈、循环队列实验报告(含程序代码及截图)

3、各运算和变量命名直观易懂，并有相应的注释。 实验任务

编写算法实现下列问题的求解。 <1>初始化一个队列。 <2>判断是否队空。 <3>判断是否队满。

设队列最大长度：MaxLen=100

第一组数据：入队n个元素，判断队满

第二组数据：用循环方式将1到99，99个元素入队，判队满 <4>入队

第一组数据：4，7，8，12，20，50 第二组数据：a,b,c,d,f,g <5>出队

<6>取队头元素

<7>求当前队列中元素个数 <8>编写算法实现

①初始化空循环队列；

②当键盘输入奇数时，此奇数入队； ③当键盘输入偶数时，队头出队； ④当键盘输入0时，算法退出；

⑤每当键盘输入后，输出当前队列中的所有元素。

2. 实验目的

实验一 顺序表实验

1、理解线性表的顺序存储结构。

2、熟练掌握顺序表的有关算法设计。

3、根据具体问题的需要，设计出合理的表示数据的顺序结构，并设计相关算法。

实验二 单链表实验

实验目的

1、理解线性表的链式存储结构。

2、熟练掌握单链表结构及有关算法的设计。

3、根据具体问题的需要，设计出合理的表示数据的链表结构，并设计相关算法。

实验三 链栈实验

实验目的

线性表、链表、链栈、循环队列实验报告(含程序代码及截图)

1、掌握栈的基本概念。

2、掌握链栈的建立、入栈和出栈等方法。

3、根据具体问题的需要，设计出合理的表示数据的结构，并设计相关算法。

实验四 循环队列实验

实验目的

1、掌握队列的基本概念。

2、掌握循环队列的建立、入队和出队等方法。

3、根据具体问题的需要，设计出合理的表示数据的结构，并设计相关算法。

3. 数据结构设计

采用带头结点的链表结构设计

4. 算法设计

实验一 顺序表实验

<1>

#include "stdafx.h" #include "iostream.h" #include "seqList.h"

void GetElement(seqList L,int i,elementType x) {

if(getElement(L,i,x))

cout<<"L中第"<<i<<"个元素是："<<x<<endl; else

cout<<"输入序号超出顺序表L范围。"<<endl; }

void main(int argc, char* argv[]) {

seqList L; int i;

elementType x;

initialList(&L); //初始化顺序表 CreateSeqList( L);

cout<<"请输入要查找的序号"<<endl; cin>>i;

线性表、链表、链栈、循环队列实验报告(含程序代码及截图)

GetElement( L,i, x); } <2>

#include "stdafx.h" #include "iostream.h" #include "seqList.h"

void InsertData(seqList *L, elementType x, int m) {

int k,i;

k=listInsert( L, x, m); if (k==0)

cout<<"表满"<<endl; else if (k==1)

cout<<"插入序号错误"<<endl; else

cout<<"插入后的顺序表为"<<endl; for(i=0;i<L->listLen;i++) cout<<L->data[i]<<" "; cout<<endl; }

void main (int argc, char* argv[]) {

seqList L; int m,i;

elementType x;

initialList(&L); CreateSeqList( L);

cout<<"请输入要插入的序号"<<endl; cin>>m;

cout<<"请输入插入的元素值"<<endl; cin>>x;

cout<<"插入前的顺序表为："<<endl; for(i=0;i<L.listLen;i++) cout<<L.data[i]<<" "; cout<<endl;

InsertData(&L, x, m); } <3>

#include "stdafx.h"

线性表、链表、链栈、循环队列实验报告(含程序代码及截图)

#include "iostream.h" #include "seqList.h"

void DeleteData(seqList *L,int m) {

int k,i;

k=listDelete(L,m); if(k==0)

cout<<"空表"<<endl; else if(k==1)

cout<<"删除的序号超出范围"<<endl; else {

for(i=0;i<L->listLen;i++) cout<<L->data[i]<<" "; cout<<endl; } }

void main(int argc, char* argv[]) {

seqList L; int m,i;

initialList(&L); CreateSeqList( L);

cout<<"请输入删除的序号"<<endl; cin>>m;

cout<<"原顺序表为："<<endl;

for(i=0;i<L.listLen;i++) cout<<L.data[i]<<" "; cout<<endl;

cout<<"删除后的顺序表是："<<endl; DeleteData(&L, m); } <4>

#include"stdafx.h" #include"iostream.h" #include"seqList.h"

void OrderInsert(seqList &L,elementType x) {

线性表、链表、链栈、循环队列实验报告(含程序代码及截图)

int i=L.listLen-1; if(i>=MaxLen-1)

cout<<"序号超出范围"<<endl; else {

while(i>=0&&L.data[i]>x) {

L.data[i+1]=L.data[i]; i--; }

L.data[i+1]=x; L.listLen++; } }

void main() {

seqList L; int i;

elementType x; initialList(&L); CreateSeqList( L);

cout<<"原递增顺序表为"<<endl; for(i=0;i<L.listLen;i++) cout<<L.data[i]<<" "; cout<<endl;

cout<<"请输入插入的元素"<<endl; cin>>x;

OrderInsert(L,x);

cout<<"插入后的递增顺序表为："<<endl; for(i=0;i<L.listLen;i++) cout<<L.data[i]<<" "; cout<<endl; } <5>

#include"stdafx.h" #include"iostream.h" #include"seqList.h"

void SeperateData(seqList &L) {

seqList O,J; int i,m=0,n=0;

for(i=0;i<L.listLen;i++) {

线性表、链表、链栈、循环队列实验报告(含程序代码及截图)

if(L.data[i]%2==0)

O.data[m++]=L.data[i]; else J.data[n++]=L.data[i]; }

cout<<"偶数值顺序表为"<<endl; for(i=0;i<m;i++)

cout<<O.data[i]<<" "; cout<<endl;

cout<<"奇数值顺序表为"<<endl; for(i=0;i<n;i++)

cout<<J.data[i]<<" "; cout<<endl; }

void main() {

int i;

seqList L;

initialList(&L); CreateSeqList(L);

cout<<"原顺序表为"<<endl; for(i=0;i<L.listLen;i++) cout<<L.data[i]<<" "; cout<<endl;

SeperateData(L); } <6>

#include"stdafx.h" #include"iostream.h" #include"seqList.h"

void PublicData(seqList &L1,seqList &L2,seqList &L3) {

int i1=0,i2=0,i3=0,i;

while(i1<L1.listLen&&i2<L2.listLen) if(L1.data[i1]==L2.data[i2]) {

L3.data[i3++]=L1.data[i1++]; i2++; }

else if(L1.data[i1]>L2.data[i2]) {

i2++; } else

线性表、链表、链栈、循环队列实验报告(含程序代码及截图)

{

i1++; }

L3.listLen=i3;

for(i=0;i<L3.listLen;i++) cout<<L3.data[i]<<" "; cout<<endl; }

void main() {

int i;

seqList L1,L2,L3; initialList(&L1); initialList(&L2); initialList(&L3);

cout<<"请输入第一个递增顺序表的元素"<<endl; CreateSeqList( L1);

cout<<"请输入第二个递增顺序表的元素"<<endl; CreateSeqList( L2);

cout<<"第一个顺序表为："<<endl; for(i=0;i<L1.listLen;i++) cout<<L1.data[i]<<" "; cout<<endl;

cout<<"第二个顺序表为："<<endl; for(i=0;i<L2.listLen;i++) cout<<L2.data[i]<<" "; cout<<endl;

cout<<"公共元素为："<<endl; PublicData(L1,L2,L3); }

实验二 单链表实验

<1>

#include"linkedList.h" void main() {

node *L,*p; int i;

initialList(*& L); createListR( *& L );

cout<<"请输入要查找的元素节点序号"<<endl; cin>>i;

线性表、链表、链栈、循环队列实验报告(含程序代码及截图)

p=getElement(L, i);

cout<<"第"<<i<<"个节点的指针 p="<<p<<endl; }

<2>

#include"linkedList.h"

void InsertData(node *L,elementType x, int i) {

node *p; bool Q;

Q=listInsert( L, i, x ); if(Q==true) {

//打印链表

cout<<"插入后的链表为："<<endl; p=L->next; while(p) {

cout<<p->data<<" "; p=p->next; }

cout<<endl; }

else cout<<"插入位置 i不对"<<endl; }

void main() {

node *L,*p; elementType x; int i;

createListR( *& L );

cout<<"原链表为："<<endl; p=L->next; while(p) {

cout<<p->data<<" "; p=p->next; }

cout<<endl;

cout<<"请输入要插入的元素值"<<endl; cin>>x;

cout<<"请输入要插入的位置"<<endl;

线性表、链表、链栈、循环队列实验报告(含程序代码及截图)

cin>>i;

InsertData(L, x, i); } <3>

#include"linkedList.h"

void DeleteData(node *L,int i) {

node *p;

bool Q=listDelete( L, i); if(Q==true) {

cout<<"删除后的链表为："<<endl; p=L->next; while(p) {

cout<<p->data<<" "; p=p->next; }

cout<<endl; }

else

cout<<"删除节点错误"<<endl; }

void main() {

node *L,*p; int i;

createListR( *& L );

cout<<"原链表为："<<endl; p=L->next; while(p) {

cout<<p->data<<" "; p=p->next; }

cout<<endl;

cout<<"请输入要删除的节点序号："<<endl; cin>>i;

DeleteData(L,i);

线性表、链表、链栈、循环队列实验报告(含程序代码及截图)

} <4>

#include"linkedList.h"

void OrderInsert(node *L,elementType x) {

node *u,*p=L;

while(p->next!=NULL&&p->next->data<x) p=p->next;

if(p->next==NULL||p->next->data>x) {

u=new node;//产生节点，此步骤不可少 u->data=x;

u->next=p->next; p->next=u; }

p=L->next;

while(p!=NULL) {

cout<<p->data<<" "; p=p->next; }

cout<<endl; }

void main() {

elementType x; node *p; node *L;

createListR( *& L );

cout<<"输出原递增有序的链表"<<endl; p=L->next; while(p)

{cout<<p->data<<" "; p=p->next; }

cout<<endl;

cout<<"输入插入的数字"<<endl; cin>>x;

cout<<"输出插入后的递增有序表"<<endl; OrderInsert(L,x); }

线性表、链表、链栈、循环队列实验报告(含程序代码及截图)

<5>

#include "linkedList.h" void PrintList(node *L) {

node *p; p=L->next; while(p) {

cout<<p->data<<" "; p=p->next; }

cout<<endl; }

void SeperateData(node *L,node *&J,node *&O) {

node *p,*Rj,*Ro,*u,*t; J=new node; O=new node; Rj=J; Ro=O;

p=L->next; while(p) {

if(p->data%2==0) {

u=new node;

u->data=p->data; Ro->next=u;Ro=u; } else {

t=new node; t->data=p->data; Rj->next=t;Rj=t; }

Ro->next=NULL; Rj->next=NULL; p=p->next; } }

void main()

线性表、链表、链栈、循环队列实验报告(含程序代码及截图)

node *L,*J,*O;

cout<<"创建一个链表"<<endl; createListR( *& L );

cout<<"所创建的链表为"<<endl; PrintList(L);

SeperateData( L, *&J, *&O);

cout<<"奇数结点组成的链表为"<<endl; PrintList(J);

cout<<"偶数结点组成的链表为"<<endl; PrintList(O); } <6>

#include"linkedList.h" void PrintList(node *L) {

node *p; p=L->next; while(p) {

cout<<p->data<<" "; p=p->next; }

cout<<endl; }

void PublicData(node *A,node *B,node *&C) {

node *pa,*pb,*Rc,*u; C=new node; Rc=C;

pa=A->next;pb=B->next; while(pa!=NULL&&pb!=NULL) if(pa->data<pb->data) pa=pa->next;

else if(pb->data>pb->data) pb=pb->next; else {

u=new node;

u->data=pa->data; Rc->next=u;Rc=u; pa=pa->next;

线性表、链表、链栈、循环队列实验报告(含程序代码及截图)

pb=pb->next; }

Rc->next=NULL; }

void main() {

node *A,*B,*C;

cout<<"创建第一个链表"<<endl; createListR( *&A );

cout<<"创建第二个链表"<<endl; createListR( *&B);

cout<<"打印第一个链表:"<<endl; PrintList(A);

cout<<"打印第二个链表"<<endl; PrintList(B);

PublicData(A,B,*&C);

cout<<"打印公共元素组成的链表"<<endl; PrintList(*&C); }

实验三 链栈实验

// alltest.cpp : Defines the entry point for the console application. //

#include "stdafx.h" #include "iostream.h"

#include "linkStack.h"

int main(int argc, char* argv[]) {

node* H, *L, *P,*q; elementType y;

initialstack(L);//初始化 if(stackEmpty(L))

cout<<"空栈"<<endl; else

cout<<"栈不空"<<endl;

cout<<"尾插法创建带头结点的单链表>>"<<endl;

数据结构实验报告.doc 将本文的Word文档下载到电脑
下载这篇word文档

    上一篇：塑料成型技术综述

    下一篇：江苏省常熟市2018_2019学年八年级语文上学期期末质量监测试卷新人教版

    精彩图片

    猜你喜欢

    热门精选

    经典双语美文：加油为了心中的梦想

    2020-09-14

    美文赏析：花开向暖，素锦留香

    2020-09-14

    经典美文：花开向暖，素锦留香

    2020-09-14

    经典美文：青春如歌，携一份懂得同行

    2020-09-14

    在雨中静听自己的心跳美文

    2020-09-14

    浅谈当今大学教育的含金量双语美文

    2020-09-14

    大家正在看

    宜昌住房公积金贷款流程 &#167;6.2用天平测物体的质量导 医疗用毒性药品目录 2013版英语复习方略教用：素能提 生产线布局情况 2010年初级护师考试大纲(015)-儿科 K201409,厦门大学网络教育2014-2015学 杭州市劳动合同范本
    × 游客快捷下载通道（下载后可以自由复制和排版）

    限时特价：7 元/份 原价:20元

    支付方式：

    微信支付并下载

    开通VIP包月会员 特价：29元/月

    注：下载文档有可能“只有目录或者内容不全”等情况，请下载之前注意辨别，如果您已付费且无法下载或内容有问题，请联系我们协助你处理。
    微信：fanwen365 QQ：370150219