线性链表及其基本操作及用链表实现的多项式

线性链表及其基本操作

链表在空间的合理利用上和插入、删除时不需要移动等优点，因此在很多场合下，它是线性表的首先储存结构。然而它也存在着实现某些基本操作，如求线性表的长度时不如顺序储存结构的特点。因而从新定义线性链表及其基本操作

头文件：

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define MYOVERFLOW -2
typedef int Status;
typedef int Elemtype;
typedef struct LNode{//结点类型
    Elemtype data;
    LNode *next;
}*Link,*Position;
typedef struct{//链表类型
    Link head, tail;//分别指向线性链表中的头结点和最后一个结点
    int len;//指示线性链表中数据元素的个数
}LinkList;
Status compare(Elemtype s1, Elemtype s2);//比较两者的大小，相等返回TRUE，否则返回FALSE
Status visit(LinkList L);//若存在，则遍历L返回OK，否则返回ERROR
Status Create_List(LinkList &);//创造一个链表
Status MakeNode(Link &p, Elemtype e);
//分配由p指向的值为e的结点，并返回OK；若分配失败，则返回ERROR
void FreeNode(Link &p);
//释放p所指结点
Status InitList(LinkList &L);
//构造一个空的线性链表L
Status DestroyList(LinkList &L);
//销毁线性链表L，L不再存在
Status ClearList(LinkList &L);
//将线性链表L重置为空表，并释放原链表的结点空间
Status InsFirst(Link h, Link s);
//已知h指向线性链表的头结点，将s所指结点插入在第一个结点之前
Status DelFirst(Link h, Link &q);
//已知h指向线性链表的头结点，删除链表中的第一个结点并以q返回
Status Append(LinkList &L, Link s);
//将指针s所指（彼此以指针相链）的一串结点链接在线性链表L的最后一个结点
//之后，并改变链表L的尾指针指向新的尾结点
Status Remove(LinkList &L, Link &q);
//删除线性链表L中的尾结点并以q返回，改变链表L的尾指针指向新的尾结点
Status InsBefore(LinkList &L, Link &p, Link s);
//已知p指向线性链表L中的一个结点，将s所指结点插入在p所指结点之前，
//并修改指针p指向新插入的结点
Status InsAfter(LinkList &L, Link &p, Link s);
//已知p指向线性链表L中的一个结点，将s所指结点插入在p所指结点之后，
//并修改指针p指向新插入的结点
Status SetCurElem(Link &p, Elemtype e);
//已知p指向线性链表中的一个结点，用e更新p所指结点中数据元素的值
Elemtype GetCurElem(Link p);
//已知p指向线性链表中的一个结点，返回p所指结点中数据元素的值
Status ListEmpty(LinkList L);
//若线性链表L为空表，则返回TRUE，否则返回FALSE
int ListLength(LinkList L);
//返回线性链表L中元素个数
Position GetHead(LinkList L);
//返回线性链表L中头结点的位置
Position GetLast(LinkList L);
//返回线性链表L中最后一个结点的位置
Position PriorPos(LinkList L, Link p);
//已知p指向线性链表L中的一个结点，返回p所指结点的直接前驱的位置，
//若无前驱，则返回NULL
Position NextPos(LinkList L, Link p);
//已知p指向线性链表L中的一个结点，返回p所指结点的直接后继的位置，
//若无后继，则返回NULL
Status LocatePos(LinkList L,int i, Link &p);
//返回p指示线性链表L中第i个结点的位置并返回OK，i值不合法时返回ERROR
Position LocateElem(LinkList L, Elemtype e, Status(*P)(Elemtype, Elemtype));
//返回线性链表L中第一个与e满足函数p（）判定关系的元素的位置，
//若不存在这样的元素，则返回NULL
Status ListTraverse(LinkList L, Status(*visit)(LinkList));
//依次对L的每个元素调用函数visit（）。一旦visit（）失败，则操作失败

上述操作的实现：

