第6章 數(shù)據(jù)的組織結(jié)構(gòu)課件

第6章數(shù)據(jù)的組織結(jié)構(gòu)第6章數(shù)據(jù)的組織結(jié)構(gòu)（二）6.3文件

6.2指針類型

6.1結(jié)構(gòu)體類型

6.4聯(lián)合體與枚舉類型

第6章數(shù)據(jù)的組織結(jié)構(gòu)6.1結(jié)構(gòu)體類型

結(jié)構(gòu)體類型的概念

結(jié)構(gòu)體是一種可以將若干個不同數(shù)據(jù)類型的變量組合在一起的復合型數(shù)據(jù)類型。人們常常借助于它將表達同一對象的不同屬性封裝在一起，使之達到邏輯概念與程序變量一一對應的目的，從而提高程序的清晰度，降低程序的復雜度，改善程序的可維護性。第6章數(shù)據(jù)的組織結(jié)構(gòu)結(jié)構(gòu)體類型的聲明

類型聲明的語法格式為：struct<結(jié)構(gòu)體類型名>{<數(shù)據(jù)類型><成員1>；<數(shù)據(jù)類型><成員2>；

......<數(shù)據(jù)類型n><成員n>；};第6章數(shù)據(jù)的組織結(jié)構(gòu)例如：structpoint_type{intx;/*x坐標*/inty;/*y坐標*/};這個結(jié)構(gòu)體類型表示：point_type類型的變量將包含兩個成員x、y，它們分別用于存儲坐標點的兩個坐標值。可以利用point_type類型聲明下面這個結(jié)構(gòu)體類型：structrectangle_type{structpoint_typelefttop;/*左上角的坐標*/structpoint_typerightbottom;/*右下角的坐標*/};第6章數(shù)據(jù)的組織結(jié)構(gòu)

在C語言中，允許用戶為已經(jīng)存在的數(shù)據(jù)類型起一個別名，其說明格式為：

typedef原數(shù)據(jù)類型新數(shù)據(jù)類型名；

typedefstructpoint_type{intx;inty;}POINT;

在這里，POINT與structpoint_type完全等價第6章數(shù)據(jù)的組織結(jié)構(gòu)結(jié)構(gòu)體變量的定義：利用結(jié)構(gòu)體類型名定義變量的格式為：<結(jié)構(gòu)體類型名><變量名>[，<變量名>[，<變量名>...]]；例如：POINTp1,p2;等價于structpoint_typep1,p2;與其他數(shù)據(jù)類型的變量一樣，一旦定義了變量之后，系統(tǒng)就會為這個變量分配相應的存儲空間。對于結(jié)構(gòu)體型變量而言，系統(tǒng)為之分配的存儲單元數(shù)量取決于結(jié)構(gòu)體所包含的成員數(shù)量以及每個成員所屬的數(shù)據(jù)類型。例如，上面定義的結(jié)構(gòu)體型變量p1包含兩個int類型的成員。第6章數(shù)據(jù)的組織結(jié)構(gòu)結(jié)構(gòu)體變量的初始化struct<結(jié)構(gòu)體類型名><變量名>={<成員值列表>}；例：structpoint_typep={10,20};structdate_typed={2005,5,20};structrectangle_typerect={{10,10},{100,100}};結(jié)構(gòu)體變量的引用

<結(jié)構(gòu)體變量名>.<成員名>第6章數(shù)據(jù)的組織結(jié)構(gòu)結(jié)構(gòu)體型變量的基本操作結(jié)構(gòu)體型變量的輸入

scanf(“%d%d%”,&d.year,&d.month,&d.day);結(jié)構(gòu)體型變量的輸出

printf(“%d%d%d”,d.year,d.month,d.day);結(jié)構(gòu)體型變量的賦值d.year=2005;d.month=5;d.day=20;如果一個結(jié)構(gòu)體型變量已經(jīng)被賦值，并且希望將它的值賦給另外一個類型完全相同的結(jié)構(gòu)體型變量，則可以采用整體賦值的方式。第6章數(shù)據(jù)的組織結(jié)構(gòu)學生基本信息的組織方式學生基本信息的組織和管理是一個十分有代表性的結(jié)構(gòu)體應用實例。為了簡化程序的復雜度，減少程序的書寫量，在這里，假設(shè)學生的基本信息只包括：學號、姓名、出生日期、所屬院系、所學專業(yè)。

第6章數(shù)據(jù)的組織結(jié)構(gòu)例1：通過鍵盤輸入30名學生的基本信息，并顯示輸出。然后，再通過鍵盤輸入一個月份和日期，查找并輸出本年度在這個給定日期之后過生日的學生信息。第6章數(shù)據(jù)的組織結(jié)構(gòu)問題分析為了表示一名學生的基本信息，應該聲明一個包括學號、姓名、出生日期、所屬院系、所學專業(yè)的結(jié)構(gòu)體類型?！俺錾掌凇毙枰萌齻€數(shù)據(jù)項才能夠表示完整，而“日期”是一個獨立的概念，也應該為之聲明一個結(jié)構(gòu)體類型。組織30名學生的信息。30名學生的基本信息屬于同一個性質(zhì)的數(shù)據(jù)，因此，應該利用一維數(shù)組將它們組織在一起。第6章數(shù)據(jù)的組織結(jié)構(gòu)算法描述

第6章數(shù)據(jù)的組織結(jié)構(gòu)#include<stdio.h>#defineNUM30typedefstruct{ /*日期結(jié)構(gòu)*/intyear;intmonth;intday;}DATE;typedefstruct{ /*學生信息結(jié)構(gòu)*/intnum;charname[24];DATEbirthday;chardepartment[48];charmajor[32];}STUDENTIFNO;voidinputInfo(STUDENTIFNO[]);voidoutputInfo(STUDENTIFNO[]);voidsearchInfo(STUDENTIFNO[],DATE);程序代碼第6章數(shù)據(jù)的組織結(jié)構(gòu)main(){STUDENTIFNOs[NUM];DATEdate;inputInfo(s);outputInfo(s);printf("\nEnteradate(month,day)");scanf("%d%d",&date.month,&date.day);searchInfo(s,date);}voidinputInfo(STUDENTIFNOs[]){inti;

