數(shù)據(jù)結(jié)構(gòu)耿國華高等教育出版社

用C語言描述西北師范大學(xué)經(jīng)濟(jì)管理學(xué)院----信息管理系數(shù)據(jù)結(jié)構(gòu)課件*1第1章 緒

論關(guān)于學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的基本概念(定義)數(shù)據(jù)結(jié)構(gòu)的內(nèi)容（研究范圍）算法設(shè)計(jì)算法描述工具對算法作性能評價(jià)數(shù)據(jù)結(jié)構(gòu)與C語言表示1.724/4/20201.1

數(shù)據(jù)結(jié)構(gòu)的基本概念（定義）數(shù)據(jù)結(jié)構(gòu)的相關(guān)名詞：數(shù)據(jù)（Data）數(shù)據(jù)元素（Data

Element）數(shù)據(jù)對象（Data

Object）數(shù)據(jù)結(jié)構(gòu)（Data

Structure）數(shù)據(jù)類型(Data

Type)數(shù)據(jù)抽象與抽象數(shù)據(jù)類型34/4/2020數(shù)據(jù)（Data）定義：數(shù)據(jù)是描述客觀事物的數(shù)值、字符以及能輸入機(jī)器且能被處理的各種符號集合。數(shù)據(jù)包含整型、實(shí)型、布爾型、圖象、字符、聲音等一切可以輸入到計(jì)算機(jī)中的符號集合。目標(biāo)程序（.obj）可執(zhí)行程序（.exe）C鏈接程序例如對C源程序C編譯程序源程序（.c）44/4/2020數(shù)據(jù)元素（Data

Element）學(xué)

號 姓

名 性

別

籍貫

出生年月

住址101

趙虹玲

女

河北

1983.11

北京...

...

...

...

...

...數(shù)據(jù)元素54/4/2020定義：數(shù)據(jù)元素是組成數(shù)據(jù)的基本單位

，是數(shù)據(jù)集合的個(gè)體，在計(jì)算機(jī)中通常作為一個(gè)整體進(jìn)行考慮和處理。例如：數(shù)據(jù)項(xiàng)數(shù)據(jù)對象（Data

Object）64/4/2020定義：數(shù)據(jù)對象是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。例如：整數(shù)集合：N={0，±1，±2，…}無限集字符集合：C={ˊAˊ，Bˊ，…，ˊZˊ}有限集數(shù)據(jù)結(jié)構(gòu)（Data

Structure）定義：數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素集合，是帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合，它指的是數(shù)據(jù)元素之間的相互關(guān)系，即數(shù)據(jù)的組織形式。例如表結(jié)構(gòu)：學(xué)

號 姓

名 性

別

籍貫

出生年月

住址101

趙虹玲

女

河北

1983.11

北京...

...

...

...

...

...74/4/2020數(shù)據(jù)結(jié)構(gòu)（Data

Structure）樹型結(jié)構(gòu)84/4/2020圖結(jié)構(gòu)12543數(shù)據(jù)類型(Data

Type)94/4/2020定義：數(shù)據(jù)類型是一組性質(zhì)相同的值集合以

