# 進階電腦系統理論與實作 補考

> [time=Sun, Nov 5, 2017 3:28 PM]
>
###### tags: `sysprog2017`

### 題目

給定以下程式碼

typedef struct __List {
    struct __List *next;
    int val;
}List;

void sort (List **head);

依據下兩項描述分別實作 bubble sort
- linked list

void sort (List **head){
    List* stageEnd;
    List* current;
    List* last;           // point to last one of current
    List* tmp;
    List Head;            //used to operate conveniently; become to the role of *head 
    bool hasChange;       //means the event of change
    bool firCmp;         //the first time to compare at every turn 

    stageEnd = NULL;    
	Head.next = *head;
    while( Head.next->next != stageEnd ){
        firCmp = true;
		last = &Head;
        current = Head.next;
        while( current->next != stageEnd){                  //judge whether it finished this turn
            hasChange = false;
            if( current->val > current->next->val ){
                //exchange
				last->next = current->next;
                tmp = current->next->next;
                current->next->next = current;
                current->next = tmp;
            }
            else // move current to next
            {
                current = current->next;
            }
			last = last->next;
			firCmp = false;
        }
        stageEnd = current;
    }
    *head = Head.next;
}

- circular linked list

將第 10 行改成 stageEnd = *head; 就可