printf("\nEnter%dstudent'sinfmation(name,birthday,department,major)\n",NUM);for(i=0;i<NUM;i++){ s[i].num=i+1; scanf("%s",s[i].name);

scanf("%d%d%d",&s[i].birthday.year,&s[i].birthday.month,&s[i].birthday.day); scanf("%s",s[i].department); scanf("%s",s[i].major);}}第6章數(shù)據(jù)的組織結(jié)構(gòu)/*輸出全部學生的信息*/voidoutputInfo(STUDENTIFNOs[]){inti;printf("\nNumNameDirthdayDepartmentMajor\n");for(i=0;i<NUM;i++){ printf("\n%4d%14s%4d/%2d/%2d%16s%16s",s[i].num,s[i].name, s[i].birthday.year,s[i].birthday.month,s[i].birthday.day, s[i].department,s[i].major);}}第6章數(shù)據(jù)的組織結(jié)構(gòu)voidsearchInfo(STUDENTIFNOs[],DATEdate){inti;for(i=0;i<NUM;i++){if(s[i].birthday.month>date.month){printf("\n%4d%16s%2d//%2d",s[i].num, s[i].name,s[i].birthday.month,s[i].birthday.day);continue;}if(s[i].birthday.month==date.month&&s[i].birthday.day>date.day){printf("\n%4d%16s%2d//%2d",s[i].num, s[i].name,s[i].birthday.month,s[i].birthday.day);}}}第6章數(shù)據(jù)的組織結(jié)構(gòu)例2：假設(shè)通過鍵盤輸入一個含有10個整數(shù)的數(shù)列。請編寫一個程序，將10個整數(shù)按照從小到大的順序重新排列，要求輸出排序后的結(jié)果以及每個整數(shù)在排序前的位置。結(jié)構(gòu)體類型應用實例

第6章數(shù)據(jù)的組織結(jié)構(gòu)問題分析排序是一種基本且應用廣泛的操作。在前面的實例中，我們已經(jīng)看到過排序操作的實現(xiàn)方法。然而，這個題目不僅要求輸出排序之后的結(jié)果，還要求輸出每個數(shù)據(jù)在排序前的位置。解決這個問題的一種方法是：將原始位置作為每個數(shù)據(jù)的屬性保留起來，并借助于結(jié)構(gòu)類型DATATYPE將每個數(shù)值data及位置pos綁定在一起，形成描述每個數(shù)據(jù)的整體信息。如果在排序過程中，需要交換兩個數(shù)據(jù)的位置，可以將兩個數(shù)據(jù)對應的結(jié)構(gòu)型變量整體相互交換，以便實現(xiàn)每個數(shù)據(jù)的原始位置信息永遠跟隨數(shù)值一同移動的目的。在這個程序中，定義了三個函數(shù)inputValue()、outputValue()和selectSort()，分別用于完成輸入、輸出和查找的操作。第6章數(shù)據(jù)的組織結(jié)構(gòu)#include<stdio.h>#defineNUM10 /*數(shù)列中包含的數(shù)值個數(shù)*/typedefstruct{intdata; /*整型數(shù)值*/intpos; /*原始位置*/}DATATYPE;voidinputValue(DATATYPE[]);voidoutputValue(DATATYPE[]);voidselectSort(DATATYPE[],int);main(){DATATYPEvalue[NUM];inputValue(value);selectSort(value,NUM);outputValue(value);}程序代碼

第6章數(shù)據(jù)的組織結(jié)構(gòu)/*通過鍵盤輸入10個整型數(shù)值*/voidinputValue(DATATYPEvalue[]){inti;printf("\nEnter%dvalues:",NUM);for(i=0;i<NUM;i++){scanf("%d",&value[i].data);value[i].pos=i+1; /*每個數(shù)值的原始位置*/}}/*輸出結(jié)果*/voidoutputValue(DATATYPEvalue[]){inti;for(i=0;i<NUM;i++) /*輸出數(shù)據(jù)及其原始位置*/printf("\n%3d:(%4d:%2d)",i+1,value[i].data,value[i].pos);}第6章數(shù)據(jù)的組織結(jié)構(gòu)/*選擇排序（n項）*/voidselectSort(DATATYPEvalue[],intn){inti,max=0;DATATYPEtemp;if(n<2)return;for(i=1;i<n;i++) /*求最大項的下標*/if(value[max].data<value[i].data) /*按照數(shù)據(jù)大小計算*/max=i;if(max!=n-1){/*整體交換兩個結(jié)構(gòu)型變量*/ temp=value[n-1]; value[n-1]=value[max]; value[max]=temp; /*將最大項移到最后*/}selectSort(value,n-1); /*將前n-1項按照同樣方法排序*/}第6章數(shù)據(jù)的組織結(jié)構(gòu)例3：編寫一個程序，模擬發(fā)撲克牌的過程。問題分析1、每張撲克牌有兩個屬性：一個是花色；一個是面值，因此，可以定義一個用于描述一張撲克牌的結(jié)構(gòu)類型。

typedefstruct{intrank; /*面值*/intsuit; /*花色*/}CARD;其中，rank表示撲克牌的面值，它應該是1~13之間的整數(shù)；suit表示撲克牌的花色，它應該是1~5之間的整數(shù)，用1~4表示花色，用5表示大小王。第6章數(shù)據(jù)的組織結(jié)構(gòu)為了增加程序的可讀性，可以聲明下面這樣一組宏定義：#defineKing5 /*王*/#defineSpade4 /*黑桃*/#defineHearts3 /*紅桃*/#defineDiamonds2 /*方塊*/#defineClub1 /*梅花*/2、一副撲克牌有54張撲克，它們屬于相同的性質(zhì)，因此可以采用一維數(shù)組類型將54張牌的信息組織起來。第6章數(shù)據(jù)的組織結(jié)構(gòu)算法描述

