數(shù)據(jù)結(jié)構(gòu)與算法應(yīng)用課程介紹學(xué)習(xí)目標(biāo)知識(shí)方面掌握基本的數(shù)據(jù)結(jié)構(gòu)掌握數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)方法以及相關(guān)經(jīng)典算法能力方面培養(yǎng)算法設(shè)計(jì)能力、程序編寫(xiě)能力培養(yǎng)計(jì)算機(jī)思維能力2第1章緒論1.1數(shù)據(jù)結(jié)構(gòu)1.2算法1.3常用算法計(jì)算機(jī)解決問(wèn)題的過(guò)程問(wèn)題1：解決客觀問(wèn)題的思維過(guò)程？認(rèn)識(shí)問(wèn)題和明確提出問(wèn)題分析問(wèn)題的特點(diǎn)提出假設(shè)，考慮解答方法驗(yàn)證結(jié)論

計(jì)算機(jī)解決問(wèn)題的過(guò)程數(shù)值問(wèn)題：矩陣運(yùn)算M1×M2×M3×…×Mn方程組求解非數(shù)值問(wèn)題：查找電話（線性表）學(xué)籍管理（樹(shù)）數(shù)據(jù)處理路徑搜索（圖）問(wèn)題2：借助計(jì)算機(jī)求問(wèn)題的過(guò)程？

計(jì)算機(jī)解決問(wèn)題的過(guò)程問(wèn)題2：借助計(jì)算機(jī)求問(wèn)題的過(guò)程？提出問(wèn)題建立數(shù)學(xué)模型確定數(shù)據(jù)的存儲(chǔ)方式（數(shù)據(jù)結(jié)構(gòu)）提出數(shù)據(jù)處理方法（算法）編寫(xiě)程序調(diào)試程序驗(yàn)證結(jié)果

計(jì)算機(jī)解決問(wèn)題的過(guò)程軟硬件獨(dú)立原理和互動(dòng)原理軟件本質(zhì)上是利用計(jì)算機(jī)來(lái)解決某個(gè)問(wèn)題的思想！

軟件的實(shí)現(xiàn)就是將這個(gè)思想數(shù)字化的過(guò)程！問(wèn)題3：工科專業(yè)學(xué)生應(yīng)對(duì)計(jì)算機(jī)軟件了解什么程度？

如何利用它？1.1數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素集合。

例如：描述一年四季的季節(jié)名春，夏，秋，冬表示數(shù)值的各個(gè)數(shù)

18，11，35，23，16，…家庭成員的各成員名父親，兒子，女兒

1.1數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)三個(gè)方面的問(wèn)題：(1)數(shù)據(jù)的邏輯結(jié)構(gòu)（算法設(shè)計(jì)）(2)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)（算法實(shí)現(xiàn)）(3)對(duì)各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算目的：提高數(shù)據(jù)處理的效率(1)提高數(shù)據(jù)處理的速度(2)盡量節(jié)省計(jì)算機(jī)存儲(chǔ)空間

1.1數(shù)據(jù)結(jié)構(gòu)的基本概念1.數(shù)據(jù)的邏輯結(jié)構(gòu)是指反映數(shù)據(jù)元素之間關(guān)系的數(shù)據(jù)元素集合的表示即帶有結(jié)構(gòu)的數(shù)據(jù)元素的結(jié)合。（1）表示數(shù)據(jù)元素的集合D；（2）表示各數(shù)據(jù)元素之間的前后件關(guān)系R。

具有4種基本結(jié)構(gòu)：集合、線性、樹(shù)型、圖狀或網(wǎng)狀數(shù)據(jù)結(jié)構(gòu)可以表示成

B＝（D，R）其中B表示數(shù)據(jù)結(jié)構(gòu)。

例如

B＝（D，R）

D＝{春，夏，秋，冬}R＝{(春，夏)，(夏，秋)，(秋，冬)}家庭成員數(shù)據(jù)結(jié)構(gòu)：

B＝（D，R）

