程序员数据结构笔记

数据结构

知识:

1.数据结构中对象的定义,存储的表示及操作的实现.

2.线性:线性表、栈、队列、数组、字符串（广义表不考） 树：二叉树

集合：查找，排序 图(不考) 能力：

分析，解决问题的能力 过程：

● 确定问题的数据。 ● 确定数据间的关系。

● 确定存储结构（顺序－数组、链表－指针） ● 确定算法 ● 编程

● 算法评价（时间和空间复杂度，主要考时间复杂度）

一、数组

1、存放于一个连续的空间

2、一维～多维数组的地址计算方式

已知data[0][0]的内存地址，且已知一个元素所占内存空间Ｓ求data[i][j]在内存中的地址。

公式：（add+(i*12+j)*S)(假设此数组为data[10][12])

注意：起始地址不是data[0][0]时候的情况。起始地址为data[-3][8]和情况；

3、顺序表的定义

存储表示及相关操作

4、顺序表操作中时间复杂度估计

5、字符串的定义（字符串就是线性表），存储表示 模式匹配算法（简单和KMP（不考））

6、特殊矩阵：存储方法（压缩存储（按行，按列）） 三对角：存储于一维数组

三对角问题：已知Aij能求出在一维数组中的下标k;已知下标k求Aij。 7、稀疏矩阵：定义，存储方式：三元组表、十字链表（属于图部分，不考）

算法

● 数组中元素的原地逆置； 对换 ● 在顺序表中搜索值为X的元素；

● 在有序表中搜索值为X的元素；（折半查找） ● 在顺序表中的第i个位置插入元素X； ● 在顺序表中的第i个位置删除元素X； ● 两个有序表的合并；算法？ 线性表数据结构定义： Typedef struct {

int data[max_size]; int len; }linear_list; ● 模式匹配 ● 字符串相加 ● 求子串

● （i,j）<=>K 注意：不同矩阵所用的公式不同； ● 稀疏矩阵的转置（两种方式，后种为妙） ● 和数组有关的算法

例程：求两个长整数之和。 a=13056952168 b=87081299 数组:

a[]:1 3 0 5 6 9 5 2 1 6 8 b[]:8 7 0 8 1 2 9 9

由于以上的结构不够直观(一般越是直观越容易解决) 将其改为: a[]:11 8 6 1 2 5 9 6 5 0 3 1 a[0]=11(位数) b[]: 8 9 9 2 1 8 0 7 8 0 0 0 b[0]=8

c[]:11 7 6 4 3 3 0 4 4 2 3 1 c[0]的值(C位数)由c[max_s+1]决定! 注意:在求C前应该将C(max_s+1)位赋0.否则为随机数; 较小的整数高位赋算法:已知a,b两个长整数,结果:c=a+b; 总共相加次数: max_s=max(a[],b[]) 程序:

for(i=1;i<=max_s;i++) { k=a[i]+b[i]+c[i]; c[i]=k; c[i+1]=k/10; }

求c位数:

if(c[max_s+1]==0) c[0]=max_s; else

c[0]=max_s+1;

以下代码是我编的(毕竟是初学者.不太简洁大家不要见怪!): /*两长整数相加*/ #include #include

#define PRIN printf(\int flag=0; /*a[0]>b[0]?1:0*/

c进位 0 1 1 0 0 1 1 1 1 0 0 0.

/* max(a[],b[]) {}*/

change(char da[],char db[],int a[],int b[],int c[]) { int i;

if(a[0]>b[0]) {

for(i=1;i<=a[0];a[i]=da[a[0]-i]-'0',i++); /*a[0]-'0' so good!*/

for(i=1;i<=b[0];b[i]=db[b[0]-i]-'0',i++); for(i=b[0]+1;i<=a[0];b[i]=0,i++); for(i=1;i<=a[0]+1;c[i]=0,i++); flag=1; }

else {

for(i=1;i<=b[0];b[i]=db[b[0]-i]-'0',i++); for(i=1;i<=a[0];a[i]=da[a[0]-i]-'0',i++); for(i=a[0]+1;i<=b[0];a[i]=0,i++); for(i=1;i<=b[0]+1;c[i]=0,i++); } }

