C语言链表算法演示

C语言链表算法演示

摘要: 链表(Linked list)是一种常见的基础数据结构,是一种线性表,但是并不会按线性的顺序存储数据,而是在每一个节点里存到下一个节点的指针)(Pointer)。由于不必须按顺序存储,链表在插入的时候可以达到O(1)的复杂度,比另一种线性表顺序表快得多,但是查找一个节点或者访问特定编号的节点则需要O(n)的时间,而顺序表相应的时间复杂度分别是O(logn)和O(1)。

使用链表结构可以克服数组链表需要预先知道数据大小的缺点,链表结构可以充分利用计算机内存空间,实现灵活的内存动态管理。但是链表失去了数组随机读取的优点,同时链表由于增加了结点的指针域,空间开销比较大。


1 链表基本概念

1.1 链表定义

​ 链表是一种常见的动态进行存储分配的数据结构。

1.2 链表背景

1.2.1 产生原因

1.C语言中使用数组存放数据时,须先定义固定数组长度,确定元素个数。如果数据超过其容量就会发生数组溢出;为防止该溢出,往往会定义很大的数组,但这样又造成资源空间浪费。如果程序采用动态数组方法复制增长的数据,方法可行但效率太低;

2.如果在数组中需要删除一个数据或插入一个数据时,此时需要将删除或插入点数组后面的数据依次移动,这样的移动也会导致程序效率非常低。

1.2.2 基础定义

结点是链表的基本存储单位,在链表中所有元素都存储在一个具有相同数据结构的结点中。一个结点对应一组数据元素,每个结点在内存中使用一块连续的存储空间(一个结点可由多种数据域组成),每个结点之间使用不连续的存储空间,结点之间通过指针链接。结点由数据域指针域/链组成。常用定义如下:

struct node
{
    dadatype data;         //数据域
    struct node *next;     //指针域:指向node结点指针
};

1.2.3 基本构成

链表一般由三部分组成:

1.表头指针:指向链表头结点的指针,头指针是链表的标志,通常用head定义头指针;

2.表头结点:链表的第一个结点,一般不保存数据信息,链表中可没有表头结点(后面讲述),它是为方便引入结点。

3.数据结点:实际保存数据信息的结点。示意图如下:

链表

上图还给出这样一层含义,链表中的各节点在内存的存储地址不是连续的,其各节点的地址是在需要时向系统申请分配的,系统根据内存的当前情况,既可以连续分配地址,也可以跳跃式分配地址。

1.2.4 链表形式

  • 有表头结点的单向链表
  • 无表头结点的单向链表
  • 有表头的单向循环表
  • 无表头的单向循环表

其中有表头与无表头的差别在于是否有表头结点,插入删除操作对应不同的判断;单向链表与单向循环链表的区别在于最后一个数据结点指针是NULL还是指向表头结点。双向链表即两个指针分别指向前一个位置和后一个位置的链表。

1.2.5 常见操作

链表的常见操作包括以下五种:

  • 建立链表
  • 遍历链表
  • 求链表表长
  • 插入数据
  • 删除结点

1.3 预备知识

1.3.1 typedef和结构体用法

1.typedef基础用法

typedef long byte_4; 

​ 给已知数据类型long起个新名字,叫byte_4。

2.typedef与结构结合使用

 typedef struct tagMyStruct 
  { 
          int iNum; 
          long lLength; 
  } MyStruct; 

这语句实际上完成两个操作:

  • 定义一个新的结构类型
 struct tagMyStruct 
  { 
          int iNum; 
          long lLength; 
  }; 

tagMyStruct称为“tag”,即“标签”,实际上是一个临时名字,struct 关键字和tagMyStruct一起,构成了这个结构类型,不论是否有typedef,这个结构都存在。

  我们可以用struct tagMyStruct varName来定义变量,但要注意,使用tagMyStruct varName来定义变量是不对的,因为structtagMyStruct合在一起才能表示一个结构类型。

  • typedef为这个新的结构起了一个名字,叫MyStruct。
  typedef struct tagMyStruct MyStruct; 

  因此,MyStruct实际上相当于struct tagMyStruct,我们可以使用MyStruct varName来定义变量。
3.typedef规范做法:

 struct tagNode 
  { 
          char *pItem; 
          struct tagNode *pNext; 
  }; 
  typedef struct tagNode *pNode; 

2 链表的优缺点

优点:可动态添加删除;大小可变;

缺点:只能通过顺次指针访问,查询效率低。

补充:

​ 顺序表的优点:查找方便,适合随机查找 :

​ 顺序表的缺点:插入、删除操作不方便,因为插入、删除操作会导致大量元素的移动。

​ 链接表的优点:插入、删除操作方便,不会导致元素的移动,因为元素增减,只需要调整指针。

​ 顺序表的缺点:查找方便,不适合随机查找。


