計(jì)算機(jī)軟件基礎(chǔ)BasicsofComputerSoftware課程內(nèi)容預(yù)備知識1數(shù)據(jù)結(jié)構(gòu)概述2線性表及其存儲結(jié)構(gòu)3樹和二叉樹45圖的基本概念和應(yīng)用6查找算法7排序算法8其他第一章預(yù)備知識BasicsofComputerSoftware目錄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è)必須要則(*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è)皇后都不在同一條橫線、縱線或者斜線上。七、回溯法（高級算法）—八皇后問題算法的解決思路是：1從棋盤的第一行開始，從第一個(gè)位置開始，依次判斷當(dāng)前位置是否能夠放置皇后，判斷的依據(jù)為：同該行之前的所有行中皇后的所在位置進(jìn)行比較，如果在同一列，或者在同一條斜線上,都不符合要求，繼續(xù)檢驗(yàn)后序的位置。2如果該行所有位置都不符合要求,則回

溯到前一行,改變皇后的位置,繼續(xù)試探。3.如果試探到最后一行，所有皇后擺放

完畢,則直接打印出8*8的棋盤。七、回溯法（高級算法）—八皇后問題1.1.6算法的復(fù)雜度分析一.算法的后期在算法中的某些部位插裝時(shí)間函數(shù)time

(),

測定算法完成某一功能所花費(fèi)時(shí)間

doublestart,stop;

time(&start);

intk=seqsearch(a,n,x);

time(&stop);

doublerunTime=stop-start;printf(“%d%d\n”,n,runTime);二.算法的事前估計(jì)1.空間復(fù)雜度度量（1）存儲空間的固定部分

程序指令代碼的空間，常數(shù)、簡單變量、定長成分(如數(shù)組元素、結(jié)構(gòu)成分、對象的數(shù)據(jù)成員等)變量所占空間（2）可變部分

尺寸與實(shí)例特性有關(guān)的成分變量所占空間、引用變量所占空間、遞歸棧所用空間、通過new和delete命令動態(tài)使用空間2.時(shí)間復(fù)雜度度量運(yùn)行時(shí)間=算法中每條語句執(zhí)行時(shí)間之和。每條語句執(zhí)行時(shí)間=該語句的執(zhí)行次數(shù)（頻度）*語句執(zhí)行一次所需時(shí)間。語句執(zhí)行一次所需時(shí)間取決于機(jī)器的指令性能和速度和編譯所產(chǎn)生的代碼質(zhì)量，很難確定。設(shè)每條語句執(zhí)行一次所需時(shí)間為單位時(shí)間，則一個(gè)算法的運(yùn)行時(shí)間就是該算法中所有語句的頻度之和。算法的基本概念PART31.1.1算法的四個(gè)基本特征：1.有窮性：

一個(gè)算法必須在執(zhí)行有窮步之后結(jié)束2.確定性：算法的每一步必須是確切定義的。對于相同輸入必須得到相同結(jié)果。3.可行性：

算法每一步都是能夠?qū)崿F(xiàn)的，即可操作的。4.有輸出：算法執(zhí)行完畢，必須有一個(gè)或若干個(gè)輸出結(jié)果。1.1.2評價(jià)算法：正確性：對于一切合法輸入都能產(chǎn)生滿足規(guī)格要求的結(jié)果易讀性：算法要便于閱讀，有助于人們對算法的理解健壯性：當(dāng)輸入非法數(shù)據(jù)時(shí)，也能正常作出反應(yīng)和處理效率和低存儲量需求：對相同規(guī)模的問題，運(yùn)行時(shí)間短、占用空間少

1.1算法的基本概念1.1算法的基本概念1.1.3算法的基本要素1、對數(shù)據(jù)的運(yùn)算和操作 如：插入、刪除2、算法的控制結(jié)構(gòu) 如用流程圖和N-S圖表示1.1.4算法描述語言采用類C語言來描述一、符號與表達(dá)式二、賦值語句三、控制轉(zhuǎn)移語句 如：go,if等語句四、循環(huán)五、其他語句：exit、ruturn、如:ab本次課程結(jié)束，謝謝大家的觀看！常州工學(xué)院主講人：黃文生BasicsofComputerSoftware第二章數(shù)據(jù)結(jié)構(gòu)概述BasicsofComputerSoftware基本概念

