要点
单链表的结构可表示如下：
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
#include
/***********************************************************************************************************************
第一部分，数据结构、宏定义
***********************************************************************************************************************/
#define MAX 5
typedef enum {
K = 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;
}