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

計(jì)算機(jī)軟件基礎(chǔ)學(xué)時(shí)安排授課34+上機(jī)22章內(nèi)容學(xué)時(shí)章內(nèi)容學(xué)時(shí)1緒論27樹和二叉樹82線性表68圖23堆棧和隊(duì)列49排序44串10查找45數(shù)組211文件6遞歸算法復(fù)習(xí)2數(shù)學(xué)軟件硬件數(shù)據(jù)結(jié)構(gòu)課程的地位是介于數(shù)學(xué)、計(jì)算機(jī)硬件和計(jì)算機(jī)軟件三者之間的一門核心課程第一章緒論1.1

數(shù)據(jù)結(jié)構(gòu)的基本概念1.2數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容和方法1.4*C語言相關(guān)內(nèi)容復(fù)習(xí)1.3算法和算法分析1.1

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

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

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

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

1.

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

2.

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

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

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

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

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

Data_Structure={D,R}

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

根據(jù)數(shù)據(jù)元素間關(guān)系的基本特性，有四種基本數(shù)據(jù)結(jié)構(gòu)集合結(jié)構(gòu)

數(shù)據(jù)元素間除“同屬于一個(gè)集合”外，無其它關(guān)系線性結(jié)構(gòu)

一個(gè)對一個(gè)，如線性表、棧、隊(duì)列樹形結(jié)構(gòu)

一個(gè)對多個(gè)，如樹圖狀結(jié)構(gòu)

多個(gè)對多個(gè)，如圖集合結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu):

SET=（K,R）

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

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

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

線性結(jié)構(gòu)

非線性結(jié)構(gòu)

順序存儲

鏈?zhǔn)酱鎯€性表堆棧隊(duì)列樹形結(jié)構(gòu)圖形結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的三個(gè)方面：

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

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

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

一個(gè)完整的算法應(yīng)該滿足下面五個(gè)基本標(biāo)準(zhǔn)：輸入性

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

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

一個(gè)程序在計(jì)算機(jī)中運(yùn)行時(shí)間的多少與諸多因素有關(guān)，其中主要有：4.時(shí)間復(fù)雜度稱為時(shí)間頻度，記為T（n）

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

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

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

例：3n+2=O(n)/*3n+24nforn2*/10n2+4n+2=O(n2)/*10n2+4n+211n2forn5*/6*2n+n2=O(2n) /*6*2n+n27*2nforn4*/常用的計(jì)算規(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))

時(shí)間復(fù)雜度T(n)按數(shù)量級遞增順序?yàn)椋?/p>

注

空間復(fù)雜度S(n)按數(shù)量級遞增順序也與上表類同。復(fù)雜度高復(fù)雜度低時(shí)間復(fù)雜度的計(jì)算：例1：{++x;s=0;}2O(1)for(i=1;i<=n;++i){++x;s+=x;}n+2nO(n)for(j=1;j<=n;++j)for(k=1;k<=n;++k){++x;s+=x;}2n+2n2O(n2)例2：例3：頻度時(shí)間復(fù)雜度程序例4：頻度時(shí)間復(fù)雜度程序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：頻度時(shí)間復(fù)雜度程序O(n3)int

i,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ù)結(jié)構(gòu)是指計(jì)算機(jī)處理的①的組織形式以及它們相互之間的②。①A.數(shù)據(jù)元素B.計(jì)算方法

C.邏輯存儲D.數(shù)據(jù)映像②A.結(jié)構(gòu)B.關(guān)系

C.運(yùn)算D.算法課堂練習(xí)3、衡量算法好壞的兩個(gè)主要指標(biāo)有算法的

和

。時(shí)間復(fù)雜度空間復(fù)雜度2、數(shù)據(jù)結(jié)構(gòu)研究數(shù)據(jù)的

、

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

A.結(jié)構(gòu)關(guān)系、組織形式

B.邏輯結(jié)構(gòu)、物理結(jié)構(gòu)

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

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

。

i=s=0;while(s<n){i++;s+=i;}O(n)5、算法的時(shí)間復(fù)雜度僅與問題的規(guī)模有關(guān)。

（）×*還與輸入的元素取值有關(guān)6、下面程序段A[i][j]=0執(zhí)行次數(shù)為

,

時(shí)間復(fù)雜度為

。

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ù)項(xiàng)，數(shù)據(jù)結(jié)構(gòu)。特別是數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及數(shù)據(jù)運(yùn)算的含義及其相互關(guān)系。數(shù)據(jù)結(jié)構(gòu)的兩大類邏輯結(jié)構(gòu)和四種常用的存儲表示方法。

掌握：算法、算法的時(shí)間復(fù)雜度和空間復(fù)雜度、最壞的和平均時(shí)間復(fù)雜度等概念，對一般算法要能分析出時(shí)間復(fù)雜度。作業(yè)：P251-1，1-2，1－3，

1－7，1-11小結(jié)END復(fù)習(xí)：C語言的數(shù)據(jù)類型1、基本數(shù)據(jù)類型intshort;long;unsignedfloatfloat;double;longdouble2、指針類型10003i_pointeri地址（i的指針）指針變量1000*i_pointeri1000

15i=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ù)時(shí)，為地址傳遞inta[100];a&a[0],a+1&a[1]……*aa[0],*(a+1)a[1]……4、字符串

