线性结构
线性结构主要有以下四种:
- 线性表
- 栈
- 队列
- 栈
每种线性结构都可以用链表或者数组去实现，本身也是属于线性表，个人自学数据结构目前主要用于程序竞赛，所以主要以数组实现为主。
线性表（List）
数据对象集：n个元素构成的有序序列（a1，a2…an）
操作集：线性表L∈List，整数i表示位置，元素X∈ElementType，线性表的基本操作主要有:
1、List MakeEmpty()：初始化一个空线性表L
2、ElementType FindKth( int K, List L )：根据位序K，返回相应元素
3、int Find( ElementType X, List L )：在线性表L中查找X的第一次出现位置
4、void Insert( ElementType X, int i, List L)：在位序i前插入一个新元素X
5、void Delete( int i, List L )：删除指定位序i的元素
6、int Length( List L )：返回线性表L的长度n
线性表c++实现（顺序存储）
#include <bits/stdc++.h>
#define ElementType int
#define Maxsize 10000
using namespace std ;
typedef struct Node{
ElementType Date[Maxsize];
int length = 0 ; // 记录当前存储了多少数据
}List,*qList;
qList MakeEmpty()
{
List newlist ;
return &newlist;
}
void Insert(ElementType X , int i ,qList L) //在位序i前插入一个新元素
{
//1.把i位置开始的元素全部往后移动
if (L->length +1 == Maxsize)
{
cout <<"位置已满，插入失败"<<endl;
return ;
}
for (int j = L->length ; j>i;j--)
L->Date[j] = L->Date[j-1];
//2. 插入新元素
L->Date[i] = X ;
L->length ++ ;
}
void TraversrList(List L ) //遍历输出
{
if (L.length == 0 )
{
cout <<"Empty!"<<endl;
return ;
}
for (int i=0 ;i < L.length ;i++)
cout <<L.Date[i]<<" ";
cout << endl;
}
ElementType FindKth(int K ,List L)//返回第k个元素
{
if (K>=L.length || K<0)
{
cout <<"位置错误"<<endl;
return -1 ;
}
return L.Date[K];
}
int Find (ElementType X , List L) //返回在线性表L中查找X的第一次出现位置
{
for (int i= 0 ;i<L.length ;i++)
if (L.Date[i]==X)
return i;
return -1;
}
void Delete(int i, qList L)
{
if (L->length <i)
{
cout <<"删除位置i无元素！"<<endl;
return ;
}
int date = L->Date[i];
cout <<"位置"<<i<<"删除的元素是："<<date <<endl;
i++;
for (;i<L->length-1 ;i++)
L->Date[i-1] = L->Date[i];
L->length--;
}
int Length(List L)
{
return L.length;
}
int main ()
{
List L = *MakeEmpty(); // 创建线性表
for (int i=0;i<100;i++)
Insert(rand(),i,&L);
Insert(-1,100,&L);
TraversrList(L);
if (Find (-1,L)>=0)
{
cout <<"-1 的位置："<< Find (-1,L)<<endl;
}
else
{
cout <<"未找到！"<<endl;
}
cout <<"位置10的元素为："<< FindKth(10,L)<<endl;
Delete(100,&L);
TraversrList(L);
}
链式存储（有时间再补。。。）
连续存储和链式存储优缺点：
- 连续存储有利于元素的访问，链式存储需要访问某位置的元素需要从头开始寻找。
- 连续存储改变元素顺序时，需要改动很大部分的存储位置，链式结构改变元素只需改变周围结点指针的指向即可。
- 连续存储使用的时连续的空间，内存无法开很大，链式存储使用的空间时不连续的，不需要大片空闲的空间，因此可以大容量存储。
广义表
广义表时线性表的推广，广义表中的单个元素也可以是另一个广义表，但是广义表是非线性的。
多重链表
链表中的节点可能同时属于多个链
- 多重链表中结点的指针域会有多个
- 但包含两个指针域的链表并不一定是多重链表，比如在双向链表 不是多重链表
- 多重链表有广泛的用途： 基本上如树、图这样相对 复杂的数据结构都可以采 用多重链表方式实现存储。
以多重链表实现矩阵为例子：
堆栈（Stack）
数据对象集：一个有0个或多个元素的又穷线性表
操作集:
1、Stack CreateStack( int MaxSize )： 生成空堆栈，其最大长度为MaxSize；
2、int IsFull( Stack S, int MaxSize )：判断堆栈S是否已满；
3、void Push( Stack S, ElementType item )：将元素item压入堆栈；
4、int IsEmpty ( Stack S )：判断堆栈S是否为空；
5、ElementType Pop( Stack S )：删除并返回栈顶元素
栈最大的特点：后进先出
应用
- 函数调用及递归实现
- 深度优先搜索
- 回溯算法
顺序存储实现
#include <bits/stdc++.h>
#define ElementType int
#define Maxsize 10000
using namespace std ;
typedef struct Node{
ElementType Date[Maxsize];
int Top= -1 ; // 记录当前存储了多少数据
}Stack,*qStack;
qStack CreateStack( )//生成空堆栈，其最大长度为MaxSize
{
Stack newstack ;
return &newstack;
}
int IsFull( Stack S )//判断堆栈S是否已满
{
if (S.Top == Maxsize-1)
return 1 ;
else
return 0 ;
}
void Push( qStack S, ElementType item )//将元素item压入堆栈
{
if (IsFull(*S))
{
cout <<"栈满！"<<endl;
return ;
}
S->Date[S->Top+1] = item ;
S->Top ++ ;
}
int IsEmpty ( Stack S )//判断堆栈S是否为空
{
if (S.Top == -1)
return 1 ;
else
return 0 ;
}
ElementType Pop( qStack S )//删除并返回栈顶元素
{
S->Top --;
return S->Date[S->Top+1];
}
int main ()
{
//将0 1 2 3 4 5 6压入栈 并以6 5 4 3 2 1 0输出
Stack s= *CreateStack();
for (int i=0;i<=6;i++)
if (!IsFull(s))
Push(&s , i);
while (!IsEmpty(s))
{
cout <<Pop(&s)<<" ";
}
}
值得一提的是，c++ STL库中已经有现成的栈供我们使用，在程序竞赛中经常会用到，下面会使用现成的Stack去实现表达式求值。
栈实现表达式求值
思路：将中缀表达式转换成后缀表达式，再计算。
- 中缀表达式：运算符号位于两个运算数之间。如：a+b*c-d
- 后缀表达式：运算符号位于两个运算数之后。如：abc*+d-
后缀表达式求值策略：从左向右“扫描”，逐个处理运算数和运算符号
- 运算数：入栈；
- 运算符：从堆栈中弹出适当数量的运算数，计算并结果入栈；
- 最后，堆栈顶上的元素就是表达式的结果值。
问题：括号会改变算数预算符的优先级
解决办法：
不理解的话看下示例：
中缀转后缀：
string change (string mid) // 中缀转后缀
{
string late ;
for (int i = 0; i < mid.length(); i++)
{
if (mid[i] >= '0' && mid[i] <= '9') // 数字直接放入
{
late.push_back(mid[i]);
}
else
{
if (s.empty() || mid[i] == '(') //符号栈 空或者为 （ 直接入栈
{
s.push(mid[i]);
}
else
{
if (mid[i] == ')') //右括号 就把左括号之后的全部输出
{
while (s.top() != '(')
{
late.push_back(s.top());
s.pop();
}
s.pop();
}
else if (rule[s.top()] >= rule[mid[i]]&& s.top()!='(') //如果优先级比栈里的低 先将高优先级的输出（同优先级按从左到右顺序排） 注意别把（输出了
{
while (!s.empty() && rule[s.top()] >= rule[mid[i]]&&s.top() != '(')
{
late.push_back(s.top());
s.pop();
}
s.push(mid[i]);
}
else //其余情况就是优先级比栈头符号里高
s.push(mid[i]);
}
}
}
while (!s.empty()) //将剩下的符号输出
{
late.push_back(s.top());
s.pop();
}
return late;
}
后缀式计算
double calculate (string late)
{
for (int i=0;i<late.length();i++)
{
if (late[i]>='0' && late[i]<='9') //数字先放入栈中
d.push(late[i]-'0');
else
{ //计算设计除法，所以用double
double number1 , number2 ; //符号的话从栈中提取两个数字做运算
number1= d.top();d.pop();
number2= d.top();d.pop();
switch (late[i])
{
case '+': //number1 和 number2的次序千万别弄反了
d.push(number2+number1); break ;
case '-':
d.push(number2-number1);break;
case '*':
d.push(number2*number1);break;
case '/':
d.push(number2/number1);break ;
}
}
}
return d.top();
}
总代码：
#include <bits/stdc++.h>
#include <stack>
using namespace std ;
stack <char> s ; //储存符号
stack <double> d ;//储存数字
map<char, int>rule ; //符号优先级按数字大小排
//2*(9+6/3-5)+4
string change (string mid) // 中缀转后缀
{
string late ;
for (int i = 0; i < mid.length(); i++)
{
if (mid[i] >= '0' && mid[i] <= '9') // 数字直接放入
{
late.push_back(mid[i]);
}
else
{
if (s.empty() || mid[i] == '(') //符号栈 空或者为 （ 直接入栈
{
s.push(mid[i]);
}
else
{
if (mid[i] == ')') //右括号 就把左括号之后的全部输出
{
while (s.top() != '(')
{
late.push_back(s.top());
s.pop();
}
s.pop();
}
else if (rule[s.top()] >= rule[mid[i]]&& s.top()!='(') //如果优先级比栈里的低 先将高优先级的输出 注意别把（输出了
{
while (!s.empty() && rule[s.top()] >= rule[mid[i]]&&s.top() != '(')
{
late.push_back(s.top());
s.pop();
}
s.push(mid[i]);
}
else //其余情况就是优先级比栈头符号里高
s.push(mid[i]);
}
}
}
while (!s.empty()) //将剩下的符号输出
{
late.push_back(s.top());
s.pop();
}
return late;
}
double calculate (string late)
{
for (int i=0;i<late.length();i++)
{
if (late[i]>='0' && late[i]<='9')
d.push(late[i]-'0');
else
{
double number1 , number2 ;
number1= d.top();d.pop();
number2= d.top();d.pop();
switch (late[i])
{
case '+':
d.push(number2+number1); break ;
case '-':
d.push(number2-number1);break;
case '*':
d.push(number2*number1);break;
case '/':
d.push(number2/number1);break ;
}
}
}
return d.top();
}
int main ()
{
rule['+'] = 0 ; // 设立数字便于优先级比较
rule['-'] = 0 ; // 同优先级按从左到右顺序排
rule['*'] = 1 ;
rule['/'] = 1 ;
rule['('] = 2 ;
string mid , late ; // 中缀 ， 后缀
cin >> mid;
late = change(mid);
cout <<late<<endl ;
cout <<calculate(late);
}
队列
数据对象集：一个有0个或多个元素的有穷线性表
操作集：长度为MaxSize的队列Q Queue，队列元素item ∈ ElementType
1、Queue CreatQueue( int MaxSize )：生成长度为MaxSize的空队列；
2、int IsFullQ( Queue Q, int MaxSize )：判断队列Q是否已满；
3、void AddQ( Queue Q, ElementType item )： 将数据元素item插入队列Q中；
4、int IsEmptyQ( Queue Q )： 判断队列Q是否为空；
5、ElementType DeleteQ( Queue Q )：将队头数据元素从队列中删除并返回
特点：先进先出
顺序存储实现
#include <bits/stdc++.h>
#define ElementType int
#define Maxsize 10000
using namespace std ;
typedef struct QUEUE {
ElementType Date[Maxsize];
int rear=0 ;
int front=0;
}Queue;
Queue CreatQueue( )//生成长度为MaxSize的空队列
{
Queue q ;
return q ;
}
int IsFullQ( Queue Q)//判断队列Q是否已满
{
if (Q.rear +1 == Q.front)
return 1 ;
else
return 0;
}
void AddQ( Queue &Q, ElementType item )//将数据元素item插入队列Q中
{
if (IsFullQ(Q))
{
cout <<"队满！"<<endl;
return ;
}
Q.Date[Q.rear]=item;
Q.rear = (Q.rear +1)%Maxsize;
}
int IsEmptyQ( Queue Q )//判断队列Q是否为空
{
if (Q.front == Q.rear )
return 1;
else
return 0;
}
ElementType DeleteQ( Queue &Q )//将队头数据元素从队列中删除并返回
{
cout <<"删除的元素为："<<Q.Date[Q.front]<<endl ;
Q.front = (Q.front+1)%Maxsize ;
}
int main ()
{
Queue q = CreatQueue ();
AddQ(q,100);
AddQ(q,55);
AddQ(q,22);
DeleteQ(q);
DeleteQ(q);
DeleteQ(q);
}
STL 中也有现成队列可以使用，主要有两种，一种是普通队列：queue ，还有一种是优先队列：priority_queue，优先队列主要的优点是可以将队列中的元素自动排序，排序的规则可自定义。
队列再算法中的应用：
- 宽度优先搜索