add(int a[],int b[],int c[]) { int i,sum; if(flag==1) {

for(i=1;i<=a[0];i++) { sum=a[i]+b[i]+c[i]; c[i+1]=sum/10; c[i]=sum; }

if(c[a[0]+1]==0) c[0]=a[0]; else

c[0]=a[0]+1; }

else {

for(i=1;i<=b[0];i++) { sum=a[i]+b[i]+c[i]; c[i+1]=sum/10; c[i]=sum; }

if(c[b[0]+1]==0) c[0]=b[0]; else

c[0]=b[0]+1; }

}

void print(int m[]) { int i;

for(i=m[0];i>=1;i--)

printf(\ }

main(){ int s;

int a[20],b[20],c[20]; char da[]={\ char db[]={\ a[0]=strlen(da); b[0]=strlen(db);

printf(\ printf(\ change(da,db,a,b,c);

printf(\ printf(\ if(flag==1) { print(a); PRIN s=abs(a[0]-b[0]); printf(\

for(s=s*2-1;s>0;s--) printf(\ print(b); PRIN }

else {

s=abs(a[0]-b[0]); printf(\

for(s=s*2-1;s>0;s--) printf(\ print(a); PRIN print(b); PRIN }

add(a,b,c);

printf(\ print(c); }

时间复杂度计算: ● 确定基本操作 ● 计算基本操作次数

● 选择T(n)

● lim(F(n)/T(n))=c ● 0(T(n))为时间复杂度

上例子的时间复杂度为O(max_s);

二:链表

1、知识点

●逻辑次序与物理次序不一致存储方法； ●单链表的定义：术语（头结点、头指针等）

●注意带头结点的单链表与不带头结点的单链表区别。（程序员考试一般不考带头结点，因为稍难理解）

●插入、删除、遍历（p==NULL表明操作完成）等操作 ● 循环链表：定义，存储表示，操作； ● 双向链表：定义，存储方法，操作；

单链表和循环链表区别在最后一个指针域值不同。 2、操作

●单链表：插入X，删除X，查找X，计算结点个数 ●单链表的逆置（中程曾考）

head->NULL/p->a1/p->a2/p->a3/p??an/NULL 注：p代表指针;NULL/p代表头结点

＝》 head->NULL/p->an/p->an-1/p->an-2/p??a1/NULL ●循环链表的操作：插入X，删除X，查找X，计算结点个数； 用p=head->next来判断一次计算结点个数完成； 程序段如下： k=0; do{ k++;

p=p->next;

}while(p!=head->next); ● 双向链表 ●多项式相加

● 有序链表合并

例程：已知两个字符串S，T，求S和T的最长公子串； 1、逻辑结构：字符串 2、存储结构：数组

3、算法： 精化（精细化工）**老顽童注：此处“精细化工”说明好像不对！

s=\ t=\

当循环到s.len-1时，有两种情况：s=\、s=\ s.len-2时，有三种情况：s=\、s=\、s=\ .

. .

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这句话的意思都不晓得，别说是让我 写程序了（到这份上也不怕把丑事都抖出来了:《数据结构》的课程设计也是哈科大的littlebob兄帮我做的，很遗憾，他高程就差几分，希望他早日成 功，我们都要向他学习）等于说我的C知识九成都是在大二下学期的时候学的。而且全是自学的。拿这个周末来说吧。我三天时间就看完了一本C语言大全。当然， 并不是从头到尾，只是根据自己的实际情况，重点是指针和数据结构那块。C最要的便是指针。程序员考试下午试题最重要的便是递归问题（1～2道，没有掌握就 没希望了哦）。我说这些并不是为了表明自己多么用功，只是希望每位\学者\都有所侧重。

第三天

排序查找是我自己觉得最头疼的算法了,常搞混去的啊.不知道各位学得如何,如果不错,还请告诉我一些经验!

查找

一、 知识点 /静态查找->数组 1、 什么是查找

\\动态查找->链树 ●顺序查找，时间复杂度 O(n)

●折半查找：条件：有序；时间复杂度 O(nlog2n) (时间复杂度实际上是查找树的高度)

●索引查找：条件：第I+1块的所有元素都大于第Ｉ块的所有元素。 算法：根据index来确定X所在的块（i） 时间复杂度：m/2 在第Ｉ块里顺序查找X 时间复杂度：n/2 总的时间复杂度：(m+n)/2

●二叉排序树 1）定义：左子树键值大于根节点键值；右子树键值小于根的键值，其左右子树均为二叉排序树。

2）特点：中序遍历有序->（删除节点用到此性质）

3）二叉排序树的查找：如果根大于要查找的树，则前左子树前进，如果根小于要查找的树，则向右子树前进。

4）结点的插入->二叉排序树的构造方法

5）结点删除（难点） 1、右子树放在左子树的最右边 2、左子树放在右子树的最左边 ●avl树（二叉平衡树）：左右子树高度只能差１层，即｜h｜<=1其子树也一样。

●B树：n阶B树满足以下条件 1）每个结点（除根外）包含有N～2N个关链字。 2）所有叶子节点都在同一层。 3）B树的所有子树也是一棵B树。 特点：降低层次数，减少比较次数。

排序

一、知识点

1、排序的定义

/内排序：只在内存中进行 2、排序的分类

\\外排序：与内外存进行排序 内排序： /直接插入排序 1）插入排序

\\shell排序 /冒泡排序 2）交换排序

\\快速排序

/简单选择排序 3）选择排序 堆

\\ 锦标赛排序 4）归并排序（二路）

5）基数排序（多关链字排序）

3、时间复杂度（上午题目常考，不会求也得记住啊兄弟姐妹们！）

* * * * * * 15 * * * 15 * * *

/稳定 * * * * * * * * 15 15 * * * *(前后不变) 排序

\\ 不稳定 * * * * * * * * 15 15 * * * *(前后改变)

经整理得:选择、希尔、堆、快速排序是不稳定的；直接插入、冒泡、合并排序是稳定的。

●锦标赛排序方法： 13 16 11 18 21 3 17 6 \\ / \\ / \\ / \\ / 13 11 3 6 \\ / \\ / 11 3 \\ /

3（胜出，将其拿出，并令其为正无穷&Go On）

●归并排序方法： 13 16 11 18 21 3 17 6 \\ / \\ / \\ / \\ / 13,16 11,18 3,21 6,17 \\ / \\ / 11,13,16,18 3,6,17,21 \\ / 3,6,11,13,16,17,18,21

●shell排序算法：1）定义一个步长（或者说增量）数组D[m]；其中：D[m-1]=1(最后一个增量必须为1，否则可能不完全) 2）共排m趟，其中第i趟增量为D[i],把整个序列分成D[i]个子序列，分别对这D[i]个子序列进行直接插入排序。 程序如下： for(i=0;i

{对第i个子序列进行直接插入排序； 注意：下标之差为D[i]; } }

●快速排序 ( smaller )data ( bigger )

d[] i-> 13 16 11 18 21 3 17 6 24 8 <-j 先从后往前找，再从前往后找。

思想：空一个插入一个，i空j挪，j空i挪（这里的i,j是指i,j两指针所指的下标）。

一次执行算法：1）令temp=d[0](枢纽)，i=0,j=n-1; 2）奇数次时从j位置出发向前找第一个比temp小的元素，找到后放到i的位置(d[i]=d[j];i++;) i往后挪。

3）偶数次时从i开始往后找第一个比temp大的数，（d[j]=d[i];j--;)

4）当i=j时，结束循环。d[i]=temp；

再用递归对左右进行快速排序，因为快速排序是一个典型的递归算法。

●堆排序

定义：d[n]满足条件：d[i]d[2i+1]&&d[i]>d[2i+2] 小堆（上小下大） 判断是否为堆应该将其转换成树的形式。总共排序n-1次

调整(重点)

程序: flag=0;

while(i<=n-1) {

if(d[i]

{ if(d[2*i+1]>d[2*i+2]) 8 24 {d[i]<->d[2*i+1]; 24 21 -> 8 21

i=2*i+1; else {

d[i]<->d[2*i+2]; i=2*i+2; } } else

flag=1; //是堆 }

堆排序过程：

●基数排序(多关键字排序) 扑克: 1) 大小->分配

2) 花色->分配,收集 思想:分配再收集.

构建链表:链表个数根据关键字取值个数有关. 例:将下面九个三位数排序:

321 214 665 102 874 699 210 333 600 定义一个有十个元素的数组:

a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] 第一趟(个位): 210 321 102 333 214 665 699

600 874

结果: 210 600 321 102 333 214 874 665 699 第二趟(十位): 600 210 321 333 665 874 699

102 214

结果: 600 102 210 214 321 333 665 874 699 第三趟(百位): 102 210 321 600 874 214 333 665 699

结果: 102 210 214 321 333 600 665 699 874(排序成功)

最近在看一位程序员的笔记,也挺不错的啊.这应当是他的网站.他总说他的网站人气不够,现在顺便就帮他宣传一下啦！http://zhgpa.vicp.net/bbs，大家有时间多去去哦，呵呵!谢谢大伙支持！另外,还向大家推荐一个网站：http://kaowang.com/，挺不错的一个考试网站。学到不少东东啊！

八大类算法

程序员考试下午试题最后一道一般是八大类算法里头的.大家尤其要注意的是递归，因为近几年都考了，而且有的还考两题。可以说如果我们不掌握递归就没有掌握C，况且递归是C里的难点。为了控制合格率，程序员考试不会让我们轻松过关的，为了中国软件业，我想也应该这样啊。 /数据结构(离散) 迭代

\\数值计算(连续) 枚举 策略好坏很重要 递推 递归 回溯 分治 贪婪 动态规划

其中：递推、递归、分治、动态规划四种算法思想基本相似。都是把大问题变成小问题，但技术上有差别。

第四天

枚举:

背包问题:

枚举策略：1)可能的方案：2N

2)对每一方案进行判断.

枚举法一般流程：

while(还有其他可能方案)

{ 按某种顺序可难方案; 检验方案; if(方案为解) 保存方案; } } 枚举策略:

例：把所有排列枚举出来 P6=6!. Min:123456 Max:654321

a1a2a3a4a5a6=>?(下一排列)=>? 比如:312654的下和种情况=>314256

递归

递归算法通常具有这样的特征：为求解规模为N的问题，设法将它分解成一些规模较小的问题，然后从这些较小问题的解能方便地构造出题目所需的解。而这些规 模较小的问题也采用同样的方法分解成规模更小的问题，通过规模更小的问题构造出规模校小的问题的解，如此不断的反复分解和综合，总能分解到最简单的能直接 得到解的情况。

因此,在解递归算法的题目时,要注意以下几点: 1) 找到递归调用的结束条件或继续递归调用条件. 2) 想方设法将处理对象的规模缩小或元素减少.

3) 由于递归调用可理解为并列同名函数的多次调用,而函数调用的原则是一层一层调用,一层一层返回.因此,还要注意理解调用返回后的下一个语句的作用.在一些 简单的递归算法中,往往不需要考虑递调用返回后的语句处理.而在一些复杂的递归算法中,则需要考虑递归调用返回后的语句处理和进一步的递归调用.

4) 在读递归程序或编写递归程序时,必须要牢记递归函数的作用,这样便于理解整个函数的功能和知道哪儿需要写上递归调用语句.当然,在解递归算法的题目时,也需要分清递归函数中的内部变量和外部变量. 表现形式:

●定义是递归的(二叉树,二叉排序树) ●存储结构是递归的(二叉树,链表,数组) ●由前两种形式得出的算法是递归的

一般流程: function(variable list(规模为N)) { if(规模小,解已知) return 解; else {

把问题分成若干个部分; 某些部分可直接得到解;

而另一部分(规模为N-1)的解递归得到; } }

例1：求一个链表里的最大元素.

大家有没想过这个问题用递归来做呢?

非递归方法大家应该都会哦? Max(nodetype *h) { nodetype *p;

nodetype *q; //存放含最大值的结点 Int max=0; P=h;

While(p!=NULL){

if (maxdata) { max=p->data; q=p; }

p=p->next; }

return q; }

下面真经来了,嘻嘻嘻~~~ *max(nodetype *h) { nodetype *temp; temp=max(h->next); if(h->data>temp->data) return h; else

return temp; }

大家有空想想下面这个算法：求链表所有数据的平均值(我也没试过)，不许偷懒，用递归试试哦!

递归程序员考试题目类型：1)就是链表的某些操作(比如上面的求平均值) 2)二叉树(遍历等)

例2.判断数组元素是否递增

int jidge(int a[],int n) { if(n==1) return 1; else

if(a[0]>a[1]) return 0;

else return jidge(a+1,n-1); }

例3.求二叉树的高度(根据二叉树的递归性质:(左子树)根(右子树)) int depth(nodetype *root) { if(root==NULL) return 0; else {

h1=depth(root->lch); h2=depth(root->rch);

return max(h1,h2)+1; } }

自己想想求二叉树结点个数(与上例类似)

例4.已知中序遍历和后序遍历,求二叉树. 设一二叉树的:

中序 S:E D F B A G J H C I ^start1 ^j ^end1 后序 T:E F D B J H G I C A ^start2 ^end2 node *create(char *s,char *t, int start1,int start2,int end1,int end2)

{ if (start1>end1) return NULL; //回归条件 root=(node *)malloc(sizeof(node)); root->data=t[end2];

找到S中T[end2]的位置为 j

root->lch=create(S,T,s1,j-1,start1,j+start2-start1-1); root->rch=create(S,T,j+1,end1,j+start2-start1,end2-1); return root; }

例5.组合问题

n 个数: (1,2,3,4,?n)求从中取r个数的所有组合. 设n=5,r=3;

递归思想：先固定一位 5 (从另四个数当中选二个) 5,4 (从另三个数当中选一个) 5,4,3 (从另二个数当中选零个) 即：n-2个数中取r-2个数的所有组合 ? 程序:

void combire(int n,int r) { for(k=n;k>=n+r-1;k--) { a[r]=k;

if(r==0) 打印a数组(表示找到一个解); else combire(n-1,r-1); } }

第五天

回溯法:

回溯跟递归都是程序员考试里常出现的问题,大家必须掌握! 回溯法的有关概念:

1) 解答树:叶子结点可能是解,对结点进行后序遍历. 2) 搜索与回溯

