0

Image Description

荆文征

Zhidu Inc.


你好,再见

大话数据结构 - 线性表 3

  • 小酒馆老板
  • /
  • 2017/12/29 17:15:0


H2

线性表的定义

线性表,从名字你就能感觉到,是具有像线一样的性质的表。在广场上,有很多人分散在各处,当中有些是小朋友,可能有很多大人甚至有不少宠物,这些小朋友的数据对于整个广场来说不是线性表的结构。但像刚才提到的那样,一个班级的小朋友,一个牵着一个排着队,有一个打头,有一个收尾,当中的小朋友每一个都知道他前面的一个是谁,他后面一个是谁,这样如同有一根线把他们串联起来。就称之为线性表。

线性表(List):零个或者多个数据元素的有限序列

这里需要强调几个关键的地方。

开始写代码了,,,,总觉的这里的代码 有种画蛇添足的感觉,好吧~ 咱们也就是模仿一下~ 看看就好~

首先它是一个序列。也就是说,元素之间是有顺序的,如元素存在多个,则第一个元素无前驱,最后一个元素无后继,其他每个元素都有且只有一个前驱和后继。如果一个小朋友去那两个小朋友后面的衣服,就不可以拍成一对了,同样,如果一个小朋友后面的衣服,被两个甚至多个小朋友拉扯这其实是打架,而不是有序排队。
然后,线性表强调的是 有限的,小朋友班级人数有限,元素个数当然也是有限的。事实上,在计算机中处理的对象都是有限的,那种无限的数列,只存在于数学的概念中。
如果用数学语言来定义。可如下:
若将线性表记为(A1,…,Ai-1,Ai,Ai+1,…,An)则表中Ai-1领先于Ai,Ai领先于Ai+1,称Ai-1是Ai的直接前驱元素,Ai+1是Ai的直接后继元素。当i=1,2,…*n-1,ai有且仅有一个直接后继,当i=2,3,…n时,ai有且仅有一个直接前驱。


Image Description
线性表前驱后继示意图


所以线性表元素的个数n(n>=0)定义为线性表的长度,当n=0时,称为空表。
在非空表中的每一个元素都有一个确定的位置,如A1是第一个数据元素,An时最后一个数据元素,Ai是第i个数据元素,称i为线性表中的位序。
我现在说一些数据集,大家来判断一下是否是线性表。
先来一个大家感兴趣的,一年里的星座列表,是不是线性表呢?


Image Description
线性表星座举例示意图


当然是,星座通常都是白羊大头,双鱼座首位,当中的星座都要前驱和后继,而且一泓也只有十二个,所以他完全符合线性表的定义。
公司的组织架构,总经理管理几个总监,没个总监管理几个经理,没个经理都有各自的下属和员工。这样的组织架构是不是一个线性关系呢?
不是为什么不是呢?哦,因为每一个元素,都有不止一个后继,所以他不是新型表。那种一个总经理只管一个总监,一个总监只管一个经历,一个经历只管一个员工的公司,俗称皮包公司岗位设置等于在忽悠外人。


H2

线性表的抽象数据类型

前面我们已经给了线性表的定义,现在我们来分析以西啊,线性表应该有一些什么样的操作呢?
还是回到刚才幼儿园小朋友的例子,老师为了让小朋友有秩序的出入,所以就考虑给他们拍一个对,并且是长期使用的顺序,这个考虑和安排的过程其实就是一个线性表的创建和初始化过程。
一开始没经验,把小朋友排好队后,发现有的高有的爱,队伍很难看,于是就让小朋友解散重新拍—这是一个线性表表重置为空表的操作。
拍好了对,我们随时可以叫队伍某一个小朋友的名字一踏的具体情况。比如有家长问,队伍里的第五个孩子,怎么这么调皮,他叫什么名字呀?傲视可以很快的告诉这位家长,这就是风清扬的儿子,叫做风云变。我在旁边就非常扭捏,看来是我给儿子的名字没取好,儿子让班级风云突变了。这种可以根据位序得到数据元素也是一种很重要的线性表操作。
还有什么呢,有时我们想知道,某个小朋友,比如麦兜是否是班里的小朋友,老师会告诉我说,不是,麦兜在春天花花幼儿园,不在我们幼儿园。这种查找某个元素是否存在的操作很常用。
而后有家长问老师,办理现在到底有多少个小朋友呀,这种获得线性表长度的问题也很普遍。
显然对于一个幼儿园来说,加入一个新的小朋友到队列中,或因某个小朋友生病,徐耀一处某个位置,都是很正常的情况,对于一个线性表来说,插入数据和删除书句都是必须的操作。
所以线性表的抽象数据类型定义如下:

