. .
1 s.len种情况 程序思路：
tag=0 //没有找到
for(l=s.len;l>0&&!tag;l--) {
判断长度为l的s中的子串是否为t的子串; 若是：tag=1; }
长度为l的s的子串在s中有（s.len-l+1）个。 子串0: 0～l-1
1: 1～l 2: 2～l+1 3: 3～l+2 ?? ??
s.len-l: s.len-l～s.len-1
由上面可得：第j个子串为j～l+j-1。
判断长度为l的s中的子串是否为t的子串: for(j=0;j 判断s中长度为l的第j个子串是否为t的子串; 如果是：tag=1; } 模式结构： tag=0; for(l=s.len;l>0&&tag==0;l--) { for(j=0;j ?? 用模式匹配方法确定s[j]～s[l+j-1]这个字符串是否为t的子串； //好好想想 若是，tag=1; } } 第二天 转眼又过了一周了,前面一周里面我编了一些程序:链表,长整型数相加,三元组表转置以及一些简单的函数.其实有些算法想想是很简单,不过写起来还是需要一定耐心和C基础的,如果你自己觉得各算法都很懂了,不妨开机编编试试.或许会有一些新的发现与体会. 栈和队列 1、知识点: ● 栈的定义:操作受限的线性表 ● 特点:后进先出 ● 栈的存储结构:顺序,链接 / push(s,d) ● 栈的基本操作: \\ pop(s) 栈定义： struct { datatype data[max_num]; int top; }; ●队列定义 特点:先进先出 /入队列 in_queue(Q,x) ●队列的操作: \\出队列 del_queue(Q) ●队列存储结构: 链队列: Typedef struct node{ Datatype data; Struct node *next; }NODE; Typedef struct { NODE *front; NODE *rear; }Queue; 顺序队列: struct { datatype data[max_num]; int front,rear; }; 问题: 队列?线性表 假溢出<=循環队列 队列满，队列空条件一样<=浪费一个存储空间 递归 定义：问题规模为N的解依赖于小规模问题的解。问题的求解通过小规模问题的解得到。 包括二个步骤： 1） 递推 6!=>5!=>4!=>3!=>2!=>1!=>0! 2） 回归 720<=120<=24<=6 <=2 <=1 <=0 递归工作栈实现递归的机制。 2、有关算法： 1） 顺序，链表结构下的出栈，入栈 2） 循環，队列的入队列，出队列。 3） 链队列的入队列，出队列。 4） 表达式计算：后缀表达式 35+6/4368/+*- 中缀表达式 （3+5）/6-4*（3+6/8） 由于中缀比较难处理，计算机内一般先将中缀转换为后缀。 运算：碰到操作数，不运算，碰到操符，运算其前两个操作数。 中缀=>后缀 5) 迷宫问题 6) 线性链表的递归算法 一个链表=一个结点+一个链表 int fuction(NODE *p) { if(p==NULL) return 0; else return(function(p->next)); } 树与二叉树 一、 知识点: 1. 树的定义: data_struct(D,R); 其中:D中有一个根,把D和出度去掉,可以分成M个部分. D1,D2,D3,D4,D5?DM R1,R2,R3,R4,R5?RM 而子树Ri形成树. 1) 递归定义 高度 2) 结点个数=1 O O O O O O O 2.二叉树定义: 结点个数>=0 . 3. 术语:左右孩子,双亲,子树,度,高度等概念. 4. 二叉树的性质 --0 --1 --2 此树的高度为2 ●层次为I的二叉树 I层结点 2I 个 ●高度为H的二叉树结点 2H+1-1个 ●H(点)=E(边)+1 ●个数为N的完全二叉树高度为|_LOG2n_| ●完全二叉树结点编号:从上到下,从左到右. i结点的双亲: i结点的左孩子: (根) |_i/2_| 2i |_i-1/2_| 2i+1 2i+2 0为起点 1 2 3 4 5 6 7 i结点的右孩子: 2i+1 1为起点 二叉树的存储结构: 1) 扩展成为完全二叉树,以一维数组存储。 A B C D E F G H I 数组下0 1 2 3 4 5 6 7 8 9 10 11 12 标 元素 A B C D E F G H I 2) 双亲表示法 数组下标 0 元素 A 双亲 -1 数组下标 元素 双亲 左子 右子 1 B 0 0 A -1 1 2 2 C 0 1 B 0 3 -1 3 D 1 2 C 0 4 5 4 E 2 3 D 1 5 F 2 4 E 2 6 G 3 5 F 2 7 H 3 ? ? ? ? ? 8 I 4 3) 双亲孩子表示法 结构: typedef struct { datatype data; int parent; int lchild; int rchild; }NODE; NODE tree[N]; // 生成N个结点的树 4) 二叉链表 5) 三叉链表 6) 哈夫曼树 5.二叉树的遍历 先根 \\ 中根 栈 中根遍历(左子树)根(右子树),再用相同的方法处理左子树,右子树. 后根 / 先,中序已知求树:先序找根,中序找确定左右子树. 层次遍历(队列实现) 6.线索二叉树(穿线树) 中序线索二树树目的:利用空指针直接得到中序遍历的结果. 手段(方法):左指针为空,指向前趋,右指针为空,指向后继. 结点结构: ltag Lch Data rch rtag Ltag=0,lch指向左孩子,ltag=1,指向前趋结点 Rtag=0,rch指向右孩子;rtag=1,指向后继结点 中序遍历: 1) 找最左结点(其左指针为空) 2) 当该结点的rtag=1,该结点的rch指向的就为后继 3) 当rtag=0,后继元素为右子树中最左边那个 N个结点的二树有空指针N+1个 周六我去了周SIR的办公室，他很热情，我问的是中序线索化二叉树的问题(递归)，关于这个问题我会在以后的笔记中作重点补充。我在这学校从来没有碰到 过像他这样热情的老师，真的，大一的时候我们学校就开了C，当时我就连#include