一元稀疏多项式的计算

2、一元稀疏多项式的计算(*)
任务：能够按照指数升序排列建立并输出多项式；能够完成两个多项式的相加、相减，并将结果输出；
要求：以链式存储结构实现多项式。

实现这个任务可以依次考虑以下几个步骤：

1. 定义链式存储结构

多项式的链式存储结构可以由三个部分组成：系数、指数和指向下一项的指针。因此，我们可以定义一个结构体来表示单项式：

typedef struct Node {
    float coef; // 系数
    int exp; // 指数
    struct Node *next; // 指向下一项的指针
} PolyNode, *PolyPtr;

2. 创建并输出多项式

输入多项式可以由用户自行输入，也可以从文件中读取。这里以用户自行输入为例。我们可以定义一个函数来创建并输出多项式：

PolyPtr createPoly() {
    PolyPtr head = (PolyPtr)malloc(sizeof(PolyNode)); // 头结点
    head->next = NULL; // 初始化为空表

    int exp;
    float coef;
    PolyPtr rear = head; // 尾指针，初始指向头结点

    int n;
    printf("输入项数:\n");
    scanf("%d", &n);
    printf("请按项的指数递增的顺序输入每一项的系数和指数（用空格分隔）:\n");
    for (int i = 1; i <= n; ++i) {
        scanf("%f%d", &coef, &exp);
        if (coef != 0) { // 系数不为0才需要加入多项式
            PolyPtr p = (PolyPtr)malloc(sizeof(PolyNode));
            p->coef = coef;
            p->exp = exp;
            p->next = NULL;
            rear->next = p;
            rear = p; // 移动尾指针
        }
    }

    return head;
}

void printPoly(PolyPtr poly) {
    PolyPtr p = poly->next; // 第一个非零项
    if (p == NULL) { // 处理多项式为空的情况
        printf("0\n");
        return;
    }
    printf("%.2fx^%d", p->coef, p->exp); // 输出第一项
    p = p->next; // 移动指针
    while (p != NULL) {
        printf(" + %.2fx^%d", p->coef, p->exp);
        p = p->next;
    }
    printf("\n");
}

3. 实现多项式加法和减法

根据多项式加法的基本原理，我们可以依次扫描两个多项式，将指数相同的项的系数相加即可。对于指数不同的项，因为多项式是按照指数递增的方式存储的，所以可以直接将较小的指数所对应的项先输出，并将指针后移即可。最后，如果某个多项式还有剩余的项，也需要将它们直接输出。

PolyPtr addPoly(PolyPtr p1, PolyPtr p2) {
    PolyPtr head = (PolyPtr)malloc(sizeof(PolyNode)); // 头结点
    head->next = NULL; // 初始化为空表

    PolyPtr rear = head; // 尾指针，初始指向头结点
    PolyPtr t1 = p1->next; // p1的第一个非零项
    PolyPtr t2 = p2->next; // p2的第一个非零项

    while (t1 != NULL && t2 != NULL) { // 两个多项式都还有未处理的项
        if (t1->exp == t2->exp) { // 两个多项式当前处理的项的指数相同
            float sum = t1->coef + t2->coef;
            if (sum != 0) { // 系数和不为0才需要加入多项式
                PolyPtr p = (PolyPtr)malloc(sizeof(PolyNode));
                p->coef = sum;
                p->exp = t1->exp;
                p->next = NULL;
                rear->next = p;
                rear = p; // 移动尾指针
            }
            t1 = t1->next; // 移动指针
            t2 = t2->next;
        } else if (t1->exp < t2->exp) { // p1的当前项的指数较小，直接将其加入多项式
            PolyPtr p = (PolyPtr)malloc(sizeof(PolyNode));
            p->coef = t1->coef;
            p->exp = t1->exp;
            p->next = NULL;
            rear->next = p;
            rear = p; // 移动尾指针
            t1 = t1->next; // 移动指针
        } else { // p2的当前项的指数较小，直接将其加入多项式
            PolyPtr p = (PolyPtr)malloc(sizeof(PolyNode));
            p->coef = t2->coef;
            p->exp = t2->exp;
            p->next = NULL;
            rear->next = p;
            rear = p; // 移动尾指针
            t2 = t2->next; // 移动指针
        }
    }

    // 将剩余的项加入多项式
    while (t1 != NULL) {
        PolyPtr p = (PolyPtr)malloc(sizeof(PolyNode));
        p->coef = t1->coef;
        p->exp = t1->exp;
        p->next = NULL;
        rear->next = p;
        rear = p; // 移动尾指针
        t1 = t1->next; // 移动指针
    }

    while (t2 != NULL) {
        PolyPtr p = (PolyPtr)malloc(sizeof(PolyNode));
        p->coef = t2->coef;
        p->exp = t2->exp;
        p->next = NULL;
        rear->next = p;
        rear = p; // 移动尾指针
        t2 = t2->next; // 移动指针
    }

    return head;
}

