1、第7章 結構體結構體由許多組織在一起的數(shù)據(jù)項組成，這些數(shù)據(jù)項不需要屬于同一類型結構體可以容納需要的任意多數(shù)據(jù)項結構體中的變量稱為結構體元素或結構體成員struct studentcharname11;intgrade;intnumber;姓名年級學號學生聲明結構體變量一旦定義了結構體，就可以聲明一個或多個該類型的變量示例：struct student h1;這條語句將會預留足夠的內(nèi)存來存放該結構體中的所有項struct studentcharname11;intgrade;intnumber; h1, h2;struct student h1; struct student h2; struc

2、t student h3, h4;定義時,聲明結構體變量先定義,后聲明 結構體類型與結構變量的最大區(qū)別在于：結構變量占有一定的內(nèi)存空間，而結構體類型只是一種數(shù)據(jù)類型的結構描述，并不占用內(nèi)存空間。 struct box float length; float width; float height; ; 它表明struct box結構體類型由大括號中所列的一些數(shù)據(jù)項組成，共需占用4x3=12個字節(jié)。 在此之后，若進行結構變量的定義如： struct box box1; 表明box1為struct box結構體類型變量，它占用了12個字節(jié)的內(nèi)存單元。初始化結構體student 類型的變量 h1 和

3、 h2 可以按照下面的方式進行聲明和初始化：struct student h1 = “張三”, 3, 20050101;struct student h2 = “李四”, 3, 20050102;struct studentcharname11;intgrade;intnumber;結構體中使用的賦值語句可以使用一條簡單的賦值語句將一個結構體變量的值賦給另一個相同類型的結構體變量例如，如果 h1 和 h2 是同一類型的結構體變量，那么下列語句是有效的：h2 = h1;訪問結構體元素結構體元素通過使用點運算符（.）來引用，這個運算符也稱為成員運算符語法：結構體變量名.元素名示例：cin h1.

4、name;#include void main()struct studentchar name10;int chinese;int english;score;;coutscore.chinese;coutscore.english; /為結構體元素賦值cout姓名: endl;cout語文: score.chineseendl;cout英語: score.englishendl;/輸出結構體元素結構體范例結構體數(shù)組首先定義結構體，然后聲明該類型的數(shù)據(jù)變量示例：struct student stu5;訪問數(shù)組 stu的第三個元素中的變量 num

5、ber :stu2.number結構體數(shù)組的初始化結構體數(shù)組是通過用一對大括號將其元素值列表括起來進行初始化的示例：struct student stu3 =“張三”, 3, 20050101,“李四”, 3, 20050102,“趙飛”, 3, 20050103【例】計算學生的平均成績并統(tǒng)計出不及格的人數(shù)。#include struct stu int num;char name20;char sex;float score;student3=200001,Li li,W,99,200002,Wang hai,M,85,200003,Liu ying,W,50;void main() int

6、 i,n;float average,sum;n=0;sum=0;for(i=0;i3;i+) sum+=studenti.score;if(studenti.score60) n+=1;coutsumendl;average=sum/3;coutaverageendln 運算符用于通過指針來訪問結構體的元素示例：struct student *p, h1;p = &h1;coutname; 這三種用于表示結構成員的形式是完全等效的。 結構變量.成員名 (*結構指針變量).成員名 結構指針變量-成員名 請注意分析下面幾種運算： s-n 得到s指向的結構變量中的成員n的值 s-n+ 得到s指向的

7、結構變量中的成員n的值，用完該值后使 它加1 +s-n 得到s指向的結構變量中的成員n的值使之加1【例】通過結構指針引用結構體成員。#include iostream.hstruct stu int num;char name20;char sex;float score;student1=102,Zhang ping,M,78.5,*s;void main() s=&student1; /*給結構指針變量賦值*/endl;cout(*s).num(*s).nameendl;coutnumnameendl;指向結構數(shù)組 當結構指針指向一

8、個結構數(shù)組時，該指針變量的值是整個結構數(shù)組的首地址。 【例】用指針變量輸出結構數(shù)組。#include iostream.hstruct stu long int num;char name20;char sex;float score;student3=200001,Li li,W,99,200002,Wang hai,M,85,200003,Liuying ,W,50;void main() struct stu *s; for(s=student;sstudent+3;s+) coutnumnameendl;結構指針作函數(shù)參數(shù) 使用結構指針，即用指向結構變量（或數(shù)組）的結構指針作函數(shù)參數(shù)進

