数据结构第4讲单链表

你的名字 2022-06-08 08:21 184阅读 0赞

**数据结构 第4讲 单链表**

链表是线性表的链式存储方式，逻辑上相邻的数据在计算机内的存储位置不一定相邻，那么怎么表示逻辑上的相邻关系呢？可以给每个元素附加一个指针域，指向下一个元素的存储位置。如图所示：

![Center][]

从图中可以看出，每个结点包含两个域：数据域和指针域，指针域存储下一个结点的地址，因此指针指向的类型也是结点类型。

**结点结构体的定义：**

![Center 1][]

定义了结点之后，我们就可以把若干个结点连接在一起，形成一个链表：

![Center 2][]

是不是像一个铁链子，一环扣一环的连在一起？

![Center 3][]

不管这个铁链子有多长，只要我们找到它的头，就可以拉起整个铁链子，因此我们给这个链表设置一个头指针，这个链表中的每个结点都可以找到了。

![Center 4][]

有时候为了操作方便，我们还会给链表增加一个不存放数据的头结点：

![Center 5][]

就像是给铁链子加个钥匙扣：

![Center 6][]

我们可以看到刚才的链表每个指针都是指向下一个结点，都是朝向一个方向的，这样的链表称为单向链表，或**单链表**。

在顺序表中，想找第*i*个元素，就可以立即通过L.elem\[i-1\]找到，称为**随机存取**方式，而在单链表中，想找第*i*个元素？没那么容易，必须从头开始，按顺序一个一个来，一直数到第*i*个元素，称为**顺序存取**方式。

下面以带头结点的单链表为例，讲解单链表的初始化、创建、取值、查找、插入、删除操作。

1. 单链表初始化

单链表初始化是指构建一个空表：

![Center 7][]

bool InitList\_L(LinkList &L)//构造一个空的单链表L

L=new LNode; //生成新结点作为头结点，用头指针L指向头结点

if(!L)

return false; //生成结点失败

L->next=NULL; //头结点的指针域置空

return true;

2. 单链表的创建

创建单链表分为**前插法**和**尾插法**两种，前插法创建的单链表和输入顺序正好相反，因此称为逆序建表，尾插法创建的单链表和输入顺序一致，因此称为正序建表。

前插法建表如图：

*  初始状态
    
    ![Center 7][]
 *  输入数据元素1，创建新结点，把元素1放入新结点数据域：
    
    ![Center 8][]
    
    s=new LNode; //生成新结点s
    
    cin>>s->data; //输入元素值赋给新结点的数据域
 *  前插操作，插入到头结点的后面：
    
    ![Center 9][]
 *  输入数据元素2，创建新结点，把元素2放入新结点数据域：
 *  ![Center 10][]
 *  前插操作，插入到头结点的后面：
    
    ![Center 11][]

解释：

![Center 12][]

**为什么要先修改后面那个指针呢？**

因为一旦修改了L结点的指针域指向s，那么原来L结点后面的结点就找不到了，

注意：修改指针顺序的**原则：先修改没有指针标记的那一端。**

![Center 13][]

如果要插入结点的两端都有标记，例如再定义一个指针*q*指向第1个结点，那么先修改哪个指针都无所谓了。

拉直链表之后：

![Center 14][]

*  继续依次输入数据元素3，4，5，6，7，8，9，10，前插法创建链表的结果：

![Center 15][]

void CreateList\_H(LinkList &L)//前插法创建单链表

int n; //输入n个元素的值，建立到头结点的单链表L

LinkList s; //定义一个指针变量

L=new LNode;

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

cout <<"请输入元素个数n：" <<endl;

cin>>n;

cout <<"请依次输入n个元素：" <<endl;

cout <<"前插法创建单链表..." <<endl;

while(n--)

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

cin>>s->data; //输入元素值赋给新结点的数据域

s->next=L->next;

L->next=s; //将新结点s插入到头结点之后

尾插法建表如图：

