C語言程序設計4.ppt

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