C/C++ 数据结构与算法

Cypress 2020-03-04

  • 线性表（Linear List）
    • 顺序存储结构
      • 顺序表（Sequence List）
      • 顺序栈（Sequence Stack）
      • 循环队列（Circular Queue）
    • 链式存储结构
      • 单链表（Singly Linked List）
      • 双链表（Doubly Linked List）
      • 循环链表（Circular Linked List）
      • 链栈（Linked Stack）
      • 链队列（Linked Queue）
#ifndef _H_LINEARLIST
#define _H_LINEARLIST

#include <iostream>
#include <stdexcept>
using namespace std;

// 线性表头文件（Linear List header file）
// 导入各种数据结构头文件

// 线性表的顺序存储
#include "SequenceList.h"        // 顺序表
#include "SequenceStack.h"        // 顺序栈
#include "CircularQueue.h"        // 循环队列
// 线性表的链式存储
#include "SinglyLinkedLIst.h"    // 单链表
#include "LinkedStack.h"        // 链栈
#include "LinkedQueue.h"        // 链队列

#endif

LinearList.h

#ifndef _H_SEQUENCELIST
#define _H_SEQUENCELIST

// 顺序表定义头文件（Sequence List）

namespace SequenceList 
{
    // SqList，顺序表类，成员有存储MAXSIZE个T类型数据的数组
    template <typename T, size_t MAXSIZE>
    class SqList 
    {
    private:
        T *data;
        size_t length;
        size_t size;
    public:
        // 初始化SqList
        SqList() 
        {
            this->size = MAXSIZE;
            this->data = new T[this->size]; 
            this->length = 0; 
        }
        // 析构化SqList
        ~SqList() { free(this->data); }
        // 是否为空
        bool Empty() const { return this->length == 0; }
        // 是否已满
        bool Full() const { return this->length == this->size; }
        // 返回长度
        size_t Length() const { return this->length; }
        // 返回大小
        size_t Size() { return this->size; }
        // 清除顺序表
        void Clear() 
        { 
            free(this->data); 
            this->size = MAXSIZE;
            this->data = new T[this->size]; 
            this->length = 0; 
        }
        // 获得index上的数据
        T GetElem(const size_t &index)
        {
            if (this->Empty())
            {
                throw out_of_range("SqList<T>: List is empty!\n");
            }
            else if (index <= 0 || index > this->length)
            {
                throw out_of_range("SqList<T>: Index out of range!\n");
            }
            else
            {
                return this->data[index-1];
            }
        }
        // 返回elem在SqList中的索引，如果找不到，返回0
        size_t LocateElem(const T &elem)
        {
            size_t index = 1;
            for (int i = 0; i < this->length; ++i, ++index)
            {
                if (this->data[i] == elem)
                {
                    return index;
                }
            }
            return 0;
        }
        // 在index位置上插入元素elem，所有index之后的元素向后移动一位
        void InsertElem(const size_t &index, const T &elem)
        {
            if (this->Full())
            {
                throw out_of_range("SqList<T>: List is full!\n");
            }
            else if (index <= 0 || index > this->length + 1)
            {
                throw out_of_range("SqList<T>: Index out of range!\n");
            }
            else
            {
                int i;
                for (i = this->length; i > index-1; --i)
                {
                    this->data[i] = this->data[i-1];
                }
                this->data[i] = elem;
                ++this->length;
            }
        }
        // 删除index上的元素elem，所有index之后的元素向前一位
        void DeleteElem(const size_t &index)
        {
            if (this->Empty())
            {
                throw out_of_range("SqList<T>: List is empty!\n");
            }
            else if (index <= 0 || index > this->length)
            {
                throw out_of_range("SqList<T>: Index out of range!\n");
            }
            else
            {
                for (int i = index-1; i < this->length - 1; ++i)
                {
                    this->data[i] = this->data[i+1];
                }
                --this->length;
            }
        }
        // 扩大顺序表，size += extra
        void Expand(size_t extra)
        {
            if (extra != 0)
            {
                T *tmp = this->data;
                this->data = new T[this->size + extra];
                // memcpy(destination, source, size)
                memcpy(this->data, tmp, this->length * sizeof(T));
                free(tmp);
                this->size += extra;
            }
        }
        // 打印SqList
        friend ostream &operator<<(ostream &os, const SqList &sql)
        {
            if (sql.Empty()) 
            {
                os << "SqList<T>[0]: {}" << endl;
            }
            else
            {
                os << "SqList<T>[" << sql.length << ", " << sql.size << "]: {";
                for (int i = 0; i < sql.length; ++i)
                {
                    os << sql.data[i] << ", ";
                }
                os << "\b\b}" << endl;
            }
            return os;
        }
    };
}


