华东师范大学系统理论专业考研全程攻略

诗算机科学技术系

第一部分、专业课终极笔记.........................................................3

一、本科生笔记...............................................................3

二、《c程序设计》考研总结笔记

三、老师讲义（附录电子版）.................................................129

四、整理过的笔记...........................................................129

第二部分：专业课复习方法.......................................................155

第三部分：复试详细情况介绍.....................................................155

第四部分：本科生期末考试试卷，平时作业题目....................................171

-、数据结构期末试题及其答案................................................

二、期中考试.................................................................

三、平时作业..................................................................

第五部分、导师近两年发表的论文.................................................179

第六部分：外校同专业真题.......................................................179

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

第一部分、专业课笔记

一、专业课笔记《C程序设计》

关于C语言的笔记分两部分：第一部分是关于基础知识的，第二部分是一些考生必须掌握的

程序。

第一部分C语言基础知识

在C考试中有C语言选择题，主要考察基础知识，考生只需掌握以下几个知识点就可以了。

1、指针知识总结:

Int*pP为指向整形数据的指针变量

Int*p[n]指针数组，它由N个指向整形数据的指针元素组成，通常用字符数组

Int(*p)[n]P为指向含N个元素的一维数组的指针变量，通常用于二维数组a[][]

Int*p()P带回一个指针的函数，该指针指向整性数据。

Int(*p)()P为指向函数的指针，返回以整形值。

Int**pP为指针变量，指向一个指向整形数据的指针变量。

至于每个指针例子考生可参看书上第十章。这个问就一定要掌握透彻，每年都会考这个

知识点。

2、常见文件的打开方式：

(l)“r”只读，为输入打开一个文本文件。

(2)“晨'只写，为输出打开一个文本文件

(3)“r+”/“w+”为读写打开/新建一个文本文档。

3关于文件的一些命令息结：