及定義在這個(gè)值集合上的一組操作的總稱。如在高級語言中，整型類型的取值范圍為：-32768~+32767，運(yùn)算符集合為加、減、乘、除、取模，即+、-、*、/、%。數(shù)據(jù)類型(Data

Type)104/4/2020高級語言中的數(shù)據(jù)類型分為兩大類：原子類型，其值不可分解。如C語言中的標(biāo)準(zhǔn)類型（整型、實(shí)型、字符型、）。結(jié)構(gòu)類型，其值是由若干成分按某種結(jié)構(gòu)組成的，因此是可以分解的，并且它的成分可以是非結(jié)構(gòu)的，也可以是結(jié)構(gòu)的。指針類型屬于哪種類型？數(shù)據(jù)抽象與抽象數(shù)據(jù)類型數(shù)據(jù)的抽象抽象數(shù)據(jù)類型(Abstract

Data

Type)抽象數(shù)據(jù)類型實(shí)現(xiàn)ADT的表示與實(shí)現(xiàn)面向?qū)ο蟮母拍罱Y(jié)構(gòu)化的開發(fā)方法與面向?qū)ο箝_發(fā)方法不同點(diǎn)114/4/20201.2數(shù)據(jù)結(jié)構(gòu)的內(nèi)容邏輯結(jié)構(gòu)存儲結(jié)構(gòu)運(yùn)算集合124/4/2020邏輯結(jié)構(gòu)134/4/2020定義：數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間邏輯關(guān)系描述。形式化描述：Data_Structure=（D,R）其中D是數(shù)據(jù)元素的有限集，R是D上關(guān)系的有限集。四類基本的結(jié)構(gòu)集合結(jié)構(gòu)、線性結(jié)構(gòu)、樹型結(jié)構(gòu)、圖狀結(jié)構(gòu)。集合結(jié)構(gòu)定義：結(jié)構(gòu)中的數(shù)據(jù)元素之間除了同屬于一個(gè)集合的關(guān)系外，無任何其它關(guān)系。例如：集合144/4/2020線性結(jié)構(gòu)154/4/2020定義：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在著一對一的線性關(guān)系。例如：線性表樹型結(jié)構(gòu)164/4/2020定義：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在著一對多的層次關(guān)系。例如：樹圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)174/4/2020定義：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在著多對多的任意關(guān)系。例如：圖綜上所述，數(shù)據(jù)的邏輯結(jié)構(gòu)可概括為：線性結(jié)構(gòu)——線性表、棧、隊(duì)、字符串?dāng)?shù)組、廣義表邏輯結(jié)構(gòu)非線性結(jié)構(gòu)——樹、圖184/4/2020邏輯結(jié)構(gòu)存儲結(jié)構(gòu)194/4/2020定義：存儲結(jié)構(gòu)（又稱物理結(jié)構(gòu)）是邏輯結(jié)構(gòu)在計(jì)算機(jī)中存儲映象，是邏輯結(jié)構(gòu)在計(jì)算機(jī)中的實(shí)現(xiàn)，它包括數(shù)據(jù)元素的表示和關(guān)系的表示。形式化描述：D要存入機(jī)器中，建立一從D的數(shù)據(jù)元素到存儲空間M單元映象S

，D→M，即對于每一個(gè)d，d∈D,都有唯一的z∈M使S（D）=Z,同時(shí)這個(gè)映象必須明顯或隱含地體現(xiàn)關(guān)系R。邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)的關(guān)系為：存儲結(jié)構(gòu)是邏輯關(guān)系的映象與元素本身映象，是數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)；邏輯結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)的抽象。數(shù)據(jù)元素之間關(guān)系在計(jì)算機(jī)中的表示方法：·順序映象（順序存儲結(jié)構(gòu)）·非順序映象（非順序存儲結(jié)構(gòu)）204/4/2020存儲結(jié)構(gòu)運(yùn)算集合214/4/2020例如工資表：編

號姓

名性別基本工資工齡工資應(yīng)扣工資實(shí)發(fā)工資100001張愛芬女345．67145．4530．00451．12100002李

林男445．90185．6045．00586．50100003劉曉峰男345．00130．0025．00450．00100004趙

俊女560．90225．9065．00721．80100005孫

濤男450．60190．8050．00591．80…………………100121張興強(qiáng)男1025．98365．53100．001291.51數(shù)據(jù)結(jié)構(gòu)的內(nèi)容224/4/2020綜上所述，數(shù)據(jù)結(jié)構(gòu)的內(nèi)容可歸納為三個(gè)部分，邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和運(yùn)算集合：按某種邏輯關(guān)系組織起來的一批數(shù)據(jù)，按一定的映象方式把它存放在計(jì)算機(jī)存貯器中，并在這些數(shù)據(jù)上定義了一個(gè)運(yùn)算的集合，就叫做數(shù)據(jù)結(jié)構(gòu)。1.3算法算法（Algorithm）定義算法的特性算法設(shè)計(jì)的要求234/4/2020算法（Algorithm）定義244/4/2020定義：Algorithm

