数据结构2.39——采用顺序存储结构编写求稀疏多项式的算法

/*2.39采用存储量同多项式项数m成正比的顺序存储结构编写求稀疏多项式的算法，并分析算法的时间复杂度*/ #include <stdlib.h> #include <stdio.h> #include <math.h> #define OK 1 #define ERROR 0 typedef int Status; typedef struct {//项结构 int coef;//系数 int exp;//指数 }Ployn; typedef struct {//多项式结构（顺序表） Ployn* elem; int length; }SqPloy; Status InitSqPloy(SqPloy& L) { //初始化多项式 L.elem = (Ployn*)malloc(100 * sizeof(Ployn)); if (!L.elem) return ERROR; L.length = 0; return OK; }//InitSqPloy Status CreatSqPloy(SqPloy& L, int m) { //创建一个m项的多项式 Ployn* p = L.elem;//指针p指向多项式第一项 printf("逐项请输入稀疏多项式的系数和指数，英文逗号隔开\n"); for (int i = 0; i < m; i++) { //依次输入每项的系数和指数 scanf_s("%d,%d", &(p->coef), &(p->exp)); p++; L.length++; } return OK; }//CreatSqPloy Status ShowSqPloy(SqPloy& L) { //展示多项式 Ployn* p = L.elem; printf("P(X) ="); for (int i = 0; i < L.length; i++){ printf("%d x exp（%d） ",p->coef,p->exp); p++; } printf("\n"); return OK; }//ShowSqPloy int Calculate(SqPloy& L, int x0) { //计算并返回多项式的值 int a; int s = 0; Ployn* p = L.elem; for (int i = 0; i < L.length; i++){ a = p->coef * int(pow(x0, p->exp)); p++; s += a; } return s; }//Calculate int main() { SqPloy L; InitSqPloy(L); CreatSqPloy(L, 3);//以三项式为例 ShowSqPloy(L); printf("多项式的结果为:%d",Calculate(L, 3));//给x0赋值位3，计算多项式 }

运行结果：

Calculate函数中，循环体执行次数为顺序表长度，时间复杂度 O（n）=n。