語言進(jìn)階第五講數(shù)據(jù)結(jié)構(gòu)與鏈表

第五講

數(shù)據(jù)結(jié)構(gòu)與鏈表張哲ASIC工程中心

Test1Charstr[]=“hello”;Char*p=str;Intn=10;Sizeof(str)=Sizeof(p)=Sizeof(n)=Test2VoidFunc(charstr[100]){sizeof(str)=}Test3Void*p=malloc(100);Sizeof(p)=Test4VoidGetMemory(char*p){p=(char*)malloc(100);}VoidTest(void){char*str=NULL;GetMemory(str);Strcpy(str,”helloworld”);printf(str);}Test5Char*GetMemory(void){charp[]=“helloworld”;returnp;}VoidTest(void){char*str=NULL;str=GetMemory();printf(str);}Test6voidGetMemory2(char**p,intnum){*p=(char*)malloc(num);}VoidTest(void){char*str=NULL;GetMemory(&str,100);strcpy(str,”hello”);printf(str);}Test7VoidTest(void){char*str=(char*)malloc(100);strcpy(str,“hello”);free(str);If(str!=NULL){strcpy(str,“world”);printf(str);}}目錄結(jié)構(gòu)，聯(lián)合，枚舉用結(jié)構(gòu)構(gòu)成鏈表單向鏈表雙向鏈表循環(huán)雙向鏈表窗口系統(tǒng)的數(shù)據(jù)結(jié)構(gòu)與代碼分析窗口系統(tǒng)的代碼調(diào)試結(jié)構(gòu)體結(jié)構(gòu)是由若干（可不同類型的）數(shù)據(jù)項(xiàng)組合而成的復(fù)合數(shù)據(jù)對(duì)象，這些數(shù)據(jù)項(xiàng)稱為結(jié)構(gòu)的成分或成員。字段:C語言的結(jié)構(gòu)還提供了一種定義字段的機(jī)制，使人在需要時(shí)能把幾個(gè)結(jié)構(gòu)成員壓縮到一個(gè)基本數(shù)據(jù)類型成員里存放，這可以看作是一種數(shù)據(jù)壓縮表示方式。structpack{unsigneda:2;unsignedb:8;unsignedc:6;}pk1,pk2;結(jié)構(gòu)變量pk1或者pk2的三個(gè)成員將總共占用16位存儲(chǔ)，其中a占用2位，b占用8位，c占用6位結(jié)構(gòu)體內(nèi)部的成員的對(duì)齊計(jì)算結(jié)構(gòu)體長(zhǎng)度（尤其是用sizeof）時(shí)，需要注意！根據(jù)不同的編譯器和處理器，結(jié)構(gòu)體內(nèi)部的成員有不同的對(duì)齊方式，這會(huì)引起結(jié)構(gòu)體長(zhǎng)度的不確定性。#include

<stdio.h>struct

a{char

a1;char

a2;char

a3;}A;

struct

b{short

a2;char

a1;}B;

voidmain(void){

printf(“%d,%d,%d,%d”,sizeof(char),sizeof(short),sizeof(A),sizeof(B));

}在TurboC2.0中結(jié)果是:在VC6.0中是:結(jié)構(gòu)體內(nèi)部的成員的對(duì)齊計(jì)算結(jié)構(gòu)體長(zhǎng)度（尤其是用sizeof）時(shí)，需要注意！根據(jù)不同的編譯器和處理器，結(jié)構(gòu)體內(nèi)部的成員有不同的對(duì)齊方式，這會(huì)引起結(jié)構(gòu)體長(zhǎng)度的不確定性。#include

<stdio.h>struct

a{char

a1;char

a2;char

a3;}A;

struct

b{short

a2;char

a1;}B;

voidmain(void){

printf(“%d,%d,%d,%d”,sizeof(char),sizeof(short),sizeof(A),sizeof(B));

}在TurboC2.0中結(jié)果是:1,2,3,3在VC6.0中是:1,2,3,4字節(jié)對(duì)齊滿足三個(gè)準(zhǔn)則結(jié)構(gòu)體變量的首地址能夠被其最寬基本類型成員的大小所整除；結(jié)構(gòu)體每個(gè)成員相對(duì)于結(jié)構(gòu)首地址的偏移量（offset）都是成員大小的整數(shù)倍，

