线性表的类型定义

B B A

线性表的顺序表示和实现

/*************************************************************
    date: April 2017
    copyright: Zhu En
    DO NOT distribute this code without my permission.
**************************************************************/
// 顺序表操作实现文件
//////////////////////////////////////////////////////////////
#include <stdio.h>
#include <stdlib.h>
#include "Seqlist.h"

SeqList* SL_Create(int maxlen)
// 创建一个顺序表。
// 与SqLst_Free()配对。
{
	SeqList* slist=(SeqList*)malloc(sizeof(SeqList));
	slist->data = (T*)malloc(sizeof(T)*maxlen);
	slist->max=maxlen;
	slist->len=0;
	return slist;
}

void SL_Free(SeqList* slist)
// 释放/删除 顺序表。
// 与SqLst_Create()配对。
{
	free(slist->data);
	free(slist);
}

void SL_MakeEmpty(SeqList* slist)
// 置为空表。
{
	slist->len=0;
}

int SL_Length(SeqList* slist)
// 获取长度。
{
	return slist->len;
}

bool SL_IsEmpty(SeqList* slist)
// 判断顺序表是否空。
{
	return 0==slist->len;
}

bool SL_IsFull(SeqList* slist)
// 判断顺序表是否满。
{
	return slist->len==slist->max;
}

T SL_GetAt(SeqList* slist, int i)
// 获取顺序表slist的第i号结点数据。
// 返回第i号结点的值。
{
	if(i<0||i>=slist->len) {
		printf("SL_GetAt(): location error when reading elements of the slist!\n");		
		SL_Free(slist);
		exit(0);
	}
	else 
		return slist->data[i];
}

void SL_SetAt(SeqList* slist, int i, T x)
// 设置第i号结点的值（对第i号结点的数据进行写）。
{
	if(i<0||i>=slist->len) {
		printf("SL_SetAt(): location error when setting elements of the slist!\n");		
		SL_Free(slist);
		exit(0);
	}
	else 
		slist->data[i]=x;
}

bool SL_InsAt(SeqList* slist, int i, T x)
// 在顺序表的位置i插入结点x, 插入d[i]之前。
// i 的有效范围[0,plist->len]。
{
    // 请在下面的Begin-End之间补充代码，插入结点。
    /********** Begin *********/
    // 检查插入位置是否有效
    if (i < 0 || i > slist->len) {
        return false;
    }
    // 检查顺序表是否已满
    if (SL_IsFull(slist)) {
        return false;
    }
    // 将位置i及之后的元素向后移动一位
    for (int j = slist->len; j > i; j--) {
        slist->data[j] = slist->data[j - 1];
    }
    // 在位置i插入新元素
    slist->data[i] = x;
    // 长度加1
    slist->len++;
    return true;
    /********** End **********/
}

T SL_DelAt(SeqList* slist, int i)
// 删除顺序表plist的第i号结点。
// i的有效范围应在[0,plist->len)内，否则会产生异常或错误。
// 返回被删除的数据元素的值。
{
    // 在下面的Begin-End之间补充代码，删除第i号结点。
    /********** Begin *********/
    // 保存要删除的元素值
    T deleted_value = slist->data[i];
    // 将位置i之后的元素向前移动一位
    for (int j = i; j < slist->len - 1; j++) {
        slist->data[j] = slist->data[j + 1];
    }
    // 长度减1
    slist->len--;
    // 返回被删除的元素值
    return deleted_value;
    /********** End **********/
}

int SL_FindValue(SeqList* slist, T x)
// 在顺序表表中查找第一个值为x的结点，返回结点的编号。
// 返回值大于等于0时表示找到值为x的结点的编号，-1表示没有找到。
{
	int i=0;
	while(i<slist->len && slist->data[i]!=x) i++;
	if (i<slist->len) return i;
	else return -1;
}

int SL_DelValue(SeqList* slist, T x)
// 删除第一个值为x的结点。
// 存在值为x的结点则返回结点编号, 未找到返回－1。
{
    // 在下面的Begin-End之间补充代码，删除第一个值为 x 的结点。
    /********** Begin *********/
    // 查找值为x的结点位置
    int pos = SL_FindValue(slist, x);
    // 如果找到了，删除该位置的结点
    if (pos >= 0) {
        SL_DelAt(slist, pos);
        return pos;
    }
    // 未找到，返回-1
    return -1;
    /********** End **********/
}

