线性表及多项式操作.docx

实 验 报 告
实验名称
线性表及多项式的运算
指导教师
邹志强
实验类型
验证
实验学时
2+2
实验时间
2016.9.16
一、实验目的和要求
1.掌握线性表的两种基本存储结构及其应用场合：顺序存储和链接存储。
2.掌握顺序表和链表的各种基本操作算法。
3.理解线性表应用于多项式的实现算法。
二、实验环境(实验设备)
Dev-C++
三、实验原理及内容
内容：
1.参照程序2.1~程序2.7，编写程序，完成顺序表的初始化、查找、插入、删除、输出、撤销等操作。
2.已知代表头节点的单链表的类型定义，参照程序2.8~程序2.14，编写程序，完成带表头节点的单链表的初始化、查找、插入、删除、输出、撤销等操作。
3.以第2题所示带表头节点的单链表为例，编写程序实现单链表的逆置操作(原单链表为(a0,a1,...an-1)，逆置后为(an-1,an-2,...,a0)，要求不引入新的存储空间。)
4.以第2题所示带表头节点的单链表为存储结构，编写程序实现将单链表排序成为有序单链表的操作。
5.已知带表头节点一元多项式的类型定义，编写程序实现一元多项式的创建、输出、撤销以及两个一元多项式相加和相乘的操作。

实 验 报 告
三、实验过程及代码等
1.顺序表的基本运算
顺序表的类型定义：
typedef struct
{
int n;
int maxLength;
int *element;
}SeqList;

顺序表的初始化：
typedef int Status;
Status Init(SeqList *L,int mSize)
{
L->maxLength=mSize;
L->n=0;
L->element=(int*)malloc(sizeof(Status)*mSize);
if(!L->element) // 判断顺序表是否申请成功
return ERROR;
return OK;
}
顺序表的查找
Status Find(SeqList L,int i,int *x)
{
if(i<0||i>L.n-1) //越界判断
return ERROR;
*x=L.element[i];
return OK;
}
顺序表的插入：
Status Insert(SeqList *L,int i,int x)
{
int j;
if(i<-1||i>L->n-1)
return ERROR;
if(L->n==L->maxLength)
return ERROR;
for(j=L->n-1;j>i;j--)
L->element[j+1]=L->element[j];
L->element[i+1]=x;
L->n++;
return OK;
}
顺序表的删除：
Status Delete(SeqList *L,int i)
{
int j;
if (i<0||i>L->n-1)
return ERROR;
if(!L->n)
return ERROR;
for(j=i+1;j<L->n;j++)
L->element[j-1]=L->element[j];
L->n--;
return OK;
}
顺序表的输出：
Status Output(SeqList L)//输出
{
int i;
if(!L.n)
return ERROR;
for(i=0;i<L.n;i++)
printf("%d ",L.element[i]);
return OK;
}

顺序表的析构：
void Destroy(SeqList *L)
{
L->n=0;
L->maxLength=0;
free(L->element);
}
用主函数进行测试：
#include <stdio.h>
#include <stdlib.h>
#define ERROR 0
#define OK 1
int main()
{

int i;
SeqList list;
Init(&list,10);
for(i=0;i<10;i++)
Insert(&list,i-1,i);
Output(list);
printf("\n");
Delete(&list,0);
Output(list);
Destroy(&list);
}
调用结果：

实 验 报 告
2. 带表头节点单链表的基本运算
单链表的类型定义（struct.h）:
typedef struct Node
{
int element; //结点的数据域
struct Node *link; //结点的指针域
}Node;
typedef struct
{
struct Node * head;
int n;
}headerList;

typedef int status;

