2.6 实训例题
2.6.1 实训例题1：有序顺序表的建立及查找
【问题描述】
编写算法，以输入的整数序列（34,66,-21,73,84,-3,6,16）作为线性表各元素的值，创建一按元素值升序排列的顺序表，并能对用户的输入值x给出是否在表中的判断，若表中有此值，则将其删除。
【基本要求】
对于输入序列构造相应的顺序表（升序排列），该过程涉及数据元素（在有序表中）的插入；对于用户的输入值x，给出是否在表中的判断，此过程涉及表的查找；若表中有值x，则将其删除，涉及顺序表的删除操作。
• 功能：
（1）初始化顺序表；
（2）有序表的插入；
（3）在有序表中查找数据元素；
（4）删除有序表的某一元素；
（5）输出顺序表各元素的值。
• 输入：给定的整数序列（34,66,-21,73,84,-3,6,16）及要删除的值。
• 输出：顺序表中（删除指定值后）各元素的值。
【测试数据】
输入（第一组）：34,66,-21,73,84,-3,6,16
要删除的值：6
预期的输出结果是：
-21 -3 6 16 34 66 73 84
及
-21 -3 16 34 66 73 84
输入（第二组）：34,66,-21,73,84,-3,6,16
要删除的值：18
预期的输出结果是：
-21 -3 6 16 34 66 73 84
及
18 does not exit in the list.
-21 -3 6 16 34 66 73 84
【数据结构】
顺序表的定义如下。
#define MaxSize 20
typedef struct seqlist
{ int elem[MAXSIZE];
int listlength;
}SeqList;
【算法思想】
初始化顺序表，循环输入整数，并将其插入到有序顺序表中，输出顺序表各元素的值。输入要删除的值，在有序表中查找该值，如果存在，则将其删除，再次输出顺序表各元素的值。
【模块划分】
① 初始化顺序表InitList。
② 将元素插入有序表InsList。
③ 在有序表中查找数据元素InList。
④ 删除有序表的某一元素DelList。
⑤ 输出顺序表各元素的值Print。
⑥ 主函数main。
【源程序】
#define MaxSize 20
typedef struct seqlist
{ int elem[MaxSize];
int listlength;
}SeqList;
void InitList(SeqList *l) /*初始化顺序表*/
{ l->listlength=0;
}/*InitList */
void Print(SeqList l) /*输出顺序表各元素的值*/
{ int i;
for(i=0;i<l.listlength;++i)
printf("%d ",l.elem[i]);
} /*Print*/
int InList(SeqList l,int x) /*在有序表中查找元素x */
{ int i=0;
while (i<l.listlength && l.elem[i]<x)
++i;
if (i<l.listlength)
if(x==l.elem[i]) return (i);
return (-1);
} /*InList*/
void InsList(SeqList *l,int x) /*将元素x插入有序表*/
{ int i=0,j;
while (i<l->listlength && x>l->elem[i])
i++;
for(j=l->listlength-1;j>=i;--j)
l->elem[j+1]=l->elem[j];
l->elem[i]=x;
(l->listlength)++;
}/*InsList*/
void DelList(SeqList *l,int i) /*删除有序表的第i个元素*/
{ int j;
if (i<0 || i>l->listlength-1)
{ printf("\nIndex error ");
return;
}
for(j=i+1;j<=l->listlength-1;++j)
l->elem[j-1]=l->elem[j];
l->listlength--;
}/*DelList */
main()
{ SeqList list;
int index,element,x;
InitList(&list);
printf("Enter the first value in the list: ");
scanf("%d",&element);
printf("Enter the others in the list:");
while(element!=0)
{ InsList(&list,element);
scanf("%d,",&element);
}
Print(list);
printf("Enter the value to be deleted: ");
scanf("%d",&x);
index=InList(list,x);
if(index==-1)
printf("%d does not exit in the list. \n ",x);
else
DelList(&list,index);
Print(list);
}/*main*/
【测试情况】
第一组数据：
Enter the first value in the list: 34
Enter the others in the list: 66,-21,73,84,-3,6,16,0
-21 -3 6 16 34 66 73 84
Enter the value to be deleted: 6
-21 -3 16 34 66 73 84
第二组数据：
Enter the first value in the list: 34
Enter the others in the list: 66,-21,73,84,-3,6,16,0
-21 -3 6 16 34 66 73 84
Enter the value to be deleted: 18
18 does not exit in the list.
-21 -3 6 16 34 66 73 84
【心得】
学生可以根据程序在计算机上调试运行，并结合自己在上机过程中遇到的问题和解决方法的体会，写出调试分析过程、程序使用方法和测试结果，提交实训报告。
2.6.2 实训例题2：多项式的表示和相加
【问题描述】
在数学上，一个一元多项式Pn(x)可按升幂的形式写成
Pn(x)=p0+p1x+p2x2+p3x3+…+pnxn
此多项式可以由n+1个系数唯一确定。因此，对应地可以用一个线性表P来表示
P=(p0,p1,p2,…,pn)
多项式中每项的指数就是相应系数的序号。
假设Qm(x)是一个一元多项式，则它也可以用一个线性表Q来表示，即
Q=(q0,q1,q2,…,qm)
若m<n，则两个多项式相加的结果Rn(x)=Pn(x)+Qm(x)，也可以用线性表R来表示
R=(p0+q0,p1+q1,p2+q2,…,pm+qm,pm+1,…,pn)
问当多项式中存在大量的零系数时，是选择顺序存储结构还是链式存储结构？写算法实现一元多项式的相加。
【基本要求】
对于线性表P、Q和R可以采用顺序存储结构，也可以采用链式存储结构。使用顺序存储结构可以使多项式相加的算法十分简单，即p[0]（q[0]）存储系数p0（q0），p[1]（q[1]）存储系数p1（q1）,…,p[n]（q[n]）存储系数pn（qn），p、q对应单元的内容相加即可。但是，当多项式中存在大量的零系数时，这种表示方式就会浪费大量的存储空间。因此，应采用链式存储结构表示多项式，多项式中的每一个非零系数项构成链表中的一个结点（系数项和指数项），而对于系数为零的项则无须表示。
如图2-16所示为两个多项式的单链表，分别表示多项式A14(X)=9+6X+8X9+3X14与多项式B9(X)=7X+21X7-8X9。
图2-16 单链表表示的多项式
• 功能：求两个单链表表示的多项式的和。
• 输入：两个多项式每项的系数与指数。
• 输出：和多项式的系数与指数。
【测试数据】
输入：3,14 8,9 6,1 9,0与-8,9 21,7 7,1，预期的输出是9,0 13,1 21,7 3,14。
【数据结构】
单链表结点、指针类型定义如下。
typedef struct PNode
{ int exp； /*指数为整数*/
float coef； /*系数为实数*/
struct PNode *next；
}PolyNode，*PolyList；
【算法思想】
多项式相加的原则是两个多项式中所有指数相同的项的对应系数相加，若和不为零，则构成“和多项式”中的一项，所有指数不相同的项均复制到“和多项式”中。以单链表作为存储结构，“和多项式”中的结点无须另外生成，可由多项式A、多项式B对应的单链表polya、polyb中的结点构成（和多项式链表可由polya指向）。
设pa、pb分别指向多项式A、B的一项（单链表polya、polyb中的一个结点），比较pa、pb所指结点的指数项，有如下3种情况。
（1）若pa->exp<pb->exp，则结点pa所指的结点应是“和多项式”中的一项，令指针pa后移。
（2）若pa->exp>pb->exp，则结点pb所指的结点应是“和多项式”中的一项，将pb所指结点插入在pa所指结点之前，且令指针pb在原来的链表上后移。
（3）若pa->exp=pb->exp，则将两个结点中的系数相加，当和不为零时修改pa所指结点的系数域，释放pb结点；若和为零，则和多项式中无此项，从A中删去pa所指结点，同时释放pa和pb所指的结点。
按以上运算规则对图2-16表示的两个多项式，得到的和多项式链表如图2-17所示。其中孤立结点代表被释放的结点。
图2-17 运算后的“和多项式”
【模块划分】
① 建立带头结点的单链表Create，单链表是依指数升序排列的有序表，所输入数据（系数，指数）是依指数为降序的序列。
② 求单链表polya与单链表polyb对应多项式的和PolyAdd。
③ 输出单链表每个结点两个数据域的值（多项式每项系数与指数）Print。
④ 主函数main，调用Create建立单链表polya，调用Create建立单链表polyb，调用PolyAdd求polya与polyb对应多项式的和，调用Print输出和多项式每项的系数与指数（依指数升序）。
【源程序】
typedef struct PNode
{ int exp; /*指数为整数*/
float coef;/*系数为实数*/
struct PNode *next;
} PolyNode, *PolyList;
PolyList create() /*建立带头结点的单链表*/
{
PolyList h,p;
float c;
int e;
h=(PolyList)malloc(sizeof(PolyNode));
h->next=NULL;
printf("\nEnter coef and exp:");
scanf("%f,%d",&c,&e);/*输入系数、指数*/
while (e !=-1)
{
p=(PolyList)malloc(sizeof(PolyNode));
p->coef=c;p->exp=e;
p->next=h->next;
h->next=p;
printf("Enter coef and exp:");
scanf("%f,%d",&c,&e);
}
return(h);
} /*create*/
void Print(PolyList h) /*输出单链表的值*/
{
PolyList p;
p=h->next;
printf("\n");
while(p!=NULL)
{
printf("%g,%d ",p->coef,p->exp);
p=p->next;
}
}/*Print*/
void PolyAdd(PolyList polya,PolyList polyb) /*求单链表polya与polyb对应多项式的和*/
{
PolyList pa,pb,pre,temp;/* pre指向和多项式链表的尾结点，temp 为临时指针*/
float sum;
pa=polya->next;
pb=polyb->next;
pre=polya;
while (pa!=NULL && pb!=NULL) /*当两个多项式均未扫描结束时*/
{
if(pa->exp<pb->exp) /*将pa结点加入到和多项式中*/
{
pre->next=pa;
epr=pre->next;
pa=pa->next;
}
else if (pa->exp==pb->exp) /*指数相同，则相应的系数相加*/
{
sum=pa->coef+pb->coef;
if(sum!=0)
{
pa->coef=sum;
pre->next=pa;pre=pre->next;
pa=pa->next;
temp=pb;pb=pb->next;free(temp);
}
else /*若系数和为零，则释放pa和pb所指结点*/
{
temp=pa->next;free(pa);pa=temp;
temp=pb->next;free(pb);pb=temp;
}
}
else /*将pb所指结点加入到和多项式中 */
{
pre->next=pb;pre=pre->next;
pb=pb->next;
}
}
if(pa!=NULL) /*polya中还有剩余的结点*/
pre->next=pa;
else /* polyb中还有剩余的结点*/
pre->next=pb;
free(polyb);
} /*PolyAdd */
main()
{
PolyList pa,pb;
pa=create();
pb=create();
PolyAdd(pa,pb);
Print(pa);
}_/*main*/
【测试情况】
Enter coef and exp: 3,14
Enter coef and exp: 8,9
Enter coef and exp: 6,1
Enter coef and exp: 9,0
Enter coef and exp: -1,-1
Enter coef and exp:-8,9
Enter coef and exp: 21,7
Enter coef and exp: 7,1
Enter coef and exp: -1,-1
9,0 13,1 21,7 3,14
【心得】
学生可以根据程序在计算机上调试运行，并结合自己在上机过程中遇到的问题和解决方法的体会，写出调试分析过程、程序使用方法和测试结果，提交实训报告。