邏輯結(jié)構(gòu)物理結(jié)構(gòu)數(shù)據(jù)操作目錄數(shù)據(jù)結(jié)構(gòu)的基本概念1數(shù)據(jù)的邏輯結(jié)構(gòu)2數(shù)據(jù)的物理結(jié)構(gòu)3數(shù)據(jù)操作41.無序表和有序表的查找有序表的查找無序表的查找基本概念

邏輯結(jié)構(gòu)物理結(jié)構(gòu)數(shù)據(jù)操作問題引入結(jié)論01數(shù)據(jù)的組織結(jié)構(gòu)和算法是密切相關(guān)的2.學(xué)生成績表成績表我們可以采用鏈表，數(shù)組，樹形結(jié)構(gòu)，甚至可以用圖型結(jié)構(gòu)進(jìn)行表示和存儲，但相應(yīng)的各種操作算法也不同基本概念

邏輯結(jié)構(gòu)物理結(jié)構(gòu)數(shù)據(jù)操作問題引入結(jié)論：數(shù)據(jù)結(jié)構(gòu)和算法是相互依賴的關(guān)系：基本概念

邏輯結(jié)構(gòu)物理結(jié)構(gòu)數(shù)據(jù)操作問題引入02算法要作用在特定的數(shù)據(jù)結(jié)構(gòu)之上算法要結(jié)合數(shù)據(jù)存儲的特點(diǎn)，用最優(yōu)的策略來分析并處理數(shù)據(jù)。01數(shù)據(jù)結(jié)構(gòu)是為算法服務(wù)的數(shù)據(jù)結(jié)構(gòu)要配合算法選擇最優(yōu)的存儲結(jié)構(gòu)來存儲數(shù)據(jù)。隊(duì)列可以用線性鏈表描述家譜可以用樹描述交通網(wǎng)可以用圖或者網(wǎng)絡(luò)來描述基本概念

邏輯結(jié)構(gòu)物理結(jié)構(gòu)數(shù)據(jù)操作什么是數(shù)據(jù)結(jié)構(gòu)基本概念

邏輯結(jié)構(gòu)物理結(jié)構(gòu)數(shù)據(jù)操作什么是數(shù)據(jù)結(jié)構(gòu)描述這類非數(shù)值計(jì)算問題的數(shù)學(xué)模型不是數(shù)學(xué)方程,而是樹、表和圖之類的數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是一門研究數(shù)據(jù)組織、存儲和運(yùn)算的一般方法的學(xué)科因此從廣義上講，數(shù)據(jù)結(jié)構(gòu)描述現(xiàn)實(shí)世界實(shí)體的數(shù)學(xué)模型及其上的操作在計(jì)算機(jī)中的表示和實(shí)現(xiàn)學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)知識有助于編制高質(zhì)量的計(jì)算機(jī)應(yīng)用程序數(shù)據(jù)結(jié)構(gòu)（DataStructure）形式定義：數(shù)學(xué)上的抽象的定義

某一數(shù)據(jù)對象的所有數(shù)據(jù)成員之間的關(guān)系。記為：

Data_Structure={D,S}其中，D是某一數(shù)據(jù)對象S是該對象中所有數(shù)據(jù)成員之間的關(guān)系的有限集合如：線性表（2，5，7，9）中可以寫成：D={2，5，7，9}S={(2,5),(5,7),(7,9)}基本概念

邏輯結(jié)構(gòu)物理結(jié)構(gòu)數(shù)據(jù)操作什么是數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)(Data)是信息的載體，是描述客觀事物的數(shù)、字符、以及所有能輸入到計(jì)算機(jī)中，被計(jì)算機(jī)程序識別和處理的符號的集合。數(shù)值性數(shù)據(jù)非數(shù)值性數(shù)據(jù)基本概念

邏輯結(jié)構(gòu)物理結(jié)構(gòu)數(shù)據(jù)操作基本概念和術(shù)語數(shù)據(jù)的基本單位。在計(jì)算機(jī)程序中常作為一個(gè)整體進(jìn)行考慮和處理。數(shù)據(jù)元素又稱為元素、結(jié)點(diǎn)、記錄一個(gè)數(shù)據(jù)元素往往可以由若干數(shù)據(jù)項(xiàng)(DataItem)組成。數(shù)據(jù)項(xiàng)是具有獨(dú)立含義的最小標(biāo)識單位。數(shù)據(jù)元素（DataElement）基本概念