#endif

SequenceList.h

// SequenceStack.h
#ifndef _H_SEQUENCESTACK
#define _H_SEQUENCESTACK

// 顺序栈定义头文件（Sequence Stack）

namespace SequenceStack
{
    template <typename T, size_t MAXSIZE>
    class SqStack
    {
    private:
        T *data;            // 数组
        size_t topPtr;         // 栈顶指针
        size_t length;        // 长度
        size_t size;        // 大小
    public:
        // 初始化
        SqStack()
        {
            this->size = MAXSIZE;
            this->data = new T[this->size];
            this->length = 0;
            this->topPtr = -1;
        }
        // 析构化
        ~SqStack() { free(this->data); }
        // 是否为空
        bool Empty() const { return this->length == 0; };
        // 是否已满
        bool Full() const { return this->length == this->size; }
        // 返回长度
        size_t Length() const { return this->length; }
        // 返回大小
        size_t Size() const { return this->size; }
        // 清除顺序栈
        void Clear()
        {
            free(this->data);
            this->size = MAXSIZE;
            this->data = new T[this->size];
            this->length = 0;
            this->topPtr = -1;
        }
        // 获取栈顶指针数据
        T Top() 
        { 
            if (this->Empty())
            {
                throw out_of_range("SqStack<T>: stack is empty!\n");
            }
            else
            {
                return this->data[this->topPtr]; 
            }
        }
        // 压入栈
        void Push(const T &elem) 
        {
            if (this->Full())
            {
                throw out_of_range("SqStack<T>: stack is full!\n");
            }
            else
            {
                ++this->topPtr;
                this->data[this->topPtr] = elem;
                ++this->length;
            }
        }
        // 弹出栈
        void Pop()
        {
            if (this->Empty())
            {
                throw out_of_range("SqStack<T>: stack is empty!\n");
            }
            else
            {
                --this->topPtr;
                --this->length;
            }
        }
        // 扩大顺序栈，size += extra
        void Expand(const size_t &extra)
        {
            if (extra != 0)
            {
                T *tmp = this->data;
                this->data = new T[this->size + extra];
                // memcpy(destination, source, size)
                memcpy(this->data, tmp, this->length * sizeof(T));
                free(tmp);
                this->size += extra;
            }
        }
        // 打印栈
        friend ostream &operator<<(ostream &os, const SqStack &sq)
        {
            os << "SqStack<T>[" << sq.length << ", " << sq.size << "] {";
            if (sq.Empty())
            {
                os << "}" << endl;
            }
            else
            {
                for (int i = sq.topPtr; i >= 0; --i)
                {
                    os << sq.data[i] << ", ";
                }
                os << "\b\b}" << endl;
            }
            return os;
        }
    };    
}

#endif

SequenceStack.h

// CircularQueue.h
#ifndef _H_CIRCULARQUEUE
#define _H_CIRCULARQUEUE