PolyPtr subPoly(PolyPtr p1, PolyPtr p2) {
    PolyPtr head = (PolyPtr)malloc(sizeof(PolyNode)); // 头结点
    head->next = NULL; // 初始化为空表

    PolyPtr rear = head; // 尾指针，初始指向头结点
    PolyPtr t1 = p1->next; // p1的第一个非零项
    PolyPtr t2 = p2->next; // p2的第一个非零项

    while (t1 != NULL && t2 != NULL) { // 两个多项式都还有未处理的项
        if (t1->exp == t2->exp) { // 两个多项式当前处理的项的指数相同
            float diff = t1->coef - t2->coef;
            if (diff != 0) { // 系数差不为0才需要加入多项式
                PolyPtr p = (PolyPtr)malloc(sizeof(PolyNode));
                p->coef = diff;
                p->exp = t1->exp;
                p->next = NULL;
                rear->next = p;
                rear = p; // 移动尾指针
            }
            t1 = t1->next; // 移动指针
            t2 = t2->next;
        } else if (t1->exp < t2->exp) { // p1的当前项的指数较小，直接将其加入多项式
            PolyPtr p = (PolyPtr)malloc(sizeof(PolyNode));
            p->coef = t1->coef;
            p->exp = t1->exp;
            p->next = NULL;
            rear->next = p;
            rear = p; // 移动尾指针
            t1 = t1->next; // 移动指针
        } else { // p2的当前项的指数较小，直接将其加入多项式
            PolyPtr p = (PolyPtr)malloc(sizeof(PolyNode));
            p->coef = -t2->coef; // 注意，这里要取负数
            p->exp = t2->exp;
            p->next = NULL;
            rear->next = p;
            rear = p; // 移动尾指针
            t2 = t2->next; // 移动指针
        }
    }

    // 将剩余的项加入多项式
    while (t1 != NULL) {
        PolyPtr p = (PolyPtr)malloc(sizeof(PolyNode));
        p->coef = t1->coef;
        p->exp = t1->exp;
        p->next = NULL;
        rear->next = p;
        rear = p; // 移动尾指针
        t1 = t1->next; // 移动指针
    }

    while (t2 != NULL) {
        PolyPtr p = (PolyPtr)malloc(sizeof(PolyNode));
        p->coef = -t2->coef; // 注意，这里要取负数
        p->exp = t2->exp;
        p->next = NULL;
        rear->next = p;
        rear = p; // 移动尾指针
        t2 = t2->next; // 移动指针
    }

    return head;
}

最后，我们可以将这些函数整合起来，演示多项式的创建、输出、加法和减法：

int main() {
    PolyPtr p1 = createPoly();
    PolyPtr p2 = createPoly();

    printf("p1 = ");
    printPoly(p1);
    printf("p2 = ");
    printPoly(p2);

    printf("p1 + p2 = ");
    printPoly(addPoly(p1, p2));

    printf("p1 - p2 = ");
    printPoly(subPoly(p1, p2));

    return 0;
}

