計(jì)算機(jī)軟件基礎(chǔ)課件：預(yù)備知識

計(jì)算機(jī)軟件基礎(chǔ)

BasicsofComputerSoftware課程內(nèi)容預(yù)備知識1數(shù)據(jù)結(jié)構(gòu)概述2線性表及其存儲結(jié)構(gòu)3樹和二叉樹45圖的基本概念和應(yīng)用6查找算法7排序算法8其他2021年3月編制主講人：工作單位：電氣信息工程學(xué)院辦公室：開陽樓C408電話/p>

預(yù)備知識BasicsofComputerSoftware答辯人：XXX目錄C語言復(fù)習(xí)1常用算法2算法的基本概念3C語言復(fù)習(xí)PART1if-else語句的一般形式為：if(表達(dá)式)

語句1;

else

語句2;其中：語句1和語句2可以是空語句,一般語句2為空，就是不帶else的語句例：將a和b按從小到大排列#include<stdio.h>intmain(){inta,b,t;printf("請輸入2個(gè)數(shù)字：");scanf("%d%d",&a,&b);if(a>b){t=a;a=b;b=t;}printf("%5d%5d\n",a,b);}不帶else的語句例：將a、b、c按從小到大排列（只寫完成該功能的程序段）if(a>b){t=a;a=b;b=t;}if(a>c){t=a;a=c;c=t;}if(b>c){t=b;b=c;c=t;}例：判斷一個(gè)數(shù)字是奇數(shù)還是偶數(shù)。#include<stdio.h>intmain(){intx;printf("請輸入一個(gè)數(shù)字：");scanf("%d",&x);if(x%2==0)printf("%d是偶數(shù)！\n",x);elseprintf("%d是奇數(shù)！\n",x);return0;}帶else的語句多分支結(jié)構(gòu)和else-if語句一般形式為：

if(表達(dá)式1)

語句1;

elseif(表達(dá)式2)

語句2；

…

elseif(表達(dá)式n-1)

語句n-1;

else

語句n；sign(x)符號函數(shù)其功能是取某個(gè)數(shù)的符號：當(dāng)x>0，sign(x)=1;當(dāng)x=0，sign(x)=0;當(dāng)x<0，sign(x)=-1；sign(x)符號函數(shù)方法一：if(x>0)sign=1；if(x==0)sign=0；if(x<0)

sign=-1；方法二：if(x>0)sign=1elseif(x==0)sign=0elsesign=-1三種循環(huán)結(jié)構(gòu)for循環(huán)：一般用在循環(huán)次數(shù)固定或已知的情況while循環(huán)：又稱當(dāng)型循環(huán)，用的較多do-while循環(huán)：又稱直到型循環(huán)，盡量用while實(shí)現(xiàn)一般的循環(huán)程序都涉及循環(huán)變量，循環(huán)變量盡量和問題對應(yīng)我們通過例子來復(fù)習(xí)猴子吃桃問題猴子第一天摘下N個(gè)桃子，當(dāng)時(shí)就吃了一半，還不過癮，就又吃了一個(gè)。第二天又將剩下的桃子吃掉一半，又多吃了一個(gè)。以后每天都吃前一天剩下的一半零一個(gè)。到第10天在想吃的時(shí)候就剩一個(gè)桃子了,求第一天共摘下來多少個(gè)桃子？猴子吃桃問題設(shè)D1為前一天的桃子數(shù)，D2為后一天的桃子數(shù)，則根據(jù)吃桃過程有公式：

D2=D1—(D1/2＋1)=D1/2—1這是根據(jù)前一天算后一天，但我們現(xiàn)在是要根據(jù)后一天算前一天，∴有D1=(D2＋1)×2我們用C語言的賦值語句來替換上面的等式，有：D=(D＋1)×2等號右邊的D代表后一天的個(gè)數(shù)，左邊的D代表前一天的個(gè)數(shù)猴子吃桃問題int

main(){

int

i;

int

D=1;

for(i=9;i>=1;i--)

D=2*(D+1);

printf("%d\n",D);}循環(huán)變量i

