数据结构之第一章 引论 及 课后题答案
程序员文章站
2022-04-26 13:32:19
...
数据结构之第一章 引论 及 课后题答案
写代码许多年，总是觉得浮于表面，不能深入，看大神说研究一下数据结构和算法可以改进不少，所以决定学习一下，课本采用《数据结构与算法分析：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. 选择问题
#include <iostream>
using namespace std;
/************************************************************************/
/* 冒泡排序：
比较相邻的元素。如果第一个比第二个小，就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较
*/
/************************************************************************/
void sort(int* a,int N) //此处取冒泡排序
{
if (a==NULL)
{
cout<<"数组指针为空"<<endl;
return;
}
for (int j=0; j<N-1; j++) //要比较N-1轮
{
for(int i=0;i<N-1-j; i++) //第每进行一轮，就可以少比较一个
{
if(a[i]<a[i+1])
{
int tmp = a[i+1];
a[i+1]=a[i];
a[i] = tmp;
}
}
}
}
//第一种方法，全部排序
void fun1(int *a, int len, int k)
{
sort(a,10); //排序
cout<<"排序结果如下："<<endl;
for (int i=0;i<10;i++)
{
cout<<a[i]<<" ";
}
cout<<endl<<"*********************************"<<endl;
cout<<"排名第"<<k<<"位的数字为:"<<a[k-1]<<endl;
}
//第二种方法，生成k大小的数组，排序，然后把剩下的每个元素都与生成的数组比较
void fun2(int *a, int len, int k)
{
int *K = new int[k]; //生成数组
for (int i=0;i<k;i++) //取a数组中的前k个数据
{
K[i] = a[i];
}
int *dA = new int[len-k]; //用来存放a数组中剩下的元素
int j=0; //dA的下标
for (int i=k; i<len; i++)
{
dA[j]=a[i];
j++;
}
//dA每个元素与K的最后一位比较，小于则不管，大于则插入K的合适位置
for (int i=0;i<len-k;i++)
{
if(dA[i]>K[k-1])
{
for (int x=0;x<k;x++) //在K中判断，一旦发现比dA[i]小的，就挨个后移，然后插入dA[i]
{
if(K[x]<dA[i]) //当dA[i]大于K的第x元素时，k中元素从x处开始逐一后延
{
for (int y=k-1;y>x;y++)
{
K[y]=K[y-1];
}
K[x]=dA[i];
}
}
}
}
cout<<endl<<"第二种方法得出第"<<k<<"位的数字为："<<K[k-1];
delete K;
delete dA;
}
int main()
{
int N[10]={1,4,3,5,6,9,10,33,67,0}; //取N=10
int k=3; //取排名第三的数
fun1(N,10,k);
fun2(N,10,k);
return 0;
}2.字谜问题
#include <iostream>
using namespace std;
/************************************************************************/
/* 比较行列组合，是否完全包含word单词。单词长度肯定是小于等于行列对角线的
字母组合的。
*/
/************************************************************************/
bool isEqual(char *matrixWord, int len, char*word,int wordLen)
{
bool eq = true;
for (int i=0;i<wordLen-1;i++)
{
if (word[i]==0)
{
break;
}
if (word[i]==matrixWord[i]) //挨着每位对比
{
continue;
}else
{
eq=false;
break;
}
}
return eq;
}
int main()
{
char word[4][5]={"this","two","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<wordCount;i++) //每个单词取行列和对角线中去比较
{
for (int row=0;row<rowCount;row++)//获取每行的信息
{
//先比较行的正序和反序
if(isEqual(matrix[row],columCount,word[i],wordLen))
{
cout<<"第"<<row<<"行存在单词："<<word[i]<<endl;
}else
{
char *oppoRow = new char[columCount];//行的倒序组合
for (int j=0;j<columCount;j++)
{
oppoRow[j]=matrix[row][columCount-j-1];
}
if(isEqual(oppoRow,columCount,word[i],wordLen))
{
cout<<"第"<<row<<"行存在单词："<<word[i]<<endl;
}
delete oppoRow;
}
}
for (int colum=0;colum<columCount;colum++)
{
char *col = new char[rowCount]; //存放列字母组合
for (int j=0; j<rowCount;j++)
{
col[j] = matrix[j][colum]; //j行的colum列的字母存放到col中
}
if(isEqual(col,rowCount, word[i],wordLen))
{
cout<<"第"<<colum<<"列存在单词："<<word[i]<<endl;
}else
{
for (int j=0; j<rowCount;j++)
{
col[j] = matrix[rowCount-j-1][colum]; //j行的colum列的字母存放到col中
}
if(isEqual(col,rowCount, word[i],wordLen))
{
cout<<"第"<<colum<<"列存在单词："<<word[i]<<endl;
}
}
delete col;
}
//对角线的数据
char *forwdLine = new char[rowCount]; //正对角线
char *forwdLineOp = new char[rowCount]; //正对角线逆向
char *reverLine = new char[rowCount]; //反对角线
char *reverLineOp = new char[rowCount]; //反对角线逆向
for (int j=0;j<rowCount;j++) //矩阵的行和列数是一样的
{
forwdLine[j]=matrix[j][j];
forwdLineOp[j]=matrix[rowCount-j-1][columCount-j-1];
reverLine[j]=matrix[j][columCount-1-j];
reverLineOp[j] = matrix[rowCount-1-j][j];
}
if (isEqual(forwdLine,rowCount,word[i],wordLen))
{
cout<<"正对角线存在单词："<<word[i]<<endl;
}else if(isEqual(forwdLineOp, rowCount,word[i],wordLen))
{
cout<<"正对角线存在单词："<<word[i]<<endl;
}
if (isEqual(reverLine,rowCount,word[i],wordLen))
{
cout<<"反对角线存在单词："<<word[i]<<endl;
}else if(isEqual(reverLineOp, rowCount,word[i],wordLen))
{
cout<<"反对角线存在单词："<<word[i]<<endl;
}
}
return 0;
}这个程序写的还是有问题的：
1.矩阵要满足下面的条件：行、列、对角线的第一个字母或最后一个字母必须是单词的起始字母，该条件可以从isEqual的实现看出来。要想解决这个问题也很简单，只需要判断行列对角线组成的字符串，是否包含单词就可以了。即isEqual函数使用strstr库函数代替。
2.效率低下的问题，一旦一个矩阵确定了，其行、列、对角线的组合也就确定了，没有必要每个单词进行检测的时候都生成一遍行、列、对角线组合，该正该问题并没什么难度，先不改了。
1问题改正版的代码如下：
#include <iostream>
#include <string.h>
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<wordCount;i++) //每个单词取行列和对角线中去比较
{
for (int row=0;row<rowCount;row++)//获取每行的信息
{
//先比较行的正序和反序
char *oppoRow = new char[columCount+1];//行的倒序组合 为了调用strstr函数，所以必须满足c语言风格的字符串，所以长度为columCount+1。
memset(oppoRow, 0, columCount+1);
//if(isEqual(matrix[row],columCount,word[i],wordLen))
for (int j=0;j<columCount;j++)
{
oppoRow[j]=matrix[row][j];
}
if(strstr(oppoRow,word[i])!=NULL)
{
cout<<"第"<<row<<"行存在单词："<<word[i]<<endl;
}else
{
for (int j=0;j<columCount;j++)
{
oppoRow[j]=matrix[row][columCount-j-1];
}
//if(isEqual(oppoRow,columCount,word[i],wordLen))
if(strstr(oppoRow,word[i])!=NULL)
{
cout<<"第"<<row<<"行存在单词："<<word[i]<<endl;
}
}
}
for (int colum=0;colum<columCount;colum++)
{
char *col = new char[rowCount+1]; //存放列字母组合
memset(col, 0,rowCount+1);
for (int j=0; j<rowCount;j++)
{
col[j] = matrix[j][colum]; //j行的colum列的字母存放到col中
}
//if(isEqual(col,rowCount, word[i],wordLen))
if(strstr(col,word[i])!=NULL)
{
cout<<"第"<<colum<<"列存在单词："<<word[i]<<endl;
}else
{
for (int j=0; j<rowCount;j++)
{
col[j] = matrix[rowCount-j-1][colum]; //j行的colum列的字母存放到col中
}
//if(isEqual(col,rowCount, word[i],wordLen))
if(strstr(col,word[i])!=NULL)
{
cout<<"第"<<colum<<"列存在单词："<<word[i]<<endl;
}
}
delete col;
}
//对角线的数据
char *forwdLine = new char[rowCount+1]; //正对角线
char *forwdLineOp = new char[rowCount+1]; //正对角线逆向
char *reverLine = new char[rowCount+1]; //反对角线
char *reverLineOp = new char[rowCount+1]; //反对角线逆向
memset(forwdLine, 0, rowCount+1);
memset(forwdLineOp, 0, rowCount+1);
memset(reverLine, 0, rowCount+1);
memset(reverLineOp, 0, rowCount+1);
for (int j=0;j<rowCount;j++) //矩阵的行和列数是一样的
{
forwdLine[j]=matrix[j][j];
forwdLineOp[j]=matrix[rowCount-j-1][columCount-j-1];
reverLine[j]=matrix[j][columCount-1-j];
reverLineOp[j] = matrix[rowCount-1-j][j];
}
//if (isEqual(forwdLine,rowCount,word[i],wordLen))
if(strstr(forwdLine,word[i])!=NULL)
{
cout<<"正对角线存在单词："<<word[i]<<endl;
//}else if(isEqual(forwdLineOp, rowCount,word[i],wordLen))
}else if(strstr(forwdLineOp,word[i])!=NULL)
{
cout<<"正对角线存在单词："<<word[i]<<endl;
}
//if (isEqual(reverLine,rowCount,word[i],wordLen))
if(strstr(reverLine,word[i])!=NULL)
{
cout<<"反对角线存在单词："<<word[i]<<endl;
//}else if(isEqual(reverLineOp, rowCount,word[i],wordLen))
}else if(strstr(reverLineOp,word[i])!=NULL)
{
cout<<"反对角线存在单词："<<word[i]<<endl;
}
}
return 0;
}3.递归打印任意实数
该问题的难点是实数的定义，实数包括有理数和无理数，如果只是打印整数的话还是很简单的，但是如果是高精度的无理小数和有理小数就很有难度了。无理小数为无限不循环小数，因为无限，无法实现。如果是有理小数，如果输入过长，超过double的类型所能表示的范围，也很难实现，暂且实现double类型范围内的有理数打印。
实现要全部用递归实现，找不到实现的思路，如果有高手能够实现，还请留言指教。
我的思路是，先将无理数拆分为整数和小数部分，分别对其使用打印正整数的递归函数：
void printDigit(int n) //打印整数
{
if (n>=10) //先打印大于10的部分，如果大于10就一直靠近基础情形（小于10的情形）
{
printDigit(n/10);
}
cout<<n%10; //打印完毕之后，再打印最后的个位数
}然后，再进行拼凑，打印出所有数值，所有代码如下：
#include <iostream>
#include <math.h>
using namespace std;
void printDigit(int n) //打印整数
{
if (n>=10) //先打印大于10的部分，如果大于10就一直靠近基础情形（小于10的情形）
{
printDigit(n/10);
}
cout<<n%10<<flush; //打印完毕之后，再打印最后的个位数
}
void printReal(double data, int numbers) //numbers是小数点后的位数
{
int integ = data;//强制转换，获取整数部分
double decimal = data - integ;
//处理负数
if (data<0)
{
cout<<"-"<<flush;
integ = -integ;
}
//打印整数部分
printDigit(integ);
if(numbers>0) //打印小数点
cout<<"."<<flush;
double factor = 0.5;//四舍五入的因子
for (int i=0;i<numbers;i++)
{
factor = factor/10;
}
decimal = decimal+factor;
int intDec = decimal*pow(10,numbers);
printDigit(intDec);
}
int main()
{
double num;
cin>>num;
printReal(num, 3);
getchar();
return 0;
}这个程序仍有个问题未解决，小数部分转换成整数，是乘以10的n次方，如果小数保留太长，int不能完全存储，就会出现溢出现象，导致数据出现错误。即小数部分不能超过2^32。但是没有想到完美的解决方法，如果有兄弟看到这篇文章，欢迎指教。
4.递归读取文件
读取文件时，当遇到 “#include”时，将路径解析出来，继续加载新的include路径，代码如下：
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#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"<<endl;
exit(0);
}
while (in.getline(buff,LEN).good())
{
if (string(buff).find("#include")!=string::npos)
{
vector<string> strv;
split(string(buff),string("\""), &strv);
string pathtmp = strv[1];
loadAllInclude(pathtmp);
}else
cout<<buff<<endl;
}
in.close();
}
int main()
{
loadAllInclude("e:/main.cpp");
return 0;
}示例文件：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_OBJECT
public:
explicit MainWindow(QWidget *parent = 0);
~MainWindow();
private:
Ui::MainWindow *ui;
};
#endif // MAINWINDOW_H
e:titlebar.h
#ifndef TITLE_BAR
#define TITLE_BAR
class QLabel;
class QPushButton;
class TitleBar : public QWidget
{
Q_OBJECT
public:
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.剩下的数学题，就不做解答了。
上一篇： 【编译原理】第一章引论
推荐阅读