数据结构-线性表顺序单项链表双向链表循环链表

1数据结构概述

数据结构是计算机组织、存储数据的方式。是思想层面的东西，和具体的计算机编程语言没有关系。可以用任何计算机编程语言去实现这些思想。

1.1 数据逻辑结构

反映数据逻辑之间的逻辑关系，这些逻辑关系和他们咱在计算机中的存储位置无关。

常用的逻辑结构有：

线性结构：数据元素存在一对一的互相关系；

树形结构：数据元素存在一对多的互相关系；

图形结构：数据元素存在多对多的互相关系。

1.2数据存储结构（物理结构）

数据元素在计算机存储空间中的存放形式称为数据存储结构，或者物理结构。

一般来说，一种数据的逻辑结构开业有多种存储结构，常见的存储结构：顺序存储和链式存储。

2.线性表

2.1基本概念

线性表是由零个或多个数据元素组成的有序序列。

特征：

数据元素之间是有顺序的；

数据元素个数是由限的；

一般情况下，在强类型语言中，数据元素的类型是相同的。

2.2数学定义

线性表是n个元素组成的有限序列，a1,a2,a3....an，其中ai(1<=i<=n)是表项，n是线性表的长度，

其中，a1为线性表的第一个元素，只有后继元素，没有前驱元素，an为线性表的最后一个元素，只有前驱元素，没有后继元素。除了a1和an之外的其他元素，既有前驱元素，，也有后继元素。

2.3线性表的顺序存储结构

线性表的顺序存储结构，指的是用一段连续的存储空间来存储线性表中的数据元素。

