下圖就是最簡單最一般的單向鏈表：
還有這種：
多一個Tail指針，好處就是能很方便地找到末尾。
留一個終始標志，這個節點作為一個標志，不用于存儲數據，鏈表末尾指向這個節點，形成一個“環形鏈表”，這樣無論在鏈表的哪里插入新的元素，操作都一致了，不必判斷頭和尾的特殊性。數組的好處就是鏈表的壞處，數組的壞處就是鏈表的好處，鏈表插入刪除方便，遍歷麻煩；數組遍歷方便，插入刪除都要移動。
因為需要從頭開始找，沒辦法像數組那樣直接跳到那個地址。而插入元素，就比數組方便了，如果你已經得知了要插入的地址的話，不過還要注意哦，是“后插入”（Insert After）：
有“后插入”，那就有“前插入”（Insert Before），兩者對單向鏈表來說真的不一樣，下圖描述了“前插入”：
由于指針向后不向前，我們不知道要插入位置的前一個節點是什么，只能從頭找，所以比較麻煩。
#include <stdio.h>struct node{ int data; struct node *next;};typedef struct node Node;#define SIZE sizeof(Node)//創建節點Node* creteNode(int d){ Node* pn=malloc(SIZE); pn->data=d; pn->next=NULL; return pn;}//創建鏈表void creatList(Node** h){ Node* pn=NULL; Node* p=NULL; int d; PRintf("請輸入數據/n"); scanf("%d",&d); pn=creteNode(d); *h=pn; p=*h; while(1) { printf("請輸入數據/n"); scanf("%d",&d); if(d==0) break; pn=creteNode(d); p->next=pn; p=p->next; }}這就是上面函數創建的
createNode函數創建一個個的節點，createList將一個個節點串起來。//查找某個節點的位置Node* findNode(Node* h,int n){ int i; if((h==NULL)||(n<0)) { printf("查找位置不合法||鏈表為空！/n"); return NULL; } if(n==1) { return h; } for(i=1;i<=n;i++) { h=h->next; if(h==NULL) break; } return h;}findNode函數是為了查找某個節點，在插入和刪除時使用這個函數方便。//末尾增加一個新的節點int addBack(int d,Node* h){ Node *pn=NULL; pn=creteNode(d); Node* p=h; while(p->next) { p=p->next; } p->next=pn; pn->next=NULL;}
在末尾插入一個節點，先要遍歷到最后一個節點，然后將新節點放在后面。//頭插法int addFont(int d,Node** h)//修改頭節點 傳入二級指針{ Node* pn=NULL; pn=creteNode(d); pn->next=*h; *h=pn;}同尾插法一樣，在頭節點位置插入一個元素。只是不需要遍歷。//插入int insertNode(int n,int d,Node** h)//在n位置插入d{ if((n<1)||(*h==NULL)) { printf("插入位置不合法||鏈表為空!/n"); return 0; } Node* pn=creteNode(d);//創建新的節點 //插入位置為1，即插入頭節點的位置 if(n==1) { Node* pn=NULL; pn=creteNode(d); pn->next=*h; *h=pn; return 0; } else { Node* pf=findNode(h,n-1); //得到插入位置的前一個節點 pn->next=pf->next; pf->next=pn; return 1; }}
首先我們用findNode函數找到插入位置的前一個節點，插入的時候要記得先要斷開以前的連接，刪除也是的，先要斷開連接再進行操作。//刪除第n個位置的元素int deleteNode(int n,Node** h){ //判斷頭節點是否為空，位置是不是合法 if((*h==NULL)||(n<1)) { printf("刪除的鏈表為空||刪除的位置不合法！/n"); return 0; } Node* pd=NULL; //判斷是否只有一個頭節點 if(((*h)->next)==NULL) { printf("只用一個節點/n"); return 0; } //刪除頭節點 if(n==1) { pd=*h; *h=pd->next; free(pd); pd=NULL; return 1; } //刪除 //判斷節點是否存在 if(NULL==findNode(*h,n-1)) { printf("刪除節點不存在/n"); return 0; } //找到要刪除的節點的前一個節點 Node* pf=findNode(*h,n-1); pd=pf->next;//將要刪除的節點的給pd pf->next=pd->next; free(pd); pd=NULL; pf=NULL; return 1;}
也是用findNode函數找到前一個節點的位置，然后先斷開刪除節點位置和后面一個節點的位置。
//打印鏈表void print(Node* h){ printf("list:/n"); while(h) { printf("%d ",h->data); h=h->next; } printf("/n");}int main(){ Node* head=NULL; creatList(&head); print(head); Node* p=findNode(head,0); printf("%d/n",p->data); deleteNode(2,&head); print(head); return 0;}
新聞熱點
疑難解答
