未完待續(xù)==
一、數(shù)據(jù)結(jié)構(gòu)與算法
1. 排序
排序
- 插入排序
N-1趟排序組成艇抠。從P=1到P=N-1趟妒御，插入排序保證從位置0到位置P上的元素為已排序狀態(tài)。
反著比較冈绊，若比當前元素大依次向后移位侠鳄，否則插入。
void InsertSort(int *a, int n)
{
int temp;
for(int i=1; i<n; i++)
{
temp = a[i]; //即將新插入的值
for (int j=i; j>0 && a[j-1]>temp; j--)
a[j] = a[j-1]; //元素依次向后移動
a[j] = temp; //插入空擋
}
}
- 選擇排序
每次選擇最小的元素死宣，交換到相應位置伟恶。
void SelectSort(int *a, int n)
{
for(int i=0; i<n; i++)
{
int min = i; //先賦值每趟的開始位置為最小
for (int j=i+1; j<n; j++)
{
if(a[j]<a[min])
min = j; //時刻更新最小位置
}
if(i!=min)
swap(a[i], a[min]);
}
}
- 冒泡排序
void BubbleSort(int *a, int n)
{
for (int i=0; i<n; i++)
{
for(int j=i+1; j<n; j++)
{
if(a[i]>a[j])
swap(a[i], a[j]);
}
}
}
- 歸并排序
分治思想。
合并兩個已排序的表毅该。兩個輸入數(shù)組A和B博秫，一個輸出數(shù)組C，三個計數(shù)器Aptr眶掌， Bptr挡育， Cptr， A[Aptr]和B[Bptr]中較小者放入C的下一個位置朴爬。當其中一個表沒有剩余時即寒，將其余元素全部拷貝到C中。 - 堆排序
- 快速排序
//partition函數(shù)
int partition(int *a, int left, int right)
{
int temp = a[left]; //為方便起見召噩，最左邊元素為樞紐母赵。其實是不科學的
while(left<right)
{
while(left<right && a[right]>temp)
-- right; //若右側(cè)元素比樞紐元素值大，則繼續(xù)向左查找
a[left] = a[right]; //一旦查找到比樞紐元素小的值具滴，則交換到左邊（樞紐）位置
while(left<right && a[left]<=temp)
++ left;
a[right] = a[left];
}
a[left] = temp; //將樞紐插入空位
return left凹嘲； //返回樞紐位置
}
//quicksort函數(shù)
void QuickSort(int *a, int left, int right)
{
int pivot;
if(left>=right) return;
pivot = partition(a, left, right);
QuickSort(a, left, pivot-1);
QuickSort(a, pivot+1, right);
}
2. 二分查找
//不使用遞歸
int binarySearch(int arry[], int len, int value)
{
if(arry==NULL||len<=0)
return -1;
int start=0;
int end=len-1;
while(start<=end)
{
int mid=start+(end-start)/2;
if(arry[mid]==value)
return mid;
else if(value<arry[mid])
end=mid-1;
else
start=mid+1;
}
return -1;
}
//不要傳參，傳引用調(diào)用构韵，減少垃圾周蹭。
int binarySearchRecursion(int arry[], int value, int start, int end)
{
if(start>end)
return -1;
int mid=start+(end-start)/2;
if(arry[mid]==value)
return mid;
else if(value<arry[mid])
return binarySearchRecursion(arry,value,start,mid-1);
else
return binarySearchRecursion(arry,value,mid+1,end);
}
二趋艘、操作系統(tǒng)
- 進程和線程的區(qū)別
- 一個進程至少有一個主線程谷醉。線程是進程內(nèi)的一個執(zhí)行單元致稀，也是進程內(nèi)的可調(diào)度實體。
- 進程是資源分配的基本單位俱尼，線程是CPU調(diào)度和分派的基本單位抖单。
- 進程有自己獨立的地址空間，線程共享進程的地址空間遇八，沒有單獨的地址空間矛绘，線程可以有自己的寄存器和堆棧。
- 線程更加靈活刃永，進程更加穩(wěn)定货矮。一個線程死掉就等于整個進程死掉，所以多進程的程序要比多線程的程序健壯斯够，但在進程切換時囚玫，耗費資源較大，效率要差一些读规。但對于一些要求同時進行并且又要共享某些變量的并發(fā)操作抓督，需要用多線程。
- 進程的狀態(tài)
進程的三種狀態(tài)及轉(zhuǎn)換
運行狀態(tài)束亏，阻塞狀態(tài)铃在，就緒狀態(tài)。
進程狀態(tài)轉(zhuǎn)換圖
創(chuàng)建和退出不是進程的狀態(tài)碍遍。阻塞和就緒的區(qū)別：阻塞是等待除CPU以外的資源定铜，而就緒等待的是CPU資源。
- 進程三種狀態(tài)間的轉(zhuǎn)換
一個進程在運行期間怕敬，不斷地從一種狀態(tài)轉(zhuǎn)換到另一種狀態(tài)揣炕，它可以多次處于就緒狀態(tài)和執(zhí)行狀態(tài)，也可以多次處于阻塞狀態(tài)赖捌。
(1) 就緒→執(zhí)行處于就緒狀態(tài)的進程祝沸，當進程調(diào)度程序為之分配了處理機后，該進程便由就緒狀態(tài)轉(zhuǎn)變成執(zhí)行狀態(tài)越庇。
(2) 執(zhí)行→就緒處于執(zhí)行狀態(tài)的進程在其執(zhí)行過程中，因分配給它的一個時間片已用完而不得不讓出處理機奉狈，于是進程從執(zhí)行狀態(tài)轉(zhuǎn)變成就緒狀態(tài)卤唉。
(3) 執(zhí)行→阻塞正在執(zhí)行的進程因等待某種事件發(fā)生而無法繼續(xù)執(zhí)行時，便從執(zhí)行狀態(tài)變成阻塞狀態(tài)仁期。
(4) 阻塞→就緒處于阻塞狀態(tài)的進程桑驱，若其等待的事件已經(jīng)發(fā)生竭恬，于是進程由阻塞狀態(tài)轉(zhuǎn)變?yōu)榫途w狀態(tài)。
- 進程通信的幾種方式
linux系統(tǒng)下：
- 管道（pipe）：管道是一種半雙工的通信方式熬的，數(shù)據(jù)只能單向流動痊硕，而且只能在具有親緣關(guān)系的進程間使用。進程的親緣關(guān)系通常是指父子進程關(guān)系押框。
- 命名管道（named pipe）：命名管道也是半雙工的通信方式岔绸，但是它允許無親緣關(guān)系進程間的通信。
- 信號量（semophore）：信號量是一個計數(shù)器橡伞，可以用來控制多個進程對共享資源的訪問盒揉。它常作為一種鎖機制，防止某進程正在訪問共享資源時兑徘，其他進程也訪問該資源刚盈。因此，主要作為進程間以及同一進程內(nèi)不同線程之間的同步手段挂脑。
- 消息隊列（message queue）：消息隊列是由消息的鏈表藕漱，存放在內(nèi)核中并由消息隊列標識符標識。消息隊列克服了信號傳遞信息少崭闲、管道只能承載無格式字節(jié)流以及緩沖區(qū)大小受限等缺點肋联。
- 信號（signal）：信號是一種比較復雜的通信方式，用于通知接收進程某個事件已經(jīng)發(fā)生镀脂。
- 共享內(nèi)存（shared memory）：共享內(nèi)存就是映射一段能被其他進程所訪問的內(nèi)存牺蹄，這段共享內(nèi)存由一個進程創(chuàng)建，但多個進程都可以訪問薄翅。共享內(nèi)存是最快的 IPC 方式沙兰，它是針對其他進程間通信方式運行效率低而專門設(shè)計的。它往往與其他通信機制翘魄，如信號量鼎天，配合使用，來實現(xiàn)進程間的同步和通信暑竟。
- 套接字（socket）：套解口也是一種進程間通信機制斋射，與其他通信機制不同的是，它可用于不同及其間的進程通信但荤。
線程同步幾種方式罗岖。(一定要會寫生產(chǎn)者、消費者問題腹躁，完全消化理解)
線程的實現(xiàn)方式桑包。 (也就是用戶線程與內(nèi)核線程的區(qū)別)
- 內(nèi)核線程：由操作系統(tǒng)內(nèi)核創(chuàng)建和撤銷。內(nèi)核維護進程及線程的上下文信息以及線程切換纺非。一個內(nèi)核線程由于I/O操作而阻塞哑了，不會影響其它線程的運行赘方。Windows NT和2000/XP支持內(nèi)核線程
- 用戶線程：由應用進程利用線程庫創(chuàng)建和管理，不以來于操作系統(tǒng)核心弱左。不需要用戶態(tài)/核心態(tài)切換窄陡，速度快。操作系統(tǒng)內(nèi)核不知道多線程的存在拆火，因此一個線程阻塞將使得整個進程（包括它的所有線程）阻塞跳夭。由于這里的處理器時間片分配是以進程為基本單位，所以每個線程執(zhí)行的時間相對減少榜掌。
- 死鎖
是指兩個或兩個以上的進程在執(zhí)行過程中优妙，因爭奪資源而造成的一種互相等待的現(xiàn)象，若無外力作用憎账，它們都將無法推進下去套硼。
- 產(chǎn)生原因：
資源競爭引起進程死鎖。
進程推進順序不當胞皱。 - 導致死鎖四個必要條件：
簡潔版：
互斥條件 : 任一時刻只允許一個進程使用資源邪意。
非剝奪條件: 進程已經(jīng)占用的資源, 不會被強制剝奪。
占用并請求條件: 進程占有部分資源 , 申請更多的資源 , 且不會釋放已經(jīng)占有的資源反砌。
循環(huán)等待 : 請求資源的進程形成了循環(huán)雾鬼。
復雜版：
1、互斥條件：指進程對所分配到的資源進行排它性使用宴树，即在一段時間內(nèi)某資源只由一個進程占用策菜。如果此時還有其它進程請求資源，則請求者只能等待酒贬，直至占有資源的進程用畢釋放又憨。
2、請求和保持：指進程已經(jīng)保持至少一個資源锭吨，但又提出了新的資源請求蠢莺，而該資源已被其它進程占有，此時請求進程阻塞零如，但又對自己已獲得的其它資源保持不放躏将。
3、不剝奪條件：指進程已獲得的資源考蕾，在未使用完之前祸憋，不能被剝奪，只能在使用完時由自己釋放肖卧。
4夺衍、環(huán)路等待條件：指在發(fā)生死鎖時，必然存在一個進程——資源的環(huán)形鏈喜命，即進程集合{P0沟沙，P1，P2壁榕，···矛紫，Pn}中的P0正在等待一個P1占用的資源；P1正在等待P2占用的資源牌里，……颊咬，Pn正在等待已被P0占用的資源。 - 處理死鎖的四個方式：
1牡辽、撤消陷于死鎖的全部進程喳篇；
2、逐個撤消陷于死鎖的進程态辛，直到死鎖不存在麸澜；
3、從陷于死鎖的進程中逐個強迫放棄所占用的資源奏黑，直至死鎖消失炊邦；
4、從另外一些進程那里強行剝奪足夠數(shù)量的資源分配給死鎖進程熟史，以解除死鎖狀態(tài)馁害。 - 預防死鎖的方法、避免死鎖的方法：
采用資源靜態(tài)分配蹂匹，破壞“部分分配”條件碘菜；
允許進程剝奪使用其他進程占用的資源，破壞“不可剝奪”條件限寞；
采用資源有序分配法忍啸，破壞“環(huán)路”條件；
互斥條件無法破壞昆烁。
c++基礎(chǔ)知識
C++面試題——基礎(chǔ)概念篇
C++面試出現(xiàn)頻率最高的30道題目（一）
C++面試出現(xiàn)頻率最高的30道題目（二）
C++面試出現(xiàn)頻率最高的30道題目（三）
- static
- 隱藏吊骤。未加static前綴的全局變量和函數(shù)都具有全局可見性；使用static在不同文件中定義同名函數(shù)和同名變量静尼，不必擔心命名沖突白粉。
- 保持變量內(nèi)容持久。全局變量和static變量存儲在靜態(tài)存儲區(qū)鼠渺，存儲在靜態(tài)存儲區(qū)的變量會在程序剛開始運行就完成初始化鸭巴，也是唯一一次初始化。
- 默認初始化為0拦盹。（全局變量也是）鹃祖。
- const
修飾的內(nèi)容不可改變，包括const數(shù)據(jù)成員普舆，const參數(shù)恬口，const返回值校读，const成員函數(shù)。被修飾的東西會被強制保護祖能，可以預防意外變動歉秫，提高程序的健壯性。 - 宏#define和const關(guān)鍵字的區(qū)別
- const是有數(shù)據(jù)類型的常量养铸，而宏常量沒有雁芙，編譯器可以對前者進行靜態(tài)類型安全檢查，而后者只是字符串替換钞螟，沒有類型安全檢查兔甘，在字符替換時可能會發(fā)生意想不到的錯誤。
- 有些編譯器可以對const常量進行調(diào)試鳞滨，不能進行宏調(diào)試洞焙。
- const無法代替宏作為衛(wèi)哨來防止文件的重復包含。
- C++中引用和指針的區(qū)別
引用是對象的別名太援， 操作引用就是操作這個對象闽晦， 必須在創(chuàng)建的同時有效得初始化（引用一個有效的對象， 不可為NULL）提岔， 初始化完畢就再也不可改變仙蛉， 引用具有指針的效率， 又具有變量使用的方便性和直觀性碱蒙， 在語言層面上引用和對象的用法一樣荠瘪， 在二進制層面上引用一般都是通過指針來實現(xiàn)的， 只是編譯器幫我們完成了轉(zhuǎn)換赛惩。 之所以使用引用是為了用適當?shù)墓ぞ咦銮∪缙浞值氖拢?體現(xiàn)了最小特權(quán)原則哀墓。 - C與C++的內(nèi)存分配方式
- 靜態(tài)存儲區(qū)域分配。內(nèi)存在程序編譯時就已經(jīng)分配好喷兼，這塊內(nèi)存在程序的整個運行期間都存在篮绰，如全局變量，static變量季惯。
- 在棧上創(chuàng)建吠各。在執(zhí)行函數(shù)時，函數(shù)內(nèi)部局部變量的存儲單元可以在棧上創(chuàng)建勉抓，函數(shù)執(zhí)行結(jié)束時這些存儲單元自動被釋放贾漏。棧內(nèi)存分配運算內(nèi)置于處理器的指令集中，效率很高藕筋，但是分配的內(nèi)存容量有限纵散。
- 從堆上分配（動態(tài)內(nèi)存分配）。程序在運行的時候用malloc或new申請任意多少的內(nèi)存，程序員負責在何時用free或delete釋放內(nèi)存伍掀。動態(tài)內(nèi)存的生存期自己決定掰茶，使用非常靈活。
- 面向?qū)ο蟪绦蛟O(shè)計的優(yōu)點
開發(fā)時間短硕盹， 效率高符匾， 可靠性高。面向?qū)ο缶幊痰木幋a具有高可重用性瘩例，可以在應用程序中大量采用成熟的類庫（如STL），從而雖短了開發(fā)時間甸各，軟件易于維護和升級垛贤。
數(shù)據(jù)庫
https://www.zhihu.com/question/19552975/answer/123523074
數(shù)據(jù)庫基礎(chǔ)知識復習
