发表于 | 分类 | 评论数： | 阅读次数：

引入

我们学习了什么是队列，也了解了队列的一些基本特性，以及如何初始化一个队列，今天我们来看看如何创建和删除以及销毁一个队列。

创建一个队列

创建一个队列要注意以下两点

  • 创建一个头结点
  • 队列的头指针、尾指针都指向该结点
  • 因为队列是空的，这样就创建完成了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
#include <stdlib.h>
#define sizeof(struct Queue)

struct Queue{
int data;
struct Queue *next;
};

struct Queue_link{
struct Queue *front;
struct Queue *rear;
}

void init(Queue_link *q){
q->frout=q->rear=(struct Queue *)malloc(LEN);
if(!q->front){
exit(0);
}
q->frount->next=NULL;
}
阅读全文 »

发表于 | 分类 | 评论数： | 阅读次数：

引入

介绍完栈的各种定义，今天我们来介绍一下队列。我们常常会把栈和队列放在一起讲，因为它们有相似的地方，也有所不同，我们今天来看看什么是队列，以及如何初始化一个队列。

栈和队列

队列嘛，我们就可以想象成排队

  • 先来的排在前面，后来的排在后面
  • 不能插队，因为要讲究先来后到
  • 所以先来的先出队，后来的排在队尾

理解了上面的例子，要理解栈和队列，那就简单了

  • 栈：后进先出，只能在顶端进行插入和删除，也就是压栈和出栈
  • 队列：先进先出，队列只能在尾部出，头部入队。

队列

队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。

  • 与栈相反：队列是先进先出（First In First Out），简称为FIFO 的线性表。
  • 与栈相同：队列也是一种重要的线性结构，实现一个队列同样需要顺序表或链表作为基础。
阅读全文 »

发表于 | 分类 | 评论数： | 阅读次数：

引入

在20世纪30年代，波兰逻辑学家扬·卢卡西维茨（Jan Łukasiewicz）,发明了一种将所有操作符置于操作数的后面，因此也被称为后缀表示法。我们称之为逆波兰记法。逆波兰记法不需要括号来标识操作符的优先级。

逆波兰表示法

上面的引入感觉很高大上，我们来个例题，对于解

$(1-2)\times (4+5)$

连小朋友都知道，先算括号里面的，再算括号外面的，最后结果相乘。
如果计算机来解题的话，就会用很多 if…else… 进行判断，显然对于我们人类方便的括号优先级表达法，对计算机不那么友好。
那么能不能对计算机友好一点？逆波兰表达式出现了，对于上面的问题：

普通式为：$(1-2)\times (4+5)$
逆波兰表达式为：$12-45\times$

基本的转换方法如下

  • 所有数字从左到右写，位置不用动
  • 遇到括号，先写出括号内的数字
  • 然后在数字后面，以先乘除后加减的方式写出括号内的运算符
  • 然后继续写数字，直到所有数字写完
  • 然后在数字后面，以先乘除后加减的方式写出剩余的运算符
阅读全文 »

发表于 | 分类 | 评论数： | 阅读次数：

引入

我们之前，讲解了栈的顺序存储结构，那么既然是线性表，如何用链式存储结构来使用栈呢？链式存储和顺序存储在栈中又会有什么不一样呢？我们一起来看一下~

想一想

我们在开始之前先想一想，栈和链式存储结构的特点
链式存储结构

  • 有头部
  • 根据头部存储的指针信息，一环扣一环

顺序存储结构的栈

  • 后进先出
  • 插入和删除只能在顶端进行

链式存储结构的栈呢

  • 有头部
  • 每个结点存储着指针信息，一环扣一环
  • 后进先出
  • 插入和删除只能再顶端进行
阅读全文 »

发表于 | 分类 | 评论数： | 阅读次数：

引入

我们学习了栈的基本操作，今天我们就看看，栈能为我们做哪些服务，以及如何灵活的使用栈的这些特性。我们就从二进制数转换为十进制数的例子说起。

方法

首先，我们先说明一下二进制转十进制的公式

公式 $n\times 2^{n-1}$

N 表示二进制的从右向左的位数，然后把所有位的和相加，就是十进制结果。

演示
二进制数：$100101$
第 1 位：$1 \times 2^{1-1}=1 \times 1=1$
第 2 位：$0 \times 2^{2-1}=0 \times 2=0$
第 3 位：$1 \times 2^{3-1}=1 \times 4=4$
第 4 位：$0 \times 2^{4-1}=0 \times 8=0$
第 5 位：$0 \times 2^{5-1}=0 \times 16=0$
第 6 位：$1 \times 2^{6-1}=1 \times 32=32$
结果是：$1+0+4+0+0+32=37$
其实就是计算非零数相加。

阅读全文 »