Status MakeNode(Link &p, Elemtype e)
//分配由p指向的值为e的结点，并返回OK；若分配失败，则返回ERROR
{
    p = new LNode;//为*p分配空间
    if (p){
        p->data = e;
        return OK;
    }
    else
        return ERROR;
}
void FreeNode(Link &p)
//释放p所指结点
{
    delete p;//删除*p所占用的空间
}
Status InitList(LinkList &L)
//构造一个空的线性链表L
{
    Link p = new LNode;
    if (p){
        L.head = p;//新建一个结点，并且头指针和尾指针都指向该结点，长度为0
        L.tail = L.head;
        L.len = 0;
        return OK;
    }
    else
        return ERROR;
    
}
Status Create_List(LinkList &L)//创造一个链表
{
    if (InitList(L)){//初始化链表
        cout << "please input the length of the linklist:" << endl;
        int len;
        cin >> len;
        L.len = len;
        cout << "please input the data of the linklist:" << endl;
        for (int i = 1; i <= len; i++){
            Link temp = new LNode;//创建结点
            cin >> temp->data;//输入结点的数据元素
            L.tail->next = temp;//将结点插入到表的末尾
            L.tail = L.tail->next;
            }
        L.tail->next = NULL;
        return OK;
    }
    else return ERROR;
}
Status visit(LinkList L)//若存在，则遍历L返回OK，否则返回ERROR
{
    if (L.head){
        cout << "the data of the list is:" << endl;
        L.head = L.head->next;
        for (; L.head != L.tail;){
            cout << L.head->data << " ";
            L.head = L.head->next;
        }
        cout << L.tail->data << endl;//最后输出尾结点的数据元素
        return OK;
    }
    else return ERROR;
}
Status ListTraverse(LinkList L, Status(*visit)(LinkList))
//依次对L的每个元素调用函数visit（）。一旦visit（）失败，则操作失败
{
    if (visit(L)){
        
        return OK;}
    else
    {
        return ERROR;
    }
}
Status DestroyList(LinkList &L)
//销毁线性链表L，L不再存在
{
    
    for (; L.head != L.tail; L.len--){//释放链表中结点所占的内存空间
        Link pt;
        pt = L.head;
        L.head = L.head->next;
        delete pt;
    }
    delete L.head;
    if (L.len == 0){//使L的头指针和尾指针不指向任何地方
        L.head = NULL;
        L.tail = NULL;
        LinkList *p = &L;
        delete p;
        return OK;
    }
    else
    {
        return ERROR;
    }
}
Status ClearList(LinkList &L)
//将线性链表L重置为空表，并释放原链表的结点空间
{
    Link temp = L.head;
    L.head = L.head->next;
    for (; L.len>0; L.len--){//释放链表中的结点所占的内存空间
        Link pt;
        pt = L.head;
        L.head = L.head->next;
        delete pt;
    }
    L.head = temp;
    if (L.len == 0&&L.head==L.tail){
        return OK;
    }
    else
    {
        return ERROR;
    }
}
Status InsFirst(Link h, Link s)
//已知h指向线性链表的头结点，将s所指结点插入在第一个结点之前
{
    if (h){//判断头结点是否存在
        s->next = h->next;//将s结点插入到表中
        h->next = s;
        return OK;
    }
    else return ERROR;
}
Status DelFirst(Link h, Link &q)
//已知h指向线性链表的头结点，删除链表中的第一个结点并以q返回
{
    if (h->next){//判断第一个结点是否存在
        q = h->next;//给q赋予第一个结点的值
        h->next = h->next->next;//将第一个结点从链表中删除
        q->next = NULL;
        return OK;
    }
    else return ERROR;
}
Status Append(LinkList &L, Link s)
//将指针s所指（彼此以指针相链）的一串结点链接在线性链表L的最后一个结点
//之后，并改变链表L的尾指针指向新的尾结点
{
    if (s){
        Link temp = s;
        for (; s->next; s = s->next)
        {
            L.len++;
        }//让S移动到链表的最后一个结点
        L.len++;
        L.tail->next = temp;
        L.tail = s;//使L.tail指向最后一个结点
        return OK;
    }
    else return ERROR;
}
Status Remove(LinkList &L, Link &q)
//删除线性链表L中的尾结点并以q返回，改变链表L的尾指针指向新的尾结点
{
    if (L.head != L.tail){
        q = L.tail;//用q返回尾结点
        Link temp;
        temp = L.head;
        for (; temp->next != L.tail; temp = temp->next){}//使temp指向尾结点的前一个结点
        L.tail = temp;//使尾结点指向新的尾结点
        L.tail->next = NULL;
        delete temp->next;//删除旧的尾结点
        L.len--;
        return OK;
    }
    else return ERROR;
}
Status InsBefore(LinkList &L, Link &p, Link s)
//已知p指向线性链表L中的一个结点，将s所指结点插入在p所指结点之前，
//并修改指针p指向新插入的结点
{
    Link temp=L.head;
    for (; temp->next != p&&temp; temp = temp->next){}
    if (temp->next == p){
        s->next = p;
        temp->next = s;
        p = s;
        L.len++;
        return OK;
    }
    else return ERROR;
}
Status InsAfter(LinkList &L, Link &p, Link s)
//已知p指向线性链表L中的一个结点，将s所指结点插入在p所指结点之后，
//并修改指针p指向新插入的结点
{
    Link temp = L.head;
    for (; temp != p&&temp; temp = temp->next){}
    if (temp == p){
        temp->next=s;
        s->next = p;
        p = s;
        if (temp == L.tail)
            L.tail = s;
        L.len++;
        return OK;
    }
    else return ERROR;
}
Status SetCurElem(Link &p, Elemtype e)
//已知p指向线性链表中的一个结点，用e更新p所指结点中数据元素的值
{
    if (p){
        p->data = e;
        return OK;
    }
    else return ERROR;
}
Elemtype GetCurElem(Link p)
//已知p指向线性链表中的一个结点，返回p所指结点中数据元素的值
{
    if (p){
        return p->data;
    }
    else return NULL;
}
Status ListEmpty(LinkList L)
//若线性链表L为空表，则返回TRUE，否则返回FALSE
{
    if (L.len == 0){
        return TRUE;
    }
    else return FALSE;
}
int ListLength(LinkList L)
//返回线性链表L中元素个数
{
    return L.len;
}
Position GetHead(LinkList L)
//返回线性链表L中头结点的位置
{
    return L.head;
}
Position GetLast(LinkList L)
//返回线性链表L中最后一个结点的位置
{
    return L.tail;
}
Position PriorPos(LinkList L, Link p)
//已知p指向线性链表L中的一个结点，返回p所指结点的直接前驱的位置，
//若无前驱，则返回NULL
{
    Link temp = L.head;
    for (; temp->next != p&&temp; temp = temp->next){}
    if (temp->next == p){
        return temp;
    }
    else return NULL;
}
Position NextPos(LinkList L, Link p)
//已知p指向线性链表L中的一个结点，返回p所指结点的直接后继的位置，
//若无后继，则返回NULL
{
    Link temp = L.head->next;
    for (; temp != p->next&&temp; temp = temp->next){}
    if (temp == p->next){
        return temp;
    }
    else return NULL;
}
Status LocatePos(LinkList L, int i, Link &p)
//返回p指示线性链表L中第i个结点的位置并返回OK，i值不合法时返回ERROR
{
    for (int j = 1; L.head&&j <= i; j++, L.head = L.head->next){}
    if (L.head){
        p = L.head;
        return OK;
    }
    else return ERROR;
}
Status compare(Elemtype s1, Elemtype s2){
    if (s1 == s2)return OK;
    else return ERROR;
}
Position LocateElem(LinkList L, Elemtype e, Status(*P)(Elemtype s1, Elemtype s2))
//返回线性链表L中第一个与e满足函数p（）判定关系的元素的位置，
//若不存在这样的元素，则返回NULL
{
    for (; !P(L.head->next->data, e) && L.head->next; L.head = L.head->next){}
    if (!L.head->next){
        return L.head->next;
    }
    else return NULL;
}

