网站内容管理系统下载,有专门做房孑特卖的网站吗,镇江微淘软件开发,服装网站设计欣赏CQUPT 的某数据结构homework 基于线性表的图书信息管理基于栈的算术表达式求值基于字符串模式匹配算法的病毒感染检测问题 基于哈夫曼树的数据压缩算法基于二叉树的表达式求值算法基于 Dijsktra 算法的最短路基于广度优先搜索的六度空间排序算法的实现与分析 基于线性表的图书信… CQUPT 的某数据结构homework 基于线性表的图书信息管理基于栈的算术表达式求值基于字符串模式匹配算法的病毒感染检测问题 基于哈夫曼树的数据压缩算法基于二叉树的表达式求值算法基于 Dijsktra 算法的最短路基于广度优先搜索的六度空间排序算法的实现与分析 基于线性表的图书信息管理
首先因为我们要输入输出汉语所以需要更改编码成为utf-8 我使用的是devcpp 所以其他版本编译器更改编码的就请自己去查询更改方式。 工具 编译选项 编译时加入以下命令打勾下面粘上此代码 -stdc11 -finput-charsetutf-8
/*
*/
#includebits/stdc.h
using namespace std;
#define ll long long
typedef pairint,int pi ;
#define if1(x) for(int i 1 ;ix;i)
#define if0(x) for(int i 0;ix;i)
#define jf0(x) for(int j 0;jx;j)
#define jf1(x) for(int j 1;jx;j)
struct node_book
{string name_book;string id_book;float price_book;//int myid;};
unordered_mapstring ,intmmp;//去重用
listnode_book books;
vectornode_book high_books;
double evrage;
int books_num,idx;
void output(){for(auto j:books){coutj.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){cinidnameprice;if(id0name0price0)break;add(id,price,name);mmp[id];// evrage price;}
}
void func1(){init();coutbooks_numendl;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);coutbooks_numendl;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_bookhigh_price){high_books.clear();high_books.push_back(j);high_price j.price_book;}else if(high_pricej.price_book){high_books.push_back(j);}}couthigh_books.size()endl;for(auto j: high_books){coutj.id_book j.name_book ;printf(%.02f\n,j.price_book);}
}
void func4(){init();float price;string name,id;int place,idx 1;cinplace;cinidnameprice;node_book new_book;new_book.id_book id;new_book.name_book name;new_book.price_book price;listnode_book::iterator pos ;pos books.begin();for(auto j:books){idx;pos;if(idxplace){books.insert(pos,new_book);books_num;coutbooks_numendl;output();return;}}cout抱歉入库位置非法!\n;}
void func5(){init();float price;string name,id;int place,idx 1;cinplace;listnode_book::iterator pos ;pos books.begin();for(auto j:books){idx;pos;if(idxplace){books.erase(pos);books_num--;}}coutbooks_numendl;output();
}
void func6(){init();int place;listnode_book::iterator pos ;vectorlistnode_book::iterator dela;pos books.begin();for(auto j:books){//coutmmp[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);}coutbooks_numendl;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();cinop;if(op 1)func1();else if(op2)func2();else if(op3)func3();else if(op4)func4();else if(op5)func5();else if(op6)func6();books.clear();}return 0;
}基于栈的算术表达式求值
普通应用即可
#includebits/stdc.h
using namespace std;
#define MAXSIZE 100
#define N 10
string S;
//运算符栈
unordered_mapchar,intmmp;
void init0(){mmp[(] mmp[)]3;mmp[*] mmp[/] 2;mmp[] mmp[-] 1;
}stackchar sta_op;
stackint sta_num;
int verify(char ch)
{//coutchendl;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]0S[j]9){temp*10;tempS[j]-0;j;}sta_num.push(temp);idx j-1;
}
int judge(int a,char e,int b)
{//couteendl;if(e)return ab;else if(e-)return a-b;else if(e*)return a*b;else if(e/)return a/b;else{couterror!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[idx1]0S[idx1]9){//*/在后面跟上的是数字的情况下一定是可以直接进行运算的//那么不妨在这种情况下面直接开算int j idx1;int temp 0;while(S[j]0S[j]9){temp*10;tempS[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(){cinS;if(S)return 0;for(int i0;S[i]!\0;i){if(S[i]0S[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);} coutsta_num.top()endl;sta_num.pop();return 1;
}
int main()
{int ti1;while(ti){cout\n请输入中缀表达式的算数表达式\n仅输入一个 时结束程序\n;if(!func())break;}return 0;
}基于字符串模式匹配算法的病毒感染检测问题
kmp即可
#includebits/stdc.h
using namespace std;
#define ll long longtypedef pairint,int pi ;
#define if1(x) for(int i 1 ;ix;i)
#define if0(x) for(int i 0;ix;i)
#define jf0(x) for(int j 0;jx;j)
#define jf1(x) for(int j 1;jx;j)
const int mod 1e97;
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;cinxy;n y.size();m x.size();if0(n){s[i1] y[i];}if0(m) p[i1] x[i];if(x0y0)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(jm){coutYES\n;return 1;}if (j m){j ne[j];// 匹配成功后的逻辑}
}
coutNO\n;
return 1;}
int main(){int t1;while (t){tishi();if(!solve()) {break;}}// getchar();return 0;
}基于哈夫曼树的数据压缩算法
这个还是比较有趣可以自己试试
/*
*/
#includebits/stdc.h
using namespace std;
#define ll long longtypedef pairint,int pi ;
#define if1(x) for(int i 1 ;ix;i)
#define if0(x) for(int i 0;ix;i)
#define jf0(x) for(int j 0;jx;j)
#define jf1(x) for(int j 1;jx;j)
const int mod 1e97;
const int inf 0x3f3f3f3f;
string s;
string ans[1000];
unordered_mapchar,int mmp;
vectortupleint,int,int,inttre;//重fal,r
bool cmp(pairchar,int a,pairchar,int b)
{return a.firstb.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,temp0);if(r1!-1)dfs(r1,temp1);}
void solve(){int m,n,idx 0;tre.clear();memset(ans,\0,sizeof(ans));priority_queuepi,vectorpi,greaterpimq;mmp.clear();for(auto j:s)mmp[j];vectorpairint,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});}coutendl;//建立合成节点的树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({w1w2,idx});tre.push_back({w1w2,-1,id1,id2});//以后要牢记tuple一般用于无修改的操作//不是说内容一旦过长就用tupleauto 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;coutj1 w1 f11 l11 r11endl;}//dfs编码树dfs(idx-1,\0);if0(ss.size()){char ch ss[i].first;coutch:ans[i] ;}coutendl;string res;if0(ss.size()){jf0(ss[i].second){resans[i];}}coutresendl;//解码感觉会比较复杂//奥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;coutch;now idx-1;auto te1 tre[now];tie(w1,f1,l1,r1) te1;}if(j0){//向左边走、now l1;}else now r1;}char ch ss[now].first;coutch;now idx-1;coutendl;
}
int main(){//ios::sync_with_stdio(false);//cin.tie(nullptr);//cout.tie(nullptr); while (1){cins;if(s0)break;solve();}// getchar();return 0;
}基于二叉树的表达式求值算法
最傻逼的作业
#includebits/stdc.h
using namespace std;
#define MAXSIZE 100
#define N 10
string S;
//运算符栈
unordered_mapchar,intmmp;
void init0(){mmp[(] mmp[)]3;mmp[*] mmp[/] 2;mmp[] mmp[-] 1;
}
struct node{bool isnum;int val;char op;node* L;node* R;
};
stackchar sta_op;
stacknode* sta_num;
int verify(char ch)
{//coutchendl;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]0S[j]9){temp*10;tempS[j]-0;j;}node* te new(node);te-isnum1;te-valtemp;sta_num.push(te);idx j-1;
}
int judge(int a,char e,int b)
{//couteendl;if(e)return ab;else if(e-)return a-b;else if(e*)return a*b;else if(e/)return a/b;else{couterror!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[idx1]0S[idx1]9){//*/在后面跟上的是数字的情况下一定是可以直接进行运算的//那么不妨在这种情况下面直接开算int j idx1;int temp 0;while(S[j]0S[j]9){temp*10;tempS[j]-0;j;}node* te new(node);te-isnum1;te-valtemp;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-isnum0;fa-op ch;fa-Lla;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-isnum0;fa-op sta_op.top();fa-Lla;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-isnum0;fa-op sta_op.top();fa-Lla;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),rdfs(root-R);return judge(l,root-op,r);
}
int func(){cinS;if(S)return 0;for(int i0;S[i]!\0;i){if(S[i]0S[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-isnum0;fa-op sta_op.top();fa-Lla;fa-R re;sta_num.push(fa);sta_op.pop();} node* root sta_num.top();coutdfs(root)endl;sta_num.pop();return 1;
}
int main()
{int ti1;while(ti){cout\n请输入中缀表达式的算数表达式\n仅输入一个 时结束程序\n;if(!func())break;}return 0;
}基于 Dijsktra 算法的最短路
/*
*/
#includebits/stdc.h
using namespace std;
#define ll long longtypedef pairint,int pi ;
#define if1(x) for(int i 1 ;ix;i)
#define if0(x) for(int i 0;ix;i)
#define jf0(x) for(int j 0;jx;j)
#define jf1(x) for(int j 1;jx;j)
const int mod 1e97;
const int inf 0x3f3f3f3f;
int e[200],h[200],ne[200],w[200],idx,idx1;
unordered_mapstring ,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_queuepi 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(distancew[p]dist[q]){dist[q] distancew[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)cins;memset(h,-1,sizeof(h));if0(m){cinabc;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);}cinab;memset(pre,-1,sizeof(pre));dijsktra(mmp[a]);stackstringwedg;int en mmp[b];while(en!-1){wedg.push(xiufu[en]);en pre[en];}coutdist[mmp[b]]endl;while(!wedg.empty()){coutwedg.top() ;wedg.pop();}coutendl;}
int main(){//ios::sync_with_stdio(false);//cin.tie(nullptr);//cout.tie(nullptr); while(1){cinnm;if(m0n0)break;solve();}return 0;
}基于广度优先搜索的六度空间
/*
*/
#includebits/stdc.h
using namespace std;
#define ll long longtypedef pairint,int pi ;
#define if1(x) for(int i 1 ;ix;i)
#define if0(x) for(int i 0;ix;i)
#define jf0(x) for(int j 0;jx;j)
#define jf1(x) for(int j 1;jx;j)
const int mod 1e97;
const int inf 0x3f3f3f3f;
vectorint wedg[10005];
bool marked[10005];
int frend;
int m,n;
queuepimq;
void bfs(){while(!mq.empty()){auto j mq.front();mq.pop();if(marked[j.first]||j.second6)continue;marked[j.first]1;frend;for(auto t:wedg[j.first]){if(!marked[t])mq.push(make_pair(t,j.second1));}}}
void solve(){if0(m){int a,b;cinab;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){cinnm;if(n0m0)return 0;solve();}// getchar();return 0;
}排序算法的实现与分析
归并法
/*
*/
#includebits/stdc.h
using namespace std;
#define ll long longtypedef pairint,int pi ;
#define if1(x) for(int i 1 ;ix;i)
#define if0(x) for(int i 0;ix;i)
#define jf0(x) for(int j 0;jx;j)
#define jf1(x) for(int j 1;jx;j)
const int mod 1e97;
const int inf 0x3f3f3f3f;
struct node{string name;double grade;
};
bool cmp(node a,node b){return a.gradeb.grade;
}
void hebin(vectornode da,int l,int r,int mid){node* temp new node[r-l2];int i l,j mid1,k0;while(imidjr){if(cmp(da[i],da[j])){temp[k] da[i];}else{temp[k] da[j];}}while(imid)temp[k] da[i];while(jr) temp[k] da[j];k0;for(int i l; ir;)da[i] temp[k];delete []temp;
}
void guibin(int l,int r,vectornode da){if(lr){int mid lr1;guibin(l,mid,da);guibin(mid1,r,da);hebin(da,l,r,mid);}
}
int main(){string s;double grade;vectornode date;while(1){cinsgrade;if(s0grade0)break;node te ;te.grade grade;te.name s;date.push_back(te);}guibin(0,date.size()-1,date);if0(date.size()){coutdate[i].name ;printf(%.2f\n,date[i].grade);}return 0;
}
