数据结构--实验报告 线性表的基本操作

2024年6月13日发(作者：)

一、 实验目的

二、 实验内容和要求

三、 源代码

1) 顺序表的代码

2) 单链表的代码

四、 测试结果

1) 顺序表的测试结果

2) 单链表的测试结果

五、心得体会

实验一 线性表的基本操作及其应用

一、实验目的

1、帮助读者复习C++语言程序设计中的知识。

2、熟悉线性表的逻辑结构。

3、熟悉线性表的基本运算在两种存储结构上的实现。

4、掌握顺序表的存储结构形式及其描述和基本运算的实现。

5、熟练掌握动态链表结构及有关算法的设计

二、实验内容

题目一：顺序表的基本操作

[问题描述]

实现顺序表的建立、求长度，取元素、修改元素、插入、删除等顺序表的基本操作。

[基本要求]

（1）依次从键盘读入数据，建立带头结点的顺序表；

（2）输出顺序表中的数据元素

（3）求顺序表的长度；

（4）根据指定条件能够取元素和修改元素；

（5）实现在指定位置插入和删除元素的功能。

2

（6）根据算法，将两个有序的顺序表合并成一个有序顺序表。

[测试数据] 由学生任意指定。

题目二：单链表的基本操作

[问题描述]

实现带头结点的单链表的建立、求长度，取元素、修改元素、插入、删除等单链表的

基本操作。

[基本要求]

（1）依次从键盘读入数据，建立带头结点的单链表；

（2）输出单链表中的数据元素

（3）求单链表的长度；

（4）根据指定条件能够取元素和修改元素；

（5）实现在指定位置插入和删除元素的功能。

（6）根据算法，将两个有序的单链表合并成一个有序单链表。

[测试数据]

3

由学生任意指定。

三、源代码

(一) 顺序表的基本操作

#include

using namespace std;

#define TRUE 1

#define FALSE 0

#define OK 1

#define ERROR 0

#define OVERFLOW -2

typedef int Status;

typedef int ElemType;

#define LIST_INIT_SIZE

100

4

#define LISTINCREMENT 10

typedef struct { //结构体

ElemType *elem;

int length;

int listsize;

}SqList;

SqList Lx;

Status InitList_Sq(SqList &L) //分配空间

{ =new ElemType[LIST_INIT_SIZE];

if(!)exit(OVERFLOW);

=0;

ze=LIST_INIT_SIZE;

return OK;

5

}

Status ListInsert(SqList &L,int i,ElemType e) //插入新元素

{ int *q,*p;ElemType *newbase;

if(i<1 || i>+1) return ERROR;

if(>=ze)

{ newbase=new ElemType[ze+LISTINCREMENT];

if(!newbase) exit(OVERFLOW);

=newbase;

ze+=LISTINCREMENT;

}

q=&([i-1]);

for (p=&([-1]);p>=q;--p)

*(p+1)=*p;

6

*q=e;

++;

return OK;

}

Status Listlength(SqList L)

{ int *p=;

while(p)

{ return (); }

}

Status GetElem(SqList L, int i,ElemType &e)

{ if(i<1 || i>)

return ERROR;

else

//长度

//判断线形表是否存在

//取元素

7

{ e=[i-1];

return e;

}

}

void MergeList(SqList La,SqList Lb,SqList &Lc)

{ ElemType ai,bj;

InitList_Sq(Lc);

int i=1,j=1,k=0;

int La_len,Lb_len;

La_len=Listlength(La);

Lb_len=Listlength(Lb);

while((i<=La_len)&&(j<=Lb_len))

{ GetElem(La,i,ai);GetElem(Lb,j,bj);

//合并

8

if(ai<=bj)

{ ListInsert(Lc,++k,ai);++i; }

else

{ ListInsert(Lc,++k,bj);++j;

}

while(i<=La_len)

{ GetElem(La,i++,ai);

ListInsert(Lc,++k,ai);

}

while(j<=Lb_len)

{ GetElem(Lb,j++,bj);

ListInsert(Lc,++k,bj);

}

}

9

}

void show(SqList L,int i) //显示