用这些基本操作实现插入操作和将两个非递减排列合并成一个新的非递减序列

头文件：

Status ListInsert_L(LinkList &L, int i, Elemtype e);
//在带头结点的单链线性表L的第i个元素之前插入元素e
Status MergeList_L(LinkList &La, LinkList &Lb, LinkList &Lc, int(*compare)(Elemtype, Elemtype));
//已知单链线性表La和Lb的元素按值非递减排列。
//归并La和Lb得到新的单链线性表Lc，Lc的元素也按值非递减排列
int compare1(Elemtype a, Elemtype b);//返回a-b的值

操作的实现：

Status ListInsert_L(LinkList &L, int i, Elemtype e)
//在带头结点的单链线性表L的第i个元素之前插入元素e
{ 
    Link h,s;    
    if (!MakeNode(s, e))return ERROR;
    if (i = L.len + 1){
        s->next = L.tail->next;
        L.tail->next = s;
        L.tail = L.tail->next;
    }
    else {
        if (!LocatePos(L, i - 1, h))return ERROR;
        InsFirst(h, s);    
    }
    L.len++;
    return OK;
}
int compare1(Elemtype a, Elemtype b){
    return a - b;
}
Status MergeList_L(LinkList &La, LinkList &Lb, LinkList &Lc, int(*compare)(Elemtype, Elemtype))
//已知单链线性表La和Lb的元素按值非递减排列。
//归并La和Lb得到新的单链线性表Lc，Lc的元素也按值非递减排列
{
    if (!InitList(Lc))return ERROR;
    Link ha; Link hb;
    ha = GetHead(La); hb = GetHead(Lb);
    Link pa; Link pb;
    pa = NextPos(La, ha);
    pb = NextPos(Lb, hb);
    int lenLc = La.len + Lb.len;
    while (pa&&pb){
        Link q;
        Elemtype a, b;
        a = GetCurElem(pa); b = GetCurElem(pb); 
        if (compare(a, b)<=0){
            DelFirst(ha, q);
            Append(Lc, q);
            pa = NextPos(La, ha);    
        }
        else{
            DelFirst(hb, q);
            Append(Lc, q);
            pb = NextPos(Lb, hb);
        }
    }   
        if (pa)Append(Lc, pa);
        else Append(Lc, pb); 
        FreeNode(ha); FreeNode(hb);
        Lc.len = lenLc;
    return OK;
}

