《C++程序設(shè)計：第六章 結(jié)構(gòu)和鏈表》由會員分享，可在線閱讀，更多相關(guān)《C++程序設(shè)計：第六章 結(jié)構(gòu)和鏈表（43頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、第六章第六章 結(jié)構(gòu)和鏈表結(jié)構(gòu)和鏈表6 6.1.1 結(jié)構(gòu)類型結(jié)構(gòu)類型6 6.2.2 結(jié)構(gòu)的應(yīng)用結(jié)構(gòu)的應(yīng)用-鏈表鏈表6 6.3.3 應(yīng)用舉例應(yīng)用舉例現(xiàn)實生活中的數(shù)據(jù)現(xiàn)實生活中的數(shù)據(jù)學(xué)生信息學(xué)生信息學(xué)號姓名性別成績1150001張小兵男90.351150002李楠女92.13校園一卡通校園一卡通卡號余額身份1150001200學(xué)生99088150教師.將不同類型的數(shù)據(jù)組合成一個有機的整體將不同類型的數(shù)據(jù)組合成一個有機的整體結(jié)構(gòu)體結(jié)構(gòu)體6.1 6.1 結(jié)構(gòu)類型結(jié)構(gòu)類型 6.1.1 結(jié)構(gòu)類型說明結(jié)構(gòu)類型說明說明結(jié)說明結(jié)構(gòu)類型構(gòu)類型的關(guān)鍵字的關(guān)鍵字 struct 結(jié)構(gòu)類型標(biāo)識符結(jié)構(gòu)類型標(biāo)識符 結(jié)構(gòu)成員結(jié)構(gòu)

2、成員1;1;結(jié)構(gòu)成員結(jié)構(gòu)成員2;2;結(jié)構(gòu)成員結(jié)構(gòu)成員n;n;類型可任意類型可任意（不能為該結(jié)構(gòu)自身）（不能為該結(jié)構(gòu)自身）C語言提供了這樣一種數(shù)據(jù)結(jié)構(gòu)：它將不同類型的數(shù)據(jù)組合成一個有機的整體結(jié)構(gòu)體。struct date int month;int day;int year;struct man char name15;char sex;int age;date birthday;如，說明一個結(jié)構(gòu)類型如，說明一個結(jié)構(gòu)類型datedate，含三個整型數(shù)據(jù)成員含三個整型數(shù)據(jù)成員在此基礎(chǔ)上，又在此基礎(chǔ)上，又可說明另一個結(jié)可說明另一個結(jié)構(gòu)類型構(gòu)類型manmanbirthdayNamesexagemont

3、hdayyear struct man結(jié)構(gòu)類型6.1.2 6.1.2 結(jié)構(gòu)變量定義及初始化結(jié)構(gòu)變量定義及初始化先說明結(jié)構(gòu)類型再定義結(jié)構(gòu)變量先說明結(jié)構(gòu)類型再定義結(jié)構(gòu)變量在說明結(jié)構(gòu)數(shù)據(jù)類型的同時定義結(jié)構(gòu)變量在說明結(jié)構(gòu)數(shù)據(jù)類型的同時定義結(jié)構(gòu)變量省略結(jié)構(gòu)標(biāo)識符直接定義結(jié)構(gòu)類型變量省略結(jié)構(gòu)標(biāo)識符直接定義結(jié)構(gòu)類型變量struct man man1,man2;struct man char name15;char sex;int age;struct date birthday;man1,man2;struct char name15;char sex;int age;struct date birthda

4、y;man1,man2;無無類型名變量類型名變量 struct goods /定義一個商品結(jié)構(gòu)類型定義一個商品結(jié)構(gòu)類型 char bh6;/商品編號商品編號 char mc20;/商品名稱商品名稱 float dj;/商品單價商品單價 int sl;/商品數(shù)量商品數(shù)量 char jhrq8;/進貨日期進貨日期g1=10012,shoes,124,100,080912；結(jié)構(gòu)變量也允許在定義的同時給出初值，即初始化。如：struct person char name15;char sex;int age;s10=Fang Min,F,24,Fang Hua,M,35;定義一個結(jié)構(gòu)數(shù)組并對其部分元素