// 循环队列定义头文件（Circular Queue）
namespace CircularQueue
{
    template <typename T, size_t MAXSIZE>
    class CuQueue
    {
    private:
        T *data;        // 数组
        size_t head;    // 头指针
        size_t rear;    // 尾指针
        size_t length;    // 长度
        size_t size;    // 大小
    public:
        // 构造器
        CuQueue()
        {
            this->head = 0;
            this->rear = 0;
            this->length = 0;
            this->size = MAXSIZE;
            this->data = new T[this->size];
        }
        // 析构器
        ~CuQueue() { free(this->data); }
        // 是否为空
        bool Empty() const { return this->length == 0; }
        // 是否已满
        bool Full() const { return this->size == this->length; }
        // 返回长度
        size_t Length() const { return this->length; }
        // 返回大小
        size_t Size() const { return this->size; }
        // 清除队列
        void Clear()
        {
            free(this->data);
            this->size = MAXSIZE;
            this->data = new T[this->size];
            this->length = 0;
            this->head = 0;
            this->rear = 0;
        }
        // 返回队列头元素
        T Head()
        {
            if (this->Empty())
            {
                throw out_of_range("CuQueue<T>: queue is empty!\n");
            }
            else
            {
                return this->data[this->head];
            }
        }
        // 进列
        void EnQueue(const T &elem)
        {
            if (this->Full())
            {
                throw out_of_range("CuQueue<T>: queue is full!\n");
            }
            else
            {
                // 当head和rear指向同一个位置时，队列为空
                this->data[this->rear] = elem;
                ++this->rear;
                ++this->length;
                if (this->rear == this->size)
                {
                    this->rear = 0;
                }
            }
        }
        // 出列
        void DeQueue()
        {
            if (this->Empty())
            {
                throw out_of_range("CuQueue<T>: queue is empty!\n");
            }
            else
            {
                ++this->head;
                --this->length;
                if (this->head == this->size)
                {
                    this->head = 0;
                }
            }
        }
        // 扩大循环队列，size += extra
        void Expand(const size_t &extra)
        {
            if (extra != 0)
            {
                T *tmp = this->data;
                this->data = new T[this->size + extra];
                // memcpy(destination, source, size)
                memcpy(this->data, tmp, this->length * sizeof(T));
                free(tmp);
                this->size += extra;
            }
        }
        // 打印循环队列
        friend ostream &operator<<(ostream &os, const CuQueue &cq)
        {
            os << "CuQueue<T>:[" << cq.length << ", " << cq.size << "][" << cq.head << ", " << cq.rear << "]: {";
            if (cq.Empty()) 
            {
                os << "}" << endl;
            }
            else
            {
                int index = cq.head;
                for (int i = 0; i < cq.length; ++i, ++index)
                {
                    if (index == cq.size) { index = 0; }
                    os << cq.data[index] << ", "; 
                }
                os << "\b\b}" << endl;
            }
            return os;
        }
    };
}

#endif

CircularQueue.h

#ifndef _H_SINGLYLINKEDLIST
#define _H_SINGLYLINKEDLIST

// 单链表定义头文件（Singly Linked List）

namespace SinglyLinkedList
{
    template <typename T>
    class SgNode
    {
    private:
        T elem;
        SgNode<T> *next;
    public:
        template <typename I> friend class SgList;
        T Elem() { return this->elem; }
        SgNode<T> *Next() { return this->next; }
        SgNode() {}
    };

    template <typename T>
    class SgList 
    {
    private:
        SgNode<T> *head;
        size_t length;
    public:
        // 初始化
        SgList() 
        {
            this->head = NULL;
            this->length = 0;
        }
        // 析构，删除每个节点
        ~SgList()
        {
            SgNode<T> *tmp;
            for (SgNode<T> *node = this->head; node;)
            {
                tmp = node;
                node = node->next;
                delete tmp;
            }
        }
        // 是否为空
        bool Empty() const { return this->length == 0; }
        // 长度
        size_t Length() const { return this->length; }
        // 清除单链表 
        void Clear()
        {
            SgNode<T> *tmp;
            for (SgNode<T> *node = this->head; node;)
            {
                tmp = node;
                node = node->next;
                delete tmp;
            }
            this->head = NULL;
            this->length = 0;
        }
        // 获取index上的elem
        T GetElem(const size_t &index)
        {
            if (this->Empty())
            {
                throw out_of_range("SgList<T>: List is empty!\n");
            }
            else if (index <= 0 || index > this->length)
            {
                throw out_of_range("SgList<T>: Index out of range!\n");
            }
            else
            {
                SgNode<T> *node = this->head;
                for (int i = 1; i < index; ++i)
                {
                    node = node->next;
                }
                return node->elem;
            }
        }
        // 返回elem在单链表中的索引
        size_t LocateElem(const T &elem)
        {
            size_t index = 1;
            for (SgNode<T> *node = this->head; node; node = node->next, ++index) 
            {
                if (node->elem == elem)
                {
                    return index;
                }
            }
            return 0;
        }
        // 在index位置插入elem
        void InsertElem(const size_t &index, const T &elem)
        {
            if (index <= 0 || index > this->length + 1)
            {
                throw out_of_range("SgList<T>: Index out of range!\n");
            }
            else
            {
                SgNode<T> *node = new SgNode<T>;
                node->elem = elem;
                if (index == 1)
                {
                    if (this->head == NULL)
                    {
                        node->next = NULL;
                        this->head = node;
                    }
                    else
                    {
                        node->next = this->head;
                        this->head = node;
                    }
                }
                else
                {
                    // 找到index-1上的节点
                    SgNode<T> *prior = this->head;
                    for (int i = 1; i < index - 1; ++i)
                    {
                        prior = prior->next;
                    }
                    node->next = prior->next;
                    prior->next = node;
                }
                ++this->length;
            }
        }
        // 删除index位置上的elem
        void DeleteElem(const size_t &index)
        {
            if (this->Empty())
            {
                throw out_of_range("SgList<T>: List is empty!\n");
            }
            else if (index <= 0 || index > this->length)
            {
                throw out_of_range("SgList<T>: Index out of range!\n");
            }
            else
            {
                if (index == 1)
                {
                    SgNode<T> *node = this->head;
                    this->head = this->head->next;
                    delete node;
                }
                else
                {
                    // 找到index-1上的节点
                    SgNode<T> *prior = this->head;
                    for (int i = 1; i < index-1; ++i)
                    {
                        prior = prior->next;
                    }
                    SgNode<T> *node = prior->next;
                    prior->next = prior->next->next;
                    delete node;
                }
                --this->length;
            }
        }
        // 打印SgList
        friend ostream &operator<<(ostream &os, const SgList &sg)
        {
            os << "SgList<T>[" << sg.length << "]: {";
            if (sg.Empty())
            {
                os << "NULL}" << endl;
            }
            else
            {
                for (SgNode<T> *node = sg.head; node; node = node->Next())
                {
                    os << node->Elem() << " -> ";
                }
                os << "NUll}" << endl;
            }

            return os;
        }
    };
}

