专栏首页开发与安全数据结构:程序加图示分析单链表的插入和删除操作

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

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

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 条评论
登录 后参与评论

相关文章

  • 数据结构:双向链表实现队列与循环链表

    一、双向链表(double linked list)如图26.5,是在单链表的每个结点中,再设置一个指向其前驱结点的指针域。双向链表的基本操作与单链表基本一样,...

    s1mba
  • linux系统编程之文件与I/O(三):目录的操作

    一、目录的访问 功能说明:打开一个目录 原型:DIR*  opendir(char *pathname); 返回值: 打开成功,返回一个目录指针 打开...

    s1mba
  • 数据结构:线性表之链式存储结构

    为了表示每个数据元素ai与其直接后继元素ai+1之间的逻辑关系,对数据ai,除了存储其自身的信息之外,还需存储一个指示其 直接后继的信息(即直接后继的存储位置)...

    s1mba
  • 数据结构:双向链表实现队列与循环链表

    一、双向链表(double linked list)如图26.5,是在单链表的每个结点中,再设置一个指向其前驱结点的指针域。双向链表的基本操作与单链表基本一样,...

    s1mba
  • Linux内核链表的使用

    在Linux内核中使用了大量的链表结构来组织数据,包括设备列表以及各种功能模块中的数据组织。这些链表大多采用在include/linux/list.h实现的一个...

    morixinguan
  • jQuery中on()、bind()、live()、delegate()之间的区别

    首先简述下回涉及到的几个知识点: DOM树 首先,可视化一个HMTL文档的DOM树是很有帮助的。一个简单的HTML页面看起来就像是这个样子:

    Clearlove
  • 给Emlog模板添加复制提醒

    陌涛
  • 【休息室】一张图看懂Java的垃圾回收机制

    ? 新手程序员第一次做项目的过程…… ? 代码写好了,咱们来测试吧…… ? 一张图看懂 Java 多线程阻塞机制…… ? Bug多了,总有一个会把你坑了…… ...

    老九君
  • JavaScript实现继承

    众所周知,JavaScript 这门语言在 ES6 出来之前是没有类(class)这一概念的,所以 JavaScript 中的类都是通过原型链来实现的。同样,使...

    疯狂的技术宅
  • 大数据将给百姓生活带来什么?

        无人驾驶的汽车,提供符合学生个性化的教学辅导材料,计算机来编辑新闻……日前,在北京召开的“首届大数据时代创新与媒介变革研讨会”上,专家们提出,大数据将给...

    腾讯研究院

扫码关注云+社区

领取腾讯云代金券