void SL_Print(SeqList* slist)
// 打印整个顺序表。
{
	if (slist->len==0) {
		printf("The slist is empty.\n");		
		return;
	}

	//printf("The slist contains: ");
	for (int i=0; i<slist->len; i++) {
		printf("%d  ", slist->data[i]);
	}

	printf("\n");	
	
}

线性表的链式表示和实现

/*************************************************************
    date: April 2017
    copyright: Zhu En
    DO NOT distribute this code without my permission.
**************************************************************/
// 单链表实现文件

#include <stdio.h>
#include <stdlib.h>
#include "LinkList.h"

// 1）
LinkList* LL_Create()
// 创建一个链接存储的线性表，初始为空表，返回llist指针。
{
    LinkList* llist=(LinkList*)malloc(sizeof(LinkList));
    llist->front=NULL;
    llist->rear=NULL;
    llist->pre=NULL;
    llist->curr=NULL;
    llist->position=0;
    llist->len=0;
    return llist;
}

// 2）	
void LL_Free(LinkList* llist)
// 释放链表的结点，然后释放llist所指向的结构。
{
    LinkNode* node=llist->front;
    LinkNode* nextnode;
    while(node){
        nextnode=node->next;
        free(node);
        node=nextnode;
    }
    free(llist);
}

// 3）	
void LL_MakeEmpty(LinkList* llist)
// 将当前线性表变为一个空表，因此需要释放所有结点。
{
    LinkNode* node=llist->front;
    LinkNode* nextnode;
    while(node){
        nextnode=node->next;
        free(node);
        node=nextnode;
    }
    llist->front=NULL;
    llist->rear=NULL;
    llist->pre=NULL;
    llist->curr=NULL;
    llist->position=0;
    llist->len=0;
}

// 4）	
int LL_Length(LinkList* llist)
// 返回线性表的当前长度。
{
    return llist->len;
}

// 5）	
bool LL_IsEmpty(LinkList* llist)
// 若当前线性表是空表，则返回true，否则返回TRUE。
{
    return llist->len==0;
}

// 6）  
bool LL_SetPosition(LinkList* llist, int i)
// 设置线性表的当前位置为i号位置。
// 设置成功，则返回true，否则返回false（线性表为空，或i不在有效的返回）。
// 假设线性表当前长度为len，那么i的有效范围为[0,len]。
{	
    int k;
    /* 若链表为空，则返回*/
    if (llist->len==0) return false;

    /*若位置越界*/
    if( i < 0 || i > llist->len)
    {	printf("LL_SetPosition(): position error");
        return false;
    }

    /* 寻找对应结点*/
    llist->curr = llist->front;
    llist->pre = NULL;
    llist->position = 0;
    for ( k = 0; k < i; k++)	{
        llist->position++;
        llist->pre = llist->curr;
        llist->curr = (llist->curr)->next;
    }
    
    /* 返回当前结点位置*/
    return true;
}

// 7)	
int LL_GetPosition(LinkList* llist)
// 获取线性表的当前位置结点的编号。
{
    return llist->position;
}

// 8）	
bool LL_NextPosition(LinkList* llist)
// 设置线性表的当前位置的下一个位置为当前位置。
// 设置成功，则返回true，否则返回false（线性表为空，或当前位置为表尾）。
{
    if (llist->position >= 0 && llist->position < llist->len)
    /* 若当前结点存在，则将其后继结点设置为当前结点*/
    {
        llist->position++;
        llist->pre = llist->curr;
        llist->curr = llist->curr->next;
        return true;
    }
    else 
        return false;
}

// 9）	
T LL_GetAt(LinkList* llist)
// 返回线性表的当前位置的数据元素的值。
{
    if(llist->curr==NULL)
    {
        printf("LL_GetAt(): Empty list, or End of the List.\n");
        LL_Free(llist);
        exit(1);
	}
    return llist->curr->data;
}

// 10）	
void LL_SetAt(LinkList* llist, T x)
// 将线性表的当前位置的数据元素的值修改为x。
{
    if(llist->curr==NULL)
    {
        printf("LL_SetAt(): Empty list, or End of the List.\n");
        LL_Free(llist);
        exit(1);
    }
    llist->curr->data=x;
}

