1、1第六章第六章 結(jié)構(gòu)和鏈表結(jié)構(gòu)和鏈表6.1 6.1 結(jié)構(gòu)類型結(jié)構(gòu)類型6.2 6.2 結(jié)構(gòu)的應(yīng)用結(jié)構(gòu)的應(yīng)用-鏈表鏈表6.3 6.3 應(yīng)用舉例應(yīng)用舉例26.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)識(shí)符結(jié)構(gòu)類型標(biāo)識(shí)符 結(jié)構(gòu)成員結(jié)構(gòu)成員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語(yǔ)言提供了這樣一種數(shù)據(jù)結(jié)構(gòu)：它將不同類型的數(shù)據(jù)組合成一個(gè)有機(jī)的整體結(jié)構(gòu)體。3struct date int month; int day; int year;

2、 struct man char name15; char sex; int age; date birthday;如，說明一個(gè)結(jié)構(gòu)類型如，說明一個(gè)結(jié)構(gòu)類型datedate，含三個(gè)整型數(shù)據(jù)成員，含三個(gè)整型數(shù)據(jù)成員在此基礎(chǔ)上，又在此基礎(chǔ)上，又可說明另一個(gè)結(jié)可說明另一個(gè)結(jié)構(gòu)類型構(gòu)類型manmanbirthdayNamesexagemonthdayyear struct man結(jié)構(gòu)類型46.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ù)類型的同時(shí)定義結(jié)構(gòu)變量在說明結(jié)構(gòu)數(shù)據(jù)類型的同時(shí)定義結(jié)構(gòu)變量省略結(jié)構(gòu)標(biāo)識(shí)符直接定義結(jié)

3、構(gòu)類型變量省略結(jié)構(gòu)標(biāo)識(shí)符直接定義結(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 birthday; man1, man2;無類型名變量無類型名變量5 struct goods /定義一個(gè)商品結(jié)構(gòu)類型定義一個(gè)商品結(jié)構(gòu)類型 char bh6; /商品編號(hào)商品編號(hào) char mc20; /商品名稱商品名稱 float dj; /商品單價(jià)商品單價(jià) in

4、t sl; /商品數(shù)量商品數(shù)量 char jhrq8; /進(jìn)貨日期進(jìn)貨日期g1=10012, shoes, 124,100, 080912；結(jié)構(gòu)變量也允許在定義的同時(shí)給出初值，即初始化。如： struct person char name15; char sex; int age; s10 =Fang Min,F,24, Fang Hua,M,35;定義一個(gè)結(jié)構(gòu)數(shù)組并對(duì)其部分元素初始化。66.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)的指針-成員

5、名成員名或或或或通過指向結(jié)構(gòu)的指針引用結(jié)構(gòu)變量成員通過指向結(jié)構(gòu)的指針引用結(jié)構(gòu)變量成員成員訪問運(yùn)算符成員訪問運(yùn)算符優(yōu)先級(jí)最高的優(yōu)先級(jí)最高的四個(gè)運(yùn)算符之一四個(gè)運(yùn)算符之一 括號(hào)不能少括號(hào)不能少如，假設(shè)有定義如，假設(shè)有定義man m,*p=&m; strcpy (, Fang Min);p-birthday.month = 8; 則可如下引用結(jié)構(gòu)成員則可如下引用結(jié)構(gòu)成員7【例6.1】某商場(chǎng)周年店慶期間對(duì)其會(huì)員進(jìn)行積分換購(gòu)活動(dòng)，活動(dòng)內(nèi)容為允許每天前五名光臨的會(huì)員用其積分換購(gòu)相應(yīng)的商品，假設(shè)每100個(gè)積分可以換購(gòu)5元的商品，編程序求該商場(chǎng)店慶期間每天換購(gòu)出去的商品金額以及會(huì)員換購(gòu)后的剩

6、余積分值。假設(shè)會(huì)員將全部可能積分全部進(jìn)行換購(gòu)。 分析：可以將會(huì)員卡號(hào)和積分組合在一起定義一個(gè)結(jié)構(gòu)類型，用結(jié)構(gòu)數(shù)組來描述若干會(huì)員的信息。如， struct card char num10; int score; c10;8#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); /每100分換購(gòu)5元商品 ci.score=ci.score-100*(ci.score/100);