如有需要編譯器會(huì)在成員之間加上填充字節(jié)（internaladding）；結(jié)構(gòu)體的總大小為結(jié)構(gòu)體最寬基本類型成員大小的整數(shù)倍，如有需要編譯器會(huì)在最末一個(gè)成員之后加上填充字節(jié)（trailingpadding）。幾點(diǎn)說明結(jié)構(gòu)體某個(gè)成員相對(duì)于結(jié)構(gòu)體首地址的偏移量可以通過宏offsetof()來獲得，這個(gè)宏也在stddef.h中定義基本類型是指前面提到的像char、short、int、float、double這樣的內(nèi)置數(shù)據(jù)類型，這里所說的“數(shù)據(jù)寬度”就是指其sizeof的大小。由于結(jié)構(gòu)體的成員可以是復(fù)合類型，比如另外一個(gè)結(jié)構(gòu)體，所以在尋找最寬基本類型成員時(shí)，應(yīng)當(dāng)包括復(fù)合類型成員的子成員，而不是把復(fù)合成員看成是一個(gè)整體。但在確定復(fù)合類型成員的偏移位置時(shí)則是將復(fù)合類型作為整體看待聯(lián)合體在一個(gè)結(jié)構(gòu)（變量）里，結(jié)構(gòu)的各成員順序排列存儲(chǔ)，每個(gè)成員都有自己獨(dú)立的存儲(chǔ)位置。聯(lián)合變量的所有成員共享從同一片存儲(chǔ)區(qū)。因此一個(gè)聯(lián)合變量在每個(gè)時(shí)刻里只能保存它的某一個(gè)成員的值聯(lián)合變量的初始化:聯(lián)合變量也在可以定義時(shí)直接進(jìn)行初始化，但這個(gè)初始化只能對(duì)第一個(gè)成員做。例如下面的描述定義了一個(gè)聯(lián)合變量，并進(jìn)行了初始化uniondata{charn;floatf;};uniondatau1={3};可以利用聯(lián)合體判斷CPU的印第安序intcheckCPU(){unionw{inta;charb;}c;c.a=1;return(c.b==1);}Linux中給出了更加精練的實(shí)現(xiàn)staticunion{charc[4];unsignedlongl;}endian_test={{'l','?','?','b'}};#defineENDIANNESS((char)endian_test.l)枚舉枚舉是一種用于定義一組命名常量的機(jī)制，以這種方式定義的常量一般稱為枚舉常量。一個(gè)枚舉說明不但引進(jìn)了一組常量名，同時(shí)也為每個(gè)常量確定了一個(gè)整數(shù)值。缺省情況下其第一個(gè)常量自動(dòng)給值0，隨后的常量值順序遞增。給枚舉常量指定特定值與給變量指定初始值的形式類似。如果給某個(gè)枚舉量指定了值，跟隨其后的沒有指定值的枚舉常量也將跟著順序遞增取值，直到下一個(gè)有指定值的常量為止例如寫出下面枚舉說明enumcolor{RED=1,GREEN,BLUE,WHITE=11,GREY,BLACK=15};這時(shí)，RED、GREEN,、BLUE的值將分別是?、?、?WHITE、GREY的值將分別是?、?而BLACK的值是?給枚舉常量指定特定值與給變量指定初始值的形式類似。如果給某個(gè)枚舉量指定了值，跟隨其后的沒有指定值的枚舉常量也將跟著順序遞增取值，直到下一個(gè)有指定值的常量為止例如寫出下面枚舉說明enumcolor{RED=1,GREEN,BLUE,WHITE=11,GREY,BLACK=15};這時(shí)，RED、GREEN,、BLUE的值將分別是1、2、3WHITE、GREY的值將分別是11、12而BLACK的值是15用枚舉常量作為數(shù)組長(zhǎng)度typedefenum{WHITE,RED,BLUE,YELLOW,BLACK,COLOR_NUM}COLOR;……floatBallSize[COLOR_NUM];上例中當(dāng)顏色數(shù)量發(fā)生變化時(shí)，只需在枚舉類型定義中加入或刪去顏色。無需修改COLOR_NUM的定義。與大量使用#define相比既簡(jiǎn)潔又可靠。如：typedefenum{WHITE,RED,BLUE,COLOR_NUM}COLOR;sizeof的定義和使用sizeof是C/C++中的一個(gè)操作符（注意！不是函數(shù)！就像return一樣）。其作用就是返回一個(gè)對(duì)象或者類型所占的內(nèi)存字節(jié)數(shù)。sizeof有三種使用形式，如下：

1)sizeof(var);//sizeof(變量);

