南昌大学数据结构实验.pdfVIP

目录

实验1：线性表及其应用

实验2：栈

实验3：队列

实验4：稀疏矩阵

1

实验1：线性表及其应用

一、实验目的

帮助学生掌握线性表的基本操作在顺序和链表这两种存储结构上的实现，尤以链表的操

作和应用作为重点。

二、问题描述

1.构造一个空的线性表L。

2.在线性表L的第i个元素之前插入新的元素e；

3.在线性表L中删除第i个元素，并用e返回其值。

三、实验要求

1、分别利用顺序和链表存储结构实现线性表的存储，并设计出在不同的存储结构中线

性表的基本操作算法。

2、在实验过程中，对相同的操作在不同的存储结构下的时间复杂度和空间复杂度进行

分析。

四、实验环境

PC微机

DOS操作系统或Windows操作系统

TurboC程序集成环境或VisualC++程序集成环境

五、实验代码

#ifndefSQLIST_H

#defineSQLIST_H

李雪刚非循环单链表

#endif

templatetypenameElemType

classMySqList:publicSqListElemType

{

public:

voidRandom();

voiddisplay();

voidkai_1(MySqListElemTypeSql);

voidkai_2(MySqListElemTypeSql);

voidkai_3(MySqListElemTypeSql);

MySqList(ElemType*p,intnsize);

2

};

//输出线性表

templatetypenameElemType

voidMySqListElemType::display()

{

inti;

intn=getLength();

此时的线性表为

for(i=1;i=n;i++)

coutendl;

for(i=0;in;i++)

coutendl;

}

//删除第i个元素

templatetypenameElemType

voidkai_1(MySqListElemTypeSql)

{

删除第i个元素

inti;

inte;

请输入要删去的序号

cini;

Sql.deleteElem(i,e);

Sql.display();

}

//取第i个元素

templatetypenameElemType

voidkai_2(MySqListElemTypeSql)

{

取第i个元素

inti;

inte;

请输入要取的数的序号

cini;

Sql.getElem(i,e);

3

couteendl;

}

//在第i个元素前插入一个元素

templatetypenameElemType

voidkai_3(MySqListElemTypeSql)

{

在第i个元素前插入一个元素

inti;