5、初始化。定義一個結(jié)構(gòu)數(shù)組并對其部分元素初始化。6.1.3 6.1.3 結(jié)構(gòu)變量的訪問結(jié)構(gòu)變量的訪問訪問形式：訪問形式：結(jié)構(gòu)變量名結(jié)構(gòu)變量名.成員名成員名(*(*指向結(jié)構(gòu)的指針指向結(jié)構(gòu)的指針).).成員名成員名 指向結(jié)構(gòu)的指針指向結(jié)構(gòu)的指針-成員名成員名或或或或通過指向結(jié)構(gòu)的指針引用結(jié)構(gòu)變量成員通過指向結(jié)構(gòu)的指針引用結(jié)構(gòu)變量成員成員訪問運算符成員訪問運算符優(yōu)先級最高的優(yōu)先級最高的四個運算符之一四個運算符之一 括號不能少括號不能少如，假設(shè)有定義如，假設(shè)有定義man m,*p=&m;strcpy(m.name,Fang Min);p-birthday.month=8;則可則可如下引用結(jié)構(gòu)成員如下引用

6、結(jié)構(gòu)成員【例6.1】某某商商場場周周年年店店慶慶期期間間對對其其會會員員進進行行積積分分換換購購活活動動，活活動動內(nèi)內(nèi)容容為為允允許許每每天天前前五五名名光光臨臨的的會會員員用用其其積積分分換換購購相相應(yīng)應(yīng)的的商商品品，假假設(shè)設(shè)每每100100個個積積分分可可以以換換購購5 5元元的的商商品品，編編程程序序求求該該商商場場店店慶慶期期間間每每天天換換購購出出去去的的商商品品金金額額以以及及會會員員換換購購后后的的剩剩余余積積分分值值。假假設(shè)設(shè)會會員員將將全全部部可能積分全部進行換購?？赡芊e分全部進行換購。分分析析：可可以以將將會會員員卡卡號號和和積積分分組組合合在在一一起起定定義義一一個個結(jié)結(jié)

7、構(gòu)構(gòu)類類型型，用用結(jié)結(jié)構(gòu)數(shù)組來描述若干會員的信息。如構(gòu)數(shù)組來描述若干會員的信息。如，struct card char num10;int score;c10;#include iostream.h#define N 5void main()struct card char num10;int score;cN;int i,s=0;for(i=0;ici.numci.score;s=s+5*(ci.score/100);/每每100100分換購分換購5 5元商品元商品 ci.score=ci.score-100*(ci.score/100);/該會員的剩余積分該會員的剩余積分 cout扣除積分后

8、扣除積分后:n;for(i=0;iN;i+)coutci.numtci.scoreendl;cout積分換購金額積分換購金額=sdata=10;q=new node;q-data=20;NULLq-next=NULLp-next=q;6.2.2 6.2.2 鏈表的建立鏈表的建立【例例6.36.3】創(chuàng)建一個含有創(chuàng)建一個含有n n個結(jié)點的、包含一個數(shù)據(jù)域，且其類型個結(jié)點的、包含一個數(shù)據(jù)域，且其類型為整型的單鏈表。為整型的單鏈表。鏈表的建立過程如下：鏈表的建立過程如下：首先設(shè)置首先設(shè)置headhead為為NULLNULL，即建立一個空的鏈表。，即建立一個空的鏈表。申請一個新結(jié)點存儲區(qū)域，讓申請一個新

9、結(jié)點存儲區(qū)域，讓newnodenewnode指向該結(jié)點，然后向其數(shù)指向該結(jié)點，然后向其數(shù)據(jù)域輸入數(shù)據(jù)。據(jù)域輸入數(shù)據(jù)。把把newnodenewnode所指向的結(jié)點插入到鏈表中。所指向的結(jié)點插入到鏈表中。如果當(dāng)前鏈表是空表，如果當(dāng)前鏈表是空表，newnodenewnode所指向的結(jié)點應(yīng)該成為該鏈所指向的結(jié)點應(yīng)該成為該鏈表中唯一的一個結(jié)點，故表中唯一的一個結(jié)點，故headhead和和tailtail都應(yīng)該指向該結(jié)點。都應(yīng)該指向該結(jié)點。如果當(dāng)前鏈表非空，則如果當(dāng)前鏈表非空，則newnodenewnode所指向的結(jié)點應(yīng)該做為鏈所指向的結(jié)點應(yīng)該做為鏈表中的最后一個結(jié)點加入到鏈表中，故應(yīng)該將其插在表中的最后

