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

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

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

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

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

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

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

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

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

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

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

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

第五部分、導(dǎo)師近兩年發(fā)表的論文.................................................179

第六部分：外校同專業(yè)真題.......................................................179

第七部分：部分年份真題解析180

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

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

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

程序。

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

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

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

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

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

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

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

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

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

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

知識點。

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

(l)“r”只讀，為輸入打開一個文本文件。

(2)“晨'只寫，為輸出打開一個文本文件

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

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

(D打開文件：

If((fp=fopcn(student.datw,"r+"))==NULL)

{printf("can'topenthisfile\nw);

Exit(O);)

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

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

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

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

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

(4)frecid(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'表示開始點’1'表示當(dāng)前’2'表示末尾

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

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

第二部分C程序源代碼

1、起泡排序

/*fromsmalltobig*/

main()

{inta[ll];

inti,j,t;

printf(，/input10mnumbers:\n，z);

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

scanf(〃%d",&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;J

printf(Sprintthesortednumber:\n，z);

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

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

2、選擇排序

\main()

{inta[10];

inti,j,temp;

printf(z,input10numbers:\n,z);

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

scanf&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]J;

}

3、插入排序

main()

{inti,j,a[ll];

printf("input10numbers:\nz，);

for(i=l;i<l1;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>

ttdefineN10

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

{inti;

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

{printf(z/\ninputNO.:〃)；

scanf);

printf(/z\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,nane[i]);

num[i]=num[min]:

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

num[min]=templ;

strcpy(name[min],temp2);

)

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

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

，，，，

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

)

voidsearch(intn,intnum[],charnamc[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(^NO.%d,hisnameis%s\n/z,n,name[loca]);

sign=T;

)

elseif(n<num[mid])

bott=mid-l;

elsetop=mid+l;

)

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

printf(/zcannotfind%d\n〃，n);

)

main()

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

charname[N][8];

input(num,name);

sort(num,name);

while(flag)

{printf(，?\ninputnumbertolookfor:〃)；

scanf(〃%d〃,&number);

search(number,nun,name);

printf(z/\nCONTINUEornot(Y/N)?");

getchar();

c=getchar();

if(c='N'||c二二'n)

flag=0;

)

}

6,在數(shù)組中插入一個數(shù)：

(第一種方法)

main()

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

intn,i,j,tempi,tenp2;

printfCAnthearrayis:\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++J

{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(z/\nthenewarrayis:\n〃)；

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

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

}

(第二種方法)

/*charusort*/

main()

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

printf(^Xninputanumber:\n〃)；

scanf&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(z，thesortedarrayis〃)；

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

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

}

7、鏈表的基本操作：

#dcfineNULL0

#defineLENsizeof(structstudent)

structstudent

{longnum;

floatscore;

structstudent*next;

}；

intn;

structstudent*creat(void)

{structstudent*hcad,*pl,*p2;

n=0;

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

scanf(，z%ld,%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(〃％ld,%f〃，&pl->num,&pl->score);

)

p2->next=NULL;

return(head);

)

voidprint(structstudent*head)

(structstudent*p;

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

p=head;

if(head!=NULL)

do

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

p=p->next;

}while(p!:NULL);

}

structstudent*del[structstudent*head,longnum)

{structstudent*pl,*p2;

if(hcad==NULL)

{printf(z，\nlistnull!\n〃)；gotoend;}

pl二head;

while(num!=p1->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%：d\n〃,num);

n=n-l;

)

，z

elseprintf(%ldnotbeenfound!\n〃，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>p?num&&pl->next!=NULL)

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

)

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

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

elsep2->next=p0;

pO->next=pl;

else

{pl->next=pO;

pO->next=NULL;

)

n=n+l;

return(head);

)

main()

(structstudent*head,stu;

longdelnum;

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

head=creat();

print(head);

printf("inputthedeletednumber/');

scanf(*%1d〃,&delnum);

head=del(head,del_num);

print(head);

printf(，z\ninputtheinsertedrecord:");

scanf%f”,&stu.num,&stu.score);

head=insert(head,&stu);

print(head);

}

8、文件的基本操作：

^defineNULL0

#include<stdio.h>

main()

{FILE*fp;

charch,filename[10];

scanf("%s〃，filename);

if((fp=fopen(filename,*w'))==NULL)

{printf(^cannotopenthisfile");

exit(0);

)

ch=getchar();

while(ch!=,#')

{fputc(ch,fp);

ch=getchar();

)

fclose(fp);

)

9、判斷是不是素數(shù)〉

#include<math.h>

main()

{intx,i;

printf("inputanunber:/z);

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_cnd=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(/?thescoreofNO.%dare:\n?/,n);

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

printfC%6.2f",*(*(p+n)+i));

)

voidsearchfai1(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(//N0.%dfails,hisscoresare:\n〃，j+1);

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

printf(〃％5.lf〃，*(*(p+j)+i));

printf(〃\n〃)；

)

}

}

main()

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

average(*score,12);

search(score,2);

searchfail(score,3);

)

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

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

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

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

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

Structstudent

{intnum;

Charname[20];

Intscore[8];

Intmark;

)

答題要點：

^defineM1000

Main()

{FILE*fpl,*fp2;

Structstudentstu[M];

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

If((fpl=fopen(student.dat“，"r+"))==NULL)

{printf("can'topenthisfile\nM);

Exit(O);)

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

{printf(“can'topenthisfile\nw);

Exit(0);}

i=0;

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

i++；

count=l;

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

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

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

If(m>=3)mark=0;

Elsemark-1;)

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

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

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

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

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

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

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

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

stu[j].mark=stu[j+l].mark;}

Elsefwrite(&stu[i].sizeof(structstudent

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

第一章線性表

線性表是最常用、垠簡單的一種線性結(jié)構(gòu)。因為它的應(yīng)用范圍十分廣泛，所以有必要

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

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

1.1.1線性表

線性表是具有相同類型的n個數(shù)據(jù)元素ko,ki,…J的有限序列,記為(ko,ki,…匕一3元

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

時，ko是最前面的一個元素，k”/是最后一個元素，線性表相數(shù)據(jù)元素的相對位置是確定的。

因為線性表的數(shù)據(jù)元素構(gòu)成一個序列，在序列中，k排在ki+i前面，我們稱太是ki+i的前趨

元素；排在左后面，我們稱ki+i是％的后繼元素。k0沒有前趨元素，％」沒有后繼元素;

當(dāng)n22時，ko有后繼元素ki，k『i有前趨元素km;當(dāng)n23時，ki(0<i<n-l)既有前趨

元素ki”,也有后繼元素ki+i。

對于給定的線性表(koH,…kn/)，它的數(shù)據(jù)元素集合為{ko.k1,…匕」)，而數(shù)據(jù)元素之間

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

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

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

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

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

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

以是構(gòu)造類型。數(shù)據(jù)項也稱為空段，或稱為城.

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

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

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

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

星期MonTucWedThuFriSatSun

溫度15.516.016.515.715.016.116.4

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

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

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

表L1.2職工工資表

職工號姓名性別年齡工資

001Wangmale35160.50

002Caimale32150.00

003Zhangfemale28130.00

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

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

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

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

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

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

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

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

I.查找

（1）查找線性表的笫i（OWi<n-l）個結(jié)點。

（2）在線性表中查找值為x的結(jié)點。

2.插入

<1）把新結(jié)點插在線性表的第i（0<個位置上。

（2）把新結(jié)點插在值為x的結(jié)點的前面（或后面）

3.刪除

（I）在線性表中刪除第i（0WiWn-1）個結(jié)點。

（2）在線性表中刪除值為x的結(jié)點。

4.其他運(yùn)算

（1）統(tǒng)計線性表中結(jié)點的個數(shù)。

（2）打印線性表中眇有結(jié)點。

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

（4）把一個線性表拆成幾個線性表。

（5）把幾個線性表合并成一個線性表。

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

1.2順序存貯的線性表

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

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

因為線性表中所有結(jié)點的數(shù)據(jù)類型是相同的，所以每個結(jié)點在存貯器中占用大小相同的

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

設(shè)存放結(jié)點ki（OWi<n-l）的開始地址為ak”那么結(jié)點ki的地址aki可用整數(shù)i,以及地

址計算公式

aki=ako+i*s

計算出來。

對于順序存貯的線性表，因為可以利用地址計算公式直接計算出k,,所以存取第i（0

<iWn-1）個結(jié)點特別方便。

如果用C語言的數(shù)組表示線性表（kok,…kn/）,我們可使用如下的說明：

#defineMAXSIZE100

intlist[MAXSIZE];

intn;

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

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

%,ki,…knd依次存放在數(shù)組元素list[O],list[1],?--list[n-1]（I3o這樣,存放線性表各個結(jié)點的地

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

akn-i

t

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

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

因aki=&list[i]

而&list[i]=&list|Oj+i*s

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

1.2.1線性表的插入

這里所講的插入是在具有n個結(jié)點的線性表中，把新結(jié)點插在線性表的第i（0WiWn-l）

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

前，必須把原來位置號（序號）為（n-l）至位置號為i的結(jié)點依次往后移一個位置，然后

把新結(jié)點放在第i個位置上，此時宮移動（n-i）個結(jié)點。對于i=n,只要把新結(jié)點插在第n

個位置上，此時無需移動結(jié)點。

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

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

位置上（即<0或i>n）,則返回I；若產(chǎn)^^*5也￡（即線性表已滿），此時lisl數(shù)組沒有存

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

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

實現(xiàn)插入后線性表長度n增加1。

intsq_inscrt(list,p_n,i,x)

intlistfLx;

int*p_nj;

{intj；

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

retum(I);

if(*p_n=MAXSIZE)

rcturn(2);

foi(j=*p_n;j'>i;j-)

list[i]=x;

(*p_n)++;

retum(O);

}

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

i(O<iWn-l)個位置上，可用如下的調(diào)用語句：

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

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

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

件=因為把一個新結(jié)點插在第i個位置上需移動(n-i)個結(jié)點，所以移動結(jié)點的平

1=0

均次數(shù)為

；=0

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

1

P(尸P產(chǎn)…二Pn-尸----

1.2.2線性表的刪除

這里所講的刪除是在具有n個結(jié)點的線性表中刪除第i(OWiWn-l)個位置上的結(jié)點，

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

(n-1)的結(jié)點都依次向前移動一個位置,此時共需移動(n-i-1)個結(jié)點.

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

list中,刪除第i(OWiWnT)個位置上的結(jié)點.若刪除的結(jié)點不在可刪除的位置上(即i<0活i

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

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

減少L

intsq_delete(list,p_n,i)

intlist[];

int*p_n,i;

intj;

if(i<0||i>=*pn)return(l);

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

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

(*p_n)—;

return(0);

}

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

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

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

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

n-\

2〃尸1?因為刪除第1(0(]?「1)位置上的結(jié)點需移動(11-廣1)個結(jié)點,所以移動結(jié)點的平

<=0

均次數(shù)為

J-0

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

1

P0=Pl=，，，=Pn-1=----

〃+1

那么上面的和式可改寫為

n-\n

一1?-〃-(-〃--一-1-)=-----七一

n222

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

的結(jié)點很多，且每個結(jié)點的數(shù)據(jù)量相當(dāng)大時，花贄在移劭結(jié)點上的執(zhí)行時間就會很長。

1.2.3用順序存貯的線性表表示多項式

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

e,H

A(x)=amx+…+qK+q//

其中每個%(OWiWm)是A(x)的非零系數(shù)；次數(shù)4(OWiWm)是遞減的，即>ei)

20。

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

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

#defineMAXN100

typedefstructterm

(

floatcoef;

intexp;

}TERM;

TERMpoly[MAXN];

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

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

例如，對于下面兩個多項式：

A(X)=8X60+6X50+4X25+2X10+1

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

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

0123456789???MAXN-1

coef864217-63???

exp605025100605020■?■

ahatbhbtfree

圖1.2.1多項式的存貯

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

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

這里順便指出一點,ah,at,bh,bt及free等,它們其實不是指針，只是一種蝴.這是因為

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

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

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

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

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

為下次添加結(jié)點但提供存放位置.下面給出C語言的說明及實現(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],cocf=c;

poly[free++].exp=e;

return(0);

)

intpoly_add(ah,at,bh,bt,p_ch,pct)

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=polyfp].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(l);

p++；

q++；

break;

case'<':

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

return(l);

q++；

break;

case'>’:

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

return(l);

P++；

break;

}

)

while(p<=at)

(

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

return(l);

P++；

)

while(q<=bt)

if(append(poly[p].cocf,poly[q].exp))

return(l);

*pct=free-l;

return(0);

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

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

printf("ERROR'n");

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

么說明相加后得到一個零多項式.

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

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

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

次數(shù)都不想同時，執(zhí)行循步的次數(shù)最多，共執(zhí)行(mE)次，故其執(zhí)行時間最多為0(min);第二和

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

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

1.3順序存貯的棧和隊列

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

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

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

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

允許插入和刪除的一端為.愎頂。若給定棧5=(so,s.,…，sQ,則sD是棧底結(jié)點，Sn?是棧頂結(jié)

點,s,”是在sMOWiWn-1)之上，棧S的結(jié)構(gòu)圖如圖1.3.1所示.通常稱棧的插入為進(jìn)棧，?稱棧的

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

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

棧頂

棧底

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

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

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

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

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

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

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

top=-l表示?？盏某跏紶顟B(tài).結(jié)點進(jìn)棧時,首先執(zhí)行top加1,使top指向進(jìn)棧結(jié)點在數(shù)組的存

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

結(jié)點送到接受結(jié)點的變量中，然后執(zhí)行top減1,使top指向新的棧頂結(jié)點.進(jìn)棧和出棧可以交

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

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

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

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

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

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

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

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

時棧的變化情況.

在下面實現(xiàn)棧的運(yùn)算時,采用如儆.3.初『示的第二種表示方法.對于第一種棧的表示

方法，處理棧的運(yùn)算也是相似的,請讀者自己去完成.

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

#defineMAXN26

charstack[MAXN];

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

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

chairx;

(

if(lop>=MAXN)

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

stack[top++]=x;

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

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

char*p_y;

if(top==0)

return(l);/*?？眨鰲Ｊ?，返回1*/

*P_y=stack[-top];

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

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

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

一端為班直，.稱允許插入的i端為JO。有時稱隊列的插入為進(jìn)叢;稱隊列的刪除為出?限.

若給定的隊列為Q=(q°,q】,…,qn-i),則q0是隊首結(jié)點,qm是隊尾結(jié)點,q：在q.之前,q-

在卬之后(OWiWnT).圖1.3.6給出隊列Q的結(jié)構(gòu).因為最先進(jìn)入隊列的結(jié)點必定最先出隊.

所以隊列具有先進(jìn)先出的特性.因此，隊列也稱先進(jìn)先出表，簡稱￡!K(FirstInFirstOut)

&

出隊^_qOq1...qiqi+1...qn-1----------進(jìn)隊

隊首隊尾

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

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

head為頭指軌;用另一個指針tail指向隊尾結(jié)點在數(shù)組的存放位置，稱tail為星指針.我們置

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

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

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

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

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

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

的情況.

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

向存放隊首結(jié)點的數(shù)組元素的前?個數(shù)組元素，而不是指向隊首結(jié)點的數(shù)組元素;讓尾指針

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

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

仍然是tail=MAXN-l.圖L3.硼述了用第二種表示方法時進(jìn)隊和出隊的情況.

對于用笫一種方法表示的隊列，在隊列不滿的情況下，允許進(jìn)隊.進(jìn)隊時，首先讓tail

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

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

量中.

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

^defineMAXN26

charq[MAXN];

inthead=-l,tail=-l;

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

charx;

(

if(tail==MAXN-l)

return(l);

q[++tail]=x;

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

)

intdc_queue(py)/*出隊*/

char*p_y;

(

if(head==tail)

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

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

p_y所指的變量中*/

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

)

從圖I.3.8可以看出，一旦出現(xiàn)tail=MAXNT時,盡管原來存放出隊結(jié)點的數(shù)組元素已

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

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

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

一個結(jié)點出隊時,就把隊列中所有的結(jié)點都依次向隊首方向移動?個位置,并修改頭指針和

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

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

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

1.3.3環(huán)形隊列

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

這樣的環(huán)形表為環(huán)形隊列(見圖/.3.9).初始時,置隊列空的初態(tài)為head=tail=0,如圖?所

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

隊列.

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

如圖c所示.在隊列非空的情況下,可以出隊.當(dāng)出現(xiàn)headXail時，隊列已空,此時不能再出隊

了，如圖e所示.由此可見,環(huán)形隊列的隊滿和隊空都有hcad=tail.

如上所述,環(huán)形隊列的隊滿和隊空都有headrail.因此，不能只用headfail來判斷隊

滿或隊空.此時,必須增加一個標(biāo)志tag.在head=tail的情況下，由tag為0(或1)來表示隊列空

(或滿).根據(jù)環(huán)形隊列的特點，下面給出實現(xiàn)進(jìn)隊和出隊的函數(shù).環(huán)形隊列空的初始狀態(tài)為

head=tail=0,且tag=0.

#defineMAXN26

cheirq[MAXN];

inthead=0,tai1=0,tag=D;

intenqueue(x)

charx;

(

if(tail==head&&tag==l)

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

tail=(tail+l)%MAXN;

q[tail]=x;

if(tail==hcad)tag=l;/*置堆滿標(biāo)志*/

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

)

intde_queue(py)

char*p_y;

{

if(head==tail&&tag==O)

return(l);/*隊列空，出隊失敗，返回1*/

head=(head+l)%MAXN;

*p_y=qLhead];

if(hecid==tail)tag=0;/*置隊空標(biāo)志*/

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

)

由于增加了一個標(biāo)志tag,使得程序的語句增加了，判斷條件也更雜了，這樣將增加程

序的運(yùn)行時間.在頻繁執(zhí)行進(jìn)隊和出隊運(yùn)算的情況下,如操作系統(tǒng)的作業(yè)排隊和進(jìn)程排隊,將

大大地增加運(yùn)行時間.為了盡量提高運(yùn)行速度而減少執(zhí)行時間,我們以?個結(jié)點所占用的存

貯空間為代價,來節(jié)省執(zhí)行時間.實現(xiàn)的辦法是在進(jìn)隊時，首先讓tail加上1進(jìn)行模MAXN運(yùn)算

后，再存入tail.然后判別tail是否已趕上head:如果tail沒有趕上head,那么就執(zhí)行進(jìn)隊運(yùn)

算;如果tail趕上head,盡管還有一個空的數(shù)組元素可以存放進(jìn)隊結(jié)點,但我們不允許新結(jié)點

進(jìn)隊，而是報告隊滿.引入上述機(jī)制后，可以把上面兩個函數(shù)改寫成如下的函數(shù)：

^defineMAXN26

charq[MAXN];

inthead=0,tai1=0;

intencq(x)

charx;

{

tail=(tail+l)%MAXN;

if(tail==head)

(

if(tail==0)