主函数：

int _tmain(int argc, _TCHAR* argv[])
{
    LinkList l1,l2,l3;
    Create_List(l1);
    Create_List(l2);
    MergeList_L(l1, l2, l3,compare1);
    ListTraverse(l3, visit);
    return 0;
}

最终得到的结果如下图：

用链表实现的多项式

链表的头文件：

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define MYOVERFLOW -2
typedef int Status;
typedef int Elemtype;
typedef struct LNode{//结点类型
    Elemtype data;
    LNode *next;
}*Link,*Position;
typedef struct{//链表类型
    Link head, tail;//分别指向线性链表中的头结点和最后一个结点
    int len;//指示线性链表中数据元素的个数
}LinkList;
Status compare(Elemtype s1, Elemtype s2);//比较两者的大小，相等返回TRUE，否则返回FALSE
Status visit(LinkList L);//若存在，则遍历L返回OK，否则返回ERROR
Status Create_List(LinkList &);//创造一个链表
Status MakeNode(Link &p, Elemtype e);
//分配由p指向的值为e的结点，并返回OK；若分配失败，则返回ERROR
void FreeNode(Link &p);
//释放p所指结点
Status InitList(LinkList &L);
//构造一个空的线性链表L
Status DestroyList(LinkList &L);
//销毁线性链表L，L不再存在
Status ClearList(LinkList &L);
//将线性链表L重置为空表，并释放原链表的结点空间
Status InsFirst(Link h, Link s);
//已知h指向线性链表的头结点，将s所指结点插入在第一个结点之前
Status DelFirst(Link h, Link &q);
//已知h指向线性链表的头结点，删除链表中的第一个结点并以q返回
Status Append(LinkList &L, Link s);
//将指针s所指（彼此以指针相链）的一串结点链接在线性链表L的最后一个结点
//之后，并改变链表L的尾指针指向新的尾结点
Status Remove(LinkList &L, Link &q);
//删除线性链表L中的尾结点并以q返回，改变链表L的尾指针指向新的尾结点
Status InsBefore(LinkList &L, Link &p, Link s);
//已知p指向线性链表L中的一个结点，将s所指结点插入在p所指结点之前，
//并修改指针p指向新插入的结点
Status InsAfter(LinkList &L, Link &p, Link s);
//已知p指向线性链表L中的一个结点，将s所指结点插入在p所指结点之后，
//并修改指针p指向新插入的结点
Status SetCurElem(Link &p, Elemtype e);
//已知p指向线性链表中的一个结点，用e更新p所指结点中数据元素的值
Elemtype GetCurElem(Link p);
//已知p指向线性链表中的一个结点，返回p所指结点中数据元素的值
Status ListEmpty(LinkList L);
//若线性链表L为空表，则返回TRUE，否则返回FALSE
int ListLength(LinkList L);
//返回线性链表L中元素个数
Position GetHead(LinkList L);
//返回线性链表L中头结点的位置
Position GetLast(LinkList L);
//返回线性链表L中最后一个结点的位置
Position PriorPos(LinkList L, Link p);
//已知p指向线性链表L中的一个结点，返回p所指结点的直接前驱的位置，
//若无前驱，则返回NULL
Position NextPos(LinkList L, Link p);
//已知p指向线性链表L中的一个结点，返回p所指结点的直接后继的位置，
//若无后继，则返回NULL
Status LocatePos(LinkList L,int i, Link &p);
//返回p指示线性链表L中第i个结点的位置并返回OK，i值不合法时返回ERROR
Position LocateElem(LinkList L, Elemtype e, Status(*P)(Elemtype, Elemtype));
//返回线性链表L中第一个与e满足函数p（）判定关系的元素的位置，
//若不存在这样的元素，则返回NULL
Status ListTraverse(LinkList L, Status(*visit)(LinkList));
//依次对L的每个元素调用函数visit（）。一旦visit（）失败，则操作失败

