单链表 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