单链表的算法
要点
在顺序表的算法文章中，我们讨论了线性表的顺序存储结构——顺序表。
顺序表是用一组地址连续的存储单元来保存数据的，所以它具有随机存取的特点。即查找快速，但是做插入或删除动作是，需要移动大量元素，效率较低。
链表
链表是线性表的链式存储结构，它相比于顺序表，在插入和删除元素时，效率要高很多。
链表，是用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。
每个数据单元有两部分组成，一个是数据域，存储数据值；另一个是指针域，指向下一个数据单元。这样的数据单元叫做结点。
当多个结点通过指针指向，关联起来，就形成了一个链，即链表。
单链表
链表可分为单链表、双链表、循环链表。
本文先介绍单链表。
单链表就是沿着单方向的链表。例如：A->B->C->D->... 只能顺序的连下去，即可以从A往下找其他元素，但是反之则不行。
单链表结点的结构可表示如下：
typedef int ElemType; typedef struct LNode { ElemType data; struct LNode* next; } LNode, *LinkList; |
|---|
基本算法
插入结点
假设要在单链表的a结点和b结点之间插入一个值为x的新结点。
如下图所示，指针s指向一个值为x的结点，为了插入s。
首先让s的next指针指向b，即s->next = p->next;
然后，让a的next指针指向s，即p->next = s;
删除结点
假设要删除单链表中的b结点。
首先，找到b结点前面的结点a。
如下图所示，p指针指向a结点。b的下一个结点就是p->next->next。
所以，只要让p的next指针跳过b结点，指向b的下一个结点就OK了，即p->next = p->next->next;
参考代码
以下为本人实现的单链表的基本操作。欢迎指正。本人的编译环境为Visual Studio2010，C语言。
基本操作
/*********************************************************************************************************************** [单链表操作] [1] destroyList, 销毁单链表 [2] initList, 初始化一个带头结点的空单链表，如果传入一个不为空的单链表，将被重置 [3] insertElem, 在单链表中第 i 个位置插入元素 elem [4] removeElem, 在单链表中移除第 pos 个元素，并由 elem 返回其值 [5] createList, 根据数组 elems 构建一个单链表 [6] isEmptyList, 判断单链表是否为空 [7] getElem, 获取单链表上位置为 pos 的元素 [8] locateElem, 获取元素 elem 在单链表上第一次出现的位置，如果不存在返回 -1 [9] getLength, 获取单链表长度 [10] printList, 打印整个单链表 [11] reverseList, 反转单链表 ***********************************************************************************************************************/ #include <stdio.h> #include <stdlib.h> /*********************************************************************************************************************** 第一部分，数据结构、宏定义 ***********************************************************************************************************************/ #define MAX 5 typedef enum { OK = 0, ERROR = 1 } STATUS_EN; typedef enum { TRUE = 0, FALSE = -1 } BOOL; typedef int ElemType; typedef struct LNode { ElemType data; struct LNode* next; } LNode, *LinkList; /*********************************************************************************************************************** 第二部分，函数实现 ***********************************************************************************************************************/ /******************************************************************************* Funtion : [1] destroyList Description : 销毁单链表 Input : struct LNode **ppHead Output : struct LNode **ppHead Return Value : STATUS_EN(OK/ERROR) Author : VictorZhang Date : 2015-03-30 *******************************************************************************/ void destroyList(struct LNode **ppHead) { LNode *p = *ppHead; LNode *q = p->next; // 先遍历删除所有元素 while (p && p->next) { q = p->next; p = q->next; free(q); q = NULL; } // 最后释放头结点 free(*ppHead); *ppHead = NULL; } /******************************************************************************* Funtion : initList Description : 初始化一个带头结点的空单链表，如果传入一个不为空的单链表， 将被重置 Input : struct LNode **ppHead Output : struct LNode **ppHead Return Value : STATUS_EN(OK/ERROR) Author : VictorZhang Date : 2015-03-30 *******************************************************************************/ STATUS_EN initList(struct LNode **ppHead) { if (*ppHead) destroyList(ppHead); LNode *p = (LNode*)malloc(sizeof(LNode)); p->next = NULL; p->data = 0; *ppHead = p; return OK; } /******************************************************************************* Funtion : insertElem Description : 在单链表中第 i 个位置插入元素 elem Input : struct LNode **ppHead, const int pos, const ElemType elem Output : struct LNode **ppHead Return Value : STATUS_EN(OK/ERROR) Author : VictorZhang Date : 2015-03-30 *******************************************************************************/ STATUS_EN insertElem(struct LNode **ppHead, const int pos, const ElemType elem) { LNode *p = *ppHead; LNode *s = NULL; // 寻找链表当前最后一个结点 int i = 0; while (p && i < pos) { p = p->next; i++; } // 未找到末尾结点 if (!p || i > pos) return ERROR; // 生成新结点 s = (LNode*) malloc (sizeof(LNode)); if (!s) return ERROR; // 插入单链表中 s->data = elem; s->next = p->next; p->next = s; return OK; } /******************************************************************************* Funtion : removeElem Description : 在单链表中移除第 pos 个元素，并由 elem 返回其值 Input : struct LNode **ppHead, const int pos, ElemType *pElem Output : struct LNode **ppHead, ElemType *pElem Return Value : STATUS_EN(OK/ERROR) Author : VictorZhang Date : 2015-03-30 *******************************************************************************/ STATUS_EN removeElem(struct LNode **ppHead, const int pos, ElemType *pElem) { LNode *p = *ppHead; LNode *q = NULL; int i = 0; while (p && p->next && i < pos) { p = p->next; i++; } // 删除位置不合理 if (!(p->next) || i > pos) return ERROR; // 删除并释放结点 q = p->next; p->next = q->next; *pElem = q->data; free(q); return OK; } /******************************************************************************* Funtion : createList Description : 根据数组 elems 构建一个单链表 Input : struct LNode **ppHead, const ElemType elems[], const int n Output : struct LNode **ppHead Return Value : STATUS_EN(OK/ERROR) Author : VictorZhang Date : 2015-03-30 *******************************************************************************/ STATUS_EN createList(struct LNode **ppHead, const ElemType elems[], const int n) { int i = 0; STATUS_EN statu = OK; // 按序将数组元素插入到单链表尾部 for (i = 0; i < n; i++) { statu = insertElem(ppHead, i, elems[i]); if (OK != statu) return statu; } return OK; } /******************************************************************************* Funtion : isEmptyList Description : 判断单链表是否为空 Input : struct LNode *pHead Output : N/A Return Value : BOOL Author : VictorZhang Date : 2015-03-30 *******************************************************************************/ BOOL isEmptyList(struct LNode *pHead) { if (NULL == pHead || NULL == pHead->next) return TRUE; else return FALSE; } /******************************************************************************* Funtion : getElem Description : 获取单链表上位置为 pos 的元素 Input : struct LNode *pHead, const int pos, ElemType *pElem Output : ElemType *pElem Return Value : STATUS_EN(OK/ERROR) Author : VictorZhang Date : 2015-03-30 *******************************************************************************/ STATUS_EN getElem(struct LNode *pHead, const int pos, ElemType *pElem) { int i = 0; LNode *p = pHead->next; while (p && i <= pos) { if (i == pos) { *pElem = p->data; return OK; } else { p = p->next; i++; } } return ERROR; } /******************************************************************************* Funtion : locateElem Description : 获取元素 elem 在单链表上第一次出现的位置，如果不存在返回 -1 Input : struct LNode *pHead, const ElemType elem Output : N/A Return Value : int Author : VictorZhang Date : 2015-03-30 *******************************************************************************/ int locateElem(struct LNode *pHead, const ElemType elem) { int pos = 0; LNode *p = pHead->next; while (p) { if (p->data == elem) { return pos; } else { pos++; p = p->next; } } return -1; } /******************************************************************************* Funtion : getLength Description : 获取单链表长度 Input : struct LNode *pHead Output : N/A Return Value : int Author : VictorZhang Date : 2015-04-02 *******************************************************************************/ int getLength(struct LNode *pHead) { if (NULL == pHead || NULL == pHead->next) { return 0; } int i = 0; LNode *p = pHead->next; while (p) { p = p->next; i++; } return i; } /******************************************************************************* Funtion : printList Description : 打印整个单链表 Input : struct LNode *pHead Output : N/A Return Value : N/A Author : VictorZhang Date : 2015-04-02 *******************************************************************************/ void printList(struct LNode *pHead) { if (NULL == pHead || NULL == pHead->next) { printf("LinkList is empty\n"); return; } LNode *p = pHead->next; printf("LinkList:"); while (p) { printf(" %d", p->data); p = p->next; } printf("\n"); } /******************************************************************************* Funtion : reverseList Description : 反转单链表 Input : struct LNode **ppHead Output : struct LNode **ppHead Return Value : N/A Author : VictorZhang Date : 2015-04-02 *******************************************************************************/ void reverseList(struct LNode **ppHead) { if (NULL == *ppHead || NULL == (*ppHead)->next) { return; } LNode *prev = NULL; LNode *cur = (*ppHead)->next; LNode *next = NULL; while (cur) { next = cur->next; cur->next = prev; prev = cur; cur = next; } (*ppHead)->next = prev; } |
|---|
测试例部分
/***********************************************************************************************************************
第三部分，测试例
***********************************************************************************************************************/
void testCase0() {
printf("================== testCase0 ==================\n");
int len = 0;
BOOL bFlag = FALSE;
ElemType A[MAX] = {4,5,2,1,3};
struct LNode *pHead = NULL;
// 初始化链表
initList(&pHead);
printf("Init List\n");
// 获取链表长度
len = getLength(pHead);
printf("Length of List is %d\n", len);
// 根据一个数组来创建单链表
createList(&pHead, A, MAX);
printf("After create List：\n");
printList(pHead);
// 获取链表长度
len = getLength(pHead);
printf("Length of List is %d\n", len);
// 判断单链表是否为空
bFlag = isEmptyList(pHead);
if (bFlag) {
printf("It is a empty List.\n");
} else {
printf("It is not a empty List.\n");
}
// 销毁链表
printf("Destroy List\n");
destroyList(&pHead);
// 获取链表长度
len = getLength(pHead);
printf("Length of List is %d\n", len);
// 判断单链表是否为空
bFlag = isEmptyList(pHead);
if (bFlag) {
printf("It is a empty List.\n");
} else {
printf("It is not a empty List.\n");
}
}
void testCase1() {
printf("================== testCase1 ==================\n");
STATUS_EN statu;
ElemType A[MAX] = {4,5,2,1,3};
struct LNode *pHead = NULL;
// 初始化链表
initList(&pHead);
printf("Init List\n");
createList(&pHead, A, MAX);
printf("After create List：\n");
printList(pHead);
// 在尾部位置尝试插入元素
statu = insertElem(&pHead, 5, 9);
printf("Insert element：\n");
if (OK != statu) {
printf("Insert failed!\n");
} else {
printList(pHead);
}
// 在头部位置尝试插入元素
statu = insertElem(&pHead, 0, 2);
if (OK != statu) {
printf("Insert failed!\n");
} else {
printList(pHead);
}
// 中间位置尝试插入元素
statu = insertElem(&pHead, 3, 7);
if (OK != statu) {
printf("Insert failed!\n");
} else {
printList(pHead);
}
// 尝试在不合理的位置上插入元素
statu = insertElem(&pHead, 99, 15);
if (OK != statu) {
printf("Insert failed!\n");
} else {
printList(pHead);
}
}
void testCase2() {
printf("================== testCase2 ==================\n");
STATUS_EN statu;
ElemType elem;
ElemType A[MAX] = {4,5,2,1,3};
struct LNode *pHead = NULL;
// 初始化链表
initList(&pHead);
printf("Init List\n");
createList(&pHead, A, MAX);
printf("After create List：\n");
printList(pHead);
// 尝试移除尾部位置的元素
statu = removeElem(&pHead, 4, &elem);
printf("Remove element pos(%d)\n", 4);
if (OK != statu) {
printf("Remove failed!\n");
} else {
printList(pHead);
}
// 尝试移除头部位置的元素
statu = removeElem(&pHead, 0, &elem);
printf("Remove element pos(%d)\n", 0);
if (OK != statu) {
printf("Remove failed!\n");
} else {
printList(pHead);
}
// 尝试移除中间位置的元素
statu = removeElem(&pHead, 1, &elem);
printf("Remove element pos(%d)\n", 1);
if (OK != statu) {
printf("Remove failed!\n");
} else {
printList(pHead);
}
// 尝试移除不合理位置的元素
statu = removeElem(&pHead, 11, &elem);
printf("Remove element pos(%d)\n", 11);
if (OK != statu) {
printf("Remove failed!\n");
} else {
printList(pHead);
}
}
void testCase3() {
printf("================== testCase3 ==================\n");
int pos = 4;
STATUS_EN statu;
ElemType elem;
ElemType A[MAX] = {4,5,2,1,3};
struct LNode *pHead = NULL;
// 初始化链表
initList(&pHead);
printf("Init List\n");
createList(&pHead, A, MAX);
printf("After create List：\n");
printList(pHead);
// 获取指定位置上的元素
statu = getElem(pHead, pos, &elem);
if (OK != statu) {
printf("Get element failed!\n");
} else {
printf("The elem in pos(%d) is %d\n", pos, elem);
}
// 查找元素在单链表中第一次出现的位置
elem = 4;
pos = locateElem(pHead, elem);
printf("%d is in pos(%d) of List\n", elem, pos);
elem = 9;
pos = locateElem(pHead, elem);
printf("%d is in pos(%d) of List\n", elem, pos);
}
void testCase4() {
printf("================== testCase4 ==================\n");
ElemType A[MAX] = {4,5,2,1,3};
struct LNode *pHead = NULL;
// 初始化链表
initList(&pHead);
printf("Init List\n");
createList(&pHead, A, MAX);
printf("After create List：\n");
printList(pHead);
// 反转单链表
reverseList(&pHead);
printf("Reverse List：\n");
printList(pHead);
}
int main() {
testCase0();
testCase1();
testCase2();
testCase3();
testCase4();
return 0;
}
参考资料
《数据结构》（C语言版） ，严蔚敏、吴伟民
《数据结构习题与解析》（B级第3版），李春葆、喻丹丹
相关阅读
欢迎阅读 程序员的内功——数据结构和算法 系列