算法設計題
問題1
已知一個帶頭結點的單鏈表head，假設結點中的元素為整數，試編寫算法：按遞增次序輸出單鏈表中各個結點的數據元素，并釋放結點所占的存儲空間。要求：(1)用文字給出你的算法思想；(2)不允許使用數組作為輔助空間。
//算法思想（冒泡排序）
對鏈表進行遍歷，在每趟遍歷中查找鏈表的最小值，輸出并釋放空間。再查找次小值，輸出并釋放空間，最后釋放頭節點。算法時間復雜度為O(n^2)
//代碼實現while(head->next != null){LNode *pre = head;LNode *p = head->next;while(p->next != null){if(p->next->data < pre->next->data){pre = p;}p = p->next;}cout << pre->next->data;LNode *q = pre->next;pre->next = q->next;free(q)}free(head);
}
問題2
假設以帶頭結點的循環單鏈表表示隊列，并且只設置一個指針rear指向隊尾結點，但不設頭指針，請寫出相應的入隊列和出隊列操作。
//算法思想
本題是鏈隊基本操作的擴展，知道尾指針后，要實現元素入隊，則直接用鏈表的插入操作即可。要實現出隊操作，則需要根據尾指針找出頭結點和開始結點，然后進行刪除。要注意的是，尾指針應始終指向終端結點，并且當刪除結點后隊列為空時，必須特殊處理
//代碼實現
typedef struct QueueNode{int data;struct QueueNode *next;
}QueueNode;typedef struct{QueueNode *rear;
}LinkQueue;bool isEmpty(LinkQueue *Q){return Q->rear->next == Q->rear;
}void initQueue(){Q->rear = (QueueNode *)malloc(sizeof(QueueNode));Q->rear->next = Q->rear;
}void enQueue(LinkQueue *&Q, int x){QueueNode *p = (QueueNode *)malloc(sizeof(QueueNode));p->data = x;p->next = Q->rear->next;Q->rear->next = p;Q->rear = p;//將尾指針移向新節點
}int deQueue(LinkQueue *&Q, int &x){if(isEmpty(Q)){return 0;}QueueNode *p;p = Q->rear->next->next;if(p == Q->rear){//隊列中除頭結點外只有一個結點Q->rear = Q->rear->next;Q->rear->next = Q->rear;}else{Q->rear->next->next = p->next;}x = p->data;free(p);return x;
}
注意：什么時候用. 什么時候用->
typedef struct LNode {int data;struct LNode *next;
}LNode，*LinkList;LNode* p;LinkList L;
結構體變量用「.」來訪問成員，而結構體指針用「->」來訪問
訪問data的兩種方式： p->data 等價于 L.data
)
)