stChinaNormalUniversity

講算機(jī)科學(xué)技術(shù)系

濟(jì)算機(jī)醫(yī)用赫

頓韭僦羹縷看讖

第一部分、專業(yè)課終極筆記........................................................3

一、本科生筆記..............................................................3

二、《c程序設(shè)計(jì)》考研總結(jié)筆記

三、老師講義（附錄電子版）................................................129

四、整理過的筆記..........................................................129

第二部分：專業(yè)課復(fù)習(xí)方法......................................................155

第三部分：復(fù)試詳細(xì)情況介紹....................................................155

第四部分：本科生期末考試試卷，平時(shí)作業(yè)題目...................................171

-、數(shù)據(jù)結(jié)構(gòu)期末試題及其答案...............................................

二、期中考試................................................................

三、平時(shí)作業(yè).................................................................

第一部分、專業(yè)課筆記

一、專業(yè)課筆記—《C程序設(shè)計(jì)》

關(guān)于c語言的筆記分兩部分：第一部分是關(guān)于基礎(chǔ)知識的，第二部分是一些考生必須掌握的

程序。

第一部分c語言基礎(chǔ)知識

在c考試中有c語言選擇題，主要考察基礎(chǔ)知識，考生只需掌握以下幾個(gè)知識點(diǎn)就可以了。

1、指針知識總結(jié)：

Int*pp為指向整形數(shù)據(jù)的指針變量

Int*p[n]指針數(shù)組，它由N個(gè)指向整形數(shù)據(jù)的指針元素組成，通常用字符數(shù)組

Int(*p)[n]P為指向含N個(gè)元素的一維數(shù)組的指針變量，通常用于二維數(shù)組a[][]

Int*p()P帶回一個(gè)指針的函數(shù)，該指針指向整性數(shù)據(jù)。

Int(*p)()P為指向函數(shù)的指針，返回以整形值。

Int**pP為指針變量，指向一個(gè)指向整形數(shù)據(jù)的指針變量。

至于每個(gè)指針例子考生可參看書上第十章。這個(gè)問難一定要掌握透徹，每年都會(huì)考這個(gè)

知識點(diǎn)。

2、常見文件的打開方式：

(1)urM只讀，為輸入打開一個(gè)文本文件。

(2)“w”只寫，為輸出打開一個(gè)文本文件

(3)“r+”/“w+”為讀寫打開/新建一個(gè)文本文檔。

3關(guān)于文件的一些命令總結(jié)：

(1)打開文件：

If((fp=fopen("student,dat","r+"))—NULL)

{printf("can'topenthisfile\n");

Exit(0);}

(2)文件打開:FILE*P；

fp=fopen(文件名，使用方式)；

關(guān)閉文件：fp=fclose(文件名，使用方式)；

(3)把一個(gè)字符寫到磁盤文件中:fputc(ch,fp);

把一個(gè)字符讀入磁盤文件中：fgetc(fp);

(4)fread(buffer,size,count,fp)讀入數(shù)據(jù)

fwrite(buffer,size,count,fp)輸出數(shù)據(jù)

(5)fwrite(文件指針，格式字符串，輸出表列)

Fscanf(文件指針，格式字符串，輸入表列)

它們的讀寫對象是文件磁盤

(6)fgets(str,n,fp)從fp中讀入字符串到str中

fputs(str,n,fp)向指定文件中輸出字符串

(7)fseek(文件指針,位置偏移量，起始位)

'O'表示開始點(diǎn)'1'表示當(dāng)前'2'表示末尾

其他的知識點(diǎn)比較瑣碎，考生需要把書上第7、10章的內(nèi)容仔細(xì)的看一邊，又一些細(xì)節(jié)

的知識在考試的選擇題中經(jīng)常出現(xiàn)，不過就一兩道。

第二部分C程序源代碼

1、起泡排序

/*fromsmalltobig*/

main()

