线性表和链表的区别：每个元素都是单个元素，这句话是什么意思？

来源：蜘蛛抓取(WebSpider) 时间：2022-10-14 19:54 标签： 线性表和链表的区别

线性表可以看成是广义表的特例，如果广义表中的每个元素都是原子，则广义表便成为线性表。

题王网让考试变得更简单

扫码关注题王，更多免费功能准备上线！

　　一个线性表是是n个数据元素的有限序列，有以下定义：

　线性表是零个或者多个数据元素的集合

　线性表中的数据之间是有顺序的

　线性表中的数据元素是有限的

　线性表中的数据元素的类型必须相同

　　线性表的一些常用操作：

　　这些都是线性表的一些基础知识，线性表还有好些操作，当然相关命名也是可以变得 ，在后面的线性表的顺序存储结构和线性表链式存储结构中会运用到这些，下面来介绍一下线性表的顺序存储结构。

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

　　在C语言中，可以用一维数组来实现顺序存储结构。存储空间的起始位置：数组node;线性表的最大容量：数组长度MAXSIZE；线性表的当前长度：length。。可表示如下:

　　获取元素操作算法如下：

5 //判断线性表是否合法 6 //判断位置是否合法
3 //判断线性表是否合法 7 //判断插入位置是否合法 18 //从最后一个元素开始到第pos个位置 19 //分别将他们都向后移动一个位置 25 //将新元素插入
6 //判断线性表是否合法 7 //判断删除位置是都合法 10 //取出删除元素 13 //把删除位置pos后的元素分别向前移动一个位置

　　这种方法无需为线性表中的逻辑关系增加额外的空间，可以快速的获取表中合法位置的元素，但是插入和删除元素的草种需要移动大量的元素，当线性表长度变化较大时难以确定存储空间的容量。

　　为了表示每个元素与其直接后继元素之间的逻辑关系，每个元素除了本身的信息之外，还需要存储指示其直接后继的信息，这就是链式存储。　　

　　在Ｃ语言中可以用结构体来定义链表中的指针域，链表中的表头结点也可以用结构体来实现，代码如下：

　　获取第pos个元素操作

2 //判断线性表是否合法 3 //判断位置是否合法 7 //由表头开始通过next指针移动pos次后，当前元素的next指针即指 向要获取的元素

　　插入元素到位置pos的算法

2 //判断线性表是否合法 3 //判断插入位置是否合法 6 //由表头看似hi通过next指针移动pos次后，当前元素的next指针即指向要插入的位置

　　删除第pos个元素的算法

2 //判断线性表是否合法 3 //判断插入位置是否合法 16 //将第pos个元素从链表中删除

　　链式结构无需一次性定制链表的容量并且插入和删除操作无需移动数据元素，但是数据元素必须保存后继元素的位置信息，获取指定数据的元素操作需要顺序访问之前的元素。

线性结构的基本特点：除第一个元素无直接前驱，最后一个元素无直接后继，其他元素都有一个前驱和一个后继。

说人话就是：第一个元素不能向前访问，最后一个元素不能向后访问，中间的元素都可以前后访问其他元素。

虽然该线性表中数据元素各不相同，但每个元素都具有相同的特性，都属于同一数据对象

线性表：由有限个数据特性相同的数据元素构成的有限序列

如果没有数据元素，该线性表也叫空表。

1，存在唯一 一个“第一个”与“最后一个”数据元素
2，出第一个和最后一个数据元素，其余元素都有一个前驱和一个后驱
解释一下：前驱和后继就是逻辑关系中的上一个元素和下一个元素
我原先以为是指针之类的。

线性表的长度可以根据需要增长或减小。还拥有任意位置的插入和删除
线性表分为顺序表和链表

线性表的顺序存储就是顺序表，是指**一组地址连续的存储单元依次存储的数据元素。**实际就是每个元素都是依次储存在地址连续的空间（简称：数组）。对于顺序存储而言，逻辑上是连续的，其物理次序上也是连续的

来看一张图增强一下理解（这是我写顺序存储的习惯，可能会存在差异）

对于线性表的顺序存储的而言，每个数据元素都可以通过下标来快速访问，读取。正规来说就是随机存取

这是我对顺序存储的结构体类型的定义 

 sel* arr;//动态开辟的线性表空间的首地址，通过这个指针访问到线性表空间
 int size;//当前已经使用了的空间的个数

这里我为了简单一些描述，我直接使用了每个数据元素都相当于只有int 类型的数据项。

其实就是跟通讯录一样，每个数据元素都是一个人的全部信息的集合（应该可以这么说吧），而数据项就是每个元素中包含的一部分。

