数据结构基础==数据结构与算法2

1、数据处理的基本操作：增、删、查
其中，增和删又可细分为在数据结构中间的增和删，以及在数据结构最后进行增和删，区别在于原始数据的位置是否发生改变。查找又可分为按照位置条件的查找和按照数值特征的查找。

2、线性表结构的增删查

• （1）线性表是 n 个数据的有限序列，最常用的是线性链表，即链表。
• （2）链表有单向链表、循环链表、双向链表、双向循环链表。
• （3）链表新增、删除操作都比较容易，可以在 O(1)的时间复杂度内完成。但查找操作需要 O(n)的时间复杂度，不管是按照位置条件还是数值条件的查找。然而，链表的新增、 删除操作通常都伴随着查找操作。
• （4）当数据的元素个数不确定，且需要经常进行数据的新增和删除时，那么链表会比较合 适。
• （5）线性表案例：
  • ①单向链表的翻转：双指针。
  • ②给定一个奇数个元素的链表，查找出这个链表中间位置的结点的数值：暴力方法、快慢指 针方法。
  • ③判断链表是否有环：快慢指针方法。

3、栈（先进后出的线性表）如何实现增、删、查？

• （1）栈是个限制版的线性表，限制的功能是，只允许数据从栈顶进出。不管是顺序栈（依赖数组）还是链式栈（依赖链表），对于数据的新增操作和删除操作的时间复杂度都是 O(1)，而对于查找操作则需要 O(n)的时间复杂度。
• （2）栈具有后进先出的特性，当面对的问题需要高频使用新增、删除操作，且新增和删除 操作的数据执行顺序具备后来居上的相反顺序时，栈就是个不错的选择。例如：浏览器页面的前进和后退、括号匹配等问题。

4、队列（先进先出的线性表）如何实现增删查？

• （1）队列也是一种加了限制的线性表，它值允许从队尾插入数据，从队头删除数据，通常 有顺序队列（数组方式）和链式队列（链表方式）。队列通常用 front 指针指向队头， 用 rear 指针指向队尾。
• （2）顺序队列有普通队列和循环队列，循环队列可以防止出现“假溢出”问题。
• （3）链式队列的头结点不存放数据，是为了避免当队列为空时 front 和 rear 成为野指针。
• 4）在时间复杂度上，循环队列和链式队列的新增、删除操作都为 O(1)，查找操作为 O(n)。 在空间性能方面，循环队列必须有一个固定的长度，因此存储的元素数量有限制且有时会造成空间浪费，而链式队列则更为灵活一些。
• （5）约瑟夫环可以用循环队列来解决。

5.数组：如何实现基于索引的查找？

• （1）链表、栈、队列都是线性表，而数组可以看成线性表的一种推广，属于另外一种数据 结构。
• （2）数组增删查操作的特点：
  • ①增加：若插入数据在最后，则时间复杂度为 O(1)；若不是， 则时间复杂度为 O(n)。
  • ②删除：对应位置的删除，时间复杂度为 O(n)。
  • ③查找：如果 只根据索引值进行查找，则时间复杂度为 O(1)；
  • 若根据数值条件进行查找，则时间复 杂度为 O(n)。 （3）数组需要在定义时
• （3）数组需要在定义时就确定长度，且在内存中是按顺序存储的；而链表的长度灵活可变， 且在内存中随机存储。
• （4）数组更适合在数据量确定，且较少需要进行数据的增加、删除操作的场景下使用。同 时也更适合在数据对位置敏感的场景下使用。链表对数据的增加、删除操作的时间复 杂度更低。

6.字符串匹配

• （1）字符串是由 n 个字符组成的有序整体，字符串的存储结构与线性表相同，也有顺序存储和链式存储两种。
• （2）字符串增删查的特点：
  • ①增加：和数组非常相似，正常情况下时间复杂度为 O(n)，若在最后插入（也叫连接），则为 O(1)。
  • ②删除：同样是 O(n)和 O(1)。
  • ③查找（字符串匹配），若主串的长度为 n，模式串的长度为 m，则时间复杂度为 O(nm)。
• （3）案例：字符串翻转，给定一个字符串，逐个翻转字符串中每个单词，例如，输入“the sky is blue”，输出“blue is sky the”。

#include 
#include 
#include 

