單連結清單C++

單連結清單 C++

題目

1、建立單連結清單

2、初始化單連結清單

3、釋放單連結清單

4、擷取單連結清單中元素的數量

5、輸出單連結清單中的所有資料

6、擷取單連結清單中指定位置的元素

7、根據鍵值查找指定元素

8、采用頭插法向單連結清單中插入一個元素

9、采用尾插法向單連結清單中插入一個元素

10、向單連結清單中的指定位置插入一個元素

11、删除指定位置的元素

設計類圖

檔案結構

效果

store.h

#pragma once
// store.h 儲存的結構體
#include "typeRedefinition.h"
#define Node_Length 20

/*儲存基本的儲存結構*/
class Elemtype {
private:
    string num;    // 學号
    string name;    // 姓名
    int age;    // 年齡
    string major;    // 專業
    int regissterYear;    // 入學年份
public:
    int setNum(string num);
    string getNum();
    int setName(string name);
    string getName();
    int setAge(int age);
    int getAge();
    int setMajor(string major);
    string getMajor();
    int setRegissterYear(int regissterYear);
    int getRegissterYear();
};

/*節點*/
class Node: public Elemtype{
public:
    Node* next = NULL;
    Node();
};
           

store.cpp

// store.cpp
#include "pch.h"
#include "store.h"

/*構造函數*/
Node::Node(){
    this->next = NULL;
    Elemtype::setAge(0);
    Elemtype::setMajor("NULL");
    Elemtype::setName("NULL");
    Elemtype::setNum("NULL");
    Elemtype::setRegissterYear(0);
}

/*學号*/
int Elemtype::setNum(string num)
{
    this->num = num;
    return 0;
}

string Elemtype::getNum(){
    return this->num;
}

/*姓名*/
int Elemtype::setName(string name)
{
    this->name = name;
    return 0;
}

string Elemtype::getName()
{
    return this->name;
}

/*年齡*/
int Elemtype::setAge(int age)
{
    this->age = age;
    return 0;
}

int Elemtype::getAge()
{
    return this->age;
}

/*專業*/
int Elemtype::setMajor(string major)
{
    this->major = major;
    return 0;
}

string Elemtype::getMajor()
{
    return this->major;
}

/*入學年份*/
int Elemtype::setRegissterYear(int regissterYear)
{
    this->regissterYear = regissterYear;
    return 0;
}

int Elemtype::getRegissterYear()
{
    return this->regissterYear;
}           

typeRedefinition.h

#pragma once
// typeRedefinition.h   
#include <string>
using namespace std;

//typedef struct Elemtype elemtype;    
//typedef struct Elemtype*  p_Elemtype;    // 基本的儲存
//typedef Node* p_Node;    // 儲存的方式
typedef string* p_string;    // string 指針           

method.cpp

// method.cpp 單連結清單
#include "pch.h"
#include "method.h"

/*構造函數*/
list::list() {
    this->createList();
}

/*析構函數*/
list::~list() {
    this->destroyList();
}

/*建立連結清單*/
int list::createList() {
    Node* head = new Node();    // 建立頭節點
    this->head = head;
    try {
        if (head == NULL) {
            exit(-2);
        }
    }catch (const string msg) {
        this->error = msg;
        return -1;
    }

    // 維護線性表長度
    this->length = 0;

    return 0;
}

/*獲得連結清單長度*/
int list::getLength()
{
    Node* p;
    int i = 0;    // 頭節點為0 依次不斷遞增，第一個存儲有内容的節點為1
    
    // 處理0節點的問題
    if (this->length == 0)
        return 0;
    
    p = this->head->next;

    while (p != NULL) {
        i++;
        p = p->next;
    }

    try {
        if (i != this->length) {
            exit(-3);
        }
    }catch (const string msg) {
        this->error = msg;
        this->length = 0;
        return 0;
    }

    return this->length;
}

/*獲得連結清單*/
// 将擷取的線性表的結果儲存在result字元串中
list* list::getList() {
    Node* p;
    if (this->length == 0)
        return 0;

    p = this->head->next;    // 指向第一個擁有資料的節點

    for (int index = 1; index <= this->getLength(); index++) {
        // 由于第一個節點為空節點，是以index的初值為1
        /*輸出節點序号*/
        this->result += "\n節點序号\t" + to_string(index) + "\n";
        this->result += "輸出學号\t" + p->getNum() + "\n";
        /*輸出姓名*/
        this->result += "輸出姓名\t" + p->getName() + "\n";
        /*輸出年齡*/
        this->result += "輸出年齡\t" + to_string(p->getAge()) + "\n";
        /*輸出專業*/
        this->result += "輸出專業\t" + p->getMajor() + "\n";
        /*輸出入學年份*/
        this->result += "入學年份\t" + to_string(p->getRegissterYear()) + "\n";
        /*指向下一個節點*/
        p = p->next;
        this->result += "------------------------------------------------";
    }
    return this;
}

