一.单链表：

1.1定义：

对于链表来说，总得有个头有个尾，链表也不例外。我们把链表中的第一个结点的存储位置叫做头指针，最后一个结点指针为空(NULL)。
三、单链表 - 图1
头指针
头指针是指链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指针。
头指针具有标识作用，所以常用头指针冠以链表的名字（指针变量的名字）。
无论链表是否为空，头指针均不为空。
头指针是链表的必要元素。

头结点
头结点是为了操作的统一和方便而设立的，放在第一个元素的结点之前，其数据域一般无意义（但也可以用来存放链表的长度）。
有了头结点，对在第一元素结点前插入结点和删除第一结点起操作与其它结点的操作就统一了。
头结点不一定是链表的必须要素。

  1. typedef struct Node
  2. {
  3. ElemType data;      // 数据域
  4. struct Node* Next;  // 指针域
  5. } Node, * LinkList;

1.2 实例

InitList(*L): 初始化操作，建立一个空的链表L。
ListEmpty(L): 判断链表是否为空表，若线性表为空，返回true，否则返回false。
ClearList(*L): 将链表清空。
GetElem(L,i,*e): 将链表L中的第i个位置元素值返回给e。
LocateElem(L,e): 在链表L中查找与给定值e相等的元素，如果查找成功，返回该元素在 表中序号表示成功；否则，返回0表示失败。
ListInsert(*L,i,e): 在链表L中第i个位置插入新元素e。
ListDelete(L,i,e): 删除链表L中第i个位置元素，并用e返回其值。
ListLength(L): 返回链表L的元素个数。

1.3 eg:

list.h

  1. #include<stdio.h>
  2. #include <stdlib.h>
  3. #include<assert.h>
  5. typedef int DataType;
  7. typedef struct ListNode
  8. {
  9.     DataType data;
  10.     struct ListNode* next;
  11. }Node, * LinkList;
  13. LinkList InitList(void);                                    //初始化
  14. LinkList BuyNode(DataType data);                            //创建新结点
  15. void Printflist(LinkList list);                             //打印
  16. void PushFront(LinkList list, DataType data);               //头插   (有头节点的)
  17. void PushBack(LinkList list, DataType data);                //尾插
  18. void PopFront(LinkList list);                               //头删(有头节点的)
  19. void PopBack(LinkList list);                                //尾删
  20. LinkList Find(LinkList plist, DataType data);               //查找
  21. bool GetElem(LinkList list, int pos, DataType* e);          //用e返回L中第pos个数据元素的值
  22. bool ListInsert(LinkList list, int pos, DataType data);     //在L中第pos个位置之前插入新的数据元素e，L的长度加1
  23. void Removelist(LinkList list, DataType data);              //删除第一个指定元素
  24. bool ListDelete(LinkList list, int pos, DataType* e);       //删除第pos个数据元素，并用e返回其值，L的长度-1
  25. void ClearList(LinkList list);                              //释放链表

