1.链表
#include <iostream>
#include <fstream>
#include <time.h>
#include <map>
using namespace std;
struct Node{
int val;
Node* next;
Node(int v,Node* n):val(v),next(n){};
Node(int v):Node(v,nullptr){};
};
class List{
public:
List()
{
head = new Node(0);
tail = head;
len=0;
}
void addItem(int v)
{
++len;
if(tail==head)
{
Node* tmp=new Node(v);
head->next=tmp;
tail=head->next;
return;
}
Node* tmp = new Node(v);
tail->next = tmp;
tail = tail->next;
}
void Traverse()
{
Node* scan=head->next;
while(scan)
{
cout<<scan->val<<" ";
scan=scan->next;
}
cout<<endl;
}
void SelectSort()
{
Node* scan=head;
for(int i=0;i<len;i++)
{
//cout<<"i:"<<i<<endl;
if(scan==nullptr) break;
//找到scan后的最大节点
Node* tmp=scan;
Node* maxNode=scan->next;
Node* bfMax = scan;
while(tmp->next)
{
if(maxNode->val < tmp->next->val)
{
bfMax = tmp;
maxNode = tmp->next;
}
tmp=tmp->next;
}
//cout<<"maxnode"<<maxNode->val<<endl;
//放入头结点后
bfMax->next = maxNode->next;
maxNode->next = head->next;
head->next= maxNode;
//处理
if(i==0)
scan=maxNode;
}
}
void Reverse()
{
if(len<2) return;
Node *scan=head->next->next;
head->next->next=nullptr;
while(scan)
{
Node* tmp=scan->next;
scan->next=head->next;
head->next=scan;
scan=tmp;
}
}
void DelSame()
{
map<int,int> s;//n-upNum
Node* scan = head->next;
while(scan)
{
if(s[scan->val]) s[scan->val]++;
else s[scan->val]=1;
scan=scan->next;
}
scan=head->next;
Node* bf=head;
while(scan)
{
if(s[scan->val]==1)
{
scan=scan->next;
bf=bf->next;
continue;
}
len--;
s[scan->val]--;
if(scan->next){
Node* tmp=scan;
scan=scan->next;
bf->next=scan;
free(tmp);
}
else{
bf->next=nullptr;
free(scan);
scan=nullptr;
}
}
}
private:
Node* head;
Node* tail;
int len;
};
int main()
{
srand(time(0));
List l;
for(int i=10;i>0;i--)
{
l.addItem(rand()%10);
}
l.SelectSort();
l.Traverse();
l.Reverse();
l.Traverse();
l.DelSame();
l.Traverse();
}
2.树
#include <iostream>
#include <fstream>
#include <map>
#include <stack>
using namespace std;
struct Node
{
int val;
Node* left;
Node* right;
Node(int n):val(n),left(nullptr),right(nullptr){};
};
class BinaryTree{
public:
BinaryTree()
{
root=nullptr;
}
void initTree()
{
}
void addItem(int n)
{
if(root==nullptr)
{
Node* tmp = new Node(n);
root = tmp;
}
else addItem(root,n);
}
void PreOrder()
{
PreOrderHelper(root);
cout<<endl;
}
void PostOrder()
{
stack<bool> visit;
stack<Node*> q;
q.push(root);
visit.push(false);
while(!q.empty())
{
Node* scan=q.top();q.pop();
bool v=visit.top();visit.pop();
if(scan==nullptr) continue;
if(!v)
{
q.push(scan);visit.push(true);
q.push(scan->right);visit.push(false);
q.push(scan->left);visit.push(false);
}
else{
cout<<scan->val<<" ";
}
}
cout<<endl;
}
void DelNum(int n)
{
Node* scan = root;
if(scan->val==n)
{
DelTree(scan);
root=nullptr;
return;
}
while(scan!=nullptr)
{
if(scan->left&&scan->left->val==n)
{
DelTree(scan->left);
scan->left=nullptr;
PreOrder();
return;
}
if(scan->right&&scan->right->val==n)
{
DelTree(scan->right);
scan->right=nullptr;
PreOrder();
return;
}
if(scan->val<n)
{
scan=scan->right;
}
else if(scan->val>n)
{
scan=scan->left;
}
}
cout<<n<<"不存在"<<endl;
}
private:
Node* root;
void addItem(Node* root,int n)
{
//cout<<n<<" aaa"<<endl;
if(root==nullptr) return;
if(n>root->val)
{
if(root->right)
addItem(root->right,n);
else
{
root->right = new Node(n);
}
}
if(n<root->val)
{
if(root->left)
addItem(root->left,n);
else
{
root->left = new Node(n);
}
}
}
void PreOrderHelper(Node* root)
{
if(root==nullptr) return;
if(root) cout<<root->val<<' ';
if(root->left) PreOrderHelper(root->left);
if(root->right) PreOrderHelper(root->right);
}
void DelTree(Node *root)
{
if(root==nullptr) return;
if(root->left)
{
DelTree(root->left);
}
if(root->right)
{
DelTree(root->right);
}
if(root->left==nullptr&&root->right==nullptr)
{
free(root);
root=nullptr;
}
}
void DelTree2(Node *&root)
{
if(root==nullptr) return;
if(root->left)
DelTree(root->left);
if(root->right)
DelTree(root->right);
if(root->left==nullptr&&root->right==nullptr)
free(root);
root=nullptr;
}
};
int main()
{
fstream f("Test3.txt",ios::in);
int n;
f>>n;
BinaryTree t;
for(int i=0;i<n;i++)
{
int x;
f>>x;
t.addItem(x);
}
f.close();
t.PreOrder();
cout<<endl;
t.PostOrder();
}
3.图
#include <iostream>
#include <fstream>
#include <map>
#include <queue>
using namespace std;
class Graph{
public:
int vNum;
int eNum;
int **edge;
bool *visit;
map<int,int> name2v;
map<int,int> v2name;
Graph()
{
fstream f;
f.open("Test2.txt",ios::in);
f>>vNum;
edge=new int*[vNum];
for(int i=0;i<vNum;i++)
edge[i] = new int[vNum];
visit = new bool[vNum];
for(int i=0;i<vNum;i++)
{
for(int j=0;j<vNum;j++)
{
edge[i][j]=0;
edge[j][i]=0;
}
}
for(int i=0;i<vNum;i++)
{
//cout<<i<<endl;
int x;
f>>x;
v2name[i]=x;
name2v[x]=i;
}
f>>eNum;
for(int i=0;i<eNum;i++)
{
int x;int y;int val;
f>>x>>y>>val;
edge[name2v[x]][name2v[y]]=val;
edge[name2v[y]][name2v[x]]=val;
}
}
void Print()
{
for(int i=0;i<vNum;i++)
{
for(int j=0;j<vNum;j++)
{
if(edge[i][j])
{
cout<<v2name[i]<<" "<<v2name[j]<<" "<<edge[i][j]<<endl;
}
}
}
}
void DFS()
{
for(int i=0;i<vNum;i++)
visit[i]=false;
for(int i=0;i<vNum;i++)
{
if(!visit[i]){
DFS(i);
cout<<endl;
}
}
}
void BFS()
{
for(int i=0;i<vNum;i++)
visit[i]=false;
for(int i=0;i<vNum;i++)
{
if(!visit[i]){
BFS(i);
cout<<endl;
}
}
}
void Prime()
{
int *closetid=new int[vNum];
int *dist=new int[vNum];
for(int i=0;i<vNum;i++)
{
closetid[i]=0;
dist[i]=edge[0][i]==0?999999999:edge[i][0];
}
dist[0]=0;
for(int i=0;i<vNum-1;i++)
{
//找到目前最近的
int pos=-1;
int lowcost=99999999;
for(int j=1;j<vNum;j++)
{
if(dist[j]!=0&&dist[j]<lowcost)
{
lowcost=dist[j];
pos=j;
}
}
//处理后续
cout<<v2name[pos]<<" "<<v2name[closetid[pos]]<<" "<<edge[pos][closetid[pos]]<<endl;
dist[pos]=0;
for(int j=1;j<vNum;j++)
{
if(edge[pos][j]&&edge[pos][j]<dist[j])//要有边
{
dist[j]=edge[pos][j];
closetid[j]=pos;
}
}
}
}
void Dijkstra(int s,int end)
{
int *path=new int[vNum];
int *dist=new int[vNum];
bool *visit=new bool[vNum];
//初始化
for(int i=0;i<vNum;i++)
{
visit[i]=false;
dist[i]=edge[s][i]==0?9999999:edge[i][s];
path[i]=s;
}
visit[s]=true;dist[s]=-1;path[s]=-1;
for(int i=0;i<vNum;i++)
{
//找到最短的和它的序号
int k=-1;int lowcost=99999;
for(int j=0;j<vNum;j++)
{
if(visit[j]) continue;
if(dist[j]<lowcost)
{
lowcost=dist[j];
k=j;
}
}
//处理
visit[k]=true;
//更新
for(int j=0;j<vNum;j++)
{
if(visit[j]) continue;//要没有访问过
if(edge[k][j]&&dist[k]+edge[k][j]<dist[j])//要保证有边存在
{
//cout<<"test2:"<<v2name[j]<<endl;
dist[j]=dist[k]+edge[k][j];
path[j]=k;
}
}
}
cout<<"最短路径为：";
cout<<dist[end]<<endl;
int count=0;
int road[vNum];
int e=end;
while(e!=s)
{
road[count++]=e;
e=path[e];
}
count--;
cout<<v2name[s]<<" ";
for(int i=count;i>=0;i--)
{
cout<<v2name[road[i]]<<" ";
}
}
private:
void BFS(int i)
{
queue<int> q;
q.push(i);
while(!q.empty())
{
int tmp=q.front();q.pop();
if(!visit[tmp])
cout<<v2name[tmp]<<" ";
visit[tmp]=true;
for(int j=0;j<vNum;j++)
{
if(edge[tmp][j]&&!visit[j])
{
q.push(j);
}
}
}
}
void DFS(int i)
{
cout<<v2name[i]<<" ";
visit[i]=true;
for(int j=0;j<vNum;j++)
{
if(edge[i][j]&&!visit[j])
{
DFS(j);
}
}
}
};
int main()
{
Graph g;
//g.Print();
//g.BFS();
g.Dijkstra(0,5);
}