数据结构与算法

绪论

数据结构

形式定义：
- 数据结构是一个四元组 Data_Structure=（D,L,S,O）
  - D是数据元素的有限集
  - L是D上客观存在的关系（逻辑结构）
  - S是关系L在计算机中的存储表示（存储结构）
  - O是D上规定的一组操作。
组成：
- 集合（set）—若干具有共同特征的事物的“聚合”。
- 数据（data) —所有能输入到计算机中的描述客观事物的符号
- 数据元素（data element）—数据的基本单位，也称节点（node）或记录（record）
- 数据项（data item）—有独立含义的数据最小单位，也称域(field)
- 关键码（key）—数据元素中能起标识作用的数据项。
- 关系 —集合中元素之间的某种相关性
逻辑结构
- 线性结构：一对一，线性表、栈、队列等
- 树形结构
- 图状结构
存储结构
- 顺序：借助相对位置表示元素间关系
- 链式：借助指针
- 散列：通过对关键字直接计算

算法

为了解决某类问题而规定的一个有限长的操作序列

特性：有穷、确定、可行、功能性
目标：正确、可读、健壮、高效率与低存储量需求
衡量方法
- 算法的时间特性用执行基本操作次数来度量
- 算法的空间特性用算法运行所需存储量的增长率

线性表、栈与队列

线性结构特点：在数据元素的非空有限集中
- 存在唯一一个称作“第一个”的数据元素
- 存在唯一一个称作“最后一个”的数据元素
- 除第一个外，集合中的每个数据元素均只有一个前驱
- 除最后一个外，集合中的每个数据元素均只有一个后继

线性表

定义：一个线性表是n个数据元素的有限序列
- 元素个数n = 表长度
- a_1 无直接前驱，a_n 无直接后继
- i 为 a_i 再线性表中的位序

顺序存储

逻辑上相邻 - 物理地址相邻

操作
- 插入：复杂度 n/2，算在 i 出的平均移动次数
- 删除：复杂度 (n-1)/2
优点：
- 逻辑相邻，物理相邻
- 可随机存取任一元素
- 存储空间使用紧凑
缺点：
- 插入、删除操作需要移动大量的元素
- 预先分配空间需按最大空间分配，利用不充分
- 表容量难以扩充

链式存储

特点：
- 用一组任意的存储单元存储线性表的数据元素，利用指针实现：用不相邻的存储单元存放逻辑上相邻的元素
- 每个数据元素ai，除存储本身信息外，还需存储其直接后继的信息

单链表

结构：

1
2
3
4
5
6
7
8
9


typedef struct ListNode {
 ElemType data;
 struct ListNode  *next;
 }ListNode,*ListNodePtr;

// 生成新节点
p=(ListNodePtr) malloc ( sizeof ( ListNode ));
// 回收节点
free(p)

操作
- 查找：O(n)
- 插入、删除：O(1)
特点：
- 动态结构，整个存储空间为多个链表共用
- 不需预先分配空间，指针额外存储空间
- 不能随机读取，查找慢

循环链表

表中最后一个结点的指针指向头结点，使链表构成环状

从表中任一结点出发均可找到表中其他结点，提高查找效率

操作与单链表基本一致,循环条件不同：
- 单链表 p 或 p->next=NULL
- 循环链表 p->next=h

双向链表

解决单链表单向性的问题，存储前、后指针

栈

顺序存储

定义：
- 限定仅在表尾进行插入或删除操作的线性表，进行操作的一端称栈顶，固定的一端称栈底，不含元素的空表称空栈。
- 先进后出
操作：
- 用指针 top 始终指向栈顶，初值为 -1 （栈空），终值为 M-1 （栈满）

1
2
3
4
5
6


// 初始化
#define MAXSTACK 100
 typedef struct{
 int top;
 StackEntry entry[MAXSTACK];
 }SqStack;

链式存储

top 始终指向下一个插入的位置，类似

队列

限定只能在表的一端进行插入，在表的另一端进行删除的线性表，先进先出

链式存储

设队首、队尾指针 front 和rear, front 指向头结点，rear 指向队尾

问题：

队列不满时假溢出、队列满时真溢出

解决：

队首固定：需要频繁移动 X
循环队列：将队列设计成环形，让 让sq[0] 接在 sq[M-1] 之后，若 rear == M，则令 rear = 0
- 问题：队空和队满标志一样
- 解决：另设标志位、少用一个元素空间、用一个计数变量

优先队列

不完全遵守先进先出，设有优先级

数组

顺序存储：

需要区分列主序、行主序
Loc (j1, j2, ... , jn )=Loc (0, 0, ... , 0)+(b2*b3*...*bn*j1 + b3*b4*...*bn*j2+ ...+bn*jn-1+ jn)*l

三角矩阵：