#endif

SinglyLinkedList.h

#ifndef _H_LINKEDQUEUE
#define _H_LINKEDQUEUE

// 链队列的数据结构定义

namespace LinkedQueue
{
    template <typename T>
    class LiNode
    {
    private:
        T elem;
        LiNode<T> *next;
    public:
        template <typename I> friend class LiQueue;
        LiNode() {}
        T Elem() { return this->elem; }
        LiNode<T> *Next() { return this->next; }
    };

    template <typename T>
    class LiQueue
    {
    private:
        LiNode<T> *head;
        LiNode<T> *rear;
        size_t length;
    public:
        // 构造器
        LiQueue() 
        {
            this->head = NULL;
            this->rear = NULL;
            this->length = 0;
        }
        // 析构器
        ~LiQueue()
        {
            LiNode<T> *tmp;
            for (LiNode<T> *node = this->head; node;)
            {
                tmp = node;
                node = node->next;
                delete tmp;
            }
        }
        // 是否为空
        bool Empty() const { return this->length == 0; }
        // 长度
        size_t Length() const { return this->length; }
        // 清除链队列
        void Clear()
        {
            LiNode<T> *tmp;
            for (LiNode<T> *node = this->head; node;)
            {
                tmp = node;
                node = node->next;
                delete tmp;
            }
            this->head = NULL;
            this->rear = NULL;
            this->length = 0;
        }
        // 返回头部元素
        T Head()
        {
            if (this->Empty())
            {
                throw out_of_range("LiQueue<T>: queue is empty!\n");
            }
            else
            {
                return this->head->elem;
            }
        }
        // 入队
        void EnQueue(T elem)
        {
            LiNode<T> *node = new LiNode<T>;
            node->elem = elem;
            node->next = NULL;
            if (this->Empty())
            {
                
                this->head = node;
                this->rear = node;
            }
            else
            {    
                this->rear->next = node;
                this->rear = node;
            }
            ++this->length;
        }    
        // 出队 
        void DeQueue()
        {
            if (this->Empty())
            {
                throw out_of_range("LiQueue<T>: queue is empty!\n");
            }
            else
            {
                if (this->length == 1)
                {
                    delete this->head;
                    this->head = NULL;
                    this->rear = NULL;
                }
                else
                {
                    LiNode<T> *node = this->head;
                    this->head = this->head->next;
                    delete node;
                }
                --this->length;
            }
        }
        // 打印链队列
        friend ostream &operator<<(ostream &os, LiQueue &li)
        {
            os << "LiQueue<T>[" << li.length << "]: {";
            if (li.Empty()) 
            {
                os << "}" << endl;
            }
            else
            {
                for (LiNode<T> *node = li.head; node; node = node->Next())
                {
                    os << node->Elem() << ", ";
                }
                os << "\b\b}" << endl;
            }
            return os;
        }
    };
}

#endif

LinkedQueue.h

  • 算法（Algorithms）
    • 斐波那契数列（Fibonacci）
