浙江同凯建设深圳公司_中国制造网属于b2b吗_百度营销中心_手机百度2020最新版

文章目录

- 单链表
- - 基本概念
  - 链表的分类
  - 单链表节点设计
  - 单链表初始化
  - 单链表增删节点
  - 单链表的遍历
  - 单链表的销毁
  - 链表优缺点
- 循环单项链表

单链表

基本概念

顺序表:顺序存储的线性表
链式表:链式存储的线性表，简称链表

既然顺序存储中的数据因为挤在一起而导致需要成片移动，那很容易想到的解决方案是将数据离散地存储在不同内存块中，然后在用来指针将它们串起来。这种朴素的思路所形成的链式线性表，就是所谓的链表。

顺序表和链表在内存在的基本样态如下图所示：
在这里插入图片描述

链表的分类

根据链表中各个节点之间使用指针的个数，以及首尾节点是否相连，可以将链表细分为如下种类：

单向链表
单向循环链表
双向链表
双向循环链表

这些不同链表的操作都是差不多的，只是指针数目的异同。以最简单的单向链表为例，其基本示意

图如下所示：
在这里插入图片描述
上图中，所有的节点均保存一个指针，指向其逻辑上相邻的下一个节点（末尾节点指向空）。另外注意到，整条链表用一个所谓的头指针 head 来指向，由 head 开始可以找到链表中的任意一个节点。head 通常被称为头指针

链表的基本操作，一般包括：

节点设计
初始化空链表
增删节点
链表遍历
销毁链表

下面着重针对这几项常见操作，讲解单向链表的处理

单链表节点设计

单向链表的节点非常简单，节点中除了要保存用户数据之外（这里以整型数据为例），只需要增加一个指向本类节点的指针即可，如下所示：

typedef int DATA;typedef struct Node
{
DATA data; // 存储数据---数据域
struct Node *next; // 存储下一个节点的地址---指针域
} NODE;

单链表初始化

首先，空链表有两种常见的形式。一种是带所谓的头结点的，一种是不带头结点的。所谓的头结点是不存放有效数据的节点，仅仅用来方便操作，如下：
在这里插入图片描述
而不带头结点的空链表如下所示：

注意：

头指针 head 是必须的，是链表的入口
头节点是可选的，为了方便某些操作

由于头结点是不存放有效数据的，因此如果空链表中带有头结点，那么头指针 head 将永远不变，这会给以后的链表操作带来些许便捷

下面以带头结点的链表为例，展示单向链表的初始化的示例代码：

int slist_create(NODE** head,DATA data)
{NODE* p = (NODE*)malloc(sizeof(NODE));if(!P){return -1;}p->data = data;p->next = NULL;*head = p;return 0;
}

单链表增删节点

相对于顺序表需要整片移动数据，链表增删节点只需要修改几个相关指针的指向，动作非常快速。与顺序表类似，可以对一条链表中的任意节点进行增删操作，示例代码是：

//头插法
int slist_addHead(NODE** head,DATA data)
{NODE* p = (NODE*)malloc(sizeof(NODE));if(!p){return -1;}p->data = data;p->next = *head;*head = p;return 0;
}//尾插法
int slist_addTail(NODE** head,DATA data)
{NODE* pNew = (NODE*)malloc(sizeof(NODE));if(!pNew){return -1;}pNew->data = data;pNew->next = NULL;NODE* P = *head,*q = NULL;if(!p){q = p;p = p->next;}q->next = pNew;return 0;
}//随便插法
int slist_insert(NODE** head,DATA pos,DATA data)
{NODE* pNew = (NODE*)malloc(sizeof(NODE));if(!pNew)return -1;pNew->data = data;pNew->next = NUll;NODE *p = *head,*q = NULL;if(!p){*head = pNew;return 0;}if(memcmp(&(p->data),&pos,sizeof(DATA)) == 0){pNew->next = *head;*head = pNew;return 0;}while(p){if(memcmp(&(p->data),&pos,sizeof(DATA)) == 0){pNew->next = p;q->next = pNew;return 0;}q = p;p = p->next;}q->next = pNew;return 0;
}int slist_update(const NODE* head,DATA old,DATA newdata) 
{NODE* p = NULL;if(!(p = slist_find(head,old)))return -1;p->data = newdata;return 0;
}int slist_delete(NODE** head,DATA data)
{NODE *p = *head,*q = NULL;if(!p)return -1;if(memcmp(&(p->data),&data,sizeof(DATA)) == 0){*head = p->next;free(p);return 0;}while(p){if(memcmp(&(p->data),&data,sizeof(DATA)) == 0){q->next = p->next;free(p);return 0;}q = p;p = p->next;}return -1;
}

