增城网站建设价格,自己怎么做网站免费的,产品广告设计,怀化网站建设有哪些文章目录目录一.栈1.栈的基本操作2.使用C模板类实现栈二.队列1.队列的基本操作2.循环队列**循环队列顺序存储****循环队列链式存储**3.双端队列目录 数据结构#xff1a; 逻辑结构#xff1a;数组#xff0c;栈#xff0c;队列#xff0c;字符串#xff0c;树#xff0c…
文章目录目录一.栈1.栈的基本操作2.使用C模板类实现栈二.队列1.队列的基本操作2.循环队列**循环队列顺序存储****循环队列链式存储**3.双端队列目录 数据结构 逻辑结构数组栈队列字符串树图存储结构顺序存储链式存储 C常用的数据结构有string , stack , queue , deque , vector , list , map , iterators. 一.栈 栈可以看成一种特殊的线性表特殊之处在于只能在表头或者表尾进行删除和插入操作。 1.栈的基本操作
push(): 向栈内压入一个成员 pop(): 从栈顶弹出一个成员 empty(): 如果栈为空返回true否则返回false top(): 返回栈顶但不删除成员 size(): 返回栈内元素的大小
例子
#include iostream
#include stackusing namespace std;int main(){//定义一个整形的栈stack int mStack;coutthe size of mStack is:mStack.size()endl;//向栈中加入元素mStack.push(1);mStack.push(2);mStack.push(3);mStack.push(4);coutafter push , the size of mStack is:mStack.size()endl;//弹出栈中的内容while(!mStack.empty()){ //栈的遍历 coutthe data will be pop is:mStack.top()endl;mStack.pop();coutafter pop ,the len of stack is:mStack.size()endl;}// for(int i 0 ; i 4;i){
// mStack.pop(); //出栈
// coutthe i pop is:mStack.top()endl;
// coutthe len i pop is:mStack.size()endl;
// }return 0;
}the size of mStack is:0 after push , the size of mStack is:4 the data will be pop is:4 after pop ,the len of stack is:3 the data will be pop is:3 after pop ,the len of stack is:2 the data will be pop is:2 after pop ,the len of stack is:1 the data will be pop is:1 after pop ,the len of stack is:0
2.使用C模板类实现栈 虽然C自带了stack的模板类也实现了大部分的栈的操作但是我们还是需要自己实现栈这种逻辑结构。 #include iostream
#include stackusing namespace std;#define MAXSIZE 0XFFFFtemplateclass T
class myStack{private:int top; //栈顶指针顺序存储中位数组的下标所以必须为整形 T* my_s; //栈的存储空间指针 int maxSize; //栈最大的存储空间 public://默认的构造函数 myStack():top(-1),maxSize(MAXSIZE){my_s new T[maxSize]; //为栈申请存储if(my_s NULL){cerr内存分配失败endl;exit(1);} }//带参数的构造函数 myStack(int size):top(-1),maxSize(size){my_s new T[maxSize]; //为栈申请存储if(my_s NULL){cerr内存分配失败endl;exit(1);}} ~myStack(){coutdelete the stack!endl;delete [] my_s; //删除整个栈 }bool isEmpty();//判空函数void push(T data); //压栈函数void pop(); //出栈函数T getTopValue(); //取出栈顶元素 int size(); //判断栈的大小
};//函数定义
templateclass T
bool myStackT::isEmpty(){if(top-1){ //栈顶指针为-1表示栈空 return true;}else{return false;}
} templateclass T
void myStackT::push(T data){if((top1) maxSize){ my_s[top] data; //先将栈顶指针加一然后在给栈顶赋值 }else{cout栈满!endl;}
} templateclass T
void myStackT::pop(){if(top -1){cout栈空endl;}else{top--; //栈顶指针减一 }
} templateclass T
T myStackT::getTopValue(){if(top -1){cout栈空endl;}else{return my_s[top];}
} templateclass T
int myStackT::size(){return top1;
} int main(){// myStackint mStack; //创建一个栈
// coutThe size of mStack is mStack.size()endl;
// //压栈
// mStack.push(1);
// mStack.push(2);
// mStack.push(3);
// mStack.push(4);
// coutAfter push , the size of mStack is mStack.size()endl;
// while(!mStack.isEmpty()){
// coutthe top value of mStack is : mStack.getTopValue()endl;
// mStack.pop();
// coutAfter pop , the size of mStack is mStack.size()endl;
// }myStackdouble mStack; //创建一个栈coutThe size of mStack is mStack.size()endl;//压栈mStack.push(1.1);mStack.push(2.4);mStack.push(3.5);mStack.push(4.8);coutAfter push , the size of mStack is mStack.size()endl;//出栈 while(!mStack.isEmpty()){coutthe top value of mStack is : mStack.getTopValue()endl;mStack.pop();coutAfter pop , the size of mStack is mStack.size()endl; }return 0;
}The size of mStack is 0 After push , the size of mStack is 4 the top value of mStack is : 4.8 After pop , the size of mStack is 3 the top value of mStack is : 3.5 After pop , the size of mStack is 2 the top value of mStack is : 2.4 After pop , the size of mStack is 1 the top value of mStack is : 1.1 After pop , the size of mStack is 0 delete the stack! 二.队列 队列也是一种特殊的线性表它只允许在表的一头插入元素队尾表的另一头删除元素队头。 1.队列的基本操作
q.empty() 如果队列为空返回true否则返回false q.size() 返回队列中元素的个数 q.pop() 删除队列首元素但不返回其值 q.push() 在队尾压入新元素 q.front() 返回队首元素的值但不删除该元素 q.back() 返回队列尾元素的值但不删除该元素
例子使用c自带的库实现的
#include iostream
#include queueusing namespace std;int main(){queueint mQueue; //创建一个新的队列coutthe size of mQueue is: mQueue.size()endl;coutmQueue is empty?: mQueue.empty()endl;//入队mQueue.push(1); mQueue.push(2);mQueue.push(3);mQueue.push(4);coutafter push , the size of mQueue is: mQueue.size()endl;coutthe front data of mQueue is: mQueue.front()endl;coutthe back data of mQueue is: mQueue.back()endl;while(!mQueue.empty()){coutthe front data of mQueue is: mQueue.front()endl;mQueue.pop();coutafter pop , the size of mQueue is: mQueue.size()endl; }return 0;
}the size of mQueue is: 0 mQueue is empty?: 1 after push , the size of mQueue is: 4 the front data of mQueue is: 1 the back data of mQueue is: 4 the front data of mQueue is: 1 after pop , the size of mQueue is: 3 the front data of mQueue is: 2 after pop , the size of mQueue is: 2 the front data of mQueue is: 3 after pop , the size of mQueue is: 1 the front data of mQueue is: 4 after pop , the size of mQueue is: 0
注意 由于单端队列的空间利用率非常低几乎就是一次性的只要入队满了然后全部出队后便不可再用所以此处就不讨论自己实现单端队列了。 2.循环队列
循环队列中判断队空的方法是判断frontrear队满的方法是判断frontrear1%maxSize。 可以解决单端队列中空间一次性消耗的问题
循环队列顺序存储
#include iostream
#include queueusing namespace std;#define MAXSIZE 0XFFFF templateclass T
class myQueue{private:int front,rear; //队头和队尾元素 T* my_q; //队列的存储空间 int maxSize; //最大的队列存储空间public://默认构造函数 myQueue():front(-1),rear(-1),maxSize(MAXSIZE){my_q new T[maxSize]; //申请内存if(my_q NULL){cerr内存申请失败endl;exit(1);} }//带参数的构造函数 myQueue(int size):front(-1),rear(-1),maxSize(size){my_q new T[maxSize]; //申请内存if(my_q NULL){cerr内存申请失败endl;exit(1);} }//析构函数 ~myQueue(){coutdelete the queue!!!endl;delete [] my_q;} //操作函数bool isEmpty(); //判空 void push(T data); //入队操作 void pop(); //出队操作 T getFrontData(); //获取队头元素 T getRearData(); //获取队尾元素 int size(); //获取队列长度
};templateclass T
bool myQueueT::isEmpty(){if(front rear){ //判空条件 return true;}else{return false;}
}templateclass T
void myQueueT::push(T data){if((rear1)%maxSize front){ //队列满时候的条件 cout队列满了endl;}else{my_q[rear] data; //首先队尾元素赋值 rear (rear1) % maxSize;}
}templateclass T
void myQueueT::pop(){if(rear front){cout队列为空endl;}else{front (front1) % maxSize; //队头指针加一 }
}templateclass T
T myQueueT::getFrontData(){if(rear front){cout队列为空endl;}else{return my_q[front];}
}templateclass T
T myQueueT::getRearData(){if(rear front){cout队列为空endl;}else{return my_q[rear];}
}templateclass T
int myQueueT::size(){return (rear-frontmaxSize)%maxSize; //队列长度计算
}//main loop
int main(){myQueueint mQueue;//创建一个新的队列coutthe size of mQueue is: mQueue.size()endl;coutmQueue is empty?: mQueue.isEmpty()endl;//入队mQueue.push(1); mQueue.push(2); mQueue.push(3); mQueue.push(4); coutafter push , the size of mQueue is: mQueue.size()endl;coutthe front data of mQueue is: mQueue.getFrontData()endl;coutthe back data of mQueue is: mQueue.getRearData()endl;while(!mQueue.isEmpty()){coutthe front data of mQueue is: mQueue.getFrontData()endl;mQueue.pop();coutafter pop , the size of mQueue is: mQueue.size()endl; }return 0;
}the size of mQueue is: 0 mQueue is empty?: 1 after push , the size of mQueue is: 4 the front data of mQueue is: 1 the back data of mQueue is: 0 the front data of mQueue is: 1 after pop , the size of mQueue is: 3 the front data of mQueue is: 2 after pop , the size of mQueue is: 2 the front data of mQueue is: 3 after pop , the size of mQueue is: 1 the front data of mQueue is: 4 after pop , the size of mQueue is: 0 delete the queue!!!
循环队列链式存储
#include iostream
using namespace std;
templateclass T
struct LinkNode{T data;LinkNodeT *link;LinkNode(T x,LinkNodeT *lNULL){datax;linkl;}
};
templateclass T
class LinkedQueue{protected:LinkNodeT *front,*rear;public:LinkedQueue(){frontrearNULL;}~LinkedQueue(){makeEmpty();}bool enQueue(T x){if(frontNULL)frontrearnew LinkNodeT(x);else{rearrear-linknew LinkNodeT(x);}return true;}bool deQueue(T x){if(isEmpty()) return false;LinkNodeT *pfront;xfront-data;frontfront-link;delete p;return true;}bool getFront(T x)const{if(isEmpty()) return false;xfront-data;return true;}void makeEmpty(){LinkNodeT *p;while(front!NULL){pfront;frontfront-link;delete p;}}bool isEmpty()const{return (frontNULL)?true:false;}int getSize()const{LinkNodeT *p;int count0;pfront;while(p!NULL){count;pp-link;} return count;}
};
void menu(){cout1.入队endl;cout2.获取队首元素endl;cout3.出队endl;cout4.队列置空endl;cout5.获取队中元素数量endl;cout6.退出endl;
} void function(int num,LinkedQueueint *lq){switch(num){int x;case 1:cinx;lq-enQueue(x);break;case 2:lq-getFront(x);coutxendl;break;case 3:lq-deQueue(x);break;case 4:lq-makeEmpty();break;case 5:xlq-getSize();coutxendl;break; default:exit(1);}
}
int main(int argc, char** argv) {LinkedQueueint *lqnew LinkedQueueint;int num;while(true){menu();cinnum;function(num,lq);} delete lq;return 0;
}3.双端队列 可以在两头进行插入和删除操作的队列 deque k; 定义一个deque的变量(定义时已经初始化) 例如: deque k;
k.empty() ------ 查看是否为空范例,是的话返回1,不是返回0 k.clear() ------ 清除队列里的所有数据 k.push_front(i)------ 从已有元素前面增加元素i(队伍大小不预设) k.push_back(i) ------ 从已有元素后面增加元素i(队伍大小不预设) k.pop_front() ------ 清除第一个元素 k.pop_back() ------ 清除最后一个元素 k.front() ------ 显示第一个元素 k.back() ------ 显示最后一个元素 k.size() ------ 输出现有元素的个数
例子使用c自带的库实现的
#include iostream
#include dequeusing namespace std;//main loop
int main(){dequeint myDeque;//创建一个双端队列coutthe size of myDeque is: myDeque.size()endl;coutmyDeque is empty? : myDeque.empty()endl; //从对头插入元素myDeque.push_front(1);myDeque.push_front(2);myDeque.push_front(4);myDeque.push_front(3);//从队尾插入 myDeque.push_back(0);myDeque.push_back(-1);myDeque.push_back(-1);myDeque.push_back(-3);//从队头出队dequeint tempQueue myDeque;while(!tempQueue.empty()){coutthe front data of queue is: tempQueue.front()endl;tempQueue.pop_front();coutthe size of myDeque is: tempQueue.size()endl;} //从队尾出队dequeint tempQueue1 myDeque;while(!tempQueue1.empty()){coutthe front data of queue is: tempQueue1.back()endl;tempQueue1.pop_back();coutthe size of myDeque is: tempQueue1.size()endl;} //清空队列dequeint tempQueue2 myDeque;coutthe size of myDeque is: tempQueue2.size()endl;tempQueue2.clear();coutthe size of myDeque1 is: tempQueue2.size()endl;return 0;
}the size of myDeque is: 0 myDeque is empty? : 1 the front data of queue is: 3 the size of myDeque is: 7 the front data of queue is: 4 the size of myDeque is: 6 the front data of queue is: 2 the size of myDeque is: 5 the front data of queue is: 1 the size of myDeque is: 4 the front data of queue is: 0 the size of myDeque is: 3 the front data of queue is: -1 the size of myDeque is: 2 the front data of queue is: -1 the size of myDeque is: 1 the front data of queue is: -3 the size of myDeque is: 0 the front data of queue is: -3 the size of myDeque is: 7 the front data of queue is: -1 the size of myDeque is: 6 the front data of queue is: -1 the size of myDeque is: 5 the front data of queue is: 0 the size of myDeque is: 4 the front data of queue is: 1 the size of myDeque is: 3 the front data of queue is: 2 the size of myDeque is: 2 the front data of queue is: 4 the size of myDeque is: 1 the front data of queue is: 3 the size of myDeque is: 0 the size of myDeque is: 8 the size of myDeque1 is: 0
