1操作系統(tǒng)軟件技術(shù)基礎(chǔ)軟件開發(fā)平臺開發(fā)原則數(shù)據(jù)管理＝文檔＋程序數(shù)據(jù)結(jié)構(gòu)算法軟件工程數(shù)據(jù)庫2本課程共60學(xué)時，其中課堂講授40學(xué)時，上機實驗20學(xué)時。課程共有三部分：數(shù)據(jù)結(jié)構(gòu)軟件工程操作系統(tǒng)關(guān)于應(yīng)掌握的內(nèi)容請注意課堂小結(jié)。課程的主要內(nèi)容及安排3第一部分?jǐn)?shù)據(jù)結(jié)構(gòu)5第1章

緒論一、什么是數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)數(shù)值型數(shù)據(jù):研究數(shù)據(jù)模型。如雞兔同籠問題非數(shù)值型數(shù)據(jù)：研究數(shù)據(jù)結(jié)構(gòu)。如聲音、圖形、圖像、視頻等6數(shù)據(jù)結(jié)構(gòu)研究的是非數(shù)值計算的程序設(shè)計語言中所出現(xiàn)的計算機操作對象以及他們之間的關(guān)系和操作的學(xué)科。簡單來說，就是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。第1章

緒論一、什么是數(shù)據(jù)結(jié)構(gòu)7數(shù)據(jù)結(jié)構(gòu)例1學(xué)生信息表學(xué)號姓名年齡專業(yè)1001張紅19英語1002王衛(wèi)18化工1003安然17數(shù)學(xué)…………1800李梅21儲運一行為一個數(shù)據(jù)元素也稱為記錄計算機處理的對象（數(shù)據(jù)元素）存在一種簡單的線性關(guān)系為線性數(shù)據(jù)結(jié)構(gòu)。如考試查分系統(tǒng)、倉庫管理系統(tǒng)等。除首行外每條記錄有一個前驅(qū)，除末尾外每條記錄有一個后繼。線性結(jié)構(gòu)第1章

緒論一、什么是數(shù)據(jù)結(jié)構(gòu)8數(shù)據(jù)結(jié)構(gòu)例2族譜一個數(shù)據(jù)元素也稱為節(jié)點。計算機處理的對象（數(shù)據(jù)元素）存在一種非線性關(guān)系，除首節(jié)點外每個節(jié)點只有一個前驅(qū)，除葉節(jié)點外每個節(jié)點有若干個后繼－－

樹型結(jié)構(gòu)。如八皇后問題。樹型結(jié)構(gòu)爺爺父親伯伯叔叔哥哥弟弟你…………第1章

緒論一、什么是數(shù)據(jù)結(jié)構(gòu)10集合是指若干個或無窮多個具有相同屬性的元素的集體。分為有限集、無限集和空集（）。

集合用大寫字母表示：如M

元素用小寫字母表示：如a第1章

緒論二、數(shù)學(xué)知識

元素與集合的關(guān)系：為屬于和不屬于

如a∈M,b∈M

集合與集合的關(guān)系：有包含和相等

如NM,M=N

123.笛卡爾積

設(shè)有n個集合D1,D2……Dn,此n個集合的笛卡爾積為：D1×D2×…×Dn={<d1,d2,…,dn>|di,i=1,2,…,n}其中<d1,d2,…,dn>稱為n元組，di稱為n元組的第i個分量.第1章

緒論二、數(shù)學(xué)知識例：設(shè)有集合A={1,2}，B={a,b,c}則它們的笛卡兒積為

A×B={<1,a>,<1,b>,<1,c>,<2,a>,<2,b>,<2,c>}若n個集合D1D2…Dn中的元素個數(shù)分別為m1,m2,…,mn，則笛卡兒積中的元素個數(shù)共有m1×m2×…×mn個元組。請問有多少個元組？144.二元關(guān)系第1章

緒論二、數(shù)學(xué)知識