邏輯結(jié)構(gòu)物理結(jié)構(gòu)數(shù)據(jù)操作基本概念和術(shù)語數(shù)據(jù)項(xiàng)(DataItem)

姓名部門名稱出生日期入職時(shí)間職位業(yè)績年月日基本概念

邏輯結(jié)構(gòu)物理結(jié)構(gòu)數(shù)據(jù)操作基本概念和術(shù)語數(shù)據(jù)對象(dataobject)具有相同性質(zhì)的數(shù)據(jù)元素的集合。整數(shù)數(shù)據(jù)對象N={0,1,2,…}字母字符數(shù)據(jù)對象

C={‘A’,‘B’,‘C’,…‘F’}基本概念

邏輯結(jié)構(gòu)物理結(jié)構(gòu)數(shù)據(jù)操作基本概念和術(shù)語從邏輯關(guān)系上描述數(shù)據(jù)，與數(shù)據(jù)的存儲方式無關(guān)從具體問題抽象出來的數(shù)據(jù)模型與數(shù)據(jù)元素本身的形式、內(nèi)容無關(guān)與數(shù)據(jù)元素的相對位置無關(guān)基本概念邏輯結(jié)構(gòu)物理結(jié)構(gòu)數(shù)據(jù)操作數(shù)據(jù)的邏輯結(jié)構(gòu)四個(gè)基本結(jié)構(gòu)樹形結(jié)構(gòu)（一對多）線性結(jié)構(gòu)（一對一）集合（松散結(jié)構(gòu)）圖形結(jié)構(gòu)（多對多）基本概念邏輯結(jié)構(gòu)物理結(jié)構(gòu)數(shù)據(jù)操作數(shù)據(jù)的邏輯結(jié)構(gòu)基本概念邏輯結(jié)構(gòu)物理結(jié)構(gòu)數(shù)據(jù)操作數(shù)據(jù)的邏輯結(jié)構(gòu)02非線性結(jié)構(gòu)樹和圖（網(wǎng)絡(luò)）01線性結(jié)構(gòu)邏輯結(jié)構(gòu)的分類bindevetclibuser線性結(jié)構(gòu)基本概念邏輯結(jié)構(gòu)物理結(jié)構(gòu)數(shù)據(jù)操作數(shù)據(jù)的邏輯結(jié)構(gòu)102114131211234678955一般的樹987456231二叉樹3158710119613二叉排序樹堆結(jié)構(gòu)123548711102916非線性結(jié)構(gòu)：樹型結(jié)構(gòu)基本概念邏輯結(jié)構(gòu)物理結(jié)構(gòu)數(shù)據(jù)操作數(shù)據(jù)的邏輯結(jié)構(gòu)125643125436113318146651921圖結(jié)構(gòu)網(wǎng)絡(luò)結(jié)構(gòu)ABECF非線性結(jié)構(gòu)：圖型結(jié)構(gòu)基本概念邏輯結(jié)構(gòu)物理結(jié)構(gòu)數(shù)據(jù)操作數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu)：又稱物理結(jié)構(gòu)，指數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示，依賴于計(jì)算機(jī)語言基本概念邏輯結(jié)構(gòu)物理結(jié)構(gòu)數(shù)據(jù)操作數(shù)據(jù)的物理結(jié)構(gòu)增加一個(gè)或多個(gè)指針，用于存放和該數(shù)據(jù)元素有關(guān)的另一個(gè)數(shù)據(jù)元素的地址，可以不占用連續(xù)地址空間。鏈接存儲表示是一種在數(shù)據(jù)元素的關(guān)鍵碼與存儲位置之間建立確定對應(yīng)關(guān)系的查找技術(shù)。散列存儲表示將邏輯上相鄰的數(shù)據(jù)元素存放在內(nèi)存中的相鄰位置中順序存儲表示指除建立存儲結(jié)點(diǎn)信息外，還建立附加的索引表來標(biāo)識結(jié)點(diǎn)的地址索引存儲表示基本概念邏輯結(jié)構(gòu)物理結(jié)構(gòu)數(shù)據(jù)操作數(shù)據(jù)的操作構(gòu)造一個(gè)空結(jié)構(gòu)初始化在數(shù)據(jù)結(jié)構(gòu)中插入一個(gè)新元素插入在數(shù)據(jù)結(jié)構(gòu)中刪除滿足指定要求的元素刪除在數(shù)據(jù)結(jié)構(gòu)中修改原有的數(shù)據(jù)元素修改在數(shù)據(jù)結(jié)構(gòu)中查找指定要求的元素查找將數(shù)據(jù)按某一關(guān)鍵字排序排序數(shù)據(jù)操作數(shù)據(jù)結(jié)構(gòu)的研究內(nèi)容基本概念邏輯結(jié)構(gòu)物理結(jié)構(gòu)數(shù)據(jù)操作本章小結(jié)數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的運(yùn)算1數(shù)據(jù)的邏輯結(jié)構(gòu)按照某種邏輯關(guān)系將數(shù)據(jù)組織好，即邏輯結(jié)構(gòu)2數(shù)據(jù)的存儲結(jié)構(gòu)將數(shù)據(jù)及數(shù)據(jù)之間的關(guān)系存儲到存儲區(qū)域中，即存儲結(jié)構(gòu)3數(shù)據(jù)的運(yùn)算在這些數(shù)據(jù)上定義一個(gè)基本運(yùn)算的集合反映數(shù)據(jù)元素之間的邏輯關(guān)系1.數(shù)據(jù)的邏輯結(jié)構(gòu)2.數(shù)據(jù)的存儲結(jié)構(gòu)A.線性結(jié)構(gòu)B.非線性結(jié)構(gòu)A.順序存儲B.鏈?zhǔn)酱鎯.散列結(jié)構(gòu)D.索引結(jié)構(gòu)線性表?xiàng)ｊ?duì)列樹形結(jié)構(gòu)圖形結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的研究內(nèi)容數(shù)據(jù)元素在計(jì)算機(jī)內(nèi)部的組織方式3.數(shù)據(jù)的運(yùn)算：檢索、排序、插入、刪除、修改等基本概念邏輯結(jié)構(gòu)物理結(jié)構(gòu)數(shù)據(jù)操作本章小結(jié)第三章

