单链表的算法

要点

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

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

链表

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

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

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

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

单链表

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

本文先介绍单链表。

单链表就是沿着单方向的链表。例如: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 条评论
登录 后参与评论

相关文章

来自专栏潇涧技术专栏

Android NDK and OpenCV development with Android Studio

Android NDK and OpenCV development with Android Studio

752
来自专栏依乐祝

[译]ASP.NET Core Web API 中使用Oracle数据库和Dapper看这篇就够了

文章地址: https://www.cnblogs.com/yilezhu/p/9276565.html

991
来自专栏Android 开发学习

Android studio 2.2 JNI ffmpeg 简单的播放器(这里只有视频解码)include "libavcodec/avcodec.h"include "libavformat/avf

3003
来自专栏jeremy的技术点滴

解决zookeeper导致tomcat停止时报异常的问题

7035
来自专栏CreateAMind

视觉机械臂 visual-pushing-grasping

1021
来自专栏Java学习网

Java 语言版本整理,先到1.8版本,不全请补充

Java 语言版本 JDK 1.1.4 Sparkler 宝石 1997-09-12 JDK 1.1.5 Pumpkin 南瓜 1997-12-13 JDK 1...

2585
来自专栏CreateAMind

国产ros小车及相关文档

Roch(robot platform for commecial and home) integrated multiple different RGBD c...

1182
来自专栏10km的专栏

java nio: walkFileTree实现文件夹复制移动删除

从java 1.7开始,java提供了java.noi.file.Files类用于更方便的实现文件/文件夹操作。 在Files中提供了丰富的静态方法用于文件...

2968
来自专栏java达人

nginx配置https(亲测可用)

配置https前需要先创建证书,这里使用自签名ca证书: 1、创建ca自签名证书,使用sha256 算法签名,rsa2048位公钥算法。 openssl req...

2986
来自专栏数据和云

DBA必备技能:通过truss跟踪解决监听无法启动案例

作者简介:刘斌,云和恩墨高级技术专家,擅长数据库故障诊断分析,数据库性能优化,自动化运维开发,坚持学习、写作、分享, 在Oracle DBA的日常工作中,通过各...

3007

扫码关注云+社区