字符串定義成字符數(shù)組‘\0’為字符串結(jié)束標(biāo)志chara[40]=“Iamastudent”;strlen(a)為14不包括‘\0’5.結(jié)構(gòu)體類型結(jié)構(gòu)體由若干個(gè)結(jié)構(gòu)體成員組成。定義結(jié)構(gòu)體類型變量：1.定義結(jié)構(gòu)體類型；2.定義結(jié)構(gòu)體類型變量。structstudent{charname[10];

intage;floatscore;};structstudentstudent1;structstudentstu2[100];structstudent*p;6.

自定義類型typedefcharelemtype;typedef

structstudent{charname[10];

intage;floatscore;}stu;elemtypea;stustudent1;

數(shù)據(jù)項(xiàng)具有獨(dú)立含義的最小標(biāo)識單位,是數(shù)據(jù)的最小單位數(shù)據(jù)元素?cái)?shù)據(jù)項(xiàng)學(xué)號姓名性別籍貫出生年月住址06048001趙玲女上海1987.10上海06048002楊揚(yáng)男北京1987.3北京………………………………邏輯結(jié)構(gòu)a1a2a3

a30…d1d2d3d4

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

姓名性別民族年齡其他

例2.鏈?zhǔn)酱鎯Y(jié)構(gòu)…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);}求解：設(shè)母雞、公雞、小雞各為i,j,k只，則有：

i+j+k=100 5i+3j+k/3=100

只需要解出本方程就可以得到答案。方法1：用三重循環(huán)方法2、3：用兩重循環(huán)因總共買100只雞，所以小雞的數(shù)目可以由母雞數(shù)和公雞數(shù)得到。

for(i=0;i<100;i++)for(j=0;j<100;j++){

k=100-i-j;if(k%3==0&&(5*i+3*j+k/3)==100)

printf(“%d,%d,%d\n”,i,j,k);}for(i=0;i<=20;i++)for(j=0;j<33;j++){

k=100-i-j;if(k%3==0&&(5*i+3*j+k/3)==100)

printf(“%d,%d,%d\n”,i,j,k);}

方法4：用一重循環(huán)由i+j+k=100和5*i+3*j+k/3=100合并為一個(gè)方程： 14*i+8*j=200,

簡化:7*i+4*j=100

得:i不超過14，i必為4的倍數(shù)？!

for(i=0;i<=14;i+=4){

j=(100-7*i)/4;k=100-i-j;

printf(“%d,%d,%d\n”,i,j,k);}上面四個(gè)方法中， 第一個(gè)方法的循環(huán)次數(shù)為：100*100*100,一百萬次；第二個(gè)方法的循環(huán)次數(shù)為：100*100，1萬次；第三個(gè)方法為：20*34，680次;

第四個(gè)方法為：4次.由此可見，算法的設(shè)計(jì)至關(guān)重要。BACK第二章線性表Chapter2LinearList數(shù)據(jù)結(jié)構(gòu)課程——涉及數(shù)學(xué)、計(jì)算機(jī)硬件和計(jì)算機(jī)軟件數(shù)據(jù)結(jié)構(gòu)定義——指互相有關(guān)聯(lián)的數(shù)據(jù)元素的集合，用D_S=(D,R)或S=(D,R)表示。數(shù)據(jù)結(jié)構(gòu)內(nèi)容——數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和運(yùn)算

算法效率指標(biāo)——時(shí)間效率和空間效率要點(diǎn)回顧

數(shù)據(jù)的邏輯結(jié)構(gòu)

數(shù)據(jù)的存儲結(jié)構(gòu)

數(shù)據(jù)的運(yùn)算

線性結(jié)構(gòu)

非線性結(jié)構(gòu)

順序存儲

鏈?zhǔn)酱鎯€性表、棧、隊(duì)列、串、數(shù)組樹形結(jié)構(gòu)圖形結(jié)構(gòu)

散列存儲索引存儲插入、刪除、修改、查找、排序等邏輯結(jié)構(gòu)唯一存儲結(jié)構(gòu)不唯一運(yùn)算的實(shí)現(xiàn)依賴于存儲結(jié)構(gòu)線性表的邏輯結(jié)構(gòu)線性表的順序存儲結(jié)構(gòu)線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)（單鏈表）應(yīng)用實(shí)例本章內(nèi)容

若結(jié)構(gòu)是非空有限集，則有且僅有一個(gè)開始結(jié)點(diǎn)和一個(gè)終端結(jié)點(diǎn)，并且所有結(jié)點(diǎn)都最多只有一個(gè)直接前趨和一個(gè)直接后繼。可表示為：（a0,a1,……,an-1）

線性結(jié)構(gòu)的定義：線性結(jié)構(gòu)的特點(diǎn)：①只有一個(gè)首結(jié)點(diǎn)和一個(gè)尾結(jié)點(diǎn)；②

除首尾結(jié)點(diǎn)外，其他結(jié)點(diǎn)只有一個(gè)直接前驅(qū)和一個(gè)直接后繼。線性結(jié)構(gòu)包括線性表、堆棧、隊(duì)列、字符串、數(shù)組等等，其中，最典型最常用的是------（a0,a1…ai-1，ai,ai＋1

，…,an-1）2.1線性表的邏輯結(jié)構(gòu)

1.線性表的定義：用數(shù)據(jù)元素的有限序列表示n=0時(shí)稱為數(shù)據(jù)元素線性起點(diǎn)（首結(jié)點(diǎn)）ai的直接前趨ai的直接后繼下標(biāo)，是元素的序號，表示元素在表中的位置空表線性終點(diǎn)（尾結(jié)點(diǎn)）n為元素總個(gè)數(shù)，即表長例1分析26個(gè)英文字母組成的英文表