線性表BasicsofComputer

Software12345線性表的基本概念線性表的順序存儲線性表的鏈?zhǔn)酱鎯Χ殃?duì)棧列線

性

表

的

基

本

概

念

與

運(yùn)

算PART 01abcdea,b,c,d,e是數(shù)據(jù)元素，表長為5線性表的概念線性表的運(yùn)算線性表的定義abcde線性表的概念線性表的運(yùn)算線性表的特點(diǎn)常見線性表有：隊(duì)列、堆棧、字符串、數(shù)組線性表的運(yùn)算線性表的概念

線性表的運(yùn)算線性表的運(yùn)算置空表取前驅(qū)求表長取后繼插入結(jié)點(diǎn)刪除結(jié)點(diǎn)按值查找提取元素排序運(yùn)算回憶：數(shù)據(jù)的物理結(jié)構(gòu)線性表的概念

線性表的運(yùn)算回顧鏈接存儲表示增加一個(gè)或多個(gè)指針，用于存放和該數(shù)據(jù)元素

有關(guān)的另一個(gè)數(shù)據(jù)元素的地址，可以不占用連續(xù)地址空間。散列存儲表示是一種在數(shù)據(jù)元素的關(guān)鍵碼與存儲位置之間建立確定對應(yīng)關(guān)系的查找

技術(shù)。順序存儲表示將邏輯上相鄰的數(shù)據(jù)元素存放在內(nèi)存中的相鄰位置中索引存儲表示指除建立存儲結(jié)點(diǎn)信息外，還建立附加的索引表來標(biāo)識結(jié)點(diǎn)的地址線

性

表

的

順

序

存

儲

及

其

運(yùn)

算PART 02定 義：將線性表中的元素相繼存放在一個(gè)

連續(xù)的存儲空間中存儲結(jié)構(gòu)：順序存儲（如：動態(tài)數(shù)組）特 點(diǎn)：邏輯上相鄰的元素，物理次序也相鄰存取方式：隨機(jī)存取順序表的概念順序表的運(yùn)算順序表的應(yīng)用順序表的定義012345678910371354645652175888092LOC(a1)=LOC(a1)LOC(a2)=

LOC(a1)+(2-1)*l：LOC(ai)=

