My Little World

learn and share


  • 首页

  • 分类

  • 标签

  • 归档

  • 关于
My Little World

KMP算法

发表于 2017-02-02

next数组

经推导发现,进行模式匹配时,子串的移位规律与主串内容无关,与子串的内容有关,
因此根据子串的内容,生成基于子串的next数组,用来存放在对应位置如果发生失配,
应该将子串的哪个位置移动到失配位置
1.失配位置的前缀:永远是子串第一位
2.失配位置的后缀:失配位置的前一位
3.失配位置的前后缀相同位数:
从第一位开始的n位和从后缀开始倒数的n位相同,但前缀连续长度最长不能包含后缀那一位,
后缀也不能包含前缀,重叠也没关系,就说失配位置的前缀和后缀有n位相同
例:
ababc
若在倒数第二位的b位置(位置4)失配,则位置4的前缀是位置1的a,后缀是位置3的a,
从位置1和位置3开始,二者只有一位相同,则前后缀有1为相同,
若在最后一位位置5失配,前缀a虽然和后缀b不相同,但前缀连续两位ab和后缀连续两位ab相同
则c的前后缀有两位相同
ssssb
若在b位置失配,前缀连续sss,后缀连续sss,虽然重叠位置2和位置3的s,但前后缀相同位数为3
4.next数组值
失配位置的next数组值 = 失配位置的前后缀相同位数 + 1
特殊情况:子串位置1的next数组值为0,位置2的next数组值为1
例:

T: a b a b a a a b a
下标: 1 2 3 4 5 6 7 8 9
next: 0 1 1 2 3 4 2 2 3

next数组获取代码实现

i后缀 1 2 。 3 4 5 6 7 。 8 9
j前缀 0 1 0 1 2 3 4 2 1 2 3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var string = "9ababaaaba"; //第一位存放字符串长度
function getnext(T){
var next=[];
next[0]=T.length-1;
var i = 1;## 前缀
var j = 0;## 后缀
next[1] = 0;
while(i<T[0]){
if(j==0 || T[i] == T[j]){// 子串自己匹配自己
i++;
j++;
next[i]=j;
}else{
j = next[j]; // 自己匹配发生失配,则视前缀为子串,后缀为主串,将前缀回溯
}
}
console.log(next);
}
getnext(string);

KMP算法

代码链接

My Little World

队列

发表于 2017-02-02

队列

1.先进先出的线性表,有顺序表和链表
2.只允许在一段插入,另一端删除

队列的链式存储结构

和栈相反,队列常用链表实现

1
2
3
4
5
6
7
8
typedef sruct QNode{
ElemType data;
struct QNode *next;
}QNode,*QueuePrt;
typedef struct {
QueuePrt front; ##队头指针指向链队列的头结点(头结点不是必要的)
QueuePrt rear; ##队尾指针指向终端结点,空队列时,front,rear都指向头结点
}LinkQueue;

queue1
queue2

入队列

queue3

1
2
3
4
5
6
7
8
9
10
11
InsertQueue(LinkQueue *q,ElemType e){
QueuePrt p;
p = (QueuePtr)malloc(sizeof(QNode));
if(p==NULL){
exit(0);
}
p->data = e;
p->next = NULL;
q->rear->next = p;
q->rear = p;
}

出队列

queue5
queue6

1
2
3
4
5
6
7
8
9
10
11
12
13
14
DeleteQueue(LinkQueue *q,ElemType e){
QueuePrt p;
if(q->front ==q->rear)
{
retrun;
}
p=q->front->next;
*e=p->data;
q->front->next = p->next;
if(q->rear ==p){
q->rear = q->front;
}
free(p);
}

销毁一个队列

由于链队列建立在内存的动态区,因此当一个队列
不在有用时,应当及时销毁掉,以免过多占用内存空间

1
2
3
4
5
6
7
DestroyQueue(LinkQueue *q){
while(q->front){
q->rear = q->front->next;
free(q->front):
q->front = q->rear;
}
}

简单实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
var list = [];
for(var i=0;i<5;i++){
list.push({
next:i+1
})
}
list[4].next = null;
console.log(list);
//入队列
var length = list.length;
list.push({
next:null
})
list[length-1].next=length;
console.log(list);
//出队列
list.splice(0,1);
console.log(list);
//清空
list=[];

My Little World

栈

发表于 2017-02-02

栈

1.特殊线性表,所以也分为顺序存储和链式存储结构
2.表尾称为栈尾,表头称为栈底
3.元素必须后进先出;所有操作只能在表尾进行
4.插入操作叫做进栈/入栈/压栈,删除操作叫出栈/弹栈
5.最开始栈中不含有任何数据,叫空栈,此时栈顶就是栈底,
然后数据从栈顶进入,栈顶栈底分离,整个栈的当前容量变大,
数据出栈时从栈顶弹出,栈顶下移,整个栈的当前容量变小

1
2
3
4
5
6
7
栈的顺序存储结构
typedef struct
{
ElemType *base; ##指向栈底的指针变量
ElemType *top; ##指向栈顶的指针变量
int stackSize; ##栈当前可使用的最大容量
}sqStack;

