1. 线性表链式存储结构相关操作函数

这是链式存储结构常用的函数操作

（1）建立线性表L

（2）判断线性表是否为空

（3）将线性表清空

（4）取出线性表L中第i个位置的值

（5）查找线性表L中与给定值e相同的元素，成功返回1，失败返回0

（6）在线性表L中第i 个位置插入元素e

（7）删除线性表L中第i个元素

（8）求线性表L的元素个数

（9）求线性表的最大容量

 

 

 

 

Linklist.c文件

#include <stdio.h>
#include <malloc.h>
#include "LinkList.h"

//typedef void LinkList;
//typedef struct _tag_LinkListNode LinkListNode;



typedef struct _tag_LinkList
{
	LinkListNode header;			//	此处结构体嵌套结构体
	int length;

}TLinkList;


//创建线性表链式存储结构
LinkList * LinkList_Create()										//void类型的指针函数
{
	TLinkList * ret = (TLinkList*)malloc(sizeof(TLinkList));		//T结构体类型的指针

	if (ret != NULL)												//确认分配成功
	{
		ret->length = 0;
		ret->header.next = NULL;
	}

	return ret;														//返回了指针的地址


}


//销毁链表的函数

//此处只销毁了头部第一个节点，后边的节点都没有被销毁


void LinkList_Destroy(LinkList* list)					//O(1)
{
	free(list);
}



//清空链表的函数
void LinkList_Clear(LinkList* list)		//O(1)
{
	TLinkList * sList = (TLinkList*)list;			//强制将LinkList类型的指针地址转换成TLinkList类型的地址
	if (sList != NULL)
	{
		sList->length = 0;
		sList->header.next = NULL;
	}
}


//求出线性表的链式存储的长度
int LinkList_Length(LinkList* list)				//O（1）
{
	TLinkList* sList = (TLinkList*)list;			//强制将LinkList类型的指针地址转换为TLinkList类型指针的地址
	int ret = -1;

	if (sList != NULL)
	{
		ret = sList->length;						//取出链表的长度
	}

	return ret;
}


//在线性表链式存储结构中插入节点，此时是将节点node插入在pos节点之后
int LinkList_Insert(LinkList* list, LinkListNode* node, int pos)
{
	TLinkList* sList = (TLinkList*)list;
	int ret = (sList != NULL) && (pos >= 0) && (node != NULL);
	int i = 0;
	if (ret)
	{
		LinkListNode* current = (LinkListNode*)sList;

		for (i = 0; (i < pos) && (current->next != NULL); i++)
		{
			current = current->next;							//当未搜索到pos位置时，搜索current节点的下一个节点，故将其下一个节点的地址赋给current
		}
		
		//找到pos位置之后，将执行下边三步操作
		node->next = current->next;
		current->next = node;

		sList->length++;

	}

	return ret;
}


//获取pos位点的数据
LinkListNode * LinkList_Get(LinkList* list, int pos)		//O(n)   结构体指针函数
{
	TLinkList* sList = (TLinkList*)list;			//将LinkList类型指针的地址强制转换为TLinkList类型的指针地址，并将其赋值给TLinkList类型的sList指针
	LinkListNode * ret = NULL;
	int i = 0;

	if ((sList != NULL) && (0 <= pos) && (pos < sList->length))
	{
		LinkListNode* current = (LinkListNode*)sList;

		for (i = 0; i < pos; i++)
		{
			current = current->next;
		
		}
		ret = current->next;
	}

	return ret;
}

//删除pos点的信息


LinkListNode* LinkList_Delete(LinkList* list, int pos)		//O(n)
{
	TLinkList * sList = (TLinkList*)list;
	LinkListNode * ret = NULL;
	int i = 0;

	if ((sList != NULL) && (0 <= pos) && (pos < sList->length))
	{
		LinkListNode * current = (LinkListNode*)sList;

		for (i = 0; i < pos; i++)
		{
			current = current->next;						//寻找pos位置

		}


		//找到pos位置后进行如下操作

		ret = current->next;
		current->next = ret->next;

		sList->length--;

	}



	return ret;
}


 

 

LinkList.h

 

//#pragma once


#ifndef _LINKLIST_H_
#define _LINKLIST_H_


typedef void LinkList;
typedef struct _tag_LinkListNode LinkListNode;

struct _tag_LinkListNode
{
	LinkListNode* next;

};


//创建链表函数
LinkList * LinkList_Create();

//销毁链表函数
void LinkList_Destroy(LinkList* list);

//清空链表
void LinkList_Clear(LinkList* list);

//求出链表的长度
int LinkList_Length(LinkList* list);

//向链表中插入相应的节点
int LinkList_Insert(LinkList* list, LinkListNode* node, int pos);

//获取链表指定未知的数据
LinkListNode* LinkList_Get(LinkList* list, int pos);

