数据结构与算法学习笔记（三）线性表
·
本文主要分析了线性表中单向链表、双向链表的物理存储和逻辑存储的过程，并通过代码做了实现和分析，方便以后的进一步学习。
一、线性表中顺序存储与链表的对比
1、顺序存储：
按照顺序存储方式存储的线性表，且存储地址连续；顺序表存储数据时使用的就是数组，会提前申请一整块足够大小的物理空间，并将数据依次存储起来，存储时做到数据元素之间不留一丝缝隙；
顺序结构：编译期间，就将内存分配给相应的变量且内存空间连续，不过这容易造成内存的浪费；各数据元素具有相同的类型，且每个数据元素的长度相同；
缺点：容易造成内存浪费，且删除和中间添加元素速度较慢（需要移动插入或删除位置的后续元素）；优点：查找特别方便；
2、链表：
基本运算：初始化、计算表长、增、删、改、查；
链表结构：链表结点的分配是在执行时才发生的，结点之间用指针链接，故内存空间不需要是连续的，这样可以极大的节省内存空间，这被称为“动态内存分配”；当内存空间中没有足够大的连续的内存空间供顺序表使用时，通过链表就能解决问题（因为链表每次申请的都是单个数据元素的存储空间，可以利用上一些内存碎片）；
缺点：由于链表中结点的物理位置不相邻，故遍历操作速度特别慢；
优点：当对链表进行插入或者删除操作时，只要改变指针的指向，就能够快捷的进行插入和删除；
二、单向链表
1、单向链表（最重要的就是链表的表头）：
第一个节点是“链表表头的指针”；最后一个节点的指针设为NULL；单向链表具有方向性；
2、代码分析：
创建单向链表、打印链表（while循环打印、递归打印、反向打印输出）、插入或删除元素、反转单向链表（递归实现、while循环实现） 、析构掉整个链表new的内存空间
#include<iostream>
using namespace std;
int linkedlist_size = 0;
// Node that saves a data and points to next one
struct Node
{
int data; // 代表数据域
Node* next; // 代表指针域，指向直接后继元素
};
// Print a link according to header
void printlist(Node* ptr)
{
while (ptr != NULL)
{
cout << ptr->data << " ";
ptr = ptr->next;
}
cout << endl;
}
void printlist2(Node* ptr)
{
if (ptr == NULL) // Exit condition
{
cout << endl;
return;
}
cout << ptr->data << " ";
printlist2(ptr->next); // recursion call
}
void reversePrint(Node *ptr)
{
if (ptr == NULL) // Exit condition
{
return;
}
reversePrint(ptr->next); // recursion call
cout << ptr->data << " ";
}
// Create a new node
Node* newNode(int key)
{
Node* temp = new Node;
temp->data = key;
temp->next = NULL;
return temp;
}
// inital the link
void InitLink1(Node **header)
{
*header = newNode(1);
(*header)->next = newNode(2);
(*header)->next->next = newNode(3);
(*header)->next->next->next = newNode(4);
linkedlist_size = 4;
}
void InitLink2(Node **header)
{
Node* temp = (Node*)malloc(sizeof(struct Node)); // 创建首元节点
temp->data = 1; // 首元节点的初始化
temp->next = NULL;
*header = temp; // 头指针指向首元节点
linkedlist_size++;
for (int i = 2; i < 10; i++) // TailInsert
{
Node* curr = (Node*)malloc(sizeof(Node));
curr->data = i;
curr->next = NULL;
temp->next = curr;
temp = curr;
linkedlist_size++;
}
}
void Insert(Node** header, int n, int x)
{
Node* temp1 = new Node; // 等价于：Node* temp = (Node*)malloc(sizeof(Node));
temp1->data = x;
temp1->next = NULL;
if (n < 0 || n > linkedlist_size + 1) // 越界处理
{
n = linkedlist_size + 1;
}
if (n == 1) // inserting a node at the beginning
{
// head_insert
temp1->next = *header;
*header = temp1;
}
else
{
// 遍历链表
Node* temp2 = *header; // temp2相当于是header的别名
for (int i = 0; i < n - 2; i++)
{
temp2 = temp2->next; // 执行n-2次之后，temp2指向第（n-1）个节点
}
temp1->next = temp2->next; // 在第n-1和n个节点之间，加入一个节点temp1
temp2->next = temp1;
}
linkedlist_size++;
}
void Delete(Node **head, int n)
{
linkedlist_size--;
Node* temp1 = *head;
if (n == 1)
{
*head = temp1->next;
delete(temp1);
return;
}
for (int i = 0; i < n - 2; i++)
{
temp1 = temp1->next; // 执行n-2次之后，temp1指向第（n-1）个节点
}
Node* temp2 = temp1->next; // temp2指向第n个节点
temp1->next = temp2->next;
delete(temp2);
}
void recursiveReverse1(Node* curr, Node* prev, Node** head)
{
if (!(*head)) // empty link
{
return;
}
if (!curr->next) // if last node is NULL, mark it head
{
*head = curr;
curr->next = prev;
return;
}
Node* next = curr->next; // Save curr->next node for recursive call
curr->next = prev; // Update next to prev node
recursiveReverse1(next, curr, head);
}
void recursiveReverse2(Node** header)
{
Node* first;
Node* rest;
// Empty list
if (*header == NULL)
{
return;
}
// eg. first = {1, 2, 3}, rest = {2, 3}
first = *header;
rest = first->next;
// List has only one node
if (rest == NULL)
{
return;
}
// reverse the rest list and put the first element at the end
recursiveReverse2(&rest);
first->next->next = first;
first->next = NULL;
// fix the head pointer
*header = rest;
}
Node* reverseLinkedList(Node *head)
{
Node *prev; Node *current; Node *next;
prev = NULL;
current = head; // initial prev、current pointer
while (current != NULL)
{
next = current->next; // define next pointer
current->next = prev; // change the direction of pointer
prev = current; // update prev、current pointer
current = next;
}
// finally, prev points to final node; current and next point to NULL
head = prev;
return head;
}
// 释放链表内存由析构函数代替
void DeleteLinkList(Node **head)
{
if (*head == nullptr)
{
return;
}
// auto被解释为一个自动存储变量的关键字，也就是申明一块临时的变量内存
Node *pCurrent = *head;
while (pCurrent != nullptr)
{
auto *pNext = pCurrent->next; // 缓存下一个结点指针
delete pCurrent;
pCurrent = pNext;
}
linkedlist_size = 0;
cout << "free LinkList!" << endl;
}
int main()
{
cout << ".........Given linked list.........\n";
Node* head1 = NULL; // 创建链表的头节点
//InitLink1(&head1);
InitLink2(&head1);
printlist(head1);
cout << "\n.........Insert node into the linked list.........\n";
Insert(&head1, 1, 0);
Insert(&head1, 15, 10); // 验证越界处理
printlist(head1);
cout << "\n.........Reversed linked list.........\n";
Node **head = &head1; // 二级指针：指向另一个指针的指针
recursiveReverse1(*head, NULL, head);
printlist(head1);
recursiveReverse2(&head1);
printlist2(head1);
head1 = reverseLinkedList(head1);
printlist(head1);
cout << "\n.........Reversed print linked list.........\n";
reversePrint(head1);
cout << endl;
cout << "\n.........Delete the node inside the linked list.........\n";
Delete(&head1, 1);
printlist(head1);
// 析构掉申请的内存
DeleteLinkList(&head1);
system("pause");
return 0;
}
二、单向环形链表（圆环）
1、单向环形链表：
不用担心单向链表中表头丢失的问题，可以从任意的节点来遍历其他节点；通常用于内存工作区与输入/输出缓冲区；
2、代码分析：
创建环形链表、打印环形链表（while循环打印、递归打印）、插入或删除元素、反转单向环形链表（用两种时间复杂度不同的方法实现）、析构掉环形链表new的内存空间
#include<iostream>
using namespace std;
int circular_linkedlist_size = 0;
struct Node
{
int data;
Node *next;
};
void initCircularLinkList(Node **head, int size)
{
Node *temp = new Node;
temp->data = 1;
temp->next = NULL;
*head = temp;
circular_linkedlist_size++;
for (int i = 2; i <= size; i++)
{
Node *temp2 = new Node;
temp2->data = i;
temp2->next = NULL;
temp->next = temp2;
temp = temp2;
circular_linkedlist_size++;
// 让尾节点指向头节点
if (circular_linkedlist_size == size)
{
temp->next = *head;
}
}
}
// 用递归的方式打印环形列表
void PrintCircularlinklist1(Node *ptr, Node **head) // Node **head保存的是环形链表的头指针的指针
{
if (ptr->next == *head)
{
cout << endl;
return;
}
cout << ptr->data << " ";
PrintCircularlinklist1(ptr->next, head);
}
void PrintCircularlinklist2(Node *ptr)
{
Node *head = ptr;
do
{
cout << ptr->data << " ";
ptr = ptr->next;
} while (ptr->next != head);
cout << endl;
}
void Insert(Node **head, int pos, int val)
{
Node *temp = new Node;
temp->data = val;
temp->next = NULL;
// 越界处理：当插入的元素位置pos超出链表中元素个数或者为0时，令其插在头节点与尾节点之间
if (pos < 0 || pos >= circular_linkedlist_size)
{
pos = 0;
}
if (pos == 0)
{
temp->next = *head;
// 通过不断改变curr指针的指向，找到尾结点，并用curr指向尾结点
Node *curr = *head;
while (curr->next != *head)
{
curr = curr->next;
}
curr->next = temp;
*head = temp; // 调整头指针，指向刚添加的结点
}
else
{
Node *curr = *head;
for (int i = 1; i < pos; i++)
{
curr = curr->next;
}
temp->next = curr->next;
curr->next = temp;
}
circular_linkedlist_size++;
}
void Delete(Node **head, int pos)
{
circular_linkedlist_size--;
Node *curr = *head;
if (pos == 1)
{
Node *temp = *head;
while (temp->next != *head)
{
temp = temp->next;
}
*head = curr->next; // 调整头指针，指向新的头结点
temp->next = *head; // 此时的temp指向的是尾结点，让尾结点指向新的头结点
delete curr;
return;
}
for (int i = 1; i < pos - 1; i++)
{
curr = curr->next; // 执行pos-2次之后，curr指向第（pos-1）个节点
}
Node* temp = curr->next; // temp2指向第n个节点
curr->next = temp->next;
delete(temp);
}
void reverse1(Node **head)
{
Node *temp = *head;
while (temp->next != *head)
{
temp = temp->next;
}
// 此时，temp指向的头结点的上一个结点
temp->next = NULL; // 将环形链表变成单向链表
Node *prev; Node *current; Node *next;
prev = temp;
current = *head; // initial prev、current pointer
while (current != NULL)
{
next = current->next; // define next pointer
current->next = prev; // change the direction of pointer
prev = current; // update prev、current pointer
current = next;
}
// finally, prev points to final node; current and next point to NULL
*head = prev;
}
void reverse2(Node **head)
{
Node *prev; Node *current; Node *next;
prev = NULL;
current = *head; // initial prev、current pointer
next = current->next; // define next pointer
current->next = prev; // change the direction of pointer
prev = current; // update prev、current pointer
current = next;
// 让头结点指空
while (current != *head)
{
next = current->next;
current->next = prev;
prev = current;
current = next;
}
// 此时,current指向的是头结点
// 让头结点指向上一个结点
current->next = prev;
// finally, prev points to final node; current and next point to NULL
*head = prev;
}
void DeleteCircularLinkList(Node **head)
{
if (*head == nullptr)
{
return;
}
// auto被解释为一个自动存储变量的关键字，也就是申明一块临时的变量内存
Node *pCurrent = *head;
while (pCurrent->next != *head)
{
auto *pNext = pCurrent->next; // 缓存下一个结点指针
delete pCurrent;
pCurrent = pNext;
}
delete pCurrent; // 此时的pCurrent指向的尾结点
circular_linkedlist_size = 0;
cout << "free LinkList!" << endl;
}
int main()
{
cout << ".........Given the circular linked list.........\n";
Node *head = NULL;
initCircularLinkList(&head, 9);
PrintCircularlinklist1(head, &head);
PrintCircularlinklist2(head);
cout << "\n.........Insert node into the circular linked list.........\n";
// 在头结点和尾结点之间，插入结点；并调整头指针指向新添加的结点
Insert(&head, 0, 0);
Insert(&head, circular_linkedlist_size, 10);
// 在链表其他位置，插入结点
Insert(&head, 2, 11);
PrintCircularlinklist2(head);
cout << "\n.........Delete the node inside the circular linked list.........\n";
Delete(&head, 1);
Delete(&head, 2);
PrintCircularlinklist2(head);
cout << "\n.........reverse the circular linked list.........\n";
reverse1(&head);
PrintCircularlinklist2(head);
reverse2(&head);
PrintCircularlinklist2(head);
// 析构掉整个环形链表
cout << endl;
DeleteCircularLinkList(&head);
return 0;
}
三、双向链表
1、双向链表：
单向链表和环形链表，都有方向性，如果任意一个链接断裂，则链表的数据就无法复原；为了解决任一结点的指针断裂任然能快速修复的问题，提出双向链表，即一个结点分别都两个指针变量，分别指向前一个结点和后一个结点；
缺点：每个结点含有两个指针变量，所以会比较浪费空间；
2、代码分析：
创建双向链表、打印链表（while循环打印、反向打印输出）、插入或删除元素（尾插（删）、头插（删）、任意位置插入（删除））、析构掉整个链表new的内存空间
#include<iostream>
using namespace std;
int len = 0; // global variable
struct Node
{
int data;
Node* prev;
Node* next;
};
Node* GetNewNode(int x)
{
Node* newNode = new Node; // create a node in heap; malloc function is to reserve some memory in heap
newNode->data = x; // 等价于：(*newNode).data = x;
newNode->prev = NULL;
newNode->next = NULL;
return newNode;
}
void insert(Node **head, int pos, int x)
{
// 创建插入的结点
Node* newNode = GetNewNode(x);
if (len == 0) // 表示创建单链双向链表的头结点；不考虑pos大小，因为此时链表为空
{
*head = newNode;
len++;
return;
}
else
{
if (pos == 0) // 表示在单链双向链表的头结点前，插入结点并重新调整头节点指针
{
(*head)->prev = newNode;
newNode->next = *head;
*head = newNode;
len++;
return;
}
Node* temp = *head;
// pos个结点的位置编号{ pos：0~len - 1 }
for (int i = 1; i < pos; i++) // i=0~pos，表示从第0个结点（头结点）到第pos个结点；在pos个结点之前插入结点
{
temp = temp->next;
}
// 此时，temp指向的是要插入的位置的前一个结点
if (pos == len)
{
temp->next = newNode;
newNode->prev = temp;
len++;
return;
}
if (pos != len)
{
newNode->next = temp->next;
temp->next = newNode;
newNode->prev = temp;
newNode->next->prev = newNode;
len++;
return;
}
}
}
void insert_back(Node **head, int x)
{
insert(head, len, x);
}
void insert_front(Node **head, int x)
{
insert(head, 0, x);
}
void remove(Node **head, int pos)
{
if (*head == NULL)
{
cout << "empty the double link" << endl;
return;
}
else
{
Node *temp = *head;
if (pos == 0) // pos==0，表示删除头结点
{
*head = temp->next;
delete temp;
(*head)->prev = NULL;
len--;
return;
}
else
{
for (int i = 1; i < pos; i++) // 表示删除第pos个结点 {pos：0~len-1}
{
temp = temp->next;
}
// 此时，temp指向的是要删除的位置的前一个结点
if (pos == len - 1)
{
Node *temp2 = temp->next;
temp->next = NULL;
delete temp2;
len--;
return;
}
else
{
Node *temp2 = temp->next;
temp->next = temp2->next;
temp->next->prev = temp;
delete temp2;
len--;
return;
}
}
}
}
void remove_back(Node **head)
{
remove(head, len - 1);
}
void remove_front(Node **head)
{
remove(head, 0);
}
void Print(Node *head, bool flag=false) // 默认是正向打印输出
{
Node* temp = head;
if (temp == NULL) { return; } // empty the double link
if (!flag)
{
while (temp != NULL)
{
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}
else
{
// going to last node
while (temp->next != NULL)
{
temp = temp->next;
}
while (temp != NULL) // traversing backward using prev pointer
{
cout << temp->data << " ";
temp = temp->prev;
}
cout << endl;
}
}
void Delete(Node **head)
{
if (*head == nullptr)
{
return;
}
Node *temp = *head;
while (temp->next != NULL)
{
Node *temp2 = temp->next; // 缓存下一个结点指针
delete temp;
temp = nullptr;
temp = temp2;
}
len = 0;
cout << "free LinkList!" << endl;
}
int main()
{
Node *head = NULL; // empty list
for (int i = 0; i < 4; i++)
{
insert_back(&head, 1);
}
for (int i = 0; i < 4; i++)
{
insert_front(&head, 2);
}
cout << "初始化双向链表（前向插入和反向插入），正向打印输出：";
Print(head);
cout << "分别在1、3结点插入元素0，正向打印输出：";
insert(&head, 1, 0);
insert(&head, 3, 0);
insert(&head, 5, 0);
Print(head);
cout << "删除头结点，正向打印输出：";
remove_front(&head);
Print(head);
cout << "删除尾结点，正向打印输出：";
remove_back(&head);
Print(head);
cout << "删除位置编号为1的结点，正向打印输出："; // 结点的位置编号：0~len-1
remove(&head, 1);
Print(head);
cout << "反向打印输出：";
Print(head, true);
Delete(&head);
head = nullptr;
return 0;
}
四、双向环形链表（圆环）
通过模板类的方式，实现环形的双向链表；包含了双向环形链表的插入（向前插、向后插）、删除（向前删、向后删）、改、定位、查找、以及析构掉整个链表new的内存空间
代码分析：
double_linked_list.hpp
#include<iostream>
#include<string>
using namespace std;
// 双向链表结点模板类
template <typename T>
class DoubleLinkNode
{
public:
// 构造函数（explicit：指定构造函数或转换函数为显式类型转换, 即它不能用于隐式类型转换和复制初始化）
// next：下一结点指针 prev：上一结点指针
explicit DoubleLinkNode(DoubleLinkNode<T>* next = NULL, DoubleLinkNode<T>* prev = NULL) : prev(prev), next(next) {}
// data：数据项 next：下一结点指针 prev：上一结点指针
explicit DoubleLinkNode(const T& data, DoubleLinkNode<T>* next = NULL, DoubleLinkNode<T>* prev = NULL) : data(data), prev(prev), next(next) {}
T data; // 链表数据项
DoubleLinkNode<T>* next; // 下一结点
DoubleLinkNode<T>* prev; // 上一结点
};
// 双向链表模板类
template<typename T>
class DoubleLinkList
{
public:
static const int PREV_DIRECTION = 0;
static const int NEXT_DIRECTION = 1;
private:
DoubleLinkNode<T>* head_;
int len;
private:
bool InsertByDirection(int pos, const T& data, int direction); // 按方向插入
bool RemoveByDirection(int pos, T &data, int direction); // 按方向删除结点
DoubleLinkNode<T>* LocateByDirection(int pos, int direction); // 按方向定位
public:
DoubleLinkList(); // 构造函数(无参数)
~DoubleLinkList(); // 析构函数
int Length() const { return this->len; }
bool IsEmpty() const { return this->head_->next == this->head_; }
DoubleLinkNode<T>* Head() const { return this->head_; } // 获取链表头结点
bool insert_back(int pos, const T& data); // 向后插入
bool insert_front(int pos, const T &data); // 向前插入
bool remove_back(int pos, T& data); // 向后删除节点
bool remove_front(int pos, T& data); // 向前删除节点
bool GetData(int pos, T& data) const; // 获取结点数据
bool SetData(int pos, const T& data); // 设置结点数据
DoubleLinkNode<T>* Search(const T& data); // 搜索
DoubleLinkNode<T>* locate_back(int pos); // 向后定位
DoubleLinkNode<T>* locate_front(int pos); // 向前定位
void Output(bool flag); // 打印双向链表
};
template<typename T>
DoubleLinkList<T>::DoubleLinkList()
{
// 整个双向环形链表的head_指针指向的头结点中，数据data是空的
// 堆区，来存放结点的信息（回收内存时，需要自己delete掉）
this->head_ = new DoubleLinkNode<T>(); // 调用的是DoubleLinkNode<T>模板类中，第一个构造函数
this->head_->next = this->head_;
this->head_->prev = this->head_;
this->len = 0;
// 也可以换用，在栈区，来存放结点的信息（回收内存时，编译器自动回收）
//string str = "start";
//DoubleLinkNode<string> linknode(str);
//linknode.next = &linknode;
//linknode.prev = &linknode;
}
template<typename T>
DoubleLinkList<T>::~DoubleLinkList()
{
while (this->head_->next != this->head_) // 每次都删除掉头结点之后的结点，直到只剩头结点
{
DoubleLinkNode<T>* temp = this->head_->next;
this->head_->next = temp->next;
temp->next->prev = this->head_;
delete temp;
}
delete this->head_; // 删除头结点
this->head_ = nullptr;
len = 0;
cout << "Empty the double circular link" << endl;
}
template<typename T>
bool DoubleLinkList<T>::InsertByDirection(int pos, const T &data, int direction)
{
DoubleLinkNode<T>* cur = LocateByDirection(pos, direction);
if (cur == NULL) // 判断pos是否越界
{
cout << "pos is out of range" << endl;
return false;
}
else
{
DoubleLinkNode<T>* new_node = new DoubleLinkNode<T>(data);
if (new_node == NULL)
{
return false;
}
else
{
if (direction == DoubleLinkList::PREV_DIRECTION)
{
new_node->prev = cur->prev;
cur->prev = new_node;
new_node->prev->next = new_node;
new_node->next = cur;
}
if (direction == DoubleLinkList::NEXT_DIRECTION)
{
new_node->next = cur->next;
cur->next = new_node;
new_node->next->prev = new_node;
new_node->prev = cur;
}
this->len++;
return true;
}
}
}
template<typename T>
bool DoubleLinkList<T>::insert_back(int pos, const T& data)
{
return this->InsertByDirection(pos, data, DoubleLinkList::NEXT_DIRECTION);
}
template<typename T>
bool DoubleLinkList<T>::insert_front(int pos, const T& data)
{
return this->InsertByDirection(pos, data, DoubleLinkList::PREV_DIRECTION);
}
template<typename T>
bool DoubleLinkList<T>::RemoveByDirection(int pos, T& data, int direction)
{
DoubleLinkNode<T>* cur = LocateByDirection(pos, direction);
if (cur == NULL) // 处理pos越界问题
{
cout << "pos is out of range" << endl;
return false;
}
else
{
cur->next->prev = cur->prev;
cur->prev->next = cur->next;
data = cur->data;
delete cur;
this->len--;
return true;
}
}
template<typename T>
bool DoubleLinkList<T>::remove_back(int pos, T &data)
{
return this->RemoveByDirection(pos, data, DoubleLinkList::NEXT_DIRECTION);
}
template<typename T>
bool DoubleLinkList<T>::remove_front(int pos, T &data)
{
return this->RemoveByDirection(pos, data, DoubleLinkList::PREV_DIRECTION);
}
template<typename T>
bool DoubleLinkList<T>::GetData(int pos, T& data) const
{
if (pos < 1 || pos > Length()) // 处理越界问题
{
cout << "pos is out of range" << endl;
return false;
}
else
{
DoubleLinkNode<T>* cur = this->head_;
while (pos > 0)
{
cur = cur->next;
pos--;
}
data = cur->data;
return true;
}
}
template<typename T>
bool DoubleLinkList<T>::SetData(int pos, const T& data)
{
if (pos < 1 || pos > Length()) // 处理越界问题
{
cout << "pos is out of range" << endl;
return false;
}
else
{
DoubleLinkNode<T>* cur = this->head_;
while (pos > 0)
{
cur = cur->next;
pos--;
}
cur->data = data;
return true;
}
}
template<typename T>
DoubleLinkNode<T>* DoubleLinkList<T>::Search(const T& data)
{
DoubleLinkNode<T>* cur = this->head_->next;
// 整个双向环形链表的head_指针指向的结点中，数据data是空的，故“cur != this->head_”
while (cur != this->head_ && cur->data != data)
{
cur = cur->next;
}
if (cur != this->head_)
{
return cur;
}
else
{
return NULL;
}
}
template<typename T>
DoubleLinkNode<T>* DoubleLinkList<T>::LocateByDirection(int pos, int direction)
{
if (this->head_->next == head_ || pos == 0) // 如果是空链表 或者 定位位置0时, 返回头节点的地址
{
return this->head_;
}
else
{
DoubleLinkNode<T>* cur;
if (direction == DoubleLinkList::PREV_DIRECTION)
{
cur = head_->prev;
}
else
{
cur = head_->next;
}
for (int i = 1; i < pos; i++)
{
if (cur == this->head_)
{
return NULL;
}
else
{
if (direction == DoubleLinkList::PREV_DIRECTION)
{
cur = cur->prev;
}
else
{
cur = cur->next;
}
}
}
if (cur != this->head_)
{
return cur;
}
else
{
return NULL;
}
}
}
template<typename T>
DoubleLinkNode<T>* DoubleLinkList<T>::locate_back(int pos)
{
return this->LocateByDirection(pos, DoubleLinkList::NEXT_DIRECTION);
}
template<typename T>
DoubleLinkNode<T>* DoubleLinkList<T>::locate_front(int pos)
{
return this->LocateByDirection(pos, DoubleLinkList::PREV_DIRECTION);
}
template<typename T>
void DoubleLinkList<T>::Output(bool flag) // flag表示是否反向输出
{
if (this->head_ == NULL)
{
cout << "Empty list" << endl;
return;
}
else
{
DoubleLinkNode<T>* cur = this->head_;
if (!flag)
{
cout << "正向遍历输出：";
cur = cur->next;
while (cur != this->head_)
{
cout << cur->data << " ";
cur = cur->next;
}
cout << endl;
}
else
{
cout << "反向遍历输出：";
cur = cur->prev; // 此时，cur == this->head_
while (cur != this->head_)
{
cout << cur->data << "; ";
cur = cur->prev;
}
cout << endl;
}
}
}
test.cpp
#include "double_linked_list.hpp"
// 双向链表结点的标号（pos）：1~len
int main()
{
// 双向链表按方向插入
DoubleLinkList<string>* double_link = new DoubleLinkList<string>();
double_link->insert_back(0, "0+");
double_link->insert_back(1, "11");
double_link->insert_back(2, "22");
double_link->Output(false);
// 双向链表是否为空
if (double_link->IsEmpty())
{
cout << "The seq_list is empty." << endl;
}
else
{
// 获得双向链表的长度
cout << "双向链表长度: " << double_link->Length() << endl;
}
double_link->insert_front(0, "0-");
double_link->insert_front(1, "-1-1");
double_link->insert_front(2, "-2-2");
double_link->Output(false);
// 双向链表获取/设置数据项
string str;
double_link->GetData(2, str);
double_link->SetData(2, "1_1");
cout << "更改 pos=2 的结点之后: ";
double_link->Output(false);
// 删除从头结点开始“正向的”第三个结点/“反向的”第一个结点
string delete_item;
cout << "向后删除 pos=3 之后: ";
double_link->remove_back(3, delete_item);
double_link->Output(false);
cout << "向前删除 pos=1 之后: ";
double_link->remove_front(1, delete_item);
double_link->Output(false);
// 双向链表查找
DoubleLinkNode<string>* node1 = double_link->Search("-1-1");
DoubleLinkNode<string>* node2 = double_link->Search("-2-2");
cout << "The address of data(-1-1)" << " is " << node1 << endl;
cout << "The address of data(-2-2)" << " is " << node2 << endl;
// 双向链表定位
DoubleLinkNode<string>* node_ptr1 = double_link->locate_back(2);
DoubleLinkNode<string>* node_ptr2 = double_link->locate_front(1);
cout << "The node_ptr1 of pos=2（正向） is: " << node_ptr1 << endl;
cout << "The node_ptr2 of pos=2（反向） is: " << node_ptr2 << endl;
// 析构掉整个new的内存空间
delete double_link;
return 0;
}
本文是自己在学习线性表时，编写的代码实现，如有错误，还请指教！！！
魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。
更多推荐
0
0- 0
已为社区贡献2条内容
所有评论(0)