is

a

finite

set

ofrules

which

gives

a

sequence

ofoperation

for

solving

a

specific

typeof

problem.算法是規(guī)則的有限集合，是為解決特定問題而規(guī)定的一系列操作。算法的特性254/4/2020有限性：有限步驟之內(nèi)正常結(jié)束，不能形成無窮循環(huán)確定性：算法中的每一個(gè)步驟必須有確定含義，無二 義性得以實(shí)現(xiàn)。輸入：有多個(gè)或0個(gè)輸入輸出：至少有一個(gè)或多個(gè)輸出?？尚行裕涸瓌t上能精確進(jìn)行，操作可通過已實(shí)現(xiàn)基本 運(yùn)算執(zhí)行有限次而完成。算法設(shè)計(jì)的要求264/4/2020算法特征：

算法的正確性可讀性健壯性高效率和低存儲量例如要求n個(gè)數(shù)的最大值問題給出算法如下：max:=0;for（i=1

；i<=

n

;i++）{

scanf("%f",

x);if

(x>max)

max=x;}1.4算法描述的工具概述：算法+數(shù)據(jù)結(jié)構(gòu)=程序算法、語言、程序的關(guān)系設(shè)計(jì)實(shí)現(xiàn)算法過程步驟類描述算法的語言選擇274/4/2020算法、語言、程序的關(guān)系284/4/2020算法：描述了數(shù)據(jù)對象的元素之間的關(guān)系（包括數(shù)據(jù)邏輯關(guān)系、存貯關(guān)系描述）。描述算法的工具：算法可用自然語言、框圖或高級程序設(shè)計(jì)語言進(jìn)行描述。程序是算法在計(jì)算機(jī)中的實(shí)現(xiàn)。設(shè)計(jì)實(shí)現(xiàn)算法過程步驟294/4/2020找出與求解有關(guān)的數(shù)據(jù)元素之間的關(guān)系確定在某一數(shù)據(jù)對象上所施加運(yùn)算考慮數(shù)據(jù)元素的存儲表示選擇描述算法的語言設(shè)計(jì)實(shí)現(xiàn)求解的算法，并用程序語言加以描述。類描述算法的語言選擇304/4/2020類語言：類語言是接近于高級語言而又不是嚴(yán)格的高級語言，具有高級語言的一般語句設(shè)施，撇掉語言中的細(xì)節(jié)，以便把注意力主要集中在算法處理步驟本身的描述