protocol List{

    /// 初始化操作,建立一个空的线性表
    ///
    /// - Returns: List 对象
    static func InitList() -> List

    /// 若线性表为空,返回true,否则返回false
    ///
    /// - Returns: 是否
    func ListEmpty() -> Bool

    /// 将线性表清空
    func ClearList()

    /// 将线性表数据的第i个元素位置返回
    ///
    /// - Parameter i: 位序
    /// - Returns: 数据元素
    func GetElem(i:Int) -> Any?

    /// 在线性表中查重和e相同的元素,如果查找成功,返回该元素在表中序号表示成功;否则返回-1表示失败。
    ///
    /// - Parameter e: 数据元素
    /// - Returns: 位序 -1 为无数据
    func LocateElem(e:Any) -> Int

    /// 在线性表L中的第i个位置插入新元素e
    ///
    /// - Parameters:
    ///   - i: 位序
    ///   - e: 数据元素
    /// - Returns: <#return value description#>
    func ListInsert(i:Int,e:Any)

    /// 删除线性表中的第i个位置元素,并用返回其值
    ///
    /// - Parameter i: 位序
    /// - Returns: 返回被删除的元素
    func ListDelete(i:Int) -> Any?

    /// 返回线性表的元素个数
    ///
    /// - Returns: 元素个数
    func ListLength() -> Int
}

对于不同的应用,线性表的基本操作是不同的,上述操作是最基本的,对于实际问题中涉及到的关于线性表的更复杂操作,完全可以用这些基本操作的组合来实现。
比如,要实现两个线性表集合A和B的并集操作。即使要使得集合A=A∪B。说白了,就是把存在集合B中的但并不存在A中的元素插入到A中即可。
仔细分析一下这个操作,发现我们只要循环集合B中的每一个元素,判断当前元素是否存在A中,如不存在,则插入到A中即可。思路是很容易想到的。

/// 其中 ListClass 为 List 协议的实现
func union(la: ListClass,lb: ListClass){

    let lalen = la.ListLength()
    let lblen = la.ListLength()

    let list  = ListClass.InitList()

    for i in 0...lblen{

        let e = lb.GetElem(i: i)
        if la.LocateElem(e: e) == -1 {
            la.ListInsert(i: lalen+i, e: e)
        }
    }
}

这里,我们对于union操作,用到前面线性表基本操作 ListLength,GetElem,LocateElem,ListInsert等,可见对于复杂的个性化的操作,其实就是把基本操作组合起来实现的。


H2

线性表的顺序存储结构


H3

顺序存储定义

说这么多的线性表,我们来看看线性表的两种物理结构的第一种–顺序存储结构。

线性表的顺序存储结构,指的是用一顿地址连续的存储单元一次存储线性表的数据元素。

线性表(A1,A2,…,An)的顺序存储示意图如下:


Image Description
线性表顺序存储示意图


我们在第一节课时,已经讲过顺序暑促存储结构。今天我们再举一个例子。
记得大学时,我们同宿舍的有一个同学,热特别老实,热心,我们时常会让他帮我们去图书馆占座,他总是答应,你想想,我们一个宿舍连她一起共有几个人,这其实明白这是欺负人的事。他每次一吃完早饭就冲去图书馆面条一个好地儿,把它的书包里的书,一本本的按座位放好,若书包里的树不够,他会把它的饭盒,水杯,水笔都用上,常常一排,九个座硬是被他占了,后来又一次因占座的事儿差点都要打架。


