單向連結串列的基本操作

一、連結串列與陣列:

  首先,我們來看看為啥我們有了陣列,還需要連結串列呢?那麼我們來看看連結串列與陣列的區別。

二者都屬於一種資料結構:
從邏輯結構來看:

1、 陣列必須事先定義固定的長度(元素個數),不能適應資料動態地增減的情況。當資料增加時,可能超出原先定義的元素個數;當資料減少時,造成記憶體浪費;陣列可以根據下標直接存取。

2、 連結串列動態地進行儲存分配,可以適應資料動態地增減的情況,且可以方便地插入、刪除資料項。(陣列中插入、刪除資料項時,需要移動其它資料項,非常繁瑣)連結串列必須根據next指標找到下一個元素

從記憶體儲存來看:

  • (靜態)陣列從棧中分配空間, 對於程式設計師方便快速,但是自由度小
  • 連結串列從堆中分配空間, 自由度大但是申請管理比較麻煩

  從上面的比較可以看出,如果需要快速訪問資料,很少或不插入和刪除元素,就應該用陣列;相反, 如果需要經常插入和刪除元素就需要用連結串列資料結構了。


二、單向連結串列的相關操作:

1、定義連結串列結構體:

這裡沒有使用頭結點。

struct Node
{
int num;              //這裡用來方便查詢連結串列位置,可以省略
datatype data;        //資料 
struct Node *pNext;   //指向下一個結點
};
typedef struct Node node;   //定義一個node型別

2、插入資料(後面):

void backadd(node **ppnode,int num, datatype data)
{
node *pNewnode = (node *)malloc (sizeof(node));
//creat a  new node
pNewnode->num =num;    //給新結點賦值
pNewnode->data=data;
if(*ppnode == NULL)     //如果首元結點為空
{
*ppnode = pNewnode;     //將新加入的結點作為首元結點
pNewnode->pNext = NULL;
}
else  //the first node isn't empty
{
node *p = *ppnode;    //head 
while(p->pNext != NULL)  
{
p=p->pNext;
}
p->pNext = pNewnode;   //Insert        
}
}

這裡用到了二級指標,用於儲存頭結點指標的地址。如果不用二級指標則需要一個node *的返回值,才能改變結點的地址。

呼叫:

    node *pNode = NULL;    //定義頭結點
backadd(&pNode,1,11);   //出入的是地址

2、結點查詢:

  因為我們在結構體中每個結點我們能設定了一個num,現在我們就可以通過匹配這個num來查詢某個結點。

node *search(node *pNode,int num)
{
node *p=pNode;      
for(;p!=NULL; p=p->pNext)  //遍歷整個連結串列,知道為空
{
if(num == p->num)   //通過設定數字查詢
{
return p;
break;
}
}
return NULL;
}

3、替換結點內容:

  這裡與查詢有些類似,需要先查詢到對於結點,然後再對其內容進行替換。

int change(node *pNode,int oldnum,int newnum,datatype newdata)
{
while(pNode->pNext != NULL) //終止條件
{
if(pNode != NULL)
{
if(oldnum == pNode->num) 
{
pNode->num=newnum;  //賦值
pNode->data=newdata;
return 1;
}
pNode = pNode->pNext; //遍歷整個連結串列,一直到最後pNode->pNext = NULL
}
}
printf("can't find the node,modify failed!");
return 0;
}

4、刪除結點

讓上一個結點直接跳過要刪除的結點,指向要刪除結點的下一個結點。

這裡寫圖片描述

node *delete(node *pNode,int num)
{
node *p1 = NULL;
node *p2 = NULL;
p1=pNode;   //Save the infomation of the linklist
while(p1 != NULL)
{
if(p1->num == num)   //查詢結點
{
break;
}
else
{
//p2指向前一個結點
p2=p1;  //Save the previous node 
p1=p1->pNext;
}
}
if(p1 == pNode)   //要刪除的點是第一個結點
{
pNode=p1->pNext;   //把第一個結點地址變為下一個結點地址
free(p1);  
}
else
{
p2->pNext=p1->pNext;  //ignore p1(delete it)
free(p1);
}
return pNode;
}

這裡也可以用for迴圈來實現,傳入一個n值來控制要刪除具體那個結點。用for迴圈控制p要移動的次數。接下來,我們在資料的插入中將會用到。


5、資料插入(中間,前面)

  和刪除類似,需要找到前後兩個結點並用p1,p2來儲存。再進行相關操作。是刪除結點的反操作。

在中間插入圖解:
這裡寫圖片描述

void insert(node **pNode,int n,int newnum,datatype newdata)
{
node *p1,*p2;
p1=p2=NULL;
p1=*pNode;
int i=0;
while(p1 != NULL)
{
for(i=1;i<n;i  )   //用for迴圈找出要在第幾個結點前面插入
{
p2=p1;
p1=p1->pNext;
}
break;
}
node *pNewnode=(node *)malloc(sizeof(node));
pNewnode->num=newnum;
pNewnode->data=newdata;
printf("%p",pNewnode);
if(pNode == p1)    //insert it on the head
{
pNewnode->pNext = *pNode;
*pNode=pNewnode; 
}
else            //中間
{
pNewnode->pNext=p1;
p2->pNext=pNewnode;
}
}

6、連結串列逆序:

  逆序:資料顛倒,但是地址不變。也就是說要把連結串列的指向顛倒過來。需要三個變數,p1,p2用來遍歷整個連結串列,p3類似於一個臨時變數,方便p1,p2進行資料交換。最後p2==NULL時退出,p1地址作為頭結點的值,並且把原來頭結點的下一個地址置空。

這裡寫圖片描述

node *inverted(node *pNode)
{
node *p1,*p2,*p3;
p1=p2=p3=NULL;
p1=pNode;
if(pNode == NULL || pNode->pNext ==NULL)
{
return pNode;
}
else
{
p1=pNode;
p2=pNode->pNext;
}
while(p2 != NULL)
{
p3 = p2->pNext;  
p2->pNext=p1;
p1=p2;
p2=p3;
}
pNode->pNext = NULL;  //首元結點變最後一個結點,所以指向空
pNode=p1;             //p1移動到最後,把p1地址賦給首元結點。
return pNode;
}

7、連結串列摧毀:

移動一次後,把前面的結點free並置空。

void link_destory(node *pNode)
{
node *p1;
while( pNode != NULL)
{
p1=pNode->pNext;
pNode=p1;
free(p1);
p1=NULL;
}
}

總結:

關於free()與野指標
  連結串列的操作關鍵在與操作指標,所以經常出現段錯誤。為了避免這種情況,我們定義指標後一定要對它進行初始化,而且操作之前要判斷是否為NULL,這很重要,經常容易出錯。還有就是,在用完要記得free,那麼之後,free之後,指標就變成了野指標,一定要把指標賦值為NULL。

比如,在這個例子中,我們可以看到,指標free之後地址依舊不變,只不過它的值變了,變成了一個野指標。
這裡寫圖片描述

形象點來說就是:
你大學的宿舍,入學後就申請,大學四年一直是你在用,別人不能用;大學畢業後,還給了學校,學校究竟有沒有分配給別人你就不清楚了,反正你再也不能使用; 分配給你的寢室號一直在那,你的心也一直記得那個號碼

關於二級指標
  指標的指標就是二級指標。指標用來存放地址,那麼二級指標就是用來存放指標的地址。所以當程式中操作連結串列結點的地址時候,比如,要更改頭結點的時候,就需要通過二級指標來實現,我們傳入的頭結點是一個,node**型別這時候不需要返回值。我們如果不想用二級指標,也可以通過通過返回 node * 的頭結點來實現。