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

1、郝斌數(shù)據(jù)結(jié)構(gòu)自學(xué)筆記-知識點(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ù)類型和特定的存儲結(jié)構(gòu)保存到主存儲器（內(nèi)存）中，以及在此基礎(chǔ)上為實(shí)現(xiàn)某個功能（比如查找某個元素，刪除某個元素，對所有元素進(jìn)行排序）而執(zhí)行的相應(yīng)操作，這個相應(yīng)的操作也叫算法。數(shù)據(jù)結(jié)構(gòu)=個體的存儲+個體的關(guān)系存儲算法=對存儲數(shù)據(jù)的操作2_衡量算法的標(biāo)準(zhǔn)算法解題的方法和步驟衡量算法的標(biāo)準(zhǔn)1）時間復(fù)雜度：大概程序執(zhí)行的次數(shù)，而非執(zhí)行的時間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ù)的存儲+數(shù)據(jù)的操作+可以被計(jì)算機(jī)執(zhí)行的語言4_預(yù)備知識_指針_15_預(yù)備知識_指針_2指針的重要性：指針是C語言的靈魂定義：地址：地址是內(nèi)存單元的編號,從0開始的非負(fù)整數(shù)，范圍：0-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é)組成的線性一維存儲空間。內(nèi)存的基本劃分單位是字節(jié)。每個字節(jié)含有8位，每一位存放1個0或1個1.內(nèi)存和編號是一一對應(yīng)的。軟件在運(yùn)行

