1 数据结构

　　解决问题方法的效率，跟数据的组织方式有关

　　解决问题方法的效率，跟空间的利用效率有关

　　解决问题方法的效率，跟算法的巧妙程度有关

　　数据结构

　　　　数据对象在计算机中的组织方式

　　　　　　逻辑结构

　　　　　　物理存储结构

　　数据对象必定与一系列加在其上的操作相关联

　　完成这些操作所用的方法就是算法

　　抽象数据类型(Abstract Data Type)

　　　　数据类型

　　　　　　数据对象集

　　　　　　数据集合相关联的操作集

　　　　抽象: 描述数据类型的方法不依赖与具体实现

　　　　　　与存放数据的机器无关

　　　　　　与数据存储的物理结构无关

　　　　　　与实现操作的算法和编程语言无关

　　只描述数据对象集和相关操作集是什么, 并不涉及如何做到的问题

2 算法

　　算法

　　　　一个有限指令集

　　　　接受一些输入(或者没有输入)

　　　　产生输出

　　　　一定在有限步骤之后终止

　　　　每一条指令必须

　　　　　　有充分明确的目标, 不可以有歧义

　　　　　　计算机能处理的范围之内

　　　　　　描述应不依赖于任何一种计算机语言以及具体的实现手段

　　判定算法好换的依据-复杂度

　　空间复杂度S(n)

　　时间复杂度T(n)

　　一般来说关注的是最坏情况的复杂度和平均复杂度

　　复杂度的渐进表示法　　　　　　

　　1 < log_n < n <nlog_n < n² <2ⁿ < n!

3 最大子列和

　　最大子列和问题就是, 给定一个数字序列, 求其中按顺序截取的子序列和最大的

　　1) 算法1, 分三层遍历, 第一层遍历序列, 第二层遍历当前之后的, 第三层计算序列的和

　　　　算法1的具体实现

def algo_1(my_list):    max_sum = 0    size = len(my_list)    for i in range(size):        for j in range(i,size):            current_sum = 0            for k in range(i,j+1):                current_sum += my_list[k]            if current_sum >= max_sum:                max_sum = current_sum    print(max_sum)

　　2) 算法2, 分两层遍历, 第一层遍历, 第二计算值

　　　　具体代码如下

def algo_2(my_list):    max_sum = 0    size = len(my_list)    for i in range(size):        current_sum = 0        for j in range(i,size):            current_sum += my_list[j]            if current_sum > max_sum:                max_sum = current_sum    print(max_sum)

　　3) 算法3, 分而治之

　　　　分而治之实现比较复杂

　　　　基本思想就是, 分成两个部分, 求出左边最大的, 求出右边最大的, 求出跨边界最大的, 三者最大的就是最大的

　　　　算法内容是:

　　　　　　先中分, 再中分,不断中分

　　　　　　从最小两个分部开始, 选择最大的值

　　　　　　在联合就近第二小的选择, 处理跨边界, 从边界出发, 得到向左延续的1格, 2格..求出最大的, 右边也是, 然后两个最大的合在一起就是边界最大

　　　　　　不断重复直到最后

　　4) 算法4, 在线处理

　　　　时间复杂度为o(n), 应该是最快的时间复杂度了

　　　　该算法的特点的可以等待输入就可以获得当前序列的最大子序列, 这也是在线处理的由来

　　　　具体的思路是, 抓住子序列的特点的连续的

　　　　要使得连续序列能够增大, 则部分和应该是正数, 当出现负数和式, 需要舍弃值重新计算序列

　　　　具体实现如下

def algo_4(my_list):    max_sum = 0    current_sum = 0    size = len(my_list)    for i in range(size):        current_sum += my_list[i]        if current_sum > max_sum:            max_sum = current_sum        elif current_sum < 0:            current_sum = 0    print(max_sum)

4 线性表

线性结构最简单的就是线性表

4.1 多项式的表示

　　多项式的主要信息有两个, 一个是x的次数, 一个是对应的系数

　　1) 方法1, 数组方式

