• 微信公众号：美女很有趣。 工作之余，放松一下，关注即送10G+美女照片！

2小时前 1次浏览

# [NEFU 数据结构]阶段二复习

## 栈

### 顺序存储栈

``````#include<bits/stdc++.h>
using namespace std;
const int MAXSIZE=105;
typedef struct {
int data[MAXSIZE];
int top;
}SeqStack;

void Init(SeqStack &S){S.top=-1;}
bool Empty(SeqStack S){return S.top==-1;}
void Push(SeqStack &S,int x){S.data[++S.top]=x;}
int Pop(SeqStack &S){return S.data[S.top--];}
int Top(SeqStack S){return S.data[S.top];}

int main(){
SeqStack S;
Init(S);
Push(S,1);Push(S,2);
cout<<"栈顶："<<Top(S)<<endl;
cout<<"栈顶出队:"<<Pop(S)<<endl;
Pop(S);
if(Empty(S))printf("Stack Emptyn");
else printf("Stack not Emptyn");
return 0;
}
``````

### 链栈

``````#include<bits/stdc++.h>
using namespace std;

typedef struct StackNode{
int data;
struct StackNode *next;

StackNode *s;
s=(StackNode*)malloc(sizeof(StackNode));
s->data=x;s->next=top;
top=s;
}
int ret=top->data;
StackNode *p=top;
top=top->next;free(p);
return ret;
}

int main(){
int x;
Init(Stk);
Push(Stk,1);Push(Stk,2);
cout<<"栈顶："<<Top(Stk)<<endl;
cout<<"栈顶出队:"<<Pop(Stk)<<endl;
Pop(Stk);
if(Empty(Stk))printf("Stack Emptyn");
else printf("Stack not Emptyn");
return 0;
}
``````

## 队列

### 顺序存储循环队列

``````#include<bits/stdc++.h>
using namespace std;
const int MAXSIZE=105;
typedef struct{
int data[MAXSIZE];
int front,rear;
}SeQueue;
void Init(SeQueue &Q){Q.front=Q.rear=0;}
bool Empty(SeQueue Q){return Q.front==Q.rear;}
void Push(SeQueue &Q,int x){
Q.data[Q.rear]=x;
Q.rear=(Q.rear+1)%MAXSIZE;
}
int Pop(SeQueue &Q){
int ret=Q.data[Q.front];
Q.front=(Q.front+1)%MAXSIZE;
return ret;
}

int main(){
SeQueue Q;
Init(Q);
Push(Q,1);Push(Q,2);
if(Empty(Q))printf("Queue Empty!n");
else printf("Queue not Empty!n");
Pop(Q);
return 0;
}

``````

### 链队

``````#include<bits/stdc++.h>
using namespace std;
typedef struct Node{
int data;
struct Node *next;
typedef struct{
LQNode *front,*rear;

p->next=NULL;Q->front=Q->rear=p;
}
p->data=x;p->next=NULL;
Q->rear->next=p;Q->rear=p;
}
int ret=0;
Q->front->next=p->next;ret=p->data;
if(p==Q->rear)Q->rear=Q->front;//只有一个元素的话，出队后为空
free(p);
return ret;
}

int main(){
Init(Q);
Push(Q,1);Push(Q,2);
if(Empty(Q))printf("Queue Empty!n");
else printf("Queue not Empty!n");
Pop(Q);
return 0;
}

``````

## 树

### 创建树

``````typedef struct BinNode{
char data;
//可以多维护一些信息，深度啊，度数啊之类的，可以直接建树的时候维护掉
struct BinNode *left;
struct BinNode *right;
}BinNode,*BinTree;

void CreateBinTree(BinTree &T){
char ch;cin>>ch;
if(ch=='@')T=NULL;
else{
T=new BinNode;
T->data=ch;
CreateBinTree(T->left);
CreateBinTree(T->right);
}
}
``````

### 遍历

#### 递归遍历

``````void PreOrder(BinTree T){//先序遍历
if(T){
printf("%c",T->data);
PreOrder(T->left);
PreOrder(T->right);
}
}