五个数中任选三个的解答树(解肯定有三层,至叶子结点): ROOT 虚根

/ / | \\ \\ 1 2 3 4 5 / | | \\ / | \\ /\\ | 2 3 4 5 3 4 5 4 5 5 /|\\ /\\ | /\\ | | 3 4 5 4 5 5 4 5 5 5

回溯算法实现中的技巧:栈 要搞清回溯算法，先举一个(中序遍历二叉树的非递归算法)来说明栈在非递归中所起的作用。

A 过程：push()->push()->push()->push()栈内结果:ABDE(E为叶子,结束进栈)

/ \\ pop() ABD(E无右孩子,出栈) B C pop() AB(D无右孩子,出栈) /\\ pop() A(B有右孩子,右孩子进栈) D F . . / /\\ . . E G H . . / . .

I 最后结果： EDBGFIHAC 简单算法: ?

if(r!=NULL) //树不空 { while(r!=NULL) { push(s,r);

r=r->lch; //一直向左孩子前进 }

while(!empty(s)) // 栈非空,出栈 { p=pop(s);

printf(p->data);

p=p->rch; //向右孩子前进 while(p!=NULL) { push(s,p);

p=p->lch; //右孩子进栈 }

}

} //这就是传说中的回溯,嘻嘻??没吓着你吧

