c/c++中結構體(struct)知識點強化,鏈表的學習

在上一個教程中我們已經簡單的闡述了什麼是結構體了，為了進一部的學習結構體這一重要的知識點，我們今天來學習一下鏈表結構。
　　
　　 <!-- frame contents --> <!-- /frame contents --> 結構體可以看做是一種自定義的數據類型，它還有一個很重要的特性，就是結構體可以相互嵌套使用，但也是有條件的，結構體可以包含結構體指針，但絕對不能在結構體中包含結構體變量。
　　
　　strUCt test
　　{
　　char name[10];
　　float socre;
　　test *next;
　　};//這樣是正確的!
　　
　　
　　struct test
　　{
　　char name[10];
　　float socre;
　　test next;
　　};//這樣是錯誤的!
　　
　　
　　利用結構體的這點非凡特性，我們就可以自己生成一個環環相套的一種射線結構，一個指向另一個。
　　
　　鏈表的學習不像想象的那麼那麼輕易，很多人學習到這裡的時候都會碰到困難，很多人也因此而放棄了學習，在這裡我說,一定不能放棄，對應它的學習我們要進行分解式學習，方法很重要，理解需要時間，不必要把自己逼迫的那麼緊，學習前你也得做一些最基本的預備工作，你必須具備對堆內存的基本知識的了解，還有就是對結構體的基本熟悉，有了這兩個重要的條件，再進行分解式學習就可以比較輕松的把握這一節內容的難點。
　　
　　下面我們給出一個完整的創建鏈表的程序，不管看的懂看不懂希望讀者先認真看一下，想一想，看不懂沒有關系，因為我下面會有分解式的教程，但之前的基本思考一定要做，要不即使我分解了你也是無從理解的。
　　
　　代碼如下，我在重要部分做了注解：
　　
　　
　　//程序作者:管寧
　　//站點:www.cndev-lab.com
　　//所有稿件均有版權,如要轉載,請務必聞名出處和作者
　　
　　#include <iostream>
　　using namespace std;
　　
　　struct test
　　{
　　char name[10];
　　float socre;
　　test *next;
　　};
　　
　　test *head;//創建一個全局的引導進入鏈表的指針
　　
　　test *create()
　　{
　　test *ls;//節點指針
　　test *le;//鏈尾指針
　　ls = new test;//把ls指向動態開辟的堆內存地址
　　cin>>ls->name>>ls->socre;
　　head=NULL;//進入的時候先不設置head指針指向任何地址,因為不知道是否一上來就輸入null跳出程序
　　le=ls;//把鏈尾指針設置成剛剛動態開辟的堆內存地址,用於等下設置le->next,也就是下一個節點的位置
　　
　　while(strcmp(ls->name,"null")!=0)//創建循環條件為ls->name的值不是null,用於循環添加節點
　　{
　　if(head==NULL)//判定是否是第一次進入循環
　　{
　　head=ls;//假如是第一次進入循環,那麼把引導進入鏈表的指針指向第一次動態開辟的堆內存地址
　　}
　　else
　　{
　　le->next=ls;//假如不是第一次進入那麼就把上一次的鏈尾指針的le->next指向上一次循環結束前動態創建的堆內存地址
　　}
　　le=ls;//設置鏈尾指針為當前循環中的節點指針,用於下一次進入循環的時候把上一次的節點的next指向上一次循環結束前動態創建的堆內存地址
　　ls=new test;//為下一個節點在堆內存中動態開辟空間
　　cin>>ls->name>>ls->socre;
　　}
　　
　　le->next=NULL;//把鏈尾指針的next設置為空,因為不管如何循環總是要結束的,設置為空才能夠在循環顯鏈表的時候不至於死循環
　　delete ls;//當結束的時候最後一個動態開辟的內存是無效的,所以必須清除掉
　　return head;//返回鏈首指針
　　}
　　
　　void showl(test *head)
　　{
　　cout<<"鏈首指針:"<<head<<endl;
　　while(head)//以內存指向為null為條件循環顯示先前輸入的內容
　　{
　　cout<<head->name<<""<<head->socre<<endl;
　　head=head->next;
　　}
　　}
　　
　　void main()
　　{
　　showl(create());
　　cin.get();
　　cin.get();
　　}
　　 更多內容請看C/C++技術專題  電腦知識專題，或
　　   上面的代碼我們是要達到一個目的：就是要存儲你輸入的人名和他們的得分，並且以鏈狀結構把它們組合成一個鏈狀結構。
　　
　　程序種有兩個組成部分
　　
　　test *create()
　　
　　和
　　
　　void showl(test *head)
　　
　　 <!-- frame contents --> <!-- /frame contents --> 這兩個函數，create是用來創建鏈表的 ，showl是用來顯示鏈表的。
　　
　　create函數的返回類型是一個結構體指針，在程序調用的時候我們用了showl(create());，而不用引用的目的原因是引導指針是一個全局指針變量，我們不能在showl()內改變它，因為showl()函數內有一個移動操作head=head->next;，假如是引用的話我們就破壞了head指針的位置，以至於我們再也無法找會首地址的位置了。
　　
　　下面我們來分解整個程序，以一個初學者的思想來思考整個程序，由淺入深的逐步解釋。
　　
　　首先，我們寫這個程序，要考慮到由於是一個鏈表結構，我們不可能知道它的大小到底是多大，這個問題我們可以用動態開辟堆內存來解決，因為堆內存在程序結束前始終是有效的，不受函數棧空間生命期的限制，但要注重的是我們必須有一個指針變量來存儲這一鏈狀結構的進入地址，而在函數內部來建立這一指針變量顯然是不合適的，因為函數一旦退出，這個指針變量也隨之失效，所以我們在程序的開始聲明了一個全局指針變量。
　　
　　test *head;//創建一個全局的引導進入鏈表的指針
　　
　　
　　好解決了這兩個問題，我們接下去思考
　　
　　有輸入就必然有輸出，由於輸出函數和輸入函數是相對獨立的，為了不斷測試程序的正確性好調試我們先寫好輸出函數和main函數捏的調用，創建函數我們先約定好名為create。
　　
　　我們先寫出如下的代碼：
　　
　　
　　//程序作者:管寧
　　//站點:www.cndev-lab.com
　　//所有稿件均有版權,如要轉載,請務必聞名出處和作者
　　
　　#include <iostream>
　　using namespace std;
　　
　　struct test
　　{
　　char name[10];
　　float socre;
　　test *next;
　　};
　　
　　test *head;//創建一個全局的引導進入鏈表的指針
　　
　　test *create()
　　{
　　
　　return head;//返回鏈首指針
　　}
　　
　　void showl(test *head)
　　{
　　cout<<"鏈首指針:"<<head<<endl;
　　while(head)//以內存指向為null為條件循環顯示先前輸入的內容
　　{
　　cout<<head->name<<""<<head->socre<<endl;
　　head=head->next;
　　}
　　}
　　
　　void main()
　　{
　　showl(create());
　　cin.get();
　　cin.get();
　　}
　　
　　
　　程序寫到這裡，基本形態已經出來，輸入和調用我們已經有了。 更多內容請看C/C++技術專題  電腦知識專題，或 下面我們來解決輸入問題，鏈表的實現我們是通過循環輸入來實現的，既然是循環我們就一定得考慮終止循環的條件，避免死循環和無效循環的發生。
　　
　　在create()函數內部我們先寫成這樣：
　　
　　 <!-- frame contents --> <!-- /frame contents --> test *create()
　　{
　　test *ls;//節點指針
　　test *le;//鏈尾指針
　　ls = new test;//把ls指向動態開辟的堆內存地址
　　cin>>ls->name>>ls->socre;
　　head=NULL;//進入的時候先不設置head指針指向任何地址,因為不知道是否一上來就輸入null跳出程序
　　le=ls;//把鏈尾指針設置成剛剛動態開辟的堆內存地址,用於等下設置le->next,也就是下一個節點的位置
　　
　　
　　le->next=NULL;//把鏈尾指針的next設置為空,因為不管如何循環總是要結束的,設置為空才能夠在循環顯鏈表的時候不至於死循環
　　delete ls;//當結束的時候最後一個動態開辟的內存是無效的,所以必須清除掉
　　return head;//返回鏈首指針
　　}
　　
　　
　　在循環創建之前我們必須考慮一個都不輸入的情況。
　　
　　程序一單進入create函數我們首先必然要創建一個節點，我們先創建一個節點指針，後把者個節點指針指向到動態開辟的test類型的動態內存地址位置上。
　　
　　所以我們有了
　　
　　test *ls;
　　ls = new test;
　　
　　
　　
　　程序既然是循環輸入，而結構成員test *next又是用來存儲下一個接點的內存地址的，每次循環我們又要動態創建一個新的內存空間，所以我們必須要有一個指針來存儲上一次循環動態開辟的內存地址，於是就有了
　　test *le;
　　接下來在進入循環前我們要創建鏈表的第一個節點，第一個節點必然是在循環外創建，於是就有了
　　
　　cin>>ls->name>>ls->socre;
　　
　　程序執行者的情況是位置的，所以我們必然要考慮，一上來就不想繼續運行程序的情況，所以我們一開始先把head引導指針設置為不指向任何地址也就是
　　head=NULL;
　　
　　為了符合le也就是鏈尾指針的設計思路，我們在循環前一定要保存剛剛動態開辟的內存地址，好在下一次循環的時候設置上一個節點中的next成員指向，於是我們便有了：
　　
　　le=ls;
　　為了實現循環輸入我們又了下面的代碼：
　　
　　while(strcmp(ls->name,"null")!=0)
　　{
　　if(head==NULL)
　　{
　　head=ls;
　　}
　　else
　　{
　　le->next=ls;
　　}
　　le=ls;
　　ls=new test;
　　cin>>ls->name>>ls->socre;
　　}
　　
　　程序是循環必然要有終止循環的條件，所以我們的循環條件是：
　　
　　while(strcmp(ls->name,"null")!=0)
　　
　　輸入的名字是null的時候就停止循環。
　　
　　為了保證第一次進入循環，也就是在循環內預備創建第二個節點前，設置引導指針的指向我們有了如下的判定代碼：
　　
　　if(head==NULL)
　　{
　　head=ls;
　　}
　　else
　　{
　　le->next=ls;
　　}
　　代碼中的else條件是為了設置前一個節點next指向而寫的,這點我們記住先看下面的代碼,稍後大家回過頭想就明白了
　　
　　le=ls;
　　ls=new test;
　　cin>>ls->name>>ls->socre;
　　
　　le=ls;這麼寫就是為了保存上一次循環指針的位置而設的,正是為了上面的else代碼而做的預先保留
　　
　　ls=new test;
　　cin>>ls->name>>ls->socre;
　　這兩行代碼的意思就是繼續開辟下一個節點空間,和輸入節點內容!
　　
　　循環一旦結束也就結束了程序,為了保持程序不出錯,也就是最後一個節點的next成員指向為空我們有了下面的代碼
　　
　　le->next=NULL;
　　
　　程序的思路始終是以先開辟後判定為思路的,所以到最後一個不成立的時候總會有一個多開辟的內存空間,為了刪除掉它,我們有了下面的代碼
　　
　　delete ls;
　　
　　程序到最後由於返回head指針
　　
　　return head;
　　
　　顯示鏈表的函數沒有什麼太多非凡的也只需要注重下面這樣就可以了！
　　
　　head=head->next;
　　
　　我們之所以不用head+=1;來寫就是因為鏈表是我們動態開辟的，而每一個節點的位置並不是相連的，next成員指針的意義也就是下一個節點的內存地址。 更多內容請看C/C++技術專題  電腦知識專題，或
　　到這裡整個創建函數的設計思路也都說完了，筆者不一定說的很好，但基本思路是這樣的，希望讀者多思考，多對比，相信此教程還是對大家有幫助的，程序設計就是利用逐步思考的方式進行的，寫好的代碼往往直接看看不懂就是因為中間的細節並不是一次都能夠想到的。
　　 <!-- frame contents --> <!-- /frame contents --> 下面我們來說一下鏈表節點的刪除!
　　
　　我們以上面的程序為基礎，但為了我們方便學習刪除我們休整結構體為
　　
　　struct test
　　{
　　int number;
　　float socre;
　　test *next;
　　};
　　
　　number為唯一的編號每一個節點的。
　　
　　刪除的我就不多說了，裡面重要部分有注解。
　　
　　非凡注重deletel函數的參數意義，指針的引用在這裡很重要，假如只是指針，或者只是應用都是不行的，為什麼仔細思考，很多知名的教材在這一問題上都很模糊，而且很多書還有錯誤，程序不錯，但思路是錯的，我這裡非凡不說，請大家仔細閱讀程序，假如還是有問題，可以回此帖，我會回答的。
　　
　　完整代碼如下：
　　
　　
　　//程序作者:管寧
　　//站點:www.cndev-lab.com
　　//所有稿件均有版權,如要轉載,請務必聞名出處和作者
　　
　　#include <iostream>
　　using namespace std;
　　struct test
　　{
　　int number;
　　float socre;
　　test *next;
　　};
　　test *head;//創建一個全局的引導進入鏈表的指針
　　
　　test *create()
　　{
　　test *ls;//節點指針
　　test *le;//鏈尾指針
　　ls = new test;//把ls指向動態開辟的堆內存地址
　　cin>>ls->number>>ls->socre;
　　head=NULL;//進入的時候先不設置head指針指向任何地址,因為不知道是否一上來就輸入null跳出程序
　　le=ls;//把鏈尾指針設置成剛剛動態開辟的堆內存地址,用於等下設置le->next,也就是下一個節點的位置
　　while(ls->number!=0)//創建循環條件為ls->number的值不是null,用於循環添加節點
　　{
　　if(head==NULL)//判定是否是第一次進入循環
　　{
　　head=ls;//假如是第一次進入循環,那麼把引導進入鏈表的指針指向第一次動態開辟的堆內存地址
　　}
　　else
　　{
　　le->next=ls;//假如不是第一次進入那麼就把上一次的鏈尾指針的le->next指向上一次循環結束前動態創建的堆內存地址
　　}
　　le=ls;//設置鏈尾指針為當前循環中的節點指針,用於下一次進入循環的時候把上一次的節點的next指向上一次循環結束前動態創建的堆內存地址
　　ls=new test;//為下一個節點在堆內存中動態開辟空間
　　cin>>ls->number>>ls->socre;
　　}
　　le->next=NULL;//把鏈尾指針的next設置為空,因為不管如何循環總是要結束的,設置為空才能夠在循環顯鏈表的時候不至於死循環
　　delete ls;//當結束的時候最後一個動態開辟的內存是無效的,所以必須清除掉
　　return head;//返回鏈首指針
　　}
　　void showl(test *head)
　　{
　　cout<<"鏈首指針:"<<head<<endl;
　　while(head)//以內存指向為null為條件循環顯示先前輸入的內容
　　{
　　cout<<head->number<<""<<head->socre<<endl;
　　head=head->next;
　　}
　　}
　　void deletel(test *&head,int number)//這裡假如參數換成test *head,意義就完全不同了,head變成了復制而不是原有鏈上操作了,非凡注重,很多書上都不對這裡
　　{
　　test *point;//判定鏈表是否為空
　　if(head==NULL)
　　{
　　cout<<"鏈表為空,不能進行刪除工作!";
　　return;
　　}
　　if(head->number==number)//判刪除的節點是否為首節點
　　{
　　point=head;
　　cout<<"刪除點是鏈表第一個節點位置!";
　　head=head->next;//重新設置引導指針
　　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的不斷移動丟失了head,把進入循環前的head指針恢復!
　　return;
　　}
　　}
　　}
　　void main()
　　{
　　head=create();//調用創建
　　showl(head);
　　int dp;
　　cin>>dp;
　　deletel(head,dp);//調用刪除
　　showl(head);
　　cin.get();
　　cin.get();
　　}
　　 更多內容請看C/C++技術專題  電腦知識專題，或
　　最後我學習一下如何在已有的鏈表上插入節點
　　
　　我們要考慮四中情況,
　　
　　1.鏈表為空!
　　
　　2.插入點在首節點前
　　
　　3.插入點找不到的情況我們設置放在最後!
　　
　　4.插入點在中間的情況!
　　
　　 <!-- frame contents --> <!-- /frame contents --> 今天的程序在昨天的基礎上做了進一步的修改,可以避免刪除點找不到的情況,假如找不到刪除點就退出函數!
　　
　　代碼入下:重點部分我有了具體的注解,插入函數名為insterl()
　　
　　
　　//程序作者:管寧
　　//站點:www.cndev-lab.com
　　//所有稿件均有版權,如要轉載,請務必聞名出處和作者
　　
　　#include <iostream>
　　using namespace std;
　　struct test
　　{
　　int number;
　　float socre;
　　test *next;
　　};
　　test *head;//創建一個全局的引導進入鏈表的指針
　　
　　test *create()
　　{
　　test *ls;//節點指針
　　test *le;//鏈尾指針
　　ls = new test;//把ls指向動態開辟的堆內存地址
　　cout<<"請輸入第一個節點number和節點score,輸入0.0跳出函數"<<endl;
　　cin>>ls->number>>ls->socre;
　　head=NULL;//進入的時候先不設置head指針指向任何地址,因為不知道是否一上來就輸入null跳出程序
　　le=ls;//把鏈尾指針設置成剛剛動態開辟的堆內存地址,用於等下設置le->next,也就是下一個節點的位置
　　while(ls->number!=0)//創建循環條件為ls->number的值不是null,用於循環添加節點
　　{
　　if(head==NULL)//判定是否是第一次進入循環
　　{
　　head=ls;//假如是第一次進入循環,那麼把引導進入鏈表的指針指向第一次動態開辟的堆內存地址
　　}
　　else
　　{
　　le->next=ls;//假如不是第一次進入那麼就把上一次的鏈尾指針的le->next指向上一次循環結束前動態創建的堆內存地址
　　}
　　le=ls;//設置鏈尾指針為當前循環中的節點指針,用於下一次進入循環的時候把上一次的節點的next指向上一次循環結束前動態創建的堆內存地址
　　ls=new test;//為下一個節點在堆內存中動態開辟空間
　　cout<<"請下一個節點number和節點score,輸入0.0跳出函數"<<endl;
　　cin>>ls->number>>ls->socre;
　　}
　　le->next=NULL;//把鏈尾指針的next設置為空,因為不管如何循環總是要結束的,設置為空才能夠在循環顯鏈表的時候不至於死循環
　　delete ls;//當結束的時候最後一個動態開辟的內存是無效的,所以必須清除掉
　　return head;//返回鏈首指針
　　}
　　void showl(test *head)
　　{
　　cout<<"鏈首指針:"<<head<<endl;
　　while(head)//以內存指向為null為條件循環顯示先前輸入的內容
　　{
　　cout<<head->number<<""<<head->socre<<endl;
　　head=head->next;
　　}
　　}
　　void deletel(test *&head,int number)//這裡假如參數換成test *head,意義就完全不同了,head變成了復制而不是原有鏈上操作了,非凡注重,很多書上都不對這裡
　　{
　　test *point;//判定鏈表是否為空
　　if(head==NULL)
　　{
　　cout<<"鏈表為空,不能進行刪除工作!";
　　return;
　　}
　　
　　int derror=1;//設置找不到的情況的條件,預先設置為真
　　test *check=head;
　　while(check)//利用循環進行查找
　　{
　　if (check->number==number)
　　{
　　derror=0;//條件轉為假
　　}
　　check=check->next;
　　}
　　if(derror)//假如為假就跳出函數
　　{
　　return;
　　}
　　
　　if(head->number==number)//判刪除的節點是否為首節點
　　{
　　point=head;
　　cout<<"刪除點是鏈表第一個節點位置!";
　　head=head->next;//重新設置引導指針
　　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的不斷移動丟失了head,把進入循環前的head指針恢復!
　　return;
　　}
　　}
　　}
　　
　　void insterl(int number)
　　{
　　test *point=new test;
　　cout<<"請輸入節點number和節點score"<<endl;
　　cin>>point->number>>point->socre;
　　
　　if(head==NULL)//鏈表為空的情況下插入
　　{
　　head=point;
　　point->next=NULL;
　　return;
　　}
　　
　　int ierror=1;//設置找不到的情況的條件,預先設置為真
　　test *le;
　　test *check=head;
　　while(check)//利用循環進行查找
　　{
　　if (check->number==number)
　　{
　　ierror=0;//條件轉為假
　　}
　　le=check;
　　check=check->next;
　　}
　　if(ierror)
　　{
　　cout<<le->number;
　　le->next=point;
　　point->next=NULL;
　　return;
　　}
　　
　　if(head->number==number)//檢測是否是在第一個節點處插入
　　{
　　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();//調用創建
　　showl(head);
　　int dp;
　　cout<<"請輸入刪除點假如找不到就跳出函數"<<endl;
　　cin>>dp;
　　deletel(head,dp);//調用刪除
　　showl(head);
　　int ip;
　　cout<<"請輸入插入點假如找不到就在鏈尾添加"<<endl;
　　cin>>ip;
　　insterl(ip);
　　showl(head);
　　cin.get();
　　cin.get();
　　}
　　
　　 到此關於結構體的內容已經全部討論結束，鏈表的建立刪除插入操作可以很好的對前面所學知識進行一個總結，它既考察了程序員對內存大理解(堆內存操作、指針操作)也考察了對結構化編程把握的熟悉程序。
　　
　　以後的教程我們將著重練習面向對象的編程的相關知識點。 更多內容請看C/C++技術專題  電腦知識專題，或