7、 /該會(huì)員的剩余積分 cout扣除積分后:n; for(i=0;iN;i+)coutci.numtci.scoreendl; cout積分換購(gòu)金額=sdata=10;q=new node;q-data=20;NULLq-next=NULLp-next=q;206.2.2 6.2.2 鏈表的建立鏈表的建立【例6.3】創(chuàng)建一個(gè)含有n個(gè)結(jié)點(diǎn)的、包含一個(gè)數(shù)據(jù)域，且其類型為整型的單鏈表。鏈表的建立過程如下：首先設(shè)置head為NULL，即建立一個(gè)空的鏈表。申請(qǐng)一個(gè)新結(jié)點(diǎn)存儲(chǔ)區(qū)域，讓newnode指向該結(jié)點(diǎn)，然后向其數(shù)據(jù)域輸入數(shù)據(jù)。把newnode所指向的結(jié)點(diǎn)插入到鏈表中。如果當(dāng)前鏈表是空表，newnode

8、所指向的結(jié)點(diǎn)應(yīng)該成為該鏈表中唯一的一個(gè)結(jié)點(diǎn)，故head和tail都應(yīng)該指向該結(jié)點(diǎn)。21如果當(dāng)前鏈表非空，則newnode所指向的結(jié)點(diǎn)應(yīng)該做為鏈表中的最后一個(gè)結(jié)點(diǎn)加入到鏈表中，故應(yīng)該將其插在tail指向的結(jié)點(diǎn)后面。 重復(fù)執(zhí)行第2、3步共n次。 將最后一個(gè)結(jié)點(diǎn)的next域置空(NULL)。22#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 (in

9、t i=0; ix; newnode= ; /為newnode申請(qǐng)存放空間newnode-data=x;new node也可用如下語(yǔ)句newnode=( struct node *) malloc(sizeof( struct node);23 if(head=NULL) ; /newnode成為空表的第一個(gè)結(jié)點(diǎn) else ;/將newnode連接到原來的表尾 ; / newnode成為新的表尾 tail-next=NULL; return(head);void main( ) struct node *head; int n; coutn; head = create(n);head=new

10、nodetail-next=newnodetail = newnode246.2.3 6.2.3 單鏈表的基本操作單鏈表的基本操作1、鏈表的遍歷 由于鏈表的指針域中包含了后繼結(jié)點(diǎn)的存儲(chǔ)地址，所以只要知道該鏈表的頭指針，即可依次對(duì)每個(gè)結(jié)點(diǎn)進(jìn)行訪問?！纠?.4】輸出上例中建立的單鏈表的各結(jié)點(diǎn)的值。 假設(shè)定義p是指向鏈表中結(jié)點(diǎn)的工作指針，該指針從表頭head開始逐一指向后續(xù)的各個(gè)結(jié)點(diǎn)，每指向一個(gè)結(jié)點(diǎn)，便通過該指針訪問結(jié)點(diǎn)的數(shù)據(jù)域，直到p的值為NULL。25遍歷的函數(shù)實(shí)現(xiàn)如下：void print(struct node *head)struct node *p=head;while(p!=NULL)

11、coutdatanext262 2、 統(tǒng)計(jì)結(jié)點(diǎn)個(gè)數(shù)統(tǒng)計(jì)結(jié)點(diǎn)個(gè)數(shù)【例6.5】統(tǒng)計(jì)例6.3中創(chuàng)建的鏈表中結(jié)點(diǎn)的個(gè)數(shù)。 設(shè)置一個(gè)工作指針從表頭結(jié)點(diǎn)開始，每經(jīng)過一個(gè)結(jié)點(diǎn)，計(jì)數(shù)器的值增加1。實(shí)現(xiàn)統(tǒng)計(jì)的函數(shù)形式如下：int count(struct node *head) struct node *p = head; int n = 0; while (p != NULL) n+; p = p-next; return(n);273、查找結(jié)點(diǎn)【例6.6】在鏈表中按序號(hào)查找第i個(gè)結(jié)點(diǎn)。 設(shè)置一個(gè)序號(hào)計(jì)數(shù)器j和一個(gè)工作指針p，從表頭結(jié)點(diǎn)開始，順著鏈表的鏈進(jìn)行查找。僅當(dāng)j=i并且p!= NULL時(shí)查找成功，否則

12、查找不成功。28void 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!=NULL294 4、在鏈表中插入結(jié)點(diǎn)、在鏈表中插入結(jié)點(diǎn) 假定有一個(gè)指針behind 指向鏈表中的某個(gè)結(jié)點(diǎn)，newnode指向待插入結(jié)點(diǎn)。newnode12 10 15 19behindfront 如果有一個(gè)指針front指向behind的前驅(qū)，

13、則僅需編寫下面的兩個(gè)語(yǔ)句，即可實(shí)現(xiàn)插入。 ; ; 如果沒有behind指針，插入操作仍然可以完成。newnode-next=front-next;front-next=newnode;思考題：上述兩個(gè)語(yǔ)句的次序能否交換？為什么？newnode-next=behindfront-next=newnode30behind7兩種特殊情況：1. 在表頭結(jié)點(diǎn)之前插入： ; ;2. 在尾結(jié)點(diǎn)之后插入： ; ;newnodeheadbehind6 7newnode 8 【例6.7】編寫函數(shù)，實(shí)現(xiàn)在頭結(jié)點(diǎn)為head的鏈表中插入值為x的結(jié)點(diǎn)。newnode-next=behindhead=newnodebehi

14、nd-next=newnodeNULLnewnode-next=NULL31struct node * insert(node *head,int x) struct node *behind,*front,*newnode; newnode=new node; newnode-data=x; behind=head; if(head=NULL) /空表 head=newnode;newnode-next=NULL; else /非空表 while(behind!=NULL&xbehind-data)/找插入位置 front=behind; behind=behind-next; if

15、(behind=head) /插到第一個(gè)結(jié)點(diǎn)前 newnode-next=head ; head=newnode; else if(behind=NULL) /插到最后一個(gè)結(jié)點(diǎn)后 front-next=newnode; newnode-next=NULL; else /插到front之后,behind之前 front-next=newnode;newnode-next=behind; return head;325 5、刪除鏈表中的某個(gè)結(jié)點(diǎn)、刪除鏈表中的某個(gè)結(jié)點(diǎn) 刪除鏈表中的某個(gè)結(jié)點(diǎn)，是把被刪除結(jié)點(diǎn)的后繼結(jié)點(diǎn)的地址,賦給其前趨結(jié)點(diǎn)的指針域或表頭指針head，無后繼結(jié)點(diǎn)時(shí)，則賦NULL。 假定p

16、為指向要?jiǎng)h除結(jié)點(diǎn)的指針，q為指向刪除結(jié)點(diǎn)前趨的指針。 如果p=head，則刪除的是第一個(gè)結(jié)點(diǎn)，則應(yīng)修改表頭指針head，使其指向第二個(gè)結(jié)點(diǎn)，并釋放第一個(gè)結(jié)點(diǎn)占據(jù)的存儲(chǔ)空間。 head=p-next;delete p; 33如果刪除的是鏈表的中間結(jié)點(diǎn)，則應(yīng)把被刪除結(jié)點(diǎn)p的后繼結(jié)點(diǎn)的地址，賦給其前趨結(jié)點(diǎn)q的指針域。如果沒有后繼結(jié)點(diǎn)時(shí)，則賦空指針NULL。q-next=p-next ; delete p;34【例6.8】編寫函數(shù)實(shí)現(xiàn)在頭結(jié)點(diǎn)為head的鏈表中刪除值為x的結(jié)點(diǎn)。struct node *delnode(node *head,int x) struct node *p,*q; /p為工作

