线性表的定义和基本操作

1. 线性表的定义

• 线性表是具有相同数据结构类型的n(n≥0)个数据元素的有限序列，其中表长为n，当n=0时线性表是一个空表。

• 线性表的特点：

  • 表中的元素有限
  • 表中的元素具有有逻辑上的顺序性，表中的元素有其先后次序。
  • 表中的元素都是数据元素，每个元素都是单个元素。
  • 表中元素的数据类型都相同，这意味着每个元素都占有相同大小的存储空间。
  • 表中元素具有抽象性，即仅讨论元素间的逻辑关系，而不考虑元素究竟表示什么内容。

• 注意：线性表是一种逻辑结构，表示元素之间一对一的相邻关系。顺序表和链表是指存储结构。

2.线性表的基本操作

• InitList(&L):
• Length(L):
• LocateElem(L,e):
• GetElem(L,i):
• ListInsert(&L,i,e):
• ListDelete(&L,i,&e):
• PrintList(L):
• Empty(L):
• DestroyList(&L):

线性表的顺序表示

1. 顺序表的定义

• 顺序表是用一组地址连续的存储单元依次存储线性表中的数据元素，从而是的逻辑相邻的两个元素在物理位置上也相邻。
• 称 i 为元素 a_i 在线性表中的位序。
• 顺序表特点：
  • 逻辑顺序与其物理顺序相同，插入和删除操作需要移动大量元素
  • 随机访问，即通过首地址和元素序号可在时间O(1)内找到指定元素
  • 存储密度高，每个节点只存储数据元素
  • 除第一个元素外，每个元素有且仅有一个直接前驱。
  • 除最后一个元素外，每个元素有且仅有一个直接后继。
• 注意：线性表中元素的位序是从1开始的，而数组中元素的下标是从0开始的。
• 静态顺序表存储类型表述：

    #define MaxSize 50                //定义线性表的最大长度
    typedef struct {                  
        ElemType data[MaxSize];       //顺序表的元素
        int length;                   //顺序表的当前长度
    } SqList;                         //顺序表的类型定义

• 动态顺序表存储类型表述：

    #define InitSize 50               //定义线性表的初始长度
    typedef struct {                  
        ElemType *data;               //指示动态分配数组的指针
        int MaxSize, length;          //数组的最大容量和当前个数
    } SqList;                         //动态分配数组顺序表的类型定义

C的初始动态分配语句：

L.data = (ElemType*)malloc(sizeof(ElemType) * InitSize);  

2. 顺序表的基本操作

1.插入

• 算法思路：
  • 1.判断i的值是否正确
  • 2.判断表长是否超过数组长度
  • 3.从后向前到第i个位置，分别将这些元素都向后移动一位
  • 4.将该元素插入位置i 并修改表长
• 代码
• 分析：
  • 最好情况：在表尾插入（即i=n+1），元素后移语句将不执行，时间复杂度为O(1)。
  • 最坏情况：在表头插入（即i=1），元素后移语句将执行n次，时间复杂度为O(n)。
  • 平均情况：假设p_i（p_i=1/(n+1) ）是在第i个位置上插入一个结点的概率，则在长度为n的线性表中插入一个结点时所需移动结点的平均次数为 n/2,时间复杂度为O(n)

2.删除

• 算法思路：
  • 1.判断i的值是否正确
  • 2.取删除的元素
  • 3.将被删元素后面的所有元素都依次向前移动一位
  • 4.修改表长
• 代码
• 分析
  • 最好情况：删除表尾元素（即i=n），无须移动元素，时间复杂度为O(1)。
  • 最坏情况：删除表头元素（即i=1），需要移动除第一个元素外的所有元素，时间复杂度为O(n)。
  • 平均情况：假设p_i(p_i=1/n)是删除第i个位置上结点的概率，则在长度为n的线性表中删除一个结点时所需移动结点的平均次数为 (n-1)/2，时间复杂度为O(n)

数据结构学习笔记（二：线性表）

原文：https://www.cnblogs.com/missionA/p/12616327.html