（A,B,C,D,……,Z）學(xué)號姓名性別年齡班級06048001于春梅女18微電06106048002何仕鵬男18微電06106048003王爽女18微電06106048004王亞武男18微電061：：：：：例2分析學(xué)生情況登記表每個(gè)數(shù)據(jù)元素由5個(gè)數(shù)據(jù)項(xiàng)組成;元素之間的關(guān)系是線性的數(shù)據(jù)元素都是字母;元素之間的關(guān)系是線性的同一線性表中的元素必定具有相同特性2.線性表的基本操作Initiate(L)

初始化操作。建立一個(gè)空線性表L。Length(L)

求表長。求給定線性表L中數(shù)據(jù)元素的個(gè)數(shù)。Get(L,i)

讀取元素。讀取線性表L中第i個(gè)數(shù)據(jù)元素。Insert(L,i,x)前插。在線性表L中第i個(gè)數(shù)據(jù)元素

ai之前插入一個(gè)新的數(shù)據(jù)元素x。Delete(L,i)刪除。刪除線性表L中第i個(gè)的數(shù)據(jù)元素ai。Locate(L,x)

定位函數(shù)。返回線性表L中元素值等于x的數(shù)據(jù)元素ai的序號i。2.2線性表的順序存儲結(jié)構(gòu)—順序表

一、順序表

用一組地址連續(xù)的存儲單元存儲線性表的各個(gè)數(shù)據(jù)元素，稱作線性表的順序存儲結(jié)構(gòu)，簡稱順序表。

順序表的特點(diǎn)：1.邏輯上相鄰的數(shù)據(jù)元素，其物理上也相鄰；2.

若已知表中首元素在存儲器中的位置，則其他元素存放位置亦可求出（利用數(shù)組下標(biāo)，參見存儲結(jié)構(gòu)示意圖）。邏輯地址數(shù)據(jù)元素存儲地址數(shù)據(jù)元素0a0Loc(a0)a01a1Loc(a0)+Ka1…………iaiLoc(a0)+i*Kai……n-1an-1Loc(a0)+(n-1)*Kan-1線性表的順序存儲結(jié)構(gòu)示意圖首地址每個(gè)元素占K字節(jié)一個(gè)一維數(shù)組Ｍ，下標(biāo)的范圍是０到９，每個(gè)數(shù)組元素用相鄰的５個(gè)字節(jié)存儲。存儲器按字節(jié)編址，設(shè)存儲數(shù)組元素Ｍ[０]的第一個(gè)字節(jié)的地址是98，則Ｍ[３]的第一個(gè)字節(jié)的地址是

113例1：因此：LOC(M[3])=98+5×3=113解：地址計(jì)算通式為：LOC(ai)=LOC(a0)+L*i用c語言定義順序表#defineMaxlen100typedef

struct{charname[10];charsex;

intage;}elemtype;elemtype

List[Maxlen];intnum=-1;/*定義數(shù)據(jù)類型*//*定義順序表*//*當(dāng)前數(shù)據(jù)元素下標(biāo)*//*順序表最大長度*/姓名性別年齡張三M18李四F19………………typedef

struct{elemtype

List[Maxlen];

intnum;}SeqList;ss->nums->List[0]s->List[1]s->List[2]…s->List[Maxlen-1]SeqLista;SeqList*s;a.num，a.List[0]……numList[0]List[1]…用c語言定義順序表二、順序表的基本操作1.初始化ListInitiate(L)voidListInitiate(SeqList*L){L->num=-1;}/*num指示線性表最后一個(gè)元素的下標(biāo)*/2.求表長ListLength(L)int

ListLength(SeqListL){returnL.num+1;}3.取數(shù)據(jù)元素ListGet(L，i，x)int

ListGet(SeqList

L,int

i,elemtype*x){if(i<0||i>L.num){printf(“ERROR!\n”);return0;}else{*x=L.List[i];return1;}}…Maxlen-1a0a1…ai-1aiai+1an-1…01…i-1ii+1n-1…a0a1…ai-101…i-1iMaxlen-1…ai+1an-1…aii+1…i+2na0a1…ai-1aiai+1an-1…Maxlen-101…i-1ii+1…i+2…nx4.插入（在第i個(gè)（0<=i<=n）數(shù)據(jù)元素之前插入一個(gè)新的數(shù)據(jù)元素x）i位置非法？開始表滿？n-1至i位置的元素依次后移將元素x存放在i位置表長加1結(jié)束i非法表滿NYNY前插算法流程圖是否滿足0≤i≤num+1num≤

Maxlen-1是否成立for(j=num;j>=i;j--)a[j+1]=a[j];

a[i]=x;

num++;注意：n表示數(shù)據(jù)元素的個(gè)數(shù),num是線性表最后一個(gè)元素的下標(biāo)增強(qiáng)健壯性int

ListInsert(SeqList*L,inti,elemtypex){intj;

if(i<0||i>L->num+1){printf(“error\n”);return0;}if(L->num)>=Maxlen-1){printf(“overflow\n”);return0;}for(j=L->num;j>=i;j--)L->list[j+1]＝L->List[j];L->List[i]＝x;L->num＝L->num+1;return1;}判斷i是否合法判斷表是否已滿若i合法，元素后移將元素x存放在i位置當(dāng)前數(shù)據(jù)元素下標(biāo)加1用c語言描述插入算法該算法的時(shí)間復(fù)雜度：Eis:

插入一個(gè)元素所需平均移動(dòng)次數(shù):

則

