C語言程序設(shè)計4.ppt

,只能定義單一的數(shù)據(jù)類型，反映事物單一屬性,第11章：復(fù)雜數(shù)據(jù)類型,學(xué)習(xí)的意義,如定義學(xué)生成績： float score;,能定義復(fù)雜的數(shù)據(jù)類型，反映事物多個屬性,如定義學(xué)生信息： struct STU char no9; /學(xué)號 char name12; /姓名 char sex; /性別 float score; /成績 student;,復(fù)雜數(shù)據(jù)類型豐富了C語言對數(shù)據(jù)信息的處理能力。 離開了復(fù)雜數(shù)據(jù)類型，很多信息的描述是無法進行定義，更無法進行處理的。 計算機中的信息表示更多是由復(fù)雜數(shù)據(jù)類型來定義的，象數(shù)據(jù)結(jié)構(gòu)課程中的鏈表、樹、圖等 可以更好地理解數(shù)據(jù)庫中的記錄的含義， 為C+語言中類的概念的理解提供了幫助。,學(xué)習(xí)目標,熟練掌握結(jié)構(gòu)體的定義方法； 熟練掌握結(jié)構(gòu)體的引用方法； 掌握結(jié)構(gòu)數(shù)組的定義及其應(yīng)用； 掌握指向結(jié)構(gòu)的指針的概念及其應(yīng)用； 了解線性鏈表的創(chuàng)建、插入節(jié)點、刪除節(jié)點和撤銷節(jié)點的算法； 掌握利用復(fù)雜數(shù)據(jù)類型作為函數(shù)參數(shù)和返回值的函數(shù)定義方法；,學(xué)習(xí)內(nèi)容,復(fù)雜數(shù)據(jù)類型概述 結(jié)構(gòu)體 結(jié)構(gòu)體類型的定義 結(jié)構(gòu)體變量的定義和引用 結(jié)構(gòu)體變量的賦值 簡化結(jié)構(gòu)體類型名 結(jié)構(gòu)體數(shù)組 線性鏈表,11.1 結(jié)構(gòu)體,結(jié)構(gòu)體是一種構(gòu)造數(shù)據(jù)類型 用途：把不同類型的數(shù)據(jù)組合成一個整體-自定義數(shù)據(jù)類型 引入結(jié)構(gòu)體的好處：加強數(shù)據(jù)項之間的聯(lián)系,如學(xué)生的基本信息，包括學(xué)號、姓名、性別、年齡、班級、成績等數(shù)據(jù)項。這些數(shù)據(jù)項描述了一個學(xué)生的幾個不同側(cè)面。,獨立的變量表示：,結(jié)構(gòu)體變量表示：,char no9; /學(xué)號 char name20; /姓名 char sex; /性別 unsigned int age; /年齡 unsigned int classno; /班級 float grade; /成績,1、結(jié)構(gòu)體類型的定義,struct 結(jié)構(gòu)體類型名 數(shù)據(jù)類型名1 成員名1； 數(shù)據(jù)類型名2 成員名2； 數(shù)據(jù)類型名n 成員名n； ；,struct是關(guān)鍵字, 不能省略,合法標識符 可省:無名結(jié)構(gòu)體,成員類型可以是 基本型或構(gòu)造型,以分號;結(jié)尾,例1： struct Student_Info char no9; /學(xué)號 char name20; /姓名 char sex; /性別 unsigned int age; /年齡 unsigned int classno; /班級 float grade; /成績 ;,例2： struct Date int year; /年 int month; /月 int day; /日 ;,在結(jié)構(gòu)體中數(shù)據(jù)類型相同的成員，既可逐個、逐行分別定義，也可合并成一行定義，就象一次定義多個變量一樣。,struct Student_Info char no9; /學(xué)號 char name20; /姓名 char sex; /性別 unsigned int age; /年齡 unsigned int classno; /班級 float grade; /成績 ;,struct Student_Info char no9, name20, sex; unsigned int age, classno; float grade; ;,struct Date int year; /年 int month; /月 int day; /日 ;,struct Date int year, month, day; ;,注意：結(jié)構(gòu)類型只是用戶自定義的一種數(shù)據(jù)類型，用來定義描述結(jié)構(gòu)的組織形式,不分配內(nèi)存，只有用它來定義某個變量時，才會為該變量分配結(jié)構(gòu)類型所需要大小的內(nèi)存單元。所占內(nèi)存的大小是它所包含的成員所占內(nèi)存大小之和。,2、結(jié)構(gòu)體變量的定義和引用,struct 結(jié)構(gòu)體類型名 數(shù)據(jù)類型名1 成員名1； 數(shù)據(jù)類型名n 成員名n； ； struct 結(jié)構(gòu)體類型名 變量名列表；,結(jié)構(gòu)體變量的定義,間接定義法：先定義結(jié)構(gòu)類型，再定義結(jié)構(gòu)變量,struct student;,struct Student_Info student1, student2;,一次定義多個結(jié)構(gòu)體類型變量,定義指向結(jié)構(gòu)體類型的指針變量,struct Student_Info *pstu;,間接定義法中幾種錯誤的結(jié)構(gòu)體變量的定義方法,沒有結(jié)構(gòu)體類型名,Student_Info student;,缺省struct關(guān)鍵字,struct Point p; struct Point int x, y; ;,結(jié)構(gòu)類型Point定義在后,2、結(jié)構(gòu)體變量的定義和引用,struct 結(jié)構(gòu)體類型名 數(shù)據(jù)類型名1 成員名1； 數(shù)據(jù)類型名n 成員名n； 變量名列表；,結(jié)構(gòu)體變量的定義,直接定義法：定義結(jié)構(gòu)體類型的同時定義結(jié)構(gòu)體變量,struct Student_Info char no9; /學(xué)號 char name20; /姓名 char sex; /性別 unsigned int age; /年齡 unsigned int classno; /班級 float grade; /成績 student1, student2;,struct char no9; /學(xué)號 char name20; /姓名 char sex; /性別 unsigned int age; /年齡 unsigned int classno; /班級 float grade; /成績 student1, student2;,或,無名結(jié)構(gòu)體定義，變量只能一次,幾點說明：,(1) 結(jié)構(gòu)體類型與結(jié)構(gòu)體變量概念不同 類型: 不分配內(nèi)存； 變量: 分配內(nèi)存 類型: 不能賦值、存取、運算; 變量: 可以,(2) 結(jié)構(gòu)體可以嵌套,struct Point int x, y; ; struct Img int tag; struct Img *pimg; /正確，可以包含自身類型的指針 struct Img img; /錯誤，不能包含自身類型的變量 ;,(3) 結(jié)構(gòu)類型中的成員名，可以與程序中的變量同名，它們代表不同的對象，互不干擾,struct Student_Info student; char name20;,(4) 結(jié)構(gòu)體類型及變量的作用域和生存期與基本類型變量相同,結(jié)構(gòu)體變量的引用,引用規(guī)則,結(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é)合性:從左向右,成員(分量)運算符 結(jié)合性:從左向右,結(jié)構(gòu)體變量名.成員名.子成員名最低級子成員名,注意：在利用指針引用結(jié)構(gòu)體成員時，-和之間不能有空格。,3、結(jié)構(gòu)體變量的賦值,結(jié)構(gòu)體變量初始化賦值,先定義結(jié)構(gòu)體類型，再定義結(jié)構(gòu)體變量時賦初值,注意：賦初值時， 中間的數(shù)據(jù)順序必須與結(jié)構(gòu)體成員的定義順序一致，否則就會出現(xiàn)混亂。,struct Student_Info stu = “20020306“, “ZhangMing“, M, 18, 1, 90;,struct Student_Info stu = 18, “ZhangMing“, M, “20020306“, 1, 90;,3、結(jié)構(gòu)體變量的賦值,結(jié)構(gòu)體變量初始化賦值,定義結(jié)構(gòu)體類型的同時，定義結(jié)構(gòu)體變量并賦初值,struct Date int year, month, day; birthday = 1986, 12, 10;,struct int year, month, day; birthday = 1986, 12, 10;,或,struct Student_Info char no9; /學(xué)號 char name20; /姓名 char sex; /性別 unsigned int age; /年齡 unsigned int classno; /班級 float grade; /成績 student = “20020306“, “ZhangMing“, M, 18, 1, 90;,strcpy (stu1.no, stu.no); strcpy (, ); stu1.sex = stu.sex; stu1.age = stu.age; stu1.classno = stu.classno; stu1.grade = stu.grade;,struct Student_Info stu; strcpy (stu.no, “20020306“); strcpy (, “ZhangMing“); stu.sex = M; stu.age = 18; stu.classno = 1; stu.grade = 90; struct Student_Info stu1; stu1 = stu;,3、結(jié)構(gòu)體變量的賦值,結(jié)構(gòu)體變量在程序中賦值,如果在定義結(jié)構(gòu)體變量時并未對其賦初始值，那么在程序中要對它賦值的話，就只能一個一個地對其成員逐一賦值，或者用已賦值的同類型的結(jié)構(gòu)體變量對它賦值,memcpy (,【例1】 計算學(xué)生5門課的平均成績，最高分和最低分。,#include struct score float grade5; float avegrade, maxgrade, mingrade; ; void main ( ) int i; struct score m; printf (“input the grade of five course:n“); for (i = 0; i 5; i+) /輸入5門課的成績 scanf (“%f“, ,m.avegrade = 0; m.maxgrade = m.grade0; m.mingrade = m.grade0; for (i = 0; i m.maxgrade) ? m.gradei : m.maxgrade; m.mingrade = (m.gradei m.mingrade) ? m.gradei : m.mingrade; m.avegrade /= 5; printf (“avegrade = %5.1f maxgrade = %5.1f mingrade = %5.1fn“, m.avegrade, m.maxgrade, m.mingrade); ,運行結(jié)果(設(shè)5門課的成績?yōu)椋?5 80 86 90 68 )： avegrade = 79.8 maxgrade = 90.0 mingrade = 68.0,&m.gradei,注： .和 同優(yōu)先級，具有左結(jié)合性，高于&的優(yōu)先級,4、簡化結(jié)構(gòu)體類型名,利用typedef語句為結(jié)構(gòu)體類型起別名，這樣可使定義結(jié)構(gòu)體類型的變量顯得更為簡潔，同時也增加程序的易讀性。,typedef語句的格式為：,typedef 類型名 類型名的別名；,必須是已經(jīng)定義的數(shù)據(jù)類型名或C語言提供的基本類型名,必須是合法的標識符，通常用大寫字母來表示,必須以分號結(jié)尾,typedef int INTEGER; /INTEGER是別名 typedef char * STRING /STRING是別名 struct teacher_info char name20, char sex, unit30; unsigned int age, workyears; float salary; ; typedef struct teacher_info TEACHER; /TEACHER是別名 INTEGER a; /相當于int a; STRING str; /相當于char *str; TEACHER t; /相當于struct teacher_info t;,typedef char ARRAY81; /ARRAY是別名 ARRAY str; /相當于char str81;,5、結(jié)構(gòu)體數(shù)組,結(jié)構(gòu)體數(shù)組的每一個元素都是具有相同結(jié)構(gòu)體類型的下標結(jié)構(gòu)變量。,結(jié)構(gòu)體數(shù)組的定義,三種形式：,形式一： struct Student_Info char no9, name20, sex; unsigned int age, classno; float grade; ; struct Student_Info stu10;,形式二： struct Student_Info char no9, name20, sex; unsigned int age, classno; float grade; stu10;,形式三： struct char no9, name20, sex; unsigned int age, classno; float grade; stu10;,結(jié)構(gòu)體數(shù)組與二維表的對應(yīng)關(guān)系,結(jié)構(gòu)體數(shù)組就相當于一張二維表，一個表的框架對應(yīng)的就是某種結(jié)構(gòu)體類型，表中的每一列對應(yīng)該結(jié)構(gòu)體的成員，表中每一行信息對應(yīng)該結(jié)構(gòu)體數(shù)組元素各成員的具體值，表中的行數(shù)對應(yīng)結(jié)構(gòu)體數(shù)組的大小。,結(jié)構(gòu)體類型Student_Info,struct Student_Info char no9; char name20; char sex; unsigned int age; unsigned int classno; float grade; stu10;,結(jié)構(gòu)體數(shù)組的初始化,初始化的格式為:,struct 結(jié)構(gòu)體類型名 ； struct 結(jié)構(gòu)體類型名 結(jié)構(gòu)體數(shù)組size = 初值表1， ， 初值表n；,struct 結(jié)構(gòu)體類型名 結(jié)構(gòu)體數(shù)組size = 初值表1，初值表2， ， 初值表n；,或,結(jié)構(gòu)體數(shù)組的引用,引用格式為:,結(jié)構(gòu)體數(shù)組名下標.成員名；,struct Student_Info char no9; char name20; char sex; unsigned int age; unsigned int classno; float grade; stu10;,strcpy (, “WangFei“);,stu1.grade+;,printf (“%s“, );,【例2】統(tǒng)計侯選人選票。,#include #include struct person char name20; /候選人姓名 int count; /得票數(shù) leader3 = “Li“, 0, “Zhang“, 0, “Wang“, 0 ;,void main ( ) int i, j; char leader_name20; while (1) /統(tǒng)計候選人得票數(shù) scanf (“%s“, leader_name); /輸入候選人姓名 if (strcmp(leader_name, “0“) = 0) /輸入為“0“結(jié)束 break; for (j = 0; j 3; j+) /比較是否為合法候選人 if (strcmp(leader_name,) = 0) /合法 leaderj.count+; /得票數(shù)加1 for (i = 0; i 3; i+) /顯示后選人得票數(shù) printf (“%5s : %dn“, , leaderi.count); ,11.3 線性鏈表,1、線性鏈表概述及其結(jié)構(gòu),線性表：當一組數(shù)據(jù)元素形成了“前后”關(guān)系時，我們稱之為線性表,線性表在內(nèi)存中的兩種形式,順序表：以數(shù)組的形式存放，元素在內(nèi)存中是連續(xù)存放的,線性鏈表：數(shù)據(jù)元素在內(nèi)存中不需要連續(xù)存放，而是通過指針將各數(shù)據(jù)單元鏈接起來，就象一條“鏈子”一樣將數(shù)據(jù)單元前后元素鏈接起來,特點：插入或刪除一個數(shù)據(jù)元素時，需要移動其它數(shù)據(jù)元素,特點：插入或刪除一個數(shù)據(jù)元素時，不需要移動其它數(shù)據(jù)元素,節(jié)點,實際數(shù)據(jù)鏈表,頭節(jié)點,表示NULL,數(shù)據(jù)域,指針域,線性鏈表中的節(jié)點可以用一個結(jié)構(gòu)體類型來定義，其形式為：,struct 節(jié)點結(jié)構(gòu)體類型名 數(shù)據(jù)成員定義； struct 節(jié)點結(jié)構(gòu)體類型名 *指針變量名； ;,例： struct Grade_Info int score; struct Grade_Info *next; ; typedef struct Grade_Info NODE;,2、線性鏈表的基本操作,基本操作有：創(chuàng)建、插入、刪除、輸出和銷毀等。,鏈表的創(chuàng)建操作,含義：從無到有地建立起一個鏈表，即往空鏈表中依次插入若干結(jié)點，并保持結(jié)點之間的前驅(qū)和后繼關(guān)系。,基本思想：首先創(chuàng)建一個頭節(jié)點，讓頭指針head和尾指針tail都指向該節(jié)點，并設(shè)置該節(jié)點的指針域為NULL（鏈尾標志）；然后為實際數(shù)據(jù)創(chuàng)建一個節(jié)點，用指針pnew指向它，并將實際數(shù)據(jù)放在該節(jié)點的數(shù)據(jù)域，其指針域置為NULL；最后將該節(jié)點插入到tail所指向節(jié)點的后面，同時使tail指向pnew所指向的節(jié)點。,【例3】 鏈表創(chuàng)建操作函數(shù)Create_LinkList。,NODE *Create_LinkList ( ) /創(chuàng)建鏈表 NODE *head, *tail, *pnew; int scor; head = (NODE *)malloc (sizeof(NODE); /創(chuàng)建頭節(jié)點 if (head = NULL) /創(chuàng)建失敗,則返回 printf (“no enough memory!n“); return (NULL); head-next = NULL; /頭節(jié)點的指針域置NULL tail = head; /開始時尾指針指向頭節(jié)點,pnew-score = score; pnew-next = NULL; tail-next = pnew; tail = pnew; return (head); ,【例】 鏈表創(chuàng)建操作函數(shù)Create_LinkList。,input the score of students:,70,70,65,65,78,78,90,95,-1,printf (“input the score of students:n“); while (1) /創(chuàng)建學(xué)生成績線性鏈表 scanf (“%d“, ,2、線性鏈表的基本操作,鏈表的插入操作,含義：在第i個結(jié)點Ni與第i+1節(jié)點Ni+1之間插入一個新的結(jié)點N，使線性表的長度增1，且Ni與Ni+1的邏輯關(guān)系發(fā)生如下變化：插入前，Ni是Ni+1的前驅(qū)，Ni+1是Ni的后繼；插入后，新插入的結(jié)點N成為Ni的后繼、Ni+1的前驅(qū),基本思想：通過單鏈表的頭指針head，首先找到鏈表的第一個結(jié)點；然后順著結(jié)點的指針域找到第i個結(jié)點，最后將pnew指向的新結(jié)點插入到第i個結(jié)點之后。插入時首先將新節(jié)點的指針域指向第i個結(jié)點的后繼節(jié)點，然后再將第i個結(jié)點的指針域指向新節(jié)點。注意順序不可顛倒。當i=0時，表示頭節(jié)點。,【例4】 鏈表插入操作函數(shù)Insert_LinkList 。,void Insert_LinkList(NODE *head, NODE *pnew, int i) NODE *p; int j; p = head; for (j = 0; j next; if (p = NULL) /表明鏈表中第i個節(jié)點不存在 printf (“the %d node not foundt!n“, i); return; pnew-next = p-next ; /將插入節(jié)點的指針域指向第i個節(jié)點的后繼節(jié)點 p-next = pnew; /將第i個節(jié)點的指針域指向插入節(jié)點 ,假設(shè)i = 2,2、線性鏈表的基本操作,鏈表的刪除操作,含義：刪除鏈表中的第i個結(jié)點Ni，使線性表的長度減1。刪除前，節(jié)點Ni-1是Ni的前驅(qū)，Ni+1是Ni的后繼；刪除后，結(jié)點Ni+1成為Ni-1的后繼。,基本思想：通過單鏈表的頭指針head，首先找到鏈表中指向第i個結(jié)點的前驅(qū)節(jié)點的指針p和指向第i個節(jié)點的指針q；然后刪除第i個結(jié)點。刪除時只需執(zhí)行p-next = q-next即可，當然不要忘了釋放節(jié)點i的內(nèi)存單元。注意當i=0時，表示頭節(jié)點，是不可刪除的。,【例5】鏈表刪除操作函數(shù)Delete_LinkList 。,void Delete_LinkList(NODE *head, int i) NODE *p,*q; int j; if (i = 0) return; /刪除的是頭指針，則返回 p = head; /將p指向要刪除的第i個節(jié)點的前驅(qū)節(jié)點 for (j = 1; j next != NULL; j+) p = p-next; if (p-next = NULL) /表明鏈表中第i個節(jié)點不存在 printf (“the %d node not foundt!n“, i); return; ,假設(shè)i = 2,q = p-next; /q指向待刪除的節(jié)點i p-next = q-next ; /刪除節(jié)點i free(q); /釋放節(jié)點i的內(nèi)存單元 ,2、線性鏈表的基本操作,鏈表的輸出操作,含義：將鏈表中節(jié)點的數(shù)據(jù)域的值顯示出來。如果在輸出過程中，對數(shù)據(jù)進行相應(yīng)的比較，則可實現(xiàn)對鏈表的檢索操作。,基本思想：通過單鏈表的頭指針head，使指針p指向?qū)嶋H數(shù)據(jù)鏈表的第一個節(jié)點，輸出其數(shù)據(jù)值，接著p又指向下一個節(jié)點，輸出其數(shù)據(jù)值，如此進行下去，直到尾節(jié)點的數(shù)據(jù)項輸出完為止，即p為NULL為止。,void Display_LinkList(NODE *head) NODE *p; for (p = head-next; p != NULL; p = p-next) printf (“%d “, p-score); printf (“n“); ,【例6】鏈表輸出操作函數(shù)Display_LinkList 。,2、線性鏈表的基本操作,鏈表的銷毀操作,含義：將創(chuàng)建的鏈表從內(nèi)存中釋放掉，達到銷毀的目的,基本思想：每次刪除頭節(jié)點的后繼節(jié)點，最后刪除頭節(jié)點。注意，不要以為只要刪除了頭節(jié)點就可以刪除整個鏈表,要知道鏈表是一個節(jié)點一個節(jié)點建立起來的，所以銷毀它也必須一個一個節(jié)點的刪除才行。,void Free_LinkList(NODE *head) NODE *p, *q; p = head; while (p-next != NULL) q = p-next; p-next = q-next; free (q); free (head); ,【例7】鏈表銷毀操作函數(shù)Free_LinkList 。,3、線性鏈表應(yīng)用舉例,【例8】 建立一個學(xué)生成績的線性鏈表，然后對其進行插入、刪除、顯示，最后銷毀該鏈表。,#include #include struct Grade_Info int score; struct Grade_Info *next; typedef struct Grade_Info NODE; NODE *Create_LinkList ( ); void Insert_LinkList