郝斌數(shù)據(jù)構(gòu)造自學(xué)筆記

??知識(shí)點(diǎn)+程序源代碼

.12By-HZM

1」十么叫做數(shù)據(jù)構(gòu)造

數(shù)據(jù)構(gòu)造概述

定義

我們?cè)鯓影熏F(xiàn)實(shí)中大量而更雜的問題以特定的數(shù)據(jù)類型和特定的存儲(chǔ)構(gòu)造保留到主存

儲(chǔ)器（內(nèi)存）中，以及在此基礎(chǔ)上為實(shí)現(xiàn)某個(gè)功能（例如查找某個(gè)元素，刪除某個(gè)元素，

對(duì)所有元素進(jìn)行排序）而執(zhí)行的對(duì)應(yīng)操作，這個(gè)對(duì)應(yīng)的操作也叫算法。

數(shù)據(jù)構(gòu)造=個(gè)體的存儲(chǔ)+個(gè)體的關(guān)系存儲(chǔ)

算法=對(duì)存儲(chǔ)數(shù)據(jù)的操作

2—衡量算法的原則

算法

解題的措施和環(huán)節(jié)

衡量算法的原則

1）時(shí)間復(fù)雜度：大概程序執(zhí)行的次數(shù)，而非執(zhí)行的時(shí)間

2）空間復(fù)雜度：算法執(zhí)行過程中大概所占用的最大內(nèi)存

3）難易程度

4）強(qiáng)健性

3一數(shù)據(jù)構(gòu)造的特點(diǎn)

數(shù)據(jù)構(gòu)造的地位

數(shù)據(jù)構(gòu)造是軟件中最關(guān)鍵的課程

程序=數(shù)據(jù)的存儲(chǔ)+數(shù)據(jù)的操作+可以被計(jì)算機(jī)執(zhí)行的語言

4—預(yù)備知識(shí)—指針」

5_預(yù)備知識(shí)_指針_2

指針的重要性：

指針是C語言的靈魂

定義：

地址：

地址是內(nèi)存單元的編號(hào)，從。開始的非負(fù)整數(shù)，范圍：O-FFFFFFFF[0-4G-1]

CPU=====地址線，控制線，數(shù)據(jù)線=====內(nèi)存

指針：

指針就是地址，地址就是指針。

指針變量是寄存內(nèi)存單元地址的變量。

指針的本質(zhì)是一種操作受限的非負(fù)整數(shù)。

分類：

1.基本類型的指針

2.指針和數(shù)組的關(guān)系

變量并不一定持續(xù)分派，隨機(jī)分派內(nèi)存。

內(nèi)存：

內(nèi)存是多字節(jié)構(gòu)成的線性一維存儲(chǔ)空間。

內(nèi)存的基木劃分單位是字節(jié)。

每個(gè)字節(jié)具有8位，每一位寄存1個(gè)?；?個(gè)1.

內(nèi)存和編號(hào)是---對(duì)應(yīng)的。

軟件在運(yùn)行前需要向操作系統(tǒng)申請(qǐng)存儲(chǔ)空間。在軟件運(yùn)行期間，該軟件所占空間不再

分派給其他軟件。當(dāng)軟件運(yùn)行完畢后，操作系統(tǒng)將回收該內(nèi)存空間（操作系統(tǒng)并不清空該

內(nèi)存空間中遺留下來的數(shù)據(jù)）。

NOTE：1）指針變量也是變量，一般變量前不能加*,常亮和體現(xiàn)式前不能加&。

2）局部變量只在本函數(shù)內(nèi)部使用。

怎樣通過被調(diào)函數(shù)修改主調(diào)函數(shù)中?般變量的值。

1）實(shí)參為有關(guān)變量的地址；

2）形參為以該變量的類型為類型的指針變量；

3）在被調(diào)函數(shù)中通過*形參變品名的形式的形式就可以修改主函數(shù)。

CASE1

#include<stdio.h>

intmain（void）