設(shè)R是集合M上的一個關(guān)系。①若<a,b>∈R，則稱a是b的前驅(qū)，b是a的后繼；②若對每一個a∈M，都有<a,a>∈R，則稱關(guān)系R是自反的；③若<a,b>∈R時必有<b,a>∈R，則稱關(guān)系R是對稱的；④若<a,b>∈R、<b,c>∈R時必有<a,c>∈R，則稱R是傳遞的。154.二元關(guān)系上面的R2是對稱的，R3是傳遞的，R4是自反的。第1章

緒論二、數(shù)學(xué)知識例:設(shè)集合M={a,b,c,d,e}則下列各二元組的集合為在集合M上的一個關(guān)系：R1={<a,b>,<b,c>,<c,d>,<d,e>}R2={<a,e>,<a,a>,<d,b>,<e,a>,<b,d>}R3={<a,b>,<b,e>,<c,d>,<d,c>,<a,e>,<c,c>}R4={<a,a>,<b,b>,<c,c>,<d,d>,<e,e>}集合M上的一個關(guān)系實際上反映了M中各元素之間的聯(lián)系。16數(shù)據(jù)(data)：是信息的載體，它可以用計算機表示并加工，如數(shù)、字符、符號等的集合。分為數(shù)值型數(shù)據(jù)和非數(shù)值型數(shù)據(jù)兩類。數(shù)據(jù)元素(dataelement)：是數(shù)據(jù)集合中的一個個體，是數(shù)據(jù)的基本單位。如數(shù)據(jù)集合N={1，2，3，4，5}中整數(shù)1至5均為數(shù)據(jù)元素。

數(shù)據(jù)元素不一定是單個的數(shù)字或字符，也可能是若干個數(shù)據(jù)項的組合，如學(xué)生信息。

學(xué)生（學(xué)號，姓名，性別，成績）數(shù)據(jù)元素有時也稱結(jié)點或記錄。三、基本概念和術(shù)語第1章

緒論17數(shù)據(jù)對象(dataobject)：是具有相同性質(zhì)的數(shù)據(jù)元素的集合。如大寫字母字符的數(shù)據(jù)對象是集合：C={‘A’，’B’，...，’Z’}。數(shù)據(jù)結(jié)構(gòu)(datastructure)：是指同一數(shù)據(jù)對象中各數(shù)據(jù)元素間存在的關(guān)系。用集合論方法定義數(shù)據(jù)結(jié)構(gòu)為：S=（D，R）

數(shù)據(jù)結(jié)構(gòu)S是一個二元組，D是一個數(shù)據(jù)元素的非空有限集合，R是定義在D上的關(guān)系的非空有限集合。 例如一個向量x=(x1,x2,……,xn)，D={x1,x2,……,xn}

R={<x1,x2>,<x2,x3>,……,<xn-1,xn>}。三、基本概念和術(shù)語第1章

緒論18邏輯結(jié)構(gòu)(數(shù)據(jù)結(jié)構(gòu))與物理結(jié)構(gòu)(存儲結(jié)構(gòu))：數(shù)據(jù)結(jié)構(gòu)有邏輯上的數(shù)據(jù)結(jié)構(gòu)和物理上的數(shù)據(jù)結(jié)構(gòu)之分，簡稱為數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)是數(shù)據(jù)間關(guān)系的描述，它只抽象地反映數(shù)據(jù)之間的邏輯關(guān)系，而不管其在計算機中的存儲方式。數(shù)據(jù)的物理結(jié)構(gòu)指的是其邏輯結(jié)構(gòu)在計算機存儲器里的實現(xiàn)，它反映數(shù)據(jù)在計算機內(nèi)部的存儲方式。

三、基本概念和術(shù)語第1章

緒論20數(shù)據(jù)類型(datatype)：是一個值的集合和定義在這個集合上的一組操作的總稱。typedefstruct{intnum;charname[20];charsex;floatscore;}student抽象數(shù)據(jù)類型是指一個數(shù)學(xué)模型以及定義在該模型上的一組操作。如面向?qū)ο笾械念恈lass，C語言中的結(jié)構(gòu)體。三、基本概念和術(shù)語第1章

緒論21數(shù)據(jù)結(jié)構(gòu)與算法