单链表的初始化（Init.c）:
status Init(headerList *L)
{
L->head=(Node*)malloc(sizeof(Node));
if(!L->head)
return ERROR;
L->head->link=NULL;
L->n=0;
return OK;
}
单链表的查找（Find.c）:
status Find(headerList L, int i,int *x)
{
Node *p;
int j;
if (i<0 || i>L.n-1) //对i 进行越界检查
return ERROR;
p=L.head;
for ( j=0; j<i; j++)
p=p->link; //从头结点开始查找ai
*x=p->element; //通过x 返回ai 的值
return OK;
}
单链表的插入（Insert.c）:
status Insert(headerList *L,int i,int x)
{
Node *p,*q;
int j;
if (i<-1 || i>L->n-1)
return ERROR;
p=L->head;
for(j=0;j<=i;j++)
p=p->link;
q=malloc(sizeof(Node));
q->element=x;
q->link=p->link;
p->link=q;
L->n++;
return OK;
}
单链表的删除（Delate.c）:
status Delete(headerList *L,int i)
{
int j;
Node *p,*q;
if (!L->n)
return ERROR;
if (i<0 || i>L->n-1)
return ERROR;
q=L->head;
for (j=0; j<i; j++) q=q->link;
p=q->link; //p 指向ai
q->link=p->link; //从单链表中删除p 所指向的结点
free(p); //释放p 所指结点的存储空间
L->n--;
return OK;
}

单链表的输出（Output.c）:
status Output(headerList L)
{
Node *p;
if (!L.n) //判断顺序表是否为空
return ERROR;
p=L.head->link;
while(p)
{
printf("%d ",p->element);
p=p->link;
}
return OK;
}
单链表的析构（Destroy.c）:
void Destroy (headerList *L)
{
Node *p;
while(L-> head )
{
p= L-> head->link;
free(L->head);
L-> head=p;
}
}
测试所用主函数(main.c)：
void main()
{
int i;
int x;
headerList list;
Init(&list); //对线性表初始化
for(i=0;i<9;i++)
Insert(&list,i-1,i); //线性表中插入新元素
printf("the linklist is:");
Output(list);
Delete(&list,0);
printf("\nthe linklist is:");
Output(list);
Nizhi(&list);
printf("\n逆置后：\n");
Output(list);
Find(list,0,&x);
//printf("\nthe value is:");
//printf("%d ",1);
Destroy (&list);
}调用结果:单链表的基本操作和逆置是在一篇代码中，所以主函数中已包括逆置函数的调用，调用结果如图也包括了逆置结果。

3.单链表逆置操作
status Nizhi(headerList *L)
{
Node *p,*q,*r;
p=L->head;
q=p->link;
while(q)
{
r=q->link;
q->link=p;
p=q;
q=r;
}
L->head->link->link=NULL;
L->head->link=p;
return 0;
}调用结果：

4. 单链表排序操作（冒泡）
#include<stdio.h>
#include<stdlib.h>
typedef struct node
{
int element;
struct node *next;
}Node,*LinkList;
LinkList Creat(void) /*创建链表，输入数据，结束标志为当输入的数据为0*/
{
LinkList H,p,q;
int n;
n=0;
p=q=(LinkList)malloc(sizeof(Node));
printf("输入数据： （输入0标志着输入完成）\n");
scanf("%d",&p->element);
H=NULL;
while(p->element!=0)
{
n=n+1;
if(n==1)
H=p;
else
q->next=p;
q=p;
p=(LinkList)malloc(sizeof(Node));
scanf("%d",&p->element);
}
q->next=NULL;
return(H);
}
LinkList Paixu(LinkList l) /*排序*/
{
LinkList p,q;
int temp;
for(p=l;p!=NULL;p=p->next)
{
for(q=p->next;q!=NULL;q=q->next)
{
if(p->element>q->element)
{
temp=q->element;
q->element=p->element;
p->element=temp;
}
}
}
return l;
}

int main()
{
LinkList L,S,K;
L=Creat();
printf("初始化的单链表为:\n");
for(S=L;S!=NULL;S=S->next)
printf("%d ",S->element);
Paixu(L);
printf("\n按递增排序后的链表为:\n");
for(K=L;K!=NULL;K=K->next)
printf("%d ",K->element);

return 0;
}
调用结果：

5. 多项式操作
多项式的类型定义（struct.h）:
typedef struct PNode
{
int coef;
int exp;
struct PNode* link;
} PNode;
typedef struct
{
struct PNode *head;
}polynominal;