上。對C語言作以下描述：314/4/2020賦值語句簡單賦值〈變量名〉=〈表達(dá)式〉〈變量〉++，〈變量〉--，串聯(lián)賦值〈變量1〉=〈變量2〉=〈變量3〉=…=〈變量k〉=〈表達(dá)式〉對C語言作以下描述：324/4/2020成組賦值(<變量>,<變量2>,<變量3>,…<變量k〉=(<表達(dá)式1>,<表達(dá)式2>,<表達(dá)式3>,…<表達(dá)式k>)〈數(shù)組名1〉[下標(biāo)1][下標(biāo)2]=〈數(shù)組名2〉[下標(biāo)1][下標(biāo)2]條件賦值〈變量名〉=〈條件表達(dá)式〉？〈表達(dá)式1〉:〈表達(dá)式2〉對C語言作以下描述：334/4/20204.條件選擇語句·if(<表達(dá)式>)語句;·if(<表達(dá)式>)語句1;else語句2;·情況語句344/4/2020……switch(<表達(dá)式>）case判斷值n:{case判斷值1:語句組n;語句組1；break;break;[default:case判斷值2:語句組；語句組2；break;]break;}對C語言作以下描述：對C語言作以下描述：354/4/20205.循環(huán)語句·for語句for(<表達(dá)式1>；<表達(dá)式2>；<表達(dá)式3>）{循環(huán)體語句；}·while語句364/4/2020while(<條件表達(dá)式>）{循環(huán)體語句；}對C語言作以下描述：·do–while語句do{循環(huán)體語句}while(<條件表達(dá)式>）1.5對算法作性能評價(jià)評價(jià)算法的標(biāo)準(zhǔn)：評價(jià)一個(gè)算法主要看這個(gè)算法所占用機(jī)器資源的多少，而這些資源中時(shí)間代價(jià)與空間代價(jià)是兩個(gè)主要的方面，通常是以算法執(zhí)行所需的機(jī)器時(shí)間和所占用的存儲空間來判斷一個(gè)算法的優(yōu)劣。性能評價(jià)有關(guān)數(shù)量關(guān)系計(jì)算374/4/2020性能評價(jià)384/4/2020定義：對問題規(guī)模與該算法在運(yùn)行時(shí)所占的空間S與所耗費(fèi)的時(shí)間T給出一個(gè)數(shù)量關(guān)系的評價(jià)。問題規(guī)模N—對不同的問題其含義不同：對矩陣是階數(shù)；對多項(xiàng)式運(yùn)算是多項(xiàng)式項(xiàng)數(shù)；對圖是頂點(diǎn)個(gè)數(shù)；對集合運(yùn)算是集合中元素個(gè)數(shù)。有關(guān)數(shù)量關(guān)系計(jì)算394/4/2020數(shù)量關(guān)系評價(jià)體現(xiàn)在時(shí)間——算法在機(jī)器中所耗費(fèi)時(shí)間。數(shù)量關(guān)系評價(jià)體現(xiàn)在空間——算法在機(jī)器中所占存儲量。關(guān)于算法執(zhí)行時(shí)間語句頻度算法的時(shí)間復(fù)雜度數(shù)據(jù)結(jié)構(gòu)中常用的時(shí)間復(fù)雜度頻率計(jì)數(shù)最壞時(shí)間復(fù)雜度算法的空間復(fù)雜度關(guān)于算法執(zhí)行時(shí)間404/4/2020定義：一個(gè)算法的執(zhí)行時(shí)間大致上等于其所有語句執(zhí)行時(shí)間的總和，對于語句的執(zhí)行時(shí)間是指該條語句的執(zhí)行次數(shù)和執(zhí)行一次所需時(shí)間的乘積。分析：不是針對實(shí)際執(zhí)行時(shí)間的精確地算出算法執(zhí)行具體時(shí)間，而是針對算法中語句的執(zhí)行次數(shù)做出估計(jì)，從中得到算法執(zhí)行時(shí)間的信息。語句頻度414/4/2020定義：語句頻度是指該語句在一個(gè)算法中重復(fù)執(zhí)行的次數(shù)。例如：兩個(gè)矩陣相乘算法語句1234for（i=0；i<

n;i++）for

（j=0；j<n;j++）{c[i][j]=0;for

(k=0;k<

n;

k++)對應(yīng)的語句頻度nn2n2n3c[i][j]=c[i][j]+a[i][k]*b[k][j];n3}總執(zhí)行次數(shù)：Tn=2n3+2n2

+n算法的時(shí)間復(fù)雜度424/4/2020算法的時(shí)間復(fù)雜度，即是算法的時(shí)間量度記做：

T(n)=O(f(n))例如給出X=X+1x=x+1；時(shí)間復(fù)雜度為O(1)，稱為常量階；for(i=1;i<=n;i++)x=x+1;時(shí)間復(fù)雜度為O(n)，稱為線性階；for

(i=1;

i<=

n;i++)for(j=1;j<=n;j++)x=x+1;時(shí)間復(fù)雜度為O(n2),稱為平方階。常用的時(shí)間復(fù)雜度頻率計(jì)數(shù)434/4/2020數(shù)據(jù)結(jié)構(gòu)中常用的時(shí)間復(fù)雜度頻率計(jì)數(shù)有7個(gè):O(n)線性型O(2n)指數(shù)型O(n2)平方型O(log2n)對數(shù)型–O(1)常數(shù)型–O(n3)立方型–O(nlog2n)二維型按時(shí)間復(fù)雜度由小到大排列的頻率表：常用的時(shí)間復(fù)雜度頻率計(jì)數(shù)444/4/2020常用的時(shí)間復(fù)雜度頻率表：log2nnnlog2nn2n32n一般講：前3種可實(shí)現(xiàn)，后3種雖理論上是可實(shí)現(xiàn)的，實(shí)際上只有對N

限制在很小范圍才有意義，當(dāng)N較大時(shí)，不可能實(shí)現(xiàn)。010112122484248166416382464512256416642565096655365321601024327682147483648最壞時(shí)間復(fù)雜度454/4/2020定義：討論算法在最壞情況下的時(shí)間復(fù)雜度，即分析最壞情況下以估計(jì)出算法執(zhí)行時(shí)間的上界。例如冒泡排序算法void

bubble(int

a[],

int

length){將a中整數(shù)數(shù)組重新排序，達(dá)到遞增有序}int

i=0,

j,

temp;int

change

;do{change=false

;for(j=1;j<length-i;j++)if(

a[j]>a[j+1])464/4/2020{temp=

a[j];a[j]=a[j+1];a[j+1]=temp;change=true;}i=i+1;}while(i<length

||

change==true

)}最壞時(shí)間復(fù)雜度算法的空間復(fù)雜度474/4/2020定義：用空間復(fù)雜度作為算法所需存儲空間的量度，記做：

S(n)=O(f

(n))

。1.6 數(shù)據(jù)結(jié)構(gòu)與C語言表示484/4/20201.6.1數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì)的關(guān)聯(lián)性問題描述：欲求1名學(xué)生10次C語言程序設(shè)計(jì)的測試成績總分與平均分。其中10次測驗(yàn)的成績分別為：80，85，77，56，68，83，90，92，80，98。程序示例1-1：494/4/2020main(){

int

sum，verage；/*總分，平均分*//*10個(gè)變量存10次成績*//*分別賦值*/intt1,t2,t3,t4,t5,t6,t7,t8,t9,t10；t1=80；t2=85；t3=77；t4=56；

t5=68；t6=83；t7=90；t8=92；t9=80；t10=98;sum=

t1+t2+t3+t4+t5+t6+t7+t8+t9+t10;/*計(jì)算總分*/average=sum/10;

/*計(jì)算平均分*/printf(“總分=%d\n”,sum);printf(“平均分=%d\n”,average);}根據(jù)測試次數(shù)與測試成績的關(guān)系，采用數(shù)組結(jié)構(gòu)存儲測驗(yàn)成績，提高了程序的適用范圍。main(){

int

sum，erage；int

i;int

t[10]=80，85，77，56，68，83，90，92，80，98}/*分別賦值*/504/4/2020/*總分置初值*/sum=0;for

(i=0;

i<10;

i++)sum=sum+t[i];average=sum/10;/*計(jì)算平均分*/printf(“總分=%d\n”,sum);printf(“平均分=%d\n”,average);}程序示例1-2：1.6.2結(jié)構(gòu)化程序設(shè)計(jì)與函數(shù)的模塊化514/4/2020結(jié)構(gòu)化程序設(shè)計(jì)：是為使程序具有合理的結(jié)構(gòu)，以保證程序正確性而規(guī)定的一套程序設(shè)計(jì)的方法。程序設(shè)計(jì)的實(shí)質(zhì)：算法+數(shù)據(jù)結(jié)構(gòu)=程序即“程序是在數(shù)據(jù)的特定表示方式的基礎(chǔ)上，對抽象算法的具體描述”。程序結(jié)構(gòu)=控制結(jié)構(gòu)+數(shù)據(jù)結(jié)構(gòu)①

結(jié)構(gòu)化程序設(shè)計(jì)目的通過設(shè)計(jì)結(jié)構(gòu)良好的程序，以程序的靜態(tài)良好結(jié)構(gòu)保證程序動態(tài)執(zhí)行的正確性，使程序易理解、易調(diào)試、易維護(hù)，以提高軟件開發(fā)的效率，減少出錯(cuò)率。②結(jié)構(gòu)化程序設(shè)計(jì)的構(gòu)成單元任何程序都可由順序、選擇、重復(fù)三種基本控制結(jié)構(gòu)來組成。③結(jié)構(gòu)化程序設(shè)計(jì)方法其一：“自頂向下，逐步求精”的設(shè)計(jì)思想；其二：“獨(dú)立功能，一個(gè)入口，一個(gè)出口“的模塊化結(jié)構(gòu)；其三：“僅用三種基本控制結(jié)構(gòu)”的設(shè)計(jì)原則524/4/20201.6.3面向?qū)ο笈c抽象數(shù)據(jù)類型534/4/20201.面向?qū)ο蟮母拍睿好嫦驅(qū)ο?對象+類+繼承+通信對象：指在應(yīng)用問題中出現(xiàn)的各種實(shí)體、事件、規(guī)格說明等。類：具有相同屬性和服務(wù)的對象繼承：是面向?qū)ο蠓椒ǖ淖钣刑厣姆矫妗Ｃ嫦驅(qū)ο蟪绦蛟O(shè)計(jì)的特點(diǎn)是封裝性、繼承性和多態(tài)性與數(shù)據(jù)結(jié)構(gòu)密切相關(guān)的是定義在數(shù)據(jù)結(jié)構(gòu)上的一組操作?；静僮髦饕校孩挪迦耄涸跀?shù)據(jù)結(jié)構(gòu)中的指定位置上增添新的數(shù)據(jù)元素；⑵刪除：刪去數(shù)據(jù)結(jié)構(gòu)中某個(gè)指定數(shù)據(jù)元素；⑶更新：改變數(shù)據(jù)結(jié)構(gòu)中某個(gè)元素的值，在概念上等價(jià)于刪除和插入操作的組合；⑷查找：在數(shù)據(jù)結(jié)構(gòu)中尋找滿足某個(gè)特定要求的數(shù)據(jù)元素（的位置和值）；⑸排序：（在線性結(jié)構(gòu)中）重新安排數(shù)據(jù)元素之間的邏輯順序關(guān)系，使數(shù)據(jù)元素按值由小到大或由大到小的次序排列。544/4/2020結(jié)構(gòu)化與面向?qū)ο箝_發(fā)方法的不同點(diǎn)554/4/2020

