專業(yè)課參考-語言程序設計

鏈表：將數據串起來共74頁第2

頁用戶自定義類型

標準（基本）類型（如int、char、long、double等）：系統(tǒng)已經定義好的數據類型，用戶可以直接使用，無須定義。

自定義類型：用戶可根據實際情況，自己定義的、新的數據類型。 可以根據自己的需要對已有的數據類型重新命名：用typedef

語句定義與已有的數據類型等價的新的類型說明符。用typedef定義數據類型共74頁第3

頁typedef語句的一般形式typedef

已定義的類型新的類型說明符實例

typedef

intINTEGER;

typedef

floatREAL;

typedef

int*POINTI; 下述語句等價：

INTEGERi,j;<==>inti,j;

REALpai;

<==>floatpai；POINTIp;<==>

int*p;用typedef定義數據類型共74頁第4

頁例C10-18.C：改寫“用結構變量求解兩個復數之積”的程序。 typedefintINTEGER;

typedefstructcomplx{/*定義COMP*/

INTEGERreal,im;

}COMP; main() {staticCOMPza={3,4},zb={5,6};

COMPz,cmult(); voidcpr(); z=cmult(za,zb);cpr(za,zb,z); }用typedef定義數據類型共74頁第5

頁

COMPcmult(COMPza,COMPzb)/*返回COMP*/ {COMPw; w.real=za.real*zb.real-za.im*zb.im; w.im=za.real*zb.im+za.im*zb.real; return(w); } voidcpr(COMPza,COMPzb,COMPz) {printf("(%d+%di)*(%d+%di)=",za.real,za.im,zb.real,zb.im); printf("(%d+%di)\n",z.real,z.im); }用typedef定義數據類型共74頁第6

頁常見問題 如何對超長整數進行四則運算？如何保存一個任意長度的整數？

如何說明不定長度的數組？ intn; scnaf("%d",&n); intarray[n];

數組：不能進行動態(tài)說明。解決方案

采用可變長的動態(tài)結構保存不定長數據。鏈表基礎-提出問題共74頁第7

頁鏈表定義 一種簡單、常見的動態(tài)結構，通過指針（鏈）將一組保存信息的結點鏈接在一起。結點定義 結點包括兩部分：信息和鏈接結點的指針。 例如：使用結點描述一個學生的信息（姓名）

structnode{

char

name[20]; /*信息*/

structnode

*link; /*

指針*/ };鏈表基礎-定義與表示共74頁第8

頁鏈表組成

指向鏈表表頭結點的指針(表頭指針，頭指針)

表頭結點（鏈表的第一個結點，不保存信息）

表結點（數據結點，也稱為結點，保存信息）鏈表的圖示表示NULL頭指針頭結點數據結點1數據結點n數據結點i數據結點2鏈表基礎-定義與表示........共74頁第9

頁定義結點的結構，說明表頭指針 根據需要保存的信息來定義結點的結構。 定義描述學生（姓名/住址/電話）的結點：

typedefstructnode

{

charname[20],address[20],phone[15];

structnode*link; //

指針

}

NODE

; //定義結點

NODE

*

head;

//說明頭指針head

typedefstructnode*PNODE;

PNODEhead; //說明頭指針head鏈表基礎-建立鏈表的基本方法共74頁第10

頁建立表頭結點：申請存儲空間

NODE*

p,*head;

p=(

NODE*)malloc(sizeof(NODE));

//申請表頭結點

p->link=NULL; //將表頭結點的link置為NULL head=

p; //head指向表頭結點pNULL表頭結點頭指針head空鏈表p鏈表基礎-建立鏈表的基本方法 head=(

NODE*)malloc(sizeof(NODE));

head->link=NULL;

//將表頭結點的link置為NULL共74頁第11

頁從表頭開始將數據結點插入到鏈表中（插入第一個數據結點）

NODE*

p;

p=(NODE*)malloc(sizeof(NODE));//申請結點

gets(p->name); //數據存入結點

p->link=head->link; //①修改結點指針 head->link=

