數(shù)據(jù)結(jié)構(gòu)概念：
數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)相互之間存在的一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。
隊(duì)列：
FIFO：first in first out
隊(duì)列種類：
- 普通隊(duì)列
- 環(huán)形隊(duì)列
環(huán)形隊(duì)列
隊(duì)列
環(huán)形隊(duì)列實(shí)現(xiàn)代碼：
MyQueue.hpp文件
#ifndef MyQueue_hpp
#define MyQueue_hpp
#include <stdio.h>
class myQueue
{
public:
//構(gòu)造函數(shù)：初始化數(shù)據(jù)
myQueue(int queueCapacity);
//析構(gòu)函數(shù)：釋放內(nèi)存
virtual ~myQueue();
//清空隊(duì)列
void ClearQueue();
//判斷隊(duì)列是否為空
bool QueueEmpty() const;
//判斷隊(duì)列是否填滿
bool QueueFull() const;
//獲取隊(duì)列長(zhǎng)度
int QueueLength() const;
//隊(duì)列插入數(shù)據(jù)
bool EnQueue(int element);
//隊(duì)列刪除數(shù)據(jù)
bool DeQueue(int &element);
//遍歷隊(duì)列
void QueueTraverse();
private:
//隊(duì)列數(shù)組，保存插入數(shù)據(jù)
int *m_pQueue;
//隊(duì)列長(zhǎng)度
int m_iQueueLen;
//隊(duì)列總?cè)萘? int m_iQueueCapacity;
//隊(duì)列頭在隊(duì)列數(shù)組中索引
int m_iHead;
//隊(duì)列尾在隊(duì)列數(shù)組中索引
int m_iTail;
};
#endif /* MyQueue_hpp */
MyQueue.cpp文件
#include "MyQueue.hpp"
#include <iostream>
using namespace std;
myQueue::myQueue(int queueCapacity){
//隊(duì)列容量賦值
m_iQueueCapacity = queueCapacity;
//初始化隊(duì)列頭和隊(duì)列尾，一開始隊(duì)列頭和隊(duì)列尾指向同一地址
m_iHead = 0;
m_iTail = 0;
//初始化隊(duì)列長(zhǎng)度，一開始隊(duì)列長(zhǎng)度為0
m_iQueueLen = 0;
//根據(jù)隊(duì)列容量創(chuàng)建隊(duì)列數(shù)組
m_pQueue = new int[queueCapacity];
}
myQueue::~myQueue(){
//釋放隊(duì)列數(shù)組，防止內(nèi)存溢出
delete [] m_pQueue;
m_pQueue = NULL;
}
void myQueue::ClearQueue(){
m_iHead = 0;
m_iTail = 0;
m_iQueueLen = 0;
}
bool myQueue::QueueEmpty() const{
if (m_iQueueLen == 0) {
return true;
}else{
return false;
}
}
bool myQueue::QueueFull() const{
if (m_iQueueLen == m_iQueueCapacity) {
return true;
}else{
return false;
}
}
int myQueue::QueueLength() const{
return m_iQueueLen;
}
bool myQueue::EnQueue(int element){
if (QueueFull()) {
return false;
}else{
//向隊(duì)列插入數(shù)據(jù)
m_pQueue[m_iTail] = element;
//隊(duì)列尾索引加1
m_iTail++;
//防止遍歷隊(duì)列時(shí)，數(shù)組越界
m_iTail = m_iTail%m_iQueueCapacity;
//隊(duì)列長(zhǎng)度加1
m_iQueueLen++;
}
return true;
}
bool myQueue::DeQueue(int &element){
if (QueueEmpty()) {
return false;
}else{
//獲取隊(duì)列頭對(duì)應(yīng)的數(shù)據(jù)，賦值函數(shù)外的元素
element = m_pQueue[m_iHead];
//隊(duì)列頭索引加1
m_iHead++;
//防止遍歷隊(duì)列時(shí)，數(shù)組越界
m_iHead = m_iHead%m_iQueueCapacity;
//隊(duì)列長(zhǎng)度減1
m_iQueueLen--;
return true;
}
}
void myQueue::QueueTraverse(){
cout << endl;
//從隊(duì)列頭索引開始遍歷，為了遍歷所有數(shù)據(jù)，需要隊(duì)列長(zhǎng)度加上隊(duì)列頭索引
for (int i = m_iHead; i < m_iQueueLen+m_iHead; i ++) {
//為防止數(shù)組越界，整除隊(duì)列容量
cout << m_pQueue[i%m_iQueueCapacity] << endl;
}
cout << endl;
}
int *p = new int(5); 和 int *p = new int[5]的區(qū)別
int *p = new int(5);
這句是從堆上分配一個(gè)int型變量所占的字節(jié)內(nèi)存，這個(gè)內(nèi)存單元存放的整數(shù)值為5，然后讓一個(gè)整形的指針變量p指向它的地址。
釋放方式：delete p;
int *p = new int[5];
這句相當(dāng)于從堆上分配一個(gè)含有5個(gè)元素的整形數(shù)組所占的字節(jié)內(nèi)存，然后讓一個(gè)整形的指針變量p指向它的首址。
釋放方式：delete []p;(注意這個(gè)[]不能掉了，如果掉了就會(huì)只釋放P[0]所占的空間，p[1]到p[4]不會(huì)被釋放，產(chǎn)生內(nèi)存泄露。)
int *p = new int(5); 和 int *p = new int[5]的區(qū)別
int &p和int p 有什么區(qū)別
#include <iostream>
void func(int &p,int q){
int t;
t=p;
p=q;
q=t;
}
int main(int argc, const char * argv[]) {
int x=1,y=2;
func(x, y);
std::cout << x <<"," << y << std::endl;
return 0;
}
輸出結(jié)果：2，2
- 在C++中，函數(shù)void func(int &p,int q)中的第一個(gè)形式參數(shù)p是“int型引用”類型。引用是C++的特殊變量類型，它是已有變量的別名。主調(diào)函數(shù)調(diào)用func把實(shí)參傳給p時(shí)，實(shí)際上是給實(shí)參起了個(gè)別名p，所以在函數(shù)中對(duì)p的操作就是對(duì)主調(diào)函數(shù)中的對(duì)應(yīng)實(shí)參的操作，將會(huì)使實(shí)參發(fā)生永久性改變。而func中的第二個(gè)形參int q是普通的int類型，調(diào)用時(shí)只是將實(shí)參的“值”拷貝給q，所以在函數(shù)中對(duì)q的操作并不影響主調(diào)函數(shù)中的實(shí)參值。
- int &p這樣寫，只在作為函數(shù)的形式參數(shù)時(shí)是正確的，若是在聲明語句則必須初始化，只有寫成int a,&p=a;才是正確的，因?yàn)槿缜八鲆谩笆且延凶兞康膭e名”，所以不可能獨(dú)立存在。
- 題面代碼在調(diào)用func時(shí)把x傳給了第一個(gè)int引用形參p(稱為引用傳遞)，把y傳給了第二個(gè)普通int形參q(稱為值傳遞或拷貝傳遞)，函數(shù)中語句p=q;把y的值賦給了p，由于p是x的別名，所以使主調(diào)函數(shù)中x的值變成了y的值2；而q=t;語句雖使函數(shù)中的q變量的值變?yōu)閤原先的值1，但由于q只是y的拷貝，所以并不能影響到主調(diào)函數(shù)中y變量的值。