*  初始状态(尾插法需要一个尾指针永远指向链表的尾结点)
    
    ![Center 16][]
 *  输入数据元素1，创建新结点，把元素1放入新结点数据域：
    
    ![Center 17][]
    
    s=new LNode; //生成新结点s
    
    cin>>s->data; //输入元素值赋给新结点的数据域
 *  尾插操作，插入到尾结点的后面：
    
    ![Center 18][]

解释：

![Center 19][]

*  输入数据元素2，创建新结点，把元素2放入新结点数据域：
    
    ![Center 20][]
 *  尾插操作，插入到尾结点的后面：
    
    ![Center 21][]
 *  继续依次输入数据元素3，4，5，6，7，8，9，10，前插法创建链表的结果：

![Center 22][]

void CreateList\_R(LinkList &L)//尾插法创建单链表

//输入n个元素的值，建立带表头结点的单链表L

int n;

LinkList s, r;

L=new LNode;

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

r=L; //尾指针r指向头结点

cout <<"请输入元素个数n：" <<endl;

cin>>n;

cout <<"请依次输入n个元素：" <<endl;

cout <<"尾插法创建单链表..." <<endl;

while(n--)

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

cin>>s->data; //输入元素值赋给新结点的数据域

s->next=NULL;

r->next=s;//将新结点s插入尾结点r之后

r=s;//r指向新的尾结点s

3. 单链表取值

单链表的取值不像顺序表那样可以随机访问任何一个元素，单链表只有头指针，各个结点的物理地址是不连续的，要想找到第*i*个结点，就必须从第一个结点开始按顺序往后数，一直数到第*i*个结点。

那么具体怎么做呢？

**注意：链表的头指针不可以随意改动！**一个链表是由头指针来标识的，一旦头指针改动或丢失，这个链表就不完整或找不到了。想想看，你拉着铁链子一头，另一端绑着水桶，到井里打水，你手一松，链子掉井里，找不到了。所以链表的头指针是不能随意改动的，如果需要用指针移动，可定义一个指针变量进行移动。

可以定义一个*p* 指针，指向第一个元素结点，用*j*作为计数器，*j*=1；

然后p指向p的下一个结点，即：

p=p->next; //p指向下一个结点

j++; //计数器j加1

直到*p*为空或者*j*=*i*停止，*p*为空说明没有数到*i*，链表就结束了，*j*=*i*说明找到了第*i*个结点。

![Center 23][]

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<i && p) //顺着链表向后扫描，直到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;

4. 单链表查找

在一个单链表中查找是否存在元素*e*，可以定义一个*p* 指针，指向第一个元素结点，比较*p*指向结点的数据域是否为*e*，如果相等，查找成功返回true，如果不等，则p指向p的下一个结点，即：

p=p->next; //p指向下一个结点

继续比较，如果p为空，查找失败返回false。

![Center 24][]

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;

5. 单链表插入

如果要在第*i*个结点之前插入一个元素，则必须先找到第*i*\-1个结点，想一想：为什么？

单链表只有一个指针域，是向后操作的，不可以向前处理，第*i*个结点之前插入一个元素相当于把新结点放在第*i*\-1个结点和第*i*个结点之间。

![Center 25][]

解释：

![Center 26][]

**是不是有似曾相识的感觉？**

前面讲的前插法建链表，就是每次将新结点插入到头结点和第一个结点之间。

bool ListInsert\_L(LinkList &L, int i, int &e)//单链表的插入

//在带头结点的单链表L中第i个位置插入值为e的新结点

int j;

LinkList p, s;

p=L;

j=0;