#ifndef _H_ALGORITHMS
#define _H_ALGORITHMS

// 斐波那契数列
size_t Fibonacci(size_t i)
{
    if (i < 2)
        return i == 0 ? 0 : 1;
    else
        return Fibonacci(i-1) + Fibonacci(i-2);
}

#endif

Algorithms.h

Cypress

Cypress

相关推荐

学c++需要先学c语言吗？

看需求，如果是底层开发，就必须学习C语言。如果只是应用开发，可以直接从C++开始学习。实际上这两个语言是平等的，只是在语法上C++尽量与C兼容，但仍然有很多不同的地方。1) C++不是C的超集。2) 如果你选择了一本好书，学C++之前完全没有必要学C，即使

shenwenjie / 0评论 2020-09-24

盘点 Python 10 大常用数据结构（上篇）

如果你还处于Python入门阶段，通常只需掌握list、tuple、set、dict这类数据结构，做到灵活使用即可。因为相比于list, tuple实例更加节省内存，这点尤其重要。并且set内允许增删元素，且效率很高。但是值得注意，dict占用字节数是li

xiesheng / 0评论 2020-08-02

java数据结构与算法一：稀疏数组

因为二维数组的很多值是默认值0，因此记录了很多没有意义的数据，可采用稀疏数组解决此问题。当一个数组中大部分元素为0，或者为同一个值的数组时，可以使用稀疏数组来保存该数组。稀疏数组中第一行依次存放着总行数、总列数、 不同值的个数，其他行则依次存放着值所在的行

mingyunxiaohai / 0评论 2020-07-28

算法学习路线

算法学习是一条漫长而又苦涩的道路。之所以漫长，是因为有关算法的学习是无穷无尽的，如果你不想经历程序员的35岁之劫难，那就要不断地学习算法，提高自己的不可替代性。之所以是苦涩，是因为算法更像是数学题，对智力是有一定要求的，学习算法的过程中总是会质疑自己，相较

Cypress / 0评论 2020-07-08

数据结构与算法(二) 线性表一

另外，线性表强调是有限的。例如很多编程语言的整型，浮点型，字符型这些指的就是数据类型。抽象数据类型是指一个数学模型及定义在该模型上的一组操作。抽象数据类型的定义仅仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。

Cypress / 0评论 2020-06-28

数据结构与算法(一)

算法采用的策略，方案。在编写程序的时候，我们不关心语言、所用的计算机只关心它所实现的算法。在修改后的运行函数中，只保留最高项。如果最高项存在且不是1，则除这个项相乘的常数。

Dyancsdn / 0评论 2020-06-27

C#数据结构与算法系列（十五）：排序算法（SortAlgorithm）

排序是将一组数据，以指定的顺序进行排序的过程

dushine00 / 0评论 2020-06-25

《数据结构与算法之美》09——排序（二）归并排序与快速排序

要排序一个数组，先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起。归并排序使用的是分治思想。分治，就是分而治之，将一个大问题分解成小的子问题来解决。回忆一下之前学习递归的编程技巧：分析得出递推公式，然后找到终止条件。归并

Masimaro / 0评论 2020-06-21

数据结构与算法知识导图

数据结构 的主要任务是通过分析数据对象的结构特征，包括逻辑结构及数据对象之间的关系，然后把逻辑结构表示成计算机课实现的物理结构，从而便于计算机处理。算法是解决特定问题求解步骤的描述，在计算机中表现为有限的操作序列。在数据类型建立起来之后，就要对这些数据类

waitwolf / 0评论 2020-06-21

[Java数据结构与算法]简单排序之插入排序

大多数情况下，在三种简单排序中，插入排序都是最优的选择。虽然插入排序算法仍需要 O(N^2) 的时间，但在一般情况下，它要比冒泡排序快一倍，比选择排序还要快一点。插入排序可以简单表述为：使“标定项”的一侧局部有序，每次将标定项插入有序一侧，同时将另一侧的下

Jasmineyaoyao / 0评论 2020-06-16

C#数据结构与算法（六）：链表——双链表（Double-LinkedList）

对于单向链表的删除，我们首先要找到单向链表待删除节点的前一个节点，然后前一个节点的下一个节点指向删除节点的后一个节点。//如果temp.Next为null就表示temp为最后一个节点；

OldBowl / 0评论 2020-06-16

C#数据结构与算法系列（五）：常见单链表笔试

