Question

数据结构课程实践题目求助！！！！急！！！！

1 请设计一个数据结构，实现多项式的操作，具体模式如下：
1） 通过键盘输入或者文件输入模式接受多项式，并识别出相关的多项式；
2） 建立多项式；
3） 完成多项式f(x) 的导数、积分运算；
4） 根据x的取值，求出多项式的值；
5） 实现两个多项式f(x)、h(x)的加法/减法、乘法；
6） 比较两个多项式f(x)、h(x)的值的大小，并给定其具体取值范围，f(x) > g(x)；
7) 建立一系列多项式，并实现3）~5）的操作。
要求： 设计出具体的数据结构、给出明确的算法思路、分析算法的具体时间/空间复杂性、编写出程序，完成具体的操作模式。

2 完成文档编辑程序的处理，具体要求：
1） 支持文本的插入、删除、修改；
2） 支持字符串的查询、修改；
3） 支持文本行的删除、替换；
4） 支持大文本的处理；
5） 支持文本的打印；
要求： 设计出具体的数据结构、给出明确的算法思路、分析算法的具体时间/空间复杂性、编写出程序，完成具体的操作模式。

Answer 1

#include <stdio.h>
#include <stdlib.h>

typedef struct LNode{
float coef;
int expn;
struct LNode *next;
}LNode, *LinkList, *Link;

Link MakeNode(float c, int e){
Link p;
p=(Link)malloc(sizeof(LNode));
p->coef=c; p->expn=e; p->next=NULL;
return p;
}

void InitPoly(LinkList &P){
P=MakeNode(0,-1);
}

void Create(LinkList &P){
Link rear;
float c; int e;
InitPoly(P);
rear=P;
printf("Input coef expn, (0 0)Exit\n");
while(1){
scanf("%f%d",&c,&e);
if(c==0) break;
rear->next=MakeNode(c,e);
rear=rear->next;
}
}

void PrintPoly(LinkList P){
Link p;
if(P==NULL)
printf("NULL\n");
else if(P->next==NULL)
printf("0\n");
else{
p=P->next;
while(p){
printf("%fX^%d",p->coef,p->expn);
p=p->next;
if(p && p->coef>0) printf("+");
}
printf("\n");
}
}

void Copy(LinkList P1, LinkList &P2){
Link p1, p2;
if(P1==NULL) return;
InitPoly(P2);
p1=P1->next;
p2=P2;
while(p1){
p2->next=MakeNode(p1->coef,p1->expn);
p1=p1->next; p2=p2->next;
}
}

void AddPoly(LinkList P1, LinkList P2, LinkList &P3){
Link q1,q2,q3;
if(!P1 || !P2) return;
InitPoly(P3);
q3=P3;
q1=P1->next; q2=P2->next;
while(q1&&q2){
if(q1->expn<q2->expn){
q3->next=MakeNode(q1->coef,q1->expn);
q3=q3->next; q1=q1->next;
}
else if(q1->expn>q2->expn){
q3->next=MakeNode(q2->coef,q2->expn);
q3=q3->next; q2=q2->next;
}
else{
if(q1->coef+q2->coef!=0){
q3->next=MakeNode(q2->coef+q1->coef,q2->expn);
q3=q3->next;
}
q1=q1->next;q2=q2->next;
}
}
while(q1){
q3->next=MakeNode(q1->coef,q1->expn);
q3=q3->next; q1=q1->next;
}
while(q2){
q3->next=MakeNode(q2->coef,q2->expn);
q3=q3->next; q2=q2->next;
}
}

void SubPoly(LinkList P1, LinkList P2, LinkList &P3){
Link q1,q2,q3;
if(!P1 || !P2) return;
InitPoly(P3);
q3=P3;
q1=P1->next; q2=P2->next;
while(q1&&q2){
if(q1->expn<q2->expn){
q3->next=MakeNode(q1->coef,q1->expn);
q3=q3->next; q1=q1->next;
}
else if(q1->expn>q2->expn){
q3->next=MakeNode(-(q2->coef),q2->expn);
q3=q3->next; q2=q2->next;
}
else{
if(q1->coef+q2->coef!=0){
q3->next=MakeNode(q2->coef-q1->coef,q2->expn);
q3=q3->next;
}
q1=q1->next;q2=q2->next;
}
}
while(q1){
q3->next=MakeNode(q1->coef,q1->expn);
q3=q3->next; q1=q1->next;
}
while(q2){
q3->next=MakeNode(-(q2->coef),q2->expn);
q3=q3->next; q2=q2->next;
}
}