(D打开文件：

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

{printf("can'topenthisfile\nw);

Exit(O);)

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

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

关闭文件：fp=fclose(文件名，使用方式)；

(3)把一个字符写到磁盘文件中:fputc(ch,fp);

把一个字符读入磁盘文件中：fgotc(fp);

(4)frecid(buffer,size,count,fp)读入数据

fwrite(buffer,size,count,fp)输出数据

(5)fwrite(文件指针,格式字符串，输出表列)

Fscanf(文件指针，格式字符串，输入表列)

它们的读写对象是文件磁盘

(6)fgets(str,n,fp)从fp中读入字符串到str中

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

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

'O'表示开始点’1'表示当前’2'表示末尾

其他的知识点比较琐碎，考生需要把书上第7、10章的内容仔细的看一边，又一些细节

的知识在考试的选择题中经常出现，不过就一两道。

第二部分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,在数组中插入一个数：

(第一种方法)

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、判断是不是素数〉

#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、指针的应用

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年的题弄明白就可以了，一般文件的题

与排序算法相结合。请看下面例题：

现有一个记录学生成绩的数据文件studcnt.dat,其中人数不清，其文件数据结构如下所

示，每位学生参加8门课程考试，请将其中有三门及三门以上考试成绩不及格的学生信息写

入新数据文件fail,dat。文件结构同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

二、《数据结构教程》本科生笔记

第一章线性表

线性表是最常用、垠简单的一种线性结构。因为它的应用范围十分广泛，所以有必要

在这里作较详细的介绍。

1.1线性表及其基本运算

1.1.1线性表

线性表是具有相同类型的n个数据元素ko,ki,…J的有限序列,记为(ko,ki,…匕一3元

素个数n称为线性表的长度，称长度为零的线性表为空的线性表(简称为空表)。当n21

时，ko是最前面的一个元素，k”/是最后一个元素，线性表相数据元素的相对位置是确定的。

因为线性表的数据元素构成一个序列，在序列中，k排在ki+i前面，我们称太是ki+i的前趋

元素；排在左后面，我们称ki+i是％的后继元素。k0没有前趋元素，％」没有后继元素;

当n22时，ko有后继元素ki，k『i有前趋元素km;当n23时，ki(0<i<n-l)既有前趋

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

对于给定的线性表(koH,…kn/)，它的数据元素集合为{ko.k1,…匕」)，而数据元素之间

的关系由数据元素出现在线性表中的位置所确定。我们可用数据元素&ki+1构成的偶对表

示数据元素h和ki+1所存在的这种关系。因此，可用数据元素的偶对的集合表示线性表中数

据元素之间的关系，这种关系记为{(ki，ki+i)|0&i<n-l}o对于相同数据元素集合的两个

线性表，如果数据元素出现在表中的次序不相同，那么若两个线性表是不想同的.

线性表中的数据元素也称为结点，或称为记录，它可以是一个整数、一个实数、一个字

符或一个字符串；也可以由若干个数据项组成，其中每个数据项可以是一般数据类型，也可

以是构造类型。数据项也称为空段，或称为城.

比如，表1.1.1的线性表用于记录最近一周每天的平均气温。每个结点有两个字段：一

个是星期，用于指明是星期儿，它的数据类型是由三个字符组成的字符串；另一个是温度，

用于指明平均气温，它的数据类型是实数。

表1.1.1一周内眉头的平均气温记录表

星期MonTucWedThuFriSatSun

温度15.516.016.515.715.016.116.4

再比如，表1.1.2也是一个线性表，它是一个企业的职工工资表。改表由职工号、姓名、

性别、年龄和工资等五个字段所组成，其中职工号、年龄的数据类型是整数；姓名和性别是

字符串；工资是实数。

表L1.2职工工资表

职工号姓名性别年龄工资

001Wangmale35160.50

002Caimale32150.00

003Zhangfemale28130.00

线性表中的结点可由若干个字段组成，我们称能唯一标识结点的字段为关键字，或简称

为键。如表1.1.1的线性表的关键字是星期，而表1.1.2的线性表的关键字是职工号。在本书

中，为了讨论方便，往往只考虑结点的关键字，而忽略其他字段。这样的假设也不失•股性,

只要知道存放某结点的存贮单元，就能取到该结点的其他字段上的值。

1.1.2线性表的基本运算

上面介绍了线性表的基本概念，下面介绍线性表的一些基本运算。

线性表结构可以动态地增长或收缩，在线性表的任何位置上可以访问、插入或删除结点。

我们把线性表常用的运算分成几类，每类包括若干种运算。

I.查找

（1）查找线性表的笫i（OWi<n-l）个结点。

（2）在线性表中查找值为x的结点。

2.插入

<1）把新结点插在线性表的第i（0<个位置上。

（2）把新结点插在值为x的结点的前面（或后面）

3.删除

（I）在线性表中删除第i（0WiWn-1）个结点。

（2）在线性表中删除值为x的结点。

4.其他运算

（1）统计线性表中结点的个数。

（2）打印线性表中眇有结点。

（3）复制一份线性表。

（4）把一个线性表拆成几个线性表。

（5）把几个线性表合并成一个线性表。

（6）根据结点的某个字段值按升序（或降序）重新排列线性表。

1.2顺序存贮的线性表

在计算机内，可以利用不同的存贮方式表示线性表，其中最常用、最简单的方式就是顺

序存贮。所谓线性表的顺序存贮，就是用一组连续的存贮单元一次存贮线性表中的结点。

因为线性表中所有结点的数据类型是相同的，所以每个结点在存贮器中占用大小相同的

空间。如果每个结点占用计算机中按机器字编址或按字节编址的S个地址的存贮单元，并假

设存放结点ki（OWi<n-l）的开始地址为ak”那么结点ki的地址aki可用整数i,以及地

址计算公式

aki=ako+i*s

计算出来。

对于顺序存贮的线性表，因为可以利用地址计算公式直接计算出k,,所以存取第i（0

<iWn-1）个结点特别方便。

如果用C语言的数组表示线性表（kok,…kn/）,我们可使用如下的说明：

#defineMAXSIZE100

intlist[MAXSIZE];

intn;

其中MAXSIZE是数组IE中元素个数的最大值，n是线性表中当前结点个数。这里假设线

性表的结点值是整数，所以数组元素也是整数，当然可根据需要取其他类型。线性表的结点

%,ki,…knd依次存放在数组元素list[O],list[1],•­-list[n-1]（I3o这样,存放线性表各个结点的地

址与数组list各个下表变量•的地址有如下的对应关系：

akn-i

t

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

有了上述的对应关系，可得到卜面计算长的地址的公式，这里我们假设s=sizeof（int）：

因aki=&list[i]

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

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

1.2.1线性表的插入

这里所讲的插入是在具有n个结点的线性表中，把新结点插在线性表的第i（0WiWn-l）

个位置上，使原来长度为n的线性表变成长度为（n+1）的线性表。在把新结点放进线性表

前，必须把原来位置号（序号）为（n-l）至位置号为i的结点依次往后移一个位置，然后

把新结点放在第i个位置上，此时宫移动（n-i）个结点。对于i=n,只要把新结点插在第n

个位置上，此时无需移动结点。

下面用一个C函数sq_insert（）实现上述的插入算法。此函数在具有n个结点的线性表

list中，把值为x的结点插入在第i（0WiWn-1）个位置上。若插入位置i不在可以插入的

位置上（即<0或i>n）,则返回I；若产^^*5也£（即线性表已满），此时lisl数组没有存

贮单元存放新结点，则返回2；若插入成功，则返回0。在函数的参数中，有一个指针变量

p_n,在调用时，把存放线性表的当前结点个数的变量n的地址赋给指针变量p_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);

}

对于存放在数组list中的、具有n个结点的线性表，为了把值为x的结点插在线性表第

i(O<iWn-l)个位置上，可用如下的调用语句：

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

在具有n个结点的线性表中，插入一个新结点时，其执行时间主要花费在移动结点的

循环上。假设把新结点插在第i(0WiWn-1)个位置上的概率为p,各个硒应满足约束条

件=因为把一个新结点插在第i个位置上需移动(n-i)个结点，所以移动结点的平

1=0

均次数为

；=0

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

1

P(尸P产…二Pn-尸----

1.2.2线性表的删除

这里所讲的删除是在具有n个结点的线性表中删除第i(OWiWn-l)个位置上的结点，

使原来长度为n的线性表变成长度为(联1)的线性表.删|除时,要把位置号为(i+1)至位置号为

(n-1)的结点都依次向前移动一个位置,此时共需移动(n-i-1)个结点.

下面用一个C函数sq_delele()实现上述的删除算法.此函数在具有n个结点的线性表

list中,删除第i(OWiWnT)个位置上的结点.若删除的结点不在可删除的位置上(即i<0活i

2n),则返回1;若删除成功则返回0.在函数的参数中,有一个指针变量p_n,在调用时,把存

放线性表当前结点个数的变量n的地址赋给指针变量pn,以此来实现删除后线性表的长度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);

}

