01年09-11月pascal語言數(shù)據(jù)結(jié)構(gòu)線性表

1、數(shù)據(jù)結(jié)構(gòu)簡介1.數(shù)據(jù)的含義.計(jì)算機(jī)程序加工處理的對(duì)象2.數(shù)據(jù)處理的特點(diǎn):1)需要處理的是大量的各種類型的數(shù)據(jù),包括數(shù)值,字符串,還有漢字.2)數(shù)據(jù)之間存在著一定的聯(lián)系,即具有一定的結(jié)構(gòu).3)計(jì)算公式一般比較簡單,但因數(shù)據(jù)量大,需要大量的計(jì)算時(shí)間.4)大量的工作用在建表,排序,查找,修改,刪除,統(tǒng)計(jì)等方面.數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是介于數(shù)學(xué),計(jì)算機(jī)軟,硬件間的一門交叉學(xué)科,它主要研究數(shù)據(jù)的邏輯結(jié)構(gòu),物理結(jié)構(gòu)以及數(shù)據(jù)的操作.數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間的邏輯關(guān)系,數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計(jì)算機(jī)內(nèi)的存儲(chǔ)結(jié)構(gòu).數(shù)據(jù)在計(jì)算機(jī)中的兩種存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)，非順序存儲(chǔ)結(jié)構(gòu)（鏈?zhǔn)浇Y(jié)構(gòu)）。常見的數(shù)據(jù)結(jié)構(gòu)有：線性表，

2、隊(duì)列，堆棧，鏈表，樹，有向圖等。線性表線性表是由有限個(gè)數(shù)據(jù)元素組成的有序集合，每個(gè)數(shù)據(jù)元素又由一個(gè)或多個(gè)數(shù)據(jù)項(xiàng)組成。例：姓名數(shù)學(xué)物理化學(xué)總分馬蘭928895275李威859076251吳 飛959789281安然7710097274盧杰886374225線性表有唯一的前趨和后繼，若有多個(gè)則為樹或圖。線性表的特征1均勻性:各數(shù)據(jù)元素具有相同的數(shù)據(jù)類型和長度.2. 有序性:數(shù)據(jù)元素在線性表中的位置只取決于它們自己的序號(hào),數(shù)據(jù)元素間的相對(duì)位置是線性的.3.線性表可以用數(shù)組來實(shí)現(xiàn).對(duì)線性表的操作1.插入: 在線性表中指定位置上插入一個(gè)數(shù)據(jù)元素.2.刪除:刪除線性表中指定序號(hào)的數(shù)據(jù)元素.3.查找:在線性

3、表中查找具有某個(gè)特性的數(shù)據(jù)元素.4.排序:將無序的線性表按數(shù)據(jù)元素的某一關(guān)鍵字的遞增或遞減的次序重新排序.5.修改:修改線性表中的某些數(shù)據(jù)項(xiàng).6.統(tǒng)計(jì):對(duì)線性表中的某些數(shù)據(jù)項(xiàng)求和,求平均值等.1.插入: 假設(shè)在長度為N的線性表中第I個(gè)元素與第I+1個(gè)元素之間插入一個(gè)新元素.思路: 首先把原來第I+1個(gè)元素到第N個(gè)元素分別移到第I+2到N+1的位置上,騰出第I+1個(gè)單元,再讓新元素填入到第I+1個(gè)單元中去.算法: 若IN, 則表示表中無該元素; 若I=0 DO BEGIN 3.1 建立新結(jié)點(diǎn); 3.2 鏈接到表尾; 3.3 尾指針下移; 3.4 讀入下一個(gè)值 END; 4. 最后一個(gè)結(jié)點(diǎn)指針域置

4、NIL; 5. 從頭到尾輸出每個(gè)結(jié)點(diǎn)中的值.98headtail如何建立一個(gè)鏈表.算法:1. 讀入第一個(gè)值,建立首結(jié)點(diǎn); 2.讀入第二個(gè)值; 3. WHILE 讀入值=0 DO BEGIN 3.1 建立新結(jié)點(diǎn); 3.2 鏈接到表尾; 3.3 尾指針下移; 3.4 讀入下一個(gè)值 END; 4. 最后一個(gè)結(jié)點(diǎn)指針域置NIL; 5. 從頭到尾輸出每個(gè)結(jié)點(diǎn)中的值.34.198headtailnext如何建立一個(gè)鏈表.算法:1. 讀入第一個(gè)值,建立首結(jié)點(diǎn); 2.讀入第二個(gè)值; 3. WHILE 讀入值=0 DO BEGIN 3.1 建立新結(jié)點(diǎn); 3.2 鏈接到表尾; 3.3 尾指針下移; 3.4 讀入下

5、一個(gè)值 END; 4. 最后一個(gè)結(jié)點(diǎn)指針域置NIL; 5. 從頭到尾輸出每個(gè)結(jié)點(diǎn)中的值.34.1tail98headnext如何建立一個(gè)鏈表.算法:1. 讀入第一個(gè)值,建立首結(jié)點(diǎn); 2.讀入第二個(gè)值; 3. WHILE 讀入值=0 DO BEGIN 3.1 建立新結(jié)點(diǎn); 3.2 鏈接到表尾; 3.3 尾指針下移; 3.4 讀入下一個(gè)值 END; 4. 最后一個(gè)結(jié)點(diǎn)指針域置NIL; 5. 從頭到尾輸出每個(gè)結(jié)點(diǎn)中的值.34.198head255nextNILtail如何建立一個(gè)鏈表.算法:1. 讀入第一個(gè)值,建立首結(jié)點(diǎn); 2.讀入第二個(gè)值; 3. WHILE 讀入值=0 DO BEGIN 3.1 建立新結(jié)點(diǎn); 3.2 鏈接到表尾; 3.3 尾指針下移; 3.4 讀入下一個(gè)值 END; 4. 最后一個(gè)結(jié)點(diǎn)指針域置NIL; 5. 從頭到尾輸出每個(gè)結(jié)點(diǎn)中的值.34.198head255nextNILtail鏈表中的插入和刪除