单链表的算法

要点

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

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

链表

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

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

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

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

单链表

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

本文先介绍单链表。

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

相关文章

来自专栏尾尾部落

[剑指offer] 二叉树的下一个结点

给定一个二叉树和其中的一个结点,请找出中序遍历顺序的下一个结点并且返回。注意,树中的结点不仅包含左右子结点,同时包含指向父结点的指针。

641
来自专栏苍云横渡学习笔记

【慕课-数据结构-C++语言】树篇

【本文目录】 树的定义 相关术语 用数组表示二叉树 用链表表示二叉树 节点的定义与方法 树的定义与方法 ---- 树的定义 树(tree)是包含n(n>0)个结...

2797
来自专栏aCloudDeveloper

用O(1)的时间复杂度删除单链表中的某个节点

给定链表的头指针和一个结点指针,在O(1)时间删除该结点。链表结点的定义如下: struct ListNode { int m_nKe...

1958
来自专栏架构之路

Combination Sum II 组合数求和之2-Leetcode

原题: Given a collection of candidate numbers (C) and a target number (T), find al...

2755
来自专栏杨建荣的学习笔记

关于查询转换的一些简单分析(三) (r3笔记第69天)

关于查询转换,已经讨论了视图合并和子查询解嵌套,还有谓词推进和物化视图查询重写也是查询转换中不可或缺的部分。 -->谓词推进 这个术语听起来高大上,有点故弄玄虚...

26811
来自专栏算法与数据结构

数据结构 重点详解

线性数据结构 线性表-顺序表 代码实现: #include <bits/stdc++.h> #define TRUE 1 #define FALSE 0...

2306
来自专栏企鹅号快讯

数据库中间件 Sharding-JDBC 源码分析——SQL 解析之插入SQL

1. 概述 本文前置阅读: 《SQL 解析(一)之词法解析》 《SQL 解析(二)之SQL解析》 本文分享插入SQL解析的源码实现。 不考虑 INSERT SE...

1855
来自专栏苍云横渡学习笔记

【慕课-数据结构-C++语言】树篇

原文地址:https://www.cloudcrossing.xyz/post/31/

3942
来自专栏郭耀华‘s Blog

剑指offer 第十一天

46.扑克牌顺子 LL今天心情特别好,因为他去买了一副扑克牌,发现里面居然有2个大王,2个小王(一副牌原本是54张^_^)...他随机从中抽出了5张牌,想测测自...

3099
来自专栏ml

poj------2406 Power Strings

A - Power Strings 难度:☆☆ Time Limit:3000MS     Memory Limit:65536KB     64bit I...

2988

扫码关注云+社区