第6章數(shù)據(jù)的組織結(jié)構(gòu)#include<stdio.h>#include<stdlib.h>#defineKing5 /*王*/#defineSpade4 /*黑桃*/#defineHearts3 /*紅桃*/#defineDiamonds2 /*方塊*/#defineClub1 /*梅花*/#defineNUM54typedefstruct{intrank; /*面值*/intsuit; /*花色*/}CARD;voidcreate(CARDcard[]); /*構(gòu)造撲克牌*/voidriffle(CARDcard[]); /*洗牌*/voiddeal(CARDcard[]); /*發(fā)牌*/main(){CARDcard[NUM];create(card);riffle(card);deal(card);}程序代碼

第6章數(shù)據(jù)的組織結(jié)構(gòu)voidcreate(CARDcard[])/*構(gòu)造撲克牌*/{inti;for(i=0;i<NUM;i++){card[i].rank=i%13+1; /*產(chǎn)生撲克牌的面值*/card[i].suit=i/13+1; /*產(chǎn)生撲克牌的花色*/}}voidriffle(CARDcard[])/*洗牌*/{inti,rand1,rand2;CARDtemp;for(i=0;i<1000;i++){ /*重復1000次*/rand1=random(NUM); /*產(chǎn)生兩個隨機數(shù)*/rand2=random(NUM);if(rand1!=rand2){ /*交換兩個位置的撲克牌信息*/ temp=card[rand1]; card[rand1]=card[rand2]; card[rand2]=temp;}}}第6章數(shù)據(jù)的組織結(jié)構(gòu)/*發(fā)牌*/voiddeal(CARDcard[]){inti,count;for(i=0;i<4;i++){ /*循環(huán)4次*/printf("\n\n%drdman:\n",i+1);for(count=0;count<NUM;count+=4){ /*顯示花色*/ switch(card[count+i].suit){ caseKing: printf("(King,"); break; caseSpade: printf("(Spade,"); break; caseHearts: printf("(Herats,"); break; caseDiamonds:printf("(Diamonds,"); break; caseClub: printf("(Club,"); break; }/*顯示面值見下頁*/}}}

第6章數(shù)據(jù)的組織結(jié)構(gòu)

switch(card[count+i].rank){ /*顯示面值*/ case1:if(card[count+i].suit==King) printf("Big_King)"); else printf("A)"); break; case2:if(card[count+i].suit==King) printf("Small_King)"); else printf("2)"); break; case3:case4: case5:case6: case7:case8: case9: case10:printf("%d)",card[count+i].rank); break; case11:printf("J)"); break; case12:printf("Q)"); break; case13:printf("K)"); break; }

第6章數(shù)據(jù)的組織結(jié)構(gòu)6.2指針類型指針類型

指針類型是C語言提供的一種特殊的基本數(shù)據(jù)類型。指針類型變量中存放的不是待操作的數(shù)據(jù)，而是那些待操作數(shù)據(jù)的存儲地址。

地址是用來表示數(shù)據(jù)在內(nèi)存中存放位置的一種標識C語言提供了一種獲取變量地址的途徑?！?”被稱為取地址運算符，它是一個一元運算符，其使用格式為：&變量名。

第6章數(shù)據(jù)的組織結(jié)構(gòu)指針型變量的定義與引用

指針型變量的定義<數(shù)據(jù)類型>*<指針型變量名>；例如：int*intptr;intptr=&a;指針型變量的引用指針部分的引用格式：<指針型變量>指針所指變量部分的引用格式：*<指針型變量>例如：*intptr=30;例如：scanf(“%d”,intptr);printf(“%d”,*intptr);第6章數(shù)據(jù)的組織結(jié)構(gòu)指針與指針所指變量的關(guān)系

第6章數(shù)據(jù)的組織結(jié)構(gòu)指針的基本操作

指針的初始化int*ptr1=&value;int*ptr2=NULL;

NULL是一個特殊的值，它表示目前指針沒有指向任何變量，通常將這種狀態(tài)稱為“空”指針。指針的賦值ptr2=ptr1

可以將一個指針賦給另一個基類型相同的指針，其含義是兩個指針在同一時刻指向同一個變量。第6章數(shù)據(jù)的組織結(jié)構(gòu)指針的比較用來判斷兩個指針在同一時刻是否指向同一個變量，或者判斷某個指針是否為“空”。例如if(ptr1==NULL)return;指針的加減在利用指針訪問數(shù)組元素的時候，應用這種操作移動指針十分便捷。

第6章數(shù)據(jù)的組織結(jié)構(gòu)指針與一維數(shù)組的關(guān)系數(shù)組名是一個含有數(shù)組第1個元素地址的常量指針。a[i]等價于*(a+i)。

數(shù)組名本身并不占有內(nèi)存空間，它是一個指針常量，一旦定義，不允許被更改；而指針卻是一個獨立的變量，在TurboC環(huán)境下占用2個字節(jié)的存儲單元，它的內(nèi)容可以被隨時地更改。例如：int*ptr,iarray[10]；

ptr=iarray；這樣一來，*(ptr+1)就等價于iarray[1]第6章數(shù)據(jù)的組織結(jié)構(gòu)利用指針對數(shù)組元素進行操作假設(shè)有定義：intiarray[20],*ptr;ptr=iarray將數(shù)組iarray的內(nèi)容顯示輸出方法1、for(ptr=iarray,i=0;i<20;i++)

printf(“%d“,*(ptr+i));方法2、for(ptr=iarray;ptr<iarray+20;ptr++)

