程序员经验分享-hwhale

数据结构——小白入门篇

2023-11-09

数据结构——小白入门篇

浅谈学习心得

  • 我为什么想要学数据结构？

    在计算机界有这样一个万能公式：数据结构 + 算法 = 程序.

    在如今这计算机引领风骚的时代，不学数据结构，你凭什么想要做时代的弄潮儿；所以我毅然决然的提前自学了数据结构。

  • 学习数据结构前的我是这样认为的？！

    什么是数据结构？数据结构要用什么语言实现？学了数据结构后能做什么？

  • 学习数据结构后的我有什么感触?

    • 数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成。
      记为：

      Data_Structure=(D,R)

      其中D是数据元素的集合，R是该集合中所有元素之间的关系的有限集合。

    • 数据结构是一种处理数据的思想；

    • 数据结构是一种处理数据的模型（计算机的本领就是处理数据的能力超强），可见数据结构的重要性！

学习过程总结

学习技巧：

    **实践是检验真理的唯一标准，也是学习数据结构的唯一技巧**

文中所有的代码实现都使用了类模板，大家使用时可酌情选择！

  • 第一夜：线性表

    线性结构：数据结构中的元素存在一对一的相互关系，

    线性表是N个数据元素的有限序列；

    • 常用的线性结构有：线性表，栈，队列，双队列，数组，串。
    • 常见的非线性结构有：二维数组，多维数组，广义表，树(二叉树等)，图。
    • 在具体实现时，长度Length的概念贯穿在顺序表和链表中，非常有用；

    以下主要总结了两种特例线性结构：顺序表和链表；

线性表之——顺序表篇

用基本数据类型—数组 去实现顺序表的增改删查的方法，
话不多说，直接上源码解释；

  1. list.h 文件内容如下：
/*
    代码要求实现效果:建立一个顺序表存取一下序列：
    1,3,5,7,9

    对于线性表中的每一个元素，在该元素前的一个元素叫 前驱 ，
    在该元素后的一个元素叫 后继 ，
    第一个元素只有 后继，最后一个元素只有 前驱；
*/

#ifndef LIST_H
#define LIST_H

/*
#ifndef LIST_H 
#define LIST_H

...

#endif

这样一段话的意思是 如果没有定义头文件的别名，就定义它

他的作用是，如果有其他文件多次调用这个头文件，那么为了防止重复定义，加入

判断语句，只有第一次会进行定义，当第一个定义后，其他的调用定义会忽略。
*/

#include <iostream>

using namespace std;

template <class Datatype>  // 定义类模板
class List
{
public:
    List(int size); //构造函数，定义数组大小为size
    ~List();
    void clearList();  //清空该顺序表
    bool listEmpty(); //用于判断该表是否为空，返回bool类型
    int listLength(); //用于检测数组（表）中以存元素的数量
    Datatype listGet(int i); //获取数组（表）中指定的索引的元素；
    int listLocate(Datatype x); //用于获取指定元素在数组中第一次出现位置的索引；
    Datatype Precursor(Datatype x); //获取指定元素的前驱；
    Datatype next(Datatype x); //获取指定元素的后驱
    bool listInsert(int i,Datatype x); //用于在索引为i的位置插入元素
    Datatype listDelete(int i); //用于删除索引为i的元素；
    void printList(); //遍历并打印出该顺序表；
private:
    Datatype *p_List;  //定义表的指针变量
    int Size; // 用于初始化表的大小
    int Length; //存表所存元素的数量
};

template <class Datatype>
List<Datatype>::List( int size )
{
    Size = size; //有用户传入参数以定义表的大小；
    Length = 0; //长度初始化为0；
    p_List = new Datatype[Size]; //在堆中去申请一个数组用于实现顺序表（存数据）；
}

template <class Datatype>
List<Datatype>::~List() //析构函数，用于整理申请的空间归仓；
{
    delete []p_List;
    p_List = NULL;
}

template <class Datatype>
void List<Datatype>::clearList()
{
    Length = 0; // 将表的元素个数置 0
    //(因为下面所有的操作都是基于元素长度来进行，
    //所以这里将长度置为0就相当于在清空表)
}

template <class Datatype>
bool List<Datatype>::listEmpty()
{   //这里很容易理解吧！
    if (Length == 0)
    {
        return true;
    } 
    else
    {
        return false;
    }
}

template <class Datatype>
int List<Datatype>::listLength()
{
    return Length;
}

template <class Datatype>
Datatype List<Datatype>::listGet( int i )
{   
    //遍历整个表去寻找；
    try
    {
        if (i>=0&&i<=Length)
        {
            return p_List[i];
        }
        else
        {
            throw 1; //所给元素越界，抛出错误!
        }
    }

    catch(int) //捕捉错误；
    {
        cout<<"查找位置非法！"<<endl;
    }
}

template <class Datatype>
int List<Datatype>::listLocate( Datatype x )
{
    for (int j=0;j<Length;j++) //遍历整个数组寻找
    {
        if (x == p_List[j])
        {
            return j; //找到就返回元素的索引；
        }
    }
    return 0;  // 没找到就返回0；
}

template <class Datatype>
Datatype List<Datatype>::Precursor( Datatype x )
{
    try
    {
        int temp = listLocate(x); //先定位到该元素；
        //若有所指的元素有前驱便返回前驱；
        if (temp!=0 && temp>0 && temp<=Length)
        {
            return p_List[temp-1];
        } 
        else
        {
            throw 1;
        }
    }
    catch(int)
    {
        cout<<"该位置没有前驱！"<<endl;
    }
}

template <class Datatype>
Datatype List<Datatype>::next( Datatype x )
{
    try
    {
    //写法类似于找前驱！
        int temp = listLocate(x);
        if (temp>=0 && temp<Length)
        {
            return p_List[temp+1];
        } 
        else
        {
            throw 1;
        }
    }
    catch (int)
    {
        cout<<"该位置没有后驱！"<<endl;
        //exit(1);
    }

}

template <class Datatype>
bool List<Datatype>::listInsert( int i,Datatype x )
{
//插入元素时必须把插入点后面的元素都往后移动一个位置
    if (i<0 || i>Length) //判断位置合法性；
    {
        return false;
    } 
    for (int k=Length-1;k>=i;k--) //从后往前遍历，已达到移位的效果；
    {
        p_List[k+1] = p_List[k];
    }
    p_List[i] = x; //移动完毕，实施插入；
    Length++; // 长度+1
    return true; //返回插入成功的信号（bool类型）
}

template <class Datatype>
Datatype List<Datatype>::listDelete( int i)
{
//删除元素是，该元素之后的所有元素分别往前移动一位即可；
    try
    {
        if (i<0||i>Length) //判断i的合法性；
            {
                throw 1;
            }
        Datatype temp;
        temp = p_List[i]; //存下要删除的元素，以便于返回其值出来
        for (int k=i;k<Length;k++)//从后往前遍历，已达到移位的效果；
        {
            p_List[k] = p_List[k+1];
        }
        Length--;
        return temp;
    }   
    catch (int)
    {
        cout<<"删除位置非法!"<<endl;
        //exit(1);
    }
}

template <class Datatype>
void List<Datatype>::printList()
{
//遍历输出表中所有元素；
    for (int i=0;i<Length;i++)
    {
        cout<< p_List[i] <<endl;
    }
}

#endif
  1. list.cpp 文件的类容如下：(测试代码)
#include "list.h"
#include <iostream>
#include "Coordinate.h"

using namespace std;

int main()
{

    cout<<list.listEmpty()<<endl;

    int num[5] = {1,3,5,7,9};
    for (int i=0;i<5;i++)
    {
        list.listInsert(i,num[i]);
    }
    list.printList();

    cout<< list.listLength()<<endl;

    int m,n;
    m = list.listDelete(4);
    n = list.listDelete(0);
    cout<< m <<endl;
    cout<< n <<endl;
    list.listLength();

    cout<<list.listGet(1)<<endl;
    cout<<list.Precursor(5)<<endl;
    cout<<list.next(3)<<endl;

    list.clearList();
    cout<<list.listLength()<<endl;
    list.listDelete(1);
    cout<<list.listLength()<<endl;
    list.Precursor(1);

    list.printList();

    system("pause");
    return 0;
}
  1. 用刚实现的顺序表存 点 类型的数据，下面为 点 类型的类的代码，包括相关运算符的重载；
    下面为 coordinate.h 文件的源码：