//删除链表指定位置的节点
LinkListNode* LinkList_Delete(LinkList* list, int pos);







#endif // _LINKLIST_H_


 

学过线性代数都知道，先求出秩，根据秩的大小与向量的阶数比较判断出线性是否相关。求秩matlab用rank函数
rank函数格式
rank(A)

求下列矩阵判断是否线性相关并求出极大无关组

>> a1=[1 2 2 3]';
>> a2=[1 4 -3 6]';
>> a3=[-2 -6 1 -9]';
>> a4 = [1 4 -1 7]';
>> a5 = [4 8 2 9]';
>> A=[a1,a2,a3,a4,a5];
>> r=rank(A)

r =

     3

>> 

然后根据线性代数学科中极大无关组定义将阶梯形矩阵求出来，从右边往做取就行了。

化为阶梯形矩阵
[R,j]=rref(A)
A是矩阵
R是简化后的阶梯形
j是主元

>> [R,j]=rref(A)

R =

     1     0    -1     0     4
     0     1    -1     0     3
     0     0     0     1    -3
     0     0     0     0     0


j =

     1     2     4

>> A1=A(:,j)

A1 =

     1     1     1
     2     4     4
     2    -3    -1
     3     6     7

>> 

然后从这里就会发现A1就是它的极大线性无关组。

五、向量组与线性空间

1/4判断某向量是否可由某向量组线性表示

判断矩阵的秩相等

2/4判断某个向量组是否线性相关

R<向量个数，线性相关。R=向量个数，线性无关。

3/4 已知三维向量的一组基底，求某一向量在此基底下的坐标

写线性相关函数，得到方程组，得到系数，系数组即为坐标

4/4求几个行向量的极大无关组

组合成大矩阵，求秩R，写编号，如有调换行，编号跟着调换，前R的编号就组成了极大无关组

六、解方程组

1/6判断方程组解的情况

条件
			
解的情况
		
齐次
			
R(A)=未知数的个数
			
唯一解（零解）
		
R(A)<未知数的个数
			
多个解（零解和多个非零解）
		
非齐次
			
R(A)!=R(A|b)
			
无解
		
R(A)=R(A|b)
			
有解
			
R(A)=R(A|b)=未知数个数
			
一个非零解
		
R(A)=R(A|b)<未知数个数
			
多个非零解
		
 

2/6解方程组

求R(A|b),变换矩阵，将矩阵变回方程组，设(n=未知数个数-R)个未知数，将方程整理成标准型，用n个未知数来替换倒数n个变量

3/6求方程组的通解，特解，基础解系

上一个求得解就是通解，特解：通解中的未知数赋任何值得到的结果为特解，基础解系：通解带系数的向量替换成未知数

4/6已知某方程组的多个特解，求某齐次方程的通解

设未知数n=x的个数-秩，找出n个线性无关矩阵满足给出的通解（利用给出的特解），通解=k1X1+k2X2+...knXn

5/6已知某方程组的多个特解，求某非齐次方程的通解

设未知数n=x的个数-秩，找出n个线性无关矩阵满足给出的通解去掉常数项的格式（利用给出的特解），求矩阵Y，满足通解的格式，通解=Y+k1X1+k2X2+...knXn

6/6判断解集合中线性无关的解向量个数

齐次：未知数个数（列）-R（秩）

非齐次：未知数个数（列）-R（秩）+1

七 方阵对角化及其应用

1/6规范正交化

套公式，中括号，双竖线的含义和计算

2/6求矩阵的特征值

|A-KE|=0,k为特征值，k的个数要等于矩阵的阶数

3/6求矩阵的特征向量

(A-kE)x=0的通解即为特征向量，先求特征向量k，然后带入方程，求该方程的通解

4/6判断方阵是否与对角阵相似/是否满足P-1AP=A

条件
			
结论
		
特征向量个数=阶数
			
相似、满足
		
特征向量个数！=阶数
			
不相似、不满足
		
5/6求方阵对应的对角阵A及可逆变换矩阵P

求特征值，特征向量，对角阵：对角线为特征值，其余为零。

去掉特征矩阵的未知系数，然后规范正交化（重复特征值的放在一起正交化）得到e

P=(e1,e2,,,en)

6/6已知P-1AP=对角矩阵，求关于A的复杂师资

八、二次型

1/6求二次型对应的系数矩阵

 

 

 

线性回归模型是一种比较简单的、容易解释的回归预测方法。在实际应用中，可以用线性回归模型简单判断特征与目标值之间是否存在某种线性相关的关系。若存在，可以用多个线性模型去表示回归值；若不存在，即可以考虑特征与回归值之间的非线性关系（非线性关系可以考虑SVM的核函数映射方式或者神经网络中使用激活函数的方式等，将特征映射到更高维的空间或者表示出非线性的表达式，进行拟合出特征与回归值之间的一种表达形式。这里不做探讨，若有兴趣，请自行查阅相关知识，也可留言，看到即回复。）

