单向链表

单向链表（又名单链表、线性链表）是链表的一种，其特点是链表的链接方向是单向的，对链表的访问要通过从头部开始，依序往下读取。

数据结构

一个单向链表的节点被分成两个部分。第一个部分保存或者显示关于节点的信息，第二个部分存储下一个节点的地址。单向链表只可向一个方向遍历。

动态单链表（C语言）

单向链表的数据结构可以分为两部分：数据域和指针域，数据域存储数据，指针域指向下一个存储节点的地址。
  1 #include <stdio.h>  2 #include <stdlib.h>  3 #include <conio.h>  4   5 #define Status int  6 #define ElemType int // 以整型為例  7   8 #define OVERFLOW -1  9 #define ERROR 0 10 #define OK 1 11  12 // 線性表的單鏈表存儲结構 13 typedef struct LNode { 14     ElemType data; 15     struct LNode *next; 16 } LNode, *LinkList; 17  18 // 带有头结點的單鏈表的基本操作(12个) 19 void InitList(LinkList *L) { 20     // 操作结果：構造一个空的線性表L 21     *L = (LinkList)malloc(sizeof(struct LNode)); 22     // 產生头结點，並使L指向此头结點 23     if (!*L) // 存儲分配失敗 24         exit(OVERFLOW); 25     (*L)->next = NULL; // 指针域為空 26 } 27  28 void DestroyList(LinkList *L) { 29     // 初始條件：線性表L已存在。操作结果：销毁線性表L 30     LinkList q; 31     while (*L) { 32         q = (*L)->next; 33         free(*L); 34         *L = q; 35     } 36 } 37  38 void ClearList(LinkList L) { // 不改变L 39     // 初始条件：线性表L已存在。操作结果：将L重置为空表 40     LinkList p, q; 41     p = L->next; // p指向第一个结点 42     while (p) { // 没到表尾 43         q = p->next; 44         free(p); 45         p = q; 46     } 47     L->next = NULL; // 头结点指针域为空 48 } 49  50 Status ListEmpty(LinkList L) { 51     // 初始条件：线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE 52     return L->next == NULL; 53 } 54  55 int ListLength(LinkList L) { 56     // 初始条件：线性表L已存在。操作结果：返回L中数据元素个数 57     int i = 0; 58     LinkList p = L->next; // p指向第一个结点 59     while (p) { // 没到表尾 60         i++; 61         p = p->next; 62     } 63     return i; 64 } 65  66 Status GetElem(LinkList L, int i, ElemType *e) { 67     // L为带头结点的单链表的头指针。当第i个元素存在时，其值赋给e并返回OK，否则返回ERROR 68     int j = 1; // j为计数器 69     LinkList p = L->next; // p指向第一个结点 70     while (p && j < i) { // 顺指针向后查找，直到p指向第i个元素或p为空 71         p = p->next; 72         j++; 73     } 74     if (!p || j > i) // 第i个元素不存在 75         return ERROR; 76     *e = p->data; // 取第i个元素 77     return OK; 78 } 79  80 int LocateElem(LinkList L, ElemType e, Status(*compare)(ElemType, ElemType)) { 81     // 初始条件: 线性表L已存在，compare()是数据元素判定函数(满足为1，否则为0) 82     // 操作结果: 返回L中第1个与e满足关系compare()的数据元素的位序 83     // 若这样的数据元素不存在，则返回值为0 84     int i = 0; 85     LinkList p = L->next; 86     while (p) { 87         i++; 88         if (compare(p->data, e)) // 找到这样的数据元素 89             return i; 90         p = p->next; 91     } 92     return 0; 93 } 94  95 Status PriorElem(LinkList L, ElemType cur_e, ElemType *pre_e) { 96     // 初始条件: 线性表L已存在 97     // 操作结果: 若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱， 98     // 返回OK；否则操作失败，pre_e无定义，返回INFEASIBLE 99     LinkList q, p = L->next; // p指向第一个结点100     while (p->next) { // p所指结点有后继101         q = p->next; // q为p的后继102         if (q->data == cur_e) {103             *pre_e = p->data;104             return OK;105         }106         p = q; // p向后移107     }108     return INFEASIBLE;109 }110 111 Status NextElem(LinkList L, ElemType cur_e, ElemType *next_e) {112     // 初始条件：线性表L已存在113     // 操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继，114     // 返回OK;否则操作失败，next_e无定义，返回INFEASIBLE115     LinkList p = L->next; // p指向第一个结点116     while (p->next) { // p所指结点有后继117         if (p->data == cur_e) {118             *next_e = p->next->data;119             return OK;120         }121         p = p->next;122     }123     return INFEASIBLE;124 }125 126 Status ListInsert(LinkList L, int i, ElemType e) {127     // 算法2.9。不改变L128     // 在带头结点的单链线性表L中第i个位置之前插入元素e129     int j = 0;130     LinkList p = L, s;131     while (p && j < i - 1) { // 寻找第i-1个结点132         p = p->next;133         j++;134     }135     if (!p || j > i - 1) // i小于1或者大于表长136         return ERROR;137     s = (LinkList)malloc(sizeof(struct LNode)); // 生成新结点138     s->data = e; // 插入L中139     s->next = p->next;140     p->next = s;141     return OK;142 }143 144 Status ListDelete(LinkList L, int i, ElemType *e) {145     // 算法2.10。不改变L146     // 在带头结点的单链线性表L中，删除第i个元素，并由e返回其值147     int j = 0;148     LinkList p = L, q;149     while (p->next && j < i - 1) { // 寻找第i个结点，并令p指向其前驱结点150         p = p->next;151         j++;152     }153     if (!p->next || j > i - 1) // 删除位置不合理154         return ERROR;155     q = p->next; // 删除并释放结点156     p->next = q->next;157     *e = q->data;158     free(q);159     return OK;160 }161 162 void ListTraverse(LinkList L, void(*vi)(ElemType)) {163     // vi的形参类型为ElemType，与bo2-1.c中相应函数的形参类型ElemType&不同164     // 初始条件：线性表L已存在。操作结果：依次对L的每个数据元素调用函数vi()165     LinkList p = L->next;166     while (p) {167         vi(p->data);168         p = p->next;169     }170     printf("\n");171 }