17、指針,q為p的前驅(qū) p = head; if(head=NULL) /空表 coutdata!= x) / 找刪除的結(jié)點(diǎn) q=p; p = p-next; if(p=head) /刪除第一個(gè)結(jié)點(diǎn) head=p-next; delete p; else if(p!=NULL) /刪除非表頭結(jié)點(diǎn) q-next=p-next ; delete p; else /未找到要?jiǎng)h除的元素coutx-next = p-link; p-next = newnode;headnewnodeheadnewnode插入插入headnewnodeheadnewnode插入插入pppp非空表非空表空表空表可見，空表和非空

18、表的操作是一致的，無需再分別討論，簡(jiǎn)化了操作。37q = p-next;p-next = q-next;delete q; headheadheadheadpqpq可見，即使刪除后為空表，也無需修改head，與非空表操作一致386.3 6.3 應(yīng)用舉例應(yīng)用舉例【例6.9】建立一個(gè)帶表頭結(jié)點(diǎn)的單鏈表，要求每次都將最后加入的結(jié)點(diǎn)加到最前面，結(jié)點(diǎn)中的數(shù)據(jù)均是不為0的整數(shù)（要求輸入0時(shí)建立過程結(jié)束），然后統(tǒng)計(jì)結(jié)點(diǎn)個(gè)數(shù)并輸出結(jié)點(diǎn)中的所有數(shù)據(jù)。分析分析 根據(jù)題意，建立該鏈表的過程是不斷向表頭插入新結(jié)點(diǎn)的過程?？紤]到題目要求建立的是一個(gè)含表頭結(jié)點(diǎn)的單鏈表，因此新結(jié)點(diǎn)應(yīng)加入到偽結(jié)點(diǎn)的后面，成為第一個(gè)有效結(jié)點(diǎn)。 39#include iostream.hstruct node int data; struct node *next;void main() struct node *head,*newnode,*p; int x,count=0; head=new node ; head-next=NULL; while(1) cinx; if(x=0) break; n