數據結構：C語言實現----帶頭結點的單鏈表

帶頭結點的單鏈表

特點：
①頭結點定義在棧區，不儲存數據，起標記作用，不參與具體運算。
②其他數據結點在堆區，動態申請記憶體/

帶頭結點的單鏈表結構體宣告

typedef struct Node
{
 int data;
 struct Node *next;
}Node, *LinkList;

具體實現如下：

（1）初始化：頭結點本身已存在，只需將頭的next置爲NULL

void InitLinkList(LinkList plist)
{
 assert(plist != NULL);
 if(plist == NULL)
 {
  return;
 }
 plist->next = NULL;
}

（2）求鏈表長度

int Listlength(LinkList plist)
{
 assert(plist != NULL);
 if(plist == NULL)
 {
  return -1;
 }
 
 plist->data=0;
 LinkList p = plist->next;
 while(p!=NULL)
 {
	plist->data++;
 	p=p->next;
 } 
 return plist->data;
 }

(3)求結點位置，返回該結點

LinkList GetNode(LinkList plist, int pos)
{
 assert(plist != NULL);
 if(plist == NULL)
 {
  return NULL;
 }

 if(pos<0) //判斷pos是否合法
 {
  return NULL;
 }

 LinkList p=plist;
 while(pos!=0 && p!=NULL)
 {
  p=p->next;
  pos--;
 }
 return p;
}

（4）靜態函數：申請新節點（避免了呼叫函數是進棧出棧，速度快很多）

static LinkList NodeApply(LinkList next, int val) 
{
 LinkList q=(Node *)malloc(sizeof(Node))；
 assert(q != NULL);
 if(q == NULL)
 {
  return NULL;
 }
 
 q->data=val;
 q->next = next; //先連後面
 
 return q;
}

（5）插入

void Insert(LinkList plist,int pos,int val)
{
 assert(plist != NULL);
 if(plist == NULL)
 {
  return;
 }

 LinkList p=GetNode(plist,pos); //找到要插入其後的結點的位置
 p->next=NodeApply(p->next,val);
}

（6）頭插 //呼叫Insert

void InsertHead(LinkList plist, int val)
{
 assert(plist != NULL);
 if(plist == NULL)
 {
  return;
 }
 Insert(plist, 0, val);
}

（7）尾插

void InsertTail(LinkList plist, int val)
{
 assert(plist != NULL);
 if(plist == NULL)
 {
  return;
 }
 Insert(plist, Listlength(plist), val);
}

（8）輸出

void Show(LinkList plist)
{
 assert(plist != NULL);
 if(plist == NULL)
 {
  return;
 }
 
 for(Node *p=plist->next; p!=NULL; p=p->next)
 {
  printf("%d -->",p->data);
 }
 
 printf("NULL\n");
}

（9）刪除

void Delete(LinkList plist, int pos)
{
 assert(plist != NULL);
 if(plist == NULL)
 {
  return;
 }
 
  if(pos<0 || pos>Listlength(plist))
 {
  return;
 }

 LinkList p=GetNode(plist,pos-1); //要刪除的結點的前一個結點；
 LinkList q=p->next; //要刪除的結點
 p->next=q->next;
 free(q);
}

（10）O(1)頭刪

void DeleteHead(LinkList plist)
{
 assert(plist != NULL);
 if(plist == NULL)
 {
  return;
 }
 
 LinkList p= plist->next;
 if(p!=NULL)
 {
  plist->next=p->next; //刪除p
 }
 free(p);
}

（11）尾刪

void DeleteTail(LinkList plist)
{
 assert(plist != NULL);
 if(plist == NULL)
 {
  return;
 }
 Delete(plist,Listlength(plist));
}

（12）判空

int ListEmpty(LinkList plist)
{
 assert(plist != NULL);
 if(plist == NULL)
 {
  return -1;
 }
 
 if(plist->next == NULL)
 {
  return -1; //爲空
 }
 
 return 0;
 }

(13)清空鏈表

void ClearList(LinkList plist)
{
 assert(plist != NULL);
 if(plist == NULL)
 {
  return;
 }
 
  while(!ListEmpty(plist)) //只要不爲空
 {
  DeleteHead(plist); //進行頭刪，效率高
 }
}