list.c

  1. #include"list.h"
  3. LinkList InitList(void)//初始化
  4. {
  5.     LinkList list = (LinkList)malloc(sizeof(Node));
  6.     assert(list);
  7.     list->data = 0;
  8.     list->next = NULL;
  9.     return list;
  10. }
  12. LinkList BuyNode(DataType data)//创建新结点
  13. {
  14.     LinkList NewNodelist = (LinkList)malloc(sizeof(Node));
  16.     if (NewNodelist == NULL)
  17.     {
  18.         printf("fail");
  19.         exit(EXIT_FAILURE);
  20.     }
  21.     NewNodelist->data = data;
  22.     NewNodelist->next = NULL;
  23.     return NewNodelist;
  24. }
  26. void Printflist(LinkList list)//打印
  27. {
  28.     LinkList cur = NULL;
  30.     cur = list;
  31.     if (cur == NULL)
  32.     {
  33.         printf("list is mepty");
  34.     }
  35.     else
  36.     {
  37.         while (cur)
  38.         {
  39.             printf("%d->", cur->data);
  40.             cur = cur->next;
  41.         }
  42.         printf("over \n");
  43.     }
  44. }
  46. void PushFront(LinkList list, DataType data)//头插   (有头节点的)
  47. {
  48.     LinkList NewNodelist = BuyNode(data);
  49.     NewNodelist->next = list->next;
  50.     list->next = NewNodelist;
  51. }
  52. void PushBack(LinkList list, DataType data)//尾插
  53. {
  54.     assert(list);
  55.     LinkList NewNode = NULL;
  56.     NewNode = BuyNode(data);
  57.     while (list->next)
  58.     {
  59.         list = list->next;
  60.     }
  61.     list->next = NewNode;
  62. }
  63. void PopFront(LinkList list)    //头删(有头节点的)
  64. {
  65.     LinkList del = NULL;
  66.     assert(list);
  67.     if (list == NULL)
  68.     {
  69.         printf("list is empty");
  70.         exit(EXIT_FAILURE);
  71.     }
  72.     del = list->next;
  73.     list->next = del->next;
  74.     free(del);
  75.     del = NULL;
  76. }
  77. void PopBack(LinkList list)//尾删
  78. {
  79.     LinkList cur = NULL;
  80.     LinkList prev = NULL;
  81.     assert(list);
  82.     cur = list;
  83.     if (cur == NULL)
  84.     {
  85.         printf("list ic empty");
  86.         exit(EXIT_FAILURE);
  87.     }
  88.     if (cur->next == NULL)//1.只有一个结点
  89.     {
  90.         free(cur);
  91.         cur = NULL;
  92.     }
  93.     else//2.有大于一个的结点
  94.     {
  95.         while (cur->next)
  96.         {
  97.             prev = cur;
  98.             cur = cur->next;
  99.         }
  100.         free(cur);
  101.         prev->next = NULL;
  102.     }
  103. }
  104. LinkList Find(LinkList list, DataType data)//查找某个第一个元素，并返回指向该元素的结点的指针
  105. {
  106.     LinkList cur = list;
  107.     assert(list);
  108.     if (cur == NULL)//1.如果链表为空
  109.     {
  110.         printf("list is empty");
  111.         exit(EXIT_FAILURE);
  112.     }
  113.     while (cur)//2.链表不为空
  114.     {
  115.         if (cur->data == data)
  116.         {
  117.             return cur;
  118.         }
  119.         cur = cur->next;
  120.     }
  121.     printf("no exist");
  122.     return  NULL;
  123. }
  126. /* 初始条件：顺序线性表L已存在，1<=pos<=ListLength(L) */
  127. /* 操作结果：用e返回L中第pos个数据元素的值 */
  128. bool GetElem(LinkList list, int pos, DataType* e)
  129. {
  130.     int j;
  131.     LinkList cur;
  132.     //list为头指针，必不为空，数据为头节点（一般存放数据大小）
  133.     cur = list->next;
  134.     j = 1;
  136.     while (cur && j < pos)
  137.     {
  138.         cur = cur->next;
  139.         ++j;
  140.     }
  142.     if (!cur || j > pos)
  143.     {
  144.         return false;
  145.     }
  147.     *e = cur->data;
  149.     return true;
  150. }
  151. /* 初始条件：顺序线性表L已存在，1<=pos<=ListLength(L) */
  152. /* 操作结果：在L中第pos个位置之前插入新的数据元素e，L的长度加1 */
  153. bool ListInsert(LinkList list, int pos, DataType data)
  154. {
  155.     int j;
  156.     LinkList cur;
  157.     LinkList NewNodelist =  BuyNode(data);
  158.     cur = list;
  159.     j = 1;
  161.     while (cur && j < pos)   // 用于寻找第i个结点
  162.     {
  163.         cur = cur->next;
  164.         j++;
  165.     }
  167.     if (!cur || j > pos)
  168.     {
  169.         return false;
  170.     }
  172.     NewNodelist->next = cur->next;
  173.     cur->next = NewNodelist;
  175.     return true;
  176. }
  177. void Removelist(LinkList list, DataType data)           //删除第一个指定元素
  178. {
  179.     LinkList cur = NULL;
  180.     LinkList prev = NULL;
  181.     LinkList del = NULL;
  182.     assert(list);
  183.     cur = list;
  184.     if (list == NULL)//1.空链表
  185.     {
  186.         printf("list is empty");
  187.         exit(EXIT_FAILURE);
  188.     }
  190.     while (cur)//2.非空链表
  191.     {
  192.         if (cur->data == data)
  193.         {
  194.             if (cur == list)        //2.1删除的结点为第一个结点
  195.             {
  196.                 del = cur;
  197.                 list = cur->next;
  198.                 free(del);
  199.             }
  200.             else                    //2.2删除的不是第一个结点
  201.             {
  202.                 del = cur;
  203.                 prev->next = cur->next;
  204.                 free(del);
  205.             }
  206.             return;
  207.         }
  208.         else
  209.         {
  210.             prev = cur;
  211.             cur = cur->next;
  212.         }
  213.     }
  214. }
  216. /* 初始条件：顺序线性表L已存在，1<=pos<=ListLength(L) */
  217. /* 操作结果：删除L的第pos个数据元素，并用e返回其值，L的长度-1 */
  218. bool ListDelete(LinkList list, int pos, DataType* e)
  219. {
  220.     int j;
  221.     LinkList p, q;
  223.     p =  list;
  224.     j = 1;
  226.     while (p->next && j < pos)
  227.     {
  228.         p = p->next;
  229.         ++j;
  230.     }
  232.     if (!(p->next) || j > pos)
  233.     {
  234.         return false;
  235.     }
  237.     q = p->next;
  238.     p->next = q->next;
  240.     *e = q->data;
  241.     free(q);
  243.     return true;
  244. }
  246. void ClearList(LinkList list)//释放链表
  247. {
  248.     LinkList  cur = list;
  249.     LinkList  del = NULL;
  250.     assert(list);
  251.     while (cur)
  252.     {
  253.         del = cur;
  254.         cur = cur->next;
  255.         free(del);
  256.         del = NULL;
  257.     }
  258.     list = NULL;
  259. }

