本页使用了标题或全文手工转换

单向链表

维基百科,自由的百科全书
(重定向自单链表
跳到导航 跳到搜索

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

数据结构[编辑]

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

Link zh.png

動態單鏈表(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无定义,返回INFEASIBLE
115     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。不改变L
128     // 在带头结点的单链线性表L中第i个位置之前插入元素e
129     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。不改变L
146     // 在带头结点的单链线性表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个元素之前插入新的数据元素e
106     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 }