痛苦的数据结构OJ
感覺這篇博客寫完，會方便更多同學。。。。
有些題目真的，很難啊，最后的幾道題目，我也是谷歌的！做到吐血。
A - B Problem II
這是個大數相加的問題，即高精度加法
貼一發高精度模板總結
陶陶摘蘋果
這個就注意一下，多組數據測試就行了，沒打過ACM的可能會出錯while(cin>>a[0])
# include <iostream>using namespace std;int main(){int a[10],h;while(cin>>a[0]){int sum=0;for(int i=1;i<10;i++)cin>>a[i];cin>>h;for(int i=0;i<10;i++){if(h+30>=a[i])sum++;}cout<<sum<<endl;}return 0;}校門外的樹
這道題是參考洛洛師傅的，其中把要移走的樹值賦為-1，然后計算值為-1的數目
個人感覺這個思想很好。。。。
自動加密
這道題就是注意大小寫都要寫，然后字符對照ASCII,轉換一下就行了
#include <iostream>using namespace std;int main(){int i;char s[100];cin>>s;for(i=0;s[i];i++){if(s[i]>='a'&&s[i]<='z'){s[i]+=5;if(s[i]>'z'){s[i]-=26;}}else if(s[i]>='A'&&s[i]<='Z'){s[i]+=5;if(s[i]>'Z'){s[i]-=26;}}}cout<<s<<endl;return 0;}計算秒數
這個和上一道題思路差不多，字符轉數字
#include <iostream>using namespace std;int sum(char x,char y,int z){int result;if(x=='0'){result=(y-48)*z;}else{result=((x-48)*10+y-48)*z;}return result;}int main(){int i,n,h,m,s;char t[10];while(cin>>n){for(i=0;i<n;i++){cin>>t;h=sum(t[0],t[1],3600);m=sum(t[3],t[4],60);s=sum(t[6],t[7],1);cout<<h+m+s<<endl;}}return 0;}算法2-1：集合union
這道題給出了合并函數，補充表頭，和定義類就行了，注意輸出n+2行
#include<iostream>using namespace std;typedef struct List{int L[205];int length;}List;List La,Lb;bool LocateElem(List &La,int e){for(int i=0;i<La.length;i++){if(La.L[i]==e)return true;}return false;}void show(List &L){cout<<L.L[0];for(int i=1;i<L.length;i++)cout<<" "<<L.L[i];cout<<endl;}void Union(List &La,List &Lb){int e;for(int i=0;i<Lb.length;i++){e=Lb.L[i];if(!LocateElem(La,e)){La.L[La.length]=e;La.length++; }show(La);}}int main(){int n1,n2,i;while(cin>>n1){ for(i=0;i<n1;i++)cin>>La.L[i];La.length=n1;cin>>n2;for(int i=0;i<n2;i++) cin>>Lb.L[i];Lb.length=n2;show(La);show(Lb);Union(La,Lb);cout<<endl;} return 0;}算法2-2：有序線性表的有序合并
上道題會了，這道題就會了，就是變一下主函數,并且注意空格格式，ACM要求很嚴格
#include<iostream>using namespace std;typedef struct List{int date[200];int length;}List;List La,Lb;void InitList(List &L) { L.length=0; }int ListLength(List L){ return L.length; }int GetElem(List L,int p,int &e){ if(p<1||p>L.length) return 0; e=L.date[p]; return 0; }int ListInsert(List &L,int p,int e){ int i; if(p<1||p>L.length||L.length==200-1) return 0; for(i=L.length;i>=p;--i) L.date[i+1]=L.date[i]; L.date[p]=e; return 0; }void MergeList(List La,List Lb,List &Lc){ int La_len,Lb_len; int ai,bj; int i=1,j=1,k=0; InitList(Lc); La_len=ListLength(La); Lb_len=ListLength(Lb); Lc.length=La.length+Lb.length; while((i<=La_len)&&(j<=Lb_len)){ GetElem(La,i,ai); GetElem(Lb,j,bj); if(ai<=bj){ ListInsert(Lc,++k,ai); ++i; }else{ ListInsert(Lc,++k,bj); ++j; } } while (i<=La_len){ GetElem(La,i++,ai); ListInsert(Lc,++k,ai); } while(j<=Lb_len){ GetElem(Lb,j++,bj); ListInsert(Lc,++k,bj); } }int main(){List La,Lb,Lc; InitList(La); InitList(Lb); while(cin>>La.length){ for(int i=1;i<=La.length;i++){ cin>>La.date[i]; } cin>>Lb.length; for(int i=1;i<=Lb.length;i++){ cin>>Lb.date[i]; } MergeList(La,Lb,Lc); if(Lc.length!=0){ cout<<Lc.date[1]; for(int i=2;i<=Lc.length;i++) cout<<" "<<Lc.date[i]; } cout<<endl; } return 0;}算法2-3~2-6：Big Bang
這是谷歌加修改的。
#include<stdio.h>#include<stdlib.h>#include<string.h>#define LIST_INIT_SIZE 100#define LISTINCREMENT 10typedef struct{char name[100];}ElemType;typedef struct{ElemType * elem;int length;int listsize;}List;int InitList(List &L){L.elem = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!L.elem)return 0;L.length = 0;L.listsize = LIST_INIT_SIZE;return 1;}int ListInsert(List &L,int i,ElemType e){ElemType *p;if(i<1||i>L.length+1)return 0;if(L.length>=L.listsize){ElemType *newbase;newbase = (ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));if(!newbase){return 0;}L.elem = newbase;L.listsize+=LISTINCREMENT;}ElemType *q = &(L.elem[i-1]);for(p = &(L.elem[L.length-1]);p>=q;--p)*(p+1)=*p;*q=e;++L.length;return 1;}int ListDlete (List &L,int i,ElemType e){ElemType *p,*q;if(i<1||i>L.length)return 0;p=&(L.elem[i-1]);e=*p;q=L.elem+L.length-1;for(++p;p<=q;++p){*(p-1)=*p;}--L.length;return 1;}int LocateElem(List L,ElemType e,int(*compare)(ElemType,ElemType)){int i;ElemType *p;i=1;p=L.elem;while(i<=L.length&&!(*compare)(*p++,e))++i;if(i<=L.length)return i;elsereturn 0;}void listshow(List L){int i;for(i=0;i<L.length;i++){if(i)putchar(' ');printf("%s",L.elem[i].name);}putchar('\n');}int cmp(ElemType e1, ElemType e2){return (int)!strcmp(e1.name, e2.name);}int main (void){char mark[10];List nameList;InitList(nameList);int number;ElemType e;while(~scanf("%s",mark)){if(strcmp(mark,"insert")==0){scanf("%d %s",&number,e.name);ListInsert(nameList,number,e);}else if(strcmp(mark,"show")==0)listshow(nameList);else if(strcmp(mark,"delete")==0){scanf("%s",e.name);number=LocateElem(nameList,e,cmp);ListDlete(nameList,number,e);}else if(strcmp(mark,"search")==0){scanf("%s",e.name);printf("%d\n",LocateElem(nameList,e,cmp));}}return 0;}算法2-8~2-11：鏈表的基本操作
這個也是谷歌加修改的。
#include<string.h> #include<malloc.h>#include<stdio.h> #include<stdlib.h>#include<math.h>#define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1typedef int Status; typedef int Boolean;typedef int ElemType;struct LNode { ElemType data; struct LNode *next; }; typedef struct LNode *LinkList; Status GetElem(LinkList L,int i,ElemType *e){ int j=1;LinkList p=L->next;while(p&&j<i) { p=p->next; j++; } if(!p||j>i)return ERROR; *e=p->data; return OK; } Status ListInsert(LinkList L,int i,ElemType e){int j=0; LinkList p=L,s; while(p&&j<i-1){ p=p->next; j++; } if(!p||j>i-1) return ERROR; s=(LinkList)malloc(sizeof(struct LNode)); s->data=e;s->next=p->next; p->next=s; return OK; }Status ListDelete(LinkList L,int i,ElemType *e) {int j=0; LinkList p=L,q; while(p->next&&j<i-1) { p=p->next; j++; } if(!p->next||j>i-1)return ERROR; q=p->next; p->next=q->next; *e=q->data; free(q); return OK; } void CreateList(LinkList *L,int n) {int i; LinkList p; *L=(LinkList)malloc(sizeof(struct LNode)); (*L)->next=NULL; for(i=n; i>0; --i) { p=(LinkList)malloc(sizeof(struct LNode)); scanf("%d",&p->data); p->next=(*L)->next;(*L)->next=p; } } int ShowList(LinkList L) { int numOfList = 0; LinkList p = L->next; while(p) { if(numOfList) { putchar(' '); } numOfList++; printf("%d",p->data); p = p->next; } if(numOfList == 0) { return 0; } else { putchar('\n'); return numOfList;} } int main() { int n; int m; char strInst[30]; int a; LinkList L;int e; scanf("%d", &n); CreateList(&L, n); scanf("%d", &m); while(m--){ scanf("%s", strInst); if(strcmp(strInst, "get") == 0) { scanf("%d", &a); if(GetElem(L, a, &e) == OK){ printf("%d\n", e); } else { puts("get fail");}} else if(strcmp(strInst, "insert") == 0) { scanf("%d%d", &a, &e); if(ListInsert(L, a, e) == OK) { puts("insert OK");}else {puts("insert fail"); } }else if(strcmp(strInst, "delete") == 0){ scanf("%d",&a);if(ListDelete(L, a, &e) == OK) { puts("delete OK"); } else { puts("delete fail");} } else if(strcmp(strInst, "show") == 0) { if(ShowList(L) == 0){ puts("Link list is empty");} } } return 0; }算法2-13~2-16：靜態鏈表
google+alter
Sample Input
show
insert 1 ZHAO
show
insert 2 QIAN
show
insert 3 SUN
show
insert 4 LI
insert 5 ZHOU
insert 6 WU
insert 7 ZHENG
insert 8 WANG
show
insert 1 ZHANG
show
search LI
算法2-18~2-19：雙向循環鏈表
google+alter
#include<stdio.h>#include<stdlib.h>typedef struct DLNode{int data;struct DLNode *next;struct DLNode *prior;} DNLode;void createDLNode(DLNode *&L){L = (DLNode *)malloc(sizeof(DLNode));L->prior = L;L->next = L;}void printDLNode(DLNode *L){DLNode *q;q=L->next;int i=0;while(q!=L){if(i++)//good idea!{putchar(' ');}printf("%d",q->data);q=q->next;}printf("\n");}void insertDLNode(DLNode *&L,int i,int e){DLNode *q,*qlen;q=L;qlen=L->next;int num=0;while(qlen!=L){num++;qlen=qlen->next;}int j=1;while(j<i){j++;q=q->next;}if(i>num+1||i<1)return ;DLNode *s;s=(DLNode *)malloc (sizeof(DLNode));s->data = e;s->next = q->next;s->prior = q;q->next = s;q->next->prior = s;return ;}void deleteDLNode (DLNode *&L,int i){DLNode *q,*qlen;qlen=L->next;q=L;int num=0;while(qlen!=L){qlen=qlen->next;num++;}if(i<1||i>num){return ;}int j=0;while(j<i-1){q=q->next;j++;}DLNode *qfree;qfree= q->next;q->next=qfree->next;qfree->next->prior=q;free(qfree);}int main (void){int n;DNLode *L;createDLNode(L);while(~scanf("%d",&n)){switch(n){case 0:{printDLNode(L);break;}case 1:{int i,e;scanf("%d%d",&i,&e);insertDLNode(L,i,e);// printDLNode(L);break;}case 2:{int i;scanf("%d",&i);deleteDLNode(L,i);// printDLNode(L);break;}default:break;}}return 0;}算法2-23：一元多項式加法
來自洛洛師傅，沒有用他給出的函數233333333333333333
#include<iostream>#include<stdlib.h>#include<stdio.h>#include<cstring>#include<string.h>using namespace std;void hs(char*str,int *ss,int *sss){char *p=NULL;int zan;zan=atoi(strtok(str," "));for(int q=0;(p =strtok(NULL," "));q++){if(q%2==0){if(atoi(p)>=0)ss[atoi(p)]=zan;elsesss[-1*atoi(p)]=zan;}else{zan=atoi(p);}}return;}void hss(char*str,int *ss,int *sss){ char *p1=NULL;int zan1;zan1=atoi(strtok(str," "));//cout<<zan1<<endl;for(int q=0;(p1 =strtok(NULL," "));q++){if(q%2==0){if(atoi(p1)>=0)ss[atoi(p1)]+=zan1;elsesss[-1*atoi(p1)]+=zan1;//if(ss[atoi(p1)]>0)// ss[atoi(p1)]+=zan1;//else// ss[atoi(p1)]=zan1;//cout<<ss[atoi(p1)]<<endl;}else{zan1=atoi(p1);//cout<<zan1<<endl;}}return;}int main(){char strA[500],strB[500];while(gets(strA) && strlen(strA)){int ss[300]={0},sss[300]={0};hs(strA,ss,sss);if(gets(strB)&& strlen(strB))hss(strB,ss,sss);int gg;for(int j=0;j<150;j++){if(ss[j]!=0)gg=j;}//gg--;for(;gg>=0;gg--)if(ss[gg]!=0)cout<<ss[gg]<<' '<<gg<<' ';for(int y=0;y<300;y++)if(sss[y]!=0)cout<<sss[y]<<' '<<-1*y<<' ';cout<<endl;}return 0;}算法3-1：八進制數
這道題目雖然放在了最后，但是并不難
#include<iostream> #include<stack> using namespace std; #define MAXSIZE 1000 char str[MAXSIZE]; void Conversion(int num,int b){ stack<int>S;do{S.push(num%b); num/= b; }while(num);while(!S.empty()){ cout<<S.top(); S.pop(); }cout<<endl; }int main() {int a,b; while(cin>>a){ b = 8; Conversion(a,b); }return 0; }轉載于:https://www.cnblogs.com/bay1/p/10982527.html
總結