void InOrder(BinTree T){//中序遍历
if(T){
InOrder(T->left);
printf("%c",T->data);
InOrder(T->right);
}
}

void BackOrder(BinTree T){//后序遍历
if(T){
BackOrder(T->left);
BackOrder(T->right);
printf("%c",T->data);
}
}
``````

#### 非递归遍历

``````#include<stack>//STL栈，不用手写了

void PreOrder2(BinTree T){//非递归先序遍历
if(T){
stack<BinTree>stk;
stk.push(T);
BinTree cur = T;
while(!stk.empty()){
cur = stk.top();stk.pop();
cout<<cur->data;
if(cur->right!=NULL)stk.push(cur->right);//栈后进先出
if(cur->left!=NULL)stk.push(cur->left);
}
}
}
void InOrder2(BinTree T){//非递归中序遍历
if(T){
stack<BinTree>stk;
BinTree cur = T;
while(!stk.empty()||cur!=NULL){
if(cur!=NULL){
stk.push(cur);
cur = cur->left;
}else{
cur = stk.top();stk.pop();
cout<<cur->data;
cur = cur->right;
}
}
}
}

void BackOrder2(BinTree T){//非递归后序遍历
if(T){
stack<BinTree>stk1;
stack<BinTree>stk2;
BinTree cur = T;
stk1.push(cur);
while(!stk1.empty()){
cur = stk1.top();stk1.pop();
stk2.push(cur);
if(cur->left!=NULL)stk1.push(cur->left);
if(cur->right!=NULL)stk1.push(cur->right);
}
while(!stk2.empty()){
cur = stk2.top();stk2.pop();
cout<<cur->data;
}

}
}
``````

#### 层序遍历

``````#include<queue>//STL队列 不用手写了

int deg0,deg1,deg2;
void BFS(BinTree T){//可以顺便统计不同度数的结点个数
if(T){
queue<BinTree>q;
q.push(T);
while(!q.empty()){
else deg1++;
}
}
}
``````

### 信息统计

``````int CountLeaf(BinTree T){//统计叶子结点个数
int res=0;
if(T==NULL)return 0;
if(T->left==NULL)return 1+CountLeaf(T->right);
else return CountLeaf(T->left)+CountLeaf(T->right);
}
int GetDepth(BinTree T){//统计树的深度
int LeftDepth=0,RightDepth=0;
if(T==NULL)return 0;
else{
LeftDepth=GetDepth(T->left);
RightDepth=GetDepth(T->right);
if(LeftDepth>RightDepth)return LeftDepth+1;
else return RightDepth+1;
}
}
int dep[105];//dep表层数，记录第i层有多少个结点
int GetWidth(BinTree T){//统计二叉树的最大宽度
if(T==NULL)return 0;

//BFS层序遍历
queue<BinTree>q;q.push(T);
queue<int>depth;depth.push(1);

while(!q.empty()){
int now_depth=depth.front();depth.pop();
dep[now_depth]++;
depth.push(now_depth+1);
}
depth.push(now_depth+1);
}
}
int ret=0;
for(int i=1;i<=105;i++)ret=max(ret,dep[i]);
return ret;
}
``````

### 其他

``````bool Compare(BinTree A,BinTree B){//判断两棵树是否相等
if(A==NULL&&B==NULL)return true;
else if(A==NULL||B==NULL)return false;
if(A->data!=B->data)return false;
bool left=Compare(A->left,B->left);
bool right=Compare(A->right,B->right);
return left&&right;
}

void SwapSon(BinTree T){//交换每个结点的左右孩子
if(T==NULL)return;
if(T->left==NULL&&T->right==NULL)return;//叶子结点不用换了
BinTree tmp=T->left;
T->left=T->right;
T->right=tmp;
SwapSon(T->left);
SwapSon(T->right);
}

BinTree Find(BinTree T,char ch){
if(T==NULL)return NULL;
else if(T->data==ch)return T;
else{
BinTree p=Find(T->left,ch);
if(p!=NULL)return p;
else return Find(T->right,ch);
}
}
``````

### 找祖先

``````#include<iostream>
#include<cstdio>

using namespace std;