while (p&&j<i-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;

6. 单链表删除

删除一个结点，实际上是把这个结点跳过去。如图：

![Center 27][]

要想跳过第*i*个结点，就必须先找到第*i*\-1个结点，否则是无法跳过去的。

p->next=q->next；含义是将*q*结点的下一个结点地址赋值给*p*结点的指针域。在这些有关指针的赋值语句中，很多同学不理解，容易混淆，在此说明一下，等号的右侧是结点的地址，等号的左侧是结点的指针域：

![Center 28][]

*q*结点的下一个结点地址存储在q->next里面，等号右侧的q->next就相当于把*q*结点的下一个结点地址读出来，赋值给*p*结点的next指针域，这样，就把*q*结点跳过去了。然后用delete q释放被删除结点的空间。

bool ListDelete\_L(LinkList &L, int i) //单链表的删除

//在带头结点的单链表L中，删除第i个位置

LinkList p, q;

int j;

p=L;

j=0;

while((p->next)&&(j<i-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;

单链表基本操作完整代码：

完整代码：

\#include<iostream>

\#include<string>

\#include<iomanip>

\#include<stdlib.h>

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：" <<endl;

cin>>n;

cout <<"请依次输入n个元素：" <<endl;

cout <<"前插法创建单链表..." <<endl;

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：" <<endl;

cin>>n;

cout <<"请依次输入n个元素：" <<endl;

cout <<"尾插法创建单链表..." <<endl;

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<i && p) //顺链域向后扫描，直到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<i-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<i-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 <<p->data <<"\\t";

p=p->next;

cout<<endl;

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 << "个元素是："<<e<< endl;

else

cout << "查找失败\\n\\n";

break;

case 5: //单链表的按值查找

cout<<"请输入所要查找元素x:";

cin>>x;

if (LocateElem\_L(L,x))

cout << "查找成功\\n";

else

cout << "查找失败! " <<endl;

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;

本文来自《趣学数据结构》，让数据结构变得简单有趣。

[Center]: /images/20220608/37b9c78335aa4f518f33f6056ea62fc5.png
[Center 1]: /images/20220608/24b9d704bf3e491a94bf8bf865fc5e6b.png
[Center 2]: /images/20220608/7f11d115a29b4d71964717892a8a66f9.png
[Center 3]: /images/20220608/9ed118e177d64510a2a7d0635caef81f.png
[Center 4]: /images/20220608/f97f44cb3d0e41919890df7f1a01714c.png
[Center 5]: /images/20220608/e0afd6b8e32240f780945d7c0aa6508f.png
[Center 6]: /images/20220608/f637ebba6ac54c4abaf04ed2ad8d804f.png
[Center 7]: /images/20220608/d23f670ea5d743c1bfc9d072d76a8163.png
[Center 8]: /images/20220608/10fb7a69006c4361ba5132c8beb9ede9.png
[Center 9]: /images/20220608/8e2aac52f8fe4fdfbdfbdcf9709b2775.png
[Center 10]: /images/20220608/86cd24ddda67422586877fcd6e50a233.png
[Center 11]: /images/20220608/f54939b74c534112b4e32d38dc49b157.png
[Center 12]: /images/20220608/e9239bd8d85947249c0852b57275f829.png
[Center 13]: /images/20220608/a7a683a91da74cdc8414dd28cd1d4aa0.png
[Center 14]: /images/20220608/3d9036d528a14d57bbb942e5ee11fa76.png
[Center 15]: /images/20220608/5ab2ae778663448dafdabfd779c6a2d6.png
[Center 16]: /images/20220608/160d4e1513e441b18766cd0f76cca93b.png
[Center 17]: /images/20220608/a66032e56952441eae40ab26f9567697.png
[Center 18]: /images/20220608/fb88d001681248e99f80c6ac5fcd6f4e.png
[Center 19]: /images/20220608/a6649d3c90b848b5a1699a44d5badccd.png
[Center 20]: /images/20220608/bd13e51d0bb34c9ea4cfb33cc6e221b1.png
[Center 21]: /images/20220608/7a8f7aba62524bf2a9656c3e38a9dcf5.png
[Center 22]: /images/20220608/86ecc40cdc184e3b98a308ffee939c86.png
[Center 23]: /images/20220608/a254914314c145c5801b222f86b26c38.png
[Center 24]: /images/20220608/040f83ccad06437493ec0358791a0b57.png
[Center 25]: /images/20220608/3ef14004b85e47bf836362a6948262cf.png
[Center 26]: /images/20220608/8fcd8e35d27e4972818a4aa7f7960627.png
[Center 27]: /images/20220608/c442e6b95af442f1bfdf5a6bc3a031b1.png
[Center 28]: /images/20220608/28868f90878541d89b9d0cf71f01c154.png