#ifndef COORDINATE_H
#define COORDINATE_H

#include <iostream>
#include <ostream>

using namespace std;

class Coordinate
{
    //声明输出重载函数为友元函数；
    friend ostream &operator<<(ostream &out,Coordinate &coor); 
public:
    Coordinate(int x=0,int y=0); //含默认参数的构造函数；
    ~Coordinate(){};
    void printCoordinate(); // 打印出 点 ；
    bool operator==(Coordinate &coor); //重载用算符 == 

protected:
    int X;
    int Y;
};

Coordinate::Coordinate( int x/*=0*/,int y/*=0*/ )
{
    X = x;
    Y = y;
}

void Coordinate::printCoordinate()
{
    cout<< "(" << X << ',' << Y << ")" <<endl;
}

ostream &operator<<(ostream &out,Coordinate &coor)
{
    out<< "(" << coor.X << ',' << coor.Y << ")" <<endl;
    return out;
}


bool Coordinate::operator==( Coordinate &coor )
{
    if (this->X == coor.X && this->Y == coor.Y)
    {
        return true;
    } 
    else
    {
        return false;
    }
}


#endif

以下为coordinate类的测试源码：

#include "list.h"
#include <iostream>
#include "Coordinate.h"

using namespace std;

int main()
{

    List<Coordinate> list(5);
    cout<<list.listEmpty()<<endl;
    /*
    int num[5] = {1,3,5,7,9};
    for (int i=0;i<5;i++)
    {
        list.listInsert(i,num[i]);
    }
    list.printList();

    cout<< list.listLength()<<endl;

    int m,n;
    m = list.listDelete(4);
    n = list.listDelete(0);
    cout<< m <<endl;
    cout<< n <<endl;
    list.listLength();

    cout<<list.listGet(1)<<endl;
    cout<<list.Precursor(5)<<endl;
    cout<<list.next(3)<<endl;

    list.clearList();
    cout<<list.listLength()<<endl;
    //list.listDelete(1);
    //cout<<list.listLength()<<endl;
    //list.Precursor(1);
    */

    Coordinate e1(1,1);
    Coordinate e2(2,2);
    Coordinate e3(3,3);
    Coordinate e4(4,4);

    list.listInsert(0,e1);
    list.listInsert(1,e2);
    list.listInsert(2,e3);
    list.listInsert(3,e4);

    list.printList();
    cout<<list.listLocate(e3)<<endl;

    system("pause");
    return 0;
}

线性表之——链表篇

自我总结C++实现链表的思想在于用next指针把每一个节点类（结构体）串连起来，你可以想象一条链条…：

  1. 节点类的实现：

    链表中每一个节点有两大特征：存数据的DATA + next指针；所以除了头结点外的每一个节点的地址都必须从上一个节点那里获取，也就是必须通过上一个节点的next来指向下一个节点，以此方法来对节点的访问；另外还有一点需要特别注意的是，头结点是不存数据的！

    Node.h 文件的内容 上源码：

#ifndef NODE_H
#define NODE_H


#include <iostream>


using namespace std;

template <class T>
class Node
{
public:
    T data; //定义一个模板类的数据域;
    Node *next; //定义一个指针域;
    void printNode(); //打印节点数据
};

template <class T>
void Node<T>::printNode()
{
    cout<< data <<endl;
}

#endif

  1. 用LinkList类将各节点串连起来，并实现对链表中节点的增、改、删、查的功能以及扩充的功能；

    LinkList.h 文件的内容如下：

#ifndef LINKLIST_H
#define  LINKLIST_H

#include "Node.h"
#include <string>
#include <iostream>

using namespace std;

//可参见顺序表的类声明
template <class T>
class LinkList
{

public:
    LinkList(); //链表在创建时可以从堆中去申请到一块空间所以不用赋初值;
    ~LinkList();
    void ClearList();
    bool ListEmpty();
    int ListLength();
    int LocateElement( Node<T> *pNode );
    bool PriorElement( Node<T> *pCurrentNode,Node<T> *pPreNode );
    bool NexitElement( Node<T> *pCurrentNode,Node<T> *pNextNode );
    void ListTraverse();
    bool ListInsertHead( Node<T> *pNode );
    bool ListInsertTail( Node<T> *pNode );
    bool ListInsert( int i,Node<T> *pNode );
    bool ListDelete( int i,Node<T> *pNode );
    bool GetElement( int i,Node<T> *pNode );
private:
    Node<T> *p_List; //定义头结点;
    int Length;
};

template <class T>
LinkList<T>::LinkList()
{
    p_List = new Node<T>; //重堆中申请一个内存空间给头结点；
    Length = 0;
    //p_List->data = NULL;
    p_List->next = NULL;
}

template <class T>
void LinkList<T>::ClearList()
{
//思想是从头结点开始，从上一个节点的next指针去找到下一个节点的地址再删除，直到最后一个节点；
    Node<T> *currentNode = p_List->next;
    while(currentNode != NULL) //用审犯人，交代下线的方式来理解就很容易;
    {
        Node<T> *temp = currentNode->next;
        delete currentNode;
        currentNode  = temp;
    }
    p_List->next = NULL;  //将头节点的next置空;
    Length = 0;
}

template <class T>
LinkList<T>::~LinkList()
{
    ClearList();
    delete p_List;
    p_List = NULL;
}

template <class T>
bool LinkList<T>::ListEmpty()
{
    if (Length == 0)
    {
        return true;
    }
    else
    {
        return false;
    }
}

template <class T>
int LinkList<T>::ListLength()
{
    return Length;
}

template <class T>
//先定义插入操作后，后面方法定义更容易理解;
bool LinkList<T>::ListInsertHead( Node<T> *pNode )
{
    Node<T> *temp = p_List->next; //从头节点的下一个节点的地址 //首先保存头结点的指针域;
    Node<T> *newNode = new Node<T>; //创建一个新节点;
    if (newNode == NULL) //判断申请内存是否失败；
    {
        return false;
    }
    newNode->data = pNode->data;  //将传入的节点数据传给新节点
    newNode->next = temp; //把新节点作为下一个节点
    p_List->next = newNode;  //这两步为连接操作;
    Length++;
    return true;
}

template <class T>
bool LinkList<T>::ListInsertTail( Node<T> *pNode )
{
    Node<T>* currentNode = p_List; //从头节点开始访问；
    while(currentNode->next != NULL)
    {
        currentNode = currentNode->next;
    }
    Node<T> *newNode = new Node<T>;
    if (newNode == NULL)
    {
        return false;
    }
    newNode->data = pNode->data; //将传入的节点的数据保存到新节点
    //currentNode->next = newNode;
    newNode->next = NULL; //将新节点作为最后一个节点；
    currentNode->next = newNode; //连接操作
    Length++;
    return true;
}

template <class T>
bool LinkList<T>::ListInsert( int i,Node<T> *pNode )
{
    if (i<0 || i>Length)
    {
        return false;
    }
    else
    {
        Node<T> *currentNode = p_List; //获取头结点，以便于遍历寻找下一个节点;
        for (int k=0;k<i;k++)
        {
            currentNode = currentNode->next;
        }
        Node<T> *newNode = new Node<T>;
        if (newNode == NULL)
        {
            return false;
        }
        newNode->data = pNode->data;
        newNode->next = currentNode->next;//使之前的下一个元素与新的元素相连;
        currentNode->next = newNode;
        Length++;
        return true;
    }
}

template <class T>
bool LinkList<T>::ListDelete( int i,Node<T> *pNode )
{
    if(i<0 || i>=Length)
    {
        return false;
    }
    Node<T> *currentNode = p_List;
    Node<T> *currentNodeBefore = NULL;
    for (int k=0;k<=i;k++)
    {
        currentNodeBefore = currentNode; //将当前节点的首地址保存下来，;
        currentNode = currentNode->next;        //保持与之前元素的连接;
    }
    currentNodeBefore->next = currentNode->next; //删除i所示元素的下一个元素，即目标元素；
    pNode->data = currentNode->data;
    delete currentNode;
    currentNode = NULL;
    Length--;
    return true;
}