因此,該算法的時(shí)間復(fù)雜度為O(n)。a0a1…ai-101…i-1iai5.刪除（刪除第i個(gè)（0<=i<=n-1）數(shù)據(jù)元素）…Maxlen-1a0a1…ai-1aiai+1an-1…01…i-1ii+1n-1…Maxlen-1…ai+1ai+2an-1…i+1n-2…iaix刪除算法流程圖位置非法？開始i+1至n-1位置的元素依次前移表長減1結(jié)束i非法NY表空？表空Yfor(j=i+1;j<=num;j++)a[j-1]=a[j];num--;判斷num<0是否成立是否滿足0≤i≤

numN用c語言描述刪除算法int

ListDelete(SeqList*L,inti,elemtype*x){intj;if(L->num<0){printf(“\nThelistisempty!”);return0;}elseif(i<0||i>L->num){printf(“\nthepositionisinvalid”);return0;}else{*x=L->list[i];for(j=i+1;j<=L->num;j++)L->list[j-1]=L->list[j];L->num--;return1;}}/*刪除順序表L中的第i個(gè)元素,并將其保存在x中*//*判斷表是否為空*//*若i合法，元素依次前移*//*當(dāng)前數(shù)據(jù)元素下標(biāo)減1*//*判斷i值是否合法*/該算法的時(shí)間復(fù)雜度：Edl：刪除一個(gè)元素所需平均移動(dòng)次數(shù)

因此,該算法的時(shí)間復(fù)雜度為O(n)。算法時(shí)間主要耗費(fèi)在移動(dòng)元素的操作上，因此計(jì)算時(shí)間復(fù)雜度的基本操作（最深層語句頻度）T(n)=O

(移動(dòng)元素次數(shù))移動(dòng)元素的個(gè)數(shù)取決于插入或刪除元素的位置.順序表時(shí)間效率分析:順序表的空間復(fù)雜度S(n)=O(1)（沒有占用輔助空間）順序表空間效率分析:三、順序存儲結(jié)構(gòu)的特點(diǎn)順序表的優(yōu)點(diǎn)：無需為表示節(jié)點(diǎn)間的邏輯關(guān)系而增加額外的存儲空間可以方便地隨機(jī)存取表中的任一節(jié)點(diǎn)順序表的缺點(diǎn)：插入和刪除運(yùn)算不方便,需要移動(dòng)大量的數(shù)據(jù)元素。由于要求占用連續(xù)的存儲空間，存儲分配只能預(yù)先進(jìn)行作業(yè)：P552-82-14(順序表)如何克服順序表的這些缺點(diǎn)呢？第二章線性表線性結(jié)構(gòu)的特點(diǎn)：僅有一個(gè)首、尾結(jié)點(diǎn)，其余元素僅有一個(gè)直接前驅(qū)和一個(gè)直接后繼。2.線性表邏輯結(jié)構(gòu)：“一對一”或1:1存儲結(jié)構(gòu)：順序存儲、鏈?zhǔn)酱鎯?.順序表特征：邏輯上相鄰，物理上一定相鄰優(yōu)點(diǎn)：隨機(jī)查找快缺點(diǎn)：插入、刪除慢；

需要預(yù)先知道線性表的長度

單鏈表基本概念單鏈表基本操作

線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)—鏈表循環(huán)單鏈表雙向鏈表單鏈表初始化插入刪除求元素個(gè)數(shù)取元素單鏈表的基本概念線性表鏈?zhǔn)酱鎯Y(jié)構(gòu)的一種。用一組不一定連續(xù)的存儲單元來存放數(shù)據(jù)元素。

數(shù)據(jù)域指針域結(jié)點(diǎn)頭指針空指針130Aheada01475130Aa110CB1475a2^10CB

數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針連接次序來實(shí)現(xiàn)的。

結(jié)點(diǎn)datanext數(shù)據(jù)域指針域typedef

structNode{DataTypedata;

structNode*next;}SLNode；單鏈表結(jié)點(diǎn)的定義：

2.3.1單鏈表的存儲結(jié)構(gòu)Loc(a1)Loc(a2)…Loc(an-1)Loc(a0)第2個(gè)學(xué)生信息第3個(gè)學(xué)生信息…最后一個(gè)學(xué)生信息第1個(gè)學(xué)生信息邏輯示意圖第2個(gè)學(xué)生信息Loc(a2)第3個(gè)學(xué)生信息Loc(a3)……第n個(gè)學(xué)生信息結(jié)束標(biāo)志第1個(gè)學(xué)生信息Loc(a1)物理示意圖第n個(gè)學(xué)生信息NULL第1個(gè)學(xué)生信息Loc(a2)第2個(gè)學(xué)生信息Loc(a3)head

鏈表結(jié)構(gòu)示意圖……帶頭結(jié)點(diǎn)的單鏈表12EFhead130A12EFa01475130Aa110CB1475a2^10CB帶頭結(jié)點(diǎn)的空單鏈表

^headhead->next==NULL不帶頭結(jié)點(diǎn)的單鏈表130Aheada01475130Aa110CB1475a2^10CB不帶頭結(jié)點(diǎn)的空單鏈表^headhead==NULL頭指針頭結(jié)點(diǎn)首元結(jié)點(diǎn)何謂頭指針、頭結(jié)點(diǎn)和首元結(jié)點(diǎn)？頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)（或?yàn)轭^結(jié)點(diǎn)或?yàn)槭自Y(jié)點(diǎn)）的指針。

單鏈表可由一個(gè)頭指針唯一確定。頭結(jié)點(diǎn)是在鏈表的首元結(jié)點(diǎn)之前附設(shè)的一個(gè)結(jié)點(diǎn)；數(shù)據(jù)域內(nèi)只放空表標(biāo)志和表長等信息;首元結(jié)點(diǎn)是指鏈表中存儲線性表第一個(gè)數(shù)據(jù)元素a0的結(jié)點(diǎn)。