下面是关于多项式的一些操作的头文件

#include"LinkList.h"
typedef LinkList polynomial;
int compare2(Elemtype e1, Elemtype e2);
//如果e1的指数值<(或=)(或>)e2的指数值，分别返回-1，0，和+1
Status LocateElem(LinkList L, Elemtype e, Position &q, int(*compare)(Elemtype, Elemtype));
//若有序链表L中存在与e满足判定函数compare（）取值为0的元素，则q指示L中第一个值为e的结点的位置
//并返回TRUE；否则q指示第一个与e满足判定函数compare（）取值＞0的元素的前驱的位置，并返回FALSE
Status OrderInsert(LinkList &L, Elemtype e, int(*compare)(Elemtype, Elemtype));
//按有序判定函数compare（）的约定，将值为e的结点插入到有序链表L的适当位置上
void CreatPolyn(polynomial &P);
//输入n项的系数和指数，建立表示一元多项式的有序链表P
void DestroyPolyn(polynomial &P);
//销毁一元多项式P
void PrintPolyn(polynomial p);
//打印输出一元多项式P
int PolynLength(polynomial P);
//返回一元多项式P中的项数
void AddPolyn(polynomial &Pa, polynomial &Pb);
//完成多项式相加运算，即：Pa=Pa+Pb，并销毁一元多项式Pb
void SubtractPolyn(polynomial &Pa, polynomial &Pb);
//完成多项式减法运算，即：Pa=Pa-Pb，并销毁一元多项式Pb
void MultiplyPolyn(polynomial &Pa, polynomial &Pb);
//完成多项式相乘运算，即：Pa=Pa*Pb，并销毁一元多项式Pb