void str_reverse(char *str,char* rev)
{
	int len=strlen(str),i,j,left=0,index;
	for(i=0;i<=len;i++){
		if(str[i]==''||str[i]=='\0'){
			index=len-i;
			for(j=left;j<i;j++){
				rev[index]=str[j];
				index++;//直接越位
			}
			if(left==0)
				rev[index]='\0';
			else
				rev[insex]='';
			left=i+1;//左端设置
		}
	}
}
void main()
{
	char str[]="the sky si blue";
	char* rev=(char*)malloc(strlen(str)+1);
	str_reverse(str,rev);
	printf("The outis:%s\n", rev);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

7.树和二叉树：分支关系与层次结构下，如何有效实现增删查？

• （1）树是由结点和边组成的，不存在环的一种数据结构。

• （2）相关概念：根结点、父结点、子结点、兄弟结点、叶子结点、深度、层。

• （3）二叉树：每个结点最多有两个分支，其中有两个特殊类型：

  • ①满二叉树。
  • ②完全二叉树：除了最后一层外，其他层的结点个数都达到最大，并且最后一层的叶 子结点都靠左排列。
    

• （4）二叉树有两种存储方法：

  • 链式存储法
  • 顺序存储法（下标为 i 的左子结点为 2i，右子 结点为 2i+1）
    

• （5）二叉树的基本操作：

  • ①遍历：前序遍历、中序遍历、后序遍历。时间复杂地为 O(n)。
  • ②增加和删除：时间复杂度位 O(1)==类似链表
    

• （6）二叉查找（搜索）树（BST）

  • ①任意一个结点的的左子树的每个结点的值都小于该结点的值，右子树的每个结点的 值都大于该结点的值。对二叉查找树进行中序遍历，即可输出一个从小到大的有序数据队列。
  • ②二叉查找树的查找操作、插入操作（包含查找位置）的时间复杂度为 O(logn)。
  • ③删除操作比较复杂：
    • a.要删除某个叶子结点，则直接删除，将其父结点指针指向 NULL。
    • b.要删除的结点只有一个子结点，则将其父结点指针指向其子结点的指针。
    • c.要删除的结点有两个子结点，第一种方法是找到这个结点的左子树中的最大结点来替换该结点；第二种方法是找到这个结点的右子树中的最小 结点来替换该结点。

• （7）Trie 树/字典树：根结点不包含字符、其他结点都只包含一个字符；从根结点到某一叶子结点，路径上经过的字符连接起来，即为集合中的某个字符串。

8.哈希表：高效率查找的利器

• （1）哈希表也叫散列表，是一种特殊的数据结构，其核心思想是：如果有一种方法，可以实现”地址” = f(关键字)的映射关系，那么就可以快速完成基于数据的数值查找了。但 哈希表不可避免地会产生哈希冲突，即不同的关键字得到相同的地址。
• （2）常用的设计哈希函数的方法:
  • ①直接定制法：哈希函数为关键字到地址的线性函数，如 H(key) = a * key + b。
  • ②数字分析法：假设关键字集合中的每个关键字 key 都是由 s 位数字组成的，从中提 取分布均匀的若干为组成哈希地址。
  • ③平方取中法：如果关键字的每一位都有重复的数字出现，并且频率很高，就可以先求关键字的平方值，扩大差异，然后取中间几位作为存储地址。
  • ④折叠法：如果关键字的位数很多，可以将关键字分割为几个等长的部分，取它们的 叠加和的值（舍去进位）作为哈希地址。
  • ⑤除留余数法：预先设置一个数 p，然后对关键字进行取余运算，即地址 为 key mod p。
• （3）常用解决哈希冲突的方法：
  • ①开放定址法：当一个关键字和另一个关键字产生冲突时，使用某种探测技术在哈希表中形成一个探测序列，然后沿着这个探测序列一次查找下去，当碰到空的单元时则插入其中。常用的探测方法是线性探测法。
  • ②链地址法：将哈希地址相同的记录存储在一张线性链表中。（拉链法）
• （4）哈希表可以提供非常快速的插入、删除、查找，无论多少数据，插入和删除只需要接 近常量的时间，查找的速度比树还快。但哈希表中的数据没有顺序的概念，同时 key 是不允许重复的。
• （5）在很多高级语言中，哈希函数、哈希冲突都已完成了黑盒化处理，是不需要开发者自 己设计的。