入栈操作

每次向栈中压入一个数据,top指针+1,直到栈满为止

出栈操作

在栈顶取数,栈顶指针随之下移,当前容量-1,

JS数组push和pop方法对数组处理

二进制转10进制
主要思想,每次pop数组最后一项,即二进制的位数依次增长,顺序i正好为指数

1
2
3
4
5
6
7
8
var list = [1,1,0,1,0,1,0,1];
var sum = 0;
var length = list.length;
for(var i = 0;i<length;i++){
var pop = list.pop();
sum+= pop*Math.pow(2,i);
}
console.log(sum);

二进制转8进制
主要思想,三位一组生成10进制,最后十进制按位数相加

1
2
3
4
5
6
7
8
9
10
11
12
13
var list = [1,1,0,1,0,1,0,1];
var hex = 0;
var length = list.length;
for(var i=0;i<length/3+1;i++){
var sum = 0;
for(var j = 0;j<3;j++){
if(list.length>0){
sum+=list.pop()*Math.pow(2,j);
}
}
hex +=sum*Math.pow(10,i);
}
console.log(hex);

二进制转16进制
注意 >9时,转换成字母,pop,进行反序链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
var list = [1,1,0,1,0,1,0,1];
var hex = [];
var length = list.length;
for(var i=0;i<length/4+1;i++){
var sum = 0;
if(list.length>0){
for(var j = 0;j<4;j++){
if(list.length>0){
sum+=list.pop()*Math.pow(2,j);
}
}
if (sum >-1&&sum<10) {
hex.push(String.fromCharCode(sum+48));
}
if(sum >9 && sum <16){
hex.push(String.fromCharCode(sum+55));
}
}
}
var str = "";
for(var l = hex.length-1;l>-1;l--){
str+=hex[l];
}
console.log(str);

My Little World

逆波兰表达式/后缀表达式

发表于 2017-02-02

栈的链式存储结构

栈的链式存储结构

stack2

1
2
3
4
5
6
7
8
typedef struct StackNode{
ElemType data; ##存放栈的数据
struct StackNode *next;
}StackNode,*LinkStackPtr;
typedef struct LinkStack{
LinkStackPrt top; ##top指针
int count; ##栈元素计数器
}

栈链的入栈操作

假设元素值e的新结点是s,top为栈顶指针

1
2
3
4
5
6
7
8
Status Push(LinkStack *s,ElemType e){
LinkStackPtr p=(LinkStackPtr)malloc(sizeof(StackNode));
p->data = e;
p->next = s->top;
s->top = p;
s->count++;
return OK;
}

栈的出栈操作

假设变量p用来存储要删除的栈顶结点,将栈顶指针下移一位,最后释放p

1
2
3
4
5
6
7
8
9
10
11
12
Status Pop(LinkStack *s,ElemType e){
LinkStackPtr p;
if(StackEmpty(*s)){
return ERROR;
}
*e=s->top->data;
p=s->top;
s->top = s->top->next;
free(p);
s->count--;
return OK;
}

逆波兰表达式/后缀表达式

正常表达式–>后缀表达式
(1-2)x(4+5)–> 1 2 - 4 5 + x
1.计算后缀表达式
主要思想是判断字符是否为运算符,若为数字,则入栈,为运算符则连续出栈两次进行运算,再将运算结果入栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
var list =[1,2,3,4,'-','*','+']
var stack = [];
for(var i = 0;i<list.length;i++){
if(!isNaN(list[i])){
stack.push(list[i]);
}else{
var a = stack.pop();
var b = stack.pop();
if(list[i] =="+"){
stack.push(b+a);
}else if(list[i] =="-"){
stack.push(b-a);
}else if(list[i] =="*"){
stack.push(b*a);
}else if(list[i] =="/"){
stack.push(b/a);
}
}
}
console.log(stack);