1.基本形式

数据集：给定一个由n个属性(或特征),m个样本表示的数据集，其中​表示第i个特征，y表示样本值。

线性模型就是一个通过属性的线性组合来进行预测的函数值，即： 

                                                                                                                          (1)

一般向量的表示为：

                                                                                                                                                          (2)

其中.

2. 损失函数

线性回归预测，希望预测值与真实值之间的差距越小越好，可以用均方误差来评判模型的预测情况。设置均方误差函数为损失函数：

                                                                                                               (3)

基于均方误差最小化进行模型求解参数的方法，称之为“最小化二乘法”。在线性回归中，最小二乘法就是试图找到一条直线，使所有样本到直线上的欧式距离之和最小。

3.参数求解

求解参数“W”和"b"使损失函数最小化的过程，称之为线性回归模型的最下二乘法“参数估计(parameter estimation)” 。损失函数分别就参数“W”和"b"进行求偏导。

                                                                                                       (4)

                                                                                                                  (5)

若该问题为凸优化问题，那么最优点在偏导数为0的点， 既有(4)和(5)为0，求解得到：

                                                                                                                                     (6)

                                                                                                                                                    (7)

其中为x的均值。

将上述过程整理为向量形式：

                                         

其中，n列表示特征列，m行表示第m个样本，n+1列表示对应的回归值。回归值y可以表示为

于是将式子（3）整理为下式：

                                                                                         (8)

对式子(8)求偏导，并令其得到：

                                                                                                                         (9)

                                                                                                                              (10)

用最小二乘法求解参数的过程，涉及计算，当满秩(full-rank matrix)或为正定矩阵(positive definite matrix)时，令式子(9)为0，可得到：

                                                                                                                                            （11）

                                                                                                                                 (12)

此时得到的W估计值是无偏且有效的。线性回归模型为：

                                              (13)

4.一般情况

一般情况下，式子(9)中总不是满秩或者正定矩阵。这种情况下，我们不能再继续使用最小乘估计求解参数的值。常用的解决此类问题的方法有：1）对特征列X或者回归值y进行对数处理，希望经过对数变换后的值，能够满足满秩或者为正定矩阵；2）对损失函数添加正则项L1或者L2，然后使用梯度下降的方法，迭代更新参数，得到损失函数最小得参数。迭代求解参数的过程，并不能得到最优的解，因为此时的估计参数W始终是有偏的。正因为无法得到最优的参数W和最小的损失函数，常采用次优的结果。这时候需要限制迭代次数或者损失函数的阈值，以停止模型一直训练。

对于2），添加正则项L1或者L2的线性回归，分别对应不同的名称：

线性回归添加正则项L1，称之为Lasso回归(Lasso-regression)。python中调用：

#加载Lasso模型算法库
from sklearn.linear_model import Lasso
# 创建Lasso回归模型的对象
reg = Lasso(alpha=0.1)
# 利用训练集训练Lasso回归模型
reg.fit([[0, 0], [1, 1]], [0, 1])
"""
Lasso(alpha=0.1, copy_X=True, fit_intercept=True, max_iter=1000,
normalize=False, positive=False, precompute=False, random_state=None,
selection='cyclic', tol=0.0001, warm_start=False)
"""
# 使用测试集做预测
reg.predict([[1, 1]])

线性回归添加正则项L2，称之为岭回归（Ridge regression）。python中调用：

#加载线性模型算法库
from sklearn.linear_model import Ridge
# 创建岭回归模型的对象
reg = Ridge(alpha=.5)
# 利用训练集训练岭回归模型
reg.fit([[0, 0], [0, 0], [1, 1]], [0, .1, 1]) 
#输出各个系数
reg.coef_
reg.intercept_

线性回归添加正则项L1和L2，称之为Elastic Net回归。python中调用：

#加载ElasticNet模型算法库
from sklearn.linear_model import ElasticNet
#加载数据集
from sklearn.datasets import make_regression
X, y = make_regression(n_features=2, random_state=0)
#创建ElasticNet回归模型的对象
regr = ElasticNet(random_state=0)
# 利用训练集训练ElasticNet回归模型
regr.fit(X, y)
print(regr.coef_) 
print(regr.intercept_) 
print(regr.predict([[0, 0]]))

线性回归模型比较简单，限制条件较多，但是却是一个简单容易判断数据与回归值关系的方法。而且很多非线性回归的方法也在此基础上，得到了发展。例如，添加核函数，将特征X映射到更高维的空间，使得在此空间中，特征与回归值之间满足某种线性关系。比较突出的例子为：SVM中添加多项式核函数和高斯核函数，将非线性的问题转化为线性问题进行解决。线性回归，一般可以用于预测粮食产量和价格之间的关系等。

 

参考文献：

周志华《机器学习》

如何为你的回归问题选择最合适的机器学习方法？