頭指針頭結(jié)點(diǎn)首元結(jié)點(diǎn)a0一個(gè)線性表的邏輯結(jié)構(gòu)為：（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），其存儲結(jié)構(gòu)用單鏈表表示如下，請問其頭指針的值是多少？存儲地址數(shù)據(jù)域指針域1LI437QIAN1313SUN119WANGNULL25WU3731ZHAO737ZHENG1943ZHOU25例：答：頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)的指針，因此關(guān)鍵是要尋找第一個(gè)結(jié)點(diǎn)的地址。7ZHAOH31∴頭指針的值是31上例鏈表的邏輯結(jié)構(gòu)示意圖有以下兩種形式：①ZHAOQIANLISUNZHOUWUZHENG/\WANGH②HZHAOQIANLISUNZHOUWUZHENG/\WANG區(qū)別：①

無頭結(jié)點(diǎn)②

有頭結(jié)點(diǎn)

相關(guān)知識動(dòng)態(tài)內(nèi)存分配設(shè)計(jì)人員根據(jù)具體問題的具體需要，在程序運(yùn)行時(shí)再具體確定數(shù)組的個(gè)數(shù)或占用內(nèi)存單元的大小，從而在程序運(yùn)行時(shí)具體確定所需要的內(nèi)存單元空間。malloc()函數(shù)free()函數(shù)頭文件malloc.h#include<malloc.h>malloc()函數(shù)free()函數(shù)函數(shù)原型：

void*malloc(unsignedsize)函數(shù)功能：用于向系統(tǒng)動(dòng)態(tài)申請size個(gè)字節(jié)的內(nèi)存單元空間，函數(shù)返回值為所申請的內(nèi)存空間首地址。函數(shù)原型：

voidfree(void*p)函數(shù)功能：用于釋放動(dòng)態(tài)分配的內(nèi)存空間。sizeof

運(yùn)算符：sizeof(已定義的數(shù)據(jù)類型)功能：返回括號中給出的已定義數(shù)據(jù)類型占用的字節(jié)個(gè)數(shù)。MemoryAllocation如：sizeof(int)例如：定義結(jié)構(gòu)體類型

typedef

struct

nodetype{intdata;

struct

nodetype*next;}SLNode;p=(SLNode*)malloc(sizeof(SLNode));SLNode*p;p=malloc(sizeof(SLNode));強(qiáng)制類型轉(zhuǎn)換（1）指針后移操作

p=p->next130Apa11475130Aa216001475…1475（2）指向指針的指針

SLNode**h;130A*ha11475130A**h1000h1000一級指針二級指針int

ListInitiate(SLNode**head){if((*head=(SLNode*)malloc(sizeof(SLNode)))==NULL)return0;(*head)->next=NULL;return1;}（1）初始化2.3.2單鏈表的操作實(shí)現(xiàn)12EFhead*headNULLmain(){SLNode*h;ListInitiate(&h);}頭結(jié)點(diǎn)12EF(2)求當(dāng)前數(shù)據(jù)元素個(gè)數(shù)int

ListLength(SLNode*head){SLNode*p=head;

intsize=0;while(p->next!=NULL){p=p->next;size++;}returnsize;}12EFhead130A12EFa01475130Aan-110CB1800…12EFpsize=0130Apsize=11800psize=n(3)取元素（尋找到第i個(gè)結(jié)點(diǎn)ai并返回該結(jié)點(diǎn)的數(shù)據(jù)元素）12EFhead130A12EFa01475130Aai10CB1800an-1^1700…ai+1150010CB…1800p130Ap12EFp{p=p->next;j++;}while(p->next!=NULL&&j<i)*x=p->data;int

ListGet(SLNode*head,int

i,DataType*x){SLNode*p;

intj=0;p＝head;while((p->next!=NULL)&&(j<i)){p＝p->next;j++;}if(j!=i){printf(“取元素位置參數(shù)錯(cuò)！”);return0;}*x=p->data;return1;}/*找第i個(gè)結(jié)點(diǎn)*//*判斷是否找到該結(jié)點(diǎn)*//*將數(shù)據(jù)元素值賦給*x*/

xP(1)步驟:（1）找插入位置，指針p指向ai的前一個(gè)結(jié)點(diǎn)

（2）插入：1、x結(jié)點(diǎn)指針域指向ai結(jié)點(diǎn)

2、ai-1結(jié)點(diǎn)的指針域指向x結(jié)點(diǎn)

(2)(2.1)(2.2)（4）插入運(yùn)算（前插，即在ai之前插入一個(gè)數(shù)據(jù)元素x）sheada0ai-1ai…an-1

不可以?。?.1）和（2.2）可不可以交換？為什么？heada0ai-1ai…an-1

P(1)

xs

x？an-1^1700{p=p->next;j++;}while(p->next!=NULL&&j<i-1)1614x1614sp->next=s;12EFhead130A12EFa01475130Aai-110CB1800…ai150010CB…161410CBs->next=p->next;s->data=x;s=(SLNode*)malloc(sizeof(SLNode));12EFpj=-1130Apj=01800pj=i-1int

