知識:
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=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進位 0 1 1 0 0 1 1 1 1 0 0
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.否則為隨機數; 較小的整數高位賦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<stdio.h>
#include<string.h>
#define PRIN printf("\n");
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\t",a[0]);
printf("b[0]=%d",b[0]); PRIN
change(da,db,a,b,c);
printf("flag=%d\n",flag); PRIN
printf("-----------------\n");
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("-----------------\n");
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.len-l+1&&!tag;j++){
判斷s中長度為l的第j個子串是否為t的子串;
如果是：tag=1;
}
模式結構：
tag=0;
for(l=s.len;l>0&&tag==0;l--) {
for(j=0;j<s.len-l+1&&!tag;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 * * * *(前后改變)
經整理得:選擇、希爾、堆、快速排序是不穩定的；直接插入、冒泡、合并排序是穩定的。
●錦標賽排序方法： 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<m;i++)
{for(j=0;j<d[i];j++)
{對第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] 大堆（上大下�。�
d[i]>d[2i+1]&&d[i]>d[2i+2] 小堆（上小下大）
判斷是否為堆應該將其轉換成樹的形式�？偣才判騨-1次
調整(重點)
程序: flag=0;
while(i<=n-1) {
if(d[i]<d[2*i+1])||(d[i]<d[2*i+2]))
{ 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(排序成功)
八大類算法
程序員考試下午試題最后一道一般是八大類算法里頭的.大家尤其要注意的是遞歸，因為近幾年都考了，而且有的還考兩題�？梢哉f如果我們不掌握遞歸就沒有掌握C，況且遞歸是C里的難點。為了控制合格率，程序員考試不會讓我們輕松過關的，為了中國軟件業，我想也應該這樣啊。
/數據結構(離散)
迭代
\數值計算(連續)
枚舉 策略好壞很重要
遞推
遞歸
回溯
分治
貪婪
動態規劃
其中：遞推、遞歸、分治、動態規劃四種算法思想基本相似。都是把大問題變成小問題，但技術上有差別。
枚舉:
背包問題:
枚舉策略：1)可能的方案：2N
2)對每一方案進行判斷.
枚舉法一般流程：
while(還有其他可能方案)
{ 按某種順序可難方案;
檢驗方案;
if(方案為解)
保存方案;
}
}
枚舉策略:
例：把所有排列枚舉出來 P6=6!.
Min:123456
Max:654321
a1a2a3a4a5a6=>?(下一排列)=>?
比如:312654的下和種情況=>314256
遞歸
遞歸算法通常具有這樣的特征：為求解規模為N的問題，設法將它分解成一些規模較小的問題，然后從這些較小問題的解能方便地構造出題目所需的解。而這些規模較小的問題也采用同樣的方法分解成規模更小的問題，通過規模更小的問題構造出規模校小的問題的解，如此不斷的反復分解和綜合，總能分解到最簡單的能直接得到解的情況。
因此,在解遞歸算法的題目時,要注意以下幾點:
1) 找到遞歸調用的結束條件或繼續遞歸調用條件.
2) 想方設法將處理對象的規�？s小或元素減少.
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 (max<p->data) {
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<r-1)&&(s.data[s.top]!=n) //有孩子
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<r-1)&&(s.data[s.top]!=n)
push(s,s.data[s.top]+1);
}
背包問題: 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<n)&&(temp_w+w[i]<=TW)
{ push(s,i);
temp_w+=w[i];
i++;
}
max_w=0;
while(!empty(s))
{ if(max_w<temp_w)
max_w=temp_w;
x=pop(s);
temp_w-=w[x];
x++;
while(x<n)&&(temp_w+w[x]>TW)
x++;
while(x<n)
{ push(s,x);
temp_w=temp_w+w[x];
x++;
while(x<n)&&(temp_w+w[x]>TW)
x++;
}
}
請大家思考:四色地圖問題,比如給中國地圖涂色,有四種顏色,每個省選一種顏色,相鄰的省不能取同樣的顏色.不許偷懶，不能選人口不多于xxxxＷ的"大國"哦!如果真的有一天臺灣獨立了，下場就是這樣了，一種顏色就打發了，不過臺灣的程序員們賺到了，省事！呵呵。
貪婪法:
不求最優解,速度快(以精確度換速度)
例:哈夫曼樹,最小生成樹
裝箱問題:
有n個物品,重量分別為w[n]，要把這n個物品裝入載重為TW的集裝箱內,需要幾個集裝箱?
思想1:對n個物品排序
拿出第1個集裝箱，從大到小判斷能不能放。
2 …
3 …
. …
. …
思想2: 對n個物品排序
用物品的重量去判斷是否需要一只新箱子，如果物品重量小于本箱子所剩的載重量,則裝進去,反之則取一只新箱子。
程序:
count=1;qw[0]=TW;
for(i=0;i<n;i++)
{
k=0;
while(k<count)&&(w[i]>qw[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<n;I++)
d[i]=v[i]/w[i]; //求性價比
for(I=0;I<n;I++)
{ max=-1;
for(j=0;j<n;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<n;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<position)
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<m;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<i)&&( （4） ))
j++;
for (k=j;k<i;k++)
data[k+1]=data[k];
�。�5） ;
�。�6） }
}
五、求樹的寬度
所謂寬度是指在二叉樹的各層上，具有結點數最多的那一層上的結點總數。本算法是按層次遍歷二叉樹，采用一個隊列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<num;i++)
{ flag=1;
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]<end[j])) flag=0;
if (flag) break;
}
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表示該位置上是白子�？梢杂没厮莘▽崿F提子算法。
下列程序是黑棋（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<length;i++)
for (j=0;j<length;j++)
�。�1） ;
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<d[i] （2）data,d[i],j,n�。�3）num+i*d<n �。�4）data[j+i*d]<temp �。�5）data[j]=temp
（1）q[rear]=T （2）front<p （3）q[rear]=T->lchild （4）count++ （5）flag<count
（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
文章來源于領測軟件測試網 http://www.kjueaiud.com/
