前言
该篇为我跟着006_尚硅谷_线性结构和非线性结构_哔哩哔哩_bilibili视频学习时所做的笔记，内容属于入门级别，更加深入的研究内容我以后会单独写博客
1.线性结构与非线性结构
- 线性结构
- 特点是数据元素存在一对一的线性关系
- 有两种存储结构：顺序存储结
- 构（数组）与链式存储结构（链表）。
- 顺序存储的线性表称为顺序表，顺序表中的存储元素是连续的（地址是连续的）
- 链式存储的线性表称为链表，存储元素的地址不一定连续。我们可以借此充分利用零碎的内存，元素节点中存放数据元素以及相邻元素的地址信息
- 常见的有：数组、队列、链表、栈
- 非线性结构
- 常见的有：二维数组、多维数组、广义表、树结构、图结构
2. 稀释数组
用来压缩一个特殊二维数组的方式，这个二维数组的绝大大部分元素为一个相同的数(通常为0)，而少部分元素的值为其他值。最经典的就是五子棋程序，空位置为0，黑子为1，白子为2，如果用正常数组来记录，其实空位置是没有意义的数据（他们都是默认值），很占用内存
我们通过稀疏数组来记录原二维数组中这些特殊值的位置，其他位置的值相同所以可以不用记录
第一行来记录整个二维数组的行列以及特殊元素个数，而从数组第一位开始挨个记录特殊元素的行、列、值
二维数组转稀疏数组
- 遍历原始二维数组，得到有效数据个数sum
- 根据sum创建稀疏数组，我们一般命名为sparseArr，大小为[sum+1][3]（第零行用来记录二维数组信息）
- 将二维数组有效数据存入稀疏数组中
稀疏数组转二维数组
- 先读取稀疏数组第一行来创建二维数组
- 读取后几行，恢复特殊元素
程序
我由于想把所有步骤都搞成函数，所以用了好多我不熟练的指示点（比如指针），所以反而是程序更复杂了，但是中间我也学到了很多
#include<bits/stdc++.h>
using namespace std;
//填充二维数组的内容，包括默认值和特殊值
void makeArray(int *a,int row,int col){
for(int i=0;i<row;i++){
for(int j=0;j<col;j++){
a[i*col+j]=0;
}
}
a[1*col+2]=1;
a[2*col+3]=2;
return;
}
//打印二维数组
void printArray(int *a,int row,int col){
for(int i=0;i<row;i++){
for(int j=0;j<col;j++){
printf("%2d ",a[i*col+j]);
}
cout<<endl;
}
cout<<"-------------------------------------------"<<endl;
return;
}
//生成稀疏数组
int * makeSparseArray(int *a,int row,int col){
int num=0;
for(int i=0;i<row;i++){
for(int j=0;j<col;j++){
if(a[i*col+j]!=0) num++;
}
}
//动态管理内存，防止系统收回局部变量
int * ptr=new int[(num+1)*3];
int line=1;
ptr[0]=row;
ptr[1]=col;
ptr[2]=num;
for(int i=0;i<row;i++){
for(int j=0;j<col;j++){
if(a[i*col+j]!=0){
ptr[line*3]=i;
ptr[line*3+1]=j;
ptr[line*3+2]=a[i*col+j];
line++;
}
}
}
return ptr;
}
//将稀疏数组还原为二维数组
int * resume(int *a,int row,int col){
//读取二维数组的行数与列数
int r_row=a[0];
int r_col=a[0];
//同理
int * ptr=new int [r_row*r_col];
//初始化二维数组默认值
for(int i=0;i<r_row;i++){
for(int j=0;j<r_col;j++){
ptr[i*r_col+j]=0;
}
}
for(int i=1;i<=a[2];i++){
//读取该特殊元素的坐标与值
int this_row=a[i*3];
int this_col=a[i*3+1];
int value=a[i*3+2];
ptr[this_row*r_col+this_col]=value;
}
return ptr;
}
int main(){
int array[11][11];
//得到二维数组的行数与列数，这里是为了提高程序扩展性，其实就是11和11
int row=sizeof(array)/sizeof(array[0]);
int col=sizeof(array[0])/sizeof(array[0][0]);
makeArray(*array,row,col);
printArray(*array,row,col);
int * sparseArray=makeSparseArray(*array,row,col);
printArray(sparseArray,sparseArray[2]+1,3);
int * resumeArray=resume(sparseArray,sparseArray[2]+1,3);
printArray(resumeArray,sparseArray[0],sparseArray[1]);
//删除动态内存，防止发生内存泄露
delete[] sparseArray;
delete[] resumeArray;
return 0;
}
3.队列
比较经典的例子就是银行排队与叫号
- 队列是一个有序列表，可以用数组或者链表来表示
- 先入先出
我们看下面的示意图
- 图中有我们的容器，从0开始，所以最大位置为MaxSize-1，rear用来记录增加，front用来记录结束
- 当有数据进入我们的队列时，front不动，rear开始变化，变红的部分代表进入队列的数据（相当于当前银行前台开始接客）
- 当数据处理结束时，rear不动，front开始从移动，front是慢于rear的，这也符合我们先进先出的要求，图中1、2数据处理结束
数组模拟队列
有缺陷的非环形队列
目前数组只能使用一次，不能复用。数组rear指针指到最大位置后这个队列也就再也不能存数据了
#include<bits/stdc++.h>
using namespace std;
class ArrayQueue{
public:
int maxSize;
int front;
int rear;
int *arr;
public:
void init(int arrMaxSize);
bool isEmpty();
bool isFull();
void addQueue(int n);
int getQueue();
void showQueue();
int headQueue();
};
void ArrayQueue::init(int arrMaxSize){
maxSize=arrMaxSize;
arr=new int [maxSize];
front=-1;
rear=-1;
for(int i=0;i<maxSize;i++){
arr[i]=0;
}
}
bool ArrayQueue::isEmpty(){
return rear==front;
}
bool ArrayQueue::isFull(){
return rear==maxSize-1;
}
void ArrayQueue::addQueue(int n){
if(isFull()){
cout<<"队列满，不能添加数据"<<endl;
return;
}
rear++;
arr[rear]=n;
}
int ArrayQueue::getQueue(){
if(isEmpty()){
cout<<"队列空，不能取数据"<<endl;
return 0;
}
int res;
front++;
res=arr[front];
arr[front]=0;
return res;
}
void ArrayQueue::showQueue(){
if(isEmpty()){
cout<<"队列为空，没有数据可以展示"<<endl;
return;
}
cout<<"=================="<<endl;
for(int i=0;i<maxSize;i++){
printf("arr[%d]=%d\n",i,arr[i]);
}
cout<<"==================";
}
int ArrayQueue::headQueue(){
if(isEmpty()){
cout<<"队列为空，没有数据"<<endl;
return 0;
}
return arr[front+1];
}
int main(){
cout<<"请输入队列最大尺寸:";
int max;
cin>>max;
ArrayQueue a;
a.init(max);
char key=' ';
bool loop=true;
while(loop){
cout<<"s(show):显示队列"<<endl;
cout<<"a(add):添加数据到队列"<<endl;
cout<<"g(get):从队列中取出数据"<<endl;
cout<<"h(head):查看队列头的数据"<<endl;
cout<<"e(exit):退出程序"<<endl;
cin>>key;
int res;
switch(key){
case 's':
a.showQueue();
break;
case 'e':
loop=false;
break;
case 'a':
cout<<"请输入一个数字";
int value;
cin>>value;
a.addQueue(value);
break;
case 'g':
res=a.getQueue();
cout<<"取出的数据为"<<res<<endl;
break;
case 'h':
res=a.headQueue();
cout<<"队列头的数据是"<<res<<endl;
break;
}
system("pause");
system("cls");
}
return 0;
}
环形队列
我们做如下修改
- front变量的含义做一个调整：front指向队列的第一个元素，也就是说arr[front]代表的就是队列中当前最早的那个元素，front的初始值=0
- rear变量的含义做一个调整：rear指向队列的最后一个元素的后一个位置，因为希望空出一个空间作为约定，rear的初始值=0
- 当队列满时，条件是(rear+1)%maxSize=front
- 当队列为空时，rear=front
- 当我们这样分析时，队列中有效的数据的个数是(rear+maxSize-front)%maxSize