3、前需要向操作系統(tǒng)申請存儲空間。在軟件運(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#includeint main(void)int *p;/p是個變量名字，int*表示該p變量只能存儲int類型變量的地址int

4、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的值；任何場合下，*p和i可以互換。*p等價于i。/p=10;/errorj=*p;/等價于j=i;printf(i=%d,j=%d,*p=%dn,i,j,*p); return 0;CASE 2#includevoid f(int * i)/不是定義了一個名字叫做*i的形參，而是定義了一個形參，該形參名字叫做i，它的類型是int*i=100;int main(void

5、)int i=9;f(&i);/局部變量只在本函數(shù)內(nèi)部使用。printf(i=%dn,i);指針和數(shù)字?jǐn)?shù)組名：一維數(shù)組名是個指針變量，它存放的是一維數(shù)組第一個元素的地址，它的值不能被改變，一維數(shù)組名指向的是數(shù)組的第一個元素。CASE 1a3=*(3+a); 3a =*(a+3)=*(3+a);int a5=1,2,3,4,5;Show_Aarry(a,5);/a等價于&a0,&a0本身就是int*類型void Show_Array(int * p,int len)Int I;/P2=-1;/ p0=*p ; p2=*(p+2)=*(a+2)=a2 ; pi就是主函數(shù)的aifor (i=0;il

6、em;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個子節(jié) 用第一個字節(jié)的地址表示整個變量的地址CASE 1double *p;double x=66.6;/一個double占8個字節(jié)p=&x;/x占8個字節(jié)，1個字節(jié)是8位，1個字節(jié)一個地址，p內(nèi)只存放了一個地址，通常是字節(jié)的首地址double arr3=1.1

7、,2.2,3.3;double *q;q=&arr0;printf(“%pn”,q); /%p實(shí)際就是以十六進(jìn)制輸出q=&arr1;q=printf(“%pn”,q);/p,q相差8無論指針指向的變量占多少個字節(jié)，指針變量統(tǒng)一都只占4個字節(jié)7_如何通過函數(shù)修改實(shí)參的值發(fā)送地址CASE 1 修改指針變量的值，只能修改地址void f(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;

8、/錯誤，不會改變p的值/void f(int * q)*q=(int *)0xffffffff; 8_結(jié)構(gòu)體的使用概述結(jié)構(gòu)體為什么會出現(xiàn)結(jié)構(gòu)體：為了表示一些復(fù)雜的數(shù)據(jù)，而普通的基本類型變量無法滿足要求什么叫做結(jié)構(gòu)體：結(jié)構(gòu)體是用戶根據(jù)實(shí)際需要自己定義的復(fù)合數(shù)據(jù)類型如何使用結(jié)構(gòu)體：兩種方式struct Student 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這個成員CASE 1#include#include struct

9、 Studentint sid；char name200;int age;/分號不能省Int main(void)struct Student st=1000,”zhagnsan”,20;printf(“%d,%s%dn,”,st.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-等價于(*pst).sid，而(*p

10、st).sid等價于st.sid，所以pst-sid等價于st.sidReturn 0;注意事項(xiàng)：結(jié)構(gòu)體變量不能加減乘除，但可以相互賦值普通結(jié)構(gòu)體變量和結(jié)構(gòu)體指針變量作為函數(shù)傳參的問題CASE 2#includestruct 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);/

11、 printf(“%d %s %dn”,st.sid,,st.age);/輸出方法一return 0;void g(struct Student 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-

12、age=22;9_malloc()動態(tài)分配內(nèi)存概述動態(tài)內(nèi)存的分配和釋放CASE 1#icclude#includeint main(void)int a5=1,2,3,4,5;/靜態(tài)數(shù)組int len;printf(“請輸入你需要分配的數(shù)組長度：len=”);scanf(“%d”,&len);int *pArr=(int *)malloc(sizeof(int)*len);/(int *)為強(qiáng)制轉(zhuǎn)換，強(qiáng)制使pArr指向前四個字節(jié)?？梢詫Arr當(dāng)做數(shù)組名來操作/*pArr=4;/類似于a0=4;/pArr1=10;/類似于a1=10;/printf(“%d %dn”,*pArr,pArr1);

13、/我們可以把pArr當(dāng)做一個普通數(shù)組來使用for (int i=0;ilen;+i)scanf(“%d”,&pArr);for (i=0;ilen;+i)printf(“%dn”,*(pArr+i);free(pArr);/把pArr所代表的的動態(tài)分配的20個字節(jié)的內(nèi)存釋放return 0;10_跨函數(shù)使用內(nèi)存講解及其示例CASE 1#includeint f();int main(void)int i=10;i=f();printf(“i=%dn”,i);for(i=0;i2000;+i)f();return 0;int f()int j=20;return j;CASE 2main ()i

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

15、tint 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(struct Student);p-sid=99;p-age=88;return p;void Sho

16、wStudent(struct Student *pst)printf(“%d %dn”,pst-sid,pst-age);11_復(fù)習(xí)12_連續(xù)存儲數(shù)組的算法演示_113_連續(xù)存儲數(shù)組的算法演示_2模塊一：線性結(jié)構(gòu)【把所有的結(jié)點(diǎn)用一根直線穿起來】1）連續(xù)存儲數(shù)組2）離散存儲鏈表線性結(jié)構(gòu)的兩種常見應(yīng)用之一 棧線性結(jié)構(gòu)的兩種常見應(yīng)用之二 隊(duì)列專題：遞歸1. 1=2+3+4+.100的和2. 求階乘3. 漢諾塔4. 走迷宮模塊二：非線性結(jié)構(gòu)樹圖連續(xù)存儲數(shù)組1. 什么叫數(shù)組元素類型相同，大小相同2. 數(shù)組的優(yōu)缺點(diǎn)：CASE 1#include#include/包含了malloc函數(shù)#include/包

17、含了exit函數(shù)/定義了一個數(shù)據(jù)類型，該數(shù)據(jù)類型的名字叫做struct Arr,該數(shù)據(jù)類型含有3個成員，分別為pBase，len,cntstruct Arrint *pBase;/存儲的是數(shù)組第一個元素的地址int len;/數(shù)組所能容納的最大元素的個數(shù)int cnt;/當(dāng)前數(shù)組有效元素的個數(shù)/int increment;/自動增長因子;void init_arr(struct Arr *pArr,int length);/初始化,使pBase指向一個有效的數(shù)組，而不再是垃圾數(shù)字bool append_arr(struct Arr *pArr,int val);/追加，可能成功，可能失敗boo

18、l 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);/是否為空void sort_arr(struct Arr *pArr);/排序void show_arr(struct Arr *pArr);/顯示,分號不能省void innversion_arr(struct Arr *p

19、Arr);/倒置int main (void)struct Arr arr; /只定義沒初始化時，內(nèi)部三個變量里都是垃圾數(shù)字int val;int posi=2;int len=6;/init_arr(arr);/會輸出垃圾數(shù)字，并不能改變arr的值/printf(%dn,arr.len);init_arr(&arr,len);/會輸出垃圾數(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(

20、append_arr(&arr,34)printf(追加成功！n);else printf(追加失敗！n);printf(追加之后的數(shù)組內(nèi)容是:n);show_arr(&arr);if(delete_arr(&arr,posi,&val)printf(刪除成功！n);printf(刪除的元素是第%d個元素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);

21、insert_arr(&arr,1,99);/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);sort_arr(&arr);printf(排序之后的數(shù)組內(nèi)容是:n);show_arr(&arr);return

22、 0;void init_arr(struct Arr *pArr,int length)/(*pArr).len=99;pArr-pBase = (int*)malloc(sizeof(int)*length);if(NULL=pArr-pBase)printf(動態(tài)內(nèi)存分配失??！n);exit(-1);/終止整個程序elsepArr-len=length;pArr-cnt=0;return;bool is_empty(struct Arr *pArr)/是否已滿if(0=pArr-cnt)return true;else return false;void show_arr(struct

23、Arr *pArr)/顯示/if(數(shù)組為空)/提示用戶數(shù)組為空/else/輸出數(shù)組有效內(nèi)容if(is_empty(pArr)/printf(數(shù)組為空!n);elsefor(int i=0;icnt;i+)printf(%d ,pArr-pBasei);printf(n);bool is_full(struct Arr *pArr)/是否為空if(pArr-cnt=pArr-len)return true;elsereturn false;bool append_arr(struct Arr *pArr,int val)/追加，可能成功，可能失敗/滿時返回falseif(is_full(pArr

24、)return false;/不滿時追加pArr-pBasepArr-cnt=val;(pArr-cnt)+;return true;bool insert_arr(struct Arr *pArr,int pos,int val)/pos的值從1開始int i;if(is_full(pArr)return false;if(pospArr-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;boo

25、l delete_arr(struct Arr *pArr,int pos,int *pVal)int i;if(is_empty(pArr)return false;if(pospArr-cnt)return false;*pVal=pArr-pBasepos-1;for(i=pos;icnt;+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(ipBasei;pArr-pBasei=pAr

26、r-pBasej;pArr-pBasej=t;+i;-j;return;void sort_arr(struct Arr *pArr)/排序int i,j,t;for(i=0;icnt;+i)for(j=i+1;jcnt;+j)if(pArr-pBaseipArr-pBasej)t=pArr-pBasei;pArr-pBasei=pArr-pBasej;pArr-pBasej=t;14_鏈表的重要性15_typedef的用法CASE 1#includetypedefint ZHAGNSAN;/為int再重新多取一個名字，ZHAGNSAN等價于inttypedef struct Studenti

27、nt sid;char name100;char sex;ST;int main(void)int i=10;/等價于ZHANGSAN i=10;/ZHAGNSAN j=20;/printf(%dn,j);struct Student st;/等價于ST st；struct Student *ps=&st;/等價于ST *ps;ST st2;st2.sid=200;printf(%dn,st2.sid);return 0;CASE 2#includetypedefint ZHAGNSAN;/為int再重新多取一個名字，ZHAGNSAN等價于inttypedef struct Studentin

28、t sid;char name100;char sex;*PST;/PST等價于struct Student *int main(void)struct Student st;/等價于ST st；PST ps=&st;ps-sid=99;printf(%dn,ps-sid);return 0;CASE 3#includetypedefint ZHAGNSAN;/為int再重新多取一個名字，ZHAGNSAN等價于inttypedef struct Studentint sid;char name100;char sex;*PSTU,STU;/PSTU等價于struct Student *,STU

29、代表了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-sid);return 0;16_鏈表的定義定義：n個節(jié)點(diǎn)離散分配；彼此通過指針相連；每個節(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)之前的那個節(jié)點(diǎn)；頭節(jié)點(diǎn)并不存放存放有效數(shù)據(jù)；加頭節(jié)點(diǎn)的目主要是為了方便對鏈表的操作。

30、頭指針：指向頭節(jié)點(diǎn)的指針變量尾指針：指向尾節(jié)點(diǎn)的指針變量頭節(jié)點(diǎn)-首節(jié)點(diǎn)。尾節(jié)點(diǎn)【頭節(jié)點(diǎn)并沒有存儲有效數(shù)據(jù)，也沒有存放鏈表中有效節(jié)點(diǎn)的個數(shù)。首節(jié)點(diǎn)開始存放有效數(shù)據(jù)。在鏈表前邊加一個沒有實(shí)際意義的頭節(jié)點(diǎn)，可以方便對鏈表的操作。頭節(jié)點(diǎn)于之后節(jié)點(diǎn)的數(shù)據(jù)類型相同】分類：算法：鏈表的優(yōu)缺點(diǎn)：17_如果希望通過一個函數(shù)來對鏈表進(jìn)行處理，我們至少需要接受鏈表的哪些參數(shù)如果希望通過一個函數(shù)來對鏈表進(jìn)行處理，我們至少需要接受鏈表的哪些參數(shù)只需要一個參數(shù)：頭指針因?yàn)槲覀兺ㄟ^頭指針可以推算出鏈表的其他所有參數(shù)18_每一個鏈表節(jié)點(diǎn)的數(shù)據(jù)類型該如何表示的問題CASE 1#includetypedef struct Nod

31、eint data;/數(shù)據(jù)域struct Node * pNext;/指針域NODE,*PNODE;/NODE等價于struct Node，PNODE等價于struct Node *int main(void)return 0;19_鏈表的分類分類：單鏈表：每個鏈表的指針域只能指向后面的節(jié)點(diǎn)雙鏈表：每一個節(jié)點(diǎn)有兩個指針域循環(huán)鏈表：能通過任何一個節(jié)點(diǎn)找到其他所有的結(jié)點(diǎn)非循環(huán)鏈表：20_非循環(huán)單鏈表插入節(jié)點(diǎn)偽算法講解算法：遍歷查找清空銷毀求長度排序刪除節(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，

32、q不是節(jié)點(diǎn)，是指針變量】。21_刪除非循環(huán)單鏈表節(jié)點(diǎn)偽算法的講解刪除算法1（不采用）：p-pNext=p-pNext-pNext;/容易導(dǎo)致內(nèi)存泄露，沒有釋放內(nèi)存算法2：先臨時定義一個指向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#include#includetypedef struct Nodeint data;/數(shù)據(jù)域struct Node * pNext;/指針域NODE,*PNODE;/NODE等價于struct Node，PNOD

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

34、入的節(jié)點(diǎn)的值/分配了一個不存放有效數(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(請輸入您需要生成的鏈表節(jié)點(diǎn)的個數(shù)：len=);scanf(%d,&len);for (i=0;idata=val;/掛pTail-pNext=pNew;pNew-pNext=NULL;pTail=pNew;return pHead;void traverse_list(PNODE pHead)PNODE

35、p=pHead-pNext;while(NULL!=p)printf(%d ,p-data);p=p-pNext;/不連續(xù)，不能用p+printf(n);return;25_判斷鏈表是否為空 和 求鏈表長度 算法的演示#include#include#includetypedef struct Nodeint data;/數(shù)據(jù)域struct Node * pNext;/指針域NODE,*PNODE;/NODE等價于struct Node，PNODE等價于struct Node */函數(shù)聲明PNODE create_list(void);void traverse_list(PNODE pHea

36、d);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;/等價于struct Node *pHead=NULL；pHead=create_list();/creat_list()功能：創(chuàng)建一個非循環(huán)單鏈表,并將該鏈表的頭節(jié)點(diǎn)的地址付給pHeadtraverse_list(pHead);int len=length

37、_list(pHead);printf(鏈表長度是%dn,len);if(is_empty(pHead)printf(鏈表為空！n);else printf(鏈表不空！n);return 0;PNODE create_list(void)int len;/用來存放有效節(jié)點(diǎn)的個數(shù)int i;int val;/用來臨時存放用戶輸入的節(jié)點(diǎn)的值/分配了一個不存放有效數(shù)據(jù)的頭節(jié)點(diǎn)PNODE pHead=(PNODE)malloc(sizeof(NODE);if(NULL=pHead)printf(分配失敗，程序終止！n);exit(-1);PNODE pTail=pHead;pTail-pNext=NU

38、LL;printf(請輸入您需要生成的鏈表節(jié)點(diǎn)的個數(shù)：len=);scanf(%d,&len);for (i=0;idata=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-pNext=NULL)return

39、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ù)的存儲方式密切相關(guān)廣義的算法是與數(shù)據(jù)的存儲方式無關(guān)泛型：利用某種技術(shù)達(dá)到的效果就是：不同的存儲方式，執(zhí)行的操作是一樣的#include#include#includetypedef struct Nodeint data;/數(shù)據(jù)域struct Node

40、* pNext;/指針域NODE,*PNODE;/NODE等價于struct Node，PNODE等價于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;/等價于st

41、ruct Node *pHead=NULL；pHead=create_list();/creat_list()功能：創(chuàng)建一個非循環(huán)單鏈表,并將該鏈表的頭節(jié)點(diǎn)的地址付給pHeadtraverse_list(pHead);int len=length_list(pHead);printf(鏈表長度是%dn,len);if(is_empty(pHead)printf(鏈表為空！n);else printf(鏈表不空！n);sort_list(pHead);traverse_list(pHead);return 0;PNODE create_list(void)int len;/用來存放有效節(jié)點(diǎn)的個數(shù)

42、int i;int val;/用來臨時存放用戶輸入的節(jié)點(diǎn)的值/分配了一個不存放有效數(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(請輸入您需要生成的鏈表節(jié)點(diǎn)的個數(shù)：len=);scanf(%d,&len);for (i=0;idata=val;/掛pTail-pNext=pNew;pNew-pNext=NULL;pTail=pNew;return pHead;void traverse

43、_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=pHead-pNext;int len=0;while(NULL!=p)len+;p=p-pNext;return len;void sort_list(PNOD

44、E pHead)int i,j,t;int len=length_list(pHead);PNODE p,q;for(i=0,p=pHead-pNext;ipNext)for(j=i+1,q=p-pNext;jpNext)if(p-dataq-data)/類似于數(shù)組中的：aiajt=p-data;/類似于數(shù)組中的：t=ai;p-data=q-data;/類似于數(shù)組中的：ai=aj;q-data=t;/類似于數(shù)組中的：aj=t;27_如何學(xué)習(xí)算法自己的一些感想28_鏈表插入和刪除算法的演示#include#include#includetypedef struct Nodeint data;/數(shù)據(jù)域struct Node * pNext;/指針域NODE,*PNODE;/NODE等價于struct Node，PNODE等價于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 de