/*輸出result*/
string list::toString()
{
    return this->result;
}
/*設定result字元串*/
list* list::setString(string& msg)
{
    this->result = msg;
    return this;
}


/*輸出error*/
string list::toError()
{
    return this->error;
}

/*頭插法插入元素*/
list* list::insertElem_Head(Node& node){
    Node* p = NULL;
    p = this->head->next;
    node.next = p;
    this->head->next = &node;
    this->head->next;
    (this->length)++;    // 長度維護

    return this;
}

/*尾插法，插入元素*/
list* list::insertElem_Foot(Node& node){
    Node* p = this->head;    // 指向頭結點
    for (int i = 1; i <= this->length; i++) {
        p = p->next;
    }
    // 進行插入
    p->next = &node;    // 設定指向
    p = p->next;    // 指針移動
    p->next = NULL;    // 設定空值
    (this->length)++;

    return this;
}

/*根據鍵值查找指定節點*/
Node* list::getNumNode(const string& num){
    Node* p = this->head->next;    // 指向第一個節點
    int index = 1;    // 計數為1

    // 周遊連結清單
    try {
        while (p != NULL) {
            if (p->getNum() == num) {
                return p;    // 找到節點以後傳回一個指針
            }
            // 檢查越界情況
            if (index > this->length)
                exit(-4);
            // 移動指針
            p = p->next;
            index++;
        };
    }
    catch (string msg) {
        this->error = msg;
        return this->head;
    }
    return this->head;    // 未找到傳回空指針
}

/*擷取指定loc位置的節點*/
Node* list::getNode(const int& loc){
    // 對loc進行判斷
    try {
        if (loc < 0 || loc > this->length) {
            exit(-1);
        }
    }
    catch (const char msg) {
        this->error = msg;    // 錯誤儲存
        return this->head;    // 傳回一個指針
    }

    // 擷取指定位置的節點
    Node* p = this->head;    // 頭節點
    for (int index = 0; index < loc; index++) {
        p = p->next;    // 移動指針
    }

    return p;
}

/*插入指定位置的元素*/
Node * list::insertLoc(Node & node, int & loc){
    node.next = this->getNode(loc + 1);
    this->getNode(loc - 1)->next = &node;
    return &node;
}

/*删除節點*/
list* list::deleteNode(const int& loc){
    // 對loc進行處理
    try {
        if (loc < 0 || loc > this->length)
            exit(-1);
    }
    catch (string msg) {
        this->error = msg;
        return this;    
    }

    // 删除節點
    Node* p_loc_previous = this->getNode(loc-1);    // 擷取要删除的節點的上一個節點
    Node* p_loc = this->getNode(loc);    // 擷取要删除的節點
    p_loc_previous->next = this->getNode(loc)->next;    // 删除鍊
    delete p_loc;    // 删除new出的堆記憶體
    p_loc = NULL;    // 設定指針為空

    // 維護長度
    (this->length)--;
    return this;
}

/*連結清單反轉*/
list* list::reverse()
{
    // 使用三個指針，周遊單連結清單，逐個對連結清單進行反轉
    // 思路，将連結清單的指針進行反向，為了防止連結清單斷裂，使用一個指針進行儲存,然後再和頭節點進行連接配接
    Node* last;
    Node* tmp;
    Node* first;
    // 進行初始化
    first = this->head->next;
    last = this->head->next->next;    // 此時上方的指向為  first->next = last

    // 開始連結清單反轉
    try {
        while (last->next != NULL) {    // 當最後一個連結清單的next的值為NULL的時，表明連結清單反轉完成
            // 檢視連結清單是否單連結清單循環，防止死循環發生
            if (this->judgingRingList())
                exit(-1);
            
            // 為了防止連結清單丢失，将第三個連結清單進行用tmp暫存
            tmp = last->next;
            // 調整first和last之間的順序
            last->next = first;    // 注；此時first->next仍舊指向last此時為一個閉環
            // 指針往後移動
            first = last;
            last = tmp;
        }
    }
    catch (string msg) {
        this->error = msg;
        return this;
    }

    // 處理最後一個節點
    last->next = first;
    // 此時this->head 指向該連結清單的最後一個節點,以及倒數的第二個節點形成環
    // 即 first->next = last  last -> next = first  this->head->next = first
    // 處理環，以及頭節點
    this->head->next->next = NULL;    // 處理尾部節點
    this->head->next = last;    //處理頭節點

    return this;
}