{inta[ll];

inti,j,t;

printf("input10mnumbers:\nz/);

for(i=l;i<ll;i++)

scanf&a[i]);

printf("\n");

for(j=l;j<=9;j++)

for(i=l;i<=10-j;i++)

if(a[i]>a[i+l])

{t=a[i];a[i]=a[i+l];a[i+l]=t;}

printf("printthesortednumber:\nz，);

for(i=l;i<ll;i++)

printf("%5d",a[i]);

)

2、選擇排序

\main()

{inta[10];

inti,j,temp;

printf(z，input10numbers:\nz，);

for(i=0;i<10;i++)

scanfC%dv,&a[i]);

printf('\n");

for(i=0;i<9;i++)

for(j=i+l;j<10;j++)

if(a[i]>a[j])

{temp=a[i];

a[i]=a[j];

a[j]=temp;}

printf("\n");

for(i=0;i<10;i++)

printf("%3d”,a[i]);

3、插入排序

mainO

{inti,j,a[ll];

printf("input10numbers:\nz，);

for(i=l;i<ll;i++)

scanf(線d〃，&a[i]);

for(i=2;i<ll;i++)

{a[0]=a[i];

j=i-l；

while(a[0]>a[j])

a[j+l]=a[j—];

a[j+l]=a[0];

)

for(i=l;i<ll;i++)

printf(〃％3d〃，a[i]);

4、判斷是不是閏年

main()

{intyear;

printf("inputayear:");

scanf(〃%d〃,&year);

if((year%4==0&&year%100!=0)||year%400==0)

printf(，，it，saleapyear");

else

printf(/，it，snotaleapyear");

)

5、排序和折半查找的綜合：

#include<stdio.h>

#defineN10

voidinput(intnum[],charname[N][8])

{inti;

for(i=0;i<N;i++)

{printfC\ninputNO.:〃)；

scanf&num[i]);

printfC?\ninputname:");

getchar();

gets(name[i]);

voidsort(intnum[],charname[N][8])

{inti,j,min,tempi;

chartemp2[8];

for(i=0;i<N;i++)

{min=i;

for(j=i;j<N;j++)

if(num[min]>num[j])

min=j;

templ=num[i];

strcpy(temp2,name[i]);

num[i]=num[min];

strcpy(name[i],name[min]);

num[min]二tempi;

strcpy(name[min],temp2);

}

printf(z，\nresult:\n，z);

for(i=0;i<N;i++)

printf(，，\n%5d%10s，z,num[i],name[i]);

)

voidsearch(intn,intnum[],charname[N][8])

{intbott=N-l,top=0,mid,loca=0,sign=l;

if(n<num[0]||n>num[N-l])

loca="l;

while(sign==l&&top<=bott)

{mid=(top+bott)/2;

if(n二二num[mid])

{loca=mid;

printf(z，N0.%d,hisnameis%s\n，z,n,nametloca]);

sign=-l;

}

elseif(n<num[mid])

bott=mid-l;

elsetop=mid+l;

}

if(sign==l||loca==-l)

printf(z/cannotfind%d\n〃,n);

)

main()

{intnum[N],number,flag=l,c,n;

charname[N][8];

input(num,name);

sort(num,name);

while(flag)

{printf(，z\ninputnumbertolookfor:，z);

scanf&number);

search(number,num,name);

printfC\nCONTINUEornot(Y/N)?，z);

getchar();

c=getchar();

if(c==，N?||c==，n')

flag=0;

)

)

6、在數(shù)組中插入一個(gè)數(shù)：

(第一種方法)

main()

{inta[10]={l,5,7,9,10,13,45,59,100};

intn,i,j,tempi,temp2;

printf(，z\nthearrayis:\n〃)；

for(i=0;i<9;i++)

printf(〃%5d〃,a[i]);

printf("inputtheinsertednumber:");

scanf(〃%d〃,&n);

if(n>a[8])

a[9]=n;

else

{for(i=0;i<9;i++)

{if(a[i]>n)

{templ=a[i];

a[i]=n;

for(j=i+l;j<10;j++)

{temp2=a[j];

a[j]=templ;

templ=temp2;

)

break;

printf(〃\nthenewarrayis:\n〃)；

for(i=0;i<10;i++)

printf(〃％5d〃，a[i]);

)

(第二種方法)

Acharusort*/

mainO

{inti,j,n,a[5]={l,4,6,7};

printf(〃\ninputanumber:\n/，);

scanf(〃％d〃，&n);

if(n>a[3])

a[4]=n;

else

(

i=0;

while(n>a[i])i++;

for(j=3;j>=i;j—)

a[j+l]=a[j];

a[j+l]=n;}

printf(〃\n〃)；

printf(，zthesortedarrayis〃)；

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

printf(〃％5d〃，a[i]);

)

7、鏈表的基本操作：

#defineNULL0

#defineLENsizeof(structstudent)

structstudent

{longnum;

floatscore;

structstudent*next;

)；

intn;

structstudent*creat(void)

{structstudent*head,*pl,*p2;

n=0;

pl=p2=(structstudent*)malloc(LEN);

scanf%f〃,&pl->num,&pl->score);

head=NULL;

while(pl->num!=0)

{n=n+l;

if(n==l)head=pl;

elsep2->next=pl;

p2=pl;

pl=(structstudent*)malloc(LEN);

scanf%f〃,&pl->num,&pl->score);

)

p2->next=NULL;

return(head);

voidprint(structstudent*head)

{structstudent*p;

printf(z，\nNow,these%drecordsare:\n，z,n);

p=head;

if(head!=NULL)

do

{printf(z，%ld%5.lf\n〃,p->num,p->score);

p=p->next;

}while(p!=NULL);

)

structstudent*del(structstudent*head,longnum)

{structstudent*pl,*p2;

if(head==NULL)

{printf(zz\nlistnull!\n，/);gotoend;}

pl=head;

while(num!=pl->num&&p1->next!=NULL)

{p2=pl;

pl=pl->next;

)

if(num==pl->num)

{if(pl==head)head=pl->next;

elsep2->next=pl->next;

printf("delete%ld\n〃，num);

n=n-l;

)

elseprintf(z，%ldnotbeenfound!\nz，,num);

end:

return(head);

)

structstudent*insert(structstudent*head,structstudent*stud)

{structstudent*p0,*pl,*p2;

pl二head;

pO=stud;

if(head==NULL)

{head=pO;

pO->next=NULL;

)

else

while(pO->num>pl->num&&pl->next!=NULL)

{p2=pl;pl=pl->next;

}

if(pO->num<=pl->num)

{if(head==p1)head=pO;

elsep2->next=p0;

pO->next=pl;

)

else

{pl->next=pO;

pO->next=NULL;

)

n=n+l;

return(head);

}

mainO

{structstudent*head,stu;

longdel_num;

printf(，z\ninputrecords:\n，z);

head=creat();

print(head);

printf("inputthedeletednumber:，z);

scanf&del_num);

head=del(head,del_num);

print(head);

printf(z/\ninputtheinsertedrecord:");

scanf(，z%ld,〃，&stu.num,&stu.score);

head=insert(head,&stu);

print(head);

)

8、文件的基本操作：

ttdefineNULL0

#include<stdio.h>

mainO

{FILE*fp;

charch,filename[10];

scanf(〃％s〃，filename);

if((fp=fopen(filename,?))==NULL)

{printf(z，cannotopenthisfile");

exit(0);

)

ch=getchar0;

while(ch!=，#')

{fputc(ch,fp);

ch=getchar();

)

fclose(fp);

)

9、判斷是不是素?cái)?shù)〉

#include<math.h>

mainO

{intx,i;

printf("inputanumber:");

scanf(〃%d〃,&x);

printf(〃\n〃)；

for(i=2;i<sqrt(x);i++)

if(x%i==0)

{printf(，znotasushu");

break;}

if(i>=sqrt(x))

printf(，，it，sasushu〃)；

}

10、指針的應(yīng)用

voidaverage(float*p,intn)

{float*p_end;

floatsum=0,aver;

p_end=p+n-l;

for(;p<=p_end;p++)

sum=sum+(*p);

aver=sum/n;

printf("average=%5.2f\n〃，aver);

}

voidsearch(float(*p)[4],intn)

{inti;

printf(/zthescoreofNO.%dare:\n，z,n);

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

printf(z，%6.2f〃，*(*(p+n)+i));

)

voidsearchfail(float(*p)[4],intn)

{inti,j,flag;

for(j=0;j<n;j++)

{flag=0;

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

if(*(*(p+j)+i)<60)

flag=l;

if(flag==l)

{printf(z，N0.%dfails,hisscoresare:\nz，,j+1);

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

printff%5.If",*(*(p+j)+i));

printf(〃\n〃)；

}

mainO

{floatscore[3][4]={{65,67,70,60},{48,87,90,81},{90,99,100,98}};

average(*score,12);

search(score,2);

searchfail(score,3);

}

11、對文件方面的題，考生只需把05年的題弄明白就可以了，一般文件的題

與排序算法相結(jié)合。請看下面例題：

現(xiàn)有一個(gè)記錄學(xué)生成績的數(shù)據(jù)文件student.dat,其中人數(shù)不清，其文件數(shù)據(jù)結(jié)構(gòu)如下所

示，每位學(xué)生參加8門課程考試，請將其中有三門及三門以上考試成績不及格的學(xué)生信息寫

入新數(shù)據(jù)文件fail,date文件結(jié)構(gòu)同student.dat,同時(shí)在student.dat中刪除該條記錄。

Structstudent

{intnum;

Charname[20];

Intscore[8];

Intmark;

)

答題要點(diǎn)：

ttdefineM1000

MainO

{FILE*fpl,*fp2;

Structstudentstu[M];

Inti,j,k,count,m=0,n;

If((fpl=fopen("stud6nt.dat"，“r+”))二二NULL)

{printf(<<can,topenthisfile\n,,);

Exit(0);}

If((fp2=fopen("fail,dat“，"w"))==NULL)

{printf("can'topenthisfile'n");

Exit(0);}

i=0;

while(fread(&stu[i],sizeof(structstudent),1,fp))

i++；

count=I;

for(i=0;i<count;i++)

{for(j=0;j<8;j++)

If(stu[i].score[j]<60)m++;

If(m>=3)mark=0;

Elsemark=l;}

For(i=0;i<count;i++)

If(stu[i].mark==0)

{fwrite(&stu[i],sizeof(structstudent),1,fp2);

For(j=I;j<count-l;j++)

{stu[j].num=stu[j+1].num;

strcpy(stu[j].name,stu[j+1].name);

for(n=0;n<8;n++)

stu[j].score[n]=stu[j+1].score[n];

stu[j].mark二stu[j+1].mark;}

Elsefwrite(&stu[i].sizeof(structstudentl),l,fpl);}

二、《數(shù)據(jù)結(jié)構(gòu)教程》本科生筆記

第一章線性表

線性表是最常用、最簡單的一種線性結(jié)構(gòu)。因?yàn)樗膽?yīng)用范圍十分廣泛，所以有必要

在這里作較詳細(xì)的介紹。

1.1線性表及其基本運(yùn)算

1.1.1線性表

線性表是具有相同類型的n個(gè)數(shù)據(jù)元素kok,…Q的有限序列，記為(ko,k|,…kQ。元

素個(gè)數(shù)n稱為線性表的長度，稱長度為零的線性表為空的線性表(簡稱為空表)。當(dāng)nel

時(shí)，ko是最前面的一個(gè)元素，kz是最后一個(gè)元素，線性表中數(shù)據(jù)元素的相對位置是確定的。

因?yàn)榫€性表的數(shù)據(jù)元素構(gòu)成一個(gè)序列，在序列中，ki排在ki+i前面，我們稱％是ki+i的前趨

元素；ki+1排在ki后面，我們稱ki+I是ki的后繼元素。ko沒有前趨元素，心」沒有后繼元素;

當(dāng)n22時(shí)，ko有后繼元素k"％」有前趨元素％⑵當(dāng)n》3時(shí)，k,(0<i<n-l)既有前趨

元素kz，也有后繼元素ki+i。

對于給定的線性表(koki,???1),它的數(shù)據(jù)元素集合為{kok,…而數(shù)據(jù)元素之間

的關(guān)系由數(shù)據(jù)元素出現(xiàn)在線性表中的位置所確定。我們可用數(shù)據(jù)元素3ki+i構(gòu)成的偶對表

示數(shù)據(jù)元素k,和ki+i所存在的這種關(guān)系。因此，可用數(shù)據(jù)元素的偶對的集合表示線性表中數(shù)

據(jù)元素之間的關(guān)系，這種關(guān)系記為{(ki，ki+l)|0Wi<n-l)?對于相同數(shù)據(jù)元素集合的兩個(gè)

線性表，如果數(shù)據(jù)元素出現(xiàn)在表中的次序不相同，那么著兩個(gè)線性表是不想同的。

線性表中的數(shù)據(jù)元素也稱為結(jié)點(diǎn)，或稱為記錄,它可以是一個(gè)整數(shù)、一個(gè)實(shí)數(shù)、一個(gè)字

符或一個(gè)字符串；也可以由若干個(gè)數(shù)據(jù)項(xiàng)組成，其中每個(gè)數(shù)據(jù)項(xiàng)可以是一般數(shù)據(jù)類型，也可

以是構(gòu)造類型。數(shù)據(jù)項(xiàng)也稱為字段,或稱為域。

比如，表1.1.1的線性表用于記錄最近一周每天的平均氣溫。每個(gè)結(jié)點(diǎn)有兩個(gè)字段：一

個(gè)是星期，用于指明是星期幾，它的數(shù)據(jù)類型是由三個(gè)字符組成的字符串；另一個(gè)是溫度，

用于指明平均氣溫，它的數(shù)據(jù)類型是實(shí)數(shù)。

表1.1.1一周內(nèi)眉頭的平均氣溫記錄表

星期MonTueWedThuFriSatSun

溫度15.516.016.515.715.016.116.4

再比如，表1.1.2也是一個(gè)線性表，它是一個(gè)企業(yè)的職工工資表。改表由職工號、姓名、

性別、年齡和工資等五個(gè)字段所組成，其中職工號、年齡的數(shù)據(jù)類型是整數(shù)；姓名和性別是

字符串；工資是實(shí)數(shù)。

表1.1.2職工工資表

職工號姓名性別年齡工資

001Wangmale35160.50

002Caimale32150.00

003Zhangfemale28130.00

?,

線性表中的結(jié)點(diǎn)可由若干個(gè)字段組成，我們稱能唯一標(biāo)識結(jié)點(diǎn)的字段為關(guān)鍵字，或簡稱

為鍵。如表1.1.1的線性表的關(guān)鍵字是星期，而表1.1.2的線性表的關(guān)鍵字是職工號。在本書

中，為了討論方便，往往只考慮結(jié)點(diǎn)的關(guān)鍵字，而忽略其他字段。這樣的假設(shè)也不失一般性,

只要知道存放某結(jié)點(diǎn)的存貯單元，就能取到該結(jié)點(diǎn)的其他字段上的值。

1.1.2線性表的基本運(yùn)算

上面介紹了線性表的基本概念，下面介紹線性表的一些基本運(yùn)算.

線性表結(jié)構(gòu)可以動(dòng)態(tài)地增長或收縮，在線性表的任何位置上可以訪問、插入或刪除結(jié)點(diǎn)。

我們把線性表常用的運(yùn)算分成兒類，每類包括若干種運(yùn)算。

1.查找

(1)查找線性表的第i(OWi<n-l)個(gè)結(jié)點(diǎn)。

(2)在線性表中查找值為x的結(jié)點(diǎn)。

2.插入

(1)把新結(jié)點(diǎn)插在線性表的第i(OWiWn-1)個(gè)位置上。

(2)把新結(jié)點(diǎn)插在值為x的結(jié)點(diǎn)的前面(或后面)

3.刪除

(1)在線性表中刪除第i(OWiWn-1)個(gè)結(jié)點(diǎn)。

(2)在線性表中刪除值為x的結(jié)點(diǎn)。

4.其他運(yùn)算

(1)統(tǒng)計(jì)線性表中結(jié)點(diǎn)的個(gè)數(shù)。

(2)打印線性表中所有結(jié)點(diǎn)。

(3)復(fù)制一份線性表。

(4)把一個(gè)線性表拆成幾個(gè)線性表。

(5)把幾個(gè)線性表合并成一個(gè)線性表。

(6)根據(jù)結(jié)點(diǎn)的某個(gè)字段值按升序(或降序)重新排列線性表。

1.2順序存貯的線性表

在計(jì)算機(jī)內(nèi)，可以利用不同的存貯方式表示線性表，其中最常用、最簡單的方式就是順

序存貯。所謂線性表的順序存貯，就是用一組連續(xù)的存貯單元一次存貯線性表中的結(jié)點(diǎn)。

因?yàn)榫€性表中所有結(jié)點(diǎn)的數(shù)據(jù)類型是相同的，所以每個(gè)結(jié)點(diǎn)在存貯器中占用大小相同的

空間。如果每個(gè)結(jié)點(diǎn)占用計(jì)算機(jī)中按機(jī)器字編址或按字節(jié)編址的S個(gè)地址的存貯單元，并假

設(shè)存放結(jié)點(diǎn)ki(OWiWn-1)的開始地址為aki，那么結(jié)點(diǎn)ki的地址aki可用整數(shù)i,以及地

址計(jì)算公式

aki=ako+i*s

計(jì)算出來。

對于順序存貯的線性表，因?yàn)榭梢岳玫刂酚?jì)算公式直接計(jì)算出k”所以存取第i(0

WiWn-1)個(gè)結(jié)點(diǎn)特別方便。

如果用C語言的數(shù)組表示線性表(k0,ki,-kn.,),我們可使用如下的說明：

#defineMAXSIZE100

intlist|MAXSIZE];

intn;

其中MAXSIZE是數(shù)組list中元素個(gè)數(shù)的最大值，n是線性表中當(dāng)前結(jié)點(diǎn)個(gè)數(shù)。這里假設(shè)線

性表的結(jié)點(diǎn)值是整數(shù)，所以數(shù)組元素也是整數(shù)，當(dāng)然可根據(jù)需要取其他類型。線性表的結(jié)點(diǎn)

ko,k|,…k?i依次存放在數(shù)組元素…中。這樣，存放線性表各個(gè)結(jié)點(diǎn)的地

址與數(shù)組list各個(gè)下表變量的地址有如下的對應(yīng)關(guān)系：

akoaki.....akiiaki.....akn-i

ttttt

&list[O]&list[l]&list[i-l]&list[i]&list[n-l]

有了上述的對應(yīng)關(guān)系，可得到下面計(jì)算ki的地址的公式，這里我們假設(shè)s=sizeof(inl)：

因aki=&list[i]

而&list[i]=&list[O]+i*s

故aki=&list[O]+i*s

1.2.1線性表的插入

這里所講的插入是在具有n個(gè)結(jié)點(diǎn)的線性表中，把新結(jié)點(diǎn)插在線性表的第i(0WiWn-1)

個(gè)位置上，使原來長度為n的線性表變成長度為(n+1)的線性表。在把新結(jié)點(diǎn)放進(jìn)線性表

前，必須把原來位置號(序號)為(n-1)至位置號為i的結(jié)點(diǎn)依次往后移一個(gè)位置，然后

把新結(jié)點(diǎn)放在第i個(gè)位置上，此時(shí)宮移動(dòng)(n-i)個(gè)結(jié)點(diǎn)。對于i=n,只要把新結(jié)點(diǎn)插在第n

個(gè)位置上，此時(shí)無需移動(dòng)結(jié)點(diǎn)。

下面用一個(gè)C函數(shù)sq_insert()實(shí)現(xiàn)上述的插入算法。此函數(shù)在具有n個(gè)結(jié)點(diǎn)的線性表

list中，把值為x的結(jié)點(diǎn)插入在第i(0WiWn-1)個(gè)位置上。若插入位置i不在可以插入的

位置上(即<0或i>n),則返回1；若戶\1人*5比￡(即線性表已滿)，此時(shí)list數(shù)組沒有存

貯單元存放新結(jié)點(diǎn)，則返回2；若插入成功，則返回0。在函數(shù)的參數(shù)中，有一個(gè)指針變量

p_n,在調(diào)用時(shí)，把存放線性表的當(dāng)前結(jié)點(diǎn)個(gè)數(shù)的變量n的地址賦給指針變量p_n,以此來

實(shí)現(xiàn)插入后線性表長度n增加L

intsq_insert(list,p_n,i,x)

intlist[],x；

int*p_n,i;

{intj；

if(i<O||i>*p_n)

return(l);

if(*p_n==MAXSIZE)

return(2);

for(j=*p_n;j>i;j-)

list[j]=list[j-l];

list[i]=x;

(*p_n)++;

return(O);

對于存放在數(shù)組list中的、具有n個(gè)結(jié)點(diǎn)的線性表，為了把值為x的結(jié)點(diǎn)插在線性表第

i(OWi^n-1)個(gè)位置上，可用如下的調(diào)用語句：

k=sq_insert(list,&n,i,x)；

在具有n個(gè)結(jié)點(diǎn)的線性表中，插入一個(gè)新結(jié)點(diǎn)時(shí)，其執(zhí)行時(shí)間主要花費(fèi)在移動(dòng)結(jié)點(diǎn)的

循環(huán)上。假設(shè)把新結(jié)點(diǎn)插在第i(OWiWn-1)個(gè)位置上的概率為p”各個(gè)R應(yīng)滿足約束條

n-\

件2口行。因?yàn)榘岩粋€(gè)新結(jié)點(diǎn)插在第i個(gè)位置上需移動(dòng)(n-i)個(gè)結(jié)點(diǎn)，所以移動(dòng)結(jié)點(diǎn)的平

i=0

均次數(shù)為

7J-1

￡-i)

i=0

如果線性表中每個(gè)可插入位置的插入概率相同，即有

1

PO=Pl="=Pn-產(chǎn)----

n+\

1.2.2線性表的刪除

這里所講的刪除是在具有n個(gè)結(jié)點(diǎn)的線性表中刪除第i(0Wi<n-l)個(gè)位置上的結(jié)點(diǎn)，

使原來長度為n的線性表變成長度為(n-1)的線性表.刪除時(shí),要把位置號為(i+1)至位置號為

(n-1)的結(jié)點(diǎn)都依次向前移動(dòng)一個(gè)位置,此時(shí)共需移動(dòng)(n-i-1)個(gè)結(jié)點(diǎn).

下面用一個(gè)C函數(shù)sq_delete()實(shí)現(xiàn)上述的刪除算法.此函數(shù)在具有n個(gè)結(jié)點(diǎn)的線性表

list中,刪除第i(OWiWn-l)個(gè)位置上的結(jié)點(diǎn).若刪除的結(jié)點(diǎn)不在可刪除的位置上(即i<0活i

》n),則返回1;若刪除成功,則返回0.在函數(shù)的參數(shù)中,有一個(gè)指針變量p_n,在調(diào)用時(shí),把存

放線性表當(dāng)前結(jié)點(diǎn)個(gè)數(shù)的變量n的地址賦給指針變量p_n,以此來實(shí)現(xiàn)刪除后線性表的長度n

減少1.

intsq_delete(list,p_n,i)

intlist[];

int*p_n,i;

intj;

if(i<0||i>=*p_n)return(1);

for(j=i+l;j<*p_n;j++)

list[j-l]=list[j];

(*p_n)—;

return(0);

)

調(diào)用時(shí)，可使用如下的語句：

k=sq_delete(list,&n,i);

在具有n個(gè)結(jié)點(diǎn)的線性表中，刪除一個(gè)結(jié)點(diǎn)所需的執(zhí)行時(shí)間主要花費(fèi)在移動(dòng)結(jié)點(diǎn)

的循環(huán)上.假設(shè)刪除第i(OWiWn-l)個(gè)位置上的結(jié)點(diǎn)的概率為pi,每個(gè)口應(yīng)滿足約束條件

gpi=l.因?yàn)閯h除第i(OWiWn-l)位置上的結(jié)點(diǎn)需移動(dòng)(n-i-1)個(gè)結(jié)點(diǎn)，所以移動(dòng)結(jié)點(diǎn)的平

/=0

均次數(shù)為

Zp，("iT)

i=0

如果假設(shè)刪除線性表任何一個(gè)結(jié)點(diǎn)的概率相同，即有

1

pO=p|h"=pn.l=------

〃+1

那么上面的和式可改寫為

1?一!1_〃--1?〃

一一

o~n2-~2

上式表明，在順序存貯的線性表中，刪除一個(gè)結(jié)點(diǎn)，平均大約需要移動(dòng)一半結(jié)點(diǎn)。當(dāng)線性表

的結(jié)點(diǎn)很多，且每個(gè)結(jié)點(diǎn)的數(shù)據(jù)量相當(dāng)大時(shí)，花費(fèi)在移動(dòng)結(jié)點(diǎn)上的執(zhí)行時(shí)間就會(huì)很長。

1.2.3用順序存貯的線性表表示多項(xiàng)式

一般代數(shù)多項(xiàng)式可寫成

ee>,

A(x)=amx",++…+qx"+aQx

其中每個(gè)%(OWiWm)是A(x)的非零系數(shù)；次數(shù)q(OWiWm)是遞減的，即e?>em^>->e{>e0

我們可用包含coef和exp兩個(gè)字段的結(jié)點(diǎn)表示多項(xiàng)式的非零項(xiàng),其中coef給出系數(shù),exp

給出次數(shù).這樣,可用數(shù)組poly[MAXN]表示多項(xiàng)式.因此,可使用如下的說明：

ftdefineMAXN100

typedefstructterm

{

floatcoef;

intexp;

}TERM;

TERMpoly[MAXN];

其中MAXN是數(shù)組poly可存放結(jié)點(diǎn)的最大個(gè)數(shù).有時(shí),我們可把MAXN取得適當(dāng)大,使得多個(gè)多項(xiàng)

式可共享數(shù)組poly。

例如，對于下面兩個(gè)多項(xiàng)式：

60502510

A(X)=8X+6X+4X+2X+1

B(X)=7X60-6X50+3X20

它們在數(shù)組poly中的存貯情況如圖1.2.1所示。

0123456789???MAXN-1

coef864217-63.??

exp605025100605020???

ahatbhbtfree

圖1.2.1多項(xiàng)式的存貯

我們使用了指效ah和bh,它們分別給出A(x)和B(x)的第一項(xiàng)在數(shù)組中的存放位置,而指

針at和bt分別給出A(x)和B(x)的最后一項(xiàng)在數(shù)組中的存放位置,取free=9;

這里順便指出一點(diǎn),ah,at,bh,bt及free等,它們其實(shí)不是指針,只是--種游標(biāo).這是因?yàn)?/p>

存放在ah,at,bh,bt及free內(nèi)的不是數(shù)組元素在存貯器中的地址,而是數(shù)組元素的下標(biāo)值，但

由于使用上的習(xí)慣,我們?nèi)匀环Q它們?yōu)橹羔?希望讀者加以區(qū)別.

上面介紹如果用數(shù)組存放多項(xiàng)式的方法,下面我們討論如何用C函數(shù)首先多項(xiàng)式相加的

算法.在下面的程序中，函數(shù)polyadd()首先C(x)=A(x)+B(x)的運(yùn)算;而函數(shù)append()把系數(shù)c

和次數(shù)e構(gòu)成的項(xiàng)存放到指針free所指出的位置上,成為結(jié)果多項(xiàng)式的一個(gè)項(xiàng)，同時(shí)free加1,

為下次添加結(jié)點(diǎn)但提供存放位置.下面給出C語言的說明及實(shí)現(xiàn)運(yùn)算的函數(shù).

#defineMAXN100

typedefstruct

(

intcoef;

intexp;

}TERM;

TERMpoly[MAXN];

intah,at,bh,bt,ch,ct,free;

intappend(c,e)

intc,e;

(

if(free)二MAXN)return(1);

poly[free].coef=c;

poly[free++].exp=e;

return(0);

)

intpoiy_add(ah,at,bh,bt,p_ch,p_ct)

intah,at,bh,bt;

int*p_ch,*p_ct;

(

intp,q,pe,qe;

intc;

charch;

p=ah;

q=bh;

*p_ch=free;

while(p<=at&&q<=bt)

{

pe=poly[p].exp;

qe=poly[q].exp;

if(pe==qe)ch二'=';

elseif(pe<qe)ch='〈'；

elsech='>';

switch(ch)

(

case'=，:

c=poly[p].coef+poly[q].coef;

if(c)

if(append(c,pe))

return(1);

P++；

q++;

break;

case':

if(append(poly[q].coef,qe))

return(1);

q++；

break;

case'>’:

if(append(poly[p].coef,pe))

return(1);

P++；

break;

)

)

while(p<=at)

(

if(append(poly[p].coef,poly.[p].exp))

return(1);

p++；

)

while(q<=bt)

(

if(append(poly[p].coef,polytq].exp))

return(1);

q++；

)

*p_ct=free-l;

return(0);

)

可用如下的調(diào)用語句執(zhí)行A(x)和B(x)兩個(gè)多項(xiàng)式的相加：

if(polyadd(ah,at,bh,bt,&ch,&ct))

printf("ERROR\n");

如果打印出ERROR,那么說明數(shù)組poly不夠用；如果沒有打印出ERROR,但調(diào)用后出現(xiàn)ct<ch,那

么說明相加后得到一個(gè)零多項(xiàng)式.

現(xiàn)在分析polyadd()的執(zhí)行時(shí)間.首先應(yīng)指出,執(zhí)行函數(shù)append。的時(shí)間是0(1).在

polyadd()中,執(zhí)行三個(gè)循環(huán)之外的幾個(gè)語句的時(shí)間也是0(1).所以,執(zhí)行時(shí)間主要花費(fèi)在三

個(gè)循環(huán)上.設(shè)A(x)和B(x)非零項(xiàng)的個(gè)數(shù)分別為m和n,對于第一個(gè)循環(huán)，當(dāng)A(x)和B(x)的各項(xiàng)的

次數(shù)都不想同時(shí),執(zhí)行循環(huán)的次數(shù)最多,共執(zhí)行(m+n)次,故其執(zhí)行時(shí)間最多為0(m+n);第二和

第三個(gè)循環(huán)最多分別執(zhí)行m次和n次，故其執(zhí)行時(shí)間最多分別為0(m)和0(n).這樣,執(zhí)行

po1yadd()的時(shí)間為0(1)+0(m+n)+0(m)+0(n)=0(m+n).

1.3順序存貯的棧和隊(duì)列

棧和隊(duì)列都是特殊的線性表。這兩種結(jié)構(gòu)比一般的線性表簡單，但非常有用，所以有

必要對它們進(jìn)行仔細(xì)討論。

1.3.1棧及其基本運(yùn)算

棧是只允許在一端進(jìn)行插入和刪除的線性表。稱允許插入和刪除的一端為棧頂；稱不

允許插入和刪除的一端為援匹若給定棧S=(s。,Si,…,sQ,則s。是棧底結(jié)點(diǎn),S,T是棧頂結(jié)

點(diǎn),si是在sNOWiWnT)之上,棧$的結(jié)構(gòu)圖如圖1.3.1所示.通常稱棧的插入為進(jìn)棧，?稱棧的

刪除為出棧.因?yàn)樽詈筮M(jìn)棧的結(jié)點(diǎn)必定最先出棧,所以棧具有后進(jìn)先出的特性.這樣,棧也稱

后進(jìn)先出表,簡稱JJ?(LastInFirstOut)表.

棧頂

棧底

圖1.3.1棧的結(jié)構(gòu)

日常生活中有很多棧的例子.比如,我們可以把放在桌上的一疊書看作是一個(gè)棧,并約

定不能把書插入中間,或從中間把書抽出.那么，后來放進(jìn)的書只能放在頂上,從這疊書取走

的只能是頂上的那一本.又如圖Z3.2所示的鐵路棧道B,只能從A進(jìn)入B,在B中停留的列車只

能從C離去.這樣，只有最后進(jìn)入棧道B的列車才能馬上向C離去.

我們可以用數(shù)組表示棧,在一般情況下,用一個(gè)指針top指向棧頂結(jié)點(diǎn)在數(shù)組的存放位

置,稱top為棧項(xiàng)指針.對于C語言來講,下標(biāo)為0的數(shù)組元素也用來存放棧的結(jié)點(diǎn).我們置

top=T表示棧空的初始狀態(tài).結(jié)點(diǎn)進(jìn)棧時(shí),首先執(zhí)行top加1,使top指向進(jìn)棧結(jié)點(diǎn)在數(shù)組的存

放位置,然后把進(jìn)棧結(jié)點(diǎn)送到top當(dāng)前所指的位置上;在執(zhí)行出棧時(shí),首先把top所指向的棧頂

結(jié)點(diǎn)送到接受結(jié)點(diǎn)的變量中,然后執(zhí)行top減1,使top指向新的棧頂結(jié)點(diǎn).進(jìn)棧和出?？梢越?/p>

替進(jìn)行.當(dāng)成功的出棧次數(shù)等于成功的進(jìn)棧次數(shù)時(shí),這時(shí)出現(xiàn)top=T的?？諣顟B(tài).?？諘r(shí)不能

出棧.如果表示棧的數(shù)組共有MAXN個(gè)元素,那么當(dāng)成功的進(jìn)棧比成功的出棧多MAXN次時(shí),這時(shí)

出現(xiàn)top=MAXNT的棧滿狀態(tài).棧滿時(shí)不能進(jìn)棧，圖1.3.3表示棧的這種表示方法.

第二種用C語言的數(shù)組表示棧的方法時(shí)用棧頂指針top指向下一次進(jìn)棧結(jié)點(diǎn)的存放位

置,并用top=0表示?？?，當(dāng)top=MAXN時(shí),表示棧滿.圖1.3.4表明了這種表示方法.在結(jié)點(diǎn)進(jìn)棧

時(shí),首先把結(jié)點(diǎn)送到top所指的數(shù)組元素中，然后top加1,讓top指向下次結(jié)點(diǎn)進(jìn)棧的存放位置;

在出棧時(shí),首先top減1,然后把top現(xiàn)在所指的數(shù)組元素所存放的結(jié)點(diǎn)送到接受出棧結(jié)點(diǎn)的變

量中.當(dāng)然,在出現(xiàn)?？諘r(shí),不能出棧;在出現(xiàn)棧滿時(shí),不能進(jìn)棧.圖1.3.5給出每次進(jìn)棧和出棧

時(shí)棧的變化情況.

在下面實(shí)現(xiàn)棧的運(yùn)算時(shí),采用如圖7.3.4所示的第二種表示方法.對于第一種棧的表示

方法,處理?xiàng)５倪\(yùn)算也是相似的,請讀者自己去完成.

下面給出C語言的說明及實(shí)現(xiàn)棧運(yùn)算的函數(shù).假設(shè)棧中結(jié)點(diǎn)的數(shù)據(jù)類型是char.

#defineMAXN26

charstack[MAXN];

inttop=0;/*把棧置成空的狀態(tài)*/

intpush(x)/*push。函數(shù)實(shí)現(xiàn)結(jié)點(diǎn)x進(jìn)棧*/

charx;

(

if(top>=MAXN)

return(1);/*棧滿，進(jìn)棧失敗，返回1*/

stack[top++]=x;

return(0);/*進(jìn)棧成功，返回0*/

}

intpop(p_y)/*pop()函數(shù)實(shí)現(xiàn)出棧*/

char*p_y；

(

if(top==0)

return(1);/*棧空，出棧失敗，返回1*/

*P_y=stack[-top];

return(0);/*出棧成功，返回0*/

)

1.3.2隊(duì)列及其基本運(yùn)算

隊(duì)列是只允許在一端進(jìn)行插入,且只允許在另一端進(jìn)行刪除的線性表.稱允許刪除的

一端為隊(duì)首，?稱允許插入的一端為隊(duì)尾.有時(shí)稱隊(duì)列的插入為進(jìn)隊(duì);稱隊(duì)列的刪除為幽?

若給定的隊(duì)列為Q二(qo,qi,…,qn-i),則qo是隊(duì)首結(jié)點(diǎn),是隊(duì)尾結(jié)點(diǎn),qi在qi+i之前,qi+i

在qi之后(OWiWn-l).圖1.3.6給出隊(duì)列Q的結(jié)構(gòu).因?yàn)樽钕冗M(jìn)入隊(duì)列的結(jié)點(diǎn)必定最先出隊(duì).

所以隊(duì)列具有先進(jìn)先出的特性.因此,隊(duì)列也稱先進(jìn)先出表,簡稱FIFOOirstInFirstOut)

出隊(duì)一qOq1...qiqi+1...qn-1.---------進(jìn)隊(duì)

隊(duì)首隊(duì)尾

圖1.3.6隊(duì)列Q的結(jié)構(gòu)

我們可以用數(shù)組表示隊(duì)列,通常用一個(gè)指針head指向隊(duì)首結(jié)點(diǎn)在數(shù)組的存放位置,稱

head為頭指鈦;用另一個(gè)指針tail指向隊(duì)尾結(jié)點(diǎn)在數(shù)組的存放位置,稱tail為尾指針.我們置

head=0和tail=T表示隊(duì)列空的初始狀態(tài).

假設(shè)用C語言的數(shù)組q[MAXN]表示隊(duì)列，當(dāng)tail=MAXNT時(shí)，出現(xiàn)隊(duì)列滿.在隊(duì)列不滿時(shí)，

可執(zhí)行進(jìn)隊(duì)運(yùn)算.進(jìn)隊(duì)時(shí),首先執(zhí)行tail加1,使tail給出新結(jié)點(diǎn)的存放位置,再把新結(jié)點(diǎn)送到

由tail所指的數(shù)組元素中.在隊(duì)列非空時(shí),可執(zhí)行出隊(duì)運(yùn)算.出隊(duì)時(shí),首先把head所指的隊(duì)首

結(jié)點(diǎn)送到接受結(jié)點(diǎn)的變量中,然后執(zhí)行head加1,使head指向新的隊(duì)首結(jié)點(diǎn),當(dāng)頭指針超過尾

指針時(shí)，出現(xiàn)隊(duì)空狀態(tài),這時(shí)有head>tail.圖1.3.先苗述了用這種方法表示隊(duì)列的進(jìn)隊(duì)和出隊(duì)

的情況.

為配合下面環(huán)形隊(duì)列的描述,這里給出隊(duì)列的第二種表示方法.我們讓頭指針head指

向存放隊(duì)首結(jié)點(diǎn)的數(shù)組元素的前一個(gè)數(shù)組元素,而不是指向隊(duì)首結(jié)點(diǎn)的數(shù)組元素;讓尾指針

tail仍然指向存放隊(duì)尾結(jié)點(diǎn)的數(shù)組元素.這時(shí),隊(duì)列空的初始狀態(tài)是head=tail=T.在經(jīng)過多

次進(jìn)隊(duì)和出隊(duì)運(yùn)算之后，一旦head趕上tail(即head=tail)時(shí)，則出現(xiàn)隊(duì)列空.隊(duì)列滿的標(biāo)志

仍然是tail=MAXNT.圖1.3.史苗述了用第二種表示方法時(shí)進(jìn)隊(duì)和出隊(duì)的情況.

對于用第二種方法表示的隊(duì)列,在隊(duì)列不滿的情況下,允許進(jìn)隊(duì).進(jìn)隊(duì)時(shí),首先讓tail

加1,然后把新結(jié)點(diǎn)存放在由tail所指的數(shù)組元素中.在隊(duì)列非空的情況下,允許出隊(duì).出隊(duì)時(shí),

首先讓head加1,然后將存放在由head指出的數(shù)組元素中的結(jié)點(diǎn)取出，送到接受出隊(duì)結(jié)點(diǎn)的變

量中.

下面給出C語言的說明及實(shí)現(xiàn)用第二種方法表示的隊(duì)列的進(jìn)隊(duì)和退隊(duì)的函數(shù).

ttdefineMAXN26

charq[MAXN];

inthead=-l,tail=-l;

inten_queue(x)/*結(jié)點(diǎn)x進(jìn)隊(duì)*/

charx;

(

if(tail二二MAXN-1)

return(1);

q[++tail]=x;

return(0);/*進(jìn)隊(duì)成功，返回0*/

)

intde_queue(p_y)/*出隊(duì)*/

char*p_y;

if(head-tail)

return(1);/*對空，不能出隊(duì)，返回1*/

*P_y=q[++head];/*頭指針加1,把隊(duì)首結(jié)點(diǎn)送到指針

p_y所指的變量中*/

return(0);/*出隊(duì)成功，返回0*/

從圖38可以看出，一旦出現(xiàn)tai1=MAXNT時(shí)，盡管原來存放出隊(duì)結(jié)點(diǎn)的數(shù)組元素已

空著,但卻沒有再被使用.所以，當(dāng)tail=MAXNT時(shí)，隊(duì)列不是真正的滿,而是假滿.這時(shí),我們

可以采取下面的處理方法，以充分利用已空著的數(shù)組元素.首先，當(dāng)隊(duì)列出現(xiàn)隊(duì)空時(shí),就把頭

指針和尾指針置成隊(duì)空的初始狀態(tài)，即置head=tail=T.另外,可采用兩種極端方法:一是當(dāng)

一個(gè)結(jié)點(diǎn)出隊(duì)時(shí),就把隊(duì)列中所有的結(jié)點(diǎn)都依次向隊(duì)首方向移動(dòng)一個(gè)位置,并修改頭指針和

尾指針;另一是當(dāng)tail=MAXNT且隊(duì)列不是真正滿時(shí)，把隊(duì)列的所有結(jié)點(diǎn)都依次移到數(shù)組的最

前端,并修改頭指針和尾指針.雖然這兩種方法都能充分利用數(shù)組元素,但需要移動(dòng)隊(duì)列的所

有結(jié)點(diǎn),這樣做很麻煩且花費(fèi)時(shí)間.為了克服這一缺點(diǎn),我們下面引進(jìn)更為實(shí)用的環(huán)形隊(duì)列.

1.3.3環(huán)形隊(duì)列

如果我們把表示隊(duì)列的數(shù)組的元素q[0]和q[MAXNT]連接起來,形成一個(gè)環(huán)形的表,稱

這樣的環(huán)形表為環(huán)形隊(duì)列(見圖Z3.9).初始時(shí),置隊(duì)列空的初態(tài)為head=tail=0,如圖3所

示.此時(shí),如果連續(xù)進(jìn)隊(duì)三次,那么進(jìn)隊(duì)后的隊(duì)列如?所示.然后出隊(duì)兩次,則有如圖c所示的

隊(duì)列.

在隊(duì)列不滿的情況下,可以進(jìn)隊(duì).當(dāng)出現(xiàn)tail=head時(shí)，隊(duì)列已滿,此時(shí)不能再進(jìn)隊(duì)了，

如副所示.在隊(duì)列非空的情況下,可以出隊(duì).當(dāng)出現(xiàn)head=tail