上述基本操作的实现：

int compare2(Elemtype e1, Elemtype e2)
//如果e1的指数值<(或=)(或>)e2的指数值，分别返回-1，0，和+1
{
    int i = 0;
    if (e1.expn < e2.expn)i = -1;
    if (e1.expn>e2.expn)i = 1;
    return i;
}
Status LocateElem(LinkList L, Elemtype e, Position &q, int(*compare)(Elemtype, Elemtype))
//若有序链表L中存在与e满足判定函数compare（）取值为0的元素，则q指示L中第一个值为e的结点的位置
//并返回TRUE；否则q指示NULL，并返回FALSE
{
    if (L.head->next){
        for (; L.head->next; L.head = L.head->next){
            if (!compare(L.head->next->data, e))break;
        }
        q = L.head->next;
        if (!L.head->next)//判断是否全部结点都不满足compare（）函数，如果有满足的则返回TRUE
            return TRUE;
        else
            return FALSE;//否则返回FALSE
    }
    q = NULL;
    return FALSE;
}
Status OrderInsert(LinkList &L, Elemtype e, int(*compare)(Elemtype, Elemtype))
//按有序判定函数compare（）的约定，将值为e的结点插入到有序链表L的适当位置上,注意L若是个空链表，则将值为e的结点插入到head的后面
{
    Link temp=L.head,p=L.head;
        for (; temp->next; temp = temp->next){
            if (compare(e, temp->next->data) == -1)break;//找到前一个结点
        }
            Link t;
            MakeNode(t, e);
            t->next = temp->next;
            if (temp->next)L.tail = t;//将值为e的结点插入到L中，如果为最后一个结点，则要改变尾结点的指向
            temp->next = t;
            L.len++;
            return OK;
}
void CreatPolyn(polynomial &P)
//输入m项的系数和指数，建立表示一元多项式的有序链表P
{
    Create_List(P);
}
void DestroyPolyn(polynomial &P)
//销毁一元多项式P
{
    DestroyList(P);
}
void PrintPolyn(polynomial p)
//打印输出一元多项式P
{
    ListTraverse(p, visit);
}
int PolynLength(polynomial P)
//返回一元多项式P中的项数
{
    return ListLength(P);
}
void AddPolyn(polynomial &Pa, polynomial &Pb)
//完成多项式相加运算，即：Pa=Pa+Pb，并销毁一元多项式Pb
{
    Link ta = Pa.head->next;
    Link tb = Pb.head->next;
    Link tta = Pa.tail;
    Link beforeta = Pa.head;
    for (; ta&&tb;){
        if (ta->data.expn < tb->data.expn){//如果ta的指数小于tb的指数，则只需ta向后移
            beforeta = ta; ta = ta->next;
        }
        else if (ta->data.expn == tb->data.expn){//如果==
            ta->data.ceof += tb->data.ceof;//ta的系数为两者系数之和
            Link tempb = tb;//删除tb，tb向后移一位
            tb = tb->next;
            delete tempb;
        if (ta->data.ceof == 0){//如果系数之和为0，则要删除ta
                Link tempa = ta;
                beforeta->next = ta->next;
                ta = ta->next;
                Pa.len--;
                if (tempa == tta)tta = beforeta;
                delete tempa;
            }
        }
        else {//如果是>
            Link temp=tb->next;//则要把tb插进来
            beforeta->next = tb;
            tb->next = ta;
            beforeta =tb;
            tb = temp;
            Pa.len++;
        }
    }
    if (!ta){//如果是ta先为空，则要把tb的剩余元素插进来
        tta->next = tb;
        Pa.tail = Pb.tail;
        for (; tb; tb = tb->next)Pa.len++;
        delete Pb.head;
    }
}
void SubtractPolyn(polynomial &Pa, polynomial &Pb)
//完成多项式减法运算，即：Pa=Pa-Pb，并销毁一元多项式Pb
{   Link tb = Pb.head->next;//将tb数据元素的系数全部变成相反数，然后进行加法的运算
for (; tb; tb = tb->next){
    tb->data.ceof = -tb->data.ceof; 
}
    Link ta = Pa.head->next;
    tb = Pb.head->next;
    Link tta = Pa.tail;
    Link beforeta = Pa.head;
    for (; ta&&tb;){
        if (ta->data.expn < tb->data.expn){//如果ta的指数小于tb的指数，则只需ta向后移
            beforeta = ta; ta = ta->next;
        }
        else if (ta->data.expn == tb->data.expn){//如果==
            ta->data.ceof += tb->data.ceof;//ta的系数为两者系数之和
            Link tempb = tb;//删除tb，tb向后移一位
            tb = tb->next;
            delete tempb;
            if (ta->data.ceof == 0){//如果系数之和为0，则要删除ta
                Link tempa = ta;
                beforeta->next = ta->next;
                ta = ta->next;
                Pa.len--;
                if (tempa == tta)tta = beforeta;
                delete tempa;
            }
        }
        else {//如果是>
            Link temp = tb->next;//则要把tb插进来
            beforeta->next = tb;
            tb->next = ta;
            beforeta = tb;
            tb = temp;
            Pa.len++;
        }
    }
    if (!ta){//如果是ta先为空，则要把tb的剩余元素插进来
        tta->next = tb;
        Pa.tail = Pb.tail;
        for (; tb; tb = tb->next)Pa.len++;
        delete Pb.head;
    }
}
void MultiplyPolyn(polynomial &Pa, polynomial &Pb)
//完成多项式相乘运算，即：Pa=Pa*Pb，并销毁一元多项式Pb
{
    polynomial Pc,Pd;
    InitList(Pc);//构造一个空的链表
    Pc.head->next = NULL;
    Link tb = Pb.head->next;
    for (; tb; ){
        Link ta = Pa.head->next;
        InitList(Pd);
        Pd.head->next = NULL;
        Link td = Pd.head;
        Link tempd;
        for (; ta; ta = ta->next){
            tempd=new LNode;
            tempd->data.ceof = ta->data.ceof*tb->data.ceof;
            tempd->data.expn = ta->data.expn + tb->data.expn;
            tempd->next = NULL;
            td->next= tempd;
            td = td->next;
            Pd.len++;
            if (ta->next == NULL)Pd.tail = tempd;
        }
        AddPolyn(Pc, Pd);    
        Link tempb = tb;
        tb = tb->next;
        delete tempb;
    }
    Pa.head = Pa.head->next;
    for (; Pa.head;){
        Link temp = Pa.head;
        Pa.head = Pa.head->next;
        delete temp;
    }
    delete Pb.head;
    Pa = Pc;
}