　　　　数组按照索引的方式, 索引对应x的次数, 系数就存放在对应的数组位置

　　　　优点: 计算十分方便

　　　　缺点: 浪费空间

　　2) 方法2: 二维数组方式

　　　　数组里面再存一个数组, 数组里面存放系数和次数

　　　　为了便于计算, 存储的时候要按照次数按顺序存入

　　　　计算方式:

　　　　　　取出两个多项式的第0项目, 比较系数大小, 如果不相同, 输出大的, 然后获得对应多项式的第1项目, 在比较系数进行运算; 如果相同直接运算输出;

　　　 　优点: 不用存储系数为0的项目, 节省空间

　　3) 方法3: 使用链表存储

　　　　定义一个结构体, 内容有次数, 系数, 下一个指针

　　　　计算方式同方法2

4.2 线性表以及顺序存储

　　一般来说, 线性表的问题都是有两种方式, 要么是数组, 要么是链表

　　线性表: 由类型数据元素构成有序序列的线性结构

　　　　表中元素的个数恒伟线性表的长度

　　　　线性表没有元素时, 称为空表

　　　　表其实位置称为表头, 表结束位置称为表尾

　　线性表的ADT表示

　　(1) 线性表的顺序存储实现

　　　　利用数组的连续存储空间顺序存放线性表的各个元素

　　　　使用数组的方式来构建线性表

　　数据类型表示

typedef struct{	ElementType Data[MAXSIZE];	int Last; }List;List L,*PtrL;

　　线性表的主要操作

　　1) 初始化

List *MakeEmpty(){	List *PtrL;	PtrL = (List *)malloc(sizeof(List));	PtrL->Last = -1;	return PtrL;}

　　2) 查找

int Find(ElementType X, List *PtrL){	int i = 0;	while( i<=PtrL->Last && PtrL->Data[i]!=X )		i++;	if( i> PtrL->Last)		return -1;	else		return i;}

　　　　查找的平均次数是 (n+1)/2

　　　　平均时间性能为 O(n)

　　3) 插入

　　　　在第i(1<=i<=n+1)个位置插入元素X

　　　　对应在数据上, 就是插入到索引 i-1 的位置

　　　　需要遵循的是先移动再插入

　　　　实现为

void Insert(ElementType X, int i, List *PtrL){	int j;	if(PtrL->Last == MAXSIZE-1){		printf("表满了");		return ;	}	if( i < 1 || PtrL->Last+2){		printf("位置不合法");		return ;	}		for(j=PtrL->Last; j>=i-1; j--)		PtrL->Data[j+1] = PtrL->Data[j];	PtrL->Data[i-1] = x;	PtrL->Last++;	return;}

　　4) 删除

　　　　删除第i(1<=i<=n)个元素　　

　　　　后面的元素依次往前移动

　　　　实现

void Delete( int i, List *PtrL){	int j;	if( i <1 || PtrL->Last+1 ){		printf("不存在第%d个元素", i);		return ;	}	for( j=1; j<=PtrL->Last; j++)		PtrL->Data[j-1] = PtrL->Data[j];	PtrL->Last--;	return ;}

　　　　平均移动次数为(n-1)/2

　　　　平均时间性能为O(n)

　　(2) 线性表的链式存储实现　　

　　链式存储不需要物理存储上也是相邻存储

　　元素之间通过指针来链接

　　定义数据结构

typedef struct Node{	ElementType Data;	struct Node *Next;}List;List L, *PtrL;

　　主要的操作实现

　　1) 求表长度

int Length(List *PtrL){	List *p = PtrL;	int j = 0;	while(p){		p = p->Next;		j++	}	return j;}

　　　　时间复杂度为O(n)

　　2) 查找

　　　　按照序号查找

List *FindKth( int K, List *PtrL){	List *p = PtrL;	int i = 1;	while( p != NULL && i < K){		p = p->Next;		i++;	}	if( i==K )		return p;	else		return NULL;}

Mooc数据结构-基础和线性结构