---
tags: 大二筆記
---

# 資料結構 下

## priority_queue
### 產品價格排序

#include <iostream>
#include <queue>
#include <deque>

using namespace std;

typedef struct pd{
    string name;
    priority_queue<int, deque<int>, greater<int> > pq;
}pd;


int main() {

    cin.tie(0);
    ios_base::sync_with_stdio(false);

    int n,money,i,sum=0;
    string str;
    pd pd[100];

    cin >> n;
    while(n--){
        cin >> str >> money;

        //scan
        int flag=1;//if(flag)push
        for(i=0;i<sum;i++){
            if(pd[i].name==str){
                pd[i].pq.push(money);
                flag=0;
                break;
            }
        }
        //push(str)
        if(flag){
            pd[sum].name=str;
            pd[sum].pq.push(money);
            sum++;
        }
    }
    //print
    for(i=0;i<sum;i++){
        cout << pd[i].name<<",";
        while(!pd[i].pq.empty()){
            cout << pd[i].pq.top()<<",";
            pd[i].pq.pop();
        }
        cout << "\n";
    }
   return 0;
}

## 11/25實習(list)
### [QQ鍵盤](http://140.121.198.41:20211/contest/13/problem/1)
### [UVa_11988 Broken Keyboard (iterator與list)](https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=3139)

#include<bits/stdc++.h>

using namespace std;

int main()
{
    string str;
    while(cin >> str){
        list<char> _list;
        list<char>::iterator it;
        it=_list.begin();   //初始化
        for(char c:str){    //字元判斷
            if(c=='['){ //頭
                it=_list.begin();
            }
            else if(c==']'){    //尾
                it=_list.end();
            }
            else{   //插入it的位置
                _list.insert(it,c);
            }
        }
        
        //output
        for(char c:_list){
            cout << c;
        }
        cout << "\n";
        
    }
    return 0;
}

### [多項式加法與乘法](http://140.121.198.41:20211/contest/13/problem/2)

#include<bits/stdc++.h>
using namespace std;

typedef struct poly* polypointer;
struct poly{
	int coef;
	int exp;
	polypointer link;
};

polypointer bubbleSortList(polypointer* head) {
	// bubble sort with no size
	polypointer tmp;
	polypointer curr = *head;
	polypointer prev = *head;
	polypointer tail = NULL;
	while (*head != tail) {
		curr = *head;
		prev = *head;
		while (curr && curr->link && curr->link != tail) {
			if (curr->exp < curr->link->exp) {
				tmp = curr->link;
				curr->link = tmp->link;
				tmp->link = curr;
				if (curr == *head) {
					prev = tmp;
					*head = tmp;
				}
				else {
					prev->link = tmp;
					prev = prev->link;
				}
			}
			else {
				if (curr != *head)
					prev = prev->link;
				curr = curr->link;
			}
		}
		// In each iteration, we need to adjust tail. And we know curr->link = tail, so we let tail = curr here.
		tail = curr;
	}
	return *head;
}

void add(polypointer* first, int coe, int ex) {
	polypointer temp, cur;
	temp = (polypointer)malloc(sizeof(*temp));
	temp->coef = coe, temp->exp = ex;
	temp->link = NULL;
	if (*first != NULL) {
		cur = *first;
		while (cur->link != NULL) {
			cur = cur->link;
		}
		cur->link = temp;
	}
	else
		*first = temp;
}

void print(polypointer* first) {
	for (; *first != NULL; *first = (*first)->link) {
		if ((*first)->exp == 0)
			cout << (*first)->coef;
		else if ((*first)->exp == 1)
			cout << (*first)->coef << "x";
		else
			cout << (*first)->coef << "x^" << (*first)->exp;
		if ((*first)->link != NULL) {
			cout << " + ";
		}
	}
	cout << "\n";
}

void mul_list(polypointer head, polypointer head1) {
	polypointer ans, newnode, cur, cpyhead1,temp;
	ans = NULL;
	newnode = (polypointer)malloc(sizeof(*newnode));
	newnode->link = NULL;
	for (; head != NULL; head = head->link) { //乘數
		for (cpyhead1 = head1; cpyhead1 != NULL; cpyhead1 = cpyhead1->link) {  //被乘數
			int f = 0;
			for (temp = ans; temp != NULL; temp = temp->link) { //判斷ans_list中
				if (temp->exp == head->exp + cpyhead1->exp) { //如果有指數相同,則係數相加。
					temp->coef += head->coef * cpyhead1->coef;
					f = 1;
					break;
				}
			}
			if (!f) {
				add(&ans, head->coef * cpyhead1->coef, head->exp + cpyhead1->exp);
			}
		}
	}
	bubbleSortList(&ans);
	cout << "mult = ";
	print(&ans);
}

void add_list(polypointer head, polypointer head1) {
	polypointer ans;
	ans = NULL;
	while (head != NULL && head1 != NULL) {
		if (head->exp == head1->exp) {
			if (head->coef + head1->coef != 0) { //coef=0不加入list中
				add(&ans, head->coef + head1->coef, head->exp);
			}
			head = head->link, head1 = head1->link;
		}
		else if (head->exp > head1->exp) { //丟入head到list
			add(&ans, head->coef, head->exp);
			head = head->link;
		}
		else { //丟入head1到list
			add(&ans, head1->coef, head1->exp);
			head1 = head1->link;
		}
	} //剩下
	for (; head != NULL; head = head->link) {
		add(&ans, head->coef, head->exp);
	}
	for (; head1 != NULL; head1 = head1->link) {
		add(&ans, head1->coef, head1->exp);
	}
	cout << "add = ";
	print(&ans);
}