Image Description
占位说明示意图


H3

顺序存储方式

线性表的顺序存储结构说白了,和刚才的例子一样,就是在内存中找了块地儿,通过占位的方式,吧一定内存空间给占了,然后把相同数据类型的数据元素一次存放在这块空地种。既然线性表的每个数据元素的类型,都相同,所以可以用C的以为数组来实现顺序存储结构,即把第一个元素存到数组下表为0的位置,就表示从这开始,这地方归我了。为了建立一个线性表,要在内存中找一块地儿,于是这块地额第一个位置就非常关键,他是存储空间的其实位置。
接着,因为我们一共几个人,所以它需要占九个座,在线性表中,我们估算这个线性表的最大存储容量,建立一个数组,数组的长度就是这个最大存储容量。
可现实中,我们宿舍总有那么几个不是很好学的人,为了游戏没了恋爱,就不去图书馆自习了。假设我们就个人,去了六个,真正被使用的座位,也就只是六个,另外三个是空的。同样的,我们已经有了其实的位置,也有了最大的容量,于是我们就可以在里面增加数据了,随着数据的插入,我们线性表的长途开始变大,不过线性表的当前长度不能超过存储容量,即数组的长度。想想也是,如果我们有10个人,只占了九个组,自然是坐不下的
来看线性表的顺序存储的结构代码

struct ListClass: List {

    /// 数组元素类型根据实际情况而定,这里假设为 Int
    typealias T = Int

    /// 存储空间初始化分配量
    var MAXSIZE = 20

    /// 数组存储数据元素,最大值为MAXSIZE
    var data:[T] = []
    /// 线性表的长度
    var length = 0
}

这里,我们就发现描述顺序存储结构需要三个属性:

  • 存储空间的起始位置: 数组 data,他的存储位置就是存储空间的存储位置。
  • 线性表的最大存储容量: 数组长度MAXSIZE
  • 线性表的当前长度: length

H3

数据长度与线性表长度区别

注意哦,这里有两个概念,“数组的长度”和“线性表的长度”徐耀区分一下。
数组的长度是春芳线性表存储空间的长度,存储分配后这个粮食一般不变的。有个别的同学可能会问,数组的大小一定不可以变吗?我怎么看到有书中谈到可以动态分配一组数组。是的,一般高级语言,比如C,VB都可以用编程手段实现动态分配数组,不过这会带来性能上的损耗。
线性表的长度是线性表中元素的个数,随着闲心表插入和删除操作的进行,这个是变化的。
在任一时刻,线性表的长度应该小于等于数组的长度。


H3

地址计算方法

由于我们数数都是从1开始树数的,线性表的定义也不能免俗,其实也是1,可C语言中的数组却是从0开始作为第一个下表的,于是线性表的第i个元素要存储在数组下表为i-1de位置。即数据元素的需要和存放他的数组下表之间存在对应关系


Image Description
数组长度关系示意图


用数组存储顺序表意味着要分配固定长度的数字空间,由于线性表中可以进行插入和删除操作,因此分配的数组空间,由于线性表中可以进行插入和删除操作,因此分配的数组空间大于等于当前性表的长度。
其次,内存中的地址,就喝图书馆和电影院的祖伟一样,都是有编号的。存储器中的每个存储但愿都有自己的编号,这个编号成为地址。当我们占座后,占多的第一个位置确定后,后面的位置都是可以计算的。试想一下,我们班级成绩第五名,我们后面的10名同学成绩名次是多少呢?当然是6,7.。。15,因为5+1,+5+2,,,+5+10.由于每个数据元素,不管他是整型,实型还是字符型,他都需要一定的存储空间的。假设占用的是C个存储单元,那么线性表中第i+1个数据元素的存储位置和第i个数据元素的存储位置满足下列关系(LOC表示获得存储位置的函数)。

LOC(ai+1) = LOC(ai)+c

所以对于第i个数据元素Ai的存储位置可以有A1推送得出:

LOC(Ai)=LOC(Ai)+(i-1)*c

从图来理解:


Image Description
元素位置示意图


