計算機軟件基礎(chǔ)緒論

計算機軟件基礎(chǔ)教學(xué)目的和任務(wù)：1、本課程的任務(wù)是在基礎(chǔ)方面，要求學(xué)生掌握常用數(shù)據(jù)結(jié)構(gòu)的基本概念及其不同的實現(xiàn)方法；在技能方面，通過系統(tǒng)學(xué)習(xí)能夠在不同存儲結(jié)構(gòu)上實現(xiàn)不同的運算，并對算法設(shè)計的方式和技巧有所體會。2、設(shè)置本課程的目的在于為后繼的專業(yè)課打基礎(chǔ)，能夠使用計算機軟件方法解決問題的能力，同時也為從事計算機軟件的開發(fā)提供基礎(chǔ)知識。本課程先修課為C語言。參考教材：學(xué)習(xí)教材：《計算機軟件基礎(chǔ)》，孟彩霞編，西安電子科技大學(xué)出版社參考教材：《數(shù)據(jù)結(jié)構(gòu)(C語言版)》嚴(yán)蔚敏、吳偉民清華大學(xué)出版社

《計算機軟件技術(shù)基礎(chǔ)》,李淑芬等編著出版社：機械工作出版社，2009年8月第一版課程要求：教學(xué)內(nèi)容重點分為1、掌握數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)知識。包括線性表、棧和隊列、樹、二叉樹和圖的部分概念。2、掌握查找及排序相關(guān)的概念、算法和應(yīng)用。課程要求：（1）基本要求

掌握基本原理；熟悉主要算法特點；了解常用算法的設(shè)計思想與結(jié)構(gòu)。注意：理論性強，比較枯燥。學(xué)好理論，才能在實際程序設(shè)計靈活應(yīng)用。（2）學(xué)習(xí)方法a.知識：需要記憶、積累、聯(lián)想、對比——抓重點b.技能：需要訓(xùn)練、經(jīng)驗、方法、技巧——抓特點c.思路：邏輯思維、形象思維（3）認(rèn)真完成書后作業(yè)和補充習(xí)題。

學(xué)時安排授課36+上機18內(nèi)容學(xué)時內(nèi)容學(xué)時緒論3樹和二叉樹8線性表6圖2堆棧和隊列4排序4串查找4數(shù)組2文件遞歸算法復(fù)習(xí)3數(shù)學(xué)軟件硬件數(shù)據(jù)結(jié)構(gòu)的地位是介于數(shù)學(xué)、計算機硬件和計算機軟件三者之間的一門核心課程第一章緒論1.1

數(shù)據(jù)結(jié)構(gòu)的基本概念1.2數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容和方法1.4*C語言相關(guān)內(nèi)容復(fù)習(xí)1.3算法和算法分析1.1

數(shù)據(jù)結(jié)構(gòu)的基本概念為什么學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)數(shù)值計算數(shù)學(xué)模型→選擇計算機語言→編出程序→測試→最終解答。數(shù)值計算的關(guān)鍵是：如何得出數(shù)學(xué)模型（方程）？程序設(shè)計人員比較關(guān)注程序設(shè)計的技巧。非數(shù)值計算數(shù)據(jù)元素之間的相互關(guān)系一般無法用數(shù)學(xué)方程加以描述數(shù)據(jù)描述客觀事物的數(shù)字、字符以及一切能夠輸入到計算機中，并且能夠被計算機程序處理的符號的集合。

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

表示一個事物的一組數(shù)據(jù)，是數(shù)據(jù)的基本單位，又稱結(jié)點。在計算機程序中通常作為一個整體進(jìn)行處理。一個數(shù)據(jù)元素由若干數(shù)據(jù)項構(gòu)成。數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)元素之間具有的關(guān)系，即數(shù)據(jù)的組織形式。數(shù)據(jù)對象具有相同性質(zhì)的數(shù)據(jù)元素組成的集合?；靖拍畋斫Y(jié)構(gòu)學(xué)號姓名性別籍貫出生年月住址06048001趙玲女上海1987.10上海06048002楊揚男北京1987.3北京………………………………學(xué)籍登記表交通圖烏魯木齊蘭州西安呼和浩特北京鄭州成都18921145668676695511842圖結(jié)構(gòu)

