博客

一.链表的引入

1.链表是怎么来的？

在了解链表的来路之前，需要知道数组的缺陷，数组主要有两个缺陷：

①数组中所有元素类型必须相同

②数组在定义时必须明确指定数组元素的个数，且个数一般来说是不可改的。

==如果希望数组的大小能够实时扩展。怎么解决那？==

譬如我刚开始定了一个元素个数是10，后来程序运行时觉得不够因此动态扩展为20.普通的数组显然不行，我们可以对数组进行封装以达到这种目的；如下图

我们还可以使用一个新的数据结构来解决，这个新的数据结构就是链表。

即采用化整为零的思路，在原来不同的情况下，去外部扩展新的分基地（即新的内存空间），然后通过连接两个内存空间的这种方法，即为链表。

可类比大学建立新分校区。而上面那种数组封装的方式就是一个老校区卖掉，再去简历一个新校区，这样，损失的就是效率。

==最后，我们就知道了链表出现的初衷就是为了解决数组大小不能实时扩展的问题。所以链表也可以当作数组理解，作用都是用来存储数据的==

2.链表的组成结构

链表是由若干个节点组成的（链表的各个节点结构是完全类似的），节点是由有效数据和指针组成的。有效数据区域用来存储信息完成任务的，指针区域用于指向链表的下一个节点从而构成链表。

二.单链表的实现

单链表的形象理解如下

链表是由节点组成的，节点中包含：有效数据和指针两部分；

由上图可知，我们来构建一个简单的单链表，则需要以下几步：

①==定义头指针==

②==创建第一个节点，并将头指针指向第一个节==点

③==接着创建节点，并将新创建的节点从前一个节点的尾部插入进来==。

④==依次类推，最终形成上图的链表。==

程序分步骤的实现如下

==1.实现一个链表的首要任务就是构造节点，在c语言中构构造节点的方法就是定义一个结构体：==

// 构建一个链表的节点
struct node
{
    int data;   // 有效数据
    struct node *pNext; // 指向下一个节点的指针
};

==2.使用堆内存创建一个节点==

因为链表的内存要求比较灵活，不能用栈，也不能用data数据段。只能用堆内存

创建节点的过程：

①==申请一个节点大小的堆内存==

②==检查堆内存是否申请成功==

③==清理申请到的堆内存==

④==填充节点中的数据==

⑤==节点中的指针域初始化为NULL；==

代码的具体实现

**// 作用：创建一个链表节点
// 返回值：指针，指针指向我们本函数新创建的一个节点的首地址
struct node * create_node(int data)
{
    struct node *p = (struct node *)malloc(sizeof(struct node));
    if (NULL == p)
    {
        printf("malloc error.\n");
        return NULL;
    }
    // 清理申请到的堆内存
    bzero(p, sizeof(struct node));
    // 填充节点
    p->data = data;
    p->pNext = NULL;    
      //将来用来指向下一个节点的首地址，这里没有下一个节点，故初始化为NULL
    return p; //返回值，是刚创建的节点的首地址的指针**
}

==3.构造一个简单的链表（只含一个节点的链表）==

具体构造的过程：这里只有一个节点，依次类推，只需要后面添加新的节点单链表就形成链表了

/***构建一个简单的单链表，对main1中创建节点，关联节点的方法进行封装********/
int main2(void)
{
    // 定义头指针
     struct node *pHeader=NULL;

         pHeader = create_node(1);  
    // 将本节点和它前面的头指针关联起来     
}

三.单链表的实现之从尾部插入节点

==#### 思考下面图中的问题？如何将多个节点连接在链表的后面？==

我们可以通过在链表尾部插入节点的方法实现

尾部插入节点的任务分析：

思路：将从链表尾部插入节点的任务分为两步：

①==找到链表的最后一个节点==

②==将新的节点和原来的最后一个节点连接起来==

代码具体实现：

/**思路：将从链表尾部插入节点的任务分为两步：
①找到链表的最后一个节点
②将新的节点和原来的最后一个节点连接起来
参数：struct node *ph：链表的头指针ph
      struct node *new：插入新节点的首地址new
思路：由头指针向后遍历，直到走到原来的最后一个节点。原来最后一个节点里面的pNext是NULL，现在我们只要将它改成new就可以了。添加了之后新节点就变成了最后一个。
**/
void insert_tail(struct node *ph,struct node *new)
{
    struct node *p=ph;
    while(NULL !=p->pNext)//第一步，找到链表的最后一个节点
    {
        p=p->pNext;      //这句话意思是如果没有找到尾节点，就访问下一个节点，直到找到最后一个节点为止，跳出循环
    }

    p->pNext=new;//将新节点的首地址和原来最后一个节点连接起来    
}

/**************单链表的算法之尾部插入节点***********************/
int main3(void)
{
    // 定义头指针
    // struct node *pHeader=NULL;
    //这样令头指针等于NULL，会导致insert_tail函数出错引发段错误。
    //故这样，直接定义一个头指针后创建一个新的节点给予指针初始化
    struct node *pHeader=create_node(1);//注意这样并不是头节点，而是直接赋节点值

     //调用该函数使链表尾部插入新的节点
     insert_tail(pHeader,create_node(2));
     insert_tail(pHeader,create_node(3));
     insert_tail(pHeader,create_node(4));

    // 访问链表第1个节点的有效数据
    printf("node1 data: %d.\n", pHeader->data); 

    // 访问链表第2个节点的有效数据
    printf("node2 data: %d.\n", pHeader->pNext->data);  

    // 访问链表第3个节点的有效数据
    printf("node3 data: %d.\n", pHeader->pNext->pNext->data);   

    // 访问链表第4个节点的有效数据
    printf("node4 data: %d.\n", pHeader->pNext->pNext->pNext->data);    

    return 0;
}

