数据结构:程序加图示分析单链表的插入和删除操作

下图展示了单链表的基本结构:

head指针是链表的头指针,指向第一个节点,每个节点的next指针域指向下一个节点,最后一个节点的next指针域为NULL,在图中用0表示。

下面先来看程序(栈的链式存储实现,另外一个实现点这里)和对应的输出(注意输出前进行了链表反转(见《单链表反转》,否则程序后面的while循环输出的顺序是250,200,100),接着来分析程序:

/* linkedlist.h */

#ifndef LINKEDLIST_H
#define LINKEDLIST_H

typedef struct node *link;
struct node
{
    unsigned char item;
    link next;
};

link make_node(unsigned char item);
void free_node(link p);
link search(unsigned char key);
void insert(link p);
void deletep(link p);
void traverse(void (*visit)(link));
void reverse(void);
void destroy(void);
void push(link p);
link pop(void);

#endif
/* linkedlist.c */
#include <stdlib.h>
#include <stdio.h>
#include "linkedlist.h"

static link head = NULL;

link make_node(unsigned char item)
{
    link p = malloc(sizeof(*p));
    p->item = item;
    p->next = NULL;
    printf("make node from Item %d\n", item);
    return p;
}

void free_node(link p)
{
    printf("free node ...\n");
    free(p);
}

link search(unsigned char key)
{
    link p;
    printf("search by key %d\n", key);
    for (p = head; p; p = p->next)
        if (p->item == key)
            return p;
    return NULL;
}

void insert(link p)
{
    printf("insert node from head ...\n");
    p->next = head;
    head = p;
}

/*
void delete(link p)
{
    link pre;
    printf("delete node from ptr ...\n");
    if (p == head) {
        head = p->next;
        return;
    }
    for (pre = head; pre; pre = pre->next) 
        if (pre->next == p) {
            pre->next = p->next;
            return;
     }
}
*/

void deletep(link p)
{
    link *pnext;
    printf("delete node from ptr ...\n");
    for (pnext = &head; *pnext; pnext = &(*pnext)->next)
        if (*pnext == p)
        {
            *pnext = p->next;
            return;
        }
}

void traverse(void (*visit) (link))
{
    link p;
    printf("linkedlist traverse ...\n");
    for (p = head; p; p = p->next)
        visit(p);
}

void reverse(void)
{
    link pnode = head;
    link pprev = NULL;
    printf("reverse linkedlist ...\n");
    while (pnode != NULL)
    {
        // get the next node, and save it at pNext
        link pnext = pnode->next;
        // reverse the linkage between nodes
        pnode->next = pprev;
        // move forward on the the list
        pprev = pnode;
        pnode = pnext;

    }
    head = pprev;
}

void destroy(void)
{
    link q, p = head;
    printf("destory linkedlist ...\n");
    head = NULL;
    while (p)
    {
        q = p;
        p = p->next;
        free_node(q);
    }
}

void push(link p)
{
    printf("push item from head ...\n");
    insert(p);
}

link pop(void)
{
    if (head == NULL)
        return NULL;
    else
    {
        link p = head;
        printf("pop item from head ...\n");
        head = head->next;
        return p;
    }
}
/*************************************************************************
    > File Name: main.c
    > Author: Simba
    > Mail: dameng34@163.com
    > Created Time: Fri 28 Dec 2012 01:22:24 PM CST
 ************************************************************************/

#include<stdio.h>
#include "linkedlist.h"

void print_item(link p)
{
    printf("print item %d \n", p->item);
}

int main(void)
{
    link p = make_node(10);
    insert(p);
    p = make_node(5);
    insert(p);
    p = make_node(90);
    insert(p);
    p = search(5);
    deletep(p);
    free_node(p);
    traverse(print_item);
    destroy();
    printf("..................\n");
    p = make_node(100);
    push(p);
    p = make_node(200);
    push(p);
    p = make_node(250);
    push(p);

    reverse();//链表反转

    while ((p = pop()))
    {

        print_item(p);
        free_node(p);
    }

    return 0;
}

输出为:

分析:

在初始化时把头指针head初始化为NULL,表示空链表(不带头结点)。然后main函数调用make_node创建几个节点,分别调用insert插入到链表中。

链表的插入操作如下图:

正如上图所示,insert函数虽然简单,其中也隐含了一种特殊情况(Special Case)的处理,当head为NULL时,执行insert操作插入第一个节点之后,head指向第一个节点,而第一个节点的next指针域成为NULL,这很合理,因为它也是最后一个节点。所以空链表虽然是一种特殊情况,却不需要特殊的代码来处理,和一般情况用同样的代码处理即可,这样写出来的代码更简洁,但是在读代码时要想到可能存在的特殊情况。当然,insert函数传进来的参数p也可能有特殊情况,传进来的p可能是NULL,甚至是野指针,本章的函数代码都假定调用者的传进来的参数是合法的,不对参数做特别检查。事实上,对指针参数做检查是不现实的,如果传进来的是NULL还可以检查一下,如果传进来的是野指针,根本无法检查它指向的内存单元是不是合法的,C标准库的函数通常也不做这种检查,例如strcpy(p, NULL)就会引起段错误。

接下来main函数调用search在链表中查找某个节点,如果找到就返回指向该节点的指针,找不到就返回NULL。

search函数其实也隐含了对于空链表这种特殊情况的处理,如果是空链表则循环体一次都不执行,直接返回NULL。

然后main函数调用delete从链表中摘除用search找到的节点,最后调用free_node释放它的存储空间。

链表的删除操作如下图:

从上图可以看出,要摘除一个节点需要首先找到它的前趋然后才能做摘除操作,而在单链表中通过某个节点只能找到它的后继而不能找到它的前趋,所以删除操作要麻烦一些,需要从第一个节点开始依次查找要摘除的节点的前趋。delete操作也要处理一种特殊情况,如果要摘除的节点是链表的第一个节点,它是没有前趋的,这种情况要用特殊的代码处理,而不能和一般情况用同样的代码处理。这样很不爽,能不能把这种特殊情况转化为一般情况呢?可以把delete函数改成上述程序那样:

消除特殊情况的链表删除操作如下图:

定义一个指向指针的指针pnext,在for循环中pnext遍历的是指向链表中各节点的指针域,这样就把head指针和各节点的next指针统一起来了,可以在一个循环中处理。(其实增加一个头节点也可以消除delete的特殊情况《线性表的链式存储结构》) 然后main函数调用traverse函数遍历整个链表,调用destroy函数销毁整个链表。

参考:《linux c 编程一站式学习》

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Dawnzhang的开发者手册

数据结构与算法学习笔记之 提高读取性能的链表(上)

链表(Linked list)比数组稍微复杂一点,在我们生活中用到最常见的应该是缓存,它是一种提高数据读取性能的技术,常见的如cpu缓存,浏览器缓存,数据库缓...

733
来自专栏吾爱乐享

java之学习Random类的概述和注意事项

793
来自专栏机器学习入门

挑战程序竞赛系列(72):4.7高度数组(2)

挑战程序竞赛系列(72):4.7高度数组(2) 传送门:POJ 3415: Common Substrings 题意: 公共子串:统计A和B长度不小于K的公共...

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

22:因子分解

22:因子分解 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB描述 输入一个数,输出其素因子分解表达式。 输入输入一个整数...

31612
来自专栏小古哥的博客园

JS数组去重的三种方法

在程序中,通常解决一个问题的方法有很多种。当然这些不同思路的解决方法,在性能和效率上也有很大差异。 以下是数字去重的三种方法, 一、循环遍历法(传统思路) 最简...

3475
来自专栏desperate633

[编程题] 偶串分析代码

输出描述: 输出一个整数,表示删除之后能得到的最长偶串长度是多少。保证测试数据有非零解

681
来自专栏Android开发指南

10.TreeSet、比较器

34810
来自专栏用户画像

腾讯面试题之词频统计

有一千万条短信,有重复,以文本文件的形式保存,一行一条,找出重复出现最多的前10条。

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

Leetcode 72 Edit Distance DP好题

Given two words word1 and word2, find the minimum number of steps required to c...

1879
来自专栏闻道于事

JavaScript数组基础及实例

js数组 和var i=1;这样的简单存储一样是js中的一种数据结构,是专门用来存储多个数据的一种数据结构。 摘:数组是一组数据的集合,其表现形式就是内存中的一...

2879

扫码关注云+社区