節(jié)線性數(shù)據(jù)結(jié)構(gòu)-基本概念-去掉聲音效果了

1、第二章第二章 線性數(shù)據(jù)結(jié)構(gòu)線性數(shù)據(jù)結(jié)構(gòu)描述客觀事物的數(shù)字、字符以及一切描述客觀事物的數(shù)字、字符以及一切能夠輸入到計(jì)算機(jī)中，并且能夠被計(jì)能夠輸入到計(jì)算機(jī)中，并且能夠被計(jì)算機(jī)程序處理的算機(jī)程序處理的符號(hào)的集合符號(hào)的集合。 表示一個(gè)事物的一組數(shù)據(jù)，是數(shù)據(jù)的基表示一個(gè)事物的一組數(shù)據(jù)，是數(shù)據(jù)的基本單位，又稱結(jié)點(diǎn)。在計(jì)算機(jī)程序中通本單位，又稱結(jié)點(diǎn)。在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行處理。一個(gè)數(shù)據(jù)元常作為一個(gè)整體進(jìn)行處理。一個(gè)數(shù)據(jù)元素由若干素由若干數(shù)據(jù)項(xiàng)數(shù)據(jù)項(xiàng)構(gòu)成。構(gòu)成。數(shù)據(jù)元素之間具有的關(guān)系，即數(shù)據(jù)的組數(shù)據(jù)元素之間具有的關(guān)系，即數(shù)據(jù)的組織形式?？椥问?。2.1.1 數(shù)據(jù)和數(shù)據(jù)結(jié)構(gòu) 具有獨(dú)立含義的最小標(biāo)識(shí)單位

2、具有獨(dú)立含義的最小標(biāo)識(shí)單位, ,是是數(shù)據(jù)的數(shù)據(jù)的最小單位最小單位學(xué)號(hào)學(xué)號(hào)姓名姓名性別性別籍貫籍貫出生年月出生年月住址住址06048001趙玲女上海1987.10上海06048002楊揚(yáng)男北京1987.3北京 描述客觀事物的數(shù)字、字符以及一切描述客觀事物的數(shù)字、字符以及一切能夠輸入到計(jì)算機(jī)中，并且能夠被計(jì)能夠輸入到計(jì)算機(jī)中，并且能夠被計(jì)算機(jī)程序處理的算機(jī)程序處理的符號(hào)的集合符號(hào)的集合。 表示一個(gè)事物的一組數(shù)據(jù)，是數(shù)據(jù)的基表示一個(gè)事物的一組數(shù)據(jù)，是數(shù)據(jù)的基本單位，又稱結(jié)點(diǎn)。在計(jì)算機(jī)程序中通本單位，又稱結(jié)點(diǎn)。在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行處理。一個(gè)數(shù)據(jù)元常作為一個(gè)整體進(jìn)行處理。一個(gè)數(shù)據(jù)元素由若干

3、素由若干數(shù)據(jù)項(xiàng)數(shù)據(jù)項(xiàng)構(gòu)成。構(gòu)成。數(shù)據(jù)元素之間具有的關(guān)系，即數(shù)據(jù)的組數(shù)據(jù)元素之間具有的關(guān)系，即數(shù)據(jù)的組織形式?？椥问?。2.1.1 數(shù)據(jù)和數(shù)據(jù)結(jié)構(gòu)表結(jié)構(gòu)表結(jié)構(gòu)學(xué)號(hào)學(xué)號(hào)姓名姓名 性別性別籍貫籍貫出生年月出生年月住址住址06048001 趙玲女上海1987.10上海06048002 楊揚(yáng)男北京1987.3北京 學(xué)籍登記表學(xué)籍登記表交通圖交通圖烏魯木齊蘭州西安呼和浩特北京鄭州成都18921145668676695511842圖結(jié)構(gòu)圖結(jié)構(gòu) 1. 研究數(shù)據(jù)元素之間的客觀聯(lián)系研究數(shù)據(jù)元素之間的客觀聯(lián)系。 2. 研究具有某種邏輯關(guān)系的數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)研究具有某種邏輯關(guān)系的數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ) 器內(nèi)的存儲(chǔ)方式。器內(nèi)的

