數(shù)據(jù)結構
1. 棧和堆
- 定義
- 棧（stack）又名堆棧半火，是一種運算受限的線性表塞赂，其限制是僅允許在表的一端進行插入和刪除運算。這一端被稱為棧頂跌前，相對地棕兼，把另一端稱為棧底。向一個棧插入新元素又稱作進棧抵乓、入棸橹浚或壓棧，它是把新元素放到棧頂元素的上面灾炭，使之成為新的棧頂元素茎芋；從一個棧刪除元素又稱作出棧或退棧蜈出，它是把棧頂元素刪除掉田弥，使其相鄰的元素成為新的棧頂元素
- 優(yōu)缺點
- 存取速度比堆要快，僅次于直接位于CPU中的寄存器
- 但缺點是铡原，存在棧中的數(shù)據(jù)大小與生存期必須是確定的偷厦，缺乏靈活性。另外燕刻，棧數(shù)據(jù)在多個線程或者多個棧之間是不可以共享的只泼，但是在棧內部多個值相等的變量是可以指向一個地址的，
-
棧和堆的區(qū)別理解
- 棧和堆是什么時候創(chuàng)建的 ---當線程創(chuàng)建時卵洗，os為每一個系統(tǒng)級的線程分配棧请唱，通常情況下操作系統(tǒng)通過調用語言的運行時為應用創(chuàng)建堆
- 分別的作用范圍： 棧附屬與線程，因此當線程結束棧被回收，堆通常是在應用程序啟動的時候被分配十绑，應用程序退出的時候被回收
- 棧和堆的大小由什么決定：線程創(chuàng)建的時候設置棧的大小聚至，在應用程序啟動的時候設置堆的大小，但是在需要的時候擴展本橙，分配器向內存申請
- 棧和堆的速度比較： 棧比堆要快晚岭，因為她的存取模式使她輕松的分配和重新分配內存（指針/整形只是進行簡單的遞增或者遞減運算），然而堆在分配和釋放的時候由更多復雜的bookkeeping參與勋功，另外，在棧上的每個字節(jié)頻繁的被服用也就意味著它可能映射到處理器緩存中库说，所以很快狂鞋；
- 較為經典的理解http://blog.jobbole.com/75321/
-
數(shù)組/鏈表/隊列/棧
- 數(shù)組 是將元素在內存中連續(xù)存放，由于每個元素占用內存相同潜的，可以通過下標迅速訪問數(shù)組中任何元素骚揍。
- 鏈表 鏈表中的元素在內存中不是順序存儲的，而是通過存在元素中的指針聯(lián)系到一起啰挪，每個結點包括兩個部分：一個是存儲 數(shù)據(jù)元素的數(shù)據(jù)域信不，另一個是存儲下一個結點地址的 指針。
- 隊列 隊列是一種操作受限制的線性表亡呵，它只允許在表的前端（front）進行刪除操作抽活，而在表的后端（rear）進行插入操作
- 棧（stack）又名堆棧，它是一種運算受限的線性表锰什。其限制是僅允許在表的一端進行插入和刪除運算下硕。這一端被稱為棧頂，相對地汁胆，把另一端稱為棧底梭姓；
- 棧和隊列的區(qū)別
- 棧是限定只能在表的一端進行插入和刪除操作的線性表。 隊列是限定只能在表的一端進行插入和在另一端進行刪除操作的線性表
2.數(shù)據(jù)結構（Data Structure）是指互相之間存在著一種或多種關系的數(shù)據(jù)元素的集合嫩码。在任何問題中誉尖，數(shù)據(jù)元素之間都不會是孤立的，在它們之間都存在著這樣或那樣的關系铸题，這種數(shù)據(jù)元素之間的關系稱為結構铡恕。根據(jù)數(shù)據(jù)元素間關系的不同特性，通常有下列四類基本的結構：
- 集合結構回挽。在集合結構中没咙，數(shù)據(jù)元素間的關系是“屬于同一個集合”。集合是元素 關系極為松散的一種結構千劈。
- 線性結構祭刚。該結構的數(shù)據(jù)元素之間存在著一對一的關系。
- 樹型結構。該結構的數(shù)據(jù)元素之間存在著一對多的關系涡驮。
- 圖形結構暗甥。該結構的數(shù)據(jù)元素之間存在著多對多的關系，圖形結構也稱作網(wǎng)狀結構捉捅。
算法的時間復雜度和空間復雜度
- 時間復雜度
-
時間頻度
一個算法執(zhí)行所耗費的時間撤防，從理論上是不能算出來的，必須上機運行測試才能知道棒口。但我們不可能也沒有必要對每個算法都上機測試寄月，只需知道哪個算法花費的時間多，哪個算法花費的時間少就可以了无牵。并且一個算法花費的時間與算法中語句的執(zhí)行次數(shù)成正比例漾肮，哪個算法中語句執(zhí)行次數(shù)多，它花費時間就多茎毁。一個算法中的語句執(zhí)行次數(shù)稱為語句頻度或時間頻度克懊。記為T(n)；
-
時間復雜度
在剛才提到的時間頻度中七蜘，n稱為問題的規(guī)模谭溉，當n不斷變化時，時間頻度T(n)也會不斷變化橡卤。但有時我們想知道它變化時呈現(xiàn)什么規(guī)律扮念。為此，我們引入時間復雜度概念碧库。 一般情況下扔亥，算法中基本操作重復執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)，用T(n)表示谈为，若有某個輔助函數(shù)f(n),使得當n趨近于無窮大時旅挤，T(n)/f(n)的極限值為不等于零的常數(shù)，則稱f(n)是T(n)的同數(shù)量級函數(shù)伞鲫。記作T(n)=Ｏ(f(n)),稱Ｏ(f(n)) 為算法的漸進時間復雜度粘茄，簡稱時間復雜度。
T (n) = Ο(f (n)) 表示存在一個常數(shù)C秕脓，使得在當n趨于正無窮時總有 T (n) ≤ C * f(n)柒瓣。簡單來說，就是T(n)在n趨于正無窮時最大也就跟f(n)差不多大吠架。也就是說當n趨于正無窮時T (n)的上界是C * f(n)芙贫。其雖然對f(n)沒有規(guī)定，但是一般都是取盡可能簡單的函數(shù)傍药。例如磺平，O(2n2+n +1) = O (3n2+n+3) = O (7n2 + n) = O ( n2 ) 魂仍，一般都只用O(n2)表示就可以了。注意到大O符號里隱藏著一個常數(shù)C拣挪，所以f(n)里一般不加系數(shù)
從圖中可見擦酌，我們應該盡可能選用多項式階O(nk)的算法，而不希望用指數(shù)階的算法菠劝。常見的算法時間復雜度由小到大依次為：Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜…＜Ο(2n)＜Ο(n!)一般情況下赊舶，對一個問題（或一類算法）只需選擇一種基本操作來討論算法的時間復雜度即可赶诊，有時也需要同時考慮幾種基本操作，甚至可以對不同的操作賦予不同的權值舔痪，以反映執(zhí)行不同操作所需的相對時間出吹，這種做法便于綜合比較解決同一問題的兩種完全不同的算法辙喂。
-
計算
將基本語句執(zhí)行次數(shù)的數(shù)量級放入大Ο記號中鸠珠。 如果算法中包含嵌套的循環(huán)，則基本語句通常是最內層的循環(huán)體渐排，如果算法中包含并列的循環(huán)，則將并列循環(huán)的時間復雜度相加驯耻。例如 for (i=1; i<=n; i++) x++; for (i=1; i<=n; i++) for (j=1; j<=n; j++) x++; 第一個for循環(huán)的時間復雜度為Ο(n)亲族，第二個for循環(huán)的時間復雜度為Ο(n2)可缚，則整個算法的時間復雜度為Ο(n+n2)=Ο(n2)。 Ο(1)表示基本語句的執(zhí)行次數(shù)是一個常數(shù)帘靡，一般來說，只要算法中不存在循環(huán)語句描姚，其時間復雜度就是Ο(1)涩赢。其中Ο(log2n)、Ο(n)轩勘、 Ο(nlog2n)筒扒、Ο(n2)和Ο(n3)稱為多項式時間，而Ο (2n)和Ο(n!)稱為指數(shù)時間绊寻。 -
理解
- 一個經驗規(guī)則：其中c是一個常量花墩，如果一個算法的復雜度為c 悬秉、 log2n 、n 观游、 n*log2n ,那么這個算法時間效率比較高 搂捧，如果是2n ,3n ,n!，那么稍微大一些的n就會令這個算法不能動了懂缕，居于中間的幾個則差強人意允跑。
-
時間復雜度評價性能
有兩個算法A1和A2求解同一問題，時間復雜度分別是T1(n)=100n2搪柑，T2(n)=5n3聋丝。（1）當輸入量n＜20時，有T1(n)＞T2(n)工碾，后者花費的時間較少弱睦。（2）隨著問題規(guī)模n的增大，兩個算法的時間開銷之比5n3/100n2=n/20亦隨著增大渊额。即當問題規(guī)模較大時况木，算法A1比算法A2要有效地多。它們的漸近時間復雜度O(n2)和O(n3)從宏觀上評價了這兩個算法在時間方面的質量旬迹。在算法分析時火惊，往往對算法的時間復雜度和漸近時間復雜度不予區(qū)分，而經常是將漸近時間復雜度T(n)=O(f(n))簡稱為時間復雜度奔垦，其中的f(n)一般是算法中頻度最大的語句頻度屹耐。
-
-
2. 算法的空間復雜度
1. 一個算法的空間復雜度(Space Complexity)S(n)定義為該算法所耗費的存儲空間，它也是問題規(guī)模n的函數(shù)椿猎。漸近空間復雜度也常常簡稱為空間復雜度惶岭。
2. 分為三部分
- 固定部分。這部分空間的大小與輸入/輸出的數(shù)據(jù)的個數(shù)多少犯眠、數(shù)值無關按灶。主要包括指令空間（即代碼空間）、數(shù)據(jù)空間（常量筐咧、簡單變量）等所占的空間兆衅。這部分屬于靜態(tài)空間。
- 可變空間嗜浮，這部分空間的主要包括動態(tài)分配的空間，以及遞歸棧所需的空間等畏铆。這部分的空間大小與算法有關。一個算法所需的存儲空間用f(n)表示辞居。S(n)=O(f(n)) 其中n為問題的規(guī)模楷怒，S(n)表示空間復雜度
代碼
單鏈表的實現(xiàn)
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
//定義鏈表的節(jié)點鸠删，由當前的節(jié)點值外加指向下個節(jié)點的指針
//NODE等價于struct Node, PNODE等價于struct Node *
typedef struct Node{
int data;
struct Node *pNext;
}NODE,*PNODE;
//函數(shù)的聲明
PNODE createLinkList(); //定義創(chuàng)建鏈表的指針函數(shù)
void traverseLinkList(PNODE pHead);//遍歷鏈表的函數(shù)
bool isEmpty(PNODE pHead) ;//判斷鏈表是否為空的函數(shù)
int getLength(PNODE pHead);//獲取鏈表的長度
bool insertElement(PNODE pHead, int pos, int val); //向鏈表中插入元素的函數(shù)贼陶，三個參數(shù)依次為鏈表頭結點、要插入元素的位置和要插入元素的值
bool deleteElement(PNODE pHead, int pos, int * pVal); //從鏈表中刪除元素的函數(shù)碉怔，三個參數(shù)依次為鏈表頭結點、要刪除的元素的位置和刪除的元素的值
void sort(PNODE pHead); //對鏈表中的元素進行排序的函數(shù)(基于冒泡排序)
int main(void){
int val;
PNODE pHead = NULL;
pHead = createLinkList();
traverseLinkList(pHead);
if(isEmpty(pHead)){
printf("鏈表為空撮胧！\n");
}else{
printf("鏈表不為空！\n");
}
printf("鏈表的長度為：%d\n",getLength(pHead));
sort(pHead);
traverseLinkList(pHead);
if(deleteElement(pHead,3,&val))
printf("刪除元素成功锻离！刪除的元素是：%d\n",val);
else
printf("刪除元素失斈够场！\n");
traverseLinkList(pHead);
system("pause");
return 0 ;
}
//創(chuàng)建一個鏈表
PNODE createLinkList(void){
int length;
int value;
int i;
//創(chuàng)建一個不存放有效數(shù)據(jù)的頭節(jié)點
PNODE pHead = (PNODE)malloc(sizeof(NODE));
if(pHead==NULL){
printf("內存分配失敗捺疼，程序退出啤呼！\n");
exit(-1);
}
PNODE pTail = pHead;
pTail->pNext=NULL;
printf("請輸入您想要創(chuàng)建鏈表節(jié)點的個數(shù)： len = ");
scanf("%d\n",&length);
for( i = 0 ; i < length ; i ++){
printf("請輸入第%d個節(jié)點的值：",i+1);
scanf("%d",&value);
PNODE pNew= (PNODE)malloc(sizeof(NODE));
if(pNew==NULL){
printf("內存分配失敗呢袱，程序退出！\n");
exit(-1);
}
pNew->data=value;//新節(jié)點中放入值
pTail->pNext=pNew;//將尾節(jié)點指向新的節(jié)點
pNew->pNext=NULL;//將新的節(jié)點的指針域清空
pTail=pNew;//指針往后移動惕蹄，將新的節(jié)點賦值給pTail，使得pTail始終指向尾節(jié)點
}
return pHead;
}
//遍歷鏈表
void traverseLinkList(PNODE pHead) {
PNODE p = pHead->pNext;
while(NULL != p)
{
printf("%d ", p->data);
p = p->pNext;
}
printf("\n");
return;
}
bool isEmpty(PNODE pHead)
{
if(NULL == pHead->pNext)
return true;
else
return false;
}
int getLength(PNODE pHead)
{
PNODE p = pHead->pNext; //指向首節(jié)點
int len = 0; //記錄鏈表長度的變量
while(NULL != p)
{
len++;
p = p->pNext; //p指向下一結點
}
return len;
}
void sort(PNODE pHead) {
int len = getLength(pHead); //獲取鏈表長度
int i, j, t; //用于交換元素值的中間變量
PNODE p, q; //用于比較的兩個中間指針變量
for(i=0,p=pHead->pNext ; i<len-1 ; i++,p=p->pNext){
for(j=i+1,q=p->pNext;j<len;j++,q=q->pNext){
if(p->data > q->data){
t = p->data;
p->data = q->data;
q->data = t;
}
}
}
return;
}
bool insertElement(PNODE pHead, int pos, int val){
int i = 0;
PNODE p = pHead;
//判斷p是否為空并且使p最終指向pos位置的結點
while(NULL!=p && pos-1>i){
p = p->pNext;
i++;
}
if(NULL==p || i>pos-1)
return false;
//創(chuàng)建一個新結點
PNODE pNew = (PNODE)malloc(sizeof(NODE));
if(NULL == pNew){
printf("內存分配失敗，程序退出!\n");
exit(-1);
}
pNew->data = val;
//定義一個臨時結點张峰，指向當前p的下一結點
PNODE q = p->pNext;
//將p指向新結點
p->pNext = pNew;
//將q指向之前p指向的結點
pNew->pNext = q;
return true;
}
bool deleteElement(PNODE pHead, int pos, int * pVal){
int i = 0;
PNODE p = pHead;
//判斷p是否為空并且使p最終指向pos結點
while(NULL!=p->pNext && i<pos-1){
p = p->pNext;
i++;
}
if(NULL==p->pNext || i>pos-1)
return false;
//保存要刪除的結點
* pVal = p->pNext->data;
//刪除p后面的結點
PNODE q = p->pNext;
p->pNext = p->pNext->pNext;
free(q);
q = NULL;
return true;
}
