链式线性表——实验及提升训练

#include 
#include 
struct node
{//链表结点类型，包含一个存放整型数据的 data 成员，和一个指向下一个结点的next成员
    int data ;
    struct node *next ;
};

struct node *mycreateList()
{//函数功能：创建一个只有一个头结点的空链表，头节点的数据域赋值为0，并将表头结点的地址返回
    struct node *head = (struct node *)malloc(sizeof(struct node));
    head->data = 0;
    head->next = NULL;
    return head;
}


void myinsertHead(struct node * head, int insData )
{
    /*函数功能：实现在head为表头的链表中使用头插法，插入数据元素insData*/
    struct node *p ;
    p = (struct node *)malloc(sizeof(struct node));
    p->data = insData;
    p->next = head->next ;
    head->next = p ;
}

void myinsertTail(struct node *  head , int insData )
{
    /*在head为表头的单链表表尾插入数据元素insData*/
    struct node *p ,*q ;
    p = (struct node *)malloc(sizeof(struct node));
    p->data = insData;
    p->next = NULL;
    q = head ;
    while(q->next!=NULL)
        q = q->next;
    q->next = p ;
}

void myprintList(struct node *L)
{
    /*输出head为表头的链表中的数据元素，每输出一个数据空一格*/
    struct node *p = L->next ;
    int cnt=0;
    while(p)
    {
    cnt++;
    p = p->next ;
    }
for (;cnt>0;cnt--){
    p=L->next;
    for (int tmp=cnt-1; tmp>0&&p->next!=NULL; p=p->next,tmp--) {}
        printf("%d ",p->data);
}
}
void genNumber( struct node *A , int num)
{//本函数用于接收输入的大数的各个位，返回大数链表表头，可使用上面已实现的链表插入函数
/*------begin---------*/
        int n;
    for (int i = 0; i < num; ++i) {
        scanf("%d",&n);
        myinsertHead(A,n);
    }

/*------end---------*/
}

struct node *addNumber(struct node *A ,struct node *B)
{
    //此处实现函数求两数相加，并返回和值链表的表头；
    /*------begin---------*/
    struct node *p,*q,*tmp;
    p=A->next;
    q=B->next;
    struct node *ans=(struct node *)malloc(sizeof(struct node));
    ans->next=NULL;
    tmp=ans;
    int flag=0;
    for(;p!=NULL&&q!=NULL;q=q->next,p=p->next){
        struct node *list=(struct node *)malloc(sizeof(struct node));
        list->next=NULL;
        list->data=p->data+q->data;
        if(flag){
            list->data=p->data+q->data+1;
            flag=0;
        }

        if(list->data>=10){
        flag=1;
        list->data=list->data%10;
        }
        tmp->next=list;
        tmp=tmp->next;
    }
    if(p!=NULL){
        q=p;
    }
    for(;q!=NULL;q=q->next){
        struct node *list=(struct node *)malloc(sizeof(struct node));
        list->next=NULL;
        list->data=q->data;
        if (flag){
            list->data+=1;
            flag=0;
        }
        if(list->data>=10){
            flag=1;
            list->data=list->data%10;
        }
        tmp->next=list;
        tmp=tmp->next;
    }
    return ans;

    /*------end---------*/
}

#ifndef _LAB1_H_
#define  _LAB1_H_
#include 
#include 



//存放多项式某项的结点结构 
struct node
{
    int exp ;  // 表示指数
    int coef ; //表示系数
    struct node *next;  //指向下一个结点的指针
};

typedef  struct node * PNODE ;

