結(jié)構(gòu)體可以看做是一種自定義的數(shù)據(jù)類型，它還有一個(gè)很重要的特性，就是結(jié)構(gòu)體可以相互嵌套使用，但也是有條件的，結(jié)構(gòu)體可以包含結(jié)構(gòu)體指針，但絕對(duì)不能在結(jié)構(gòu)體中包含結(jié)構(gòu)體變量。
利用結(jié)構(gòu)體的這點(diǎn)特殊特性，我們就可以自己生成一個(gè)環(huán)環(huán)相套的一種射線結(jié)構(gòu)，一個(gè)指向另一個(gè)。
鏈表的學(xué)習(xí)不像想象的那么那么容易，很多人學(xué)習(xí)到這里的時(shí)候都會(huì)碰到困難，很多人也因此而放棄了學(xué)習(xí)，在這里我說(shuō),一定不能放棄，對(duì)應(yīng)它的學(xué)習(xí)我們要進(jìn)行分解式學(xué)習(xí)，方法很重要，理解需要時(shí)間，不必要把自己逼迫的那么緊，學(xué)習(xí)前你也得做一些最基本的準(zhǔn)備工作，你必須具備對(duì)堆內(nèi)存的基本知識(shí)的了解，還有就是對(duì)結(jié)構(gòu)體的基本認(rèn)識(shí)，有了這兩個(gè)重要的條件，再進(jìn)行分解式學(xué)習(xí)就可以比較輕松的掌握這一節(jié)內(nèi)容的難點(diǎn)。
下面我們給出一個(gè)完整的創(chuàng)建鏈表的程序，不管看的懂看不懂希望讀者先認(rèn)真看一下，想一想，看不懂沒(méi)有關(guān)系，因?yàn)槲蚁旅鏁?huì)有分解式的教程，但之前的基本思考一定要做，要不即使我分解了你也是無(wú)從理解的。
代碼如下，我在重要部分做了注解：
//程序作者:管寧
//站點(diǎn):www.cndev-lab.com
//所有稿件均有版權(quán),如要轉(zhuǎn)載,請(qǐng)務(wù)必著名出處和作者
#include <iostream>
using namespace std;
struct test
{
char name[10];
float socre;
test *next;
};
test *head;//創(chuàng)建一個(gè)全局的引導(dǎo)進(jìn)入鏈表的指針
test *create()
{
test *ls;//節(jié)點(diǎn)指針
test *le;//鏈尾指針
ls = new test;//把ls指向動(dòng)態(tài)開(kāi)辟的堆內(nèi)存地址
cin>>ls->name>>ls->socre;
head=NULL;//進(jìn)入的時(shí)候先不設(shè)置head指針指向任何地址,因?yàn)椴恢朗欠褚簧蟻?lái)就輸入null跳出程序
le=ls;//把鏈尾指針設(shè)置成剛剛動(dòng)態(tài)開(kāi)辟的堆內(nèi)存地址,用于等下設(shè)置le->next,也就是下一個(gè)節(jié)點(diǎn)的位置
while(strcmp(ls->name,"null")!=0)//創(chuàng)建循環(huán)條件為ls->name的值不是null,用于循環(huán)添加節(jié)點(diǎn)
{
if(head==NULL)//判斷是否是第一次進(jìn)入循環(huán)
{
head=ls;//如果是第一次進(jìn)入循環(huán),那么把引導(dǎo)進(jìn)入鏈表的指針指向第一次動(dòng)態(tài)開(kāi)辟的堆內(nèi)存地址
}
else
{
le->next=ls;//如果不是第一次進(jìn)入那么就把上一次的鏈尾指針的le->next指向上一次循環(huán)結(jié)束前動(dòng)態(tài)創(chuàng)建的堆內(nèi)存地址
}
le=ls;//設(shè)置鏈尾指針為當(dāng)前循環(huán)中的節(jié)點(diǎn)指針,用于下一次進(jìn)入循環(huán)的時(shí)候把上一次的節(jié)點(diǎn)的next指向上一次循環(huán)結(jié)束前動(dòng)態(tài)創(chuàng)建的堆內(nèi)存地址
ls=new test;//為下一個(gè)節(jié)點(diǎn)在堆內(nèi)存中動(dòng)態(tài)開(kāi)辟空間
cin>>ls->name>>ls->socre;
}
le->next=NULL;//把鏈尾指針的next設(shè)置為空,因?yàn)椴还苋绾窝h(huán)總是要結(jié)束的,設(shè)置為空才能夠在循環(huán)顯鏈表的時(shí)候不至于死循環(huán)
delete ls;//當(dāng)結(jié)束的時(shí)候最后一個(gè)動(dòng)態(tài)開(kāi)辟的內(nèi)存是無(wú)效的,所以必須清除掉
return head;//返回鏈?zhǔn)字羔?nbsp;
}
void showl(test *head)
{
cout<<"鏈?zhǔn)字羔?"<<head<<endl;
while(head)//以內(nèi)存指向?yàn)閚ull為條件循環(huán)顯示先前輸入的內(nèi)容
{
cout<<head->name<<"|"<<head->socre<<endl;
head=head->next;
}
}
void main()
{
showl(create());
cin.get();
cin.get();
}
上面的代碼我們是要達(dá)到一個(gè)目的：就是要存儲(chǔ)你輸入的人名和他們的得分，并且以鏈狀結(jié)構(gòu)把它們組合成一個(gè)鏈狀結(jié)構(gòu)。
程序種有兩個(gè)組成部分
test *create()
和
void showl(test *head)
這兩個(gè)函數(shù)，create是用來(lái)創(chuàng)建鏈表的 ，showl是用來(lái)顯示鏈表的。
create函數(shù)的返回類型是一個(gè)結(jié)構(gòu)體指針，在程序調(diào)用的時(shí)候我們用了showl(create());，而不用引用的目的原因是引導(dǎo)指針是一個(gè)全局指針變量，我們不能在showl()內(nèi)改變它，因?yàn)閟howl()函數(shù)內(nèi)有一個(gè)移動(dòng)操作head=head->next;，如果是引用的話我們就破壞了head指針的位置，以至于我們?cè)僖矡o(wú)法找會(huì)首地址的位置了。
下面我們來(lái)分解整個(gè)程序，以一個(gè)初學(xué)者的思想來(lái)思考整個(gè)程序，由淺入深的逐步解釋。
首先，我們寫(xiě)這個(gè)程序，要考慮到由于是一個(gè)鏈表結(jié)構(gòu)，我們不可能知道它的大小到底是多大，這個(gè)問(wèn)題我們可以用動(dòng)態(tài)開(kāi)辟堆內(nèi)存來(lái)解決，因?yàn)槎褍?nèi)存在程序結(jié)束前始終是有效的，不受函數(shù)棧空間生命期的限制，但要注意的是我們必須有一個(gè)指針變量來(lái)存儲(chǔ)這一鏈狀結(jié)構(gòu)的進(jìn)入地址，而在函數(shù)內(nèi)部來(lái)建立這一指針變量顯然是不合適的，因?yàn)楹瘮?shù)一旦退出，這個(gè)指針變量也隨之失效，所以我們?cè)诔绦虻拈_(kāi)始聲明了一個(gè)全局指針變量。
test *head;//創(chuàng)建一個(gè)全局的引導(dǎo)進(jìn)入鏈表的指針
好解決了這兩個(gè)問(wèn)題，我們接下去思考
有輸入就必然有輸出，由于輸出函數(shù)和輸入函數(shù)是相對(duì)獨(dú)立的，為了不斷測(cè)試程序的正確性好調(diào)試我們先寫(xiě)好輸出函數(shù)和main函數(shù)捏的調(diào)用，創(chuàng)建函數(shù)我們先約定好名為create。
我們先寫(xiě)出如下的代碼：
程序?qū)懙竭@里，基本形態(tài)已經(jīng)出來(lái)，輸入和調(diào)用我們已經(jīng)有了。
下面我們來(lái)解決輸入問(wèn)題，鏈表的實(shí)現(xiàn)我們是通過(guò)循環(huán)輸入來(lái)實(shí)現(xiàn)的，既然是循環(huán)我們就一定得考慮終止循環(huán)的條件，避免死循環(huán)和無(wú)效循環(huán)的發(fā)生。
在create()函數(shù)內(nèi)部我們先寫(xiě)成這樣：
在循環(huán)創(chuàng)建之前我們必須考慮一個(gè)都不輸入的情況。
程序一單進(jìn)入create函數(shù)我們首先必然要?jiǎng)?chuàng)建一個(gè)節(jié)點(diǎn)，我們先創(chuàng)建一個(gè)節(jié)點(diǎn)指針，后把者個(gè)節(jié)點(diǎn)指針指向到動(dòng)態(tài)開(kāi)辟的test類型的動(dòng)態(tài)內(nèi)存地址位置上。
所以我們有了
程序既然是循環(huán)輸入，而結(jié)構(gòu)成員test *next又是用來(lái)存儲(chǔ)下一個(gè)接點(diǎn)的內(nèi)存地址的，每次循環(huán)我們又要?jiǎng)討B(tài)創(chuàng)建一個(gè)新的內(nèi)存空間，所以我們必須要有一個(gè)指針來(lái)存儲(chǔ)上一次循環(huán)動(dòng)態(tài)開(kāi)辟的內(nèi)存地址，于是就有了
test *le;
接下來(lái)在進(jìn)入循環(huán)前我們要?jiǎng)?chuàng)建鏈表的第一個(gè)節(jié)點(diǎn)，第一個(gè)節(jié)點(diǎn)必然是在循環(huán)外創(chuàng)建，于是就有了
cin>>ls->name>>ls->socre;
程序執(zhí)行者的情況是位置的，所以我們必然要考慮，一上來(lái)就不想繼續(xù)運(yùn)行程序的情況，所以我們一開(kāi)始先把head引導(dǎo)指針設(shè)置為不指向任何地址也就是
head=NULL;
為了符合le也就是鏈尾指針的設(shè)計(jì)思路，我們?cè)谘h(huán)前一定要保存剛剛動(dòng)態(tài)開(kāi)辟的內(nèi)存地址，好在下一次循環(huán)的時(shí)候設(shè)置上一個(gè)節(jié)點(diǎn)中的next成員指向，于是我們便有了：
le=ls;
為了實(shí)現(xiàn)循環(huán)輸入我們又了下面的代碼：
程序是循環(huán)必然要有終止循環(huán)的條件，所以我們的循環(huán)條件是：
while(strcmp(ls->name,"null")!=0)
輸入的名字是null的時(shí)候就停止循環(huán)。
為了保證第一次進(jìn)入循環(huán)，也就是在循環(huán)內(nèi)準(zhǔn)備創(chuàng)建第二個(gè)節(jié)點(diǎn)前，設(shè)置引導(dǎo)指針的指向我們有了如下的判斷代碼：
代碼中的else條件是為了設(shè)置前一個(gè)節(jié)點(diǎn)next指向而寫(xiě)的,這點(diǎn)我們記住先看下面的代碼,稍后大家回過(guò)頭想就明白了
le=ls;
ls=new test;
cin>>ls->name>>ls->socre;
le=ls;//這么寫(xiě)就是為了保存上一次循環(huán)指針的位置而設(shè)的,正是為了上面的else代碼而做的預(yù)先保留
ls=new test;
cin>>ls->name>>ls->socre;
這兩行代碼的意思就是繼續(xù)開(kāi)辟下一個(gè)節(jié)點(diǎn)空間,和輸入節(jié)點(diǎn)內(nèi)容!
循環(huán)一旦結(jié)束也就結(jié)束了程序,為了保持程序不出錯(cuò),也就是最后一個(gè)節(jié)點(diǎn)的next成員指向?yàn)榭瘴覀冇辛讼旅娴拇a
le->next=NULL;
程序的思路始終是以先開(kāi)辟后判斷為思路的,所以到最后一個(gè)不成立的時(shí)候總會(huì)有一個(gè)多開(kāi)辟的內(nèi)存空間,為了刪除掉它,我們有了下面的代碼
delete ls;
程序到最后由于返回head指針
return head;
顯示鏈表的函數(shù)沒(méi)有什么太多特別的也只需要注意下面這樣就可以了！
head=head->next;
我們之所以不用head+=1;來(lái)寫(xiě)就是因?yàn)殒湵硎俏覀儎?dòng)態(tài)開(kāi)辟的，而每一個(gè)節(jié)點(diǎn)的位置并不是相連的，next成員指針的意義也就是下一個(gè)節(jié)點(diǎn)的內(nèi)存地址。
到這里整個(gè)創(chuàng)建函數(shù)的設(shè)計(jì)思路也都說(shuō)完了，筆者不一定說(shuō)的很好，但基本思路是這樣的，希望讀者多思考，多對(duì)比，相信此教程還是對(duì)大家有幫助的，程序設(shè)計(jì)就是利用逐步思考的方式進(jìn)行的，寫(xiě)好的代碼往往直接看看不懂就是因?yàn)橹虚g的細(xì)節(jié)并不是一次都能夠想到的。
下面我們來(lái)說(shuō)一下鏈表節(jié)點(diǎn)的刪除!
我們以上面的程序?yàn)榛A(chǔ)，但為了我們方便學(xué)習(xí)刪除我們休整結(jié)構(gòu)體為
struct test
{
int number;
float socre;
test *next;
};
number為唯一的編號(hào)每一個(gè)節(jié)點(diǎn)的。
刪除的我就不多說(shuō)了，里面重要部分有注解。
特別注意deletel函數(shù)的參數(shù)意義，指針的引用在這里很重要，如果只是指針，或者只是應(yīng)用都是不行的，為什么仔細(xì)思考，很多知名的教材在這一問(wèn)題上都很模糊，而且很多書(shū)還有錯(cuò)誤，程序不錯(cuò)，但思路是錯(cuò)的，我這里特別不說(shuō)，請(qǐng)大家仔細(xì)閱讀程序，如果還是有問(wèn)題，可以回此帖，我會(huì)回答的。
完整代碼如下：
struct test
{
int number;
float socre;
test *next;
};
最后我學(xué)習(xí)一下如何在已有的鏈表上插入節(jié)點(diǎn)
我們要考慮四中情況,
1.鏈表為空!
2.插入點(diǎn)在首節(jié)點(diǎn)前
3.插入點(diǎn)找不到的情況我們?cè)O(shè)置放在最后!
4.插入點(diǎn)在中間的情況!
今天的程序在昨天的基礎(chǔ)上做了進(jìn)一步的修改,可以避免刪除點(diǎn)找不到的情況,如果找不到刪除點(diǎn)就退出函數(shù)!
代碼入下:重點(diǎn)部分我有了詳細(xì)的注解,插入函數(shù)名為insterl()
//程序作者:管寧
//站點(diǎn):www.cndev-lab.com
//所有稿件均有版權(quán),如要轉(zhuǎn)載,請(qǐng)務(wù)必著名出處和作者
#include <iostream>
using namespace std;
struct test
{
int number;
float socre;
test *next;
};
test *head;//創(chuàng)建一個(gè)全局的引導(dǎo)進(jìn)入鏈表的指針
test *create()
{
test *ls;//節(jié)點(diǎn)指針
test *le;//鏈尾指針
ls = new test;//把ls指向動(dòng)態(tài)開(kāi)辟的堆內(nèi)存地址
cout<<"請(qǐng)輸入第一個(gè)節(jié)點(diǎn)number和節(jié)點(diǎn)score,輸入0.0跳出函數(shù)"<<endl;
cin>>ls->number>>ls->socre;
head=NULL;//進(jìn)入的時(shí)候先不設(shè)置head指針指向任何地址,因?yàn)椴恢朗欠褚簧蟻?lái)就輸入null跳出程序
le=ls;//把鏈尾指針設(shè)置成剛剛動(dòng)態(tài)開(kāi)辟的堆內(nèi)存地址,用于等下設(shè)置le->next,也就是下一個(gè)節(jié)點(diǎn)的位置
while(ls->number!=0)//創(chuàng)建循環(huán)條件為ls->number的值不是null,用于循環(huán)添加節(jié)點(diǎn)
{
if(head==NULL)//判斷是否是第一次進(jìn)入循環(huán)
{
head=ls;//如果是第一次進(jìn)入循環(huán),那么把引導(dǎo)進(jìn)入鏈表的指針指向第一次動(dòng)態(tài)開(kāi)辟的堆內(nèi)存地址
}
else
{
le->next=ls;//如果不是第一次進(jìn)入那么就把上一次的鏈尾指針的le->next指向上一次循環(huán)結(jié)束前動(dòng)態(tài)創(chuàng)建的堆內(nèi)存地址
}
le=ls;//設(shè)置鏈尾指針為當(dāng)前循環(huán)中的節(jié)點(diǎn)指針,用于下一次進(jìn)入循環(huán)的時(shí)候把上一次的節(jié)點(diǎn)的next指向上一次循環(huán)結(jié)束前動(dòng)態(tài)創(chuàng)建的堆內(nèi)存地址
ls=new test;//為下一個(gè)節(jié)點(diǎn)在堆內(nèi)存中動(dòng)態(tài)開(kāi)辟空間
cout<<"請(qǐng)下一個(gè)節(jié)點(diǎn)number和節(jié)點(diǎn)score,輸入0.0跳出函數(shù)"<<endl;
cin>>ls->number>>ls->socre;
}
le->next=NULL;//把鏈尾指針的next設(shè)置為空,因?yàn)椴还苋绾窝h(huán)總是要結(jié)束的,設(shè)置為空才能夠在循環(huán)顯鏈表的時(shí)候不至于死循環(huán)
delete ls;//當(dāng)結(jié)束的時(shí)候最后一個(gè)動(dòng)態(tài)開(kāi)辟的內(nèi)存是無(wú)效的,所以必須清除掉
return head;//返回鏈?zhǔn)字羔?nbsp;
}
void showl(test *head)
{
cout<<"鏈?zhǔn)字羔?"<<head<<endl;
while(head)//以內(nèi)存指向?yàn)閚ull為條件循環(huán)顯示先前輸入的內(nèi)容
{
cout<<head->number<<"|"<<head->socre<<endl;
head=head->next;
}
}
void deletel(test *&head,int number)//這里如果參數(shù)換成test *head,意義就完全不同了,head變成了復(fù)制而不是原有鏈上操作了,特別注意,很多書(shū)上都不對(duì)這里
{
test *point;//判斷鏈表是否為空
if(head==NULL)
{
cout<<"鏈表為空,不能進(jìn)行刪除工作!";
return;
}
int derror=1;//設(shè)置找不到的情況的條件,預(yù)先設(shè)置為真
test *check=head;
while(check)//利用循環(huán)進(jìn)行查找
{
if (check->number==number)
{
derror=0;//條件轉(zhuǎn)為假
}
check=check->next;
}
if(derror)//如果為假就跳出函數(shù)
{
return;
}
if(head->number==number)//判刪除的節(jié)點(diǎn)是否為首節(jié)點(diǎn)
{
point=head;
cout<<"刪除點(diǎn)是鏈表第一個(gè)節(jié)點(diǎn)位置!";
head=head->next;//重新設(shè)置引導(dǎo)指針
delete point;
return;
}
test *fp=head;//保存連首指針
for(test *&mp=head;mp->next;mp=mp->next)
{
if(mp->next->number==number)
{
point=mp->next;
mp->next=point->next;
delete point;
head=fp;//由于head的不斷移動(dòng)丟失了head,把進(jìn)入循環(huán)前的head指針恢復(fù)!
return;
}
}
}
void insterl(int number)
{
test *point=new test;
cout<<"請(qǐng)輸入節(jié)點(diǎn)number和節(jié)點(diǎn)score"<<endl;
cin>>point->number>>point->socre;
if(head==NULL)//鏈表為空的情況下插入
{
head=point;
point->next=NULL;
return;
}
int ierror=1;//設(shè)置找不到的情況的條件,預(yù)先設(shè)置為真
test *le;
test *check=head;
while(check)//利用循環(huán)進(jìn)行查找
{
if (check->number==number)
{
ierror=0;//條件轉(zhuǎn)為假
}
le=check;
check=check->next;
}
if(ierror)
{
cout<<le->number;
le->next=point;
point->next=NULL;
return;
}
if(head->number==number)//檢測(cè)是否是在第一個(gè)節(jié)點(diǎn)處插入
{
point->next=head;
head=point;
return;
}
for(test *&mp=head;mp->next;mp=mp->next)//在鏈表中間插入
{
if(mp->next->number==number)
{
point->next=mp->next;
mp->next=point;
return;
}
}
}
void main()
{
head=create();//調(diào)用創(chuàng)建
showl(head);
int dp;
cout<<"請(qǐng)輸入刪除點(diǎn)如果找不到就跳出函數(shù)"<<endl;
cin>>dp;
deletel(head,dp);//調(diào)用刪除
showl(head);
int ip;
cout<<"請(qǐng)輸入插入點(diǎn)如果找不到就在鏈尾添加"<<endl;
cin>>ip;
insterl(ip);
showl(head);
cin.get();
cin.get();
}
到此關(guān)于結(jié)構(gòu)體的內(nèi)容已經(jīng)全部討論結(jié)束，鏈表的建立刪除插入操作可以很好的對(duì)前面所學(xué)知識(shí)進(jìn)行一個(gè)總結(jié)，它既考察了程序員對(duì)內(nèi)存大理解(堆內(nèi)存操作、指針操作)也考察了對(duì)結(jié)構(gòu)化編程掌握的熟悉程序。