数据结构：单链表（LinkList）基本操作的算法描述（C语言）_linklist函数声明

作者在学习数据结构时，发现鲜有完全按照 C 语言描述的算法操作，这让习惯于写 .c 而不是 .cpp 的初学者很是头疼。本文将基于 C 语言描述算法操作，如有错漏还望大佬们指正。

前言

本文将按照严惠敏所著《数据结构(C语言版)》所做的函数原型声明进行算法描述，由于C语言不支持函数参数中出现取地址符，我将函数参数更改为指针，调用函数时需要使用一级指针。新增了打印函数 PrintList； 单链表的基本操作调用示例将在本文后给出。

一、单链表基本操作的函数声明

//构造一个空的单链表 L 并初始化
extern Status InitList(LinkList* L);
//销毁单链表 L
extern Status DestroyList(LinkList* L);
//将 L 重置为空表
extern Status ClearList(LinkList L);
//若 L 为空表，则返回 TRUE，否则返回 FALSE
extern Status ListEmpty(LinkList L);
//返回 L 中数据元素个数
extern int ListLength(LinkList L);
//用 e 返回 L 中第 i 个数据元素的值
extern Status GetElem(LinkList L, int i, ElemType* e);
//返回 L 中第一个与 e 满足关系 compare() 的数据元素的位序，若这样的数据元素不存在，则返回 0
extern int LocateElem(LinkList L, ElemType e, Status(*compare)(ElemType, ElemType));
//若 cur_e 是 L 的数据元素，且不是第一个，则用 pre_e 返回它的前驱，否则操作失败，pre_e 无定义
extern Status PriorElem(LinkList L, ElemType cur_e, ElemType* pre_e);
//若 cur_e 是 L 的数据元素，且不是最后一个，则用 next_e 返回它的后继，否则操作失败，next_e 无定义
extern Status NextElem(LinkList L, ElemType cur_e, ElemType* next_e);
//在带头结点的单链线性表 L 中第 i 个位置之前插入元素 e
extern Status ListInsert(LinkList* L, int i, ElemType e);
//在带头结点的单链线性表 L 中，删除第 i 个元素，并用 e 返回其值
extern Status ListDelete(LinkList* L, int i, ElemType* e);
//打印单链表
extern Status PrintList(LinkList L);
//逆位序输入 n 个元素的值，建立带表头结点的单链线性表 L
extern void CreateList(LinkList* L, int n);
//归并两个非递减排列的线性表 La、Lb 至 Lc，Lc也是非递减排列的
extern void MergeList(LinkList La, LinkList Lb, LinkList* Lc);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

二、单链表基本操作的完整描述

/* 单链表*/
#include <stdio.h>
#include <stdlib.h>
#define TRUE  			1
#define FALSE 			0
#define OK    			1
#define ERROR 			0
#define INFEASIBLE 		-1
#define OVERFLOW   		-2
#define EQUAL			0
#define LOWER			1
#define HIGHER			2

typedef int Status;
typedef int ElemType;
typedef struct LNode {
    ElemType data;
    struct LNode* next;
} LNode, * LinkList;

//--------单链表的基本操作的函数声明--------

//构造一个空的单链表 L 并初始化
extern Status InitList(LinkList* L);
//销毁单链表 L
extern Status DestroyList(LinkList* L);
//将 L 重置为空表
extern Status ClearList(LinkList L);
//若 L 为空表，则返回 TRUE，否则返回 FALSE
extern Status ListEmpty(LinkList L);
//返回 L 中数据元素个数
extern int ListLength(LinkList L);
//用 e 返回 L 中第 i 个数据元素的值
extern Status GetElem(LinkList L, int i, ElemType* e);
//返回 L 中第一个与 e 满足关系 compare() 的数据元素的位序，若这样的数据元素不存在，则返回 0
extern int LocateElem(LinkList L, ElemType e, Status(*compare)(ElemType, ElemType));
//若 cur_e 是 L 的数据元素，且不是第一个，则用 pre_e 返回它的前驱，否则操作失败，pre_e 无定义
extern Status PriorElem(LinkList L, ElemType cur_e, ElemType* pre_e);
//若 cur_e 是 L 的数据元素，且不是最后一个，则用 next_e 返回它的后继，否则操作失败，next_e 无定义
extern Status NextElem(LinkList L, ElemType cur_e, ElemType* next_e);
//在带头结点的单链线性表 L 中第 i 个位置之前插入元素 e
extern Status ListInsert(LinkList* L, int i, ElemType e);
//在带头结点的单链线性表 L 中，删除第 i 个元素，并用 e 返回其值
extern Status ListDelete(LinkList* L, int i, ElemType* e);
//打印单链表
extern Status PrintList(LinkList L);
//逆位序输入 n 个元素的值，建立带表头结点的单链线性表 L
extern void CreateList(LinkList* L, int n);
//归并两个非递减排列的线性表 La、Lb 至 Lc，Lc也是非递减排列的
extern void MergeList(LinkList La, LinkList Lb, LinkList* Lc);