三对角矩阵：

稀疏矩阵：

链式存储

表示矩阵：

数组 + 链表

查找、排序、递归

递归

定义：

一个过程或函数出现调用本过程或本函数的成分,称之为递归。
若调用自身,称之为直接递归。若过程或函数p调用过程或函数q,而q又调用 p,称之为间接递归。
如果一个递归过程或递归函数中递归调用语句是最后一条执行语句,则称这种递归调用为尾递归。

查找

顺序表

顺序查找，改变 R[0] 以控制结束：

1
2
3
4
5


int seqsearch(DataType R[], KeyType key){
                  R[0].key=key, i=n;
                  while (R[i].key != key)  i=i-1;
                  return i;
}

折半查找，对于有序表

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


int BinarySearch(DataType SL[], KeyType key, int n){
   //在长度为n的有序表SL中折半查找其关键字等于key的数据元素
   //查找成功返回其在有序表中的位置，查找失败否返回0
	int low=1; 
	int high=n;
	while(low<=high){
	    mid=(low+high)/2;
	    if(key = = SL[mid].key) {return mid;}              
	    else if( key>SL[mid].key) low=mid+1;
	    else high=mid-1;
	}
	return 0;
}

索引表查找
- 基本思想：将原表分成若干块，各块内部不一定有序，但表中的块是“分块有序”的，抽取各块中的最大关键字及其起始位置建立索引表。
- 块间顺序：复杂度 1/2 * (n/s + s) + 1 (n 长度，分成 n/s 块)
- 块间二分：log_2(n/s + 1) + s/2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


int IndexSequelSearch(IndexType ls[], DataType s[], int m, int l, KeyType key){
       //索引表中顺序查找关键字为key的记录。索引表为ls[0]-ls[m-1]
    //顺序表为s，块长为l
    //在索引表中顺序查找
         i=0;
         while(i<m && key>ls [i ].key)i++;  //块间查找
             if(i>=m)return -1;  //查找失败
             else{           //在块内顺序查找
                  j=ls[ i ].Link;
                  while(Key!=s[j].key && j-ls[ i ].Link<l)j++;
                   if(key = = s[j].key)return j;  //查找成功
                   else return -1;  //查找失败
           }
}

哈希表查找
- 以 h(key) 哈希函数 作为 key 的记录在表中的位置，常见构造方法有：
  - 直接哈希：适用于地址集合大小 == 关键字集合大小
  - 数字分析：取随机
  - 平方取中：取关键字平方后的中间几位
  - 折叠：关键字分割后求和
  - 除留取余：除某个不大于哈希表长度的数后取余
  - 随机数：取随机数
- 冲突处理方法：
  - 开放地址：线性探测、平方探测、随机探测再散列
  - 再哈希：将 n 个不同哈希函数排成序列，往下计算
  - 链地址：将关键字发生冲突的记录存储在一个线性链表中
  - 公共溢出：将发生冲突的放在冲突表中
- ALS 影响因素：
  - 选用的哈希函数
  - 冲突处理方法
  - 哈希表饱和度、装载因子 n/m 的大小

排序

基本概念

稳定性：对于任意的数据元素序列，以在排序前后相同关键字数据的相对位置是否改变为依据
内外部：
- 无需借助外存，称内部排序
- 数据量巨大，需要借助外村，称外部排序

插入

直接插入：

1
2
3
4
5


for ( i=2;  i<=n;  ++i )
   if (R[i].key<R[i-1].key) 
     {  在 R[1..i-1]中查找R[i]的插入位置;
         插入R[i] ;
     }

折半插入
- 因为 R[1..i-1] 是一个按关键字有序的有序序列，则可以利用折半查找实现
希尔排序
- 对于n较大而且无序时，直接插入排序效率就较低，这时，如果能将序列分成几个较小的序列，对这些较小的序列先排序，然后再对较长的序列进行排序，可一定程度地提高排序效率。
- 步骤：
  - 先选取一个小于n的整数di（步长），然后把待排序的序列分成di个组
  - 第一趟完成之后，减小步长，再进行分组，再排序，如此知道 d=1

交换

冒泡排序
- 基于两两比较及交换，直到某一趟没有发生数据的交换为止。
- 改进：记下上次交换的位置

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


void Bubble_Sort(DataType R[], int n){
//对长度为n的序列R按升序进行冒泡排序，降序排序类似
for(i=1; i<n; ++i){
swap=0;  //交换标志
for(j=1; j<=n-i; ++j){ // 可以改进成 j<i
		if(R[j].key>R[j+1].key){  不满足升序规则，交换
			R[0]=R[j+1];  R[j+1]=R[j];  R[j]=R[0];
			swap=1;
		}
		if(swap==0) break;  //此趟冒泡没有发生交换，排序结束
}
        }
}