D＝{父親，兒子，女兒}R＝{(父親，兒子），(父親，女兒）}n維向量X＝（x1，x2，…，xn）也是一種數(shù)據(jù)結(jié)構(gòu)，即：

B＝（D，R）

D＝{x1，x2，…，xn}R＝{(x1，x2)，(x2，x3)，…，(xn－1，xn)}線性數(shù)據(jù)結(jié)構(gòu)與非線性數(shù)據(jù)結(jié)構(gòu)線性結(jié)構(gòu)：（1）有且只有一個(gè)根結(jié)點(diǎn)；（2）每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件，也最多有一個(gè)后件。注意：在一個(gè)線性結(jié)構(gòu)中插入或刪除任何一個(gè)結(jié)點(diǎn)后

還應(yīng)是線性結(jié)構(gòu)。非線性結(jié)構(gòu)：如果一個(gè)數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu)，則稱之為非線性結(jié)

構(gòu)。2.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)（物理結(jié)構(gòu)）

數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式。

常用的存儲(chǔ)結(jié)構(gòu)有：順序、鏈接、索引等存儲(chǔ)結(jié)構(gòu)。1.1數(shù)據(jù)結(jié)構(gòu)的基本概念143.數(shù)據(jù)的基本運(yùn)算：

插入

刪除查找1.2算法算法是一種求解問(wèn)題的思維方法和有效策略，是解決某一特定問(wèn)題的運(yùn)算序列程序的基礎(chǔ)來(lái)自于人工解題的思路，算法需要從人工解題過(guò)程中獲取靈感。

例：在紙牌游戲中，如果讓計(jì)算機(jī)來(lái)發(fā)牌，怎么做，可以給每張牌指定1~52中的一個(gè)整數(shù)，這樣可以從1~52中隨機(jī)取樣5個(gè)不重復(fù)的整數(shù)來(lái)得到一手牌。

問(wèn)題：1）如何隨機(jī)得到不同的數(shù)？2）如何分配不重復(fù)？1.2算法算法的基本特征

確定性：算法中的每一步都應(yīng)當(dāng)是確定的，而不是模棱兩可的。有窮性：算法執(zhí)行有限步之后應(yīng)結(jié)束，且每一步的執(zhí)行時(shí)間有限?？尚行裕核惴ㄖ兴械倪\(yùn)算可以準(zhǔn)確實(shí)現(xiàn)。輸入項(xiàng)：算法有零個(gè)或多個(gè)輸入。輸出項(xiàng)：算法至少有一個(gè)輸出，可以是數(shù)據(jù)、動(dòng)作或者其它信息形式。1.2算法算法分析

時(shí)間復(fù)雜度【例1-1】計(jì)算如下程序段時(shí)間復(fù)雜度。intx=99,y=200;

while(y>0)if(x<90){x=x+10;y--;}elsex--;

【例1-2】計(jì)算如下程序段時(shí)間復(fù)雜度。intcount=1;for(inti=1;i<=n;i++)