ListInsert(SLNode*head,inti,DataTypex){SLNode*p,*s;

intj;p=head;j=-1;

while((p->next!=NULL)&&(j<i-1)){p=p->next;j++;}用c語言實(shí)現(xiàn)的單鏈表插入算法定義變量并初始化搜索表，尋找ai-1結(jié)點(diǎn)if(j!=i-1){printf(“\n插入位置不合理！”);return0;}if((s=(SLNode*)

malloc(sizeof(SLNode)))==NULL)return0;s->data=x;s->next=p->next;p->next=s;return1;}插入位置不合理判斷是否申請到新結(jié)點(diǎn)將該結(jié)點(diǎn)插入到ai結(jié)點(diǎn)之前（5）單鏈表的刪除（刪除第i(i>=0)個(gè)結(jié)點(diǎn)）130A12EFa01475130Aai-110CB1800ai150010CB1800pai+11600150010CBs12EFhead………1500s=p->next;p->next=s->next;free(s);{p=p->next;j++;}while(p->next!=NULL&&p->next->next!=NULL&&j<i-1)ListDelete(SLNode*head,inti,DataType*x){SLNode*p,*s;

intj;p=head;j=0;while(p->next!=NULL&&p->next->next!=0&&j<i-1){p=p->next;j++;}

用c語言實(shí)現(xiàn)的單鏈表刪除算法定義變量并初始化搜索表，尋找ai-1結(jié)點(diǎn)if(j!=i-1){printf(“\n

刪除位置不合理!”);return0;}s=p->next;*x=s->data;p->next=p->next->next;free(s);return1;}刪除位置不合理將ai結(jié)點(diǎn)刪除釋放s結(jié)點(diǎn)空間關(guān)于上機(jī)的相關(guān)說明1、實(shí)驗(yàn)報(bào)告不得有雷同，否則按不及格處理；2、函數(shù)自己編寫，函數(shù)名、變量名等自己定義；#include<stdio.h>#defineMAXLEN100typedef

int

datatype;typedef

struct{

datatype

List[MAXLEN];

intnum;}Seqlist;函數(shù)聲明voidmain(){變量定義

printf(“選擇所要進(jìn)行的操作：1:初始化\n2:插入\n3:刪除\n4:輸出\n5:退出\n“)；

scanf(%d”,&sel);

switch(sel){case1:調(diào)用初始化函數(shù);break;case2:調(diào)用插入函數(shù);break;case3:調(diào)用刪除函數(shù);break;case4:調(diào)用輸出函數(shù);break;case5:break;default:給出出錯(cuò)信息，并要求重新輸入｝｝(6)單鏈表的創(chuàng)建

尾接法12EFhead12EFp130Ap*s130Asa0NULL*headNULL130A1475p*s1475sa1NULL1475for(j=0;j<=n-1;j++){if((s=(SLNode*)malloc(sizeof(SLNode)))==NULL)return0;s->data=a[j];s->next=NULL;p->next=s;p=s;}開始初始化單鏈表尾結(jié)點(diǎn)指向新結(jié)點(diǎn)修改尾指針NY初始化尾指針鏈表創(chuàng)建結(jié)束?申請新結(jié)點(diǎn)結(jié)束尾接法創(chuàng)建單鏈表流程圖intCreatL1(SLNode**h,DataType

a[],intn){SLNode*p,*s;

inti,j;

i=ListInitiate(h);if(i==0)return0;p=*h;

for(j=0;j<=n-1;j++){if((s=(SLNode*)malloc(sizeof(SLNode)))==NULL)return0;s->data=a[j];s->next=NULL;p->next=s;p=s;}return1;}12EFh*s130Asa0NULL*hNULL130A*s1475sa1130A1475for(j=0;j<=n-1;j++){if((s=(SLNode*)malloc(sizeof(SLNode)))==NULL)return0;s->data=a[j];s->next=(*h)->next;(*h)->next=s;}(6)單鏈表的創(chuàng)建頭插法開始初始化單鏈表新結(jié)點(diǎn)指向第一個(gè)結(jié)點(diǎn)頭結(jié)點(diǎn)指向新結(jié)點(diǎn)NY鏈表創(chuàng)建結(jié)束?申請新結(jié)點(diǎn)結(jié)束頭接法創(chuàng)建單鏈表流程圖intCreatL2(SLNode**h,DataType

a[],intn){SLNode*s;

inti,j;i=ListInitiate(h);if(i==0)return0;for(j=0;j<=n-1;j++){if((s=(slnodetype*)malloc(sizeof(slnodetype)))==NULL)return0;s->data=a[j];s->next=(*h)->next;(*h)->next=s;}return1;}

2.3.5循環(huán)單鏈表head非空表空表headhead->next==head2.3.6雙向循環(huán)鏈表typedef

structNode{DataTypedata;

structNode*prior,*next;}DLNode;priordatanext要點(diǎn)回顧線性表的鏈?zhǔn)酱鎯Α湵硖卣鳎哼壿嬌舷噜彛锢砩喜灰欢ㄏ噜彛粌?yōu)點(diǎn)：不需預(yù)先確定數(shù)據(jù)元素的最大個(gè)數(shù)；插入、刪除不需移動(dòng)數(shù)據(jù)元素缺點(diǎn)：空間利用率低；算法較復(fù)雜單鏈表結(jié)點(diǎn)datanext數(shù)據(jù)域指針域單鏈表的初始化、插入、刪除、頭插法及尾插法創(chuàng)建單鏈表討論線性表邏輯結(jié)構(gòu)特點(diǎn)是，只有一個(gè)首結(jié)點(diǎn)和尾結(jié)點(diǎn)；除首尾結(jié)點(diǎn)外其他結(jié)點(diǎn)只有一個(gè)直接前驅(qū)和一個(gè)直接后繼。簡言之，線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是一對一（1:1）的。問1：線性表的邏輯結(jié)構(gòu)特點(diǎn)是什么？其順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)的特點(diǎn)是什么？答：

