精华内容
下载资源
问答
  • 第一章 编写一个程序解决选择问题,令k=N/2.得到所编程序对于N的不同值的运行时间 (语法方面很多不熟悉,所以做了相关的笔记注释) ...//为了使用日期时间相关的函数和结构,需要在 C++ 程序中引用 <

    第一章

    1. 编写一个程序解决选择问题,令k=N/2.得到所编程序对于N的不同值的运行时间
      (语法方面很多不熟悉,所以做了相关的笔记注释)
      *选择问题是指 设有一组N个数而要确定其中第K个最大者
      考虑用两种方法实现这个问题
      一种是将N个数读进一个数组里,再通过冒泡排序,以递减顺序将数组排序,然后返回位置k上的元素
      另一种方法是先排序再比较
    #include <iostream>
    #include <ctime>//为了使用日期和时间相关的函数和结构,需要在 C++ 程序中引用 <ctime> 头文件
    #include <cmath>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    
    
    void sort(vector<int> & vec)
    { // bubble sort ascending
      bool sorted = false;
      while (!sorted)
      {
    	sorted = true;
    	for (auto i = 1; i < vec.size(); i++)
    	{
    	  if (vec[i-1]> vec[i])
    	  {
            swap(vec[i],vec[i-1]);//C++中的swap函数:交换函数
    
                                    //好处:不用担心交换变量精度的缺失,无需构造临时变量,不会增加空间复杂度
    
                                    //swap 包含在命名空间std 里面
    
                                    //swap(a,b);(交换两个数)
    
                                    //swap(a[i] = b[j]);(交换两个位置上的变量)
    
     
    		sorted = false;
    	  }
    	}
      }
    }
    
    void sortDec(vector<int> & vec)
    { // bubble sort descending
      bool sorted = false;
      while (!sorted)
      {
    	sorted = true;
    	for (auto i = 1; i < vec.size(); i++)
    	{
    	  if (vec[i-1]< vec[i])
    	  {
            swap(vec[i],vec[i-1]);
    		sorted = false;
    	  }
    	}
      }
    }
    
     int  select1(vector<int>  nums)
    {
      int k = (nums.size()+1)/2;
      sort(nums);
      return nums[k];
    }
    
    
      int  select2(const vector<int> &nums)
    {
    	int k = nums.size()/2;
    	vector<int> topK(nums.begin(), nums.begin() + k);//c.begin();           返回指向容器 最开始位置数据的指针
                                                        //c.end();             返回指向容器最后一个数据单元+1的指针
    	 
    	sortDec(topK);
    	for (auto i = k; i < nums.size(); i++)
    	{
    		if (nums[i] > topK[k-1])
    		{
    			for (auto j = k-2; j >=0 ; j--)
    				if (nums[i] < topK[j])
    				{topK[j+1] = nums[i]; break;}
    				else
    					topK[j+1] = topK[j];
    			if (topK[0] < nums[i])
    				topK[0] = nums[i];
    		}
    	}
    	return topK[k-1];
    }
    
    int main()
    {
      vector<int> nums;
      int selected;
      time_t start, end;//有四个与时间相关的类型:clock_t、time_t、size_t 和 tm。类型 clock_t、size_t 和 time_t 能够把系统时间和日期表示为某种整数。
    
      srand(time(NULL));//srand函数是随机数发生器的初始化函数。
                        //原型:void srand(unsigned seed);
                        //用法:它需要提供一个种子,这个种子会对应一个随机数,
      for (auto numInts = 1000; numInts<=10000; numInts+=1000)
    	  // sizes 1,000, 2,000, 3,000, ...10,000
      {
            nums.resize(numInts);//resize 设置数组大小
            
            start = time(NULL);
            for (auto i = 0; i < 10; i++) // run 10 times
            {
                for (auto j = 0; j < numInts; j++)
                nums[j] = rand()%(2*numInts);//rand函数产生一组随机数,前面需要用srand函数做初始化
                selected = select2(nums); // or selected = select2(nums);
            }
            end = time(NULL);
            cout<<numInts<<"\t"<<difftime(end,start)<<endl;
      }
      return 0;
    }
    
    
    
    1. 字谜游戏
      输入一些由字母构成的二维数组和一个单词表组成。目标是找出字谜中的单词,这些单词可能是水平、垂直或者在对角线上以任何方式放置的。
    #include<iostream>
    #include<fstream>
    #include<string>
    #include<vector>
    #include "matrix.h"
    #include<algorithm>
    
    using namespace std;
    
    const int MAXROWS = 4;
    const int MAXCOLS = 4;
    
    struct Orientation
    {
    	Orientation() : delRow(0), delCol(0) {}
    Orientation operator() (int direction)
      {
        switch (direction)
       {
    	case 0 : delRow = -1; delCol = -1; break;
    	case 1 : delRow = -1; delCol =  0; break;
    	case 2 : delRow = -1; delCol =  1; break;
    	case 3 : delRow = 0; delCol =  -1; break;
    	case 4 : delRow = 0; delCol =   1; break;
    	case 5 : delRow = 1; delCol =  -1; break;
    	case 6 : delRow = 1; delCol =   0; break;
    	case 7 : delRow = 1; delCol =   1; break;
       }
    	return *this;
      }
      int delRow;
      int delCol;
    };
    
    class Puzzle
    {
    public:
    
      
      Puzzle(int numRows, int numCols ) 
    	{ 
    		matrix<char> temp(numRows,numCols);
    		puzzle= temp;
    		initPuzzle();
    	}
    	Puzzle(int numRows , int numCols , vector<string> wordList) : dictionary(wordList)
         { 
    	    matrix<char> temp(numRows,numCols);
    		  puzzle= temp;
    		  initPuzzle();
    	 }
    	void solvePuzzle();
    	void findWords(int startRow, int startCol, Orientation orient);
    private:
       void initPuzzle();
       matrix<char> puzzle;
       vector<string> dictionary;
    };
    
    void Puzzle::initPuzzle()
    {
      puzzle[0][0] = 't';
      puzzle[0][1] = 'h';
      puzzle[0][2] = 'i';
      puzzle[0][3] = 's';
      puzzle[1][0] = 'w';
      puzzle[1][1] = 'a';
      puzzle[1][2] = 't';
      puzzle[1][3] = 's';
      puzzle[2][0] = 'o';
      puzzle[2][1] = 'a';
      puzzle[2][2] = 'h';
      puzzle[2][3] = 'g';
      puzzle[3][0] = 'f';
      puzzle[3][1] = 'g';
      puzzle[3][2] = 'd';
      puzzle[3][3] = 't';
    }
    
    void Puzzle::solvePuzzle()
    {
      Orientation orient;
      for ( auto startRow = 0; startRow < puzzle.numrows(); startRow++)
    	  for ( auto startCol=0; startCol < puzzle.numcols(); startCol++)
    		 for (auto i = 0; i < 8 ; i++)
    			 findWords(startRow,startCol,orient(i));
    }
    
    
    void Puzzle::findWords(int startRow, int startCol, Orientation orient)
    {
      string word ="";
     int row = startRow;
     int col = startCol;
     do
    	 { 
    		 word = word + puzzle[row][col];
    		 if (find(dictionary.begin(), dictionary.end(), word) != dictionary.end())
    			 cout<<word<<" found starting at ("<<startRow<<","<<startCol<<")\n";
    		 row += orient.delRow;
    		 col += orient.delCol;
    	 }  while (row > -1 && col > -1 && row < puzzle.numrows() && col < puzzle.numcols());
    }
    
    int main()
    {
     string diction[] = {"this", "two", "fat", "fats", "at", "wad", "ad", "hat", "that", "his","is","it","ah"} ;
     vector<string> dictionary(diction,diction+ 12);
     Puzzle puzzle(MAXROWS, MAXCOLS, dictionary);
    
      puzzle.solvePuzzle();
    
      return 0;
    }
    
    
    #ifndef MATRIX_H
    #define MATRIX_H
    
    #include <vector>
    #include <initializer_list>
    using namespace std;
    
    template <typename Object>
    class matrix
    {
      public:
        // add default construction function
        matrix(){}
        matrix( int rows, int cols ) : array( rows )
        {
            for( auto & thisRow : array )
                thisRow.resize( cols );
        }
    
        matrix( initializer_list<vector<Object>> lst ) : array( lst.size( ) )
        {
            int i = 0;
            for( auto & v : lst )
                array[ i++ ] = std::move( v );
        }
    
        matrix( const vector<vector<Object>> & v ) : array{ v }
          { } 
        matrix( vector<vector<Object>> && v ) : array{ std::move( v ) }
          { }
        
        const vector<Object> & operator[]( int row ) const
          { return array[ row ]; }
        vector<Object> & operator[]( int row )
          { return array[ row ]; }
    
        int numrows( ) const
          { return array.size( ); }
        int numcols( ) const
          { return numrows( ) ? array[ 0 ].size( ) : 0; }
      private:
        vector<vector<Object>> array;
    };
    
    #endif
    
    展开全文
  • 采用前序后序两个序列来判断二叉树上结点 B 必定是结点 F 的祖先。 在前序序列中某结点的祖先都排在其前。若结点 B 是 F 的祖先,则 B必定在 F 之前。 而在后序序列中,某结点的祖先排在其后,即若结点 B 是 F

    一、选择题

    1.A 2.C 3.C 4.A 5.D 6.A 7.D 8.C 9.D 10.D

    二、填空题

    在这里插入图片描述

    三、判断题

    1. √ 2. √ 3.× 4. √ 5. × 6. √ 7. √ 8. × 9. √ 10. ×

    四、简答题

    1. 答案如下:
      在这里插入图片描述

    2. 采用前序和后序两个序列来判断二叉树上结点 B 必定是结点 F 的祖先。
      在前序序列中某结点的祖先都排在其前。若结点 B 是 F 的祖先,则 B必定在 F 之前。
      而在后序序列中,某结点的祖先排在其后,即若结点 B 是 F 的祖先,则 B 必在 F 之后。
      根据这条规则来判断若结点 B 在前序序列中在 F 之前,在后序序列中又在 F 之后,则它必是结点 F 的祖先

    3. 树的孩子兄弟链表表示法和二叉树二叉链表表示法,本质是一样的,只是解释不同,
      也就是说树(树是森林的特例,即森林中只有一棵树的特殊情况)可用二叉树唯一表示,并可使用二叉树的一些算法去解决树和森林中的问题。
      树和二叉树的区别有三:一是二叉树的度至多为 2,树无此限制;
      二是二叉树有左右子树之分,即使在只有一个分枝的情况下, 也必须指出是左子树还是右子树,树无此限制;
      三是二叉树允许为空,树一般不允许为空(个别书上允许为空)

    4. 在后续线索二叉树中,若节点*p有右线索,则右线索为后继节点;否则,*p节点的后继节点为其双亲节点右子树中最左下的叶子节点。

    五、计算题

    1. 代码如下:
    int LeafNum(CSTree& T)
    {
    	if(T){
    		if(!T->firstchild)
    			return 1+LeafNum(T->nextsibling);
    		else
    			return LeafNum(T->firstchild)+LeafNum(T->nextsibling);
    	}
    	else 
    return 0;
    }
    
    1. //n 个结点的完全二叉树存于一维数组 A 中,本算法据此建立以二叉链表表示的完全二
      叉树
    BiTree Creat(ElemType A[], int i)
    {
    	BiTree tree;
    	if (i<=n)
    	{
    		tree=(BiTree)malloc( sizeof(BiNode)); 
    		tree->element=A[i];
    		if(2*i>n) 
    		{
    			tree->lchild=NULL;
    		}
    		else 
    		{
    			tree->lchild=Creat(A,2*i)}
    		if(2*i+1>n)
    		{
     			tree->rchild=NULL}
    		else
    		{
    			 tree->rchild=Creat(A,2*i+1)}
    	}
    	return (tree)}//Creat
    
    
    1. (1)//删除二叉树代码如下:
    Status DelBTree(BiTree& T)
    {
    	if(T)
    {
    		DelBTree(T->lchild);
    		DelBTree(T->rchild);
    		delete T;
    		return OK;
    	}
    	else
     return ERROR;
    }
    

    (2) //求二叉树中度为1的节点个数

    int NumberOfOneDegree(BTNode *T)//求二叉树中度为1的节点个数 
    {
        int i=0;
        if(NULL != T)
        {
               
               if((NULL!=T->lchild  && NULL==T->rchild) ||(NULL!=T->rchild && NULL ==T->lchild))
                {
                     i=1+NumberOfOneDegree(T->lchild)+NumberOfOneDegree(T->rchild);
                }
                else
                {
                     i=NumberOfOneDegree(T->lchild)+NumberOfOneDegree(T->rchild);
                }
                
        }
        return i;
    }
    

    (3) // 按先序交换二叉树的左右子树

    Status ExchangeBiTree(BiTree& T)
    {
    	BiTree p;
    	if(T){
    		p=T->lchild;
    		T->lchild=T->rchild;
    		T->rchild=p;
    		ExchangeBiTree(T->lchild);
    		ExchangeBiTree(T->rchild);
    	}
    	return OK;
    }
    
    1. 解析如下:
      在这里插入图片描述
    2. 解析如下:
      在这里插入图片描述

    六、说明

    本人已毕业多年,读研时撰写了一份 《数据结构与算法分析(C++语言版)_张琨版 课后习题答案》,每年依旧有大量考研的学弟学妹们来找这份答案,现将其公布在blog上,仅供学术交流,上述解答如有问题,可私信沟通。

    展开全文
  • 书中首先介绍了抽象与分析、数据的抽象等数据结构的基本原理知识,然后结合Python 的特点介绍了容器类、链式结构迭代器、堆栈队列、递归、树;随后,简单介绍了C++语言的知识,并进一步讲解了C++类、C++的动态...

    本书使用Python 和C++两种编程语言来介绍数据结构。全书内容共15 章。书中首先介绍了抽象与分析、数据的抽象等数据结构的基本原理和知识,然后结合Python 的特点介绍了容器类、链式结构和迭代器、堆栈和队列、递归、树;随后,简单介绍了C++语言的知识,并进一步讲解了C++类、C++的动态内存、C++的链式结构、C++模板、堆、平衡树和散列表、图等内容;最后对算法技术进行了总结。每章最后给出了一些练习题和编程练习,帮助读者复习巩固所学的知识。

    本书适合作为高等院校计算机相关专业数据结构课程的教材和参考书,也适合对数据结构知识感兴趣的读者学习参考。

    本书使用Python和C++两种编程语言来介绍数据结构。Python的面向对象特性, 让它成为一种非常适合用来学习数据结构课程的语言。C++的语法比Python更复杂,但是在学习了Python并掌握了基本的编程概念之后,学习C++的语法变得更为容易。

    本书首先介绍了抽象与算法分析、数据的抽象等数据结构的基本原理和知识, 然后结合Python的特点介绍了容器类、链式结构和迭代器、堆栈和队列、递归、树;随后,简单介绍了C++语言的知识,并进一步讲解了C++类、C++的动态内存、C++的链式结构、C++模板、堆、平衡树和散列表、图等内容;最后对算法技术进行了总结。每章末尾给出了一些练习题和编程练习,帮助读者复习巩固所学的知识。

    本书适合作为高等院校计算机相关专业数据结构课程的教材和参考书,也适合对数据结构感兴趣的读者学习参考。

    随书附赠源代码,可在异步社区轻松下载。

    戴维·M. 瑞德(David M. Reed) 美国Capital大学计算机科学系教授,负责教授Python和C++ 编程。他拥有俄亥俄州立大学计算机博士学位。

    约翰·策勒(John Zelle)美国Wartburg 大学数学和计算机系教授。他负责教授Python 程序设计课程,是《Python程序设计(第3版)》一书的作者。

    目 录

    第 1 章 抽象与分析 1

    1.1 概要 1

    1.1.1 大型编程. 1

    1.1.2 前方的道路 2

    1.2 功能的抽象 3

    1.2.1 契约式设计 3

    1.2.2 验证先验条件 6

    1.2.3 自上而下的设计. 9

    1.2.4 记录副作用. 11

    1.3 算法分析. 12

    1.3.1 线性搜索 12

    1.3.2 二分搜索 14

    1.3.3 非正式的算法比较. 15

    1.3.4 算法的正式分析 17

    1.3.5 大O 符号与Θ 符号 21

    1.4 小结 23

    1.5 练习 23

    第 2 章 数据的抽象. 27

    2.1 概要 27

    2.2 抽象数据类型 27

    2.2.1 从数据类型到抽象数据

    类型. 28

    2.2.2 定义抽象数据类型. 28

    2.2.3 实现抽象数据类型. 30

    2.3 抽象数据类型和对象 32

    2.3.1 规范. 32

    2.3.2 实现. 34

    2.3.3 改变存储方式 35

    2.3.4 面向对象的设计和编程. 36

    2.4 抽象数据类型的实例:

    数据集(Dataset) 38

    2.4.1 面向对象设计的过程 38

    2.4.2 定义一个抽象数据

    类型. 39

    2.4.3 实现这个抽象数据类型. 41

    2.5 抽象数据类型的实例:

    有理数(Rational) .42

    2.5.1 运算符重载.42

    2.5.2 有理数(Rational)类44

    2.6 增量开发以及单元测试45

    2.7 小结48

    2.8 练习48

    第3 章 容器类52

    3.1 概要52

    3.2 Python 的列表52

    3.3 顺序集合:扑克牌牌组53

    3.4 有序集合:手牌.56

    3.4.1 创建桥牌的手牌56

    3.4.2 比较扑克牌.58

    3.4.3 扑克牌排序.59

    3.5 Python 里列表的实现61

    3.5.1 基于数组的列表61

    3.5.2 效率分析62

    3.6 Python 的字典(选读) .63

    3.6.1 字典抽象数据类型63

    3.6.2 熟悉Python 字典.64

    3.6.3 字典的实现.65

    3.6.4 扩展示例:马尔可夫链67

    3.7 小结70

    3.8 练习71

    第4 章 链式结构和迭代器.75

    4.1 概要75

    4.2 Python 的内存模型75

    传递参数80

    4.3 链表实现.81

    4.4 链表抽象数据类型的实现.85

    4.5 迭代器95

    4.5.1 Python 的迭代器95

    4.5.2 在链表(LList)里

    添加迭代器.96

    4.5.3 通过Python 的生成器来

    迭代 97

    4.6 基于游标的列表API(选读) . 99

    4.6.1 游标(Cursor)的

    API 99

    4.6.2 Python 的游标列表

    (CursorList) 100

    4.6.3 链式结构的游标列表

    (CursorList) 102

    4.7 链表vs 数组 104

    4.8 小结. 104

    4.9 练习. 105

    第5 章 堆栈和队列 109

    5.1 概要. 109

    5.2 堆栈. 109

    5.2.1 堆栈抽象数据类型 109

    5.2.2 堆栈的简单应用 110

    5.2.3 堆栈的实现 112

    5.2.4 应用程序:处理算术

    方程. 113

    5.2.5 应用程序:语法的处理

    (选读) . 116

    5.3 队列. 119

    5.3.1 队列抽象数据类型 119

    5.3.2 队列的简单应用 120

    5.4 队列的实现. 121

    5.5 应用程序示例:队列的模拟

    (选读) . 123

    5.6 小结. 128

    5.7 练习. 128

    第6 章 递归 133

    6.1 概要. 133

    6.2 递归定义 134

    6.3 简单的递归示例 136

    6.3.1 示例:字符串反转 136

    6.3.2 示例:字谜 137

    6.3.3 示例:快速计算指数. 138

    6.3.4 示例:二分搜索 139

    6.4 递归的分析. 140

    6.5 排序.142

    6.5.1 递归设计:归并排序142

    6.5.2 分析归并排序.144

    6.6 一个“难”题:汉诺塔146

    6.7 小结.149

    6.8 练习.150

    第7 章 树156

    7.1 概要.156

    7.2 树的术语156

    7.3 示例应用程序:表达式树158

    7.4 树的存储方式159

    7.5 应用:二叉搜索树.160

    7.5.1 二分查找属性.160

    7.5.2 实现一个二叉搜索树161

    7.5.3 遍历整个二叉搜索树

    (BST) 166

    7.5.4 二叉搜索树(BST)的

    运行时分析168

    7.6 使用二叉搜索树(BST)来

    实现映射(选读)169

    7.7 小结.171

    7.8 练习.172

    第8 章 为Python 程序员准备的

    C++简介.177

    8.1 概要.177

    8.2 C++的历史和背景178

    8.3 注释、代码块、变量名和

    关键字.182

    8.4 数据类型和变量声明183

    8.5 Include 语句、命名空间

    以及输入/输出186

    8.6 编译.189

    8.7 表达式和运算符优先级191

    8.8 条件语句193

    8.9 数据类型转换196

    8.10 循环语句197

    8.11 数组199

    8.11.1 一维数组199

    8.11.2 多维数组201

    8.11.3 字符数组. 201

    8.12 函数的细节 202

    8.12.1 声明、定义以及原型. 202

    8.12.2 值传递 205

    8.12.3 引用传递. 205

    8.12.4 将数组作为参数传递. 206

    8.12.5 常量参数 208

    8.12.6 默认参数. 208

    8.13 头文件和内联函数 209

    8.14 断言与测试 213

    8.15 变量的作用域以及生命周期. 214

    8.16 Python 程序员编写C++程序

    时的常见错误. 215

    8.17 其他的C++相关话题

    (选读) 216

    8.17.1 C++的Switch 语句. 216

    8.17.2 创建C++的命名空间. 218

    8.17.3 全局变量. 219

    8.18 小结 220

    8.19 练习 220

    第9 章 C++类. 224

    9.1 基本的语法和语义. 224

    9.2 字符串 232

    9.3 文件输入和输出 234

    9.4 运算符重载. 236

    9.5 类变量和方法 242

    9.6 小结. 246

    9.7 练习. 246

    第 10 章 C++的动态内存. 250

    10.1 概要 250

    10.2 C++的指针 254

    10.3 动态数组 259

    10.4 动态内存类 263

    10.4.1 析构函数. 263

    10.4.2 复制构造函数 265

    10.4.3 赋值运算符 268

    10.4.4 完整的动态数组类 270

    10.4.5 引用返回类型 275

    10.5 动态内存错误. 276

    10.5.1 内存泄漏.276

    10.5.2 访问无效内存277

    10.5.3 内存错误总结280

    10.6 小结281

    10.7 练习281

    第 11 章 C++的链式结构285

    11.1 概要285

    11.2 C++链式结构的类286

    11.3 C++链表.288

    11.4 C++链接的动态内存错误.298

    11.5 小结299

    11.6 练习300

    第 12 章 C++模板.302

    12.1 概要302

    12.2 模板方法303

    12.3 模板类.305

    12.3.1 标准模板库的

    vector 类305

    12.3.2 用户定义的模板类.308

    12.4 小结 311

    12.5 练习312

    第 13 章 堆、平衡树和散列表314

    13.1 概要314

    13.2 优先队列和堆.314

    13.2.1 堆排序320

    13.2.2 关于堆和优先队列

    实现的说明320

    13.3 平衡树.321

    13.4 其他的树结构.329

    13.5 散列表.329

    13.6 小结339

    13.7 练习339

    第 14 章 图.343

    14.1 概要343

    14.2 图数据结构344

    14.3 最短路径算法.347

    14.3.1 无权最短路径347

    14.3.2 加权最短路径350

    14.4 深度优先算法.353

    14.5 最小生成树 357

    14.5.1 Kruskal 算法. 358

    14.5.2 不交集数据结构. 358

    14.5.3 Prim 算法 361

    14.6 小结 361

    14.7 练习 362

    第 15 章 算法技术 365

    15.1 概要 365

    15.2 分治算法 365

    15.2.1 分析递归函数 366

    15.2.2 快速排序.368

    15.3 贪心算法372

    15.4 动态规划378

    15.4.1 最长公共子序列379

    15.4.2 记忆化382

    15.4.3 矩阵链乘法382

    15.5 NP 完全问题383

    15.6 小结384

    15.7 练习385

    术语表387

    展开全文
  • } 六、说明 本人已毕业多年,读研时撰写了一份 《数据结构算法分析C++语言版)_张琨版 课后习题答案》,每年依旧有大量考研的学弟学妹们来找这份答案,现将其公布在blog上,仅供学术交流,上述解答如有问题,可...

    一、选择题

    1.D 2.B 3.A B 4.C 5.B 6.C 7.B 8.D 9.D 10.C

    二、填空题

    1. 1 7
    2. 8 59/15
    3. 3.4
    4. 冲突
    5. 949
    6. 小于等于表长的最大素数
    7. 9 3
    8. 拉链法
    9. a[9]
    10. 2

    三、判断题

    1.× 2. × 3. × 4. × 5. × 6. √ 7. × 8. × 9. √ 10. √
    7. 哈希表的结点中可以包含指针,指向其元素
    8. 也可以链式存储

    四、简答题

    1. 答案如下:
      在这里插入图片描述
    2. 二叉排序树如下:
      在这里插入图片描述
    3. 散列表如下:
      在这里插入图片描述
    4. 答案如下:
      在这里插入图片描述
    5. 答案如下:
      在这里插入图片描述

    五、计算题

    1. 【思想】采用循环语句边查找边累计层次n(初始时bt指向根结点,n=1)。当找到关键字为k的结点时返回n;否则返回0,算法如下:
    int level(BSTNode *bt,KeyType k)
    {
    	int n=1;
    	BSTNode *p=bt;
    	while(p && p->key !=k)
    	{
    		if(k<p->key)
    			p=p->lchild;
    		else
    			p=p->rchild;
    		n++;
    	}
    	if(p)
    		return n;
    	return 0;
    }
    
    1. 【思想】对于二叉排序树俩说,其中序遍历序列为一个递增有序序列。因此,对给定的二叉树进行中序遍历,如果始终能保持前一个值比后一个小,则说明该二叉树是一棵二叉排序树。算法如下:
    KeyType predt=-32767;
    int JudgeBST(BSTNode *bt)
    {
    	int b1,b2;
    	if(NULL==bt)
    		return 1;
    	else
    	{
    		b1=JudgeBST(bt->lchild);
    		if(0==b1 || predt>=bt->key)
    			return 0;
    		predt=bt->key;
    		b2=JudgeBST(bt->rchild);
    		return b2;
    	}
    }
    
    1. 【思想】在哈希表中删除关键字为k的记录的过程:先调用SearchHT(ha,p,k)找到关键字k在哈希表中的地址addr,若addr=-1,表示哈希表中不存在这样的关键字,返回0;否则在ha[adr]为头结点的单链表中查找并删除关键字为k的节点,返回1.对应算法如下
    int DeleteHT(HNode *ha[],int p,int k)
    {
    	int adr;
    	HNode *q;
    	SNode *s,*t;
    	adr=SearchHT(ha,p,k);
    	if(adr!=-1)
    	{
    		q=ha[adr];
    		s=q->next;
    		if(s->key==k)
    		{
    			q->next=s->next;
    			free(s);
    		}
    		else
    		{
    			t=s;s=s->next; //t指向*s的前一个结点
    			while(s &&s->key!=k)
    			{
    				t=s;
    				s=s->next;
    			}
    			t->next=s->next;
    			free(s);
    		}
    		return 1;
    	}
    	else
    		retrun 0;
    }
    

    4.哈希表: ha[0…m-1] 存放元素n个, 哈希函数 H(key)=key%p(p<=m), 平方探测法: H=(H(key)+d)%m d= 1,-1,4,-4…
    【思想】建立哈希表的过程:先将表中各节点的关键字清空,使其地址为开放的,然后调用插入算法将给定的关键字依次插入表中,代码如下:

    //将k插入到哈希表
    void InsertHT(HastTable ha,int &n,KeyType k,int p,int m)
    {
    	int i,j,adr,adr1,sign;
    	adr=adr1=k%p;
    	if(ha[adr].key==NULLKEY || ha[adr].key==DELKEY)
    	{
    		ha[adr].key=k;
    		ha[adr].count=1;
    	}
    	else
    	{
    		sign=1;
    		i=j=1;
    		do{
    			adr=(adr1+sign*i*i)%m;
    			if(sign==1)
    				sign=-1;
    			else
    			{
    				sign=1;
    				i++;
    			}
    			j++;
    		}while(ha[adr].key!=NULLKEY &&ha[adr].key!=DELKEY)
    		ha[adr].key=k;
    		ha[adr].count=j;
    	}
    	n++;
    }
    //创建哈希表
    void CreatHT(HashTable ha,KeyType x[],int n,int m,int p)
    {
    	int i,n1=0;
    	//哈希表置初值
    	for(i=0;i<m;i++)
    	{
    		ha[i].key=NULLKEY;
    		ha[i].count=0;
    	}
    	for(i=0;i<n;i++)
    		InsertHT(ha,n1,x[i],p,m);
    }
    
    1. 哈希表: ha[0…m-1] 存放元素n个, 哈希函数 H(key)=key%p(p<=m),
      解决冲突方法:拉链法
      【思想】建立哈希表的过程:先创建表头结点并将next置空,然后调用插入算法将给定的关键字序列依次插入到哈希表中。对应算法如下:
    //将k插入到哈希表
    void InsertHT(HNode * ha[],KeyType k,int p)
    {
    	int adr;
    	HNode *q;
    	SNode *s,*t;
    	adr=k%p;
    	s=(SNode*)malloc(sizeof(SNode));
    	s->key=k;
    	s->next=NULL;
    	q=ha[adr];
    	t=q->next;
    	if(NULL==t)
    		q->next=s;
    	else
    	{
    		while(t->next!=NULL)
    			t=t->next;
    		t->next=s;
    	}
    }
    //创建哈希表
    void CreatHT(HNode * ha[],KeyType x[],int n,int p)
    {
    	int i=0;
    	//哈希表置空
    	for(i=0;i<p;i++)
    	{
    		ha[i]=(HNode*)malloc(sizeof(HNOde));
    		ha[i]->next=NULL;
    	}
    	for(i=0;i<n;i++)
    		InsertHT(ha,x[i],p);
    }
    
    1. 【思想】在哈希表中查找关键字k的过程:根据建表时设定的哈希函数H,计算出关键字k对应的哈希地址adr,若在ha[adr]为头结点的单链表中存在关键字为k的节点,返回adr;否则返回-1。对应算法如下:
    int SearchHT(HNode *ha[],int p,KeyType k)
    {
    	int adr;
    	SNode *q;
    	adr=k%p;
    	q=ha[adr]->next;
    	while(q && q->key!=k)
    		q=q->next;
    	if(NULL==q)
    		return -1;
    	else
    		return adr;
    }
    

    六、说明

    本人已毕业多年,读研时撰写了一份 《数据结构与算法分析(C++语言版)_张琨版 课后习题答案》,每年依旧有大量考研的学弟学妹们来找这份答案,现将其公布在blog上,仅供学术交流,上述解答如有问题,可私信沟通。

    展开全文
  • 数据结构概述 1.数据结构定义: 我们如何把现实中大量而复杂的问题,以特定的数据类型特定的存储结构保存到主存储器(内存)中。 (注:数据结构解决了数据存储的问题,比如要存储一个班级50人的成绩,可以使用...
  • × 主要用于数据压缩 √ 因为三元组表除了存储非零元素值外,还需要存储其行号列号 × × 第一行最后一行都有两个非零元素 × 稀疏矩阵转置后,除行列下标及行列数互换外,还必须确定该元素转置后在新三元组中的...
  • 案例丰富:从应用出发,结合大量实际案例,对概念与算法进行详尽描述,加深学生对数据结构基本概念、原理方法的理解。插图易懂:在阐述基本概念、基本理论和算法原理时,配有丰富的插图,以直观的方式清晰解释复杂...
  • 最小生成树是指在一个无向图连通中求得连通所有点的一条路径,且这条路径的所有边的权值之最小,此时无向图的这个子图便称为最小生成树 Prim算法 prim算法是图论中用来求最小生成树的算法,与Dijkstra最短路算法求...
  • 对于每一个队列数据结构,我们保留一个数组 theRay以及位置 frontback,它们代表队列的两端。我们还要记录实际存在于队列中的元素的个数 currentsize。 操作应该是清楚的。要 enqueue元素x,可将 currentsize...
  • 数据结构算法与应用-c语言描述(清晰版)下载第一部分 预 备 知 识第1章 C + +程序设计大家好!现在我们将要开始一个穿越“数据结构、算法程序”这个抽象世界的特殊旅程,以解决现实生活中的许多难题。在程序开发...
  • 一、选择题 B 2.A 3.B 4.C 5.D 6.A 7.D 8.B 9.D 10.B ...× 广度优先遍历算法适合于有向图无向图 √ 任何一条边计入一个顶点的入度另一个顶点的出度 √ × 最大出度为n × 一个有向图G=(V,E),V={0,
  • 文章目录数据结构算法分析前言一、数据结构概述数据结构相关基本概念1. 数据2. 数据元素3. 数据项4. 数据对象5. 数据结构6. 程序结构7. 数据类型8. 算法基本结构简介1.从集合到结构体2.映射、函数、算法3.线性结构...
  • 建议初学数据结构的同学直接使用C,绝不建议使用Java。C能让你进一步了解底层的代码的实现和算法思想,Java封装太深,让人很容易忽略底层代码(底层代码不容易看到)。对于算法我建议使用C++或是Java,算法侧重思想...
  • 数据、数据元素、数据结构、数据类型的含义分别是什么?数据:对客观事物的符号表示,在计算机科学中是指所有能输入到计算机中并由计算机程序处理的符号的总称。数据元素:数据的基本单位,在计算机程序中通常作为一...
  • 数据结构算法分析

    2021-07-30 01:23:25
    书名数据结构算法分析作者Mark Allen Weiss原作品Data Structures and Algorithm Analysis出版社人民邮电出版社出版时间2007年定价49 元开本16 开ISBN9787115139238数据结构算法分析图书简介编...
  • 贪心选择性质最优子结构性质: (1)贪心选择性质:贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择(贪心选择)来达到,它采用自顶向下的方式将所求问题简化为规模更小的子问题。 (2)最优子...
  • 在DFS中我们已经知道,在DFS中有隐含的搜索树存在,BFS中同样也有(分析题目时用) 分支限界,分为两个剪枝:分支限界。 分支:即可行性剪枝,当遍历到一个点时,判断它是否符合题意,如果不符合,那么则将这个分支...
  • C++ 数据结构——BF算法

    千次阅读 2021-04-02 08:55:10
    BF算法 */ #include <iostream> #include <string> using namespace std; int main() { string s1,s2; cin>>s1>>s2; int i=0,j=0,start=0; while (s1[i]!='\0'&&s2[j]!='\0')...
  • 第二章 算法分析 算法(algorithm)是为求解一个问题需要遵循的、被清楚地指定的简单指令的集合。 本章将讨论 ·如何估计一个程序所需要的时间。 ·如何将一个程序的运行时间从天或年降低到不足一秒。 ·粗心地使用...
  • 数据结构算法与应用 c++语言描述》 第二章 习题 自己默默做题总是没有动力做完,网上查题解好费劲,按序答在此处。希望自己慢慢补充完,其中可能有错误,欢迎大家指出。 你的留言,是我前进的动力!哈哈哈。 p...
  • vector是基本类类型,这意味着不同于C++中的基本数组,vecto可以复制并且其占用的内存可以自动回收(通过其析构函数)。 我们已经讨论了C+基本数组的一些重要特性 数组就是指向一块内存的指针变量:实际的数组的大小...
  • } 六、说明 本人已毕业多年,读研时撰写了一份 《数据结构算法分析C++语言版)_张琨版 课后习题答案》,每年依旧有大量考研的学弟学妹们来找这份答案,现将其公布在blog上,仅供学术交流,上述解答如有问题,可...
  • 本章讨论最简单最基本的三种数据结构。实际上,每一个有意义的程序都将明晰地至少使用一个这样的数据结构,而栈则在程序中总是要间接地用到,而不管你在程序中是否进行了声明。本章将: 介绍抽象数据类型(ADT)的...
  • lowbit 介绍 lowbit操作是求出非负整数x的最后一位1所表示的数值。 原理 假设有一个非负整数x,我们知道x的负数用二进制表示是x取反+1 以121212为例,12=110012 = 110012=1100,−12=0011+1=0100-12 = 0011 + 1 = ...
  • Q城C_858 来自于 微博 2011年12月12日 10:30我刚刚填写了问卷星上的一个问卷(北京大学“数据结构算法实习课”课程调查),大家一起帮忙来填写吧,填写问卷后可免费参与抽奖,赢取苹果iPhone 4!acmicpc 来自于 微博...
  • 文章目录数据结构C++——最短路径之Dijkstra算法和Floyd算法一、最短路径之Dijkstra算法①Dijkstra算法的实现原理②Dijkstra算法的代码实现③测试的完整代码二、最短路径之Floyd算法①Floyd算法的实现原理②Floyd...
  • 30 个重要数据结构和算法完整介绍(建议收藏保存)

    万次阅读 多人点赞 2021-06-07 08:02:06
    数据结构和算法 (DSA)通常被认为是一个令人生畏的话题——一种常见的误解。它们是技术领域最具创新性概念的基础,对于工作/实习申请者有经验的程序员的职业发展都至关重要。话虽如此,我决定在CSDN新星计划挑战...
  • [注] 最优化原理(最优子结构性质) 最优化原理可以这样阐述:一个最优化策略具有这样的性质,不论过去状态决策如何,对前面的决策所形成的状态而言,余下的诸决策必须构成最优策略。简而言之,一个最优化策略的...
  • c++数据结构算法分析、二叉树、打印、算法
  • 按照我下面整理的思路学习,保证能让你大幅提升数据结构算法实践能力! 许多人有这样的疑问,《数据结构算法》理论学习完了,但是做题还是不会;有的同学感觉数据结构算法不知道怎么学习。那看这篇文章就对了...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 125,312
精华内容 50,124
关键字:

数据结构和算法分析c++

c++ 订阅
数据结构 订阅