《数据结构》2.6单链表应用举例

  1 //单链表倒置（头插法，时间复杂度O(n)）
  2 /*算法思路:
  3     依次取出原链表中的每个节点，每次都将其作为第一个节点插入原链表中；由于采用头插法，插入顺序与取节点
  4 顺序正好相反，故可以完成倒置操作。
  5 */
  6 void reverseList(LinkList h)        //reverse：背面、相反、颠倒
  7 {
  8     LNode *p;
  9     p = h->next;                    //*p指向第一个数据元素节点
 10     h->next = NULL;                    //将原链表置为空表
 11     while(p)
 12     {
 13         q = p;
 14         p = p->next;
 15         q->next = h->next;            //将第一个节点插到当前节点的后面（即当前节点插到了头节点的后面）
 16         h->next = q;
 17     }
 18 }
 19 
 20 //重复节点的删除（单链表中数据域值相同的节点称为重复节点，时间复杂度O(n*n)）
 21 /*算法思路：
 22     用指针p指向第一个数据节点，从它的直接后继节点开始直到链表的结束，找到与其值相同的节点并删除；p指向
 23 下一节点，重复上述操作；依此类推；当p指向表尾节点时算法结束。
 24 */
 25 void del_LinkList(LinkList h)
 26 {
 27     LNode *p, *q, *r;
 28     p = L->next;                    //p指向第一个节点
 29     if(p = NULL) return 0;
 30     while(q->next)
 31     {
 32         q = p;
 33         while(q->next)                //从p的后继开始查找重复节点
 34         {
 35             if(q->next->data == p->data)
 36             {
 37                 r = q->next;        //r指向重复节点
 38                 q->next = r->next;
 39                 free(r);            //删除r
 40             }
 41             else
 42                 q = q->next;
 43         }
 44         p = p->next;                //p指向下一个节点
 45     }
 46 }
 47 
 48 //单链表的合并（头插法，时间复杂度O(m+n)，合并：merge）
 49 //两个单链表A、B中元素均为递增有序，现将A、B归并一个按元素值非递增（允许有相同值）有序单链表C，不需要重新申请节点。
 50 /*算法思路：
 51     利用A、B递增有序的特点，依次取出当前节点进行比较，将当前值较小者取下，插入C的头部；由于采用的是
 52 头插法，最先找到的最小值节点将会在C的尾部；依此类推，所以得到的C为非递增有序的单链表。
 53 */
 54 LinkList merge_LinkList(LinkList A, LinkList B) //A、B均为带头节点的单链表
 55 {
 56     LinkList C;
 57     LNode *p, *q, *r;
 58     p = A->next;
 59     q = B->next;
 60     c = A;                            //C的头节点
 61     c->next = NULL;
 62     free(B);                        //释放B的头节点
 63     while(p && q)
 64     {
 65         if(p->data < q->data)
 66         {
 67             r = p; p = p->next;
 68         }
 69         else
 70         {
 71             r = q; q = q->next;        //从原A、B上取下较小值的节点
 72             r->next = C->next;        //将第一个节点插到当前节点的后面（即插入到C的头部）
 73             C->next = r;
 74         }
 75         if(p == NULL) p = q;
 76         while(p)                    //将剩余的节点一个个取下，插入C的头部
 77         {
 78             r = p; p = p->next;
 79             r->next = C->next;
 80             C->next = r;
 81         }
 82     }
 83 }
 84 
 85 //一元多项式的表示及相加（时间复杂度O(m+n)）
 86 /*    在数学上，一个n元多项式可以表示为Pn(x)=p0+p1*x+p2*x^2+…+pn*x^n，该多项式由n+1个系数唯一确定。
 87 在计算机里，可以用一个线性表P来表示，即P=(p0,p1,p2,…pn)，每项的指数i隐含在其系数pi的序号里。同理，
 88 Qm(x)表示为Q=(q0,q1,q2,…qm),设m<n,相加结果Rn(x)表示为R=(p0+q0,p1+q1,p2+q2,…,pm+qm,pm+1,…,pn)。
 89     为了有效而合理的利用存储空间，对于系数为0的所有项全都不存储，只存储非0项的系数及其相应的指数。
 90 算法思路：
 91     设PA和PB分别为两个参与运算多项式的头指针，PC为结果链表头指针，指针ha和hb分别指向多项式PA和PB中当前进行比较的节点；
 92 比较两个节点的指数项，进行如下操作。
 93     （1）指针ha所指节点的指数值小于指针hb所指节点的指数值，将ha所指节点插入PC链尾，指针ha后移一个节点；
 94     （2）指针ha所指节点的指数值等于指针hb所指节点的指数值，将ha和hb两个节点的系数相加，若系数之和为零，则删除两节点；
 95 若系数之和不为零，则将两者系数之和赋值给ha所指节点且插入PC链尾，删除hb所指节点；
 96     （3）指针ha所指节点的指数值大于指针hb所指节点的指数值，将hb所指节点插入PC链尾，指针hb后移一个节点。
 97     若PA和PB中有一个链表先行比较完毕，那么另一个未比较完链表的余下部分可直接连接到PC链表的表尾。
 98 */
 99 //定义节点
100 typedef struct Lnode
101 {
102     float coef;                        //系数（coeficient）
103     int exp;                        //指数（exponent）
104     struct Lnode *next;
105 }Lnode, *LinkList;
106 //多项式相加
107 void Add(Lnode *PA, Lnode *PB, Lnode *PC)
108 {
109     Lnode *ha, *hb, *temp;
110     int sum;
111     ha = PA->next;
112     hb = PB->next;
113     PC = PA;                        //PC指针最初是指向结果链的表头
114     while(ha != NULL && hb !=NULL)
115     {
116         if(ha->exp < hb->exp)
117         {
118             PC->next = ha; PC = PC->next; ha = ha->next; //PC此时变为移动指针，指向结果链当前节点
119         }
120         else if(ha->exp == hb->exp)
121         {
122             sum = ha->coef + ha->coef;
123             if(sum != 0)            //如果系数和不为零
124             {
125                 ha->coef = sum;
126                 PC->next = ha; PC = PC->next; ha = ha->next;
127                 temp = hb; hb = hb->next; free(temp);
128             }
129             else                    //如果系数和为零，则删除节点ha与hb，并将两指针分别指向下一个节点
130             {
131                 temp = ha; ha = ha->next; free(temp);
132                 temp = hb; hb = hb->next; free(temp);
133             }
134         }
135         else                        //ha=>exp > hb->exp;
136         {
137             PC->next = hb; PC = PC->next; hb = hb->next;
138         }
139     }
140     if(ha != NULL)                    //将多项式PA中剩余的节点连接到PC中
141         PC->next = ha;
142     else                            //将多项式PB中剩余的节点连接到PC中
143         PC->next = hb;
144         PC = PA;                    //PC指针恢复为指向结果链表头
145         free(PB);                    //释放掉剩余的PB头指针
146 }