通过这个公式,你可以随时酸楚线性表中任意位置的地址,不管他是第一个还是最后一个,都是相同的时间。那么我们对每个线性表位置的存入和去除数据,对于计算机来说都是相等的时间,也就是一个常数,因此用我们算法中学到的时间复杂度的感念来说,她的去存时间性能为O(1).我们通常把具有这一特点的存储结构称为随机存取结构。


H2

顺序存储结构的插入与删除


H3

获得元素操作

对于线性表的顺序存储结构来说,如果我们要实现GetElem操作,即将线性表第i个位置元素返回,其实是非常简单的。就程序而言,只要i的树枝在数组下标范围内,就是把数组第i-1下表的只返回即可。来看代码:

func GetElem(i:Int) -> Any?{

    if self.data.count == 0 || i < 0 || i >= self.data.count {
        return nil
    }
    return self.data[i]
}

H3

插入操作

刚才我们也谈到,这里的时间复杂度为O(1)。我们现在来考虑,如果我们要实现 ListInsert(i,e),即在线性表中的第i个位置插入新元素,应该如何操作?
举个例子,本来我们在春运是去买火车票,大家都排队排的好好的。这时来了一个咩女,对着队伍中排在第三位的你说,“大哥,求求你帮帮忙,我家母亲有病,我得急着回去看她,着队伍这么长,你可否让我排在你的前面嫩?”你心一软,就同意了。这是你必须后退一步。否则他是没法进到队伍来的这可不得了,后面的人像蠕虫一样,全部都得退后一步没否则他就没法进到队伍来的。这可不得了,后面的人像蠕虫一样没全部都得退一步。骂声四起。但后面的人,也不清楚这加塞是怎么回事儿,没什么办法。


Image Description
数据结构插入操作示意图


插入算法的思路:

  • 如果插入位置不合理,抛出异常;
  • 如果线性表长度大于等于数组长度,则抛出异常或动态增加容量;
  • 从最后一个元素开始向前编导第i个位置,分别将他们向后移动一个位置;
  • 将要插入元素填入位置i处;
  • 表长加1

H3

删除操作

接着刚才的例子。此时后面排队的人群y一件都很大,都说怎么可以这样,不管什么原因,插队就是不行,有本事,找火车站开后门去。就在这时,远处跑来一胖子,对着这么美女喊,可找到你了,你这个骗子,还我钱。只见这女子,二话没说门突然就冲出了对了,胖子追在其后,消失在人群中。哦,原来他是倒卖火车票的黄牛,刚才还装可怜,于是排队的人群,又像蠕虫一样,均相亲移动了一步,骂声渐息,队伍又恢复了平静。
这就是线性表的顺序存储结构删除元素的过程。


Image Description
线性表删除操作示意图


删除算法的思路:

  • 如果删除位置不可理,抛出异常
  • 去除删除元素
  • 从删除元素位置开始便利到最后一个元素位置,分别将他们都向前移动一个位置
  • 表长减1

现在我们来分析一下,插入和删除的时间复杂度。

先来看最好的情况,如果元素要插入到最后一个位置,或者删除最后一个元素,此次时间复杂度为O(1),因为不徐耀移动元素的,就如同来了新人要正常排队,当然是排在最后,如果此时他又不想排了,那么他一个人离开就好了,不影响任何人。
最坏的情况呢,如果元素要插入到第一个位置或者删除第一个元素,此时时间复杂度是多少呢?那就意味着要移动所有的元素向后或者向前,所以这个时间复杂度为O(n)。
至于平均的情况,由于元素插入到第i个位置或删除地i个元素,徐耀移动n-i个元素。根据概率远离,没个位置插入或删除元素的可能性是相同的,也就说位置靠前,移动元素多,位置考后,移动元素少,最终移动次数为 (n-1)/2。
我们前面的讨论过时间复杂度的推导,可以得到,平均时间复杂度还是O(n)。
这说明什么?线性表的顺序存储结构,在存,度数据时,不管是那个位置,时间复杂度都是O(1);在插入或删除时,时间复杂度都是O(n).这都说说明,他比较适合元素个数不太变化,而更多的是存取数据的应用。当然,它的优缺点还不止这些….


