探討:將兩個(gè)鏈表非降序合并為一個(gè)鏈表并依然有序的實(shí)現(xiàn)方法
實(shí)現(xiàn)過(guò)程中,list1中的節(jié)點(diǎn)和list2中的節(jié)點(diǎn)都轉(zhuǎn)移到了list3中,注意泛型的友元函數(shù)的用法。
程序如有不足之處,還望指正!??!
定義List類(lèi)
#include "stdafx.h"
#include <iostream>
using namespace std;
template<class T>
struct Node
{
T data;
Node<T> * next;
};
template <class T>
class MyList
{
public:
//構(gòu)造函數(shù),初始化一個(gè)頭結(jié)點(diǎn),data為空,next指向第一個(gè)節(jié)點(diǎn)
MyList()
{
phead = new Node<T>;
phead->data = NULL;
phead->next = NULL;
}
//析構(gòu)函數(shù),將整個(gè)鏈表刪除,這里采用的是正序撤銷(xiāo)
~MyList()
{
Node<T>* p;
p = phead;
while (p)
{
Node<T>* q;
q = p;
p = p->next;
delete q;
}
}
//復(fù)制構(gòu)造函數(shù)
MyList(MyList& mylist)
{
Node<T>* q = mylist.phead->next;
Node<T>* pb = new Node<T>;
this->phead = pb;
while (q != NULL)
{
Node<T>* p = new Node<T>;
p->data = q->data;
p->next = NULL;
pb->next = p;
pb = p;
q = q->next;
}
}
//插入一個(gè)元素的方法,在第i個(gè)元素插入一個(gè)元素e,
//返回值為NOTE<T>型指針,指向插入的那個(gè)元素
Node<T>* Insert(int i, T e)
{
//在鏈表的第i個(gè)位置,插入一個(gè)元素e
int j = 0;
Node<T>* p;
p = phead;
while (p && j < i - 1)
{
p = p->next;
++j;
}
if (!p || j > i -1)
{
return phead;
}
Node<T>* q;
q = new Node<T>;
q->data = e;
q->next = p->next;
p->next = q;
return q;
}
//輸出list中的元素
void Show()
{
Node<T> *p = phead->next;
while (NULL != p)
{
cout << p->data << " ";
p = p->next;
}
}
template<class T> friend void MergeList(MyList<T> &list1, MyList<T> &list2, MyList<T> &list3);
private:
Node<T>* phead;};
<PRE class=cpp name="code">// </PRE><PRE class=cpp name="code">//將兩個(gè)鏈表合并成一個(gè)鏈表,并且依然有序。方法保留了合并之前l(fā)ist1和list2的節(jié)點(diǎn),
//合并之后list1和list2消失。將list1和list2合并為list3
template<class T>
void MergeList(MyList<T> &list1, MyList<T> &list2, MyList<T> &list3)
{
Node<T> *head1 = list1.phead, *head2 = list2.phead;
Node<T> *head3 = list3.phead, *temp = NULL;
if (head1->next == NULL)
{//如果list1為空,則list3頭指針指向list2
head3 = head2;
list2.phead->next = NULL;//將list2消除,防止析構(gòu)函數(shù)析構(gòu)list2時(shí)找不到對(duì)象
}
else if (head2->next == NULL)
{//如果list1為空,則list3頭指針指向list2
head3 = head1;
list1.phead->next = NULL;//將list1消除,防止析構(gòu)函數(shù)析構(gòu)list2時(shí)找不到對(duì)象
}
head1 = head1->next;
list1.phead->next = NULL;//將list1消除,防止析構(gòu)函數(shù)析構(gòu)list2時(shí)找不到對(duì)象
head2 = head2->next;
list2.phead->next = NULL;//將list2消除,防止析構(gòu)函數(shù)析構(gòu)list2時(shí)找不到對(duì)象
if (head1->data < head2->data)
{//如果list1的第一個(gè)元素小于list2的第一個(gè)元素
head3->next = head1;//將list1的第一個(gè)元素接到list3上
head1 = head1->next;
}
else
{
head3->next = head2;//將list2的第一個(gè)元素接到list3上
head2 = head2->next;
}
temp = head3->next;//指向list3當(dāng)前最后一個(gè)節(jié)點(diǎn)
while (head1 != NULL && head2 != NULL)
{
if (head1->data < head2->data)
{
temp->next = head1;//將list1中的元素接到list3的后面
temp = head1;
head1 = head1->next;
}
else
{
temp->next = head2;//將list2中的元素接到list3的后面
temp = head2;
head2 = head2->next;
}
}
if (NULL == head1) //將list1或者list2中的剩余部分接到list3的后面
{
temp->next = head2;
}
else if (NULL == head2)
{
temp->next = head1;
}
}<PRE class=cpp name="code"> </PRE><PRE class=cpp name="code">//主函數(shù)</PRE><PRE class=cpp name="code">int _tmain(int argc, _TCHAR* argv[])
{
MyList<int> list1, list2, list3;
for (int i = 1; i <= 10; i ++)
{
list1.Insert(i, 3*i);
list2.Insert(i, 2*i);
}
MergeList(list1, list2, list3);
list3.Show();
return 0;
}</PRE><BR>
<PRE></PRE>
<PRE></PRE>
<PRE></PRE>
<PRE></PRE>
<PRE></PRE>
<PRE></PRE>
<PRE></PRE>
<PRE></PRE>
</PRE>
- Java采用循環(huán)鏈表結(jié)構(gòu)求解約瑟夫問(wèn)題
- C語(yǔ)言實(shí)現(xiàn)雙向鏈表
- JavaScript實(shí)現(xiàn)的鏈表數(shù)據(jù)結(jié)構(gòu)實(shí)例
- C++語(yǔ)言實(shí)現(xiàn)線性表之鏈表實(shí)例
- C#通過(guò)鏈表實(shí)現(xiàn)隊(duì)列的方法
- C++實(shí)現(xiàn)的鏈表類(lèi)實(shí)例
- JavaScript中數(shù)據(jù)結(jié)構(gòu)與算法(三):鏈表
- 逆轉(zhuǎn)交替合并兩個(gè)鏈表的解析與實(shí)現(xiàn)
相關(guān)文章
C++實(shí)現(xiàn)圖的鄰接矩陣存儲(chǔ)和廣度、深度優(yōu)先遍歷實(shí)例分析
這篇文章主要介紹了C++實(shí)現(xiàn)圖的鄰接矩陣存儲(chǔ)和廣度、深度優(yōu)先遍歷,實(shí)例分析了C++實(shí)現(xiàn)圖的遍歷技巧,非常具有實(shí)用價(jià)值,需要的朋友可以參考下2015-04-04OpenCV圖像算法實(shí)現(xiàn)圖像切分圖像合并示例
這篇文章主要為大家介紹了python圖像算法OpenCV實(shí)現(xiàn)圖像切分圖像合并操作示例,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2022-06-06C++分析類(lèi)的對(duì)象作類(lèi)成員調(diào)用構(gòu)造與析構(gòu)函數(shù)及靜態(tài)成員
終于到了對(duì)象的初始化和清理的最后階段了,在這里分享一個(gè)cpp里有多個(gè)類(lèi)時(shí),一個(gè)類(lèi)的對(duì)象作為另一個(gè)類(lèi)成員的時(shí)候構(gòu)造函數(shù)和析構(gòu)函數(shù)調(diào)用的時(shí)機(jī)。還有一個(gè)靜態(tài)成員也是經(jīng)??嫉降狞c(diǎn),在這篇博客將會(huì)詳解其概念并舉出案例鞏固,讓我們開(kāi)始2022-05-05C++的template模板中class與typename關(guān)鍵字的區(qū)別分析
這篇文章中我們來(lái)談一談C++的template模板中class與typename關(guān)鍵字的區(qū)別分析,同時(shí)會(huì)講到嵌套從屬名稱(chēng)時(shí)的一些注意點(diǎn),需要的朋友可以參考下2016-06-06C/C++實(shí)現(xiàn)矩陣的轉(zhuǎn)置(示例代碼)
C/C++實(shí)現(xiàn)矩陣的轉(zhuǎn)置(示例代碼)需要的朋友可以過(guò)來(lái)參考下,希望對(duì)大家有所幫助2013-10-10C++中小數(shù)點(diǎn)輸出格式(實(shí)例代碼)
下面小編就為大家?guī)?lái)一篇C++中小數(shù)點(diǎn)輸出格式(實(shí)例代碼)。小編覺(jué)得挺不錯(cuò)的,現(xiàn)在就分享給大家,也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2017-06-06C語(yǔ)言SQLite3事務(wù)和鎖的操作實(shí)例
這篇文章主要介紹了C語(yǔ)言SQLite3事務(wù)和鎖的操作,結(jié)合完整實(shí)例形式分析了C語(yǔ)言針對(duì)SQLite3數(shù)據(jù)庫(kù)的事務(wù)與鎖相關(guān)操作技巧,需要的朋友可以參考下2017-07-07C語(yǔ)言實(shí)現(xiàn)二叉樹(shù)鏈?zhǔn)浇Y(jié)構(gòu)的示例詳解
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)二叉樹(shù)鏈?zhǔn)浇Y(jié)構(gòu)的相關(guān)資料,文中的示例代碼講解詳細(xì),對(duì)我們學(xué)習(xí)C語(yǔ)言有一定的幫助,需要的可以參考一下2022-11-11C++11右值引用和std::move語(yǔ)句實(shí)例解析(推薦)
右值引用(及其支持的Move語(yǔ)意和完美轉(zhuǎn)發(fā))是C++0x將要加入的最重大語(yǔ)言特性之一。這篇文章主要介紹了C++11右值引用和std::move語(yǔ)句實(shí)例解析,非常不錯(cuò),具有參考借鑒價(jià)值,需要的朋友可以參考下2017-03-03C++實(shí)現(xiàn)簡(jiǎn)單計(jì)算器功能
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)簡(jiǎn)單計(jì)算器功能,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2020-05-05