typedef struct BinNode{
char data;
struct BinNode *left;
struct BinNode *right;
struct BinNode *father;
}BinNode,*BinTree;

void CreateBinTree(BinTree &T,BinTree &fa){
char ch;cin>>ch;
if(ch=='*')T=NULL;
else{
T=new BinNode;
T->data=ch;T->father=fa;
CreateBinTree(T->left,T);
CreateBinTree(T->right,T);
}
}

BinTree Find(BinTree T,char ch){
if(T==NULL)return NULL;
else if(T->data==ch)return T;
else{
BinTree p=Find(T->left,ch);
if(p!=NULL)return p;
else return Find(T->right,ch);
}
}

void Ancestors(BinTree T){
if(T->father==NULL)printf("没有祖先结点");
else{
while(T->father){
cout<<T->father->data<<" ";
T=T->father;
}
}
}

int main(){
BinTree T,fa=NULL;
CreateBinTree(T,fa);
char ch;cin>>ch;
BinTree A=Find(T,ch);
if(A==NULL)printf("%c不存在",ch);
else Ancestors(A);
return 0;
}

``````

## 图

### 建图

``````typedef struct ArcNode{
struct ArcNode * nextarc;
}ArcNode;

typedef struct VNode{
int data;
ArcNode *firstarc;

typedef struct{
int vexnum,arcnum;
}Graph;

void CreateUDG(Graph &G){//无向图
cin>>G.vexnum>>G.arcnum;
for(int i=1;i<=G.vexnum;i++){
cin>>G.verlist[i].data;
G.verlist[i].firstarc=NULL;
}
for(int i=1;i<=G.arcnum;i++){
int x,y;cin>>x>>y;

ArcNode * p1= new ArcNode;
ArcNode * p2= new ArcNode;

p1->nextarc=G.verlist[x].firstarc;
G.verlist[x].firstarc=p1;

p2->nextarc=G.verlist[y].firstarc;
G.verlist[y].firstarc=p2;
}
}

void CreateDG(Graph &G){//有向图
cin>>G.vexnum>>G.arcnum;
for(int i=1;i<=G.vexnum;i++){
cin>>G.verlist[i].data;
G.verlist[i].firstarc=NULL;
}
for(int i=1;i<=G.arcnum;i++){
int x,y;cin>>x>>y;

ArcNode * p1= new ArcNode;

p1->nextarc=G.verlist[x].firstarc;
G.verlist[x].firstarc=p1;
}
}
``````

### BFS

``````void BFS(Graph G){//无向图，有向图是特殊的无向图，也可以直接用
queue<int>Q;
bool vis[MAXN];
memset(vis,0,sizeof(vis));
cout<<"v1 ";
Q.push(1);
vis[1]=true;
while(!Q.empty()){
int u=Q.front();Q.pop();
ArcNode* p=G.verlist[u].firstarc;
while(p!=NULL){
}
p=p->nextarc;
}
}
}
``````

### DFS

``````bool vis[MAXN];
//如果你要看是否存在某一条路径
//dfs调用的u传入起点
//然后看vis[v]就可以知道是否存在u->v的一条路径了

void DFS(Graph G,int u){
ArcNode* p=G.verlist[u].firstarc;
vis[u]=true;
cout<<"v"<<u<<" ";
while(p!=NULL){
}
p=p->nextarc;
}
}

``````

``````bool vis[MAXN];

void DFS(Graph G,int u){
stack<int>stk;
stk.push(u);vis[u]=true;
cout<<"v1 ";
while(!stk.empty()){
int tt=stk.top();
ArcNode *p=G.verlist[tt].firstarc;
p=p->nextarc;
}
}
if(p==NULL)stk.pop();
}
}
``````

### 输出邻接表

``````void Print(Graph G){
for(int i=1;i<=G.vexnum;i++){
ArcNode* p=G.verlist[i].firstarc;
cout<<i<<":";
while(p!=NULL){
if(p->nextarc!=NULL)cout<<" ";
p=p->nextarc;
}
cout<<endl;
}
}
``````

### 统计度数