H3

线性顺序存储结构的优缺点

我就一展示数据的表格
优点 缺点
无须为表示表中元素之间的逻辑关系而增加额外的存储空间 插入和删除操作需要移动大量元素
可以快速的存取表中任一位置的元素 当线性表长度变化较大时。难以确定存储空间的容量
- 造成存储空间的“碎片”

H2

线性表的链式存储结构


H3

顺序存储结构不足的解决办法

前面我们讲的线性表的顺序存储结构。他是有缺点的,最大的缺点就是插入和删除时需要移动大量元素,这显然就需要耗费时间。能不能想办法解决呢?
要解决这个问题,我们就得考虑一下导致这个问题的原因。
为什么当插入和删除时,就徐耀大量元素,仔细分析后,发现原因在于相邻的两元素的存储位置也具有邻居关系。他们编号是1,2,3…,n,他们在内存中的位置也是挨着的,中间没有空隙,当然就无法快速介入,而删除后,当中就会滤除空隙,自然需要弥补。问题就出在这里。
我们反正也是要让相邻元素留有足够余地,干脆所有的元素都不要考虑相邻位置了,哪有空位就到哪里,而只是让每一个元素都知道他的下一个元素位置在哪里,这样我们可以在找到,这样,我们可以在第一个元素时,就知道第二个元素的位置,而找到他。


H3

线性表链式存储结构定义

在解释这个思路之前,我们先来谈另一个话题。前几年,有一本书风靡了全世界,他叫《达芬奇密码》,成为世界上最畅销的小说之一,树的内容集合了侦探,惊悚和阴谋论等多种风格,很好看。
我犹豫看的时间太贵于救援,情节都忘的差不多了,不过这本书和绝大部分侦探小说一样,都是同一种处理办法。那就是,作者不会让你实现知道整个过程的全部,而是在一步步的到达某个环节,才根据现场的信息,获得或推断出下一步是什么,也就说,每一步出了对侦破的信息进一步确定外(之前信息也不一定都是对的,有时就是证明某个信息不正确),还有就是对下一步如何操作或行动的指引。
不过这个例子也不完全与线性表相符合。因为侦破的限速可能是错综复杂的,有点像我们之后要讲到的树和图的数据结构。今天我们要谈的就是单线索,五分制的情况,即线性表的链式存储结构。
线性表的链式存储结构的特点是用一组人以的存储单元存储线性表的数据元素,这组存储单元可以是连续的,也可以是不连续的。不就意味着这些数据元素可以存在内存未被占用的任意位置


Image Description
线性表链式存储结构示意图


以前在顺序结构中,每个数据元素只徐耀村数据元素信息就可以了。现在链式结构中,除了窑村数据元素信息外,还要存储他的后即元素的存储地址。
因此,为了表示每个数据元素A1与其直接后需数据元素Ai+1之间的逻辑关系,对数据元素A1来说,除了存储其本身的信息之外,还徐耀存储一个指示器直接后需的信息(即直接后即的存储位置)。我们把存储数据信息的域成为数据域,把存储直接后继位置的域成为指针域。指针域存储的信息被称为指针或链。这两部分信息组成数据Ai的存储印象,成为结点(Node)。
n个结点(A1的存储印象)连接成一个链表,即为线性表的链式存储结构,因为次链表的每个节点斗志包含一个指针与,所以叫做 单链表。单链表正是通过每个节点的指针域将线性表的数据元素按期逻辑次序连接在一起。


Image Description
线性表链式结构存储示意图


对于线性表来说,但得有个头有个尾,链表也不例外。我们把链表中第一个节点存储位置叫做头指针,那么整个链表的存储就必须是从头指针开始进行了。之后的每一个结点,他的指针指向哪里?
最后一个,当然就意味着直接后继不存在了,所以我们桂东,线性链表的最后一个结点指针为“空”(通常用NULL或”^”符号来表示)


Image Description
线性表链式存储头指针和空指针示意图


