[NEFU 数据结构]阶段二复习
[NEFU 数据结构]阶段二复习
阶段二只考编程题目，所以进行常见带代码整理
考串到图的遍历，由于是写代码，所以我尽量精简一些
由于个人习惯，可能C和C++代码会混合起来，所以编写的时候，请写.cpp文件，并使用C++的编译方式。
因为这个玩意写的比较早后面老师又更新了范围之类的，所以你们挑着看吧，就代码模块而言这篇文档应该足够了。
如果按老师说的加难度，那我觉得应该是算法和思维方面加难度吧。
另外STL很爽，可以学一下。但是考试尽量别用吧，下面代码为了简化可能直接使用STL，你们可以自己手打栈和队列
如何编写和编译运行C++文件
机房主要是codeblock和dev c++，所以我以这两个举例
明天去机房更新（如果我空的话）
codeblock
dev c++
栈
顺序存储栈
#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,*LinkStack;
void Init(LinkStack &top){top=NULL;}
bool Empty(LinkStack top){return top==NULL;}
int Top(LinkStack top){return top->data;}
void Push(LinkStack &top,int x){
StackNode *s;
s=(StackNode*)malloc(sizeof(StackNode));
s->data=x;s->next=top;
top=s;
}
int Pop(LinkStack &top){
int ret=top->data;
StackNode *p=top;
top=top->next;free(p);
return ret;
}
int main(){
int x;
LinkStack Stk;
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;}
int Head(SeQueue Q){return Q.data[Q.front];}
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);
cout<<Head(Q)<<endl;
if(Empty(Q))printf("Queue Empty!n");
else printf("Queue not Empty!n");
Pop(Q);
cout<<Head(Q)<<endl;
return 0;
}
链队
#include<bits/stdc++.h>
using namespace std;
typedef struct Node{
int data;
struct Node *next;
}LQNode,*LinkQNode;
typedef struct{
LQNode *front,*rear;
}LQueue,*LinkQueue;
void Init(LinkQueue &Q){
LinkQNode p;
Q=(LinkQueue)malloc(sizeof(LQueue));//申请头尾指针节点
p=(LinkQNode)malloc(sizeof(LQNode));//申请链队头节点
p->next=NULL;Q->front=Q->rear=p;
}
void Push(LinkQueue &Q,int x){
LinkQNode p=(LinkQNode)malloc(sizeof(LQNode));
p->data=x;p->next=NULL;
Q->rear->next=p;Q->rear=p;
}
int Pop(LinkQueue &Q){
int ret=0;
LinkQNode p=Q->front->next;
Q->front->next=p->next;ret=p->data;
if(p==Q->rear)Q->rear=Q->front;//只有一个元素的话，出队后为空
free(p);
return ret;
}
int Head(LinkQueue Q){return Q->front->next->data;}
bool Empty(LinkQueue Q){return(Q->front==Q->rear);}
int main(){
LinkQueue Q;
Init(Q);
Push(Q,1);Push(Q,2);
cout<<Head(Q)<<endl;
if(Empty(Q))printf("Queue Empty!n");
else printf("Queue not Empty!n");
Pop(Q);
cout<<Head(Q)<<endl;
return 0;
}
字符串
貌似没啥好写的，应该不会很难，感兴趣的话可以看看C++ STL的string.
如果搞你的话应该是不让你用string.h里的库函数的
树
创建树
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()){
BinTree head = q.front();q.pop();//获取队首后出队
cout<<head->data;
if(head->left==NULL&&head->right==NULL)deg0++;
else if(head->left!=NULL&&head->right!=NULL)deg2++;
else deg1++;
if(head->left)q.push(head->left);
if(head->right)q.push(head->right);
}
}
}
信息统计
这些玩意其实都可以直接在建树的时候就维护起来的，下面是建树后的一些递归算法。
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()){
BinTree head=q.front();q.pop();
int now_depth=depth.front();depth.pop();
dep[now_depth]++;
if(head->left){
q.push(head->left);
depth.push(now_depth+1);
}
if(head->right){
q.push(head->right);
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);
}
}
找祖先
创建的时候加个father指针方便回溯
#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{
int adjvex;
struct ArcNode * nextarc;
}ArcNode;
typedef struct VNode{
int data;
ArcNode *firstarc;
}VNode,AdjList[MAXN];
typedef struct{
AdjList verlist;
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->adjvex=y;
p1->nextarc=G.verlist[x].firstarc;
G.verlist[x].firstarc=p1;
p2->adjvex=x;
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->adjvex=y;
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){
if(!vis[p->adjvex]){
cout<<"v"<<p->adjvex<<" ";
vis[p->adjvex]=true;
Q.push(p->adjvex);
}
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){
if(!vis[p->adjvex]){
DFS(G,p->adjvex);
}
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;
while(p&&vis[p->adjvex]){
p=p->nextarc;
}
while(p&&!vis[p->adjvex]){
cout<<"v"<<p->adjvex<<" ";
vis[p->adjvex]=true;
stk.push(p->adjvex);
p=G.verlist[p->adjvex].firstarc;
}
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){
cout<<p->adjvex;
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){
in[p->adjvex]++;
out[i]++;
p=p->nextarc;
}
}
}
C++ STL相关应用
头文件与命名空间
万能头文件
#include<bits/stdc++.h>
如果万能头没法编译通过又不想设置编译参数，那么根据需求使用下面这些头文件（和C语言头文件不冲突的）
#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;
}
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
THE END
二维码