程序設(shè)計(jì)方法08課件第10章

1、2022/8/1310第十章C語(yǔ)言高級(jí)程序應(yīng)用2022/8/13*10.1鏈表鏈表是由鏈指針構(gòu)成的一種動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)。鏈表分為單向鏈表、雙向鏈表和循環(huán)鏈表。單向鏈表只用一個(gè)鏈指針指向下一個(gè)結(jié)點(diǎn)。雙向鏈表用兩個(gè)鏈指針分別指向前一個(gè)結(jié)點(diǎn)和后一個(gè)結(jié)點(diǎn)。循環(huán)鏈表最后一個(gè)數(shù)據(jù)項(xiàng)的指針指向第一個(gè)數(shù)據(jù)項(xiàng)，因此循環(huán)鏈表是一個(gè)無(wú)表頭和表尾的鏈表。 2022/8/1310 .1.1 引用自身的結(jié)構(gòu) 引用自身的結(jié)構(gòu)是指一種特殊的結(jié)構(gòu)類型，即在結(jié)構(gòu)中包含有指向該結(jié)構(gòu)本身的指針。例如：struct slistint info;struct slist *next;該結(jié)構(gòu)中定義了兩個(gè)成員，第一個(gè)是info；第二個(gè)是next

2、，這是指向struct slist自身的指針。 2022/8/1310.1.2 單向鏈表單向鏈表是由稱為結(jié)點(diǎn)的數(shù)據(jù)項(xiàng)構(gòu)成的。數(shù)據(jù)項(xiàng)通常是由包含數(shù)據(jù)成員和鏈指針成員的結(jié)構(gòu)型數(shù)據(jù)組成，鏈指針用來(lái)指向后繼結(jié)點(diǎn)(即存放指向結(jié)點(diǎn)的地址)。單向鏈表的最后一個(gè)結(jié)點(diǎn)的鏈指針定義為空(用NULL表示)，表示鏈表結(jié)束。另外還需要一個(gè)頭指針head，始終指向鏈表的起始結(jié)點(diǎn)，以便于對(duì)鏈表的操作。單向鏈表的結(jié)構(gòu)如圖10-1-1所示。2022/8/13鏈表元素插入在圖10-1-3的單向鏈表中，在p和q指針?biāo)赶虻慕Y(jié)點(diǎn)間插入一個(gè)數(shù)據(jù)為30的新結(jié)點(diǎn)。2022/8/13鏈表元素刪除2022/8/13 鏈表是由一個(gè)個(gè)有序的結(jié)點(diǎn)組

3、成的，每個(gè)結(jié)點(diǎn)是同類型的結(jié)構(gòu)變量。 通過程序可以建立和顯示鏈表，可以插入、刪除及增加結(jié)點(diǎn)來(lái)維護(hù)鏈表。 鏈表總是包含有鏈?zhǔn)字羔?，鏈表的操作一般都先由鏈?zhǔn)字羔樢龑?dǎo)。 鏈表的創(chuàng)建與遍歷：例如：下面程序建立一個(gè)鏈表，并輸出該鏈表。#include struct student long number; float score; struct student *next;2022/8/13struct student *head; /* 鏈?zhǔn)字羔?*/struct student *create( ) ; /* 創(chuàng)建鏈表函數(shù) */ struct student *ps; /* 創(chuàng)建新結(jié)點(diǎn)指針 */ st

