华东师大计算机应用技术2023年考研全程攻略

stChinaNormalUniversity

讲算机科学技术系

济算机医用赫

顿韭僦羹缕看谶

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

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

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

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

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

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

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

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

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

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

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

第一部分、专业课笔记

一、专业课笔记—《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、常见文件的打开方式：

(1)urM只读，为输入打开一个文本文件。

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

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

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

(1)打开文件：

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

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

Exit(0);}

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

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

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

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

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

(4)fread(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:\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、在数组中插入一个数：

(第一种方法)

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

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

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

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

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

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

入新数据文件fail,date文件结构同student.dat,同时在student.dat中删除该条记录。

Structstudent

{intnum;

Charname[20];

Intscore[8];

Intmark;

)

答题要点：

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

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

第一章线性表

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

在这里作较详细的介绍。

1.1线性表及其基本运算

1.1.1线性表

线性表是具有相同类型的n个数据元素kok,…Q的有限序列，记为(ko,k|,…kQ。元

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

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

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

元素；ki+1排在ki后面，我们称ki+I是ki的后继元素。ko没有前趋元素，心」没有后继元素;

当n22时，ko有后继元素k"％」有前趋元素％⑵当n》3时，k,(0<i<n-l)既有前趋

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

对于给定的线性表(koki,•••1),它的数据元素集合为{kok,…而数据元素之间

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

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

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

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

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

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

以是构造类型。数据项也称为字段,或称为域。

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

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

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

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

星期MonTueWedThuFriSatSun

温度15.516.016.515.715.016.116.4

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

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

字符串；工资是实数。

表1.1.2职工工资表

职工号姓名性别年龄工资

001Wangmale35160.50

002Caimale32150.00

003Zhangfemale28130.00

•,

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

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

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

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

1.1.2线性表的基本运算

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

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

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

1.查找

(1)查找线性表的第i(OWi<n-l)个结点。

(2)在线性表中查找值为x的结点。

2.插入

(1)把新结点插在线性表的第i(OWiWn-1)个位置上。

(2)把新结点插在值为x的结点的前面(或后面)

3.删除

(1)在线性表中删除第i(OWiWn-1)个结点。

(2)在线性表中删除值为x的结点。

4.其他运算

(1)统计线性表中结点的个数。

(2)打印线性表中所有结点。

(3)复制一份线性表。

(4)把一个线性表拆成几个线性表。

(5)把几个线性表合并成一个线性表。

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

1.2顺序存贮的线性表

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

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

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

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

设存放结点ki(OWiWn-1)的开始地址为aki，那么结点ki的地址aki可用整数i,以及地

址计算公式

aki=ako+i*s

计算出来。

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

WiWn-1)个结点特别方便。

如果用C语言的数组表示线性表(k0,ki,-kn.,),我们可使用如下的说明：

#defineMAXSIZE100

intlist|MAXSIZE];

intn;

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

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

ko,k|,…k»i依次存放在数组元素…中。这样，存放线性表各个结点的地

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

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

ttttt

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

有了上述的对应关系，可得到下面计算ki的地址的公式，这里我们假设s=sizeof(inl)：

因aki=&list[i]

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

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

1.2.1线性表的插入

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

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

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

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

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

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

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

位置上(即<0或i>n),则返回1；若户\1人*5比£(即线性表已满)，此时list数组没有存

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

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

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

i(OWi^n-1)个位置上，可用如下的调用语句：

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

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

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

n-\

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

i=0

均次数为

7J-1

£-i)

i=0

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

1

PO=Pl="=Pn-产----

n+\

1.2.2线性表的删除

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

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

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

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

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

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

放线性表当前结点个数的变量n的地址赋给指针变量p_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);

)

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

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

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

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

gpi=l.因为删除第i(OWiWn-l)位置上的结点需移动(n-i-1)个结点，所以移动结点的平

/=0

均次数为

Zp，("iT)

i=0

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

1

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

〃+1

那么上面的和式可改写为

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

一一

o~n2-~2

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

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

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

一般代数多项式可写成

ee>,

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

其中每个%(OWiWm)是A(x)的非零系数；次数q(OWiWm)是递减的，即e„>em^>->e{>e0

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

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

ftdefineMAXN100

typedefstructterm

{

floatcoef;

intexp;

}TERM;

TERMpoly[MAXN];

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

式可共享数组poly。

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

60502510

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

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

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

0123456789・・・MAXN-1

coef864217-63.・・

exp605025100605020・・・

ahatbhbtfree

图1.2.1多项式的存贮

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

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

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

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

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

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

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

和次数e构成的项存放到指针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].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);

)

可用如下的调用语句执行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)的各项的

次数都不想同时,执行循环的次数最多,共执行(m+n)次,故其执行时间最多为0(m+n);第二和

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

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

1.3顺序存贮的栈和队列

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

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

1.3.1栈及其基本运算

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

允许插入和删除的一端为援匹若给定栈S=(s。,Si,…,sQ,则s。是栈底结点,S,T是栈顶结

点,si是在sNOWiWnT)之上,栈$的结构图如图1.3.1所示.通常称栈的插入为进栈，•称栈的

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

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

栈顶

栈底

图1.3.1栈的结构

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

时栈的变化情况.

在下面实现栈的运算时,采用如图7.3.4所示的第二种表示方法.对于第一种栈的表示

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

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

#defineMAXN26

charstack[MAXN];

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

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

charx;

(

if(top>=MAXN)

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

stack[top++]=x;

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

}

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

char*p_y；

(

if(top==0)

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

*P_y=stack[-top];

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

)

1.3.2队列及其基本运算

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

一端为队首，•称允许插入的一端为队尾.有时称队列的插入为进队;称队列的删除为幽•

若给定的队列为Q二(qo,qi,…,qn-i),则qo是队首结点,是队尾结点,qi在qi+i之前,qi+i

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

所以队列具有先进先出的特性.因此,队列也称先进先出表,简称FIFOOirstInFirstOut)

出队一qOq1...qiqi+1...qn-1.---------进队

队首队尾

图1.3.6队列Q的结构

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

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

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

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

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

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

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

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

的情况.

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

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

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

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

仍然是tail=MAXNT.图1.3.史苗述了用第二种表示方法时进队和出队的情况.

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

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

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

量中.

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

ttdefineMAXN26

charq[MAXN];

inthead=-l,tail=-l;

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

charx;

(

if(tail二二MAXN-1)

return(1);

q[++tail]=x;

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

)

intde_queue(p_y)/*出队*/

char*p_y;

if(head-tail)

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

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

p_y所指的变量中*/

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

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

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

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

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

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

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

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

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

1.3.3环形队列

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

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

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

队列.

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

如副所示.在队列非空的情况下,可以出队.当出现head=tail