非數(shù)值計算問題的數(shù)學(xué)模型不再是數(shù)學(xué)方程，而是諸如表、樹和圖之類的數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)課程研究的是計算機所處理的數(shù)據(jù)元素間的結(jié)構(gòu)關(guān)系及其操作實現(xiàn)的算法

1.

研究數(shù)據(jù)元素之間的客觀聯(lián)系。

2.

研究具有某種邏輯關(guān)系的數(shù)據(jù)在計算機存儲器內(nèi)的存儲方式。

3.研究如何在數(shù)據(jù)的各種結(jié)構(gòu)(邏輯的和物理的)

的基礎(chǔ)上對數(shù)據(jù)實施一系列有效的基本操作。

邏輯結(jié)構(gòu)存儲結(jié)構(gòu)1.2數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容算法數(shù)據(jù)結(jié)構(gòu)：

計算機處理的數(shù)據(jù)元素的組織形式及其相互間的關(guān)系。由數(shù)據(jù)元素的有限集合及所有數(shù)據(jù)元素之間的關(guān)系組成。記為：

Data_Structure={D,R}

其中，D是數(shù)據(jù)元素的有限集，R是所有數(shù)據(jù)元素之間的關(guān)系的有限集合。

根據(jù)數(shù)據(jù)元素間關(guān)系的基本特性，有四種基本數(shù)據(jù)結(jié)構(gòu)集合結(jié)構(gòu)

數(shù)據(jù)元素間除“同屬于一個集合”外，無其它關(guān)系線性結(jié)構(gòu)

一個對一個，如線性表、棧、隊列樹形結(jié)構(gòu)

一個對多個，如樹圖狀結(jié)構(gòu)

多個對多個，如圖集合結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu):

SET=（K,R）

K={01,02,03,04,05,06,07,08,09,10} R={}08010305020704060910集合結(jié)構(gòu)示意圖線性結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)

LINEARITY=（K,R）

K={01,02,03,04,05,06,07,08,09,10}R={<05,01>,<01,03>,<03,08>,<08,02>,<02,07>,<07,04>,<04,06>,<06,09>,<09,10>}05010308020704060910線性結(jié)構(gòu)示意圖數(shù)據(jù)元素之間的聯(lián)系：1:1樹結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)

TREE=（K,R）K={01,02,03,04,05,06,07,08,09,10}R={<01,02>,<01,03>,<01,04>,<02,05>,<02,06>,<03,07>,<03,08>,<03,09>,<04,10>}01020304070809050610樹結(jié)構(gòu)示意圖數(shù)據(jù)之間的聯(lián)系：1：NGraph=(D,R)D={1,2,3,4,5,6,7,8,9}R={<1,2>,<1,3>,<2,4>,<2,5>,<2,6>,<2,8>,<3,2>,<3,4>,<4,5>,<5,7>,<6,7>,<6,9>,<7,9>,<8,9>}圖結(jié)構(gòu)數(shù)據(jù)之間的聯(lián)系：M：N存儲結(jié)構(gòu)（StorageStructure):數(shù)據(jù)在計算機中的表示(或稱映象）稱為數(shù)據(jù)的存儲結(jié)構(gòu)，又稱為物理結(jié)構(gòu)。四種基本的存儲方法：（1）順序存儲方法（順序存儲結(jié)構(gòu)）（2）鏈接存儲方法（鏈?zhǔn)酱鎯Y(jié)構(gòu)）（3）索引存儲方法（4）散列存儲方法同一種邏輯結(jié)構(gòu)可采用不同的存儲方法（以上四種之一或組合），這主要考慮的是運算方便及算法的時空要求。順序存儲結(jié)構(gòu):用數(shù)據(jù)元素在存儲器中的相對位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系。鏈?zhǔn)酱鎯Y(jié)構(gòu)：在每一個數(shù)據(jù)元素中增加一個存放地址的指針，用此指針來表示數(shù)據(jù)元素之間的邏輯關(guān)系。

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

數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的運算

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

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

順序存儲

鏈?zhǔn)酱鎯€性表堆棧隊列樹形結(jié)構(gòu)圖形結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的三個方面：

散列存儲索引存儲串及數(shù)組查找、排序、插入、刪除、修改等1.3算法和算法分析1.算法的定義(1).

算法是用來解決某個特定問題的指令的集合。(2).