调用时，可使用如下的语句：

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

在具有n个结点的线性表中，删除一个结点所需的执行时间主要花费在移动结点

的循环上.假设删除第i(OWiWnT)个位置上的结点的概率为pi,每个止应满足约束条件

n-\

2〃尸1・因为删除第1(0(]・「1)位置上的结点需移动(11-广1)个结点,所以移动结点的平

<=0

均次数为

J-0

如果假设删除线性表任何一个结点的概率相同，即有

1

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

〃+1

那么上面的和式可改写为

n-\n

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

n222

上式表明，在顺序存贮的线性表中，删除一个结点，平均大约需要移动一半结点。当线性表

的结点很多，且每个结点的数据量相当大时，花贽在移劭结点上的执行时间就会很长。

1.2.3用顺序存贮的线性表表示多项式

一般代数多项式可写成

e,H

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

其中每个%(OWiWm)是A(x)的非零系数；次数4(OWiWm)是递减的，即>ei)

20。

我们可用包含coef和exp两个字段的结点表示多项式的非零项,其中coef给出系数,exp

给出次数.这样,可用数组poly[MAXW表示多项式.因此,可使用如下的说明：

#defineMAXN100

typedefstructterm

(

floatcoef;

intexp;

}TERM;

TERMpoly[MAXN];

其中MAXN是数组poly可存放结点的最大个数.有时,我们可把MAXN取得适当大,使得多个多项

式可共享数组poly。

例如，对于下面两个多项式：

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

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

它们在数组poly中的存贮情况如图1.2.1所示。

0123456789•••MAXN-1

coef864217-63•••

exp605025100605020■•■

ahatbhbtfree

图1.2.1多项式的存贮

我们使用了攘tah和bh,它们分别给出A(x)和B(x)的第一项在数组中的存放位置,而指

针al和bl分别给出A(x)和B(x)的最后一项在数组中的存放位置,取free=9;

这里顺便指出一点,ah,at,bh,bt及free等,它们其实不是指针，只是一种蝴.这是因为

存放在ah,at,bh,bl及free内的不是数组元素在存贮器中的地址,而是数组元素的下标值，但

由于使用上的习惯，我们仍然称它们为指针,希望读者加以区别.

上面介绍如果用数组存放多项式的方法,下面我们讨论如何用C函数首先多项式相加的

算法.在下面的程序中，函数polyadd()首先C(x)=A(x)+B：x)的运算;而函数append。把系数c

