鏈表是一種數(shù)據(jù)結(jié)構(gòu)，對于要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的人學(xué)習(xí)好鏈表是非常重要的蚜枢。
一個(gè)鏈表需要包含什么呢缸逃，我的理解就是：1针饥、有n個(gè)節(jié)點(diǎn)離散分配，2需频、每個(gè)節(jié)點(diǎn)通過指針來連接丁眼，3、每個(gè)節(jié)點(diǎn)都有一個(gè)前驅(qū)節(jié)點(diǎn)和一個(gè)后驅(qū)節(jié)點(diǎn)昭殉，4苞七、首節(jié)點(diǎn)沒有前驅(qū)節(jié)點(diǎn)，尾節(jié)點(diǎn)沒有后驅(qū)節(jié)點(diǎn)挪丢。
一蹂风、節(jié)點(diǎn)的構(gòu)造
typedef struct Nod
{
int data;//存放數(shù)據(jù)的域
struct Node *pNext; //定義一個(gè)結(jié)構(gòu)體指針，指向下一個(gè)數(shù)據(jù)類型相同的節(jié)點(diǎn)
}NODE,*PNODE; //NODE等價(jià)于 struct Node; PNODE等價(jià)于struct Node *乾蓬； 此處用大寫是為了與變量區(qū)分惠啄，可以讓人容易變出是個(gè)數(shù)據(jù)類型
typedef 只是給數(shù)據(jù)類型取個(gè)別名，即 typedef 數(shù)據(jù)類型 別名巢块；我們知道struct Node 是我們定義的數(shù)據(jù)類型礁阁；
（2）鏈表的創(chuàng)建
在創(chuàng)建鏈表之前，我們需要需要了解一下專業(yè)術(shù)語：
首節(jié)點(diǎn)：存放第一個(gè)有效數(shù)據(jù)的節(jié)點(diǎn)族奢；
尾節(jié)點(diǎn)：存放最后一個(gè)有效數(shù)據(jù)的節(jié)點(diǎn)姥闭；
頭節(jié)點(diǎn)：頭節(jié)點(diǎn)的數(shù)據(jù)類型與首節(jié)點(diǎn)的數(shù)據(jù)類型相同，并且頭節(jié)點(diǎn)是首節(jié)點(diǎn)前面的那個(gè)節(jié)點(diǎn)越走，并不存放有效數(shù)據(jù)棚品；頭節(jié)點(diǎn)的存在只是為了方便鏈表的操作。
頭指針：指向頭節(jié)點(diǎn)的指針廊敌；
尾指針：指向尾節(jié)點(diǎn)的指針铜跑；
二、在頭節(jié)點(diǎn)后面插入一個(gè)節(jié)點(diǎn)
PNODE Create_Lise(void){
int len;//存放鏈表的長度
int i;//循環(huán)變量
int val;//用來臨時(shí)存放變量
PNODE Lise;
PNODE pHead=(PNODE) malloc(sizeof(NODE));//分配一個(gè)節(jié)點(diǎn)
if(pHead==NULL){
printf("請輸入鏈表的值");
exit(-1);
}else{
PNODE pTail=pHead;
pHead->pNext=null;
printf("需要一個(gè)指針指向結(jié)尾");
scanf("%d",&len);
for(i=o;i<len;i++){
PNODE p=(PNODE)malloc(sizeof(NODE));
if(null=p){
printf("插入了");
exit(-1);
} else{
printf("我在最后插入");
scanf("%d",&val);
p->data=val;
pTail->pNext=p;
p->pNext=null;
pTail=p;
}
}
}
}
三骡澈、向鏈表插入元素
//鏈表的第pos有效元素前面插入元素val锅纺，首先我們應(yīng)該找到第pos個(gè)元素前面一個(gè)元素的位置；
//當(dāng)鏈表有3個(gè)元素時(shí)肋殴，pos=4囤锉，將不會(huì)進(jìn)行插入操作
bool Insert_List(PNODE pHead,int pos,int val){
int i=0;
PNODE p=pHead;
while((Null!=p)&&(i<pos-1)){
p=p->pNext;
i++
}
if(p==null||i>pos-1)//把鏈表為空的情況考慮進(jìn)去了；i>pos-1可以防止用戶輸入錯(cuò)誤护锤；
return false;
//程序執(zhí)行到這之后官地，i=pos-1；p指針指向鏈表第pos個(gè)有效節(jié)點(diǎn)前驅(qū)烙懦，即指向第pos-1節(jié)點(diǎn)驱入；
PNODE q=(PNODE)malloc(sizeof(NODE));
q->data=val;
q->pNext=p->pNext;
p->pNext=q;
}
四、刪除鏈表中的元素
bool Delete_Lise(PNODE pHead,int pos,int *var){
int i=0;
PNODE p=pHead;
while((NULL!=p)&&(i<pos-1)){
p=p->pNext;
i++;
}
if(p==null||i>pos-1) //把鏈表表為空的情況去了
return false;
//程序執(zhí)行到這后，i=pos-1亏较；
PNODE q=p->pNext;//q指向待刪除的節(jié)點(diǎn)
*val=q->data;
p->pNext=q->pNext;//修改鏈表的指向
free(q); //釋放q所指向節(jié)點(diǎn)的內(nèi)存
q=NULL; //如果不清空莺褒，會(huì)出現(xiàn)野指針
}
五來來來冒泡排序一下
void Sort_List(PNODE pHead){
int i,j;
int temp;
int len=length_List(pHead);
PNODE p,q;
for(i=0,p-pHeda->pNext;i<len-1;i++,p->pNext){
for(j=i+1,q=p->pNext;i<len;j++,q=q->pNext){
//交換數(shù)據(jù)
if(p->data>q->data){
temp=p->data;
p->data=q->data;
q->data=temp;
}
}
}
}