多项式的创建（Create.c）:
void Create(polynominal *p)
{
PNode *pn,*pre,*q;
p->head=(void*)malloc(sizeof(PNode));
p->head->exp=-1;
p->head->link=NULL;
printf("请输入多项式\n");
for( ; ; )
{
pn=(void*)malloc(sizeof(PNode));
printf("coef:\n");
scanf("%d",&pn->coef);
printf("exp:\n");
scanf("%d",&pn->exp);
if(pn->exp<0) break;
pre=p->head;
q=p->head->link;
while(q&&q->exp>pn->exp)
{
pre=q;
q=q->link;
}
pn->link=q;
pre->link=pn;
}
}

多项式的输出（Output.c）:
void Output(polynominal L)
{
PNode *p;
p=L.head->link;
while(p->link!=NULL)
{

printf("%d*X^%d+",p->coef,p->exp);

p=p->link;
}
printf("%d*X^%d\n",p->coef,p->exp);
}

多项式的析构（Destroy.h）:
void Destroy (polynominal *L)
{
PNode *p;
while(L-> head )
{
p= L-> head->link;
free(L->head);
L-> head=p;
}
}

两个多项式的加法（Add.c）:
void Add(polynominal *px,polynominal *qx)
{
PNode *q,*q1=qx->head,*p,*temp;
p=px->head->link;
q=q1->link;
while(p&&q)
{
while(p->exp<q->exp)
{
q1=q;q=q->link;
}
if(p->exp==q->exp)
{
q->coef=q->coef+p->coef;
if(q->coef==0)
{
q1->link=q->link;
free(q);
q=q1->link;
p=p->link;
}

else
{
q1=q;
q=q->link;
p=p->link;
}
}

else
{
temp=(void*)malloc(sizeof(PNode));
temp->coef=p->coef;
temp->exp=p->exp;
temp->link=q1->link;
q1->link=temp;
p=p->link;
}
}
}

两个多项式的乘法（Mult.c）:
polynominal* Mult(polynominal *a,polynominal *b)
{
PNode *an,*bn;
polynominal temp;
printf("初始化temp，输入0 0 0 -1");
Create(&temp);
an=a->head;
bn=b->head;
while(an->link)
{
an=an->link;
while(bn->link)
{
bn=bn->link;
bn->exp+=an->exp;
bn->coef*=an->coef;
}
Add(b,&temp);
bn=b->head;
while(bn->link)
{
bn=bn->link;
bn->exp-=an->exp;
bn->coef/=an->coef;
}
bn=b->head;
}
return &temp;
}
调用主函数测试：
void main()
{
polynominal listA,listB,listC,listD,temp;
int choose=0;
printf("请选择操作： 1.多项式相加 2.多项式相乘 \n");
scanf("%d",&choose);
switch(choose)
{
case 1:{

Create(&listA);
Create(&listB);
printf("多项式A为： ");
Output(listA);
printf("多项式B为： ");
Output(listB);
Add(&listA,&listB);
printf("\n");
printf("A与B相加得：");
Output(listB);
Destroy(&listA);
Destroy(&listB);
} break;
case 2:{
Create(&listC);
Create(&listD);
printf("多项式C为： ");
Output(listC);
printf("多项式D为： ");
Output(listD);
//Mult(&listC,&listD);
Output(*Mult(&listC,&listD));
Destroy(&listC);
Destroy(&listD);
}break;
}
}
运行结果：
（1） 多项式加法：

（2） 多项式乘法：

实 验 报 告
四、实验小结（包括问题和解决方法、心得体会、意见与建议等）
一、前面写顺序表的时候没有遇到什么问题，只是有两个地方有点小问题但很快解决了；（1）(void*)malloc(sizeof(PNode))在malloc前面漏掉强制类型转换。（2）for（int i=1,i<n,i++）类似上式，有些编译器不支持for循环类定义变量名。
二、刚开始写链表的代码时，总是搞不清一个链表内的成员和关系，后来一直到完成多项式加法时才对链表有了一个较为全面的认识。
三、在写多项式乘法时，在网上找了一个乘法的算法，可是改来改去还是会出问题，在输出最终结果时输出的系数和指数是地址而不是数，和舍友讨论了很久也没有解决，我后来在舍友的帮助下完成了多项式的乘法；但是之前的那段没有找出问题的代码还是没有找到答案，而且目前还以注释的形式保留在源代码中。

四、希望自己能够在实验和作业中有所收获，使得自己的代码水平有一定的提升。

五、指导教师评语

成 绩

批阅人

日 期

24