### 数据结构实验报告知识点梳理
#### 一、实验目的与要求
本次实验旨在通过实践让学生深入理解线性表的基本操作及应用，具体包括以下几点：
1. **掌握线性表的基本操作**：如插入、删除、查找等操作的设计与实现。
2. **学会利用线性表解决实际问题**：通过实验掌握如何运用线性表提供的接口来解决具体的计算问题。
3. **熟悉线性表的存储方式**：了解不同类型的线性表（如单链表、双链表、循环链表等）在存储结构上的差异及其适用场景。
#### 二、实验内容与原理
本实验的具体内容是设计一个一元多项式的简单计算器，具备以下功能：
- 输入并建立多项式
- 输出多项式
- 多项式相加
**实验原理**：采用单链表作为存储结构来描述一元多项式。每个节点包含该多项式中某一项的系数和指数。在建立单链表时，确保指数较高的节点位于指数较低的节点之前，从而使得线性表中的元素按照指数递增的顺序排列。
#### 三、实验环境
- 开发工具：Visual C++ 6.0
- 运行平台：PC机
#### 四、算法描述与实验步骤
**思想算法**：本实验采用单链表来表示多项式，并按照指数递增的顺序进行排序。具体步骤如下：
1. **多项式加法**：定义指针`p`和`q`分别指向两个多项式`ha`和`hb`的首节点。
- 若`p`和`q`所指节点的指数相同，则将它们的系数相加并将结果存入新节点`r`中。
- 若`p`所指节点的指数小于`q`所指节点的指数，则将`q`所指节点的系数和指数复制到`r`中，并移动`q`。
- 若`p`所指节点的指数大于`q`所指节点的指数，则将`p`所指节点的系数和指数复制到`r`中，并移动`p`。
- 重复以上步骤直到`p`或`q`为空。
2. **多项式乘法**：定义指针`fp`和`gp`分别指向两个多项式`f`和`g`的首节点。
- 首先确定乘积多项式的最大指数`maxp`，并通过循环计算所有可能的乘积项。
- 每次迭代过程中，计算`fp`和`gp`所指节点的指数之和`p`。
- 若`p`大于`maxp`，则移动`fp`；若`p`小于`maxp`，则移动`gp`；若`p`等于`maxp`，则将系数相乘累加至结果。
#### 五、实验结果
根据实验步骤，分别输入两个多项式进行相加和相乘操作，并输出结果。
1. **多项式相加示例**：输入多项式`5X^3 + 4X^2 + 3X + 2`和`X^2 + X + 1`，输出结果为`5X^3 + 5X^2 + 4X + 3`。
2. **多项式相乘示例**：输入多项式`6X^4 + 4X^2 + 2`和`5X + 6`，输出结果为`30X^5 + 36X^4 + 20X^3 + 24X^2 + 12X + 12`。
#### 六、总结
本次实验通过实际操作，不仅加深了对线性表的理解，还掌握了如何运用线性表解决实际问题的方法。实验过程中，对算法思想有了更深刻的认识，同时也对指针的使用更加熟练。这些经验和技能对于后续的学习和项目开发都非常有帮助。
#### 七、附录
1. **建立多项式列表代码**
```c
mulpoly*creatpoly() /* 建立多项式列表 */
{mulpoly*head,*r,*s;/*设中间变量*/
int m,n;
head=(mulpoly*)malloc(sizeof(mulpoly));/*头结点申请空间*/
printf("\ninput coef and exp:\n");
scanf("%d%d",&n,&m);/*输入多项式系数和指数*/
r=head;/*尾指针指向头指针*/
while(n!=0)/*将输入的多项式存放在S中*/
{s=(mulpoly*)malloc(sizeof(mulpoly));
s->coef=n;
s->exp=m;
r->next=s;
r=s;
/*printf("input coef and exp:\n");*/
scanf("%d%d",&n,&m);/*再次输入多项式系数和指数*/
}
r->next=NULL;/*将尾指针置空*/
head=head->next;/*将head哑结点向前跑一个结点，使其不为空*/
return(head);/*返回多项式*/
}
```
2. **两个多项式相加代码**
```c
mulpoly*polyadd(mulpoly*ha,mulpoly*hb) /* 两个多项式相加 */
{mulpoly*hc,*p,*q,*s,*r;/*声明结构体型*/
int x;
p=ha;
q=hb;
hc=(mulpoly*)malloc(sizeof(mulpoly));/*申请结点空间*/
s=hc;
while((p!=NULL)&&(q!=NULL))/*两多项式不为空*/
if(p->exp==q->exp)/*指数相等*/
{x=p->coef+q->coef;/*系数相加*/
if(x!=0)/*系数不为零*/
{r=(mulpoly*)malloc(sizeof(mulpoly));/*结果放r中存放*/
r->exp=q->exp;
r->coef=x;
s->next=r;
s=r;
}
// ... (此处省略了剩余的代码)
```
通过本次实验，学生不仅学会了如何实现多项式的加法和乘法，更重要的是理解了如何通过编程解决问题的基本思路和方法。这对于提高编程能力有着不可估量的价值。
