下载掌阅APP，畅读海量书库
立即打开
在C语言中，处理已知数量的数据可以使用数组。如果事先并不知道要处理的数据的个数，则需要使用链表结构。链表需要动态分配内存，链表的长度随时可以发生变化。在今后学习数据结构的过程中，数据结构的单链表、树、图等结构还需要用到链表结构。本节主要给大家介绍内存的动态分配、释放及链表。
在C语言中，内存的动态分配与释放往往离不开malloc函数和free函数。
函数malloc的主要作用是分配一块长度为size的内存空间。函数原型如下。
void *malloc(unsigned int size);
其中，参数size是要分配的内存空间的大小（字节），这一块内存空间是连续的。如果分配成功，则函数的返回值是一个指向新分配内存空间的起始位置。如果分配不成功，则返回NULL。
（1）函数malloc常常与运算符sizeof配合使用。例如，要分配一个大小为20的int型的内存空间，代码如下。
int *p; /* 定义一个int 型的指针变量p*/ p=(int*)malloc(sizeof(int)*20); /* 分配一个大小为20 的int 型的内存空间，p 指向新开辟的空间首地址*/
因为这是为int型的数据开辟内存空间，所以需要将函数的返回值void*转换为int*。当然，以上代码也可以放在一起写成一行，代码如下。
int *p=(int*)malloc(sizeof(int)*20); /*p 指向新分配一个20 个int 型的内存空间的首地址*/
以上两段代码是等价的。
（2）也可以为一个结点类型分配内存空间，代码如下。
int *p; /* 定义一个int 型的指针变量p*/ p=(struct student*)malloc(sizeof(struct student)); /* 分配一个大小为1 的struct student 型的内存空间*/
其中，struct student是上面定义的结构体类型，表示一个结点。通过以上动态分配就可以得到一个结点的内存空间，然后就可以将数据存入该结点了。
函数free的主要作用是将动态分配的内存空间释放。它的函数原型如下。
void free(void *p);
其中，参数p指向要释放的内存空间。函数free没有返回值。
函数原型malloc和free都在头文件stdlib.h和alloc.h中定义。使用动态内存分配函数和动态内存释放函数需要注意以下几点。
·在调用函数malloc分配内存空间时，最好检查下是否分配成功，即检查函数的返回值是否等于NULL，以保证程序的正确运行。
·在使用完由malloc函数分配的内存空间时，要利用free函数将该内存空间及时释放。
·不能使用已经被free函数释放的内存空间。
链表是一种常用的数据结构。链表是一种特殊的结构体类型，它有一个指针类型的成员指向自身，该指针指向与结构体一样的类型。例如如下语句。
struct node
{
int data;
struct data *next;
};
这就是一种自引用结构体类型。自引用结构体类型为struct node，该结构体类型有两个成员：一个是整型成员data，一个是指针成员next。成员next是指向结构体为struct node类型的指针。通过这种形式定义的结构体通过next指针把两个结构体变量连在一起，如图2-57所示。
这种自引用结构体单元称为 结点 。结点之间通过箭头连接起来，构成一个表，称为 链表 。链表中指向第一结点的指针称为头指针，通过头指针，可以访问链表的每一个结点。链表的最后一个结点的指针部分用空（^）表示。为了方便操作，在链表的第一个结点之前增加一个结点，称为 头结点 。一个带头结点的链表如图2-58所示。
图2-57 不带头结点的链表
图2-58 带头结点的链表
创建链表首先需要生成结点，然后将结点利用指针域连接起来，这样就构成了一个链表。只是生成链表时，使用的是动态内存分配。假设要创建的链表的结点类型定义如下。
struct student /*
定义结点*/
{
long no; /*
学号*/
char name[20]; /*
姓名*/
char addr[30]; /*
地址*/
struct student *next; /*
指向结构体的指针*/
};
定义3个指向struct student类型的指针变量h、prev和cur，h代表头指针，指向第一个结点。初始时，令h=NULL，表示链表为空。链表为空就是链表这没有结点存在，头指针head的值为NULL。代码如下。
LIST *h=NULL,*prev,*cur;
初始状态如图2-59所示。
图2-59 空链表
①动态生成一个结点，由指针cur指向该结点，代码如下。
cur=(struct student *)malloc(sizeof(struct student)); /* 动态分配结点*/
②因为这是第一个结点，所以使用头指针h指向该结点，代码如下。
h=cur;
③此时链表中只有一个结点，因此将该结点的next域置为NULL，代码如下。
cur->next=NULL;
④最后需要为该结点输入数据，代码如下。
scanf("%d %s %s",&cur->no,cur->name,cur->addr);
输入的数据如下。
10901 郭庆峰 北京< 回车>
⑤令pre指针指向该结点。pre指针指向的结点表示要插入结点的前一个结点。在插入一个新结点后，当前结点变为下一个结点的前一个结点，需要使用pre指向该结点。代码如下。
prev = cur;
此时，链表的状态如图2-60所示。
图2-60 插入第一个结点的过程
①动态生成一个结点，由指针cur指向该结点，代码如下。
cur=(struct student *)malloc(sizeof(struct student)); /* 动态分配结点*/
②因为当前结点一定是最后一个结点，所以将next指针域置为NULL，代码如下。
cur->next=NULL;
③令指针prev的next域指向当前结点，使cur指向的结点成为链表中的最后一结点，代码如下。
prev->next=cur;
④为该结点输入数据，代码如下。
scanf("%d %s %s",&cur->no,cur->name,cur->addr);
输入的数据如下。
10902 王志恒 陕西< 回车>
⑤将prev指向最后一个结点，代码如下。
prev = cur;
此时，链表的状态如图2-61所示。
图2-61 在链表中插入第2个结点的过程
在链表的末尾插入第3个结点的方法与第3步的方法类似，过程如图2-62所示。
图2-62 在链表中插入第3个结点的过程
插入的过程如图2-63所示。
图2-63 在链表中插入第4个结点的过程
这样，经过以上操作就构造出了一个具有4个结点的链表。
经过以上分析，得到创建链表的程序如下。
struct student /*
定义结点*/
{
long no; /*
学号*/
char name[20]; /*
姓名*/
char addr[30]; /*
地址*/
struct student *next; /*
指向结构体指针*/
};
typedef struct student LIST; /*
将类型重新命名为LIST*/
LIST *CreateList() /*
创建链表的函数定义*/
{
LIST *h,*prev,*cur; /*
定义指向LIST
的指针变量*/
int i,n; /*
定义变量*/
h=NULL; /*
初始时头指针h
为空*/
printf("
输入结点个数：\n");
scanf("%d",&n); /*
输入链表中结点的个数*/
for(i=0;i<n;i++)
{
cur=(LIST *)malloc(sizeof(LIST)); /*
动态生成一个结点空间*/
cur->next=NULL; /*
将cur
的next
置为NULL*/
if(h==NULL) /*
如果h=NULL
，表示当前正在处理第一个结点*/
h=cur; /*
令h
指向第一个结点*/
else /*
如果不是第一个结点*/
prev->next=cur; /*
令链表中最后一个结点的next
指向cur*/
scanf("%d %s %s",&cur->no,cur->name,cur->addr); /*
为cur
指向的结点输入数据*/
prev = cur; /*
将prev
指向最后一个结点*/
}
return h; /*
返回头指针h*/
}
初始时，链表为空，头指针h为NULL。在链表中，将h==NULL作为链表为空的条件。指针prev永远指向链表的最后一个结点，当要插入cur指向的结点，则需要让prev指向的结点的next域指向cur指向的结点，这样就将cur指向的结点插入了链表，成为最后一个结点，主要通过以下代码实现。
prev->next=cur;
然后让prev指向最后一结点，准备下一次插入新结点。在函数的最后，将头指针h返回给调用函数。这样调用函数就可以利用头指针访问链表中的每一个结点。
链表的输出操作就是输出链表中每个结点的数据。要输出链表中的结点的数据，需要从链表的头指针出发，令指针p指向第一个结点，输出p指向的结点的数据。然后通过结点的指针域next找到下一个结点，并输出数据。依次类推，直到最后一个结点。
输出链表中的每个结点的数据的过程如图2-64所示。
图2-64 输出链表中每个结点记录的过程
图中的虚线表示前一个指针所在的位置。在（a）图中，p指向第一个结点，并输出该结点的数据。然后令p=p->next，p指向了第二个结点，并输出第二个结点的数据。当p指向最后一个结点时，p->next为NULL，表示该结点之后没有结点，停止输出。
在输出过程中，主要通过如下代码找到下一个结点。
p=p->next;
将p->next赋值给p，而p->next是下一个结点的地址，也就是说将下一个结点的地址赋值给p，这样p的地址就是下一个结点的地址，即p指向下一个结点。
完整的链表输出操作的程序代码如下。
void DispList(LIST *h)
{
LIST *p=h; /*
定义指针p
并指向链表的第一个结点*/
while(p!=NULL) /*
如果p
不为NULL*/
{
printf("%d %s %s\n",p->no,p->name,p->addr); /*
输出p
指向结点的数据*/
p=p->next; /*
指针p
指向下一个结点*/
}
}
下面编写一个main函数，在main函数中调用CreateList和DispList，测试一下程序的正确性，代码如下。
LIST *CreateList();
void DispList(LIST *h);
void main()
{
LIST *head;
head=CreateList();
printf("
学号
姓名
地址\n");
DispList(head);
}
程序的运行结果如图2-65所示。
图2-65 程序运行结果
链表的插入操作是指将一个结点插入到链表中。在由学生构成的链表中，结点是按照学号的从小到大进行排列。如果将一个结点插入到链表中，需要处理以下两个问题：找到要插入的位置和如何插入新结点。
要在链表中寻找插入的位置，先看生活中的一个例子。有一群学生手拉手按照个子从低到高排成一队，要将一个新学生插入其中，要求这一队学生仍然是按照个子从低到高排列。这可以将这个新学生与第一个学生进行比较，如果它的个子比第一个学生高，则与第二个学生的个子比较，如果比第二个学生的个子高，则继续与第三个学生进行比较，如果它的个子低于第三个学生的个子，则将其插入到第三个学生之前第二个学生之后。
在链表中寻找插入的位置与此类似。从链表的第一个结点出发，将新结点的学号与链表中的结点的学号进行比较，如果新结点的学号比前一个结点的学号大，而小于后一个结点的学号，则将新结点插入到两者之间。例如，s指向要插入的结点，它的学号是10908，需要将s->no依次与链表中第一个结点先进行比较，因为s->no>p->no，所以将指针p向后移动，即p=p->next，p指向第二个结点，因为s->no>p->no，所以继续让p向后移动，即执行p=p->next，此时p指向第三个结点，因为s->no<=p->no，则要插入的位置应该是第二个结点与第三个结点之间，如图2-66所示。
图2-66 s指向的结点寻找插入的位置
新结点要插入的位置有3种可能，即在第一个结点之前、在第一个结点和最后一个结点之间、在最后一个结点之后。
（1）将新结点插入第一个结点之前
如果要插入的结点的学号小于第一个结点的学号，则要将该结点插入第一个结点之前。例如，链表的第一个结点的学号是10903，而要插入的结点的学号是10902，因为s->no<h->no，则需要将s指向的结点插入到h指向的结点之前，如图2-67所示。
插入过程分为两步操作，第1步需要将s指向的结点的指针域指向第一个结点，即s->next=h；第2步令头指针h指向s指向的结点，即h=s，这是因为s指向的结点变为了第一个结点。
图2-67 在第一个结点之前插入新结点的过程
（2）将新结点插入链表的中间
插入的新结点位于链表中某一个结点，不是第一个结点之前，也不是最后一个结点之后，这种情况如图2-68所示。s指向的结点应该插入到第2个结点和第3个结点之间，其中pre指向要插入的位置之前的结点，p指向要插入的位置之后的结点。
图2-68 在链表的中间插入一个新结点的过程
要将s指向的结点插入到链表中，需要进行以下两步操作，第1步将s指向的结点的指针域指向p，即s->next=p；第2步将pre指向的结点的指针域指向s指向的结点，即pre->next=s。需要说明的是，这两个步骤可以相互交换，不会影响到程序的结果。
（3）将新结点插入链表的最后一个结点之后
如果新结点的学号大于最后一个结点，则需要将新结点插入到最后一个结点之后，如图2-69所示。这时，新结点称为链表的最后一个结点。
在这种情况下，只需要一步操作，即将s指向的结点插入p指向的结点之后即可，即p->next=s。
图2-69 将新结点插入链表中最后一个结点之后的过程
在链表中插入新结点的程序代码如下。
LIST *InsertNode(LIST *h,LIST *s)
{
LIST *pre,*p; /*
定义指针变量pre
和p*/
p=h; /*
令p
指向第一个结点*/
if(h==NULL) /*
如果链表为空*/
{
h=s; /*s
结点就是表的第一个结点，让头指针h
指向该结点*/
s->next=NULL; /*
将s
指向的结点的指针域置为NULL*/
}
else /*
如果链表不为空*/
{
while((s->no>p->no)&&(p->next!=NULL)) /*
在链表中查找要插入的位置*/
{
pre=p; /*pre
指向p
指向的结点的前面的一个结点*/
p=p->next; /*p
指向下一个结点*/
}
if(s->no<=p->no) /*
如果s
指向的结点的学号小于等于p
指向的学号*/
{
if(h==p) /*
如果要插入的位置在第一个结点之前*/
{
h=s; /*
则让头指针h
指向新结点*/
s->next=p; /*
让新结点的指针域指向第一个结点*/
}
else /*
如果插入的位置在中间*/
{
pre->next=s; /*
将前一个结点的指针域指向新结点*/
s->next=p; /*
让新结点的指针域指向p
指向的结点*/
}
}
else /*
如果要插入的位置位于最后一个结点之后*/
{
p->next=s; /*
将最后一个结点即p
指向的结点的指针域指向新结点*/
s->next=NULL; /*
令s
指向的结点的指针域置为空*/
}
}
return h; /*
返回头指针*/
}
在链表中插入新结点时，需要说明以下几点。
·在插入新结点时，需要考虑链表是否为空的情况。如果链表为空，则新结点直接作为链表的第一个结点，就是让头指针h指向该结点。代码如下。
if(h==NULL) /*
如果链表为空*/
{
h=s; /*s
结点就是表的第一个结点，让头指针h
指向该结点*/
s->next=NULL; /*
将s
指向的结点的指针域置为NULL*/
}
·如果链表不为空，则需要在链表中查找要插入的位置。在查找时，用到两个指针pre和p。其中，pre指向p指向的前一个结点。要插入的新结点位置应该为pre和p之间。查找插入位置的代码如下。
while((s->no>p->no)&&(p->next!=NULL)) /*
在链表中查找要插入的位置*/
{
pre=p; /*pre
指向p
指向的结点的前面的一个结点*/
p=p->next; /*p
指向下一个结点*/
}
其中，条件有两个，即s->no>s->no和p->next！=NULL，前者是比较学号的大小，后者控制链表是否结束。因此，退出该循环有两个可能，一个是s->no<=p->no，一个是p->next==NULL。
·如果s->no<=p->no，说明找到了要插入的位置，该位置存在两种可能，一个是插入的位置位于第一个结点之前；另一个是插入的位置在链表中间。对于第一种情况，只需要将新结点的指针域指向第一个结点，然后让头指针指向新结点，新结点成为链表的第一个结点。代码如下。
if(h==p) /*
如果要插入的位置在第一个结点之前*/
{
h=s; /*
则让头指针h
指向新结点*/
s->next=p; /*
让新结点的指针域指向第一个结点*/
}
对于第二种情况，需要将新结点插入pre和p指向的结点之间，代码如下。
pre->next=s; /* 将前一个结点的指针域指向新结点*/ s->next=p; /* 让新结点的指针域指向p 指向的结点*/
·如果p->next==NULL，则p指向的是最后一个结点。此时新结点的学号大于最后一个结点的学号，需要将新结点插入到最后一个结点之后，代码如下。
p->next=s; /* 将最后一个结点即p 指向的结点的指针域指向新结点*/ s->next=NULL; /* 令s 指向的结点的指针域置为空*/
链表的删除操作就是将链表中的某个结点删除。例如有6个小孩手拉手玩耍，有个小孩离开之后，剩余的5个小孩继续手拉手保持队形不变。这就类似于链表的生删除操作，其中小孩手拉手就像是一个链表，每个小孩像链表中的结点。
在链表中删除某个结点后，链表中剩下的结点次序保持不变，将剩下的结点相连接仍然是一个链表。下面通过具体的实例说明链表的删除操作。
如果要删除学号为10903的结点，需要先找到该结点，然后从链表中将该结点删除。删除该结点就是将该结点从链表中脱离出来，使该结点不再是链表的一部分。最后释放结点占用的内存空间。删除过程如图2-70所示。
图2-70 删除学号为10903结点的过程
①删除一个结点，需要使用两个指针pre和p，其中p指向要删除的结点，pre指向要删除结点的前一个结点，如图2-70（a）所示。
②将p指向的结点从链表中去除，也就是让pre指向的结点直接指向p指向的下一个结点，这样在顺着链表找到到第二个结点后，顺着第二个结点的指针域直接找到了第四个结点，因为第二结点的指针域不再指向了第三个结点。要实现这个操作，需要将p指向的下一个结点的地址赋值给pre->next，即pre->next=p->next。如图2-63（b）所示。
③因为结点的内存空间是动态分配的，所以需要使用函数free将这些空间释放掉。如图2-63（c）所示。将结点释放掉之后，链表的状态就是图2-63（d）。
删除操作的程序代码如下所示。
LIST *DeleteNode(LIST * h,long no)
{
LIST *pre, *p; /*
定义指针变量*/
if(h==NULL) /*
如果链表为空，则不能删除结点*/
{
printf("
链表为空，不能删除结点!\n");
return NULL; /*
返回空指针*/
}
p=h; /*
将p
指向第一个结点*/
while (p->no!=no&&p->next!=NULL) /*
如果当前结点不是要删除的结点*/
{
pre=p; /*pre
指向p
指向的结点*/
p=p->next; /*p
指向下一个结点*/
}
if (p->no==no) /*
如果p
指向的结点是要删除的结点*/
{
if(p==h) /*
如果要删除的结点是第一个结点*/
h=p->next; /*
则头指针指向第二个结点*/
else /*
如果要删除的结点不是第一个结点*/
pre->next=p->next; /*
则让pre
的指针域指向p
的下一个结点，即将p
删除*/
free(p); /*
释放p
指向的结点的内存空间*/
printf("
结点被成功删除.\n");
}
else /*
如果没有找到要删除的结点*/
printf("
没有发现要删除的结点!\n");/*
输出提示信息*/
return h; /*
返回链表的头指针*/
}
在删除操作过程中，需要说明以下几点。
·首先要判断链表是否为空，如果为空，则不能进行删除操作，代码如下。
if(h==NULL) /*
如果链表为空，则不能删除结点*/
{
printf("
链表为空，不能删除结点!\n");
return; /*
直接返回*/
}
判断链表是否为空的条件是h==NULL。如果为空，则将程序直接返回，不再执行下面的操作。
·如果链表不为空，则需要从链表的第一个结点开始，即头指针h出发，依次比较结点的学号。先让指针p指向第一个结点，代码如下。
p=h; /* 将p 指向第一个结点*/
接着比较结点的学号即p->no==no。如果等于no，则需要继续比较，代码如下。
while (p->no!=no&&p->next!=NULL) /*
如果当前结点不是要删除的结点*/
{
pre=p; /*pre
指向p
指向的结点*/
p=p->next; /*p
指向下一个结点*/
}
·如果找到链表中要删除的结点，则需要继续判断，看要删除的结点是第一个结点还是中间结点。如果要删除的结点是第一个结点，则需要将头指针h指向第二结点，然后释放p指向的结点内存空间，代码如下。
if(p==h) /*
如果要删除的结点是第一个结点*/
h=p->next; /*
则头指针指向第二个结点*/
要删除的结点是第一个结点的情况如图2-71所示。
图2-71 删除第一个结点的过程
·如果没有找到要删除的结点，也就是当p->next！=NULL条件不成立时，输出提示信息。
·在程序的最后要返回链表的头指针h，供调用函数或其他函数使用。
前面介绍了链表的各种操作，包括创建链表、输出链表、插入链表和删除链表，本节将通过main函数调用这些链表操作，测试程序的正确性。
【例2-18】 编写一个main函数，分别调用函数CreateList创建链表，调用InsertNode插入新结点，调用函数DeleteNode删除结点，调用函数DispList输出结点的值。
实现程序如下。
#include<stdio.h>
struct student /*
定义结点*/
{
long no; /*
学号*/
char name[20]; /*
姓名*/
char addr[30]; /*
地址*/
struct student *next; /*
指向结构体指针*/
};
typedef struct student LIST; /*
重新定义结点类型*/
LIST *CreateList(); /*
声明函数CreateList*/
LIST *InsertNode(LIST *h,LIST *s); /*
声明函数InsertNode*/
LIST *DeleteNode(LIST * h,long no); /*
声明函数DeleteNode*/
void DispList(LIST *h); /*
声明函数DispList*/
void main()
{
LIST *head,*p; /*
定义指向结点的指针*/
long no; /*
定义一个长整型，表示输入的学号*/
head=CreateList(); /*
调用函数CreateList
创建链表*/
printf("
学号
姓名
地址\n");
DispList(head); /*
调用函数DispList
输出链表中的结点*/
printf("
输入要插入的结点元素：\n");
p=(LIST*)malloc(sizeof(LIST)); /*
动态生成一个新结点*/
scanf("%d %s %s",&p->no,p->name,p->addr); /*
输入结点的数据*/
head=InsertNode(head,p); /*
调用函数InsertNode
插入新结点*/
printf("
学号
姓名
地址\n");
DispList(head); /*
调用函数DispList
输出插入新结点后的链表*/
printf("
请输入一个要删除结点的学号:\n ");
scanf("%d",&no); /*
输入要删除结点的学号*/
head=DeleteNode(head,no); /*
调用函数DeleteNode
输出学号为no
的结点*/
if(head!=NULL)
{
printf("
学号
姓名
地址\n");
DispList(head); /*
调用函数DispList
输出删除结点后的链表*/
}
}
程序运行结果如图2-72所示。
该程序省略了函数CreateList、InsertNode、DeleteNode、DispList的定义。这几个函数的具体实现请参见2.2.1～2.2.4小节。
图2-72 程序运行结果
假设一元多项式为P n （x）=a n x n +a n-1 x n-1 +…+a 1 x+a 0 ，一元多项式的每一项由系数和指数构成，因此要表示一元多项式，需要定义一个结构体。结构体由两个部分构成，分别为coef和exp，分别表示系数和指数。定义结构体的代码如下。
struct node
{
float coef; /*
系数*/
int exp; /*
指数*/
};
如果用结构体数组表示多项式的每一项，则需要n+1个数组元素存放多项式（假设n为最高次数）。遇到指数不连续且指数之间跨越非常大时，例如，多项式2x 500 +1，则需要数组的长度为501。这显然会浪费很多内存单元。
为了有效利用内存空间，可以使用链表表示多项式，多项式的每一项使用结点表示。结点由系数、指数和指针域3个部分构成，结构如图2-73所示。
图2-73 多项式每一项的结点结构
结点用C语言描述如下。
struct node
{
float coef; /*
系数*/
int exp; /*
指数*/
struct node *next; /*
指针域*/
};
为了操作方便，将链表按照指数的从高到低进行排列，即降幂排列。一个最高次数为n的多项式构成的链表如图2-74所示。
例如，有两个一元多项式p（x）=3x 2 +2x+1和q（x）=5x 3 +3x+2，链表表示如图2-75所示。
图2-74 一元多项式的链表结构
图2-75 一元多项式的链表表示
如果要将两个多项式相加，需要比较两个多项式的指数项后决定。当两个多项式的两项中指数相同时，才将系数相加。如果两个多项式的指数不相等，则多项式该项和的系数是其中一个多项式的系数。实现代码如下。
if(s1->exp==s2->exp) /*
如果两个指数相等，则将系数相加*/
{
c=s1->coef+s2->coef;
e=s1->exp;
s1=s1->next;
s2=s2->next;
}
else if(s1->exp>s2->exp) /*
如果s1
的指数大于s2
的指数，则将s1
的指数作为结果*/
{
c=s1->coef;
e=s1->exp;
s1=s1->next;
}
else /*
如果s1
的指数小于等于s2
，则将s2
的指数作为结果*/
{
c=s2->coef;
e=s2->exp;
s2=s2->next;
}
其中，s1和s2分别指向两个链表表示的表达式。因为表达式是按照指数从大到小排列的，所以在指数不等时，将指数大的作为结果。指数小的还要继续进行比较。例如，如果当前s1指向系数为3，指数为2的结点即（3，2），s2指向（3，1）的结点，因为s1->exp>s2->exp，所以将s1的结点作为结果。在s1指向（2，1）时，还要与s2的（3，1）相加，得到（5，1）。
如果相加后的系数不为0，则需要生成一个结点存放到链表中，代码如下。
if(c!=0)
{
p=(ListNode*)malloc(sizeof(ListNode));
p->coef=c;
p->exp=e;
p->next=NULL;
if(s==NULL)
s=p;
else
r->next=p;
r=p;
}
如果在一个链表已经到达末尾，而另一个链表还有结点，需要将剩下的结点插入新链表中，代码如下。
while(s1!=NULL)
{
c=s1->coef;
e=s1->exp;
s1=s1->next;
if(c!=0)
{
p=(ListNode*)malloc(sizeof(ListNode));
p->coef=c;
p->exp=e;
p->next=NULL;
if(s==NULL)
s=p;
else
r->next=p;
r=p;
}
}
while(s2!=NULL)
{
c=s2->coef;
e=s2->exp;
s2=s2->next;
if(c!=0)
{
p=(ListNode*)malloc(sizeof(ListNode));
p->coef=c;
p->exp=e;
p->next=NULL;
if(s==NULL)
s=p;
else
r->next=p;
r=p;
}
}
最后，s指向的链表就是两个多项式的和。
【例2-19】 依次输入两个多项式，编写程序求两个多项式的和。
该程序实现可以分为创建多项式、输出多项式、求两个多项式的和几个部分。
①创建多项式。依次输出多项式的系数和指数，创建多项。当输入“0，0”即系数和指数都为0时，输入结束。创建多项式的代码如下。
#include<stdio.h>
#include<stdlib.h>
struct node
{
int exp;
float coef;
struct node *next;
};
typedef struct node ListNode;
ListNode *createpoly()
/*
创建多项式链表*/
{
ListNode *h=NULL,*p,*q=NULL;
int e;
float c;
printf("
请输入系数和指数:");
scanf("%f,%d",&c,&e);
while(e!=0||c!=0)
{
p=(ListNode*)malloc(sizeof(ListNode));
p->coef=c;
p->exp=e;
p->next=NULL;
if(h==NULL)
h=p;
else
q->next=p;
q=p;
printf("
请输入系数和指数:");
scanf("%f,%d",&c,&e);
}
return h;
}
②输出多项式。为了避免在指数为0时输出系数，增加一个条件语句。如果指数为0，则只输出系数。输出链表的代码如下。
void disppoly(ListNode *h)
/*
输出多项式*/
{
ListNode *p;
p=h;
while(p!=NULL)
{
if(p->exp==0)
printf("%.2f",p->coef);
else
printf("%fx^%d",p->coef,p->exp);
p=p->next;
if(p!=NULL)
printf("+");
}
printf("\n");
}
③求两个多项式的和，代码如下。
ListNode *addpoly(ListNode *h1,ListNode *h2)
/*
将两个多项式相加*/
{
ListNode *p,*r=NULL,*s1,*s2,*s=NULL;
float c;
int e;
s1=h1;
s2=h2;
while(s1!=NULL&&s2!=NULL)
{
if(s1->exp==s2->exp)
{
c=s1->coef+s2->coef;
e=s1->exp;
s1=s1->next;
s2=s2->next;
}
else if(s1->exp>s2->exp)
{
c=s1->coef;
e=s1->exp;
s1=s1->next;
}
else
{
c=s2->coef;
e=s2->exp;
s2=s2->next;
}
if(c!=0)
{
p=(ListNode*)malloc(sizeof(ListNode));
p->coef=c;
p->exp=e;
p->next=NULL;
if(s==NULL)
s=p;
else
r->next=p;
r=p;
}
}
while(s1!=NULL)
{
c=s1->coef;
e=s1->exp;
s1=s1->next;
if(c!=0)
{
p=(ListNode*)malloc(sizeof(ListNode));
p->coef=c;
p->exp=e;
p->next=NULL;
if(s==NULL)
s=p;
else
r->next=p;
r=p;
}
}
while(s2!=NULL)
{
c=s2->coef;
e=s2->exp;
s2=s2->next;
if(c!=0)
{
p=(ListNode*)malloc(sizeof(ListNode));
p->coef=c;
p->exp=e;
p->next=NULL;
if(s==NULL)
s=p;
else
r->next=p;
r=p;
}
}
return s;
}
④释放链表所占用的内存空间。在使用完链表后，需要释放链表所占用的内存空间，代码如下。
void deletepoly(ListNode *h)
/*
释放多项式所占用内存单元*/
{
ListNode *p,*r=h;
while(r!=NULL)
{
p=r->next;
free(r);
r=p;
}
}
⑤测试，代码如下。
void main()
{
ListNode *head1,*head2,*head;
printf("
创建第一个多项式:\n");
head1=createpoly();
printf("
创建第二个多项式:\n");
head2=createpoly();
printf("
将两个多项式相加:\n");
head=addpoly(head1,head2);
disppoly(head);
deletepoly(head);
}
程序运行结果如图2-76所示。
图2-76 程序运行结果