printf(“%d“,*ptr);第6章數(shù)據(jù)的組織結(jié)構(gòu)例4：從鍵盤輸入一個文本行，統(tǒng)計其中包含的空格和非空格字符的數(shù)量。問題分析在一個文本行中，所包含的字符由空格和非空格兩部分組成。統(tǒng)計空格和非空格字符的數(shù)量需要對整個文本行從前向后掃描一遍。從前面的例子我們早已得知，文本行可以采用字符型數(shù)組表示。在這里，我們采用指針法引用字符型數(shù)組中的每個元素，然后對其進行判斷和統(tǒng)計處理。第6章數(shù)據(jù)的組織結(jié)構(gòu)算法描述第6章數(shù)據(jù)的組織結(jié)構(gòu)#include<stdio.h>#defineNUM80/*文本行包含的最多字符數(shù)目*/main(){chartextline[NUM]; /*存放文本行內(nèi)容的字符型數(shù)組*/char*s; /*作為索引的指針變量*/intcharnum,spacenum; /*字符個數(shù)和空格個數(shù)*/printf("\nEnterastring:"); /*輸入文本行內(nèi)容*/gets(textline);charnum=0; /*統(tǒng)計空格和非空格字符的數(shù)量*/spacenum=0;for(s=textline;*s!='\0';s++){ /*檢查字符串結(jié)尾*/if(*s=='') spacenum++;else charnum++;}

printf("\n%dcharactersand%dspacesinthestring.",charnum,spacenum);}程序代碼第6章數(shù)據(jù)的組織結(jié)構(gòu)指針與二維數(shù)組的關(guān)系

假設(shè)有下列定義：#defineROWNUM5#defineCOLNUM4inta[ROWNUM][COLNUM];int*ptr1;int(*ptr2)[ROWNUM];輸出二維數(shù)組的每個元素內(nèi)容第6章數(shù)據(jù)的組織結(jié)構(gòu)方法一：ptr1=a[0];for(i=0;i<ROWNUM;i++){for(j=0;j<COLNUM;j++)printf("%3d",*(ptr1+i*COLNUM+j));printf("\n");}方法二：ptr2=a;for(i=0;i<ROWNUM;i++){for(j=0;j<COLNUM;j++)printf("%3d",*(*(ptr2+i)+j));printf("\n");}第6章數(shù)據(jù)的組織結(jié)構(gòu)例5：構(gòu)造一個如下所示的下三角方陣。

1000000

1200000

1230000

1234000

1234500

1234560

1234567

第6章數(shù)據(jù)的組織結(jié)構(gòu)問題分析位于下三角部分的元素內(nèi)容等于列下標加1，上三角部分的元素內(nèi)容全部為0。位于下三角元素的坐標特點是i>=j；位于上三角元素的坐標特點是i<j。第6章數(shù)據(jù)的組織結(jié)構(gòu)#include<stdio.h>#defineNUM7main(){inta[NUM][NUM];int*ptr,i,j;/*構(gòu)造下三角方陣*/for(i=0;i<NUM;i++){ptr=*(a+i);/*ptr指向第i行的第1個元素*/for(j=0;j<NUM;j++)if(i>=j) *(ptr+j)=j+1;/*ptr+j指向ptr所指行的下標為j的元素*/ else *(ptr+j)=0;}/*輸出下三角方陣*/for(i=0;i<NUM;i++){ptr=*(a+i);for(j=0;j<NUM;j++)printf("%3d",*(ptr+j));printf("\n");}}程序代碼第6章數(shù)據(jù)的組織結(jié)構(gòu)動態(tài)申請存儲空間

所謂動態(tài)是指在程序運行之后，再根據(jù)實際需求申請相應的存儲空間，這樣既可以滿足用戶在確定所需的元素數(shù)量之后再申請空間，也可以提高存儲空間的利用率。

void*malloc(intsize)這個標準函數(shù)的功能是：請求系統(tǒng)分配size個字節(jié)的連續(xù)存儲空間。如果分配成功，將返回所分配的存儲空間的首地址；否則返回NULL。

例如：ptr=(int*)malloc(sizeof(int)*20);voidfree(void*p)這個標準函數(shù)的功能是：釋放由指針p指向且由malloc()函數(shù)分配的存儲空間。例如：free(ptr);第6章數(shù)據(jù)的組織結(jié)構(gòu)例6：構(gòu)造10行楊輝三角形。楊輝三角形的數(shù)據(jù)如下所示：1

11

121

1331

14641

15101051

第6章數(shù)據(jù)的組織結(jié)構(gòu)問題分析第i行就有i個數(shù)值每行的第1個數(shù)值和第i個數(shù)值都是1，第j（<1<j<i）個數(shù)值是上1行第

j-1個和第j個數(shù)值之和。考慮到各行數(shù)據(jù)的個數(shù)不同，應為每行數(shù)據(jù)提供不同數(shù)量的存儲空間，來保存每行的整數(shù)。同時，為了將各行數(shù)據(jù)組織在一起，需要使用一個數(shù)組，保存每行數(shù)據(jù)的首地址。第6章數(shù)據(jù)的組織結(jié)構(gòu)算法描述

