這是為了給一個(gè)朋友講解鏈表的操作塞俱，寫(xiě)的一些流程无宿，最后轉(zhuǎn)成實(shí)際的代碼吴菠。
/*****
Step0.鏈表節(jié)點(diǎn)的定義
typedef struct Node
{
int val;
int *next;
}Node;
Step1. 鏈表的建立
函數(shù)：void* malloc (size_t size);
單個(gè)節(jié)點(diǎn)的創(chuàng)建:
初始化：
Node *createOneNode(int val)
{
Node *n = (Node *)malloc(sizeof(Node));
n->val = val;
n->next = NULL;
}
Step2. 連個(gè)節(jié)點(diǎn)連接起來(lái).
n1->next = n2;
Step3. 遍歷所有的節(jié)點(diǎn)（帶頭節(jié)點(diǎn)）赔退。
void traverse(Node *head)
{
Node *p = head->next;
while (p!=NULL)
{
printf("%d ", p->val);
p = p->next;
}
}
Step4. 查找一個(gè)節(jié)點(diǎn)忌堂，為了方便后續(xù)的刪除，返回查找到節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)拴曲。
Sample: head->1->2->3->NULL;
查找2時(shí)争舞，返回結(jié)果為1的地址q，
假如2的地址為comp澈灼， 刪除的時(shí)候竞川，只需要店溢，
1. q->next = q->next->next; //把3的地址賦給了1的下一個(gè)節(jié)點(diǎn)，2就刪除了委乌。
2.記得釋放2的空間 free(comp);
Node *find(Node *head, val)
{
if (head==NULL)
return ;
Node *q = head;
Node *comp = head->next;
while (comp!=NULL && comp->val != val)
{
q = comp;
comp = comp->next;
}
if (comp==NULL)
return NULL;
return q;
}
Step5.刪除一個(gè)節(jié)點(diǎn)床牧。
先找到要?jiǎng)h除節(jié)點(diǎn)的父節(jié)點(diǎn)。
void delNode(Node *head, int val)
{
if (head==NULL)
return ;
Node *q = find(head, val);
if (q==NULL)
return ;
else
{
Node *deln = q->next;//先保存下要?jiǎng)h除的節(jié)點(diǎn)
q->next = deln->next;//將要?jiǎng)h除節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)賦給父節(jié)點(diǎn)指針的下一個(gè)節(jié)點(diǎn)遭贸，3的地址賦給1->next戈咳；
//上一段代碼等同 q->next = q->next->next;
free(deln);//釋放掉要?jiǎng)h除的節(jié)點(diǎn)。
}
}
Step6.插入一個(gè)節(jié)點(diǎn)
頭插法壕吹、尾插法著蛙、任意位置插入。
void headInsert(Node *head, Node *innode)
{
if (head == NULL || innode==NULL)
return ;
Node *tnext = head->next;//先保存下來(lái)頭節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)耳贬。
head->next = innode;//更換頭節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)踏堡。
innode->next = tnext;//將新加進(jìn)入的節(jié)點(diǎn)連接到原來(lái)頭節(jié)點(diǎn)后面的節(jié)點(diǎn)。
}
void tailInsert(Node *head, Node *innode)
{
if (head==NULL || innode==NULL)
return ;
//找到尾節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn).
Node *front = head;
Node *index = head->next;
while (index!=NULL)
{
front = index;
index = index->next;
}
front->next = innode;
}
****/
#include <stdio.h>
#include <stdlib.h>
typedef struct Node
{
int val;
Node *next;
}Node;
Node *createOneNode(int val)
{
Node *p = (Node *)malloc(sizeof(Node));
p->val = val;
p->next = NULL;
return p;
}
//返回查找到節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)
Node *findNode(Node *head, int val)
{
if (head == NULL)
return NULL;
Node *pre = head;
Node *back = head->next;
while (back != NULL && back->val != val)
{
pre = back;
back = back->next;
}
if (back == NULL)
return NULL;
return pre;
}
void delOneNode(Node *head, int val)
{
Node *pre = findNode(head, val);
if (pre == NULL)
return ;
Node *save = pre->next;
pre->next = save->next;
free(save);
}
void headInsert(Node *head, Node *innode)
{
if (head == NULL || innode == NULL)
return ;
Node *save = head->next;
head->next = innode;
innode->next = save;
}
void tailInsert(Node *head, Node *innode)
{
if (head==NULL || innode==NULL)
return ;
//找到尾節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn).
Node *front = head;
Node *index = head->next;
while (index != NULL)
{
front = index;
index = index->next;
}
front->next = innode;
}
void showNodes(Node *head)
{
if (head == NULL)
return ;
Node *p = head->next;
while (p != NULL)
{
printf(" %d", p->val);
p = p->next;
}
printf("\n");
}
void insertBefore(Node *head, int val, Node *innode)
{
;
}
int main()
{
Node *head = createOneNode(0);
Node *pt = NULL;
int i = 0;
for (i=1;i<=10; ++i)
{
pt = createOneNode(i);
headInsert(head, pt);
}
delOneNode(head, 5);
showNodes(head);
delOneNode(head, 10);
showNodes(head);
delOneNode(head, 1);
showNodes(head);
return 0;
}
以上都是帶頭節(jié)點(diǎn)的情況咒劲，
如果應(yīng)用過(guò)程中顷蟆，不存在頭節(jié)點(diǎn)，可以自己申請(qǐng)一個(gè)節(jié)點(diǎn)缎患，作為頭節(jié)點(diǎn)慕的，然后讓它連接到，原本鏈表的第一個(gè)節(jié)點(diǎn)挤渔。
Node *prefirstNode = createOneNode(10);//10隨意值
Node *auxHead = createOneNode(0);//
auxHead->next = prefirstNode;
這樣肮街，上面的函數(shù)就可以傳入 auxHead了。
留一個(gè)函數(shù)判导，在某一節(jié)點(diǎn)前插入嫉父，給讀者實(shí)現(xiàn)。
