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 once
class 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();
}