LOC(a1)+(i-1)*la1a2…a

i………ana a+l … a+(i-1)*l

…… …a+(n-1)*lidle順序表的概念順序表的運(yùn)算順序表的應(yīng)用1 2 …順序表的存儲方式i … … … na1a2…a

i………ana a+l … a+(i-1)*l…

… … a+(n-1)*l idle例如：設(shè)順序表的首地址為1000，數(shù)據(jù)類型是整型數(shù)，則每個(gè)元素的長度是2個(gè)字節(jié)，則有：LOC(a5)=LOC(a1)+(5-1)*

2=1000+4*2=1008順序表的概念順序表的運(yùn)算順序表的應(yīng)用1 2 …順序表的存儲方式i … … … nabcd……4datalength#defineListSize

100

//最大允許長度typedefchar

ListData;typedefstruct

{

ListData

data[listsize];

//存儲空間基址

int

length; //當(dāng)前元素個(gè)數(shù)

}

SeqList; 順序表的類型名

SeqList

L；L是變量名順序表的概念順序表的運(yùn)算 順序表的應(yīng)用順序表的類型定義012345678910371354645652175data8length設(shè)有定義：SeqList

L；L表的最大長度為11表的當(dāng)前長度為8L.data[6]

//訪問第7個(gè)，即6號元素

21L.length

//表長L.data[L.length]

//順序表的下一個(gè)空位置，即8號位置順序表的概念順序表的運(yùn)算順序表的應(yīng)用順序表的引用初始化

voidInitList(SeqList

L){

L.length=

0;

}8012345678910371354645652175datalengthL0順序表的概念

順序表的運(yùn)算順序表的應(yīng)用順序表的初始化順序表的概念

順序表的運(yùn)算順序表的應(yīng)用順序表的查找

intFind(SeqListL,ListDatax

)

{int

i=0;

while(i<L.length&&

L.data[i]!=x)

i++;

if(i<L.length)return

i;

elsereturn

-1;

}i

1-1

0順序表的概念

順序表的運(yùn)算順序表的應(yīng)用按值查找算法順序表基本運(yùn)算——求表的長度

intLength(SeqListL

)

{

return

L.length;

}順序表的概念

順序表的運(yùn)算順序表的應(yīng)用求表長算法012345678910371354645652175data8lengthL在順序表L中提取第i個(gè)元素的值

ListDataGetData(SeqList&L,inti

)

{if

(i>=1&&i<=L.length)

return

L.data[i-1];

else

{

printf

(“參數(shù)

i不合理！\n”);

returnnull}

}

順序表的概念

順序表的運(yùn)算順序表的應(yīng)用取元素算法（提取函數(shù)）012345678910371354645652175data8lengthL順序表的概念

順序表的運(yùn)算順序表的應(yīng)用取元素的前驅(qū)操作listdataNext(SeqList&L,ListData

x)

{inti=

Find(L,x);

if(i>=0&&i<L.length-1

)

returnL.data[i+1];else

return

null;

}順序表的概念

順序表的運(yùn)算順序表的應(yīng)用取元素的后繼操作插入操作(i號位置插入x)for

( j=L.length;j>i;j--

)L.data[j]=L.data[j-1];L.data[i]=x;L.length++;return

