红魔咖啡馆

头发越掉越多，头发越掉越少

0%

【数据结构】表

发表于 更新于 分类于 ，
本文字数： 7.5k 阅读时长 ≈ 14 分钟
介绍了线性表，主要是多种链表的实现

表

线性表

n个数据类型相同的元素构成的有限序列

  • 空表：大小为0的表
  • 首节点：存在唯一一个被称为第一个的元素
  • 尾节点：存在唯一一个被称为最后一个的元素
  • 前驱：\(A_{i-1}\)前驱\(A_i\)
  • 后继：\(A_{i+1}\)后继\(A_i\)

对于除了首尾节点的元素\(A_i\)，它只会有一个前驱、一个后继

顺序表实现

顺序表：一组连续内存单元存储线性表的各个元素

对于静态表，main函数调用时，应传入列表的地址(&)

建表

1
2
3
4
5
6
7
8
9
#define MAXSIZE 100
typedef int ElemType; // 方便存储不同类型数据的情况下修改数据类型

// 建表
typedef struct SeqList
{
  ElemType data[MAXSIZE];
  int length; // 顺序表数据个数
};

初始化

1
2
3
4
// 初始化
void initList(SeqList *L){
  L->length = 0;
}

尾插元素

1
2
3
4
5
6
7
8
9
10
// 尾插元素
int appendElem(SeqList *L, ElemType e){
  if (L->length>=MAXSIZE){ // 判满
    printf("已满\n");
    return 0;
  }
  L->data[L->length] = e; // 在末尾添加元素
  L->length++; // 将顺序表长度加一
  return 1;
}

插入元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 插入元素
int insertElem(SeqList *L, ElemType e, int pos){
  if (L->length>=MAXSIZE){ // 判满
    printf("已满\n");
    return 0;
  }
  if (pos<1 || pos> L->length){
    printf("位置错误\n");
    return 0;
  }
  for (int i = L->length-1; i>=pos-1;i--){ // 倒序让插入元素后面的元素后移一位
    L->data[i+1] = L->data[i]; // 向后移动元素
  }
  L->data[pos-1] = e; // 插入元素
  L->length++; // 将顺序表长度加一
  return 1;

}

最坏时间复杂度\(O(n)\)

需要将插入位置后的元素都后移一位

遍历列表

1
2
3
4
5
6
7
// 遍历元素
void listElem(SeqList *L){
  for (int i = 0; i < L->length; i++){
    printf("%d ", L->data[i]);
  }
  printf("\n");
}

删除元素

1
2
3
4
5
6
7
8
9
10
11
// 删除元素并返回删除的元素
int delElem(SeqList *L, int pos, ElemType *e){
  *e = L->data[pos-1]; // 取出删除元素
  if (pos < L->length){
    for (int i = pos; i<L->length; i++){
      L->data[i-1] = L->data[i]; // 从pos开始向后，将后面一位覆盖到前一位实现删除
    }
  }
  L->length--; // 表长度减一，这样最后一个元素不用覆盖也可以
  return 1;
}

该删除可以返回删除掉的元素，用e变量存储

查找元素

1
2
3
4
5
6
7
8
9
// 查找元素
int findElem(SeqList *L, ElemType e){
  for (int i = 0; i<L->length; i++){
    if (e==L->data[i]){ // 找到元素
      return i+1; // 返回位置
    } 
  }
  return -1; // 找不到返回-1
}

使用动态顺序表实现

通过malloc函数在堆中动态分配内存建表

不同的地方只是在建表与初始化上

1
2
3
4
5
6
7
8
9
10
11
12
13
// 建表 
typedef struct {
  ElemType *data;
  int length;
}SeqList;

// 初始化 分配内存
SeqList* initList(){
  SeqList *L = (SeqList*)malloc(sizeof(SeqList));
  L -> data = (ElemType*)malloc(sizeof(ElemType)*MAXSIZE);
  L -> length = 0;
  return L;
}

此时在main函数建表时只需要调用initList函数初始化并将返回的结构体指针存入一个对应变量即可

由于此时获得的直接是地址，故对应操作时便不需要取地址了

链表实现

链表存储的特点是用一组任意的存储单元存储数据（可连续可不连续）

对每一个存储单元，除了要存储当前数据，还需要存储一个指示其直接后继的信息（地址），这两部分信息组成了一个节点，n个节点链接成了一个链表，即为线性表

节点包括两个域：

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

单链表

next中存储了下一个节点的地址，其中尾节点中的next指向NULL，表示到达链表尾部

初始化

1
2
3
4
5
6
7
8
9
10
11
12
// 单链表初始化-建立头节点
Node* initList(){
  Node *head = (Node*)malloc(sizeof(Node)); // 分配一个节点大小的空间
  head->data = 0; // 数据设为0
  head->next = NULL; // 下一个地址设为NULL
  return head;
}

int main(){
  Node* test = initList();
  return 0;
}

建立一个头节点，作为线性表的开始，其数据为0，地址默认为NULL

创建链表时，只需要调用initList函数并将返回的结构体指针赋给对应变量即可