3 案例分析

3.1 单链表的建立

例:

typedef struct list_node
{
     int data; //数据域,用于存储数据
     struct list_node *next; //指针域,指针,可以用来访问节点数据,也可以遍历,指向下一个节点
}list_single;

在链表节点的定义中,除一个整型成员外,成员next是指向与节点类型完全相同的指针。

在链表节点的数据结构中,非常特殊的一点就是结构体内的指针域的数据类型使用了未定义成功的数据类型。这是在C中唯一规定可以先使用后定义的数据结构。

定义好了链表的结构之后,只要在程序运行的时候数据域中存储适当的数据,如有后继结点,则把链域指向其直接后继,若没有,则置为NULL

3.2 链表的创建、输出步骤

单链表的创建过程有以下几步:

  1. 定义链表的数据结构;
  2. 创建一个空表;
  3. 利用malloc ( )函数向系统申请分配一个节点;
  4. 将新节点的指针成员赋值为空。若是空表,将新节点连接到表头(NULL);若是非空表,将新节点接到表尾;
  5. 判断一下是否有后续节点要接入链表,若有转到3,否则结束;

将上面的创建过程用函数来实现如下:

struct list *create_node(int data) ;
如何创建单链表的节点,主要分以下步骤:
(1)给当前的每个节点的数据结构配置定量的空间大小
   ep : struct list *node = malloc(sizeof(struct list));
(2)清节点数据(由于结构体变量在未初始化的时候,数据是脏的)
   ep : memset(node,0,sizeof(struct list));
(3)给节点初始化数据
   ep : node->id = data ; 
(4)将该节点的指针域设置为NULL
   ep : node->next = NULL ;

单链表的输出过程有以下几步(函数实现略,读者可自己尝试编写):

  1. 找到表头;
  2. 若是非空表,输出节点的值成员(数据成员),是空表则退出;
  3. 跟踪链表的增长,即找到下一个节点的地址;
  4. 转到2.

例:

1.创建一个链表中的一个节点,为了好看,我们把创建节点封装成函数,以后想创建多少个节点,我们就可以反复调用一个函数来创建:

//创建一个链表中的一个节点
list_single *create_list_node(int data)
{
    list_single *node = NULL ; //2、首先,当然是定义一个头指针 、第一步定义数据结构见上
    node = (list_single *)malloc(sizeof(list_single));//3、然后分配内存空间
    if(node == NULL){
        printf("malloc fair!\n"); //若为空,分配失败
    }
    memset(node,0,sizeof(list_single)); //4、清一下,注意要包含string头文件。将list_single中的成员全都初始化为0
    node->data = 100 ; //5、给链表节点的数据赋值
    node->next = NULL ; //6、链表的指针域指向空
    return node ;
}

2.链表的输出就很简单了,大致可以如下使用

list_single *node_ptr = create_list_node(data); //创建一个节点
    printf("node_ptr->data=%d\n",node_ptr->data);   //打印节点里的数据
    printf("node_ptr->next=%d\n",node_ptr->next);  

3.整个程序如下:

#include <stdio.h>
#include <stdlib.h> //包含malloc函数
#include <string.h> //包含memset函数
struct  list_node
{
    int data ; 
    struct list_node *next ;
};

typedef struct list_node list_single ;     
list_single *create_list_node(int data)
{
    list_single *node = NULL ;
    node = (list_single *)malloc(sizeof(list_single));
    if(node == NULL){
        printf("malloc fair!\n");
    }
    memset(node,0,sizeof(list_single));
    node->data = data;
    node->next = NULL ;
    return node ;
}
int main(void)
{
    int data = 100 ;
    list_single *node_ptr = create_list_node(data); //创建一个节点
    printf("node_ptr->data=%d\n",node_ptr->data);   //打印节点里的数据
    printf("node_ptr->next=%d\n",node_ptr->next);  
    free(node_ptr); //注意只能释放一次
    return 0 ;
}

3.3 单链表的尾插

由上面的描述我们可以得到单链表的模型如下图:

链表2

只要实现:

header->next = new 

链表三

双向链表尾插节点的函数可以定义如下:

void double_list_tail_insert(struct double_list *header, struct double_list *new) ;

尾插的步骤:

(1)获取当前节点的位置,也就是访问头节点
   ep : 
   struct list *p = header ;
(2)判断是否为最后一个节点,如果不是,移动到下一个节点,如果是,将数据插入尾部。
   ep : 
   while(NULL != p->next) p = p->next ;
        p->next = new ;

3.4 单链表的头插

链表四

很好理解,头插就是把新的节点插在原来的节点和原来节点的下一个节点之间的一个节点。如图,新的节点插在头节点和节点1。
所以可以推出头插流程如下:

(1)获取当前节点的位置,也就是访问头节点
    ep : struct list *p = header ;
