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

學無先后，達者為師

網站首頁 編程語言 正文

c++如何實現歸并兩個有序鏈表_C 語言

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

歸并兩個有序鏈表

1、題目描述

利用基礎題里構建的單鏈表類創建兩個有序的整數鏈表對象，實現將兩個有序鏈表歸并成一個新的有序鏈表并輸出該新有序鏈表的結果。（可以調用已定義的鏈表類的方法來實現，并注意如何將兩個有序的線性表進行歸并的算法）

2、設計思路

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

last->link = newNode;
last = newNode;

只要用戶沒有輸入標志結束的數據0，便一直將鏈表擴展下去。

最終令last->link = NULL;

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

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

或者是

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

與線性表不同的是，鏈表中判斷一個鏈表是否取遍可用p是否等于NULL來確定，當一個鏈表取遍后，將另一個鏈表剩下的結點連接到新鏈表即可。

頭文件代碼如下：

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

.cpp文件如下：

#include"LinkList.h"
#include<iostream>
using namespace std;
template<class T>
List<T>::List(List<T>& L){
?? ?//復制構造函數
?? ?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; ? ? ? ? ?//左值游動指針移動到下一個
?? ??? ?srcptr = srcptr->link; ? ? ? ? ? //右值游動指針移動到下一個
?? ?}
?? ?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 {
?? ?//計算帶附加頭節點的單鏈表的長度
?? ?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) {
?? ?//在表中搜索含數據x的節點，搜索成功時返回該節點的地址，否則返回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{
?? ?//定位函數 返回表中第i個節點的地址 如果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個節點的data
?? ?if (i <= 0) return NULL; ? ? ? ? ? ? //數據非法返回false
?? ?LinkNode<T>* current = Locate(i); ? ? ? ? //借助定位函數直接定位到相應的節點
?? ?if (current == NULL) return false; ? ? ? ? ? ? //i超過單鏈表的長度返回false
?? ?else {
?? ??? ?x = current->data;
?? ??? ?return true;
?? ?}
}
template<class T>
void List<T>::setData(int i, T& x) {
?? ?//設置鏈表的第i個元素為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個節點之后插入新節點
?? ?LinkNode<T>* current = Locate(i);
?? ?if (NULL == current) return false;
?? ?LinkNode<T>* newNode = new LinkNode<T>(x);
?? ?if (NULL == newNode)?
?? ??? ?cout << "存儲分配錯誤" << endl;
?? ?newNode->link = current->link;
?? ?current->link = newNode;
?? ?return true;
}
template<class T>
bool List<T>::Remove(int i, T& x) {
?? ?//將鏈表中第i個節點刪除 刪除成功返回true并將刪除的data存儲在x中
?? ?LinkNode<T>* current = Locate(i - 1); ? ? ? ?//定位到指向i節點的節點
?? ?if (NULL == current || NULL == current->link) return false; ? ? ? ? ? ? //不存在待刪除的節點
?? ?LinkNode<T>* del = current->link; ? ? ? ? //標記待刪除的節點
?? ?current->link = del->link; ? ? ? ? ? //重新拉鏈
?? ?x = del->data; ? ? ? ? ? ? ?//記錄下刪除節點的data
?? ?delete del; ? ? ? ? ? ? ? //釋放刪除節點
?? ?return true;
}
template<class T>
void List<T>::Output(){
?? ?//單鏈表的輸出函數 ：將單鏈表中所有節點的data按邏輯順序輸出到屏幕上
?? ?LinkNode<T>* current = first->link; ? ? ? ?//創建遍歷指針
?? ?while (current != NULL) {
?? ??? ?cout<<current->data << ' ';
?? ??? ?current=current->link;
?? ?}
?? ?cout<<endl;
}
template<class T>
void List<T>::InputRear(T endFlag) {
?? ?//函數功能 ： 順序建立單鏈表
?? ?//函數參數 ： 輸入結束標志的數據
?? ?LinkNode<T>* newNode, *last; ? ? ? ? ?//需要一個指針時刻標記結尾
?? ?T val;
?? ?makeEmpty();
?? ?cin >> val;
?? ?last = first; ? ? ? ? ? ? ?//首先令last指針指向頭節點
?? ?while (val != endFlag) {
?? ??? ?newNode = new LinkNode<T>(val);
?? ??? ?if (newNode== NULL)?
?? ??? ??? ?cout << "內存分配錯誤" << 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<<"請輸入第一個鏈表(結束符為0)：";
?? ?x.InputRear(0);//以0作為結束符正序創建鏈表
?? ?cout<<"請輸入第二個鏈表(結束符為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) ? //歸并后對元素個數多的鏈表的單獨處理?
?? ?{
?? ??? ?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();
}

將兩個有序鏈表合并為一個新的有序鏈表并返回

新鏈表是通過拼接給定的兩個鏈表的所有節點組成的。?

示例

輸入：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;
? ? }
};

因為經過while循環后，指針p的位置已經發生改變，所以需要一個輔助指針temp保存其初始位置。

因為在定義指針p的時候給它賦值了一個自定義的ListNode節點地址（相當于一個附加頭指針），所以最后函數返回的應該是該結點的下一個結點，即temp->next。

在力扣上的提交結果

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

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

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

欄目分類
最近更新