// 11）	
bool LL_InsAt(LinkList* llist, T x)
// 在线性表的当前位置之前插入数据元素x。当前位置指针指向新数据元素结点。
// 若插入失败，返回false，否则返回true。
{	
    LinkNode *newNode=(LinkNode*)malloc(sizeof(LinkNode));
    if (newNode==NULL) return false;

    newNode->data=x;

    if (llist->len==0){
        /* 在空表中插入*/
        newNode->next=NULL;
        llist->front = llist->rear = newNode;
	}
    //当前位置为表头。
    else if (llist->pre==NULL)
    {
        /* 在表头结点处插入*/
        newNode->next = llist->front;
        llist->front = newNode;
    }
    else {  
        /* 在链表的中间位置或表尾后的位置插入*/
        newNode->next = llist->curr;
        llist->pre->next=newNode;
    }
    //插入在表尾后。
    if (llist->pre==llist->rear)
        llist->rear=newNode;
    /* 增加链表的大小*/
    llist->len++;
    /* 新插入的结点为当前结点*/
    llist->curr = newNode;
    return true;
}

// 12）	
bool LL_InsAfter(LinkList* llist, T x)
// 在线性表的当前位置之后插入数据元素x。空表允许插入。当前位置指针将指向新结点。
// 若插入失败，返回false，否则返回true。
{
    // 请在Begin-End之间补充代码，实现结点插入。
    /********** Begin *********/
    LinkNode *newNode=(LinkNode*)malloc(sizeof(LinkNode));
    if (newNode==NULL) return false;

    newNode->data=x;

    if (llist->len==0){
        /* 在空表中插入*/
        newNode->next=NULL;
        llist->front = llist->rear = newNode;
        llist->pre = NULL;
        llist->curr = newNode;
        llist->position = 0;
    }
    else if (llist->curr==NULL)
    {
        /* 当前位置为表尾之后，在表尾后插入*/
        newNode->next = NULL;
        llist->rear->next = newNode;
        llist->pre = llist->rear;
        llist->rear = newNode;
        llist->curr = newNode;
    }
    else {  
        /* 在当前位置之后插入*/
        newNode->next = llist->curr->next;
        llist->curr->next = newNode;
        /* 如果当前位置是表尾，更新表尾指针*/
        if (llist->curr == llist->rear)
            llist->rear = newNode;
        /* 更新当前位置*/
        llist->pre = llist->curr;
        llist->curr = newNode;
        llist->position++;
    }
    /* 增加链表的大小*/
    llist->len++;
    return true;

    /********** End **********/
}

// 13）	
bool LL_DelAt(LinkList* llist)
// 删除线性表的当前位置的数据元素结点。
// 若删除失败（为空表，或当前位置为尾结点之后），则返回false，否则返回true。
{	
    LinkNode *oldNode;
    /* 若表为空或已到表尾之后，则给出错误提示并返回*/
    if (llist->curr==NULL)
    {	
        printf("LL_DelAt(): delete a node that does not exist.\n");
        return false;
    }
    oldNode=llist->curr;
    /* 删除的是表头结点*/
    if (llist->pre==NULL)
    {	
        llist->front = oldNode->next;
    }
    /* 删除的是表中或表尾结点*/
    else if(llist->curr!=NULL){
        llist->pre->next = oldNode->next;
    }
    if (oldNode == llist->rear)	{
        /* 删除的是表尾结点，则修改表尾指针和当前结点位置值*/
        llist->rear = llist->pre;
    }

    /* 后继结点作为新的当前结点*/
    llist->curr = oldNode->next;

    /* 释放原当前结点*/
    free(oldNode);

    /* 链表大小减*/
    llist->len --;
    return true;
}

// 14）	
bool LL_DelAfter(LinkList* llist)
// 删除线性表的当前位置的后面那个数据元素。
// 若删除失败（为空表，或当前位置时表尾），则返回false，否则返回true。
{
    LinkNode *oldNode;
    /* 若表为空或已到表尾，则给出错误提示并返回*/
    if (llist->curr==NULL || llist->curr== llist->rear)
    {
        printf("LL_DelAfter():  delete a node that does not exist.\n");
        return false;
    }
    /* 保存被删除结点的指针并从链表中删除该结点*/
    oldNode = llist->curr->next;
    llist->curr->next=oldNode->next;
    
    if (oldNode == llist->rear)
        /* 删除的是表尾结点*/
        llist->rear = llist->curr;
    /* 释放被删除结点*/
    free(oldNode);
    /* 链表大小减*/
    llist->len --;
    return true;
}

// 15）	
int LL_FindValue(LinkList* llist, T x)
// 找到线性表中第一个值为x的数据元素的编号。
// 返回值-1表示没有找到，返回值>=0表示编号。
{
    LinkNode* p=llist->front;
    int idx=0;
    while(p!=NULL && p->data!=x) {
        idx++;
        p = p->next;
    }
    if (idx>=llist->len) return -1;
    else return idx;
}