結(jié)構(gòu)化的開發(fā)方法：是面向過程的開發(fā)方法，首先著眼于系統(tǒng)要實(shí)現(xiàn)的功能。面向?qū)ο蟮拈_發(fā)方法：–首先著眼于應(yīng)用問題所涉及的對象，包括對象、對象屬性和要求的操作，從而建立對象結(jié)構(gòu)和為解決問題需要執(zhí)行的時(shí)間序列。2．抽象數(shù)據(jù)類型與問題求解方法564/4/20定義：抽象數(shù)據(jù)類型（簡稱ADT）是指基于一類邏輯關(guān)系的數(shù)據(jù)類型以及定義在這個(gè)類型之上的一組操作。一個(gè)抽象數(shù)據(jù)類型確定了一個(gè)模型，但將模型的實(shí)現(xiàn)細(xì)節(jié)隱藏起來；它定義了一組運(yùn)算，但將運(yùn)算的實(shí)現(xiàn)過程隱藏起來。用抽象數(shù)據(jù)類型的概念來指導(dǎo)問題的求解過程：數(shù)學(xué)模型抽象數(shù)據(jù)模型數(shù)據(jù)結(jié)構(gòu)非形式算20

法偽語言程序可執(zhí)行程序數(shù)據(jù)的抽象574/4/2020匯編語言中十進(jìn)制表示的數(shù)據(jù)98.65、9.6E3等,它們是二進(jìn)制數(shù)據(jù)的抽象;高級語言中，給出更高一級的數(shù)據(jù)抽象，如整型、實(shí)型、字符型等，還可以進(jìn)一步定義更高級的數(shù)據(jù)抽象，如各種表、隊(duì)、棧、樹、圖、窗口、管理器等復(fù)雜的抽象數(shù)據(jù)類型。抽象數(shù)據(jù)類型584/4/2020線性表的抽象數(shù)據(jù)類型的描述：–ADT

