线性表（单链表）的存储结构和基本操作(初始化，创建，取值，查找，插入，删除)_完成线性表的基本操作实现(初始化单链表、判断是否为空表、插入(至少插入5个数据)

目录

单链表的存储结构

单链表的基本操作实现

1、初始化

2、创建单链表

（1）前插法

（2）后插法

3、单链表的取值

4、单链表的查找 

5、单链表插入元素

6、单链表删除元素

整体代码：

运行截图​编辑

---

在单链表中，对于数据元素来说，除了存储其本身的信息外，还需要存储有关于其直接后继的信息（直接后继的存储位置），这两部分信息组成数据元素的存储映像，称为结点，它包括两个域，存储数据元素信息的域称为数据域，存储直接后继存储位置的域称为指针域。

单链表的存储结构

由一个结点是由数据域和指针域构成的，可以用代码表示出单链表的存储结构

typedef struct LNode{
	ElemType date;//结点的数据域，用来存储自身的信息
	struct LNode *next;//结点的指针域，用来指向一整个结点
}LNode,*LinkList;//对同一结构体指针类型起了两个名称

LinkList与LNode*,两者本质上是相等的，都是结构体指针类型的名称，但两者所强调内容不一样：

1、用LinkList定义单链表，强调定义的是某个单链表的头指针（指向列表中第一个结点的针），例如LinkList L，则L为单链表的头指针。

2、用LNode *定义指向单链表中任意结点的指针变量，例如LNode *p，则p为指向单链表中某个结点的指针，用*p代表该结点

（若定义LinkList p 或者 LNode *p，则p表示指向某结点的指针变量，表示该结点的地址，而*p为对应的结点变量，表示该结点的名称）

单链表的基本操作实现

1、初始化

操作步骤：

1. 要生成一个新的头结点，让头指针L指向头结点，
2. 将头结点的指针域置空，代码如下：

算法描述： 

Status InitList(LinkList &L)
{
	L=new LNode;//生成新的头结点，并让头指针L指向头结点
	L->next=NULL;//将头结点的指针域置空
	return OK; 
} 

2、创建单链表

（1）前插法

操作步骤：

1. 创建一个只有头结点的空链表
2. 根据列表中即将输入的元素个数n，执行以下操作n次

                1）创建一个新的结点，并使指针p指向该节点

                2）输入该结点的数据域，即p->data

                3)  修改p的指针域为L的指针域，并将L的指针域指向新 生成的结点p

算法描述：

void CreatList_Q(LinkList &L,int n)
{
    L=new LNode;
    L->next=NULL;
    for(i=0;i<n;i++){
        p=new LNode;
        cin>>p->date;
        p->next=L->next;L->next=p;
    }
}

（2）后插法

操作步骤：

1. 创建一个只有头结点的空链表
2. 引入一个指针变量r，让指针r始终指向该链表的最后一个结点（开始时r=L）
3. 根据列表中即将输入的元素个数n，执行以下操作n次

                1）创建一个新的结点，并使指针p指向该节点

                2）输入该结点的数据域，即p->data

                3）将p的指针域置空并将r的指针域指向结点p

                4）让指针p指向r（保证指针r指向该链表的最后一个结点）

算法描述： 

void CreatList_H(LinkList &L,int n)
{
    L=new LNode;
    L->next=NULL;
    r=L;
    for(i=0;i<n;i++){
        p=new LNode;
        cin>>p->data;
        p->next=NULL;r->next=p;
        r=p;
    }
} 

3、单链表的取值

操作步骤：

1. 引入指针p ，让指针p指向首元结点，并引入计数器j
2. 当指针p所指结点不为空并且计数器j的值小于i的值时进行以下循环

                1）p指向下一个结点

                2）计数器的值加1 

     3.当p为NULL时或者计数器j的值大于i的值，找到安全出口（return ERROR)

     4.当计数器j的值等于i的值时，将指针p所指结点的数据域赋值给e，并安全推出

算法描述：

