1、清华大学出版社2008年12月根据问题需求功能目标，此模型的所需的主要处理操作有插入、删除、查找和修改等基本操作。所以，现用抽象数据类型bookList表示问题模型，其逻辑结构与基本操作的定义如下：（1）逻辑结构bookList=（ D, r ）D=bi| bi为bookType类型的元素，i=1,2,3, ., n，n0r= | i=1,2, n-1, n0 （2）基本操作初始化操作函数：InitBookList（&BL）。初始条件：图书表BL不存在。操作结果：构造一个空的图书表BL。求图书表长度bookListLength（BL）。图书表BL已存在。返回图书表BL中所包含的数据元素（图书）
2、的个数。取图书表中元素getBook（BL, i, &b）。图书表BL已存在，且1ibookListLength（BL）。用b返回图书表BL中的第i个数据元素的值。按编号查找locateById（BL, id）。图书表BL已存在，id是给定的一个图书编号。返回图书表BL中图书编号为id的数据元素的位序，若这样的数据元素不存在，则返回0。按编号查找locateByName（BL, i, name）。图书表BL已存在，且1ibookListLength（BL），name是给定的一个图书名。从图书表BL中第i个元素开始，查找图书名与给定name相等的第一个元素，若找到则返回其位序，否则返回0。插入图
3、书insertBook（&BL, i, b）。图书表BL已存在，且1ibookListLength（BL）+1。在图书表BL的第i个位置上插入一个值为b的新元素，使线性表的长度增1。删除操作deleteBook（&BL, i, &线性表L已存在，1ilistLength（L）。删除图书表BL的第i个数据元素，并用b返回其值，使线性表的长度减1。11. （1）【解】函数体内为简单语句，时间复杂度为T（n）=O（1）【解】选取的基本语句为“if（aiak） k=i;”其执行频度为n-1，时间复杂度为T（n）=O（n）。【解】选取的基本语句为最内层的循环体语句“total+=aij;”，其执行频度为
4、n（n+1）/2，时间复杂度为T（n）=O（n2）。【解】选取的基本语句为最内层的循环体语句“cij+=aik*bkj;”，其执行频度为n3，时间复杂度为T（n）=O（n3）。（5）【解】函数有两个并列的循环，其问题规模分别为n和m，对于第一个for循环选取的基本语句为“if（aiamax） max=i;”，其执行频度为n-1；对于第二个for循环选取的基本语句为“if（bibmin） min=i;”，其执行频度为m-1。所以该函数的时间复杂度为T（n,m）=O（n+m）。（6）【解】选取的基本语句为while的循环体，其执行频度为max，时间复杂度为T（n）=O（）。12. 【解】算法（1）
5、中有两个并列的循环，每个循环的循环体语句执行次数均为n，故该函数的语句频度为2n。算法（2）只用了一个循环，其循环体语句执行次数为n，即该函数的语句频度为n。所以算法（1）与算法（2）相比较，算法（1）的时间效率更好。但它们的时间复杂度都为O（n），这说明：随着n值的增大，这两个函数执行时间的增长率相同，都是线性增长的。13. 【解】由题意，设计程序如下：#include stdlib.hstruct stuInfo int num; char name18; int score;void inputInfo（struct stuInfo stus, int n） /输入n个同学信息存于数组s
6、tus中 int i; for（i=0;in;i+） printf（输入%d个学生信息：n, i+1）; printf（学号：）; scanf（%d, &stusi.num）;姓名：%s, stusi.name）;成绩：stusi.score）; void sortByScore（struct stuInfo stus, int n） /将数组stus中n个同学信息按成绩进行递减排序 int i,j,k; struct stuInfo temp;n-1; k=i; for（j=i+1;jstusk.score） k=j; if（k!=i） temp=stusi; stusi=stusk;stu
7、sk=temp;void outputInfo（struct stuInfo stus, int n） /输出数组stus中n个同学信息报表%6s %17s %6sn, 学号姓名成绩）；%6d %17s %6dn, stusi.num, stusi.name, stusi.score）;int main（） int n; struct stuInfo *stus;输入学生数:n）; stus=（struct stuInfo*）malloc（n*sizeof（struct stuInfo）; if（!stus） printf（内存空间溢出！ return -2; inputInfo（stus,
8、n）; sortByScore（stus, n）; outputInfo（stus, n）; system（pause14.【解】由题意，函数设计如下：Status TriArea（double a, double b, double c, double &area） double s; if（a=0|b=0|c=0） return ERROR; if（a+b=c|a+c=b|b+cnext=p-next; p-next=s; （2）q=p-next=q- free（p）;（3）q-next=L- L-next=q; L-next=NULL（4）q-next=L; L=q; L=NULL 9.
9、 （1）s-next；s-pre=p; p-next-pre=s;（2）s-pre=p-pre; s-next=p;pre-（3）q=p- p- q- free（q）;（4）q=ppre=q- q-（5）p-next =p-pre= p- free（p）;（6）s-pre=L;pre =s;10. 略11. 【解】算法如下所示： void union（List La,List Lb,List &Lc） int i=1,j=1,k=1,m; LElemType x,y,e; while（!listEmpty（La）&!listEmpty（Lb） getElem（La,i,x）; getElem（
10、Lb,j,y）; if（xy） listInsert（Lc,k,x）; i+; else listInsert（Lc,k,y）; j+; k+;if（listEmpty（La） for（m=j;m=0; i-） /查找插入位置，并进行元素后移 if（enext= NULL; while（p） q=p- p=q;15.【解】算法如下所示：int count（LinkList L, LElemType x） int n=0; LNode *p; while（p!=NULL） if（p-data= =x） n+; p=p- return n;16.【解】算法如下所示：void delinsert（L
11、inkList &L） LNode *p,*pre,*q;p=L- /p是链表的工作指针 pre=L; /pre指向链表中数据域最小值结点的前驱 q=p; /q指向数据域最小值结点，初始假定是首元结点 while（p-next!=NULL） if（p-datadata） /找到新的最小值结点 pre=p; p=p- if（q!=L-next） /若最小值是第一元素结点，则不需再操作 pre- /将最小值结点从链表上摘下 /将q结点插到头结点之后17. 【解】该算法的时间复杂度为O（n2），而算法2-16的时间复杂度为O（n），显然算法2-16的效率更高。18. 【解】不带头结点的单链表的插入操
12、作listInsert（&L, i, e）和删除操作listDelete（&L, i, &e）的算法如下：Status listInsert（LinkList &L, int i, LElemType e） /在不带头结点单链表L的第i个位置插入一个值为e的结点 LNode *p=L,*q; /p用于查找第i-1个结点，初始指向头结点；q用于指向欲插入结点 int j=1; if（i=1）q=（LNode*）malloc（sizeof（LNode）; /生成新结点q） return OVERFLOW; q-data=e; while （jnext） if（j=i-1） /若p所指结点第j个结点
13、为第i-1个结点时，在其后插入新结点 q=（LNode*）malloc（sizeof（LNode）; /将e赋给新结点的数据域 else return ERROR; /第i-1个结点不存在，插入位置不正确Status listDelete（LinkList &L, int i, LElemType &e） /删除不带头结点单链表L的第i个元素 L=L- while（jdata; /由e返回删除元素的值若单链表带有头结点，则在首元结点的位置上插入新结点或者是删除首先结点的情况与在链表中间位置插入新结点或者是删除中间某个结点的情况是相同的，可以统一处理，但若单链表不带头结点，则在首元结点的位置上插
14、入新结点或者是删除首先结点的情况需要特殊处理，由此可见头结点的好处。19. 【解】算法如下：int listLength（LinkList L） /求循环单链表L的长度 LNode *p=L; /p指向头结点 int j=0; /j用于计数，表示p所指结点的位序=L） /p所指结点存在 /指针后移，指向其后继 /计数器加1 return j;Status listEmpty（LinkList L） /循环单链表的判空操作 if（L-next=L） return TRUE; else return FALSE;20.【解】具体算法如下：Status swap（DLNode *p） DLNode
15、*q；next=p-prior） return ERROR;prior= p;prior= p-prior;prior-prior=q;21. 【解】算法如下。void setUnion（mySetType &A, mySetType B） /集合的并集运算，实现A=AB int i,len1,len2,e; len1=listLength（A）; len2=listLength（B）; for（i=1;=len2;i+） getElem（B,i,e）;locateElem（A, e） listInsert（A, +len1, e）;void setIntersection（mySetType
16、 A, mySetType B, mySetType &C） /集合交集运算，实现C=AB int i,e,len,k=0; clearList（C）; k=0; /集合C清空；用k保存当前集合C的长度 len=listLength（A）; i while（pb!=NULL） pa=La- while（pa!=NULL&pa-data!=pb-data） pa=pa- if（pa=NULL） s=（LinkList） malloc （sizeof（LNode）;data=pb-next=La- La- pb=pb-23. 【解】一元多项式的创建操作、输出操作及测试主函数的参考算法如下： voi
17、d CreatPoly（Poly &L, int n） /一元多项式的创建操作，其中n为一元多项式的项数 int i,coef,expn; Poly p,s; L=（Poly）malloc（sizeof（struct PNode）;next=NULL; p=L;=n;input %dth coef:,i）;,&coef）;input %dth expn:expn）; s=（Poly）malloc（sizeof（struct PNode）;coef=coef;exp=expn;p=s; void OutputPoly（Poly L） /一元多项式的输出操作 int flag=1; /flag用来
18、是否为第一项的标识 Poly p; while（p） if（flag） printf（%dX%d,p-coef,p-exp）; flag=0; else printf（%+dX%d int main（） Poly La,Lb;Creat Poly La:t Input the number of items of La: CreatPoly（La,n）;nLa（x）= OutputPoly（La）;Creat Poly Lb:tInput the number of items of Lb: CreatPoly（Lb,n）;nLb（x）= OutputPoly（Lb）; PolyAdd（La,Lb）;Lc（a）=La（x）+Lb（x）= syste