2)sizeof(type_name);//sizeof(類型);3)sizeofvar;//sizeof變量;數(shù)組的sizeof數(shù)組的sizeof值等于數(shù)組所占用的內(nèi)存字節(jié)數(shù)char*ss="";sizeof(ss)sizeof(*ss);charss[]="";sizeof(ss);sizeof(*ss);charss[100]="";sizeof(ss);strlen(ss);intss[100]="";sizeof(ss);strlen(ss);數(shù)組的sizeof數(shù)組的sizeof值等于數(shù)組所占用的內(nèi)存字節(jié)數(shù)char*ss="";sizeof(ss)//結(jié)果4,ss是指向字符串常量的字符指針sizeof(*ss);//結(jié)果1,*ss是第一個(gè)字符charss[]="";sizeof(ss);//結(jié)果11,計(jì)算到‘\0’位置，因此是10＋1sizeof(*ss);//結(jié)果1,*ss是第一個(gè)字符charss[100]="";sizeof(ss);//結(jié)果100,表示在內(nèi)存中的大小100×1strlen(ss);//結(jié)果10,strlen是到‘\0’為止之前的長(zhǎng)度intss[100]="";sizeof(ss);//結(jié)果200,ss表示在內(nèi)存中的大小100×2strlen(ss);//錯(cuò)誤,strlen的參數(shù)只能是char*且必須以‘\0’結(jié)尾鏈表單向鏈表anextanextanextanextNULLHeadStrutmylink{int a;structmylink *next;}*Head,ptr;代碼typedefstructslink{structslink*next;inta;}SLINK;

SLINK*Head=NULL;

SLINK*AddNewSnode(intvalue){SLINK*ptr;

ptr=(SLINK*)malloc(sizeof(SLINK));if(ptr==NULL)returnNULL;

ptr->a=value;if(Head!=NULL){ptr->next=Head;Head=ptr;}else{Head=ptr;ptr->next=NULL;}

returnptr;}intDeleteSnode(SLINK*ptr){SLINK*p;

if(Head==NULL||ptr==NULL)return-1;

for(p=Head;p==ptr||p==NULL;p=p->next);

if(p==NULL)return-1;

if(p==Head){Head=p->next;}else{

}雙向鏈表HeadanextprevanextprevanextprevNULLStrutmylink{int a;structmylink *next;structmylink *prev;}*Head,ptr;NULL循環(huán)雙向鏈表HeadanextprevanextprevanextprevStrutmylink{int a;structmylink *next;structmylink *prev;}*Head,ptr;ASIXWindow窗口系統(tǒng)

的數(shù)據(jù)結(jié)構(gòu)與代碼分析任務(wù)鏈表和窗口鏈表ASIXWindow說明窗口分為兩類，但是在系統(tǒng)內(nèi)部采用統(tǒng)一的數(shù)據(jù)結(jié)構(gòu)窗體(Form)－也就是我們看到的窗口控件(Control)－按鈕，下拉框，菜單，滾動(dòng)條某一個(gè)控件一定是一個(gè)窗體或則另一個(gè)控件的子窗口；而窗體只能作為父窗口存在；一個(gè)任務(wù)可以有多個(gè)窗體，但是只有最前面的窗體（也就是所謂當(dāng)前窗口）才能接受用戶的輸入消息；ASIXWindow的數(shù)據(jù)結(jié)構(gòu)winptrTCBchildnextprevchildnextprevchildnextprevCurWindowchildnextprevchildnextprevchildnextprevchildnextprevASIXWin中窗口的數(shù)據(jù)結(jié)構(gòu)typedefstructasix_window{

structasix_window *prev; //pointtotheprevioussiblinglink

structasix_window *next; //pointtothenextsiblinglink

structasix_window *child; //pointtothechildrenlink

WNDCLASS *wndclass; //pointtothereleventclassentry

unsignedint task_id; //thetaskidofthiswindow

unsignedint wnd_id; //thewindowidwhichisassignedbyCreatwindow()

unsignedint parent_id; //thewinIdofthiswindows'sparent

unsignedint status;

unsignedshort x; unsignedshort y; unsignedshort width; unsignedshort hight; char *caption; //thecaptiontextstring char *tag; //thehelptagstring unsignedint style; unsignedint hmenu; void *ctrl_str; //pointtothecontrolrelatedstruct void *exdata;}ASIX_WINDOW;窗口類的數(shù)據(jù)結(jié)構(gòu)typedefstructwindow_class{

unsignedchar wndclass_id;

unsignedint (*create)(char*caption,U32style,U16x,U16y,\ U16width,U16hight,U32wndid,U32menu,void**ctrl_str,void*exdata);

unsignedint (*destroy)(void*ctrl_str); unsignedint (*msg_proc)(U32win_id,U16asix_msg,U32lparam,void*data,U16wparam,void*reserved); unsignedint (*msg_trans)(void*ctrl_str,U16msg_type,U32areaId,P_U16data,U32size,void*trans_msg);

unsignedint(*repaint)(void*