資訊工程 - 演算法與資料結構 - 資料結構 - 鏈結串列（Linked List）
連結リスト（Linked List）
是鏈結串列。
鏈結串列的定義：
typedef struct node
{
int data;
struct node *next;
}node,*list;
不要問爲什麽這麽寫，聲明一個結構體變數就是這樣的。
最簡單的鏈結串列，頭部放data，尾部放結構體指標，用於鏈接下一個鏈結串列。
*雖說是結構體指標，但是你從鏈結串列裏面抽出任意一個node，都可以通過這一個node獲得它之後一長串的整條鏈結串列
鏈結串列的搜索：
node *search(list head, int val)
{
while(head!=NULL)
{
if(head->data==val)
return head;
else
head=head->next;
}
return NULL;
}
鏈結串列的插入：
//這個是在某個指定index位置插入
list insert(list head,int val,int pos)
{
//這句話是用來判斷是否超過索引,size函數自己寫，size函數是獲得鏈結串列的長度
if(pos>size(head))
return head;
//聲明生成一個新的node（沿用原node的結構，來申請内存空間）
node *new_node=(node *)malloc(sizeof(node));
new_node->data=val;
//如果你在頭部插入的話，那直接把新生成的node的next指向head就完事了
if(pos==0)
{
new_node->next=head;
return new_node;
}
//取出head的實體
node *prev=head;
int i;
//尋找到指定插入的位置i
for(i=0;i<pos-1;i++)
//反復把下一個node賦給prev
prev=prev->next;
//最後把指定位置的node的next傳給new_node(因爲這是新生成的node，next沒有指向)
new_node->next=prev->next;
//然後再讓prev的next指向new_node，這樣鏈結串列就鏈接成功了
prev->next=new_node;
//最後返回整條鏈結串列
return head;
}
鏈結串列的刪除：
list del(list head, int pos)
{
//size函數是返回head的長度，如果你很確信你放進去的pos不會超過索引長度，可以刪除以下兩句不寫
if(pos>=size(head))
return head;
//如果你只是想刪除首個節點
if(pos==0)
{
node *tmp=head;
head=head->next;
free(tmp);
return head;
}
//操作大致和插入相同，不多贅述
node *prev=head;
int i;
for(i=0;i<pos-1;i++)
prev=prev->next;
node *tmp=prev->next;
prev->next=tmp->next;
free(tmp);
return head;
}
Size函數：
int size(list L)
{
node* p;
int len;
p=L->next;
if(!p)return -1;
while(p){
len++;
p=p->next;
}
return len;
}
這是我自己寫的一個size函數。（未實際測試）
双方向リスト（Double Linked List）
雙向鏈結串列的定義：
typedef struct node
{
int data;
struct node *next;
struct node *prev;
}node,*list;
循環（双方向）リスト（Circular(doublely)Linked List）
這個就是基於雙向鏈結串列，只不過是最後頭尾相連接了而已。
留言
張貼留言