1;}else {§intInsert(SeqList&L,ListDatax,inti

)if(i<0||i>L.length||L.length==

ListSize)return0; //插入失敗//移動數(shù)據(jù)//插入成功順序表的概念

順序表的運(yùn)算順序表的應(yīng)用插入操作插入時(shí)，數(shù)據(jù)平均移動次數(shù)AMN在各表項(xiàng)插入概率相等時(shí)，有：Pi是在i號位置上插入元素的概率,我們假設(shè)是等概率情況Ci是在i號位置上插入元素時(shí)所需要的移動次數(shù)插入操作(i號位置插入x)順序表的概念

順序表的運(yùn)算順序表的應(yīng)用插入操作的算法分析int Delete(SeqList&L,ListDatax

){inti=Find(L,

x);if(i>=0

)//在表中查找

x//在表中找到

x{for(intj=i;j<L.length;j++)L.data[j]=L.data[j+1];L.length--

;//成功刪除return1;}return

0;

//表中沒有

x}順序表的概念

順序表的運(yùn)算刪除指定元素x順序表的應(yīng)用刪除算法刪除時(shí)，平均移動次數(shù)AMN在各位置刪除概率相等時(shí)，有：Pi是在刪除i號位置上的元素的概率,我們假設(shè)是等概率情況Ci是在刪除i號位置上的元素時(shí)所需要的移動次數(shù)順序表的概念

順序表的運(yùn)算順序表的應(yīng)用刪除算法算法分析順序存儲結(jié)構(gòu)的優(yōu)缺點(diǎn)邏輯相鄰，物理相鄰可隨機(jī)存取任一元素存儲空間使用緊湊優(yōu)點(diǎn) 缺點(diǎn)插入、刪除操作需要移動大量的元素預(yù)先分配空間需按最大空間分配，利用不充分表容量難以擴(kuò)充設(shè)：

集合A={1，3，4，5，7，10}集合B={2，4，7，9}則：A=A∪B={1，2，3，4，5，7，9，10}={1，3，4，5，7，10，2，9}={2，4，7，9，1，3，5，10}看：A=A∪B={1，3，4，5，7，10，2，9}=A+(B-A)結(jié)論：A和B的并集中，A中的所有元素屬于他們的并集B中除去屬于A的剩余元素同樣屬于他們的并集因此：只要以A為基礎(chǔ)，從B中依次取出所有元素，在A中查詢，如果沒找到就將該元素插入到A中順序表的概念順序表的運(yùn)算

順序表的應(yīng)用集合的“并”運(yùn)算//在B中取一元素//在A中查找它//未找到，則插入到A尾部{intx=GetData(B,i

);intk=Find(A,

x);if(k==-1

)Insert(A,x,

A.length)}}算法思路：以A為基礎(chǔ)，從B中依次取出所有元素，在A中查詢，如果沒找到就將該元素插入到A中voidUnion(SeqList&A,SeqList&B

){ for(inti=0;i<B.lenggth;i++

)順序表的概念順序表的運(yùn)算

順序表的應(yīng)用

集合的“并”運(yùn)算設(shè)：

集合A={1，3，4，5，7，10}集合B={2，4，7，9}則：A=A∩B={4，7}因此：只要以A為基礎(chǔ)，從A中依次取出所有元素，在B中查詢，如果沒找到就將該元素從A中刪除順序表的概念順序表的運(yùn)算

順序表的應(yīng)用集合的“交”運(yùn)算voidIntersection(SeqList&A,SeqList&B

){inti=

0;while(i<A.length

){//在A中取一元素//在B中查找它//未找到在A中刪除它intx=GetData(A,i

);intk=Find(B,x

);if(k==-1

)Delete(A,

x);elsei++;}}順序表的概念順序表的運(yùn)算

順序表的應(yīng)用集合的“交”運(yùn)算（一）voidIntersection(SeqList&A,SeqList&B

){inti=A.length-1;while(i>=0A.length

){//在A中取一元素//在B中查找它//未找到在A中刪除它intx=GetData(A,i

);intk=Find(B,x

);if(k==-1

)Delete(A,

x);i++;}}大家可以分析一下交集的方法1和方法2有什么不同？為什么不用for循環(huán)？順序表的概念順序表的運(yùn)算

順序表的應(yīng)用集合的“交”運(yùn)算（二）線

性

表

的

鏈

式

存

儲

及

其

運(yùn)

算PART 03單鏈表雙向鏈表循環(huán)鏈表靜態(tài)鏈表鏈表：線性表的鏈?zhǔn)酱鎯Ρ硎?定義：用一組地址任意的存儲單元存放線性表中的數(shù)據(jù)元素。鏈表：線性表的鏈?zhǔn)酱鎯Ρ硎?每個(gè)元素由結(jié)點(diǎn)(Node)構(gòu)成，它包括兩個(gè)域:數(shù)據(jù)域（Data）和

指針域（next）存儲結(jié)構(gòu)：鏈?zhǔn)酱鎯Y(jié)構(gòu)特 點(diǎn)：存儲單元可以不連續(xù)。存取方式：按順序存取。Nodedata

next線性鏈表的結(jié)點(diǎn)結(jié)構(gòu)1typedefintListData;

//定義數(shù)據(jù)類型typedefstructnode

//鏈表結(jié)點(diǎn)