int length = 0;var cur = headNode.Next;if (cur == null) break;length++;cur = cur.Next;return length;public static HeroNode GetLa

alicelmx / 0评论 2020-06-16

数据结构：第六章学习小结

第六章图的学习感觉比较侧重阅读和理解代码，而写代码部分占比比较小。所以这一章的总结全都是知识点的整理，是用自己的话来表达自己对代码以及做题过程步骤的理解。邻接表存储顶点名称，同时将顶点下标存储在一个结点内，因此当邻接矩阵调用Locate方法来得到顶点下标值

Masimaro / 0评论 2020-06-14

数据结构之稀疏数组的使用场景及实现

顺序存储的线性表称为顺序表，顺序表中的存储元素是连续的。　　链式存储的线性表称为链表，链表中的存储元素不一定是连续的，元素节点中存放数据元素以及相邻元素的地址信息。　　线性结构常见的有：数组、队列、链表和栈，后面我们会详细讲解.　　编写的五子棋程序中，有存

waitwolf / 0评论 2020-06-08

数据结构之递归与调用栈

递归算法是一种直接或间接调用自身算法的过程。每个递归函数都有两部分：基线 条件和递归条件。基线条件则指的是函数不再调用自己，函数的终止条件，避免形成无限循环 。所有函数调用都进入调用栈，使用递归必须理解这个概念。调用栈是的原则是先进后出，栈有两种操作：压入

nurvnurv / 0评论 2020-06-05

数据结构与算法-线性表和散列表的总结

将元素映射为下标，然后将数据存储在数组中对应下标的位置，当需要对元素进行操作时，使用同样的方法将元素映射为下标，找到下标的位置，从对应数组下标的位置取数据

ustbfym / 0评论 2020-06-04

前端就不需要掌握算法与数据结构？

因为开发的过程就是把实际问题转换成计算机可识别的指令，也就是《数据结构》里说的，「设计出数据结构，在施加以算法就行了」。编写指令的好坏，会直接影响到程序的性能优劣，而指令又由数据结构和算法组成，所以数据结构和算法的设计基本上决定了最终程序的好坏。另外，在阅

ziruoxiangyi / 0评论 2020-06-03

前端就不需要掌握算法与数据结构？

因为开发的过程就是把实际问题转换成计算机可识别的指令，也就是《数据结构》里说的，「设计出数据结构，在施加以算法就行了」。编写指令的好坏，会直接影响到程序的性能优劣，而指令又由数据结构和算法组成，所以数据结构和算法的设计基本上决定了最终程序的好坏。另外，在阅

范范 / 0评论 2020-06-03

数据结构：第五章学习小结

②利用check数组，将其初始化为false，后续创建树的过程中，将孩子结点的编号作为check数组下标，若出现则变为true，以此找出根结点。

Jasmineyaoyao / 0评论 2020-05-31

数据结构与算法-java-哈希表

散列表，是根据关键码值而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。给定表M，存在函数f，对任意给定的关键字值key，代入函数后若能得到包含该关键字的

alicelmx / 0评论 2020-05-26

算法与数据结构（二）嵌套与俄罗斯套娃

理论上是通过LIFO 的 stack 缓存实现：把套娃一个一个拆开先放好，从最小一个套娃开始再一个一个的合上。斐波纳契数列前两个数是 0，1 后面数字是前面个数字的和。

学习 / 0评论 2020-05-25

数据结构与算法之选择排

selectionSort(array);return;int min = i;min = array[min] < array[j] ?min: j;ArrayUtil.swap(array,min,i);

范范 / 0评论 2020-05-25

数据结构与算法之归并排

int [] help = new int [R - L + 1];

hanyujianke / 0评论 2020-05-25

数据结构与算法——C语言描述 二叉树的存储结构

二叉树的顺序结构就是将所有的结点按照一定的次序，顺序存储在一维数组当中，并且结点的存储位置，也就是数组的下标要能够体现出节点之间的逻辑关系，例如双亲和孩子的关系、左右兄弟的关系等。但是，用顺序存储结构来表示二叉树也有着明显的缺点。对于一个稀疏的二叉树来说，

Jasmineyaoyao / 0评论 2020-05-15

数据结构与算法 (03)

继续来进行 pythonCookbook. 学习大佬代码使我快乐, 与其自己写, 还不如直接抄, 然后加上自己的注解, 这样才是最适合我的学习之道哇.就去个重, 私以为不用那么麻烦的吧. 其实更多的是, 我们通常不用考虑其顺序, 就去重, 这样一来,