对于顺序表来说，绝大部分可以当成数组进行操作，当然，也就是要考虑顺序的容量问题，是否需要扩容的几个动态变化问题。 

 a->size = 0;//数组元素以0开始计算,size是最后一个元素的下标，不是元素总数量


  

  

    扩容是当准备对顺序表的元素进行操作时元素个数已经达到最大容量时，由于我们的size是下标，就要加一。因为我们准备扩容，所以是不会允许size>=capacity。

    同时，扩容不能一次性扩太多，否则或导致空间浪费。

    又不能扩太少，少了就要多次扩容，会增加消耗。

    所以，自己看情况吧。嘻嘻~
  

  

    

  

  

    

  

  

    尾插法没那么复杂，检查一下扩容，直接在后面放入元素就行。

    下面我就不再举例了，举一反三很容易的。
  

  

    
 


  

  

    头插法就需要将放入位置后的元素全部向后移动一个位置。

    但是，怎么移又是要考虑一下的问题。
  

  

    是从前向后开始移动，还是从最后一个元素开始移动。
  

  

    会造成这个样子，后面元素就一直是1，则，这种方法就是错误的。
  

  

    这种方法是可以行的通的。

    再元素向后移，再头插。
  

  

    
 


  

  

    删除就不头删尾删了，直接任意位置删除。
  

  

    找到那个元素的下标，再开始向前覆盖

    对于删除而言，元素移动又是一个麻烦事。

    这次我们对于删除而言，元素得从前向后开始移动。
  

  

    

  

  

    删除后要将边界也就是size自减，防止越界。
  

  

    传要添加的位置，再开始向后移动。
  

  

    

  

  

    其实就是头插法的一种变形。
  

  

    对于数组删除元素，要从前向后开始移动。

    而对于数组增加元素，要从后向前开始移动。

    同时删除添加的位置都要符合条件，不能越界。
  

  

    该存储结构的存储特点是：用一组任意的存储单元存储线性表的数据元素。（这组存储单元可以是连续的也可以是不连续的，简称：随机分布的存储单元）
  

  

    而每个分配到存储单元都要分为两个部分：数据域与指针域。

    这两个域或者信息组成数据元素的存储映像。是逻辑层次的元素在物理层次的投影。也叫结点。
  

  
    
    
  • 数据域：储存每个数据元素，包括各个数据项
    
    • 
    
  • 指针域：储存一个指针，也就是下一个结点的地址
    
    • 
  

  

    注意，链式储存也就是链表，其每个结点的地址都是随机的，并不是像顺序表一样，每个空间依次排列。
  

  

    链表有超多种结构，如：单链表，单向/双向循环链表，双向链表，二叉链表，十字链表，邻链表，邻接多重表等。
  

  

    本文主要分析单链表，循环链表，双向链表。其余的暂时不分析（其实是我不会，目前比较菜），以后会补充分析。
  

  

    数据结构最好先画图，这样可以增强理解与分析。
  

  

    大致了解一下链表的结构。
  

  

    由于链表中的每个结点的物理关系是不确定的，是随机的，就需要靠指针域来表示，构成逻辑关系。指针指向是十分重要的。
  

  

    这个哨兵位的头节点的可要可不要的。
  

  

    

  

  

    先分析哨兵位的链表，好理解
  

  

    

  

  

    head就是哨兵位，而这个last，是要来定位最后一个结点，当last指向head时，就代表是一个空表。

    由于我是在测试函数中创建了哨兵结点和尾结点指针，所以要对指针进行操作得传一个二级指针，传址调用才能才能对链表进行影响。

    当尾结点指向哨兵结点时，表示是一个空表。
  

  

    

  

  

    要在尾结点，也就是last结点。
  

  

    尾插结点图解，就是这样的。

  

  

    

  

  

    要在哨兵位后进行插入，每次插入都要满足在哨兵位节点后进行。
  

  

    而哨兵位结点是始终不变的，我们可以通过这样的操作不断头插。
  

  

    

  

  

    从哨兵位结点进行遍历，依次打印。
  

  

    

  

  

    由于是有哨兵位的链表，在任意位置删除还好，但无哨兵位的链表，就有一些麻烦。
  

  

    虽然差不多的变化。因位要保存结点的前一个结点地址，当没有哨兵位的时候就需要if判断一下。其实也没多麻烦。

    任意位置插入和删除是一样的。
  

  

    每个结点都具有两个指针，一个指向上一个逻辑关系结点，一个指向下一个逻辑关系结点。
  

  

    这一般使用一个哨兵位的结点，可以创建使用双向链表的步骤更简单。

    对于双向链表与单链表而言，双向链表在链表的插入，删除以及多个操作上更具有优势。
  

  

    对于单链表，要指针遍历找到尾结点，再插入。时间复杂度为O(N).

    而双向链表，他的头结点的prev指针指向了最后一个结点，根本不需要依次遍历。
  

  

    单链表都要准备两个指针。

    而双向链表直接访问prev指针就可以找到上一个结点。
  

  

    虽然，指针较多可能比单链表麻烦，但整体操作上，却要简单。
  

  

    而且，在以后的很多结构上，单链表都不会拿出来单独使用，而是作为某个数据结构的一部分。双向链表才是会作为一个主体来使用。
  

  

    测试双向链表（主函数）
  

  

    

  

  

    因为我是创建了一个结构体变量，要对其进行操作，需要传址调用，如果传值调用会，导致实际上哨兵并未改变，只是改变了函数中的形参。
  

  

    

  

  

    因为双向链表要形成一个闭环，初始化时也要形成闭环
  

  

    

  

  

    

  

  

    有链表中多个结点的情况
  

  

    

  

  

    

  

  

    对于头插尾插，尾删头删，一定要注意顺序，不然可能会导致指针指向错误的地方。
  

  

    而对于双向链表的删除插入，不需要多个指针，这样要方便很多。
  

  

    

  

  

    

  

  

    以上就是C语言编程数据结构线性表之顺序表和链表原理分析的详细内容，更多关于C语言数据结构线性表顺序表和链表的资料请关注脚本之家其它相关文章！
  



                            

                                                

                    

                

            

            


            

                
我要回帖

                

                    

                        
                        
                    

                

            

            

                        

                
更多关于 线性表和链表的区别 的文章

                

                    
                

            

                    

        

            

                
 

                


                

            

            

            

                
随机推荐