注意:

删除链表的节点并不意味着释放其内存，而是将其剔除出链表

单链表的遍历

遍历的意思就是逐个访问每一个节点，对于线性表而言，由于路径唯一的选择就是从头走到尾。因此相当而言比较简单

下面是单向链表的遍历示例代码，假设遍历每个节点并将其整数数据输出：

//查找
NDOE* slist_find(const NODE* head,DATA data)
{const NODE* p = head;while(p){if(memcmp(&(p->data),&data,sizeof(DATA)) == 0){return (NODE*)p;}p = p->next;}return NULL;
}//遍历
void slist_showAll(const NODE* head)
{const NODE* p = head;while(p){printf("%d",p->data);p = p->next;}printf("\n");
}

单链表的销毁

由于链表中的各个节点被离散地分布在各个随机的内存空间，因此销毁链表必须遍历每一个节点，释放每一个节点

注意：

销毁链表时，遍历节点要注意不能弄丢相邻节点的指针

示例代码如下：

void slist_destroy(NODE** head)
{NODE* p = *head,*q = NULL;while(p){q = p;p = p->next;free(q);}*head = NULL;
}

面试题：对于一个具有n和节点的单向链表(n > 100)，只通过一次遍历找到倒数第 50个节点

提示： 借助于 2个指针，一个在前，一个在后。
思路：先让前一个指针遍历到第50个节点的位置，然后后一个指针，再跟随前一个
指针一起向后移动，当前一个指针遍历完所有节点，后一个指针就是指向了
倒数第50个节点的位置

链表优缺点

链式存储中，所有节点的存储位置是随机的，他们之间的逻辑关系用指针来确定，跟物理存储位置无关，因此从上述示例代码可以很清楚看到，增删数据都非常迅速，不需要移动任何数据。另外，又由于位置与逻辑关系无关，因此也无法直接访问某一个指定的节点，只能从头到尾按遍历的方式一个个找到想要的节点。简单讲，链式存储的优缺点跟顺序存储几乎是相对的

总结其特点如下：

优点

插入、删除时只需要调整几个指针，无需移动任何数据
当数据节点数量较多时，无需一整片较大的连续内存空间，可以灵活利用离散的内存
当数据节点数量变化剧烈时，内存的释放和分配灵活，速度快

缺点

在节点中，需要多余的指针来记录节点之间的关联。
所有数据都是随机存储的，不支持立即访问任意一个随机数据。

循环单项链表

所谓的循环，指得是将链表末尾节点的后继指针指向头结点。比如，单向链表变成循环链表的示意图如下所示：
在这里插入图片描述
循环链表的操作跟普通链表操作基本上是一致的，只要针对循环特性稍作修改即可

singleCList.h

#ifndef _SINGLECLIST_H
#define _SINGCLIST_H#include <stdio.h>
#include <stdlib.h>
#include <string.h>typedef int DATA;/*** 节点结构体*/
typedef struct node
{DATA    data;//节点数据struct node *next;//指向下一个同类节点的指针
}NODE;/*** 链表创建* @param head 指向头指针变量的地址，用来接收首节点地址* @param data 节点数据*/
int sclist_create(NODE** head, DATA data);/*** 检测头结点是否存在* @param head 指向头指针变量的地址，用来接收首节点地址*/
NODE* sclist_findtail(const NODE* head);/*** 向链表插入一个节点数据data* @param head 指向头指针变量的地址，用来接收首节点地址* @param data 节点数据*/
int sclist_insert(NODE** head,DATA data);/*** 查找链表数据data* @param head 指向头指针变量的地址，用来接收首节点地址* @param data 节点数据*/
NODE* sclist_find(const NODE* head,DATA data);/*** 更新链表数据old位newdata* @param head 指向头指针变量的地址，用来接收首节点地址* @param old 需要修改的节点数据* @param newdata 节点新数据*/
int sclist_update(const NODE* head,DATA old,DATA newdata);/*** 遍历链表数据* @param head 指向头指针变量的地址，用来接收首节点地址*/
int sclist_showAll(const NODE* head);/*** 链表数据的删除（其实就是将节点从链表剔除掉）* @param head 指向头指针变量的地址，用来接收首节点地址* @param data 需要删除节点的数据*/
int sclist_delete(NODE** head,DATA data);/*** 回收链表* @param head 指向头指针变量的地址，用来接收首节点地址*/
void sclist_destroy(NODE** head);#endif

singleCList.c

