今天偶然间发现了之前考研电脑的文档, 我想看一看吧,一看我人都傻了,欺负我这个半年没学习数据结构的考研er,这好吗,这不好.于是就想把之前的东西给整理下,以后方便复习.

线性表Linear List

线性表（linear list）是n个具有相同特性的数据元素的有限序列。

线性表是一种在实际中广泛使用的数据结构，

常见的线性表：顺序表、链表、栈、队列、字符串...

顺序表Contiguous List

定义

线性表的顺序存储称为顺序表，用一组地址连续的存储单元依次存储线性表中的数据元素。

即顺序表的两元素不仅逻辑相邻，物理位置也相邻。逻辑顺序与物理顺序相同

在大学学习的过程中使用最多的就是c语言中的数组了吧!

特点

  • 支持随机访问 (即通过元素序号和首地址下标在O(1)时间复杂度内找到该元素)
  • 存储密度高 (即每个节点都存储数据元素)
  • 插入和删除需要移动大量元素 (因为顺序表逻辑上相邻的元素物理上也相邻,修改一个元素则需要变更很多)

顺序表考查角度

解题一般使用暴力解法

枚举法

枚举法是最容易想到的方法，把所有可能的情况都考虑到，然后从中选出符合题目要求的情况，通常使用for循环遍历。

快速排序

对于一个无序的数组可以先通过排序把他变成有序再处理，排序使用快速排序。考试中直接默写快速排序，然后注意调用快速排序时的参数即可。

快排思想

快速排序是一种分治思想，每一轮快排分为两个步骤：

  • ①选择枢值key。

  • ②枢值移动到他的最终位置，左右划分为两个区间，左边区间的所有元素都小于枢值，右边区间的所有元素都大于枢值。

  • 然后对左右区间分别进行快排，不断重复直到当前处理区间元素个数小于等于1（即L>=R）。

快排时间空间复杂度

快速排序的平均时间复杂度是O(nlogn)，平均空间复杂度是O(logn)，是考试中最快的不稳定排序算法，一般要用到排序时都使用快速排序。快速排序的最坏时间复杂度是O(n2)，最坏空间复杂度都是O(logn)，但我们只需要加一个小优化就能避免最坏情况：即随机选择一个元素作为枢值。优化后最坏时间复杂度O(nlogn)，最坏空间复杂度O(logn)。

快排Pseudocode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void Qsort(int A[], L, R){      	//a数组保存数据，L和R是边界
   if (L>=R) return;             	//当前区间元素个数<=1则退出
   int key, i=L, j=R;            	//i和j是左右两个数组下标移动
   把a数组中随机一个元素和A[L]交换  	//快排优化，使得基准值的选取随机 
   key=A[L];                    	//key作为枢值参与比较
   while (i<j){
      while (i<j && A[j]>key)
          j--;
      while (i<j && A[i]<= key) 
          i++;
      if (i<j)
          swap(A[i], A[j]);      //交换A[i]和A[j]
   }
   Swap(A[L], A[i]);  
   Qsort(A, L, i-1);         		//递归处理左区间
   Qsort(A, i+1, R);          	//递归处理右区间
      }

如果我们不满足于暴力解法，就应该想，暴力解法浪费了什么，我们在什么地方可以对他优化，优化一般要使时间或者空间复杂度减小（主要是时间复杂度），比如说题目给的是有序数组，但是我们没有用到有序性，这是有条件没用；或者题目不需要排序，只要求中位数，但是我们对他排序了，超额完成任务，本来可以不做这么多的，这就是浪费。最好的情况就是我们完美的利用了题目的条件，而且又不多做一丁点事，这样的算法一般都更优秀。

折半查找(利用有序性)

思想:

折半查找，也叫二分查找，假设我们在升序数组A[L~R]中查找x，L和R是上下界（即Left和Right），

mid=(L+R)/2，每次把x与A[mid]比较：

如果x>A[mid]，说明x一定不会出现在A[Lmid]，只可能出现在A[mid+1R]，更新L=mid+1；

而如果x<=A[mid]，说明x一定不会出现在A[mid+1R]，只可能出现在A[Lmid]，更新R=mid。

折半查找Pseudocode

1
2
3
4
5
6
7
8
9
10
11
int Binary_Search(int A[], L, R, x){ //A[]和x不一定是int型
   int mid;
   while (L<R){                     	//如果L>R则范围错误
      mid=(L+R)/2;                 	//mid取中间数，向下取整
      if (x<=A[mid]) R=mid;
          else L=mid+1;             	//更新查找范围
   }
   if (A[L]==x) return L;           	//查找成功，返回数组下标L
      else -1;                     	//查找失败
}
// 时间复杂度为O(logn)，空间复杂度为O(1)。

设置多指针后移

例题：

定义距离d = |x – y|，给定2个长度为n的升序数组A、B，x是数组A中的某个元素，y是数组B中的某个元素。请设计一个尽可能高效的算法，计算并输出所有可能的的最小距离D。例如 数组A = {–16, –8, 5, 8, 13}，B ={-2, 0, 2, 6, 10}，则最小距离为1，相应的x=5, y=6, d= |5 – 6|=1。

