大一下第二学期期中知识复习梳理 之 c++动态内存分配

标签：Node 结点 template c++ 链表 期中 link 表头 动态内存

一、动态内存分配基本概念

1、数组实现顺序表的缺陷：静态内存管理——程序在编译时，根据数组元素类型和个数分配所需内存大小，在程序运行时无法改变。 2、内存空间分布

 3、动态内存管理

1）

 2）动态内存分配

（1）操作符new

动态分配变量数组（对象数组）： 指针变量=new 变量类型[变量表达式]； 指针变量的值为动态分配的数组的首地址；new的返回值是变量类型的指针，指向变量/对象（数组）的（首）地址。 分配对象空间时，调用无参数的构造函数，调用次数与数组长度相等；分配的数组空间是无名对象，只能通过指针间接访问；new分配空间可能不成功（返回NULL），因此返回 的指针访问该空间前需要进行分配确认 。 eg ： int *pi=new int[size];   Complex *pComplex=new Complex[cnt];   //不带初始化参数，必须有无参数构造函数 

 （2）优势

动态分配数组空间，数组的大小是个变量，彻底解决变长数组的问题。

2）动态内存释放

（1）操作符delete a）动态释放变量（对象）： 如果是类对象指针，则调用析构函数：delete 指针变量； 注：释放(delete)指针变量指向的空间，不是delete指针变量 b） 动态释放数组 如果是类对象指针，则调用析构函数，调用次数与数组长度相等：delete []指针变量； 注：如果是类对象数组指针，则调用多次析构函数；[]中不用写数组元素个数，系统会自动判断。 eg：Complex *p=new Complex[10]; A) delete p;   ×  ——只删除第一个元素p[0]   ； B) delete []p; √  ——删除整个数组p[0]~p[9] 例：动态数组的建立与撤销：

#include <iostream>
#include <cstring>
using namespace std;
int main(){
int n;
char *pc;
cout<<"请输入动态数组的元素个数"<<endl;
cin>>n;
pc=new char[n]; //申请包含25个字符元素的内存空间
strcpy(pc,“自由存储区内存的动态分配”); //12个字+’\0’
cout<<pc<<endl;
delete []pc; // 撤销并释放pc所指向的n个字符的内存空间
return 0 ;
}

View Code

例：自由存储区对象分配和释放 

#include<iostream>
using namespace std;
class CGoods{
    string Name;
    int Amount;
    float Price;
    float Total_value;
public:
    CGoods(){cout<<"调用默认构造函数"<<endl;};
    CGoods(string name,int amount ,float price){
    cout<<"调用三参数构造函数"<<endl;
    Name=name; Amount=amount;
    Price=price; Total_value=price*amount;
    }
    ~CGoods(){ cout<<"调用析构函数"<<endl;}
};
int main()
{
    int n;
    CGoods *pc,*pc1,*pc2;
    pc=new CGoods("夏利2000",10,118000); //调用三参数构造函数
    pc1=new CGoods(); //调用默认构造函数
    cout<<"输入商品类数组元素数"<<endl;
    cin>>n;
    pc2=new CGoods[n]; //调用默认构造函数，共调n次
    delete pc;
    delete pc1;
    delete []pc2;
    return 0;
}
 

View Code

c）空悬指针

动态释放后，指针变量还可以用来访问空间，warning！ 避免措施：动态释放后立即将指针变量置为空值：指针变量名=NULL; 3）动态内存管理 （1）操作符new和delete必须配对使用 （a）内存泄漏：少了：没有delete——导致动态分配的空间没有释放，也无法被再次分配； （b）重复释放：多了：重复delete——可能这部分空间已经被再次分配，再次delete时导致新分配的空间被误释放，或者其他不可预知的后果。 （2）动态分配对象的生命期不限于建立时的作用域。

 （3）对类对象复制的影响

