线性表_牛客博客

线性表

1.顺序存储——顺序表

2.链式存储

2.1 单链表

2.2 双链表

2.3 循环链表

2.4 静态链表——借助数组实现

1.线性表

1.概念

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

2.特点：

1）每个数据元素所占空间一样大

2）有次序

3）除第一个元素外，每个元素有且仅有一个直接前驱；除了最后一个元素外，每个元素有且仅有一个直接后继

4）位序：线性表中的第i个元素，其中i即为位序，位序从1开始。

2.基本操作

//初始化，构造空的线性表，分配内存空间
InitList(&L);
//销毁操作，释放内存空间
DestoryLit(&L);
//插入删除
ListInsert(&L,i,e);
ListDelete(&L,i,&e);
//按值查找
LocateElem(L,e);
//按位序查找
GetElem(L,i);
//表长、打印链表、判空
Length(L);
PrintList(L);
Empty(L);

1.注意：对数的操作，——创销，增删改查

2.为什么要实现基本操作？

团队合作编程，封装思想，方便后续使用。

2.顺序表

1.概念与特点

1、顺序表——用顺序存储的方式实现线性表顺序存储。把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。

2、特点

1）随机访问

2）存储密度高

3）拓展容量不方便

4）插入删除元素不方便

2.实现方式——静态分配

#define MaxSize 10
typedef struct{
  ElemType data[MaxSize];
  int lenght;
}SeqList;

1、在分配内存空间的时候，一定要进行初始化，否则内存中遗留的脏数据会导致一些很隐蔽的bug；

2、静态分配方式：定义一个静态数组存放顺序表的数据；

3、缺点：顺序表的大小固定，分配后无法更改；如果一开始就声明一个很大的内存空间，在使用过程中，仅仅用到了很小的一部分，则内存的利用率很低

3.实现方式——动态分配

#define InitSize 100
typedef struct{
  ElemType *data;   //指向动态分配数组的指针
  int lenght;
  int capacity;     //顺序表的最大容量
}SeqList;

//初始化
void InitList(&L){
  L.data = (ElemType*)malloc(sizeof(ElemType)*InitSize);
  L.length = 0;
  L.capacity = InitSize;
}

//增加动态数组的长度
void IncreaseSize(SeqList &L, int len){
  int *p = L.data;
  L.data = (int *)malloc(L.capacity + len)*sizeof(int));
  for(int i = 0; i < L.length; ++i){
    L.data[i] = p[i];
  }
  L.capacity = L.capacity + len;
  free(p);
}

4.插入操作

1、复杂度

时间复杂度：最好O(1)；最坏O(n)；平均O(n/2)

//在L的位序i出插入元素e
bool ListInsert(SeqList& L, int i , int e){
  if(i < 1 || i > L.length + 1){
    assert("插入位置非法");
    return false;
  }
  if(i >= L.capacity){
    assert("存储空间满，不能插入");
    return false;
  }
  L.length++;            //前面的判断已经说明插入位置合法
  for(int j = L.length - 1; j >= i - 1; --j){
    L.data[j + 1] = L.data[j];
  }
  L.data[i - 1] = e;
  return true;
}

2、注意：

1）L.length 除了表示顺序表的长度外，另外还表示顺序表中的最后一个元素的索引，不能是位序；

2）L.legth++写在for循环前，还是后，均正确；

如果写在for后面，如下当length = 0时，不会进入循环，直接执行L.data[i - 1] = e 和 L.length++;

L.data[i - 1] = e;
L.length++;

如果写在for前面，代码则会更加直观，易于阅读，个人感觉

5.删除操作

1.复杂度

最好情况O(1)；最坏情况O(n)；平均情况O((n - 1)/2)

bool ListDelete(SeqList &L, int i, int &e){
  if(i < 1 || i > L.length){
    assert("删除位置非法")
    return false;
  }
  e = L.data[i - 1];
  //向前移动
  for(int j = i; j < L.length; ++j){
    L.data[j - 1] = L.data[j];
  }
  L.lenght--;
  return true;
}

注意要删除的是第i个元素，还是数组下标为i的元素

6.查找操作

1.按位查找——GetElem

O(1)

//i表示位序，查找第i个位置的元素，通过e返回
bool GetElem(SeqList L, int i, int& e){
  if(i < 1 || i > L.length){
    assert("访问位置非法");
    return false;
  }
  e = L.data[i - 1];
  return true;
}