静态单链表（C语言）

1 // 线性表的静态单链表存储结构  2 #define MAX_SIZE 100 // 链表的最大长度  3 typedef struct {  4     ElemType data; //此處的ElemType可以自由代換（如int/float等）  5     int cur;  6 } component, SLinkList[MAX_SIZE];  7   8 // 一个数组只生成一个静态链表的基本操作(11个)  9 #define DestroyList ClearList // DestroyList()和ClearList()的操作是一样的 10  11 void InitList(SLinkList L) { 12     // 构造一个空的链表L，表头为L的最后一个单元L[MAX_SIZE-1]，其余单元链成 13     // 一个备用链表，表头为L的第一个单元L[0]，“0”表示空指针 14     int i; 15     L[MAX_SIZE - 1].cur = 0; // L的最后一个单元为空链表的表头 16     for (i = 0; i < MAX_SIZE - 2; i++) // 将其余单元链接成以L[0]为表头的备用链表 17         L[i].cur = i + 1; 18     L[MAX_SIZE - 2].cur = 0; 19 } 20  21 void ClearList(SLinkList L) { 22     // 初始条件：线性表L已存在。操作结果：将L重置为空表 23     int i, j, k; 24     i = L[MAX_SIZE - 1].cur; // 链表第一个结点的位置 25     L[MAX_SIZE - 1].cur = 0; // 链表空 26     k = L[0].cur; // 备用链表第一个结点的位置 27     L[0].cur = i; // 把链表的结点连到备用链表的表头 28     while (i) { // 没到链表尾 29         j = i; 30         i = L[i].cur; // 指向下一个元素 31     } 32     L[j].cur = k; // 备用链表的第一个结点接到链表的尾部 33 } 34  35 Status ListEmpty(SLinkList L) { 36     // 若L是空表，返回TRUE；否则返回FALSE 37     if (L[MAX_SIZE - 1].cur == 0) // 若为空表 38         return TRUE; 39     else 40         return FALSE; 41 } 42  43 int ListLength(SLinkList L) { 44     // 返回L中数据元素个数 45     int j = 0, i = L[MAX_SIZE - 1].cur; // i指向第一个元素 46     while (i) { // 没到静态链表尾 47         i = L[i].cur; // 指向下一个元素 48         j++; 49     } 50     return j; 51 } 52  53 Status GetElem(SLinkList L, int i, ElemType *e) { 54     // 用e返回L中第i个元素的值 55     int l, k = MAX_SIZE - 1; // k指向表头序号 56     if (i < 1 || i > ListLength(L)) 57         return ERROR; 58     for (l = 1; l <= i; l++) // 移动到第i个元素处 59         k = L[k].cur; 60     *e = L[k].data; 61     return OK; 62 } 63  64 int LocateElem(SLinkList L, ElemType e) { // 算法2.13(有改动) 65     // 在静态单链线性表L中查找第1个值为e的元素。若找到，则返回它在L中的 66     // 位序，否则返回0。(与其它LocateElem()的定义不同) 67     int i = L[MAX_SIZE - 1].cur; // i指示表中第一个结点 68     while (i && L[i].data != e) // 在表中顺链查找(e不能是字符串) 69         i = L[i].cur; 70     return i; 71 } 72  73 Status PriorElem(SLinkList L, ElemType cur_e, ElemType *pre_e) { 74     // 初始条件：线性表L已存在 75     // 操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱， 76     // 否则操作失败，pre_e无定义 77     int j, i = L[MAX_SIZE - 1].cur; // i指示链表第一个结点的位置 78     do { // 向后移动结点 79         j = i; 80         i = L[i].cur; 81     } while (i && cur_e != L[i].data); 82     if (i) { // 找到该元素 83         *pre_e = L[j].data; 84         return OK; 85     } 86     return ERROR; 87 } 88  89 Status NextElem(SLinkList L, ElemType cur_e, ElemType *next_e) { 90     // 初始条件：线性表L已存在 91     // 操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继 92     // 否则操作失败，next_e无定义 93     int j, i = LocateElem(L, cur_e); // 在L中查找第一个值为cur_e的元素的位置 94     if (i) { // L中存在元素cur_e 95         j = L[i].cur; // cur_e的后继的位置 96         if (j) { // cur_e有后继 97             *next_e = L[j].data; 98             return OK; // cur_e元素有后继 99         }100     }101     return ERROR; // L不存在cur_e元素，cur_e元素无后继102 }103 104 Status ListInsert(SLinkList L, int i, ElemType e) {105     // 在L中第i个元素之前插入新的数据元素e106     int l, j, k = MAX_SIZE - 1; // k指向表头107     if (i < 1 || i > ListLength(L) + 1)108         return ERROR;109     j = Malloc(L); // 申请新单元110     if (j) { // 申请成功111         L[j].data = e; // 赋值给新单元112         for (l = 1; l < i; l++) // 移动i-1个元素113             k = L[k].cur;114         L[j].cur = L[k].cur;115         L[k].cur = j;116         return OK;117     }118     return ERROR;119 }120 121 Status ListDelete(SLinkList L, int i, ElemType *e) {122     // 删除在L中第i个数据元素e，并返回其值123     int j, k = MAX_SIZE - 1; // k指向表头124     if (i < 1 || i > ListLength(L))125         return ERROR;126     for (j = 1; j < i; j++) // 移动i-1个元素127         k = L[k].cur;128     j = L[k].cur;129     L[k].cur = L[j].cur;130     *e = L[j].data;131     Free(L, j);132     return OK;133 }134 135 void ListTraverse(SLinkList L, void(*vi)(ElemType)) {136     // 初始条件：线性表L已存在。操作结果：依次对L的每个数据元素调用函数vi()137     int i = L[MAX_SIZE - 1].cur; // 指向第一个元素138     while (i) { // 没到静态链表尾139         vi(L[i].data); // 调用vi()140         i = L[i].cur; // 指向下一个元素141     }142     printf("\n");143 }