头插元素

头插元素实现了在头节点后插入数据

先让新节点的next指向原头节点指向的下一个节点

再让头节点指向的节点更改为新的节点

顺序很重要

1
2
3
4
5
6
int insertHead(Node* L, ElemType e){
  Node *p = (Node*)malloc(sizeof(Node)); // 分配存储数据的节点的空间
  p->data = e; // 将插入元素赋值给该节点
  p->next = L->next; // 将该节点的next指向原头节点指向的节点
  L->next = p; // 将原头节点的next指向该新节点
}

尾插元素

头插元素实现了在尾节点后插入数据，我们需要先寻找尾节点

找到某节点的next==NULL时便找到了尾节点

1
2
3
4
5
6
7
8
// 获得尾节点地址
Node* get_tail(Node* L){
  Node *p = L;
  while(p->next!=NULL){ // 当节点不为空时
    p = p->next; // 顺着寻找下一个节点
  }
  return p;
}

先让先前的尾节点指向新节点

再让新节点指向NULL

1
2
3
4
5
6
7
8
// 尾插法插入元素
Node* insertTail(Node* tail, ElemType e){
  Node* p = (Node*)malloc(sizeof(Node));
  p->data = e;
  tail->next = p;
  p->next = NULL;
  return p;
}

注意，尾插法每次返回尾节点，这样下次插入时就可以接着上一次的插入了，不需要再get

指定位置插入元素

首先要找到待插入位置的前一个元素，然后让新节点指向该元素的下一个元素

然后让前一个节点指向新节点的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 指定位置插入元素
int insertNode(Node* L, int pos, ElemType e){
  Node* p = L;
  // 让指针指向需要插入位置的前驱节点
  for(int i = 0; i<pos-1;i++){
    p = p->next;
    if (p==NULL){
      return 0;
    }

  }
  Node* q = (Node*)malloc(sizeof(Node)); // 要插入的新节点
  q->data = e; // 输入数据
  q->next = p->next; // 新节点下一个位置赋值为前驱节点指向的后一个节点
  p->next = q; // 前驱节点指向插入的新节点
  return 1;
}

删除节点

找到删除节点的前驱节点p

用指针q指向要删除的节点

通过改变p的后继节点实现删除

并释放删除节点的空间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 删除节点
int delNode(Node* L, int pos){
  Node* p = L;
  // 让指针指向需要删除位置的前驱节点
  for (int i = 0; i<pos-1; i++){
    p = p->next;
    if (p == NULL) {
      return 0;
    }
  }
  if (p->next == NULL){
    printf("位置错误\n");
  }
  
  Node* q = p->next; // q指向要删除的节点
  p->next = q->next; // 要删除节点的前驱节点指向其后继节点
  free(q);
  return 1;
  
}

获取链表长度

1
2
3
4
5
6
7
8
9
10
// 获取链表长度
int listLength(Node* L){
  Node* p = L;
  int cnt = 0;
  while(p!=NULL){
    p = p->next;
    cnt++;
  }
  return cnt;
}

释放链表

把头结点后的节点都释放掉

让指针p指向头节点后的第一个节点

若p不为NULL，让q指向p的后继节点，并释放p指向的节点

让p, q指向同一个节点，循环以上操作

1
2
3
4
5
6
7
8
9
10
11
12
13
// 释放链表
void freeList(Node* L){
  Node* p = L->next; // p指针指向头节点后的第一个节点
  Node* q;
  while(p!=NULL){ // 判断p指向是否是空节点
    q = p->next; // q指向p的后继
    free(p); // 释放p
    p = q; // p指向其后继（q指向的节点）

  }
  L->next = NULL; //释放后原链表头节点指向NULL

}

注意

  • 时间复杂度：读取数据–顺序表>链表 修改数据–链表>顺序表
  • 不要忘记初始化指针变量，防止其变为野指针
  • 何时使用malloc？
    • 声明指向一个结构的指针不会创建该结构，而是给出足够空间容纳结构可能会使用的地址
    • 使用malloc可以使系统创建一个新的结构并返回指向该结构的指针
    • 故若想使用指针变量沿着一个表行进，就没必要创建新的结构，不宜使用malloc
  • free的结果：指针指向的地址没变，但该位置处的数据已经无定义了（野指针）
  • 若未对链表进行过删除操作，则调用malloc的次数应该等于表的大小，含表头再+1

单项循环链表

特点：表中最后一个节点的指针域指向头节点，形成一个环

终止条件：p!=L或p->next!=L

判断是否有环

快慢指针

让快指针一次走两步，慢指针一次走一步

当遇不到NULL时，若有环，则两者会一直追赶，根据概率一定会有一个时候相遇

若能相遇则说明有环，否则若碰到NULL证明没有环

注意特判只有一个元素或没有元素时，不然当前节点的指针域会赋值给空指针而报RE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode* fast = head;
        ListNode* slow = head;
        if (fast==nullptr||fast->next==nullptr) return false;
        while(fast!=nullptr&&fast->next!=nullptr){
            fast = fast->next->next;
            slow = slow->next;
            if (fast==slow) return true;
        }
        return false;
    }
};

