线性表的链式存储的基本

链表是线性表的链式存储方式，逻辑上相邻的数据在计算机内的存储位置不一定相邻，因此，我们需要为每一个元素设置有一个指针来指向与它逻辑相邻的元素。

为此，我们为每个元素设置一个结点，每个结点由数据域和指针域组成，数据域用来存放该结点的元素值，指针域用来存放与其逻辑相邻的元素的地址。

链表有带头结点的链表和不带头结点的链表之分，带头结点的链表会有一个头结点，头结点

单链表只能向后走，不能往回走。

为了操作方便，我们给单向链表加了头结点，头结点的data域是不存储数据的，

什么时候操作方便呢？当我们把第一个结点删除的时候，如果在没有头结点的情况下，删除第一个结点与删除其他结点是不一样的，因为我们需要改头指针，第一个结点删除，头指针需要指向第二个；但是当我们设置头结点后，我要删除第一个结点，头指针是不用动的。

 单链表的基本操作包含：

• 初始化

首先要生成一个结点，然后将其next域置空。

• 创建

头插法：采用头插法将结点s插入链表L中，逆序建表

1. s->next = L->next;
2. L->next = s;

 

 尾插法：采用尾插法将结点s插入链表L中，正序建表

1. 定义尾指针r记录尾结点
2. 创建新生成了的结点用s,将待插值赋给结点s的data域，并将s结点的next域置空
3. r->next = s;
4. r = s;更新尾指针

 

• 取值：找链表L的第i个结点

1. 链表头指针不可以随意改动
2. 设置一个指针 p 指向第一个元素即  p = L->next;
3. 设置计数变量 j  并将其初始化为1
4. 如果 j < i 且 p->next != NULL，继续向后找即  p = p->next; j++;
5. 一直走到 j == i ，成功找到了链表L的第i个结点
6. 一直往后找的时候，需要判断有没有走到链表的头部，有没有等空，等空就不需要再找了
7. 另外，需要判断 j 是否小于 i，如果大于的话，也不需要再找了

• 插入：再链表的第 i 个结点之前插入新结点s

1. 先找到第 i-1 个结点，让p指针指向该结点
2.  s->next = p->next;
3. p->next = s;

 

• 查找：在单链表L中查找data域为e的结点

1. 定义指针p并将其指向链表的第一个结点
2. 在p结点存在的情况下，判断p的data域的值是否等于e，如果不等于继续向后查找
3. 如果找到链表结尾仍然没有找到，返回false
4. 如果找到的情况下，返回true

• 删除：删除链表L的第 i 个结点

1. 查找链表的第 i - 1 个结点，将p指向该节点
2. 判断删除的结点位置是否合理，如果第 i - 1 个结点的next域为空，即不存在要删除的第 i 个结点，或者 如果要删除的位置索引 i 大于链表的长度或者小于 0时，删除位置不合理
3. 如果删除位置合理的话，用指针q指向待删除的第 i 个结点，即p->next
4. 将第 i - 1 个结点的next指向第 i 个结点的next域所指向的第 i+1 个结点
5. 最后通过delete命令释放第 i 个结点的空间

 

 

 

#include
#include
#include
#include
using namespace std;
 
typedef struct LNode {
	int data; //结点的数据域
	struct LNode *next; //结点的指针域
}LNode, *LinkList; //LinkList为指向结构体LNode的指针类型
 
bool InitList_L(LinkList &L)//构造一个空的单链表L
{
    L=new LNode;     //生成新结点作为头结点，用头指针L指向头结点
	if(!L)
      return false;  //生成结点失败
	L->next=NULL;   //头结点的指针域置空
	return true;
}
 
void CreateList_H(LinkList &L)//前插法创建单链表
{
	//输入n个元素的值，建立到头结点的单链表L
	int n;
	LinkList s; //定义一个指针变量
	L=new LNode;
	L->next=NULL; //先建立一个带头结点的空链表
	cout <<"请输入元素个数n：" <
	cin>>n;
	cout <<"请依次输入n个元素：" <
	cout <<"前插法创建单链表..." <
	while(n--)
    {
		s=new LNode; //生成新结点s
		cin>>s->data; //输入元素值赋给新结点的数据域
		s->next=L->next;
		L->next=s; //将新结点s插入到头结点之后
	}
}
 
void CreateList_R(LinkList &L)//尾插法创建单链表
{
	//输入n个元素的值，建立带表头结点的单链表L
	int n;
	LinkList s, r;
	L=new LNode;
	L->next=NULL; //先建立一个带头结点的空链表
	r=L; //尾指针r指向头结点
	cout <<"请输入元素个数n：" <
	cin>>n;
	cout <<"请依次输入n个元素：" <
	cout <<"尾插法创建单链表..." <
	while(n--)
    {
		s=new LNode;//生成新结点
		cin>>s->data; //输入元素值赋给新结点的数据域
		s->next=NULL;
		r->next=s;//将新结点s插入尾结点*r之后
		r=s;//r指向新的尾结点s
	}
}
 
