文的盲

既然学了栈这种数据结构，那么就应该进一步深入或者熟练地应用。这也构成了两种不同的应用方式： 一种是利用栈这种数据结构，来实现一些其他的数据结构，比如：用栈来实现队列，或者是实现一些特殊的栈，比如：最小栈。 另一种是具体问题的解决，比如经典的逆波兰表达式的求解等一系列问题 闲话部分——在线提交 为什么要在线提交？答案很简单，就是保证自己代码的完全正确性。 怎么理解呢，就是说，你写完一个程序之后，应该仅仅会想出一组或者部分样例来进行测试代码运行结果是否符合自己的预期，但是自己想出来的这些样例往往是不完备的，而在线提交平台的样例基本是完备的，尤其是一些著名的提交平台。 那么有哪些平台可以选择呢？ 我个人的喜好是 LeetCode ，由于网速和英语不好的原因，我选择了其中文网站，如果想练习英语，也可以进其英文官网。 还有其他类似的平台，牛客啊啥的，可凭自己喜好进行选择。 栈的应用 LeetCode 还有比较好的一点就是可以按照标签进行刷题，而网站的题量也在稳步上升，而关于栈的应用，我特意选了这么几道有代表性的题： 最小栈 逆波兰表达式求值 二叉 ...

堆栈是一种数据项按序排列的数据结构，只能在一端（称为栈顶(top)）对数据项进行插入和删除。 简单地说，堆栈可以看作一个箱子，只能在一端放和取，所以其主要操作有： 插入数据：入栈（Push） 删除数据：出栈（Pop） 而只能一端存取，也形成了其最主要的特性： 后入先出：Last In First Out（LIFO） 类型名称：堆栈（Stack） 数据对象集：一个有0个或多个元素的有穷线性表 操作集：长度为 MaxSize 的堆栈 S 属于 Stack ， 堆栈元素 item 属于 ElementType 123451. Stack CreateStack () 生成空堆栈2. int IsFull (Stack S) 判断堆栈S是否已满3. void Push (Stack PtrS, ElementType item) 将元素item压入堆栈4. int IsEmpty (Stack S) 判断堆栈S是否为空5. ElementType Pop (Stack PtrS) 删除堆栈并返回栈顶元素 ...