10、一個結(jié)點加入到鏈表中，故應(yīng)該將其插在tailtail指指向的結(jié)點后面。向的結(jié)點后面。重復(fù)執(zhí)行第重復(fù)執(zhí)行第2 2、3 3步共步共n n次。次。將最后一個結(jié)點的將最后一個結(jié)點的nextnext域置空域置空(NULL)(NULL)。#include iostream.hstruct node int data;struct node *next;struct node *create(int n)struct node *head=NULL;struct node *tail,*newnode;int x;for(int i=0;ix;newnode=;/為為newnodenewnode申請存放空間

11、申請存放空間newnode-data=x;new node也可用如下語句也可用如下語句newnode=(struct node*)malloc(sizeof(struct node);if(head=NULL);/newnodenewnode成為空表的第一個結(jié)點成為空表的第一個結(jié)點 else ;/將將newnodenewnode連接到原來的表尾連接到原來的表尾 ;/newnodenewnode成為新的表尾成為新的表尾 tail-next=NULL;return(head);void main()struct node *head;int n;coutn;head=create(n);head=

12、newnodetail-next=newnodetail=newnode6.2.3 6.2.3 單鏈表的基本操作單鏈表的基本操作1 1、鏈表的遍歷、鏈表的遍歷 由于鏈表的指針域中包含了后繼結(jié)點的存儲地址，所以只要知由于鏈表的指針域中包含了后繼結(jié)點的存儲地址，所以只要知道該鏈表的頭指針，即可依次對每個結(jié)點進行訪問。道該鏈表的頭指針，即可依次對每個結(jié)點進行訪問?！纠?.46.4】輸出上例中建立的單鏈表的各結(jié)點的值。輸出上例中建立的單鏈表的各結(jié)點的值。分析：分析：假設(shè)定義假設(shè)定義p p是指向鏈表中結(jié)點的工作指針，該指針從表是指向鏈表中結(jié)點的工作指針，該指針從表頭頭headhead開始逐一指向后續(xù)的

13、各個結(jié)點，每指向一個結(jié)點，便通過該開始逐一指向后續(xù)的各個結(jié)點，每指向一個結(jié)點，便通過該指針訪問結(jié)點的數(shù)據(jù)域，直到指針訪問結(jié)點的數(shù)據(jù)域，直到p p的值為的值為NULLNULL。遍歷的函數(shù)實現(xiàn)如下：遍歷的函數(shù)實現(xiàn)如下：void print(struct node *head)struct node*p=head;while(p!=NULL)coutdatanext2 2、統(tǒng)計結(jié)點個數(shù)統(tǒng)計結(jié)點個數(shù)【例例6.56.5】統(tǒng)計例統(tǒng)計例6.36.3中創(chuàng)建的鏈表中結(jié)點的個數(shù)。中創(chuàng)建的鏈表中結(jié)點的個數(shù)。分析：分析：設(shè)置一個工作指針從表頭結(jié)點開始，每經(jīng)過一個結(jié)點，設(shè)置一個工作指針從表頭結(jié)點開始，每經(jīng)過一個結(jié)點，計

14、數(shù)器的值增加計數(shù)器的值增加1 1。實現(xiàn)統(tǒng)計的函數(shù)形式如下：。實現(xiàn)統(tǒng)計的函數(shù)形式如下：int count(struct node *head)struct node *p=head;int n=0;while(p!=NULL)n+;p=p-next;return(n);3、查找結(jié)點【例例6.66.6】在鏈表中按序號查找第在鏈表中按序號查找第i i個結(jié)點。個結(jié)點。分析：分析：設(shè)置一個序號計數(shù)器設(shè)置一個序號計數(shù)器j j和一個工作指針和一個工作指針p p，從表頭結(jié)點開始，從表頭結(jié)點開始，順著鏈表的鏈進行查找。僅當(dāng)順著鏈表的鏈進行查找。僅當(dāng)j=ij=i并且并且p!=NULLp!=NULL時查找成功，否則

15、時查找成功，否則查找不成功。查找不成功。void search(struct node *head,int i)int j=1;struct node *p=head;if(i0)coutillegal indexn;elsewhile(j!=i&p!=NULL)j+;if()coutindexi:data;else coutnextj=i&p!=NULL4 4、在鏈表中插入結(jié)點、在鏈表中插入結(jié)點 假假定定有有一一個個指指針針behind behind 指指向向鏈鏈表表中中的的某某個個結(jié)結(jié)點點，newnodenewnode指指向向待插入結(jié)點。待插入結(jié)點。newnode12 10 15 19be

16、hindfront 如如果果有有一一個個指指針針frontfront指指向向behindbehind的的前前驅(qū)驅(qū)，則則僅僅需需編編寫寫下下面面的的兩兩個語句，即可實現(xiàn)插入。個語句，即可實現(xiàn)插入。;如果沒有如果沒有behindbehind指針，插入操作仍然可以完成。指針，插入操作仍然可以完成。newnode-next=front-next;front-next=newnode;newnode-next=behindfront-next=newnode兩個語句的兩個語句的次序能否交次序能否交換？為什么換？為什么？behind7兩種特殊情況：兩種特殊情況：1.1.在表頭結(jié)點之前插入：在表頭結(jié)點之前插

17、入：;2.2.在尾結(jié)點之后插入：在尾結(jié)點之后插入：;newnodeheadbehind6 7newnode 8 【例例6.76.7】編寫函數(shù)，實現(xiàn)在頭結(jié)點為編寫函數(shù)，實現(xiàn)在頭結(jié)點為headhead的鏈表中插入值為的鏈表中插入值為x x的結(jié)點。的結(jié)點。newnode-next=behindhead=newnodebehind-next=newnodeNULLnewnode-next=NULLstructstruct node*node*insert(nodeinsert(node*head,inthead,int x)x)structstruct node*behind,*front,*node

18、*behind,*front,*newnodenewnode;newnodenewnode=new node;=new node;newnodenewnode-data=x;behind=head;-data=x;behind=head;if(headif(head=NULL)/=NULL)/空表空表 head=head=newnodenewnode;newnodenewnode-next=NULL;-next=NULL;else /else /非空表非空表 while(behindwhile(behind!=!=NULL&xNULL&xbehind-data)/behind-data)/找插

19、入位置找插入位置 front=behind;behind=front=behind;behind=behindbehind-next;-next;if(behindif(behind=head)/=head)/插到第一個結(jié)點前插到第一個結(jié)點前 newnodenewnode-next=head;head=-next=head;head=newnodenewnode;else else if(behindif(behind=NULL)/=NULL)/插到最后一個結(jié)點后插到最后一個結(jié)點后 front-next=front-next=newnodenewnode;newnodenewnode-next

20、=NULL;-next=NULL;else /else /插到插到frontfront之后之后,behind,behind之前之前 front-next=front-next=newnode;newnodenewnode;newnode-next=behind;-next=behind;return head;return head;5 5、刪除鏈表中的某個結(jié)點、刪除鏈表中的某個結(jié)點 刪刪除除鏈鏈表表中中的的某某個個結(jié)結(jié)點點，是是把把被被刪刪除除結(jié)結(jié)點點的的后后繼繼結(jié)結(jié)點點的的地地址址,賦賦給其前趨結(jié)點的指針域或表頭指針給其前趨結(jié)點的指針域或表頭指針headhead，無后繼結(jié)點時，則賦無后繼結(jié)

21、點時，則賦NULLNULL。假定假定p p為指向要刪除結(jié)點的指針，為指向要刪除結(jié)點的指針，q q為指向刪除結(jié)點前趨的指針。為指向刪除結(jié)點前趨的指針。如果如果p=headp=head，則刪除的是第一個結(jié)點，則應(yīng)修改表頭指針，則刪除的是第一個結(jié)點，則應(yīng)修改表頭指針headhead，使其指向第二個結(jié)點，并釋放第一個結(jié)點占據(jù)的存儲空間。，使其指向第二個結(jié)點，并釋放第一個結(jié)點占據(jù)的存儲空間。head=p-next;delete p;如果刪除的是鏈表的中間結(jié)點，則應(yīng)把被刪除結(jié)點如果刪除的是鏈表的中間結(jié)點，則應(yīng)把被刪除結(jié)點p p的后繼的后繼結(jié)點的地址，賦給其前趨結(jié)點結(jié)點的地址，賦給其前趨結(jié)點q q的指針域。

22、如果沒有后繼結(jié)的指針域。如果沒有后繼結(jié)點時，則賦空指針點時，則賦空指針NULLNULL。q-next=p-next;delete p;【例例6.86.8】編寫函數(shù)實現(xiàn)在頭結(jié)點為編寫函數(shù)實現(xiàn)在頭結(jié)點為headhead的鏈表中刪除值為的鏈表中刪除值為x x的結(jié)點。的結(jié)點。structstruct node*node*delnode(nodedelnode(node*head,inthead,int x)x)structstruct node*p,*q;/p node*p,*q;/p為工作指針為工作指針,q,q為為p p的前驅(qū)的前驅(qū) p=head;p=head;if(headif(head=NULL

23、)/=NULL)/空表空表 coutcoutThe list is null!n;data!=x)/-data!=x)/找刪除的結(jié)點找刪除的結(jié)點 q=p;p=p-next;q=p;p=p-next;if(pif(p=head)/=head)/刪除第一個結(jié)點刪除第一個結(jié)點 head=p-next;delete p;head=p-next;delete p;else else if(pif(p!=NULL)/!=NULL)/刪除非表頭結(jié)點刪除非表頭結(jié)點 q-next=p-next;delete p;q-next=p-next;delete p;else /else /未找到要刪除的元素未找到要刪除

