【数据结构】线性表的链式存储-单链表

骑猪看日落 2021-11-27 03:22 414阅读 0赞

## 单链表的定义 ##

线性表的链式存储又称为单链表，它是指通过一组任意的存储单元来存储线性表中的数据元素。 为了建立起数据元素之间的线性关系，对每个链表结点，除了存放元素自身的信息之外，还需要存放一个指向其后继的**指针**。

每个结点包括数据域和指针域。节点是一个结构体，看一下结构体的定义：

typedef struct LNode{
            ElemType data;
            struct LNode *next;
    }LNode,*LinkList;

注意这是节点而不是整个单链表。  
节点的第一个部分是数据域data。  
第二个部分是指针next，指向的类型是节点的类型，表示指向下一个节点。  
节点的名字取为LNode。  
结构体的指针类型记作LinkList。

那么如何表示一个单链表呢？

## 单链表的两种建表方法 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70]

> 头结点和头指针的区别？

不管带不带头结点，头指针始终指向链表的第一个结点，而头结点是带头结点链表中的第一个结点，结点内通常不存储信息。

> 为什么要设置头结点？

1.  处理操作起来方便 例如：对在第一元素结点前插入结点和删除第一结点起操作与其它结点的操作就统一了
2.  无论链表是否为空，其头指针是指向头结点的非空指针，因此空表和非空表的处理也就统一了。

如何建立单链表？按照插入位置分为两种方式：

## 1.头插法建立单链表： ##

建立新的节点分配内存空间，将新节点插入到当前链表的**表头**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70 1]

LinkList CreatList1(LinkList &L)
    {
            LNode *s;						  //辅助指针
    		int x;							  //储存插入节点的数据的值
            L=(LinkList)malloc(sizeof(LNode));//创建头节点
            L->next=NULL;					  //初始为空链表
            scanf("%d",&x);					  //输入节点的值
            while(x!=9999){					  //输入9999表示结束（要根据实际题目来确定终止条件）
                    s=(LNode*)malloc(sizeof(LNode));	//创建新节点
                    s->data=x;							//对新节点的数据域进行赋值
                    s->next=L->next;					//**新节点的后继指向第一个节点**
                    L->next=s;							//**头节点的后继指向新节点**
                    scanf("%d",&x);					//读入下一个节点值
            }
            return L;										//返回建好的链表的头指针L
    }

头插法建立单链表，读入数据的顺序与生成的链表中元素的顺序是**相反**的。

## 2.尾插法建立单链表 ##

建立新的结点分配内存空间，将新结点插入到当前链表的**表尾**。  
需要增加一个指向表尾元素的尾指针。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70 2]

LinkList CreatList2(LinkList &L)
    {
            int x;
            L=(LinkList)malloc(sizeof(LNode));			//带头节点的链表
            LNode *s,*r=L;								//r为表尾指针 指向表尾
            scanf("%d",&x);								//输入结点的值
            while(x!=9999){								//输入9999表示结束
                    s=(LNode*)malloc(sizeof(LNode));
                    s->data=x;
                    r->next=s;
                    r=s;								//r指向新的表尾结点
                    scanf("%d",&x);
            }
            r->next=NULL;								//尾结点指针置空
            return L;
    }

尾插法建立单链表，读入数据的顺序与生成的链表中元素L 的顺序是相同的。

## 单链表的基本操作 ##

### 按序号查找 ###

在单链表中从第一个结点出发，顺指针next域逐个往下搜索，直到找到第i个结点为止,否则返回最后一个结点指针域NULL。  
![在这里插入图片描述][20190723180627428.png]

因为是查找结点，所以函数的返回类型是指向结点的指针类型。  
参数有两个，是链表L和结点序号i（只需对链表进行读取，不需修改，所以不必设置引用类型）

LNode *GetElem(LinkList L,int i)
    {
            int j=1;					//计数，初始为1
            LNode *p=L->next;			//第一个结点指针赋给p
            if(i==0)					//若i等于0，则返回头结点
                    return L;					
            if(i<1)						//若i无效，则返回NULL
                    return NULL;
            while(p&&j<i)				//从第1个结点开始找，查找第i个结点	（此处一定要判断p不为空）
            {
                    p=p->next;
                    j++;
            }
            return p;					//返回第i个结点的指针，如果i大于表长，直接返回p即可
    }

### 按值查找 ###

从单链表第一个结点开始，由前往后依次比较表中各结点数据域的值，若某结点数据域的值等于给定值e，则返回该结点的指针；若整个单链表中没有这样的结点，则返回NULL。  
![在这里插入图片描述][20190723180558466.png]

LNode *LocateElem(LinkList L,ElemType e)
    {
            LNode *p=L->next;
            while(p!=NULL&&p->data!=e)		//从第1个结点开始查找data域为e的结点（此处一定要判断p不为空）
                    p=p->next;
            return p;										//找到后返回该结点指针，否则返回NULL
    }

### 插入 ###

插入操作是将值为x的新结点插入到单链表的第i个位置上。先检查插入位置的合法性，然后找到待插入位置的前驱结点，即第i−1个结点，再在其后插入新结点。  
**算法思路：**

1.  取指向插入位置的前驱结点的指针  
    ① p=GetElem(L,i-1);
2.  令新结点*s的指针域指向*p的后继结点  
    ② s->next=p->next;
3.  令结点*p的指针域指向新插入的结点*s  
    ③ p->next=s;  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70 3]

bool ListFrontInsert(LinkList L,int i,ElemType e)
    {
            LinkList p=GetElem(L,i-1);
            if(NULL==p)
            {
                    return false;
            }
            LinkList s=(LNode*)malloc(sizeof(LNode));//为新插入的结点申请空间
            s->data=e;
            s->next=p->next;
            p->next=s;
            return true;
    }

### 删除 ###

删除操作是将单链表的第i个结点删除。先检查删除位置的合法性，然后查找表中第i−1个结点，即被删结点的前驱结点，再将其删除。  
**算法思路：**

1.  取指向删除位置的前驱结点的指针 p=GetElem(L,i-1);
2.  取指向删除位置的指针 q=p->next;
3.  p指向结点的后继指向被删除结点的后继 p->next=q->next
4.  释放删除结点 free(q);  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70 4]

bool ListDelete(LinkList L,int i)
    {
            LinkList p=GetElem(L,i-1);
            if(NULL==p)
            {
                    return false;
            }
            LinkList q;
            q=p->next;
            p->next=q->next;
            free(q);
            return true;
    }

### 参考资料 ###

[https://www.bilibili.com/video/av36895433/?p=11][https_www.bilibili.com_video_av36895433_p_11]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70]: /images/20211126/96859e428e4141a4b122aeb0a8601b1d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70 1]: /images/20211126/bb81f1823152492980f67923455d0a5a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70 2]: /images/20211126/20ed91a65cdd4151baa75aba4a6bcfaa.png
[20190723180627428.png]: /images/20211126/de65746405fb431e8903adf518e6d858.png
[20190723180558466.png]: /images/20211126/956312d6a576461db76b89fb515fa51a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70 3]: /images/20211126/ad21277eeb404300ba509ba827db9dfd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70 4]: /images/20211126/3e992c70c5e04b12b1331771751c080b.png
[https_www.bilibili.com_video_av36895433_p_11]: https://www.bilibili.com/video/av36895433/?p=11