数据结构第4讲单链表

痛定思痛。 2022-05-17 00:49 147阅读 0赞

数据结构 第4讲 单链表

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

![这里写图片描述][70]

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

结点结构体的定义：

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

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

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

![这里写图片描述][70 1]

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

![这里写图片描述][70 2]  
就像是给铁链子加个钥匙扣：

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

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

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

1.  单链表初始化

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

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

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

if(!L)

return false; //生成结点失败

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

1.  单链表的创建

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

前插法建表如图：

初始状态

输入数据元素1，创建新结点，把元素1放入新结点数据域：

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

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

前插操作，插入到头结点的后面：

![这里写图片描述][70 3]

输入数据元素2，创建新结点，把元素2放入新结点数据域：

前插操作，插入到头结点的后面：

`![这里写代码片](https://img-blog.csdn.net/20180803200903206?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNzg5OTU5/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70)`

解释：

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

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

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

![][70 4]

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

拉直链表之后：

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

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插入到头结点之后
    
    }

尾插法建表如图：

初始状态(尾插法需要一个尾指针永远指向链表的尾结点)

输入数据元素1，创建新结点，把元素1放入新结点数据域：

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

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

尾插操作，插入到尾结点的后面：

解释：

输入数据元素2，创建新结点，把元素2放入新结点数据域：

尾插操作，插入到尾结点的后面：

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

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
    
    }

[70]: /images/20220517/4c83c5dc748e4ad7a7138bc1bbc93995.png
[70 1]: /images/20220517/d18fc999762b4a73bf667c0ec16bdfad.png
[70 2]: /images/20220517/35aed913e30b4e4f9710df468b9ee56f.png
[70 3]: /images/20220517/e77af055d32a461da8962c33527abe4b.png
[70 4]: /images/20220517/a02bddd0e6294274b87ec15ecb853466.png