/*
  函数功能：生成多项式
  函数名：createPoly
  函数参数：无
  返回值：指向多项式的头指针 
*/
PNODE createPoly(void)
{
    //在此处填写代码，能实现创建一个多项式并返回多项式头指针的函数
    //注意：头指针不存放多项式的项。
    /**********  Begin **********/
    PNODE head=(PNODE)malloc(sizeof(struct node));
    head->next=NULL;
    PNODE p=head;
    int e;
    int c;
    scanf("%d%d",&c,&e);
    for(;c!=0;){
        PNODE node=(PNODE)malloc(sizeof(struct node));
        node->exp=e;
        node->coef=c;
        node->next=NULL;
        p->next=node;
        p=p->next;
        // fflush(stdin);
        scanf("%d%d",&c,&e);
    }
    return head;

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

/*
   函数功能：进行多项式相加
   函数名：addPoly
   函数参数：polyAddLeft ：加法左边多项式头指针, polyAddRight：加法右边多项式头指针 
   返回值：指向结果多项式的头指针 
*/
PNODE addPoly(PNODE polyAddLeft , PNODE polyAddRight)
{
    //在此处填写代码，能实现创两个多项式相加并返回结果多项式头指针的函数
    /**********  Begin **********/
    PNODE ans=(PNODE)malloc(sizeof(struct node));
    ans->next=NULL;
    PNODE p,q;
    p=polyAddLeft->next;
    q=polyAddRight->next;
    PNODE n=ans;
    for(;p!=NULL&&q!=NULL;){

        if(q->exp>p->exp){
            PNODE node=(PNODE)malloc(sizeof(struct node));
            node->next=NULL;
            n->next=node;
            n=n->next;
            node->exp=p->exp;
            node->coef=p->coef;
            p=p->next;
            continue;
        } else if(q->expexp){
            PNODE node=(PNODE)malloc(sizeof(struct node));
            node->next=NULL;
            n->next=node;
            n=n->next;
            node->exp=q->exp;
            node->coef=q->coef;
            q=q->next;
            continue;
        } else{
            if(p->coef+q->coef!=0){
                PNODE node=(PNODE)malloc(sizeof(struct node));
                node->next=NULL;
                n->next=node;
                n=n->next;
                node->exp=q->exp;
                node->coef=q->coef+p->coef;
            }
                q=q->next;
                p=p->next;
        }

    }
    if(p!=NULL){
        q=p;
    }
    while(q!=NULL){
        PNODE node=(PNODE)malloc(sizeof(struct node));
        node->next=NULL;
        n->next=node;
        n=n->next;
        node->exp=q->exp;
        node->coef=q->coef;
        q=q->next;
    }
    return ans;
    /**********  End **********/
}

/*
   函数功能：输出多项式 
   函数名：printPoly
   函数参数：待输出多项式的头指针poly 
   返回值：无 
*/
void printPoly(PNODE poly)
{
    //在此处填写代码，能实现按格式输出多项式的功能，输出格式样例见说明
    /**********  Begin **********/
    PNODE p;
    p=poly->next;
    while(p!=NULL){
        printf("%dx^%d",p->coef,p->exp);

        if(p->next!=NULL){
            printf("+");
        }
        p=p->next;
    }

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

void destroyPoly(PNODE poly)
{
//释放存储多项式的链表空间
    PNODE q,p;
    p=q=poly;
    while(p!=NULL){
        p=p->next;
        free(q);
        q=p;
    }
    free(poly);
}
#endif

#ifndef _LINKSET_H_
#define _LINKSET_H_
#include 
#include 

typedef int DataType;

struct  node
{
    DataType  element;
    struct node  *next;
};
typedef struct node * SET;
void insert(DataType datax, SET set);

/*
  函数名： InitSet
  函数功能：根据参数num，初始化集合
  函数参数：集合元素的个数 
  返回值：集合头指针 
*/
SET InitSet(int num)
{

    SET p;
    p = ( struct  node *)malloc(sizeof(struct node)) ;
    p->next = NULL;
    p->element = num;
    int temp;
    for(int i =0;i)
    {
        scanf("%d",&temp);
        insert(temp, p); //调用insert函数，将输入数据插入集合
    }
    return p;
}


/*
  函数名： find
  函数功能：在集合中查找值为datax的成员 
  函数参数：datax:待查找的值 ； set：集合的头结点 
  返回值：找到值为datax的成员返回1，否则返回0 
*/
int find(DataType datax, SET  set)
{
    //请在此处填写代码，在set集合中查找值为datax的成员，若找到返回1，否则返回0
    /**********  Begin  **********/

    if(set==NULL){
        return 0;
    }
    SET p;
    p=set->next;
    while(p!=NULL){
        if(p->element==datax){
            return 1;
        }
        p=p->next;
    }
    return  0;
    /**********   End   **********/
}

/*
  函数名： insert
  函数功能：在集合set中插入值为datax的成员 ，插入位置在表头 
  函数参数：datax:待插入的值 ； set：集合的头结点 
  返回值：无 
  时间复杂度：O（1）
*/
void insert(DataType datax, SET set)
{
    //请在此处填写代码，将datax插入集合set， 注意因集合元素是无序的，只需将新成员插入表头
    /**********  Begin  **********/

    if(set->element<=0){
        return;
    }
    SET s=( struct  node *)malloc(sizeof(struct node)) ;
    s->element=datax;
    s->next=NULL;
    SET p=set;
    //p=p->next;
    while(p->next!=NULL){
        p=p->next;
    }

    p->next=s;

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

/*
  函数名： copyList
  函数功能：将集合setA复制生成集合setB 
  函数参数：setA 、setB的头结点 
  返回值：无 
*/
void copySet(SET setA, SET setB)
{
    //请在此处填写代码，实现将集合setA的成员复制到集合setB的功能
    /**********  Begin  **********/
    if(setA==NULL){
        return;
    }
    SET p=setA->next;

    while (p->next!=NULL){
        insert(p->element,setB);
        setB->element++;
        p=p->next;
    }



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

/*
  函数名： printSet
  函数功能：输出集合的元素，以空格作为元素之间分界符 
  函数参数：set的头结点 
  返回值：无 
*/
void printSet(SET set)
{
    //请在此处填写代码，实现输出集合元素的功能，元素之间以空格为分界符
    /**********  Begin  **********/
 SET p=set->next;
 while(p!=NULL){
     int n=p->element;
     printf("%d ",n);
     p=p->next;
 }

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

/*
  函数名： setUnion
  函数功能：求两个集合setA 和 setB的并集 
  函数参数：setA和setB的头结点 
  返回值：并集集合的头结点 
*/
SET setUnion(SET setA ,SET setB)
{
    //请在此处填写代码，可直接使用上面已经实现的各操作
    /**********  Begin  **********/
    //copySet(setA,setB);
    SET p,q;
    p=setA;
    p=p->next;
    q=setB;
    q=q->next;
    SET ret=(SET)malloc(sizeof(struct node));
    ret->next=NULL;
    ret->element=0;
    SET tmp=ret;
        while (q!=NULL){//将B中非A元素放入链栈
            if(!find(q->element,setA)) {
                SET n = (SET) malloc(sizeof(struct node));
                n->element = q->element;
                n->next = NULL;
                ret->element++;
                tmp->next = n;
                tmp = tmp->next;
            }
                q = q->next;
        }
    while (p!=NULL){//将A所有（非链栈）元素放入链栈
        if(!find(p->element,ret)){
        SET n=(SET)malloc(sizeof(struct node));
        n->element=p->element;
        n->next=NULL;
        ret->element++;
        tmp->next=n;
        tmp=tmp->next;
        }
        p=p->next;
    }

    return ret;

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

/*
  函数名： setIntersect
  函数功能：求两个集合setA 和 setB的交集 
  函数参数：setA和setB的头结点 
  返回值：交集集合的头结点 
*/
SET setIntersect(SET setA ,SET setB)
{
    //请在此处填写代码，可直接使用上面已经实现的各操作
    /**********  Begin  **********/
SET p,q,ans;


ans=( struct  node *)malloc(sizeof(struct node)) ;
    ans->next = NULL;
    ans->element=0;
p=ans;
        for (q=setB->next;q!=NULL;q=q->next){
    if(find(q->element,setA)){
        SET node=( struct  node *)malloc(sizeof(struct node)) ;
        node->element=q->element;
        node->next=NULL;
    p->next=node;
    p=p->next;
    ans->element++;
    }
        }
    return ans;
    /**********  End  **********/
}

/*
  函数名： setExcept
  函数功能：求两个集合setA 和 setB的差 
  函数参数：setA和setB的头结点 
  返回值：结果集合的头结点 
*/
SET setExcept(SET setA ,SET setB)
{
    //请在此处填写代码，可直接使用上面已经实现的各操作
    /**********  Begin  **********/
    SET p,q,ans;

//返回A有B无！！！
    ans=( struct  node *)malloc(sizeof(struct node)) ;
    ans->next = NULL;
    ans->element=0;
    p=ans;
    for (q=setA->next;q!=NULL;q=q->next){
        if(!find(q->element,setB)){
            SET node=( struct  node *)malloc(sizeof(struct node)) ;
            node->element=q->element;
            node->next=NULL;
            p->next=node;
            p=p->next;
            ans->element++;
        }
    }
    return ans;

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

void destroySet(SET set)
{
//释放存储集合的链表空间，表头为set
SET p,q;
p=q=set;
while (p->next!=NULL){
    p=p->next;
    free(q);
    q=p;
}
//free(set);
}

#endif