数据结构、算法、线性表总结

一、数据结构

1.存储结构是逻辑结构是映射

2.逻辑结构与存储结构的关系

◼ 存储结构是逻辑结构在计算机中的存储形式

◼ 同一逻辑结构可以对应多种存储结构

◼ 同样的操作在不同的存储结构上，实现方法不同

二、算法

1.递归O()计算：

◼时间复杂度的关系：

O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n3)

◼指数时间的关系为：

O(2^n)<O(n!)<O(nn)

◼最好时间复杂度

算法在最好情况下的时间复杂度

◼ 最坏时间复杂度

算法在最坏情况下的时间复杂度，确定了算法执行时间的上界。

◼ 平均时间复杂度

算法在所有可能情况下，按照输入实例以等概率出现时，算法计算量的加权平均值。

◼更关心最坏情况下和平均情况下的时间复杂度。

◼很多情况下，算法的平均时间复杂度难于确定，通常只考虑最坏情况下的时间复杂度。

3.算法存储空间分析

◼ 算法的空间效率

算法的执行过程中，所占据的辅助空间数量

◼ 空间复杂度

算法在运行过程中临时占用的存储空间的度量

◼一般也是问题规模n的的函数S(n)=O(g(n))

◼算法的时间复杂度与空间复杂度相互影响。

◼好的时间复杂度，可能会导致占用较多存储空间

◼ 通常情况下：

鉴于运算空间较为充足，常以算法的时间复杂度作为算法优劣的衡量指标。

三、线性表

1.顺序

2.链式

3.建立单链表

◼头插法

思路：生成一个空表，不断将新节点插入链表表头

void CreateListF(LinkList *&L, ElemType a[], int n)
{ 	
	LinkList *s;
	int i;
	L = new LNode;
    L->next = NULL; //创建头节点,其next域置为NULL
	for (i=0; i<n; i++) { //循环建立数据节点
		s = new LNode; 
		s->data = a[i]; //创建数据节点*s
		s->next = L->next; //将*s插在原开始节点之前,头节点之后
		L->next = s;
	}
}

链表的节点顺序与逻辑次序相反

◼尾插法

思路：将新节点始终插入链表表尾，需要一个尾指针r

void CreateListR(LinkList *&L, ElemType a[], int n)
{ 
	LinkList *s,*r;
	int i;
	L = new LNode; //创建头节点
	r=L; //r始终指向尾节点,开始时指向头节点
	for (i=0; i<n; i++) { //循环建立数据节点
		s = new LNode;
		s->data = a[i]; //创建数据节点*s
		r->next = s; //将*s插入*r之后
		r = s;
	}
	r->next = NULL; //尾节点next域置为NULL
}

四、栈与队列

◼ 链栈

无需附加头结点，栈顶指针就是链表（即链栈）头指针

五、串

◼ next函数

疑难问题及解决方案
迷宫问题和KMP，以及next函数，一开始并没有看懂，后来在网上找了一些讲解资源，弄懂了
PTA上有一些对一半的题，通过和同学作业的对比，找出了问题，改正了过来