《數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）》第一章 緒言

數(shù)據(jù)結(jié)構(gòu)課程內(nèi)容：數(shù)據(jù)結(jié)構(gòu)課時(shí)安排：上課——64學(xué)時(shí)課外上機(jī)——16學(xué)時(shí)教材：數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版)

第一章緒言1.1什么是數(shù)據(jù)結(jié)構(gòu)

程序=數(shù)據(jù)結(jié)構(gòu)+算法例1書目自動(dòng)檢索系統(tǒng)登錄號(hào)：書名：作者名：分類號(hào)：出版單位：出版時(shí)間：價(jià)格：書目卡片書目文件按書名按作者名按分類號(hào)索引表線性表例2人機(jī)對(duì)奕問題樹……..……..…...…...…...…...多叉路口交通燈管理問題圖CEDABABACADBABCBDDADBDCEAEBECED古老的七橋問題圖ABDCADCB數(shù)據(jù)結(jié)構(gòu)定義:是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的操作對(duì)象以及它們之間的關(guān)系和操作等等的學(xué)科1.2基本概念和術(shù)語(yǔ)數(shù)據(jù)（data)—所有能輸入到計(jì)算機(jī)中去的描述客觀事物并被計(jì)算機(jī)程序處理的符號(hào)的總稱數(shù)據(jù)元素（dataelement）—數(shù)據(jù)的基本單位，也稱節(jié)點(diǎn)（node）或記錄（record），如“樹”中的一個(gè)棋盤格局，“圖”中的一個(gè)圓圈數(shù)據(jù)項(xiàng)（dataitem）—有獨(dú)立含義的數(shù)據(jù)最小單位，也稱域(field)，是不可分割的，如書目信息中的書名、作者等數(shù)據(jù)對(duì)象（dataobject）—性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集關(guān)鍵碼（key）—數(shù)據(jù)元素中能起標(biāo)識(shí)作用的數(shù)據(jù)項(xiàng)。關(guān)系—集合中元素之間的某種相關(guān)性數(shù)據(jù)結(jié)構(gòu)（datastructure)—數(shù)據(jù)元素和數(shù)據(jù)元素關(guān)系的集合根據(jù)數(shù)據(jù)元素間關(guān)系的基本特性，有四種基本數(shù)據(jù)結(jié)構(gòu)（集合）——數(shù)據(jù)元素間除“同屬于一個(gè)集合”外，無其它關(guān)系線性結(jié)構(gòu)——一個(gè)對(duì)一個(gè)，如線性表、棧、隊(duì)列樹形結(jié)構(gòu)——一個(gè)對(duì)多個(gè)，如樹圖狀結(jié)構(gòu)——多個(gè)對(duì)多個(gè)，如圖 Group=（P，R）其中：P={T，G1，…，Gn，S11…Snm}1≤n≤3，1≤m≤2 R={R1，R2} R1={<T，Gi>|1≤i≤n，1≤n≤3} R2={<Gi，Sij>|1≤i≤n，1≤j≤m，1≤n≤3，1≤m≤2}數(shù)據(jù)結(jié)構(gòu)的形式定義為:數(shù)據(jù)結(jié)構(gòu)是一個(gè)二元組Data_Structure=（D，S）其中：D是數(shù)據(jù)元素的有限集，S是D上關(guān)系的有限集。例1-5假設(shè)我們需要編制一個(gè)事務(wù)管理的程序，管理學(xué)校科學(xué)研究課題小組的各項(xiàng)事務(wù)，則首先要為程序的操作對(duì)象——課題小組設(shè)計(jì)一個(gè)數(shù)據(jù)結(jié)構(gòu)。假設(shè)每個(gè)小組由一位教師、一至三名研究生及一至六名本科生組成，小組成員之間的關(guān)系是：教師指導(dǎo)研究生，而由每位研究生指導(dǎo)一至兩名本科生。則可以如下定義數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)的邏輯結(jié)構(gòu)—只抽象反映數(shù)據(jù)元素的邏輯關(guān)系數(shù)據(jù)的存儲(chǔ)（物理）結(jié)構(gòu)—數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器中的實(shí)現(xiàn)數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)密切相關(guān) 算法設(shè)計(jì) 邏輯結(jié)構(gòu) 算法實(shí)現(xiàn) 存儲(chǔ)結(jié)構(gòu) 存儲(chǔ)結(jié)構(gòu)分為：順序存儲(chǔ)結(jié)構(gòu)——借助元素在存儲(chǔ)器中的相對(duì)位置來表示數(shù)據(jù)元素間的邏輯關(guān)系鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)——借助指示元素存儲(chǔ)地址的指針表示數(shù)據(jù)元素間的邏輯關(guān)系元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存儲(chǔ)地址存儲(chǔ)內(nèi)容Loc(元素i)=Lo+（i-1)*m順序存儲(chǔ)1536元素21400元素11346元素3∧元素41345h存儲(chǔ)地址