第6章數(shù)據(jù)的組織結(jié)構(gòu)#include<stdio.h>#include<stdlib.h>#defineMAXLINE10main(){int*a[MAXLINE];/*存放楊輝三角形的指針型數(shù)組*/inti,j;a[0]=(int*)malloc(sizeof(int)); /*構(gòu)造第1行數(shù)值*/*a[0]=1;for(i=1;i<MAXLINE;i++){ /*構(gòu)造2~10行內(nèi)容*/a[i]=(int*)malloc(sizeof(int)*(i+1));/*申請i+1個整數(shù)的存儲空間*/*a[i]=1;for(j=1;j<i;j++) *(a[i]+j)=*(a[i-1]+j-1)+*(a[i-1]+j); /*計算第i+1行的第j+1個數(shù)據(jù)*/*(a[i]+i)=1;}for(i=0;i<MAXLINE;i++){/*顯示楊輝三角形*/for(j=0;j<=i;j++) printf("%4d",*(a[i]+j));printf("\n");}for(i=0;i<MAXLINE;i++)free(a[i]);/*釋放所有存儲空間*/}程序代碼第6章數(shù)據(jù)的組織結(jié)構(gòu)指針與字符串字符串是一種以字符’\0’作為結(jié)束標志的字符數(shù)組。表示字符串可以有下面幾種方法：charstr1[]=“ThisisaCprogram.”;char*str2=“ThisisaCprogram.”;char*str3=(char*)malloc(sizeof(char)*25);strcpy(str3,str2);str1是一個含有21個元素的字符型數(shù)組，前20個元素用來存放字符序列“ThisisaCprogram.”，最后一個元素存放字符串結(jié)束符‘\0’；str2是一個指向字符串常量的指針；str3指向一塊動態(tài)申請且可以放置25個字符的存儲空間，調(diào)用strcpy()函數(shù)的目的是將str2所指向的字符串常量復制到str3指向的存儲空間中。第6章數(shù)據(jù)的組織結(jié)構(gòu)計算字符串的長度

比較兩個字符串大小

intstrlen(char*s)

{intlen=0;for(;*s!='\0';s++,len++);returnlen;}

intstrcmp(char*s,char*t){for(;*s==*t;s++,t++)/*對應字符比較，且兩個指針同步加1*/if(*s==’\0’)return0;

/*如果比較到’\0’，兩個對應字符仍相等，則返回0*/return*s-*t;/*此時*s!=*t，根據(jù)對應字符的大小決定比較結(jié)果*/}

第6章數(shù)據(jù)的組織結(jié)構(gòu)

voidstrcpy(char*s,char*t){ while((*s=*t)!=’\0’){s++;t++;}}拷貝字符串。第6章數(shù)據(jù)的組織結(jié)構(gòu)例7：輸入若干個單詞（<50個），每個單詞占據(jù)一行。假設(shè)以空行作為結(jié)束標志。請將輸入的所有單詞按照字典序列重新排序，并輸出排序后的結(jié)果。第6章數(shù)據(jù)的組織結(jié)構(gòu)問題分析由于輸入若干個單詞，且需要對它們進行排序，所以必須保存每個單詞，并且將它們組織成單詞序列。從前面的實例中可以想到：為了提高存儲空間的利用率，可以定義一個字符指針型數(shù)組char*word[50]；每個數(shù)組元素保存一個字符指針，也就是單詞首字符的地址，而為每個單詞申請的存儲單元數(shù)量可以通過調(diào)用函數(shù)strlen()得到。申請到相應的存儲空間后，再調(diào)用strcpy()函數(shù)將剛剛輸入的單詞拷貝到分配的存儲空間中，從而實現(xiàn)將輸入的所有單詞保留起來的目的。判斷單詞之間大小的操作需要調(diào)用strcmp()函數(shù)實現(xiàn)。第6章數(shù)據(jù)的組織結(jié)構(gòu)#include<stdio.h>#include<stdlib.h>#include<string.h>main(){charbuf[32],*p;char*word[64];intindex,i,j,min;index=0;while(1){/*輸入若干個單詞*/gets(buf); if(strlen(buf)==0)break;word[index]=(char*)malloc(strlen(buf)+1);strcpy(word[index++],buf);}程序代碼第6章數(shù)據(jù)的組織結(jié)構(gòu)for(i=0;i<index;i++){/*按照字典序列排序*/min=i;for(j=i+1;j<index;j++) if(strcmp(word[j],word[min])<0) min=j;if(min!=i){ p=word[i]; word[i]=word[min]; word[min]=p;}}for(i=0;i<index;i++)/*輸出結(jié)果*/puts(word[i]);}程序代碼第6章數(shù)據(jù)的組織結(jié)構(gòu)指針型函數(shù)參數(shù)及函數(shù)返回值

指針型參數(shù)的特殊用途—函數(shù)實現(xiàn)兩個數(shù)互換

voids*x,int*y){ inttemp;

temp=*x; *x=*y; *y=temp;}

第6章數(shù)據(jù)的組織結(jié)構(gòu)指針與數(shù)組型參數(shù)

數(shù)組名代表了數(shù)組首元素的地址。因此，它可以保存在指針型變量中，也可以傳遞給指針型的形式參數(shù)；而數(shù)組型的形式參數(shù)和指針型的形式參數(shù)是完全等價的。

voidinputValue(intvalue[],intnum){ inti;

printf(“\nEnter%dintegers:”,num); for(i=0;i<num;i++) scanf(“%d”,value+i);}

第6章數(shù)據(jù)的組織結(jié)構(gòu)命令行參數(shù)main函數(shù)帶參數(shù)的形式：

main(intargc,char*argv[])使用這種形式的main函數(shù)可以讓用戶在發(fā)出運行程序命令的同時，通過命令行向程序傳遞若干個參數(shù)。參數(shù)表中的第一個參數(shù)argc負責帶入命令行包含的參數(shù)個數(shù)，第二個參數(shù)argv是一個指向字符的指針型數(shù)組，它負責帶入命令行中的每個參數(shù)。利用命令行參數(shù)向程序傳遞信息，可以加大程序的靈活性，擴展程序的使用范圍。

第6章數(shù)據(jù)的組織結(jié)構(gòu)例8：通過鍵盤輸入若干個文本行，輸出所有包含給定字符串的文本行。這個給定字符串是通過命令行參數(shù)給出的。第6章數(shù)據(jù)的組織結(jié)構(gòu)問題分析由于需要由命令行參數(shù)傳入一個字符串，所以命令行應該包含兩個參數(shù)，一個是將要運行的程序名稱，另一個是需要帶入的字符串。在main()函數(shù)中，首先應該判斷命令行中是否包含兩個參數(shù)，如果不是，輸出相應的提示信息，并結(jié)束程序的執(zhí)行。第6章數(shù)據(jù)的組織結(jié)構(gòu)算法描述