void Qiudao(LinkList P1, LinkList &P2){
Link p1, p2;
if(P1==NULL) return;
InitPoly(P2);
p1=P1->next;
p2=P2;
while(p1){
p2->next=MakeNode((p1->coef)*(p1->expn),p1->expn-1);
p1=p1->next; p2=p2->next;
}
}

void jifenpolyn(LinkList P1, LinkList &P2){
Link p1, p2;
if(P1==NULL) return;
InitPoly(P2);
p1=P1->next;
p2=P2;
while(p1){

p2->next=MakeNode((p1->coef)/(p1->expn+1),p1->expn+1);
p1=p1->next; p2=p2->next;
}
}

void IS(LinkList P1, LinkList &P2,float c, int e){
if(P1==NULL) return;
Link q1,q2;
InitPoly(P2);
q1=P1->next;
q2=P2;
while(q1){
q2->next=MakeNode((q1->coef)*c,q1->expn+e);
q1=q1->next; q2=q2->next;
}
}
void Multiplypolynl(LinkList P1, LinkList P2, LinkList &P3,LinkList &P4){
Link q2;
q2=P2;
if(!P1 || !P2) return;
InitPoly(P3);
InitPoly(P4);
while(q2){
q2=q2->next;
IS(P1,P3,q2->coef,q2->expn);
AddPoly(P3,P4,P4 );
}
}

void Destroypolyn(LinkList P){
Link rear;
while(rear){
rear=P->next;
P->next=rear->next;
free(rear);}
free(P);
}

void Changepolyn(LinkList P,float c, int e){
Link rear;
while(rear->expn<e)
rear=rear->next;
rear->coef=c;

}

void Insert( LinkList P1,LinkList P3,float c, int e){
LinkList P2;
P2=MakeNode(c,e);
AddPoly(P1,P2,P3);}

#define N 12
void main(){
LinkList P[N]={NULL};
int i1,i2,i3,i4,menu,i;

while(1){
printf(" 0 -- Exit\n");
printf(" 1 -- Create\n");
printf(" 2 -- Print\n");
printf(" 3 -- Copy\n");
printf(" 4 -- Add\n");
printf(" 5 -- sub\n");
printf(" 6 -- qiudao\n");
printf(" 7 -- jifeng\n");
printf(" 8 -- multi\n");
printf(" 9 -- destory\n");
printf(" 10 -- change\n");
printf(" 11 -- insert\n");

printf(" Select: ");
scanf("%d", &menu);

switch(menu){
case 0: return;
case 1:
printf(" Address: ");
scanf("%d", &i1);
Create(P[i1]);
break;
case 2:
printf("\n");
for(i=0;i<N; i++){
printf(" P(%d)= ", i);
PrintPoly(P[i]);
}
printf("\n");
break;
case 3:
printf(" A-->B, Input A,B: ");
scanf("%d%d",&i1,&i2);
Copy(P[i1],P[i2]);
break;
case 4:
printf(" A+B=C, Input A,B,C: ");
scanf("%d%d%d",&i1,&i2,&i3);
AddPoly(P[i1],P[i2],P[i3]);
break;
case 5:
printf(" A-B=C, Input A,B,C: ");
scanf("%d%d%d",&i1,&i2,&i3);
SubPoly(P[i1],P[i2],P[i3]);
break;

case 6:
printf(" 对A求导, Input A,B:");
scanf("%d%d",&i1,&i2);
Qiudao(P[i1],P[i2]);
break;
case 7:
printf(" 对A积分 Input A,B:");
scanf("%d%d",&i1,&i2);
jifenpolyn(P[i1],P[i2]);
break;
case 8:
printf(" A*B=C, Input A,B,C: ");
scanf("%d%d%d%d",&i1,&i2,&i3,&i4);
Multiplypolynl(P[i1],P[i2],P[i3],P[i4]);
break;
case 9:
printf("销毁A Input A:");
scanf("%d",&i1);
Destroypolyn(P[i1]);
break;
case 10:
float c; int e;
printf("change Input A,e,c:");
scanf("%d%d%f",&i1,&e,&c);
Changepolyn(P[i1],c,e);
break;
case 11:
float d; int f;
printf("insert Input A,B,e,c: ");
scanf("%d%d%d%f",&i1,&i2,&f,&d);
Insert(P[i1],P[i2],c,e);
break;
default: ;
}
}
}