9、行傳送，這時由實參向形參傳遞的是地址，屬于“地址傳遞”方式，減少了時間和空間上的開銷。【例】用結構指針變量作函數(shù)參數(shù)編程，計算一組學生的平均成績#include iostream.hstruct stu long int num;char name20;char sex;float score;student3=200001,Li li,W,99,200002,Wang hai,M,85,200003,Liuying ,W,50;void average(struct stu *ps) int n=0,i;float ave,s=0;for(i=0;iscore; ave=s/3;coutav

10、erage=avenum=102;strcpy(s-name,Zhang ping);s-sex=M;s-score=62.5;coutnumnameendl;coutsexscoreendl;free(s);鏈表的使用 鏈表是一種常見的、重要的數(shù)據(jù)結構，它采用動態(tài)的分配辦法為一個結構體分配內(nèi)存空間。 一方面需要時就分配一塊空間用來存放，從而節(jié)約了寶貴的內(nèi)存資源；且便于刪除與加入。 另一方面，在動態(tài)分配時，每個結點之間可以是不連續(xù)的(結點內(nèi)是連續(xù)的)，結點之間的聯(lián)系是通過指針來實現(xiàn)的，即在結點結構中定義一個成員項用來存放下一結點的首地址，這個用于存放地址的成員，常把它稱為指針域。 這樣一種連接

11、方式，如同一條一環(huán)接一環(huán)的鏈子，在數(shù)據(jù)結構中稱之為“鏈表”。struct stu int num; int score; struct stu *next; 在該結構體中前兩個成員項組成數(shù)據(jù)域，最后一個成員項next構成指針域，它是一個指向struct stu類型的結構指針變量。 單鏈表的常用操作：結點的插入、刪除、檢索和排序等。新項目插在表頭新項目插在表中間新項目info1info30info2新項目插在表尾新項目info1info30info2新項目info1info30info2新項目0info1info3info2 建立鏈表【例】編寫一個建立單向鏈表的函數(shù)，存放學生數(shù)據(jù)。#includ

12、e #include malloc.h#define NULL 0 /*令NULL為0，用它表示空地址*/#define LEN sizeof (struct stu) struct stu long int num; float score; struct stu *next; int n; struct stu *creat() /*此函數(shù)返回一個指向鏈表頭的指針*/ struct stu *head,*p1,*p2; n=0;/*n為結點的個數(shù)*/ p1=p2=(struct stu *)malloc(LEN);/*開辟一個新單元*/ cinp1-nump1-score; head=NU

13、LL; while(p1-num!=0) n=n+1; if (n=1)head=p1; else p2-next=p1; p2=p1; p1=( struct stu *)malloc(LEN); cinp1-nump1-score; p2-next=NULL; return(head);/*返回鏈表的頭地址*/圖7-1、圖7-2、圖7-3、圖7-4、圖7-5表示出creat函數(shù)的執(zhí)行過程。圖7-1圖7-2圖7-3(a)圖7-3(b)圖7-3(c)圖7-4(a)圖7-4(b)圖7-4(c)圖7-5鏈表的輸出將鏈表中各結點的數(shù)據(jù)依次輸出，首先要知道鏈表頭元素的地址。程序執(zhí)行過程可見圖7-6所示

14、?！纠繉懸粋€函數(shù)，輸出鏈表中所有結點。void print(head) /*由實參將已有的鏈表的頭指針傳給被調(diào)函數(shù)*/struct stu *head; struct student *p; p=head; /* p指向頭結點*/while(p!=NULL) coutnumscorenext; /*使p指向下一個結點*/ 圖7-6鏈表的刪除操作 從一個鏈表中刪除一個結點，并不是真正從內(nèi)存中把它抹去，而是把它從鏈表中分離開來。 分析：設兩個指針變量p1和p2，先使p1指向第一個結點。刪除一個結點有兩種情況： 一種情況是要刪除結點是第一個結點，此時只需使head指向第二個結點即可，即head=p