第6章數(shù)據(jù)的組織結(jié)構(gòu)#include<stdio.h>#include<string.h>#defineMAXLINE80intgetline(char*line);main(intargc,char*argv[]){charline[MAXLINE];if(argc!=2){printf("usage:exatext\n");return;}else{while(getline(line)>0)/*如果讀入非空文本行，執(zhí)行循環(huán)體*/if(strstr(line,argv[1])!=NULL)/*查找給定字符串*/ printf("%s\n",line);}}intgetline(char*line)/*讀入文本行，并返回文本行包含的字符數(shù)量*/{gets(line);returnstrlen(line);}程序代碼第6章數(shù)據(jù)的組織結(jié)構(gòu)指針型函數(shù)返回值

返回字符串str中由start開始的len個字符組成的子串。

char*strsub(char*str,intstart,intlen){ inti,num; char*p;if(strlen(str)<start) returnNULL; /*start無效返回NULL*/ if(start+len>strlen(str))num=strlen(str)-start; /*確定子串包含的字符數(shù)量*/ elsenum=len; p=(char*)malloc(sizeof(char)*(num+1)); /*申請存儲空間*/ for(i=0;i<num;i++)/*構(gòu)造子串*/ *(p+i)=*(str+start+i); *(p+i)=’\0’; returnp;/*返回子串*/}第6章數(shù)據(jù)的組織結(jié)構(gòu)指針類型的應用實例——鏈表鏈表的相關(guān)概念

將一系列結(jié)點通過指針連接起來，好像一個鏈，人們習慣地將這種存儲形式稱為鏈表。其中，每個結(jié)點有表示數(shù)據(jù)值部分的數(shù)據(jù)域（data）；表示后繼數(shù)據(jù)存儲地址的指針域（next）。鏈表結(jié)構(gòu):head是頭指針，它指向鏈表中的第一個結(jié)點。這是鏈表操作的唯一入口點，所有鏈表元素的訪問必須從這里出發(fā)。由于最后一個結(jié)點沒有后繼結(jié)點，所以，它的指針域存放一個特殊值NULL。NULL在圖中常用（^）符號表示，代表了表尾，也可以代表一個空表。

第6章數(shù)據(jù)的組織結(jié)構(gòu)鏈表的基本操作1、計算鏈表中包含的結(jié)點個數(shù)

intListLength(NODE*p){intlen=0；

for(;p!=NULL;p=p->next)len++; *掃描并累加結(jié)點數(shù)量*/returnlen;

}

第6章數(shù)據(jù)的組織結(jié)構(gòu)2、在鏈表head中第i個結(jié)點之前插入一個新數(shù)據(jù)e，返回表頭指針。將新結(jié)點s插入到p之后的方法s->next=p->next;p->next=s;第6章數(shù)據(jù)的組織結(jié)構(gòu)Node*ListInsert(NODE*head,inti,inte){NODE*p,*s;if(i<1||i>ListLength(head)+1) /*檢測i的合理性*/ returnhead;s=(NODE*)malloc(sizeof(NODE));/*構(gòu)建新結(jié)點s*/if(s==NULL) returnhead; /*空間分配失敗時*/s->item=e;if(i==1){ s->next=head; /*直接添加在第1結(jié)點前*/ returns;}p=head;for(p=head;i>2;p=p->next) /*尋找第i-1個結(jié)點，并由p指向*/ i--;s->next=p->next; /*將s結(jié)點插入到p之后*/p->next=s;returnhead;}

第6章數(shù)據(jù)的組織結(jié)構(gòu)3、將鏈表head中第i個結(jié)點刪除，返回表頭指針從鏈表中將s結(jié)點刪除s=p->next;p->next=s->next;free(s);第6章數(shù)據(jù)的組織結(jié)構(gòu)Node*ListDelete(NODE*head,inti){NODE*p,*s;

if(i<1||i>ListLength(L)) /*檢查i值的合理性*/returnhead;if(i==1){ p=head->next; free(head); returnp;}for(p=head;i>2;p=p->next) /*尋找第i-1個結(jié)點*/ i--;s=p->next; /*用s指向?qū)⒁獎h除的結(jié)點*/p->next=s->next; /*刪除s指針所指向的結(jié)點*/free(s);returnhead;}

第6章數(shù)據(jù)的組織結(jié)構(gòu)例9：約瑟夫（Joseph）問題：編號為1，2，···，n的n個人按順時針方向圍坐在一張圓桌旁。首先輸入一個正整數(shù)作為報數(shù)上限值m，然后，從第一個人開始按順時針方向自1開始順序報數(shù)，報到m的人離開桌旁，然后從順時針方向的下一個就坐在桌旁的人開始重新從1報數(shù)，如此下去，直至所有人全部離開桌旁為止。

假設(shè)有10個人，編號從1到10，最初的m=3，通過報數(shù)，這10個人離開桌旁的順序應該是：3，6，9，2，7，1，8，5，10，4。

請設(shè)計一個C程序來模擬這個過程。要求輸出所有人離開桌旁的順序。

第6章數(shù)據(jù)的組織結(jié)構(gòu)問題分析為了區(qū)分不同的人，需要為每個人分配一個編號，由這n個編號組成了一個線性序列。最初，這個線性序列應該為1，2，3，...，n由于n個人坐在一個圓桌旁，所以這個線性序列應該首尾相接，形成一個環(huán)狀。由于每次報到m的人離開桌旁，所以線性序列中的數(shù)據(jù)越來越少。第6章數(shù)據(jù)的組織結(jié)構(gòu)算法描述

第6章數(shù)據(jù)的組織結(jié)構(gòu)#include<stdio.h>#include<stdlib.h>#defineNUM10typedefstructnode{intNo;/*編號*/structnode*next;}NODE;