(2)新的节点的下一个节点设置为原来头节点的下一个节点(第一个节点)
    ep : new->next = p->next ;
(3)原来的头节点的下一个节点设置为现在新插入的头节点
    ep : p->next = new ;

3.5 单链表的遍历

如图为一条单向链表的模型,看图知道该链表由头节点和若干个节点组成,最后一个节点(尾节点)为NULL

遍历节点函数原型可定义如下:

void Print_nod(struct list * pH)

链表五

从图中可以得出信息,如果我们要打印出各个节点的数据,要考虑以下问题:

  • 需要打印头节点吗?(头节点肯定是不用打印的,因为这是我们为了操作方便而设置的一个节点)。
  • 这条链表有多少个节点我们怎么知道?(通过判断该链表是否已经到达了尾节点,标志就是NULL)

那么可以得到流程如下:

(1)获取当前节点的位置,也就是访问头节点
    ep : struct list *p = header ;
(2)由于头节点我们不需要去打印它,这时候,初始化打印的节点需要从第一个节点开始。
    ep : p = p->next ;  
(3)判断是否为最后一个节点,如果不是,先打印第一个节点的数据(1),然后移动到下一个节点(2),重复这两个步骤。
   如果是最后一个节点,直接打印数据即可。
    while(NULL != p->next)
    {    printf("node:%d\n",p->data) ; 
         p = p->next ;}
        printf("node:%d\n",p->data);
   当然还可以一句代码解决,这样就达到了先偏移,后取数据。
    while(NULL != p->next){ p = p->next ;                              printf("node:%d\n",p->data) ; }

3.6 单链表的删除

删除节点的函数原型可定义如下:

int detele_list_node(struct list *pH , int data);

单向链表的删除要考虑两种情况,一种是普通节点的删除(当然,头节点不能算)
还有一种是尾节点的前一个节点的删除情况注意,删除完节点还需要释放对应节点的内存空间。

链表六

例:普通节点的删除

定义两个数据结构:prev为当前节点的上一个节点,p表示当前节点。

如果找到数据是节点一的数据,将节点一的数据指向节点一的下一个节点,然后释放节点一的内存空间,这样就需要有一个指针来保存节点一的前一个节点。

if(p->id == data)
{
​    prev->next = p->next;free(p);
}

例:考虑尾节点的下一个节点为NULL的节点删除

链表七

定义两个数据结构:prev为当前节点的上一个节点,p表示当前节点。如果找到数据是节点三的数据,将节点三的上一个节点指向NULL,然后释放节点三的内存空间。

if(p->id == data)
{if(p->next == NULL)
{    
​    prev->next = NULL;free(p);
}
}

删除节点的设计流程:

(1)先定义两个指针,一个表示当前的节点,另一个表示当前节点的上一个节点。

ep : struct list *p = header ;  //当前节点
     struct list *prev = NULL ; //当前节点的上一个节点

(2)遍历整个链表,同时保存当前节点的前一个节点

ep : while(NULL != p->next)
        { 
          //保存了当前的节点的前一个节点
          prev = p ;  
          //保存当前偏移的节点
          p = p->next ; 
          return 0 ;
        }

(3)在遍历的过程中查找要删除的数据

ep : while(NULL != p->next){//保存了当前的节点的前一个节点
​          prev = p ;//保存当前偏移的节点
​          p = p->next ;//查找到了数据if(p->id == data){
          }return 0 ;}


(4)查找到了数据后,分两种情况删除

ep : 普通节点的删除
​        if(p->id == data){
​            prev->next = p->next ;free(p);}
ep : 考虑尾节点的下一个节点为NULL的节点删除
​        if(p->id == data){if(p->next == NULL){
​                prev->next = NULL ;free(p);}
        }


3.7 单链表的逆序

逆序操作的函数原型可定义如下:

链表八

void trave_list(L * pH)

逆序步骤:

(1)设置两个指针,一个保存当前的第一个节点的位置,一个表示链表的第一个有效节点

ep:
//保存当前第一个节点的位置
struct list * p  = pH->next;
//表示链表的第一个有效节点
struct list * pBack; 

(2)当链表没有有效节点或者只有一个有效节点的时候,不做任何操作。

链表九

ep:
if (p == NULL || p->next == NULL)也就是上面的这种情况
    return;

(3)遍历链表

1).保存第一个节点的下一个节点的地址

ep:pBack = p_>next;

2).对第一个有效节点做特殊处理,也就是把第一个有效节点放到末尾。

ep:if (p == pH->next)
    p->next = NULL;

3).如果不是第一个有效节点,则进行头插操作,把当前的节点当做一个新的节点:

链表十

ep:
p->next = pH->next; //尾部连接
pH->NEXT = P;         //头部连接 

4).继续走下一个节点

p = pBack;     //走下一个节点

