文档章节

3.1 单链表

沐浴星光
 沐浴星光
发布于 2015/06/04 16:56
字数 1827
阅读 31
收藏 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
0
数组和链表结构(python)_2

本文内容目录如下,会分拆为两篇笔记,另一则笔记是 "数组和链表结构(python)_1"。 3. 链表结构 Linked Structures 在数组之后,链表结构可能使程序中最常用的数据结构。 3.1 单链表结构和双...

曾翔翔
07/28
0
0
数据结构与算法-C语言篇6-线性表之链式存储结构

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

香沙小熊
01/07
0
0
数据结构和算法之一——线性表_3_链式存储结构_1_单链表

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

Eric_Hunter
01/11
0
0
Java实现链表面试题

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

火力全開
2016/10/09
13
0

没有更多内容

加载失败,请刷新页面

加载更多

基于 Docker 快速部署多需求 Spark 自动化测试环境

引言 在进行数据分析时,Spark 越来越广泛的被使用。在测试需求越来越多、测试用例数量越来越大的情况下,能够根据需求快速自动化部署 Spark 环境、快速完成所有测试越来越重要。 本文基于 ...

呐呐丶嘿
10分钟前
0
0
支付宝APP支付之查看支付宝商户ID

1、登录支付宝蚂蚁金服开放平台 2、查看账号详情,选择合作伙伴管理,账户管理,查看角色身份,此处的PID就是商户ID 3、点击秘钥管理,可查看绑定的相关应用及其APPID等信息

Code辉
13分钟前
0
0
崛起于Springboot2.X之通讯WebSocket(40)

技术简介:Springboot2.0.3+freemaker+websocket 1、添加pom依赖 <dependencies> <dependency> <groupId>org.springframework.boot</groupId> <artifactId>spring-bo......

木九天
22分钟前
1
0
Java常用四大线程池用法以及ThreadPoolExecutor详解

为什么用线程池? 1.创建/销毁线程伴随着系统开销,过于频繁的创建/销毁线程,会很大程度上影响处-理效率 2.线程并发数量过多,抢占系统资源从而导致阻塞 3.对线程进行一些简单的管理 在Java中...

孟飞阳
24分钟前
1
0
Netty+Websocket 实现一个简易聊天室

后台代码 /** * 服务端 */public class ChatServer {public static void main(String[] args) throws Exception {int port=8080; //服务端默认端口new ChatServer().bind...

这很耳东先生
25分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部