Sakuraine
Back to note
•
5 min read
线性表

2.1 线性表的定义与基本操作

线性表（linear-list）

2.1.1 线性表的定义

线性表是具有相同数据类型的 n（n≥0）个数据元素的有限序列。

线性表的抽象数据类型定义：

在数据元素的非空有限集中：

  • 存在唯一的一个被成做“第一个”的数据元素；
  • 存在唯一的一个被称作“最后一个”的数据元素；
  • 除第一个之外，集合中的每个数据元素均只有一个前驱；
  • 除最后一个之外，集合中每个数据元素均只有一个后继。

线性表是逻辑结构，顺序表和链表是存储结构

特点：

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

2.1.2 线性表的基本操作

  • InitList(&L)：初始化表。构造一个空的线性表 L，分配内存空间。
  • Length(L)：求表长。返回线性表 L 的长度，即 L 中数据元素的个数。
  • LocateElem(L, e): 按值查找操作。在表 L 中查找具有给定关键字值的元素。
  • GetElem(L, i): 按位查找操作。获取表 L 中第 i 个位置的元素的值。
  • ListInsert(&L, i, e): 插入操作。在表 L 中第 i 个位置插入指定元素 e。
  • ListDelete(&L, i, &e): 删除操作。删除表 L 中第 i 个位置的元素，并用 e 返回删除元素的值。
  • PrintList(L): 输出操作。按前后顺序输出线性表 L 的所有元素值。
  • Empty(L): 判空操作。若 L 为空表，则返回 true，否则返回 false。
  • DestroyList(&L): 销毁操作。销毁线性表，并释放线性表 L 所占用的内存空间。

2.2 线性表的顺序表示

2.2.1 顺序表的定义

特点：逻辑顺序与物理顺序相同。可以随机存取

优点：

  • 随机存取时间复杂度 O(1)
  • 存储密度高，每个节点只存储数据元素（不包含位置指针）

缺点：

  • 插入删除时间复杂度 O(n)
  • 需要预分配连续的存储空间

2.2.2 顺序表的基本操作

1. 顺序表的初始化

typedef struct {
  ElemType *data;
  int length;
  int MaxSize;
} SeqList;

静态分配

void InitList(SqList &L)
{
  L.length = 0;
}

动态分配

#define MAX_SIZE 10

void InitList(SeqList &L)
{
  L.data = (ElemType *)malloc(InitSize * sizeof(ElemType));
  L.length = 0;
  L.MaxSize = MAX_SIZE;
}

2. 插入操作

bool ListInsert(SqList &L, int i, ElemType e)
{
  if (i < 1 || i > L.length + 1 || L.length >= L.MaxSize)
    return false;
  for (int j = L.length; j >= i; j--)
    L.data[j] = L.data[j - 1];
  L.data[i - 1] = e;
  L.length++;
  return true;
}

3. 删除操作

bool ListDelete(SqList &L, int i, ElemType &e)
{
  if (i < 1 || i > L.length)
    return false;
  e = L.data[i - 1];
  for (int j = i; j < L.length; j++)
  {
    L.data[j - 1] = L.data[j];
  }
  L.length--;
  return true;
}

4. 按值查找

int LocateElem(SqList L, ElemType e)
{
  for (int i = 0; i < L.length; i++)
  {
    if (L.data[i] == e)
      return i + 1;
  }
  return 0;
}

2.3 线性表的链式表示

线性链表

节点（Node）：数据元素的存储映像。由存放数据元素的数据域和存放后继结点地址的指针域组成

  • 数据域：存储数据元素信息的域
  • 指针域：存储直接后继位置的指针

特点：

  • 用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）
  • 链表中结点的逻辑顺序和物理顺序不一定相同

2.3.1 单链表的定义

优点：

  • 插入删除时间复杂度 O(1)
  • 不需要分配连续的存储空间

缺点：

  • 随机存取时间复杂度 O(n)
typedef struct LNode
{
  ElemType data;
  struct LNode *next;
} LNode, *LinkList;

单链表分为带头节点和不带头节点

引入头节点的优点：

  • 链表第一个位置上的操作和其他位置一致，无需特殊处理
  • 无论链表是否为空，头指针都是指向头节点的非空指针，空表和非空表的处理也就统一了

2.3.2 单链表的基本操作

1. 初始化

带头节点

bool InitList(LinkList &L)
{
  L = (LNode *)malloc(sizeof(LNode));
  L->next = NULL;
  return true;
}