``````int in[MAXN],out[MAXN];
void GetInfo(Graph G){
for(int i=1;i<=G.vexnum;i++){
ArcNode* p=G.verlist[i].firstarc;
while(p!=NULL){
out[i]++;
p=p->nextarc;
}
}
}
``````

## C++ STL相关应用

### 头文件与命名空间

`万能头文件`

``````#include<bits/stdc++.h>
``````

``````#include<cstdio>//使用c语言 printf scanf
#include<iostream>//使用c++ cin cout操作
#include<cstring>//使用c语言字符串相关函数,memcpy
#include<string> //使用C++ string
#include<stack>//使用STL的栈
#include<queue>//使用STL的队列
#include<vector>//使用vector
#include<algorithm>//使用sort等直接算法
#include<set>//使用STL set
#include<map>//使用STL map
``````

`命名空间`

``````using namespace std;
``````

### 使用STL stack

`.empty()`判栈空，空返回true否则false
`.push(x)`x入栈
`.size()`获取栈元素数量
`.pop()`栈顶元素出栈
`.top()`获取栈顶元素

``````#include<bits/stdc++.h>
using namespace std;

int main(){
stack<int>stk_int;//创建一个存放int类型的栈

//.empty()判栈空，如果为空返回true,否则false
if(stk_int.empty())printf("栈空n");

//.size()得到栈的大小
printf("栈的大小%dn",stk_int.size());

//把1入栈
stk_int.push(1);
stk_int.push(2);

//获取栈顶
//cout 输出，endl换行。不会的花用printf代替就行
cout<<stk_int.top()<<endl;

//栈顶出栈
stk_int.pop();

printf("现在栈的大小%dn",stk_int.size());

//获取新的栈顶
cout<<stk_int.top()<<endl;
return 0;
}
``````

### 使用STL queue

`.push(x)`x入队
`.empty()`判队空
`.pop()`队首出队
`.front()`获取队首
`.size()`获取队内元素数量

``````#include<bits/stdc++.h>
using namespace std;

int main(){
queue<int>queue_int;//创建一个存放int类型的

//.empty()判队列空，如果为空返回true,否则false
if(queue_int.empty())printf("队列空n");

//.size()得到队列的大小
printf("队列的大小%dn",queue_int.size());

//入队
for(int i=1;i<=10;i++){
queue_int.push(i);
}

//获取队首
//cout 输出，endl换行。不会的花用printf代替就行
cout<<"队首元素为"<<queue_int.front()<<endl;

//队首出队
queue_int.pop();

printf("现在队列的大小%dn",queue_int.size());

//获取新的队首
cout<<"队首元素为"<<queue_int.front()<<endl;

//手动清空队列，栈也可以这么弄
while(!queue_int.empty()){
printf("当前队首元素为%dn",queue_int.front());
printf("出队n");
queue_int.pop();
}
if(queue_int.empty())printf("队列已经被清空了");
return 0;
}
``````

### 使用STL sort

``````#include<bits/stdc++.h>
using namespace std;
const int N=105;
int a[N]={1,4,5,2,5,6,8};
int b[N]={1,4,5,2,5,6,8};
int c[N];
bool cmp1(int a,int b){return a>b;}
bool cmp2(int a,int b){return a<b;}
int main(){
for(int i=0;i<7;i++)printf("%d ",a[i]);puts("");
for(int i=0;i<7;i++)printf("%d ",b[i]);puts("");

sort(a,a+7);
for(int i=0;i<7;i++)printf("%d ",a[i]);puts("");

sort(b,b+7,greater<int>());
for(int i=0;i<7;i++)printf("%d ",b[i]);puts("");

int n;cin>>n;
for(int i=1;i<=n;i++)cin>>c[i];
sort(c+1,c+1+n,cmp1);//根据cmp1从大到小排，注意sort前两个参数分别+1和+n因为我们要排序的数据是1～n不是0～n-1
for(int i=1;i<=n;i++)cout<<c[i]<<" ";
cout<<endl;
sort(c+1,c+1+n,cmp2);//根据cmp2从小到大排
for(int i=1;i<=n;i++)cout<<c[i]<<" ";
cout<<endl;
return 0;
}
``````