計算機軟件基礎緒論

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

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

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

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

數(shù)據(jù)結構的基本概念1.2數(shù)據(jù)結構研究的內(nèi)容和方法1.4*C語言相關內(nèi)容復習1.3算法和算法分析1.1

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

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

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

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

1.

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

2.

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

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

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

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

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

Data_Structure={D,R}

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

根據(jù)數(shù)據(jù)元素間關系的基本特性，有四種基本數(shù)據(jù)結構集合結構

數(shù)據(jù)元素間除“同屬于一個集合”外，無其它關系線性結構

一個對一個，如線性表、棧、隊列樹形結構

一個對多個，如樹圖狀結構

多個對多個，如圖集合結構數(shù)據(jù)結構:

SET=（K,R）

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

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線性結構示意圖數(shù)據(jù)元素之間的聯(lián)系：1:1樹結構數(shù)據(jù)結構

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樹結構示意圖數(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>}圖結構數(shù)據(jù)之間的聯(lián)系：M：N存儲結構（StorageStructure):數(shù)據(jù)在計算機中的表示(或稱映象）稱為數(shù)據(jù)的存儲結構，又稱為物理結構。四種基本的存儲方法：（1）順序存儲方法（順序存儲結構）（2）鏈接存儲方法（鏈式存儲結構）（3）索引存儲方法（4）散列存儲方法同一種邏輯結構可采用不同的存儲方法（以上四種之一或組合），這主要考慮的是運算方便及算法的時空要求。順序存儲結構:用數(shù)據(jù)元素在存儲器中的相對位置來表示數(shù)據(jù)元素之間的邏輯關系。鏈式存儲結構：在每一個數(shù)據(jù)元素中增加一個存放地址的指針，用此指針來表示數(shù)據(jù)元素之間的邏輯關系。

數(shù)據(jù)的邏輯結構

數(shù)據(jù)的存儲結構數(shù)據(jù)的運算

線性結構

非線性結構

順序存儲

鏈式存儲線性表堆棧隊列樹形結構圖形結構數(shù)據(jù)結構的三個方面：

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

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

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

一個完整的算法應該滿足下面五個基本標準：輸入性

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

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

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

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

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

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

例：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))

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

注

空間復雜度S(n)按數(shù)量級遞增順序也與上表類同。復雜度高復雜度低時間復雜度的計算：例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：頻度時間復雜度程序例4：頻度時間復雜度程序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：頻度時間復雜度程序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ù)結構是指計算機處理的

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

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

C.邏輯存儲D.數(shù)據(jù)映像②A.結構B.關系

C.運算D.算法課堂練習3、衡量算法好壞的兩個主要指標有算法的

和

。時間復雜度空間復雜度2、數(shù)據(jù)結構研究數(shù)據(jù)的

、

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

A.結構關系、組織形式

B.邏輯結構、物理結構

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

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

。

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

,

時間復雜度為

。

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ù)結構。特別是數(shù)據(jù)結構的邏輯結構、存儲結構及數(shù)據(jù)運算的含義及其相互關系。數(shù)據(jù)結構的兩大類邏輯結構和四種常用的存儲表示方法。

掌握：算法、算法的時間復雜度和空間復雜度、最壞的和平均時間復雜度等概念，對一般算法要能分析出時間復雜度。小結END復習：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’為字符串結束標志chara[40]=“Iamastudent”;strlen(a)為14不包括‘\0’5.結構體類型結構體由若干個結構體成員組成。定義結構體類型變量：1.定義結構體類型；2.定義結構體類型變量。structstudent{charname[10];intage;floatscore;};structstudentstudent1;structstudentstu2[100];structstudent*p;6.

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

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

邏輯結構a1a2a3a30…d1d2d3d4

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

姓名性別民族年齡其他

例2.鏈式存儲結構…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);}求解：設母