文档章节

3.1 单链表

沐浴星光
 沐浴星光
发布于 2015/06/04 16:56
字数 1827
阅读 31
收藏 0
点赞 0
评论 0

1.单链表简介

   数组在编程语言中用的非常有用,但是属数组至少有两个缺点

 (1) 编译时就得知道数组的大小

 (2) 在计算机内存中是连续存储的,这就意味着在数组中插入或删除一个数据,就需要调整其他数据。

而使用链表结构就不存在这些问题

下图表示一个链表的结构及其构造过程。


上图所示的链表中的每个节点都是下面类定义(节点值为整数型)的一个实例:

这是一种C++面向对象的写法,在C语言中,我们习惯定义成结构体。

 class IntSLLNode { 
     public:   IntSLLNode() {//第一个构造函数初始化next指针为NULL	
     next = 0;	 }   
     IntSLLNode(int i, IntSLLNode *in = 0) {//第二个构造函数设置两个成员数据的值	
     info = i; next = in;}
     int info;
     IntSLLNode *next;//指向下一个节点,这个节点的类型与本节点相同,这里要定义成公有成员,以便实施链表的操作 };


节点包含两个数椐成员: info 和 next,  info 成员用于对用户有用的存储, next 是用于连接链表节点对从而形成链表结构。

有了这个定义我们就可以构造上图所示的链表了:

IntSLLNode *p = new IntSLLNode(10);

p->next = new IntSLLNode(8);

p->next->next = new IntSLLNode(50);

这里仅定义了一个头指针p来访问数据,不是很方便,在实际操作中一般会定义两个指针或更多指针方便操作。


2.单链表操作

链表节点类型已经由类IntSLLNode定义好了,接下来就是定义一个类实施对链表的各种错作,单链表的操作无非是增删查改

定义下面的类IntSLList

  1. class IntSLList {
    public:
       IntSLList() {
           head = tail = 0;
       }
       ~IntSLList();
       int isEmpty() {
           return head == 0;
       }
       void addToHead(int);
       void addToTail(int);
       int  deleteFromHead(); // delete the head and return its info;
       int  deleteFromTail(); // delete the tail and return its info;
       void deleteNode(int);
       bool isInList(int) const;
       void printAll() const;
    private:
       IntSLLNode *head, *tail;//两个私有成员变量,分别是指向单链表的头和尾的指针
    };

2.1 插入

(1)添加到链表开头

四步:

  • 创建一个空节点

  • 初始化节点值el

  • 添加新节点到链表最前面,并将新节点的next指向头节点,也就是head的当前值

  • 将head更新为指向新节点的指针

void IntSLList::addToHead(int el) {    
      head = new IntSLLNode(el,head);//一句话就完成了四步,这就是C++的魅力了    
      if (tail == 0)       
          tail = head;
}

(2)添加到链表末尾

四步:

  • 创建一个空节点

  • 初始化节点值el,因为该节点要添加到链表的末尾,所以将新节点的next设置为NULL

  • 让原链表的尾节点的next指向新建的尾节点,这样就将新节点添加到了末尾

  • 将tail更新为指向新节点的指针

void IntSLList::addToTail(int el) {  
  if (tail != 0) {      // 先判断链表是否为空         
     tail->next = new IntSLLNode(el);         
     tail = tail->next;    
  }    
  else 
     head = tail = new IntSLLNode(el);}


2.2 删除

(1)删除头节点并返回它的值

为了程序的严谨需要考虑两种特殊情况:

  • 一种是试图从一个空链表删除一个节点。

  • 二是链表只有一个节点的情况。

int IntSLList::deleteFromHead() {
    if(!isEmpty())//检查链表链表是否为空
    {    
    int el = head->info;     
    IntSLLNode *tmp = head;     
    if (head == tail)     //加入链表只有一个节点;        
       head = tail = 0;     
    else 
      head = head->next;     
     delete tmp;     
     return el;    
     }   
    else   //std::cout<<"The List is Empty!"       return 0;}

注意:上面的程序实际上有一个问题,程序开始用if语句检查了链表是否为空,假如为空就就会执行else的操作返回0;而对于调用

这个方法的语句并不知道返回的0是头节点本身的值是0,还是因为链表为空而返回的0。最好的解决方法是调用此方法之前就判定一

下链表是否为空。

(2)删除尾节点并返回它的值

该删除操作由成员函数 deleteFromTail实现。 问题在删除了尾节点之后, tail应当指向链表的新末尾节点,也就是说, tail 必须反方向移动一个节点,但是因为从最后一个节点到它的前驱节点没有直接的链接,所以无法进行反方向移动。 因此必须从链表的幵头查找这个前驱 节点,并恰好在tail前面停止。这个任务是通过在for在 循环中用个临时变量temp遍历链表完成的 。

int IntSLList::deleteFromTail() {   
 int el = tail->info;   
  if (head == tail) {   // if only one node on the list;         
   delete head;        
   head = tail = 0;    
   }   
  else {                // if more than one node in the list,        
    IntSLLNode *tmp; // find the predecessor of tail;        
     for (tmp = head; tmp->next != tail; tmp = tmp->next);         
     delete tail;         
     tail = tmp;      // the predecessor of tail becomes tail;         t
     ail->next = 0;   
    }   
      return el;
 }

(3) 删除值为el的节点

前面讨论的这两种刪除操作是从开头或者末尾删除一个节点。如果要刪除一个包含特定整数的节点,而不关心这个节点在链表中的位置就需要使用不同的方法。这个节点也许正好在链表的开头、末尾,或者在链表中的任何位置。简单地说,必须先找到这个节点, 然后将其前驱节点与后继节点连接,从而将其从链表中删除。因为不知道该节点在什么位置, 操作复杂得多。

将前驱结点以及后继节点连接起来就 能从链表中删除这个节点 ,但是因为链表只有向后的链接,因此无法从某个节点获得其前驱。完成这个忏务的方法之一是先扫描链表找到处要删除的节点,然后再次扫描链表找到它的前驱,另一种方法如下图所示,借助两个指针变量pred和tmp。

前面的图只讨论了 一种情况,还有下面几种情况:

  • 试图从空链表中刪除节点,此时函数立即退出。

  • 从单节点链表中删除唯一的节点: head 和 tail都设置成 null

  • 从至少有两个节点的链表中刪除第一个节点,此吋需要更新 head

  •  从至少有两个节点的链表中刪除最后一个节点,此吋需要更新 tail

  •  链表中不存在包含某个数字的节点:不进行任何操作.

void IntSLList::deleteNode(int el) {
    if (head != 0)                     // if non-empty list;
    if (head == tail && el == head->info) { // if only one
        delete head;                       // node on the list;
        head = tail = 0;
    }
    else if (el == head->info) {  // if more than one node on the list
        IntSLLNode *tmp = head;
        head = head->next;
        delete tmp;              // and old head is deleted;
    }
    else {                        // if more than one node in the list
        IntSLLNode *pred, *tmp;
        for (pred = head, tmp = head->next; // and a non-head node
            tmp != 0 && !(tmp->info == el);// is deleted;
            pred = pred->next, tmp = tmp->next);
        if (tmp != 0) {
            pred->next = tmp->next;
            if (tmp == tail)
                tail = pred;
            delete tmp;
        }
    }
}

2.3 查找

插入和删除操作都对链表进行了修改。查找操作扫描已有的链表,以确定其中是否包含某个数, 在此用布尔成员函数 isInList()实现这个操作。

bool IntSLList::isInList(int el) const {    
  IntSLLNode *tmp;    
  for (tmp = head; tmp != 0 && !(tmp->info == el); tmp = tmp->next);    
  return tmp != 0;
}

完整代码:http://www.oschina.net/code/snippet_588162_48571


来自为知笔记(Wiz)


© 著作权归作者所有

共有 人打赏支持
沐浴星光
粉丝 4
博文 14
码字总数 26411
作品 0
武汉
带头结点的链表

1、链表和顺序表 链表是很常见的数据结构,链表总是会和线性顺序表来比较。 1.1、顺序表 具有随机存储的特性,给定位置就能通过计算找到数据所在位置,因为在分配存储空间的时候,是连续分配...

王奥宇 ⋅ 2017/12/05 ⋅ 0

数据结构与算法-C语言篇6-线性表之链式存储结构

数据结构与算法-目录 1、线性表的链式存储结构 1.1、线性表链式存储结构定义 线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素,这组存储单元可以是连续的,也可以是不...

香沙小熊 ⋅ 01/07 ⋅ 0

Java实现链表面试题

本文包含链表的以下内容:   1、单链表的创建和遍历   2、求单链表中节点的个数   3、查找单链表中的倒数第k个结点(剑指offer,题15)   4、查找单链表中的中间结点   5、合并两个...

火力全開 ⋅ 2016/10/09 ⋅ 0

数据结构和算法之一——线性表_3_链式存储结构_1_单链表

1. 链表的定义 线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素,这组存储单元可以存在内存中未被占用的任意位置。 (比起顺序存储结构每个数据元素只需要存储一个位置...

Eric_Hunter ⋅ 01/11 ⋅ 0

线性表

1、线性表的定义 线性表(List):零个或多个数据元素的有限序列 第一个元素无前驱,最后一个元素无后继,其他元素都有且只有一个前驱和后继。然后,线性表强调是有限的, 线性表元素的个数n...

DWade_Coding ⋅ 2017/11/08 ⋅ 0

zephyr笔记 2.5.1 FIFOs

1 前言 fifo是实现传统先进先出(FIFO)队列的内核对象,允许线程和ISR添加和删除任何大小的数据项。 我正在学习 Zephyr,一个很可能会用到很多物联网设备上的操作系统,如果你也感兴趣,可点...

iotisan ⋅ 05/03 ⋅ 0

SylixOS调试与性能分析技术--内存泄漏检测

1.内存泄漏检测原理 内存泄漏是指程序中已动态分配的堆内存由于某种原因程序未释放或无法释放,造成系统内存的浪费,导致程序运行速度减慢甚至系统崩溃。 SylixOS提供了内存检测方法,可以检...

诸葛一帆丶 ⋅ 2017/11/23 ⋅ 0

Java8 HashMap实现原理探究

前言:Java8之后新增挺多新东西,在网上找了些相关资料,关于HashMap在自己被血虐之后痛定思痛决定整理一下相关知识方便自己看。图和有些内容参考的这个文章:http://www.importnew.com/1659...

任杰LL ⋅ 2016/03/02 ⋅ 0

链表面试题(上)

一、题目 1、从尾到头打印单链表 (有四种方法) 2、删除一个无头单链表的非尾节点(不能遍历链表) 3、在无头单链表的一个节点前插入一个节点(不能遍历链表) 4、单链表实现约瑟夫环(Joseph...

qq_38646470 ⋅ 01/04 ⋅ 0

单双链表练习题

本文是关于链表的一些操作(包括单链表和双向循环链表) 1、单链表,双链表的创建。 2、单链表和双链表的打印。 3、单链表的插入,删除。 4、双链表的插入和删除。 5、单链表的逆置。 6、单链...

qq_38646470 ⋅ 01/27 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

聊聊spring cloud gateway的LoadBalancerClientFilter

序 本文主要研究一下spring cloud gateway的LoadBalancerClientFilter GatewayLoadBalancerClientAutoConfiguration spring-cloud-gateway-core-2.0.0.RELEASE-sources.jar!/org/springfram......

go4it ⋅ 34分钟前 ⋅ 0

详解:Nginx反代实现Kibana登录认证功能

Kibana 5.5 版后,已不支持认证功能,也就是说,直接打开页面就能管理,想想都不安全,不过官方提供了 X-Pack 认证,但有时间限制。毕竟X-Pack是商业版。 下面我将操作如何使用Nginx反向代理...

问题终结者 ⋅ 40分钟前 ⋅ 0

002、nginx配置虚拟主机

一、nginx配置虚拟主机可分为三种方式,分别为: 1、基于域名的虚拟主机,通过域名来区分虚拟主机——应用:外部网站 2、基于端口的虚拟主机,通过端口来区分虚拟主机——应用:公司内部网站...

北岩 ⋅ 43分钟前 ⋅ 0

shell脚本之死循环写法

最近在学习写shell脚本,在练习if while等流程控制时,突然它们的死循环写法是怎么样的?经过百度与亲测记录如下: for死循环 #! /bin/bashfor ((;;));do date sleep 1d...

hensemlee ⋅ 45分钟前 ⋅ 0

苹果的ARKit2.0有多可怕,看了就知道

序言 ARKit主要由三部分组成: 跟踪(Tracking) 跟踪是ARKit的核心组件之一,其提供了设备在物理世界中的位置与方向信息,并对物体进行跟踪,如人脸。 2.场景理解(Scene Understanding) 场...

_小迷糊 ⋅ 46分钟前 ⋅ 0

5.1 vim介绍 5.2 vim移动光标 5.3 ,5.4vim一般模式下移动光标,复制粘贴

vim命令 vim是vi的一个升级版;vim可以显示文字的颜色 安装vim这一个包vim-enhanced 如果不知道安装包,可以使用 命令下面命令来查看vim命令是那个包安装的。 [root@linux-128 ~]# yum prov...

Linux_老吴 ⋅ 50分钟前 ⋅ 0

vim一般模式

vim 是什么 vim是什么 ? 在之前接触Linux,编辑网卡配置文件的时候我们用过了vi ,vim简单说就是vi的升级版,它跟vi一样是Linux系统中的一个文本编辑工具。 如果系统中没有vim ,需要安装一...

李超小牛子 ⋅ 58分钟前 ⋅ 0

docker实战

构建企业级Docker虚拟化平台实战 重点剖析虚拟化和云计算概念; 分析Docker虚拟化的概念和原理; 从0开始实战Docker虚拟化平台; 基于Docker构建Nginx WEB服务器和CentOS虚拟机; 基于开源监...

寰宇01 ⋅ 今天 ⋅ 0

vim介绍、vim颜色显示和移动光标、vim一般模式下移动光标、一般模式下复制粘贴剪切

VIM Vim 是 UNIX 文本编辑器 Vi 的加强版本,加入了更多特性来帮助编辑源代码。Vim 的部分增强功能包括文件比较(vimdiff),语法高亮,全面的帮助系统,本地脚本(Vimscript),和便于选择的...

蛋黄Yolks ⋅ 今天 ⋅ 0

springboot+mockito测试controller层遇到的问题

使用MockitoJUnitRunner测试的一个例子,原来报错无法找到bean, 类似的异常如下:createBeanError..... 原因:是因为@Runwith使用了SpringRunner,应该修改为MockitoJUnitRunner 代码如下: ...

writeademo ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部