順序存儲時(shí)，相鄰數(shù)據(jù)元素的存放地址也相鄰（邏輯與物理統(tǒng)一）；要求內(nèi)存中可用存儲單元的地址必須是連續(xù)的。鏈?zhǔn)酱鎯r(shí)，相鄰數(shù)據(jù)元素可隨意存放，但所占存儲空間分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針。順序存儲的優(yōu)點(diǎn)是存儲密度大(＝1)，存儲空間利用率高。缺點(diǎn)是插入或刪除元素時(shí)不方便。鏈?zhǔn)酱鎯Φ膬?yōu)點(diǎn)是插入或刪除元素時(shí)很方便，使用靈活。缺點(diǎn)是存儲密度小（<1），存儲空間利用率低。答：問2：順序存儲和鏈?zhǔn)酱鎯Ω饔心男﹥?yōu)缺點(diǎn)？事實(shí)上，鏈表插入、刪除運(yùn)算的快捷是以空間代價(jià)來換取時(shí)間。問3：在什么情況下用順序表比鏈表好？順序表適宜于做查找這樣的靜態(tài)操作；鏈表宜于做插入、刪除這樣的動(dòng)態(tài)操作。若線性表的長度變化不大，且其主要操作是查找，則采用順序表；若線性表的長度變化較大，且其主要操作是插入、刪除操作，則采用鏈表。答：具體要求順序表鏈表基于空間適于線性表長度變化不大，易于事先確定其大小時(shí)采用。適于當(dāng)線性表長度變化大，難以估計(jì)其存儲規(guī)模時(shí)采用。基于時(shí)間由于順序表是一種隨機(jī)存儲結(jié)構(gòu)，當(dāng)線性表的操作主要是查找時(shí)，宜采用。鏈表中對任何位置進(jìn)行插入和刪除都只需修改指針，所以這類操作為主的線性表宜采用鏈表做存儲結(jié)構(gòu)。若插入和刪除主要發(fā)生在表的首尾兩端，則宜采用尾指針表示的單循環(huán)鏈表。應(yīng)用實(shí)例1

刪除順序表la中所有值為x的數(shù)據(jù)元素。設(shè)順序表的數(shù)據(jù)結(jié)構(gòu)定義為：#defineMAX100typedef

int

DataType;typedef

struct{

DataTypeList[MAX];

intnum;/*最后一個(gè)數(shù)據(jù)元素的下標(biāo)*/}SeqList;

voidDeleteSeqList(SeqList*la,DataTypex){intj,k;for(j=0;j<=la->num;j++){if(la->List[j]==x){for(k=j;k<la->num;k++)la->List[k]=la->List[k+1];la->num--;

j--;}}}

應(yīng)用實(shí)例2刪除順序表a中第i(i>=0)個(gè)元素起的k個(gè)元素。#defineMAX100typedef

int

DataType;typedef

struct{

DataTypeList[MAX];

intnum;/*最后一個(gè)數(shù)據(jù)元素的下標(biāo)*/ }SeqList;int

DeleteK(SeqList*a,int

i,intk)

{intj;

if(a->num<0){printf(“順序表已空！\n”);return0;}elseif(i<0||k<0||i+k-1>a->num)return0;else{for(j=i;j<=a->num-k;j++)

a->List[j]=a->List[j+k];a->num=a->num-k;

return1;}

}/*判斷表是否為空*//*判斷刪除位置、個(gè)數(shù)是否合理*//*刪除從第i個(gè)元素開始的k個(gè)元素*/應(yīng)用實(shí)例3在有序順序表中插入值為x的數(shù)據(jù)元素以保持順序表的有序性。#defineMAX100typedef

int

DataType;typedef

struct{

DataTypeList[MAX];

intnum;/*最后一個(gè)數(shù)據(jù)元素的下標(biāo)*/}SeqList;

int

