第八周软件工程学习知识总结（《数据结构与算法》《数据科学概论 》）
一.数据结构与算法
第一章、线性表
一.线性表的逻辑结构：n个类型相同数据元素（data element）的有限序列
数据元素可由若干数据项（data item）组成
二.线性表的特点
1.同一性：类型相同
2.有穷性：由有限个数据元素组成
3.有序性：相邻数据元素之间存在着次序
三.有序线性表
一个线性表 (linear list) 是 n 个类型相同数据元素(homogeneous data element) 以线性 (linear, 一维结构) 的方式排列。线性表的元素可以是没有顺序的 (non-ordered) 或是有顺序的 (ordered)；如果是有顺序的线性表，它的顺序可以是递增的 (increasing, 由小而大排序) 或递减的 (decreasing, 由大而小排序)。我们将先介绍有序线性表 (ordered liner list)，且考虑其顺序为递增的。
1.有序线性表的数据可以是整数 (integer)、有理数 (ratioanl number)、实数 (real number)。
2.有序线性表的元素不可以是复数 (complex number)，因为复数不能比较大小，无顺序可言。
3.有序线性表的数据可以是包含学号、姓名、专业、生年月日、入学年月、电邮帐号、手机号的学生数据。学生数据可以依照学号或姓名排序。
有序线性表的存储是一维的空间：
有序线性表的基本操作：
initial(L) : 初始化线性表 L，此时的线性表是空的，没有任何元素。
getSize(L) : 取得线性表 L 的長度，返回元素个数。
getCapacity(L) : 取得线性表 L 的内存容量。(不适合固定数组线性表)
getElem(L, i) : 从 L 取出第 i 个位置的元素 e，i0；返回 e 。
search(L, e) : 搜寻元素 e 在 L 中的位置，若成功，返回 e 的索引 (下标)；否则，返回 -1。
delete(L, e) : 从 L 删除元素 e。搜寻第一个等于 e 的元素位置，假设为 i，将位置 i 之后的元素往前移一个位置，返回 i 的值。若 L 没有任何元素等于 e, 返回 -1。下图 n 为线性表元素个数。
destroy(L) : 将线性表 L 销毁。(不适合固定数组线性表)
clear(L) : 将线性表 L 清空。
is_empty(L) : 检查线性表 L 是否为空表。
使用数组实现有序线性表
在 C 程序语言可使用数组 (array) 实现有序线性表：
固定数组 (fixed-size array):
#define MAXSIZE 100 // 有序线性表元素上限，可以是任何正整数
typedef struct {
ElemType elem[MAXSIZE]; // 元素类型的固定数组
int size; // 有序线性表的元素个数，0 至 MAXSIZE；初始值为 0。
} List;
动态数组 (dynamic array):
#define SEGMENT 50 // 有序线性表元素每段长度
typedef struct {
ElemType *elem; // 元素类型的动态数组指针
int size; // 有序线性表的元素个数，初始值为 0。
int capacity; // 有序线性表内存容量。
} List;
固定数组的有序线性表
有序线性表基本操作介面：
使用 C 程序语言的固定数组 (fixed-size array) 实现有序线性表。
// 初始化线性表 L，将 size设为 0。
void initial(List *L);
// 线性表 L 的長度，返回元素个数，即 size。
int getSize(List L);
// 从 L 取出位置 i 的元素 e, 0i<size，返回 e，否则，返回 -1。
ElemType getElem(List L, int i);
// 搜寻元素 e 在 L 中的位置。若成功，返回 e 的位置；否则，返回 -1。
int search(List L, ElemType e);
// 将元素 e 插入到 L 适当的位置。若成功，返回 e 的位置；
// 否则，返回 -1。
int insert(List *L, ElemType e);
使用 C 程序语言的固定数组 (fixed-size array) 实现有序线性表。
有序线性表基本操作介面：
// 从 L 删除元素 e。若成功，返回 e 原来的位置；否则，返回 -1。
int delete(List *L, ElemType e);
// 将线性表 L 清空。
void clear(List *L);
// 檢查线性表 L 是否為空表。若是空，返回 1；否则，返回 0。
int is_empty(List L);
假设线性表的元素是介于 0 与 99 之间的随机整数，且线性表最多是 100 个元素。写一个 C 程序语言的程序实现固定数组的有序线性表。主程序中，创建两任意长度的线性表 L1 与 L2，打印两个线性表。(1) 将 L1 和 L2 合并 (merge)；若两个表的总元素超过线性表的上限，舍弃超出的 L1 与 L2 元素；打印合并后的线性表。(2) 自 L1 中移除 (remove) 所有 L2 的元素；打印移除后的线性表。
执行代码如下：
运行结果如下
二、数据科学概论
一.Web Scraping
1.Web Scraping介绍：
数据集或API形式中不存在许多数据。许多这些数据存在于互联网上，在我们与之互动的网页中。在不等待提供者创建API的情况下访问这些数据的一种方法是使用一种称为Web Scraping的技术。
Web Scraping允许我们将网页加载到Python中，并提取我们想要的信息。然后，我们可以使用正常的数据分析工具，如pandas和numpy来处理数据。
为了进行Web Scraping，我们需要了解我们正在使用的网页的结构，然后找到一种以合理的方式提取该结构的部分的方法。
当我们了解Web Scraping时，我们将大量使用请求库，它使我们能够下载一个网页，以及美丽的soup库，它使我们能够提取网页的相关部分。
2、为什么要进行web scraping
1.如果只会通过浏览器访问互联网，我们将会丧失许多的可能。尽管浏览器可以很方便处理JavaScript脚本，展示图片，以人类可读的方式处理对象，但是web scraper更适合于收集和处理大量数据。因而，你不用一次只在一个小窗口里浏览一个页面，你可以一次性浏览上千甚至上百万的页面。
2.其次，web scraper还可以做传统搜索引擎做不了的工作。如果你用搜索引擎搜索“去往A市最便宜的航班”,那么你可能得到大量的广告或者是一些航班搜索站点。搜索引擎只知道这些网站的内容页面，却不知道针对具体问题的准确答案。然而一个开发良好的web scraper可以造访若干网站，记录通往A市的航班的价格，最终告诉你购票的最佳时间。
3.有些人可能会问，为什么不使用某些API呢？当然，如果恰好你能找到适合你的API，那再好不过。但是，也有一些原因导致某些你想要的API不存在：
(1)某些你想要获得数据的站点，不提供相应的API
(2)你需要的数据量较小、有限，所以站点管理员不认为这需要一些API
(3)该数据源的管理者，没有相应的基础设施和技术能力进行API的开发
即使存在相应的API，也会存在种种原因使得你的目的不能被满足
3.网络结构（Webpage Structure）
网页以超文本标记语言(HTML)编码. HTML不像Python那样是一种编程语言，但它是一种标记语言，有自己的语法和规则。 当浏览器，如Chrome或Fire fox，下载网页时，它会读取HTML以了解如何呈现网页并显示给您。
二.利用后羿采集器进行网络数据采集
1.实际操作：
进入京东商城采集有关华为手机的所有型号，在搜索栏中键入华为，后点击搜索按钮元素一次，后点击手机分类选项，提取列表中有关华为手机的数据，并进行采集以及导出的数据。