C语言基础---链表

版权声明：本文为小斑马伟原创文章，转载请注明出处！
一、数组的缺陷
数组的缺陷1:静态空间，一旦分配内存后，不可以动态扩展。如果分配少了，可能不够用，如果分配多了，可能造成浪费。
数组缺陷2：对头部删除和插入、效率很低。因为头部数据插入和删除，要移动数据。
二、链表的基本概念
链表的组成:链表是由节点组成的，节点由数据域和指针域组成。
链表的分类：方式1：静态链表 动态链表 方式2：单向链表 双向链表 单向循环链表和双向循环链表。

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

//1.静态链表

//节点的声明
struct LinkNode
{
    int num; //数据域
    struct LinkNode* next; //指针域
};

void test01() 
{
   //创建节点
   struct LinkNode node1 = { 10, NULL };
   struct LinkNode node2 = { 20, NULL };
   struct LinkNode node3 = { 30, NULL };
   struct LinkNode node4 = { 40, NULL };
   struct LinkNode node5 = { 50, NULL };

      //建立关系
   node1.next = &node2;
   node2.next = &node3;
   node3.next = &node4;
   node4.next = &node5;
   node5.next = NULL;

   //如何遍历这个链表

   //创建一个指针 指向第一个节点
   struct LinkNode* pCurrent = &node1;

   while (pCurrent != NULL) {
       printf("%d\n", pCurrent->num);

       pCurrent = pCurrent->next;
   }

}

//动态链表
void test2() {
    struct LinkNode* node1 = malloc(sizeof(struct LinkNode));
    struct LinkNode* node2 = malloc(sizeof(struct LinkNode));
    struct LinkNode* node3 = malloc(sizeof(struct LinkNode));
    struct LinkNode* node4 = malloc(sizeof(struct LinkNode));
    struct LinkNode* node5 = malloc(sizeof(struct LinkNode));

    node1->num = 10;
    node2->num = 30;
    node3->num = 50;
    node4->num = 70;
    node5->num = 90;

 //建立关系
    node1->next = node2;
    node2->next = node3;
    node3->next = node4;
    node4->next = node5;
    node5->next = NULL;

//遍历链表
   struct LinkNode* pCurrent = node1;
   while (pCurrent != NULL) {
       printf("%d\n", pCurrent->num);

       pCurrent = pCurrent->next;
    }

}

int main() {
    test01();
    printf("\n");
    test2();
    system("pause");
    return EXIT_SUCCESS;

}

静态链表 创建在栈上 动态链表 创建在堆上
三、带头和不带头的链表
带头节点链表：固定一个节点作为头结点（数据域不保存有效数据），起一个标志位的作用，以后不管链表节点如何改变，此头节点固定不变。

不带节点的链表：头节点不固定，根据实际需要交换头节点（如在原来头节点前插入新节点，然后，新节点重新作为链表的头节点）。