存儲(chǔ)內(nèi)容

指針1345

元素1

14001346

元素4∧

…….

……..

…….

1400

元素21536

…….

……..

…….1536

元素31346

鏈?zhǔn)酱鎯?chǔ)

h

數(shù)據(jù)的邏輯結(jié)構(gòu)

數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的運(yùn)算：檢索、排序、插入、刪除、修改等

線性結(jié)構(gòu)

非線性結(jié)構(gòu)

順序存儲(chǔ)

鏈?zhǔn)酱鎯?chǔ)線性表?xiàng)ｊ?duì)樹形結(jié)構(gòu)圖形結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的三個(gè)方面：數(shù)據(jù)類型—高級(jí)語(yǔ)言中指數(shù)據(jù)的取值范圍及其上可進(jìn)行的操作的總稱例C語(yǔ)言中，提供int,char,float,double等基本數(shù)據(jù)類型，數(shù)組、結(jié)構(gòu)體、共用體、枚舉等構(gòu)造數(shù)據(jù)類型，還有指針、空(void)類型等。用戶也可用typedef

自己定義數(shù)據(jù)類型typedef

struct

{intnum;charname[20];floatscore;}STUDENT;STUDENTstu1,stu2,*p;1.3抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)抽象數(shù)據(jù)類型（abstractdatatype）—指一個(gè)數(shù)學(xué)模型以及定義在該模型上的一組操作?！俺橄蟆钡囊饬x在于強(qiáng)調(diào)數(shù)據(jù)類型的數(shù)學(xué)特性與其在計(jì)算機(jī)內(nèi)部如何表示和實(shí)現(xiàn)無關(guān)P7-131.4算法和算法分析算法（algorithm）—解決某一特定問題的具體步驟的描述，是指令的有限序列算法特性—算法的描述—采用類C語(yǔ)言（P6-9）算法的評(píng)價(jià)—衡量算法優(yōu)劣的標(biāo)準(zhǔn)正確性(correctness)：

1、不含語(yǔ)法錯(cuò)誤

2、對(duì)于幾組輸入數(shù)據(jù)能夠得出滿足規(guī)格說明要求的結(jié)果

3、對(duì)于精心選擇的典型、苛刻而帶有刁難性的數(shù)據(jù)能夠得出滿足規(guī)格說明要求的結(jié)果

4、對(duì)于一切合法的輸入數(shù)據(jù)都能產(chǎn)生滿足規(guī)格說明要求的結(jié)果可讀性(readability)：人的閱讀與交流健壯性(robustness)：當(dāng)輸入非法數(shù)據(jù)時(shí)，算法能夠適當(dāng)?shù)淖龀龇磻?yīng)或進(jìn)行處理，不會(huì)產(chǎn)生莫名其妙的結(jié)果效率與低存儲(chǔ)量：算法的執(zhí)行時(shí)間和所需的最大存儲(chǔ)空間算法效率——用依據(jù)該算法編制的程序在計(jì)算機(jī)上執(zhí)行所消耗的時(shí)間來度量

1.事后統(tǒng)計(jì)——利用計(jì)算機(jī)內(nèi)記時(shí)功能，不同算法的程序可以用一組或多組相同的統(tǒng)計(jì)數(shù)據(jù)區(qū)分缺點(diǎn)：必須先運(yùn)行依據(jù)算法編制的程序所得時(shí)間統(tǒng)計(jì)量依賴于硬件、軟件等環(huán)境因素，掩蓋算法本身的優(yōu)劣

2.事前分析估計(jì)——一個(gè)高級(jí)語(yǔ)言程序在計(jì)算機(jī)上運(yùn)行所消耗的時(shí)間取決于：依據(jù)的算法選用何種策略問題的規(guī)模程序語(yǔ)言編譯程序產(chǎn)生機(jī)器代碼質(zhì)量機(jī)器執(zhí)行指令速度同一個(gè)算法用不同的語(yǔ)言、不同的編譯程序、在不同的計(jì)算機(jī)上運(yùn)行，效率均不同，———所以使用絕對(duì)時(shí)間單位衡量算法效率不合適一般：算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個(gè)函數(shù)f(n)時(shí)間復(fù)雜度：隨問題規(guī)模n的增大，算法執(zhí)行時(shí)間的增長(zhǎng)率和f(n)的增長(zhǎng)率相同，稱作算法的漸進(jìn)時(shí)間復(fù)雜度。簡(jiǎn)稱時(shí)間復(fù)雜度?！椿静僮鳎ㄔ僮鳎┲貜?fù)執(zhí)行的次數(shù)的階數(shù)

T(n)=o(f(n))例1：nXn矩陣相乘for(i=1;i<=n;i++)

for(j=1;j<=n;j++){c[i][j]=0;

for(k=1;k<=n;k++)

c[i][j]=c[i][j]+a[i][k]*b[k][j];} 例