《数据结构》1-5章

《数据结构（C语言版）》严蔚敏编著，第1-5章重点详略

概论

数据结构三要素：数据逻辑结构、存储结构、数据运算

数据的逻辑结构

集合
每个结点有且仅有一个前驱和后继：线性结构
有一个开始结点，多个终端结点：树型结构
每个结点都可以有多个前驱和后继：图形/网状结构。

数据的存储结构

顺序存储
链式存储
索引存储
散列存储

散列存储的思想是构造一个从集合K到存储区域M的函数h（Hash存储）

试题技巧（时间复杂度）

循环主体中的变量参与循环条件的判断

1
2
3

int i=1;
while(i<=n)
    i=i*2;

解说：i乘2的次数正是主体语句的执行次数，因此有2^t<=n，所以T(n)=($\log_2 n$)。此类题应该找出主体语句中与T(n)成正比的循环变量，将之带入条件中进行计算。

循环主体中的变量与循环条件无关

此类题可采用数学归纳法或直接累计循环次数
递归程序一般使用公式进行递推。非递归程序可以直接累计次数。

线性表

线性表在计算机中的存储基本上是采用顺序存储和链式存储两种方式

顺序表

顺序表采用顺序存储的方式存储就称为顺序表
在第i个位置上插入一个新元素，需要移动n-i个元素。在长度为n的顺序表中插入一个元素所需的平均移动次数为：∑i=0-n 在第i个位置上插入一个数的可能性*(n-i)=[1/(n+1)]*[n(n+1)/2]=n/2，即在一个长度为n的顺序表中插入一个元素平均需移动表中的一半元素
在第i个位置上删除一个元素，需要移动n-i-1个元素。在长度为n的顺序表中插入一个元素所需的平均移动次数为：∑i=0-(n-1) 在第i个位置上删除一个数的可能性*(n-i-1)=[1/n]*[n(n-1)/2]=(n-1)/2，即在一个长度为n的顺序表中插入一个元素平均需移动表中大约一半的元素

链式表

用一组任意的存储单元（可以连续也可以不连续）存储线性表的数据元素称为线性链表。其中又分为带头结点的和不带头结点的。头结点的数据域随意，指针域存储指向第一个结点的指针。
每个结点包括两个域：存储数据元素的数据域和存储直接后继存储位置的指针域。
若线性表为空表，则头结点指针域为空。
添加s结点（在指针P指向的结点后添加指针s指向的结点）：s->next=p->next; p->next=s;
删除（删除指针p指向结点的后一位结点）p->next=p->next->next;
从表尾到表头逆向建立单链表：建立一个指针域为空的头结点，建立一个新结点p，p->data中存入数据，p->next = L->next; L->next = p
循环链表：表中最后一个结点的指针域指向头结点，整个链表形成一个环。循环链表和线性链表的操作基本一致，差别仅在于算法中的循环条件不是p或者p->next是否为空，而是它们是否等于头指针。
双向链表：结点中有两个指针域，一个指向直接后继p->next，一个指向直接前趋p->prior

栈

栈是限定仅在表尾进行插入或删除操作的线性表（两端分为栈顶和栈底）后进先出
称top为栈顶指针，其初值指向栈底，即top = base，可作为栈空的标记。每当插入新的栈顶元素时，top++，删除栈顶元素时，top–。

汉诺塔递归

有3个X/Y/Z的塔座，X有n个直径大小不同、从小到大依次编号12…n的圆盘。要求将X上的n个圆盘移到Z上并仍按同样顺序叠排。
局限：

每次只能移动一个圆盘
大圆盘不能压在小圆盘上

思路：
n = 1时，将编号为1的圆盘从X移到Z上即可。
n > 1时，需利用Y作为辅助塔，将n - 1个圆盘从X移到Y上，编号为n的从X移到Z上，再将Y上的n - 1个圆盘移到Z上。

伪代码：
这里用了递归

public void hanoi(int n, char x, char y, char z){
    if(n == 1) move(x, 1, z);//将编号为1的圆盘从x移到z
    else{
        hanoi(n - 1, x, z, y);//将x上编号为1至n-1的圆盘移到y，z作辅助塔
        move(x, n, z)//将编号n的圆盘从x移到z
        hanoi(n - 1, y, x, z);
    }
}

队列

队列只允许在一端进行插入，在另一端进行删除（两端分为队头和队尾）先进先出
双端队列：限定插入和删除操作在表的两端进行的线性表
链队列：队列的链式表示和实现。
- 一个链队列需要两个分别指示队头和队尾的指针
- 空的链队列的判决条件为头指针和尾指针均指向头结点
- 当队列中最后一个元素被删后，队列尾指针也丢失了，因此需对尾指针重新赋值：指向头结点

链队列

循环队列：队列的顺序表示和实现。
顺序循环队列各状态判决：
- 进队：rear = (rear + 1) % n
- 出队：front = (front + 1) % n
- 队空：rear == front
- 队满：(rear + 1) % n == front
- 队长：(rear - front + n) % n