链表
相对于顺序表，链表的插入和删除操作更加高效，但是访问链表中的元素需要遍历整个链表。
链表是一种线性表的链式存储结构，它使用一组不连续的存储单元来存储线性表中的数据元素。
特点
链表中的数据元素不连续存储，而是通过指针链接在一起。
链表中的数据元素可以通过指针访问，但是不能通过下标直接访问。
为了表示每个数据元素 与其后继数据元素 之间的逻辑关系，对于数据元素 来说，除了存储其本身的信息外，还需存储一个指向其后继数据元素的指针。这两部分组成数据元素 的存储映像，称为结点（Node）。
节点包括两个部分：数据域和指针域。数据域用于存储数据元素的信息，指针域用于存储指向后继节点的指针。
n个节点通过指针链接成一个链表，这种链表称为单链表。此外，每个节点还包含一个指针域，用于指向前驱节点，这种链表称为双向链表。如果链表成环，则称为循环链表。
graph LR
%% 核心结构
HEAD((HEAD)) -->|next| Node1
HEAD -.->|prev| NULL_HEAD[/NULL/]
Node1 -->|prev| HEAD
Node1 -->|data| DATA1[Data 1]
Node1 -->|next| Node2
Node2 -->|prev| Node1
Node2 -->|data| DATA2[Data 2]
Node2 -->|next| Node3
Node3 -->|prev| Node2
Node3 -->|data| DATA3[Data 3]
Node3 -->|next| NULL_TAIL[/NULL/]
%% 样式定义
classDef head fill:#1e3a8a,stroke:#bde0fe,color:#fff;
classDef node fill:#1e90ff,stroke:#bde0fe,color:#fff;
classDef data fill:#32CD32,stroke:#fff,color:#000;
classDef null fill:#555,stroke:#fff,color:#fff;
classDef nextPointer stroke:#FFA500,stroke-width:2px;
classDef prevPointer stroke:#00FF00,stroke-width:2px,dashed;
class HEAD head
class Node1,Node2,Node3 node
class DATA1,DATA2,DATA3 data
class NULL_HEAD,NULL_TAIL null
%% 箭头样式
linkStyle 0,3,6,9 stroke:#FFA500,stroke-width:2px
linkStyle 1,4,7,10 stroke:#00FF00,stroke-width:2px,dashed
以上就是双向链表的图示。
🔵 蓝色圆角矩形：头节点HEAD
🔷 蓝色矩形：普通节点
🟩 绿色区块：数据域
⬛ 灰色菱形：NULL标识
单向链表顾名思义，单向链表就是只能从前往后遍历的链表。
实现代码这里我先写一个单向链表，代码如下：
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239#include#include using namespace std;const int MAXSIZE = 10000;typedef long long ElementType;struct Linklist{ ElementType data; struct Linklist* next;};Linklist* init(){ Linklist* head = new Linklist; head->next = NULL; return head;}void insertHead(Linklist* Head, ElementType data){ Linklist* p = new Linklist; p->data = data; //先把p的next指向L的next，再把L的next指向p p->next = Head->next; Head->next = p;}void insertTail(Linklist* Tail, ElementType data){ Linklist* p = new Linklist; p->data = data; //先把p的next指向NULL p->next = NULL; //找到链表的最后一个节点 Linklist* q = Tail; while (q->next != NULL) q = q->next; //把q的next指向p q->next = p;}void insertNode(Linklist* Node, ElementType data, int i){ //由于头节点不存储数据，所以插入下标从1开始 if(Node==NULL) {cout << "链表为空" << endl; return; } Linklist* p = new Linklist; Linklist* q = Node; //找到第i个节点的前一个节点 for(int j=1; jnext == NULL) { cout << "插入位置错误" << endl; return; } q = q->next; } p->data = data; p->next = q->next; q->next = p;}void deleteNode(Linklist* Node, int i){ Linklist* p = Node; //这里下标从1开始 //找到第i个节点的前一个节点 for(int j=1; jnext == NULL) { cout << "删除位置错误" << endl; return; } p = p->next; } if(p->next == NULL) {cout << "删除位置错误" << endl; return; } Linklist* q = p->next; // 保存要删除的节点(一定要先保存) p->next = p->next->next; // 连接下下个节点 delete(q); // 删除节点}int GetLength(Linklist* Node){ int len = 0; Linklist* p = Node; while(p->next != NULL) { len++; p=p->next; } return len;}int ClearList(Linklist* Node){ Linklist* p = Node; while(p->next != NULL) { Linklist* q = p->next; p->next = p->next->next; delete(q); } return 0;}ElementType GetElem(Linklist* Node, int i){ /// 这里下标从1开始 Linklist* p = Node; for(int j=0; jnext == NULL) { cout << "获取位置错误" << endl; return -1; } p = p->next; } return p->data;}ElementType RGetElem(Linklist* Node, int i){ /// 找到倒数第i个元素 /* 利用双指针，先让p和q都指向头节点，然后让p先走i步，然后p和q一起走， 直到p走到最后一个节点，此时q指向的就是倒数第i个节点 时间复杂度O(n)，比先遍历找到尾巴节点，再从尾巴节点开始遍历的方法O(2n)要快 */ Linklist* p = Node; Linklist* q = Node; for(int j=1; jnext; //这里下标从1开始 while(p->next != NULL) { p = p->next; q = q->next; } return q->data;}void Reverse(Linklist* Node){ Linklist* p = NULL; Linklist* q = Node->next; Linklist* r = NULL; while(q != NULL) { r=q->next; q->next = p; p = q; q = r; } Node->next = p;}int DelMid(Linklist* Node){ if(Node == NULL||Node->next == NULL) {cout << "链表为空" << endl; return -1; } //删除中间节点 //对于长度为奇数的链表，删除中间节点 //对于长度为偶数的链表，删除中间两个节点靠后的那个 Linklist* p = Node; Linklist* q = Node; while(p->next != NULL && q->next->next != NULL) { p = p->next; q = q->next->next; } Linklist* r=p->next; if(r==NULL) return -1; p->next = p->next->next; delete(r); return 0;}int PrintNd(Linklist* Node){ Linklist* p = Node; while(p->next != NULL) { cout << p->next->data << " "; p = p->next; } return 0;}int main(){ SetConsoleOutputCP(CP_UTF8); Linklist* L = init(); for(int i=1; i<=5; i++) insertHead(L, i); for(int i=1; i<=10; i++) insertTail(L, i); // while(L->next != NULL) // { // cout << L->next->data << " "; // L = L->next; // } //注意此方法直接修改L的地址，遍历完后L指向NULL（）最后一个节点 //正确的遍历方法应该是先创建一个temp指针指向L，再遍历temp Linklist* temp = L; while(temp->next != NULL) { cout << temp->next->data << " "; temp = temp->next; } cout << endl << "-----------------" << endl; insertNode(L, 100, 5); cout << "在下标5处插入100" << endl; PrintNd(L); cout << endl << "-----------------" << endl; deleteNode(L, 5); cout << "删除下标为5的节点" << endl; PrintNd(L); cout << endl << "-----------------" << endl; Reverse(L); cout << "反转链表" << endl; PrintNd(L); cout << endl << "-----------------" << endl; DelMid(L); cout << "删除中间节点" << endl; PrintNd(L); cout << endl << "-----------------" << endl; cout << "链表第四个元素为" << GetElem(L, 4) << endl; cout << "链表倒数第四个元素为" << RGetElem(L, 4) << endl; cout << "-----------------" << endl; cout << "链表长度为" << GetLength(L) << endl; cout << "-----------------" << endl; ClearList(L); cout << "清空链表" << endl; cout << "链表长度为" << GetLength(L) << endl; cout << "-----------------" << endl; system("pause");}
我们注意到，对于单链表，我们遍历时只能向尾部遍历，不能向头部遍历，这样对于一些如删除中间节点等操作，需要用双指针来实现。下面我们来学习单向循环链表、双向链表。
单向循环链表单向循环链表和单向链表的区别在于，单向链表的最后一个节点的next指针指向NULL，而单向循环链表的最后一个节点的next指针指向头节点。
这是一个可以让链表某个指定元素成环的代码：
12345678910int makeLoop(Linklist* Node, int idx){ if(idx<1||idx>GetLength(Node)) return -1; Linklist* tail = Node; Linklist* target = Node; for(int i=1; inext; while(tail->next != NULL) tail = tail->next; tail->next = target; return 0;}
这个代码可以让原单链表中下标为idx的元素成环，即让该元素指向自己。例如：
原链表为1->2->3->4->5，调用makeLoop(Node, 3)，则链表变为1->2->3->4->5->3
在遍历单向循环链表时，我们只需要判断当前节点的next指针是否指向头节点，就可以知道是否遍历完了整个链表。剩下的代码和单向链表一样。
那么如何判断一个链表是否有循环链表呢？我们可以用双指针的方法，定义两个指针p和q，初始时p指向头节点，q指向头节点的下一个节点，然后让p每次走一步，q每次走两步，如果p和q相遇，那么说明链表有循环链表。
12345678910111213bool isLoop(Linklist* Node){ if(Node == NULL||Node->next == NULL) return false; Linklist* p = Node; Linklist* q = Node; whlie(q!=NULL && q->next!=NULL) { p = p->next; q = q->next->next; if(p==q) return true; } return false;}
那么如何找到循环链表的入口节点呢？我们可以再做个cnt计数，先求出环的长度，然后让p和q都指向头节点，然后让p先走环的长度步，然后p和q一起走，直到p和q相遇，此时p指向的就是循环链表的入口节点。
1234567891011121314151617181920212223242526272829303132333435Linklist* findLoopNode(Linklist* Node){ if(Node == NULL||Node->next == NULL) return NULL; Linklist* p = Node; Linklist* q = Node; // 判断是否有环 while(q!=NULL && q->next!=NULL) { p=p->next; q=q->next->next; if(p==q) { // 有环，求环的长度 Linklist* r=q; int cnt=1; while(r->next!=p) { r=r->next; cnt++; } // 找到环的入口节点 // 一个指针先走cnt步，然后两个指针一起走 // 直到两个指针相遇，此时指针指向的就是环的入口节点 q=Node, p=Node; for(int i=0; inext; while(p!=q) { p=p->next; q=q->next; } return p;//返回循环链表入口节点指针 } } return NULL;//没有环}
双向链表链式存储结构的节点中只有一个指示直接后继的指针域，由此，从某个结点出发只能顺指针向后寻找其它节点。若要寻找结点的直接前驱，则必须从表头指针出发。换句话说，在单链表中，查找直接后继的执行时间为 O(1)，而查找直接前驱的执行时间为 O(n)。
为克服单链表这种单向性的缺点，可利用双向链表Double Linked List。在双向链表的节点中有两个指针域，一个指向直接后继，另一个指向直接前驱。
实现代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178#include #include using namespace std;const int MAXSIZE = 10000;typedef long long ElementType;class DoubleLinklist {private: struct Node { ElementType data; Node* next; Node* prev; Node(ElementType val = 0) : data(val), next(nullptr), prev(nullptr) {} }; Node* head;public: DoubleLinklist() { head = new Node(); // Dummy head node } ~DoubleLinklist() { ClearList(); delete head; } int insertHead(ElementType data) { Node* p = new Node(data); p->next = head->next; p->prev = head; if (p->next != nullptr) p->next->prev = p; head->next = p; return 0; } int insertTail(ElementType data) { Node* p = new Node(data); Node* tail = head; while (tail->next != nullptr) tail = tail->next; tail->next = p; p->prev = tail; return 0; } int insertNode(ElementType data, int i) { if (head == nullptr) { cout << "链表为空" << endl; return -1; } Node* q = head; for (int j = 1; j < i; j++) { if (q->next == nullptr) { cout << "插入位置错误" << endl; return -1; } q = q->next; } Node* p = new Node(data); p->next = q->next; p->prev = q; q->next = p; if (p->next != nullptr) p->next->prev = p; return 0; } void deleteNode(int i) { Node* p = head; for (int j = 1; j < i; j++) { if (p->next == nullptr) { cout << "删除位置错误" << endl; return; } p = p->next; } if (p->next == nullptr) { cout << "删除位置错误" << endl; return; } Node* q = p->next; p->next = q->next; if (p->next != nullptr) p->next->prev = p; delete q; } int GetLength() { int len = 0; Node* p = head; while (p->next != nullptr) { len++; p = p->next; } return len; } int ClearList() { if (head == nullptr) { cout << "链表为空" << endl; return -1; } Node* p = head->next; while (p != nullptr) { Node* q = p; p = p->next; delete q; } head->next = nullptr; return 0; } ElementType GetElem(int i) { Node* p = head; for (int j = 0; j < i; j++) { if (p->next == nullptr) { cout << "获取位置错误" << endl; return -1; } p = p->next; } return p->data; } ElementType RGetElem(int i) { Node* p = head; Node* q = head; for (int j = 1; j < i; j++) p = p->next; while (p->next != nullptr) { p = p->next; q = q->next; } return q->data; } void Reverse() { Node* cur = head->next; Node* prev = nullptr; Node* next = nullptr; while (cur != nullptr) { next = cur->next; cur->next = prev; cur->prev = next; prev = cur; cur = next; } head->next = prev; if (prev != nullptr) prev->prev = head; } int DelMid() { if (head == nullptr || head->next == nullptr) { cout << "链表为空" << endl; return -1; } Node* p = head; Node* q = head; while (q->next != nullptr && q->next->next != nullptr) { p = p->next; q = q->next->next; } Node* r = p->next; if (r == nullptr) return -1; p->next = r->next; if (r->next != nullptr) r->next->prev = p; delete r; return 0; } void Print() { Node* p = head->next; while (p != nullptr) { cout << p->data << " "; p = p->next; } cout << endl; }};
总结
比较项目
存储结构
顺序表
链表
空间
存储空间
预先分配，会出现闲置或溢出现象
动态分配，不会出现存储空间闲置或溢出现象
存储密度
不用为表示节点间的逻辑关系而增加额外的存储，存储密度等于1
需要借助指针来体现元素间的逻辑关系，存储密度小于1
时间
存取元素
随机存取，按位置访问元素的时间复杂度为 O(1)
顺序存取，按位置访问元素时间复杂度为 O(n)
插入、删除
平均移动约表中一半元素，时间复杂度为 O(n)
不需要移动元素，确定插入、删除位置后，时间复杂度为 O(1)
适用情况
-
1）表长变化不大，且能事先确定变化的范围2）很少进行插入或删除操作，经常按位置访问数据元素
1）表长变化较大2）频繁进行插入或删除操作
栈栈是一种只能在一端进行插入和删除操作的线性表，它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。因此，栈又被称为后进先出LIFO（Last In First Out）的线性表。
栈的插入操作叫做进栈（push），栈的删除操作叫做出栈（pop）。栈的插入和删除操作都是在一端进行的，这一端称为栈顶，另一端称为栈底。
那么栈作为一种特殊的线性表，我们可以通过顺序表和链表来实现。
顺序栈顺序栈是使用顺序表实现的栈，顺序栈的插入和删除操作都是在栈顶进行的，因此，我们只需要在顺序表的尾部进行插入和删除操作即可。
实现代码我这里直接用类来写了，顺序栈的代码如下：
123456789101112131415161718192021222324252627282930313233343536373839#include#include using namespace std;typedef long long ElementType;class Stack{private: ElementType *_data; int _top; int _capacity;public: Stack(int size=200005) //可以指定大小，默认为200005 { _capacity=size; _data = new ElementType[_capacity]; _top = -1; } ~Stack(){delete[] _data;}//析构函数，释放内存；当作用域结束时，析构函数自动调用 bool isEmpty(){return _top==-1;} bool isFull(){return _top==_capacity-1;} void push(ElementType x) { if(isFull()){cout<<"Stack is full"<
链栈链栈是使用链表实现的栈，链栈的插入和删除操作都是在栈顶进行的，因此，我们只需要在链表的头部进行插入和删除操作即可。
实现代码链栈的代码如下：
123456789101112131415161718192021222324252627282930313233343536#include#include using namespace std;typedef long long ElementType;class Stack{private: ElementType _data; Stack *_next;public: Stack(){_next = NULL;} bool isEmpty(){return _next == NULL;} void push(ElementType d) { Stack* p = new Stack(); p->_data=d; p->_next=this->_next; this->_next=p; } ElementType pop() { if(isEmpty()){cout<<"Stack is empty"<_next->_data; Stack *p=this->_next; this->_next=this->_next->_next; delete p; return d; } ElementType top() { if(isEmpty()){cout<<"Stack is empty"<_data; }};
但以上代码有个不安全的地方：我写链表结构时，实现方式是一个哑头节点 dummy head node模型，this 永远是头节点，它的数据是无效的，真正的数据从 _next 开始。
改进方法123456789101112131415161718192021222324252627282930313233class Stack{private: struct Node { ElementType _data; Node* _next; Node(ElementType d,Node* n=NULL):_data(d),_next(n){} // 构造函数，使用初始化列表 }; Node* _top;public: Stack(){_top = NULL;} ~Stack(){while(!isEmpty())pop();} bool isEmpty(){return _top == NULL;} void push(ElementType d) { _top = new Node(d,_top); } ElementType pop() { if(isEmpty()){cout<<"Stack is empty"<_data; Node *p=_top; _top=_top->_next; delete p; return d; } ElementType top() { if(isEmpty()){cout<<"Stack is empty"<_data; }};
这里说下cpp专有的构造函数初始化列表 Constructor Initialization List语法：
1Node(ElementType d,Node* n=NULL):_data(d),_next(n){}
Node(ElementType d, Node* n = nullptr)是构造函数声明，表示在创建Node对象时可以传进两个参数，第一个d要存入的数据，第二个n该节点的下一个指针，默认值是nullptr。
后面的: data(d), next(n)是初始化列表，这与下面的写法更高效：
12345Node(ElementType d, Node* n = nullptr){ _data = d; _next = n;}
具体使用上，我们可以这样Node* p=new Node(20,q)，这个语句是创建一个Node对象，并将20存入_data，q存入_next，然后返回该对象的指针p。
队列队列是一种先进先出FIFO First In First Out 的线性表。它只允许在表的一端进行插入，而在另一端进行删除。在队列中，允许插入的一端叫做队尾rear，允许删除的一端叫做队头front。队列的插入操作叫做入队 enqueue ，队列的删除操作叫做出队dequeue 。
那么队列作为一种特殊的线性表，我们可以通过顺序表和链表来实现。
顺序队列简单顺序队列我们先用顺序表和两个指针_rear和_front来实现。
1234567891011121314151617181920212223242526272829303132333435class queue{private: ElementType *_arr; int _front, _rear, _size;public: queue(int size=100005) { _arr = new ElementType[size]; _front = _rear = 0; _size = size; } ~queue(){delete[]_arr;} bool isEmpty(){return _front == _rear;} void push(ElementType x) { if(_rear==_size) { if(_front == 0){cout<< "Queue is full"<
注意到这中写法，如果队列的_rear到尽头了，需要将前面的元素移到后面，这样可以让队列的空间利用率更高。但是，要移动的元素很大，那么这种写法效率不高。于是，循环队列应运而生。
循环队列循环队列是顺序队列的一种改进，它将队列的首尾相连，形成一个环。这样，当队列的_rear到尽头时，可以继续从队列的头部开始，这样就可以避免顺序队列中需要移动元素的问题。
具体怎样移动呢？我们小学就学过一个问题，23个带序号的小朋友围成一圈，老师从序号为1的小朋友开始绕圈数数，数到114514时指的是序号为几的小朋友？我们可以直接用23对114514取余，得到的结果就是序号。
那么对于循环队列，我们也可以用这个模整体容量的方法来，来计算队列的_rear和_front的位置。
我们令_arr下标0位置为队头，不存储数据，便于使用(_rear+1)%_size==_front判断队列是否已满、_rear==_front判断队列是否为空。
123456789101112131415161718192021222324252627282930class queue{private: ElementType *_arr; int _front, _rear, _size;public: queue(int size=100005) { _arr = new ElementType[size+1]; _front = _rear = 0; _size = size; } ~queue(){delete[]_arr;} bool isEmpty(){return _front == _rear;} bool isFull(){return (_rear+1)%_size==_front;} void push(ElementType x) { if(isFull()){cout<< "Queue is full"<
实际上还有一种写法，就是_cnt记录当前队列中元素的个数，在push和pop时，都让元素个数加一减一，然后判断_cnt==_size 和_cnt==0即可。（也就省去了(_rear+1)%_size==_front和_rear==_front😅）
链式队列这个也就是用链表来实现队列，掌握链表的话，这个应该不难。
这个链式的就没必要作循环了，链表本身就是可以无限扩展的😋。
123456789101112131415161718192021222324252627282930313233343536373839#includetemplate ///新学到的模板语法，使用如queue q;可以指定类型class queue{private: struct Node { ElementType _data; Node *_next; }; Node *_rear, *_front;public: queue() { _front = new Node; _rear = _front; _front->_next = NULL; } ~queue(){while(!empty())pop();delete _front;} bool empty(){return _front == _rear;} void push(ElementType x) { Node *p=new Node; p->_data=x; p->_next=NULL; _rear=_rear->_next=p; } void pop() { if(empty()){std::cout << "Queue is empty" << std::endl; return;} Node *p=_front->_next; _front->_next=p->_next; if(_rear==p)_rear=_front; delete p; } ElementType front(){return (empty())?ElementType():_front->_next->_data;} ElementType back(){return (empty())?ElementType():_rear->_data;}};
双端队列双端队列是一种特殊的线性表，它允许在两端进行插入和删除操作。
顺序双端队列这里由于可以两端插入，我们直接用循环队列的写法。那么对于在队首插入push_front我们需要在_front前插入一个元素，那么_front就要减一，但是要注意当_front=0，减一后为-1，需要加上_size，然后取余。同样地，对于在队尾插入push_back，也需要加一后再加上_size，然后取余。剩余的成员函数与循环队列类似。
123456789101112void push_front(ElementType x){ if(isFull()){cout<< "Queue is full"<
链式双端队列链式双端队列的实现与链式队列类似，只是多了在队首插入元素的操作。
1234567void push_front(ElementType x){ Node *p=new Node; p->_data=x; p->_next=_front->_next; _front->_next=p;}
刷题现在已经学完大部分常用的线性表了，那么接下来就看看这些线性表在实际中都有哪些应用吧。
以下题目均出自洛谷：
P1996 约瑟夫问题题目$n$ 个人围成一圈，从第一个人开始报数,数到 $m$ 的人出列，再由下一个人重新从 $1$ 开始报数，数到 $m$ 的人再出圈，依次类推，直到所有的人都出圈，请输出依次出圈人的编号。$1 \le m, n \le 100$
解答显然地，我们可以用循环链表来实现。我们构造一个循环链表，然后从链表头开始遍历，每遍历到第 $m$ 个节点，就删除这个节点，然后继续遍历，直到链表为空。
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465#include using namespace std;#define ll long long#define endl '\n'int n,m;struct Lli{ int data; struct Lli* next;};Lli* init(){ Lli* head = new Lli; head->next = NULL; return head;}int iTail(Lli* Tail, ElementType data){ Lli* p = new Lli; p->data = data; p->next = NULL; Lli* q = Tail; while (q->next != NULL) q = q->next; q->next = p; return 0;}int makeLoop(Lli* Node){ Lli* head=Node; Lli* tail=Node; while(tail->next!=NULL) tail=tail->next; tail->next=head->next; return 0;}int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cin >> n >> m; Lli* L=init(); for(int i=1; i<=n; i++) iTail(L,i); makeLoop(L); Lli* pre=L; Lli* cur=L->next; while(n--) { for(int i=1; inext; } cout << cur->data << " "; pre->next=cur->next; delete cur; cur=pre->next; } return 0;}
这样写还是太麻烦了，我们直接用循环表来实现，也就代码短点🤪
123456789101112131415161718192021222324#include using namespace std;#define ll long long#define endl '\n'#define maxn 200005#define minn 1005int n,m,i=0;int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cin >> n >> m; vector a(n); for(int i=0; i
时间复杂度为 $O(n*2)$ 对于这个数据规模是可以接受的😅
P1160 队列安排题目题目太长，我这里简短说下：
有一个长度为 $n$ 的队列，将数字 $1$ 放到队首后，有 $n-1$ 个操作，每个操作对应数字 $i=2,3,4 \cdots n$ 的插入位置：
0 x将编号i的数字插入到编号为x的数字前面（左边）；
1 x将编号i的数字插入到编号为x的数字后面（右边）。
接下来有 $m$ 个询问，每个询问对应一个数字 $i$ ，删除编号为 $i$ 的数字，并输出最终删除后的队列。
解答我们注意到这题需要大量地插入和删除，自然我们想到用链表来实现，对于数字 $i$ 的位置，我们可以用一个数组来存储该节点指针。
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798#include using namespace std;#define ll long long#define endl '\n'#define maxn 200005#define minn 1005int n,p,pp,m;class Li{private: struct Node { int dt; Node *nt,*ft; }; Node *a[maxn]; Node *head;public: Li() { head=new Node; Node *p= new Node; p->dt=1; p->nt=NULL; p->ft=head; head->nt=p; a[1]=p; } void inL(int i,int x) { Node *t=a[x]; Node *p=new Node; Node *tt=t->ft; p->dt=i; tt->nt=p; p->nt=t; p->ft=tt; t->ft=p; a[i]=p; } void inR(int i,int x) { Node *t=a[x]; Node *p=new Node; Node *tt=t->nt; p->dt=i; if(tt)tt->ft=p; //具有后继节点才能连接 p->ft=t; t->nt=p; p->nt=tt; a[i]=p; } void rm(int x) { if(!a[x])return; Node *t=a[x]; Node *lt=t->ft; Node *rt=t->nt; if(lt)lt->nt=rt; //删除前要判断是否有前驱 if(rt)rt->ft=lt; //删除后要判断是否有后继 delete t; a[x]=NULL; } void print() { Node *t=head->nt; while(t!=NULL) { cout << t->dt << " "; t=t->nt; } cout << endl; }};int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cin >> n; Li L; for(int i=2; i<=n; i++) { cin >> p >> pp; if(pp==0)L.inL(i,p); else if(pp==1)L.inR(i,p); } cin >> m; while(m--) { int x; cin >> x; L.rm(x); } L.print(); return 0;}
P1540 [NOIP 2010 提高组] 机器翻译题目题目太长，我这里简短说下：
题目要求模拟一个具有内存的翻译器，内存大小为 $m$ 、单词个数为 $n$ ，翻译时会把已经翻译过的单词存入内存中，这样遇到内存中已经存在的单词就可以不翻译，如果内存存满了，则删除最先存入的单词。$1 \le m \le 100$ ， $1 \le n \le 1000$ 。
解答我们可以用队列来实现。但值得注意的是，如果要用STL库中的queue那么是不能通过遍历该队列来找到判断是否存入单词，那么只能用STL中的deque。
12345678910111213141516171819202122232425262728#include using namespace std;#define endl '\n'int n,m,cnt=0;int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cin >> m >> n; vector a(n); for(int i=0; i>a[i]; deque b; for(int i=0; i
P4387 【深基15.习9】验证栈序列题目题目大意是：给定一个入栈序列和出栈序列，这两序列都没有重复元素，判断是否合法。
解答我们直接可以用栈进行模拟，开一个对于出栈序列的指针pos，如果入栈序列依次入栈时，栈顶元素等于出栈序列的pos位置元素，那么出栈并pos加一（后移一位），如果出栈后栈顶元素又等于pos位置元素，继续进行以上操作，直到不相等为止。之后继续入栈，直到入栈序列全部入栈，如果此时栈为空，那么说明合法，否则不合法。
12345678910111213141516171819202122232425262728293031323334#include using namespace std;#define ll long long#define endl '\n'int q;ll n;int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cin >> q; while(q--) { ll pos=0; cin >> n; vector a(n),b(n); stack st; for(ll i=0; i> a[i]; for(ll i=0; i> b[i]; for(ll i=0; i
表达式求值我们对于一个表达式，比如最简单的四则运算表达式 $1+(4 \div 2+3 \times 3)-3 \times [121 \div 11-(12+3) ]$ 直接输入 1+(4/2+3*3)-3*(121/11-(12+3)) 由于计算符号的顺序，是无法直接进行运算的。我们需要将其转化为某种可以让计算机读取到计算顺序的表达式，然后再进行逐项计算。
这里涉及的观点有点像树，如果要了解树，请先看数据结构笔记4。
我们写的表达式就是中缀表达式，而计算机读取的则是后缀表达式，如下面的表格：
中缀表达式
后缀表达式
2*2-(2-4/2)*1
2 2 * 2 4 2 / - 1 * -
x*y-x-y
x y * x - y -
(x+y)*(x+y)-2*x*y
x y + x y + * x y * -
12-2*(35+14/(1-34/2+17))
12 2 35 14 1 34 2 / - 17 + / + * -
转化对于一个中值表达式我们可以将其用运算符优先级来转化，比如对于表达式 1+(4/2+3*3)-3*(121/11-(12+3)) 我们可以将其转化为树，如下：
首先按照这个字符串从左到右扫描，按照以下规则：
如果遇到数字，则直接输出（到后缀表达式）
如果遇到计算符号
如果栈空，则直接入栈
判断运算符号与栈顶符号的优先级
如果优先级大于栈顶符号，则直接入栈
对于左括号(，在栈外时，属于高优先级，在栈外时，属于低优先级。即直接入栈，入栈后优先级变为低优先级
对于右括号)，在栈外时，属于低优先级，在栈外时，属于高优先级。即当栈顶元素不是左括号)，持续出栈并输出，直到遇到左括号)结束输出，左括号出栈，不输出
如果优先级小于等于栈顶符号，则持续出栈并输出，直到栈空或者遇到优先级小于当前符号的符号，再将当前符号入栈
扫描结束后，将栈中元素依次出栈并输出。
代码实现在代码实现前，我们需要定义一个运算符优先级表，如下：
符号
优先级
+ -
1
* /
2
( )
0
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758#include using namespace std;#define ll long long#define ull unsigned long long#define endl '\n'map rule;string s,res;stack st;int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> s; rule['+']=1,rule['-']=1,rule['*']=2,rule['/']=2,rule['(']=0,rule[')']=0; for(int i=0; i<(int)s.size(); i++) { if(isdigit(s[i])) { while(i<(int)s.size() && isdigit(s[i])) { cout << s[i]; i++; } cout << " "; i--; } else { if(s[i]=='(') st.push(s[i]); else if(s[i]==')') { while(st.top()!='(' && !st.empty()) { cout << st.top() << " "; st.pop(); } if(!st.empty())st.pop(); } else // 这里我们直接考虑不是括号的情况 { // 优先考虑栈顶元素优先级大于等于当前元素的情况 while(!st.empty() && rule[st.top()] >= rule[s[i]]) { cout << st.top() << " "; st.pop(); } // 剩下就是栈顶元素优先级小于当前元素，直接入栈 st.push(s[i]); } } } while(!st.empty()){cout << st.top() << " "; st.pop();} return 0;}
这样，我们就将中缀表达式转化为了后缀表达式，接下来我们就可以进行计算了。
计算对于后缀表达式，我们可以直接用栈来模拟计算，如下：
如果遇到数字，则直接入栈
如果遇到运算符，则将栈顶两个元素出栈，进行运算，并将结果入栈
代码实现1234567891011121314151617181920212223242526272829void sol(string s){ stack t; for(int i=0; i<(int)s.size(); i++) { if(isdigit(s[i])) { ll x=0; while(i<(int)s.size() && isdigit(s[i])) { x=x*10+s[i]-'0'; i++; } i--; t.push(x); } else if(s[i]==' ') continue; else { ll x=t.top(); t.pop(); ll y=t.top(); t.pop(); if(s[i]=='+')t.push(y+x); else if(s[i]=='-')t.push(y-x); else if(s[i]=='*')t.push(y*x); else if(s[i]=='/')t.push(y/x); } } cout << t.top() << endl;}
如此，后缀表达式的作用就体现出来，后缀表达式直接可以进行计算，而不需要考虑运算符的优先级。
综合的代码我们先读取一个中缀表达式，然后将其转化为后缀表达式，最后计算后缀表达式并输出。
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394#include using namespace std;#define ll long long#define ull unsigned long long#define endl '\n'map rule;string res;string build(){ string s,res; stack st; cin >> s; for(int i=0; i<(int)s.size(); i++) { if(isdigit(s[i])) { while(i<(int)s.size() && isdigit(s[i])) { res+=s[i]; i++; } res+=' '; i--; } else { if(s[i]=='(') st.push(s[i]); else if(s[i]==')') { while(st.top()!='(' && !st.empty()) { res+=st.top(); res+=' '; st.pop(); } if(!st.empty())st.pop(); } else { while(!st.empty() && rule[st.top()] >= rule[s[i]]) { res+=st.top(); res+=' '; st.pop(); } st.push(s[i]); } } } while(!st.empty()){res+=st.top(); res+=' '; st.pop();} return res;}void sol(string s){ stack t; for(int i=0; i<(int)s.size(); i++) { if(isdigit(s[i])) { ll x=0; while(i<(int)s.size() && isdigit(s[i])) { x=x*10+s[i]-'0'; i++; } i--; t.push(x); } else if(s[i]==' ') continue; else { ll x=t.top(); t.pop(); ll y=t.top(); t.pop(); if(s[i]=='+')t.push(y+x); else if(s[i]=='-')t.push(y-x); else if(s[i]=='*')t.push(y*x); else if(s[i]=='/')t.push(y/x); } } cout << t.top() << endl;}int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); rule['+']=1,rule['-']=1,rule['*']=2,rule['/']=2,rule['(']=0,rule[')']=0; sol(build()); return 0;}
好了现在已经掌握表达式的大部分内容了，来试试这题吧。P1175 表达式的转换