有时,我们为了更加方便的对链表进行操作,会在单链表的第一个节点前附设一个结点,成为头结点。头节点的数据域可以不存储任何信息,谁脚踏实地一个呢,有这个特权。也可以存储如线性表的长度等附加信息,头结点的指针与存储只想第一个节点的指针。


Image Description
头结点示意图


H3

头指针与头节点的异同

我就一展示数据的表格
头指针 头结点
头指针是指链表指向第一个结点的指针,若链表有头结点,则是指向头结点的指针 头结点是为了操作的统一和方便而设立的,放在第一个元素结点之前,其数据与一般无意义(也可存放链表的长度)
头指针具有表示作用,所以常用头指针冠以链表的名字 有了头结点,对在第一元素结点钱插入结点和删除第一结点,其操作与其结点的额操作就统一了
无论链表是否为空,头指针均不为空。头指针是链表的必要元素 头结点不一定是链表必须要素

H3

线性表链式存储结构代码描述

若线性表为空表,则头结点的指针域为“空”


Image Description
不好的空链示意图


这里我们大概的用图示表达了内存中单链表的存储状态。看着满途的省略号“…… ”,你就知道是多么不方便。而我们真正关心的额:他是在内存中的实际位置吗?不是的,这只是他所表示的线性表中的数据元素雨数据元素之间的逻辑关系,所以我们该用更方便的存储示意图来表示单链表


Image Description
链表新的存储示意图


如带有头结点的单链表表示为:


Image Description
头结点链表表示示意图


空链表表示为:


Image Description
空链表表示示意图


H2

单链表的读取

在线性表的顺序存储结构中,我们要计算任意一个元素的存储位置是很容易的。但在单链表中,由于第i个元素到底咋哪儿?没办法一开始就知道,必须得从头开始找。因此,对于单链表实现第i个元素的数据操作getElem,在算法上相对于要麻烦一些。
获得链表地第i个数据的算法思路:

  1. 声明一个结点p指向链表第一个节点,初始化j从1开始
  2. 当j<i时,就便利链表,让p的指针向后移动,不断指向下一个结点,j累加1
  3. 若是链表末尾p为空,则说明第i个元素不存在
  4. 否则查找成功,返回结点p的数据

说白了,就是从头开始找,知道第i个元素为止。由于这个算法时间复杂度取决于i的为止,当i=1,则不需要遍历,第一个就去除数据了,而当i=n是则遍历n-1次。因此最最坏情况的额时间复杂度是O(n)。
由于单链表的结构中没有定义表厂,所以不能实现知道要循环多少次,因此也就不方便是哟个for循环来控制循环。其主要核心思想就是“工作指针后移”,这其中也是很多算法的常用技术。
此时就有人说,这么麻烦,这数据结构有什么意思!还不如顺序存储结构呢?
哈,世界万物总是有两面的,有好自然有不足,有差自然就有优势。下面我们来看以下单链表中的如何实现“插入”和“删除”的吧。


H2

单链表的插入与删除


H3

单链表的插入

算法思路

  1. 声明一结点P只想链表第一个节点,初始化j从1开始
  2. 当j<i时,就遍历链表,让p的指针向后移动,不断指向下一结点,j累加1
  3. 若到链表末尾p为空,则说明第i个元素不存在
  4. 否则查找成功,在系统生成一个空结点s
  5. 将数据元素e赋值到s的数据域
  6. 单链表的插入标准语句 s->next=p->next p->next=s
  7. 返回成功

H3

单链表的删除

算法思路

  1. 声明一结点P只想链表第一个节点,初始化j从1开始
  2. 当j<i时,就遍历链表,让p的指针向后移动,不断指向下一结点,j累加1
  3. 若到链表末尾p为空,则说明第i个元素不存在
  4. 否则查找成功,将要删除的结点p->next复制给q
  5. 单链表的删除标准语句 p->next=q->next
  6. 将q结点的数据复制给e,作为返回
  7. 释放q结点
  8. 返回成功

