日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學(xué)無先后，達(dá)者為師

網(wǎng)站首頁 編程語言 正文

c++如何實(shí)現(xiàn)歸并兩個(gè)有序鏈表_C 語言

作者：SVicen ? 更新時(shí)間： 2022-09-13 編程語言

歸并兩個(gè)有序鏈表

1、題目描述

利用基礎(chǔ)題里構(gòu)建的單鏈表類創(chuàng)建兩個(gè)有序的整數(shù)鏈表對象，實(shí)現(xiàn)將兩個(gè)有序鏈表歸并成一個(gè)新的有序鏈表并輸出該新有序鏈表的結(jié)果。（可以調(diào)用已定義的鏈表類的方法來實(shí)現(xiàn)，并注意如何將兩個(gè)有序的線性表進(jìn)行歸并的算法）

2、設(shè)計(jì)思路

首先通過InputRear()函數(shù)構(gòu)造兩個(gè)鏈表，通過不斷修改last指針的指向。

last->link = newNode;
last = newNode;

只要用戶沒有輸入標(biāo)志結(jié)束的數(shù)據(jù)0，便一直將鏈表擴(kuò)展下去。

最終令last->link = NULL;

鏈表的合并，整體思路與順序表的合并相似，通過比較兩個(gè)鏈表元素的大小，將小的元素賦值給新的鏈表，指針不斷改變指向以循環(huán)整個(gè)鏈表

r->link=p;
r = p;
p = p->link;

或者是

r->link=q;
r = q;
q = q->link;

與線性表不同的是，鏈表中判斷一個(gè)鏈表是否取遍可用p是否等于NULL來確定，當(dāng)一個(gè)鏈表取遍后，將另一個(gè)鏈表剩下的結(jié)點(diǎn)連接到新鏈表即可。

頭文件代碼如下：

#include<iostream>
using namespace std;
//#include"LinearList.h"
template <class T> ?//結(jié)點(diǎn)結(jié)構(gòu)定義
struct LinkNode {
?? ?T data; ? ? ? ? ? ? ? ? ? ? ? ? //結(jié)點(diǎn)數(shù)據(jù)?
?? ?LinkNode<T>* link; ? ?//結(jié)點(diǎn)鏈接指針
?? ?LinkNode(LinkNode<T>* ptr = NULL) { link = ptr; } ?//構(gòu)造函數(shù)?? ?
?? ?LinkNode(const T& item, LinkNode<T>* ptr = NULL) { data = item; link = ptr; }
};
template<class T>
class List{
protected:
?? ?struct LinkNode<T>* first;
public:
?? ?List() { first = new LinkNode<T>; } ? ? ? ? //構(gòu)造函數(shù)
?? ?List(const T& x) { first = new LinkNode<T>(x); } ? ? ?//構(gòu)造函數(shù)
?? ?List(List<T>& L); ? ? ? ? ? ? //復(fù)制構(gòu)造函數(shù)
?? ?~List() { makeEmpty(); } ? ? ? ? ? ?//析構(gòu)函數(shù)
?? ?void makeEmpty(); ? ? ? ? ? ? //將鏈表置空
?? ?int Length() const; ? ? ? ? ? ? //計(jì)算鏈表的長度
?? ?LinkNode<T>* getHead() const { return first; }
?? ?LinkNode<T>* Search(T x); ? ? ? ? ? //搜素?cái)?shù)據(jù)為x的節(jié)點(diǎn)
?? ?LinkNode<T>* Locate(int i)const; ? ? ? ? ?//搜索第i個(gè)元素的地址
?? ?bool getData(int i, T& x) const; ? ? ? ? //取出第i個(gè)節(jié)點(diǎn)的數(shù)據(jù)
?? ?void setData(int i, T& x); ? ? ? ? ? //用x修改第i個(gè)元素的值
?? ?bool Insert(int i, T& x); ? ? ? ? ? //在第i個(gè)節(jié)點(diǎn)后插入新節(jié)點(diǎn)
?? ?bool Remove(int i, T& x); ? ? ? ? ? //刪除第i個(gè)節(jié)點(diǎn)數(shù)據(jù)返回到x中
?? ?bool IsEmpty() const ? ? ? ? ? ?//判斷表是否為NULL
?? ?{
?? ??? ?return first->link == NULL ? true : false;
?? ?}
?? ?bool IsFull() const { return false; } ? ? ? ?//判斷表滿
?? ?void InputFront(T ?endFlag); ? ? ? ? ?//倒序創(chuàng)建單鏈表
?? ?void InputRear(T endFlag); ? ? ? ? ? //正序創(chuàng)建單鏈表
?? ?void Output(); ? ? ? ? ? ? ?//輸出
};