for(intj=1;j<i+1;j++)for(intk=1;k<j+1;k++)count++;2.空間復(fù)雜度1.3常用算法1、窮舉法【例1-4】公元五世紀(jì)我國(guó)數(shù)學(xué)家張丘建在其《算經(jīng)》一書(shū)中提出了“百雞問(wèn)題”：雞翁一值錢5，雞母一值錢3，雞雛三值錢1。百錢買百雞，問(wèn)雞翁、母、雛各幾何？編寫(xiě)程序，求出結(jié)果。#include“stdio.h”intmain(){inthen,cock,chick;for(cock=1;cock<20;cock++)for(hen=1;hen<33;hen++){chick=100-hen-cock;if(cock*5+hen*3+chick/3==100)printf(“cock:%d;hen:%d;chick:%d\n”,cock,hen,chick);}}1.3常用算法1、窮舉法【例1-5】將100元人民幣兌換為1元，2元和5元的人民幣，共有多少種兌換方法？#include“stdio.h”intmain(){intcount=0;for(intcount_5=0;count_5<=20;count_5++)for(intcount_2=0;count_2<=50;count_2++)for(intcount_1=0;count_1<=100;count_1++)if(count_1+2*count_2+5*count_5==100)count++;printf(“%d”,count);}1.3常用算法2、貪婪法【例1-6】假設(shè)1角、5角、1元、5元、10元的硬幣分別有10、8、3、6、8枚，要用這些錢支付cost元，至少需要用多少枚硬幣，采用貪婪算法編寫(xiě)C語(yǔ)言程序計(jì)算結(jié)果。#include“stdio.h”intvalue[5]={1,5,10,50,100};intcount[5]={10,8,3,6,8};intmain(){floatcost;intnum_money=0;scanf(“%f”,&cost);cost=cost*10;for(inti=4;i>=0;i--){inttemp;if((int)(cost/value[i])>count[i])temp=count[i];elsetemp=(int)(cost/value[i]);cost=cost-temp*value[i];num_money+=temp;}if(cost>0)printf(“Nocorrectsolution”);elseprintf(“num:%d”,num_money);}1.3常用算法3、遞推法【例1-7】斐波那契數(shù)列，設(shè)它的函數(shù)為f(n)，已知f(0)=0，f(1)=1；f(n)=f(n-2)+f(n-1)，(n≥3，n∈N)。通過(guò)遞推可知，f(3)=f(1)+f(2)=2，f(4)=f(2)+f(3)=3……直至要求的解。采用遞推算法編寫(xiě)C語(yǔ)言程序計(jì)算結(jié)果，輸出f(0)~f(20)的結(jié)果。#include“stdio.h”intmain(){intfib[21];fib[0]=0;fib[1]=1;for(inti=2;i<=20;i++)fib[i]=fib[i-1]+fib[i-2];for(inti=0;i<=20;i++)printf(“%d:%d\n”,i,fib[i]);}1.3常用算法3、遞推法【例1-8】編寫(xiě)C語(yǔ)言程序，使用遞推法求解n！#include“stdio.h”intmain(){longfac=1;inti,n;scanf(“%d”,&n);for(i=1;i<=n;i++)fac=fac*i;printf(“Thefactorialofnis:%ld”,fac);}1.3常用算法4、遞歸法【例1-9】編寫(xiě)C語(yǔ)言程序，使用遞歸法求解n！#include“stdio.h”longn_factorial(intn){longfac;if(n==1||n==0)return1;elsereturnfac=n*n_factorial(n-1);}intmain(){longfac;intn;scanf(“%d”,&n);fac=n_factorial(n);printf(“Thefactorialofnis:%ld”,fac);}1.3常用算法4、遞歸法

【例1-10】漢諾塔問(wèn)題

假設(shè)有n個(gè)圓盤和3個(gè)塔座，如圖1-3所示。初始時(shí)所有圓盤從下往上，由大到小堆在塔1，要求把所有圓盤按照同樣的順序移到塔2，在移動(dòng)圓盤時(shí)，一次只能移動(dòng)一個(gè)圓盤，同時(shí)不允許較大的圓盤放在較小圓盤之上，編寫(xiě)算法，輸出移動(dòng)過(guò)程。1.3常用算法4、遞歸法

【例1-10】漢諾塔問(wèn)題voidHanoi(intn,inth_1,inth_2,inth_3){if(n>0){Hanoi(n-1,h_1,h_3,h_2);printf(“Fromtopoftower%dtotopoftower%d\n”,h_1,h_2);Hanoi(n-1,h_3,h_2,h_1);}}1.3常用算法5、分治法【例1-11】有16個(gè)硬幣，其中有一個(gè)是偽造的，并且偽造的硬幣比真的硬幣要輕一些。為完成任務(wù)，提供一臺(tái)可用來(lái)比較兩組硬幣重量的儀器，如何借助儀器更快的找出偽造的硬幣？1.3常用算法6、回溯法【例1-13】八皇后問(wèn)題要求在8×8的國(guó)際象棋棋盤上擺放8個(gè)皇后，皇后之間不能互相攻擊，問(wèn)有多少種擺法，編寫(xiě)C語(yǔ)言程序輸出正確的擺法。#include<stdio.h>intboard[8]={0};intcheck(intcur_row,intcur_col){intpre_col;for(intpre_row=0;pre_row<cur_row;pre_row++){pre_col=board[pre_row];if(cur_col==pre_col)return0;elseif((pre_row+pre_col)==(cur_row+cur_col))return0;elseif((pre_row-pre_col)==(cur_row-cur_col))return0;}return1;}1.3常用算法6、回溯法【例1-13】八皇后問(wèn)題voidplace_eight_queen(intcur_row){if(cur_row==8){for(introw=0;row<8;row++){for(intcol=0;co