鏈表習題

1.判斷兩個單鏈表是否相交

bool Union(LinkList listA,LinkList listB)
{
 assert(listA != NULL && listB != NULL);
 if(listA == NULL || listB == NULL)
 {
  return false;
 }
 
 int len1=Listlength(listA);
 int len2=Listlength(listB);
 LinkList p1=listA;
 LinkList p2=listB;
  if(len1>len2)
 {
  for(int i=0; i<len1-len2; i++)
  {
   p1=p1->next; //p1前進兩條鏈表長度相差的長度單位，即p2在同一出發點
  }
 }
 else
 {
  for(int i=0; i<len2-len1; i++)
  {
   p2=p2->next;
  }
 }
  while(p1 != NULL)
 {
  p1=p1->next; //p1和p2同時後移
  p2=p2->next;
    if(p1 == p2) //相等即證明相交
   return p2;
 }
 return NULL;
 }

2.找倒數第K個結點

LinkList BackFind(LinkList plist,int k)
{
 assert(plist != NULL);
 if(plist == NULL)
 {
  return NULL;
 }

 LinkList p=plist;
 LinkList q=plist;
 for(int i=0; i<k && p != NULL; i++)
 {
  p=p->next; //即p先走k步
 }
 
  if(p == NULL) //k的值大於鏈表長度
  	return NULL;
  	
  while(p != NULL) //p和q同時向後走，則p走到最後時，q指向的就是倒數第k個
 {
  p=p->next;
  q=q->next;
 }
 
return q;
}

3.O(1)刪除p節點(p是指向鏈表中的某一個不爲尾節點的節點)

void DeleteO1(LinkList plist,LinkList delnode)
{
 assert(plist != NULL && delnode!=NULL);
 if(plist == NULL || delnode == NULL)
 {
  	return;
 }
  if(delnode->next == NULL) //若爲尾結點，則呼叫尾刪
 {
 	 DeleteTail(plist);
 }
  if(plist->next!=NULL) 
  {
  	LinkList tmp=delnode->next; //將要刪除結點的後一個結點前移，即賦值給要刪除的結點
  	delnode->data=tmp->data;
  	delnode->next=tmp->next;
  	free(tmp);
  }
 }

4.判斷單鏈表是否有環

LinkList Circle(LinkList plist) 
{
 assert(plist != NULL);
 if(plist == NULL)
 {
  return NULL;
 }
 
 LinkList p1=plist; //慢指針
 LinkList p2=plist; //快指針
 
 while(p2!=NULL && p2->next!=NULL) //即類似跑步快的人，一定能追上跑步慢的人
 {
  	p1=p1->next;
  	p2=p2->next->next;
  	if(p1 == p2) 
     		return p1; //相交的第一個節點
 }

return NULL;
}

5.如果有環，找到入環的第一個節點

p(快):x+y+(k+y)*n
q(慢):x+y
推到可得：
2(x+y)=x+y+(k+y)*n
x=(k+y)(n-1)+k
k+y是一圈，n-1可認爲m,即跑了m圈。x就等於k加上m個圈

LinkList FindLoop(LinkList plist)
{
 LinkList s=Circle(plist);
 if(s == NULL)
  return NULL;
  
 LinkList p=plist;
 LinkList q=s; //相交結點
 
  while(p != q)
 {
  p=p->next; //走x的路程 
  q=q->next; //把剩下的k走完，若是找不到入環，則一直轉圈，直到找到入環點
 }
 return p;
}

6.實現鏈表逆置

void Reverse(LinkList plist)
{
 assert(plist != NULL);
 if(plist == NULL)
 {
  return;
 }
 
 LinkList p=NULL; //記錄當前要處理的節點位置
 LinkList q=plist->next; //當前要處理結點的後一個結點
 LinkList s=q->next;
 
 while(q)
 {
  	q->next=p;
 	p=q;
        q=s;
  	if(s != NULL)         //q指向最後一個，s爲空
  		s=s->next;
 }
  plist->next=p; //頭指針指向最後一個
  }