LOFTER for ipad —— 让兴趣,更有趣

点击下载 关闭

LOFTER-网易轻博

数据结构

2358浏览    431参与
txwtech笛科思

cb01a_c++_数据结构_顺序容器_STL_deque类

deque是一个动态数组,比vector更加灵活.两者都属于动态数组

deque与vector非常类似

deque可以在数组开头和末尾插入和删除数据

vector只能在数组的末尾插入和删除数据


distance算法

size_t nOffset = distance(a.begin(),iElementLocater);//计算a.begin()与iElementLocator之间的距离

a.begin()位置不变,iElementLocator在变化,所以就可以用在做下标。

*/


#include <iostream>

#include <...

deque是一个动态数组,比vector更加灵活.两者都属于动态数组

deque与vector非常类似

deque可以在数组开头和末尾插入和删除数据

vector只能在数组的末尾插入和删除数据


distance算法

size_t nOffset = distance(a.begin(),iElementLocater);//计算a.begin()与iElementLocator之间的距离

a.begin()位置不变,iElementLocator在变化,所以就可以用在做下标。

*/


#include <iostream>

#include <deque>

#include <algorithm>//算法


using namespace std;


int main()

{

    deque<int> a;

    a.push_back(3);

    a.push_back(5);

    a.push_back(6);

    a.push_front(2);

    a.push_front(1);

    a.push_front(0);


    for (size_t nCount = 0; nCount < a.size(); ++nCount)

    {

        cout <<"a["<<nCount<<"]=" << a[nCount] << endl;

    }

    //

    cout << endl;


    a.pop_front();//删除前面的数据

    a.pop_back();//删除后面的数据

    for (size_t nCount = 0; nCount < a.size(); ++nCount)

    {

        cout << "a[" << nCount << "]=" << a[nCount] << endl;

    }


    cout <<"使用distance算法"<< endl;

    //使用deque的迭代器,没有下标

    deque<int>::iterator iElementLocater;

    for (iElementLocater = a.begin(); iElementLocater != a.end(); ++iElementLocater)

    {

        size_t nOffset = distance(a.begin(),iElementLocater);//计算a.begin()与iElementLocator之间的距离

        cout << "a[" << nOffset << "]=" <<*iElementLocater << endl;

    }


    return 0;

}


txwtech笛科思

cb02a_c++_数据结构_顺序容器_STL_list类_双向链表

cb02a_c++_数据结构_顺序容器_STL_list类_双向链表

实例化std::list对象

在list开头插入元素

在list末尾插入元素

在list中间插入元素,插入时间恒定,非常快。数组:中间插入慢。

删除list中的元素

对list中元素进行反转和排序


通过指针指向下一个节点

//链表不是数组,没有下标。只能使用迭代器

*/


#include <iostream>

#include <list>


using namespace std;