{

int^p;〃p是個(gè)變量名字，int*表達(dá)該p變量只能存儲(chǔ)int類型變量的地址

inti=10;

intj;

//j=*P；

//printf（"%d\n",j）;//error,p未指定

//charch='A';

//p=&ch;//error,類型不一致

p=&i;〃p保留i￥j地址，p指向i：修改p的值不影響i的值，修改i的值不影響p

的值；任何場(chǎng)所下，*p和i可以互換。*p等價(jià)于i。

//p=10;//error

j=*P；〃等價(jià)于j=i；

printf（"i=%d,j=%d/p=%d\n"J/j/*p）;

return0;

CASE2

#include<stdio.h>

voidf(int*i)〃不是定義了一種名字叫做*i的形參，而是定義了一種形參，該形參名字叫做

i,它的類型是int*

(

*i=100;

intmain(void)

(

inti=9;

〃局部變量只在本函數(shù)內(nèi)部使用。

printf("i=%d\n",i);

指針和數(shù)字

數(shù)組名：一維數(shù)組名是個(gè)指針變量，它寄存的是一維數(shù)組第一種元素的地址，它的值不能

被變化，一維數(shù)組名指向的是數(shù)組的第一種元素。

CASE1

a[3]==*(3+a);3[a]==*(a+3)==*(3+a);

inta[5]={l,2,3A5};

Show_Aarry(a,5);//a等價(jià)于&a[0],&a[0]自身就是int*類型

voidShow_Array(int+pjntlen)

(

IntI;

//P[2]=-l;//p[O]=*p;p⑵==*(p+2)==*(a+2)==a⑵；p[i]就是主函數(shù)的a[i]

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

printf("%d\n",p[i]);

)

指針變量的運(yùn)算

指針變量不能相加，不能相乘，不能相除。

假如兩指針變量屬于同一數(shù)組，則可以相減。

指針變量可以加減一整數(shù)，前提是最終止果不能超過指針變量

p+i的值是p+i*(p所指向的變量所占的字節(jié)數(shù))

p-i的值是p-i*(p所指向的變量所占的字節(jié)數(shù))

p++<==>p+lp—<==>P-1

6_所有的指針變量只占4個(gè)子節(jié)用第?種字節(jié)的地址表達(dá)整個(gè)變量的地址

CASE1

double*p;

doublex=66.6;〃一種double占8個(gè)字節(jié)

p=&x;//x占8個(gè)字節(jié)，1個(gè)字節(jié)是8位，1個(gè)字節(jié)一種地址，p內(nèi)只寄存了一種地址，一般

是字節(jié)的首地址

doublearr[3]={l.l,2.2,3.3};

double*q;

q=&arr[0];

printf("％p\n〃,q);〃％p實(shí)際就是以十六進(jìn)制輸出

q=&arr[l];

q=printf(//%p\n,；q);〃p,q相差8

無論指針指向的變量占多少個(gè)字節(jié)，指針變量統(tǒng)一都只占4個(gè)字節(jié)

7_怎樣通過函數(shù)修改實(shí)參的值

發(fā)送地址

CASE1修改指針變量的值，只能修改地址

voidf(int**);

intmain(void)

{

inti=9;

int*p=&i;//*p;p=&i;

printf("%p\n",p);

f(&P)；

printf("%p\n",p);

return0;

)

//voidf(int+q)

//{

//q=(int*)Oxffffffff;〃錯(cuò)誤，不會(huì)變化p的值

//)

voidf(int**q)

(

*q=(int*)Oxffffffff;

8一構(gòu)造體的使用概述

構(gòu)造體

為何會(huì)出現(xiàn)構(gòu)造體：

為了表達(dá)某些復(fù)雜的數(shù)據(jù)，而?般的基本類型變量無法滿足規(guī)定

什么叫做構(gòu)造體：

構(gòu)造體是顧客根據(jù)實(shí)際需要自己定義的復(fù)合數(shù)據(jù)類型

怎樣使用構(gòu)造體：

兩種方式——

structStudentst={1000//zhagnsan,,,20};

structStudent*pst=&st;

1)通過構(gòu)造體變最名來實(shí)現(xiàn)

st.sid

2)通過指向構(gòu)造體變量的指針來實(shí)現(xiàn)【1

pst->sid

pst所指向的構(gòu)造體變量中的sid這個(gè)組員

CASE1

#include<stdio.h>

ttinclude<string.h>

structStudent

(

intsid；

charname[200];

intage;

}；〃分號(hào)不能省

Intmain(void)

(

structStudentst={1000/,zhagnsan/,,20};

printf("%d,%s%d\n,”,st.sid,,st.age);

printf("%d,%s%d\n,〃,st);//error

st.sid=99;〃第一種

〃=Tisi";//error

strcpy(/,lisi,,)；

st.age=22;

structStudent*pst;

pst=&st;〃第二種

pst->sid=99;〃pst->等價(jià)于(*pst).sid,rfn(*pst).sid等價(jià)于st.sid,因此pst->sid等

價(jià)于st.sid

Return0;

)

注意事項(xiàng)：

構(gòu)造體變量不能加減乘除，但可以互相賦值

一般構(gòu)造體變量和構(gòu)造體指針變量作為函數(shù)傳參的問題

CASE2

#include<stdio.h>

structStudent

intsid：

charname[200];

intage;

)；

voidf(structStudent*pst);

voidg(structStudentst);

voidg2(structStudent*pst；;

intmain(void)

(

structStudentst;〃己經(jīng)為st分派好了內(nèi)存

f(ast)；

//g(st)；

g2(&st);

//printf(/z%d%s%d\n//,st.sid,,st.age);〃輸出措施一

return0;

)

voidg(structStudentst)〃整體變顯賦值〃輸出措施二，速度慢，耗空間，耗內(nèi)存,不推薦

(

/,

printf("%d%s%d\n,st.sid,/st.age);

)

voidg2(structStudent*pst)

(

//

printf("%d%s%d\n,pst->sid/pst->name/pst->age);

voidf(structStudent*pst)

{

(*pst).sid=99;

strcpy(pst->name/zhagnsan,/)；

pst->age=22;

)

9_malloc()動(dòng)態(tài)分派內(nèi)存概述

動(dòng)態(tài)內(nèi)存的分派和釋放

CASE1

#icclude<stdio.h>

#include<malloc.h>

intmain(void)

(

inta(5)={l,2,3,4,5};〃靜態(tài)數(shù)組

intlen;

printf(“請(qǐng)輸入你需要分派的數(shù)組長(zhǎng)度：len=〃);

scanf("%d”,&len);

int*pArr=(int*)malloc(sizeof(int)*len);〃(int*)為強(qiáng)制轉(zhuǎn)換，強(qiáng)制使pArr指向前四

個(gè)字節(jié)?？梢詫Arr當(dāng)做數(shù)組名來操作

〃*pArr=4;〃類似于a[0]=4;

//pArr⑴=10;〃類似于a[l]=10;

,,

//printf("%d%d\n/*pArr,pArr[l]);

〃我們可以把pArr當(dāng)做一種一般數(shù)組來使用

for(inti=0;i<len;++i)

scanf("%d”,&pAnj;

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

printf(/z%d\nw,*(pArr+i));

free(pArr);〃把pArr所代表的的動(dòng)態(tài)分派的20個(gè)字節(jié)的內(nèi)存釋放

return0;

)

10一跨函數(shù)使用內(nèi)存講解及其示例

CASE1

#include<stdio.h>

intf();

intmain(void)

(

inti=10;

i=f();

printf("i=%d\n〃,i);

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

f()；

return0;

)

intf()

(

intj=20;

returnj;

}

CASE2

main()

(

int*p;

fun(&p);

)

intfun(int**q)

ints;〃s為局部變量。調(diào)用完畢后s就沒有了，最終p沒有指向一種合法的整型

單元

*q=&s;

)

CASE3

main()

(

int*p;

fun(&p);

)

intfun(int**q)

(

*q=(int*)malloc(4);〃返回4個(gè)字節(jié)，只取第1個(gè)字節(jié)地址賦給*q,*q==p0執(zhí)

行完后，由于沒有free。，內(nèi)存沒有釋放。假如沒有free。，整個(gè)程序徹底終止時(shí)才能釋放

)

程序內(nèi)部類定義措施

Aaa=newA();

A*pa=(A*)malloc(sizeof(A));

CASE4

#include<stdio.h>

#include<malloc.h>

structStudent

{

intsid;

intage;

)

structStudent*CreatStudent(void);

voidShowStudent(structStudent*);

intmain(void)

(

structStudent*ps;

ps=CreatStudent();

ShowStudent(ps);

return0;

)

structStudent*CreatStudent(void)

structStudent*P=(structStudent*)malloc(sizeof(structStudent));

p->sid=99;

p->age=88;

returnp;

)

voidShowStudent(structStudent*pst)

{

printf("%d%d\n,,,pst->sid,pst->age);

)

11_復(fù)習(xí)

12_持續(xù)存儲(chǔ)數(shù)組的算法演示」

13一持續(xù)存儲(chǔ)數(shù)組的算法演示_2

模塊一：線性構(gòu)造【把所有的結(jié)點(diǎn)用一根直線穿起來】

1)持續(xù)存儲(chǔ)［數(shù)組］

2)離散存儲(chǔ)［鏈表］

線性構(gòu)造的兩種常見應(yīng)用之一棧

線性構(gòu)造的兩種常見應(yīng)用之二隊(duì)列

專題：遞歸

1.1=2+3+4+...100的和

2.求階乘

3.漢諾塔

4.走迷宮

模塊二：非線性構(gòu)造

樹

圖

持續(xù)存儲(chǔ)［數(shù)組］

1.什么叫數(shù)組

元素類型相似，大小相似

2.數(shù)組的優(yōu)缺陷：

CASE1

#include<stdio.h>

#include<malloc.h>〃包括了malloc函數(shù)

#include<stdlib.h>//包括了exit函數(shù)

〃定義了一種數(shù)據(jù)類型，該數(shù)據(jù)類型的名字叫做structArr,該數(shù)據(jù)類型具有3個(gè)組員，分別

為pBase,len,cnt

structArr

(

int*pBase;〃存儲(chǔ)的是數(shù)組第一種元素的地址

intlen;〃數(shù)組所能容納的最大元素的個(gè)數(shù)

intent;〃目前數(shù)組有效元素的個(gè)數(shù)

//intincrement;〃自動(dòng)增長(zhǎng)因子

voidinit_arr(structArr*pArr,intlength);〃初始化，使pBase指向一種有效的數(shù)組，而不再是垃

圾數(shù)字

boolappend_arr(structArr*pArr,intval);〃追加，也許成功，也許失敗

boolinsert_arr(structArr*pArr,intposjntval);//pos的值從1開始

booldelete_arr(structArr*pArr;intposjnt*pVal);

intget();

boolis_empty(structArr*pArr);〃與否已滿

boolis_full(structArr*pAr);〃與否為空

voidsort_arr(structArr*pArr);〃排序

voidshow_arr(structArr*pArr);〃顯示，分號(hào)不能省

voidinnversion_arr(structArr*pArr);〃倒置

intmain(void)

(

structArrarr;〃只定義沒初始化時(shí)，內(nèi)部二個(gè)變量里都是垃圾數(shù)字

intval;

intposi=2;

intlen=6;

〃init_arr(arr);〃會(huì)輸出垃圾數(shù)字，并不能變化arr的值

//printf("%d\n",arr.len);

init_arr(&arr,len);//會(huì)輸出垃圾數(shù)字，并不能變化arr的值

show_arr(&arr);

append_arr(&arr,li;

append_arr(&arr/-3);

append_arr(&arr,6i;

append_arr(&arr,45);

append_arr(&arr,13);

if(append_arr(&arr,34))

(

printf("追加成功！\n");

)

else

(

print-追加失敗!\n");

)

print"”追加之后的數(shù)組內(nèi)容是:\n“);

show_arr(&arr);

if(delete_arr(&arr/posi,&val))

printf("刪除成功!\n");

printf("ffl除的元索是第％d個(gè)元素\n",posi);

一刪除的元素是:

print%d\n"zval);

)

else

(

printf("刪除失敗!\n");

)

/*

append_arr(&arr,ll;

append_arr(&arr,2j;

append_arr(&arr,3l;

append_arr(&arr,4l;

append_arr(&arr,5i;

insert_arr(&arr,l,99);//pos的值從1開始

*/

/*append_arr(&arr,6l;

append_arr(&arr,7l;

show_arr(&arr);

if(append_arr(&arr,8))

(

print-追加成功!\n");

}

else

{

printf("追加失敗!\n");

)

V

printf("刪除之后的數(shù)組內(nèi)容是:\n")；

show_arr(&arr);

innversion_arr(&anj;〃倒置

printf("倒置之后的數(shù)組內(nèi)容是:\n“);

show_arr(&arr);

sort_arr(&arr);

printf("排序之后的數(shù)組內(nèi)容是:\n");

show_arr(&arr);

return0;

)

voidinit_arr(structArr*pArr,intlength)

//(*pArr).len=99;

pArr->pBase=(int*)malloc(sizeof(int)*length);

if(NULL==pArr->pBase)

{

printf("動(dòng)態(tài)內(nèi)存分派失敗!\n");

exit(-l);〃終止整個(gè)程序

)

else

(

pArr->len=length;

pArr->cnt=O;

)

return;

}

boolis_empty(structArr*pArr)〃與否已滿

(

if(O==pArr->cnt)

returntrue;

else

returnfalse;

voidshow_arr(structArr*pAnj〃顯示

(

//if(數(shù)組為空)

//提醒顧客數(shù)組為空

//else

//輸出數(shù)組有效內(nèi)容

if(is_empty(pArr))//

(

printf(啜組為空!\n“)；

)

else

{

for(inti=O;i<pArr->cnt;i++)

printf("%d",pArr->pBase[i]);

printf("\n");

)

)

boolis_full(structArr*pAnj〃與否為空

if(pArr->cnt==pArr->len)

returntrue;

else

returnfalse;

)

boolappend_arr(structArr*pArr,intval)〃追加，也許成功，也許失敗

(

〃滿時(shí)返回false

if(is_full(pArr))

returnfalse;

〃不滿時(shí)追加

pArr->pBase[pArr->cnt]=val;

(pArr->cnt)++;

returntrue;

}

boolinsert_arr(structArr*pArr;intposjntval)//pos的值從1開始

(

inti;

if(is_full(pArr))

returnfalse;

if(pos<l||pos>pArr->cnt+l)//

returnfalse;

for(i=pArr->cnt-l;i>=pos-l;--i)

{

pArr->pBase[i+l]=pArr->pBase[i];//i賦給i+1

)

pArr->pBase[pos-l]=val;

pArr->cnt++;

returntrue;

)

booldelete_arr(structArr*pArr,intposjnt*pVal)

(

inti;

if(is_empty(pArr))

returnfalse;

if(pos<l||pos>pArr->cnt)

returnfalse;

*pVal=pArr->pBase[pos-l];

for(i=pos;i<pArr->cnt;++i)

{

pArr->pBase[i-l]=pArr->pBase[i];

)

pArr->cnt-;

returntrue;

)

voidinnversion_arr(structArr*pArr)〃倒置

(

inti=0;

intj=pArr->cnt-l;

intt;

while(i<j)

(

t=pArr->pDase[i];

pArr->pBase[i]=pArr->pBase[j];

pArr->pBase[j]=t;

++i；

"j；

)

return;

)

voidsort_arr(structArr*pArr)〃排序

(

int

for(i=0;i<pArr->cnt;++i)

(

for(j=i+l;j<pArr->cnt;++j)

(

if(pArr->pBase[i]>pArr->pBase[j])

|

t=pArr->pBase[i];

pArr->pBase[i]=pArr->pBase(j);

pArr->pBase[j]=t;

)

)

)

14_鏈表的重要性

15_typedef的使用方法

CASE1

#include<stdio.h>

typedefintZHAGN5AN;〃為int再重新多取一種名字，ZHAGNSAN等價(jià)于int

typedefstructStudent

{

intsid;

charname[100];

charsex;

}ST;

intmain(void)

{

inti=10;〃等價(jià)于ZHANGSANi=10;

//ZHAGNSANj=20;

//printf("%d\n"J);

structStudentst;〃等價(jià)于STst；

structStudent*ps=&st;〃等價(jià)于ST*ps;

STst2;

st2.sid=2OO;

printf("%d\n"/st2.sid);

return0;

CASE2

#include<stdio.h>

typedefintZHAGNSAN;〃為int再重新多取一種名字，ZHAGNSAN等價(jià)于int

typedefstructStudent

intsid;

charname[100];

charsex;

}*PST;//PST等價(jià)于structStudent*

intmain(void)

{

structStudentst;〃等價(jià)于STst；

PSTps=&st;

ps->sid=99;

printf("%d\n",ps->sid);

return0;

CASE3

#include<stdio.h>

typedefintZHAGNSAN;〃為int再重新多取一種名字，ZHAGNSAN等價(jià)于int

typedefstructStudent

intsid;

charname[100];

charsex;

等價(jià)于代表了

}*PSTU,STU;//PSTUstructStudent*ZSTUstructStudent

intmain(void)

STUst;〃相稱于structSrudentst;

PSTUps=&st;〃相稱于structSrudent*ps=&st;

ps->sid=99;

printf("%d\n",ps->sid);

return0;

)

16—鏈表的定義

定義：

Ilei

n個(gè)節(jié)點(diǎn)離散分配一?

彼此通過指針相連，二

每個(gè)節(jié)點(diǎn)只有一個(gè)前建節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)月后續(xù)節(jié)點(diǎn)

首節(jié)點(diǎn)沒有前驅(qū)節(jié)點(diǎn)尾節(jié)點(diǎn)沒有后續(xù)節(jié)詢飛二

n個(gè)節(jié)點(diǎn)離散分派；彼此通過指針相連；每個(gè)節(jié)點(diǎn)只有一種后續(xù)節(jié)點(diǎn)，首節(jié)點(diǎn)沒有

前驅(qū)節(jié)點(diǎn)，尾節(jié)點(diǎn)沒有后續(xù)節(jié)點(diǎn)。

專業(yè)術(shù)語：

首節(jié)點(diǎn)：第一種有效節(jié)點(diǎn)

尾節(jié)點(diǎn)：最終一種有效節(jié)點(diǎn)

頭節(jié)點(diǎn)：頭節(jié)點(diǎn)的數(shù)據(jù)類型和首節(jié)點(diǎn)的數(shù)據(jù)類型相似。第一種有效節(jié)點(diǎn)之前的那個(gè)節(jié)

點(diǎn)；頭節(jié)點(diǎn)并不寄存寄存有效數(shù)據(jù)；加頭節(jié)點(diǎn)的目重要是為了以便對(duì)鏈表的操作。

頭指針：指向頭節(jié)點(diǎn)的指針變最

尾指針：指向尾節(jié)點(diǎn)的指針變量

頭節(jié)點(diǎn)-首節(jié)點(diǎn)。?！?。。。尾節(jié)點(diǎn)【頭節(jié)點(diǎn)并沒有存儲(chǔ)有效數(shù)據(jù)，也沒有寄存鏈表中

有效節(jié)點(diǎn)的個(gè)數(shù)。首節(jié)點(diǎn)開始寄存有效數(shù)據(jù)。在鏈表前邊加一種沒有實(shí)際意義的頭節(jié)點(diǎn)，

可以以便對(duì)鏈表的操作。頭節(jié)點(diǎn)于之后節(jié)點(diǎn)的數(shù)據(jù)類型相似】

分類：

算法：

鏈表的優(yōu)缺陷：

17_假如但愿通過一種函數(shù)來對(duì)鏈表進(jìn)行處理，我們至少需要接受鏈表的哪些參數(shù)

假如但愿通過一種函數(shù)來對(duì)鏈表進(jìn)行處理，我們至少需要接受鏈表的哪些參數(shù)

只需要一種參數(shù)：頭指針

由于我們通過頭指針可以推算出鏈表的其他所有參數(shù)

18—每一種鏈表節(jié)點(diǎn)的數(shù)據(jù)類型該怎樣表達(dá)的問題

CASE1

#include<stdio.h>

typedefstructNode

{

intdata;〃數(shù)據(jù)域

structNode*pNext;〃指針域

}NODE,*PNODE;//NODE等價(jià)于structNode,PNODE等價(jià)于structNode

intmain(void)

(

return0;

)

19一鏈表的分類

分類：

單鏈表：每個(gè)鏈表的指針域只能指向背面的節(jié)點(diǎn)

雙鏈表：每一種節(jié)點(diǎn)有兩個(gè)指針域

循環(huán)鏈表：能通過任何?種節(jié)點(diǎn)找到其他所有的結(jié)點(diǎn)

非循環(huán)鏈表：

20_非循環(huán)單鏈表插入節(jié)點(diǎn)偽算法講解

算法：

遍歷

查找

清空

銷毀

求長(zhǎng)度

排序

刪除節(jié)點(diǎn)

插入節(jié)點(diǎn)

插入算法l)r=p->pNext;p->Next=q;q->pNe>:t=r;

插入算法2)q->Next=p->pNext;p->Next=q;1p,q不是節(jié)點(diǎn)，是指針變量】

21_刪除非循環(huán)單鏈表節(jié)點(diǎn)偽算法的講解

刪除

算法1(不采用)：

p

p->pNext=p->pNext->pNext;//J^易導(dǎo)致內(nèi)存泄露，沒有釋放內(nèi)存

算法2：先臨時(shí)定義一種指向p背面節(jié)點(diǎn)的指針r

r=p->pNext;

p->pNext=p->pNext->pNext;

free(r);

鏈表中每個(gè)結(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu)【預(yù)備知識(shí)】

typedefstructnode

intdata;〃存儲(chǔ)數(shù)據(jù)本身

structnode*pNext;//pNext指向一個(gè)和它本身存儲(chǔ)指向下一個(gè)

結(jié)點(diǎn)的指針

}NODE,*PNODE;

■解釋：

■NODE等價(jià)于structnode

■PNODE等價(jià)于structnode*

PNODEp=(PNODE)malloc(sizeof(NODE));

■解祥，

■將動(dòng)態(tài)分配的新節(jié)點(diǎn)的地址賦給P

free討//刪除p指向結(jié)點(diǎn)所占的內(nèi)存，不是刪除p本身所占內(nèi)存—

p->pNext;〃p所指向結(jié)構(gòu)體變量中的pNext成員本身

22一學(xué)習(xí)數(shù)據(jù)構(gòu)造的目的和要到達(dá)的規(guī)定

23一復(fù)習(xí)

24一鏈表創(chuàng)立和鏈表遍歷克法的演示

#include<stdio.h>

#include<malloc.h>

#include<stdlib.h>

typedefstructNode

{

intdata;〃數(shù)據(jù)域

structNode*pNext;〃指針域

}NODE,*PNODE;//NODE等價(jià)于structNode,PNODE等價(jià)于structNode*

〃函數(shù)申明

PNODEcreatejist(void);

voidtraverse_list(PNODEpHead);

intmain(void)

(

PNODEpHead=NULL;〃等價(jià)于structNode*pHead=NULL：

pHead=create」ist();〃creat_list()功能：創(chuàng)立一種非循環(huán)單鏈表,并將該鏈表的頭節(jié)點(diǎn)

的地址付給pHead

traverse_list(pHead);

return0;

PNODEcreate_list(void)

(

intlen;〃用來寄存有效節(jié)點(diǎn)的個(gè)數(shù)

inti;

intval;〃用來臨時(shí)寄存顧客輸入的節(jié)點(diǎn)的值

〃分派了一種不寄存有效數(shù)據(jù)的頭節(jié)點(diǎn)

PNODEpHead=(PNODE)malloc(sizeof(NODE));

if(NULL==pHead)

{

printf("分派失敗，程序終止!\n")；

exit(-l);

)

PNODEpTail=pHead;

pTail->pNext=NULL;

printf("請(qǐng)輸入您需要生成的鏈表節(jié)點(diǎn)的個(gè)數(shù)：len=");

scanf("%d",&len)；

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

{

printf("請(qǐng)輸入第％d個(gè)節(jié)點(diǎn)的值:",i+l);

scanf("%d"z&val);

PNODEpNew=(PNODE)malloc(sizeof(NODE));

if(NULL==pNew)

{

printf("分派失敗,程序終止!\n')；

exit(-l);

)

pNew->da:a=val;//S

pTail->pNext=pNew;

pNew->pNext=NULL;

pTail=pNew;

}

returnpHead;

)

voidtraverse_list(PNODEpHead)

{

PNODEp=pHead->oNext;

while(NULL!=p)

printf(%d,p->data);

p=p->pNext;〃不持續(xù)，不能用p++

)

printf("\n")；

return;

)

主

入你

壁切

、

鏈

表

點(diǎn)的

個(gè)數(shù)

節(jié)

s總A,

I-A

目

K開len=4

篝

點(diǎn)

直

\主A

I-1T3

EDK二

第

占

主

A節(jié)s

,sJ

T-2lz2

目

A」&:

主

第

煮

節(jié)s

T-3y4

D二&:

EKA道

主

，

第

點(diǎn)

i節(jié)

T-4「/,6

EBK二

3246A

pressanyyt

Ke

25_判斷鏈表與否為空和求鏈表長(zhǎng)度算法的演示

#include<stdio.h>

#include<malloc.h>

#include<stdlib.h>

typedefstructNode

{

intdata;〃數(shù)據(jù)域

structNode*pNext;〃指針域

}NODE,*PNODE;//NODE等價(jià)于structNode,PNODE等價(jià)于structNode

〃函數(shù)申明

PNODEcreatejist(void);

voidtraverse_list(PNODEpHead);

boolis_empty(PNODEpHead);

intlengthJist(PNODE);

boolinsertJist(PNODEJntJnt);

booldeleteJistfPNODEJntJnt*);

voidsort_list(PNODE);

intmain(void)

(

PNODEpHead=NULL;〃等價(jià)于structNode*pHead=NULL：

pHead=create」ist();〃creat_list()功能：創(chuàng)立一種非循環(huán)單鏈表,并將該鏈表的頭節(jié)點(diǎn)

的地址付給pHead

traverse_list(pHead);

intlen=length_list(pHead);

printf("鏈表長(zhǎng)度是％5七所);

if(is_empty(pHead))

printf("鏈表為空!\n");

else

printf("鏈表不空！\n");

return0;

)

PNODEcreatejist(void)

(

intlen;〃用來寄存有效節(jié)點(diǎn)的個(gè)數(shù)

inti;

intval;〃用來臨時(shí)寄存顧客輸入的節(jié)點(diǎn)的值

〃分派了一種不寄存有效數(shù)據(jù)的頭節(jié)點(diǎn)

PNODEpHead=(PNODE)malloc(sizeof(NODE));

if(NULL==pHead)

{

printf("分派失敗，程序終止!\n");

exit(-l);

)

PNODEpTail=pHead;

pTail->pNext=NULL;

printf("請(qǐng)輸入您需要生成的鏈表節(jié)點(diǎn)的個(gè)數(shù)：len=");

scanf("%d",&len);

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

(

printf("請(qǐng)輸入第％d個(gè)節(jié)點(diǎn)的值匚i+1);

scanf("%d",&val);

PNODEpNew=(PNODE)malloc(sizeof(NODE));

if(NULL==pNew)

(

printf("分派失敗，程序終止!\n")；

exit(-l);

)

pNew->da:a=val;〃掛

pTail->pNext=pNew;

pNew->pNext=NULL;

pTail=pNew;

)

returnpHead;

voidtraverse_list(PNODEpHead)

(

PNODEp=pHead->3Next;

while(NULL!=p)

(

printf("%d",p->data);

p=p->pNext;〃不持續(xù)，不能用p++

)

printf("\n");

return;

)

boolis_empty(PNODEpHead)

(

if(pHead->pNext==NULL)

returntrue;

else

returnfalse;

)

intlength_list(PNODEpHead)

{

PNODEp=pHead->oNext;

intlen=0;

while(NULL!=p)

(

len++;

p=p->pNe>:t;

)

returnlen;

)

的

、怵

品

苴

入

你

京-

月len=4

值

點(diǎn)

入

第

主1k?5

月

z4值

點(diǎn)

入

第

?

主2D3

月

】

值

點(diǎn)

入

第

苴36

月

rl值

點(diǎn)

入

第I

主4Y1

產(chǎn)

>61rs

二

是

連

長(zhǎng)

度4

人

—

連Is

不

二

工

ASyey

an

26.通過鏈表排序算法的演示再次詳細(xì)討論究竟什么是算法以及究竟什么是泛型【巾產(chǎn)】

算法:

狹義的算法是與數(shù)據(jù)的存儲(chǔ)方式親密有關(guān)

廣義的算法是與數(shù)據(jù)的存儲(chǔ)方式無關(guān)

泛型：

運(yùn)用某種技術(shù)到達(dá)的效果就是：不一樣的存儲(chǔ)方式，執(zhí)行的操作是同樣的

#include<stdio.h>

#include<malloc.h>

#include<stdlib.h>

typedefstructNode

{

intdata;〃數(shù)據(jù)域

structNode*pNext;〃指針域

}NODE,*PNODE;//NODE等價(jià)于structNode,PNODE等價(jià)于structNode

〃函數(shù)申明

PNODEcreate_list(void);

voidtraverse_list(PNODEpHead);

boolis_empty(PNODEpHead);

intlength_list(PNODE);

boolinsert_list(PNODE,int,int);

booldeleteJistfPNODEJntJnt*);

voidsort_list(PNODE);

intmain(void)

(

PNODEpHead=NULL;〃等價(jià)于structNode*pHead=NULL；

pHead=create」ist();〃creat_list()功能：創(chuàng)立一種非循環(huán)單鏈表,并將該鏈表的頭號(hào)點(diǎn)

的地址付給pHead

traverseJist(pHead);

intlen=length_list(pHead);

printf("鏈表長(zhǎng)度是％d\n'漫n);

if(is_empty(pHead))

printf("鏈表為空!\n");

else

printf("鏈表不空!\n")；

sort_list(pHead);

traverseJist(pHead);

return0;

)

PNODEcreatejist(void)

(

intlen;〃用來寄存有效節(jié)點(diǎn)的個(gè)數(shù)

inti;

intval;〃用來臨時(shí)寄存顧客輸入的節(jié)點(diǎn)的值

〃分派了一種不寄存有效數(shù)據(jù)的頭節(jié)點(diǎn)

PNODEpHead=(PNODE)malloc(sizeof(NODE));

if(NULL==pHead)

(

printf("分派失敗,程序終止!\n");

exit(-l);

)

PNODEpTail=pHead;

pTail->pNext=NULL;

printf("請(qǐng)輸入您需要生成的鏈表節(jié)點(diǎn)的個(gè)數(shù)：len=");

scanf("%d",&len);

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

{

printf("請(qǐng)輸入第％d個(gè)節(jié)點(diǎn)的值\i+l);

scanf("%d",&val);

PNODEpNew=(PNODE)malloc(sizeof(NODE));

if(NULL==pNew)

(

printf(“分派失敗，程序終止！\n")；

exit(-l);

)

pNew->da:a=val;//fi

pTail->pNext=pNew;

pNew->pNext=NULL;

pTail=pNew;

)

returnpHead;

voidtraverse_list(PNODEpHead)

(

PNODEp=pHead->oNext;

while(NULL!=p)

{

printf("%d",p->data);

p=p->pNext;〃不持續(xù)，不能用p++

)

printf("\n");

return;

)

boolis_empty(PNODEpHead)

{

if(pHead->pNext==NULL)

returntrue;

else

returnfalse;

)

intlength_list(PNODEpHead)

(

PNODEp=pHead->oNext;

intlen=0;

while(NULL!=p)

{

len++;

p=p->pNext;

)

returnlen;

)

voidsort_list(PNODEpHead)

(

int

intlen=length_list(pHead);

PNODEp,q;

for(i=0,p=pHead->pNext;i<len-l;++izp=p->pNext)

(

for(j=i+l,q=p->pNext;j<len;++j,q=q->pNexti

if(p->data>q->data)〃類似于數(shù)組中的：a[i]>a[j]

t=p->data;〃類似于數(shù)組中的:t=a[i);

p->data=q->data;〃類似于數(shù)組中的：a[i]=a[j];

q?>data=t;〃類似于數(shù)組中的:a[j]=t;

入

領(lǐng)

訶

學(xué)

將

皆

需

474

值

入

第

武7

8&?

值

入

第I4

嘉.

點(diǎn)「

I

I值

入

第

」9

點(diǎn)

】

制

I值

入

”

第2

fn

492I

是

度

長(zhǎng)

表

不

！

空

表

479

O

27一怎樣學(xué)習(xí)算法自己的某些感想

28_鏈表插入和刪除算法的演示

#include<stdio.h>

#include<malloc.h>

#include<stdlib.h>

typedefstructNode

(

intdata;〃數(shù)據(jù)域

structNode*pNext;//J旨針域

}NODE,*PNODE;//NODE等價(jià)于structNode,PNODE等價(jià)于structNode*

〃函數(shù)申明

PNODEcreate_list(void);

voidtraverse_list(PNODEpHead);

boolis_empty(PNODEpHead);

intlength_list(PNODE);

boolinsert_list(PNODE,intJnt);

booldelete_list(PNODE/int/int*);

voidsortJist(PNODE);

intmain(void)

(

PNODEpHead=NULL;〃等價(jià)于structNode*pHead=NULL；

intval;

pHead=create」ist();〃creat_list()功能：創(chuàng)立一種非循環(huán)單鏈表,并將該鏈表的頭節(jié)點(diǎn)

的地址付給pHead

traverse_list(pHead);

intlen=length_list(pHead);

printf("鏈表長(zhǎng)度是％5己,廝);

if(is_empty(pHead))

printf("鏈表為空!\n");

else

printf("鏈表不空！\n");

sort_list(pHead);

traverse_list(pHead);

insert_list(pHead,4,33);

traverse_list(pHead);

if(delete_list(pHead,4,&val))

(

printf("刪除成功，您刪除的元素是：%d\n",val);

)

else

{

printf("刪除失??！您刪除的元素不存在!\n“)；

)

traverse_list(pHead);

return0;

)

PNODEcreatejist(void)

{

intlen;〃用來寄存有效節(jié)點(diǎn)的個(gè)數(shù)

inti;

intval;〃川來臨時(shí)寄存顧客輸入的節(jié)點(diǎn)的值

〃分派了一種不寄存有效數(shù)據(jù)的頭節(jié)點(diǎn)

PNODEpHead=(PNODE)malloc(sizeof(NODE));

if(NULL==pHead)

(

printf("分派失敗，程序終止！\n");

exit(-l);

)

PNODEpTail=pHead;

pTail->pNext=NULL;

printf("請(qǐng)輸入您需要生成的鏈表節(jié)點(diǎn)的個(gè)數(shù)：len=")；

scanf("%d",&len);

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

printf(嘴輸入第％d個(gè)節(jié)點(diǎn)的值:",i+l);

scanf(”%d",&val);

PNODEpNew=(PNODE)malloc(sizeof(NODE));

if(NULL==pNew)

(

printf("分派失敗，程序終止！\n');

exit(-l);

)

pNew->da:a=val;//tfe

pTail->pNext=pNew;

pNew->pNext=NULL;

pTail=pNew;

)

returnpHead;

}

voidtraverse_list(PNODEpHead)

(

PNODEp=pHead->3Next;

while(NULL!=p)

(

printf("%d",p->data);

p=p->pNext;〃不持續(xù)，不能用p++

)

printf("\n");

return;

)

boolis_empty(PNODEpHead)

(

if(pHead->pNext==NULL)

returntrue;

else

returnfalse;

)

intlength_list(PNODEpHead)

{

PNODEp=pHead->oNext;

intlen=0;

while(NULL!=p)

Ien++;

p=p->pNext;

)

returnlen;

)

voidsort_list(PNODEpHead)

(

int