{ int j;ElemType k;

cout<<"顺序表显示如下:"<

for(j=0;j

{ k=[j];

cout<"; }

if(j==i-1 && i>0)

{ k=[j]; cout<

cout<

}

void create(SqList &L,int n)

{ int e;

}

//输入元素

10

for(int i=0;i

{ cin>>e;

[i]=e;

=i+1; }

}

Status ListDelete_Sq(SqList &L,int i,ElemType &e)

{ ElemType *p, *q;

if(i<1 || i>) return ERROR;

p=&([i-1]);

e=*p;

q=+-1;

for(++p;p<=q;++p) *(p-1)=*p;

--;

//删除

11

return OK;

}

Status Listxiugei(SqList &L,int i,ElemType &e) //修改

{ if(i<1 || i>)

return ERROR;

else

{ [i-1]=e;

return OK; }

}

void shuru(SqList &L1)

{ int a;

InitList_Sq(L1);

cout<<"请输入顺序表的长度：";

//顺序表的创建

12

cin>>a;

cout<<"请输入顺序表的元素(共"<

create(L1,a);

show(L1,a);

}

void chaxun(SqList &L1) //取第i个位置的元素

{ int j;ElemType e1;

cout<<"请选择所要取出元素的位置:";

cin>>j;

while(j<0||j>Listlength(L1))

{ cout<<"输入有误，请重新输入"<

cout<<"请选择所要取出元素的位置:";

cin>>j; }

13

GetElem(L1,j,e1);

cout<<"取出的元素为:"<

void xiugai(SqList &L1) //修改第i个位置的元素

{ int a;

int j; ElemType e1;

a=;

cout<<"请选择所要修改元素的位置:";

cin>>j;

while(j<0||j>Listlength(L1))

{ cout<<"输入有误，请重新输入"<

cout<<"请选择所要修改元素的位置:";

cin>>j; }

cout<<"要修改成的元素:";

14

cin>>e1;

Listxiugei(L1,j,e1);

cout<<"修改后的顺序表数据:"<

show(L1,a);

}

void shanchu(SqList &L1) //删除顺序表里的元素

{ int a;

int j; ElemType e1;

a=;

cout<<"请选择所要删除元素的位置:";

cin>>j;

while(j<0||j>Listlength(L1))

{ cout<<"输入有误，请重新输入"<

15

cout<<"请选择所要删除元素的位置:";

cin>>j; }

ListDelete_Sq(L1,j,e1);

cout<<"修改后的顺序表数据:"<

show(L1,a-1);

}

void charu(SqList &L1) //插入元素到顺序表里

{ int a; int j; ElemType e1;

a=;

cout<<"请选择所要插入元素的位置:";

cin>>j;

while(j<0||j>Listlength(L1))

{ cout<<"输入有误，请重新输入"<

16

cout<<"请选择所要插入元素的位置:";

cin>>j; }

cout<<"要插入的元素:";

cin>>e1;

ListInsert(L1,j,e1);

cout<<"修改后的顺序表数据:"<

show(L1,a+1);

}

void hebing(SqList &L3) //合并两个顺序表

{ SqList L1,L2;

int a,b;

InitList_Sq(L1); InitList_Sq(L2);

cout<<"请输入第一个有序表的长度："; cin>>a;

17

cout<<"请输入第一个有序表的元素(共"<

create(L1,a);

show(L1,a);

cout<<"请输入第二个有序表的长度："; cin>>b;

cout<<"请输入第二个有序表的元素(共"<

create(L2,b);

show(L2,b);

MergeList(L1,L2,L3);

cout<<"合并后的有序表如下："; show(L3,a+b);

}

void main() //主菜单

{ int choice;

for(;;)

18

{ cout<<" 顺序表的基本操作"<

cout<<" 1.顺序表的创建"<

cout<<" 2.顺序表的显示"<

cout<<" 3.顺序表的长度"<

cout<<" 4.取第i个位置的元素"<

cout<<" 5.修改第i个位置的元素"<

cout<<" 6.插入元素到顺序表里"<

cout<<" 7.删除顺序表里的元素"<

cout<<" 8.合并两个顺序表"<

cout<<" 9.退出系统"<

cout<<"请选择：";

cin>>choice;

switch(choice)

19

{ case 1: shuru(Lx);break;

case 2: show(Lx,);break;

case 3: cout<<"顺序表的长度:"<

case 4: chaxun(Lx);break;

case 5: xiugai(Lx);break;

case 6: charu(Lx);break;

case 7: shanchu(Lx);break;

case 8: hebing(Lx);break;

case 9: cout<<"退出系统!"<

default : cout<<"输入有误，请重新选择"<

}

}

(二) 单链表的基本操作

}

20

#include

using namespace std;

#define true 1

#define false 0

#define ok 1

#define error 0

#define overflow -2

typedef int Status;

typedef int ElemType;

typedef struct LNode

{ ElemType data;

struct LNode *next;

}LNode,*LinkList;

//存储结构

21

void CreateList(LinkList &L,int n) //尾插法创建单链表

{ LinkList p;

L=new LNode;

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

LinkList q=L; //使q指向表尾

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

{ p=new LNode;

cin>>p->data;

p->next=NULL;

q->next=p;

q=p; }

}

Status GetElem(LinkList L,int i,ElemType &e)//取第i个元素

22

{ LinkList p=L->next;

int j=1;

while(p&&j

{ p=p->next;

++j; }

if(!p||j>i) return error; //第i个元素不存在

e=p->data;

return ok;

}

Status LinkInsert(LinkList &L,int i,ElemType e) //插入

{ LinkList p=L;

int j=0;

while(p&&j

23

{ p=p->next;

++j; } //寻找第i-1个结点

if(!p||j>i-1)

return error; //i小于1或者大于表长加1

LinkList s=new LNode; //生成新结点

s->data=e;

s->next=p->next; //插入L中

p->next=s;

return ok;

}

Status ListDelete(LinkList &L,int i,ElemType &e)

{ LinkList p=L;

LinkList q;

// 删除

24

int j=0;

while(p->next&&j

{ //寻找第i个结点，并令p指向其前驱

p=p->next;

++j; }

if(!(p->next)||j>i-1) return error; //删除位置不合理

q=p->next;

p->next=q->next; //删除并释放结点

e=q->data;

delete(q);

return ok;

}

void MergeList(LinkList &La,LinkList &Lb,LinkList &Lc)

25

{ //合并两个顺序链表

LinkList pa,pc,pb;

pa=La->next;

pb=Lb->next;

Lc=pc=La;

while(pa&&pb)

{ if(pa->data<=pb->data)

{ pc->next=pa;

pc=pa;

pa=pa->next; }

else

{ pc->next=pb;

pc=pb;

26

pb=pb->next; }

}

pc->next=pa?pa:pb;

delete(Lb);

}

void show(LinkList L)

{ LinkList p;

p=L->next;

while(p)

{ cout<data<<"-->";

p=p->next; }

cout<

}

//显示

27

int Length(LinkList L,int i) //表长

{ i=0;

LinkList p=L->next;

while(p)

{ ++i;

p=p->next; }

return i;

}

void xiugai(LinkList L)

{ int i,j=1;

ElemType k;

ElemType e,m;

LinkList p=L->next;

//修改

28

cout<<"请输入要修改的元素位置(0

cin>>i;

GetElem(L,i,e);

cout<<"该位置的元素:"<

cout<<"修改后的元素值:";

cin>>k;

while(p&&j

{ p=p->next;

++j; }

m=p->data;

p->data=k;

cout<<"修改后的单链表显示如下:"<

show(L);

29

}

void hebing() //合并两个单链表

{ int a,b;

LinkList La,Lb,Lc;

cout<<"请输入第一个有序链表的长度:"<

cin>>a;

cout<<"请输入第一个有序链表的元素共（"<

CreateList(La,a);

show(La);

cout<<"请输入第二个有序链表的长度:"<

cin>>b;

cout<<"请输入第二个有序链表的元素共（"<

CreateList(Lb,b);

30

show (Lb);

MergeList(La,Lb,Lc);

cout<<"合并后的有序链表如下："<

show(Lc);

}

void main()

{ int select;

int x;

ElemType y;

LinkList list;

for(;;)

{ cout<<"

cout<<"

//主函数

单链表的基本操作"<

1.单链表的创建"<

31

cout<<" 2.单链表的显示"<

cout<<" 3.单链表的长度"<

cout<<" 4.取第i个位置的元素"<

cout<<" 5.修改第i个位置的元素"<

cout<<" 6.插入元素到单链表里"<

cout<<" 7.删除单链表里的元素"<

cout<<" 8.合并两个单链表"<

cout<<" 9.退出系统"<

cout<<"请选择:";

cin>>select;

switch(select)

{ case 1:cout<<"请输入单链表的长度:"<

cin>>x;

32

cout<<"请输入"<

CreateList(list,x);

break;

case 2: cout<<"单链表显示如下:"<

show(list);

break;

case 3: int s;

cout<<"单链表的长度为:"<

break;

case 4: cout<<"请选择所要取出元素的位置:";

cin>>x;

while(x<0||x>Length(list,s))

{ cout<<"输入有误，请重新输入"<

33

cout<<"请选择所要取出元素的位置:";

cin>>x; }

GetElem(list,x,y);

cout<<"该位置的元素为:"<

break;

case 5: xiugai(list); break;

case 6: cout<<"请选择要插入的位置:"; cin>>x;

while(x<0||x>Length(list,s))

{ cout<<"输入有误，请重新输入"<

cout<<"请选择所要插入元素的位置:";

cin>>x; }

cout<<"要插入的元素值:";

cin>>y;

34

LinkInsert( list,x,y);

cout<<"插入后单链表显示如下:"<

show(list);

break;

case 7: cout<<"请选择要删除的位置:"; cin>>x;

while(x<0||x>Length(list,s))

{ cout<<"输入有误，请重新输入"<

cout<<"请选择所要删除元素的位置:";

cin>>x; }

ListDelete(list,x,y);

cout<<"要删除的元素值:"<

cout<<"删除后的单链表显示如下:"<

show(list);

35

break;

case 8: hebing();

break;

case 9: exit(0);

break;

default : cout<<"输入有误，请重新输入"<

break;

}

}

}

四、测试结果

1) 顺序表 的测试结果

36

37

38

39

2) 单链表的测试结果

40

41

42

43

44

五、心得体会

当听到老师说写数据结构实验报告时，我有点惊讶，才学了不到一个月，就要写实验

报告。记得去年学习C++时，学了一个学期，程序设计用了三周，才完成的，这个实验报

告居然要一周完成两个设计，觉得很难。但是现在一周过去了，我也写完了，自我感觉良

好。

通过这次写实验报告，我深切的理解了这门课的本质。刚开始学这门课时，当时还不

清楚这门课程的目的，现在，我真正的理解了：数据结构像是身体的骨骼，而C++是填充

这骨骼的肉体，二者相结合才能使整个程序更加完整，健全。数据结构是个框架，模型，

抽象数据类型中列举了各种操作，而所用的C++语言，将各种操作描述出来构成算法。数

据结构+算法=程序设计。

在这次设计的过程中，我还遇到了，很多的问题。顺序表是按顺序存储的，用了一维

45

数组来存储，又结合C++的程序设计，我又用了类，但是，在执行时出现了问题。后来问

同学，指出我的错误，不过获益不少。我又重新整理思路，把顺序表的基本操作写好了。

虽然走了很多弯路，但是让我认识到，一定要创新，大胆，不能按照旧的思路去干新的事

情。

单链表写起来简单多了，这个很快就搞定了。但是细节上出了问题。比如说，有些变

量的重复定义，有些变量又没有定义，在调用函数，就直接复制过来，没有改参数……通过

修改，我深刻理解到：细节决定成败，在以后，不管做任何事情都要认真，细心。

这次的实验报告，让我受益匪浅，不仅有知识方面的，还有生活和精神上的。总之，

我会继续我的兴趣编程，相信在编程的过程中，能不断的提高自己。

46