// 16）	
int LL_DelValue(LinkList* llist, T x)
// 删除第一个值为x的数据元素，返回该数据元素的编号。如果不存在值为x的数据元素，则返回-1。
{
    int idx=LL_FindValue(llist, x);
    if (idx<0) return -1;
    LL_SetPosition(llist, idx);
    LL_DelAt(llist);
    return idx;
}

// 17）	
void LL_Print(LinkList* llist)
// 打印整个线性表。
{
    LinkNode* node=llist->front;
    while (node) {
        printf("%d ", node->data);
        node=node->next;
    }
    printf("\n");
}

线性链表

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
struct stu{
    char  name[32];
    struct stu  *next;
};

/*创建链表，参数n是初始化链表时建立的数据个数
prev：指向当前结点的前一个结点
cur：指向当前结点
head：保存表头结点的指针*/
struct stu* CreatList(int n){
    int i;
    char age[12];
    struct stu *prev,*cur,*head;
    head=(struct stu*)malloc(sizeof(struct stu));
    if(head==NULL){
        printf("Can't alloc memory\n");
        return NULL;
    }
    prev=head;
    head->name[0]='\0';
    head->next=NULL;
    for(i=1;i<=n;i++){
        cur=(struct stu*)malloc(sizeof(struct stu));
        if(cur==NULL){
            printf("Can't alloc memory\n");
            return NULL;                
        }
    scanf("%s",cur->name);
    // 请在下面的Begin-End之间补充代码，插入结点。
    /********** Begin *********/
    cur->next = prev->next;
    prev->next = cur;
    prev = cur;
    /********** End **********/ 
    }
    printf("线性链表创建成功！\n");
    return head;
}
/*遍历链表，打印链表数据*/
void Print(struct stu *head){
    struct stu *cur;
    cur=head->next;
    while(cur!=NULL){
        printf("%s\n",cur->name);
        cur=cur->next;
    }
}
int main(){
    int number=3;
    char _name[32];
    struct stu *head,*cur,*fro;
    head=CreatList(number);
    if(head==NULL)
        return -1;
    Print(head);
    return 0;   
}

循环链表

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include<stdlib.h>
#define ERROR 0
#define OK 1
typedef int EleType;
typedef struct CLinkNode
{
	EleType data;
	struct CLinkNode *next;
}CLinkNode,*CLinkList;
 
/*
初始化循环链表
*/
int InitCLinkList(CLinkList *list)
{
	if (list == NULL)
	{
		return ERROR;
	}
 
	int data = 0;
	CLinkNode* target = NULL;
	CLinkNode* head_node = NULL;
	printf("输入结点数据中...\n");
	while (1)
	{
		scanf("%d", &data);
		if (data == 0)
		{
			//退出循环标志，用户输入0 表示结束输入数据
			break;
		}

		if (*list == NULL)
		{
			CLinkNode* head= (CLinkNode*)malloc(sizeof(CLinkNode));
			//分配结点空间失败
			if (head == NULL)
			{
				exit(0);
			}
 
			*list = head;//链表指向头结点
 
			CLinkNode* node = (CLinkNode*)malloc(sizeof(CLinkNode));
			if (node == NULL)
			{
				exit(0);
			}
			node->data = data;
			node->next = head;
			head->next = node;
		}
		else
		{
			for (target = (*list)->next; target->next != *list; target = target->next);
			head_node = target->next;
 
			CLinkNode* node = (CLinkNode*)malloc(sizeof(CLinkNode));
			if (node == NULL)
			{
				exit(0);
			}
			node->data = data;
			node->next = head_node;
 
			target->next = node;//将新结点插入尾部
		}
 
	}
	return OK;
}
/*
往链表指定位置插入数据
list 循环链表
loc 第loc位置插入元素，loc 从1 开始计数
data 插入元素的数据域
*/
int InsertCLinkNode(CLinkList list,int loc, EleType data)
{
	if (list == NULL || loc < 1)
		return ERROR;
	/*
	循环目的：找到第loc-1位置结点
	*/
	int i = 1;
	CLinkNode* node = list;//刚开始node指向头结点
	while (node->next!=list && i < loc)
	{
		node = node->next;
		i++;
	}
	if (i == loc)
	{
		CLinkNode* new_node = (CLinkNode*)malloc(sizeof(CLinkNode));
		if (new_node == NULL)
		{
			exit(0);
		}
		new_node->data = data;
		new_node->next = node->next;//新结点指针域 指向前驱结点的后继结点
		node->next = new_node;//将新结点加入链表
	}
	else
	{
		return	ERROR;
	}
 
	return OK;
}
/*
删除指定结点，通过指针返回删除结点的数据，并保存至data
*/
int DelCLinkNode(CLinkList list,int loc, EleType* data)
{
	if (list == NULL || loc < 1)
		return ERROR;
	/*
	循环目的：找到第loc-1位置结点
	*/
	int i = 1;// 按人类的读法 i表示第i个位置 和 loc 表达意思一致
	CLinkNode* node = list;//刚开始node指向头结点
	while (node->next != list && i < loc)
	{
		node = node->next;
		i++;
	}
	//循环结束 node 指向 loc-1 位置 且 node 不能为尾结点,为什么不能为尾结点？因为不能删除 位置上没有元素的结点！
	if (i == loc && node->next != list)
	{
        // 请在下面的Begin-End之间补充代码，完成对结点的删除。
        /********** Begin *********/

		CLinkNode* del_node = node->next;  // 要删除的结点
		*data = del_node->data;             // 保存删除结点的数据
		node->next = del_node->next;        // 前一个结点指向后一个结点
		free(del_node);                     // 释放内存

            
        /********** End **********/
 
	}
	return OK;
}
/*
展示循环链表元素
*/
int ShowCLinkList(CLinkList list)
{
	if (list == NULL)
	{
		return ERROR;
	}
	CLinkNode* target = NULL;
	
	for (target = list->next; target != list; target = target->next)
		printf("%d \t",target->data);
	printf("\n");
	return OK;
}
int main(int argc, char *argv[])
{
	int flag = 0;
	CLinkList list = NULL;
	list = NULL;
	InitCLinkList(&list);
	printf("--------循环链表初始元素------\n");
	ShowCLinkList(list); 
	int loc = 2;
	int data = 0;
	DelCLinkNode(list, loc, &data);
	printf("--------删除第二个结点后------\n");
	ShowCLinkList(list); 
	return 0;
}

