频道栏目
首页 > 程序开发 > 软件开发 > 其他 > 正文
单链表的算法
2015-04-14 09:01:05           
收藏   我要投稿
要点

 

单链表的结构可表示如下:

 

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;

}

点击复制链接 与好友分享!回本站首页
相关TAG标签 算法
上一篇:验证验生成的原始方法
下一篇:关于A*寻路算法的认识
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站