发表于 | 分类 | 评论数： | 阅读次数：

引入

我们学习了栈的初始化、压栈、出栈，今天我们来看看如何清空和销毁一个栈。

清空栈

也就是将栈内的元素全部删除，但栈本身的物理空间，即内存地址是不会发生改变的。这个和销毁是有很大区别的。那么该如何清空呢？

  • 将 s->top 赋值为 s->base 即可，也就是让顶部和底部相等。
  • 可以这么理解，数据还在那，找数据的地址全没了。
  • 新数据写入的时候，会覆盖掉原来这个地址的数据。

代码实现

非常简单

1
2
3
ClaerStack( sqstack *s ){
s->top=s->base;   //让顶部等于底部
}

阅读全文 »

发表于 | 分类 | 评论数： | 阅读次数：

引入

上一节，我们了解了栈的基本信息，知道了栈的各种特性，并且试着初始化了一个空栈。今天我们就来看看，如何将数据存入栈中。

入栈操作

入栈，我们有称之为压栈，简单来说就是向栈中存放数据。

  • 入栈从栈顶进行。
  • 每压入一个数据，top 的指针就要+1
  • 直到栈满了为止

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#define StackSize 100  //首先设置一个容量
//这里需要注意，实参的 s 需要先创建内存空间
void push(struct Stack *s,int data){
//下面开始判断栈是否满了，用头部-底部，如果距离为最大容量，就是满了
    if(s->top - s->base >= s->StackSize){
//给底部赋值一个新的最大容量，为什么是底部？因为那是起始地址
        s->base=(int *)realloc(s->base, (s->StackSize+10)*sizeof(LEN));
//顶部等于新底部+最大容量，就是顶部
        s->top=s->base+s->StackSize;  
//最大容量记得增加
        s->StackSize=s->StackSize+10;
    }
    //下面这两个才是实际的压栈
    *(s->top)=data;  //顶部的地址的值赋值为传递进来的形参
    s->top++;  //顶部向后移动一位
}
阅读全文 »

发表于 | 分类 | 评论数： | 阅读次数：

引入

今天，我们开始讲一种特殊的线性表，栈。既然是特殊的线性表，那么有哪些不一样的呢？我们一起来看看！

从弹夹说起

下面的图片是一个弹夹

我们知道，如果子弹没有了，那么我们需要一颗一个的将子弹装入弹夹

  • 第一颗被装入的子弹在弹夹的最上方
  • 第二颗则压在第一颗的上方，循环往复，直到装满
  • 此时如果我们要射击，最上面的一颗子弹会首先被发射出去
  • 然后弹夹下面的弹簧会将压在下面的子弹顶上来

也就是说，最后被装入的子弹，最先被发射出去。我们将这种情况称之为后进先出。

阅读全文 »

发表于 | 分类 | 评论数： | 阅读次数：

引入

前面我们简单了解了一下双链表，以及在插入和删除时的一些变化。这一节，我们就跟着一个凯撒密码，来看看双循环链表的初始化、插入、操作结点等过程。

凯撒密码

凯撒密码是一种代换密码。据说凯撒是率先使用加密函的古代将领之一，因此这种加密方法被称为凯撒密码。他的基本思想是

  • 通过把字母移动一定的位数来实现加密和解密。
  • 明文中的所有字母都在字母表上向后（或向前）按照一个固定数目进行偏移后被替换成密文。
  • 当偏移量是4的时候，所有的字母A将被替换成E，B变成F，以此类推W将变成A，X变成B，Y变成C，Z 变成 D。
  • 而这个偏移量就是凯撒密码加密和解密的密钥。

例题

有26个英文字母，我们需要设计一个程序

  • 用户输入可为正负的正整数
  • 如果是正数，那从左边取 N 位正整数移动到表尾
  • 如果是负数，那从右边取 N 位正整数移动到表头
阅读全文 »

发表于 | 分类 | 评论数： | 阅读次数：

引入

我们介绍了单链表、介绍了将单链表头尾相连组成循环链表，又讲了循环链表中一些有趣得应用，现在是时候了解线性表中的大拿，双循环链表了。

为什么需要双链表

在单循环链表中，链表中的各个节点是这样的，一个结点指向下一个结点

A -> B -> C -> D -> E -> F

如果我们需要从 A 到达 D 结点，那么需要

A -> B -> C -> D

如果到了 D 之后，有需要到 C，那么就麻烦了

D -> E -> F -> A -> B -> C

明明相邻得两个结点，为什么要转一圈才能找到彼此呢？
答案很简单，因为结点都是向后指的，单循环链表嘛~
而解决这个问题的答案更简单，那我们就把结点
既指向它的前驱节点，也指向它的后继节点不就好了~
这就是双向链表。

阅读全文 »