分析一下刚才我们讲解的单链表的插入和删除算法,我们发现,他们其实都是由两部分组成的。第一部分就是遍历查第i个元素;第二个部分就是插入和删除元素。
从整个算法来说,我们很容易就推导处,他的时间复杂度都是O(n)。如果在我们不知道第i个元素的指针为止,单链表数据结构在插入和删除操作上,与线性表的顺序存储结构没有什么太大的有时。但如果我们希望从i为止插入10个元素,对于顺序结构存储就意味着,每一次插入都需要移动n-1个元素每次都是O(n)。而单链表,我们只需要第一次是,找到第i个位置的指针,此时为O(n),接下来只是简单的通过复制移动指针而已,时间复杂度都是O(1).显然对于插入或删除数据越频繁的操作。单链表的效率优势越是明显。


H2

单链表的正表创建

回顾一下,顺序存储结构的创建了其实就是一个个数组的初始化,即声明一个类型和大小的数组并复制的过程。而单链表和顺序存储结构就不一样,他不像顺序存储结构那么集中,它可以很散,是一种动态结构。对于每个链表来说,他所占用的空间的大小和位置是不是需要预先分配划定的,可以根据俄系统的情况和实际的需求即时生成。
所以创建单链表的过程就是一个动态生成链表的过程。即从“空表”的初始状态其,依次建立个元素结点,并出个插入链表。
单链表正表创建的算法思路:

  1. 声明一结点p和计数器变量i
  2. 初始化一空链表L
  3. 让L的头结点的指针指向NULL,即建立一个戴头结点的单链表
  4. 循环:
    • 生成一新结点复制给P
    • 随机生成艺术字复制给P的数据域p->data
    • 将p插入到头结点与新结点之间
      H2

      单链表的正表删除

  5. 声明一结点配合q
  6. 将第一个节点复制给p
  7. 循环:
    • 将下一结点复制给q
    • 释放p
    • 将q复制给p
      H2

      单链表的结构与顺序结构的优缺点

我就一展示数据的表格
存储分配方式 时间性能 空间性能
顺序存储结构用一段连续的存储单元依次存储线性表的数据元素 查找
1.顺序存储结构O(1)
2.单链表O(n)
顺序存储结构需要预分配存储空间,分大了,浪费,分销了易发生上溢
单链表采用链式存储结构,用一组人以的存储单元存放线性表的元素 插入和删除
1.顺序存储结构徐耀平均移动表长一半的元素,时间为O(n)
2.单链表再找出某位置的指针后,插入和删除时间为O(1)
单链表不徐耀分配存储空间,只要有就可以分配,元素个数也不受限制

通过上面的对比,我们可以得出一些经验性的结论:

  • 若线性表需要频发查找,很少进行插入和删除操作时,宜采用顺序存储结构。如需要频繁插入和删除时,宜采用单链表结构。比如说游戏开发中,对于用户注册的个人信息,除了注册时插入数据外,绝大属情况都是读取,所以应该考虑用顺序存储结构,而游戏中的玩家的武器或者装备列表,随着玩家的游戏过程中,可能会随时增加或删除,此时在用顺序存储就不太合适了,单链表结构就可以大展拳脚。当然,这只是简单的类比,现实中的软件开发,要考虑的问题会复杂的多。
  • 当线性表中的元素个数变化较大或者根本不知道有多大时,最好用单链表结构,这样就不徐耀考虑存乎空间的大小问题。而如果实现知道线性表的大大只长度,比如一年12个月,一周就是星期一至星期日共七天,这种用顺序存储结构效率会高很多。

总之,线性表的顺序存储结构和单链表结构各有其优缺点,不能简单的说哪个好,那个不好,需要根绝实际情况,来综合平和采用哪种数据结构更能满足和达到需求和性能。


H2

静态链表

