欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【线性表】(List)

程序员文章站 2024-01-19 09:58:10
...
本文围绕以下三个部分展开:

一、线性表(List)
二、顺序存储结构
三、链式存储结构






一、线性表(List)

        1. 概念

        线性表:0个或多个数据元素的有限序列。(像线一样性质的表)

            线性表的每个数据元素的类型都是相同的。

            A. 是一个序列。(元素之间是有顺序的,若元素存在多个,则第一个元素无前驱,最后一个元素无后继,其他每个元素都有且只有一个前驱和后继。)

            B. 元素个数是有限的。

【线性表】(List)
            
    
    博客分类: 数据结构 数据结构线性表 


            类比:幼儿园小朋友按次序排队。


        2. 线性表的抽象数据类型

        (1)基本操作:

【线性表】(List)
            
    
    博客分类: 数据结构 数据结构线性表 


        抽象数据类型定义如下:

【线性表】(List)
            
    
    博客分类: 数据结构 数据结构线性表 

【线性表】(List)
            
    
    博客分类: 数据结构 数据结构线性表 


        (2)复杂的个性化操作

        例题:union操作(实现两个线性表集合A和B的并集操作)

        思想:把存在在集合B中但不存在在A中的数据元素插入到A中即可。即:循环集合B中的每个元素,判断当前元素是否存在A中。若不存在,则插入到A中即可。

【线性表】(List)
            
    
    博客分类: 数据结构 数据结构线性表 




二、顺序存储结构

        1. 顺序存储

        指用一段地址连续的存储单元依次存储线性表的数据元素。

【线性表】(List)
            
    
    博客分类: 数据结构 数据结构线性表 



        2. 顺序存储方式

        在内存中找了块地儿,通过占位符的形式,把一定内存空间给占了,然后把相同数据类型的数据元素依次存放在这块空地中。

        使用一维数组来实现顺序存储结构。即:把第一个数据元素存到数组下标为0的位置中,接着把线性表相邻的元素存储在数组中相邻的位置。


        3. 顺序存储结构代码和三个属性

【线性表】(List)
            
    
    博客分类: 数据结构 数据结构线性表 


【线性表】(List)
            
    
    博客分类: 数据结构 数据结构线性表 



        4. 地址计算方法

        存储器中每个存储单元都有自己的编号,称为地址。

        (1)数据元素的序号和存放它的数组下标之间的对应关系:

【线性表】(List)
            
    
    博客分类: 数据结构 数据结构线性表 


        (2)假设一个数据元素占c个存储单元,则第i+1个数据元素的存储位置和第i个数据元素的存储位置的关系:

【线性表】(List)
            
    
    博客分类: 数据结构 数据结构线性表 


        第i个数据元素的存储位置和第1个数据元素的存储位置的关系:

【线性表】(List)
            
    
    博客分类: 数据结构 数据结构线性表 


【线性表】(List)
            
    
    博客分类: 数据结构 数据结构线性表 


        (3)随机存取结构:可以随时算出线性表中任意位置的地址,存取时间复杂度均为O(1),具有这样特点的存取结构称为随机存取结构。


        5. 获得元素的操作(GetElem):将线性表L中第i个位置元素值返回。

【线性表】(List)
            
    
    博客分类: 数据结构 数据结构线性表 

【线性表】(List)
            
    
    博客分类: 数据结构 数据结构线性表 



        6. 插入某个数据元素

【线性表】(List)
            
    
    博客分类: 数据结构 数据结构线性表 


【线性表】(List)
            
    
    博客分类: 数据结构 数据结构线性表 


【线性表】(List)
            
    
    博客分类: 数据结构 数据结构线性表 



        7. 删除某个数据元素

【线性表】(List)
            
    
    博客分类: 数据结构 数据结构线性表 


【线性表】(List)
            
    
    博客分类: 数据结构 数据结构线性表 


【线性表】(List)
            
    
    博客分类: 数据结构 数据结构线性表 
【线性表】(List)
            
    
    博客分类: 数据结构 数据结构线性表 


        8. 优缺点

【线性表】(List)
            
    
    博客分类: 数据结构 数据结构线性表 




三、链式存储结构

【线性表】(List)
            
    
    博客分类: 数据结构 数据结构线性表 


        1. 特点:

        用一组任意的存储单元存储线性表的数据元素。这组存储单元可以连续,也可以不连续。意味着,这些数据元素可以存放在内存中未被占用的任意位置。


        2. 数据域、指针域、指针/链、结点

【线性表】(List)
            
    
    博客分类: 数据结构 数据结构线性表 


【线性表】(List)
            
    
    博客分类: 数据结构 数据结构线性表 



        3. 头结点、头指针

        (1)头指针:链表中第一个结点的存储位置。

        链表最后一个结点的指针为空(NULL/"^")

        (2)头结点:为了更方便地对链表进行操作,在单链表的第一个结点前附设的一个结点。

        数据域可以不存储任何信息,也可以存储如线性表长度等附加信息。

        指针域存储指向第一个结点的指针。

【线性表】(List)
            
    
    博客分类: 数据结构 数据结构线性表 


        (3)二者的异同

【线性表】(List)
            
    
    博客分类: 数据结构 数据结构线性表 



        4. 分类

        链式存储结构又有不同形式,分为:单链表、静态链表、循环链表和双向链表。






整理时重点参考:《大话数据结构》程杰著