p; //②插入到表頭NULL頭指針表頭結點headp數據結點nameNULL鏈表基礎-建立鏈表的基本方法共74頁第12

頁在鏈頭插入數據結點（插入下一個數據結點）

p=(NODE*)malloc(sizeof(NODE));

gets(p->name);

p->link=head->link;//①修改結點指針 head->link=

p;//②插入到表頭p頭指針表頭結點head數據結點name1NULL新數據結點xname2鏈表基礎-建立鏈表的基本方法頭指針表頭結點headname1NULLname2共74頁第13

頁將結點插入到鏈表的鏈頭（程序）

調用create函數時，已經建立好表頭結點。 head=(

NODE*)malloc(sizeof(NODE));

head->link=NULL;//head指向頭結點 voidcreate(NODE*

head,

intn)//建n個結點

{ NODE*p;

for(;n>0;n--

) {

p=(NODE*)malloc(sizeof(NODE)); gets(p->name);

p->link=head->link;//①修改結點指針 head->link=

p;//②插入到表頭 }

}鏈表基礎-建立鏈表的基本方法共74頁第14

頁訪問鏈表中全部數據結點 voidoutput(NODE*head)

{NODE*p;

p

=

head->link; //指向第一個數據結點

while

(p!=NULL

)

{

puts(p->name); //輸出結點數據

p=p->link;

//p指向下一結點 }

}NULL頭指針表頭結點head鏈表基礎-訪問鏈表全部結點頭指針表頭結點head數據結點1name數據結點nnameNULL....共74頁第15

頁求鏈表長度：鏈表中所包含的數據結點的數量。 intlength(NODE*head) {intlen;

NODE*p; for(len=0,p=head->link;p!=NULL;++len)

p=p->link;//p指向下一個結點

return(len); }鏈表基礎-求鏈表長度NULL頭指針表頭結點head頭指針表頭結點head數據結點1name數據結點nnameNULL....^ppp^p....共74頁第16

頁在第i

個結點的后面插入新結點：基本原理定位：指針q

指向第i

個結點，指針

p

指向需要插入的結點headD3D2D1D0^表頭結點數據結點數據結點i數據結點數據結點Dpqx鏈表基礎-插入操作鏈接后面指針：p->link=q->link;鏈接前面指針：q->link=p;共74頁第17

頁在第i

個結點的后面插入新結點p voidinsert_node(NODE*head,

NODE*p,

inti)

{NODE*

q;intn=0; for(q=head;

n<i&&

q->link!=NULL;++n

)

q

=

q->link; //①定位

p->link=q->link; //②鏈接后面指針

q->link=p; //③鏈接前面指針

}特殊情況：空表插入/插入位置超過鏈表長度^head表頭結點Dpq^鏈表基礎-插入操作共74頁第18

頁刪除第i

個結點：基本原理定位：指針

q

指向第i-1

個結點，指針

p

指向被刪除的結點headD3D2D1D0^頭結點數據結點數據結點i-1數據結點i數據結點qpx鏈表基礎-刪除操作摘鏈：q->link=p->link;釋放p結點：free(p)共74頁第19

頁在鏈表中刪除第i

個結點（程序）

voiddelete_node(NODE*head,inti)

{NODE*q，

*p;intn=0;

for

(q=head;

n<i-1&&

q->link!=NULL;++n

)

q=q->link; //①定位

if

(i>0&&q->link!=

NULL

){ p=q->link; //p指向被刪除結點

q->link=p->link; //②摘鏈

free(p); //③釋放p結點

}

}特殊情況

指定位置i超長；

刪成空鏈表

head表頭結點^數據結點qp^x鏈表基礎-刪除操作共74頁第20

頁head-1DnD1D0^表頭結點數據結點數據結點數據結點數據結點headDnD1D0^數據結點數據結點數據結點數據結點數據結點headDnD1D0數據結點數據結點數據結點數據結點數據結點head-1DnD1D0表頭結點數據結點數據結點數據結點數據結點有表頭結點的單向鏈表無表頭結點的單向鏈表有表頭結點的單向環(huán)表無表頭結點的單向環(huán)表鏈表基礎-常見形式共74頁第21

頁約瑟夫問題 這是十七世紀的法國數學家加斯帕在《數目的游戲問題》中講的一個故事：15個基督教徒和15個異教徒在海上遇險，必須將一半的人投入海中，其余的人才能幸免于難，于是想了一個辦法：30個人圍成一個圓圈，從第一個人開始依次報數，每數到第9個人就將他扔入大海，如此循環(huán)進行直到僅余15人為止。問怎樣排法，才能使每次投入大海的都是異教徒。算法分析與設計 定義一個結構，表示船上每一個人的狀態(tài)。成員包括每個人的下一個相鄰的人編號和是否被扔下海的記錄。

structnode{ intnextp; /*指向下一個人的指針*/ intno_out; /*是否被扔下海的標記。1：船0：海*/ }link[31];§10-8鏈表基礎-舉例共74頁第22

頁23...10...i+1i+2...2930111...1...11...111link[0]link[30]link[i]link[9]數組下標j30報數計數器k0被扔下海的人數i023...10...i+1i+2...2930111...0...11...111link[0]link[30]link[i]link[9]j11k9i1§10-8鏈表基礎-舉例共74頁第23

頁 main() { inti,j,k; printf(“Theoriginalcircleis”); for(i=1;i<=30;i++) /*初始化數據*/ { link[i].nextp=i+1;link[i].no_out=1; } link[30].nextp=1;

j

=30;/*j:指向處理完的數組元素，從開始link[j]計數*/ for(i=0;i<15;i++) /*i扔下海的人數計數器*/ { for(k=0;;) /*報數計數器*/ if(k<9) { j=link[j].nextp;

k+=link[j].no_out; } elsebreak;

link[j].no_out=0; /*將該人扔下海，標志置0*/ } for(...)... /*輸出結果*/ }§10-8鏈表基礎-舉例例C6_8001共74頁第24

頁用鏈表的方法對約瑟夫問題進行編程算法分析與設計

用鏈表解決約瑟夫問題，首先定義鏈表數據結構

structnode{ intno_out;

structnode*next; };1111...head表頭結點數據結點數據結點數據結點數據結點§10-8鏈表基礎-舉例共74頁第25

頁 main() { inti,j,k; structnode*head,*p;

head=(structnode*)malloc(sizeof(structnode));

head->next=head; for(i=1;i<30;i++) /*初始化數據*/ { p=(structnode*)malloc(sizeof(structnode));

p->next=head->next;

p->no_out=1;head->next=p; } head->no_out=1;

p=(structnode*)malloc(sizeof(structnode));

p->next=head;

head=p;/*j:指向處理完的數組元素，從開始link[j]計數*/ for(i=0;i<15;i++) /*扔下海的人數計數器*/ { for(k=0;;) /*報數計數器*/ if(k<9) {p=p->next;k+=p->no_out; } elsebreak; p->no_out=0; /*將該人扔下海，標志置0*/ } for(...)... /*輸出結果*/ }§10-8鏈表基礎-舉例例C6_8002共74頁第26

頁約瑟夫問題 十七世紀法國數學家加斯帕在《數目的游戲問題》中講的一個故事：15個基督教徒和15個異教徒在海上遇險，必須將一半的人投入海中，其余的人才能幸免于難，于是30個人圍成一個圓圈，從第1個人開始依次報數，每數到第

9

個人就將他扔入大海，如此循環(huán)直到僅余15

人為止。 問人員應該怎樣安排，才能使每次投入大海的都是異教徒。鏈表基礎-舉例共74頁第27

頁用鏈表的方法對約瑟夫問題進行編程算法分析與設計

首先定義鏈表數據結構

structnode{ intno;

structnode*next; };期望建立的原始鏈表形式122930...head表頭數據結點數據結點數據結點數據結點鏈表基礎-舉例共74頁第28

頁main(){ inti,k;structnode*head,*p,*q; head=(structnode*)malloc(sizeof(structnode)); head->no=-1; head->next=head;鏈表基礎-舉例-1122930...head表頭數據結點數據結點數據結點數據結點-1head表頭 for(i=30;i>0;i--)

{

p=(structnode*)malloc(sizeof(structnode)); p->no=i; p->next=head->next; head->next=p; }30pxp29p共74頁第29

頁 while(p->next!=head)//鏈跳過表頭結點 p=p->next;鏈表基礎-舉例-1122930...head表頭數據結點數據結點數據結點數據結點-1122930...head表頭數據結點數據結點數據結點數據結點p p->next=head->next; //p指向30-1122930...head表頭數據結點數據結點數據結點數據結點pp共74頁第30

頁 for(i=0;i<15;i++)//15人出列

{

for(k=1;k<9;k++)//報數到9為止 p=p->next; q=p->next;//p的下一個結點出列 p->next=q->next;//跳過要出列的結點 printf("%3d",q->no);//q結點的編號 free(q);//釋放q結點 }鏈表基礎-舉例-1122930...head表頭數據結點數據結點數據結點數據結點p共74頁第31

頁main(){ inti,k;structnode*head,*p,*q; head=(structnode*)malloc(sizeof(structnode)); head->no=-1; head->next=head; for(i=30;i>0;i--)/*生成循環(huán)鏈表*/ { p=(structnode*)malloc(sizeof(structnode)); p->next=head->next;p->no=i;head->next=p; } printf("\nTheoriginalcircleis:"); while(p->next!=head)/*循環(huán)鏈跳過表頭結點*/ p=p->next; p->next=head->next; /*p指向30*/

for(i=0;i<15;i++)

{

for(k=1;k<9;k++) p=p->next; q=p->next;/*p的下一個結點是要出列的結點*/ p->next=q->next;/*循環(huán)鏈表跳過要出列的結點*/ printf(“%3d”,q->no);/*輸出

q結點的編號*/ free(q);/*釋放q

結點*/ }}鏈表基礎-舉例例C6_8003共74頁第32

頁已知一個有表頭結點的單鏈表，結點結構為data/link，假設該鏈表只給出了頭指針list。在不改變鏈表的前提下，請設計一個盡可能高效的算法，查找鏈表中倒數第k個位置上的結點（k為正整數）。若查找成功，算法輸出該結點的data域的值，并返回1；否則，只返回0。要求：（1）描述算法的基本設計思想；（2）描述算法的詳細實現步驟；（3）根據設計思想和實現步驟，采用程序設計語言描述算法（使用C或C++或Java語言實現），關鍵之處請給出簡要注釋。鏈表基礎-舉例共74頁第33

頁算法的基本設計思想假設鏈表的最后一個結點為倒數第1個結點。

對鏈表進行一遍掃描，用指針p和q分別指向兩個結點，且保持指針p和指針q之間的“距離”（包含的結點數）為k，當p指向最后一個結點時，q指向的就是倒數第k個結點。鏈表基礎-舉例共74頁第34

頁算法的詳細實現步驟假設表頭指針為list，定義兩個指針p和q：①初始化：距離計數器count=0；p=q=list->link，指向鏈表第1個數據結點；②若p非空，則執(zhí)行③和④；否則轉⑤；③如果count小于k，則count=count+1；否則q指向下一個結點；④p指向下一個結點，轉步驟②；⑤若count等于k，則查找成功，輸出該結點的data值，返回1；否則，查找失敗，返回0。算法結束。鏈表基礎-舉例共74頁第35

頁intSearchRevk(pLinkListlist,intk){pLinkListp,q;intcount=0;//

距離計數器p=q=list->link;//p和q指向第一個數據結點while(p!=NULL){ if(count<k)count++; //計數器+1elseq=q->link; //q指向下一個結點p=p->link; //p指向下一個結點

}if(count==k)

{printf("%d\n",q->data); //

查找成功return1;

}elsereturn0; //

查找失敗}鏈表基礎-舉例共74頁第36

頁用帶頭結點的單鏈表保存單詞，當兩個單詞有相同的后綴時，可共享相同的后綴存儲