/*連結清單一分為二*/
Node* list::TwoPoints()    {
    Node* q1 = this->head;
    Node* q2 = this->head;
    
    // 判斷是否為環單連結清單
    try {
        if (this->judgingRingList())
            exit(-1);
    }
    catch (string msg) {
        this->error = msg;
        return NULL;
    }

    // 進行一分為二
    while (q2->next != NULL) {
        q1 = q1->next;    // q1走一步
        if (q2->next == NULL)
            break;    // 循環到終止
        q2 = q2->next->next;    // q2走兩步
    }

    // q1重新設定頭，形成一條單獨的鍊,并傳回
    return (new Node())->next = q1;
}

/*釋放單連結清單*/ 
int list::destroyList(){
    for (int index = 1; index <= this->length; index++) {
        this->deleteNode(index);
            
    }

    // 删除頭節點
    delete this->head;
    this->head = NULL;
    return 0;
}


/*判斷環單連結清單*/
bool list::judgingRingList(){
    Node* q1 = this->head;
    Node* q2 = this->head;
    
    while (q2->next != NULL) {
        q1 = q1->next;    // q1走一步
        if (q2->next == NULL)
            break;    // 循環到終止,證明單連結清單
        q2 = q2->next->next;    // q2走兩步
        
        if (q1 == q2)
            return true;    // 證明為環單連結清單
    }
    return false;
}           

method.h

#pragma once
#include "store.h"
// method.h 單連結清單
// 0 号節點為頭節點 1号節點開始存儲内容
class list {
public: 
    list();    // 構造函數
    ~list();    // 析構函數
    int getLength();    // 獲得連結清單長度
    list* getList(); // 獲得連結清單
    string toString();    // 獲得result字元串
    list* setString(string& msg);    // 設定result字元串
    string toError();    // 獲得error
    list* insertElem_Head(Node& node);    // 頭插法，插入元素
    list* insertElem_Foot(Node& node);    // 尾插法，插入元素
    Node* getNumNode(const string& num);    // 根據鍵值查找指定節點,傳回指向該節點的指針
    Node* getNode(const int& loc);    // 擷取指定loc的節點，傳回指向該節點的指針
    Node* insertLoc(Node& node, int& loc);    // 插入指定位置的元素
    list* deleteNode(const int& loc);    // 删除節點
    list* reverse();    // 反轉連結清單
    Node* TwoPoints();    // 連結清單一分為二，傳回第二個連結清單的頭
private:
    Node* head;    // 連結清單頭結點
    int length=NULL;    // 連結清單的長度
    string result = "";    // 臨時儲存結果
    string error;    // 儲存錯誤
    bool judgingRingList();    // 判斷環單連結清單
    int createList();    // 建立連結清單
    int destroyList();    // 釋放線性表
};           

單元測試

// ConsoleApplication3.cpp : 此檔案包含 "main" 函數。程式執行将在此處開始并結束。
//

#include "pch.h"
#include "method.h"
#include "store.h"
#include "typeRedefinition.h"
#include <iostream>

int main()
{
    // 建立
    list* list1 = new list();
    cout << list1->TwoPoints() << endl;
    cout << list1->getList() << endl;
    cout << list1->toString() << endl;
    cout << list1->getLength() << endl;
    cout << list1->getList() << endl;
    cout << list1->toString() << endl;
    cout << list1->toError() << endl;
    Node* node1 = new Node();
    node1->setAge(12);
    node1->setMajor("match");
    node1->setName("ming");
    node1->setNum("1211111");
    node1->setRegissterYear(201800012);
    cout << node1->getAge() << endl;
    cout << node1->getMajor() << endl;
    cout << node1->getName() << endl;
    cout << node1->getNum() << endl;
    cout << node1->getRegissterYear() << endl;
    list1->insertElem_Head(*node1);
    Node* node2 = new Node();
    node2->setAge(123);
    node2->setMajor("3333");
    node2->setName("66777");
    node2->setNum("666");
    node2->setRegissterYear(8888);
    list1->insertElem_Foot(*node2);
    cout << list1->getNode(1)->getAge()<< endl;
    cout << list1->getLength() << endl;
    cout << 3333 << endl;
    cout << list1->getList()->toString()<< endl;
    cout << list1->toError() << endl;
    cout << 3333 << endl;
    string tmp = "";
    cout << list1->setString(tmp)->toString() << endl;
    list1->reverse();
    cout << list1->getList()->toString() << endl;
    cout << list1->TwoPoints() << endl;
    delete list1;
    list1 = NULL;


    return 0;
}
           

ps

僅僅為最基本的，下面用qt架構做ui