程序代碼第6章數(shù)據(jù)的組織結(jié)構(gòu)main(){NODE*head=NULL;NODE*p,*rear,*pre;inti,count,m;for(i=1;i<=NUM;i++){/*構(gòu)造循環(huán)鏈表*/p=(NODE*)malloc(sizeof(NODE));p->No=i;if(head==NULL){head=p; /*第1個結(jié)點*/rear=p;}else{rear->next=p; /*加入新的結(jié)點*/rear=p; /*尾結(jié)點*/}}rear->next=head;第6章數(shù)據(jù)的組織結(jié)構(gòu)printf("\Enterm:"); /*輸入報數(shù)上限*/scanf("%d",&m);p=head; /*從第1個結(jié)點開始*/while(p->next!=p){ /*存在多個結(jié)點時，重復報數(shù)*/count=1;do{ /*報數(shù)過程*/p=p->next; /*p始終指向當前報數(shù)的結(jié)點*/count++;}while(count!=m);for(pre=p;pre->next!=p;pre=pre->next);/*找到當前結(jié)點之前的結(jié)點pre*/printf("%4d",p->No); /*輸出離開者信息*/pre->next=p->next; /*從鏈表中刪除離開者*/free(p);p=pre->next;}printf("%4d\n",p->No); /*處理最后一個人的信息*/free(p);}第6章數(shù)據(jù)的組織結(jié)構(gòu)例10：記錄學生考試成績情況。假設(shè)在一個班中有35名學生，為了能夠在畢業(yè)的時候打印出學生的成績單，應該將每個學生的每次考試成績記錄下來。鑒于簡化問題的考慮，這里僅記錄每個學生參加考試的課程名稱和考試成績。請編寫一個C程序，記錄這個班級中每個學生的考試成績情況。

第6章數(shù)據(jù)的組織結(jié)構(gòu)問題分析在這個程序中，主要應該描述兩個部分的數(shù)據(jù)，一部分是學生信息，假設(shè)只包含學生姓名，由于這部分數(shù)據(jù)的數(shù)量已經(jīng)相對固定，所以可以采用一維數(shù)組組織學生信息；另外一部分是每個學生的若干門課程的考試成績，由于每個學生的考試科目及數(shù)量又可能不一樣，甚至差異可能較大，所以采用鏈表組織這部分數(shù)據(jù)。其中，每個結(jié)點包含課程名稱、考試成績和指向下一個結(jié)點的指針。

第6章數(shù)據(jù)的組織結(jié)構(gòu)#include<stdio.h>#include<string.h>#include<stdlib.h>#defineNUM30typedefstructcnode{ /*考試成績結(jié)點結(jié)構(gòu)*/charcname[16]; /*課程名稱*/intscore; /*成績*/structcnode*next;}CNODE;typedefstruct{ /*學生基本信息結(jié)構(gòu)*/charname[20]; /*學生姓名*/CNODE*head; /*指向成績鏈表的指針*/}SNODE;voidinitStuInfo(SNODE[]);voidinputCourseInfo(SNODE[],intNo);voidoutputInfo(SNODE[]);程序代碼第6章數(shù)據(jù)的組織結(jié)構(gòu)voidmain(){inti;SNODEs[NUM];initStuInfo(s); /*輸入學生信息*/for(i=0;i<NUM;i++) inputCourseInfo(s,i); /*輸入一個學生的所有成績*/outputInfo(s); /*輸出所有學生的信息和成績*/}voidinitStuInfo(SNODEs[]) /*輸入學生基本信息*/{inti;printf("\nEnterinformationof%dstudents:\n",NUM);for(i=0;i<NUM;i++){ /*完成學生信息數(shù)組的初始化*/ gets(s[i].name); /*讀入一行文本（學生姓名），存入結(jié)點*/ s[i].head=NULL;}}第6章數(shù)據(jù)的組織結(jié)構(gòu)voidinputCourseInfo(SNODEs[],intNo)/*輸入一個學生的考試成績*/{chartext[80],buf[40];intscore,num,i;CNODE*c;printf("\nEntercourse'snumber:");gets(text); /*讀入一行文本*/sscanf(text,"%d",&num); /*從字符數(shù)組中讀取成績*/printf("\nEntercourse'sname&score:\n");for(i=1;i<=num;i++){gets(text); /*讀入一行文本*/c=(CNODE*)malloc(sizeof(CNODE));sscanf(text,"%s%d",c->cname,&c->score);/*從文本中取出課程名稱和成績*/c->next=s[No].head; /*添加到成績鏈表的表頭*/s[No].head=c;}}第6章數(shù)據(jù)的組織結(jié)構(gòu)voidoutputInfo(SNODEs[])/*輸出所有信息*/{inti;CNODE*p;for(i=0;i<NUM;i++){printf("\n%12s:",s[i].name);for(p=s[i].head;p!=NULL;p=p->next) printf("(%10s,%d)",p->cname,p->score);printf("\n");}}第6章數(shù)據(jù)的組織結(jié)構(gòu)6.3文件文件的概念文件是指存儲在外部介質(zhì)上的一組相關(guān)數(shù)據(jù)的集合。按照不同的組織方式，文件被劃分為兩個類別：文本文件和二進制碼文件。對文件的操作需要經(jīng)過打開文件、讀寫文件和關(guān)閉文件三個階段。

文本文件以字符為基本單位，每個字符占用一個字節(jié)存放對應的ASCII碼；這種文件形式又被稱為ASCII文件。二進制文件是指直接按照二進制編碼形式存儲數(shù)值的方式。第6章數(shù)據(jù)的組織結(jié)構(gòu)文件的基本操作

定義文件指針定義格式為：FILE*<指針變量名>；例如FILE*fp;文件的打開<文件指針>=fopen（<文件名>，<操作模式>）if((fp=fopen("c:\\","r"))==NUUL){printf(“\nCannotopenthefile”);return1; }<文件名>是以字符串形式描述的文件名；<操作模式>是指文件的類別和操作方式?！皉”表示只讀,“w”表示只寫。如果文件打開成功，函數(shù)返回FILE型變量的地址，否則，返回NULL。

