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

2018-06-18 04:18:13来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

  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 }

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:颠倒字符串

下一篇:glibc 内存申请和释放及堆连续检查