[线性表 链表实验报告]链表线性表
实验一：线性表运算的实现
班级 姓名 学号
一、实验预备知识
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 插入位置的前驱结点不存在!