这是2个升序数组，查找一种最小的情况，可以考虑使用指针后移，设置两个指针（实际上是两个int变量）i和j保存此时正在处理的数组A、B元素的下标，每次只比较A[i]和B[j]，数组A和B都是升序，每次i或j后移都会导致x或y变大，最终要求的是最小的d，所以我们的每次选择i还是j后移的时候原则就是尽量不让d变大，即要让A[i]和b[j]中较小的那个后移。初始时i=j=0, x=-16, y=-2, d=14，A[i]小，应该i后移即i++，这样会缩小x和y的差距，而如果j后移会继续拉大x和y的差距。①如果i++，则x=-8, y=-2，d=6；②如果j++，则x=-16, y=-0，d=16。我们的目的是求出最小的d，所以②这种情况是没意义的，选①情况，每次比较完x和y后把较小的那个值指针后移。最终每一个数组都只会遍历一次，不会回头，所以时间复杂度是O(n)。

链表Linked List

定义

顺序表和链表都是线性表的一种。但链表与顺序表不同的是，他的物理上与逻辑上的机构并不一致。
顺序表的话，逻辑相邻，物理上也是相邻的。所以对于一整块连续的物理地址，当我们进行插入和删除操作的时候就会需要大量的移动元素。
而链表不需要使用地址连续的存储单元，即不需要满足物理与逻辑一致，通过”链”建立数据之间的逻辑关系，当进行插入或删除操作的时候，只需要修改指针即可

特点

  1. 是线性表。线性表能用的方法他都能用，比如归并两个有序序列，所以数组指针后移的方法也可以用到链表中。
  2. 无法随机访问。如果一个方法需要利用随机访问的特性，那就不能用在链表上，比如说折半查找和快速排序。
  3. 只能向后查找，无法回头。比如要求倒数第k个结点，无法从最后一个结点往前查，得转化成正数第x个结点，从前往后查，或者采用前后指针固定间距。

链表考察角度

单链表定义Pseudocode

单链表（data是该节点的权值，一般可以定义成int；next是指向下一个节点的指针，保存的是下一个节点的位置）

1
2
3
4
typedef struct LNode{
          Elemtype data;                   //该节点的权值
          struct LNode *next;              //next指向下一个节点
      }LNode;

双链表定义Pseudocode

双链表（不需要特别记忆，只是比单链表多一个prior指针而已）

1
2
3
4
typedef struct LNode{
          Elemtype data;                   //该节点的权值
          struct LNode *prior,*next;       //prior指向上一个节点
      }LNode;

暴力解法

枚举法，直接处理

​ 链表的一些题目可以先采用最直接易想的方法，比如要改变链表元素顺序的话，可以将需要重排的元素一个一个拆下来重新插入。这些方法一般看起来比较憨，但是容易想到。

​

将链表用数组保存，再处理

​ 可以使用数组保存链表中的结点地址或者直接保存数据，然后再按照数组的做题方法操作即可。注意：①如果题目中求的是处理之后的链表；②如果题目要求空间复杂度为O(1)；这两种情况都不能使用数组保存链表的结点。

链表的优化算法

设置多指针后移

类似于前面的数组多指针后移，在链表中也可以使用这种方法，在数组中每次后移是i++，而链表中则是p=p->next，本质上都是一样的。

例题：

已知两个长度分别为m和n带头节点的升序链表L1和L2，若将它们合并为一个长度为m + n的升序链表，头节点为L3。请设计一个时间和空间上尽可能高效的算法，返回新的头节点L1。要求：

（1）给出算法的基本设计思想。

（2）根据设计思想，采用C或C++语言描述算法，关键之处给出注释。

（3）说明你所设计算法的时间复杂度和空间复杂度。

这是2个升序链表，要合并这两个链表得到新的升序链表，可以考虑使用指针后移，设置两个指针p和q分别保存此时正在处理的链表L1和L2中的结点，每次比较p和q所指结点的权值，把权值较小的那个结点取下来尾插入新的链中，然后对应指针后移一个结点，重复进行直到一条链遍历完，然后把另一条链连在L3末尾，得到的L3就是升序序列。最终每个结点都只会遍历一次，不会回头，所以时间复杂度是O(n+m)。

链表基本操作

取出/删除p指向的结点

有三个节点的简单链表: pre -> p -> post

1
2
3
4
5
6
//取出p指向的结点：
pre->next=post;
p->next=null;                //不写也没关系，之后会改变p->next;
       删除p指向的结点：
pre->next=post;
free(p);                     //不写也没关系，考试不会扣分的

将p结点插入到pre结点后面

有2个节点的简单链表: pre -> post

1
2
3
//p插入pre后面的结点：
p->next=post;
pre->next=p;                 //不写也没关系，之后会改变p->next;

头插法插入p

有2个节点的简单链表: L -> post, 需要将p插入到L和post之间

1
2
p->next=post;
L->next=p;                   //不写也没关系，之后会改变p->next

遍历链表

对于线性表（数组+链表）的遍历，如果表中元素个数确定就用for循环，否则用while循环。

在遍历过程中访问指针p每次都需要后移即p=p->next，不要忘记。

1
2
3
4
5
6
7
8
9
10
11
12
13
//已知元素个数n：
Node* p=L->next;
for (int i=0; i<n; i++){
   visit(p);                              //访问p结点
   p=p->next;
}
       
//不知道元素个数：
Node* p=L->next;
while (p!=null){
   visit(p);                              //访问p结点
   p=p->next;
}