C语言至少可以通过两种结构来存储数据。

数组与链表的对比

数组

数组的优点

存取速度快。

数组的缺点

  • 需要一个连续的很多的内存；

  • 插入和删除元素的效率很低。

    链表

    链表的优点

  • 插入和删除元素效率高；

  • 不需要一个连续的很大的内存。

    链表的缺点

    查找某个位置的元素的效率低。

    链表的定义

    链表（浅谈） - 图1
    链表（浅谈） - 图2

    首节点

    链表中第一个有效数据的节点。

    尾结点

    存放最后一个有效数据的节点。其中，下一个数据的指针为NULL（类似于字符串的结束符”\0”）。

    头结点

  • 头结点的数据类型和首节点的数据类型相同；

  • 头结点是首节点的上一个节点；
  • 头结点并不存放有效数据；
  • 设置头结点的目的是为了方便对链表的操作；
  • 头结点不是必须的。

    头指针

    存放头结点地址的指针变量。

    确定一个链表所需的参数

    确定一个链表只需要一个参数，即头指针的地址（尾结点的数据指针为NULL，可判断为结束符）。 ```c 链表示例：

include

struct Node { int data; struct Node pNext; }; int main(void) { struct Node pHead = NULL; //声明一个链表头指针 pHead = create_list(); //头指针指向链表 traverse_list(pHead); //传输链表

  1. return 0;

}

  1. <a name="RDBSw"></a>
  2. ## 创建一个链表
  4. 1. **创建一个头指针；**
  5. 1. **创建一个头结点（可选）；**
  6. 1. **创建多个存储数据的节点（创建过程中要做好逻辑关系）**。
  7. ```c
  8. #include <stdio.h>
  10. #define LIST_LEN 5
  12. struct Node
  13. {
  14.     int data;
  15.     struct Node *pNext;
  16. };
  18. struct Node *create_list(void)
  19. {
  20.     //struct Node *p = NULL;    //创建一个头指针
  21.     //创建一个不存放有效数据的头结点
  22.     struct Node * pHead = (struct Node *)malloc(sizeof(struct Node));
  23.     if(NULL == pHead)    //判断头结点是否创建成功
  24.     {
  25.         printf("链表头结点分配失败\n");
  26.         exit(-1);
  27.     }
  28.     //头指针指向头结点
  29.     //p = pHead;
  30.     struct Node *pTemp = pHead;    //创建一个临时指针指向头结点
  32.     for(int i = 0;i < LIST_LEN;i++)
  33.     {
  34.         //创建一个新的节点
  35.         struct Node * pNew = (struct Node *)malloc(sizeof(struct Node));
  36.         if(NULL == pNew)    //判断新节点是否创建成功
  37.         {
  38.             printf("链表新节点分配失败\n");
  39.             exit(-1);
  40.         }
  41.         //新节点初始化
  42.         pNew->data = i;    //填充链表数据
  43.         pNew->pNext = NULL;    //指针初始化为NULL
  44.         //通过临时指针建立链表逻辑关系
  45.         pTemp->pNext = pNew;    //上一个链表元素的指针指向pNew
  46.         pTemp = pTemp->pNext;    //替换临时指针为当前pNew----pTemp->pNext其实就是上一行代码的pNew
  48.     }
  49.     return pHead;
  50. }

遍历输出一个链表

  1. #include <stdio.h>
  3. struct Node
  4. {
  5.     int data;
  6.     struct Node *pNext;
  7. };
  9. void traverse_list(struct Node *pHead)
  10. {
  11.     struct Node *p = pHead->pNext;    //定义结构体指针，指向下一个数据的指针
  12.     while(NULL != p)    //判断该指针是否为空--空则为链表末位
  13.     {
  14.         printf("%d\n",p->data);    //循环输出链表数据
  15.         p = p->pNext;    //p指向下一个元素的指针
  16.     }
  17. }