template <class T>
bool LinkList<T>::GetElement( int i,Node<T> *pNode )
{
//获取指定位置的元素，将其传出来；
    if (i<0 || i>Length)
    {
        return false;
    }
    Node<T> * currentNode = p_List;
    for (int k=0;k<=i;k++)
    {
        currentNode = currentNode->next;
    }
    pNode->data = currentNode->data;
    return true;
}

template <class T>
int LinkList<T>::LocateElement( Node<T> *pNode )
{
    Node<T> *currentNode = p_List;
    int count = 0; //头结点不存数据，应从头结点的next元素开始算;
    while(currentNode != NULL)
    {
        currentNode = currentNode->next;
        //改注释的代码块为下面的通讯录Damon的，执行通讯录时请将下面的if语句替换掉
        //if (pNode->data == currentNode->data)
        //{
        //  return count;
        //}

        if (pNode->data == currentNode->data)
        {
            return count;
        }
        else
        {
            return -1;
        }
        count++;
    }
    //cout<< "该链表中没有该元素！"<<endl;
    //return -1;
}

template <class T>
bool LinkList<T>::PriorElement( Node<T> *pCurrentNode,Node<T> *pPreNode )
{
    Node<T> *currentNode = p_List;
    Node<T> *tempNode = NULL;
    while(currentNode =! NULL)
    {
        tempNode = currentNode;
        currentNode = currentNode->next;
        if (currentNode->data == pCurrentNode->data)
        {
            if (tempNode == p_List)
            {
                return false;
            } 
            else
            {
                pPreNode->data = tempNode->data;
                return true;
            }
        }
    }
}

template <class T>
bool LinkList<T>::NexitElement( Node<T> *pCurrentNode,Node<T> *pNextNode )
{
    Node<T> *currentNode = p_List;
    while(currentNode =! NULL)
    {
        currentNode = currentNode->next;
        if (currentNode.data == pCurrentNode->data)
        {
            if (currentNode->next == NULL)
            {
                return false;
            } 
            else
            {
                pNextNode->data = currentNode->next->data; //头结点不算元素;
                return true;
            }
        }
    }
}

template <class T>
void LinkList<T>::ListTraverse()
{
    if ( Length == 0)
    {
        cout<<"error"<<endl;
        exit(1);
    }
    Node<T> *currentNode = p_List;
    while(currentNode->next != NULL)
    {
        currentNode = currentNode->next;
        currentNode->printNode();
    }
}

#endif

  1. 用刚才实现的链表打造一个 通讯录 ；

    • 首先得写一个people类用于存每个人的信息；
    • 利用链表的数据结构将people类的数据组织起来，以便于增改删查功能；

i. 写出people类，people.h 的源码如下：

#ifndef PERSON_H
#define PERSON_H

#include <string>
#include <ostream>

using namespace std;


class Person
{
    friend ostream &operator<<(ostream &out,Person &person); //声明友元函数用于重载输出运算符；
public:
    string name; //用于存联系人名字；
    string phone; //用于存联系人电话；
    //int age;
    Person &operator=(Person &person); //重载比较运算符
    bool operator==(Person &person); //重载==运算符
};

ostream &operator<<(ostream &out,Person &person)
{
    out << person.name << "-------" << person.phone <<endl;
    return out;
}

Person & Person::operator=( Person &person )
{
    this->name = person.name;
    //this->age = person.age;
    this->phone = person.phone;
    return *this;
}

bool Person::operator==( Person &person )
{
    if (this->name == person.name && this->phone == person.phone)
    {
        return true;
    } 
    return false;
}

#endif

j. LinkList.cpp 文件的内容如下：

#include "LinkList.h"
#include "Person.h"
//#include "Node.h"
#include <iostream>

using namespace std;


int menu()
{
    cout<<endl;
    cout<<"---------功能表---------"<<endl;
    cout<<"------1.新建联系人------"<<endl;
    cout<<"------2.删除联系人------"<<endl;
    cout<<"------3.查询联系人------"<<endl;
    cout<<"------4.浏览联系人------"<<endl;
    cout<<"------5.退出通讯录------"<<endl;
    cout<<endl;
    int n = 0;
    cout<< "请选择功能:" <<endl;
    cin>> n ;
    if (n<0 || n>5)
    {
        cout<< "选择功能未开发......请重选！"<<endl;
        cout<< "请选择功能:" <<endl;
        menu();
    }
    return n;
}

void createPerson(LinkList<Person> *list) 
{
    Node<Person> node;
    Person person;
    cout<<"请输入新建联系人信息："<<endl;
    cout<<"姓名： ";
    cin>>person.name;
    cout<<"电话： ";
    cin>>person.phone;
    node.data = person;
    list->ListInsertTail(&node);
}

void deletePerson(LinkList<Person> *list) 
{
    Node<Person> node1,node2;
    Person person;
    cout<<"请输入需要删除的联系人信息："<<endl;
    cout<<"姓名： ";
    cin>>person.name;
    node1.data = person;
    int locate_i;
    locate_i = list->LocateElement(&node1);
    if (locate_i != -1)
    {
        list->ListDelete(locate_i,&node2);
        cout<<"删除成功！"<<endl;
        return ;
    }
    cout<<"您的通讯录里没有这个人，请重选功能！"<<endl;
    return ;
}

void selectPerson( LinkList<Person>* list ) 
{
    Node<Person> node1,node2;
    Person person;
    cout<<"请输入所查联系人的信息："<<endl;
    cout<<"姓名： ";
    cin>>person.name;
    node1.data = person;
    int locate_i;
    locate_i = list->LocateElement(&node1);
    if (locate_i != -1)
    {
        list->GetElement(locate_i,&node2);
        cout<<"查询结果如下："<<endl;
        node2.printNode();
        return ;
    }
    else
    {
        cout<< "您的通讯录里没有该联系人！"<<endl;
        cout<<"请重选功能"<<endl;
        return ;
    }
}

void allPerson( LinkList<Person>* list ) 
{
    list->ListTraverse();
}

int main()
{
    LinkList<Person> list;
    int select = 0;
    while(select != 5)
    {
        select = menu();
        switch (select)
        {
        case 1:
            cout<< "用户指令--->>新建联系人："<<endl;
            createPerson(&list);
            cout<<"新建成功！"<<endl;
            break;
        case 2:
            cout<<"用户指令--->>删除联系人： "<<endl;
            deletePerson(&list);
            //cout<<"删除成功！"<<endl;
            break;
        case 3:
            cout<<"用户指令--->>查询联系人： "<<endl;
            selectPerson(&list);
            //cout<<"查询成功！"<<endl;
            break;
        case 4:
            cout<<"用户指令--->>浏览联系人： "<<endl;
            allPerson(&list);
            //cout<<"浏览成功！"<<endl;
        }
    }
    exit(1);

    system("pause");
    return 0;
}

一个通过链表来实现的简易通讯录就这样实现了，作为一名程
序猿来说，此时的心情是谈10个女朋友也无法比拟的。真是美
滋滋啊~~~~~

  • 第二夜：数据结构之——队列篇；

    队列：队列是一种特殊的线性表，特殊之处在于它只
    允许在表的前端（front）进行删除操作，而在表的后端（
    rear）进行插入操作，和栈一样，队列是一种操作受限制
    的线性表。
    简言之就是一种先进先出（FIFO）的数据模型；可以理解
    为一队人在买票，先来者站前面，先买好就先走，后来的
    站后面，从前往后买；排在最前面的称作队头，最后面的
    称为队尾！

    1. 这里直接实现了环形队列，CirQueue.h 的源码如下：
#ifndef CIRQUEUE_H
#define CIRQUEUE_H

#include <iostream>

using namespace std;

//const int CirQueueSize = 4;

template <class Datatype> //定义类模板；

