郝斌數(shù)據(jù)結(jié)構(gòu)自學(xué)筆記--知識(shí)點(diǎn)+程序源代碼

1、郝斌數(shù)據(jù)結(jié)構(gòu)自學(xué)筆記-知識(shí)點(diǎn)+程序源代碼2015.12 By-HZM1_什么叫做數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)概述定義我們?nèi)绾伟熏F(xiàn)實(shí)中大量而復(fù)雜的問題以特定的數(shù)據(jù)類型和特定的存儲(chǔ)結(jié)構(gòu)保存到主存儲(chǔ)器（內(nèi)存）中，以及在此基礎(chǔ)上為實(shí)現(xiàn)某個(gè)功能（比如查找某個(gè)元素，刪除某個(gè)元素，對(duì)所有元素進(jìn)行排序）而執(zhí)行的相應(yīng)操作，這個(gè)相應(yīng)的操作也叫算法。數(shù)據(jù)結(jié)構(gòu)=個(gè)體的存儲(chǔ)+個(gè)體的關(guān)系存儲(chǔ)算法=對(duì)存儲(chǔ)數(shù)據(jù)的操作2_衡量算法的標(biāo)準(zhǔn)算法解題的方法和步驟衡量算法的標(biāo)準(zhǔn)1）時(shí)間復(fù)雜度：大概程序執(zhí)行的次數(shù)，而非執(zhí)行的時(shí)間2）空間復(fù)雜度：算法執(zhí)行過程中大概所占用的最大內(nèi)存3）難易程度4）健壯性3_數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)數(shù)據(jù)結(jié)構(gòu)的地位數(shù)據(jù)結(jié)構(gòu)是軟件中最

2、核心的課程程序=數(shù)據(jù)的存儲(chǔ)+數(shù)據(jù)的操作+可以被計(jì)算機(jī)執(zhí)行的語(yǔ)言4_預(yù)備知識(shí)_指針_15_預(yù)備知識(shí)_指針_2指針的重要性：指針是C語(yǔ)言的靈魂定義：地址：地址是內(nèi)存單元的編號(hào),從0開始的非負(fù)整數(shù)，范圍：0-FFFFFFFF【0-4G-1】CPU=地址線，控制線，數(shù)據(jù)線=內(nèi)存指針：指針就是地址，地址就是指針。指針變量是存放內(nèi)存單元地址的變量。指針的本質(zhì)是一個(gè)操作受限的非負(fù)整數(shù)。分類：1.基本類型的指針2.指針和數(shù)組的關(guān)系變量并不一定連續(xù)分配，隨機(jī)分配內(nèi)存。內(nèi)存：內(nèi)存是多字節(jié)組成的線性一維存儲(chǔ)空間。內(nèi)存的基本劃分單位是字節(jié)。每個(gè)字節(jié)含有8位，每一位存放1個(gè)0或1個(gè)1.內(nèi)存和編號(hào)是一一對(duì)應(yīng)的。軟件在運(yùn)行

3、前需要向操作系統(tǒng)申請(qǐng)存儲(chǔ)空間。在軟件運(yùn)行期間，該軟件所占空間不再分配給其他軟件。當(dāng)軟件運(yùn)行完畢后，操作系統(tǒng)將回收該內(nèi)存空間（操作系統(tǒng)并不清空該內(nèi)存空間中遺留下來的數(shù)據(jù)）。NOTE：1）指針變量也是變量，普通變量前不能加*，常亮和表達(dá)式前不能加&。2）局部變量只在本函數(shù)內(nèi)部使用。如何通過被調(diào)函數(shù)修改主調(diào)函數(shù)中普通變量的值。1）實(shí)參為相關(guān)變量的地址；2）形參為以該變量的類型為類型的指針變量；3）在被調(diào)函數(shù)中通過 *形參變量名的形式 的形式就可以修改主函數(shù)。CASE 1#include<stdio.h>int main(void)int *p;/p是個(gè)變量名字，int*表示該p變