算法是由人們組織起來準(zhǔn)備加以實施的一系列有限的基本步驟。2.算法的描述文字形式程序設(shè)計語言形式（如C語言等）偽碼形式3.算法的性質(zhì)

一個完整的算法應(yīng)該滿足下面五個基本標(biāo)準(zhǔn)：輸入性

有0個或多個輸入輸出性有一個或多個輸出(處理結(jié)果)確定性每步定義都是確切、無歧義的有窮性算法應(yīng)在執(zhí)行有窮步后結(jié)束；整個指令序列在有限的時間內(nèi)完成?？尚行裕ㄓ行裕┧惴ㄖ械拿恳粋€步驟都應(yīng)當(dāng)能被有效的執(zhí)行，并得到確定的結(jié)果。例如：被零除的計算動作是不能被有效執(zhí)行的。4.算法設(shè)計目標(biāo)正確性可讀性健壯性高時間效率高空間效率當(dāng)時間效率目標(biāo)和空間效率目標(biāo)發(fā)生矛盾時，應(yīng)先考慮時間效率目標(biāo)5.算法分析時間復(fù)雜度T（n）空間復(fù)雜度S（n）其它（如可讀性、可移植性等）前提條件：算法必須正確

2.源程序編譯的強弱以及所產(chǎn)生的機器代碼質(zhì)量的優(yōu)劣。3.機器執(zhí)行一條指令的時間長短。4.程序中語句的執(zhí)行次數(shù)。1.問題的規(guī)模。

一個程序在計算機中運行時間的多少與諸多因素有關(guān)，其中主要有：4.時間復(fù)雜度稱為時間頻度，記為T（n）

定義：若有一輔助函數(shù)f(n)，當(dāng)n趨于無窮大時，T(n)/f(n)為一不等于零的實常數(shù)，則f(n)為T(n)的同數(shù)量級函數(shù)，記為

T(n)=O(f(n))

稱O(f(n))為時間復(fù)雜度。

例：3n+2=O(n)/*3n+24nforn2*/10n2+4n+2=O(n2)/*10n2+4n+211n2forn5*/6*2n+n2=O(2n) /*6*2n+n27*2nforn4*/常用的計算規(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))

時間復(fù)雜度T(n)按數(shù)量級遞增順序為：

注

空間復(fù)雜度S(n)按數(shù)量級遞增順序也與上表類同。復(fù)雜度高復(fù)雜度低時間復(fù)雜度的計算：例1：{++x;s=0;}2O(1)for(i=1;i<=n;++i){++x;s+=x;}2nO(n)for(j=1;j<=n;++j)for(k=1;k<=n;++k){++x;s+=x;}n*2nO(n2)例2：例3：頻度時間復(fù)雜度程序例4：頻度時間復(fù)雜度程序x=n;//n>1while(x>=(y+1)*(y+1))y++;n1/2-1O(n1/2)例5：x=91;y=100;while(y>0)if(x>100){x=x-10;y--;}elsex++;常數(shù)O(1)例6：頻度時間復(fù)雜度程序O(n3)inti,j,k,x=0;for(i=1;i<=n;i++)for(j=1;j<=i;j++)for(k=1;k<=j;k++)x=x+2;按增長率由小至大的順序排列下列各函數(shù)：

2100,(3/2)n,(2/3)n,nn,n0.5,n!,2n,lgn,nlgn,n3/2

思路：先將題中的函數(shù)分成如下幾類：常數(shù)階：2100對數(shù)階：lgnK次方階：n0.5、n3/2

指數(shù)階(按指數(shù)由小到大排)：nlgn、(3/2)n、2n、n!、nn(2/3)n<2100<lgn<n0.5<n3/2<nlgn<(3/2)n<2n<n!<nn

1、數(shù)據(jù)結(jié)構(gòu)是指計算機處理的

的組織形式以及它們相互之間的

。①A.數(shù)據(jù)元素B.計算方法

C.邏輯存儲D.數(shù)據(jù)映像②A.結(jié)構(gòu)B.關(guān)系

C.運算D.算法課堂練習(xí)3、衡量算法好壞的兩個主要指標(biāo)有算法的

和

。時間復(fù)雜度空間復(fù)雜度2、數(shù)據(jù)結(jié)構(gòu)研究數(shù)據(jù)的

、

和操作實現(xiàn)算法。

A.結(jié)構(gòu)關(guān)系、組織形式