.cpp文件如下：

#include"LinkList.h"
#include<iostream>
using namespace std;
template<class T>
List<T>::List(List<T>& L){
?? ?//復(fù)制構(gòu)造函數(shù)
?? ?T value;
?? ?LinkNode<T>* srcptr = L.getHead();
?? ?LinkNode<T>* destptr = first = new LinkNode<T>;
?? ?while (srcptr->link != NULL) { ? ? ? ? ?//逐一賦值
?? ??? ?value = srcptr->link->data;
?? ??? ?destptr->link = new LinkNode<T>(value);
?? ??? ?destptr = destptr->link; ? ? ? ? ?//左值游動(dòng)指針移動(dòng)到下一個(gè)
?? ??? ?srcptr = srcptr->link; ? ? ? ? ? //右值游動(dòng)指針移動(dòng)到下一個(gè)
?? ?}
?? ?destptr->link = NULL;
}
template<class T>
void List<T>::makeEmpty() {
?? ?LinkNode<T> *q;
?? ?while(first->link!=NULL){
?? ??? ?q=first->link;
?? ??? ?first->link=q->link;
?? ??? ?delete q;
?? ?}
}
template<class T>
int List<T>::Length() const {
?? ?//計(jì)算帶附加頭節(jié)點(diǎn)的單鏈表的長度
?? ?LinkNode<T>* p = first->link;
?? ?int count = 0;
?? ?while (p != NULL) {
?? ??? ?count++;
?? ??? ?p = p->link;
?? ?}
?? ?return count;
}
template<class T>
LinkNode<T>* List<T>::Search(T x) {
?? ?//在表中搜索含數(shù)據(jù)x的節(jié)點(diǎn)，搜索成功時(shí)返回該節(jié)點(diǎn)的地址，否則返回NULL
?? ?LinkNode<T>* current = first->link;
?? ?while (current != NULL) {
?? ??? ?if (current->data == x) break;
?? ??? ?else current=current->link;
?? ?}
?? ?return current;
}
template<class T>
LinkNode<T>* List<T>::Locate(int i)const{
?? ?//定位函數(shù) 返回表中第i個(gè)節(jié)點(diǎn)的地址 如果i < 0 或者i 超過鏈表長度則返回NULL
?? ?if (i < 0) return NULL;
?? ?LinkNode<T>* current = first;
?? ?int m = 0;
?? ?while (current != NULL && m < i) {
?? ??? ?current = current->link;
?? ??? ?m++;
?? ?}
?? ?return current;
}
template<class T>
bool List<T>::getData(int i, T& x) const {
?? ?//取出鏈表中第i個(gè)節(jié)點(diǎn)的data
?? ?if (i <= 0) return NULL; ? ? ? ? ? ? //數(shù)據(jù)非法返回false
?? ?LinkNode<T>* current = Locate(i); ? ? ? ? //借助定位函數(shù)直接定位到相應(yīng)的節(jié)點(diǎn)
?? ?if (current == NULL) return false; ? ? ? ? ? ? //i超過單鏈表的長度返回false
?? ?else {
?? ??? ?x = current->data;
?? ??? ?return true;
?? ?}
}
template<class T>
void List<T>::setData(int i, T& x) {
?? ?//設(shè)置鏈表的第i個(gè)元素為x
?? ?if (i <= 0) return;
?? ?LinkNode<T>* current = Locate(i);
?? ?if (current == NULL) return;
?? ?else current->data = x;
}
template<class T>
bool List<T>::Insert(int i, T& x) {
?? ?//在i個(gè)節(jié)點(diǎn)之后插入新節(jié)點(diǎn)
?? ?LinkNode<T>* current = Locate(i);
?? ?if (NULL == current) return false;
?? ?LinkNode<T>* newNode = new LinkNode<T>(x);
?? ?if (NULL == newNode)?
?? ??? ?cout << "存儲(chǔ)分配錯(cuò)誤" << endl;
?? ?newNode->link = current->link;
?? ?current->link = newNode;
?? ?return true;
}
template<class T>
bool List<T>::Remove(int i, T& x) {
?? ?//將鏈表中第i個(gè)節(jié)點(diǎn)刪除 刪除成功返回true并將刪除的data存儲(chǔ)在x中
?? ?LinkNode<T>* current = Locate(i - 1); ? ? ? ?//定位到指向i節(jié)點(diǎn)的節(jié)點(diǎn)
?? ?if (NULL == current || NULL == current->link) return false; ? ? ? ? ? ? //不存在待刪除的節(jié)點(diǎn)
?? ?LinkNode<T>* del = current->link; ? ? ? ? //標(biāo)記待刪除的節(jié)點(diǎn)
?? ?current->link = del->link; ? ? ? ? ? //重新拉鏈
?? ?x = del->data; ? ? ? ? ? ? ?//記錄下刪除節(jié)點(diǎn)的data
?? ?delete del; ? ? ? ? ? ? ? //釋放刪除節(jié)點(diǎn)
?? ?return true;
}
template<class T>
void List<T>::Output(){
?? ?//單鏈表的輸出函數(shù) ：將單鏈表中所有節(jié)點(diǎn)的data按邏輯順序輸出到屏幕上
?? ?LinkNode<T>* current = first->link; ? ? ? ?//創(chuàng)建遍歷指針
?? ?while (current != NULL) {
?? ??? ?cout<<current->data << ' ';
?? ??? ?current=current->link;
?? ?}
?? ?cout<<endl;
}
template<class T>
void List<T>::InputRear(T endFlag) {
?? ?//函數(shù)功能 ： 順序建立單鏈表
?? ?//函數(shù)參數(shù) ： 輸入結(jié)束標(biāo)志的數(shù)據(jù)
?? ?LinkNode<T>* newNode, *last; ? ? ? ? ?//需要一個(gè)指針時(shí)刻標(biāo)記結(jié)尾
?? ?T val;
?? ?makeEmpty();
?? ?cin >> val;
?? ?last = first; ? ? ? ? ? ? ?//首先令last指針指向頭節(jié)點(diǎn)
?? ?while (val != endFlag) {
?? ??? ?newNode = new LinkNode<T>(val);
?? ??? ?if (newNode== NULL)?
?? ??? ??? ?cout << "內(nèi)存分配錯(cuò)誤" << endl;
?? ??? ?last->link = newNode;
?? ??? ?last = newNode;
?? ??? ?cin >> val;
?? ?}
?? ?last->link = NULL;
}
int main()
{
?? ?List<int> x;?
?? ?List<int> y;?
?? ?List<int> z;
?? ?LinkNode <int>*p,*q,*r;
?? ?cout<<"請輸入第一個(gè)鏈表(結(jié)束符為0)：";
?? ?x.InputRear(0);//以0作為結(jié)束符正序創(chuàng)建鏈表
?? ?cout<<"請輸入第二個(gè)鏈表(結(jié)束符為0)：";
?? ?y.InputRear(0);
?? ?p = x.getHead();
?? ?q = y.getHead();
?? ?r = z.getHead(); ? //新鏈表?
?? ?q = q->link;?
?? ?p = p->link;
?? ?cout << "歸并前的鏈表一：" << endl;
?? ?x.Output();
?? ?cout << "歸并前的鏈表二：" << endl;
?? ?y.Output();
?? ?while(p&&q)
?? ?{
?? ??? ?if(p->data <= q->data)
?? ??? ?{
?? ??? ??? ?r->link=p;
?? ??? ??? ?r = p;
?? ??? ??? ?p = p->link;
?? ??? ??? ?continue;
?? ??? ?}
?? ??? ?if(p->data>q->data)
?? ??? ?{
?? ??? ??? ?r->link=q;
?? ??? ??? ?r = q;
?? ??? ??? ?q = q->link;
?? ??? ??? ?continue;
?? ??? ?}
?? ?}
?? ?if(p) ? //歸并后對元素個(gè)數(shù)多的鏈表的單獨(dú)處理?
?? ?{
?? ??? ?while(p)
?? ??? ?{
?? ??? ??? ?r->link = p;
?? ??? ??? ?r = p;
?? ??? ??? ?p = p->link;
?? ??? ?}
?? ?}
?? ?if(q)
?? ?{
?? ??? ?while(q)
?? ??? ?{
?? ??? ??? ?r->link = q;
?? ??? ??? ?r = q;
?? ??? ??? ?q = q->link;
?? ??? ?}
?? ?}
?? ?cout<<"歸并后的鏈表為："<<endl;
?? ?z.Output();
}

