数据结构—线性结构—(单链表)

素颜马尾好姑娘i 2023-07-19 05:50 53阅读 0赞

### 这里写目录标题 ###

*   *  定义：
     *  存取方式：
     *  单链表的两种实现形式：
     *  单链表的基本操作：
     *   *  头插法建立单链表：
         *  尾插法建立单链表：
         *  按序号查找&按值查找：
         *   *  按序号查找：
             *  按值查找：
         *  插入：
         *   *  前插法：
             *  后插法：
         *  删除：
         *   *  删除第i个元素
             *  删除给定节点 \*p
         *  求表长：

## 定义： ##

线性表的链式存储又称单链表

即：通过一组任意的存储单元来存储线性表当中的数据元素，数据元素存储的位置不一定是连续的。

（有可能连续，有可能不连续）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70]

## 存取方式： ##

通过指针实现线性的逻辑关系

链表不能实现随机存取，且每个元素包含两部分，

> ① data     即元素值  
> ② \*next    即下一个元素的存储地址

所以，我们也可以使用一个指针用来表示单链表

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

## 单链表的两种实现形式： ##

不带头结点  
![在这里插入图片描述][20200329220624901.png]

带头结点（优）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 2]

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

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 4]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 5]  
![在这里插入图片描述][20200329221411427.png]

> s -> next = L -> next;  
> L -> next = s;

头插法建立单链表：时间复杂度O（n）

LinkList List_HeadInsert(LinkList &L){ 
    	LNode *s;int x;
    	L=(LinkList)malloc(sizeof(LNode));
    	L->next=NULL;
    	scanf("%d",&x);
    	while(x!=9999){ 
    		s=(LNode*)malloc(sizeof(LNode));
    		s->data=x;
    		s->next=L->next;
    		L->next=s;
    		scanf("%d",&x);
    	}
    	return L;
    }

### 尾插法建立单链表： ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 6]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 7]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 8]  
![在这里插入图片描述][20200329222708720.png]

> r -> next = s;  
> r = s;

尾插法建立单链表：时间复杂度O（n）

LinkList List_TailInsert(LinkList &L){ 
    	int x;
    	L=(LinkList)malloc(sizeof(LNode));
    	LNode *s,*r=L;
    	scanf("%d",&x);
    	while(x!=9999){ 
    		s=(LNode*)malloc(sizeof(LNode));
    		s->data=x;
    		r->next=s;
    		r=s;
    		scanf("%d",&x);
    	}
    	r->next=NULL;
    	return L;
    }

### 按序号查找&按值查找： ###

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

> 两种查找均要遍历单链表，仅比较的数据不同  
> .  
> 按序号查找需要给遍历元素计数，从而找到要找的元素  
> .  
> 按值查找需要比对每个元素的属性值是否与要找的元素相同

按序号查找&按值查找：时间复杂度O（n）

#### 按序号查找： ####

LNode *GetElem(LinkList L,int i){ 
    	int j=1;
    	LNode *p=L->next;
    	if(i==0) return L;
    	if(i<1) return NULL;
    	while(p&&j<i){ 
    		p=p->next;
    		j++;
    	}
    	return p;
    }

#### 按值查找： ####

LNode *LocateElem(LinkList L,ElemType e){ 
    	LNode *p=L->next;
    	while(p!=NULL&&p->data!=e){ 
    		p=p->next;
    	}
    	return p;
    }

### 插入： ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 10]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 11]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 12]

> p = GetElem(L, i - 1);  
> s -> next = p -> next;  
> p-> next = s ;

插入操作：

> 前插法  
> 在第 i 个位置前插入元素

#### 前插法： ####

前插法：时间复杂度O(n)

> 后插法  
> 在第 i 个位置后插入元素

#### 后插法： ####

后插法：时间复杂度O(1)

> 可以利用后插法实现前插法  
> .  
> 先在第 i 个位置插入元素 e  
> .  
> 然后交换第 i 个位置和第 i - 1 个位置的值

### 删除： ###

#### 删除第i个元素 ####

![在这里插入图片描述][20200329230244930.png]  
![在这里插入图片描述][20200329230303174.png]  
![在这里插入图片描述][20200329230334714.png]  
![在这里插入图片描述][20200329230343951.png]  
![在这里插入图片描述][20200329230416491.png]

> p = GetElem( L, i - 1 );  
> q = p -> next;  
> p -> next = q -> next;  
> free(q);

#### 删除给定节点 \*p ####

![在这里插入图片描述][20200329230758552.png]  
![在这里插入图片描述][20200329230820358.png]  
![在这里插入图片描述][20200329230837164.png]

> q=q->next;  
> p->data=p->next->data;  
> p->next=q->next;  
> free(q);

### 求表长： ###

![在这里插入图片描述][20200329231046845.png]  
求表长：时间复杂度O（n）

int count=0;
    p=head;
    while(p->next!=NULL){ 
    	count++;
    	p=p->next;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70]: /images/20230528/018867b00a0c410e99a86c411e53ab9c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 1]: /images/20230528/a64c903e7b304ed78a9590d4ad970048.png
[20200329220624901.png]: /images/20230528/99cd151a99d54cd3ba4d6adfba589efa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 2]: /images/20230528/3963fd33943d4dff978941d332fcf232.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 3]: /images/20230528/2c6a89a296914e7f89dcaf9ac642c1b3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 4]: /images/20230528/d8eec47ef4834057b799d9eebc5906f6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 5]: /images/20230528/89858815ca574b0b8471a3b3c037e985.png
[20200329221411427.png]: /images/20230528/c5f7d00037d842b39ecf2182325bb930.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 6]: /images/20230528/182eaff8473e442fb29aa16f0dc9c3eb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 7]: /images/20230528/35120a5477e54bd9833a5dddce82f739.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 8]: /images/20230528/c71998c4241548fd94fb6569208439d1.png
[20200329222708720.png]: /images/20230528/0cbd7481949f41d8b132f68892e139b6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 9]: /images/20230528/2202dfeb52c64181a1389a07b1ad95a2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 10]: /images/20230528/b690a161c93b44bdbd93cc231e6db7e0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 11]: /images/20230528/b030de2a83c2412588321b4fdb7be538.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 12]: /images/20230528/ce82217c018647a1aa05aac5690bceb4.png
[20200329230244930.png]: /images/20230528/e50c50f3dd314a6d80142f5293218325.png
[20200329230303174.png]: /images/20230528/1593dd7714d743b1802dc53051c0dc5c.png
[20200329230334714.png]: /images/20230528/c37bc38dabc7483991081b7500acd272.png
[20200329230343951.png]: /images/20230528/4f2e65f2f13c4e26b13f751bca3c912b.png
[20200329230416491.png]: /images/20230528/8bfc6affced742f3be62e4c74ac08a02.png
[20200329230758552.png]: /images/20230528/d6a16176c6fd4136a61c0c8d4b7fba40.png
[20200329230820358.png]: /images/20230528/5c8ee777e1f340ceaa00b047c0087e12.png
[20200329230837164.png]: /images/20230528/bfa45e40db3c48a791c631ce56a000a0.png
[20200329231046845.png]: /images/20230528/e161109596154de2932c012b00451917.png