线性表之循环链表编程系列复习题+834考点复习

怼烎@ 2022-01-11 07:35 48阅读 0赞

834考纲要求：

*  循环链表的概念，双向循环链表的概念，插入和删除结点
 *  多项式的链表表示，算法思想

--------------------

**1、概念级知识点：首尾相接的链表为循环链表。**任一节点出发均就可以 找到表中其他节点，分 单向循环和双向循环链表

**特殊性---*当遍历时***，判空的终止条件不同，单链表判空-----p!=NULL或p->next !=NULL，循环单链表判空-----p!=L 或 p->next !=L

双向循环链表：单向链的指针只能向后寻查节点---单向性，双向链表访问节点灵活，任意位置节点都可以移动指针访问到，判空----L-next=L->prior=L；

**2、基本操作**：循环单链和单链表的增删等操作算法基本相同，只是记得尾节点加上最后指向头节点的指针。故以下操作均指**循环双链**

**插入节点**（与头插法建立循环双链表同+与双链表插入节点同）：在\*p节点之后插入\*q节点

q->next=p->next;
    p->next->prior=q;
    p->next=q;
    q->prior=p;
    (其中顺序可换，不像单链表)
    
    //简单记:箭头指向谁，谁就在等号右边，这样可以快速很多

**删除节点（**与双链表删除节点同）：删除\*p节点之后的节点

q=p->next;
    p->next=q->next;
    q->next->prior=p;
    free(q);
    
    //也可以是(上种更好)
    p->prior->next=p->next;
    p->next->prior=p->prior;
    free(p);

**3、多项式在链表中（其实不难，新在一个节点有多个数据项，用结构体解决）**：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lheWFfMTIzNDU2Nzg_size_16_color_FFFFFF_t_70][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lheWFfMTIzNDU2Nzg_size_16_color_FFFFFF_t_70 1][]

实现多项式相加的算法如下：

//结构定义:
    
    typedef struct PNode
    {
        float coef;  //系数
        int expn;    //指数
        struct PNode *next; //指针域
        
    }PNode,*Polynomial;

void AddPolyn(Polynomial &pa,Polynomial &pb)
    {
        Polynomial *p1,*p2,*p3,*r;       //p1、p2指向首元节点，用于遍历和追踪节点
        p1=pa->next;                      //r用于释放节点，p3用于指向结果表的尾节点
        p2=pb->next;
        p3=pa;
        
        while(p1!=null&&p2!=null)
        {
            if(p1->expn==p2->expn)
            {
                sum=p1->coef+p2->coef;
                 if(sum!=0)
                 {
                    p1->coef=sum;         //修改随后链入的其中一个节点的系数
                    p3->next=p1;          //链入
                    p3=p1;
                    
                    p1=p1->next;
                    r=p2;
                    p2=p2->next;       
                    free(r);               //释放已经“验收过”的节点
                 }
                  else           //和系数为0，删掉对应节点
                 {
                    r=p1;
                    p1=p1->next;
                    free(r);
                    
                    r=p2;
                    p2=p2->next;
                    free(r);
                  }
            }
           
            else if(p1->expn<p2->expn)
            {
               p3->next=p1;        //尾插法链入节点
               p3=p1;
               p1=p1->next;
            }
             else
            {
                p3->next=p2;         //尾插法链入节点
                p3=p2;
                p2=p2->next;
            }
        }//while
        p3->next=p1?p1:p2;          //链入可能剩余的那段非空多项式的遗留项
        free(pb);
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lheWFfMTIzNDU2Nzg_size_16_color_FFFFFF_t_70]: /images/20220111/31052444bb244dd8b4b4ccf7ee237245.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lheWFfMTIzNDU2Nzg_size_16_color_FFFFFF_t_70 1]: /images/20220111/33e5143c6d284e05a2bae6ec77a23f93.png