学步园

两个链表要求已经排好序，这儿采用的是比较愚蠢的方法，创建了一个新的链表，然后一个一个的插入。

特别要注意的是，传递的函数参数究竟应该是引用还是值传递，尤其是在有动态资源申请的时候，一定要谨慎，否则可能造成灾难性的后果。

效率高的应该是直接在原来的链表上改。

//头文件</p> <p>#ifndef _LISTH<br /> #define _LISTH</p> <p>class ChainNode;<br /> class Chain;<br /> void MergeList(Chain &La, Chain &Lb, Chain &Lc);</p> <p>class Chain<br /> {<br /> public:<br /> Chain()<br /> {<br /> first = 0;<br /> }<br /> ~Chain();</p> <p>public:<br /> int LenChain() const;</p> <p> bool GetElem(int i, int &e);</p> <p> void InsertNode(int i, int &e);</p> <p> void OutputChain() const;</p> <p> friend void MergeList(Chain &La, Chain &Lb, Chain &Lc);</p> <p>private:<br /> ChainNode *first;<br /> };</p> <p>class ChainNode<br /> {<br /> public:<br /> ChainNode() { }<br /> ~ChainNode() { }<br /> friend Chain;</p> <p>private:<br /> int data;<br /> ChainNode *link;<br /> };</p> <p>#endif</p> <p>//头文件的实现文件</p> <p>int Chain::LenChain() const //求链表的长度<br /> {<br /> ChainNode *current = first;<br /> int len = 0;</p> <p> while (current)<br /> {<br /> current = current->link;<br /> ++len;<br /> }</p> <p> return len;<br /> }</p> <p>bool Chain::GetElem( int i, int &e) //从链表中找到第i个元素，将它的值赋给e<br /> {<br /> if ( i < 0)<br /> {<br /> cout << "The length of the Chain is at least 1 !" << endl;<br /> return false;<br /> }</p> <p> ChainNode *current = first;<br /> int index = 1;</p> <p> while ( index < i && current )<br /> {<br /> current = current->link;<br /> ++index;<br /> }</p> <p> if (current)<br /> {<br /> e = current->data;<br /> }</p> <p> return true;<br /> }</p> <p>void Chain::InsertNode(int i, int &e)//在链表chain中的i位置插入元素e<br /> {<br /> if ( i < 0 )<br /> {<br /> throw("The length of the Chain is at least 1 !");<br /> }</p> <p> ChainNode *current = first;</p> <p> for (int index = 0; index < i-1 && current; ++index)<br /> {<br /> current = current->link;<br /> }<br /> if ( i > 0 && !current)<br /> {<br /> throw("The element is not exit in the chain!");<br /> }</p> <p> ChainNode *y = new ChainNode;<br /> y->data = e;</p> <p> if ( i )<br /> {<br /> y->link = current->link;<br /> current->link = y;<br /> }<br /> else<br /> {<br /> y->link = first;<br /> first = y;<br /> }<br /> }</p> <p>void Chain::OutputChain() const<br /> {<br /> ChainNode *current;</p> <p> for (current = first; current; current = current->link)<br /> {<br /> cout << current->data <<" ";<br /> }<br /> }</p> <p>Chain::~Chain()<br /> {<br /> ChainNode *next;</p> <p> while(first)<br /> {<br /> next = first->link;<br /> delete first;<br /> first = next;<br /> }<br /> }</p> <p>void MergeList(Chain &La, Chain& Lb, Chain &Lc) //归并<span class='wp_keywordlink'><a href="http://www.xuebuyuan.com/category/%E7%AE%97%E6%B3%95" title="算法" target="_blank">算法</a></span><br /> {<br /> int i = 1;<br /> int j = 1;<br /> int k = 0;</p> <p> int lenla = La.LenChain();<br /> int lenlb = Lb.LenChain();</p> <p> int ai;<br /> int bj;</p> <p> while( (i <= lenla) && (j <= lenlb) )<br /> {<br /> La.GetElem(i, ai);<br /> Lb.GetElem(j, bj);</p> <p> if ( ai <= bj )<br /> {<br /> Lc.InsertNode( k++, ai);<br /> ++i;<br /> }<br /> else<br /> {<br /> Lc.InsertNode( k++, bj);<br /> ++j;<br /> }<br /> }</p> <p> while ( i <= La.LenChain() )<br /> {<br /> La.GetElem( i++, ai);<br /> Lc.InsertNode( k++, ai);<br /> }</p> <p> while ( j <= Lb.LenChain() )<br /> {<br /> Lb.GetElem( j++, bj);<br /> Lc.InsertNode( k++, bj);<br /> }<br /> }</p> <p>//主文件</p> <p>// DSList.cpp : 定义控制台应用程序的入口点。<br /> //</p> <p>#include "stdafx.h"<br /> #include "list.h"<br /> #include <vector><br /> #include <iostream><br /> using namespace std;</p> <p>int _tmain(int argc, _TCHAR* argv[])<br /> {<br /> Chain achain;<br /> Chain bchain;<br /> Chain mer_chain;</p> <p> int len_a = 4;<br /> int len_b = 3;</p> <p> cout << "Please input the number of Chain a: "<<endl;<br /> int temp;<br /> for( int index = 0; index < len_a; ++index)<br /> {<br /> cin >> temp;<br /> achain.InsertNode( index, temp);<br /> }</p> <p> cout << "Please input the number of Chain b: "<<endl;<br /> for( int index = 0; index < len_b; ++index)<br /> {<br /> cin >> temp;<br /> bchain.InsertNode( index, temp);<br /> }</p> <p> MergeList( achain, bchain, mer_chain);<br /> // cout << "Length of achain: " << achain.LenChain()<<endl;<br /> //cout << "Length of bchain: " << bchain.LenChain()<<endl;</p> <p> cout << "After merged: " << endl;<br /> // achain.OutputChain();<br /> // bchain.OutputChain();<br /> mer_chain.OutputChain();</p> <p> return 0;<br /> }<br />