找到环的入口

设起点到入口距离为\(x\)，入口到相遇距离为\(y\)，相遇再到入口距离为\(z\)，则快慢指针走的路程如下：

\(fast = x+y+n(x+y)\)

\(slow = x+y\)

其中n为圈数，由于快指针的速度为慢指针的两倍，故慢指针一定会在一圈内与快指针相遇

有\(2(x+y)=x+y+n(y+z)\)

化简得$ = n(y+z)-y\(，由于快指针先入环，且速度快于慢指针，故快指针至少转一圈才能与慢指针相遇，即\)n$至少为1

多拿出一圈来将y约掉，则\(x=(n-1)(y+z)+z\)

当\(n=1\)时，即快指针转一圈与慢指针相遇的情况下，\(x=z\)，即两者会在环的入口处相遇

当\(n>1\)时，由于\(y+z\)是一整圈的路程，即走完若干圈后快指针还会再走\(z\)距离，最后与慢指针在环的入口处相遇

故我们可以在相遇位置设置一个指针，在起始位置设置一个指针，两者相遇处即为入口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};
class Solution {
    public:
        ListNode* detectCycle(ListNode *head) {
            int cnt[10005];
            ListNode* fast = head;
            ListNode* slow = head;
            if (fast==nullptr||fast->next==nullptr) return nullptr;
            while(fast!=nullptr&&fast->next!=nullptr){
                fast = fast->next->next;
                slow = slow->next;
                if (fast==slow){
                    ListNode* index1 = fast;
                    ListNode* index2 = head;
                    while(index1!=index2){
                        index1 = index1->next;
                        index2 = index2->next;
                    }
                    return index1;
                }
            }
            return nullptr;
        }
    };

双向链表

特点：双向链表的节点中有两个指针域：一个指向直接后继，另一个指向直接前驱

建表

1
2
3
4
5
typedef int ElemType;
typedef struct node{
  ElemType data;
  struct node *prev, *next;
}Node;

初始化

与单链表相同

1
2
3
4
5
6
7
// 初始化建立头节点
Node* initList(){
  Node *head = (Node*)malloc(sizeof(Node)); // 分配一个节点大小的空间
  head->data = 0; // 数据设为0
  head->next = NULL; // 下一个地址设为NULL
  return head;
}

头插法

让新节点的prev指向头节点

让新节点的next指向头节点的next

让头节点的next节点的prev指向新节点，让头节点的next指向新节点

1
2
3
4
5
6
7
8
9
10
11
12
// 头插法
int insertHead(Node* L, ElemType e){
  Node* p = (Node*)malloc(sizeof(Node));
  p->data = e;
  p->prev = L; // 新节点的prev指向头节点
  p->next = L->next; // 新节点的next指向头节点后的第一个节点
  if (L->next!=NULL){ // 保证并非只有一个头节点
    L->next->prev = p; // 新节点的next节点的prev指向新节点
  }
  L->next = p; // 头节点的next节点指向新节点
  return 1;
}

尾插法

让新节点的prev指向尾节点

让尾节点的next指向新节点

将NULL值赋给新节点的next

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 获得尾节点地址
Node* get_tail(Node* L){
  Node *p = L;
  while(p->next!=NULL){ // 当节点不为空时
    p = p->next; // 顺着寻找下一个节点
  }
  return p;
}

// 尾插法
Node* insertTail(Node* tail, ElemType e){
  Node* p = (Node*)malloc(sizeof(Node));
  p->data = e;
  p->prev = tail;
  tail->next = p;
  p->next = NULL;
  return p;
}

指定位置插入

寻找前置节点，让新节点prev指向前置节点

让新节点的next指向后置节点

让前置节点的next的prev指向新节点

前置节点的next指向新节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 指定位置插入数据
int insertNode(Node* L, int pos, ElemType e){
  Node* p = L;
  for (int i = 0; i<pos-1; i++){
    p = p->next;
    if (p==NULL){
      return 0;
    }
  }
  Node* q = (Node*)malloc(sizeof(Node));
  q->data = e;
  q->prev = p;
  q->next = p->next;
  p->next->prev = q;
  p->next = q;
  return 1;
}

删除元素

找到要删除节点的前驱节点，用指针记录要删除的节点

改变p的后继节点以及删除节点的后继节点的前驱来删除节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 删除元素
int delNode(Node* L, int pos){
  Node *p = L;
  for (int i = 0;i<pos-1;i++){ // 找到前驱节点
    p = p->next;
    if (p==NULL){
      return 0;
    }
  }
  if (p->next==NULL){ // 判断删除位置是否超出了表长度
    printf("要删除的位置错误");
    return 0;
  }
  Node* q = p->next; // q指向要删除的节点
  p->next = q->next; // p的next指向q的后继节点
  q->next->prev = p; // q的后继节点的prev指向p
  free(q); // 删除q
  return 1;
}

顺序表与链表