4、存儲(chǔ)方式。 3. 研究如何在數(shù)據(jù)的各種結(jié)構(gòu)研究如何在數(shù)據(jù)的各種結(jié)構(gòu)(邏輯的和物理的邏輯的和物理的) 的基礎(chǔ)上對(duì)數(shù)據(jù)實(shí)施一系列有效的基本操作。的基礎(chǔ)上對(duì)數(shù)據(jù)實(shí)施一系列有效的基本操作。 邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)1.2 數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容算法算法邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)： 計(jì)算機(jī)處理的數(shù)據(jù)元素的組織形式及其相互間的關(guān)系。 由數(shù)據(jù)元素的有限集合及所有數(shù)據(jù)元素之間的關(guān)系組成。記為： Data_Structure = (D, R) 其中，D是數(shù)據(jù)元素的有限集，R是所有數(shù)據(jù)元素之間的關(guān)系的有限集合。 數(shù)據(jù)結(jié)構(gòu): SET =（D,R）08010305020704060910集合結(jié)構(gòu)示意圖D

5、= 01,02,03,04,05,06,07,08,09,10 R = 數(shù)據(jù)結(jié)構(gòu) LINEARITY =（D,R）05010308020704060910線性結(jié)構(gòu)示意圖數(shù)據(jù)元素之間的聯(lián)系：數(shù)據(jù)元素之間的聯(lián)系：1:1D = 01,02,03,04,05,06,07,08,09,10 R = , , , 數(shù)據(jù)結(jié)構(gòu) 01020304070809050610樹(shù)結(jié)構(gòu)示意圖數(shù)據(jù)之間的聯(lián)系：數(shù)據(jù)之間的聯(lián)系：1：NGraph = ( D, R )數(shù)據(jù)之間的聯(lián)系：數(shù)據(jù)之間的聯(lián)系：M：ND = 1,2,3,4,5,6,7,8,9 R = , , ,d1 d2 d3 d4 d301. 順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)線性結(jié)

6、構(gòu)線性結(jié)構(gòu)（線性表）（線性表）2. 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)a1a2a3a30list 數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu) 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) 數(shù)據(jù)的運(yùn)算數(shù)據(jù)的運(yùn)算 線性結(jié)構(gòu)線性結(jié)構(gòu) 非線性結(jié)構(gòu)非線性結(jié)構(gòu) 順序存儲(chǔ)順序存儲(chǔ) 鏈?zhǔn)酱鎯?chǔ)鏈?zhǔn)酱鎯?chǔ) 線性表線性表堆棧堆棧隊(duì)列隊(duì)列樹(shù)形結(jié)構(gòu)樹(shù)形結(jié)構(gòu)圖形結(jié)構(gòu)圖形結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的三個(gè)方面： 散列存儲(chǔ)散列存儲(chǔ)索引存儲(chǔ)索引存儲(chǔ)串及數(shù)組串及數(shù)組查找、排序、插入、刪除、修改等查找、排序、插入、刪除、修改等1. .算法的定義算法的定義(1). 算法算法是用來(lái)解決某個(gè)特定問(wèn)題的指令的集合。是用來(lái)解決某個(gè)特定問(wèn)題的指令的集合。(2). 算法算法是由人們組織起來(lái)準(zhǔn)備加以實(shí)施