bool GetElem_L(LinkList L, int i, int &e)//单链表的取值
{
	//在带头结点的单链表L中查找第i个元素
	//用e记录L中第i个数据元素的值
	int j;
	LinkList p;
	p=L->next;//p指向第一个结点，
	j=1; //j为计数器
	while (j//顺链域向后扫描，直到p指向第i个元素或p为空
    {
		p=p->next; //p指向下一个结点
		j++; //计数器j相应加1
	}
	if (!p || j>i)
		return false; //i值不合法i＞n或i<=0
	e=p->data; //取第i个结点的数据域
	return true;
}
 
bool LocateElem_L(LinkList L, int e) //按值查找
{
	//在带头结点的单链表L中查找值为e的元素
	LinkList p;
	p=L->next;
	while (p && p->data!=e)//顺链域向后扫描，直到p为空或p所指结点的数据域等于e
		p=p->next; //p指向下一个结点
	if(!p)
        return false; //查找失败p为NULL
    return true;
}
 
bool ListInsert_L(LinkList &L, int i, int e)//单链表的插入
{
	//在带头结点的单链表L中第i个位置插入值为e的新结点
	int j;
	LinkList p, s;
	p=L;
	j=0;
	while (p&&j-1) //查找第i-1个结点，p指向该结点
    {
		p=p->next;
		j++;
	}
	if (!p || j>i-1)//i＞n+1或者i＜1
		return false;
	s=new LNode;     //生成新结点
	s->data=e;       //将新结点的数据域置为e
	s->next=p->next; //将新结点的指针域指向结点ai
	p->next=s;       //将结点p的指针域指向结点s
	return true;
}
 
bool ListDelete_L(LinkList &L, int i) //单链表的删除
{
	//在带头结点的单链表L中，删除第i个位置
	LinkList p, q;
	int j;
	p=L;
	j=0;
	while((p->next)&&(j-1)) //查找第i-1个结点，p指向该结点
	{
		p=p->next;
		j++;
	}
	if (!(p->next)||(j>i-1))//当i>n或i<1时，删除位置不合理
		return false;
	q=p->next;        //临时保存被删结点的地址以备释放空间
	p->next=q->next; //改变删除结点前驱结点的指针域
	delete q;        //释放被删除结点的空间
	return true;
}
 
void Listprint_L(LinkList L) //单链表的输出
{
    LinkList p;
    p=L->next;
    while (p)
    {
        cout<data<<"\t";
		p=p->next;
    }
    cout<
}
 
int main()
{
	int i,x,e,choose;
	LinkList L;
	cout << "1. 初始化\n";
	cout << "2. 创建单链表（前插法）\n";
	cout << "3. 创建单链表（尾插法）\n";
	cout << "4. 取值\n";
	cout << "5. 查找\n";
	cout << "6. 插入\n";
	cout << "7. 删除\n";
	cout << "8. 输出\n";
	cout << "0. 退出\n";
	choose=-1;
	while (choose!=0)
    {
		cout<<"请输入数字选择:";
		cin>>choose;
		switch (choose)
		{
		case 1: //初始化一个空的单链表
			if (InitList_L(L))
				cout << "初始化一个空的单链表!\n";
			break;
		case 2: //创建单链表（前插法）
			CreateList_H(L);
            cout << "前插法创建单链表输出结果:\n";
            Listprint_L(L);
			break;
        case 3: //创建单链表（尾插法）
			CreateList_R(L);
            cout << "尾插法创建单链表输出结果:\n";
            Listprint_L(L);
			break;
		case 4: //单链表的按序号取值
			cout << "请输入一个位置i用来取值:";
			cin >> i;
			if (GetElem_L(L,i,e))
            {
				cout << "查找成功\n";
				cout << "第" << i << "个元素是："<
			}
			else
				cout << "查找失败\n\n";
			break;
		case 5: //单链表的按值查找
			cout<<"请输入所要查找元素x:";
			cin>>x;
			if (LocateElem_L(L,x))
				cout << "查找成功\n";
			else
				cout << "查找失败! " <
			break;
		case 6: //单链表的插入
			cout << "请输入插入的位置和元素（用空格隔开）:";
			cin >> i;
			cin >> x;
			if (ListInsert_L(L, i, x))
				cout << "插入成功.\n\n";
			else
				cout << "插入失败!\n\n";
			break;
		case 7: //单链表的删除
			cout<<"请输入所要删除的元素位置i:";
			cin>>i;
			if (ListDelete_L(L, i))
				cout<<"删除成功!\n";
			else
				cout<<"删除失败!\n";
			break;
		case 8: //单链表的输出
			cout << "当前单链表的数据元素分别为:\n";
			Listprint_L(L);
			cout << endl;
			break;
		}
	}
	return 0;
}