双向链表

#include <stdio.h>
#include <stdlib.h>
//节点结构
typedef struct line {
    struct line * prior;
    int data;
    struct line * next;
}line;
//双链表的创建函数
line* initLine(line * head);
//输出双链表的函数
void display(line * head);

int main() {
    //创建一个头指针
    line * head = NULL;
    //调用链表创建函数
    head = initLine(head);
    printf("链表结构为：");
    //输出创建好的链表
    display(head);
    //显示双链表的优点
    printf("链表中第 4 个节点的直接前驱是：%d", head->next->next->next->prior->data);
    return 0;
}
line* initLine(line * head) {
	printf("输入数据中...\n");
	int data[6]={0};
	for(int i=0;i<6;i++){
		scanf("%d",&data[i]);
	} 
    line * list = NULL;
    //创建一个首元节点，链表的头指针为head
    head = (line*)malloc(sizeof(line));
    //对节点进行初始化
    head->prior = NULL;
    head->next = NULL;
    head->data = data[0];
    //声明一个指向首元节点的指针，方便后期向链表中添加新创建的节点
    list = head;
    for (int i = 1; i <= 5; i++) {

        // 请在下面的Begin-End之间补充代码，插入结点，其中结点数据为data[i]。
        /********** Begin *********/
        line * body = (line*)malloc(sizeof(line));
        body->prior = NULL;
        body->next = NULL;
        body->data = data[i];
        list->next = body;
        body->prior = list;
        list = list->next;
        /********** End **********/ 
    }
    //返回新创建的链表
    return head;
}
void display(line * head) {
    line * temp = head;
    while (temp) {
        //如果该节点无后继节点，说明此节点是链表的最后一个节点
        if (temp->next == NULL) {
            printf("%d\n", temp->data);
        }
        else {
            printf("%d <-> ", temp->data);
        }
        temp = temp->next;
    }
}

一元多项式的表示及相加

#include <stdio.h>
#include <stdlib.h>
typedef struct PLnode{
    //数据域，coef 表示系数，expn 表示指数
    float coef;
    int expn;
    //指针域
    struct PLnode *next;
}PLnode,*PLinkList;