和次数。构成的项存放到指针free所指出的位置上,成为结果多项式的一个项，同时free加1,

为下次添加结点但提供存放位置.下面给出C语言的说明及实现运算的函数.

^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);

可用如下的调用语句执行A(x)和B(x)两个多项式的相加:

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

printf("ERROR'n");

如果打印出ERROR,那么说明数组poly不够用；如果没有打印出ERROR,但调用后出现ct/ch,那

么说明相加后得到一个零多项式.

现在分析polyadd。的执行时间.首先应指出，执行函数append。的时间是0(1).在

polyadd()中，执行三个循环之外的几个语句的时间也是0(1).所以，执行时间主要花费在三

个循环上.设A(x)和B(x)非零项的个数分别为m和n,对于第一个循环，当A(x)和B(x)的各项的

次数都不想同时，执行循步的次数最多，共执行(mE)次，故其执行时间最多为0(min);第二和

第三个循环最多分别执行m次和n次,故其执行时间最多分别为0(m)和0(n).这样,执行

po1yadd()的时间为0(1)+0(m+n)+0(m)+0(n)=0(m+n).

1.3顺序存贮的栈和队列

栈和队列都是特殊的线性表。这两种结构比一般的线性表简单，但非常有用，所以有

必要对它们进行仔细讨论，

1.3.1栈及其基本运算

栈是只允许在一端进行插入和删除的线性表。称允许插入和删除的一端为栈顶；称不

允许插入和删除的一端为.愎顶。若给定栈5=(so,s.,…，sQ,则sD是栈底结点，Sn।是栈顶结

点,s,”是在sMOWiWn-1)之上，栈S的结构图如图1.3.1所示.通常称栈的插入为进栈，•称栈的

删除为出栈•因为最后进栈的结点必定最先出栈,所以栈具有后进先出的特性.这样,栈也称

后进先出表,简称LIFO(LastInFirstOut)表.

栈顶

栈底

图1.3.1栈的结构

日常生活中有很多栈的例子.比如，我们可以把放在桌上的一叠书看作是一个栈，并约

定不能把书插入中间,或从中间把书抽出.那么，后来放进的书只能放在顶上,从这叠书取走

的只能是顶上的那一本.又如图I.3.2讨示的铁路栈道B,只能从A进入B,在B中停留的列车只

能从C离去.这样,只有最后进入栈道B的列车才能马上向C离去.

我们可以用数组表示栈,在一般情况下,用一个指针top指向栈顶结点在数组的存放位

置,称lop为栈顶指针.对于C语言来讲,下标为0的数组元素也用来存放栈的结点.我们置

top=-l表示栈空的初始状态.结点进栈时,首先执行top加1,使top指向进栈结点在数组的存

