的每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用求幂函数。注意：本题中的输入a (i=0,1,?,n),x和n，输出为P (x )。通常算法的输入和输出可采用下列两种方式之一：
（1）通过参数表中的参数显式传递。 （2 ）通过全局变量隐式传递。
试讨论这两种方法的优缺点，并在本题算法中以你认为较好的一种方式实现输入和输出。 void polyvalue() {
int n,p,i,x,xp,sum; float a[]; float *p=a;
printf(\ scanf(\
printf(\ for(i=0;i<=n;i++) scanf(\ printf(\ scanf(\
p=a;xp=1;sum=0; //xp 用于存放x 的i 次方 for(i=0;i<=n;i++) {
sum+=xp*(*p++); xp*=x; }
printf(\ }//polyvalue
第二章 线性表
2．4 设线性表存于 a(1:arrsize)的前elenum 个分量中且递增有序。试写一算法，将 X 插入 到线性表的适当位置上，以保持线性表的有序性。
Status Insert_SqList(SqList &va,int x)//把x 插入递增有序表va 中 {
if(va.length+1>va.listsize) return ERROR; va.length++;
for(i=va.length-1;va.elem[i]>x&&i>=0;i--) va.elem[i+1]=va.elem[i]; va.elem[i+1]=x; return OK; }//Insert_SqList
2．6 已知线性表中的元素（整数）以值递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有大于mink且小于maxk的元素（若表中存在这样的元素），分析你的算法的时间复杂度（注意：mink和maxk是给定的两个参变量，它们的值为任意的整数）。Status Delete_Between(Linklist &L,int mink,int maxk)//删除元素递增排列的链表L中值大于mink 且小于maxk 的所有元素 { p=L;
while(p->next->data<=mink) p=p->next; //p 是最后一个不大于mink 的元素 if(p->next) //如果还有比mink 更大的元素 {
q=p->next;
while(q->data
}//Delete_Between
2．7 试分别以不同的存储结构实现线性表的就地逆置算法，即在原表的存储空间将线性表（a, a ..., a ）逆置为（a, a ,..., a ）。
（1） 以一维数组作存储结构，设线性表存于 a(1:arrsize)的前 elenum 个分量中。 （2）以单链表作存储结构。
void reverse(SqList &A)//顺序表的就地逆置 {
for(i=1,j=A.length;i
2．8 假设两个按元素值递增有序排列的线性表A和B，均以单链表作为存储结构，请编写算法，将A表和B表归并成一个按元素值递减有序排列的线性表C，并要求利用原表（即A表和B表的）结点空间存放表C。 while(pa||pb) {
if(pa->data
pc=pa;q=pa->next;pa->next=pre;pa=q; //将A 的元素插入新表 } else {
pc=pb;q=pb->next;pb->next=pre;pb=q; //将B 的元素插入新表 }
pre=pc; }
C=A;A->next=pc; //构造新表头 }//reverse_merge
分析:本算法的思想是,按从小到大的顺序依次把A 和B 的元素插入新表的头部pc 处,最后处理A 或B 的剩余元素.
2．9 假设有一个循环链表的长度大于1，且表中既无头结点也无头指针。已知s为指向链表某个结点的指针，试编写算法在链表中删除指针s所指结点的前趋结点。 Status Delete_Pre(CiLNode *s)//删除单循环链表中结点 s 的直接前驱 { p=s;
while(p->next->next!=s) p=p->next; //找到s 的前驱的前驱p p->next=s; return OK;
}//Delete_Pre
2．10 已知有单链表表示的线性表中含有三类字符的数据元素（如字母字符、数字字符和其它字符），试编写算法来构造三个以循环链表表示的线性表，使每个表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。Status LinkList_Divide(LinkList &L,CiList &A,CiList &B,CiList &C)//把单链表L的元素按类型分为三个循环链表.CiList 为带头结点的单循环链表类型. {
s=L->next;
A=(CiList*)malloc(sizeof(CiLNode));p=A; B=(CiList*)malloc(sizeof(CiLNode));q=B;
C=(CiList*)malloc(sizeof(CiLNode));r=C; //建立头结点 while(s) {
if(isalphabet(s->data)) {
p->next=s;p=s; }
else if(isdigit(s->data)) {
q->next=s;q=s; } else {
r->next=s;r=s; }
}//while
p->next=A;q->next=B;r->next=C; //完成循环链表 }//LinkList_Divide
2．11 设线性表A=(a , a ,?,a )，B= (b, b ,?,b )，试写一个按下列规则合并A、B为线性表C的算法，使得：
C= (a , b ,?,a , b , b ?,b ) 当m≤n时； 或者 C= (a , b ,?,a , b , a ?,a ) 当m>n时。
线性表A、B、C均以单链表作为存储结构，且C表利用A表和B表中的结点空间构成。注意：单链表的长度值m和n 均未显式存储。void merge1(LinkList &A,LinkList &B,LinkList &C)//把链表A 和B 合并为C,A 和B 的元素间隔排列,且使用原存储空间 {
p=A->next;q=B->next;C=A; while(p&&q) {
s=p->next;p->next=q; //将B 的元素插入 if(s) {
t=q->next;q->next=s; //如A 非空,将A 的元素插入 }
p=s;q=t; }//while }//merge1
2．12 将一个用循环链表表示的稀疏多项式分解成两个多项式，使这两个多项式中各自仅含奇次项或偶次项，并要求利用原链表中的结点空间来构成这两个链表。void Divide_LinkedPoly(LinkedPoly &L,&A,&B)//把循环链表存储的稀疏多项式L 拆成只含奇次项的A 和只含偶次项的B {
p=L->next;
A=(PolyNode*)malloc(sizeof(PolyNode)); B=(PolyNode*)malloc(sizeof(PolyNode)); pa=A;pb=B; while(p!=L) {
if(p->data.exp!=2*(p->data.exp/2)) {
pa->next=p;pa=p; } else {
pb->next=p;pb=p; }
p=p->next; }//while
pa->next=A;pb->next=B; }//Divide_LinkedPoly
2．14 设多项式P(x)采用课本中所述链接方法存储。写一算法，对给定的x值，求P(x)的值。float GetValue_SqPoly(SqPoly P,int x0)//求升幂顺序存储的稀疏多项式的值 {
PolyTerm *q; xp=1;q=P.data; sum=0;ex=0; while(q->coef) {
while(ex
return sum;
}//GetValue_SqPoly
第 3 章 限定性线性表——栈和队列
3．5 试写一个算法，判断依次读入的一个以@为结束符的字母序列，是否为形如‘序列1& 序列2’模式的字符序列。其中序列1和序列2 中都不含字符’&’，且序列2 是序列1的逆序列。例如，‘a+b&b+a’是属该模式的字符序列，而‘１+３&３－１’则不是。int
IsReverse()//判断输入的字符串中'&'前和'&'后部分是否为逆串,是则返回 1,否则返回0 {
InitStack(s);
while((e=getchar())!='&') push(s,e);
while((e=getchar())!='@') {
if(StackEmpty(s)) return 0; pop(s,c);
if(e!=c) return 0; }
if(!StackEmpty(s)) return 0; return 1; }//IsReverse
3．6 假设表达式由单字母变量和双目四则运算算符构成。试写一个算法，将一个通常书写形式且书写正确的表达式转换为逆波兰式。void NiBoLan(char *str,char *new)//把中缀表达式 str 转换成逆波兰式new {
p=str;q=new; //为方便起见,设str 的两端都加上了优先级最低的特殊符号 InitStack(s); //s 为运算符栈 while(*p) {
if(*p 是字母)) *q++=*p; //直接输出 else {
c=gettop(s);
if(*p 优先级比 c 高) push(s,*p); else {
while(gettop(s)优先级不比*p 低) {
pop(s,c);*(q++)=c; }//while
push(s,*p); //运算符在栈内遵循越往栈顶优先级越高的原则 }//else }//else p++; }//while
}//NiBoLan //参见编译原理教材
3．7 假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写相应的队列初始化、入队列和出队列的算法。 void InitCiQueue(CiQueue &Q)//初始化循环链表表示的队列Q {
Q=(CiLNode*)malloc(sizeof(CiLNode));