資訊工程 - 演算法與資料結構 - 資料結構 - 鏈結串列(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)

這個就是基於雙向鏈結串列,只不過是最後頭尾相連接了而已。


下一篇:資訊工程 - 演算法與資料結構 -  資料結構 - 堆疊和佇列 - (Stack&Queue)

目錄:資訊工程 - 演算法與資料結構  -  Algorithm&Data Struncture(目錄)

留言

這個網誌中的熱門文章

【TOEIC】多益復習800分的準備 - 第2天(從600分進步到800分計劃)

微積分 - 求不定積分 $$\int \:tanxdx$$ Integral of tan x dx

【TOEIC】多益復習800分的準備 - 第4天(從600分進步到800分計劃)