单链表的算法

要点

在顺序表的算法文章中,我们讨论了线性表的顺序存储结构——顺序表。

顺序表是用一组地址连续的存储单元来保存数据的,所以它具有随机存取的特点。即查找快速,但是做插入或删除动作是,需要移动大量元素,效率较低。

链表

链表是线性表的链式存储结构,它相比于顺序表,在插入和删除元素时,效率要高很多。

链表,是用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的)。

每个数据单元有两部分组成,一个是数据域,存储数据值;另一个是指针域,指向下一个数据单元。这样的数据单元叫做结点

当多个结点通过指针指向,关联起来,就形成了一个链,即链表。

单链表

链表可分为单链表、双链表、循环链表。

本文先介绍单链表。

单链表就是沿着单方向的链表。例如: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版),李春葆、喻丹丹

相关阅读

欢迎阅读 程序员的内功——数据结构和算法 系列

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏青玉伏案

Java面向对象练习

1、定义长方形类,含:   属性:宽、高(整型);   方法:求周长、面积;   构造方法3个:(1)无参——宽、高默认值为1;(2)1个参数——宽、高均为参数...

3047
来自专栏Spark学习技巧

textFile构建RDD的分区及compute计算策略

1,textFile A),第一点,就是输入格式,key,value类型及并行度的意义。 def textFile( path: String, mi...

1957
来自专栏岑玉海

Spark源码系列(六)Shuffle的过程解析

Spark大会上,所有的演讲嘉宾都认为shuffle是最影响性能的地方,但是又无可奈何。之前去百度面试hadoop的时候,也被问到了这个问题,直接回答了不知道。...

3616
来自专栏刘笑江的专栏

learn-haskell

1023
来自专栏Code_iOS

数据结构:栈与队列

工程代码 Github: Data_Structures_C_Implemention -- Stack & Queue

733
来自专栏计算机视觉与深度学习基础

Leetcode 117 Populating Next Right Pointers in Each Node II

Follow up for problem "Populating Next Right Pointers in Each Node". What if t...

1585
来自专栏Spark生态圈

[spark] Shuffle Read解析 (Sort Based Shuffle)

本文将讲解shuffle Reduce部分,shuffle的下游Stage的第一个rdd是ShuffleRDD,通过其compute方法来获取上游Stage S...

821
来自专栏有趣的Python

8-Java常用工具类-输入输出流

生活中无处不在,只要涉及到传输。复制粘贴操作;修改头像,将本地数据上传到网络服务器。

651
来自专栏coder修行路

Go基础--终端操作和文件操作

终端操作 操作终端相关的文件句柄常量 os.Stdin:标准输入 os.Stdout:标准输出 os.Stderr:标准错误输出 关于终端操作的代码例子: pa...

2766
来自专栏Java学习网

Java实现把整数转换为英语单词的方法,实用代码

一个非负整数转换为英文单词表示。 例如: 123 -> "One Hundred Twenty Three" 12345 -> "Twelve Thousand...

2319

扫码关注云+社区