通過上一節我們知道順序表的優點：
可隨機存儲（O(1)）：查找速度快
存儲密度高：每個結點只存放數據元素，而單鏈表除了存放數據元素之外，還需存儲指向下一個節點的指針
http://t.csdn.cn/p7OQf
但是順序表也有明顯的缺點，就是需要大片的連續空間，改變容量不方便，所以出現了單鏈表
目錄
一.初始化單鏈表
二.插入結點
1.帶頭結點的插入
2.不帶頭結點的插入：不存在第’0‘個結點，因此i=1時，需要特殊處理
補充:帶頭結點
指針結點的后插操作
指針的前插操作
三.刪除結點
1.帶頭節點的刪除
2.不帶頭節點的刪除
3.刪除指定節點
四.單鏈表的查找
1.按位查找：查找第i個節點的值
2.按值查找：查找鏈表中是否有元素e
補充：求表的長度
一.初始化單鏈表
typedef struct LNode{ElemType data; //每個節點存放一個數據元素struct LNode *next;//指針指向下一個節點
}LNode,*LinkList;
//這里的LinkList==》typedef struct LNode *LinkList,定義一個指向結構體的指針
//在這里
//LNode *L與LinkList L;//都是表示指向單鏈表第一個節點的指針
//LNode *L強調的是一個節點
//LinkList L強調的是一個單鏈表/*不帶頭節點的單鏈表
bool InitList(LinkList &L)
{L=NULL;//防止空間中存在臟數據return true;}bool Empty(LinkList L)
{return (L=NULL);
}void test()
{LinkList L;InitList(L);}
*///帶頭結點的單鏈表
LinkList InitList(LinkList &L)
{L=(LNode *)malloc(sizeof(LNode));//分配一個頭結點if(L==NULL)return NULL;L->next=NULL;//聲明一個指向單鏈表的指針return L;}bool Empty(LinkList L)
{if(L->next==NULL){return true;} elsereturn false;}
//我們可以把頭結點看作第0個結點，這樣寫代碼更加方便
二.插入結點
1.帶頭結點的插入
bool ListInsert(LinkList &L,int i,ElemType e)//i表示插入的位置，e表示插入的元素
{if(i<1){return false;}LNode *p;//指針p指向當前掃描到的結點int j=0;//當前p指向的是第幾個結點p=L; //指向頭節點，頭節點是第0個節點while(p!=NULL && j<i-1)//循環找到第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;}
若先p->next=s，再s->next=p->next,即
?帶頭結點的插入
最好情況：插在表頭O(1)
最壞情況：插在表尾O(n)
平均情況：O(n)
2.不帶頭結點的插入：不存在第’0‘個結點，因此i=1時，需要特殊處理
bool ListInsert(LinkList &L,int i,ElemType e)
{if(i<1)return false;if(i==1)//插入第1個結點的操作與其他節點操作不同 {LNode *s=(LNode *)malloc(sizeof(LNode));s->data=e;s->next=L;L=s;//頭指針指向新結點return true;}LNoden *p;int j=1;//除了這里j=1和帶頭結點的指針不同,其他是相同的p=L;while(p！=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;
}刪除第一個元素時，需要更改頭指針L?
補充:帶頭結點
指針結點的后插操作
//在p結點之后,插入元素e
bool InsertNextNode(LNode *p,ElemType e)
{if(p==NULL)return false;LNode *s=(LNode *)malloc(sizeof(LNode));if(s=NULL)//如果內存分配失敗，如內存不足等return false;s->data=e;s->next=p->next; p->next=s;return true;}?指針的前插操作
1.第一種方法：通過前驅節點完成前插操作
需要傳入頭節點才能找到p的前驅結點，即
bool InsertPriorNode(LinkList L,LNode *p,ElemType e)
bool InsertPriorNode(LinkList L,LNode *p,ElemType e)
{if(p==NULL)return false;LNode *s=(LNode*)malloc(sizeof(LNode));if(s==NULL)return false;LNode *current=L;while(current->next!=p)current=current->next;s->data=e;s->next=current->next;current->next=s;return true;
}
?在這里時間復雜度為O(n)，如何減小時間復雜度，可以用第二種方法
2.第二種方法：通過結點的數據交換完成前插操作
bool InsertPriorNode(LNode *p,ElemType e)
{if(p==NULL)return false;LNode *s=(LNode *)malloc(sizeof(LNode));if(s==NULL)return false;s->next=p->next;p->next=s; //新節點s連到p之后s->data=p->data;//將p中元素復制到s中p->data=e;//p中元素覆蓋為ereturn true;}
?關鍵在于s->data=p->data;p->data=e;這樣實現了兩節點的數據交換，實現了在p結點前插入e元素，同時這里的時間復雜度是O（1）
所以對于插入節點可以觀察到如下兩個規律
1.先后再前
s->next=p->next;
p->next=s;
2.先小后大
在第一個節點插入
s->next=L;
L=s????????//頭指針指向新插入的節點s?
三.刪除結點
1.帶頭節點的刪除
bool ListDelete(LinkList &L,int i,ElemType &e)
{if(i<1){return false;}LNode *p=L;int j=0;while(p!=NULL && j<i-1)//這里是尋找要刪除結點的前驅結點{p=p->next;j++;} if(p==NULL)return false;if(p->next==NULL)//如果要刪除結點的前驅結點為NULL,那么刪除就無意義了return false;LNode *q=p->next;//令q指向被刪除結點e=q->data;//用e返回元素的值p->next=q->next;//將*q結點從鏈表中斷開free(q);//釋放qreturn true;
}
最好時間復雜度為O(1)：刪除第一個節點
最壞和平均時間復雜度為O(n)
2.不帶頭節點的刪除
bool ListDelete(LinkList& L, int i, ElemType& e) {if (i < 1)return false;if (i == 1) { LNode* p = L;L = L->next;free(p);return true;}LNode* p = L;int j = 1;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;
}
?3.刪除指定節點
//刪除指定節點p
bool DeleteNode(LNode *p)
{if(p==NULL)return false;LNode *q=p->next; // 令q指向*p的后繼節點q->data=p->next->data;p->next=q->next;//將*q節點從鏈中斷開free(q);//釋放后繼節點的存儲空間return true;}
//如果p的后繼節點剛好為NULL,那么p->next->data指向空所以這段代碼對此情況不適用
//針對此情況還是要找到其前驅節點，然后進行刪除找前驅節點進行刪除
bool DeleteNode(LinkList L, LNode* p, ElemType& e) {if (p == NULL)return false;LNode* q = L;while (q->next != p)q = q->next;q->next = NULL;e = p->data;free(p);return true;
}四.單鏈表的查找
1.按位查找：查找第i個節點的值
LNode *GetElem(LinkList L,int i)
{if(i<0)return false;LNode *p=L;int j=0;while(p!=NULL && j<i)//循環找到第i個節點{p=p->next;j++;}return p;}
平均時間復雜度O(n)
2.按值查找：查找鏈表中是否有元素e
LNode *LocateElem(LinkList L,ElemType e)
{LNode *p=L->next;//從第一個節點開始查找數據域為e的節點while(p!=NULL && p->data!=e)p=p->next;return p;//找到后返回該節點的指針，否則為NULL
}平均時間復雜度O(n)
補充：求表的長度
int length(LinkList L)
{int len=0;LNode *p=L;while(p!=NULL){p=p->next;len++;}return len;}
)
