(CQUPT 的某数据结构homework)

基于线性表的图书信息管理

首先，因为我们要输入输出汉语，所以需要更改编码成为utf-8
我使用的是devcpp
所以其他版本编译器更改编码的就请自己去查询更改方式。
工具：
编译选项：
编译时加入以下命令，打勾，下面粘上此代码
-std=c++11 -finput-charset=utf-8

/*
*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef  pair<int,int> pi ;
#define if1(x) for(int i =1 ;i<=x;i++)
#define if0(x) for(int i = 0;i<x;i++)
#define jf0(x) for(int j = 0;j<x;j++)
#define jf1(x) for(int j = 1;j<=x;j++)
struct node_book
{string name_book;string  id_book;float price_book;//int myid;};
unordered_map<string ,int>mmp;//去重用
list<node_book>  books;
vector<node_book>  high_books;
double evrage;
int books_num,idx;
void output(){for(auto j:books){cout<<j.id_book<<" "<<j.name_book<<" ";printf("%.2f\n",j.price_book);}
}
void add(string id,float price, string name){node_book new_book;new_book.id_book = id;new_book.name_book = name;new_book.price_book = price;books.push_back(new_book);books_num++;evrage+= price;
}
void init(){books_num = 0;float price;string name,id;while(1){cin>>id>>name>>price;if(id=="0"&&name=="0"&&price==0)break;add(id,price,name);mmp[id]++;// evrage += price;}
}
void func1(){init();cout<<books_num<<endl;output();
}
void func2(){init();evrage /= books_num;for(auto& j:books){float te = j.price_book;if(te < evrage)  j.price_book*=1.2;else   j.price_book*=1.1;}printf("%.2f\n",evrage);cout<<books_num<<endl;output();
}
void func3(){init();high_books.clear();high_books.push_back(*books.begin());float high_price = high_books[0].price_book;for(auto j:books){if(j.price_book>high_price){high_books.clear();high_books.push_back(j);high_price = j.price_book;}else if(high_price==j.price_book){high_books.push_back(j);}}cout<<high_books.size()<<endl;for(auto j: high_books){cout<<j.id_book<<" "<<j.name_book<<" ";printf("%.02f\n",j.price_book);}
}
void func4(){init();float price;string name,id;int place,idx = 1;cin>>place;cin>>id>>name>>price;node_book new_book;new_book.id_book = id;new_book.name_book = name;new_book.price_book = price;list<node_book>::iterator pos ;pos = books.begin();for(auto j:books){idx++;pos++;if(idx==place){books.insert(pos,new_book);books_num++;cout<<books_num<<endl;output();return;}}cout<<"抱歉，入库位置非法!\n";}
void func5(){init();float price;string name,id;int place,idx = 1;cin>>place;list<node_book>::iterator pos ;pos = books.begin();for(auto j:books){idx++;pos++;if(idx==place){books.erase(pos);books_num--;}}cout<<books_num<<endl;output();
}
void func6(){init();int place;list<node_book>::iterator pos ;vector<list<node_book>::iterator> dela;pos = books.begin();for(auto j:books){//cout<<mmp[j.id_book]<<endl;if(mmp[j.id_book]>1){mmp[j.id_book]--;dela.push_back(pos);books_num--;}pos++;}for(auto it:dela){books.erase(it);}cout<<books_num<<endl;output();
}
void tishi(){printf("\n输入1测试：基于顺序（链式）存储结构的图书信息表的创建和输出\n");cout<<"输入2测试：基于顺序（链式）存储结构的图书信息表的修改\n";cout<<"输入3测试：基于顺序（链式）存储结构的图书信息表的最贵图书的查找\n";cout<<"输入4测试：基于顺序（链式）存储结构的图书信息表的新图书的入库\n";cout<<"输入5测试：基于顺序（链式）存储结构的图书信息表的旧图书的出库\n";cout<<"输入6测试：基于顺序（链式）存储结构的图书信息表的图书去重\n";cout<<"输入-1，退出程序\n";
}
int main(){int op =1;while(op!=0){tishi();cin>>op;if(op== 1)func1();else if(op==2)func2();else if(op==3)func3();else if(op==4)func4();else if(op==5)func5();else if(op==6)func6();books.clear();}return 0;
}

基于栈的算术表达式求值

普通应用即可

#include<bits/stdc++.h>
using namespace std;
#define MAXSIZE 100
#define N 10
string S;
//运算符栈 
unordered_map<char,int>mmp;
void init0(){mmp['('] = mmp[')']=3;mmp['*'] = mmp['/'] = 2;mmp['+'] = mmp['-'] = 1;
}stack<char> sta_op;
stack<int> sta_num;
int verify(char ch)
{//cout<<ch<<endl;if(ch=='+')return 0;else if(ch=='-')return 1;else if(ch=='*')return 2;else if(ch=='/')return 3;else if(ch=='(')return 4;else if(ch==')')return 5;else{return 100;}}
void push_num(int& idx){int j = idx;int temp = 0;while(S[j]>='0'&&S[j]<='9'){temp*=10;temp+=S[j]-'0';j++;}sta_num.push(temp);idx = j-1;
}
int judge(int a,char e,int b)
{//cout<<e<<endl;if(e=='+')return a+b;else if(e=='-')return a-b;else if(e=='*')return a*b;else if(e=='/')return a/b;else{cout<<"error!"<<endl;return -1;}}
void func1(int& idx){char ch = S[idx];if(ch=='('||ch=='+'||ch=='-')sta_op.push(ch);//of course +-不需要考虑运算顺序else if(ch == '*'||ch=='/'){if(S[idx+1]>='0'&&S[idx+1]<='9'){//*/在后面跟上的是数字的情况下，一定是可以直接进行运算的//那么不妨在这种情况下面直接开算int j = idx+1;int temp = 0;while(S[j]>='0'&&S[j]<='9'){temp*=10;temp+=S[j]-'0';j++;}sta_num.push(temp);idx = j-1;//int la = sta_num.top();sta_num.pop();int pre = sta_num.top();sta_num.pop();int ans = judge(pre,ch,la);sta_num.push(ans);}else{sta_op.push(ch);//只能等后面在来运算辣//就是等下一个左括号运算完成并出栈的时候来运算此符号}}else if(ch==')'){while(sta_op.top()!='('){int la = sta_num.top();sta_num.pop();int pre = sta_num.top();sta_num.pop();int ans = judge(pre,sta_op.top(),la);sta_op.pop();sta_num.push(ans);}sta_op.pop();if(sta_op.top()=='*'||sta_op.top()=='/'){////这个时候就要运算89行处的*/法辣int la = sta_num.top();sta_num.pop();int pre = sta_num.top();sta_num.pop();int ans = judge(pre,sta_op.top(),la);sta_op.pop();sta_num.push(ans);}}}
int func(){cin>>S;if(S=="=")return 0;for(int i=0;S[i]!='\0';i++){if(S[i]>='0'&&S[i]<='9')push_num(i);elsefunc1(i);}//*/法已经算完辣，+-法没有顺序可言，但是为了减少代码量就不优化辣。while(!sta_op.empty()){int la = sta_num.top();sta_num.pop();int pre = sta_num.top();sta_num.pop();int ans = judge(pre,sta_op.top(),la);sta_op.pop();sta_num.push(ans);} cout<<sta_num.top()<<endl;sta_num.pop();return 1;
}
int main()
{int ti=1;while(ti){cout<<"\n请输入中缀表达式的算数表达式\n仅输入一个 = 时结束程序\n";if(!func())break;}return 0;
}