class CirQueue
{
    public:
        CirQueue(int CirQueueSize); //构造函数
        virtual ~CirQueue();
        void ClearQueue(); //清除队列；
        void QueueTraverse(); //遍历队列；
        bool QueueEmpty(); //判空；
        bool QueueFull(); //判满；
        int QueueLength();
        bool EnQueue(Datatype x); //入队
        bool DeQueue(Datatype &x);//出队；
        Datatype GetQueue(); //获取队头不出队；
    private:
        int *p_Queue; //队列（数组）的指针
        int QueueSize; //容器（数组）的大小；
        int Length; //队列的长度；
        int Head; //队头
        int Teal; //队尾
};


//const int CirQueueSize = 4;

template <class Datatype>
CirQueue<Datatype>::CirQueue(int CirQueueSize)
{
    QueueSize = CirQueueSize;
    try
    {
        p_Queue = new Datatype[QueueSize]; //在堆区申请一个数组用作队列元素的容器；
    }

    catch(...)
    {
        delete []p_Queue;
        p_Queue = NULL;
        //cout<< "队列创建失败，请重试！" <<endl;
    }

    Head = Teal =QueueSize-1; //队列开始时队头与队尾指针都指在同一位置；
    Length = 0;
}

template <class Datatype>
CirQueue<Datatype>::~CirQueue()
{
    delete []p_Queue;
    p_Queue = NULL;
}

template <class Datatype>
void CirQueue<Datatype>::ClearQueue()
{
    Head = Teal =QueueSize-1; //使队头与队尾都指在同一位置
    Length = 0;
}

template <class Datatype>
bool CirQueue<Datatype>::QueueEmpty()
{
    if (Length == 0)
    {
        return true;
    }
    else
    {
        return false;
    }

}

template <class Datatype>
bool CirQueue<Datatype>::QueueFull()
{
    if (Length == QueueSize)
    {
        return true;
    } 
    else
    {
        return false;
    }
}

template <class Datatype>
int CirQueue<Datatype>::QueueLength()
{
    return Length;
}

template <class Datatype>
bool CirQueue<Datatype>::EnQueue(Datatype x)
{
    if (QueueFull()) //入队时首先要判满；
    {
        return false;
    } 
    else
    {
        p_Queue[Teal] = x; //在队尾位置放元素；
        Teal = (Teal+1)%QueueSize; //放完元素后队尾指针自动往后滑一个长度，
        记得要与队列长度取余作为新队尾，防止上溢；
        Length++;
        //cout<< "EnQueue Ok" <<endl;
        return true;
    }
}

template <class Datatype>
bool CirQueue<Datatype>::DeQueue(Datatype &x)
{
    //int temp = Head;
    if (QueueEmpty())
    {
        //cout<< "下溢" <<endl; 
        return false;
    }
    else
    {
        x = p_Queue[Head]; //将队头出队；
        Head = (Head+1)%QueueSize;
        Length--;
        //return p_Queue[temp];
        return true;
    }
}


template <class Datatype>
Datatype CirQueue<Datatype>::GetQueue()
{
    return p_Queue[Head];
}

template <class Datatype>
void CirQueue<Datatype>::QueueTraverse()
{
    if (QueueEmpty())
    {
        //throw "这是一个空队列";
        cout<< "这是一个空队列!" <<endl;
        //return false;
    } 
    else
    {
    //从队头开始往后访问遍历；
        for (int i = Head;i<Length+Head;i++)
        {
            cout<< p_Queue[i%QueueSize] <<endl;
            //cout<<"********************************"<<endl;
        }
    }
}

#endif

2.一下是CirQueue.cpp调试文件的源代码：

#include <iostream>
//#include <stdlib.h>
#include "CirQueue.h"
#include "CirQueue.cpp"

using namespace std;

int main()
{
    CirQueue<int> MyQueue(4);

    bool EnQueue_1_bool;
    EnQueue_1_bool = MyQueue.EnQueue(1);
    cout<<"EnQueue_1_bool: "<< EnQueue_1_bool <<endl;

    bool EnQueue_2_bool;
    EnQueue_2_bool = MyQueue.EnQueue(2);
    cout<<"EnQueue_2_bool: "<< EnQueue_2_bool <<endl;

    int MyQueue_head;
    MyQueue_head = MyQueue.GetQueue();
    cout<<"MyQueue_head: "<<MyQueue_head <<endl;

    int MyQueue_length;
    MyQueue_length = MyQueue.QueueLength();
    cout<<"MyQueue_length: "<< MyQueue_length <<endl;

    int x;
    MyQueue.DeQueue(x);
    cout<<"DeQueue: x = "<< x <<endl;

    int y;

    MyQueue.DeQueue(y);
    cout<<"DeQueue: y = "<< y <<endl;

    bool Empty_bool;
    Empty_bool = MyQueue.QueueEmpty();
    cout<<"Empty_bool: "<< Empty_bool <<endl;

    MyQueue.EnQueue(10);
    MyQueue.EnQueue(20);
    MyQueue.EnQueue(30);
    MyQueue.EnQueue(40);
    MyQueue.QueueTraverse();

    system("pause");
    return 0;
}

  • 第三夜：数据结构之——栈篇

    栈：栈是限定仅在表头（栈顶）进行插入和删除操作的线性表”栈“者,存储货物或供旅客住宿的地方,可引申为仓库、中转站，所以引入到计算机领域里，就是指数据暂时存储的地方，所以才有进栈、出栈的说法。

    栈的特点：后进先出（LIFO）这个很容易理解的~~先进电梯的人后出来，后进电梯的人先出来。

    栈其实很简单，只要掌握好top指针的技巧就很容易理解了，top指针就相当于桶里的一只小船，水涨船高，水降船降；

    1. 栈 的实现，一下是Mystack.h 文件的源码：
#ifndef MYSTACK_H
#define MYSTACK_H

template <class Datatype>
class Mystack
{
    public:
        Mystack(Datatype size);
        ~Mystack();
        bool stackEmpty();
        bool stackFull();
        bool push(Datatype x); //入栈；
        bool pop(Datatype &x); //出栈；
        void clearStack();
        int stackLength();
        void stackTraverse(bool isFromeButtom);
    private:
        Datatype *p_Buffer;//栈的入口
        int Size; //栈的大小
        int Top; //栈顶，在栈中极为重要；
};

template <class Datatype>
Mystack<Datatype>::Mystack( Datatype size )
{
    Size = size;
    Top = 0;
    p_Buffer = new Datatype[Size];//在堆区申请一个数组来实现栈
}

template <class Datatype>
Mystack<Datatype>::~Mystack()
{
    delete []p_Buffer; 
    p_Buffer = NULL;
}


template <class Datatype>
bool Mystack<Datatype>::stackEmpty()
{
    if (Top == 0) //栈顶可以实时的反应出栈的情况
    {
        return true;
    } 
    else
    {
        return false;
    }
}

template <class Datatype>
bool Mystack<Datatype>::stackFull()
{
    if (Top == Size)
    {
        return true;
    } 
    else
    {
        return false;
    }
}

template <class Datatype>
bool Mystack<Datatype>::push( Datatype x )
{
    if (!stackFull())
    {
        p_Buffer[Top] = x; //每入栈一个元素后top自动向上移动一个位置，以作为下一次入栈的栈顶指针；
        Top++;
        return true;
    } 
    else
    {
        return false;
    }

}

template <class Datatype>
bool Mystack<Datatype>::pop(Datatype &x)
{
    if (stackEmpty())
    {
        return false;
    } 
    else
    {
        Top--;
        x = p_Buffer[Top];//将栈顶指针下滑一位，指向出栈元素
    }
}

template <class Datatype>
void Mystack<Datatype>::clearStack()
{
    Top = 0;
}

template <class Datatype>
int Mystack<Datatype>::stackLength()
{
    return Top;
}

template <class Datatype>
void Mystack<Datatype>::stackTraverse(bool isFromeButtom)
{
    if (isFromeButtom)
    {
        for (int i=0;i<Top;i++)
        {
            cout<< p_Buffer[i] ;//<< ',';
        }
    } 
    else
    {
        for (int i=Top-1;i>=0;i--)
        {
            cout<< p_Buffer[i] ;//<< ',';
        }
    }
}