ipqtjmqj / 0评论 2020-05-12

数据结构（查找）

　　对于静态查找：可以用线性表结构组织数据，这样便可使用顺序查找算法，如果再对关键字进行排序，则可使用折半查找法或斐波那契查找法等来提高效率。由于每次循环都要判断两次，所以可以考虑添加一个“哨兵”来承担监视越界的问题省去一次判断，这样效率就可提高一倍；　　

Jasmineyaoyao / 0评论 2020-05-11

数据结构的三要素

　　数据元素之间的逻辑关系。　　一个算法随着数据或者说输入规模n的增大，运行时间的数量级，一般用 大O表示，不考虑函数的低阶项和首项系数。一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。

OldBowl / 0评论 2020-05-08

数据结构与算法（Python版）：用队列（Queue）处理约瑟夫问题

在古罗马时期，犹太人背叛了罗马人，落到困境，约瑟夫和同行的一共39个犹太人只能够自杀殉国，但是犹太教义规定不能自杀，因此只能够让别人将自己杀害。他们所有39个人坐成一圈，报数1—7，报到7则由身旁的人将自己杀死。结果约瑟夫灵机一动，给自己安排了一个位置，最

小菜鸟的代码世界 / 0评论 2020-05-08

数据结构与算法参考答案（第二周）

试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。这里我们需要满足x的值大于等于va.elem[i]且小于va.elem[i+1]。之后我们需要将顺序表的va.length - i - 1个元素后移一位。最后将表长va.length加1。算法执

xhao / 0评论 2020-05-05

数据结构：第四章学习小结

　　①串的定义：注意空串()和空格串(“ ”)的区别。　　　　i. 顺序存储又分为定长顺序存储和堆式顺序存储，前者为静态存储，相当于一维数组，而后者为动态存储；　　　　ii. 链式存储：每个结点可以存放一个或多个字符；最后一个结点若是未被占满，可用“#”或

hanyujianke / 0评论 2020-05-05

数据结构与算法参考答案（第三周）

试写一高效的算法，删除表中所有值大于mink且小于maxk的元素同时释放被删结点空间，并分析你的算法的时间复杂度。当判断出来的元素大于等于maxk时，需要将原先记录的结点的指针的next指向这个元素的后继指针，同时将这个结点空间释放，然后结束循环，返回链表

shenwenjie / 0评论 2020-05-05

数据结构第四章学习小结

1）串是内容受限的线性表，考虑到存储效率和算法方便性，一般采用顺序存储结构；考虑到串变量相差较大，可采用动态分配的方法；为了便于操作，可增设尾指针。串的主要应用场景是模式匹配，其中有BF算法和KMP算法。2）关于数组，本章还介绍了特殊矩阵的压缩存储,可用三

hanyujianke / 0评论 2020-05-04

算法与数据结构（4）：堆排序

因为这个系列是介绍算法与数据结构的，所以此系列后续提到的所有“堆”，都是只一种数据结构，希望读者在自行了解相关知识时，注意区分。此文堆排序的完整代码可以在我的github上查看。

shenwenjie / 0评论 2020-05-03

数据结构与算法（线性表）

线性表是一种最简单的线性结构。用一组地址任意的存储单元存放线性表中的数据元素。在单链表中删除第 i 个结点的基本操作为:找到线性表中第i-1个结点，修改其指向后继的指针。用前者表示的线性表简称为顺序表，用后者表示的线性表简称为链表。

freedomfanye / 0评论 2020-05-03

JAVA数据结构与算法之顺序存储二叉树

1) 右图的二叉树的结点，要求以数组的方式来存放 arr : [1, 2, 3, 4, 5, 6, 6]

shenwenjie / 0评论 2020-04-26

JAVA数据结构与算法之二叉树（一）

能提高数据 存储 ， 读取的效率, 比如利用 二叉排序树，既可以保证数据的检索速度，同时也可以保证数据的 插入，删除，修改的速度。

ding0 / 0评论 2020-04-26

JAVA数据结构与算法之哈希表

散列表，是根据关键码值而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。有一个公司,当有新的员工来报道时,要求将该员工的信息加入,当输入该员工的 id 时

lickylin / 0评论 2020-04-25

JAVA数据结构与算法之 线索化二叉树