#include "singleCList.h"/*** 链表创建* @param head 指向头指针变量的地址，用来接收首节点地址* @param data 节点数据*/
int sclist_create(NODE **head, DATA data)
{//如果链表已存在，就返回if(*head)return -1;//创建一个新节点NODE *p = (NODE*)malloc(sizeof(NODE));if(!p)return -1;//初始化p->data = data;p->next = p;//因为是循环链表，所以这里的next需要指向自身//此时链表中，没有节点，需要将刚刚创建的节点作为链表的头节点*head = p;return 0;
}/*** 检测头结点是否存在* @param head 指向头指针变量的地址，用来接收首节点地址*/
NODE* sclist_findtail(const NODE* head)
{const NODE *p = head, *q = NULL;//循环遍历while(p){q = p;p = p->next;//判断是否转了一圈if(p == head)break;}return (NODE*)q;
}/*** 向链表插入一个节点数据data* @param head 指向头指针变量的地址，用来接收首节点地址* @param data 节点数据*/
int sclist_insert(NODE** head,DATA data)
{//查找尾节点NODE *tail = sclist_findtail(*head);//情景1：空链表if(!tail){return sclist_create(head,data);}//创建一个新节点NODE *pNew = (NODE*)malloc(sizeof(NODE));if(!pNew)return -1;//初始化pNew->data = data;pNew->next = *head;tail->next = pNew;
}/*** 查找链表数据data* @param head 指向头指针变量的地址，用来接收首节点地址* @param data 节点数据*/NODE* sclist_find(const NODE* head,DATA data)
{const NODE *p = head;//循环遍历while(p){if(memcmp(&(p->data),&data,sizeof(DATA)) == 0)return (NODE*)p;//改变指向p = p->next;//判断是否转了一圈if(p == head)break;}return NULL;
}/*** 更新链表数据old位newdata* @param head 指向头指针变量的地址，用来接收首节点地址* @param old 需要修改的节点数据* @param newdata 节点新数据*/
int sclist_update(const NODE* head,DATA old,DATA newdata)
{NODE *p = NULL;if(!(p = sclist_find(head,old)))return -1;//更新数据p->data = newdata;return 0;
}/*** 遍历链表数据* @param head 指向头指针变量的地址，用来接收首节点地址*/
int sclist_showAll(const NODE* head)
{const NODE *p = head;while(p){printf("%d\t",p->data);p = p->next;//循环链表，一定考虑循环的出口，不然会造成死循环if(p == head)break;}printf("\n");
}/*** 链表数据的删除（其实就是将节点从链表剔除掉）* @param head 指向头指针变量的地址，用来接收首节点地址* @param data 需要删除节点的数据*/
int sclist_delete(NODE** head,DATA data)
{NODE *p = *head, *q = NULL;//情景1:空链表if(!p)return -1;//查询尾节点NODE *tail = sclist_findtail(*head);if(memcmp(&(p->data),&data,sizeof(DATA)) == 0){//情景2:查询到的节点正好是头节点，同时头尾是同一个节点(链表只有一个节点)if(*head == tail){*head = NULL;free(p);return 0;}//情景3:查询到的节点正好是头节点，但是头尾不是同一个节点，就执行头删除法(链表有两个或以上节点))tail->next = (*head)->next;//如果剔除掉头节点,需要指定新的头节点*head = p->next;free(p);return 0;}//情景4:查询到的节点非头节点，同时链表中有多个节点while(p){if(memcmp(&(p->data),&data,sizeof(DATA)) == 00){q->next = p->next;free(p);return 0;}//改变指针q = p;p = p->next;//循环链表，需要考虑出口，否则会死循环if(p == *head)break;}return -1;
}/*** 回收链表* @param head 指向头指针变量的地址，用来接收首节点地址*/
void sclist_destroy(NODE** head)
{//情景1:空链表NODE* tail = sclist_findtail(*head);if(!tail)return ;tail->next = NULL;NODE* p = *head,*q = NULL;while(p){q = p;p = p->next;free(q);}*head = NULL;//头节点置空
}

app.c

#include "singleCList.h"int main(int argc, char const *argv[])
{NODE *head = NULL;// 创建链表sclist_create(&head, 111);// 向链表插入数据sclist_insert(&head, 222);sclist_insert(&head, 333);sclist_insert(&head, 444);// 遍历链表sclist_showAll(head);// 更新链表sclist_update(head, 333, 3333);// 遍历链表sclist_showAll(head);// 删除节点数据sclist_delete(&head, 444);// 遍历链表sclist_showAll(head);// 回收链表sclist_destroy(&head);return 0;
}

在这里插入图片描述