15、1-next，其過程如圖7-7所示。 另一種情況是被刪除結點不是第一個結點，可使被刪除結點的前一結點指向被刪結點的后一結點，即p2-next=p1-next，其過程如圖7-8所示?！纠繉懸粋€函數(shù)，刪除鏈表中的指定結點，以指定的學號作為刪除結點的標志。函數(shù)dele編寫如下： struct stu * dele(struct stu *head, long int num) struct stu *p1,*p2; 鏈表的刪除操作if(head=NULL) /*如為空表， 輸出提示信息*/ return head; p1=head; while (p1-num!=num & p1-next!=NU

16、LL) /*當不是要刪除的結點，而且也不是最后一個結點時，繼續(xù)循環(huán)*/ p2=p1;p1=p1-next; /*后移一個結點*/ if(p1-num=num) /*找到要刪除的結點*/ if(p1=head)head=p1-next; /*為第一結點head指向第二結點*/else p2-next=p1-next; /*不是第一個結點，使要刪除結點從鏈表中脫離*/ 鏈表的刪除操作n=n-1;free(p1); else Coutnext=p1;head=p0; 見圖7-9(b)。 第三種情況是在其它位置插入，見圖7-9(c)。 p0-next=p1;p2-next=p0; 最后一種情況是在表末

17、插入，見圖7-9(d)。 p1-next=p0;p0-next=NULL;【例】寫一個函數(shù)，在學生數(shù)據(jù)鏈表中，按學號順序插入一個結點。struct stu * insert(struct stu *head, struct stu *stud) struct stu *p0,*p1,*p2; p1=head;/*指向第一個結點*/ p0=stud; /*指向要插入的結點*/if(head=NULL) /*空表插入*/ head=p0;p0-next=NULL;/*將p0指向的結點作第一個結點*/ else while(p0-nump1-num)&(p1-next!=NULL) p2=p1; p

18、1=p1-next;/*找插入位置*/ if(p0-numnum) if(head=p1)head=p0;/*在第一結點之前插入*/ else p2-next=p0; /*在其它位置插入*/ p0-next=p1;else p1-next=p0; p0-next=NULL; /*在表末插入*/ n=n+1;return (head); 圖7-9(a)圖7-9(b)圖7-9(c)圖7-9(d)棧棧是一種線性表，對棧的所有操作發(fā)生在這個表的同一端，該端稱為棧的“頂”，另一端稱為棧的“底”。由于插入和刪除都在棧頂進行，因此刪除的將是最新插入的成員，所以棧又被稱為“后進先出表（LIFO表或下推表）”。

19、描述一個棧通常需要一個變量和三個函數(shù)：變量用于記錄當前的棧頂位置；函數(shù)包括將數(shù)據(jù)項壓入棧的push()、從棧頂彈出一個成員的pop()、讀棧頂成員的top()。有時還需要引入一個變量標識棧內(nèi)數(shù)據(jù)對象數(shù)目或者棧底的位置。stackINFONODE*datapNextdatapNextdatapNext.棧通常以順序方式存儲。如果棧中所有項目類型相同，并且項目總數(shù)具有上限，那么這個?？梢砸痪S數(shù)組方式實現(xiàn)，這種實現(xiàn)方式棧的基本操作十分簡單，缺點是對棧成員的總數(shù)有限制，且成員一般要具有相同類型。 棧的比較靈活的實現(xiàn)方式是采用單鏈表。聯(lián)合體 將幾種不同類型的變量存放在同一段內(nèi)存單元中的結構稱為“聯(lián)合體”

20、，也稱為“共用體”。 “聯(lián)合體”與“結構體”有一些相似之處，但兩者有本質(zhì)上的不同。在結構體中各成員有各自的內(nèi)存空間，一個結構變量的總長度是各成員長度之和；而在聯(lián)合體中，各成員共享一段內(nèi)存空間，一個聯(lián)合變量的長度等于各成員中最長的長度。聯(lián)合體類型的聲明聲明一個聯(lián)合體類型的一般形式為：union ; 例如：union perdata int class; char office10;在使用聯(lián)合體類型數(shù)據(jù)時要注意它具有以下一些特點：（1）一個聯(lián)合變量，每次只能賦予一個成員值。（2）聯(lián)合變量中起作用的成員是最后一次存放的成員。（3）不允許對聯(lián)合變量作初始化賦值，賦值只能在程序中進行。【例】編寫程序使用聯(lián)合體類型數(shù)據(jù)來保存數(shù)據(jù)。#include void main() union t char *name;int age;int income;union t list;coutsizeof(union t*)endl;/*輸出聯(lián)合體類型長度*/=Zhang hai;/*第一