(a）复制构造函数

 初始化的时候复制  参数值传递  返回值值传递 （b）赋值操作符重载函数  使用的时候复制  （c）浅复制和深复制

 

深复制实现类对象复制，分两步： 第一步，内存分配：对新的类对象，动态分配新的堆空间 第二步，内存初始化：复制原有对象的堆空间的值，用以初始化新分配的堆空间 受深复制影响的类成员函数： 复制构造函数；赋值操作符重载函数；析构函数。

#include<iostream>
#include<cstring>
using namespace std;
class student
{
    char *pName;
public:
    student();
    student(char *pname);
    student(student& str); //复制构造函数
    student & operator=(student & str); //赋值操作符重载函数
    ~student(); //析构函数        
};
student::student()
{
    cout<<"Constructor";
    pName=NULL;
    cout<<"默认"<<endl;
}
student::student(char *pname)
{
    cout<<"Constructor";
    if(pName=new char[strlen(pname)+1])
    //加1不可少，否则串结束符冲了其他信息，析构会出错！
    strcpy(pName,pname);
    cout<<pName<<endl;
}
//深复制：自定义复制构造函数实现深复制
student::student(student& str)
{
    cout<<"Copy Constructor";
    if (str.pName){ //待复制堆空间非空
    pName=new char [strlen(str.pName)+1]; //先分配
    if (pName) strcpy(pName, str.pName); //再复制
    }
    else pName=NULL;
}
//深复制：自定义赋值操作符重载函数实现深复制 
student & student::operator=(student &str)
{
    cout<<"Copy Assign operator";
    if(pName!=str.pName)//排除赋值给自己的情况，如s1=s1;
    {
        delete []pName; pName=NULL;//先释放堆空间并将指针置空
    }
    if(str.pName) //待复制堆空间非空
    {
        pName=new char [strlen(str.pName)+1];//先分配
        if(pName) strcpy(pName,str.pName);//后复制
    }
    else pName=NULL;
    return *this;
}
student::~student()
{
    cout<<"Destructor";
    delete []pName;
}
int main()
{
    student s1("范英明"),s2("沈俊"),s3;
    student s4=s1;
    s3=s2;
    return 0;
 } 

深复制的实现

二、线性表之链表

1、基本概念

1）线性表：一种含有n(≥0)个同类结点的有限序列 a）均匀性：各个结点具有相同的数据类型 b）有序性：各个结点之间的相对位置是线性的 c）按访问方式不同，可分为： 直接随机访问：顺序表（数组）；间接顺序访问：链表（参见7.2节）；双端单向访问：队列（参见7.3节）；单端双向访问：栈（参见7.3节）。

 2、单（向）链表

1）单链表的特征： a）间接顺序访问：只能由表头(head)开始，逐个访问各个结点。 b）只能访问每个结点的后继结点，不能访问前驱结点（不代表没有前驱）。 

 2）单链表的构成

（1）结点（多个）：结构变量/类对象

数据域（黄色）：存储结点数据 指针域（红色）：指向结点结构变量/类对象的指针，存储该结点的后继节点的地址

typedef int Datatype; //将int类型重命名为Datatype类型
struct node{
Datatype info; //数据域
node *link; //指针域
//指针域类型为结点类型的指针，node *缺少*则为结点类型，导致无穷递归定义的错误
};
node * n1, n2;

（2）表头指针head

定义： node *head; 指向链表第一个结点；通过head再顺序遍历链表的其他结点；如果head的值(表头地址)丢失，则整个链表丢失，内存泄漏。 （3）表尾指针tail 定义： node *tail; 指向链表最后一个结点，指针域的值为NULL；可由表头指针遍历寻得（因此也可以没有）

3）单链表操作

（1）查找结点

表头head不能动，用p指针从表头起访问每个结点。 查找终止条件：找到了：p指向的结点就是要找的结点：p->info==data  ； 找完了：p指：表尾的后继，也就是NULL：p==NULL 。 类似方式实现：打印链表，计算链表长度。

node *traversal(node *head, Datatype data){
node *p=head;
//从表头起逐个访问每个结点的后继
while(p!=NULL&&p->info!=data) p=p->link;
return p;
}

（2）插入结点

a）本质：排队和单链表类似，具有方向性——排队：向前排，插入影响后一个人（的前驱）；单链表：向后排，插入影响前一个结点（的后继）。 b）插入新结点：找到前一个结点q（插在q结点之后）： ① 修改新结点的后继，指向后一个结点p ② 修改前一个结点p的后继，指向新结点 ③ 必要的话，更新表头/表尾 c）在指定位置插入新结点newnode （i）中间（q->newnode->p）：

//①修改newnode的后继，指向p结点
newnode->link=p; //或newnode->link=q->link;
//②修改q结点的后继，指向newnode
q->link=newnode

（ii）表尾tail：

//①修改newnode的后继，指向NULL
newnode->link=NULL;
//②修改tail的后继，指向newnode
tail->link=newnode;
//③修改tail，指向newnode
tail=newnode;

（iii）表头head：

//①修改newnode的后继，指向head
newnode->link=head; 
//②修改head，指向newnode
head=newnode;

d）统一算法：实现某结点后插入新结点

在链表前额外加上一个空表头，空表头的数据域是空的，插入结点只能在空表头之后。 注意：链表为空时，仍有空表头。

//在q结点后插入新结点
void insert(node *q, Datatype x){
node *newnode=new node; //①新建结点newnode
newnode->info=x; //②newnode数据域赋值
newnode->link=q->link; //③newnode后继指向q结点的后继
q->link=newnode; //④q结点后继指向newnode
}

 （3）生成链表

a）向前生成链表：由表尾向表头逐步生成链表，将每个新结点插入表头结点之后

node *createup(){
node *head,*p;
Datatype data;
//step1:建立空表头
head=new node;
head->link=NULL;
//step2:将每个新结点作为表头结点的后继
while(cin>>data){
p=new node; //建立新结点
p->info=data; //新结点写入数据
p->link= head->link; //表头结点的后继作为新结点的后继
head->link=p; //新结点作为表头结点的后继
}
//step3:返回表头结点
return head;
}

b）向后生成链表：由表头向表尾逐步生成链表，将每个新结点插入表尾结点之后

node *createdown(){
node*head,*tail,*p;
Datatype data;
//step1:建立表尾(头)结点
tail=head=new node;
//step2:将每个新结点作为表尾结点的后继
while(cin>>data){
p=new node; //建立新结点
p->info=data; //新结点写入数据
tail->link=p; //新结点作为表尾结点的后继
tail=p; //新结点作为表尾
}
//step3:表尾结点的后继置为NULL
tail->link=NULL;
//step4:返回表头结点
return head;}

（4）删除结点

①找到前一个结点 ②修改前一个结点的后继，指向该结点的后继 ③释放该结点

//删除q结点之后的结点
void del (node *q){
node *delnode=q->link; //①标记被删结点为delnode
q->link=delnode->link; //②q结点后继指向delnode的后继
delete delnode; //③释放delnode
}
//②还可以写成q->link=q->link->link;

（5）单链表操作小结 a）核心：指针的读写 q->link=delnode->link; 赋值号左边(q->link)：被修改的指针，q结点（q指针指向的结点）的link指针； 赋值号右边（delnote->link）：q->link指针被修改为指向delnote->link；或者说，q->link指针的值（是一个地址）被修改为delnote->link指针的值。 b）每个结点通过指针域(link)连接下一个结点，构成链表。链表操作的关键 是结点指针域的修改：插入/删除结点，修改前驱结点的指针域(link)。 c）链表结点的个数运行时确定，每个结点也是动态分配，结点从链表删除时，注意结点内存的动态释放。 4）类模板实现单链表 （1）两个类模板： a）结点类模板Node 处理对象：结点 封装结点的属性（数据域；指针域）和基本操作 将链表类List作为友元类——可以在List类成员函数中直接访问Node的私有成员（数据域、指针域）。 b）链表类模板List 处理对象：链表 封装链表的属性（表头指针；表尾指针）和基本操作

（2）函数实现 （a）结点类模板Node： 在结点自身后插入结点InsertAfter，删除结点自身后的结点RemoveAfter

 1 #include<iostream>
 2 using namespace std;
 3 //结点类
 4 template<typename T> class List;//引用声明
 5 template<typename T>
 6 class Node{
 7     T info; //数据域
 8     Node<T> *link; //指针域
 9 public:
10     Node(); //构造函数（空表头结点）
11     Node(const T & data); //构造函数（非表头结点）
12     void InsertAfter(Node<T>* p); //在结点自身后插入结点
13     Node<T>* RemoveAfter(); //在结点自身后删除结点
14     friend class List<T>;
15     //以List类为友元类，使得List类可访问Node类的私有成员(info和link)
16 };
17 //构造表头结点
18 template <typename T> 
19 Node<T>::Node(){
20     link=NULL;
21 }
22 //构造结点（非表头）
23 template <typename T> 
24 Node<T>::Node(const T & data){
25     info=data;
26     link=NULL; 
27 }
28 //在结点自身后插入结点
29 template<typename T> 
30 void Node<T>::InsertAfter(Node<T>* p){
31 p->link=link; //本结点的后继作为新结点的后继
32 link=p; //新结点作为本结点的后继
33 }
34 //在结点自身后删除结点
35 template<typename T>
36 Node<T>* Node<T>::RemoveAfter(){
37 Node<T>* tempP=link; //被删结点指向本结点的后继
38 if(link) link=link->link; //如非链尾，后继的后继作为新的后继
39 return tempP; //返回被删结点
40 }

结点类模板 （b）链表类模板List： 清空链表（只留表头）MakeEmpty，查找链表中的结点 Find，计算链表长度 Length，显示链表 PrintList，向前生成链表 InsertFront，向后生成链表 InsertRear，升序生成链表 InsertOrder，创建结点（孤立结点） CreateNode，删除链表中的结点 DeleteNode。

  1 //链表类
  2 template<typename T>
  3 class List{
  4     Node<T> *head,*tail; //链表头指针和尾指针
  5 public:
  6     List(); //构造函数，生成空链表
  7     ~List(); //析构函数
  8     void MakeEmpty(); //清空链表，只余表头结点
  9     Node<T>* Find(T data); //查找结点
 10     int Length(); //计算链表长度
 11     void PrintList(); //显示链表
 12     void InsertFront(Node<T>* p); //向前生成链表
 13     void InsertRear(Node<T>* p); //向后生成链表
 14     void InsertOrder(Node<T> *p); //升序生成链表
 15     Node<T>*CreatNode(T data); //创建结点(孤立结点)
 16     Node<T>*DeleteNode(Node<T>* p); //删除结点
 17 }; 
 18 //构造函数，生成空链表（只有表头结点）
 19 template<typename T>
 20 List<T>::List(){
 21     head=tail=new Node<T>();
 22 }
 23 //析构函数
 24 template<typename T>
 25 List<T>::~List(){
 26     MakeEmpty(); //删除除了表头结点外的所有节点
 27     delete head;
 28 }
 29 //清空链表（只剩表头结点）
 30 template<typename T>
 31 void List<T>::MakeEmpty(){
 32     Node<T> *tempP; //标记被删结点为tempP
 33     while(head->link!=NULL){
 34     tempP=head->link; //tempP指向表头的后继结点
 35     head->link=tempP->link; //表头的后继指向tempP的后继
 36     //head->link=head->link->link;
 37     delete tempP;
 38     }
 39     tail=head; //只剩空表头，表头与表尾相同，即为空链
 40 }
 41 //查找结点
 42 template<typename T> 
 43 Node<T>* List<T>::Find(T data){
 44     Node<T> *tempP=head->link;
 45     while( tempP!=NULL&&tempP->info!=data)
 46     tempP=tempP->link;
 47     return tempP;
 48 }
 49 //计算链表长度
 50 template<typename T> 
 51 int List<T>::Length(){
 52     Node<T>* tempP=head->link;
 53     int count=0;
 54     while(tempP!=NULL){
 55     count++;
 56     tempP=tempP->link; }
 57     return count;
 58 }
 59 //打印链表
 60 template<typename T>
 61 void List<T>::PrintList(){
 62     Node<T>* tempP=head->link;
 63     while(tempP!=NULL){
 64     cout<<tempP->info<<'\t';
 65     tempP=tempP->link; }
 66     cout<<endl;
 67 }
 68 //计算链表长度
 69 template<typename T> 
 70 int List<T>::Length(){
 71     Node<T>* tempP=head->link;
 72     int count=0;
 73     while(tempP!=NULL){
 74     count++;
 75     tempP=tempP->link; }
 76     cout<<endl;
 77 }
 78 //向前生成链表
 79 template<typename T>
 80 void List<T>::InsertFront(Node<T> *p){
 81     p->link=head->link;
 82     head->link=p;
 83     if(tail==head) tail=p;
 84 }
 85 //向后生成链表
 86 template<typename T>
 87 void List<T>::InsertRear(Node<T> *p){
 88     p->link=tail->link; //p->link=NULL;
 89     tail->link=p;
 90     tail=p;
 91 }
 92 //升序生成链表
 93 template<typename T>
 94 void List<T>::InsertOrder(Node<T> *p){
 95     Node<T> *tempQ=head, *tempP=head->link; 
 96     //tempP是tempQ的后继
 97     while(tempP!=NULL){
 98     //找到正确位置(tempQ?p?tempP)或到表尾
 99     if(p->info<tempP->info) break; 
100     //一旦发现第一个更大的结点，即表示找到插入点
101     tempQ=tempP;
102     tempP=tempP->link;
103     }
104     tempQ->InsertAfter(p);//将p结点插在tempQ之后
105     if(tail==tempQ)
106     tail=tempQ->link; //tail=p;
107 }
108 //生成结点（孤立结点）
109 template<typename T>
110     Node<T>* List<T>::CreatNode(T data){
111     Node<T>*tempP=new Node<T>(data);
112     return tempP;
113 }
114 //删除结点p
115 template<typename T>
116 Node<T>* List<T>::DeleteNode(Node<T>* p){
117     Node<T>* tempP=head; //tempP作为p的前驱
118     while(tempP->link!=NULL&&tempP->link!=p)
119     tempP=tempP->link;
120     if(tempP->link==tail) tail=tempP;
121     return tempP->RemoveAfter(); 
122 }

链表类模板

5）线性表之链表

（1）顺序表vs链表

 （2）基本概念

线性表：一种含有n(≥0)个同类结点的有限序列。 a）均匀性：各个结点具有相同的数据类型； b）有序性：各个结点之间的相对位置是线性的； 特殊的线性表：可由顺序表或链表实现。 栈(stack)&队(queue)：操作（插入/删除）结点位置受限——与顺序表/链表区别

（3）栈

a）概念：

 b）实现方式

 1 //顺序表
 2 template <typename T, int size>
 3 class SeqList{
 4     T list [size];
 5     int max_size;
 6     int last;
 7 public:
 8     SeqList();
 9     bool IsEmpty()const; 
10     bool IsFull()const;
11     bool Insert(T & x, int i);
12     bool Remove(T & x);
13     void MakeEmpty();
14 }
15 //顺序栈
16 template <typename T, int size>
17 class Stack{
18     T list [size];
19     int max_size;
20     int top;
21 public:
22     Stack();
23     bool IsEmpty( )const; 
24     bool IsFull( )const;
25     void Push(const T & data);
26     T Pop();
27     void MakeEmpty();
28 }
29 //顺序表
30 template <typename T, int size>
31 SeqList<T, size>:: SeqList()
32 {
33     last=-1;
34     max_size=size;
35 }
36 //顺序栈
37 template <typename T, int size>
38 Stack<T, size>::Stack()
39 {
40     top=-1;
41     max_size=size;
42 }
43 //顺序表
44 template <typename T, int size>
45 bool SeqList<T, size>::IsEmpty( ) const // 判断表是否空
46 { return last == -1; }
47 template <typename T, int size>
48 bool SeqList<T, size>::IsFull( ) const // 判断表是否满
49 { return last == max_size - 1; }
50 //顺序栈
51 template <typename T, int size>
52 bool Stack<T, size>::IsEmpty( ) const // 判断栈是否空
53 { return top == -1; }
54 template <typename T, int size>
55 bool Stack<T, size>::IsFull( ) const // 判断栈是否满
56 { return top == max_size - 1; }
57 //顺序表
58 template <typename T, int size> 
59 bool SeqList<T, size>::Insert(T & x, int i)
60 {
61     if (…) return false;
62     else {…; return true;}
63 }
64 //顺序栈
65 template<typename T, > 
66 void Stack<T>::Push(const T &data){
67     assert(!IsFull()); //栈满则不能继续压栈，退出程序
68     list[++top]=data; //栈顶指针先加1，元素再进栈
69 }
70 //顺序表
71 template <typename T, int size> 
72 bool SeqList<T,size>::Remove(T & x){
73 ....
74 }
75 //顺序栈
76 template<typename T, int size>
77 T Stack<T, size>::Pop(){
78     assert(!IsEmpty()); //栈空则不能继续出栈，退出程序
79     return list[top--]; //返回栈顶元素，同时栈顶指针退1
80 }
81 //顺序表
82 template<typename T, int size>
83 void SeqList<T, size>::MakeEmpty(){
84     last=-1;
85 }
86 //顺序栈
87 template<typename T, int size>
88 void Stack<T, size>::MakeEmpty(){
89     top=-1;
90 }

顺序栈类模板

 c）链栈

#include<iostream>
using namespace std;
//链栈结点 
template<typename T>class Stack;
template<typename T>class Node
{
    T info;
    Node<T> *link;
public:
    Node(T data=0,Node<T>*next=NULL)
    {
        info=data;
        link=next;
    }
    friend class Stack<T>;
};
//用于链表类的结点类的构造函数
template<typename T>
Node<T>::Node(const T &data)
{
    info=data;
    link=NULL;
 } 
//链栈 
template <typename T>class Stack
{
    Node<T> *top;  //栈顶指针 
public:
    Stack();
    ~Stack();
    void MakeEmpty();
    bool IsEmpty();
    void Push(const T &data);
    T Pop();
    T GetTop();
};
//构造函数 
template<typename T>
Stack<T>::Stack()
{ top=NULL; }
//析构函数 
template<typename T>
Stack<T>::~Stack()
{ MakeEmpty(); }
//清空栈 
template<typename T>
void Stack<T>::MakeEmpty()
{
    Node<T> *temp;
    while(top!=NULL)
    {
        temp=top;
        top=top->link;
        delete temp;
    }
}
//判断栈空 
template<typename T>
bool Stack<T>::IsEmpty()
{ return top==NULL; }
//压栈
template<typename T>
void Stack<T>::Push(const T&data)
{ top=new Node<T>(data,top); }
//出栈 
template<typename T>
T Stack<T>::Pop()
{
    assert(!IsEmpty());
    Node<T> *temp=top;
    T data=temp->info;
    top=top->link;
    delete temp;
    return data;
}
//取栈顶 
template<typename T>
T Stack<T>::GetTop()
{
    assert(!IsEmpty());
    return top->info;
}

int main()
{
    return 0;
}

链栈类模板

d）顺序栈vs链栈

 三、线性表之队列

1、基本概念：

操作位置固定：入队的位置：队尾；出队的位置：队首。——先进先出。

 2、循环队列

#include<iostream>
using namespace std;
template<typename T>
class Queue
{
    int rear,front;    //队尾/队首 
    T *elements;    //动态数组指针 
    int MaxSize;    //最多只能容纳MaxSize-1个 
public:
    Queue(int ms);
    ~Queue();
    void MakeEmpty();           //清空 
    bool IsEmpty() const;        //是否满 
    bool IsFull() const;        //是否空 
    int Length() const;            //长度 
    void EnQue(const T&data);    //入队 
    T DeQue();                    //出队 
    T GetFront();                //取队首数据 
};
//构造函数 
template<typename T>
Queue<T>::Queue(int ms)
{
    MaxSize=ms;
    rear=front=0;
    elements=new T[MaxSize];
    assert(elements!=NULL);    //断言分配成功 
}
//析构函数 
template<typename T>
Queue<T>::~Queue()
{ delete[]elements; }
//清空队列 
template<typename T>
void Queue<T>::MakeEmpty()
{ front=rear=0; }
//是否空 
template<typename T>
bool Queue<T>::IsEmpty() const
{ return front==rear; }
//是否满 
template<typename T>
bool Queue<T>::IsFull() const
{ return (rear+1)%MaxSize==front; }
//队列长度 
template<typename T>
int Queue<T>::Length() const
{ return (rear-front+MaxSize)%MaxSize; }
//进队 
template<typename T>
void Queue<T>::EnQue(const T&data)
{
    asssert(!IsFull());        //断言队列不满
    rear=(rear+1)%MaxSize;    //更新队尾下标
    elements[rear]=data;    //从队尾入队
}
//出队 
template<typename T>
T Queue<T>::DeQue()
{
    asssert(!IsEmpty());        //断言队列不空
    front=(front+1)%MaxSize;    //更新队首下标
    return elements[front];        //从队首出队
}
//取队首数据 
template<typename T>
T Queue<T>::GetFront()
{
    assert(!IsEmpty());
    return elements[(front+1)%MaxSize];
}

int main()
{
    Queue<char>que;
    int i;
    char str1[]="abcdefghijklmnop";
    que.MakeEmpty();
    for(i=0;i<17;i++) que.EnQue(str1[i]);
    if(que.IsFull()) cout<<"队满";
    cout<<"共有元素："<<que.Length()<<endl;
    for(i=0;i<17;i++) cout<<que.DeQue();
    cout<<endl;
    if(que.IsEmpty()) cout<<"队空";
    cout<<"共有元素："<<que.Length()<<endl;

     return 0;
}

循环队列类模板

3、链表队列

#include<iostream>
using namespace std;
template<typename T>Queue;    //链队类模板 
template<typename T>        //联队结点类模板 
class Node
{
    T info;
    Node<T> *link;
public:
    Node(T data=0,Node *next=NULL)
    { info=data; link=next;}
    friend class Queue<T>;
};
template<typename T>
class Queue
{
    Node<T>*front,*rear;
public:
    Queue();
    ~Queue();
    void MakeEmpty();            //清空队列
    bool IsEmpty();                //是否空
    void Enque(const T &data);    //进队
    T DeQue();                    //出队
    T GetFront();                //取队首数据
};
//构造函数 
template<typename T>
Queue<T>::Queue()
{ rear=front=NULL; }
//析构函数 
template<typename T>
Queue<T>::~Queue()
{ MakeEmpty(); }
//清空队 
template<typename T>
void Queue<T>::MakeEmpty()
{
    Node<T> *temp;
    while(front)
    {
        temp=front;
        front=front->link;
        delete temp;
    }
}
//判断队空 
template<typename T>
bool Queue<T>::IsEmpty()
{ return NULL==front; }
//入队 
template<typename T>
void Queue<T>::EnQue(const T &data)
{
    if(NULL==front)     //空队，新结点既是队尾，也是队首
    front=rear=new Node<T>(data,NULL);
    else              //非空队，新结点是队尾
    rear=rear->link=new Node<T>(data,NULL);
}
//出队 
template<typename T>
T Queue<T>::DeQue()
{
    assert(!IsEmpty());
    Node<T> *temp=front;
    T data=temp->info;    //取队首结点数据
    front=front->link;    //队首出队
    delete temp;        //释放队首结点空间
    return data;
}
template<typename T>
T Queue<T>::GetFront()
{
    assert(!IsEmpty());
    return front->info;
}
int main()
{
    return 0;
}

链队结点类

四、小结

1、动态内存分配（7.1.1, 7.1.2节）
（1）分配地址：
堆(heap)，又称自由存储区
区别于：栈(stack)，局部变量区；全局与静态变量区；代码区
（2）分配/释放：操作符new和delete

a）new：返回指针类型
可分配变量（对象）并初始化，也可分配数组，但二者只能选一种
b）delete：通过指针变量释放
释放数组空间，要加[]（即 delete[] ）
注意问题:
分配失败（new后可能）；空悬指针（delete后一定是）；内存泄露（少delete时）；重复释放（多delete时）
动态分配对象的生命期：new后， delete前，二者之间。

2、浅复制与深复制（7.1.3节）
（1）场景：类对象的复制：
一个类对象给另一个类对象复制（赋值操作符重载）；初始化类对象（复制构造函数）；类对象作为参数值传递（复制构造函数）；类对象作为返回值值传递（复制构造函数）。

（2）复制方法区别

浅复制：仅复制每个类成员变量的值

深复制：对于类成员变量不是指针类型的，同浅复制；是指针类型的，先动态分配空间，再复制空间的值
浅复制的错，在于两个对象使用时一个对象析构，而另一个对象析构前（仍在使用时），析构后
深复制用处：复制构造函数；赋值操作符重载函数；析构函数。

3、链表（7.2 节）
（1）用处：每新增一个表成员，分配一个新结点；反之亦然。节省空间。
（2）结点构成：数据域；指针域（单链表中有且仅有一个后继指针）
（3）操作要点：
a）表头指针head不能丢
b）插入/删除结点时，关键在于修改前一个结点的指针域
c）增加时，动态分配新结点；删除时，动态释放原有结点（可选）
（4）链表操作的关键： 画图
a）查找/打印/数个数：表头起，向后逐个结点，直至表尾
b）插入结点：关键找到前一个结点；先改新结点后继，再改前一个结点后继续。

插入结点基础上：前向生成（插在表头后）；后向生成（插在表尾后）；升序生成。

空表头存在原因：
c）删除结点：关键找到前一个结点；先存待删结点，再改前一个结点后继。

4、栈（7.3.1节）
（1）特征：单端双向；后进先出
（2）顺序栈：栈顶在表尾
压栈：简化的插入结点；出栈：简化的删除结点
（3）链栈：栈顶在表头（无空表头）；不会满
压栈：简化的插入结点；出栈：简化的删除结点（位置明确）
5、队（7.3.2节）
（1）特征：双端单向；先进先出
（2）顺序队：必须用循环队（栈的时候不存在原因）
注意队首/队尾间的关系（空/满/数个数/入队/出队）
（3）链队：队首即表头（无空表头），队尾即表尾；不会满。
入队：简化的插入插入结点；出队：简化的删除结点（位置明确）

6、顺序表/链表实现栈/队

 

标签：Node,结点,template,c++,链表,期中,link,表头,动态内存
From： https://www.cnblogs.com/konglingyi/p/17370489.html