其实C语言真是好东西,它具有的指针能力,使得它可以非常容易的操作内存中的地址和数据,这比其他高级语言更加灵活方便。后来的面向对象语言,虽不是用指针,但因为启用对象引用机制,从中角度也间接的实现了指针的某些作用。但对于一些语言,早起的高级语言,由于没有指针,链表结构按照咱们前面的讲法,就诶发实现了,怎么办呢?
有人就想出来用数组来代替指针,来描述单链表。真是不得不佩服他们的智慧,我们来看看他是怎么做到的。
首先我们让数组的元素都是由两个数据域组成,data和cur。也就是说,数组的每个下表都对应一个data和一个cur。数据域data,用来存放数据元素,也就是通常我们要处理的数据;而游标cur相当于单链表中的next 指针,存放钙元素的后继在数据的下标。
我们把这种用数组描述的链表称为静态链表,这种描述方法还有起名叫做游标实现法。
为了方便我们插入数据,我们通常会把数组建立的大一些,一边有一些空闲空间可以边鱼插入时不至于溢出。

另外我们对数组第一个和最后一个元素作为特殊元素处理,不村数据。我们通常把未被使用的数组元素成为备用链表。而数组第一个元素,记下标为0的元素的cur就存放备用链表的第一个结点的下标。而数组的最后一个元素的cur则存放第一个有数据的元素的下标,相当于单链表中的头结点作用,当整个链表为空时,则为0。

加入我们已经讲数据存入静态链表,比如分别存放着“甲”,“乙”,“丁”,“戊”,“己”,“庚”等数据,则如下:


Image Description
静态链表演示图


此时,“甲”这里就存又有下一个元素的“乙”的游标2,“乙”则存有下一个元素“丁”的游标3。而“庚”作为最后一个有值元素,所以他的cur设置为0.而最后一个元素的cur,则因为前七个都有值,设置为 第一个无值的游标 7.


H3

静态链表的插入操作

个人理解:

  1. 首先检测是否还有空闲的数组位置,如果没有数组已经满了
  2. 根据最后一个元素的cur获取到一个可以被赋值的游标位置
  3. 获取cur为0的游标的数据 将cur 设置为 可以被复制的游标
  4. 赋值 并且将cur 设置为 0

H3

静态表的删除操作

  1. 首先找到到需要删除的位置数据
  2. 将头结点的的cur 设置为 该数据的 cur
  3. 将该值的cur 设置为 第一个可复制的cur 并将可以被赋值的cur 设置为该游标

H3

静态链表优缺点

我就一展示数据的表格
优点 缺点
在插入和删除的操作时,只需要修改游标,不徐耀移动元素,从而改进了在顺序存储结构中的插入和删除操作需要移动大量的缺点 没有解决连续存储空间带来的表长难以确定的问题
失去了顺序存储结构随机存取的特性

总的来说,静态链表其实是为了给没有指针的高级语言设置的一种实现单链表能力的方法。尽管大家不一定会用得上,但这样的额思考方式是非常巧妙的,应该理解其思想,以备不时之需。


H2

循环链表

对于单链表,由于每个节点只存储了向后的指针,到了为标志就停止了向后脸的操作,这样,当中某一结点就无法找到他的前驱结点了,就像我们刚才说的,不能回到从前。

将单链表中终端结点的指针短有空指针改为指向头结点,就是整个单链表形成一个环,这种头尾想接的单链表成为但循环链表,建成循环链表(circular linked list)。



Image Description
头指针单循环链表




Image Description
尾指针单循环链表


H2

双循环链表

双循环链表就是,每一个数据不仅知道他的后继是什么,还知道自己的前驱是什么。



Image Description
头指针双循环链表


H2

总结回顾

这一章,我们主要讲的是线性表。
先谈了他的定义,线性表是零个或多个具有相同类型的数据元素的有限序列。然后谈了线性表的抽象数据类型,如他的一些基本操作。
之后我们就线性表的两大结构做了讲述,先讲了是比较容易的顺序存储结构,值的是用一顿地址连续的存储单元依次存储线性表的数据元素。通常我们都是用数组来实现这一结构。
后来是我们的重点,有舒徐存储结构的插入和删除操作不方便,引出了链式存储结构,它具有不受古丁的存储空间限制,可以比较快捷的插入和删除操作的特点。然后我们分别就链式存储结构的不同形式,进行了讲解。另外我们还讲解了 如何不是用指针来实现链表的 静态链表。


Image Description
总结

专栏: 数据结构
标签: 数据结构 计算机基础