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

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

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

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

數據結構的基本概念1.2數據結構研究的內容和方法1.4*C語言相關內容復習1.3算法和算法分析1.1

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

數據元素

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

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

1.

研究數據元素之間的客觀聯系。

2.

研究具有某種邏輯關系的數據在計算機存儲器內的存儲方式。

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

的基礎上對數據實施一系列有效的基本操作。

邏輯結構存儲結構1.2數據結構研究的內容算法數據結構：

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

Data_Structure={D,R}

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

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

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

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

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

多個對多個，如圖集合結構數據結構:

SET=（K,R）

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

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線性結構示意圖數據元素之間的聯系：1:1樹結構數據結構

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

數據的邏輯結構

數據的存儲結構數據的運算

線性結構

非線性結構

順序存儲

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

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

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

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

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

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

2.源程序編譯的強弱以及所產生的機器代碼質量的優劣。3.機器執行一條指令的時間長短。4.程序中語句的執行次數。1.問題的規模。

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

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

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*/常用的計算規則：1.加法規則

T(n)=T1(n)+T2(n)=O(f1(n))+O(f2(n))

=O(max(f1(n),f2(n)))

2.乘法規則

T(n)=T1(n)×T2(n)=O(f1(n))×O(f2(n))=O(f1(n)×f2(n))

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

注

空間復雜度S(n)按數量級遞增順序也與上表類同。復雜度高復雜度低時間復雜度的計算：例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++;常數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;按增長率由小至大的順序排列下列各函數：

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

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

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

1、數據結構是指計算機處理的

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

。①A.數據元素B.計算方法

C.邏輯存儲D.數據映像②A.結構B.關系

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

和

。時間復雜度空間復雜度2、數據結構研究數據的

、

和操作實現算法。

A.結構關系、組織形式

B.邏輯結構、物理結構

C.數據元素、數據對象

D.數據復雜性、程序復雜性4、下面程序段的時間復雜度是

。

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

,

時間復雜度為

。

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

理解：數據，數據元素，數據項，數據結構。特別是數據結構的邏輯結構、存儲結構及數據運算的含義及其相互關系。數據結構的兩大類邏輯結構和四種常用的存儲表示方法。

掌握：算法、算法的時間復雜度和空間復雜度、最壞的和平均時間復雜度等概念，對一般算法要能分析出時間復雜度。小結END復習：C語言的數據類型1、基本數據類型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.數組類型數組名就是數組的起始地址數組作為函數參數時，為地址傳遞inta[100];a&a[0],a+1&a[1]……*aa[0],*(a+1)a[1]……4、字符串

字符串定義成字符數組

‘\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;

數據項具有獨立含義的最小標識單位,是數據的最小單位數據元素數據項學號姓名性別籍貫出生年月住址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);}求解：設母