锐客网

  1. 首页 > it技术 > >

数据结构之第一章 引论 及 课后题答案

数据结构之第一章 引论 及 课后题答案 写代码许多年，总是觉得浮于表面，不能深入，看大神说研究一下数据结构和算法可以改进不少，所以决定学习一下，课本采用《数据结构与算法分析：c语言描述》来学习。
第一章主要是介绍了本书的主旨是为了解决什么问题，并简单以选择问题和填字游戏问题做了简单介绍，初次之外对要用到的数学知识（指数、对数、级数、模运算和证明方法）做了一个简要介绍，不至于在后续的学习过程中因为不懂而懵逼。本文的组织形式如下：

  • 知识点总结—思维导图
  • 课后习题练习
知识点总结 知识点的总结，如下图所示：
数据结构之第一章 引论 及 课后题答案
文章图片

简介如下：
选择问题：在N个数中，选择打印出大小排名为k的数。思路有两个，一是将N个数排序，打印第k个数即可。二是在N个数中，随便取k个数放在数组a中，降序排列，然后遍历剩下的N-k个数，每个数都与a[k-1]比较，如果小于a[k-1]则忽略，如果大于a[k-1],则将这个数插入到a中合适的位置，并把a数组顺延，直到最后，得到的数就是要的数值。更有效的方式，书中将在后续给出，此处不做说明。该问题的代码将在课后题1中解答。
找单词：给出N个单词，和一个二维字符数组，每个二维数组的值都是字符，要求按照二维数组的行、列及对角线的值进行拼接，能够找到这N个单词。书中同样给了两个方法来解决这个问题。一是对单词表中每个单词，检查二维数组的每行、列和对角线，验证单词存在不存在。二是获取每行、列对角线的所有字母，判断是否在单词表中。
指数：相乘 底数不变，指数相加； 除法 底数不变，指数相减；阶乘 底数不变，指数相乘；指数相同、底数相同，相加，只把系数相加。公式见上图。
对数：公式见图
级数：公式见图
证明法：书中给出了两个常用证明方法，归纳法和反证法。
递归简介：一个函数用自己来定义时，就是递归的，递归四个准则：
  1. 基准情形：必须总有些基准情况，它无须递归就可以解出结果。
  2. 不断推进：对于需要递归求解的情况，每次递归都要使求解情况向着基准情况推进。
  3. 设计法则
  4. 合成效益法则
课后题答案 1. 选择问题
#include using namespace std; /************************************************************************/ /* 冒泡排序： 比较相邻的元素。如果第一个比第二个小，就交换他们两个。 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。 针对所有的元素重复以上的步骤，除了最后一个。 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较 */ /************************************************************************/ void sort(int* a,int N) //此处取冒泡排序 { if (a==NULL) { cout<<"数组指针为空"<K[k-1]) { for (int x=0; xx; y++) { K[y]=K[y-1]; } K[x]=dA[i]; } } } }cout<

2.字谜问题
#include using namespace std; /************************************************************************/ /* 比较行列组合，是否完全包含word单词。单词长度肯定是小于等于行列对角线的 字母组合的。 */ /************************************************************************/ bool isEqual(char *matrixWord, int len, char*word,int wordLen) { bool eq = true; for (int i=0; i

这个程序写的还是有问题的：
1.矩阵要满足下面的条件：行、列、对角线的第一个字母或最后一个字母必须是单词的起始字母，该条件可以从isEqual的实现看出来。要想解决这个问题也很简单，只需要判断行列对角线组成的字符串，是否包含单词就可以了。即isEqual函数使用strstr库函数代替。
2.效率低下的问题，一旦一个矩阵确定了，其行、列、对角线的组合也就确定了，没有必要每个单词进行检测的时候都生成一遍行、列、对角线组合，该正该问题并没什么难度，先不改了。
1问题改正版的代码如下：
#include #include using namespace std; int main() { char word[4][5]={"this","tw","fat","that"}; //单词表 char matrix[4][4]={//字母矩阵 't','h','i','s', 'w','a','t','s', 'o','a','h','g', 'f','g','d','t' }; int rowCount=4,columCount=4,wordCount=4,wordLen=5; for (int i=0; i