//dynamicArray.h#pragma once //防止头文件被重复包含class DynamicArray
{
private:int* data;//线性表的数据元素的存储的空间int size;//线性表的大小int capacity;//线性表的容量
public:DynamicArray();DynamicArray(int capacity);~DynamicArray();//添加元素void pushBack(int value);//尾部添加void insertByIndex(int index, int value);//在表中指定位置前面插入元素位置//查询相关操作int getCapacity();//返回动态数组的容量int getSize();//返回动态数组的大小int getValueByIndex(int index);//返回指定位置的元素int front();//返回动态数组的第一个元素int back();//返回动态数组的最后一个元素//删除元素void popBack();//删除尾部void delByIndex(int index);//删除指定位置的元素//打印动态数组void printDynamicArray();
};//dynamicArray.c#include "dynamicArray.h"
#include <iostream>
using  namespace std;DynamicArray::DynamicArray()
{capacity = 5;data = new int[capacity];size = 0;
}
DynamicArray::DynamicArray(int capacity)
{this->capacity = capacity;data = new int[capacity];size = 0;
}
DynamicArray::~DynamicArray()
{if (data != nullptr){delete[] data;data = nullptr;}
}
void DynamicArray::pushBack(int value)
{if (capacity == size){//容量已满，需要扩容，容量扩充一倍int* temp_data = new int[capacity * 2];//复制原来空间中的数据到新的空间for (int i = 0; i < size; i++){temp_data[i] = data[i];}delete[]data;data = temp_data;capacity = capacity * 2;}data[size] = value;size++;
}
void DynamicArray::insertByIndex(int index,int value)
{if (index<0 || index>size - 1){return;}if (capacity == size){//容量已满，需要扩容，容量扩充一倍int* temp_data = new int[capacity * 2];for (int i = 0; i < size; i++){temp_data[i] = data[i];}delete[]data;data = temp_data;capacity *= 2;}//新元素插在索引index的前面，所以从index开始的元素都要后移for (int i = size-1; i >=index; i--){data[i + 1] = data[i];}data[index] = value;size++;
}
void DynamicArray::printDynamicArray()
{for (int i = 0; i < size; i++){cout << data[i] << " ";}cout << endl;
}
int  DynamicArray::getCapacity()
{return capacity;
}
int DynamicArray::getSize()
{return size;
}
int  DynamicArray::getValueByIndex(int index)
{if (index<0 || index>size - 1){return NULL;}return data[index];
}
int DynamicArray::front()
{if(size>0){return data[0];}return NULL;
}
int DynamicArray::back()
{if (size > 0){return data[size - 1];}return NULL;
}
void DynamicArray::popBack()
{if (size > 0){size--;}}
void DynamicArray::delByIndex(int index)
{if (index < 0 || index>size - 1){return;}for (int i = index; i < size-1; i++){data[i]=data[i+1];}size--;
}void test_dynamicarry()
{DynamicArray* da = new DynamicArray();da->pushBack(11);da->pushBack(12);da->pushBack(13);da->pushBack(14);da->pushBack(15);da->printDynamicArray();da->insertByIndex(2,88);da->printDynamicArray();da->popBack();da->printDynamicArray();da->delByIndex(2);da->printDynamicArray();cout << "此动态数组的容量为：" << da->getCapacity() << endl;cout << "此动态数组的大小为：" << da->getSize() << endl;cout << "此动态数组的第三个元素为：" << da->getValueByIndex(2) << endl;cout << "此动态数组中第一个元素为：" << da->front() << endl;cout << "此动态数组中最后一个元素为：" << da->back() << endl;delete da;
}
//设计一个线性表的顺序存储结构，给线性表中插入8个整数，删除其中的奇数。
void test_homework()
{DynamicArray* hk = new DynamicArray();hk->pushBack(1);hk->pushBack(2);hk->pushBack(3);hk->pushBack(4);hk->pushBack(5);hk->pushBack(6);hk->pushBack(8);hk->pushBack(8);hk->getSize();hk->printDynamicArray();int len = hk->getSize();for (int i = 0; i < len ;){if(hk->getValueByIndex(i) % 2 == 1){hk->delByIndex(i);}else{i++;}}hk->printDynamicArray();
}

2.4线性表之单向链式存储结构

单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) +指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。

结点结构：

┌───┬───┐

│data │next │

└───┴───┘

data域--存放结点值的数据域

next域--存放结点的直接后继的地址（位置）的指针域（链域）

链表通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在一起的，每个结点只有一个链域的链表称为单链表（Single Linked List）。

头指针head和终端结点

单链表中每个结点的存储地址是存放在其前趋结点next域中，而开始结点无前趋，故应设头指针head指向开始结点。链表由头指针唯一确定，单链表可以用头指针的名字来命名。

终端结点无后继，故终端结点的指针域为空，即NULL。

链表中最简单的一种是单向链表，它包含两个域，一个信息域和一个指针域。这个链接指向列表中的下一个节点，而最后一个节点则指向一个空值。

一个单向链表包含两个值: 当前节点的值和一个指向下一个节点的链接。

一个单向链表的节点被分成两个部分。第一个部分保存或者显示关于节点的信息，第二个部分存储下一个节点的地址。单向链表只可向一个方向遍历。

练习：

设计以恶搞链式线性表，给此线性表插入十个整数，删除其中的最大值（假设最大值唯一）

// LinkList.h#pragma once
//节点类
class LinkNode
{
public:int data;//数据域，存放数据元素LinkNode* next;//指向下一个节点的指针public:LinkNode();LinkNode(int value);
};//链表本身的类
class LinkList
{
private:LinkNode* head;//头指针，指向头节点int size;//链表大小public:LinkList();~LinkList();//添加元素void pushBack(int value);//尾部添加void insertByIndex(int index, int value);//指定位置添加//查找操作int getSize();//返回链表的长度int findByIndex(int index);//返回指定位置的元素int findIndexByValue(int value);//返回指定元素所在的位置，如果有相同元素，只返回第一个int front();//返回第一个元素int back();//返回最后一个元素//删除元素void popBack();//尾部删除void delByIndex(int index);//删除指定位置元素//打印链表void printLinkList();
};//LinkList.c#include <iostream>
#include "linkList.h"using namespace std;LinkNode::LinkNode()
{data = NULL;next = nullptr;
}LinkNode::LinkNode(int value)
{data = value;next = nullptr;
}LinkList::LinkList()
{head = new LinkNode;size = 0;
}LinkList::~LinkList()
{LinkNode* curr = head;LinkNode* temp = nullptr;while (curr != nullptr){temp = curr;curr = curr->next;delete temp;}
}void LinkList::pushBack(int value)
{//新建节点LinkNode* newNode = new LinkNode(value);//找到最后一个节点LinkNode* temp = head;while (temp->next != nullptr){temp = temp->next;}//修改相应指针temp->next = newNode;size++;
}
void LinkList::insertByIndex(int index, int value)
{if (index < 0 || index > size - 1){return;}//新建节点LinkNode* newNode = new LinkNode(value);LinkNode* curr = head;//找到index节点前面的节点for (int i = 0; i < index; i++){curr = curr->next;}//修改相应指针newNode->next = curr->next;curr->next = newNode;size++;
}
int LinkList::getSize()
{if (size > 0){return size;}
}
//返回指定位置元素
int LinkList::findByIndex(int index)
{if (index < 0 || index > size - 1){return NULL;}LinkNode* curr = head;for (int i = 0; i <= index ; i++){curr = curr->next;}return curr->data;}int LinkList::findIndexByValue( int value)
{int index = -1;LinkNode* temp = head->next;while (temp != nullptr){index++;if (temp->data == value){return index;}temp = temp->next;}return -1;
}int LinkList::front()
{if (head->next != nullptr){return head->next->data;}return NULL;
}
int LinkList::back()
{if (head->next == nullptr){return NULL;}//找到最后一个节点LinkNode* temp = head;while (temp->next != nullptr){temp = temp->next;}return temp->data;
}//删除
void  LinkList::popBack()
{if (head->next == nullptr){return;}LinkNode* curr = head;LinkNode* prev = nullptr;while (curr->next != nullptr){prev = curr;curr = curr->next;}prev->next = nullptr;delete curr;size--;
}
void LinkList::delByIndex(int index)
{if (index < 0 || index > size - 1){return;}LinkNode* curr = head;for (int i = 0; i < index; i++){curr = curr->next;}LinkNode* prev = curr->next;curr->next = prev->next;delete prev;size--;
}void LinkList::printLinkList()
{//找到最后一个节点LinkNode* temp = head;while (temp->next != nullptr){temp = temp->next;cout << temp->data << " ";}cout << endl;
}void test_linklist()
{LinkList list1;for (int i = 0; i < 5; i++){list1.pushBack(i + 11);}list1.printLinkList();list1.insertByIndex(2, 88);list1.printLinkList();cout << "此链表的第六个元素为：" << list1.findByIndex(5) << endl;cout << "此链表的长度为：" << list1.getSize() << endl;list1.delByIndex(2);list1.printLinkList();}
void test_homework()
{LinkList list2;list2.pushBack(5);list2.pushBack(6);list2.pushBack(7);list2.pushBack(9);list2.pushBack(10);list2.pushBack(15);list2.pushBack(18);list2.pushBack(20);list2.printLinkList();int max = list2.front();for (int i = 0; i < list2.getSize(); i++){if (list2.findByIndex(i) > max){max = list2.findByIndex(i);}}cout << list2.getSize() << endl;cout << max << endl;int maxindex = list2.findIndexByValue(max);list2.delByIndex(maxindex);list2.printLinkList();}

2.5 线性链表之双向链表

单向链表的节点中只有一个指向其后继的指针，使得单项链表只能从节点依次往后遍历。要访问某个节点的前驱，很不方便。为了克服单项链表的这个缺点，引入了双向链表。双向链表节点中有两个指针，分别指向前驱和后继，所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。

双向链表的插入

练习：

设计一个双向链表，向其中插入几个元素，然后逆序该链表。

思路：创建一个新链表，旧链表从头删除，新链表从头添加。

要求写一个函数，实现此功能

#pragma once
//节点类
class DoubleLinkNode
{
public:int data;DoubleLinkNode* prev;DoubleLinkNode* next;public:DoubleLinkNode();DoubleLinkNode(int value);
};//链表本身的类
class DoubleLinkList
{
private:DoubleLinkNode* head;int size;public:DoubleLinkList();~DoubleLinkList();//添加元素void pushBack(int value);//尾插void pushFront(int value);//头插//打印双向链表void printDoubleLinkList();//查询相关操作int getSize();//返回双向链表的长度int front();//返回双向链表的第一个元素int back();//返回双向链表的最后一个元素//删除元素void popBack();//尾部删除void popFront();//头部删除
};//c
#include <iostream>
#include"doubleLinkList.h"
using namespace std;DoubleLinkNode::DoubleLinkNode()
{data = NULL;prev = nullptr;next = nullptr;
}DoubleLinkNode::DoubleLinkNode(int value)
{data = value;prev = next = nullptr;
}DoubleLinkList::DoubleLinkList()
{head = new DoubleLinkNode();size = 0;
}DoubleLinkList::~DoubleLinkList()
{DoubleLinkNode* curr = head;DoubleLinkNode* temp = nullptr;while (curr != nullptr){temp = curr;curr = curr->next;delete temp;}
}void DoubleLinkList::pushBack(int value)
{//新建节点DoubleLinkNode* newNode = new DoubleLinkNode(value);//找到最后一个节点DoubleLinkNode* curr = head;while (curr->next != nullptr){curr = curr->next;}//修改相关指针curr->next = newNode;newNode->prev = curr;size++;
}void DoubleLinkList::pushFront(int value)
{DoubleLinkNode* newNode = new DoubleLinkNode(value);if (size > 0)//或者使用 if (head->next != nullptr){newNode->next = head->next;head->next = newNode;newNode->prev = head;newNode->next->prev = newNode;}else{head->next = newNode;newNode->prev = head;}size++;
}void DoubleLinkList::printDoubleLinkList()
{DoubleLinkNode* curr = head;while (curr->next != nullptr){curr = curr->next;cout << curr->data << " ";}cout << endl;
}int DoubleLinkList::getSize()
{return size;
}int DoubleLinkList::front()
{if (head->next != nullptr){return head->next->data;}return NULL;
}int DoubleLinkList::back()
{DoubleLinkNode* curr = head;while (curr->next != nullptr){curr = curr->next;}return curr->data;
}void DoubleLinkList::popBack()
{if (head->next == nullptr){return;}DoubleLinkNode* curr = head;while (curr->next != nullptr){curr = curr->next;}curr->prev->next = nullptr;delete curr;size--;
}void DoubleLinkList::popFront()
{if (head->next == nullptr){cout << "没有元素" << endl;return;}DoubleLinkNode* curr = head->next;if (curr->next != nullptr){curr->next->prev = head;}head->next = curr->next;delete curr;size--;
}void test_doublelinklist()
{DoubleLinkList* dl = new DoubleLinkList();for (int i = 0; i < 5; i++){dl->pushBack(i + 20);}dl->printDoubleLinkList();dl->pushFront(88);dl->printDoubleLinkList();cout << "此双向链表的大小为：" << dl->getSize() << endl;cout << "此双向链表的第一个元素为：" << dl->front() << endl;cout << "此双向链表的最后一个元素为：" << dl->back() << endl;dl->popBack();dl->printDoubleLinkList();dl->popFront();dl->printDoubleLinkList();delete dl;
}DoubleLinkList* reverseDoubleLinkList(DoubleLinkList* list)
{DoubleLinkList* list2 = new DoubleLinkList;while (list->getSize() != 0){list2->pushFront(list->front());list->popFront();}return list2;
}void reverseDoubleLinkList2(DoubleLinkList*& list)
{DoubleLinkList* list2 = new DoubleLinkList;cout << "list: " << &list << endl;cout << "list2: " << &list2 << endl;while (list->getSize() != 0){list2->pushFront(list->front());list->popFront();}list = list2;cout << "list: " << &list << endl;/*while (list2->getSize() != 0){list->pushBack(list2->front());list2->popFront();}delete list2;*/
}void test_reverse()
{DoubleLinkList* list1 = new DoubleLinkList();for (int i = 0; i < 8; i++){list1->pushBack(i + 11);}list1->printDoubleLinkList();DoubleLinkList* list2 = reverseDoubleLinkList(list1);list2->printDoubleLinkList();delete list1;delete list2;
}void test_reverse_2()
{DoubleLinkList* list1 = new DoubleLinkList();for (int i = 0; i < 8; i++){list1->pushBack(i + 11);}list1->printDoubleLinkList();cout << "list1: " << &list1 << endl;reverseDoubleLinkList2(list1);cout << "list1: " << &list1 << endl;list1->printDoubleLinkList();
}

2.6线性表之循环链表

循环列表是一种线性表的数据结构，其中最后一个节点的指针指向头节点，形成一个环状结构。

定义与特点

定义‌：

循环列表（Circular List）是一种特殊的线性表，其最后一个节点的指针不是指向NULL，而是指向头节点，形成一个闭环。‌

特点：

‌无界性‌：从任一节点出发，可以遍历到所有节点，无需判断边界。

‌循环性‌：操作（如遍历）时，可以无缝地从尾节点回到头节点。

‌应用广泛‌：常用于实现循环队列、约瑟夫环等问题。

练习：解决约瑟夫环问题

约瑟夫问题：有n个人围城一个圈，首先第一个人从1开始报数，报到第m个人，令其出列，然后再从下一个人开始再从1开始报数，报道第m个人，令其出列。如此下去，直到所有人全部出列。

打印出列顺序。

#pragma onceclass CirlceLinkNode
{
public:int data;CirlceLinkNode* next;public:CirlceLinkNode();CirlceLinkNode(int value);
};class CircleLinkList
{
public:CirlceLinkNode* head;int size;public:CircleLinkList();~CircleLinkList();void pushBack(int value);void pushFront(int value);int getSize();int front();int back();void popBack();void popFront();void printCircleLinkList();void yuesefu(int value);void yuesefu();//约瑟夫环};#include <iostream>
#include "circleLinkList.h"using namespace std;CirlceLinkNode::CirlceLinkNode()
{data = NULL;next = nullptr;
}CirlceLinkNode::CirlceLinkNode(int value)
{data = value;next = nullptr;
}CircleLinkList::CircleLinkList()
{head = new CirlceLinkNode;head ->next = head;size = 0;
}CircleLinkList::~CircleLinkList()
{CirlceLinkNode* curr =  head->next;CirlceLinkNode* temp;while (curr != head){temp = curr;curr = curr->next;delete temp;}delete head;
}void CircleLinkList::pushBack(int value)
{CirlceLinkNode* newNode = new CirlceLinkNode(value);CirlceLinkNode* curr = head;while (curr->next != head){curr = curr->next;}curr->next = newNode;newNode->next = head;size++;
}
void CircleLinkList::pushFront(int value)
{CirlceLinkNode* newNode = new CirlceLinkNode(value);newNode->next = head->next;head->next = newNode;size++;
}int CircleLinkList::getSize()
{return size;
}int CircleLinkList::front()
{if (size > 0){return head->next->data;}return NULL;
}int CircleLinkList::back()
{if (size > 0){CirlceLinkNode* curr = head;while (curr->next != head){curr = curr->next;}return curr->data;}return NULL;
}void CircleLinkList::popBack()
{if (head->next == head){return;}CirlceLinkNode* curr = head;CirlceLinkNode* prev = nullptr;while (curr->next != head){prev = head;curr = curr->next;}prev->next = head;delete curr;size--;
}void CircleLinkList::popFront()
{if (head->next == head){return;}CirlceLinkNode* curr = head->next;head->next = curr->next;delete curr;size--;
}void CircleLinkList::printCircleLinkList()
{CirlceLinkNode* curr = head;while (curr->next != head){curr = curr->next;cout << curr->data << " ";}cout << endl;
}void test_circle()
{CircleLinkList cl;for (int i = 0; i < 8; i++){cl.pushBack(i + 30);}cl.printCircleLinkList();cl.pushFront(88);cl.printCircleLinkList();cout << "此循环链表额长度为： " << cl.getSize() << endl;cout << "此循环链第一个元素为： " << cl.front() << endl;cout << "此循环链最后一个元素为： " << cl.back() << endl;cl.popFront();cl.printCircleLinkList();
}void CircleLinkList::yuesefu()
{CirlceLinkNode* curr = head;CirlceLinkNode* prev = nullptr;/*int size = 8;while (size > 0){for (int i = 0; i < value; i++){prev = curr;if (curr->next == head){curr = curr->next;}curr = curr->next;}prev->next = curr->next;cout << curr->data << " ";size--;}*/while (size > 0){for (int i = 1; i <= 3; i++){prev = curr;curr = curr->next;if (curr == head){curr = curr->next;prev = head;}}prev->next = curr->next;cout << curr->data << " ";delete curr;curr = prev;size--;}
}void test_yuesefu()
{CircleLinkList* yuecl = new CircleLinkList;for (int i = 1; i < 9; i++){yuecl->pushBack(i);}yuecl->printCircleLinkList();//yuecl->yuesefu(3);yuecl->yuesefu();
}