鏈結串列 Linked list

鏈結串列之搜尋


鏈結串列之搜尋
因為鏈結串列的節點沒有特定名稱（不像陣列元素）可以被二元搜尋法來找出，所以鏈結串列的搜尋演算法只能是循序式的。因為鏈結串列中的節點沒有名稱，因此我們使用了兩個指標：pre（指向上一個）和 cur（指向現在的）。
開始搜尋的時候，指標 pre 是個空指標而指標 cur 指向第一個節點，搜尋演算法會把這兩個指標一起往串列的結尾處移動。
當搜尋停止時，指標 cur 會指向讓搜尋停止的節點，並且指標pre 會指向前一個節點。如果目標數值沒有被找到的話，那麼指標 cur 就是指到擁有比目標數值還要大的節點。

節錄自 Foundations of Computer Science



為什麼要用兩個指標分別指向上一個和目前這個呢?

在鏈結串列中間尋訪時，只用一個pointer並不會有問題
尋訪

p = p->link;


但當在末端(第一個及最後一個)時，
一個指標沒辦法判斷是否到了末端

單向鏈結串列不會也不需要判斷是否到第一個，
而最後一個使用一個pointer也可以 *二修

作刪除元素操作時，必須將動態分配的記憶釋放(free)，
這時使用兩個pointer較方便。 **三修


node* create_node(int data)
{
// 動態配置記憶體
node* n = (node*)malloc(sizeof(node));

n->data = data;
n->next = NULL;

return n;
}
//插入
void insert_node(node* n1, node* n2)
{
n2->next = n1->next;
n1->next = n2;
}
//刪除
void remove_node(node* n1)
{
n1->next = n1->next->next; //沒有釋放memory(recycles garbage)，會產生garbage。
}
較好的作法:

struct node *delete_from_list(struct node *list, int n)
{
struct node *cur, *prev;
for (cur = list, prev = NULL;cur != NULL && cur->value != n;prev = cur, cur = cur->next);
if (cur == NULL) return list; /* n was not found */
if (prev == NULL) list = list->next; /* n is in the first node */
else prev->next = cur->next; /* n is in some other node */
free(cur);
return list;
}



//尋訪
void print_lists(node* lists)
{
node* n = lists;

// 依序印出節點內容
while (n != NULL)
{
printf("%d ", n->data);

n = n->next;
}

printf("\n");
}



結論:
不需要用兩個指標

有兩個指標較方便

參考:
Infinite Loop