數(shù)據(jù)結(jié)構(gòu)的主要研究內(nèi)容：是數(shù)據(jù)的各種邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)，以及對數(shù)據(jù)的各種操作。邏輯結(jié)構(gòu)線性：表、隊列、棧、數(shù)組、串非線性：樹、圖物理結(jié)構(gòu)數(shù)據(jù)存儲－順序存儲、鏈?zhǔn)酱鎯?shù)據(jù)的操作建立、刪除數(shù)據(jù)結(jié)構(gòu)插入、刪除、修改數(shù)據(jù)元素查詢、排序數(shù)據(jù)元素三、基本概念和術(shù)語第1章

緒論238.數(shù)據(jù)結(jié)構(gòu)的表示設(shè)有集合

D={a,b,c,d,e}abced若有一個關(guān)系

R1={<a,b>,<b,c>,<c,d><d,e>}則圖示法表示該關(guān)系:三、基本概念和術(shù)語第1章

緒論248.數(shù)據(jù)結(jié)構(gòu)的表示設(shè)有集合

D={a,b,c,d,e，f}abcedR2={<a,b>,<a,c>,<b,d><b,e>,<c，f>}則圖示法表示該關(guān)系:f三、基本概念和術(shù)語第1章

緒論26在我們這門課中，所采用的描述語言基本類似于C語言的形式，有時也用自然語言。注釋部分用//或/*...*/表示。

有些地方為方便起見，可能省略變量定義等有關(guān)內(nèi)容。第1章

緒論四、算法描述語言27一個可執(zhí)行的算法不一定是一個好算法，算法的分析很復(fù)雜，通常用計算機執(zhí)行時在時間和空間兩方面的消耗多少作為評價算法優(yōu)劣的標(biāo)準(zhǔn)。這兩個標(biāo)準(zhǔn)分別稱為時間復(fù)雜度和空間復(fù)雜度。一般時間復(fù)雜度考慮的較多。度量一個程序的執(zhí)行時間通常有兩種方法：

事后統(tǒng)計和事前分析估算我們介紹第二種方法。五、算法分析第1章

緒論28時間復(fù)雜度頻度：指一條語句重復(fù)執(zhí)行的次數(shù)。

記作：F(n)時間復(fù)雜度：T(n)=O(F(n))下面舉例說明如何求時間復(fù)雜度？

五、算法分析第1章

緒論301

for(i=0;i<n;i++)

2

for(j=0;j<n;j++)

3{b[i][j]=0;

4

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

5b[i][j]=b[i][j]+a[i][k]*a[k][j];

6}我們以執(zhí)行次數(shù)最多的語句（第5句）進(jìn)行計算：語句頻度為：F(n)=n3

時間復(fù)雜度：T(n)=O(F(n))=O(n3)五、算法分析第1章

緒論314）思考下列程序段的時間復(fù)雜度

①x=x+1;T(n)=O(1)T(n)=O(n)T(n)=O(n2)③

for(j=0;j<n;j++)

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

x=x+1;②for(j=0;j<n;j++)x=x+1;五、算法分析第1章

緒論324）思考下列程序段的時間復(fù)雜度T(n)=O(n2)④for(j=2;j<=n;j++)

for(k=2;k<=j-1;k++)

x=x+1;計算方法：對于外層循環(huán)中的j，從2到n循環(huán)，計算出j每取一個值時，內(nèi)層循環(huán)執(zhí)行的次數(shù)0、1、2、...、n-2，然后累加起來，得到一個n的多項式(n-1)(n-2)/2，取出次數(shù)最高的項即可。五、算法分析第1章

緒論33

常見的時間復(fù)雜度1）O(1)：常量型

2）O(n)、O(n2)、...、O(nk)：多項式型

3）O(log2n)、O(2log2n)：對數(shù)型

4）O(2n)、O(en)：指數(shù)型當(dāng)n增大時，各種時間復(fù)雜度存在下列關(guān)系：O(log2n)<O(n)<O(nlog2n)<O(n)<O(n2)<…<O(2n)<O(n!)五、算法分析第1章

緒論34空間復(fù)雜