//一元多项式的链表表示创建函数，输入 m 项的系数和指数，建立表示一元多项式的有序链表L
void creatpolyn(PLinkList L, int m){
    int i;
    float coef;
    int expn;
    PLinkList tail,n;
    L->coef = m;
    L->expn = -1;
    tail = L;
    for(i=1 ; i<=m ; i++){
         n = (PLinkList)malloc(sizeof(PLnode));
         scanf("%f",&coef);
         scanf("%d",&expn);
         n->coef = coef;
         n->expn = expn;
         n->next = NULL;
         tail->next = n;
         tail = n;
    }
}
//完成多项式相加运算，即 Lc = La + Lb，并销毁一元多项式 Lb
PLinkList addpolyn(PLinkList La , PLinkList Lb){
    int x,len;
    float y;
    PLinkList Lc,pa,pb,pc,u;
    Lc = La;
    len = 0;
    pc = Lc;
    //另pa，pb 指向La 、Lb 的首元结点
    pa = La->next;
    pb = Lb->next;
    //通过 pa，pb 遍历链表 La、Lb，只有两指针同时存在时，才需要讨论
    while(pa && pb){
        x = pa->expn-pb->expn;
        //判断pa 所指结点的指数与pb 所指结点指数的大小关系
        if(x<0){
            //如果小，则找去 qa 结点到Lc 上
            pc = pa;
            len++;
            pa = pa->next;
        }
        //如果相等，则判断两结点的系数和是否为0
        else if(x == 0){
            // 请在下面的Begin-End之间补充代码，完成一元多项式的相加。
            /********** Begin *********/
            y = pa->coef + pb->coef;  // 系数相加
            if(y != 0){  // 和不为0
                pa->coef = y;  // 修改pa的系数
                pc = pa;  // pc指向pa
                len++;  // 长度加1
                pa = pa->next;  // pa后移
                u = pb;  // 保存pb
                pb = pb->next;  // pb后移
                free(u);  // 释放原pb节点
            }
            else{  // 和为0，删除pa和pb节点
                u = pa;  // 保存pa
                pa = pa->next;  // pa后移
                free(u);  // 释放pa节点
                u = pb;  // 保存pb
                pb = pb->next;  // pb后移
                free(u);  // 释放pb节点
                // pc->next应该指向新的pa
                pc->next = pa;
            }
            /********** End **********/
        }
        //如果pb 所指结点指数值小，则摘取pb所指结点到 LC链表上
        else{
            u = pb->next;
            pb->next= pa;
            pc->next=pb;
            pc = pb;
            len++;
            pb = u;
        }
    }
    //由于是在 La 上进行一元多项式的加和，所以如果运行过程 pa 不再有结点，而pb 上有，则需要将pb剩余结点链接到 Lc 上
    if(pb){
        pc->next = pb;
    }
    //计算 Lc 的长度
    while(pc){
        pc = pc->next;
        if(pc){
            len++;
        }
    }
    //Lc 的头结点中记录Lc 链表的长度
    Lc->coef = len;
    //加和完成的同时，释放Lb 结点
    free(Lb);
    return Lc;
}
//根据链表存储信息。输出结点 q
void printpoly(PLinkList q){
    if(q->expn == 0){
        printf("%.0f",q->coef);
    }
    else if(q->expn == 1){
        if(q->coef == 1){
            printf("x");
        }
        else if (q->coef == -1){
            printf("-x");
        }
        else{
            printf("%.0f",q->coef);
            printf("x");
        }
    }
    else if (q->coef == 1){
        printf("x^%d",q->expn);
    }
    else if(q->coef == -1){
        printf("-x^%d",q->expn);
    }
    else{
        printf("%.0fx^%d",q->coef,q->expn);
    }
}
//输出一元多项式L
void printpolyn(PLinkList L){
    int n;
    PLinkList p;
    p = L->next;
    n = 0;
    while(p){
        n++;
        if(n == 1){
            printpoly(p);
        }else if(p->coef>0){
            printf("+");
            printpoly(p);
        }else{
            printpoly(p);
        }
        p = p->next;
    }
}
int main(){
    PLinkList La,Lb,Lc;
    int m,n;
    //根据 n 的值，创建链表La
    scanf("%d",&n);
    La = (PLinkList)malloc(sizeof(PLnode));
    creatpolyn(La,n);
    //根据 m 的值，创建 Lb
    scanf("%d",&m);
    Lb = (PLinkList)malloc(sizeof(PLnode));
    creatpolyn(Lb,m);
    //输出La和Lb
    printf("La=");
    printpolyn(La);
    printf("\nLb=");
    printpolyn(Lb);
    //计算La+Lb，结果保存在 Lc中
    printf("\n计算结果为：");
    Lc = addpolyn(La,Lb);
    printf("\nLc=");
    printpolyn(Lc);
    return 0;
}