Status GetElem(LinkList L,int i,ElemType &e)
{
	p=L->next;j=1;
	while(p!=NULL && j<i)
	{
		p=p->next;
		j++;
	}
	if(p==NULL || j>i) return ERROR;
	e=p->data;
	return OK;
} 

4、单链表的查找 

单链表的查找返回的为地址，则返回类型应为LNode *或者LinkList

（两者本质上没有区别，但是：

习惯用LinkList强调定义的是某个单链表的头指针，如LinkList L

习惯用LNode *定义指向单链表中任意结点的指针变量，如LNode *p）

操作步骤：

1. 引入指针p指向首元结点，当p所指结点的指针域不为空且p所指结点的数据域与传入值e不相等时，执行以下操作：

                1）指针p指向下一结点的位置（p=p->next）

     2.返回指针p所指结点（即地址）

LNode *LocateElem(LinkList L,ElemType e)
{
	p=L->next;//p指向首元结点
	while(p!=NULL && p->date!=e)
		p=p->next;//p指向下一个结点
	return p;//查找成功返回e的结点地址，否则返回NULL
} 

5、单链表插入元素

操作步骤：

1.引入指针变量p指向头结点，并引入计数器，将计数器的初始值赋值为0

2.当p所指结点不为空且 j < i-1时，循环进行以下操作：

• 指针p指向下一结点的位置（p=p->next）
• 计数器加1

3.退出循环如果是因为i>n+1(p==NULL)或者是i<1(j>i-1)，需要安全退出（return ERROR） 

4.如果不是因为以上两个条件推出，则说明找到了插入位置（j==i-1），生成一个新的结点，并使指针s指向新生成的结点

5.将e的值写入新生成的结点中

6.将p的next域赋值给s的next的域

7.将p的next域指向结点s

8.正常退出（return OK）

算法描述： 

Status ListInsert(LinkList &L,int i,ElemType e)
{
	p=L;j=0;
	while(p!=NULL && (j<i-1))
		{p=p->next;j++;}
	if(p==NULL || j>i-1) return ERROR;
	s=new LNode;
	s->date=e;
	s->next=p->next;
	p->next=s;
	return OK;
} 

6、单链表删除元素

操作步骤：

1.引入指针变量p指向头结点，并引入计数器，将计数器的初始值赋值为0

2.当p的next域所指结点不为空且 j <  i-1时，循环进行以下操作：

• 指针p指向下一结点的位置（p=p->next）
• 计数器加1

3.退出循环如果是因为i>n(p->next==NULL)或者是i<1(j>i-1)，需要安全退出（return ERROR） 

4.如果不是因为以上两个条件推出，则说明找到了删除位置（j==i-1）

5.将p的next域赋值给q

6.将q的next域赋值给p的next域

7.释放删除结点所占空间

8.正常退出（return OK）

算法描述： 

Status ListDelete(LinkList &L,int i)
{
	p=L;j=0;
	while((p->next!=NULL) && (j<i-1))
		{p=p->next;j++;}
	if(p->next==NULL || (j>i-1)) return ERROR;
	q=p->next;
	p->next=q->next;
	delete q;
	return OK;
} 

整体代码：

