01背包问题
参考参考自https://www.cnblogs.com/wl-blog/p/14913905.html，这篇讲的很清楚。 先上代码：1234567891011# N = 4# V = 5# obj = [[1, 2], [2, 4], [3, 4], [4, 5]]value = [[0 for j in range(V + 1)] for i in range(N + 1)]for item in range(1, N + 1): for volume in range(1, V + 1): value[item][volume] = value[item - 1][volume] if volume >= obj[item - 1][0] and value[item][volume]< value[item - 1][volume - obj[item - 1][0]] + obj[item - 1][1]: value[item][volume] = value[item - 1][volume...
数据结构与算法·其七
栈栈的抽象数据类型顺序栈的抽象类型123456#define MAXSIZE 100typedef struct{ SElemType *base; #底边指针 SElemType *top; #顶指针，指向栈中最后一个元素的下一位 int stakesize; #栈的可用最大容量}SqSack; 顺序栈的一些算法 判断是否为空 S.top == S.base ? true : false; 栈长度 return S.top-S.base; 清空栈 if(S.base){S.top=S.base} 删除栈 if(S.base){delete S.base;...
数据结构与算法·其六
栈和队列栈和队列是只能在端点进行增删的线性表，按照存储结构分为顺序栈/队列，链栈/队列。 栈只有一个出口的结构，后进先出 队列一个入口，一个出口，先进先出 栈：进制转换案例12345# 159转8进制159%8=19---7 #7进栈19%8=2---3 #3进栈3%8=0---3 #3进栈#最后出栈 栈：括号匹配案例 栈：表达式求值 运算符优先法
数据结构与算法·其五
循环链表好处是从表中任意一点出发均可找到表中其他节点 遍历操作的终止条件是p!=L 循环链表的合并将a表的尾节点指针域指向b表的第一个节点；b的尾结点指向a表的头节点；释放b表的头节点； 双向链表具体算法 插入元素（在i位置之前插入元素e） if(!(p=Getelemp*Dul(L,i))) return ERROR;*找到要被插入的节点_ S=new DulNode;S->data=e; S->prior=p->prior;p->prior->next=S; S->next=p;p->prior=s; 删除元素 略 双链表更方便了，但是存储空间更大，插入元素要修改更多的指针。 各种链表的时间效率比较 链表的使用场景是需要频繁增加删除元素； 顺序表的使用场景是不经常增删，却经常改查；
数据结构与算法·其四
链表链式存储结构每个元素在存储器上的位置是任意的，逻辑相邻并不一定物理相邻。 每个节点存储的数据有两个部分。数据域和指针域。 访问时只能通过头节点依次向后查找，这种方法称为顺序存储法 如何判断链表是否为空 有头节点，头节点的指针为空时； 无头节点，头指针为空时； 链表种类 单链表：指针域只存储下一个元素的位置 双链表：指针域存储上一个和下一个的位置 循环链表：链表结点首尾相接 具体算法 初始化 L=new LNode L->next=Null 销毁 while(L){p=L;L=L->next;delete p;} 清空 p=L->next;while(p){q=p->next;delete p;p=q;}L->next=NULL; 相比较于删除操作，仅仅保留了头节点 获取表长 p=L->next;i=0;while(p){i++;p=p->next;}return...
数据结构学习笔记·其三
线性表线性表是具有相同特征的数据元素的一个有限序列。 特征： 只有一个开头，一个结尾 元素具有相同特征 顺序存储结构相当于数组的模式 顺序存储结构存在的问题： 存储空间分配不灵活 运算的空间复杂度高 链式存储结构在每个元素内存储与它相邻的两个元素的位置 线性表的操作（ADP） 初始化线性表 销毁线性表 清空线性表 判断线性表是否为空 获取表长度 获取表的某个元素 定位元素的位置 获取当前元素的前驱/后驱 插入元素 删除元素 遍历元素 线性表的顺序存储结构表示顺序存储：把逻辑上相邻的结构存储到物理上相邻的存储单元 顺序存储的特点： 占用连续的空间，中间不得出现空位置 根据某个元素的位置可以推出其他元素的位置 顺序存储结构的定义： 最大长度 数组长度 元素 顺序存储结构操作方法： 初始化线性表 分配存储空间，分配失败返回错误 设置length为0 销毁线性表 释放存储空间，若数组不存在则返回-1 清空线性表 设置length为0 判断线性表是否为空 length==0?return true:return...
数据结构学习笔记·其二
算法算法的定义对特定问题求解方法和步骤的一种描述，计算机中是一套指令的序列 算法的特性 有穷性，会在有穷步后结束 确定性，相同的输入得到相同额输出 可行性，可以使用基本操作执行有限次来完成 输入&输出 算法的评价标准 时间线率与空间效率（存储空间），这两者有时会矛盾 事前分析法算法中简单操作次数*每次操作所需时间 每条语句执行次数*执行一次所需时间 渐进空间复杂度算法本身占据的空间+算法所需要的辅助空间称之为空间复杂度 为了方便比较，我们一般只比较算法运算次数的数量级，n2一定比n3好。 渐进时间复杂度随着规模n的增大，算法执行的时间的增长率和fn的增长率相同，他们被称之为渐进时间复杂度。 例题