4、ruct student *pend; /*移動(dòng)的鏈尾指針,其后插入結(jié)點(diǎn)*/ ps=(struct student *)malloc(sizeof(struct student); /* 動(dòng)態(tài)申請(qǐng)新建結(jié)點(diǎn)的存儲(chǔ)空間 */ scanf(”%s%fn”,ps-number,ps-score); /*結(jié)點(diǎn)賦值*/ head=NULL; /* 開始時(shí)鏈表為空 */ pend=ps; while(ps-number!=0) if(head=NULL) head=ps; else pend-next=ps;2022/8/13 pend=ps; /*S點(diǎn) */ ps=(struct student *)ma

5、lloc(sizeof(struct student); scanf(”%s%fn”,ps-number,ps-score); pend-next=NULL; free(ps); return(head);void showlist(struct student *head) printf(”The items of list are:n”); while(head) printf(”%s , %f”,head-number,head-score); head=head-next; main( ) showlist(create( );2022/8/13輸入： 輸出結(jié)果： 85.0 The i

6、tems of list are: 73.0 401, 85.0 91.0 410, 73.0 68.0 425, 91.0 82.0 413, 68.00 0 432, 82.0 在main( )中，把建立鏈表函數(shù)create( )的返回值head(指向鏈表指針)作為實(shí)參數(shù)調(diào)用showlist( )函數(shù)。2022/8/13PendPsheadheadpendps40185.040185.071073.0create( )函數(shù)中，鏈表創(chuàng)建過程如下圖所示：第一次進(jìn)入循環(huán)到達(dá)S點(diǎn)：第一次循環(huán)結(jié)束后： head NULL進(jìn)入循環(huán)之前：2022/8/13第二次循環(huán)到達(dá)S點(diǎn)時(shí)： 第二次循環(huán)結(jié)束時(shí)： 程序

7、結(jié)束時(shí)：head40185.041073.040185.041073.042591.040185.041073.042591.041368.043282.0NULL head head pend ps pend ps2022/8/1310.1.3 雙向鏈表雙向鏈表的每個(gè)結(jié)點(diǎn)由數(shù)據(jù)成員以及指向后一結(jié)點(diǎn)和前一結(jié)點(diǎn)的鏈指針?biāo)M成。圖10-1-5表示了雙向鏈表的結(jié)構(gòu)。使用雙向鏈表的主要優(yōu)點(diǎn)是：（1）能從兩個(gè)方向?qū)︽湵磉M(jìn)行操作，不僅簡(jiǎn)化了排序，而且使用戶在數(shù)據(jù)庫(kù)文件操作中能從兩個(gè)方向檢索鏈表；（2）由于可以從正向或反向讀鏈表，當(dāng)其中一個(gè)鏈表被破壞時(shí)，可以使用另一個(gè)鏈表重建鏈表。2022/8/13 為建立

8、一個(gè)雙向鏈表，需要定義一個(gè)包含數(shù)據(jù)和兩個(gè)鏈指針的結(jié)構(gòu)類型。例如：struct dlistint info;struct dlist *next;struct dlist *prior; 其中，next是指向后一結(jié)點(diǎn)的鏈指針，prior是指向前一結(jié)點(diǎn)的鏈指針。2022/8/13雙鏈表插入2022/8/13雙鏈表刪除2022/8/1310.1.4 循環(huán)鏈表如果將單向鏈表的最后一個(gè)結(jié)點(diǎn)的鏈指針指向單向鏈表的第一個(gè)結(jié)點(diǎn)，就構(gòu)成了一個(gè)單向循環(huán)鏈表,如圖10-1-8所示。圖10-1-8 單向循環(huán)鏈表infoinfoinfo對(duì)雙向鏈表做類似的處理可構(gòu)成一個(gè)雙向循環(huán)2022/8/1310.1.5 鏈表應(yīng)用程序

9、舉例例10.1 使用單向鏈表, 把一個(gè)數(shù)組的各個(gè)元素插入到鏈表中，使這些元素在鏈表中以升序排列。 程序如：10_1.cpp例10.2 建立一個(gè)鏈表，每個(gè)結(jié)點(diǎn)包括：學(xué)號(hào)、姓名、性別、年齡，輸入一個(gè)學(xué)號(hào)，如果鏈表中的結(jié)點(diǎn)包括該學(xué)號(hào)，則輸出該結(jié)點(diǎn)內(nèi)容后，并將其結(jié)點(diǎn)刪去。 程序如： 10_2.cpp 2022/8/13*10.2 與系統(tǒng)有關(guān)的庫(kù)函數(shù)10.2.1與操作系統(tǒng)密切相關(guān)的函數(shù)Turbo C庫(kù)函數(shù)的一個(gè)重要特色是設(shè)置有與操作系統(tǒng)密切相關(guān)的一些函數(shù)。這些函數(shù)包括：時(shí)間和日期函數(shù)；BIOS接口調(diào)用函數(shù)DOS系統(tǒng)調(diào)用函數(shù)。2022/8/1310.2.2 BIOS接口調(diào)用函數(shù)在PC-DOS中，ROM_B

10、IOS設(shè)置有12個(gè)中斷。Turbo C對(duì)各種外部設(shè)備的接口調(diào)用都是通過中斷實(shí)現(xiàn)的。表10-2-l是常用的接口調(diào)用函數(shù)。2022/8/13例10.4 下面的程序顯示系統(tǒng)中的內(nèi)存容量(以KB為單位) 。程序如下：/*10_4.c*/#include #include void main()printf(“d K bytes of ramn”,biosmemory();運(yùn)行結(jié)果：4965 K bytes of ram2022/8/1310.2.3 DOS系統(tǒng)調(diào)用函數(shù)例10.6 下面是一個(gè)使用0X2C系統(tǒng)調(diào)用直接從系統(tǒng)時(shí)鐘中讀取時(shí)間的程序。/* 10_6.c */#include #include v

11、oid main()union REGS in, out;in.h.ah=0 x2c;intdos(&in,&out);printf(time is %2d:%2d:%2d,out.h.ch,out.h.cl,out.h.dh);運(yùn)行結(jié)果:time is 18: 4:272022/8/13 10.3 圖形程序 圖形適配器是顯示器和計(jì)算機(jī)之間的接口，不同的適配器支持不同的顯示器操作模式。顯示器基本工作方式：字符方式 最多2580個(gè)字符 圖形方式 分辨率 0X水平分辨率-10Y垂直分辨率-1 2022/8/13 void far initgraph(int far *gdriver, int fa

12、r *gmode, char *path);其中，gdriver和gmode分別表示圖形驅(qū)動(dòng)器和模式, path是指圖形驅(qū)動(dòng)程序所在的目錄路徑。 void far detectgraph(int *gdriver, *gmode);自動(dòng)檢測(cè)顯示器硬件的函數(shù),用gdriver= DETECT 語(yǔ)句 進(jìn)行初始化。10.3.1 圖形模式的初始化2022/8/1310.3.1 圖形模式的初始化示例#include int main() int gdriver=DETECT, gmode; initgraph(&gdriver, &gmode, c:tc); bar3d(50, 50, 150, 250

13、,30, 1); getch(); closegraph(); return 0; 2022/8/1310.3.2 獨(dú)立圖形運(yùn)行程序的建立建立步驟(以EGAVGA為例）在C:TC子目錄下輸入命令BGIOBJ EGAVGA將驅(qū)動(dòng)程序EGAVGA.BGI轉(zhuǎn)換成EGAVGA.OBJ的目標(biāo)文件TLIB LIBGRAPHICS.LIB+EGAVGA，將EGAVGA.OBJ的目標(biāo)模塊裝到GRAPHICS.LIB庫(kù)文件中。在程序中initgraph()函數(shù)調(diào)用之前加上一句:registerbgidriver(EGAVGA_driver)2022/8/13 #include int main() int gd

14、river=DETECT,gmode;registerbgidriver(EGAVGA_driver)； / *建立獨(dú)立圖形運(yùn)行程序 */initgraph( gdriver, gmode,c:tc);bar3d(50,50,250,150,20,1);getch();closegraph();return 0;2022/8/1310.3.3屏幕顏色的設(shè)置和清屏函數(shù)void far setbkcolor(int color); 設(shè)置背景色void far cleardevice(void); 清除圖形屏幕內(nèi)容 void far setcolor(int color); 設(shè)置作圖色int far

15、 getbkcolor(void); 返回當(dāng)前背景顏色值。int far getcolor(void); 返回當(dāng)前作圖顏色值。int far getmaxcolor(void); 返回最高可用的顏色值。 2022/8/1310.3.4 基本圖形函數(shù)有關(guān)坐標(biāo)位置的函數(shù) int far getmaxx(void); 返回x軸的最大值。 int far getmaxy(void); 返回y軸的最大值。 int far getx(void); 返回游標(biāo)在x軸的位置。 void far gety(void);返回游標(biāo)在y軸的位置。 void far moveto(int x, int y); 移動(dòng)游標(biāo)到

16、(x, y)點(diǎn), 不是畫點(diǎn)。void far moverel(int dx, int dy); 移動(dòng)游標(biāo)從當(dāng)前位置(x, y)移動(dòng)到 (x+dx, y+dy)的位置, 移動(dòng)過程中不畫點(diǎn)。2022/8/13畫點(diǎn)函數(shù) void far putpixel(int x, int y, int color)； int far getpixel(int x, int y);線型的設(shè)置函數(shù)。void far setlinestyle(intlinestyle,unsigned upattern,int thickness);2022/8/13畫線函數(shù)void far line(int x0, int y0,

17、 int x1, int y1);void far lineto(int x, int y); 畫一條從當(dāng)前游標(biāo)到點(diǎn)(x, y)的直線。 void far linerel(int dx, int dy); 畫一條從當(dāng)前游標(biāo)到點(diǎn)(x+dx, y+dy)的直線。 void far circle(int x, int y, int radius); 以(x, y)為圓心, radius為半徑, 畫一個(gè)圓。 void far arc(int x, int y, int stangle, int endangle,int radius);void ellipse(int x, int y, int st

18、angle, int endangle, int xradius,int yradius);2022/8/1310.3.5 封閉圖形的填充填充模式設(shè)置 void far setfillstyle(int pattern, int color); void far setfillpattern(char * upattern,int color); void far getfillpattern(char * upattern); void far getfillsetings(struct fillsettingstype far * fillinfo);輪廓函數(shù) void far bar(i

19、nt x1, int y1, int x2, int y2); void far bar3d(int x1,int y1,int x2, int y2,int depth,int topflag); void far pieslice(int x, int y, int stangle, int endangle,int radius); 2022/8/1310.3.6圖形窗口和圖形屏幕操作函數(shù)圖形窗口操作void far setviewport(int xl,int yl,int x2, int y2,int clipflag); void far clearviewport(void);清

20、除當(dāng)前圖形窗口的內(nèi)容。void far getviewsettings(struct viewporttype far * viewport); 屏幕操作void far setactivepage(int pagenum);void far setvisualpage(int pagenum);void far getimage(int xl,int yl, int x2, int y2,void far *mapbuf);void far putimage(int x,int,y,void * mapbuf, int op);unsigned far imagesize(int xl,int yl,int x2,int y2);2022/8/1310.4 聲音程序的實(shí)現(xiàn) 10.4.1