#endif
  1. 测试刚写的栈，Queue.cpp 的源码如下：
#include <iostream>
#include "Mystack.h"

using namespace std;


int main()
{
    Mystack<char> mystack(5);

    mystack.push('H');
    mystack.push('e');
    mystack.push('l');
    mystack.push('l');
    mystack.push('o');

    mystack.stackTraverse(true);

    cout<< endl;

    cout<< mystack.stackLength() <<endl;

    char x = 'x';
    cout<< mystack.pop(x) <<endl;

    cout<< mystack.stackLength() <<endl;

    cout<< mystack.stackEmpty() <<endl;

    mystack.clearStack();

    cout<< mystack.stackEmpty() <<endl;

    char y = 't';
    cout<< mystack.pop(x) <<endl;


    system("pause");
    return 0;
}
  1. 用栈实现十进制转二进制、八进制、十六进制；源码如下：
#include <iostream>
#include "Mystack.h"

using namespace std;

#define BINARY 2
#define OCTONARY 8
#define HEXADECIMAL 16

//用辗转相初法求模；


//template <class Datatype>
void to_binary(int n,int mod,Mystack<int> *p_b_stack)
{
    while (n != 0)
    {
        mod = n % BINARY;
        p_b_stack->push(mod);
        n = n / BINARY;
    }

    p_b_stack->stackTraverse(false);
    cout<<endl;
}

void to_octonary(int n,int mod,Mystack<int> *p_o_stack)
{
    while (n != 0)
    {
        mod = n % OCTONARY;
        p_o_stack->push(mod);
        n = n / OCTONARY;
    }

    p_o_stack->stackTraverse(false);
    cout<<endl;
}

void to_hexadecimal(int n,int mod,Mystack<int> *p_h_stack)
{
    while (n != 0)
    {
        mod = n % HEXADECIMAL;
        p_h_stack->push(mod);
        n = n / HEXADECIMAL;
    }
    char str[] = "0123456789ABCDEF";
    int i=0;
    while(!p_h_stack->stackEmpty())
    {
        p_h_stack->pop(i);
        cout<< str[i] ;
    }

    //p_e_stack->stackTraverse(false);
    cout<<endl;
}

int main()
{
    Mystack<int> *p_b_stack = new Mystack<int>(20);
    Mystack<int> *p_o_stack = new Mystack<int>(20);
    Mystack<int> *p_h_stack = new Mystack<int>(20);

    int n = 1;
    cin>>n;
    int mod = 0;

    to_binary(n,mod,p_b_stack);
    to_octonary(n,mod,p_o_stack);
    to_hexadecimal(n,mod,p_h_stack);

    delete p_b_stack;
    delete p_o_stack;
    delete p_h_stack;
    p_b_stack = NULL;
    p_o_stack = NULL;
    p_h_stack = NULL;

    system("pause");
    return 0;
}

  • 第四夜：数据结构之——树篇

    树：树是由根结点和若干颗子树构成的。树是由一个集合以及在该集合上定义的一种关系构成的。集合中的元素称为树的结点，所定义的关系称为父子关系。父子关系在树的结点之间建立了一个层次结构。在这种层次结构中有一个结点具有特殊的地位，这个结点称为该树的根结点，或称为树根。

    树的种类：

    无序树：树中任意节点的子结点之间没有顺序关系，这种树称为无序树,也称为自由树;

    有序树：树中任意节点的子结点之间有顺序关系，这种树
    称为有序树；

    二叉树：每个节点最多含有两个子树的树称为二叉树；

    完全二叉树

    满二叉树

    霍夫曼树：带权路径最短的二叉树称为哈夫曼树或最优二
    叉树；

下面我重点来看二叉树：

二叉树：二叉树在图论中是这样定义的：二叉树是一个连
通的无环图，并且每一个顶点的度不大于3。有根二叉树还要满
足根结点的度不大于2。有了根结点之后，每个顶点定义了唯一
的父结点，和最多2个子结点。

我主要总结了二叉树的数组实现和链表实现两种方式；

**注意**：学习二叉树我们的脑海中需要有父节点与左右孩子节点的思想
    1. 下面是二叉树的数组实现

//以数组元素为节点；

#ifndef TREE_H
#define TREE_H
#include <iostream>

using namespace std;

template <class T>
class Tree
{
public:
    Tree(int size,T *pRoot); //给定数的大小，以及根
    ~Tree();
    T *SerchNode(int nodeIndex); //搜寻节点
    bool AddNode(int nodeIndex,int derection,T *node);//添加节点；
    bool DeleteNode(int nodexIndex,T *node); //删除节点
    void TreeTreaverse();
private:
    T *p_Tree;
    int Size;
};

template <class T>
Tree<T>::Tree( int size,T *pRoot )
{
    Size = size;
    p_Tree = new T[Size]; //在堆区申请一个数组来实现二叉树
    for (int i=0;i<size;i++) //对每个节点初始化
    {
        p_Tree[i] = NULL;
    }
    p_Tree[0] = *pRoot; //定义根节点
}

template <class T>
Tree<T>::~Tree()
{
    delete []p_Tree;
    p_Tree = NULL;
}

template <class T>
T * Tree<T>::SerchNode( int nodeIndex )
{
    if (nodeIndex<0 || nodeIndex>Size)
    {
        return NULL;
    }
    if (NULL == p_Tree[nodeIndex])
    {
        return NULL;
    }
    return &p_Tree[nodeIndex];
}

//添加为左节点index = nodeIndex*2 + 1;右节点: index = nodeIdex*2 + 2;
template <class T>
bool Tree<T>::AddNode( int nodeIndex,int derection,T *node )
{
    if (nodeIndex<0 || nodeIndex>Size)
    {
        return false;
    }
    if (NULL == p_Tree[nodeIndex])
    {
        return false;
    }
    if (derection == 0)
    {
        if (nodeIndex*2 + 1>Size)
        {
            return false;
        }
        if (NULL != p_Tree[nodeIndex*2 + 1])
        {
            return false;
        }
        if ( nodeIndex*2 + 1 <= Size )
        {
            p_Tree[nodeIndex*2 + 1] = *node;
        }
    }
    if (derection == 1)
    {
        if (nodeIndex*2 + 2>Size)
        {
            return false;
        }
        if (NULL != p_Tree[nodeIndex*2 + 2])
        {
            return false;
        }
        if ( nodeIndex*2 + 2 <= Size )
        {
            p_Tree[nodeIndex*2 + 2] = *node;
        }
    }
    return true;
}

template <class T>
bool Tree<T>::DeleteNode( int nodeIndex,T *node )
{
    if (nodeIndex<0 || nodeIndex>Size)
    {
        return false;
    }
    if (NULL == p_Tree[nodeIndex])
    {
        return false;
    }
    *node = p_Tree[nodeIndex];
    p_Tree[nodeIndex] = NULL;
    return true;
}

template <class T>
void Tree<T>::TreeTreaverse()
{
    for (int k=0;k<Size;k++)
    {
        cout<< p_Tree[k] << " " <<endl;
    }
}


#endif

  • 下面是二叉树的链表实现：

    1. 首先先完成一个节点类的书写，主要存储节点索引，数据，左、右孩子节点的指针，父节点的指针；
      下面是Node.h 文件的源码：因为二叉树是递归定义的，其结点
      有左右子树之分，所以很多需要方法都需要用到递归函数，这
      些方法我们写在了Node类里。
#ifndef NODE_H
#define NODE_H
#include <iostream>

using namespace std;

template <class T>
class Node
{
public:
    Node();
    T data; //数据域;
    int index;
    Node<T> *pLchild; //左孩子节点指针；
    Node<T> *pRchild; //右孩子节点指针；
    Node<T> *pParent; //父节点;
    void DeleteNode();
    void PreorderTraversal(); //前序遍历
    void InorderTraversal(); //中序遍历
    void PostorderTraversal(); //后序遍历
    Node<T> *SearchNode(int nodeIndex); //寻找节点

};