2) 但是 6, 8, 10, 14 这几个节点的 左右指针，并没有完全的利用上.1) n 个结点的二叉链表中含有 n+1 个空指针域。利用二叉链表中的空指针域，存放指向该结点在某种遍历次序下的前驱和后继结点的指针。2) 这种加上了线索的二叉链表称为线索

范范 / 0评论 2020-04-26

JAVA数据结构与算法之插入排序

插入式排序属于内部排序法，是对于欲排序的元素以插入的方式找寻该元素的适当位置，以达到排序的目的。插入排序的基本思想是：把 把 n 个待排序的元素看成为一个有序表和一个无序表，开始时 有序表中只包含一个元素，无序表中包含有 n-1 个元素，排序过程中每次

shenwenjie / 0评论 2020-04-25

JAVA数据结构与算法之数组与队列（二）

2) 遵循 先入先出的原则。后存入的要后取出。1) 队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如上图, 其中 maxSize 是该队列的最大容量。2）因为队列的输出、输入是分别从前后端来处理，因此需要两个变量 front 及 r

Cypress / 0评论 2020-04-25

数据结构与算法之美_25_红黑树（上）：为什么工程中都用红黑树这种二叉树？

二叉查找树是最常用的一种二叉树，它支持快速插入、删除、查找操作，各个操作的时间复杂度跟树的高度成正比，理想情况下，时间复杂度是 O。不过，二叉查找树在频繁的动态更新过程中，可能会出现数的高度远大于 log2^n 的情况，从而导致各个操作的效率下降。在工程中

lickylin / 0评论 2020-04-22

【数据结构与算法】二叉树——二叉树的最小深度

给定一个二叉树，找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

roseying / 0评论 2020-04-19

【数据结构与算法】二叉树——平衡二叉树

给定一个二叉树，判断它是否是高度平衡的二叉树。使用实例域变量记录是否与有不满足平衡的节点出现，使用一次递归即可。

ding0 / 0评论 2020-04-17

【数据结构与算法之美】04-数组：为什么很多编程语言中数组都从0开始编号？

　　几乎在每一种编程语言中，都有数组这个数据类型。不过，它不仅仅是一种编程语言中的数据类型，还是一种最基础的数据结构。尽管数组看起来非常基础、简单，但是我们真的理解了它的精髓吗？在大部分编程语言中，数组都是从 0 开始编号的。从 1 开始不是更符合人类的思

Jasmineyaoyao / 0评论 2020-04-15

最小代价生成树（数据结构）

int lowcost[maxsize],visit[maxsize],v;//lowcost存放当前树到其他顶点的最小权值的顶点。//Kruskal算法：每次找出候选边中权值最小的边，就将该边并入生成树中。

Cypress / 0评论 2020-04-14

Datawhale 数据结构与算法

数组是n个相同数据类型的数据元素的有限序列；数组是具有固定格式和数量的数据有序集；数组在托管堆上分配空间，是引用类型；public abstract class Array : ICloneable, IList, ICollection, IEnumer

Jasmineyaoyao / 0评论 2020-04-07

数据结构与算法复杂度分析

算法的执行效率，粗略地讲，就是算法代码执行的时间。但是，如何在不运行代码的情况下，用“肉眼”得到一段代码的执行时间呢？这里有段非常简单的代码，求 1,2,3…现在，来估算一下这段代码的执行时间。从 CPU 的角度来看，这段代码的每一行都执行着类似的操作：读

hanyujianke / 0评论 2020-04-07

数据结构、算法、线性表总结

存储结构是逻辑结构在计算机中的存储形式。同样的操作在不同的存储结构上，实现方法不同。时间复杂度的关系：。算法在所有可能情况下，按照输入实例以等概率出现时，算法计算量的加权平均值。更关心最坏情况下和平均情况下的时间复杂度。算法的执行过程中，所占据的辅助空间数

OldBowl / 0评论 2020-03-28

数据结构-概念总结

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。集合结构，线性结构，树形结构，图结构。数据结构在计算机专业课程体系中起到承上启下的作业，熟练使用数据结构可以使程序运行的更快更流畅思维导图：。有穷性，确定性，

ding0 / 0评论 2020-03-28

数据结构、算法及线性表总结

void CreateListF//头插法建链表，L表示带头结点链表，n表示数据元素个数。,n的次序进栈；栈顶元素先出栈→栈底元素最后出栈；时进时出→元素未完全进栈时，即可出栈。void get_next { // 求模式串T的next函数值并存入数组ne

RememberMePlease / 0评论 2020-03-28