main.c

  1. #include"list.h"
  3. void Test()
  4. {
  5.     int* e = (int*)malloc(sizeof(int));
  6.     LinkList list = InitList();
  7.     PushBack(list, 1);
  8.     PushBack(list, 2);
  9.     PushBack(list, 3);
  10.     PushBack(list, 4);
  11.     PushBack(list, 5);
  12.     PushBack(list, 6);
  13.     //PopFront(list);
  14.     //PopBack(list);
  15.     ListDelete(list, 1,e);
  16.     assert(e);
  17.     printf_s("返回的元素是%d\r\n",*e);
  18.     Printflist(list);
  19.     free(e);
  20.     e = NULL;
  21. }
  22. int main()
  23. {
  24.     Test();
  26.     system("pause");
  27.     return 0;
  28. }

二、双向链表

1.定义

  1. typedef struct DualNode
  2. {
  3. ElemType data;
  4. struct DualNode *prior;  //前驱结点
  5. struct DualNode *next;   //后继结点
  6. } DualNode, *DuLinkList;

三、单链表 - 图2
既然单链表可以有循环链表，那么双向链表当然也可以有。
三、单链表 - 图3

2.插入操作

其实并不复杂，不过顺序很重要，千万不能写反了。
三、单链表 - 图4
代码实现：

  1. s->next = p;    
  2. s->prior = p->prior;    
  3. p->prior->next = s;    
  4. p->prior = s;