四.单链表的实现之从尾部插入节点引出的头节点问题

1.什么是头节点

(1)问题：因为我们在insert_tail中直接默认了头指针指向的有一个节点，因此如果程序中直接定义了头指针后就直接insert_tail就会报段错误。我们不得不在定义头指针之后先create_node创建一个新节点给头指针初始化，否则不能避免这个错误；但是这样解决让程序看起来逻辑有点不太顺，因为看起来第一个节点和后面的节点的创建、添加方式有点不同。

(2)链表还有另外一种用法，就是把头指针指向的第一个节点作为头节点使用。

头节点的特点是：第一，它紧跟在头指针后面。第二，头节点的数据部分是空的（有时候不是空的，而是存储整个链表的节点数），指针部分指向下一个节点，也就是第一个节点。

(3)这样看来，头节点确实和其他节点不同。我们在创建一个链表时添加节点的方法也不同。头节点在创建头指针时一并创建并且和头指针关联起来；后面的真正的存储数据的节点用节点添加的函数来完成，譬如insert_tail.

代码具体实现：

/**思路：将从链表尾部插入节点的任务分为两步：
①找到链表的最后一个节点
②将新的节点和原来的最后一个节点连接起来
参数：struct node *ph：链表的头指针ph
      struct node *new：插入新节点的首地址new
思路：由头指针向后遍历，直到走到原来的最后一个节点。原来最后一个节点里面的pNext是NULL，现在我们只要将它改成new就可以了。添加了之后新节点就变成了最后一个。
//计算添加了新的节点后总共有多少个节点，然后把这个数写入头节点中
**/
void insert_tail(struct node *ph,struct node *new)
{
    int cnt=0;
    struct node *p=ph;
    while(NULL !=p->pNext)//第一步，找到链表的最后一个节点
    {
        p=p->pNext;      //这句话意思是如果没有找到尾节点，就访问下一个节点，直到找到最后一个节点为止，跳出循环
        cnt++;
    }

    p->pNext=new;//将新节点的首地址和原来最后一个节点连接起来
    ph->data=cnt+1;
}

/**头节点的引入，需要改insert_tail函数****************************/
int main(void)
{
    // 定义一个头节点，用于存链表的节点数
    struct node *pHeader=create_node(0);

     //调用该函数使链表尾部插入新的节点
     insert_tail(pHeader,create_node(1));
     insert_tail(pHeader,create_node(2));
     insert_tail(pHeader,create_node(3));

    // 访问链表头结点的有效数据 
    printf("header node data: %d.\n", pHeader->data);   

    // 访问链表第1个节点的有效数据
    printf("node1 data: %d.\n", pHeader->pNext->data);  

    // 访问链表第2个节点的有效数据
    printf("node2 data: %d.\n", pHeader->pNext->pNext->data);   

    // 访问链表第3个节点的有效数据
    printf("node3 data: %d.\n", pHeader->pNext->pNext->pNext->data);    

    return 0;
}

头指针与头结点的区别：

（参考

http://blog.51cto.com/9291927/1790922

）

==但我们一般在默认链表的算法中都使用头结点。==

所以如果一个链表设计的时候就有头节点那么后面的所有算法都应该这样来处理；如果设计时就没有头节点，那么后面的所有算法都应该按照没有头节点来做

五.单链表的实现之从头部插入节点

头结点插入的重要两个步骤：

==①.新节点的pNext指向原来的第一个节点的首地址，即图中的新节点和原来的第一个节点相连==

==②.头节点的pNext指向新节点的首地址，即图中头结点和新节点相连==

思考:第一步和第二步可不可以交换一下顺序？

==答案显然是不能的，因为由上图可知，步骤②是可以完成的，但是执行步骤①时就会发现，原来的第一个有效节点的地址已经丢失了，由图中知道，我们原来第一个节点的首地址是在头结点的pNext指针中保存的，因为先执行了步骤②，故原来第一个节点的有效地址丢失了。==

代码实现思路：

第1步： 新节点的next指向原来的第一个节点

第2步： 头节点的next指向新节点的地址

第3步： 头节点中的计数要加1

// 思路：单链表之从头部插入节点
void insert_head(struct node *pH, struct node *new)
{
    // 第1步： 新节点的next指向原来的第一个节点
    new->pNext = pH->pNext;

    // 第2步： 头节点的next指向新节点的地址
    pH->pNext = new;

    // 第3步： 头节点中的计数要加1
    pH->data += 1;
}

思考以下：链表可以从头部插入，也可以从尾部插入的输出信息是什么？

/****链表从头部插入，也可以从尾部插入打印对应节点的信息***********/
int main(void)
{
    // 定义一个头节点，用于存链表的节点数
    struct node *pHeader=create_node(0);

     //调用该函数使链表尾部插入新的节点
         insert_head(pHeader,create_node(1));//头部插入
     insert_tail(pHeader,create_node(2));//尾部插入
     insert_head(pHeader,create_node(3));//头部插入

    // 访问链表头结点的有效数据 
    printf("header node data: %d.\n", pHeader->data);   

    // 访问链表第1个节点的有效数据
    printf("node1 data: %d.\n", pHeader->pNext->data);  

    // 访问链表第2个节点的有效数据
    printf("node2 data: %d.\n", pHeader->pNext->pNext->data);   

    // 访问链表第3个节点的有效数据
    printf("node3 data: %d.\n", pHeader->pNext->pNext->pNext->data);    

    return 0;
}

画个图加深影响：一目了然，所以，分析链表时候多画图

故打印结果为3 1 2