{

ListData

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

structnode*next;

//結(jié)點(diǎn)鏈域}

ListNode;Typedef

ListNode

*

LinkList;

//鏈表頭指針LinkListhead，p,q;

//鏈表頭指針Nodedata nextListNode是類型名線性鏈表的類型定義1為使運(yùn)算簡單，可以在單鏈表的第一個(gè)結(jié)點(diǎn)之前另加一個(gè)結(jié)點(diǎn)，稱之為頭結(jié)點(diǎn)。后面的鏈表操作均是帶頭結(jié)點(diǎn)的單鏈表….

FBAhead頭結(jié)點(diǎn) 第一結(jié)點(diǎn)設(shè)置表頭結(jié)點(diǎn)的目的是統(tǒng)一空鏈表與非空鏈表的操作，簡化鏈表操作的實(shí)現(xiàn)。帶頭結(jié)點(diǎn)的單鏈表1

952headPp->data;p->next;p->next->data;q->next=nil;p=p->next;q//得到元素值2//2和5之間的指針//得到元素值5p->next->next->data; //得到元素9//最后一個(gè)結(jié)點(diǎn)的指針分量置空//指針后移一個(gè)節(jié)點(diǎn)單鏈表的引用1情況1headabc ^單鏈表的插入操作情況1：在第一個(gè)結(jié)點(diǎn)前插入情況2：中間插入情況3：插入到鏈表尾部情況3情況2newnodea bc ^Newnode->next=p->next;p->next=newnode;Phead第一種情況：在第一個(gè)結(jié)點(diǎn)前插入單鏈表的插入操作第二種情況：在鏈表中間插入單鏈表的插入操作第三種情況：在鏈表尾部插入單鏈表的插入操作1.移動指針P向后移動，指向下一個(gè)結(jié)點(diǎn)：

p=p->next;2.用指針動態(tài)申請一個(gè)結(jié)構(gòu)體空間：malloc函數(shù)的格式：(類型

*)

malloc(size）；q=(ListNode*)malloc(sizeof(ListNode));q->data=x;3.在移動指針P之后，插入新結(jié)點(diǎn)的操作：q->next=p->next;p->next=q;準(zhǔn)備知識(在head鏈表第

i

個(gè)結(jié)點(diǎn)處插入新元素

x)intInsert(LinkList*head,inti,int

x)

{

p=head;

k=0;

while(p!=nil&&

k<i-1)

{

p=p->next;

k++;

}

//找第

i-1個(gè)結(jié)點(diǎn)

if(p==nil)

//終止插入

{

printf(“無效的插入位置!\n”);

return0;

}

q=(ListNode*)

malloc(sizeof(ListNode));

q->data=x;

//創(chuàng)建新結(jié)點(diǎn)

q->next=p->next;

//完成插入

p->next=q;

Return1;}

單鏈表插入算法一//完成插入

q->next=p->next;

p->next=q;

}

插入算法2(在有序鏈表head中插入元素x)Insertsort(LinkList*head,int

x)

{

p=head;

while

(p

-

>

n

e

x

t

！

=

n

i

l

&

&

p

-

>

n

e

x

t

-

>

d

a

t

a

<

=

x

)

p=p->next;

//為x結(jié)點(diǎn)定位

q=(ListNode*)

malloc(sizeof(ListNode));

q->data=x;

//創(chuàng)建新結(jié)點(diǎn)單鏈表插入算法二單鏈表的刪除操作（刪除P之后的結(jié)點(diǎn)）單鏈表的刪除操作intDelete(head,x){p=head;

while(p->next!=nil&&

p->next->data!=x)

p=p->next;

if(p->next==nil

)

{printf(“鏈表中沒有要刪除的元素”)；

return0；}

q=p->next;

p->next=q->next;

free(q);

Return

1}刪除元素值為x的結(jié)點(diǎn)單鏈表的刪除算法前插法建立單鏈表建立空鏈表從一個(gè)空表開始，重復(fù)讀入數(shù)據(jù)：生成新結(jié)點(diǎn)將讀入數(shù)據(jù)存放到新結(jié)點(diǎn)的數(shù)據(jù)域中將該新結(jié)點(diǎn)插入到鏈表的前端直到讀入結(jié)束符為止。設(shè)輸入順序?yàn)椋?、5、2LinkListcreateListF

()

