資訊工程 - 演算法與資料結構 - 資料結構 - 鏈結串列(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)
這個就是基於雙向鏈結串列,只不過是最後頭尾相連接了而已。
留言
張貼留言