template <class T>
Node<T>::Node()
{
    index = 0;
    data = NULL;
    pLchild = NULL;
    pRchild = NULL;
    pParent = NULL;
}

template <class T>
Node<T> * Node<T>::SearchNode( int nodeIndex )
{
    Node<T> *temp;
    if ( this->index == nodeIndex ) //如果所给节点为当前节点，便返回当前节点；
    {
        return this;
    }
    if (this->pLchild != NULL) //首先判断左孩子存不存在
    {
    //看看左孩子是否为所找；
        if (this->pLchild->index == nodeIndex)
        {
            return this->pLchild;
        }
        else //否则就调用递归查找
        {
            temp = this->pLchild->SearchNode(nodeIndex);
            if (temp != 0)
            {
                return temp;
            }
        }
    }
    //再判断右孩子存不存在
    if (this->pRchild != NULL)
    {
    //判断右孩子是否为所找
        if (this->pRchild->index == nodeIndex)
        {
            return this->pRchild;
        }
        //否则在调用递归查询
        else
        {
            temp = this->pRchild->SearchNode(nodeIndex);
            if (temp != 0)
            {
                return temp;
            }
        }

    }
    return NULL;
}

template <class T>
void Node<T>::DeleteNode()
{
    //判断左孩子是否为空，若不为空就调用递归删除
    if (this->pLchild != NULL)
    {
        this->pLchild->DeleteNode();
    }

    //判断左孩子是否为空，若不为空就调用递归删除
    if (this->pRchild != NULL)
    {
        this->pRchild->DeleteNode();
    }
    //判断该节点的父节点是否为空，因为空节点没有左右孩子
    if (this->pParent != NULL)
    {
        //判断该节点是否为父节点的左孩子，并删除
        if (this->pParent->pLchild == this)
        {
            this->pParent->pLchild = NULL;
        }
        //判断该节点是否为父节点的右孩子，并删除
        if (this->pParent->pRchild == this)
        {
            this->pParent->pRchild = NULL;
        }
    }
    delete this; //所有的子节点都删除完了，再删除自己
}

template <class T>
void Node<T>::PreorderTraversal()
{
//前序遍历，根-左-右
    cout<< this->index << "--->" << this->data <<endl;
    //若左孩子存在，调用递归进行前序遍历
    if (this->pLchild != NULL)
    {
        this->pLchild->PreorderTraversal();
    }
    //若右孩子存在，调用递归进行前序遍历
    if (this->pRchild != NULL)
    {
        this->pRchild->PreorderTraversal();
    }
}

template <class T>
void Node<T>::InorderTraversal()
{
//中序遍历，左-根-右
    if (this->pLchild != NULL)
    {
        this->pLchild->InorderTraversal();
    }
    cout<< this->index << "--->" << this->data <<endl;
    if (this->pRchild != NULL)
    {
        this->pRchild->InorderTraversal();
    }
}

template <class T>
void Node<T>::PostorderTraversal()
{
//后序遍历，左-右-根
    if (this->pLchild != NULL)
    {
        this->pLchild->PostorderTraversal();
    }
    if (this->pRchild != NULL)
    {
        this->pRchild->PostorderTraversal();
    }
    cout<< this->index << "--->" << this->data <<endl;
}



#endif

再将每个节点按照二叉树的关系联合起来，所以用一个LinkListTree类进行整合；LinkListTree.h 的源码如下：

#ifndef TREE_H
#define TREE_H
#include "Node.h"
#include <iostream>

using namespace std;

template <class T>
class LinkListTree
{
public:
    LinkListTree();
    ~LinkListTree();
    Node<T> *SearchNode(int nodeIndex);
    bool AddNode(int nodeIndex,int derection,Node<T> *pNode);
    bool DeleteNode(int nodexIndex,Node<T> *pNode);
    void PreorderTraversal();
    void InorderTraversal();
    void PostorderTraversal();

private:
    Node<T> *pRoot;
};

template <class T>
LinkListTree<T>::LinkListTree()
{
    pRoot = new Node<T>;
}

template <class T>
LinkListTree<T>::~LinkListTree()
{
    pRoot->DeleteNode();
    //delete pRoot;
    //pRoot = NULL;
}

template <class T>
Node<T> * LinkListTree<T>::SearchNode( int nodeIndex )
{
    return pRoot->SearchNode(nodeIndex);
}

template <class T>
bool LinkListTree<T>::AddNode( int nodeIndex,int derection,Node<T> *pNode )
{
    Node<T> *temp = SearchNode(nodeIndex);
    if (temp == NULL)
    {
        return false;
    }
    Node<T> *newNode = new Node<T>;
    if (newNode == NULL)
    {
        return false;
    }
    newNode->index = pNode->index;
    newNode->data = pNode->data;
    newNode->pParent = temp;
    if (derection == 0)
    {
        temp->pLchild = newNode;
    }
    if (derection == 1)
    {
        temp->pRchild = newNode;
    }
    return true;
}

template <class T>
bool LinkListTree<T>::DeleteNode( int nodeIndex,Node<T> *pNode )
{
    Node<T> *temp = SearchNode(nodeIndex);
    if (temp == NULL)
    {
        return false;
    }
    if (pNode != NULL)
    {
        pNode->data = temp->data;
    }
    temp->DeleteNode();
    return true;
}

template <class T>
void LinkListTree<T>::PreorderTraversal()
{
    pRoot->PreorderTraversal();
}

template <class T>
void LinkListTree<T>::InorderTraversal()
{
    pRoot->InorderTraversal();
}

template <class T>
void LinkListTree<T>::PostorderTraversal()
{
    pRoot->PostorderTraversal();
}



#endif

  • 第五夜：数据结构之——图篇

    图：数据元素间的关系是任意的。其他数据结构(如树、线性表等)都有明确的条件限制，而图形结构中任意两个数据元素间均可相关联。常用来研究生产流程、施工计划、各种网络建设等问题。

    1 理解图的两大存储结构
    1-1 邻接矩阵
    1-2 邻接表
    注意：邻接表中，指针数组里的每一个指针都是一个单链表的头指针
    注意：单链表里每个节点里存储的是图中每条边的信息。

    2 理解图的遍历算法
    2-1 深度优先遍历
    2-2 宽度优先遍历
    注意：又叫广度优先算法，需要一个队列

    3 图的最小代价生成树算法
    3-1 普里姆算法 。
    3-2 克鲁斯卡尔算法
    注意：克鲁斯卡尔的时间复杂度

下面我将总结由顶点数组(存节点)与邻接矩阵(存弧或边的相关
信息)构成的图;

  1. 首先写出构成图的节点Node类，Node.h 的源码如下：
#ifndef NODE_H
#define NODE_H

template<class T>
class Node
{
public:
    Node(T data = 0);
    T cData; //存数据
    bool bIsVisited; //节点的访问属性;
};

template<class T>
Node<T>::Node( T data )
{
    cData = data;
    bIsVisited = false;
}

#endif
  1. 由Node 节点构成边，所以写一个edge类，edge.h 的源码如下：
#ifndef EDGE_H
#define EDGE_H

class Edge
{
public:
    Edge(int nodeIndexA = 0,int nodeIndexB = 0,int weightValue = 0);
    int NodeIndexA; //节点A
    int NodeIndexB; //节点B
    int Weightvalue; //边的权值
    bool bSelected; //边的访问属性
};

Edge::Edge( int nodeIndexA /*= 0*/,int nodeIndexB /*= 0*/,int weightValue /*= 0*/ )
{
    NodeIndexA = nodeIndexA;
    NodeIndexB = nodeIndexB;
    Weightvalue = weightValue;
    bSelected = false;
}


#endif
  1. 由边构成图形，所以写一个CMap类，用于整合edge形成图，cMap.h 的源码如下：
#ifndef CMAP_H
#define CMAP_H
/*
   Map 由顶点数组(存节点) 与 邻接矩阵(存弧或边的相关信息)构成;
*/
#include "Node.h"
#include "Edge.h"
#include <vector>
#include <iostream>

using namespace std;