此篇博文根据斯坦福公开课 《编程范式》整理，也算是一个简单的笔记。 Stack（栈） 栈是一种十分基础的数据结构，也十分简单，下面我们首先来实现此种数据结构的int表示 stack.h 在此文件之中，我们对栈的结构和栈的基本操作进行了定义，其中代码如下： 12345678910typedef struct { int* elems; int logLength; int allocLength;}stack;void StackNew(stack* s);void StackDispose(stack* s);void StackPush(stack* s, int value);int StackPop(stack* s); stack.c 此文件中，将 .h 文件中的函数进行了实现，代码如下： 123456void StackNew(stack* s) { s->allocLength = 4; s->logLength = 0; s->elems = malloc(sizeof ...

众所周知，C语言是不支持泛型的，但可以利用C语言自身的语法特点来实现此特性。而此篇博文根据斯坦福公开课 《编程范式》整理，以阐述用C语言实现此种特性的大致思路，也算是一个简单的笔记。 从 Swap 谈起 交换函数应该是最常见也是最常用的函数之一，C语言的交换函数一般这样写： 12345void Swap (int *p, int *q) { int tmp = *p; *p = *q; *q = tmp;} 但是如上代码仅能对 int 类型数据进行交换，如果要交换 double 或者其他类型的数据又需要写一段极其相似的代码（仅将 int 换掉），而这样无疑是不够简练的，代码也不够优美。所以我们考虑写一个能交换所有数据类型的函数，以简练代码，提高效率。 既然有这样的想法，那么我们试着去实现它。既然要普适所以数据类型，那么我们就需要向本源出发去寻找。无论什么类型的数据，在计算机底层都是以二进制储存的，这我们就找到了所有不同类型数据的共同点，也就有了设计思路： 在内存中找到两个数据的地址 从头至尾，将两个数据的每一个字节进行交换 ...

二进制是计算机的基础，数据的存储在底层看来均是由二进制来表示的，那么如何用二进制来表示各种数据呢？此时就需要设计出一套完整的科学的储存方案 整型数据的存储 整型数据包括 short, int, long 等，其中最为常用的便是 int ，在目前的系统中（32位和64位编译器，以C语言为主要实例），其所占字节如下： 数据类型 所占字节 short 2 int 4 long 8 而整型数据的存储都是类似的，也就是以二进制方式进行存储，所以很容易理解，但是与日常使用的二进制数不同的是，在计算机储存中，为了方便地计算加减法，我们实际储存的是二进制数的 补码1: 示例 下面写几个简单 int 类型数字的在计算机中的二进制储存方式： 十进制 二进制（int） 10 00000000 00000000 00000000 00001010 -10 11111111 11111111 11111111 11110110 0 00000000 00000000 ...

想写小游戏的心早就有了，但是一直觉得额外学习一门语言的GUI编程好像不是很划算，今年趁着看了点 python 的内容，所以想试试用python来写，在过程中了解到python有一个专门的库——pygame ，所以就看了点教程，以下权当做个笔记 初识 pygame pygame最小开发框架主要包含两个方面 —— 引入库和初始化，主循环和刷新 引入主要是引入自己要用到的库 初始化主要是初始化窗体，主要包括窗体的大小，窗体的名称，图标等等 主循环主要是接收操作，逻辑判断，事件处理和刷新游戏等 根据教程的壁球小游戏，我直接贴上老师的代码： 初始化部分 1234567891011121314151617181920212223242526import pygame, sysfrom pygame.locals import *# 初始化 pygamepygame.init()# 获取系统屏幕尺寸大小sysSize = pygame.display.Info()size = width, height = 400, 600speed = [1, 1]BLACK = 25 ...

当数组（或其他查找的对象）是杂乱无章之时，或许查找起来就会比较困难，甚至只能一个一个找。但是，当数据是有序的之后，查找数据就有更为省时的算法了 二分查找 二分查找也被称之为折半查找，其绝对是应用最为广泛也的查找算法了，其 \(log(N)\) 的时间复杂度也是相当优秀，所以其名声也是相当大，以至于我在很久之前就听说过此算法并写了一篇博文，可以点击链接直接跳转 插值查找 插值查找是在二分查找的基础上改进产生的，其大致思路如下：当我们查字典时，如果首字母为 a ，我们必然不会往中间翻，而是翻向靠前的页数，所以，当我们进行查找之时，也可以根据具体情况进行镶银的调整 1234567891011121314int BinarySearch(int a[],int size,int p) { int L = 0; int R = size - 1; while( L <= R) { int mid = L + (R-L) * (p-a[L]) / a[R] - a[L]; if( p == a[mid] ) ...

查找是一类重要的算法，尤其是在现今的大数据时代来看更是如此，选择一个好的查找算法往往可以起到事倍功半的效果 顺序表查找 顺序表查找是最为简单也是最为笨重的一类查找，其遵循的理念就是一个一个找。当需要在顺序表中查找一元素时，需要做的就是从头到尾对表进行一次遍历，直到找到结果为止 代码： 123456int SequentialSearch(int* a, int n, int key) { for (int i = 0; i < n; i++) if (a[i] == key) return i; return -1;} 改进版顺序查找 为了使顺序表在每次查找之前不进行不必要的判断是否越界，我们可以利用 “哨兵” 法，在数组的开头或者末尾之前设置一个 “哨兵” ，查找至哨兵位置直接返回没找到即可 代码： 123456int SequentialSearch(int* a, int n, int key) { int i = n - 1; a[0] = key whil ...

开始之前 进阶排序是对一些特殊情况下排序的处理方式，也是非常重要的一些排序方法 表排序 当数据不再是简单的数字或者字符，而是一些比较大的元素，例如文件等，那么这时在之前介绍的排序中所采取方式就会产生很大的时间复杂度 —— 因为文件的移动是需要时间的，而且需要不短的一段时间，我们普通的排序所采取的不停Swap的操作，就会使时间大大增加 间接排序 那么此时，我们可以采取间接排序的方式，也就是在结构体中添加一个属性，将之进行简单排序，来作为数据的真实顺序 A [0] [1] [2] [3] [4] [5] [6] [7] key f d c a g b h e table 0 1 2 3 4 5 6 7 对table根据key值进行排序即可 A [0] [1] [2] [3] [4] [5] [6] [7] key f d c a g b h e table 3 5 2 ...

在了解了简单排序之后，我们仍不满足简单排序的效率，在此驱动之下，又有效率更高的排序算法被设计出来 希尔排序 在学习了冒泡和插入排序之后，我们发现，对于同一数列而言，采用冒泡排序和采用插入排序所进行的交换次数是一致的，进而可以得知，排序实际是消除逆序对的过程，由此我们可以有以下思路 实现思路 冒泡和插入排序每次只消除一个逆序对 既然排序是为了消除逆序对，那么能不能通过一次交换消除多个逆序对呢 显然，我们可以采用隔几个数字的方式来进行排序，这样一来，进行一次交换就可消除不止一个逆序对 结和以上思路，便实现了希尔排序的一般实现方式 代码1 1234567891011void ShellSort(ELEMENT_TYPE a[], int n) { // 希尔1 int i, j, k; for (i = n/2; i > 0; i /= 2) { for (j = i; j < n; j++) { ELEMENT_TYPE temp = a[j]; ...