Status InitList(LinkList* L) {
    (*L) = (LinkList)malloc(sizeof(LNode));
    if (!(*L)) exit(OVERFLOW);
    (*L)->next = NULL;
    return OK;
}// InitList

Status DestroyList(LinkList* L) {
    LinkList q;
    while (*L) {
        q = (*L)->next;
        free(*L);
        *L = q;
    }
    return OK;
}// DestroyList

Status ClearList(LinkList L) {
    LinkList p = L->next;
    L->next = NULL;
    DestroyList(&p);
}// ClearList

Status ListEmpty(LinkList L) {
    if (L->next) return TRUE;
    else return FALSE;
}// ListEmpty

int ListLength(LinkList L) {
    int i = 0;
    LinkList p = L->next;
    while (p) {
        p = p->next;
        i++;
    }
    return i;
}// ListLength

Status GetElem(LinkList L, int i, ElemType* e) {
    LinkList p = L->next; int j = 1;
    while (j < i && p) p = p->next;
    if (j > i || !p) return ERROR;
    *e = p->data;
    return OK;
}// GetElem

int LocateElem(LinkList L, ElemType e, Status(*compare)(ElemType, ElemType)) {
    int i = 1;
    LinkList p = L->next;
    while (p && (*compare)(p->data, e)) ++i;
    if (i <= ListLength(L)) return i;
    else return 0;
}// LocateElem

Status PriorElem(LinkList L, ElemType cur_e, ElemType* pre_e) {
    LinkList p = L->next;
    while (p && p->next) {
        if (p->next->data == cur_e) {
            *pre_e = p->data;
            return OK;
        }
        p = p->next;
    }
    return ERROR;
}// PriorElem

Status NextElem(LinkList L, ElemType cur_e, ElemType* next_e) {
    LinkList p = L->next;
    while (p && p->next) {
        if (p->data == cur_e) {
            *next_e = p->next->data;
            return OK;
        }
        p = p->next;
    }
    return ERROR;
}// NextElem

Status ListInsert(LinkList* L, int i, ElemType e) {
    LinkList p = *L, s; int j = 0;
    while (p && j < i - 1) { p = p->next; ++j; }
    if (!p || j > i - 1) return ERROR;
    s = (LinkList)malloc(sizeof(LNode));
    s->data = e; s->next = p->next;
    p->next = s;
    return OK;
}// ListInsert

Status ListDelete(LinkList* L, int i, ElemType* e) {
    LinkList p = *L, q; int j = 0;
    while (p->next && j < i - 1) { p = p->next; ++j; }
    if (!(p->next) || j > i - 1) return ERROR;
    q = p->next; p->next = q->next;
    *e = q->data; free(q);
    return OK;
}// ListDelete

Status PrintList(LinkList L) {
    if (!L->next) return ERROR;
    LinkList p = L->next;
    while (p) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
    return OK;
}// PrintList

void CreateList(LinkList* L, int n) {
    L = (LinkList*)malloc(sizeof(LNode));
    (*L)->next = NULL;
    LinkList p;
    for (int i = n; i > 0; --i) {
        p = (LinkList)malloc(sizeof(LNode));
        scanf("%d", &p->data);
        p->next = (*L)->next; (*L)->next = p;
    }
}// CreatList

void MergeList(LinkList La, LinkList Lb, LinkList* Lc) {
    LinkList pa = La->next, pb = Lb->next, pc;
    *Lc = pc = La;
    while (pa && pb) {
        if (pa->data <= pb->data) {
            pc->next = pa; pc = pa; pa = pa->next;
        }
        else { pc->next = pb; pc = pb; pb = pb->next; }
    }
    pc->next = pa ? pa : pb;
    free(Lb);
}// MergeList
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182

三、调用示例

int main() {
    LinkList L;
    int e = 0, pre_e = 0, nxt_e = 0;
    InitList(&L);
    ListInsert(&L, 1, 1);
    ListInsert(&L, 2, 2);
    ListInsert(&L, 3, 3);
    printf("List example: ");
    PrintList(L);
    PriorElem(L, 2, &pre_e);
    NextElem(L, 2, &nxt_e);
    printf("PriorElem(L, 2, pre_e): %d\n", pre_e);
    printf("NextElem(L, 2, nxt_e): %d\n", nxt_e);
    ListDelete(&L, 2, &e);
    printf("ListDelete(&L, 2, &e): %d\n", e);
    printf("Deleted List: ");
    PrintList(L);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

终端输出结果如下：

List example: 1 2 3 
PriorElem(L, 2, pre_e): 1
NextElem(L, 2, nxt_e): 3
ListDelete(&L, 2, &e): 2
Deleted List: 1 3 
1
2
3
4
5

总结

以上是单链表的基本操作的算法描述，更多数据结构的算法描述还在更新中，敬请关注作者专栏。