?一、前言

? ? ? ? 單鏈表是線性表的鏈式存儲結構，作為數據結構中最基礎也是最重要的線性結構之一，在考研數據結構科目中占有重要地位。本文將總結帶頭結點單鏈表的各項基本操作，包括初始化、插入、刪除、查找等，并附上完整C語言實現代碼，幫助大家系統掌握這一重要知識點。本文基于王道考研做的知識點總結和代碼復現。

二、基本操作

1. 初始化單鏈表(帶頭結點)

#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;
typedef struct LNode{ElemType data;struct LNode *next;
}LNode,*LinkList;
//初始化，帶頭結點
bool InitLinkList(LinkList &L){L=(LNode*)malloc(sizeof(LNode));L->next=NULL;return true;
}

2. 創建單鏈表

//頭插法
LinkList List_HeadInsert(LinkList &L){LNode *s;ElemType x;scanf("%d",&x);while(x!=9999){s=(LNode*)malloc(sizeof(LNode));s->data=x;s->next=L->next;L->next=s;scanf("%d",&x);	}return L;
}//尾插法
LinkList List_TailInsert(LinkList &L){LNode *r=L,*s;ElemType x;scanf("%d",&x);while(x!=9999){s=(LNode*)malloc(sizeof(LNode));s->data=x;r->next=s;r=s;//r指向新的尾節點scanf("%d",&x);}r->next=NULL;return r;
}

3.??查找、插入與刪除操作

//求長度--O(n)
int Length(LinkList L){int len=0;LNode *p=L->next;while(p!=NULL){len++;p=p->next;}return len;
}
//按位查找--O(n)
LNode *GetElem(LinkList L,int i){LNode *p=L;int j=0;while(p!=NULL&&j<i){p=p->next;j++;}return p;		
}
//按值查找--O(n)
LNode *LocateElem(LinkList L,ElemType e){LNode *p=L->next;while(p!=NULL&&p->data!=e)p=p->next;return p;
}
//插入某元素到鏈表的指定位置--O(n)
bool ListInsert(LinkList &L,int i,ElemType &e){LNode *p=L;int j=0;while(p->next!=NULL && j<i-1){p=p->next;j++;}if(p==NULL)return false;LNode *s=(LNode *)malloc(sizeof(LNode));s->data = e;s->next = p->next;p->next = s;return true;
}//刪除某元素到鏈表的指定位置--O(n)
bool ListDelete(LinkList &L,int i,ElemType &e){LNode *p=L;int j=0;while(p!=NULL&&j<i-1){p=p->next;j++;}if(p==NULL||p->next==NULL){return false;}LNode *q=p->next;e=q->data;p->next=q->next;free(q);return true;	
}

4.?判斷兩鏈表是否有相同節點

//判斷兩個鏈表是否有相同節點
LNode *getSimilar(LNode *A,LNode *B){LNode *a=A->next,*b=B->next;int ab=Length(A)-Length(B);if(ab>0){while(ab){a=a->next;ab--;}}else if(ab<0){while(ab){b=b->next;ab++;}}while(a&&b){if(a->data==b->data) return a;a=a->next;b=b->next;}return NULL;
}

三、主函數測試代碼

int main()
{//創建鏈表A,BLinkList A,B;InitLinkList(A); InitLinkList(B);printf("創建鏈表A(按9999退出):");List_TailInsert(A);printf("創建鏈表B(按9999退出):");List_TailInsert(B);//統計表長,查詢指定的值int len_A,len_B;len_A=Length(A);len_B=Length(B);printf("A,B的長度分別是%d和%d\n",len_A,len_B);printf("按位查詢A的第2個節點是，%d\n",GetElem(A,2)->data);if(LocateElem(B,2)->data != NULL)printf("按值查詢B中是否有節點值為2,有\n");elseprintf("按值查詢B中是否有節點值為2，沒有\n");//打印鏈表A,Bprintf("打印鏈表A:");LNode *p=A->next,*q=B->next;while(p!=NULL){printf("%d\t ",p->data);p=p->next;}	printf("\n打印鏈表B:");while(q!=NULL){printf("%d\t ",q->data);q=q->next;}//查找A,B是否有相同的節點if(getSimilar(A,B)!=NULL) printf("\nA,B中有相同值的節點,%d\n",getSimilar(A,B)->data);else printf("\nA,B中沒有相同值的節點\n");//刪除鏈表A,Bint x,y;for(int i=0;i<=len_A;i++)ListDelete(A,i,x);for(int j=0;j<=len_B;j++)ListDelete(B,j,y);printf("刪除A,B的最后兩個元素是%d,%d",x,y);return 0;
}

基于上述的代碼進行測試，結果如下圖所示：

四、練習模板

萬丈高樓的搭建，也離不開簡單的一磚一瓦，堅實的基礎才是拿下大題的關鍵。

#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;
typedef struct LNode{ElemType data;struct LNode *next;
}LNode,*LinkList;
//初始化，帶頭結點
bool InitLinkList(LinkList &L){}
//頭插法
LinkList List_HeadInsert(LinkList &L){}
//尾插法
LinkList List_TailInsert(LinkList &L){}
//求長度--O(n)
int Length(LinkList L){}
//按位查找--O(n)
LNode *GetElem(LinkList L,int i){}
//按值查找--O(n)
LNode *LocateElem(LinkList L,ElemType e){}
//插入某元素到鏈表的指定位置--O(n)
bool ListInsert(LinkList &L,int i,ElemType &e){}
//刪除某元素到鏈表的指定位置--O(n)
bool ListDelete(LinkList &L,int i,ElemType &e){}
//判斷兩個鏈表是否有相同節點
LNode *getSimilar(LNode *A,LNode *B){}
int main(){
//可用上面的main函數替換該部分的內容
}

五、總結

????????掌握帶頭結點單鏈表的各項操作是數據結構學習的基礎，也是考研的重點內容。帶頭結點的鏈表相比普通鏈表有以下優勢：

• 統一操作：無論鏈表是否為空，操作方式一致
• 簡化代碼：不需要特殊處理第一個結點的情況
• 提高效率：某些操作如頭插法更加高效

六、附錄

????????💡 應試技巧
1. 畫圖！用不同顏色標注指針變化
2. 先寫邊界條件（空表、單結點表）
3. 檢查循環結束后尾結點是否為NULL