3.递归打印任意实数
该问题的难点是实数的定义，实数包括有理数和无理数，如果只是打印整数的话还是很简单的，但是如果是高精度的无理小数和有理小数就很有难度了。无理小数为无限不循环小数，因为无限，无法实现。如果是有理小数，如果输入过长，超过double的类型所能表示的范围，也很难实现，暂且实现double类型范围内的有理数打印。
实现要全部用递归实现，找不到实现的思路，如果有高手能够实现，还请留言指教。
我的思路是，先将无理数拆分为整数和小数部分，分别对其使用打印正整数的递归函数：
void printDigit(int n)//打印整数 { if (n>=10)//先打印大于10的部分，如果大于10就一直靠近基础情形（小于10的情形） { printDigit(n/10); } cout<

然后，再进行拼凑，打印出所有数值，所有代码如下：
#include #include using namespace std; void printDigit(int n)//打印整数 { if (n>=10)//先打印大于10的部分，如果大于10就一直靠近基础情形（小于10的情形） { printDigit(n/10); } cout<0)//打印小数点 cout<<"."<>num; printReal(num, 3); getchar(); return 0; }

这个程序仍有个问题未解决，小数部分转换成整数，是乘以10的n次方，如果小数保留太长，int不能完全存储，就会出现溢出现象，导致数据出现错误。即小数部分不能超过2^32。但是没有想到完美的解决方法，如果有兄弟看到这篇文章，欢迎指教。
4.递归读取文件
读取文件时，当遇到 “#include”时，将路径解析出来，继续加载新的include路径，代码如下：
#include #include #include #include #define LEN 1024 using namespace std; //分割字符串 void split(std::string& s, std::string& delim,std::vector< std::string >* ret) { size_t last = 0; size_t index=s.find_first_of(delim,last); while (index!=std::string::npos) { ret->push_back(s.substr(last,index-last)); last=index+1; index=s.find_first_of(delim,last); } if (index-last>0) { ret->push_back(s.substr(last,index-last)); } }void loadAllInclude(string path) { char buff[LEN]={0}; ifstream in(path); if(!in.is_open()) { cout<<"file open failed"< strv; split(string(buff),string("\""), &strv); string pathtmp = strv[1]; loadAllInclude(pathtmp); }else cout<

【数据结构之第一章 引论 及 课后题答案】示例文件：e:main.cpp
#include "e:/mainwindow.h"int main(int argc, char *argv[]) { QApplication a(argc, argv); MainWindow w; w.show(); //QStringList numbers; //numbers << "One" << "Two" << "Three" << "Four" << "Five"; //QAbstractItemModel *model = new QStringListModel(numbers); //QTableView *firstTableView = new QTableView; //QTableView *secondTableView = new QTableView; //QTreeView *treeView = new QTreeView; //treeView->setModel(model); //firstTableView->setModel(model); //secondTableView->setModel(model); //secondTableView->setSelectionModel(firstTableView->selectionModel()); //treeView->setSelectionModel(firstTableView->selectionModel()); //firstTableView->show(); //secondTableView->show(); //treeView->show(); //QDesktopServices::openUrl(QUrl("http://blog.csdn.net/liang19890820")); //qDebug()<<"test"; return a.exec(); }

e:mainwindow.h:
#ifndef MAINWINDOW_H #define MAINWINDOW_H #include "e:/titlebar.h"namespace Ui { class MainWindow; }class MainWindow : public QMainWindow { Q_OBJECTpublic: explicit MainWindow(QWidget *parent = 0); ~MainWindow(); private: Ui::MainWindow *ui; }; #endif // MAINWINDOW_H

e:titlebar.h
#ifndef TITLE_BAR #define TITLE_BARclass QLabel; class QPushButton; class TitleBar : public QWidget { Q_OBJECTpublic: explicit TitleBar(QWidget *parent = 0); ~TitleBar(); protected:// 双击标题栏进行界面的最大化/还原 virtual void mouseDoubleClickEvent(QMouseEvent *event); // 进行鼠界面的拖动 virtual void mousePressEvent(QMouseEvent *event); // 设置界面标题与图标 virtual bool eventFilter(QObject *obj, QEvent *event); private slots:// 进行最小化、最大化/还原、关闭操作 void onClicked(); private:// 最大化/还原 void updateMaximize(); private: QLabel *m_pIconLabel; QLabel *m_pTitleLabel; QPushButton *m_pMinimizeButton; QPushButton *m_pMaximizeButton; QPushButton *m_pCloseButton; }; #endif // TITLE_BAR

运行就可以查看加载结果。
5.剩下的数学题，就不做解答了。

    推荐阅读


    上一篇：css3|vue封装checkBox列表组件（实现group和自定义选项，纯css实现效果）

    下一篇：ARM 的Boot与Remap详解