template <class T>
class CMap
{
public:
    CMap(int capacity);
    ~CMap();
    bool addNode(Node<T> *pNode);
    void resetNode();
    bool setValueToMatrixForDirectedGraph(int row,int col,int val = 1);
    bool setValueToMatrixForUndirectedGraph(int row,int col,int val = 1);

    void printMatrix();

    void depthFirstTraverse(int nodeIndex); //深度优先遍历;
    void breadthFirstTraverse(int nodeIndex); //广度优先遍历;

    void primTree(int nodeIndex); //普利姆生成树算法;

private:
    bool getValueFromeMatrix(int row,int col,int &val); //从函数中获取权值;
    void breadthFirstTraverseImpl(vector<int> preVec); //广度优先遍历实现函数;

    int getMinEdge(vector<Edge> edgeVec);

private:
    int Capacity;
    int NodeCount;
    Node<T> *NodeArray;  //存放节点（顶点）的数组;
    int *pMatrix;    //存放弧关系信息的邻接矩阵;

    Edge *pEdge;
};

template <class T>
CMap<T>::CMap( int capacity )
{
    Capacity = capacity;
    NodeCount = 0;
    NodeArray = new Node<T>[Capacity];
    pMatrix = new int[Capacity*Capacity];
    for (int i=0;i<Capacity*Capacity;i++)
    {
        pMatrix[i] = NULL;
    }

    pEdge = new Edge[Capacity-1];    //用于存放最小生成树中的所有边;
}

template <class T>
CMap<T>::~CMap()
{
    delete []NodeArray;
    NodeArray = NULL;
    delete []pMatrix;
    pMatrix = NULL;

    delete []Edge;
    pEdge = NULL;
}

template <class T>
bool CMap<T>::addNode( Node<T> *pNode )
{
    if (pNode == NULL)
    {
        return false;
    }
    NodeArray[NodeCount].cData = pNode->cData;
    NodeCount++;
    return true;
}

template <class T>
void CMap<T>::resetNode()
{
    for (int i=0;i<NodeCount;i++)
    {
        NodeArray[i].bIsVisited = false;
    }
}

template <class T>
bool CMap<T>::setValueToMatrixForDirectedGraph( int row,int col,int val /*= 1*/ )
{
    if (row>=0 && row<Capacity && col>=0 && col<Capacity)
    {
        pMatrix[row*Capacity + col] = val;
        return true;
    }
    return false;
}

template <class T>
bool CMap<T>::setValueToMatrixForUndirectedGraph( int row,int col,int val /*= 1*/ )
{
    if (row>=0 && row<Capacity && col>=0 && col<Capacity)
    {
        pMatrix[row*Capacity + col] = val;
        pMatrix[col*Capacity + row] = val;
        return true;
    }
    return false;
}

template <class T>
bool CMap<T>::getValueFromeMatrix( int row,int col,int &val )
{
    if (row>=0 && row<Capacity && col>=0 && col<Capacity)
    {
        val = pMatrix[row*Capacity + col];
        return true;
    }
    return false;
}

template <class T>
void CMap<T>::printMatrix()
{
    for (int i=0;i<Capacity;i++)
    {
        for (int j=0;j<Capacity;j++)
        {
            cout<< pMatrix[i*Capacity + j] <<' ';
        }
        cout<<endl;
    }

}

template <class T>
void CMap<T>::depthFirstTraverse( int nodeIndex )
{
    int val = 0;
    cout<< NodeArray[nodeIndex].cData <<' ';
    NodeArray[nodeIndex].bIsVisited = true;
    for (int i=0;i<Capacity;i++)
    {
        getValueFromeMatrix(nodeIndex,i,val);
        if (val == 1)
        {
            if (NodeArray[i].bIsVisited)
            {
                continue;
            }
            else
            {
                depthFirstTraverse(i);
            }
        }
        else
        {
            continue;
        }
    }

}

template <class T>
void CMap<T>::breadthFirstTraverse( int nodeIndex )
{
    cout<< NodeArray[nodeIndex].cData <<' ';
    NodeArray[nodeIndex].bIsVisited = true;

    vector<int> curVec;
    curVec.push_back(nodeIndex);
    breadthFirstTraverseImpl( curVec );
}

template <class T>
void CMap<T>::breadthFirstTraverseImpl( vector<int> preVec )
{
    int value = 0;
    vector<int> curVec;

    for (int j=0;j<(int)preVec.size();j++)
    {
        for (int i=0;i<Capacity;i++)
        {
            getValueFromeMatrix(preVec[j],i,value);
            if (value != 0)
            {
                if (NodeArray[i].bIsVisited)
                {
                    continue;
                } 
                else
                {
                    cout<<NodeArray[i].cData<<' ';
                    NodeArray[i].bIsVisited = true;

                    curVec.push_back(i);
                }
            }
        }
    }
    if (curVec.size() != 0)
    {
        breadthFirstTraverseImpl(curVec);
    }
    else
    {
        return;
    }
}

template <class T>
int CMap<T>::getMinEdge( vector<Edge> edgeVec )
{
    int minWeight = 0;
    int edgeIndex = 0;

    int i = 0;

    for (;i<(int)edgeVec.size();i++)
    {
        if (!edgeVec[i].bSelected)
        {
            minWeight = edgeVec[i].Weightvalue;
            edgeIndex = i;
            //cout<<"aaaa"<<edgeIndex<<endl;
            break;
        }
    }
    if (edgeIndex = 0)
    {
        return -1;
    }
    for (;i<(int)edgeVec.size();i++)
    {
        if (!edgeVec[i].bSelected)
        {
            if (minWeight>edgeVec[i].Weightvalue)
            {
                minWeight = edgeVec[i].Weightvalue;
                edgeIndex = i;
            }
        }
    }
    return edgeIndex;
}

//普利姆生成树算法;
template <class T>
void CMap<T>::primTree( int nodeIndex )
{
    int value = 0; //存放边的权值;
    int edgeCount = 0;
    vector<int> nodeVec; //存放点的(索引)集合;
    vector<Edge> edgeVec; //存放边的集合;
    nodeVec.push_back(nodeIndex);

    cout<< NodeArray[nodeIndex].cData <<endl;

    while(edgeCount < Capacity-1)
    {
        int temp = nodeVec.back();

        for (int i=0;i<Capacity;i++)
        {
            getValueFromeMatrix(temp,i,value);
            //cout<<"value:"<<value<<endl;
            if (value != 0)
            {
                //cout<<"test"<<endl;
                if (NodeArray[i].bIsVisited)
                {
                    continue;
                }
                else
                {
                    Edge edge(temp,i,value);//生成一个边对象;
                    edgeVec.push_back(edge);
                }
            }
        }
        //上一个for循环后获得了所有顶点的有关边，存到了edge数组里;
        //接下来从可选边集合中找出权值最小的边，添加到最小边数组中;
        int edgeIndex = getMinEdge(edgeVec);
        //cout<<"edgeIndex:"<<edgeIndex<<endl;
        edgeVec[edgeIndex].bSelected = true;

        pEdge[edgeCount] = edgeVec[edgeIndex];
        cout<<edgeVec[edgeIndex].NodeIndexA<<"---"<<edgeVec[edgeIndex].Weightvalue<<"---";
        cout<<edgeVec[edgeIndex].NodeIndexB<<endl;
        edgeCount++;

        int nextNodeIndex = edgeVec[edgeIndex].NodeIndexB;//获得与该边相连接的下一个节点索引;

        nodeVec.push_back(nextNodeIndex);//将该索引添加到存放生成树的节点的数组中，以便下次遍历;
        NodeArray[nextNodeIndex].bIsVisited = true;
        cout<<NodeArray[nextNodeIndex].cData<<endl;
    }

}


#endif

写在后面

以上便是一个小白十天学习数据结构的基本所获，在这十天中
有曾撞了无数次墙，debug了无数次，有时调Bug调到绝望，也
曾想过放弃；当然整个过程也充满了惊喜，一边是对知识和技
巧的惊，一边是对获得之后的喜，可谓是收获了满满的成就感
，最终还是坚持到了图篇！