B.邏輯結(jié)構(gòu)、物理結(jié)構(gòu)

C.數(shù)據(jù)元素、數(shù)據(jù)對象

D.數(shù)據(jù)復(fù)雜性、程序復(fù)雜性4、下面程序段的時間復(fù)雜度是

。

i=s=0;while(s<n){i++;s+=i;}O(n)5、算法的時間復(fù)雜度僅與問題的規(guī)模有關(guān)。（）×*還與輸入的元素取值有關(guān)6、下面程序段A[i][j]=0執(zhí)行次數(shù)為

,

時間復(fù)雜度為

。

for(i=1;i<=n;i++)for(j=1;j<=i;j++)A[i][j]=0;n(n+1)/2O(n2)

理解：數(shù)據(jù)，數(shù)據(jù)元素，數(shù)據(jù)項，數(shù)據(jù)結(jié)構(gòu)。特別是數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及數(shù)據(jù)運算的含義及其相互關(guān)系。數(shù)據(jù)結(jié)構(gòu)的兩大類邏輯結(jié)構(gòu)和四種常用的存儲表示方法。

掌握：算法、算法的時間復(fù)雜度和空間復(fù)雜度、最壞的和平均時間復(fù)雜度等概念，對一般算法要能分析出時間復(fù)雜度。小結(jié)END復(fù)習(xí)：C語言的數(shù)據(jù)類型1、基本數(shù)據(jù)類型intshort;long;unsignedfloatfloat;double;longdouble2、指針類型10003i_pointeri地址（i的指針）指針變量1000*i_pointeri100015i=3;3inti;

指針變量的定義

inti;int*i_pointer;i_pointer=&i;i=3;*i_pointer=3;5main(){intx=5;printf(“\n%d”,x);Function1(x);printf(“\n%d”,x)}voidFunction1(intx){x++;printf(“\n%d”,x);}main(){intx=5;printf(“\n%d”,x);Function1(&x);printf(“\n%d”,x)}voidFunction1(int*px){(*px)++;printf(“\n%d”,*px);}值傳送地址傳送x5x6x51000px1000*px63.數(shù)組類型數(shù)組名就是數(shù)組的起始地址數(shù)組作為函數(shù)參數(shù)時，為地址傳遞inta[100];a&a[0],a+1&a[1]……*aa[0],*(a+1)a[1]……4、字符串

字符串定義成字符數(shù)組

‘\0’為字符串結(jié)束標(biāo)志chara[40]=“Iamastudent”;strlen(a)為14不包括‘\0’5.結(jié)構(gòu)體類型結(jié)構(gòu)體由若干個結(jié)構(gòu)體成員組成。定義結(jié)構(gòu)體類型變量：1.定義結(jié)構(gòu)體類型；2.定義結(jié)構(gòu)體類型變量。structstudent{charname[10];intage;floatscore;};structstudentstudent1;structstudentstu2[100];structstudent*p;6.

自定義類型typedefcharelemtype;typedefstructstudent{charname[10];intage;floatscore;}stu;elemtypea;stustudent1;

數(shù)據(jù)項具有獨立含義的最小標(biāo)識單位,是數(shù)據(jù)的最小單位數(shù)據(jù)元素數(shù)據(jù)項學(xué)號姓名性別籍貫出生年月住址06048001趙玲女上海1987.10上海06048002楊揚男北京1987.3北京………………………………

邏輯結(jié)構(gòu)a1a2a3a30…d1d2d3d4

…d30a2a1a3a4a30存儲結(jié)構(gòu)1.順序存儲結(jié)構(gòu)線性結(jié)構(gòu)（線性表）劉曉光馬廣生王民…張玉華男男…女男漢回壯…漢161721…25……………

姓名性別民族年齡其他

例2.鏈?zhǔn)酱鎯Y(jié)構(gòu)…d1d2d3d4

a1a2a3a30∧list…a2a1a4a3d4d1d5d3百錢買百雞問題:100元錢買100只雞，母雞每只5元，公雞每只3元，小雞3只1元，問共可以買多少只母雞、多少只公雞、多少只小雞？

for(i=0;i<=100;i++)for(j=0;j<=100;j++) for(k=0;k<=100;k++) {if(k%3==0&&(i+j+k)==100&&(5*i+3*j+k/3)==100) printf(“%d,%d,%d\n”,i,j,k);}求解：設(shè)母