关键在于交换的过程中不要出现矛盾，例如第四步先被执行了，那么p->prior就会提前变成s，使得插入的工作出错。

3.删除操作

三、单链表 - 图5

  1. p->prior->next = p->next;
  2. p->next->prior = p->prior;    
  3. free(p);

三、静态链表

1.静态链表的游标实现法

三、单链表 - 图6

2.静态链表存储结构

  1. #include<stdio.h>
  2. #include <stdlib.h>
  3. #include<assert.h>
  5. #define MAXSIZE 100
  7. typedef struct
  8. {
  9.     int data;          // 数据
  10.     int cur;        // 游标（Cursor）
  11. } Component, StaticLinkList[MAXSIZE];
  14. bool InitList(StaticLinkList space)
  15. {
  16.     int i;
  17.     for (i = 0; i < MAXSIZE - 1; i++)
  18.         space[i].cur = i + 1;
  20.     space[MAXSIZE - 1].cur = 0;
  22.     return true;
  23. }
  25. //首先是获得空闲分量的下标：
  26. int Malloc_SLL(StaticLinkList space)
  27. {
  28.     int i = space[0].cur;
  29.     if (space[0].cur)
  30.         space[0].cur = space[i].cur;
  31.     // 把它的下一个分量用来作为备用。
  32.     return i;
  33. }
  35. /* 在静态链表L中第i个元素之前插入新的数据元素e */
  36. bool ListInsert(StaticLinkList L, int i, int e)
  37. {
  38.     int j, k, a;
  40.     k = MAXSIZE - 1;    // 数组的最后一个元素
  41.     if (i<1 || i>Malloc_SLL(L) + 1)
  42.     {
  43.         return false;
  44.     }
  46.     j = Malloc_SLL(L);
  47.     if (j)
  48.     {
  49.         L[j].data = e;
  50.         for (a = 1; a <= i - 1; a++)
  51.         {
  52.             k = L[k].cur;
  53.         }
  54.         L[j].cur = L[k].cur;
  55.         L[k].cur = j;
  57.         return true;
  58.     }
  60.     return false;
  61. }
  62. /* 删除在L中的第i个数据元素 */
  63. bool ListDelete(StaticLinkList L, int i)
  64. {
  65.     int j, k;
  67.     if (i<1 || i>Malloc_SLL(L))
  68.     {
  69.         return false;
  70.     }
  72.     k = MAXSIZE - 1;
  74.     for (j = 1; j <= i - 1; j++)
  75.     {
  76.         k = L[k].cur;    // k1 = 1, k2 = 5
  77.     }
  79.     j = L[k].cur;        // j = 2
  80.     L[k].cur = L[j].cur;
  82.     Free_SLL(L, j);
  84.     return true;
  85. }
  87. /* 将下标为k的空闲结点回收到备用链表 */
  88. void Free_SLL(StaticLinkList space, int k)
  89. {
  90.     space[k].cur = space[0].cur;
  91.     space[0].cur = k;
  92. }
  94. /* 返回L中数据元素个数 */
  95. int ListLength(StaticLinkList L)
  96. {
  97.     int j = 0;
  98.     int i = L[MAXSIZE - 1].cur;
  99.     while (i)
  100.     {
  101.         i = L[i].cur;
  102.         j++;
  103.     }
  104.     return j;
  105. }
  107. int main()
  108. {
  110.     StaticLinkList space;
  111.     InitList(space);
  114.     system("pause");
  115.     return 0;
  116. }

3.静态链表优缺点总结

优点：
在插入和删除操作时，只需要修改游标，不需要移动元素，从而改进了在顺序存储结构中的插入和删除操作需要移动大量元素的缺点。
缺点：
没有解决连续存储分配（数组）带来的表长难以确定的问题。失去了顺序存储结构随机存取的特性。

总的来说，静态链表其实是为了给没有指针的编程语言设计的一种实现单链表功能的方法。