主函数：

// polynomial.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
int _tmain(int argc, _TCHAR* argv[])
{
    polynomial list1,list2;
    CreatPolyn(list1);
    CreatPolyn(list2);
    MultiplyPolyn(list1, list2);
    PrintPolyn(list1);
    return 0;
}

结果：

前面的数字是系数，后面的数字是指数，指数是递增的。上述程序是在VS2013上实现的

以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索指针
int
链表实现多项式相加、用链表实现多项式相加、单链表实现多项式相加、用链表实现多项式乘法、链表实现多项式相乘，以便于您获取更多的相关知识。

时间： 2024-10-02 14:18:47

线性链表及其基本操作及用链表实现的多项式的相关文章

C++ 单链表的基本操作(详解)_C 语言

链表一直是面试的高频题,今天先总结一下单链表的使用,下节再总结双向链表的.本文主要有单链表的创建.插入.删除节点等. 1.概念 单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素. 链表中的数据是以结点来表示的,每个结点的构成:元素 + 指针,元素就是存储数据的存储单元,指针就是连接每个结点的地址数据.如下图: 2.链表的基本操作 SingleList.cpp: #include "stdafx.h" #include "SingleList.h&

PHP中模拟链表和链表的基本操作示例_php实例

模拟链表: <?php /** * PHP实现链表的基本操作 */ class linkList { /** * 姓名 * @var string */ public $name = ''; /** * 编号 * @var int */ public $id = 0; /* * 引用下一个对象 */ public $next = null; /** * 构造函数初始化数据 * @param int $id * @param string $name */ public function __co

简单介绍线性表以及如何实现双链表_java

线性表是一种线性结构,它是具有相同类型的n(n≥0)个数据元素组成的有限序列. 一.数组数组有上界和下界,数组的元素在上下界内是连续的. 存储10,20,30,40,50的数组的示意图如下: 数组的特点:数据是连续的:随机访问速度快. 数组中稍微复杂一点的是多维数组和动态数组.对于C语言而言,多维数组本质上也是通过一维数组实现的.至于动态数组,是指数组的容量能动态增长的数组:对于C语言而言,若要提供动态数组,需要手动实现:而对于C++而言,STL提供了Vector:对于Java而言,Collec

用C语言计算一个单链表的长度，单链表的定义如下：要求使用递归，不得出现循环。

问题描述 用C语言计算一个单链表的长度,单链表的定义如下:要求使用递归,不得出现循环. 用C语言计算一个单链表的长度,单链表的定义如下:要求使用递归,不得出现循环. 解决方案 如果链表有环,永远算不出来 只能假定,这个链表不是环形链表,也没有环 简单事情用递归做是低效率的,即便学习递归,也是不必要的 递推, 可以用递归实现 也可以用迭代实现 前者无循环,后者有 解决方案二: int listLength(List *l) { if(l->next!=NULL) { l=l->next; ret

c语言-编写一程序，将带头结点的单链表拆成一个奇数链表和一个偶数链表

问题描述 编写一程序,将带头结点的单链表拆成一个奇数链表和一个偶数链表 要求用C语言来做!! 解决方案 http://zhidao.baidu.com/link?url=5XqMAQVb1yS0vaNF3QXC9fQPICC-JgqN0lisYvRQHwzYF8jb3ek3ouh_2TG3NKa4eanjSv4illaaV1znE-nkuq 解决方案二: BaiDu:将带头结点的单链表拆成一个奇数链表和一个偶数链表 你会得到很多你想要的. 解决方案三: 这个简单,可以看看面试宝典

数据结构实验之链表一：顺序建立链表(构造函数)

数据结构实验之链表一:顺序建立链表 Time Limit: 1000MS Memory Limit: 65536KB Problem Description 输入N个整数,按照输入的顺序建立单链表存储,并遍历所建立的单链表,输出这些数据. Input 第一行输入整数的个数N: 第二行依次输入每个整数. Output 输出这组整数. Example Input 8 12 56 4 6 55 15 33 62 Example Output 12 56 4 6 55 15 33 62 Code rea

数据结构实验之链表一：顺序建立链表

数据结构实验之链表一:顺序建立链表 Time Limit: 1000MS Memory Limit: 65536KB Problem Description 输入N个整数,按照输入的顺序建立单链表存储,并遍历所建立的单链表,输出这些数据. Input 第一行输入整数的个数N: 第二行依次输入每个整数. Output 输出这组整数. Example Input 8 12 56 4 6 55 15 33 62 Example Output 12 56 4 6 55 15 33 62 Code rea

双链表的基本操作-程序运行出错运行不下去

问题描述 程序运行出错运行不下去 #include #include using namespace std; //双向链表结构 typedef struct Node{ struct Node *next; struct Node *prior; int data; }Dnode,*Linklist; //创建带有头结点的双向链表 int Creatlist(Linklist &L,int n){ int x; Linklist p; L=(Linklist)malloc(sizeof(Lin

用java简单的实现单链表的基本操作

此代码仅供参考,如有疑问欢迎评论: package com.tyxh.link; //节点类 public class Node {      protected Node next; //指针域      protected int data;//数据域           public Node( int data) {            this. data = data;      }           //显示此节点      public void display() {