4、量只能存儲(chǔ)int類型變量的地址int i=10;int j;/j=*p;/printf("%dn",j);/error,p未指定/char ch='A'/p=&ch;/error，類型不一致p=&i; /p保存i的地址，p指向i；修改p的值不影響i的值，修改i的值不影響p的值；任何場(chǎng)合下，*p和i可以互換。*p等價(jià)于i。/p=10;/errorj=*p;/等價(jià)于j=i;printf("i=%d,j=%d,*p=%dn",i,j,*p); return 0;CASE 2#include<stdio.h>void

5、f(int * i)/不是定義了一個(gè)名字叫做*i的形參，而是定義了一個(gè)形參，該形參名字叫做i，它的類型是int*i=100;int main(void)int i=9;f(&i);/局部變量只在本函數(shù)內(nèi)部使用。printf("i=%dn",i);指針和數(shù)字?jǐn)?shù)組名：一維數(shù)組名是個(gè)指針變量，它存放的是一維數(shù)組第一個(gè)元素的地址，它的值不能被改變，一維數(shù)組名指向的是數(shù)組的第一個(gè)元素。CASE 1a3=*(3+a); 3a =*(a+3)=*(3+a);int a5=1,2,3,4,5;Show_Aarry(a,5);/a等價(jià)于&a0,&a0本身就是int*類

6、型void Show_Array(int * p,int len)Int I;/P2=-1;/ p0=*p ; p2=*(p+2)=*(a+2)=a2 ; pi就是主函數(shù)的aifor (i=0;i<lem;i+)printf(“%dn”,pi);指針變量的運(yùn)算指針變量不能相加，不能相乘，不能相除。如果兩指針變量屬于同一數(shù)組，則可以相減。指針變量可以加減一整數(shù)，前提是最終結(jié)果不能超過指針變量p+i的值是p+i*(p所指向的變量所占的字節(jié)數(shù))p-i的值是p-i*(p所指向的變量所占的字節(jié)數(shù))p+<=>p+1 p-<=>P-16_所有的指針變量只占4個(gè)子節(jié) 用第一個(gè)字節(jié)