void PrintListContents(const list<...

cb02a_c++_数据结构_顺序容器_STL_list类_双向链表

实例化std::list对象

在list开头插入元素

在list末尾插入元素

在list中间插入元素,插入时间恒定,非常快。数组:中间插入慢。

删除list中的元素

对list中元素进行反转和排序


通过指针指向下一个节点

//链表不是数组,没有下标。只能使用迭代器

*/


#include <iostream>

#include <list>


using namespace std;


void PrintListContents(const list<int>& listInput);


int main()

{

    list <int> a;//list也是一个模板类,a就是双向链表

    a.push_front(10);//链表前端添加数据

    a.push_front(9);

    a.push_front(8);

    a.push_front(7);

    a.push_back(11);//链表后端添加数据


    //a.insert(a.begin(), 10);//在开头的前面插入10。 a.begin()就是迭代器

    


    

    list<int> b;

    b.push_back(100);

    b.push_back(200);

    b.push_back(300);

    b.push_back(400);

    b.push_back(500);


    //链表不是数组,没有下标

    std::list<int>::iterator iter;//迭代器就是指针


    iter = a.begin();

    a.insert(iter, 11);//在开头的前面插入11。

    a.insert(a.end(), 3, 30);//在后端插入3个30,a.end()就是迭代器


    ++iter;

    a.insert(iter, 11);//在开头的下一个位置插入11.++iter指针移动了位置

    //a.insert(a.end(), b.begin(), b.end());//把list b的数据全部插入到list a的末尾


    a.insert(a.end(),++b.begin(),--b.end());//b的第二个位置数据到 b结尾倒数一个数。一起插入


    cout << "show list a data..." << endl;

    PrintListContents(a);


    /*for (iter = a.begin(); iter != a.end(); ++iter)

    {

        cout << *iter << endl;

    }*/

    cout << "show list b data" << endl;

    PrintListContents(b);


    return 0;

}

void PrintListContents(const list<int>& listInput)

{

    std::list<int>::const_iterator iter;

    for (iter = listInput.begin(); iter != listInput.end(); ++iter)

        cout << *iter << endl;

}


txwtech笛科思

cb03a_c++_数据结构_顺序容器_STL_stack

cb03a_c++_数据结构_顺序容器_STL_stack

堆栈:LIFO--Last In First Out后进先出,用于系统程序设计

自适应容器(容器适配器),不是独立的容器,是一个适配器

栈适配器STL stack

stack<int,deque<int> s;

stack<int, vector<int>> s;

stack<int,list<int> s;

s.empey(),堆栈是否空

s.size();堆栈有多少个数据

s.pop();堆栈弹出数据

s.top();查看栈顶数据

s.push(item...

cb03a_c++_数据结构_顺序容器_STL_stack

堆栈:LIFO--Last In First Out后进先出,用于系统程序设计

自适应容器(容器适配器),不是独立的容器,是一个适配器

栈适配器STL stack

stack<int,deque<int> s;

stack<int, vector<int>> s;

stack<int,list<int> s;

s.empey(),堆栈是否空

s.size();堆栈有多少个数据

s.pop();堆栈弹出数据

s.top();查看栈顶数据

s.push(item),数据压入堆栈


int x = d.pop(); //错误,pop删除数据,定义类型void,不返回。改为d.top();

error C2440: “初始化”: 无法从“void”转换为“int”

*/

#include <iostream>

#include <stack>

#include <vector>

#include <list>


using namespace std;

int main()

{

    stack<int,deque<int>> a; //a堆栈用deque做的

    stack<int, vector<int>> b; //b堆栈用vector做的

    stack<int, list<int>> c; //c堆栈用list做的


    stack<int> d;//d,默认用的deque做的堆栈


    d.push(25);//把25压入堆栈

    d.push(10);

    d.push(1);

    d.push(6);


    cout << "现在栈里面有多少个数据呢?: " << d.size() << endl;

    

    //int x = d.pop(); //错误,pop删除数据,定义类型void,不返回数据

    int x = d.top();

    d.pop();//删除数据

    cout << x << endl;


    int x1 = d.top();

    d.pop();//删除数据

    cout << x1 << endl;

    cout << "现在栈里面有多少个数据呢?: " << d.size() << endl;

    //while(d.size()!=0)

    while (d.empty() == false)

    {

        d.pop();//删除数据

    }

    cout << "现在栈里面有多少个数据呢?: " << d.size() << endl;

    return 0;

 }


hongcaixuexi
弘才学习教育

严蔚敏数据结构教材视频课程

[视频]严蔚敏《数据结构》(C语言版)网授精讲班【教材精讲+考研真题串讲】

资料地址:http://hongcai.100xuexi.com/Ebook/45954.html

本课程由资深辅导教师耿佳老师讲授,全面讲解教材的重点、难点、考点,教会学员理解并掌握该教材中的基本概念、基本原理和基本方法,并结合名校考研真题和典型试题引导学员掌握答题的思路与方法,进一步提升应试能力。同时从不同侧面把握应试考点,再针对性地进行重点讲解,缩减考试范围,更准确地把握考试的方向和思路。

网授精讲班以大屏高清网络视频为载体,开启全新一代教学模式,给学员带来视觉上的震撼!通过授课视频和课程讲义的完美结合,为学员打造了一...

[视频]严蔚敏《数据结构》(C语言版)网授精讲班【教材精讲+考研真题串讲】

资料地址:http://hongcai.100xuexi.com/Ebook/45954.html

本课程由资深辅导教师耿佳老师讲授,全面讲解教材的重点、难点、考点,教会学员理解并掌握该教材中的基本概念、基本原理和基本方法,并结合名校考研真题和典型试题引导学员掌握答题的思路与方法,进一步提升应试能力。同时从不同侧面把握应试考点,再针对性地进行重点讲解,缩减考试范围,更准确地把握考试的方向和思路。

网授精讲班以大屏高清网络视频为载体,开启全新一代教学模式,给学员带来视觉上的震撼!通过授课视频和课程讲义的完美结合,为学员打造了一个最佳的视听学习空间。

网授课程

严蔚敏《数据结构》(C语言版)网授精讲班【共49课时】

序号 名称 课时

1 第一章 绪 论 00:40:42

2 第二章 线性表(1) 01:15:39

3 第二章 线性表(2) 00:54:58

4 第三章 栈与队列(1) 01:10:29

5 第三章 栈与队列(2) 00:59:44

6 第四章 串 01:30:00

7 第五章 数组和广义表(1) 01:13:47

8 第五章 数组和广义表(2) 01:19:12

9 第六章 树和二叉树(1) 01:19:22

10 第六章 树和二叉树(2) 01:07:44

11 第六章 树和二叉树(3) 01:21:05

12 第六章 树和二叉树(4) 00:44:26

13 第六章 树和二叉树(5) 01:09:16

14 第七章 图(1) 01:06:39

15 第七章 图(2) 00:58:01

16 第七章 图(3) 01:20:22

17 第七章 图(4) 00:45:06

18 第七章 图(5) 01:24:20

19 第七章 图(6) 01:34:34

20 第八章 动态存储管理 01:32:32

21 第九章 查找(1) 01:30:42

22 第九章 查找(2) 00:40:16

23 第九章 查找(3) 01:13:09

24 第九章 查找(4) 01:36:00

25 第九章 查找(5) 01:21:01

26 第十章 内部排序(1) 01:17:06

27 第十章 内部排序(2) 01:15:06

28 第十章 内部排序(3) 01:34:27

29 第十一章 文件与外部排序(1) 01:07:33

30 第十一章 文件与外部排序(2) 01:02:54

1.精讲教材章节内容

按照教材篇章结构,辅导老师精讲教材章节内容,并在此基础上分析重难点以及各个知识点需掌握的程度。通过梳理各章知识点,将各个知识点的经络编制清晰,使知识点形成一个框架网络,强化基础知识的基础上分析教材的考点,归纳难点、重点。

2.穿插经典考研真题

在各个章节中,通过列举并分析历年考研真题,明确命题规律和特点,引导学员掌握考点的历年出题思路及方式,从而有效指导学员复习相关知识点。

3.电子书(题库)(送手机版)

报名本课程后,本视频课程里的所有电子书(题库)均可使用。

需要提醒的是,考虑到课时的需要以及相关知识点的难易程度,对于一些简单的知识点、考试不易涉及的知识点,本课程不予以讲述或一带而过,故建议大家在学习本课程之前提前复习一遍教材,在翻看教材基础上,学习本课程。本课程的学员可以下载电子版讲义打印学习。

相关资料:

[电子书+打印版]严蔚敏《数据结构》(C语言版)【教材精讲+考研真题解析】讲义与视频课程【36小时高清视频】

资料地址:http://hongcai.100xuexi.com/Ebook/958998.html

更多优质视频课程,请登录弘才学习网:http://hongcai.100xuexi.com/


白兔青柠

数据结构学习笔记——线性表(四)

有序表(Ordered List)是线性表的衍生物,区别只在于有序表在数据元素插入的时候就给它排好序,这有点像摸扑克牌。

有序表值得说的只有二路归并算法。

二路归并算法用于将两个有序表合并成一个,当然,也是有序的合并。如果一个个读取参数有序表的元素来插入的话,效率极低,所以我们需要采用如下方法。

假设我们合并一个递增的int有序表。

首先,我们将本表设为A表,设A表为

5,6,8,123

将传来的参数表设为B表,设B表为

1,2,7

之后,我们需要建立一个C表,然后看A表的第一个元素和B表的第一个元素,哪个小就把哪个放进C里,显然1小,将其放进C里,现在A表、B表如下:

5,...

有序表(Ordered List)是线性表的衍生物,区别只在于有序表在数据元素插入的时候就给它排好序,这有点像摸扑克牌。

有序表值得说的只有二路归并算法。

二路归并算法用于将两个有序表合并成一个,当然,也是有序的合并。如果一个个读取参数有序表的元素来插入的话,效率极低,所以我们需要采用如下方法。

假设我们合并一个递增的int有序表。

首先,我们将本表设为A表,设A表为

5,6,8,123

将传来的参数表设为B表,设B表为

1,2,7

之后,我们需要建立一个C表,然后看A表的第一个元素和B表的第一个元素,哪个小就把哪个放进C里,显然1小,将其放进C里,现在A表、B表如下:

5,6,8,123

2,7

然后再看A表的第一个元素和B表的第一个元素,哪个小就把哪个放进C里,如此循环即可。

接下来会出现一个表都放进C里了,而另一个还剩下若干个数据元素的情况,这时只需将其依次放进C里即可。

这个算法的时间复杂度为O(n),n就是A、B表的长度之和。两个表都只遍历一次,是很高效的算法。

我的有序表从双链表改造而来,代码如下:

SortedIntList.h:

#pragma once

#include <initializer_list>

#include "LinkedListNode.h"

class SortedIntList

{

LinkedListNode<int>* Head = nullptr;

public:

SortedIntList() {}

SortedIntList(const std::initializer_list<int> elements);

~SortedIntList();

//在线性表插入值

void Insert(const int element);

//删除最近数据元素(从左向右遍历)

void Remove(const int element);

//删除所有指定数据元素

void RemoveAll(const int element);

//按位置删除数据元素,并返回值

int RemoveAt(const int i);

//返回线性表的长度

int Length();

//取得某个位置的值

int& operator[](const int id);

//按元素值查找元素位置

int Locate(const int element);

LinkedListNode<int>* GetHead();

//将另一个列表合并进来

SortedIntList& Union(SortedIntList* anotherlist);

};


SortedIntList.cpp:

#include <stdexcept>

#include "SortedIntList.h"

#include "LinkedListNode.h"

SortedIntList::SortedIntList(const std::initializer_list<int> elements)

{

for (auto i : elements)

Insert(i);

}

SortedIntList::~SortedIntList()

{

if (Head == nullptr) return;

LinkedListNode<int>* temppos = Head;

while (temppos != nullptr)

{

Head = Head->Next;

delete temppos;

temppos = Head;

}

}

void SortedIntList::Insert(const int element)

{

if (Head == nullptr)

{

Head = new LinkedListNode<int>;

Head->Data = element;

return;

}

LinkedListNode<int>* temppos = Head;

LinkedListNode<int>* temp;

while (temppos != nullptr && temppos->Data < element)

{

if (temppos->Next == nullptr)

{

temp = new LinkedListNode<int>;

temp->Data = element;

temp->Prev = temppos;

temppos->Next = temp;

return;

}

temppos = temppos->Next;

}

if (temppos->Prev == nullptr)

{

temp = new LinkedListNode<int>;

temp->Next = Head;

Head->Prev = temp;

temp->Data = element;

Head = temp;

return;

}

temp = new LinkedListNode<int>;

temp->Data = element;

temp->Prev = temppos->Prev;

temppos->Prev->Next = temp;

temp->Next = temppos;

temppos->Prev = temp;

}

void SortedIntList::Remove(const int element)

{

LinkedListNode<int>* temppos = Head;

if (Head->Data == element)

{

if (Head->Next == nullptr)

Head = nullptr;

else

{

Head->Next->Prev = nullptr;

Head = Head->Next;

}

delete temppos;

}

else

{

while (temppos != nullptr)

{

if (temppos->Data == element)

{

if (temppos->Next == nullptr)

temppos->Prev->Next = nullptr;

else

{

temppos->Next->Prev = temppos->Prev;

temppos->Prev->Next = temppos->Next;

}

delete temppos;

return;

}

temppos = temppos->Next;

}

}

}

void SortedIntList::RemoveAll(const int element)

{

LinkedListNode<int>* temppos = Head;

if (Head->Data == element)

{

if (Head->Next == nullptr)

{

Head = nullptr;

return;

}

else

{

Head->Next->Prev = nullptr;

Head = Head->Next;

}

delete temppos;

}

while (temppos != nullptr)

{

if (temppos == Head)

{

if (temppos->Data == element)

{

if (Head->Next == nullptr)

{

Head = nullptr;

return;

}

}

continue;

}

if (temppos->Data == element)

{

if (temppos->Next == nullptr)

temppos->Prev->Next = nullptr;

else

{

temppos->Next->Prev = temppos->Prev;

temppos->Prev->Next = temppos->Next;

}

LinkedListNode<int>* temp = temppos;

delete temp;

}

temppos = temppos->Next;

}

}

int SortedIntList::RemoveAt(const int i)

{

LinkedListNode<int>* temppos = Head;

int temp;

if (i < 0) throw std::out_of_range("所取位置不可小于0。");

else if (i == 0)

{

if (Head->Next != nullptr)Head = Head->Next;

else Head = nullptr;

temp = temppos->Data;

delete temppos;

return temp;

}

else

{

for (int j = 0; j < i - 1; j++)

{

if (temppos == nullptr)

throw std::out_of_range("所取位置超出链表范围。");

temppos = temppos->Next;

}

temppos->Prev->Next = temppos->Next;

if (temppos->Next != nullptr)temppos->Next->Prev = temppos->Prev;

temp = temppos->Data;

delete temppos;

return temp;

}

}

int SortedIntList::Length()

{

int temp = 0;

LinkedListNode<int>* temppos = Head;

while (temppos != nullptr)

{

temp++;

temppos = temppos->Next;

}

return temp;

}

int& SortedIntList::operator[](const int id)

{

LinkedListNode<int>* temppos = Head;

for (int j = 0; j < id; j++)

{

if (temppos == nullptr)

throw std::out_of_range("所取位置超出链表范围。");

temppos = temppos->Next;

}

return temppos->Data;

}

int  SortedIntList::Locate(const int element)

{

LinkedListNode<int>* temppos = Head;

int temp = 0;

while (temppos != nullptr)

{

if (temppos->Data == element) return temp;

temp++;

temppos = temppos->Next;

}

return -1;

}

LinkedListNode<int>* SortedIntList::GetHead()

{

return Head;

}

SortedIntList& SortedIntList::Union(SortedIntList* anotherlist)

{

LinkedListNode<int>* tempposA = Head;

LinkedListNode<int>* tempposB = anotherlist->GetHead();

LinkedListNode<int>* temppos = nullptr;

Head = nullptr;

while (tempposA != nullptr && tempposB != nullptr)

{

if (tempposA->Data < tempposB->Data)

{

if (Head == nullptr)

{

temppos = Head = tempposA;

tempposA = tempposA->Next;

}

else

{

temppos->Next = tempposA;

tempposA->Prev = temppos;

temppos = temppos->Next;

tempposA = tempposA->Next;

}

}

else

{

if (Head == nullptr) 

{

LinkedListNode<int>* temp = new LinkedListNode<int>;

temp->Data = tempposB->Data;

temppos = Head = temp;

tempposB = tempposB->Next;

}

else

{

LinkedListNode<int>* temp = new LinkedListNode<int>;

temp->Data = tempposB->Data;

temppos->Next = temp;

temp->Prev = temppos;

temppos = temppos->Next;

tempposB = tempposB->Next;

}

}

}

while (tempposA != nullptr)

{

if (Head == nullptr)

{

temppos = Head = tempposA;

tempposA = tempposA->Next;

}

else

{

temppos->Next = tempposA;

tempposA->Prev = temppos;

temppos = temppos->Next;

tempposA = tempposA->Next;

}

}

while (tempposB != nullptr)

{

if (Head == nullptr)

{

LinkedListNode<int>* temp = new LinkedListNode<int>;

temp->Data = tempposB->Data;

temppos = Head = temp;

tempposB = tempposB->Next;

}

else

{

LinkedListNode<int>* temp = new LinkedListNode<int>;

temp->Data = tempposB->Data;

temppos->Next = temp;

temp->Prev = temppos;

temppos = temppos->Next;

tempposB = tempposB->Next;

}

}

temppos->Next = nullptr;

return *this;

}


白兔青柠

数据结构学习笔记——线性表(三)

链表(Linked List)是线性表的链式存储结构,它的存储位置不连续,利用的是存储空间中零散的各部分,它没有容量限制,理论上可以无限延伸。

链表由若干个节点(Node)组成,每个节点包含它所储存的数据,以及前一个节点与后一个节点所在的内存地址,在C++中以指针实现,称为指针域。节点相连就成了链表。而第一个节点与最后一个节点的内存地址储存在头指针和尾指针中。

顺便说一句,链表的存储密度(节点中数据元素所占存储量/节点所占存储量)不如线性表。


链表分为单链表、双链表、循环链表。

节点前后相连即为双链表。


单链表的节点不包含前节点的指针,只向后单向传递。


循环链表首尾相连,没有头...

链表(Linked List)是线性表的链式存储结构,它的存储位置不连续,利用的是存储空间中零散的各部分,它没有容量限制,理论上可以无限延伸。

链表由若干个节点(Node)组成,每个节点包含它所储存的数据,以及前一个节点与后一个节点所在的内存地址,在C++中以指针实现,称为指针域。节点相连就成了链表。而第一个节点与最后一个节点的内存地址储存在头指针和尾指针中。

顺便说一句,链表的存储密度(节点中数据元素所占存储量/节点所占存储量)不如线性表。


链表分为单链表、双链表、循环链表。

节点前后相连即为双链表。


单链表的节点不包含前节点的指针,只向后单向传递。


循环链表首尾相连,没有头节点、尾节点。



我写的是双链表,代码如下(LinkedList.h):

#pragma once

#include <stdexcept>

#include <initializer_list>

#include "LinkedListNode.h"

#include "LinearListBase.h"

template<typename T>

class LinkedList:public LinearListBase<T>

{

LinkedListNode<T>* Head = nullptr;

public:

LinkedList(){}

LinkedList(const std::initializer_list<T> elements);

//在线性表末尾插入值

void Insert(const T element);

//在线性表的第i个位置插入值

void Insert(const T element, const int i);

//删除最近数据元素(从左向右遍历)

void Remove(const T element);

//删除所有指定数据元素

void RemoveAll(const T element);

//按位置删除数据元素,并返回值

T RemoveAt(const int i);

//返回线性表的长度

int Length();

//取得某个位置的值

T& operator[](const int id);

//按元素值查找元素位置

int Locate(const T element);

~LinkedList();

};


template<typename T>

LinkedList<T>::LinkedList(const std::initializer_list<T> elements)

{

LinkedListNode<T>* temp = nullptr;

for (T i : elements)

{

if (i == elements.begin())

{

Head = new LinkedListNode<T>;

Head->Data = i;

temp = Head;

continue;

}

temp->Next = new LinkedListNode<T>;

temp->Next->Prev = temp;

*(temp->Next->Data) = i;

temp = temp->Next;

}

}

template<typename T>

LinkedList<T>::~LinkedList()

{

if (Head == nullptr)return;

LinkedListNode<T>* temppos = Head;

while (temppos != nullptr)

{

Head = Head->Next;

delete temppos;

temppos = Head;

}

}

template<typename T>

void LinkedList<T>::Insert(const T element)

{

if (Head == nullptr)

{

Head = new LinkedListNode<T>;

Head->Data = element;

}

else

{

LinkedListNode<T>* temp = Head;

while (temp->Next != nullptr)

temp = temp->Next;

temp->Next = new LinkedListNode<T>;

temp->Next->Prev = temp;

temp->Next->Data = element;

}

}

template<typename T>

void LinkedList<T>::Insert(const T element, const int i)

{

if (i < 0)return;

else if (i == 0)

{

LinkedListNode<T>* temp = new LinkedListNode<T>;

temp->Data = element;

temp->Next = Head;

Head->Prev = temp;

Head = temp;

}

else

{

LinkedListNode<T>* temppos = Head;

for (int j = 0; j < i - 1; j++)

{

if (temppos == nullptr)

throw std::out_of_range("所取位置超出链表范围。");

temppos = temppos->Next;

}

LinkedListNode<T>* temp = new LinkedListNode<T>;

temp->Data = element;

temp->Next = temppos->Next;

if (temppos->Next != nullptr) temppos->Next->Prev = temp;

temp->Prev = temppos;

temppos->Next = temp;

}

}

template<typename T>

void LinkedList<T>::Remove(const T element)

{

LinkedListNode<T>* temppos = Head;

if (Head->Data == element)

{

if (Head->Next == nullptr)

Head = nullptr;

else

{

Head->Next->Prev = nullptr;

Head = Head->Next;

}

delete temppos;

}

else

{

while (temppos != nullptr)

{

if (temppos->Data == element)

{

if (temppos->Next == nullptr)

temppos->Prev->Next = nullptr;

else

{

temppos->Next->Prev = temppos->Prev;

temppos->Prev->Next = temppos->Next;

}

delete temppos;

return;

}

temppos = temppos->Next;

}

}

}

template<typename T>

void LinkedList<T>::RemoveAll(const T element)

{

LinkedListNode<T>* temppos = Head;

if (Head->Data == element)

{

if (Head->Next == nullptr)

{

Head = nullptr;

return;

}

else

{

Head->Next->Prev = nullptr;

Head = Head->Next;

}

delete temppos;

}

while (temppos != nullptr)

{

if (temppos == Head)

{

if (temppos->Data == element)

{

if (Head->Next == nullptr)

{

Head = nullptr;

return;

}

}

continue;

}

if (temppos->Data == element)

{

if (temppos->Next == nullptr)

temppos->Prev->Next = nullptr;

else

{

temppos->Next->Prev = temppos->Prev;

temppos->Prev->Next = temppos->Next;

}

LinkedListNode<T>* temp = temppos;

delete temp;

}

temppos = temppos->Next;

}

}

template<typename T>

T LinkedList<T>::RemoveAt(const int i)

{

LinkedListNode<T>* temppos = Head;

T temp;

if (i < 0) throw std::out_of_range("所取位置不可小于0。");

else if (i == 0)

{

if (Head->Next != nullptr)Head = Head->Next;

else Head = nullptr;

temp = temppos->Data;

delete temppos;

return temp;

}

else

{

for (int j = 0; j < i - 1; j++)

{

if (temppos == nullptr)

throw std::out_of_range("所取位置超出链表范围。");

temppos = temppos->Next;

}

temppos->Prev->Next = temppos->Next;

if (temppos->Next != nullptr)temppos->Next->Prev = temppos->Prev;

temp = temppos->Data;

delete temppos;

return temp;

}

}

template<typename T>

int LinkedList<T>::Length()

{

int temp = 0;

LinkedListNode<T>* temppos = Head;

while (temppos != nullptr)

{

temp++;

temppos = temppos->Next;

}

return temp;

}

template<typename T>

T& LinkedList<T>::operator[](const int id)

{

LinkedListNode<T>* temppos = Head;

for (int j = 0; j < id; j++)

{

if (temppos == nullptr)

throw std::out_of_range("所取位置超出链表范围。");

temppos = temppos->Next;

}

return temppos->Data;

}

template<typename T>

int  LinkedList<T>::Locate(const T element)

{

LinkedListNode<T>* temppos = Head;

int temp = 0;

while (temppos != nullptr)

{

if (temppos->Data == element) return temp;

temp++;

temppos = temppos->Next;

}

return -1;

}

这些好像也是没啥好说明的,只是我的算法应该效率较低= =。

白兔青柠

数据结构学习笔记——线性表(二)

线性表按存储结构可分为顺序表与链表,还衍生出了有序表。

顺序表(Sequential List)是线性表的顺序存储结构。它使线性表中所有元素依次存储到存储器中一块连续的空间中,表中逻辑顺序相邻的元素,其存储位置也相邻,这称为直接映射。比如创建了一个顺序表,其a1在1001-1004内存空间中,a2就在1005-1008内存空间中。


数组就是典型的顺序表,我的顺序表即是以数组为基础扩展增删改查的功能,可视为增强数组。

代码如下(SequentialList.h):

#pragma once

#include <stdexcept>

#include ...

线性表按存储结构可分为顺序表与链表,还衍生出了有序表。

顺序表(Sequential List)是线性表的顺序存储结构。它使线性表中所有元素依次存储到存储器中一块连续的空间中,表中逻辑顺序相邻的元素,其存储位置也相邻,这称为直接映射。比如创建了一个顺序表,其a1在1001-1004内存空间中,a2就在1005-1008内存空间中。



数组就是典型的顺序表,我的顺序表即是以数组为基础扩展增删改查的功能,可视为增强数组。

代码如下(SequentialList.h):

#pragma once

#include <stdexcept>

#include <initializer_list>

#include "LinearListBase.h"

template<typename T,int capacity>

class SequentialList:public LinearListBase<T>

{

T Data[capacity];

int Count = 0;

public:

SequentialList(){}

SequentialList(const std::initializer_list<T> elements);

//在线性表末尾插入值

void Insert(const T element);

//在线性表的第i个位置插入值

void Insert(const T element, const int i);

//删除最近数据元素(从左向右遍历)

void Remove(const T element);

//删除所有指定数据元素

void RemoveAll(const T element);

//按位置删除数据元素,并返回值

T RemoveAt(const int i);

//返回线性表的长度

int Length();

//取得某个位置的值

T& operator[](const int id);

//按元素值查找元素位置

int Locate(const T element);

};


template<typename T, int capacity>

SequentialList<T,capacity>::SequentialList(const std::initializer_list<T> elements)

{

for (T i : elements) 

{

if (Count >= capacity) return;

Data[Count++] = i;

}

}

template<typename T, int capacity>

void SequentialList<T, capacity>::Insert(const T element)

{

if (Count >= capacity) return;

Data[Count++] = element;

}

template<typename T, int capacity>

void SequentialList<T,capacity>::Insert(const T element, const int i)

{

if (Count >= capacity) return;

if (i == Count) Insert(element);

else if (i > Count) return;

else

{

for (int j = Count; j > i; j--)

Data[j] = Data[j - 1];

Data[i] = element;

Count++;

}

}

template<typename T, int capacity>

void SequentialList<T, capacity>::Remove(const T element)

{

for (int i = 0; i < Count; i++)

if (Data[i] == element)

{

RemoveAt(i);

break;

}

}

template<typename T, int capacity>

void SequentialList<T, capacity>::RemoveAll(const T element)

{

int k = 0;

for (int i = 0; i < Count; i++)

if (Data[i] == element)

Data[k++] = Data[i];

Count = k;

}

template<typename T, int capacity>

T SequentialList<T, capacity>::RemoveAt(const int i)

{

if (i < 0 || i >= Count) throw std::out_of_range("所取位置超出顺序表范围。");

Count--;

T temp = Data[i];

for (int j = i; j < Count; j++)

Data[j] = Data[j + 1];

return temp;

}

template<typename T, int capacity>

int SequentialList<T, capacity>::Length()

{

return Count;

}

template<typename T, int capacity>

T& SequentialList<T, capacity>::operator[](const int id)

{

if (id < 0 || id >= Count) throw std::out_of_range("所取下标超出顺序表范围。");

return Data[id];

}

template<typename T, int capacity>

int SequentialList<T, capacity>::Locate(const T element)

{

for (int i = 0; i < Count; i++)

if (Data[i] == element)

return i;

return -1;

}

白兔青柠

数据结构学习笔记——线性表(一)

线性表(Linear List)是具有相同特性的数据元素的一个有限序列,具有有穷性、一致性、序列性。

数组其实就是最典型的线性表。数组中的元素数量有限,逻辑元素一个接着一个,每个都有下标位置,以及,一切逻辑元素的类型都是相同的。


当然我们还是需要定义一个比数组功能更强大的线性表数据容器。我在初学数据结构的同时也是初学C++,我便用C++来表现线性表。本文重点记录我对数据结构的理解,代码上不做过多叙述。


一个线性表理应具备如下功能:

  1. 它是泛型的,可以适用于多种类型。

  2. 初始化时能够直接指定数据。

  3. 插入元素。

  4. 删除元素。

  5. 取得长度。

  6. 取得某个位置的值。

  7. 按值...

线性表(Linear List)是具有相同特性的数据元素的一个有限序列,具有有穷性、一致性、序列性。

数组其实就是最典型的线性表。数组中的元素数量有限,逻辑元素一个接着一个,每个都有下标位置,以及,一切逻辑元素的类型都是相同的。


当然我们还是需要定义一个比数组功能更强大的线性表数据容器。我在初学数据结构的同时也是初学C++,我便用C++来表现线性表。本文重点记录我对数据结构的理解,代码上不做过多叙述。


一个线性表理应具备如下功能:

  1. 它是泛型的,可以适用于多种类型。

  2. 初始化时能够直接指定数据。

  3. 插入元素。

  4. 删除元素。

  5. 取得长度。

  6. 取得某个位置的值。

  7. 按值查找位置。

于是产生了如下抽象类(LinearListBase.h):

 

#pragma once

template<typename T>

class LinearListBase

{

public:

//在线性表末尾插入值

virtual void Insert(const T element) = 0;

//在线性表的第i个位置插入值

virtual void Insert(const T element, const int i) = 0;

//删除最近数据元素(从左向右遍历)

virtual void Remove(const T element) = 0;

//删除所有指定数据元素

virtual void RemoveAll(const T element) = 0;

//按位置删除数据元素,并返回值

virtual T RemoveAt(const int i) = 0;

//返回线性表的长度

virtual int Length() = 0;

//取得某个位置的值

virtual T& operator[](const int id) = 0;

//按元素值查找元素位置

virtual int Locate(const T element) = 0;

};

做到这些,就基本具备了增删改查的功能。可惜我的C++是初学,还不能够添加上迭代器。

hdw2000
Chrisstarss

数据结构

B站学习课程:【郝斌】-数据结构入门

B站视频链接地址:https://www.bilibili.com/video/av6159200


以下是笔记:


  • 第一节课:

先讲一下本次课程上所有要讲的内容,请看如下信息:

1. 数据结构概述

2. 预备知识

3. 模块一:线性结构

           连续存储[数组]

          ...

B站学习课程:【郝斌】-数据结构入门

B站视频链接地址:https://www.bilibili.com/video/av6159200


以下是笔记:


  • 第一节课:

先讲一下本次课程上所有要讲的内容,请看如下信息:

1. 数据结构概述

2. 预备知识

3. 模块一:线性结构

           连续存储[数组]

           离散存储[链表]

           线性结构的两种常见应用之一 栈

           线性结构的两种常见应用之二 队列

           专题:递归

           1. 1+2+3+4+…100的和

           2. 求介乘

           3. 汉诺塔

           4. 走迷宫

4. 模块二:非线性结构

           树

           图

5. 模块三:查找和排序

           折半查找

           排序(主要讲冒泡和快排)

                 冒泡

                 插入

                 选择

                 快速排序

                 归并排序

6. Java中容器和数据结构的相关知识

           Iterator接口

           map

           哈希表

—————————————————


  • 第一节课:什么叫做数据结构


先讲数据结构概述。

配套书籍:

看书看:《数据结构》(应该是这个,老师没放图片在课上),严蔚敏、吴伟民,两本书。基本上是摘抄的,书上都是伪算法,没有具体程序。

看程序看:高一凡,把上面书里写的算法都直接用程序实现(C、C++)。【西电的】

还有一个人是黄国瑜,都是自己写的,但是没写程序。另一个人写的程序都是错的,就不说了。


数据结构概述

       定义

              我们如何把现实中大量而复杂的问题以特定的数据类型特定的存储结构保存到主存储器(内存)中,以及在此基础上为实现某个功能(比如查找某个元素、删除某个元素、对所有元素进行排序)而执行的相应操作,这个相应的操作也叫算法。

             (第一:个体如何存储,第二:个体和个体的关系如何存储,这两个问题解决了,数据的存储问题就解决了。实际上,特定的数据类型指的就是个体如何存储;特定的存储结构指的就是个体和个体的关系如何存储。)

              数据怎么去存,就是数据结构要研究的。存完之后要对数据进行操作,这个操作就是算法。

              数据结构 = 个体 + 个体的关系

              算法 = 对存储数据的操作

              算法可以分为狭义的算法和广义的算法,从广义上来讲,算法和存储没关系,从狭义上讲,存储数据的方式不同,所执行的算法也不一样。

              算法是依附于存储数据的,存储的方式不一样,算法也就不一样。

       算法

              (在上面的定义里写了),就是在此存储的基础上,为实现某个功能而执行的相应操作,这个操作就是算法。


第一节课完。



  • 第二节课:衡量算法的标准


         算法

              算法就是解题的方法和步骤。

              衡量算法的标准(最主要是前两个):

                     1. 时间复杂度

                              大概程序要执行的次数,而非执行的时间。(机器不一样,执行的时间也就不一样,所以不能按照实际来计算,而是要看程序执行了几次。)

                     2. 空间复杂度

                              算法执行过程中大概所占用的最大内存。

                     3. 难易程度(其他人理解起来的难易度,实际操作时更看重难易度。)

                     4. 健壮性(不要别人给一个非法的输入程序就挂了)

              搞研究最主要的是前两个,如果是应用到具体的程序里面,要编程序、实现算法的时候,第三个是最主要的。


第二节课完。



  • 第三节课:数据结构的特点


           数据结构的地位

                  数据结构是软件中最核心的课程。

学完之后你发现你什么也干不了,哈哈哈哈哈哈哈哈!!!老师学了三年心都快碎了!哈哈哈哈哈哈哈哈!!!!!!!!

不要指望数据结构学完了能做个什么东西出来!~

它属于一个内部课程,虽然做不出什么,但是它会促进你对很多其他课程的学习。

           程序 = 数据的存储 + 数据的操作 + 可以被计算机执行的语言

           所以数据结构学的就是  数据的存储 + 数据的操作 ,和具体的语言关系不大。(学完了和没学也差别不大,哈哈!但是慢慢会显出重要性来,加油!)

           数据结构学习的难度很大,也很重要,好好学!


第三节课完。



  • 第四节课:预备知识_指针_1


     ——学习数据结构有两种学习方法:

                       1. 按照书上的去学。书上都是伪算法,不是程序,也不是程序中的一段代码,学习起来难度大,但相对容易,不过不建议这样学。

                       2. 伪算法知道了,通过一种语言去把它实现,但是难度很大。建议是通过这种方法学习。


         预备知识:

                指针

                      (C语言中的指针,只是数据结构中指针的一部分,还有很大一部分没有讲。)

                结构体

                动态内存的分配和释放

【难度大不代表学不懂!加油!】

学习数据结构,享受学习编程的乐趣!!~


第四节课完。


  • 第五节课:预备知识_指针_1


         预备知识:

                指针

                      指针的重要性:

                             指针是C语言的灵魂。

                      定义

                             地址

                                   内存单元的编号

                                   从0开始的非负整数

                                   范围:0-FFFFFFFF(0 - 4G-1,G是指内存的2G、4G)

——————————————————————————————

补充:

内存是CPU唯一可以访问的大容量的存储设备。内存的问题是软件开发中最核心的问题之一。】

程序运行完,为程序所分配的内存单元全都回收了。回收是指该部分内存被系统回收,不能被其他程序使用了。如果需要使用,要跟系统申请,系统再重新把某个内存单元分配给程序。回收内存单元后,里面的内容不一定会清空,可能之前的数据还存放在那里。

——————————————————————————————

                             指针:

                                    指针就是地址,地址就是指针,是一个概念

                                    指针变量是存放内存单元地址的变量

                                    指针的本质是一个操作受限的非负整数

                      指针的分类

                             1. 基本类型的指针

                             2. 指针和数组的关系



待续




                结构体

                动态内存的分配和释放






像小强一样活着/cp

数据结构C语言版带书签版

《数据结构》(C语言版)是为“数据结构”课程编写的教材,也可作为学习数据结构及其算法的C程序设计的参数教材。
本书的前半部分从抽象数据类型的角度讨论各种基本类型的数据结构及其应用;后半部分主要讨论查找和排序的各种实现方法及其综合分析比较。其内容和章节编排1992年4月出版的《数据结构》(第二版)基本一致,但在本书中更突出了抽象数据类型的概念。全书采用类C语言作为数据结构和算法的描述语言。
  本书概念表述严谨,逻辑推理严密,语言精炼,用词达意,并有配套出版的《数据结构题集》(C语言版),便于教学,又便于自学。
  本书后附有光盘。光盘内容可在DOS环境下运行的以类C语言描述的“数据结构算法动态模...

《数据结构》(C语言版)是为“数据结构”课程编写的教材,也可作为学习数据结构及其算法的C程序设计的参数教材。
本书的前半部分从抽象数据类型的角度讨论各种基本类型的数据结构及其应用;后半部分主要讨论查找和排序的各种实现方法及其综合分析比较。其内容和章节编排1992年4月出版的《数据结构》(第二版)基本一致,但在本书中更突出了抽象数据类型的概念。全书采用类C语言作为数据结构和算法的描述语言。
  本书概念表述严谨,逻辑推理严密,语言精炼,用词达意,并有配套出版的《数据结构题集》(C语言版),便于教学,又便于自学。
  本书后附有光盘。光盘内容可在DOS环境下运行的以类C语言描述的“数据结构算法动态模拟辅助教学软件,以及在Windows环境下运行的以类PASCAL或类C两种语言描述的“数据结构算法动态模拟辅助教学软件”。
  本书可作为计算机类专业或信息类相关专业的本科或专科教材,也可供从事计算机工程与应用工作的科技工作者参考。


资料电子版本 点击这里领取  PDF


CDA数据分析师
W
W
hdw2000

GraphQL学习指南

作者:hdw2000
为希望开始使用GraphQL的前端Web开发人员、后端工程师以及项目或产品经理提供了一条清晰的学习路径。

将先后探索图论、图数据结构和GraphQL类型,之后在实际项目中学习如何为照片共享应用构建schema。《GraphQL学习指南》还介绍了Apollo Client,可用来将GraphQL连接到用户界面。

榴莲煮雨

数据结构第8章测试 排序

第一题、单项选择题(每题1分,5道题共5分)
1、一组记录的关键字序列为{46,79,56,38,40,84},则利用快速排序方法,以第一个记录为枢轴得到的一次划分结果是___C____。
A、{38,40,46,56,79,84} B、{40,38,46,79,56,84}
C、{40,38,46,56,79,84} D、{40,38,46,84,56,79}
2、对于关键字序列{12,13,10,18,60,15,7,20,25,100}用筛选法建堆,必须从关键字为____B___的结点开始。
A、18 B、60
C、15 D、7
3、排序方法中,从未排序序列中挑选元素,将其依次放至已排序序列(初始为空...

第一题、单项选择题(每题1分,5道题共5分)
1、一组记录的关键字序列为{46,79,56,38,40,84},则利用快速排序方法,以第一个记录为枢轴得到的一次划分结果是___C____。
A、{38,40,46,56,79,84} B、{40,38,46,79,56,84}
C、{40,38,46,56,79,84} D、{40,38,46,84,56,79}
2、对于关键字序列{12,13,10,18,60,15,7,20,25,100}用筛选法建堆,必须从关键字为____B___的结点开始。
A、18 B、60
C、15 D、7
3、排序方法中,从未排序序列中挑选元素,将其依次放至已排序序列(初始为空)的一端的方法,称为____C___。
A、插入排序 B、交换排序
C、选择排序 D、归并排序
4、下列序列中,____A____是堆。
A、{12,35,20,60,40,30} B、{100,85,120,38,10,9,36}
C、{1,5,6,24,7,3,4 } D、{38,24,15,20,30,46}
5、对n个记录的序列进行堆排序,最坏情况下的时间复杂度为___B___。
A、O(logn) B、O(nlogn)
C、O(n) D、O(n^2)
第二题、多项选择题(每题2分,5道题共10分)
1、下列方法中,____BC____算法的时间复杂度为O(nlogn)。
A、希尔排序
B、堆排序
C、快速排序
D、简单选择排序
E、直接插入排序
2、下列排序方法中,____BDE____是稳定的排序方法。
A、简单选择排序
B、起泡排序
C、快速排序
D、直接插入排序
E、折半插入排序
3、下列序列中,____AB____是堆。
A、{15,30,22,93,52,71}
B、{15,22,30,52,71,93}
C、{15,52,22,93,30,71}
D、{15,52,22,71,30,93}
4、在下列排序方法中,每一趟排序结束后都能选出一个元素放在其最终位置上的是___ABCE____。
A、简单选择排序
B、起泡排序
C、快速排序
D、直接插入排序
E、堆排序
5、下列排序方法中,空间复杂度为O(1)的排序方法有___ACD_____。
A、堆排序
B、快速排序
C、直接插入排序
D、冒泡排序
第三题、判断题(每题1分,5道题共5分)
1、快速排序的速度在所有排序方法中是最快的,而且所需的附加空间也最少。F
正确 错误
2、在一个大顶堆中,最小元素不一定在最后。T
正确 错误
3、在数据表基本有序时,冒泡排序方法的时间复杂度一定接近O(n)。T
正确 错误
4、由于希尔排序的最后一趟与直接插入排序过程相同,所以前者一定比后者花费的时间多。F
正确 错误
5、在初始数据表为逆序时,冒泡排序所执行的比较次数最多。T
正确 错误

榴莲煮雨

数据结构第7章测试 查找

第一题、单项选择题(每题1分,5道题共5分)
1、对线性表进行折半查找时,要求线性表必须___C____。
A、以顺序方式存储 B、以链式方式存储
C、以顺序方式存储且表中元素按关键字有序排列 D、以链式方式存储且表中元素按关键字有序排列
2、用线性探测法解决冲突问题时,所产生的一系列后继散列地址___A____。
A、可以大于或小于但不能等于原散列地址 B、必须大于或等于原散列地址
C、必须小于或等于原散列地址 D、无具体限制
3、如果要求一个线性表既能较快的查找,又能适应动态变化的要求,可以采用____D___查找方法。
A、折半 B、顺序
C、分块 D、散列
4、有一个有序表{1,3,9,12,32,41,...

第一题、单项选择题(每题1分,5道题共5分)
1、对线性表进行折半查找时,要求线性表必须___C____。
A、以顺序方式存储 B、以链式方式存储
C、以顺序方式存储且表中元素按关键字有序排列 D、以链式方式存储且表中元素按关键字有序排列
2、用线性探测法解决冲突问题时,所产生的一系列后继散列地址___A____。
A、可以大于或小于但不能等于原散列地址 B、必须大于或等于原散列地址
C、必须小于或等于原散列地址 D、无具体限制
3、如果要求一个线性表既能较快的查找,又能适应动态变化的要求,可以采用____D___查找方法。
A、折半 B、顺序
C、分块 D、散列
4、有一个有序表{1,3,9,12,32,41,45,62,75,77,82,95,100}中折半查找值为82的结点时,____C___次比较后查找成功。
A、1 B、2
C、4 D、8
5、高度为5的二叉平衡树至少有___B____个结点。
A、10 B、12
C、15 D、17
第二题、多项选择题(每题2分,5道题共10分)
1、构造散列函数时通常考虑的因素有___ABCD____。
A、计算函数的工作量
B、关键字的长度
C、散列表长
D、关键字的分布情况
2、对于10个元素的有序表进行折半查找,须比较3次方可查找成功的元素在表中的位置有__ACEH_____。
A、1
B、2
C、3
D、4
E、6
F、7
G、8
H、9
3、下列关于n个结点的m阶B树的说法中,正确的是___CDE____。
A、树中每个结点最多有m个关键字
B、树中叶子结点的个数为n+1
C、在B树上进行查找的过程是顺指针找结点和在结点内找关键字交叉进行的过程。
D、树中所有叶子结点都在同一层,并且不带任何信息
E、树中每个结点最多有m-1个关键字
F、树中每个结点最多有m+1个关键字
4、影响散列表的平均查找长度的因素有___ACD____。
A、散列函数
B、散列表长
C、装填因子
D、处理冲突的方法
5、在下列各种查找方法中,平均查找长度与表长有关的查找方法是___BCD____。
A、散列表查找
B、顺序查找
C、折半查找
D、排序树查找
第三题、判断题(每题1分,5道题共5分)
1、散列表的装填因子越小,发生冲突的可能性越大。 F
正确 错误
2、在散列函数H(key)=key mod p中,函数的好坏与p的选择没有任何关系。 F
正确 错误
3、二叉树为二叉排序树的充要条件是,其任意结点的值均大于其左孩子的值且小于其右孩子的值。 F
正确 错误
4、在分块查找中,对索引表的查找既可用顺序查找法,也可用折半查找法。T
正确 错误
5、若散列表的装填因子小于1,则可避免冲突的产生 F
正确 错误

榴莲煮雨

数据结构第6章测试 图

第一题、单项选择题(每题1分,5道题共5分)
1、一个有n个顶点的无向图若是连通图,则至少有___A_____条边。
A、n-1 B、n
C、n+1 D、(n+1)/2
2、无向图的邻接矩阵是一个____A____。
A、对称矩阵 B、零矩阵
C、对角矩阵 D、上三角矩阵
3、图的深度优先遍历算法类似于二叉树的____A____。
A、先序遍历 B、中序遍历
C、后序遍历 D、层序遍历
4、如果从无向图的任意顶点出发进行一次深度优先遍历就能访问到图中所有顶点,则该图一定是_B_______。
A、完全图 B、连通图
C、有回路 D、一棵树
5、对_____D___,用Prim算法求最小生成树较为合适。
A、非连通图 B、...

第一题、单项选择题(每题1分,5道题共5分)
1、一个有n个顶点的无向图若是连通图,则至少有___A_____条边。
A、n-1 B、n
C、n+1 D、(n+1)/2
2、无向图的邻接矩阵是一个____A____。
A、对称矩阵 B、零矩阵
C、对角矩阵 D、上三角矩阵
3、图的深度优先遍历算法类似于二叉树的____A____。
A、先序遍历 B、中序遍历
C、后序遍历 D、层序遍历
4、如果从无向图的任意顶点出发进行一次深度优先遍历就能访问到图中所有顶点,则该图一定是_B_______。
A、完全图 B、连通图
C、有回路 D、一棵树
5、对_____D___,用Prim算法求最小生成树较为合适。
A、非连通图 B、连通图
C、稀疏图 D、稠密图
第二题、多项选择题(每题2分,5道题共10分)
1、如果对无向图G必须进行二次广度优先遍历才能访问到图中所有顶点,则下列说法中正确的是_____ABD___。
A、G肯定不是完全图
B、G肯定不是连通图
C、G中一定有回路
D、G有两个连通分量
2、在拓扑排序中,拓扑序列的第一个顶点一定是___AB_____的顶点。
A、入度为0
B、没有前驱
C、出度为0
D、没有后继
3、下列说法中正确的是____AB____。
A、无向图中的极大连通子图称为连通分量。
B、图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点。
C、图的深度优先搜索中一般要采用队列来暂存刚访问过的顶点。
D、有向图的遍历不能采用广度优先搜索方法。
4、已知一个无向图的邻接矩阵表示,计算第i个顶点的度的方法是___ABCD___。
A、计算邻接矩阵中第i行的元素之和
B、计算邻接矩阵中第i列的元素之和
C、计算邻接矩阵中第i行的非零元个数
D、计算邻接矩阵中第i列的非零元个数
5、下列说法中不正确的有___AB_____。
A、n个顶点的无向连通图的边数为n(n-1)
B、图的广度优先遍历过程是一个递归过程
C、n个顶点的有向完全图的弧数为n(n-1)
D、有向图的强连通分量是有向图的极大强连通子图
第三题、判断题(每题1分,5道题共5分)
1、任何有向图的顶点都可以排成拓扑有序序列,而且拓扑序列不唯一。F
正确 错误
2、Dijkstra算法是按路径长度递增的顺序依次产生从某一固定源点到其他各顶点之间的最短路径。T
正确 错误
3、图的深度优先遍历算法类似于二叉树的先序遍历 T
正确 错误
4、对稀疏图,用Prim算法求最小生成树较为合适 F
正确 错误
5、利用拓扑排序,可检测一个有向图中是否存在环 T
正确 错误

榴莲煮雨

数据结构第5章测试 树和二叉树

第一题、单项选择题(每题1分,5道题共5分)
1、二叉树的第i(i≥1)层上至多有_____B___个结点。
A、2^i B、2^(i-1)
C、i+1 D、2i-1
2、树最适合表示_____C___。
A、有序数据元素 B、无序数据元素
C、元素之间具有分支层次关系的数据 D、元素之间无联系的数据
3、设高度为h的二叉树上只有度为0和度为2的结点,则此类二叉树中所包含的结点数至少为__A______。
A、2h-1 B、2h
C、2h+1 D、h+1
4、具有100个结点的完全二叉树的深度为___B_____。
A、6 B、7
C、8 D、9
5、已知二叉树的后序遍历序列是dabec,中序遍历序列是debac,则它...

第一题、单项选择题(每题1分,5道题共5分)
1、二叉树的第i(i≥1)层上至多有_____B___个结点。
A、2^i B、2^(i-1)
C、i+1 D、2i-1
2、树最适合表示_____C___。
A、有序数据元素 B、无序数据元素
C、元素之间具有分支层次关系的数据 D、元素之间无联系的数据
3、设高度为h的二叉树上只有度为0和度为2的结点,则此类二叉树中所包含的结点数至少为__A______。
A、2h-1 B、2h
C、2h+1 D、h+1
4、具有100个结点的完全二叉树的深度为___B_____。
A、6 B、7
C、8 D、9
5、已知二叉树的后序遍历序列是dabec,中序遍历序列是debac,则它的先序遍历序列是___D_____。
A、acbed B、decab
C、deabc D、cedba
第二题、多项选择题(每题2分,5道题共10分)
1、树可采用的存储结构有____BCD____。
A、顺序结构
B、多重链表
C、二叉链表
D、孩子链表
2、森林的遍历方式有____AB____
A、先序遍历
B、中序遍历
C、后序遍历
D、层序遍历
3、树型结构的特点是:任意一个结点____BC____。
A、可以有多个前驱
B、可以有多个后继
C、只有一个前驱
D、只有一个后继
4、将一个有50个结点的完全二叉树按层序编号(根编号为1),则编号为 25的结点___AD_____。
A、有左孩子
B、有右孩子
C、无左孩子
D、无右孩子
5、用二叉树的___ACD_____序列可唯一的确定一棵二叉树。
A、先序和中序
B、先序和后序
C、后序和中序
D、层序和中序
第三题、判断题(每题1分,5道题共5分)
1、二叉树按某种顺序线索化后,任意结点均有指向其前驱和后继的线索。F
正确 错误
2、n个叶子的Huffman树共有2n-1个结点。T
正确 错误
3、中序遍历中序线索二叉树时不必使用栈。T
正确 错误
4、二叉树的先序遍历序列中,任意一个结点均处在其孩子结点的前面。T
正确 错误
5、一棵树中的叶子结点数目等于与其对应的二叉树中的叶子结点数目。F
正确 错误

LOFTER

让兴趣,更有趣

简单随性的记录
丰富多彩的内容
让生活更加充实

下载移动端
关注最新消息