Linear_list–數(shù)據(jù)元素

所有ai屬于同一數(shù)據(jù)對象，i=1，2，……，n

n≥0；–邏輯結(jié)構(gòu)

所有數(shù)據(jù)元素ai（i=1，2，…，n-1）存在次序關(guān)系–<ai，ai+1>，ai無前趨，an無后繼；––––––操作

設(shè)L為Linear_listInitial(L)初始化空線性表；Length(L)求線性表的表長；Get(L,i)取線性表的第i個(gè)元素；Insert(L,i,b)在線性表的第i個(gè)位置插入元素b；Delete(L,i)刪除線性表的第i個(gè)元素；抽象數(shù)據(jù)類型實(shí)現(xiàn)594/4/2020實(shí)現(xiàn)的三種方法：傳統(tǒng)的面向過程的程序設(shè)計(jì)“包”、“模型”的設(shè)計(jì)方法面向?qū)ο蟮某绦蛟O(shè)計(jì)（Object

OrientedProgramming，簡稱OOP）ADT的表示與實(shí)現(xiàn)604/4/2020ADT的定義：ADT

<ADT名>{數(shù)據(jù)對象:<數(shù)據(jù)對象的定義>結(jié)構(gòu)關(guān)系:<結(jié)構(gòu)關(guān)系的定義>基本操作:<基本操作的定義>}ADT