2.按值查找——LocateElem

复杂度：最好O(1）；最坏O(n）；平均O(n/2）

//查找顺序表中第一个元素值等于val的元素，并返回其位序
bool LocateElem(SeqList L, int val, int index){
  for(int i = 0; i < L.length; i++){
    if(L.data[i] == val){
      index = i + 1;
      return true;
    }
  }
  index = -1;
  return false;
}

注意：此查找操作，只能用于查找基本类型，不能用于查找结构体类型，C++可以通过重载运算符来判断结构类型是否相等。

3.单链表——链表

1.概念和特点

1.定义：每个结点除了存放数据元素外，还要存储指向下一个结点的指针。

2.优点：不要求大片连续空间，改变容量方便

3.缺点：不可随机存取，要耗费一定空间存放指针

2.代码定义单链表：

typedef struct LNode{
  ElemType data;
  struct LNode *next;
}LNode,*LinkList;

3.不带头结点

//初始化
bool InitList(LinkList &L){
  L = NULL;
  return true;
}

//判断单链表是否为空
bool Empty(LinkList L){
  if(L == NULL){
    return true;
  }
  else{
    return false;
  }
}

4.带头结点

//初始化
bool InitList(LinkList &L){
  L = (LNode*)malloc(sizeof(LNode));
  if(L == NULL)
    return false;
  L->next = NULL;     //头结点之后暂时没有节点
  return true;
}

//判断带头结点的单链表是否为空
bool Empty(LinkList L){
  if(L->next == NULL)
    return true;
  else
    return false;
}

注意：带头结点的代码写代码更方便

5.单链表的插入

1.按位序插入节点

最好O(1)；最坏o(n)；

//带头结点,在第i个位置插入元素e
//此处的L指向头结点
bool ListInsert(LinkList &L, int i, ElemType e){
  if(i < 1){
    assert("插入位序非法");
    return false;
  }
  LNode *p;            //找到要插入位置的前一个节点的位置
  int j = 0;
  p = L;   //L指向头结点，头结点是第0个节点
  while(p != NULL && j < i - 1){
    p = p->next;
    j++;
  }
  if(p == NULL){            //第i-1 个节点不存在,插入位置非法
    assert("插入位序非法");
    return false;
  }
  LNode* s = (LNode*)malloc(sizeof(LNode));
  s->data = e;
  s->next = p->next;
  p->next = s;
  return true;
}

//不带头结点；在第i个位置插入元素e
//区别在于带头结点的对于第1个位置的插入需要特殊讨论
//此时的L表示第一个节点，已经不是头结点了,代码需要注意
bool ListInsert(LinkList &L, int i, ElemType e){
  if(i < 1){
    assert("插入位序非法");
    return false;
  }
  //注意，此时的L表示第一个节点，已经不是头结点了
  if(i == 1){
    LNode* s = (LNode*)malloc(sizeof(LNode));
    s->data = e;
    s->next = L;
    L = s;
    return true;
  }

  LNode *p;            //找到要插入位置的前一个节点的位置
  int j = 1;    //0处需要特殊讨论，此处从1开始

  p = L;   
  while(p != NULL && j < i - 1){
    p = p->next;
    j++;
  }
  if(p == NULL){            //第i-1 个节点不存在,插入位置非法
    assert("插入位序非法");
    return false;
  }
  LNode* s = (LNode*)malloc(sizeof(LNode));
  s->data = e;
  s->next = p->next;
  p->next = s;
  return true;
}

2.指定节点的后插操作

//在p节点后插入元素e
bool InsertNextNode(LNode *p, ElemType e){
  if(p == NULL)
    return false;
  LNode* s = (LNode*)malloc(sizeof(LNode));
  if(s == NULL){
    return false;
  }
  s->data = e;
  s->next = p->next;
  p->next = s;
  return true;
}

3.指定节点的前插操作

//在p节点之前插入元素e
bool InsertPriorNode(LNode *p, ElemType e){
  if(p == NULL){
    return false;
  }
  LNode *s = (LNode*)malloc(sizeof(LNode));
  s->data = e;
  //先后插
  s->next = p->next;
  p->next = s;
  //再交换数据
  swap(s->data, p->data);
  return true;
}

6.单链表的删除

此处指讨论带头结点的（不带头结点的链表删除时需要考虑第0个节点）

1.删除第i个位置的节点

O(n)

//删除第i个位置的节点
bool ListDelete(LinkList &L, int i, ElemType &e){
  if(i < 1){
    assert("删除位置非法");
    return false;
  }
  LNode *p;        //p指向要删除位置的前一个节点，第i - 1个节点
  int j = 0;
  p = L;        //L指向头结点
  while(p != NULL && j < i - 1){
    p = p->next;
    j++;
  }
  //要删除位置的前一个节点为空，删除位置非法
  if(p == NULL){
    return false;
  }
  //要删除位置的节点不存在，i - 1节点不为空
  if(p->next == NULL){
    assert("第 i - 1个节点之后已无其他节点")
    return false;
  }
  //删除第i个节点
  LNode *q = p->next;
  e = q->data;
  p->next = q->next;
  free(q);
  return true;
}

2.删除指定节点

//删除指定节点p
bool DeleteNode(LNode* L,LNode *p){
  if(p == NULL){
    return false;
  }
  LNode *q = p->next;
  //如果是最后一个节点，则会报错
  if(q == NULL){
    q = L->next;
    while(q != NULL && q->next != p){
      q = q->next;
    }
    if(q == NULL){
      assert("删除非法，未找到p");
      return false;
    }
    q->next = NULL;
    free(p);
    return true;
  }
  //p不是最后一个节点
  p->data = p->next->data;
  p->next = q->next;
  free(q);
  return true;;
}

7.单链表的查找

O(n)

1.按位查找

//按位查找，查找第i个节点，带头结点
LNode * GetElem(LinkList L, int i){
  if(i < 0){
    return NULL;
  }
  LNode *p;
  int j = 0;   //有时候会用到查找头结点的情况，因此从0开始好
  p = L;
  while(p != NULL && j < i){
    p = p->next;
    j++;
  }
  return p;
}

实现查找后，在第i个位置插入元素e可以简化为：

//带头结点,在第i个位置插入元素e
//此处的L指向头结点
bool ListInsert(LinkList &L, int i, ElemType e){
  if(i < 1){
    return false;
  }
  //先查找第i - 1个结点
  LNode* p = GetElem(L, i - 1);
  if(p == NULL){
    assert("插入位置非法");
    return false;
  }
  //在第p个节点后插
  if(!InsertNextNode(p, e)){
    assert("插入失败");
    return false;
  }
  return true;
}

同样的道理，可以简化删除第i个节点，先找到第i-1个节点，在进行删除

//删除第i个位置的节点
bool ListDelete(LinkList &L, int i, ElemType &e){
  if(i < 1){
    assert("删除位置非法");
    return false;
  }
  LNode *p = GetElem(L, i - 1);

  //要删除位置的前一个节点为空，删除位置非法
  if(p == NULL){
    return false;
  }
  //要删除位置的节点不存在，i - 1节点不为空
  if(p->next == NULL){
    assert("第 i - 1个节点之后已无其他节点")
    return false;
  }
  //删除第i个节点
  LNode *q = p->next;
  e = q->data;
  p->next = q->next;
  free(q);
  return true;
}

2.按值查找

//按值查找，找到数据==e的节点
LNode* LocateElem(LinkList L, ElemType e){
  LNode *p = L->next;
  while(p != NULL && p->data != e){
    p = p->next;
  }
  //找到返回p，找不到返回NULL
  return p;
}

注意，查找只能查找基本类型，对于结构类型，需要重载运算符

8.求表长

O(n)

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

9.尾插法——建立单链表

O(1)

//尾插元素过多时，每次插入都需要遍历列表，因此可以设置一个尾指针
LinkList L;
LinkList tail;
InitList(L);        //初始化
tail = L;
//带头结点
bool List_TailInsert(LinkList &tail, ElemType e){
  LNode * p = (LNode*)malloc(sizeof(LNode));
  if(p == NULL){
    return false;
  }
  p->data = e;
  p->next = NULL;

  tail->next = p;
  tail = p;
  return true;
}

10.头插法——建立单链表

//头插法，带头结点
bool List_HeadInsert(LinkList &L, ElemType e){
  LNode* s = (LNode*)malloc(sizeof(LNode));
  if(s == NULL){
    return false;
  }
  s->data = e;
  s->next = L->next;
  L->next = s;
  return true;
}

4.双链表——链表

1.概念和特点

1.单链表缺点是无法进行逆检索，有时候不太方便

2.双链表，可进可退，存储密度更低一丢丢

2.代码定义双链表

typedef struct DNode{
  ElemType data;
  struct DNode *prior,*next;
}DNode,*DLinkList;

3.初始化双链表

//带头结点的双链表
bool InitDLinkList(DLinkList &L){
  L = (DNode*)malloc(sizeof(DNode));
  if(L == NULL)
    return false;
  L->prior = NULL;
  L->next = NULL;
  return true;
}

4.双链表的插入

//在p节点后面插入s节点
bool InsertNextDNode(DNode *p, DNode *s){
  if(p == NULL || s == NULL){
    return false;
  }
  s->next = p->next;
  if(p->next != NULL){
    p->next->prior = s;
  }
  s->prior = p;
  p->next = s;
  return true;
}

5.双链表的删除

//删除p节点的后继节点
bool DeleteNextDNode(DNode *p){
  if(p == NULL){
    return false;
  }
  DNode *q = p->next;
  if(q == NULL){
    return false;       //p无后继节点
  }
  p->next = q->next;
  if(q->next != NULL){
    q->next->prior = p;
  }
  free(q);
  return true;
}

6.销毁双链表

//销毁双链表
void Destory(DLinkList &L){
  //循环释放各个节点
  while(L->next != NULL){
    DeleteNextDNode(L);
  }
  free(L);        //释放头结点
  L = NULL;
}

7.双链表的遍历

void Print(DLinkList p){
  while(p != NULL){
    p = p->next;
    std::cout << p->data << std::endl;
  }
}

5.循环单链表——链表

从一个节点出发，可以找到其他任何一个节点

注意：如果一个链表的应用场景，是需要经常在表头和表尾进行操作，可以将L设置为指向表尾元素，因此在尾插元素时要移动L，时间复杂度为O(1)

1.定义

typedef struct LNode{
  ElemType data;
  struct LNode *next;
}LNode, *LinkList;

2.初始化

bool InitList(LinkList &L){
  L = (LNode*)malloc(sizeof(LNode));
  if(L == NULL){
    return false;
  }
  L->next = L;        //头结点的next指向头结点
  return true;
}

3.判空

bool Empty(LinkList L){
  if(L->next == L){
    return true;
  }
  return false;
}

4.判断是否为尾节点

//判断节点p是否为循环单链表的表尾节点
bool isTail(LinkList L, LNode *p){
  if(p->next == L){
    return true;
  }
  return false;
}

6.循环双链表

1.定义

表头节点的prior指向表尾节点

表尾节点的next指向表头节点

typedef struct DNode{
  ElemType data;
  struct DNode *prior,*next;
}DNode,*DLinkList;

//初始化空的循环双链表
bool InitDLinkList(DLinkList &L){
  L = (DNode*)malloc(sizeof(DNode));
  if(L == NULL){
    return false;
  }
  L->prior = L;
  L->next = L;
  return true;
}

//判空
bool Empty(DLinkList L){
  if(L->next == L)
    return true;
  return false;
}

//判断节点是否为循环链表的表尾节点
bool isTail(DLinkList L, DNode *p){
  if(p->next == L){
    return true;
  }
  return false;
}

2.循环双链表的插入&删除

//在p节点后面插入s节点
bool InsertNextDNode(DNode *p, DNode *s){
  if(p == NULL || s == NULL){
    return false;
  }
  s->next = p->next;
  p->next->prior = s;
  s->prior = p;
  p->next = s;
  return true;
}

//删除p的后继节点
bool DeleteNextDNode(DNode *p){
  if(p == NULL || p->next == NULL){
    return false;
  }
  DNode *q = p->next;
  p->next = q->next;
  q->next->prior = p;    //循环双链表此处不需要判断
  free(q);
  return true;
}

7.静态链表

1.概念

1.单链表，各个节点在内存中随机存储

2.静态链表：分配一整片连续的内存空间，各个节点集中安置

如下图

图片说明

2.定义

#define MaxSize 10
typedef struct {
  ElemType data;
  int next;
}SLinkList[MaxSize];

//SLinkList   a; ===>a是一个数组，每个数组元素是一个struct

3.相关操作

图片说明

文件分配表实质上是一个静态链表，因为文件分配表的大小和磁盘的容量相关，容量定了之后，文件分配表的大小也确定；

8.总结

图片说明