將兩個(gè)有序鏈表合并為一個(gè)新的有序鏈表并返回

新鏈表是通過拼接給定的兩個(gè)鏈表的所有節(jié)點(diǎn)組成的。?

示例

輸入：1->2->4, 1->3->4

輸出：1->1->2->3->4->4

/**
?* Definition for singly-linked list.
?* struct ListNode {
?* ? ? int val;
?* ? ? ListNode *next;
?* ? ? ListNode(int x) : val(x), next(NULL) {}
?* };
?*/
class Solution {
public:
? ? ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
? ? ? ? ListNode* p = new ListNode(0);
? ? ? ? ListNode* temp = p;
? ? ? ? while( l1 || l2 ){
? ? ? ? ? ? if(l1==NULL){
? ? ? ? ? ? ? ? p->next = l2;
? ? ? ? ? ? ? ? break;
? ? ? ? ? ? }else if(l2==NULL){
? ? ? ? ? ? ? ? p->next = l1;
? ? ? ? ? ? ? ? break;
? ? ? ? ? ? }else{
? ? ? ? ? ? ? ? if ( l1->val < l2->val ){
? ? ? ? ? ? ? ? ? ? p->next = l1;
? ? ? ? ? ? ? ? ? ? l1 = l1->next;
? ? ? ? ? ? ? ? }else{
? ? ? ? ? ? ? ? ? ? p->next = l2;
? ? ? ? ? ? ? ? ? ? l2 = l2->next;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? p=p->next;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return temp->next;
? ? }
};

因?yàn)榻?jīng)過while循環(huán)后，指針p的位置已經(jīng)發(fā)生改變，所以需要一個(gè)輔助指針temp保存其初始位置。

因?yàn)樵诙x指針p的時(shí)候給它賦值了一個(gè)自定義的ListNode節(jié)點(diǎn)地址（相當(dāng)于一個(gè)附加頭指針），所以最后函數(shù)返回的應(yīng)該是該結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)，即temp->next。

在力扣上的提交結(jié)果

執(zhí)行用時(shí) : 16 ms, 在Merge Two Sorted Lists的C++提交中擊敗了95.72% 的用戶

內(nèi)存消耗 : 8.9 MB, 在Merge Two Sorted Lists的C++提交中擊敗了84.45% 的用戶

原文鏈接：https://blog.csdn.net/SWC0619/article/details/123770663

欄目分類
最近更新