<ADT名>基本操作的定義格式為：<操作名稱>(參數(shù)表)操作前提:<操作前提描述>操作結(jié)果:<操作結(jié)果描述>關(guān)于參數(shù)傳遞：參數(shù)表中的參數(shù)有值參和變參兩種。用標(biāo)準(zhǔn)C語言表示和實(shí)現(xiàn)ADT描述時(shí)，主要有兩個(gè)方面：一、通過結(jié)構(gòu)體將int、float等固有類型組合到一起,構(gòu)成一個(gè)結(jié)構(gòu)類型,再用typedef為該類型或該類型指針重新起一個(gè)名字。二、用C語言函數(shù)實(shí)現(xiàn)各操作。614/4/2020ADT的表示與實(shí)現(xiàn)1.6.4算法描述規(guī)范與設(shè)計(jì)風(fēng)格算法表示格式與函數(shù)模塊化算法表示格式[函數(shù)返回值類型]函數(shù)名（[形式參數(shù)及說明]）{內(nèi)部數(shù)據(jù)說明；執(zhí)行語句組；}/*函數(shù)名*/624/4/20201.6.4算法描述規(guī)范與設(shè)計(jì)風(fēng)格634/4/2020算法表示格式與函數(shù)模塊化函數(shù)的模塊化[包含文件語句]

[宏定義語句][自定義類型語句][所有子函數(shù)的原型說明]

[子函數(shù)1定義]...[子函數(shù)n定義]

[主函數(shù)定義]1.6.4算法描述規(guī)范與設(shè)計(jì)風(fēng)格算法描述要點(diǎn)加上必要的注釋注釋形式可以用/*字符串*/避免函數(shù)返回值隱含說明預(yù)定義常量和類型 #define

TRUE

1#

define

FALSE

0#

define

MAXSIZE

100#

define

OK

1#

define

ERROR