和第幾天對應(yīng)小球落地問題h=100;s=h;for(i=2;i<=10;i++){s=s+h;h=h/2;}小球落地問題h=100;s=h;for(i=2;i<=10;i++){h=h/2;s=s+2*h;}水仙花數(shù)問題所謂水仙花就是指一個(gè)三位數(shù)，其各個(gè)位上的數(shù)字的立方之和正好等于該數(shù)字本身。例如：153=13+53+33,那么153就是水仙花數(shù)。我們可以用一個(gè)單循環(huán)來實(shí)現(xiàn)，也可以用一個(gè)三重循環(huán)來實(shí)現(xiàn)設(shè)這個(gè)三位數(shù)是：abc水仙花數(shù)問題（單循環(huán)）main(){inti=0,a,b,c;for(i=100;i<1000;i++){a=i/100;b=i/10%10;c=i%10;if((a*a*a+b*b*b+c*c*c)==i)

//滿足水仙花條件printf("%d",i);}}水仙花數(shù)問題（多重循環(huán)）main(){inti=0,a,b,c;for(a=1;a<=9;a++)for(b=0;b<=9;b++)for(c=0;c<=9;c++){i=100*a+10*b+c;if((a*a*a+b*b*b+c*c*c)==i)

//滿足水仙花條件printf("%d",i);}}編寫一個(gè)求1到100和的程序段，結(jié)果放在sum變量中main(){intsum;sum=(1+100)*100/2；printf(“sum=%d”,sum);}用循環(huán)語句的方式，編寫一個(gè)求1到100和的程序main(){inti,sum;sum=0;for(i=1;i<=100;i++)

sum=sum+i;printf(“sum=%d”,sum);}編寫一個(gè)程序，實(shí)現(xiàn)輸入100個(gè)數(shù)據(jù)求和main(){inti,sum,x;sum=0;for(i=1;i<=100;i++)

{scanf("%d",&x);

sum=sum+x;}printf(“sum=%d”,sum);}main(){inti,sum,x;sum=0;i=1while(i<=100){scanf("%d",&x);

sum=sum+x;i=i+1;}printf(“sum=%d”,sum);}編寫一個(gè)程序，實(shí)現(xiàn)輸入以0作為結(jié)束的任意個(gè)數(shù)據(jù)求和main(){inti,sum,x;sum=0;i=1while(i<=100){scanf("%d",&x);

sum=sum+x;i=i+1;}printf(“sum=%d”,sum);}這是上一個(gè)程序main(){intsum,x;sum=0;scanf("%d",&x);

while(x<>0){sum=sum+x;scanf("%d",&x);}printf(“sum=%d”,sum);}這個(gè)程序結(jié)構(gòu)用的是最多的編寫一個(gè)程序，實(shí)現(xiàn)輸入一個(gè)班（設(shè)40人）的成績，打印出高于平均分的成績和人數(shù)main(){inti,sum,a[40],count=0;float:ave;sum=0;for(i=0;i<40;i++)

{scanf("%d",&a[i]);

sum=sum+a[i];}ave=sum/40;for(i=0;i<40;i++)

If(a[i]>ave){printf(“%d”,a[i]);

count++;}printf(“count=%d”,count);}輸出如下圖形**********printf(“*\n**\n***\n****”);scanf("%d",&n);

for(i=1;i<=n;i++)

{for(j=1;j<=i;j++)

printf(“*”);printf(“\n”);}輸入行數(shù)n，輸出如下圖形輸入行數(shù)n，輸出如下圖形**********scanf("%d",&n);

for(i=1;i<=n;i++)

{for(j=1;j<=?;j++)

printf(“*”);printf(“\n”);}ij14233241滿足：i+j=5=n+1∴有：j=n+1-i；n+1-i輸入行數(shù)n，輸出如下圖形**********scanf("%d",&n);

for(i=1;i<=n;i++)

{for(j=1;j<=?;j++)

printf(“”);

for(j=1;j<=?;j++)

printf(“*”);printf(“\n”);}打印空格關(guān)系ij10213243每一行先打印空格，再打“*”打印“*”關(guān)系ij14233241i-1n+1-ij=i-1j=n+1-i輸入行數(shù)n，輸出如下圖形**********scanf("%d",&n);

for(i=1;i<=n;i++)

{for(j=1;j<=?;j++)

printf(“”);

for(j=1;j<=?;j++)

printf(“*”);printf(“\n”);}打印空格關(guān)系ij13223140每一行先打印空格，再打“*”打印“*”關(guān)系ij11223344n-iij=n-ij=i函數(shù)（過程和函數(shù)）max（a，b）main(){

intx,y,z;x=3;y=5;

z=max(x,y)}intmax(inta,b){if(a>b)returna;elsereturnb;}形參實(shí)參35mainmax35函數(shù)舉例main(){

intx,y;x=3;y=5;

exchg(x,y);printf(“%5d%5d”,x,y);}exchg(inta,b){intt;t=a;a=b;b=t;}35mainexchg35運(yùn)行結(jié)果：?a.35b.53√指針的概念指針就是地址對單元內(nèi)容的訪問有兩種：1.直接訪問：直接通過變量名訪問x=20,y=1,z=155;2.間接訪問：通過另一個(gè)變量訪問把該變量的地址放到另一個(gè)變量中我們把存放地址的變量稱為指針變量，例如變量p定義如下：Int

x,y,z;Int*p;直接訪問：x=20,y=1,z=155;xyzp20115510001000100210042000P=&x；//指針變量賦值不能直接給指針變量賦常量間接訪問：p=1000或p=20？*P=50；//通過針變量訪問簡單變量501155P=&x；&在這是取地址運(yùn)算符，把x變量的地址賦給指針變量p&在雙目運(yùn)算中是位運(yùn)算的按位與運(yùn)算*P=50；*在這是p指針指向的變量（內(nèi)存單元）的內(nèi)容，在前面已經(jīng)將p指向了變量x，最后實(shí)現(xiàn)的是將變量x（內(nèi)存

1000單元）的內(nèi)容設(shè)成50。設(shè)有定義：int

x,y;int*p;判斷下列語句正確與否？X=y;p=&x;P=x;p=*x;X=5;x=*p;P=1000;x=&p√√√√××××例如：例如：voidmain(){inta,b,*p1,*p2,*p;a=3;b=6;p1=&a;p2=&b;63p1ap2bp運(yùn)行結(jié)果：6，33，6p=p1;p1=p2;p2=p;printf(“%d,%d\n”,*p1,*p2);printf(“%d,%d\n”,a,b);}例如：voidmain(){inta,b,t，*p1,*p2;a=3;b=6;p1=&a;p2=&b;63p1ap2bt運(yùn)行結(jié)果：6，36，363t=*p1;*p1=*p2;*p2=t;printf(“%d,%d\n”,*p1,*p2);printf(“%d,%d\n”,a,b);}例如：voidmain(){inta,b;a=3;b=6;exchg(a,b);printf(“%d,%d\n”,a,b);}exchg(intx,y){intt;t=x,x=y,y=t;}63ab運(yùn)行結(jié)果：3，663mainexchg63txy例如：用指針實(shí)現(xiàn)交換voidmain(){inta,b;a=3;b=6;exchg(&a,&b);printf(“%d,%d\n”,a,b);}exchg(int*x,*y){intt;t=*x,*x=*y,*y=t;}63ab運(yùn)行結(jié)果：6，363mainexchg&b&atxy指針和數(shù)組指向數(shù)組元素的指針（一維數(shù)組）inta[5],*p;p=a;或p=&a[0];//結(jié)果是一樣的數(shù)組名本身就是數(shù)組的起始地址inta[5],*p=a;//和上面一樣嗎？指針和數(shù)組數(shù)組元素的引用inta[5]]={10,11,12,13,14},*p=a；下標(biāo)法：通過a[i]來引用，如a[3]下列指令那些合法，什么含義p++；a++；p=a+2；a=a+2指針法：用*(a+i)、*(p+i)引用第i個(gè)元素1011121314指針和結(jié)構(gòu)體結(jié)構(gòu)體結(jié)構(gòu)體是自定義類型，由多個(gè)類型不相同的分量組成，定義如下：structstud{longnum;charname[20];chargender;intage;floatscore;}s1;numnamegenderagescore類型名為stud的結(jié)構(gòu)體18020101張三男9520numnamegenderagescore變量名為s1的結(jié)構(gòu)體變量指針和結(jié)構(gòu)體結(jié)構(gòu)體structstud{longnum;charname[20];chargender;intage;floatscore;}s1;18020101張三男9520numnamegenderagescore變量名為s1的結(jié)構(gòu)體變量s1.num=18020101strcpy(,“張三”);s1.gender=‘M’;s1.age=20;s1.score=95;s1指向結(jié)構(gòu)體的指針structstud{longnum;charname[20];chargender;intage;floatscore;}s1，*p；18020101張三男9520numnamegenderagescore變量名為s1的結(jié)構(gòu)體變量同理：strcpy(p->name,“張三”);p->gender=‘M’;p->age=20;p->score=95;s1p指針變量Pp=&s1;//這個(gè)必須要?jiǎng)t(*p).num=18020201;可表示為:p->num=18020201;鏈表headacdefg^b存儲地址數(shù)據(jù)域指針域1f137e113gnull19b3725d731a1937c25頭指針31每個(gè)元素由結(jié)點(diǎn)(Node)構(gòu)成，它包括兩個(gè)域:數(shù)據(jù)域（Data）和指針域（next）存儲結(jié)構(gòu)：鏈?zhǔn)酱鎯Y(jié)構(gòu)特點(diǎn)：存儲單元可以不連續(xù)。Nodedatanext單鏈表的類型定義typedefintListData;//定義數(shù)據(jù)類型typedefstructnode//鏈表結(jié)點(diǎn)

{

ListDatadata; //結(jié)點(diǎn)數(shù)據(jù)域

structnode*next;//結(jié)點(diǎn)鏈域}ListNode;TypedefListNode*LinkList;//鏈表頭指針LinkListhead，p，q;//鏈表頭指針ListNode*head，*p，*q;NodedatanextListNode是類型名

9

5

2

head

單鏈表的引用P

p->data;//得到2p->next;//2和5之間的指針p->next->data;//得到5p->next->next->data;//得到9q->next=nil;//最后一個(gè)指針分量置空p=p->next;//指針后移一個(gè)節(jié)點(diǎn)q

單鏈表的插入操作（三種情況）第一種情況：在第一個(gè)結(jié)點(diǎn)前插入newnodeheadabc^Newnode->next=p->next;p->next=newnode;P第二種情況：在鏈表中間插入newnodeheadabc^Newnode->next=p->next;p->next=newnode;P第三種情況：在鏈表尾部插入newnodeheadabcNewnode->next=p->next;p->next=newnode;^^PNewnode->next=p->next;p->next=newnode;注意，在這三種情況中，插入操作均是：單鏈表的刪除操作

headabe^Pcdq（刪除P結(jié)點(diǎn)之后的結(jié)點(diǎn)）q=p->next;p->next=q->next;free(q);編程：實(shí)現(xiàn)輸出以head為頭節(jié)點(diǎn)的單鏈表中所有結(jié)點(diǎn)的程序段output(head);{p=head->next；

//讓移動指針指向第一個(gè)結(jié)點(diǎn)while(p!=nil){printf(“%5d”,p->data);p=p->next;//指針后移}}常用算法PART2算法設(shè)計(jì)基本方法—常用算法一.枚舉法

枚舉法是利用計(jì)算機(jī)運(yùn)行速度快、精度高的特點(diǎn)，對要解決問題的所有可能情況，一個(gè)不落的進(jìn)行檢測，從中找出符合要求的答案。

枚舉法通過犧牲時(shí)間來換取答案的全面性。算法設(shè)計(jì)基本方法—枚舉法百錢買百雞問題中國古代數(shù)學(xué)家張丘建在《算經(jīng)》中提出：雞翁一，值錢五，雞母一，值錢三，雞雛三，值錢一，百錢買百雞，問翁、母、雛各幾何？百元買百雞——枚舉法方法1：voidbqbj(){intCock,Hen,Chicken;for(Cock=0;Cock<20;Cock++)for(Hen=0;Hen<34;Hen++)for(Chicken=0;Chicken<100;Chicken++)if((Cock+Hen+Chicken==100)&&(Cock*5+Hen*3+Chicken/3==100)&&(Chicken%3==0))printf("Cock=%dHen=%dChicken=%d\n",Cock,Hen,Chicken);}循環(huán)次數(shù)68000次百元買百雞——枚舉法方法2：voidbqbj(){intCock,Hen,Chicken;for(Cock=0;Cock<20;Cock++)for(Hen=0;Hen<34;Hen++){Chicken=100-Cock-Hen;if((Cock*5+Hen*3+Chicken/3==100)&&(Chicken%3==0))printf("Cock=%dHen=%dChicken=%d\n",Cock,Hen,Chicken);}}循環(huán)次數(shù)680次百元買百雞——枚舉法方法3：voidbqbj(){intCock,Hen,Chicken;for(Cock=0;Cock<20;Cock++)for(Hen=0;Hen<(100-Cock*5)/3;Hen++){Chicken=100-Cock-Hen;if((Cock*5+Hen*3+Chicken/3==100)&&(Chicken%3==0))printf("Cock=%dHen=%dChicken=%d\n",Cock,Hen,Chicken);

}}循環(huán)次數(shù)少于680次二、歸納法找規(guī)律在復(fù)習(xí)C語言時(shí)舉的例子基本都是找規(guī)律三、遞推法

遞推算法是通過已知條件，利用特定關(guān)系得出中間推論，直至得到結(jié)果的算法。例1：階乘函數(shù)n！=1*2*3*…*n即：n！=（n-1）！*n即：2！=1！*2，3！=2！*3,……例1：階乘函數(shù)IntFact(n){intt=1,i;for(i=1;i<=n;i++)t=t*i;returnt;}三、遞推法四、遞歸法myfunc(參數(shù)){：

：myfunc(參數(shù));::}四、遞歸法例1：階乘函數(shù)intfact(n){if(n==1)return1;elsereturnn*fact(n-1);}四、遞歸法例2：hano塔四、遞歸法例2：hano塔算法描述：如果n=1直接將n號盤從a搬到c否則做如下操作

將a上的n-1張盤從a搬到b；直接將n號盤從a搬到c；將b上的n-1張盤從b搬到c；說明：一張盤時(shí)直接搬到目的地

多張盤時(shí)調(diào)用自己基本思路：首先將n張盤看成由2部分組成：第一部分是最大的盤n號盤，然后把剩余的n-1張盤看成另外一個(gè)整體，稱n-1張盤，這樣其移動過程就和2張盤的移動過程相同，如右上角。注意，這里的n-1張盤是多張盤組成的，n號盤只有1張盤。voidHanoi(intn,a,b,c){if(n==1)move(n,a,c);//一張盤片else{Hanoi(n-1,a,c,b);

//多張盤片move(n,a,c);//一張盤片

Hanoi(n-1,b,a,c);

//多張盤片}}voidmove(intn,a,c){printf(“將%d號盤從%d搬到%d\n”,n,a,c);}五、分治法例：折半查找——查字典例如:在有序表中查找key=21的查找過程六、迭代法例：求X2-X-1=0在x=1.5附近的一個(gè)根X=(x+1)0.5所以，X=(1.5+1)0.5=1.58113883

X=(1.58113883+1)0.5=1.606592304

X=(1.606592304+1)0.5=1.614494442

X=(1.614494442+1)0.5=1.616939839

X=(1.616939839+1)0.5=1.617695842

X=(1.617695842+1)0.5=1.617929492

X=(1.617929492+1)0.5=1.618001697

X=(1.618001697+1)0.5=1.61802401七、回溯法（高級算法）—八皇后問題

有八個(gè)皇后（可以當(dāng)成八個(gè)棋子），如何在8*8的棋盤中放置八個(gè)皇后，使得任意兩個(gè)皇后都不在同一條橫線、縱線或者斜線上。七、回溯法（高級算法）—八皇后問題算法的解決思路是：