放位置，然后把进栈结点送到top当前所指的位置上;在执行出栈时，首先把top所指向的栈顶

结点送到接受结点的变量中，然后执行top减1,使top指向新的栈顶结点.进栈和出栈可以交

替进行.当成功的出栈次数等于成功的进栈次数时,这时出现top=T的栈空状态.栈空时不能

出栈.如果表示栈的数组共有MAXN个元素，那么当成功的进栈比成功的山栈多MAXN次时，这时

出现top=MAXNT的栈满状态.栈满时不能进栈,图1.3.3表示栈的这种表示方法.

第二种用C语言的数组表示栈的方法时用栈顶指针lop指向下一次进栈结点的存放位

置,并用top=0表示栈空，当top=MAXN时,表示栈满.图1.3.裱明了这种表示方法.在结点进栈

时，首先把结点送到lop所指的数组元素中,然后top加1,比lop指向下次结点进栈的存放位置;

在出栈时,首先top减1,然后把top现在所指的数组元素所存放的结点送到接受出栈结点的变

量中.当然,在出现栈空时,不能出栈;在出现栈满时,不能进栈.图1.3.静出每次进栈和出栈

时栈的变化情况.

在下面实现栈的运算时,采用如儆.3.初『示的第二种表示方法.对于第一种栈的表示

方法，处理栈的运算也是相似的,请读者自己去完成.

下面给出C语言的说明及实现栈运算的函数.假设栈中结点的数据类型是char.

#defineMAXN26

charstack[MAXN];

inttop=0;/*把栈置成空的状态*/

intpush(x)/*push。函数实现结点x进栈*/

chairx;

