数据结构之线性表（顺序表、单链表、双链表）（一）

2021-11-23 22:43:29

1 线性表的基本概念

对于同一个线性表，其每一个数据元素的值虽然不同，但必须具有相同的数据类型；

数据元素之间具有一种线性的或“一对一”的逻辑关系；

第一个数据元素没有前驱，这个数据元素被称为开始节点；

最后一个数据元素没有后继，这个数据元素被称为终端节点；

除了第一个和最后一个数据元素外，其他数据元素有且仅有一个前驱和一个后继；

2 线性表抽象数据类型描述

基本操作如下：

线性表的置空操作clear()：将一个已经存在的线性表置为空表；

线性表判空操作isEmpty()：判断线性表是否为空，若为空，则返回true；否则，返回为false；

求线性表的长度操作length()：求线性表中的数据元素的个数并返回其值；

取元素操作get(i)：读取并返回线性表中的第i个数据元素的值。其中i的取值范围为0≤i≤length()-1；

插入操作insert(i,x)：在线性表的第i个数据元素之前插入一个值为x的数据元素。其中i的取值范围为0≤i≤length()。当i=0时，在表头插入x；当i=length()时，在表尾插入x；

删除操作remove(i)：删除并返回线性表中第i个数据元素。其中i的取值范围为0≤i≤length()-1；

查找操作indexOf(x)：返回线性表中首次出现的指定的数据元素的位序号，若线性表中不包含此数据元素，则返回-1；

3 线性表的顺序表示和实现

3.1 顺序表的定义

所谓顺序表就是顺序存储的线性表。顺序存储是用一组地址连续的存储单元依次存放线性表中各个元素的存储结构。

3.2 顺序表的特点

在线性表中逻辑上相邻的数据元素，在物理存储上也是相邻的；

存储密度高，但要预先分配“足够应用”的存储空间，这可能会造成存储空间的浪费；

便于随机存储；

不便于插入和删除操作，这是因为在顺序表上进行的插入和删除操作会引起大量数据元素的移动；

3.3 顺序存储结构类的描述

数据结构之线性表（顺序表、单链表、双链表）（一）

顺序表的存储结构示意图

为了用C语言描述上图的顺序表，定义结构体SeqList如下：

typedef struct 
{
  DateType data[MAXSIZE];  /*数组存储数据元素*/
  int size;        /*线性表当前长度*/
}SqList;

【说明】：其中，DataType为数组元素（即数据元素）的数据类型，MaxSize表示数组的最大元素个数，list表示顺序表的数组成员，size表示顺序表中当前存储的数据元素个数成员，且必须满足条件size≤MaxSize，SeqList是结构体名。

3.4 顺序表操作的实现

在顺序存储结构下，线性表抽象数据类型定义的各个操作的具体实现方法如下：

初始化ListInitiate(L)
void ListInitiate(SeqList *L)    //初始化顺序表L
 {
     L->size = 0;  //定义初始化数据元素个数
 }

【说明】由于函数中要改变参数L的size域的值，所以参数L应设计为输出型参数，即参数L设计为SeqList的指针类型。否则，size域的修改值将不能带回去。

求当前数据元素个数ListLength(L)

int ListInitiate(SeqList L)    //返回顺序表L的当前数据元素个数
{
    return L.size;
}

插入数据元素ListInsert(L, i, x)

数据结构之线性表（顺序表、单链表、双链表）（一）

顺序表插入过程

代码实现：

int ListInsert(SqList *L, int i, DateType x)
{
  int k;
  if (L->size== MAXSIZE)  /*顺序线性表已满*/
  {
    printf("顺序表已满无法插入！\n");
    return 0;
  }
  if (i<1 || i>L->size)  /*i不在范围内*/
  {
    return 0;
  }
  if (i <= L->size-1)  /*插入位置不在表尾*/
  {
    //从后向前依次后移数据，为插入做准备
    for (k = L->size; k >=i-1 ; k--)
    {
      L->list[k] = L->list[k-1];
    }
  }
  L->list[i] = x;    //插入x
  L->size++;         //元素个数加1
  return 1;
}

【说明】：

如果线性表长度大于等于数组长度，抛出异常

如果插入位置不合理，抛出异常

从最后一个元素开始向前遍历到第i个位置，分别将它们都向后移动一个位置

表长加1

删除数据元素ListDelete(L, i, x)

顺序表删除过程

代码实现：

int ListDelete(SequenceList *L, int i, DateType *x) 
{
/*删除顺序表L中位置i（0 ≤ i ≤ size - 1）的数据元素值并存放到参数x中*/
/*删除成功返回1，删除失败返回0*/
    int j;
    if(L->size <= 0)
    {
        printf("顺序表已空无数据元素可删! \n");
        return 0;
    }
    else if(i < 0 || i > L->size-1)
    {
        printf("参数i不合法");
        return 0;
    }
    else
    {
        *x = L->list[i];  //保存删除的元素到参数x中
         //从i位置的后一位开始，依次往前移一位，直到最后
        for(j = i+1; j <= L->size-1; j++) 
        { 
          L->list[j-1] = L->list[j];
        }
        L->size--;        //数据元素个数减1
        return 1;
    }
}

【说明】：

如果为空表，抛出异常

如果删除位置不合理，抛出异常

从删除元素位置开始遍历到最后一个元素位置，分别将它们向前移动一个位置

表长减1

取数据元素ListGet(L, i, x)

/*取顺序表L中第i个数据元素的值存于x中，成功则返回1，失败返回0*/
int ListGet(SequenceList L, int i, DateType *x)
{
    if(i < 0 || i > L.size-1)
    {
        printf("参数i不合法! \n");
        return 0;
    }
    else
    {
        *x = L.list[i];
        return 1;
    }
}

码农公寓

1 线性表的基本概念

2 线性表抽象数据类型描述

3 线性表的顺序表示和实现

相关文章