[线性表 链表实验报告]链表线性表

Answer 1

实验一：线性表运算的实现

班级 姓名 学号

一、实验预备知识

1 复习C++中编写函数的相关内容。

2 复习如何用主函数将多个函数连在一起构成一个C++完整程序。

二、实验目的

1 掌握线性表的顺序和链式存储结构

2 熟练运用线性表在顺序存储方式下的初始化、创建、输出、插入和删除运算

3 熟练运用线性表在链式存储方式下的创建、输出、插入和删除运算

三、实验要求

1 编写初始化并创建线性表和输出线性表的算法。

2 编写对线性表插入和删除运算算法，要判断位置的合法性和溢出问题。

3 编写一个主函数，将上面函数连在一起，构成一个完整的程序。

4将实验源程序调试并运行，写出输入、输出结果，并对结果进行分析。

四、实验步骤

◇顺序表实验内容：

1．给定的线性表为L=（12，25，7，42，19，38），元素由键盘输入。

2．初始化并建立顺序表。

3．编写顺序表输出算法。（内存中开辟的单元数为8）

4．依次插入3，21，15三个数，分别插入在第4，6和2位置，每插入一次都要输出一次顺序表。

5．删除第5，第3和第12个位置上的元素，每删除一个元素都要输出一次顺序表。 ◇单链表实验内容：

1．给定的线性表为L=（12，25，7，42，19，38），元素由键盘输入。

2．建立一个带表头结点的单链表（前插入法和尾插入法都可以）。

3．编写单链表输出算法。

4．依次插入3，21，15三个数，分别插入在第4，6和12位置，每插入一次都要输出一次单链表。

5．删除第5，第3和第12个位置上的元素，每删除一个元素都要输出一次单链表。

五、实验程序

◇顺序表实验

//LinkList.h

#define MAXSIZE 8

typedef int DataType;

typedef struct{

DataType data[MAXSIZE];

int last;

}Seqlist;

void creat_seqlist(Seqlist &s);

void display_seqlist(Seqlist &s);

int insert_seqlist(Seqlist &s, int i, DataType x);

int delet_seqlist(Seqlist &s, int i);

//LinkList.cpp

#include

#include"Seqlist.h"

void creat_seqlist(Seqlist &s)

{

int x, i = 0;

cout

cin>>x;

while(x != -1){

s.data[i] = x;

cin>>x;

i ++;

}

s.last = i-1;

}

void display_seqlist(Seqlist &s)

{

int i;

cout

for(i = 0; i

cout

cout

}

int insert_seqlist(Seqlist &s, int i, DataType x)

{

int j;

if(s.last == MAXSIZE-1){

}

cout s.last + 2){ cout= i-1;j --) s.data[j+1] = s.data[j]; s.data[i-1] =x ; s.last ++; return 1;

int delet_seqlist(Seqlist &s, int i)

{

int j;

if(i s.last+1){

cout

return -1;

}

for(j = i; j

s.data[j-1] = s.data[j];

s.last --;

return 1;

}

//main.cpp

#include

#include"Seqlist.h"

int main()

{

int x,d,s;

Seqlist s_list;

creat_seqlist(s_list);

cout>d; cout>x; s=insert_seqlist(s_list ,d,x); if(s==1){ cout>d; s=delet_seqlist(s_list,d);

}

if(s==1){ cout

运行结果:

请输入数据（以输入-1结束）

12 25 7 42 19 38 -1

顺序表为：

12 25 7 42 19 38

插入操作

请输入插入的位置:4

请输入要插入的数据：3

插入后的顺序表为：

12 25 7 3 42 19 38

请输入插入的位置:6

请输入要插入的数据：21

插入后的顺序表为：

12 25 7 3 42 21 19 38

请输入插入的位置:2

请输入要插入的数据：15

表满！

删除操作

请输入删除元素的位置：5

删除后的顺序表为：

12 25 7 3 21 19 38

请输入删除元素的位置：3

删除后的顺序表为：

12 25 3 21 19 38

请输入删除元素的位置：12

不存在该元素！

Press any key to continue

◇单链表实验

//LinkList.h

typedef int DataType;

typedef struct Node{

DataType data;

struct Node *next;

}LNode,*LinkList;

void Creat_LinkList(LinkList &L); //创建链表

void Show_LinkList(LinkList &L); //显示数据

LNode * Get_LinkList(LinkList &L, int i); //获得第i个结点的地址 int Insert_linklist(LinkList &L,int i,DataType x); //插入结点

int Delete_LinkList(LinkList &L,int i); //删除结点

//LinkList.cpp

#include

#include"LinkList.h"

void Creat_LinkList(LinkList &L)

{

LNode *s;

L = NULL;

s = new LNode;

s->next = L;

L = s;

int x;

}

//头插法创建带头结点的链表 cout>x; while(x != -1){ s = new LNode; s->next = L; L->data = x; L = s; cin>>x; }

void Show_LinkList(LinkList &L)

{

LNode *p;

p = L->next;

while(p!=NULL){

coutdata

p = p->next; //显示数据

}

cout

}

LNode * Get_LinkList(LinkList &L, int i)

{

int j = 1;

LNode *q;

q = L->next;

while(q != NULL && j

q = q->next;

j++;

}

return q;

}

//获得第i个结点的地址

int Insert_LinkList(LinkList &L, int i, DataType x)//插入结点 {

LNode *p, *s;

p = Get_LinkList(L,i-1);

if(p == NULL){

}

coutdata = x; s->next = p->next; p->next = s; return 1; }

int Delete_LinkList(LinkList &L,int i)

{

LNode *p, *s;

p = Get_LinkList(L,i-1);

if(p == NULL){

//删除结点 coutnext == NULL){ cout

return 0;

}

else{

s = p->next;

p->next = s->next; delete s;

return 1;

}

}

//main.cpp

#include #include"LinkList.h"

int main()

{

int x,d,s;

LinkList H;

Creat_LinkList(H); Show_LinkList(H);

} cout>d; cout>x; s = Insert_LinkList(H,d,x); if(s == 1){ cout>d; s = Delete_LinkList(H,d); if(s == 1){ cout

运行结果：

请输入数据（以输入-1结束） 12 25 7 42 19 38 -1 单链表为：

38 19 42 7 25 12

插入操作

请输入插入的位置:4 请输入要插入的数据：3 插入后的单链表为： 38 19 42 3 7 25 12 请输入插入的位置:6 请输入要插入的数据：21 插入后的单链表为：

38 19 42 3 7 21 25 12 请输入插入的位置:12 请输入要插入的数据：15 插入位置错误!

删除操作

请输入删除元素的位置：5 删除后的单链表为：

38 19 42 3 21 25 12 请输入删除元素的位置：3 删除后的单链表为： 38 19 3 21 25 12

请输入删除元素的位置：12 插入位置的前驱结点不存在!