7、的地址表示整個(gè)變量的地址CASE 1double *p;double x=66.6;/一個(gè)double占8個(gè)字節(jié)p=&x;/x占8個(gè)字節(jié)，1個(gè)字節(jié)是8位，1個(gè)字節(jié)一個(gè)地址，p內(nèi)只存放了一個(gè)地址，通常是字節(jié)的首地址double arr3=1.1,2.2,3.3;double *q;q=&arr0;printf(“%pn”,q); /%p實(shí)際就是以十六進(jìn)制輸出q=&arr1;q=printf(“%pn”,q);/p,q相差8無(wú)論指針指向的變量占多少個(gè)字節(jié)，指針變量統(tǒng)一都只占4個(gè)字節(jié)7_如何通過函數(shù)修改實(shí)參的值發(fā)送地址CASE 1 修改指針變量的值，只能修改地址void f(

8、int *);int main(void)int i=9;int *p=&i;/*p;p=&i;printf(“%pn”,p);f(&p); printf(“%pn”,p);return 0;/void f(int *q)/q=(int *)0xffffffff; /錯(cuò)誤，不會(huì)改變p的值/void f(int * q)*q=(int *)0xffffffff; 8_結(jié)構(gòu)體的使用概述結(jié)構(gòu)體為什么會(huì)出現(xiàn)結(jié)構(gòu)體：為了表示一些復(fù)雜的數(shù)據(jù)，而普通的基本類型變量無(wú)法滿足要求什么叫做結(jié)構(gòu)體：結(jié)構(gòu)體是用戶根據(jù)實(shí)際需要自己定義的復(fù)合數(shù)據(jù)類型如何使用結(jié)構(gòu)體：兩種方式struct Stude

9、nt st=1000,”zhagnsan”,20;struct Student*pst=&st;1)通過結(jié)構(gòu)體變量名來實(shí)現(xiàn)st.sid2)通過指向結(jié)構(gòu)體變量的指針來實(shí)現(xiàn)【重點(diǎn)】pst->sidpst所指向的結(jié)構(gòu)體變量中的sid這個(gè)成員CASE 1#include<stdio.h>#include <string.h>struct Studentint sid；char name200;int age;/分號(hào)不能省Int main(void)struct Student st=1000,”zhagnsan”,20;printf(“%d,%s%dn,”,st.

10、sid,,st.age);printf(“%d,%s%dn,”,st);/errorst.sid=99;/第一種/=”lisi”;/error strcpy(,”lisi”);st.age=22;struct Student*pst;pst=&st;/第二種pst->sid=99;/pst->等價(jià)于(*pst).sid，而(*pst).sid等價(jià)于st.sid，所以pst->sid等價(jià)于st.sidReturn 0;注意事項(xiàng)：結(jié)構(gòu)體變量不能加減乘除，但可以相互賦值普通結(jié)構(gòu)體變量和結(jié)構(gòu)體指針變量作為函數(shù)傳參的問題CASE 2#i

11、nclude<stdio.h>struct Studentint sid；char name200;int age;void f(struct Student *pst);void g(struct Student st);void g2(struct Student *pst);int main (void)struct Student st;/已經(jīng)為st分配好了內(nèi)存f(&st);/g(st);g2(&st);/ printf(“%d %s %dn”,st.sid,,st.age);/輸出方法一return 0;void g(struct Stude

12、nt st)/整體變量賦值/輸出方法二，速度慢，耗空間，耗內(nèi)存，不推薦printf(“%d %s %dn”,st.sid,,st.age);void g2(struct Student *pst)printf(“%d %s %dn”,pst->sid,pst->name,pst->age);void f(struct Student *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)存的分配和釋放CASE 1#icclude<stdi

13、o.h>#include<malloc.h>int main(void)int a5=1,2,3,4,5;/靜態(tài)數(shù)組int len;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;/類似于a0=4;/pArr1=10;/類似于a1=10;/printf(“%d %dn”,*pArr,pArr1);/我們可以把pArr當(dāng)做一個(gè)普通數(shù)組來使用f

14、or (int i=0;i<len;+i)scanf(“%d”,&pArr);for (i=0;i<len;+i)printf(“%dn”,*(pArr+i);free(pArr);/把pArr所代表的的動(dòng)態(tài)分配的20個(gè)字節(jié)的內(nèi)存釋放return 0;10_跨函數(shù)使用內(nèi)存講解及其示例CASE 1#include<stdio.h>int f();int main(void)int i=10;i=f();printf(“i=%dn”,i);for(i=0;i<2000;+i)f();return 0;int f()int j=20;return j;CASE

15、2main ()int *p;fun(&p);.int fun (int *q)int s; /s為局部變量。調(diào)用完畢后s就沒有了，最終p沒有指向一個(gè)合法的整型單元*q=&s;CASE 3main()int *p;fun(&p);.int fun(int *q)*q=(int *)malloc(4);/返回4個(gè)字節(jié)，只取第1個(gè)字節(jié)地址賦給*q，*q=p。執(zhí)行完后，因?yàn)闆]有free()，內(nèi)存沒有釋放。如果沒有free()，整個(gè)程序徹底終止時(shí)才能釋放程序內(nèi)部類定義方法A aa=new A();A *pa=(A*)malloc(sizeof(A);CASE 4#include

16、<stdio.h>#include<malloc.h>struct Studentint sid;int age;struct Student * CreatStudent(void);void ShowStudent(struct Student *);int main(void)struct Student *ps;ps=CreatStudent();ShowStudent(ps);return 0;struct Student * CreatStudent(void)struct Student *P=(struct Student *)malloc(sizeof

17、(struct Student);p->sid=99;p->age=88;return p;void ShowStudent(struct Student *pst)printf(“%d %dn”,pst->sid,pst->age);11_復(fù)習(xí)12_連續(xù)存儲(chǔ)數(shù)組的算法演示_113_連續(xù)存儲(chǔ)數(shù)組的算法演示_2模塊一：線性結(jié)構(gòu)【把所有的結(jié)點(diǎn)用一根直線穿起來】1）連續(xù)存儲(chǔ)數(shù)組2）離散存儲(chǔ)鏈表線性結(jié)構(gòu)的兩種常見應(yīng)用之一 棧線性結(jié)構(gòu)的兩種常見應(yīng)用之二 隊(duì)列專題：遞歸1. 1=2+3+4+.100的和2. 求階乘3. 漢諾塔4. 走迷宮模塊二：非線性結(jié)構(gòu)樹圖連續(xù)存儲(chǔ)數(shù)組1. 什么

18、叫數(shù)組元素類型相同，大小相同2. 數(shù)組的優(yōu)缺點(diǎn)：CASE 1#include<stdio.h>#include<malloc.h>/包含了malloc函數(shù)#include<stdlib.h>/包含了exit函數(shù)/定義了一個(gè)數(shù)據(jù)類型，該數(shù)據(jù)類型的名字叫做struct Arr,該數(shù)據(jù)類型含有3個(gè)成員，分別為pBase，len,cntstruct Arrint *pBase;/存儲(chǔ)的是數(shù)組第一個(gè)元素的地址int len;/數(shù)組所能容納的最大元素的個(gè)數(shù)int cnt;/當(dāng)前數(shù)組有效元素的個(gè)數(shù)/int increment;/自動(dòng)增長(zhǎng)因子;void init_arr(s

19、truct Arr *pArr,int length);/初始化,使pBase指向一個(gè)有效的數(shù)組，而不再是垃圾數(shù)字bool append_arr(struct Arr *pArr,int val);/追加，可能成功，可能失敗bool insert_arr(struct Arr *pArr,int pos,int val);/pos的值從1開始bool delete_arr(struct Arr *pArr,int pos,int *pVal);int get();bool is_empty(struct Arr *pArr);/是否已滿bool is_full(struct Arr *pAr)

20、;/是否為空void sort_arr(struct Arr *pArr);/排序void show_arr(struct Arr *pArr);/顯示,分號(hào)不能省void innversion_arr(struct Arr *pArr);/倒置int main (void)struct Arr arr; /只定義沒初始化時(shí)，內(nèi)部三個(gè)變量里都是垃圾數(shù)字int val;int posi=2;int len=6;/init_arr(arr);/會(huì)輸出垃圾數(shù)字，并不能改變arr的值/printf("%dn",arr.len);init_arr(&arr,len);/會(huì)輸出

21、垃圾數(shù)字，并不能改變arr的值show_arr(&arr);append_arr(&arr,1);append_arr(&arr,-3);append_arr(&arr,6);append_arr(&arr,45);append_arr(&arr,13);if(append_arr(&arr,34)printf("追加成功！n");else printf("追加失??！n");printf("追加之后的數(shù)組內(nèi)容是:n");show_arr(&arr);if(delete_a

22、rr(&arr,posi,&val)printf("刪除成功！n");printf("刪除的元素是第%d個(gè)元素n",posi);printf("刪除的元素是：%dn",val);elseprintf("刪除失敗！n");/*append_arr(&arr,1);append_arr(&arr,2);append_arr(&arr,3);append_arr(&arr,4);append_arr(&arr,5);insert_arr(&arr,1,99)

23、;/pos的值從1開始*/*append_arr(&arr,6);append_arr(&arr,7); show_arr(&arr);if(append_arr(&arr,8)printf("追加成功！n");else printf("追加失??！n");*/printf("刪除之后的數(shù)組內(nèi)容是:n");show_arr(&arr);innversion_arr(&arr);/倒置printf("倒置之后的數(shù)組內(nèi)容是:n");show_arr(&arr);so

24、rt_arr(&arr);printf("排序之后的數(shù)組內(nèi)容是:n");show_arr(&arr);return 0;void init_arr(struct Arr *pArr,int length)/(*pArr).len=99;pArr->pBase = (int*)malloc(sizeof(int)*length);if(NULL=pArr->pBase)printf("動(dòng)態(tài)內(nèi)存分配失??！n");exit(-1);/終止整個(gè)程序elsepArr->len=length;pArr->cnt=0;retur

25、n;bool is_empty(struct Arr *pArr)/是否已滿if(0=pArr->cnt)return true;else return false;void show_arr(struct Arr *pArr)/顯示/if(數(shù)組為空)/提示用戶數(shù)組為空/else/輸出數(shù)組有效內(nèi)容if(is_empty(pArr)/printf("數(shù)組為空!n");elsefor(int i=0;i<pArr->cnt;i+)printf("%d ",pArr->pBasei);printf("n");bool

26、 is_full(struct Arr *pArr)/是否為空if(pArr->cnt=pArr->len)return true;elsereturn false;bool append_arr(struct Arr *pArr,int val)/追加，可能成功，可能失敗/滿時(shí)返回falseif(is_full(pArr)return false;/不滿時(shí)追加pArr->pBasepArr->cnt=val;(pArr->cnt)+;return true;bool insert_arr(struct Arr *pArr,int pos,int val)/pos

27、的值從1開始int i;if(is_full(pArr)return false;if(pos<1|pos>pArr->cnt+1)/return false;for (i=pArr->cnt-1;i>=pos-1;-i)pArr->pBasei+1=pArr->pBasei; /i賦給i+1pArr->pBasepos-1=val;pArr->cnt+;return true;bool delete_arr(struct Arr *pArr,int pos,int *pVal)int i;if(is_empty(pArr)return f

28、alse;if(pos<1|pos>pArr->cnt)return false;*pVal=pArr->pBasepos-1;for(i=pos;i<pArr->cnt;+i)pArr->pBasei-1=pArr->pBasei;pArr->cnt-;return true;void innversion_arr(struct Arr *pArr)/倒置int i=0;int j=pArr->cnt-1;int t;while(i<j)t=pArr->pBasei;pArr->pBasei=pArr->pB

29、asej;pArr->pBasej=t;+i;-j;return;void sort_arr(struct Arr *pArr)/排序int i,j,t;for(i=0;i<pArr->cnt;+i)for(j=i+1;j<pArr->cnt;+j)if(pArr->pBasei>pArr->pBasej)t=pArr->pBasei;pArr->pBasei=pArr->pBasej;pArr->pBasej=t;14_鏈表的重要性15_typedef的用法CASE 1#include<stdio.h>typ

30、edefint ZHAGNSAN;/為int再重新多取一個(gè)名字，ZHAGNSAN等價(jià)于inttypedef struct Studentint sid;char name100;char sex;ST;int main(void)int i=10;/等價(jià)于ZHANGSAN i=10;/ZHAGNSAN j=20;/printf("%dn",j);struct Student st;/等價(jià)于ST st；struct Student *ps=&st;/等價(jià)于ST *ps;ST st2;st2.sid=200;printf("%dn",st2.sid)

31、;return 0;CASE 2#include<stdio.h>typedefint ZHAGNSAN;/為int再重新多取一個(gè)名字，ZHAGNSAN等價(jià)于inttypedef struct Studentint sid;char name100;char sex;*PST;/PST等價(jià)于struct Student *int main(void)struct Student st;/等價(jià)于ST st；PST ps=&st;ps->sid=99;printf("%dn",ps->sid);return 0;CASE 3#include<

32、;stdio.h>typedefint ZHAGNSAN;/為int再重新多取一個(gè)名字，ZHAGNSAN等價(jià)于inttypedef struct Studentint sid;char name100;char sex;*PSTU,STU;/PSTU等價(jià)于struct Student *,STU代表了struct Studentint main(void)STU st;/相當(dāng)于struct Srudent st;PSTU ps=&st;/相當(dāng)于struct Srudent *ps=&st;ps->sid=99;printf("%dn",ps-&g

33、t;sid);return 0;16_鏈表的定義定義：n個(gè)節(jié)點(diǎn)離散分配；彼此通過指針相連；每個(gè)節(jié)點(diǎn)只有一個(gè)后續(xù)節(jié)點(diǎn)，首節(jié)點(diǎn)沒有前驅(qū)節(jié)點(diǎn)，尾節(jié)點(diǎn)沒有后續(xù)節(jié)點(diǎn)。專業(yè)術(shù)語(yǔ)：首節(jié)點(diǎn)：第一個(gè)有效節(jié)點(diǎn)尾節(jié)點(diǎn)：最后一個(gè)有效節(jié)點(diǎn)頭節(jié)點(diǎn)：頭節(jié)點(diǎn)的數(shù)據(jù)類型和首節(jié)點(diǎn)的數(shù)據(jù)類型相同。第一個(gè)有效節(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ù)。在鏈表前邊加一個(gè)沒有實(shí)際意義的頭節(jié)點(diǎn)，可以方便對(duì)鏈表的操作。頭節(jié)點(diǎn)于之后節(jié)點(diǎn)的數(shù)

34、據(jù)類型相同】分類：算法：鏈表的優(yōu)缺點(diǎn)：17_如果希望通過一個(gè)函數(shù)來對(duì)鏈表進(jìn)行處理，我們至少需要接受鏈表的哪些參數(shù)如果希望通過一個(gè)函數(shù)來對(duì)鏈表進(jìn)行處理，我們至少需要接受鏈表的哪些參數(shù)只需要一個(gè)參數(shù)：頭指針因?yàn)槲覀兺ㄟ^頭指針可以推算出鏈表的其他所有參數(shù)18_每一個(gè)鏈表節(jié)點(diǎn)的數(shù)據(jù)類型該如何表示的問題CASE 1#include<stdio.h>typedef struct Nodeint data;/數(shù)據(jù)域struct Node * pNext;/指針域NODE,*PNODE;/NODE等價(jià)于struct Node，PNODE等價(jià)于struct Node *int main(void)r

35、eturn 0;19_鏈表的分類分類：?jiǎn)捂湵恚好總€(gè)鏈表的指針域只能指向后面的節(jié)點(diǎn)雙鏈表：每一個(gè)節(jié)點(diǎn)有兩個(gè)指針域循環(huán)鏈表：能通過任何一個(gè)節(jié)點(diǎn)找到其他所有的結(jié)點(diǎn)非循環(huán)鏈表：20_非循環(huán)單鏈表插入節(jié)點(diǎn)偽算法講解算法：遍歷查找清空銷毀求長(zhǎng)度排序刪除節(jié)點(diǎn)插入節(jié)點(diǎn)插入算法1)r=p->pNext;p->Next=q;q->pNext=r;插入算法2)q->Next=p->pNext;p->Next=q;【p，q不是節(jié)點(diǎn)，是指針變量】。21_刪除非循環(huán)單鏈表節(jié)點(diǎn)偽算法的講解刪除算法1（不采用）：p->pNext=p->pNext->pNext;/容易導(dǎo)致

36、內(nèi)存泄露，沒有釋放內(nèi)存算法2：先臨時(shí)定義一個(gè)指向p后面節(jié)點(diǎn)的指針rr=p->pNext;p->pNext=p->pNext->pNext;free(r);22_學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的目的和要達(dá)到的要求23_復(fù)習(xí)24_鏈表創(chuàng)建和鏈表遍歷算法的演示#include<stdio.h>#include<malloc.h>#include<stdlib.h>typedef struct Nodeint data;/數(shù)據(jù)域struct Node * pNext;/指針域NODE,*PNODE;/NODE等價(jià)于struct Node，PNODE等價(jià)于str

37、uct Node */函數(shù)聲明PNODE create_list(void);void traverse_list(PNODE pHead);int main(void)PNODE pHead=NULL;/等價(jià)于struct Node *pHead=NULL；pHead=create_list();/creat_list()功能：創(chuàng)建一個(gè)非循環(huán)單鏈表,并將該鏈表的頭節(jié)點(diǎn)的地址付給pHeadtraverse_list(pHead);return 0;PNODE create_list(void)int len;/用來存放有效節(jié)點(diǎn)的個(gè)數(shù)int i;int val;/用來臨時(shí)存放用戶輸入的節(jié)點(diǎn)的值/

38、分配了一個(gè)不存放有效數(shù)據(jù)的頭節(jié)點(diǎn)PNODE pHead=(PNODE)malloc(sizeof(NODE);if(NULL=pHead)printf("分配失敗，程序終止！n");exit(-1);PNODE pTail=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"

39、,&val);PNODE pNew=(PNODE)malloc(sizeof(NODE);if(NULL=pNew)printf("分配失敗，程序終止！n");exit(-1);pNew->data=val;/掛pTail->pNext=pNew;pNew->pNext=NULL;pTail=pNew;return pHead;void traverse_list(PNODE pHead)PNODE p=pHead->pNext;while(NULL!=p)printf("%d ",p->data);p=p->

40、pNext;/不連續(xù)，不能用p+printf("n");return;25_判斷鏈表是否為空 和 求鏈表長(zhǎng)度 算法的演示#include<stdio.h>#include<malloc.h>#include<stdlib.h>typedef struct Nodeint data;/數(shù)據(jù)域struct Node * pNext;/指針域NODE,*PNODE;/NODE等價(jià)于struct Node，PNODE等價(jià)于struct Node */函數(shù)聲明PNODE create_list(void);void traverse_list(PN

41、ODE pHead);bool is_empty(PNODE pHead);int length_list(PNODE);bool insert_list(PNODE,int,int);bool delete_list(PNODE,int,int*);void sort_list(PNODE);int main(void)PNODE pHead=NULL;/等價(jià)于struct Node *pHead=NULL；pHead=create_list();/creat_list()功能：創(chuàng)建一個(gè)非循環(huán)單鏈表,并將該鏈表的頭節(jié)點(diǎn)的地址付給pHeadtraverse_list(pHead);int le

42、n=length_list(pHead);printf("鏈表長(zhǎng)度是%dn",len);if(is_empty(pHead)printf("鏈表為空！n");else printf("鏈表不空！n");return 0;PNODE create_list(void)int len;/用來存放有效節(jié)點(diǎn)的個(gè)數(shù)int i;int val;/用來臨時(shí)存放用戶輸入的節(jié)點(diǎn)的值/分配了一個(gè)不存放有效數(shù)據(jù)的頭節(jié)點(diǎn)PNODE pHead=(PNODE)malloc(sizeof(NODE);if(NULL=pHead)printf("分配失敗

43、，程序終止！n");exit(-1);PNODE pTail=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);PNODE pNew=(PNODE)malloc(sizeof(NODE);if(NULL=pNew)printf("分配失敗，程序終止！n

44、");exit(-1);pNew->data=val;/掛pTail->pNext=pNew;pNew->pNext=NULL;pTail=pNew;return pHead;void traverse_list(PNODE pHead)PNODE p=pHead->pNext;while(NULL!=p)printf("%d ",p->data);p=p->pNext;/不連續(xù)，不能用p+printf("n");return;bool is_empty(PNODE pHead)if(pHead->pN

45、ext=NULL)return true;elsereturn false;int length_list(PNODE pHead)PNODE p=pHead->pNext;int len=0;while(NULL!=p)len+;p=p->pNext;return len;26_通過鏈表排序算法的演示 再次詳細(xì)討論到底什么是算法以及到底什么是泛型【重點(diǎn)】算法：狹義的算法是與數(shù)據(jù)的存儲(chǔ)方式密切相關(guān)廣義的算法是與數(shù)據(jù)的存儲(chǔ)方式無(wú)關(guān)泛型：利用某種技術(shù)達(dá)到的效果就是：不同的存儲(chǔ)方式，執(zhí)行的操作是一樣的#include<stdio.h>#include<malloc.h&

46、gt;#include<stdlib.h>typedef struct Nodeint data;/數(shù)據(jù)域struct Node * pNext;/指針域NODE,*PNODE;/NODE等價(jià)于struct Node，PNODE等價(jià)于struct Node */函數(shù)聲明PNODE create_list(void);void traverse_list(PNODE pHead);bool is_empty(PNODE pHead);int length_list(PNODE);bool insert_list(PNODE,int,int);bool delete_list(PNOD

47、E,int,int*);void sort_list(PNODE);int main(void)PNODE pHead=NULL;/等價(jià)于struct Node *pHead=NULL；pHead=create_list();/creat_list()功能：創(chuàng)建一個(gè)非循環(huán)單鏈表,并將該鏈表的頭節(jié)點(diǎn)的地址付給pHeadtraverse_list(pHead);int len=length_list(pHead);printf("鏈表長(zhǎng)度是%dn",len);if(is_empty(pHead)printf("鏈表為空！n");else printf(&qu

48、ot;鏈表不空！n");sort_list(pHead);traverse_list(pHead);return 0;PNODE create_list(void)int len;/用來存放有效節(jié)點(diǎn)的個(gè)數(shù)int i;int val;/用來臨時(shí)存放用戶輸入的節(jié)點(diǎn)的值/分配了一個(gè)不存放有效數(shù)據(jù)的頭節(jié)點(diǎn)PNODE pHead=(PNODE)malloc(sizeof(NODE);if(NULL=pHead)printf("分配失敗，程序終止！n");exit(-1);PNODE pTail=pHead;pTail->pNext=NULL;printf("

49、請(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);PNODE pNew=(PNODE)malloc(sizeof(NODE);if(NULL=pNew)printf("分配失敗，程序終止！n");exit(-1);pNew->data=val;/掛pTail->pNext=pNew;pNew->pNext=NUL

50、L;pTail=pNew;return pHead;void traverse_list(PNODE pHead)PNODE p=pHead->pNext;while(NULL!=p)printf("%d ",p->data);p=p->pNext;/不連續(xù)，不能用p+printf("n");return;bool is_empty(PNODE pHead)if(pHead->pNext=NULL)return true;elsereturn false;int length_list(PNODE pHead)PNODE p=pH

51、ead->pNext;int len=0;while(NULL!=p)len+;p=p->pNext;return len;void sort_list(PNODE pHead)int i,j,t;int len=length_list(pHead);PNODE p,q;for(i=0,p=pHead->pNext;i<len-1;+i,p=p->pNext)for(j=i+1,q=p->pNext;j<len;+j,q=q->pNext)if(p->data>q->data)/類似于數(shù)組中的：ai>ajt=p->d

52、ata;/類似于數(shù)組中的：t=ai;p->data=q->data;/類似于數(shù)組中的：ai=aj;q->data=t;/類似于數(shù)組中的：aj=t;27_如何學(xué)習(xí)算法自己的一些感想28_鏈表插入和刪除算法的演示#include<stdio.h>#include<malloc.h>#include<stdlib.h>typedef struct Nodeint data;/數(shù)據(jù)域struct Node * pNext;/指針域NODE,*PNODE;/NODE等價(jià)于struct Node，PNODE等價(jià)于struct Node */函數(shù)聲明PNODE create_list(void);void traverse_list(PNODE pHead);bool is_empty(PNODE pHead);int length_list(PNODE);bool insert_list(PNODE,int,int);bool delete_list(PNODE,int,int*);void sort_list(PNODE);int main(void)PNODE pHead=NULL;/等價(jià)于struct Node *pHead=NULL；int val;pHead=create_list();/creat_list()功能：