表

线性表

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

空表：大小为0的表
首节点：存在唯一一个被称为第一个的元素
尾节点：存在唯一一个被称为最后一个的元素
前驱：前驱
后继：后继

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

顺序表实现

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

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

建表

#define MAXSIZE 100
typedef int ElemType; // 方便存储不同类型数据的情况下修改数据类型

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

初始化

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

尾插元素

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

插入元素

// 插入元素
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;

}

最坏时间复杂度

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

遍历列表

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

删除元素

// 删除元素并返回删除的元素
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变量存储

查找元素

// 查找元素
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函数在堆中动态分配内存建表

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

// 建表 
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，表示到达链表尾部

初始化

// 单链表初始化-建立头节点
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指向原头节点指向的下一个节点

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

顺序很重要

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时便找到了尾节点

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

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

再让新节点指向NULL

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

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

指定位置插入元素

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

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

// 指定位置插入元素
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的后继节点实现删除

并释放删除节点的空间

// 删除节点
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;
  
}

获取链表长度

// 获取链表长度
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指向同一个节点，循环以上操作

// 释放链表
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

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;
    }
};

找到环的入口

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

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

有

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

多拿出一圈来将y约掉，则

当时，即快指针转一圈与慢指针相遇的情况下，，即两者会在环的入口处相遇

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

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

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;
        }
    };

双向链表

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

建表

typedef int ElemType;
typedef struct node{
  ElemType data;
  struct node *prev, *next;
}Node;

初始化

与单链表相同

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

头插法

让新节点的prev指向头节点

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

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

// 头插法
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

// 获得尾节点地址
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指向新节点

// 指定位置插入数据
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的后继节点以及删除节点的后继节点的前驱来删除节点

// 删除元素
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;
}

顺序表与链表

本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可

红魔咖啡馆

【数据结构】表

表

线性表

顺序表实现

建表

初始化

尾插元素

插入元素

遍历列表

删除元素

查找元素

使用动态顺序表实现

链表实现

单链表

初始化

头插元素

尾插元素

指定位置插入元素

删除节点

获取链表长度

释放链表

注意

单项循环链表

判断是否有环

找到环的入口

双向链表

建表

初始化

头插法

尾插法

指定位置插入

删除元素

顺序表与链表