兩種方法的區(qū)別無非是插入的位置：
頭插法：新插入結(jié)點始終未當(dāng)前的第一個結(jié)點
尾插法：新插入結(jié)點始終為當(dāng)前的最后一個結(jié)點
頭插法建表
實現(xiàn)代碼：
//頭插法建鏈表
void HeadCreateList(LinkList L,int n)
{
int i;
srand(time(0)); //初始化隨機(jī)數(shù)種子
L = (LinkList)malloc(sizeof(LNode));
L ->next = NULL;
LinkList p;
//利用循環(huán)生成結(jié)點并添加到單鏈表中
for(i = 0;i < n;i++)
{
p = (LinkList)malloc(sizeof(LNode)); //生產(chǎn)新結(jié)點
p ->data = rand()%100 + 1; //生產(chǎn)兩位隨機(jī)數(shù)100
p ->next = L ->next;
L ->next = p; //插到表頭
}
}
尾插法建表
實現(xiàn)代碼：
void TailCreateList(LinkList L,int n)
{
LinkList p,tail;
int i;
srand(time(0)); //初始化隨機(jī)數(shù)種子
L = (LinkList)malloc(sizeof(LNode));
tail = L;
for(i = 0;i < n;i++)
{
p = (LinkList)malloc(sizeof(LNode)); //生產(chǎn)新結(jié)點
p ->data = rand()%100 + 1; //生產(chǎn)兩位隨機(jī)數(shù)100
tail ->next = p; //將表尾終端結(jié)點的指針指向新結(jié)點
tail = p; //將當(dāng)前的新結(jié)點定義為表尾的尾結(jié)點
}
tail->next = NULL; //當(dāng)前鏈表結(jié)束
}
有趣的算法：查找單鏈表的中間結(jié)點
就是給你一個單鏈表，要你獲得單鏈表中位置中間的結(jié)點？你會怎么做？
一般我們可能用一個指針，從頭到尾擼一遍，同時記錄單鏈表的長度，然后再除以2得出第幾
項為中間結(jié)點，然后再擼length / 2獲得中間節(jié)點，重復(fù)遍歷很繁瑣，有沒有其他的方法呢？
有，肯定有，這里提供一個簡單的方法：
用兩個不同的指針，按照不同的移動順序來移動，這里我們暫且把他們成為快慢指針！
每次循環(huán)，
快指針向后移動兩個結(jié)點： p = p -> next -> next；
慢指針向后移動一個結(jié)點： q = q -> next;
當(dāng)快指針到達(dá)尾部的時候，慢指針不就指向中間結(jié)點了，你說是吧~
原理非常簡單，下面我們寫下代碼實現(xiàn)：
Status GetMidLNode(LinkList *L,ElemType *e)
{
LinkList p,q;
p = q = *L;
while(p ->next ->next != NULL)
{
if(p ->next ->next != NULL)
{
p = p ->next ->next;
q = q ->next;
}else{
p = p ->next;
}
}
e = q ->data;
return OK;
}
12種基礎(chǔ)基本操作代碼實現(xiàn)
從本節(jié)開始就不像上一節(jié)一樣一步步地講解了，直接上代碼，難點部分會寫下注釋！
1）構(gòu)造空表
void InitList(LinkList L)
{
L = (LinkList)malloc(sizeof(LNode));
if(!L)exit(ERROR);
L ->next = NULL;
}
2)將鏈表置為空表
void ClearList(LinkList L)
{
LinkList p = L ->next;
L ->next = NULL;
//接著就是釋放頭結(jié)點以外的結(jié)點了
while(p)
{
p = L->next;
free(L); //釋放首元結(jié)點
L = p; //移動到當(dāng)前的首元結(jié)點
}
}
3)判斷是否為空表
這里要區(qū)分兩種情況：
有頭結(jié)點：L -> next = NULL;此時表為空表！
無頭結(jié)點：L = NULL；此時為空表！
Status ListEmpty(LinkList L)
{
//有頭節(jié)點的情況，只需判斷頭結(jié)點的指針域是否為空即可
if(L ->next)return FALSE;
else return TRUE;
}
4)銷毀單鏈表
void DestoryList(LinkList L)
{
LinkList q;
//刪除頭結(jié)點外的結(jié)點
while(L)
{
//指向首元結(jié)點，而不是頭結(jié)點
q = L ->next;
free(L);
L = q; //刪除后指向首元
}
}
5)獲得表長度
int ListLength(LinkList L)
{
int i = 0;
LinkList p = L ->next;
while(p)
{
i++;
p = p ->next;
}
return i;
}
6)獲得表中第i個元素的值
Status GetElem(LinkList L,int i,ElemType *e)
{
int j = 1;
//指向首元，然后依次后移，假如到了結(jié)尾或者j的值大于i
//還沒找個改元素說明i不合法
LinkList p = L ->next;
while(p && j < i)
{
j++;
p = p ->next;
}
if(!p || j> i)return ERROR;
e = p ->data;
return OK;
}
7)查找表中是否存在滿足條件的元素
int LocateElem(LinkList L,ElemType e,Status(*compare)(ElemType,ElemType))
{
int i = 0;
LinkList p = L -> next;
while(p)
{
i++;
if(compare(p->data,e))return i;
p = p -> next;
}
return 0;
}
8)獲得某個結(jié)點的直接前驅(qū)
Status BeforeElem(LinkList L,ElemType choose,ElemType *before)
{
LinkList q,p = L ->next;
while(p ->next)
{
q = p ->next;
//判斷p的后繼是否為choose,是的話返回OK,否則繼續(xù)后移
if(q ->data == choose)
{
before = p ->data;
return OK;
}
p = q;
}
return ERROR;
}
9.獲得某個結(jié)點的直接后繼
Status NextElem(LinkList L,ElemType choose,ElemType *behind)
{
LinkList p = L ->next;
while(p ->next)
{
if(p ->data == choose)
{
behind = p ->next ->data;
return OK;
}
p = p ->next;
}
return ERROR;
}
10.往表中第i個位置插入元素
Status ListInsert(LinkList L,int i,ElemType e)
{
int j = 0;
LinkList p,q =L; //讓q指向頭結(jié)點
while(p && j < i - 1)
{
j++;
p = p ->next; //p指向下一個節(jié)點
}
if(!p || j > i - 1)return ERROR;
p = (LinkList)malloc(sizeof(LNode));
//要先讓插入的結(jié)點的指針域指向插入位置的后繼結(jié)點
//再讓插入節(jié)點的前驅(qū)的指針域指向插入結(jié)點
//?。?！順序不能亂哦1
p ->data = e;
p ->next = q ->next;
q ->next = p;
return OK;
}
11.刪除表中第i個元素
Status ListDelete(LinkList L,int i,ElemType *e)
{
int j = 0;
LinkList p,q = L;
while(q ->next && j < i -1)
{
j++;
q = q->next;
}
if(!q || j >i -1)return ERROR;
p = q ->next; //指向準(zhǔn)備刪除的結(jié)點
q ->next = p ->next; //刪除結(jié)點的前驅(qū)的指針域指向刪除結(jié)點的后繼
e = p ->data;
free(p); //釋放要刪除的結(jié)點
return OK;
}
12.遍歷單鏈表中的所有元素
void ListTraverser(LinkList L,void(*visit)(ElemType))
{
LinkList p = L ->next;
while(p)
{
visit(p ->data);
p = p ->next;
}
printf("\n");
}