#include<bits/stdc++.h>
using namespace std;
typedef int ElemType;
typedef int Status; 
#define OK 1
#define ERROR 0 
 
 
//单链表的存储结构 
typedef struct LNode{
	ElemType data;//结点的数据域，用来存储自身的信息
	struct LNode *next;//结点的指针域，用来指向一整个结点
}LNode,*LinkList;//对同一结构体指针类型起了两个名称
 
 
//单链表的初始化 
Status InitList(LinkList &L)
{
	L=new LNode;//生成新的头结点，并让头指针L指向头结点
	L->next=NULL;//将头结点的指针域置空
	return OK; 
} 
 
 
//前插法创建单链表 
void CreatList_Q(LinkList &L,int n)
{
	LNode *p;
	L=new LNode;
	L->next=NULL;
	cout<<"请输入"<<n<<"个元素"<<endl; 
	for(int i=0;i<n;i++){
		p=new LNode;
		cin>>p->data;
		p->next=L->next;L->next=p;
	}	
}
 
 
//后插法创建单链表 
void CreatList_H(LinkList &L,int n)
{
	LNode *p,*r;
	L=new LNode;
	L->next=NULL;
	r=L;
	cout<<"请输入"<<n<<"个元素"<<endl; 
	for(int i=0;i<n;i++){
		p=new LNode;
		cin>>p->data;
		p->next=NULL;r->next=p;
		r=p;
	}
}
 
 
//单链表的取值 
Status GetElem(LinkList L,int i,ElemType &e)
{
	LNode *p;
	p=L->next;
	int j=1;
	while(p!=NULL && j<i)
	{
		p=p->next;
		j++;
	}
	if(p==NULL || j>i) return ERROR;
	e=p->data;
	return OK;
} 
 
 
//单链表的查找 
LNode *LocateElem(LinkList L,ElemType e)
{
	LNode *p; 
	p=L->next;//p指向首元结点
	while(p!=NULL && p->data!=e)
		p=p->next;//p指向下一个结点
	return p;//查找成功返回e的结点地址，否则返回NULL
} 
 
 
//单链表插入元素
Status ListInsert(LinkList &L,int i,ElemType e)
{
	LNode *p,*s; 
	p=L;
	int j=0;
	while(p!=NULL && (j<i-1))
		{p=p->next;j++;}
	if(p==NULL || j>i-1) return ERROR;
	s=new LNode;
	s->data=e;
	s->next=p->next;
	p->next=s;
	return OK;
}  
 
 
//单链表删除元素
Status ListDelete(LinkList &L,int i)
{
	LNode *p,*q; 
	p=L;
	int j=0;
	while((p->next!=NULL) && (j<i-1))
		{p=p->next;j++;}
	if(p->next==NULL || (j>i-1)) return ERROR;
	q=p->next;
	p->next=q->next;
	delete q;
	return OK;
} 
 
 
//单链表的遍历
void Display(LinkList L)
{
	LNode *p;
	p=L->next;
	cout<<"当前单链表为："<<endl; 
	while(p!=NULL){
		cout<<p->data<<" ";
		p=p->next;
	}
	cout<<endl;
} 
 
 
int main()
{
	LinkList L;
	int k; 
	k=InitList(L);
	if(k==0) cout<<"初始化失败！";
	else{
		cout<<"初始化成功！"<<endl;
		int n,h;
		cout<<"请输入您要存储的元素的个数：";
		cin>>n; 
		CreatList_H(L,n);
		Display(L);
		cout<<"1:对单链表中的元素进行取值"<<endl;
		cout<<"2:查找单链表中元素的位置"<<endl;
		cout<<"3:在单链表中插入一个元素"<<endl;
		cout<<"4:删除单链表中的一个元素"<<endl<<"5:退出"<<endl; 
		while(1){
			cout<<"请输入您的选择：";
			cin>>h;
			if(h==1){
				ElemType e;
				int i;
				cout<<"请输入您要查询的是第几个元素:";
				cin>>i;
				GetElem(L,i,e);
				cout<<"该元素为："<<e<<endl; 
			}
			else if(h==2){
				ElemType e;
				LNode *g;
				cout<<"请输入您要查询的元素：";
				cin>>e; 
				g=LocateElem(L,e);
				cout<<"该结点的地址为："<<g<<endl; 
			}
			else if(h==3){
				int i;
				ElemType e;
				cout<<"请输入您要插入的位置及元素：";
				cin>>i>>e;
				ListInsert(L,i,e);
				Display(L);
			}
			else if(h==4){
				int i;
				cout<<"请输入您要删除元素的位置：";
				cin>>i; 
				ListDelete(L,i);
				Display(L);
			}
			else if(h==5) {cout<<"退出成功！";break;}
		} 
	}
	return 0;
} 

运行截图