数据结构学习(一)-爱代码爱编程
数据结构
数据结构包括线性结构和非线性结构。
常见的线性结构:数组、队列、链表、栈。
非线性结构:二维数组,多维数组,广义表,树结构,图结构。
稀疏数组
二维数组 ↔ \leftrightarrow ↔稀疏数组 ↔ \leftrightarrow ↔数据存储
数组类型 | row | col |
---|---|---|
二维数组 | m | n |
稀疏数组 | sum+1 | 3 |
稀疏数组:
row | col | value |
---|---|---|
m | n | sum |
i | j | val |
其中sum为二维数组中非零的元素个数 |
队列
数组实现
一维数组实现循环队列方法:
//指针初始化
int front=rear=0; //rear指向数据后一位
//入队:
rear=(rear+1)%maxSize;
//出队:
front=(front+1)%maxSize;
//显示队列时计算队列长度:
length=(rear+maxSize-front)%maxSize;
//判断队列是否已满
boolean (rear+1)%maxSize==front;
//判断队列是否为空
boolean rear==front;
空一个空间作为约定,即实际可入队列长度为:maxSize-1。
链表实现
链表
单链表
单链表反转:
//从head头中删除temp节点
head.next=temp.next;
//将temp节点添加到rehead头中。方法:先插尾,再插头
temp.next=rehead.next;
rehead.next=temp;
//temp指向head的下一个节点
temp=head.next;
单链表的缺点:
1.查找方向只能是一个方向;
2.不能自我删除,需要靠辅助节点;
双链表
单项环形链表
创建单向循环链表:
1.按照顺序依次添加至链表末尾:
public void addNode(int nums){
CircleNode cur=null;//辅助遍历指针
for(int i=1;i<=nums;i++){
CircleNode node=new CircleNode(i);//使用新构造函数
if(i==1){
first=node;
node.next=first;
cur=first;//同一节点可用多个指针指向
}else{
cur.next=node;
node.next=first;
cur=cur.next;
}
}
}
2.考虑节点序号大小:
// 按序号大小添加节点
public void addNodebyOrder(CircleNode circleNode) {
if (first == null) {
first = circleNode;
first.next = first;
count++;
System.out.printf("增添节点 %d 成功!\n", count);
return;
}
CircleNode cur = first;
// 情况1:添加节点小于头节点
if (first.no > circleNode.no) {
CircleNode temp = first;
first = circleNode;
circleNode = temp;
first.next = circleNode;
while (cur.next != circleNode) {
cur = cur.next;
}
cur.next = first;
count++;
System.out.printf("增添节点 %d 成功!\n", count);
return;
}
CircleNode cur2 = first;
while (true) {
if (cur2.no < circleNode.no) {
// 情况2:添加节点大于头节点
if (cur2.next.no > circleNode.no) {
// 情况2.1:添加节点位于循环链表中间
circleNode.next = cur2.next;
cur2.next = circleNode;
count++;
System.out.printf("增添节点 %d 成功\n", count);
break;
}
if (cur2.next == first) {
// 情况2.2:添加节点位于循环链表尾部
circleNode.next = cur2.next;
cur2.next = circleNode;
count++;
System.out.printf("增添节点 %d 成功\n", count);
break;
}
} else if (cur2.no == circleNode.no) {
// 情况3:添加节点等于头节点
System.out.println("添加节点重复!");
break;
}
cur2 = cur2.next;
}
}
Josephu问题
//Josephu出圈问题:
/**
* @param startNo 计数的开始节点
* @param m 每隔m次出队一个节点
* @param nums 共有nums的节点数
*/
public void josephu(int startNo, int m, int nums) {
addNode(nums);
CircleNode helper = first;
CircleNode sNo = first;
for (int i = 1; i < startNo; i++) {
sNo = sNo.next;
}
while (helper.next != sNo) {
helper = helper.next;
}
while (helper != sNo) {
for (int i = 1; i < m; i++) {
sNo = sNo.next;
helper = helper.next;
}
System.out.printf("出圈%d\n", sNo.no);
sNo = sNo.next;
helper.next = sNo;
}
System.out.printf("留圈%d\n", sNo.no);
}
栈
入栈(push)、出栈(pop)、(peek)
应用场景:子程序调用、递归调用、表达式转换与求值、二叉树的遍历、图的深度优先(depth-first)搜索法。
数组实现
链表实现
栈实现综合计算器:
前缀表达式(波兰式):
(
3
+
4
)
×
5
−
6
(3+4)\times5-6
(3+4)×5−6
→
\rightarrow
→ -
×
\times
× + 3 4 5 6
前缀表达式的运算符位于操作数之前。
从右至左扫描表达式。
中缀表达式:
(
3
+
4
)
×
5
−
6
(3+4)\times5-6
(3+4)×5−6
在计算机结果时,往往将中缀表达式转化成后缀表达式来操作。
后缀表达式(逆波兰表达式):
( 3 + 4 ) × 5 − 6 (3+4)\times5-6 (3+4)×5−6 → \rightarrow → 3 4 + 5 × \times × 6 -
与前缀表达式相似,只是运算符位于操作数之后。
从左至右扫描表达式。
中缀表达式To后缀表达式
思路:
-
初始化两个栈:运算符栈 s 1 s_1 s1和储存中间结果的栈 s 2 ; s_2; s2;
-
从左到右扫描中缀表达式;
-
遇到操作数压到 s 2 s_2 s2;
-
遇到运算符:
- 与 s 1 s_1 s1的栈顶比较,若优先级大于栈顶的优先级,或者栈顶为"(",直接入栈 s 1 s_1 s1;
2)否则,将 s 1 s_1 s1栈顶运算符取出压入 s 2 s_2 s2中,再转到4.1);
-
遇到括号:
-
“(”,直接入栈 s 1 s_1 s1;
-
“)”,将 s 1 s_1 s1栈顶运算符出栈压入 s 2 s_2 s2中,直到 s 1 s_1 s1栈顶为"(“,并将”("丢弃;
-
-
将 s 1 s_1 s1剩余数据弹到 s 2 s_2 s2中, s 2 s_2 s2中数据弹出的逆顺序即为后缀表达式。
递归
- 递归必须向退出递归的条件逼近。
- 当一个方法执行完毕,或者遇到return,就会返回。谁调用,就将结果返回给谁。
- 递归算法的时间复杂度:递归的次数 × \times ×每次递归中的操作次数
迷宫问题
/**
* @param map 地图
* @param i,j 从(i,j)出发 当map[i][j]为0表示该点未走过,1为墙,2表示通路走过,3表示死路走过
*/
public static boolean setWay(int[][] map, int i, int j) {
if (map[6][5] == 2) {// 通路已找到
return true;
} else {
if (map[i][j] == 0) {
// 按照 下->右->上->左 走
map[i][j] = 2;
if (setWay(map, i + 1, j)) {
return true;
} else if (setWay(map, i, j + 1)) {
return true;
} else if (setWay(map, i - 1, j)) {
return true;
} else if (setWay(map, i, j - 1)) {
return true;
} else {
map[i][j] = 3;
return false;
}
} else {// 如果map[i][j]!=0,可能是1,2,3
return false;
}
}
}
}
八皇后问题
一维数组 judge判断 递归调用 回溯
// 放置第n个皇后
// check是每次递归时,进入到check中都有for循环,因此会有回溯
public void check(int n) {
if (n == max) {
print();
count++;
return;
}
// 依次放入皇后,并判断是否冲突
for (int i = 0; i < max; i++) {
// 先把当前这个皇后n,放到该行的第1列
queen[n] = i;
// 判断当放置第n个皇后到第i列,是否冲突
if (judge(n)) {// 不冲突
check(n + 1);// 放置第n+1个皇后,即递归
}
// 如果冲突,将第n个皇后放到第i+1列
}
}
// 判断放置第n个皇后位置是否正确
private boolean judge(int n) {
for (int j = 0; j < n; j++) {
// 若在与前面元素在同一列或在同一斜线上,位置错误
if (queen[j] == queen[n] || Math.abs(n - j) == Math.abs(queen[n] - queen[j])) {
return false;
}
}
return true;
}