另外，特别值得一提的是，我第一次写了一篇真正属于自己的
学习总结，还一不小心就写了这么长！在这里小小的鼓励一下
自己。。。。。。当然我更希望各位朋友多多指教，有不对的
地方还望多多包容与纠正~~感激不尽！

最后，我还想说的是，感谢慕课网以及里面授教的james_yuan老师，james老师教的的真的是一级棒，不经思路清晰，更重要的是细微入至，可谓是手把手教学啊！文中的绝大部分代码都是我跟着james老师学习之后的成果；再次给大家推荐james老师在慕课网的数据结构课程，真乃良心课程~~~

希望本文章能给和我一样不甘平凡的人带来一丝丝的帮助，那将是我的万分荣幸！

附：慕课网James老师课程：[1]https://www.imooc.com/course/list?c=cplusplus

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

Data Structure

数据结构

数据结构C实现

数据结构——小白入门篇 的相关文章

  • 远程调试(Remote Debugging)

    当运行的程序出现问题时 我们通常通过调试来追踪和定位问题 但是 当运行错误的机器上没有调试工具 我们就需要实现远程调试 简单地说 就是要调试的程序和调试器不在一台机器上 移动端web调试 alert虽然是个土方法 但也是万能的 不过这样会中

  • Javascript与CSS在IE和Firefox中的误区及区别

    Javascript中的常见问题 1 集合类对象问题 现有代码中许多集合类对象取用时使用 IE 能接受 Firefox 不能 解决方法 改用 作为下标运算 如 document forms formName 改为 Js代码 document

  • Vm配置虚拟网络信息&配置虚拟机防火墙&取消软件安装限制&解决问题Temporary failure in name resolution

    目录 配置环境 一 前置知识 1 NAT模式 用的比较多 2 桥接模式 3 仅主机模式 二 修改虚拟网卡信息 1 首先我们可以看到我们这里有两张网卡 问题一 你们可以想一下假如我没有桥接到我的真实可以上网的网卡上会怎么样 这种错误我之前犯过

  • Google敦促更快普及VP9视频压缩技术

    转自 http www cnetnews com cn 2013 0516 2159618 shtml CNET科技资讯网 05月16日 国际报道 计算机行业才谈及VP8解编码技术 Google就希望人们接受它的VP9技术了 Google的

随机推荐

  • DES 密钥生成 加密解密

    import java security InvalidKeyException import java security NoSuchAlgorithmException import java security SecureRandom

  • E1,T1, PRI, Trunk

    E1 T1 PRI Trunk 北美的24路脉码调制PCM简称T1 速率是1 544Mbit s 欧洲的30路脉码调制PCM简称E1 速率是2 048Mbit s 我国采用的是欧洲的E1标准 E1的一个时分复用帧 其长度T 125us 共划

  • read_csv文件读写参数详解————

    python pandas IO tools 之csv文件读写 英文原文 pandas IO tools 读取csv文件 pd read csv 写入csv文件 pd to csv pandas还可以读取一下文件 read csv read

  • .NET诞生20周年 .NET 7有什么新东西？

    首个预览版已发布 NET 7 有什么新东西 随着第一个预览版发布 NET 7 渐渐浮出水面 NET 高级项目经理 Jeremy Likness 在官方博客中介绍了 NET 7 的主要发展方向 俺整理给大伙做一下介绍 NET 7 建立在 NE

  • 实训二十二：交换机标准 ACL 配置

    一 实验目的 1 了解什么是标准的 ACl 2 了解标准 ACL 不同的实现方法 二 应用环境 1 ACL Access Control Lists 是交换机实现的一种数据包过滤机制 通过允许或拒绝特定的数据包进出网络 交换机可以对网络访问

  • Uoj 33 树上GCD (树分治)

    include

  • RabbitMQ：Queue的介绍和使用

    1 声明 当前内容用于本人学习和使用当前的Queue 当前内容为RabbitMQ中对Queue的介绍 当前内容来源 RabbitMQ中的Queue 2 Queue的官方介绍 首先先分析以下前面的Queue的使用 其实这个东西就是一个队列 一

  • Qt项目中头文件无法找到的几个解决办法

    项目场景 在新建项目中引用头文件 问题描述 头文件无法找到 系统提示错误 file not found 原因分析 可能是头文件写错 也可能是路径有问题 解决方案 三种解决方法 1 检查头文件是否写错 注意新旧版本的差异 2 检查路径是否为全

  • Windows下Python加载VLC的方法

    从网上看到一篇文章 Python 流媒体播放器 基于VLC 其中提到windows下开发VLC需要首先安装VLC 否则就需要设置环境变量PYTHON VLC MODULE PATH 但是我尝试了一下 没有成功 但是 这篇文章给了我一个思路

  • 剑指 Offer 25. 合并两个排序的链表

    题目链接 25 合并两个排序的链表 思路分析 利用归并排序的归并思想 Definition for singly linked list struct ListNode int val ListNode next ListNode int

  • 2021中国WMS市场发展趋势和特点

    仓储行业经历了30多年的发展 正在由手工仓向数字仓 智能仓转变 而在这个过程中 作为指挥硬件设备的 大脑 WMS起着不可或缺的作用 WMS系统通过数字化仓库作业过程管控 借助条码化和智能化技术手段 实现仓库作业条码化 作业过程透明化 库存管

  • 【满分】【华为OD机试真题2023 JS】红黑图

    华为OD机试真题 2023年度机试题库全覆盖 刷题指南点这里 红黑图 知识点枚举 时间限制 1s 空间限制 256MB 限定语言 不限 题目描述 众所周知红黑树是一种平衡树 它最突出的特性就是不能有两个相邻的红色节点 那我们定义一个红黑图

  • shardingsphere引发 java.lang.String cannot be cast to java.lang.Integer异常

    错误描述 mysql数据库查询sql在数据库连接工具中可以正常运行 在加入了shardingsphere的jar包的项目中抛如下异常 java lang ClassCastException java lang String cannot

  • shell脚本循环传值_Shell 脚本的循环控制(for/while/until)

    熟悉其他高级语言的伙伴们肯定了解循环控制语法是编程中非常基础的内容 今天就介绍Shell 中设计循环控制的语法 for while until 等内容 for 命令 for 命令是最简单的循环控制语句 它的格式为 for var in li

  • SyntaxError: Cannot use import statement outside a module

    Node 生态包含两个不同的模块系统 ESM ECMAScript 模块 和 CommonJS 两个模块系统彼此不兼容 其是 SyntaxError 无法在模块外部使用 import 语句 错误 错误 SyntaxError 无法在模块外部

  • C++ 好用的格式化库--fmt

    背景 fmt 库是一个开源的 C 格式化库 它提供了一种简洁 安全和高效的方式来进行字符串格式化 该库的设计目标是提供与 Python 的字符串格式化语法类似的功能 同时保持 C 的类型安全性和性能 下载与安装 官网下载 fmt 官网地址

  • springboot+jsp教育机构OA系统(源码免费获取+论文+答辩PPT)

    技术架构 springboot mybatis springmvc jsp mysql 功能模块 整个系统分为三种角色 1 系统管理员 2 上级角色 3 普通教师 其中系统管理员需要的功能 部门人员管理功能 档案信息的添加 工作管理功能 上

  • python爬虫案例-跳过百度验证，接口调用实现百度搜索功能

    需求背景 我们有自己的平台 但是希望在我们的平台上面想要实现一个百度搜索的接口 输入想要搜索的内容 模拟百度搜索 将返回的内容再展现在我们自己的平台中 提供给用户查看 coding utf8 import hashlib import ra

  • QT自定义类型作为槽函数的参数

    QT自定义类型作为槽函数的参数 正常情况下信号与槽之间只能传递通用数据类型 如 int 像QVector

  • 数据结构——小白入门篇

    数据结构 小白入门篇 浅谈学习心得 我为什么想要学数据结构 在计算机界有这样一个万能公式 数据结构 算法 程序 在如今这计算机引领风骚的时代 不学数据结构 你凭什么想要做时代的弄潮儿 所以我毅然决然的提前自学了数据结构 学习数据结构前的我是

热门标签