算法入门（6）——线性数据结构

前言

数据结构是一种数据组织、管理和存储的格式。它是相互之间存在一种或多种特定关系的数据元素的集合。——百度百科
我们要学习的数据结构可以帮助我们更方便地解决问题。不同的数据结构有不同的特性，有的是优点，有的是缺点。没有十全十美的数据结构，在解决问题时要根据实际需求选择不同的数据结构。本篇我们将讨论基本的几种线性数据结构，在最后我会放一个表格，展示每种数据结构对某些操作的支持复杂度。

1. 数组

数组是最常见的一种数据结构，它的特点是支持O ( 1 ) O(1)O(1)访问和修改指定下标的元素。值得注意的是，在 C++ 的 STL 里实现了一个vector类，是一个动态数组，支持动态修改元素以及增删。

2. 链表

链表分为单链表、双向链表、循环链表等。链表中的元素是离散存储的，每个元素有一个或两个（数量取决于类型）指针指向相邻元素。它支持O ( 1 ) O(1)O(1)增删元素，但是不支持随机下标访问，只能遍历。一个简单的实现：（双向链表）

structnode{// 每个节点node*nxt,*pre;// 指向前后的指针intval=0;// 元素的值};node*head,*tail;// 头和尾，初始化要创建两个空元素占位voidinit(){head=newnode();tail=newnode();head->pre=nullptr;head->nxt=tail;tail->pre=head;tail->nxt=nullptr;}voidaddafter(intv,node*p){// 在p后面加上这个新元素node*q=newnode();q->val=v;q->nxt=p->nxt;q->nxt->pre=q;q->pre=p;p->nxt=q;}voidaddhead(intv){addafter(v,head);}voidaddtail(intv){addafter(v,tail->pre);}voiddelafter(node*p){// 从p后面删除一个元素，需要保证这个元素后面有元素node*tmp=p->nxt;p->nxt=tmp->nxt;tmp->nxt->pre=p;deletetmp;}voiddelhead(){delafter(head);}voiddeltail(){delafter(tail->pre->pre);// 注意一个pre的话会把tail给删了，这样会出问题}vector<int>forloop(){// 遍历并将元素放到一个vector中vector<int>ans;node*p=head->nxt;while(p!=tail){ans.push_back(p->val);p=p->nxt;}returnans;}voiddelall(){// 清空整个链表，退出前要调用node*p=head;while(p!=tail){p=p->nxt;deletep->pre;}deletetail;}

3. 栈

栈是一种后进先出（LIFO）的数据结构，也就是说，最后进入栈的元素将会最先被弹出。栈就像煎煎饼，最后被煎好的煎饼放在最上面，也就只能先吃这个煎饼。C++STL 有stack类实现了栈，只能访问栈顶。手写栈很简单，而且支持访问栈中间的元素（不建议这么做，除非你清除知道你在做什么）：

intstk[100007],tp=0;voidpush(intv){// 压入新元素stk[++tp]=v;}voidpop(){// 弹出栈顶tp--;}inttop(){// 访问栈顶returnstk[tp];}

4. 队列

队列是一种先进先出（FIFO）的数据结构，先入队的元素先被弹出，就像排队打饭，先排队的人先打到饭。STL 有queue实现队列，支持入队和出队，以及访问队头队尾。还有deque双端队列，可以从队头和队尾分别插入和弹出。手写队列：

intque[100007],head=1,tail=0;voidpush(intv){que[++tail]=v;}voidpop(){head++;}intfront(){returnque[head];}intback(){returnque[tail];}

5. 对比

6. 小结

今天我们总结了常见的线性数据类型，希望大家好好掌握，为更难的算法学习打下坚实基础！