int main() {
	int coef, exp;
	polypointer head, head1;
	head = NULL;
	head1 = NULL;

	// Input
	while (cin >> coef) {
		if (coef == -1)break;
		cin >> exp;
		add(&head, coef, exp);
	}
	while (cin >> coef) {
		if (coef == -1)break;
		cin >> exp;
		add(&head1, coef, exp);
	}

	// Sort
	bubbleSortList(&head);
	bubbleSortList(&head1);

	// Arithmetic & Output
	add_list(head, head1);
	mul_list(head, head1);
}

### [鏈結串列反轉](http://140.121.198.41:20211/contest/13/problem/3)

void reverse(Node **head) {
    Node* curr = *head;
    Node *prev = NULL, *next = NULL;

    while (curr != NULL) {
        next = curr->nxt;
        curr->nxt = prev;
        prev = curr;
        curr = next;
    }
    *head = prev;
}

### [圓桌報數遊戲](http://140.121.198.41:20211/contest/14/problem/1)

#include <bits/stdc++.h>

using namespace std;

int main()
{
   int n,a,b,i;
   list<int> number;
   auto it=number.begin();
   
   cin >> n >> a >> b;
   for(i=1;i<=n;i++){
       number.push_back(i);
   }
   
   for(it=number.begin(),i=2-a;number.empty()!=1;it++,i++){
       
       if(it==number.end()){
           it=number.begin();
       }
       
        if(i==b){
           cout << *it <<" ";
           
           number.erase(it--);
           i=0;
        }
        
   }
   return 0;
}

### [小圈圈](http://140.121.198.41:20211/contest/14/problem/2)

#include <bits/stdc++.h>

using namespace std;

typedef struct node *nodePointer;
struct node{
    int data;
    nodePointer link;
};

int main()
{
   int T,N,M,A,B,i,j,total=0,maxt=0;
   
   cin >> T;
   while(T--){

        short int out[1001];
        nodePointer seq[1001];
        nodePointer x,y,top;

       cin >> N >> M;

       for(i=1;i<=N;i++){
           out[i]=1;seq[i]=NULL;
       }

       i=M;
       while(i--){
            cin >> A >> B;
            x = (nodePointer)malloc(sizeof(*x));
            x->data=B; x->link=seq[A];seq[A]=x;
            x = (nodePointer)malloc(sizeof(*x));
            x->data=A; x->link=seq[B];seq[B]=x;
       }

        maxt=0;
       for(i=1;i<=N;i++){
           if(out[i]){
               //cout<<"new class:"<<i<<endl;
                total=1;
                out[i]=0;
                x=seq[i];top=NULL;//初始化堆疊
                for(;;){
                    while(x){
                        j=x->data;
                        if(out[j]){
                            //cout <<"j="<< j<<"\n";
                            total++;
                            out[j]=0;
                            y=x->link;x->link=top;top=x;x=y;
                        }
                        else{
                            x=x->link;
                        }
                    }

                    if(!top){
                        if(total>maxt){
                            maxt=total;
                        }
                        break;
                    }
                    x=seq[top->data];top=top->link;//釋回堆疊
                }
           }
       }
       cout << maxt << "\n";
   }
   return 0;
}

### [二元樹的陣列表示法](http://140.121.198.41:20211/contest/15/problem/1)

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n,i=1,V,R,L,node[1024]={0};
    cin >> n;
    cin >> V >> L >> R;
    
    node[1]=V;node[2]=L;node[3]=R;
    
    while(cin >> V){
        
        if(V==-1)break;
        cin >> L >> R;
        if(R==-1||L==-1)break;
        
        int cur=1;
        while(node[++cur]!=V);
        node[cur*2]=L;
        node[cur*2+1]=R;
    }
    
    for(int j=1,sum=0;sum<n;j++){
        cout << node[j] <<" ";
        if(node[j]!=0)sum++;
    }
    
   return 0;
}

### [求二元搜尋樹高度](http://140.121.198.41:20211/contest/15/problem/2)

#include <bits/stdc++.h>
using namespace std;

int max_=0,sum=1;
typedef struct node* treePointer;
typedef struct node {
    int number;
    treePointer leftChild, rightChild;
};

void create_tree(treePointer* current,int number){
    treePointer temp = (treePointer)malloc(sizeof(node));
    temp->leftChild=NULL;   temp->rightChild=NULL;  temp->number=number;
    if(!*current)*current=temp;
    else{
        if(number < ((*current)->number)){
            if((*current)->leftChild==NULL)(*current)->leftChild=temp;
            else create_tree(&((*current)->leftChild),number);
        }
        else{
            if((*current)->rightChild==NULL)(*current)->rightChild=temp;
            else create_tree(&((*current)->rightChild),number);
        }
        sum++;
    }
}

int main()
{
   int number;
   treePointer head=NULL;
   while(cin >> number){
       sum=1;
       create_tree(&head,number);
       if(sum>max_)max_=sum;
   }
   cout << max_;
   return 0;
}