王道計(jì)算機(jī)考研 數(shù)據(jù)結(jié)構(gòu)
【代碼部分在最后面
C語(yǔ)言線(xiàn)性表CTRL+F查找代碼
】
數(shù)據(jù)元素
1.2數(shù)據(jù)元素三要素
集合
線(xiàn)性結(jié)構(gòu)
樹(shù)形結(jié)構(gòu)
邏輯結(jié)構(gòu)總和
物理結(jié)構(gòu)
存儲(chǔ)結(jié)構(gòu)
數(shù)據(jù)結(jié)構(gòu)注意問(wèn)題
總結(jié)：
先通過(guò)邏輯結(jié)構(gòu)，和數(shù)據(jù)運(yùn)算將關(guān)系表達(dá)明確，在通過(guò)物理結(jié)構(gòu)實(shí)現(xiàn)代碼
如：bool ，int，struct都是數(shù)據(jù)類(lèi)型
算法特性
健壯性
非法數(shù)據(jù)能夠輸出反應(yīng)，而不是亂碼
高效率，低存儲(chǔ)量需求
有窮性
運(yùn)行的時(shí)間有限，會(huì)結(jié)束
確定性
能確定結(jié)果的輸出
時(shí)間復(fù)雜度
1.2-2算法效率度量
時(shí)間復(fù)雜度
log（2）^n的寫(xiě)法
最好復(fù)雜度和最壞復(fù)雜度以及平均復(fù)雜度
1.23算法空間復(fù)雜度：
如果算法的空間復(fù)雜度是常數(shù)階的話(huà)，求稱(chēng)算法能夠原地工作
例子1
例子2
例子3
例子4.函數(shù)調(diào)用也會(huì)引起內(nèi)存增加
空間大小4（n）+12（a，b，c）=16bit
空間復(fù)雜度＝遞歸調(diào)用的深度
2.1線(xiàn)性表定義
【用C++的可以把&L理解成對(duì)一個(gè)表的引用，用C語(yǔ)言的可以把&L理解成指向表的指針】彈幕
命名方式要注意
知識(shí)總結(jié)
2.21順序表的定義
順序表的定義
靜態(tài)分配
初始化很有必要，應(yīng)為有些編譯器不會(huì)幫你初始化
編譯器會(huì)強(qiáng)制類(lèi)型轉(zhuǎn)換，但是再寫(xiě)一遍能多學(xué)習(xí)一點(diǎn)
代碼
C語(yǔ)言線(xiàn)性表
#include <stdlib.h>
#include <stdio.h>
#define MaxSize 10
#define InitSize 10
typedef struct{
? ? int *data;//定義一個(gè)指針來(lái)接收這些數(shù)據(jù)
? ? int maxSize;//MaxSize
? ? int length;//長(zhǎng)度
}SeqList;
// 2.1動(dòng)態(tài)順序表的初始化
void InitSeqList(SeqList *L){
? ? (*L).data=(int *)malloc(sizeof(int)*InitSize);
? ? (*L).length=1;//(*L).length等價(jià)于L->length
? ? L->maxSize=0;
}
int main()
{
? ? SeqList a;
? ? printf("%d\n",a.data[5]);
? ? InitSeqList(&a);
----------------保護(hù)線(xiàn)----------------
----------------防手殘----------------