基于字符串模式匹配算法的病毒感染检测问题

kmp即可

#include<bits/stdc++.h>
using namespace std;
#define ll long longtypedef  pair<int,int> pi ;
#define if1(x) for(int i =1 ;i<=x;i++)
#define if0(x) for(int i = 0;i<x;i++)
#define jf0(x) for(int j = 0;j<x;j++)
#define jf1(x) for(int j = 1;j<=x;j++)
const int mod = 1e9+7;
const int inf = 0x3f3f3f3f;
const int N = 1e5 + 10, M = 1e6 + 10;
char p[N], s[M];
int n, m;
int ne[N];void tishi(){cout<<"请输入病毒的ONA序列和人的NDNA序列,用空格隔开\n";cout<<"当输入的两个DNA序列为 0 0 时退出程序！\n";
}
bool solve(){string x,y;cin>>x>>y;n = y.size();m = x.size();if0(n){s[i+1]= y[i];}if0(m) p[i+1] = x[i];if(x=="0"&&y=="0")return 0;memset(ne,0,sizeof(ne));for (int i = 2, j = 0; i <= m; i ++ ){while (j && p[i] != p[j + 1]) j = ne[j];if (p[i] == p[j + 1]) j ++ ;ne[i] = j;
}// 匹配
for (int i = 0, j = -1; i <= n; i ++ ){while (j && s[i] != p[j + 1]) j = ne[j];if (s[i] == p[j + 1]) j ++ ;if(j==m){cout<<"YES\n";return 1;}if (j == m){j = ne[j];// 匹配成功后的逻辑}
}
cout<<"NO\n";
return 1;}
int main(){int t=1;while (t){tishi();if(!solve()) {break;}}// getchar();return 0;
}

基于哈夫曼树的数据压缩算法

这个还是比较有趣，可以自己试试

/*
*/
#include<bits/stdc++.h>
using namespace std;
#define ll long longtypedef  pair<int,int> pi ;
#define if1(x) for(int i =1 ;i<=x;i++)
#define if0(x) for(int i = 0;i<x;i++)
#define jf0(x) for(int j = 0;j<x;j++)
#define jf1(x) for(int j = 1;j<=x;j++)
const int mod = 1e9+7;
const int inf = 0x3f3f3f3f;
string s;
string ans[1000];
unordered_map<char,int> mmp;
vector<tuple<int,int,int,int>>tre;//重，fa，l,r
bool cmp(pair<char,int> a,pair<char,int> b)
{return a.first>b.first;
}
void dfs(int x,string temp){if(temp!="\0")ans[x] =temp ;int w1,w2,f1,f2,l1,l2,r1,r2,id1,id2;auto te1 = tre[x];tie(w1,f1,l1,r1) = te1;if(l1!=-1)dfs(l1,temp+'0');if(r1!=-1)dfs(r1,temp+'1');}
void solve(){int m,n,idx = 0;tre.clear();memset(ans,'\0',sizeof(ans));priority_queue<pi,vector<pi>,greater<pi>>mq;mmp.clear();for(auto j:s)mmp[j]++;vector<pair<int,int> > ss;for(auto j:mmp){ss.push_back({j.first,j.second});}sort(ss.begin(),ss.end());for(auto j:ss){char ch = j.first;printf("%c:%d ",ch,j.second);mq.push({j.second,idx++});//建树tre.push_back({j.second,-1,-1,-1});}cout<<endl;//建立合成节点的树while(mq.size()>1){auto t1 = mq.top();mq.pop();auto t2 = mq.top();mq.pop();int w1,w2,f1,f2,l1,l2,r1,r2,id1,id2;tie(w1,id1) = t1;tie(w2,id2)  =t2;mq.push({w1+w2,idx++});tre.push_back({w1+w2,-1,id1,id2});//以后要牢记tuple一般用于无修改的操作//不是说内容一旦过长就用tuple；auto te1 = tre[id1],te2 = tre[id2];tie(w1,f1,l1,r1) = te1;tie(w2,f2,l2,r2) = te2;tre[id1] = {w1,idx-1,l1,r1};tre[id2] = {w2,idx-1,l2,r2};}//输出树jf0(idx){int w1,w2,f1,f2,l1,l2,r1,r2,id1,id2;auto te1 = tre[j];tie(w1,f1,l1,r1) = te1;cout<<j+1<<" "<<w1<<" "<<f1+1<<" "<<l1+1<<" "<<r1+1<<endl;}//dfs编码树dfs(idx-1,"\0");if0(ss.size()){char ch = ss[i].first;cout<<ch<<":"<<ans[i]<<" ";}cout<<endl;string res;if0(ss.size()){jf0(ss[i].second){res+=ans[i];}}cout<<res<<endl;//解码，感觉会比较复杂//奥！，dfs编码，那么我也应该是dfs解码，聪明like meint now = idx-1;for(auto j:res){int w1,w2,f1,f2,l1,l2,r1,r2,id1,id2;auto te1 = tre[now];tie(w1,f1,l1,r1) = te1;if(l1==-1){//走到尽头辣,我们就可以输出当前节点的val，并且回溯到根节点char ch = ss[now].first;cout<<ch;now = idx-1;auto te1 = tre[now];tie(w1,f1,l1,r1) = te1;}if(j=='0'){//向左边走、now = l1;}else now = r1;}char ch = ss[now].first;cout<<ch;now = idx-1;cout<<endl;
}
int main(){//ios::sync_with_stdio(false);//cin.tie(nullptr);//cout.tie(nullptr); while (1){cin>>s;if(s=="0")break;solve();}// getchar();return 0;
}```

基于二叉树的表达式求值算法

最傻逼的作业

#include<bits/stdc++.h>
using namespace std;
#define MAXSIZE 100
#define N 10
string S;
//运算符栈 
unordered_map<char,int>mmp;
void init0(){mmp['('] = mmp[')']=3;mmp['*'] = mmp['/'] = 2;mmp['+'] = mmp['-'] = 1;
}
struct node{bool isnum;int val;char op;node* L;node* R;
};
stack<char> sta_op;
stack<node*> sta_num;
int verify(char ch)
{//cout<<ch<<endl;if(ch=='+')return 0;else if(ch=='-')return 1;else if(ch=='*')return 2;else if(ch=='/')return 3;else if(ch=='(')return 4;else if(ch==')')return 5;else{return 100;}}
void push_num(int& idx){int j = idx;int temp = 0;while(S[j]>='0'&&S[j]<='9'){temp*=10;temp+=S[j]-'0';j++;}node* te = new(node);te->isnum=1;te->val=temp;sta_num.push(te);idx = j-1;
}
int judge(int a,char e,int b)
{//cout<<e<<endl;if(e=='+')return a+b;else if(e=='-')return a-b;else if(e=='*')return a*b;else if(e=='/')return a/b;else{cout<<"error!"<<endl;return -1;}}
void func1(int& idx){char ch = S[idx];if(ch=='('||ch=='+'||ch=='-')sta_op.push(ch);//of course +-不需要考虑运算顺序else if(ch == '*'||ch=='/'){if(S[idx+1]>='0'&&S[idx+1]<='9'){//*/在后面跟上的是数字的情况下，一定是可以直接进行运算的//那么不妨在这种情况下面直接开算int j = idx+1;int temp = 0;while(S[j]>='0'&&S[j]<='9'){temp*=10;temp+=S[j]-'0';j++;}node* te = new(node);te->isnum=1;te->val=temp;sta_num.push(te);idx = j-1;//node* re = sta_num.top();sta_num.pop();node* la = sta_num.top();sta_num.pop();node* fa =new(node);fa->isnum=0;fa->op = ch;fa->L=la;fa->R = re;sta_num.push(fa);}else{sta_op.push(ch);//只能等后面在来运算辣//就是等下一个左括号运算完成并出栈的时候来运算此符号}}else if(ch==')'){while(sta_op.top()!='('){node* re = sta_num.top();sta_num.pop();node* la = sta_num.top();sta_num.pop();node* fa =new(node);fa->isnum=0;fa->op = sta_op.top();fa->L=la;fa->R = re;sta_num.push(fa);sta_op.pop();}sta_op.pop();if(sta_op.top()=='*'||sta_op.top()=='/'){////这个时候就要运算109行处的*/法辣node* re = sta_num.top();sta_num.pop();node* la = sta_num.top();sta_num.pop();node* fa =new(node);fa->isnum=0;fa->op = sta_op.top();fa->L=la;fa->R = re;sta_num.push(fa);sta_op.pop();}}}
int dfs(node* root){if(root->isnum) return root->val;int l = dfs(root->L),r=dfs(root->R);return judge(l,root->op,r);
}
int func(){cin>>S;if(S=="=")return 0;for(int i=0;S[i]!='\0';i++){if(S[i]>='0'&&S[i]<='9')push_num(i);elsefunc1(i);}//*/法已经算完辣，+-法没有顺序可言，但是为了减少代码量就不优化辣。while(!sta_op.empty()){node* re = sta_num.top();sta_num.pop();node* la = sta_num.top();sta_num.pop();node* fa =new(node);fa->isnum=0;fa->op = sta_op.top();fa->L=la;fa->R = re;sta_num.push(fa);sta_op.pop();} node* root = sta_num.top();cout<<dfs(root)<<endl;sta_num.pop();return 1;
}
int main()
{int ti=1;while(ti){cout<<"\n请输入中缀表达式的算数表达式\n仅输入一个 = 时结束程序\n";if(!func())break;}return 0;
}

基于 Dijsktra 算法的最短路

/*
*/
#include<bits/stdc++.h>
using namespace std;
#define ll long longtypedef  pair<int,int> pi ;
#define if1(x) for(int i =1 ;i<=x;i++)
#define if0(x) for(int i = 0;i<x;i++)
#define jf0(x) for(int j = 0;j<x;j++)
#define jf1(x) for(int j = 1;j<=x;j++)
const int mod = 1e9+7;
const int inf = 0x3f3f3f3f;
int e[200],h[200],ne[200],w[200],idx,idx1;
unordered_map<string ,int> mmp;
string xiufu[200];
int dist[200];
int pre[200];
int m,n,c;
void add(int a,int b,int c){e[idx] = b;w[idx] = c;ne[idx] = h[a];h[a] = idx++;}void dijsktra(int x){memset(dist,inf,sizeof(dist));priority_queue<pi> mq;mq.push(make_pair(0,x));dist[x]=0;while(!mq.empty()){int j = mq.top().second;int distance = mq.top().first;mq.pop();for(int p = h[j];~p;p = ne[p]){int q = e[p];//q是终点if(distance+w[p]<dist[q]){dist[q] = distance+w[p];mq.push(make_pair(dist[q],q));pre[q] = j;}}}
}
void solve(){string s;string a,b;idx1 = 1;idx = 0;mmp.clear();if0(n)cin>>s;memset(h,-1,sizeof(h));if0(m){cin>>a>>b>>c;if(mmp[a]==0){xiufu[idx1] = a;mmp[a] = idx1++;}if(mmp[b]==0){xiufu[idx1] = b;mmp[b] = idx1++;}add(mmp[a],mmp[b],c);}cin>>a>>b;memset(pre,-1,sizeof(pre));dijsktra(mmp[a]);stack<string>wedg;int en = mmp[b];while(en!=-1){wedg.push(xiufu[en]);en = pre[en];}cout<<dist[mmp[b]]<<endl;while(!wedg.empty()){cout<<wedg.top()<<" ";wedg.pop();}cout<<endl;}
int main(){//ios::sync_with_stdio(false);//cin.tie(nullptr);//cout.tie(nullptr); while(1){cin>>n>>m;if(m==0&&n==0)break;solve();}return 0;
}

基于广度优先搜索的六度空间

/*
*/
#include<bits/stdc++.h>
using namespace std;
#define ll long longtypedef  pair<int,int> pi ;
#define if1(x) for(int i =1 ;i<=x;i++)
#define if0(x) for(int i = 0;i<x;i++)
#define jf0(x) for(int j = 0;j<x;j++)
#define jf1(x) for(int j = 1;j<=x;j++)
const int mod = 1e9+7;
const int inf = 0x3f3f3f3f;
vector<int> wedg[10005];
bool marked[10005];
int frend;
int m,n;
queue<pi>mq;
void bfs(){while(!mq.empty()){auto j = mq.front();mq.pop();if(marked[j.first]||j.second>6)continue;marked[j.first]=1;frend++;for(auto t:wedg[j.first]){if(!marked[t])mq.push(make_pair(t,j.second+1));}}}
void solve(){if0(m){int a,b;cin>>a>>b;wedg[a].push_back(b);wedg[b].push_back(a);}if1(n){double ans;memset(marked,0,sizeof(marked));frend = 0;mq.push({i,0});bfs();ans = 1.*(frend)/n;printf("%d:%.2f%\n",i,ans*100);}if1(n)wedg[i].clear();
}
int main(){while(1){cin>>n>>m;if(n==0&&m==0)return 0;solve();}// getchar();return 0;
}

排序算法的实现与分析

归并法

/*
*/
#include<bits/stdc++.h>
using namespace std;
#define ll long longtypedef  pair<int,int> pi ;
#define if1(x) for(int i =1 ;i<=x;i++)
#define if0(x) for(int i = 0;i<x;i++)
#define jf0(x) for(int j = 0;j<x;j++)
#define jf1(x) for(int j = 1;j<=x;j++)
const int mod = 1e9+7;
const int inf = 0x3f3f3f3f;
struct node{string name;double grade;
};
bool cmp(node a,node b){return a.grade>b.grade;
}
void hebin(vector<node>& da,int l,int r,int mid){node* temp = new node[r-l+2];int i = l,j = mid+1,k=0;while(i<=mid&&j<=r){if(cmp(da[i],da[j])){temp[k++] = da[i++];}else{temp[k++] = da[j++];}}while(i<=mid)temp[k++] = da[i++];while(j<=r) temp[k++] = da[j++];k=0;for(int i = l; i<=r;)da[i++] = temp[k++];delete []temp;
}
void guibin(int l,int r,vector<node>& da){if(l<r){int mid = l+r>>1;guibin(l,mid,da);guibin(mid+1,r,da);hebin(da,l,r,mid);}
}
int main(){string s;double grade;vector<node> date;while(1){cin>>s>>grade;if(s=="0"&&grade==0)break;node te ;te.grade = grade;te.name = s;date.push_back(te);}guibin(0,date.size()-1,date);if0(date.size()){cout<<date[i].name<<" ";printf("%.2f\n",date[i].grade);}return 0;
}