本文來講單鍊表，主要講它的結構定義、代碼實現以及一些重要的操作。

首先，鍊表是一種鍊式存儲結構，其特點是用一組任意的存儲單元來存儲數據元素，每個存儲單元需要通過一定方式串聯起來，那麼這裡需要引入節點的概念。一個節點表示鍊表中的一個數據元素，除了包括存儲數據信息外，還需要包含下一個節點的指向信息，所以一個節點會包含數據域和指針域，數據域存儲元素的數據信息，指針域指示直接後繼的信息。如下圖

那麼結構體如下

struct node { int val; node *next; };

當然這裡的數據域就一個整數值，也可以有更多的值，根據需要而定。另外，為了方便處理空表，通常在單鍊表前面會引入一個頭節點，這個頭結點的數據域可以不存放任何數據，如果将每個節點都連接起來，不難想象結構如下

下面實現單鍊表的定義以及各種常見的操作。

需要有頭指針，臨時指針變量p和q，分别表示當前節點和它的前驅節點，如下

node *head, *p, *q; void Init() { head = new node(); q = head; }

如果在單鍊表的尾部插入元素，那麼需要創建一個新的節點，将新節點值賦值給數據域，修改其前驅節點的next，使其指向到當前節點，然後将前驅節點的指針後移，并将當前節點的指針域設置為空。代碼如下

void Insert(int x) { p = new node(); p->val = x; q->next = p; q = p; q->next = NULL; }

上面這種插入方法叫做尾插法。

直接從鍊表頭開始往後遍曆，直接判斷有無相等值存在即可。

bool Search(node *t,int x) { node *p = t; while(p != NULL) { if(p->val == x) return true; p = p->next; } return false; }

需要引入一個計數器來記錄當前已經遍曆到第幾個元素了，當遍曆元素達到k個，直接輸出第k個節點的元素值。代碼如下

int Find(node *t,int k) { int cnt = 1; node *p = t; p = t->next; while(p != NULL && (cnt < k)) { p = p->next; cnt ; } return p->val; }

若找到了要删除元素的節點，假如該節點為p，隻需要将它的前驅節點的指針域指向p的後繼節點，即q->next = p->next，如下圖

代碼如下

void Delete(node *t,int x) { node *q = t,*p; p = q->next; while(p != NULL && (p->val != x)) { q = p; p = p->next; } q->next = p->next; delete p; }

直接從head指針開始從前往後遍曆即可。代碼如下

void Print() { node *t = head; t = t->next; while(t != NULL) { printf("%d ", t->val); t = t->next; } printf("\n"); }

以上就是單鍊表的結構定義和基本操作。

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!