5选3问题算法: 思想: 进栈:搜索 出栈:回溯

边建树(进栈)边遍历(出栈) 基本流程:

太复杂了,再说我不太喜欢用WORD画图（有损形象），以后再整理! 程序: n=5;r=3 ??

init(s) //初始化栈 push(s,1) //根进栈

while(s.top

判断该\解\是否为解.

x=pop(s); //保留x,判断是否为最大值n,如果是n,则出栈 while(x==n) x=pop(s); push(s,x+1);

while(s.top

背包问题: TW=20 , w[5]={6,10,7,5,8} 解的条件:1) 该解答树的叶子结点 2) 重量最大

解答树如下： ROOT / | | | \\

6 10 7 5 8 / | | \\ / | \\ / \\ | 10 7 5 8 7 5 8 5 8 8 | | | 5 8 8 程序:

temp_w 表示栈中重量和 ?

init(s); //初始化栈 i=0;

While(w[i]>TW) i++;

If(i==n) Return -1; //无解 Else {

Push(s,i); Temp_w=w[i]; i++;

while(i

max_w=0;

while(!empty(s)) { if(max_w

while(xTW) x++; while(x

temp_w=temp_w+w[x]; x++;

while(xTW) x++; } }

请大家思考:四色地图问题,比如给中国地图涂色,有四种颜色,每个省选一种颜色,相邻的省不能取同样的颜色.不许偷懒，不能选人口不多于xxxxＷ的\大国\哦!如果真的有一天台湾独立了，下场就是这样了，一种颜色就打发了，不过台湾的程序员们赚到了，省事！呵呵。

贪婪法:

不求最优解,速度快(以精确度换速度)

例:哈夫曼树,最小生成树

装箱问题:

有n个物品,重量分别为w[n]，要把这n个物品装入载重为TW的集装箱内,需要几个集装箱?

思想1:对n个物品排序

拿出第1个集装箱，从大到小判断能不能放。 2 ? 3 ?

. ? . ?

思想2: 对n个物品排序

用物品的重量去判断是否需要一只新箱子，如果物品重量小于本箱子所剩的载重量,则装进去,反之则取一只新箱子。

程序:

count=1;qw[0]=TW; for(i=0;i

k=0;

while(kqw[k]) k++;

if(w[i]<=qw[k]) qw[k]=qw[k]-w[i];

code[i]=k; //第i个物品放在第k个箱子内 else

{count++; //取一个新箱子 qw[count-1]=TW-w[i]; code[i]=count-1; } }

用贪婪法解背包问题:

n个物品，重量:w[n] 价值v[i]

背包限重TW，设计一个取法使得总价值最大. 方法:

0 1 2 3 ? n-1 w0 w1 w2 w3 ? wn-1 v0 v1 v2 v3 ? vn-1

v0/w0 ? v(n-1)/w(n-1) 求出各个物品的\性价比\

先按性价比从高到低进行排序

已知:w[n],v[n],TW 程序: ?

for(I=1;I

d[i]=v[i]/w[i]; //求性价比 for(I=0;I

for(j=0;jmax)

{ max=d[j];x=j; }

} e[i]=x; d[x]=0; }

temp_w=0;temp_v=0; for(i=0;i

{ if(temp_w+w[e[i]]<=TW) temp_v=temp_v+v[e[v]]; } 分治法:

思想:把规模为n的问题进行分解,分解成几个小规模的问题.然后在得到小规模问题的解的基础上,通过某种方法组合成该问题的解.

例:数轴上有n个点x[n],求距离最小的两个点. 分:任取一点,可以把x[i]这n个点分成两个部分 小的部分 分点 大的部分

|_._.__.__.____._|__._._.__._.__._______._.__._._.__.___._____._| 治:解=min{小的部分的距离最小值; 大的部分的距离最小值;

大的部分最小点和小的部分最大点这两点之差;}

第六天

快考试了， 老师没有多说什么，他只是给我们讲了讲近三年试题情况，并详细讲述了两道题目：一道递归，另一道回溯。不过今天不知怎么回事，我感觉特别累，也特别想睡 觉。所以没什么感觉。这里就不说了，两道题目都有的，递归那题是2001年最后一题,回溯是在《程序员教程》P416，老师说高程曾经考过，有兴趣自己看 看也能看懂的。老师特意为我们出了一份下午试题，我现在把他拿出来让大家参考参考。到这里，就到这里！

程序员考试下午试题（模拟）

一、把一个字符串插入到另一个字符串的某个位置（指元素个数）之后 char *insert(char *s，char *t，int position) { int i;

char *target;

if（position>strlen(t)） printf(\ else

{ for (i=0;i< （1） ;i++) { if (i

{ if(i< （2） ) target[i]=t[i]; else （3） ;

} } }

return garget; }

二、辗转相除法求两个正整数的最大公约数 int f(int a,int b) { if (a==b) （4） ; else

{ if (a>b) return f(a-b,b); else （5） ; } }

三、求一个链表的所有元素的平均值 typedef struct { int num; float ave; }Back;

typedef struct node{ float data; struct node *next; } Node;

Back *aveage（Node *head） { Back *p,*q;

p=（Back *）malloc（sizeof（Back））; if （head==NULL） { p->num=0; p->ave=0; } else

{ （6） ;

p->num=q->num+1; （7） ; } retuen p; }

main()

{ Node *h; Back *p;

h=create(); /*建立以h为头指针的链表*/ if (h==NULL) printf(\没有元素\ else { p=aveage(h);

printf(\链表元素的均值为：o\ } }

四、希尔排序

已知待排序序列data[n]；希尔排序的增量序列为d[m]，其中d[]序列降序

排列，且d[m-1]=1。其方法是对序列进行m趟排序，在第i趟排序中，按增量d[i]把整个序列分成d[i]个子序列，并按直接插入排序的方法对每个子序列进行排序。

希尔排序的程序为：

void shellsort(int *data,int *d,int n,int m) { int i,j;

for (i=0;i

for (j=0; （1） ;j++) shell( （2） ); }

void shell(int *data,int d,int num,int n) { int i,j,k,temp;

for (i=1; （3） ;i++) { j=0;

temp=data[j+i*d];

while ((j

for (k=j;k

五、求树的宽度

所谓宽度是指在二叉树的各层上，具有结点数最多的那一层上的结点总数。本算法是按层次遍历二叉树，采用一个队列q，让根结点入队列，最后出队列，若有左右子树，则左右子树根结点入队列，如此反复，直到队列为空。 int Width(BinTree *T)

{ int front=-1,rear=-1; /* 队列初始化*／

int flag=0,count=0,p;/*p用于指向树中层的最右边的结点，flag记录层中结点数的最大值。*／ if(T!=Null)

{ rear++; （1） ; flag=1; p=rear; }

while( （2） ) { front++; T=q[front];

if(T->lchild!=Null)

{ rear++; （3） ; count++; } // if(T->rchild!=Null)

{ rear++; q[rear]=T->rchild; （4） ; } if(front==p) /* 当前层已遍历完毕*/ { if( （5） ) flag=count; count=0; // p=rear; /* p指向下一层最右边的结点*/

} }

return(flag); }

六、区间覆盖

设在实数轴上有n个点（x0，x1，??，xn-2，xn-1），现在要求用长度为1的单位闭区间去覆盖这n个点，则需要多少个单位闭区间。 int cover(float x[ ], int num) { float start[num],end[num]; int i ,j ,flag, count=0; for (i=0;i

for (j=0;j< （1） ;j++)

{ if ((start[j]>x[i])&&(end[j]-x[i]<=1)) （2） ; else if ( （3） ) end[j]=x[i];

else if ((x[i]>start[j])&&(x[i]

if ( （4） )

{ end[count]=x[i]; （5）; count++; } }

return count-1; }

start[count]=x[i] 七、围棋中的提子

在围棋比赛中，某一方（假设为黑方）在棋盘的某个位置（i，j）下子后，有可能提取对方（白方的一串子）。以W[19][19]表示一个棋盘，若W [i][j]=0表示在位置（i，j）上没有子，W[i][j]=1表示该位置上的是黑子，W[i][j]=-1表示该位置上是白子。可以用回溯法实现提 子算法。

下列程序是黑棋（tag=1）下在（i，j）位置后判断是否可以吃掉某些白子，这些确定可以提掉的白子以一个线性表表示。 问题相应的数据结构有：

#define length 19 /*棋盘大小*/

#define max_num 361 /*棋盘中点的数量*/ struct position { int row; int col; }; /*棋子位置*/

struct killed { struct position data[max_num]; int num; } *p; /*存储可以吃掉的棋子位置*/

struct stack { struct position node[max_num]; int top; }; /*栈*/

int w[length][length]; /*棋盘中双方的棋子分布*/

int visited[length][length]; /*给已搜索到的棋子位置作标记，初值为0，搜索到后为1*/

struct killed *kill(int w[length][length],int r,int c,int tag) { struct killed *p; struct position *s; struct stack S;

for (i=0;i

S.top=-1; p->num=-1;

if (w[r-1][c]==tag*(-1)) s->row=r-1; s->col=c;

else if (w[r+1][c]==tag*(-1)) s->row=r+1; s->col=c; else if (w[r][c-1]==tag*(-1)) s->row=r; s->col=c-1; else if (w[r][c+1]==tag*(-1)) s->row=r; s->col=c+1; else p->len=0; return p;

push(S,s); visited[s->row][s->col]=1; flag=search(s,tag); while ( （2）)

{ push(S,s); visited[s->row][s->col]=1; （3）; }

while (S->top>=0) { pop(S); （4）;

flag=search(s,tag); while (flag) { push(S,s); visit(s);

flag=search(s); } } }

void push( struct stack *S, struct position *s) { S->top++;

S->node[S->top].row=s->row; S->node[S->top].col=s->col; p->num++;

p->data[p->num].row=s->row; p->data[p->num].col=s->col; }

void pop(struct stack *S) { S->top--; }

struct position *gettop(struct stack *S) { struct position *s;

s->row=S->data[S->top].row; s->row=S->data[S->top].row; return s; }

int search(struct position *s,int tag) { int row,col;

row=s->row; col=s->col;

if (W[row+1][col]=(-1)*tag)&&(!visited[row+1][col]) { s->row=row+1;s->col=col; return 1;}

if (W[row-1][col]=(-1)*tag)&&(!visited[row-1][col]) { s->row=row-1;s->col=col; return 1;}

if (W[row][col+1]=(-1)*tag)&&(!visited[row][col+1]) { s->row=row;s->col=col+1; return 1;}

if (W[row][col-1]=(-1)*tag)&&(!visited[row][col-1]) { s->row=row;s->col=col-1; return 1} （5）; }

答案：

（1）strlen(s)+strlen(t) （2）position+strlen(t) （3）target[i]=s[i-strlen(t)]

（4）return a （5）return f(a,b-a) （6）q=aveage(head->next) （7）

p->ave=(head->data+q->ave*q->num)/p->num

（1）j

（1）q[rear]=T （2）front

lchild （4）count++ （5）flag

（1）count （2）(x[i]>end[j])&&(x[i]-start[j]<=1) （3）start[j]=x[i] （4）!flag （5） （1）visited[i][j]=0 （2）flag （3）flag=search(s,tag) （4）s=gettop(S) （5）return 0

课已全部授完,也该收笔了.望对大家有所启发吧!

本文来源：https://www.bwwdw.com/article/ap73.html