第6章數(shù)據(jù)的組織結(jié)構(gòu)文件的關(guān)閉fclose（<文件指針>）；例如：fclose(fp);文件的讀寫操作字符讀寫函數(shù)

：fgetc()和fputc()字符串讀寫函數(shù)：fgets()和fputs()數(shù)據(jù)塊讀寫函數(shù)：fread()和fwrite()格式化讀寫函數(shù)：fscanf()和fprinf()

第6章數(shù)據(jù)的組織結(jié)構(gòu)字符讀寫操作

1、fgetc()的調(diào)用格式：

<字符型變量>=fgetc(<文件指針>)；例如：ch=fgetc(fp)；這條語句的功能是：從fp指向的文件中讀取一個字符并將這個字符賦給char型變量ch。2、fputc()的調(diào)用格式：

fputc(<字符>，<文件指針>)；例如：fputc(ch,fp)；這條語句的功能是：將字符型變量ch的內(nèi)容寫入文件指針fp所指的文本文件中。第6章數(shù)據(jù)的組織結(jié)構(gòu)例11：讀取一個給定的文本文件，并將文件的內(nèi)容顯示在屏幕上。

問題分析需要讀取文本文件，所以以“r”操作模式將文件打開。

文本文件的結(jié)束標志為EOF。當文件讀寫指針指向EOF時，表示文件已經(jīng)讀到了尾部。因此，在讀文件時，需要設(shè)計一個while循環(huán)語句，它的結(jié)束條件是讀取的字符等于EOF。需要讀取的文件名稱通過命令行參數(shù)帶入，這樣可以擴展程序的使用范圍，增加程序運行的靈活性。第6章數(shù)據(jù)的組織結(jié)構(gòu)算法描述

開始結(jié)束ch!=EOF非空行NNargs!=2輸出提示信息輸出chYYYN打開不成功輸出提示信息fgetc()

chfclose()fgetc()

ch第6章數(shù)據(jù)的組織結(jié)構(gòu)#include<stdio.h>main(intargc,char*argv[]){FILE*fp;intch;if(argc!=2){printf("\nNo.");return1;}if((fp=fopen(argv[1],"r"))==NULL){ /*打開文件*/printf("Cannotopenfile!");return1;}ch=fgetc(fp); /*以字符方式讀取文件*/while(ch!=EOF){putchar(ch);ch=fgetc(fp);}fclose(fp); /*關(guān)閉文件*/}程序代碼第6章數(shù)據(jù)的組織結(jié)構(gòu)例12：文本文件的拷貝。

問題分析舊文件名和新文件名均通過命令行參數(shù)帶入。舊文件以讀方式打開，新文件以寫方式打開。一邊從舊文件中讀取字符，一邊往新文件中寫入，直到原文件結(jié)束。第6章數(shù)據(jù)的組織結(jié)構(gòu)#include<stdio.h>main(intargc,char*argv[]){FILE*fp1,*fp2;intch;if(argc!=3){ /*判斷參數(shù)的數(shù)量*/printf("No.");return1;}if((fp1=fopen(argv[1],"r"))==NULL){ /*打開舊文件*/printf("Cannotopen%s\n",argv[1]);return1;}if((fp2=fopen(argv[2],"w"))==NULL){ /*打開新文件*/printf("Cannotopen%s\n",argv[2]);return1;}while((ch=fgetc(fp1))!=EOF) /*拷貝文件*/fputc(ch,fp2);fclose(fp1); /*關(guān)閉兩個文件*/fclose(fp2);}程序代碼第6章數(shù)據(jù)的組織結(jié)構(gòu)字符串讀寫操作

1、fgets()的調(diào)用格式：

fgets(<字符數(shù)組>，n，<文件指針>)；例如：fgets(str,n,fp)；這條語句的功能是：從fp所指的文件中讀出n-1個字符并存入字符數(shù)組str中。2、fputs()的調(diào)用格式：

fputs(<字符串>，<文件指針>)；例如：fputs(“Cprogram”,fp);這條語句的功能是：將字符串“Cprogram”寫入fp所指的文件中。第6章數(shù)據(jù)的組織結(jié)構(gòu)例13：請編寫一個程序，為指定文件的讀取、顯示和寫入提供支持，并以菜單方式提供操作手段。

問題分析設(shè)計一個菜單。菜單中包含讀文件并顯示（readFile）、寫文件（writeFile）和退出（exit）三個選項。當程序運行后，根據(jù)用戶的選擇進行相應的操作。假設(shè)文件中每行的內(nèi)容不超過80個字符，則讀取一行內(nèi)容的操作可以用下面這條語句實現(xiàn)：

fgets(str,80,fp);除主函數(shù)外，設(shè)計兩個函數(shù)，一個是用于讀取文件的函數(shù)readFile()；另一個是用于寫文件的函數(shù)writeFile()。

第6章數(shù)據(jù)的組織結(jié)構(gòu)算法描述

開始結(jié)束顯示菜單choice==1YNchoice!=3NYreadFile()choice==2YNwriteFile()第6章數(shù)據(jù)的組織結(jié)構(gòu)#include<stdio.h>#include<string.h>voidreadFile();voidwriteFile();main(){intchoice,num;charlines[100][80];do{/*顯示菜單*/printf("\n=====MENU=====\n");printf("\nread");printf("\nwrite");printf("\nexit.........................3");printf("\nselect:");scanf("%d",&choice);getchar();/*用戶選擇*/if(choice==1)num=read);if(choice==2)write,num);}while(choice!=3);}程序代碼第6章數(shù)據(jù)的組織結(jié)構(gòu)intreadlines[][80]) /*讀文件*/{inti;FILE*fp;char[30];printf("\Enter:"); /*輸入要進行寫操作的文件名*/gets();if((fp=fopen(,"r"))==NULL){ /*打開