0644/4/2020exit語句：表示出現(xiàn)異常情況時(shí)，控制退出函數(shù)。1.6.4算法描述規(guī)范與設(shè)計(jì)風(fēng)格2.算法描述要點(diǎn)?使用有意義的函數(shù)名與變量名?避免可能出現(xiàn)的二義性表達(dá)?規(guī)范多分支轉(zhuǎn)向?簡化輸入、輸出表述?注意不同的退出語句區(qū)別return<表達(dá)式>或return：用于函數(shù)結(jié)束。break語句：可用在循環(huán)語句或switch語句中結(jié)束循環(huán)過程或跳出情況語句。continue語句：可用在循環(huán)語句中結(jié)束本次循環(huán)過程，進(jìn)入下一次循環(huán)過程。4/4/2020651.6.4算法描述規(guī)范與設(shè)計(jì)風(fēng)格664/4/2020與參數(shù)傳遞的相關(guān)技術(shù)變量的作用域全局變量：程序中所有函數(shù)都可以訪問的量局部變量：只能在該函數(shù)中訪問的量。參數(shù)傳遞方式參數(shù)傳遞是函數(shù)之間進(jìn)行信息通訊的重要渠道。其參數(shù)傳遞的主要方式有傳值和傳地址兩類。函數(shù)參數(shù)表中的參數(shù)有兩種：第一種參數(shù)只為操作提供待處理數(shù)據(jù),又稱值參；第二種參數(shù)既能為操作提供待處理數(shù)據(jù)，又能返回操作結(jié)果，也稱變量參數(shù)。關(guān)于參數(shù)傳遞示例源程序：#include

<stdio.h>viod

swap1(int

a,int

b){

int

c;c=a;

a=b;

b=c;printf(“swap1中的a=%d,b=%d”,a,b);}viod

swap2(int

*a,int

*b){

int

c;c=*a,

*a=*b,

*b=c;}674/4/2020void

main(){

int

x=100,y=800;684/4/2020/*輸出調(diào)用swap1后的數(shù)據(jù)*/swap1(x,y);/*調(diào)用函數(shù)swap1()*/printf(“\n調(diào)用swap1后x=%d,y=%d”,x,y);x=100;y=800;/*輸出調(diào)用swap2后的數(shù)據(jù)*/swap2(&x,&y);/*調(diào)用函數(shù)swap2()*/printf(“\n調(diào)用swap2后x=%d,y=%d”,x,y);}關(guān)于參數(shù)傳遞示例源程序：1.6.4算法描述規(guī)范與設(shè)計(jì)風(fēng)格694/4/20204.函數(shù)結(jié)果的帶出方式三種帶出方式:全程量、函數(shù)返回值、傳址參數(shù)通過參數(shù)表的參數(shù)傳遞是一種參數(shù)顯式傳遞方式，而通過全局變量是一種隱式參數(shù)傳遞，一個(gè)函數(shù)中對全局變量的改變會影響其它程序的調(diào)用，使用全局變量必須注意這個(gè)問題。若函數(shù)結(jié)果需要帶出多個(gè)值，該怎樣實(shí)現(xiàn)?可以采用①全局變量方式帶出，②通過地址傳遞帶出（數(shù)組方式、結(jié)構(gòu)體方式、指針方式）兩類方式之一來實(shí)現(xiàn)。①全局變量方式：704/4/2020{//給最大值最小值賦初值int

i,max;max=MIN=a[0];for

(i=0;i<n;i++){if(a[i]>max)

max=a[i];if

(a[i]<MIN)

MIN=a[i];}return(max);}一個(gè)全局變量方式帶出的例子int

MIN;

/*全局變量*/int

fun1(int

a[],int

n)/*通過函數(shù)return返回最大值，通過全局變量MIN帶回最小值*/int

*fun2(int

a[],int

n)/*將最大、最小值放到數(shù)組b中，通過return返回*/714/4/2020{//給最大值最小值賦初值static

int

b[2];b[0]=b[1]=a[0];int

i;for

(i=1;i<n;i++){if

(a[i]>b[0])b[0]=a[i];if

(a[i]<b[1])b[1]=a[i];}return(b);}數(shù)組方式帶出的例子Data

*fun3(int

a[],int

n)/*將最大、最小值放到結(jié)構(gòu)體指針p中，通過return返回*/724/4/2020{//指針初始化//給最大值最小值賦初值Data

*p;int

i;p=(Data

*)malloc(sizeof(Data

*));p->max=p->min=a[0];for(i=1;i<n;i++){if

(a[i]>p->max)p->max=a[i];if

(a[i]<p->min)p->min=a[i];}retu