{

head=(LinkList)

malloc(sizeof(ListNode));

head->next=nil;

//建立空鏈表

scanf(“%d”,&x);

while

(x!=0)

{

q=(listNode*)malloc

(sizeof(ListNode));

q->data=x;

//建立新結(jié)點(diǎn)

q->next=head->next;

//插入到頭節(jié)點(diǎn)之后

head->next=q;

scanf(“%d”,&x);

}

returnhead;}前插法建立單鏈表算法每次將新結(jié)點(diǎn)加在鏈表的表尾；尾指針rear

,總是指向表中最后一個(gè)結(jié)點(diǎn)，新結(jié)點(diǎn)插在它的后面；后插法建立單鏈表LinkListcreateListR

(){head=(LinkList)

malloc(sizeof(ListNode));

head->next=nil;

//建立空鏈表

rear=head;

scanf(“%d”,&x);

while

(x!=0)

{

q=(listNode*)malloc

(sizeof(ListNode));

q->data=x;

//建立新結(jié)點(diǎn)//插入到頭節(jié)點(diǎn)之后

rear->next=q;

rear=q;

scanf(“%d”,&x);

}

rear->next=

nil;

returnhead;}后插法建立單鏈表算法單鏈表的輸出output(head);//讓移動指針指向第一個(gè)結(jié)點(diǎn){p=head->next；while

(p!=nil){printf(“%5d”,p->data);p=p->next; //指針后移}}intLength(LinkList

head)

{

p=head->next;count=0;

while(p!=NULL

)

{

count++;

p=p->next;

}

return

count;}計(jì)算單鏈表長度單鏈表的清空刪去除結(jié)點(diǎn)外的所有結(jié)點(diǎn)voidmakeEmpty(LinkListhead

)

{

ListNode

*q;

while

(head->next!=nil)

{

q=head->next;

head->next=q->next;

free(q);

//釋放

}

}ListNode*Find(LinkListhead,ListDatavalue

)

{

//在鏈表中從頭搜索其數(shù)據(jù)值為value的結(jié)點(diǎn)p=head->next; //指針

p

指示第一個(gè)結(jié)點(diǎn)while(p!=nil&&

p->data!=value)

p=p->next;

return

p;

}問題：如果在有序鏈表中進(jìn)行查找，該如何修改，以提高效率？單鏈表的按值查找ListNode*Locate(LinkListhead,int

i){//返回表中第i個(gè)元素的地址

if(i<0)return

nil;

p=head;

k=0;

while(p!=nil&&k<i

)

{p=p->link;

k++;

} //找第

i

個(gè)結(jié)點(diǎn)

if

(k==i)

return

p;

//返回第

i

個(gè)結(jié)點(diǎn)地址

elsereturn

nil;

}單鏈表的按序號查找循環(huán)鏈表特點(diǎn):最后一個(gè)結(jié)點(diǎn)的

next指針不為nil，而是指向頭結(jié)點(diǎn)。只要已知表中某一結(jié)點(diǎn)的地址，就可搜尋所有結(jié)點(diǎn)的地址存儲結(jié)構(gòu):鏈?zhǔn)酱鎯Y(jié)構(gòu)an-1heada1a0head(空表)(非空表)帶表頭結(jié)點(diǎn)的循環(huán)鏈表循環(huán)鏈表的插入、刪除、查詢等操作和相應(yīng)的單鏈表的操作基本相同。區(qū)別：在判斷尾結(jié)點(diǎn)時(shí)的條件不同。單

鏈

表：p->next==nil循環(huán)鏈表：p->next==head循環(huán)鏈表q->next=p->next;p->next=q;q=p->next;p->next=q->next;free(q);循環(huán)鏈表的插入循環(huán)鏈表的刪除雙向鏈表結(jié)點(diǎn)結(jié)構(gòu)：指向直接前驅(qū)指向直接后繼非空表空表headhead雙向循環(huán)鏈表typedefintListData;typedefstruct

dnode

{

ListNode

data;

structdnode*prior,

*next;

}

DblNode;typedefDblNode*

DblList;

雙向循環(huán)鏈表的定義voidCreateDblList(DblList

head)

{

head=(DblNode*)malloc(sizeof(

DblNode));

head->prior=head;

head->next=head;

//表頭結(jié)點(diǎn)的鏈指針指向自己}head建立空的雙向循環(huán)鏈表intLength(DblList

h