2.计算表达式转后缀表达式
主要思路
1,表达式中参与运算的数字、运算符以及小括号分割,形成待处理数组
2,循环判断
A.若字符为数字,入栈2,
B.若字符为“+”、“-”,分情况讨论
(1)此时栈1为空,入栈;
(2)栈1不为空,将“(”左括号以上的符号从栈1 pop到栈2,“(”留 在栈1,处理完后,将“+”、“-”入栈1;
C若字符为“)”,将“(”以上符号从栈1 pop到栈2,“(”也pop出来
但不入栈2
D若字符为“/”“*”“(”直接入栈2
E其他情况,非法字符,抛出异常
3.将栈1元素pop到栈2;
栈2即后缀表达式
代码链接

My Little World

双向循环链表

发表于 2017-02-02

结构

1
2
3
4
5
typedef struct DualNode{
ElemType data;
struct DualNode *prior;//前驱结点
struct DualNode *next;//后继结点
}DualNode,*DuLinkList;

doublylinklist1
doublylinklist2
双向链表插入
doublylinklist3
s->next = p;
s->prior = p->prior;
p->prior->next = s;
p->prior = s;
双向链表删除
doublylinklist4
p->prior->next = p->next;
p->next ->prior = p->prior;
free(p)
小结
双向链表相对于单链表来说复杂一点,每个结点对了一个prior指针,在进行插入和删除时需要注意;
双向链表可以有效提高算法的时间性能,用空间换取时间

My Little World

拉丁方阵

发表于 2017-02-02

lating1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
function Latinsquare(num){
var list=[];
for(var i = 0;i<num;i++){
var pre = 0;
if(i==0){
pre=num;
}else{
pre = i;
}
var nextt = 0;
if(i ==num-1){
nextt = 1;
}else{
nextt = i+2;
}
list.push({
prior:pre,
data:i+1,
next:nextt
})
}
for(var i = 0;i<num;i++){
var string=[];
var p = 1;
for(var j = 0;j<i;j++){
p = list[p-1].next;
}
for(var k = 0;k<num;k++){
string.push(list[p-1].data);
p = list[p-1].next;
}
console.log(string);
}
}
Latinsquare(5);

My Little World

判断单链表是否有环

发表于 2017-02-02

有环定义:链表的尾节点指向了链表中的某个结点
ishascircle
方法一:p、q指针同时向前走,但q每次都从头开始走,对于每个结点,若p、q走的步数不等则说明有环
方法二:快慢指针:使用p,q两个指针,p每次向前走一步,q每次向前走两步,若在某个时候p==q,则存在环
代码

My Little World

单链表

发表于 2017-02-02

头插法建立单链表

chaintable17
chaintable18
代码链接

尾插法建立单链表

头插法建立的链表输入顺序与结点次序相反,尾插法可以使二者顺序相同
chaintable20
R做索引,S做中介节点
代码链接
重点r=p;将尾节点更新为r

整表删除

chaintable21
参照删除单链表制定位置结点代码代码链接

快慢指针—>标尺思想

staticlinklist3
快速找到未知长度单链表的中间结点 代码链接

单链表与顺序存储结构优缺点

1.存储分配方式:
顺序存储结构用一段连续的存储单元依次存储线性表的数据元素;
单链表采用链式存储结构,用一组任意的存储单元存放线性表的元素
2.时间性能:
—查找
顺序存储结构O(1);
单链表O(n)
—插入和删除
顺序存储结构需要平均移动表长一半的元素,时间为O(n);
单链表在计算出某位置的指针后,插入和删除时间仅为O(1)
3.空间性能
顺序存储结构需要预分配存储空间,分大了容易造成空间浪费,分小了容易发生溢出
单链表不需要分配存储空间,只要有就可以分配,元素个数也不受限制。

小结

1.频繁查找,较少插入删除操作,宜用顺序存储结构,如,游戏开发时用户注册的个人信息的存储
2.频繁插入删除操作,较少查找,宜用单链表结构,如游戏中的玩家的装备列表
3.当线性表大致长度已知,宜用顺序存储结构,反之,长度变化大或未知,则用单链表

My Little World

静态链表

发表于 2017-02-02

用数组描述的链表叫做静态链表
这种描述方法叫做游标实现法
staticlinklist1
Staticlinklist是一个容量为maxsize大的数组,数组每一项是一个结构struct,
这个结构包含两项,数据data和游标cur
整个数组的第一项(下标为0)和最后一项(下标为maxsize-1)的数据部分不存放数据
把未使用的数组元素(数据部分为空称为备用链表
约定:
——第一项的游标指向数组中除收尾两项外的项中,第一个数据部分为空的项,即首项游标为该项的下标/备用链表第一个结点的下标;
——尾项游标指向第一个有数据的元素 相当于头结点作用
——其他元素游标等于其指向的元素位于数组中的下标
——数据元素的最后一项的游标等于首项下标0,即指向备用链表开始结点

初始化静态链表相当于初始化数组

1
2
3
4
5
6
7
8
Status InitList(StatixLinkList space)
{
int i;
for(i =0;i<MAXSIZE-1;i++){
space[MAXSIZE-1].cur = 0;
return OK;
}
}

链表插入,删除,求长度 代码链接

My Little World

单循环链表

发表于 2017-02-02

循环链表

将单链表中终端结点的指针端由空指针改为指向头结点,就使整个单链表形成一个环,这种头尾相接的单链表成为单循环链表,简称循环链表
singlelooplinklist1
循环链表并不一定要有头结点
与单链表的主要差异为判断链表是否为空
单链表为空条件为head->next = null
循环链表为空条件为head->next = head
终端节点用尾指针rear指示,查找终端结点是O(1);开始结点是rear->next->next,也是O(1);
[插入、删除、返回位置 代码思路参考单链表]
Rear == rear->next 空循环链表
singlelooplinklist2
小结
循环链表的特点是无须增加存储量,仅对链接方式稍作改变,即可使得表处理更加方便灵活

1…23242526
YooHannah

YooHannah

260 日志
1 分类
23 标签
RSS
© 2025 YooHannah
由 Hexo 强力驱动
主题 - NexT.Pisces