不带头节点

bool InitList(LinkList &L)
{
  L= NULL;
  return true;
}

2. 求表长操作

带头节点

int Length(LinkList L)
{
  int len = 0;
  LNode *p = L->next;
  while (p != NULL) {
    p = p->next;
    len++;
  }
  return len;
}

不带头节点

int Length(LinkList L)
{
  int len = 0;
  LNode *p = L;
  while (p != NULL) {
    p = p->next;
    len++;
  }
  return len;
}

3. 按位查找

带头节点

LNode *GetElem(LinkList L, int i)
{
  if (i < 1)
    return NULL;
  LNode *p = L->next;
  int j = 1;
  while (j != i && p != NULL)
  {
    p = p->next;
    j++;
  }
  return p;
}

不带头节点

LNode *GetElem(LinkList L, int i)
{
  if (i < 1)
    return NULL;
  LNode *p = L;
  int j = 1;
  while (p != NULL && j < i) {
    p = p->next;
    j++;
  }
  return p;
}

4. 按值查找

带头节点

LNode *LocateElem(LinkList L, ElemType e)
{
  LNode *p = L->next;
  while (p->data != e && p!= NULL) {
    p = p->next;
  }
  return p;
}

不带头节点

LNode *LocateElem(LinkList L, ElemType e)
{
  LNode *p = L;
  while (p != NULL && p->data != e) {
    p = p->next;
  }
  return p;
}

5. 插入操作(后插操作)

带头节点

bool ListInsert(LinkList &L, int i, ElemType e)
{
  LNode *p = L;
  int j = 1;
  while (p != NULL && j != i) {
    p = p->next;
    j++;
  }
  if (p == NULL)
    return false;
  LNode *s = (LNode *)malloc(sizeof(LNode));
  s->data = e;
  s->next = p->next;
  p->next = s;
  return true;
}

不带头节点

第一位插入时，需要特殊处理

bool ListInsert(LinkList &L, int i, ElemType e)
{
  if (i < 1)
    return false;
  if (i == 1)
  {
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->data = e;
    s->next = L;
    L = s;
    return true;
  }
  LNode *p = L;
  int j = 2;
  while (p != NULL && j != i) {
    p = p->next;
    j++;
  }
  if (p == NULL)
    return false;
  LNode *s = (LNode *)malloc(sizeof(LNode));
  s->data = e;
  s->next = p->next;
  p->next = s;
  return true;
}

6. 删除操作

带头节点

bool ListDelete(LinkNode &L, int i, ElemType &e)
{
  LNode *p = L;
  int j = 0;
  while (p->next != NULL && j < i - 1) {
    p = p->next;
    j++;
  }
  if (p->next == NULL || j > i - 1)
    return false;
  LNode *q = p->next;
  e = q->data;
  p->next = q->next;
  free(q);
  return true;
}

不带头结点

bool ListDelete(LinkList &L, int i, ElemType &e)
{
  if (L == NULL)
    return false;
  if (i == 1) {
    LNode *q = L;
    e = q->data;
    L = q->next;
    free(q);
    return true;
  }
  LNode *p = L;
  int j = 1;
  while (p->next != NULL && j < i - 1) {
    p = p->next;
    j++;
  }
  if (p == NULL || p->next == NULLF)
    return false;
  LNode *q = p->next;
  e = q->data;
  p->next = q->next;
  free(q);
  return true;
}

7. 采用头插法创建单链表

带头节点

LinkList List_HandleInsert(LinkList &L, ElemType e)
{
  LNode *s = (LNode *)malloc(sizeof(LNode));
  s->data = e;
  s->next = L->next;
  L->next = s;
  return L;
}
LinkList List_HeadInsert(LinkList &L)
{
  LNode *s; int x;
  L = (LNode*)malloc(sizeof(LNode));
  L->next = NULL;
  scanf("%d", &x);
  while(x != 9999) {
    s = (LNode*)malloc(sizeof(LNode));
    s->data = x;
    s->next = L->next;
    L->next = s;
    scanf("%d", &x);
  }
  return L;
}

不带头结点

LinkList List_HeadInsert(LinkList &L)
{
  LNode *s; int x;
  L = NULL;
  scanf("%d", &x);
  while(x != 9999) {
    s = (LNode*)malloc(sizeof(LNode));
    s->data = x;
    s->next = L == NULL ? NULL : L->next;
    L = s;
    scanf("%d", &x);
  }
  return L;
}