(

if(lop>=MAXN)

return(l);/*栈满，进栈失败，返回1*/

stack[top++]=x;

return(0);/*进栈成功，返回0*/

intpop(p_y)/*pop()函数实现出栈*/

char*p_y;

if(top==0)

return(l);/*栈空，出栈失败，返回1*/

*P_y=stack[-top];

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

1.3.2队列及其基本运算

队列是只允许在一端进行插入，且只允许在另一端进行删除的线性表.称允许删除的

一端为班直，.称允许插入的i端为JO。有时称队列的插入为进丛;称队列的删除为出•限.

若给定的队列为Q=(q°,q】,…,qn-i),则q0是队首结点,qm是队尾结点,q：在q.之前,q-

在卬之后(OWiWnT).图1.3.6给出队列Q的结构.因为最先进入队列的结点必定最先出队.

所以队列具有先进先出的特性.因此，队列也称先进先出表，简称£!K(FirstInFirstOut)

&

出队^_qOq1...qiqi+1...qn-1----------进队

队首队尾

图1.3.6队列Q的结构

我们可以用数组表示队列,通常用一个指针head指向队首结点在数组的存放位置,称

head为头指轨;用另一个指针tail指向队尾结点在数组的存放位置，称tail为星指针.我们置

head=O和tail=T表示队列空的初始状态.

假设用C语言的数组q[\IAXN]表示队列，当tail=MAXNT时，出现队列满.在队列不满时，

可执行进队运算.进队时，首先执行tail加1,使tail给出新结点的存放位置,再把新结点送到

由tail所指的数组元素中.在队列非空时，可执行出队运算.出队时，首先把head所指的队首

结点送到接受结点的变量中，然后执行head加1,使head指向新的队首结点.当头指针超过尾

指针时，出现队空状态,这时有head>tail.图1.3.琳述了用这种方法表示队列的进队和出队

的情况.

为配合下面环形队列的描述,这里给出队列的第二种表示方法.我们让头指针head指

向存放队首结点的数组元素的前•个数组元素，而不是指向队首结点的数组元素;让尾指针

tail仍然指向存放队尾结点的数组元素.这时,队列空的初始状态是hcad=tail=T.在经过多

次进队和出队运算之后，一旦head赶上tail(即head二tail)时，则出现队列空.队列满的标志

仍然是tail=MAXN-l.图L3.硼述了用第二种表示方法时进队和出队的情况.

对于用笫一种方法表示的队列，在队列不满的情况下，允许进队.进队时，首先让tail

加1,然后把新结点存放在由tail所指的数组元素中.在队列非空的情况下，允许出队.出队时,

首先让head加1,然后将存放在由head指出的数组元素中的结点取出，送到接受出队结点的变

量中.

下面给出C语言的说明及实现用第二种方法表示的队列的进队和退队的函数.

^defineMAXN26

charq[MAXN];

inthead=-l,tail=-l;

inten_queue(x)/*结点x进队*/

charx;

(

if(tail==MAXN-l)

return(l);

q[++tail]=x;

return(0);/*进队成功，返回0*/

)

intdc_queue(py)/*出队*/

char*p_y;

(

if(head==tail)

return(1);/*对空，不能出队，返回1*/

*P_y=q[++head];/*头指针加1,把队首结点送到指针

p_y所指的变量中*/

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

)

从图I.3.8可以看出，一旦出现tail=MAXNT时,尽管原来存放出队结点的数组元素已

空着，但却没有再被使用.所以，当tail=MAXNT时，队列不是真正的满,而是假满.这时，我们

可以采取卜面的处理方法.以充分利用已空着的数组元素.首先，当队列出现队空时,就把头

指针和尾指针置成队空的初始状态，即置headrail二T.另外,可采用两种极端方法:一是当

一个结点出队时,就把队列中所有的结点都依次向队首方向移动•个位置,并修改头指针和

尾指针;另一是当tai1=MAXNT且队列不是真正满时，把队列的所有结点都依次移到数组的最

前端,并修改头指针和尾指针.虽然这两种方法都能充分利用数组元素,但需要移动队列的所

有结点,这样做很麻烦且花费时间.为了克服这一缺点,我们下面引进更为实用的环形队列.

1.3.3环形队列

如果我们把表示队列的数组的元素q[0]和q[MAXNT]连接起来,形成一个环形的表,称

这样的环形表为环形队列(见图/.3.9).初始时,置队列空的初态为head=tail=0,如图®所

示.此时，如果连续进队三次,那么进队后的队列如图b所示.然后出队两次,则有如图c所示的

队列.

在队列不满的情况下,可以进队.当出现tail=hcad时，队列已满,此时不能再进队了，

如图c所示.在队列非空的情况下,可以出队.当出现headXail时，队列已空,此时不能再出队

了，如图e所示.由此可见,环形队列的队满和队空都有hcad=tail.

如上所述,环形队列的队满和队空都有headrail.因此，不能只用headfail来判断队

满或队空.此时,必须增加一个标志tag.在head=tail的情况下，由tag为0(或1)来表示队列空

(或满).根据环形队列的特点，下面给出实现进队和出队的函数.环形队列空的初始状态为

head=tail=0,且tag=0.

#defineMAXN26

cheirq[MAXN];

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

intenqueue(x)

charx;

(

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

return(l);/*队满，进队失败，返回1*/

tail=(tail+l)%MAXN;

q[tail]=x;

if(tail==hcad)tag=l;/*置堆满标志*/

return(0);/*进队成功，返回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;/*置队空标志*/

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

)

由于增加了一个标志tag,使得程序的语句增加了，判断条件也更杂了，这样将增加程

序的运行时间.在频繁执行进队和出队运算的情况下,如操作系统的作业排队和进程排队,将

大大地增加运行时间.为了尽量提高运行速度而减少执行时间,我们以•个结点所占用的存

贮空间为代价,来节省执行时间.实现的办法是在进队时，首先让tail加上1进行模MAXN运算

后，再存入tail.然后判别tail是否已赶上head:如果tail没有赶上head,那么就执行进队运

算;如果tail赶上head,尽管还有一个空的数组元素可以存放进队结点,但我们不允许新结点

进队，而是报告队满.引入上述机制后，可以把上面两个函数改写成如下的函数：

^defineMAXN26

charq[MAXN];

inthead=0,tai1=0;

intencq(x)

charx;

{

tail=(tail+l)%MAXN;

if(tail==head)

(

if(tail==0)