24、的元素coutcoutxdose not exist in the list!n;xdose not exist in the list!n;return head;6 帶表頭結(jié)點的單鏈表帶表頭結(jié)點的單鏈表針對問題:表頭結(jié)點特殊,在插入和刪除結(jié)點時要單獨處理解決:增加一個偽結(jié)點,即表頭結(jié)點head10203040NULL(1)創(chuàng)建帶表頭結(jié)點的單鏈表創(chuàng)建帶表頭結(jié)點的單鏈表Struct node*creat(int n)struct node*head,*tail,*newnode;Int x;head=new node;tial=head;For(int i=1;ix;newnode=new n

25、ode;newnode-data=x;tail-next=newnode;tail=newnode;tail-next=NULL;return(head);(2)遍歷鏈表 void print(struct node*head)struct node*p;p-head-next;while(p)coutdatanext;(3)結(jié)點插入 struct node*insert(struct node *head,int x)struct node*behide,*front,*newnode;newnode=new node;newnode-data=x;front=head;behide=hea

26、d-next;while(behide&xbehide-data)front=behide;behide=behide-next;If(behide)front-next=newnode;newnode-next=behide;else front-next=newnode;newnode.next=NULL;return(head);（4）結(jié)點刪除Struct node *delnode(struct node*head,intx)struct node*p,*q;p=head-next;q=head;while(p&p-data!=x)q=p;p=p-next;If(p)q-next=p-next;delete p;elsecoutnext=NULL;while(1)cinx;if(x=0)break;newnode=new node;newnode-data=x;newnode-next=NULL;newnode-next=head-next;/讓新結(jié)點指向第一個有效結(jié)點讓新結(jié)點指向第一個有效結(jié)點 head-next=newnode;/讓新結(jié)點成為第一個有效結(jié)點讓新結(jié)點成為第一個有效結(jié)點 接接whilewhile語句后語句后p=head-next;while(p!=NULL)count+;coutdatanext;coutcount=countendl;