软考程序员数据结构笔记

软考指南：程序员数据结构笔记

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

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

树：二叉树

集合：查找，排序

图(不考)

能力：

分析，解决问题的能力

过程：

●确定问题的数据。

●确定数据间的关系。

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

●确定算法

●编程

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

一、数组

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

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

已知data[0][0]的内存地址，且已知一个元素所占内存空间s求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=130********

b=87081299

数组:

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

b[]:8 7 0 8 1 2 9 9

由于以上的结构不够直观(一般越是直观越容易解决) 将其改为:

a[]:118 6 1 2 5 9 6 5 0 3 1 a[0]=11(位数)

b[]: 89 9 2 1 8 0 7 8 0 0 0 b[0]=8

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

c[]:117 6 4 3 3 0 4 4 2 3 1 c[0]的值(C位数)由c[max_s+1]决定!

注意:在求C前应该将C(max_s+1)位赋0.否则为随机数; 较小的整数高位赋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%10;

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*/

/* 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%10;

}

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%10;

}

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("%d,",m[i]); PRIN

}

main(){

int s;

int a[20],b[20],c[20];

char da[]={"123456789"};

char db[]={"12344443"};

a[0]=strlen(da);

b[0]=strlen(db);

printf("a[0]=%d ",a[0]);

printf("b[0]=%d",b[0]); PRIN

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

printf("flag=%d ",flag); PRIN

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="abaabcacb"

t="abdcabcaabcda"

当循环到s.len-1时，有两种情况：s="abaabcacb"、s="abaabcacb"

s.len-2时，有三种情况：s="abaabcacb"、s="abaabcacb"、s="abaabcacb"

.

.

.

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 --0

O O --1

O O O O --2

此树的高度为2

2.二叉树定义:

结点个数>=0 .

3. 术语:左右孩子,双亲,子树,度,高度等概念.

4. 二叉树的性质

●层次为I的二叉树I层结点2I 个

●高度为H的二叉树结点2H+1-1个

●H(点)=E(边)+1

●个数为N的完全二叉树高度为|_LOG2n_|

●完全二叉树结点编号:从上到下,从左到右.

i结点的双亲: |_i/2_| |_i-1/2_| 1

i结点的左孩子: 2i 2i+1 2 3

i结点的右孩子: 2i+1 2i+2 4 5 6 7

(根) 1为起点0为起点

二叉树的存储结构:

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 1 2 3 4 5 6 7 8

元素A B C D E F G H I

双亲-1 0 0 1 2 2 3 3 4

3) 双亲孩子表示法

数组下标0 1 2 3 4 5 …

元素A B C D E F …

双亲-1 0 0 1 2 2 …

左子1 3 4 …

右子2 -1 5 …

结构:

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个

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

查找

一、知识点/静态查找->数组

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 * * * *(前后改变)

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

●锦标赛排序方法：1316111821317 6

////

13113 6

//

11 3

/

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

●归并排序方法：1316111821317 6

////

13,1611,183,216,17

//

11,13,16,183,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

{for(j=0;j

{对第i个子序列进行直接插入排序；

注意：下标之差为D[i];

}

}

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

d[]i->13161118213176248<-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[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]

第一趟(个位): 210321102333214665699

600874

结果: 210600321102333214874665699

第二趟(十位): 600210321333665874699

102214

结果: 600102210214321333665874699

第三趟(百位): 102210321600874

214333665

699

结果: 102210214321333600665699874(排序成功)

八大类算法

程序员考试下午试题最后一道一般是八大类算法里头的.大家尤其要注意的是递归，因为近几年都考了，而且有的还考两题。可以说如果我们不掌握递归就没有掌握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 虚根

//|

1234 5

/ ||/ | /|

234534545 5

/| /|/||

3 4 5 4 5 54 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

push(s,s.data[s.top]+1); //孩子入栈

while(!empty(s))

{ if(s.top=r-1)

判断该"解"是否为解.

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

while(x==n)

x=pop(s);

push(s,x+1);

while(s.top

push(s,s.data[s.top]+1);

}

背包问题: TW=20 , w[5]={6,10,7,5,8}

解的条件:1) 该解答树的叶子结点

2) 重量最大

解答树如下：ROOT

/ | | |

6 10758

/ | | / | / |

10 7 58 758 58 8

| ||

5 88

程序:

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

{ push(s,i);

temp_w+=w[i];

i++;

}

max_w=0;

while(!empty(s))

{ if(max_w

max_w=temp_w;

x=pop(s);

temp_w-=w[x];

x++;

while(xTW)

x++;

while(x

{ push(s,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，设计一个取法使得总价值最大.

》椒?

0123…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

{ max=-1;

for(j=0;j

{ if(d[j]>max)

{ 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{小的部分的距离最小值;

大的部分的距离最小值;

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

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

一、把一个字符串插入到另一个字符串的某个位置（指元素个数）之后

char *insert(char *s，char *t，int position)

{ int i;

char *target;

if（position>strlen(t)） printf("error");

else

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

{ if (i

target[i]=s[i];

else

{ 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("链表元素的均值为：%6f",p->ave);

}

}

四、希尔排序

已知待排序序列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）);