(4)手动插入最后一个节点

top_insert(pH, p);    //插入最后一个节点

流程咱们基本搞懂了,下面写一个程序,这将会变得非常非常的简单。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct slist
{
    int id ;
    struct slist *next ;            
}L;

//创建一个节点 
L *create_node(int data)
{
    //给每个节点分配结构体一样的空间大小 
    L *p = malloc(sizeof(L));
    if(NULL == p)
    {
        printf("malloc error!\n");
        return NULL ;
    }
    //由于结构体在未初始化的时候一样是脏数据,所以要清 
    memset(p,0,sizeof(L));
    //初始化第一个节点 
    p->id = data ; 
    //将节点的后继指针设置为NULL 
    p->next = NULL ;
}

//链表的尾插 
void tail_insert(L *pH , L *new)
{
    //获取当前的位置 
    L *p = pH ; 
    //如果当前位置的下一个节点不为空 
    while(NULL != p->next)
    {
        //移动到下一个节点 
        p = p->next ;
    }
    //如果跳出以上循环,所以已经到了NULL的这个位置
    //此时直接把新插入的节点赋值给NULL这个位置 
    p->next = new ;
}

//链表的头插 
void top_insert(L *pH , L *new)
{
    L *p = pH ;
    new->next = p->next ;
    p->next = new ;
}

//链表的遍历 
void Print_node(L *pH)
{
    //获取当前的位置 
    L *p = pH ;
    //获取第一个节点的位置 
    p = p->next ;
    //如果当前位置的下一个节点不为空 
    while(NULL != p->next)
    {
        //(1)打印节点的数据 
        printf("id:%d\n",p->id);
        //(2)移动到下一个节点,如果条件仍为真,则重复(1),再(2) 
        p = p->next ;
    }
    //如果当前位置的下一个节点为空,则打印数据
    //说明只有一个节点 
    printf("id:%d\n",p->id);
}

//删除链表中的节点 
int detele_list_node(L * pH , int data)
{
    //获取当前头节点的位置 
    L *p = pH ;
    L *prev = NULL;
    while(NULL != p->next)
    {
        //保存当前节点的前一个节点的指针 
        prev = p ;
        //然后让当前的指针继续往后移动 
        p = p->next ;     
        //判断,找到了要删除的数据  
        if(p->id == data)
        {
            //两种情况,一种是普通节点,还有一种是尾节点
            if(p->next != NULL)  //普通节点的情况 
            {
                prev->next = p->next ;
                free(p);
            }
            else //尾节点的情况 
            {
                prev->next = NULL ; //将这个尾节点的上一个节点的指针域指向空 
                free(p); 
            }
            return 0  ;
        }
    }
    printf("没有要删除的节点\n");
    return -1 ;
}

void trave_list(L * pH)
{
    //保存第一个节点的位置 
    L *p = pH->next;
    L *pBack;
    int i = 0 ;
    if(p->next == NULL || p == NULL)
        return ;

    while(NULL != p->next) //遍历链表 
    {
        //保存第一个节点的下一个节点 
        pBack = p->next ; 
        //找到第一个有效节点,其实就是头指针的下一个节点 
        if(p == pH->next) 
        {
            //第一个有效节点就是最后一个节点,所以要指向NULL 
            p->next = NULL ; 
        } 
        else
        {
            /*
            new->next = p->next ;
            p->next = new ;
            */
            p->next = pH->next ; //尾部连接 
        }
        pH->next = p ; //头部连接 
        p = pBack ; //走下一个节点 
    }
    top_insert(pH,p); //插入最后一个节点 
}

int main(int argc , char **argv) 
{
    //创建第一个节点 
    int i ;
    L *header = create_node(0); 
    for(i = 1 ; i < 10 ; i++)
    {
        tail_insert(header,create_node(i));
    }
    Print_node(header);
    detele_list_node(header,5);
    putchar('\n');
    Print_node(header);
    putchar('\n');
    trave_list(header);
    Print_node(header);
    return 0 ;
}

转载请注明: Jning C语言链表算法演示

本篇
C语言链表算法演示 C语言链表算法演示
C语言链表算法演示 摘要: 链表(Linked list)是一种常见的基础数据结构,是一种线性表,但是并不会按线性的顺序存储数据,而是在每一个节点里存到下一个节点的指针)(Pointer)。由于不必须按顺序存储,链表在插入的时候可以达到O(
2018-11-03
下一篇
C语言动态数组分配算法演示 C语言动态数组分配算法演示
C动态数组算法演示 摘要:数据结构和算法对于编程的意义不言而喻,具有指导意义的。无论从事算法优化方向研究,还是大数据处理,亦或者网站开发APP开发云云。在求职过程中数据结构必然也是笔试的重点,面试的常客。基于此,系统梳理复习下数据结构和算法
2018-11-03