你可以看下这个问题的回答https://ask.csdn.net/questions/7670868
你也可以参考下这篇文章：（1）顺序表的操作 ① 输入一组整型元素序列，建立线性表的顺序存储结构。 ② 实现该线性表的遍历。 ③ 在该顺序表中查找某一元素,查找成功显示查找元素，否则显示查找失败。 ④ 在该顺序表中删除或插入指
除此之外, 这篇博客: 设计一个程序，采用交互方式建立一个无向图的邻接表表示，并输出该图的深度优先搜索遍历得到的顶点序列。中的 题目2：设计一个程序，采用交互方式建立一个无向图的邻接表表示，并输出该图的深度优先搜索遍历得到的顶点序列。 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:

本代码参考了施老师等编著的《数据结构》一书

#include <iostream>
using namespace std;//蓝多多算法实验六 图  题2
#define MaxVertexNum 100// 最大顶点数为100
#define VertexType char//顶点域为字符型
int visited[MaxVertexNum];//标记结点是否被访问过
typedef struct enode//边表中的结点
{
	int adjvex;//边表顶点域
	struct enode* next;//指针域
}EdgeNode;
typedef   struct vnode//顶点表
{
	VertexType vertex;//顶点域
	EdgeNode* firstedge;//边表头指针
}VertexNode;
typedef struct//邻接表
{
	VertexNode vexs[MaxVertexNum];//节点表
	int n, e;//顶点数和边数
}ALGraph;
void InsertNode(ALGraph& G, int i, int j)//在边表中插入结点
{
	EdgeNode* s;
	s = (EdgeNode*)malloc(sizeof(EdgeNode));//生成新边表结点s
	s->adjvex = j;//邻接点序号为j 
	s->next = G.vexs[i].firstedge;
	G.vexs[i].firstedge = s;//将新边表结点s插入到顶点Vi的边表头部
}
ALGraph CreateALGraph()//建立邻边表
{
	ALGraph G;
	int i, j;
	cout << "请输入顶点数和边数：\n";
	cin >> G.n >> G.e;
	cout << "请输入顶点信息：\n";
	for (i = 0; i < G.n; i++)//建立有n个顶点的顶点表
	{
		cin >> G.vexs[i].vertex;//输入顶点
		G.vexs[i].firstedge = NULL;//顶点的边表头指针设为空
	}
	cout << "请输入边的信息(输入格式为：i (空格) j )：\n";
	for (int k = 0; k < G.e; k++)//建立邻接表
	{
		cin >> i >> j;
		InsertNode(G, i, j);
		InsertNode(G, j, i);
	}
	return G;
}
void DFSAL(ALGraph G, int i) //以Vi为出发点对图G搜索
{
	EdgeNode* p;
	cout << G.vexs[i].vertex << "  ";//访问顶点Vi
	visited[i] = 1;//标记Vi已访问
	p = G.vexs[i].firstedge;//取Vi边表的头指针
	while (p)//依次搜索Vi的邻接点Vj
	{
		if (visited[p->adjvex] == 0)//若Vj尚未访问，则以Vj为出发点继续搜索
			DFSAL(G, p->adjvex);
		p = p->next;//找Vi的下一个邻接点
	}
}
void DFSTraverseAL(ALGraph G)
{
	int  i;
	for (i = 0; i < G.n; i++)
		visited[i] = 0;//初始化
	for (i = 0; i < G.n; i++)
		if (visited[i] == 0)
			DFSAL(G, i);//Vi未访问过，从Vi开始搜索
}
int main()
{
	ALGraph G = CreateALGraph();
	cout << "该图的深度优先搜索遍历得到的顶点序列为：";
	DFSTraverseAL(G);
	system("pause");
	return 0;
}

实验结果：

您还可以看一下韦语洋（Lccee）老师的一机一码加密、被破解自动销毁随时授权回收升级系列视频课程课程中的软件破解与防止破解相关知识小节, 巩固相关知识点