Orderlnsert(SeqList*L,DataTypex){inti;if(L->num==Max-1){printf(“順序表已滿”);return0;}else{for(i=L->num;i>=0&&x<L->List[i];i--)L->List[i+1]=L->List[i];L->List[i+1]=x;L->num++;return1;}}應(yīng)用實(shí)例4實(shí)現(xiàn)單鏈表的就地逆序。設(shè)其頭結(jié)點(diǎn)的指針為head，編寫一個(gè)算法將單鏈表逆置。單鏈表的逆轉(zhuǎn)headpqqa1a2` a3a4a0headheada0headqa0a1a0a1a2a0a1a2a3a4a1a2a3a4a2a3a4a3a4ppheada0a1a2a3a4ppheadvoidreverse(SLNode*head){

SLNode*p,*q;p=head->next;head->next=NULL;while(p!=NULL){q=p;p=p->next;q->next=head->next;head->next=q;}}應(yīng)用實(shí)例5

已知線性表la和lb中的數(shù)據(jù)元素按非遞減有序排列，將la和lb表中的數(shù)據(jù)元素合并為一個(gè)新的線性表lc，lc中的數(shù)據(jù)元素仍按非遞減有序排列，并要求不破壞la和lb表。La=(3,5,8,11)Lb=(2,6,8,9,11,15,20)合并結(jié)果:Lc=(2,3,5,6,8,8,9,11,11,15,20)typedef

struct{elemtype

List[maxlen];

intnum;}qltype;1.順序表結(jié)構(gòu)int

mergeql(qltype

la,qltypelb,qltype*lc){

inti,j,k;if(la.num+1+lb.num+1>maxlen){printf(“\n數(shù)組下界溢出！”);return0;}i=j=k=0;while(i<=la.num&&j<=lb.num){if(la.list[i]<=lb.list[j])

lc->list[k++]=la.list[i++];else

lc->list[k++]=lb.list[j++];}while(i<=la.num)lc->list[k++]=la.list[i++];while(j<=lb.num)lc->list[k++]=lb.list[j++];lc->num=k-1;return1;}typedef

struct

slnode{elemtypedata;

struct

slnode*next;}slnodetype;2.單鏈表結(jié)構(gòu)La3

5

8

11^

Lb2

6

8

11^9

PaPbPaPbPa、Pb用于搜索La和Lb，

Pc指向新鏈表當(dāng)前結(jié)點(diǎn)Lc

…

Pa3

PcPa5

Pc11^Pc2

PbPcPaint

mergesl(slnodetype*la,slnodetype*lb,slnodetype**lc){slnodetype*pa,*pb,*pc;

if(*lc=(slnodetype*)malloc(sizeof(slnodetype)))==NULL){printf(“\n分配內(nèi)存失??！”);return0;}pa=la->next;

pb=lb->next;pc=*lc;

while(pa&&pb){if(pc->next=(slnodetype*)malloc(sizeof(slnodetype)))==NULL){printf(“\n分配內(nèi)存失?。　?;return0;}pc=pc->next;if(pa->data<=pb->data){pc->data=pa->data;pa=pa->next;}else{pc->data=pb->data;

pb=pb->next;}

while(pa){if

pc->next=(slnodetype*)malloc(sizeof(slnodetype)))==NULL)

{printf(“\n分配內(nèi)存失?。　?;return0;}pc=pc->next;pc->data=pa->data;pa=pa->next;}while(pb){if

pc->next=(slnodetype*)malloc(sizeof(slnodetype)))==NULL)

{printf(“\n分配內(nèi)存失?。　?;return0;}pc=pc->next;pc->data=pb->data;

pb=pb->next;}pc->next=NULL;return1;}

思考：1、不用Lc，直接把La表插到Lb表中；或者把Lb表插到La表中，如何編程？2、要求不能有重復(fù)的數(shù)據(jù)元素，如何編程？總結(jié)（1）了解線性表的定義和線性結(jié)構(gòu)的特點(diǎn)；（2）理解線性表的順序存儲和鏈?zhǔn)酱鎯?，理解用?shù)組與單鏈表表示線性表的優(yōu)缺點(diǎn)；（3）掌握線性順序表中數(shù)據(jù)元素的存儲位置的計(jì)算，順序表的插入、刪除等有關(guān)操作；（4）會用單鏈表編寫插入、刪除等有關(guān)算法。作業(yè)：P562-14(單鏈表）

2-172-18int

ListInitiate(SLNode**head){if((*head=(SLNode*)malloc(sizeof(SLNode)))==NULL)return0;(*head)->next=NULL;return1;}（1）初始化12EFhead*headNULL12EF第三章堆棧和隊(duì)列Chapter3StackandQueue3.1堆棧（Stack）

3.2

隊(duì)列（Queue）1.定義2.邏輯結(jié)構(gòu)3.存儲結(jié)構(gòu)4.運(yùn)算規(guī)則5.實(shí)現(xiàn)方式1.定義2.邏輯結(jié)構(gòu)3.存儲結(jié)構(gòu)4.運(yùn)算規(guī)則5.實(shí)現(xiàn)方式本章內(nèi)容3.1堆棧一、堆棧的基本概念定義

堆棧是限定只能在表的一端進(jìn)行插入和刪除的線性表。在表中允許插入和刪除的一端叫做棧頂(top)；表的另一端則叫做棧底(base)。出?；蛲藯Ｈ霔；蜻M(jìn)棧a0a1…an-2an-1basetopLastInFirstOut一般線性表邏輯結(jié)構(gòu)：一對一存儲結(jié)構(gòu)：順序表、鏈表運(yùn)算規(guī)則：隨機(jī)存取堆棧邏輯結(jié)構(gòu)：一對一存儲結(jié)構(gòu)：順序棧、鏈棧運(yùn)算規(guī)則：后進(jìn)先出(LIFO)*堆棧與一般線性表的比較*例

一個(gè)棧的輸入序列為123，若在入棧的過程中允許出棧，則可能得到的出棧序列是什么？答：可以通過窮舉所有可能性來求解：①1入1出，2入2出，3入3出，即123；②1入1出，2、3入，3、2出，即132；③1、2入，2出，3入3出，1出即231；④1、2入，2、1出，3入3出，即213；⑤1、2、3入，3、2、1出，即321；合計(jì)有5種可能性。*不可能產(chǎn)生的輸出序列：3121、初始化2、進(jìn)棧3、退棧4、取棧頂元素5、判棧是否非空二、堆棧的操作三、棧的順序表示和實(shí)現(xiàn)——順序堆棧1.順序棧的存儲結(jié)構(gòu)出棧或退棧入?；蜻M(jìn)棧basetopa0a1a3a4a5maxlen-1543210順序棧的定義typedef

int

DataType;#definemaxlen100/*順序堆棧數(shù)組最大存儲單元個(gè)數(shù)*/typedef

struct

/*順序棧定義*/{DataType

stack[maxlen];/*順序堆棧存放數(shù)據(jù)元素的數(shù)組*/

inttop;/*順序堆棧數(shù)組的當(dāng)前棧頂位置*/}seqstack;

/*結(jié)構(gòu)類型名*/2.順序堆棧的操作實(shí)現(xiàn)toptopa0a1a2toptopmaxlen個(gè)