7、的一系是由人們組織起來(lái)準(zhǔn)備加以實(shí)施的一系 列有限的基本步驟。列有限的基本步驟。2. .算法的描述算法的描述文字形式文字形式程序設(shè)計(jì)語(yǔ)言形式（如程序設(shè)計(jì)語(yǔ)言形式（如C語(yǔ)言等）語(yǔ)言等）偽碼形式偽碼形式3. .算法的性質(zhì)算法的性質(zhì) 4. .算法分析算法分析時(shí)間復(fù)雜度時(shí)間復(fù)雜度 T T（n n）空間復(fù)雜度空間復(fù)雜度 S S（n n）其它（如可讀性、可移植性等）其它（如可讀性、可移植性等）前提條件：算法必須正確4.時(shí)間復(fù)雜度時(shí)間復(fù)雜度稱為時(shí)間頻度，記為T（n） 例：例：3n+2=O(n) /* 3n+2 4n for n 2 */10n2+4n+2=O(n2) /* 10n2+4n+2 11n2 for

8、 n 5 */6*2n+n2=O(2n) /* 6*2n+n2 7*2n for n 4 */注注 空間復(fù)雜度空間復(fù)雜度S(n)按數(shù)量級(jí)遞增順序也與上表類按數(shù)量級(jí)遞增順序也與上表類同。同。常用的計(jì)算規(guī)則：1.加法規(guī)則 T(n) = T1(n)+ T2(n) = O(f1(n) + O(f2(n) = O(max(f1(n), f2(n) 2. 乘法規(guī)則 T(n) = T1(n)T2(n) = O(f1(n) O(f2(n) = O(f1(n)f2(n) 3.空間復(fù)雜空間復(fù)雜度度時(shí)間復(fù)雜度和空間復(fù)雜度的關(guān)系時(shí)間復(fù)雜度和空間復(fù)雜度的關(guān)系復(fù)習(xí)：鏈表numnamesexageaddr10001Zhan

9、g xinM19Shanghai10002Wang liF18Xian10003Li fangM18Beijing學(xué)生學(xué)籍信息學(xué)生學(xué)籍信息struct Student int num; char name20; char sex; int age; char addr30; ;記錄記錄關(guān)鍵字關(guān)鍵字結(jié)構(gòu)體名結(jié)構(gòu)體名numnamesexageaddr10001Zhang xinM19Shanghai10002Wang liF18Xian10003Li fangM18Beijing學(xué)生學(xué)籍信息學(xué)生學(xué)籍信息struct Student int num; char name20; char sex; i

10、nt age; char addr30; ;記錄記錄結(jié)構(gòu)體類型結(jié)構(gòu)體類型結(jié)構(gòu)體成員結(jié)構(gòu)體成員struct Student int num; char name20; char sex; int age; char addr30; ;struct Student s1;s1.numstruct Student *s2;(*s2).num等價(jià)于等價(jià)于s2-num 鏈表是一種常見(jiàn)的重要的數(shù)據(jù)結(jié)構(gòu) 它是動(dòng)態(tài)地進(jìn)行存儲(chǔ)分配的一種結(jié)構(gòu)head12491249A135613561475B1475C10211021DNULL頭指針頭指針各結(jié)點(diǎn)地址不連續(xù)各結(jié)點(diǎn)地址不連續(xù)各結(jié)點(diǎn)含有兩個(gè)部分各結(jié)點(diǎn)含有兩個(gè)部分表尾表

11、尾struct Student int num; float score; struct Student *next; a,b,c;1010189.510103901010785a結(jié)點(diǎn)結(jié)點(diǎn)b結(jié)點(diǎn)結(jié)點(diǎn)c結(jié)點(diǎn)結(jié)點(diǎn)a.next=&b;b.next=&c;numscorenext程序運(yùn)行過(guò)程中，程序運(yùn)行過(guò)程中，如何動(dòng)態(tài)申請(qǐng)內(nèi)存如何動(dòng)態(tài)申請(qǐng)內(nèi)存空間？空間？q 動(dòng)態(tài)內(nèi)存分配 設(shè)計(jì)人員根據(jù)具體問(wèn)題的具體需要，在程序運(yùn)行時(shí)再具體確定數(shù)組的個(gè)數(shù)或占用內(nèi)存單元的大小，從而在程序運(yùn)行時(shí)具體確定所需要的內(nèi)存單元空間。malloc()函數(shù)free()函數(shù)頭文件malloc.h# include mall

12、oc()函數(shù)free()函數(shù)函數(shù)原型： void * malloc ( unsigned size)函數(shù)功能： 用于向系統(tǒng)動(dòng)態(tài)申請(qǐng)size個(gè)字節(jié)的內(nèi)存單元空間，函數(shù)返回值為所申請(qǐng)的內(nèi)存空間首地址。函數(shù)原型： void free ( void * p)函數(shù)功能：用于釋放動(dòng)態(tài)分配的內(nèi)存空間。sizeof 運(yùn)算符：運(yùn)算符：sizeof(已定義的數(shù)據(jù)類型)功能：返回括號(hào)中給出的已定義數(shù)據(jù)類型占用的字節(jié)個(gè)數(shù)。Memory Allocation如：如：sizeof(int)p=( SLNode * ) malloc(sizeof(SLNode) );SLNode *p;p=malloc(sizeof(SL

13、Node);強(qiáng)制類型轉(zhuǎn)換 所謂建立動(dòng)態(tài)鏈表是指在程序執(zhí)行過(guò)程中從無(wú)到有地建立起一個(gè)鏈表，即一個(gè)一個(gè)地開(kāi)辟結(jié)點(diǎn)和輸入各結(jié)點(diǎn)數(shù)據(jù)，并建立起前后相鏈的關(guān)系。 例9.9 寫一函數(shù)建立一個(gè)有3名學(xué)生數(shù)據(jù)的單向動(dòng)態(tài)鏈表。 解題思路： 定義3個(gè)指針變量：head,p1和p2，它們都是用來(lái)指向struct Student類型數(shù)據(jù)struct Student *head,*p1,*p2;unsigned LEN=sizeof(struct Student); 解題思路： 用malloc函數(shù)開(kāi)辟第一個(gè)結(jié)點(diǎn)，并使p1和p2指向它p1p1=p2=(struct Student*)malloc(LEN);p2 解題思路

14、： 讀入一個(gè)學(xué)生的數(shù)據(jù)給p1所指的第一個(gè)結(jié)點(diǎn)p1scanf(%ld,%f,&p1-num,&p1-score);p21010189.5 解題思路： 讀入一個(gè)學(xué)生的數(shù)據(jù)給p1所指的第一個(gè)結(jié)點(diǎn) 使head也指向新開(kāi)辟的結(jié)點(diǎn)headp1p2scanf(%ld,%f,&p1-num,&p1-score);1010189.5 解題思路： 再開(kāi)辟另一個(gè)結(jié)點(diǎn)并使p1指向它，接著輸入該結(jié)點(diǎn)的數(shù)據(jù)headp1p21010189.5 解題思路： 再開(kāi)辟另一個(gè)結(jié)點(diǎn)并使p1指向它，接著輸入該結(jié)點(diǎn)的數(shù)據(jù)headp1p21010189.5p1=(struct Student*)malloc

15、(LEN);scanf(%ld,%f,&p1-num,&p1-score);1010390 解題思路： 使第一個(gè)結(jié)點(diǎn)的next成員指向第二個(gè)結(jié)點(diǎn)，即連接第一個(gè)結(jié)點(diǎn)與第二個(gè)結(jié)點(diǎn) 使p2指向剛才建立的結(jié)點(diǎn)headp1p21010189.5p2-next=p1;1010390 解題思路： 使第一個(gè)結(jié)點(diǎn)的next成員指向第二個(gè)結(jié)點(diǎn)，即連接第一個(gè)結(jié)點(diǎn)與第二個(gè)結(jié)點(diǎn) 使p2指向剛才建立的結(jié)點(diǎn)headp1p21010189.5p2-next=p1;1010390p2=p1; 解題思路： 再開(kāi)辟另一個(gè)結(jié)點(diǎn)并使p1指向它，接著輸入該結(jié)點(diǎn)的數(shù)據(jù)headp1p21010189.51010390 解題思

16、路： 再開(kāi)辟另一個(gè)結(jié)點(diǎn)并使p1指向它，接著輸入該結(jié)點(diǎn)的數(shù)據(jù)headp1p21010189.51010390p1=(struct Student*)malloc(LEN);scanf(%ld,%f,&p1-num,&p1-score);1010785 解題思路： 使第二個(gè)結(jié)點(diǎn)的next成員指向第三個(gè)結(jié)點(diǎn)，即連接第二個(gè)結(jié)點(diǎn)與第三個(gè)結(jié)點(diǎn) 使p2指向剛才建立的結(jié)點(diǎn)headp1p21010189.510103901010785p2-next=p1; 解題思路： 使第二個(gè)結(jié)點(diǎn)的next成員指向第三個(gè)結(jié)點(diǎn)，即連接第二個(gè)結(jié)點(diǎn)與第三個(gè)結(jié)點(diǎn) 使p2指向剛才建立的結(jié)點(diǎn)headp1p21010189.

17、510103901010785p2-next=p1;p2=p1; 解題思路： 再開(kāi)辟另一個(gè)結(jié)點(diǎn)并使p1指向它，接著輸入該結(jié)點(diǎn)的數(shù)據(jù)headp1p21010189.5101039010107850 解題思路： 再開(kāi)辟另一個(gè)結(jié)點(diǎn)并使p1指向它，接著輸入該結(jié)點(diǎn)的數(shù)據(jù)headp1p21010189.5101039010107850p1=(struct Student*)malloc(LEN);scanf(%ld,%f,&p1-num,&p1-score); 解題思路： 輸入的學(xué)號(hào)為0，表示建立鏈表的過(guò)程完成，該結(jié)點(diǎn)不應(yīng)連接到鏈表中headp1p21010189.510103901010

18、7850NULLp2-next=NULL;#include #include #define LEN sizeof(struct Student)struct Student long num; float score; struct Student *next;int n;struct Student類型數(shù)據(jù)的長(zhǎng)度類型數(shù)據(jù)的長(zhǎng)度struct Student *creat(void) struct Student *head,*p1,*p2; n=0; p1=p2=( struct Student*) malloc(LEN); scanf(“%ld,%f”,&p1-num,&p1-score); head=NULL; while(p1-num!=0) n