一、緒論 | 數據結構

一、考研的C++語言基礎以及代碼書寫規範

1、考研試卷中要求你寫的是什麼？

看一段代碼：

#include<iostream>#define n 100using namespace std;int gcd(int a,int b){ return a%b==0?b:gcd(b,a%b);}int main(){ int a=81,b=27; cout<<gcd(a,b)<<endl;}

需要你寫的其實只有int gcd部分，即解決問題所需要的一個或者多個API。

2、C++語言基礎

1）數據類型

a、結構型

typedef struct { int a; char data;}TypeA;

這個結構體就叫TypeA

b、指針型

指針即指向數據所保存位置的數據類型，保存的是數據的地址信息。

int *i=0;

電腦的內存就像一個大公寓，每個房間都有一定數量的人（數據），每個房間按順序標好了門牌號。而指針保存的就是門牌號。

c、結點的構造。

鏈表的結點有兩個域：指針域和數據域。

typedef struct Node{ int data; struct Node*next;}Node;

結點相對於結構體的特點在於，結點的內部包含了指向和自己同樣類型的數據類型的指針。所以，節點不能再匿名了，得取名字，比如上面的Node。如果沒有這樣做，就是非法的，如下面這樣：

typedef struct{ int data; struct Node*next;}Node;

編譯器就會一臉蒙蔽表示不知道struct Node*next是個啥。

當然，這樣也是可以的：

typedef struct node{ int data; struct node*next;}Node;

但何苦弄兩個名字為難自己......

二叉樹的節點：

typedef struct BTNode{ int data; struct BTNode*lc; struct BTNode*rc;}BTNode;

當然，你也可以這樣：

typedef struct BTNode{ int data; struct BTNode*lc; struct BTNode*rc;}BTNode，*btnode;

這時，btnode=BTNode ，你就可以.....少打一個『*』號。

I、如何分配內存呢？重點來了，malloc的用法：

BTNode* BT=(BTNode*)malloc(sizeof(BTNode));

更廣義地來看：

某數據類型* 指針名=(某數據類型e*)malloc(sizeof(某數據類型));

II、關於malloc，有個令人疑惑的問題：malloc(0)到底回返回什麼？

III、上面的BT如何取得它的data值呢？

這樣嗎？

BT.data

錯！BT是指針，所以應該是這樣：

BT->data

當然如果你很悶騷，也可以這樣：

(*BT).data

VI、可能會有人覺得，上面的結構體、結點寫得太麻煩了，完全可以寫得簡單一點：

struct BTNode{ int data; struct BTNode*lc; struct BTNode*rc;};

以及這樣：

class BTNode{ int data; struct BTNode*lc; struct BTNode*rc;}BTNode;

當然，在C++11里完全OjbK，但如果要求你用純C寫的話，這樣就不行了。穩妥起見，還是兩個都學會吧。

d、typedef和#define的區別：

typedef翻譯成中文應該叫：取小名兒。叫的名字不同，但完全是同一個人：

typedef int nmb;nmb i=9288;//new MacBook $9288

#define呢？叫做宏替換，和用words里的查找、替換功能完全一碼事，預編譯的時候把需要替換的東西全部替換掉。

#define nmb 9288//沒有分號int i=nmb;

在編譯器的眼裡，是這樣的：

int i=9288;

另外，注意了（敲黑板），如果你想用#define玩騷操作，千萬別翻車：

翻車案例：

#define f(x,y) x+yint i=2*f(3,4);cout<<i<<endl;

你猜答案是多少？

14？錯！是10。因為在編譯器眼裡，這段代碼是這樣的：

int i=2*3+4;cout<<i<<endl;

所以，你得加個括弧：

#define f(x,y) (x+y)int i=2*f(3,4);cout<<i<<endl;

這樣輸出結果就是14了。

2)函數

a、傳值函數

void func(int a){ a++;}int i=0;func(i);cout<<i<<endl;

輸出結果為：0。i 沒有被改變。

b、傳引用函數

void func(int &a){ a++;}int i=0;func(i);cout<<i<<endl;

輸出結果為：1。i 被改變了。

c、傳地址函數

I、

void func(int *a){ a++;}int *i=new int;cout<<i<<endl;func(i);cout<<i<<endl;

輸出為：

0x1005743700x100574370

i 所指向的地址沒有改變。

II、

void func(int* &a){ a++;}int *i=new int;cout<<i<<endl;func(i);cout<<i<<endl;

輸出為：

0x1005743700x100574374

i 所指向的地址改變了4，即一個int的長度。

III、

void func(int* a){ ++*a;}int *i=new int;cout<<*i<<endl;func(i);cout<<*i<<endl;

輸出為：

01

i 所指向的內存的數值增加了1。

以上三種情況可能看得有些暈，不妨停下來慢體會。

d、傳數組函數

I、

void func(int x[], int n){ ...}

對

II、

void func(int x[10],int n){ ...}

也沒問題

III、

void func(int x[2][10],int a,int b){ ...}

還是對

VI、

void func(int x[][10],int a,int b){ ...}

依舊對

V、

void func(int x[][],int a,int b){ ...}

這個就有問題了。

e、帶有返回值的函數

int func(int a){ return a;}

二、演算法複雜度分析

演算法的複雜度是指分析演算法的計算量。

可以參考此博客：演算法的時間複雜度和空間複雜度-總結 - CSDN博客

注意：演算法的複雜度不僅取決於問題的規模，也取決於其待處理數據的初始狀態，比如同樣是冒泡排序：

1、初態是已經基本升序排好的10000個數。

2、初態是完全打亂的10000個數。

問題規模雖然一樣，但受數據初態的影響，2消耗的時間當然要遠遠地大於1。

三、數據結構和演算法的基本概念

0、

數據：是對客觀事物的符號表示。是能輸入到計算機被計算機程序處理的符號的總稱。

數據元素：數據元素是數據的基本單位，有時候數據元素可由若干個數據項組成。

數據項：是數據結構中討論的最小單位，是數據記錄中最小的，不可分割的單位。

數據對象：性質相同的數據元素的集合比如大寫字母、小寫字母、數字。

數據結構：相互之間存在一種或者多種特定關係的數據元素的集合。

1、數據的邏輯結構

數據的邏輯結構是指數據結構在邏輯上表現出來的結構，和它是怎樣存儲沒有關係。比如並查集：輕鬆理解並查集 | 原理、優化、代碼實現以及實戰練習

並查集在邏輯上呈現樹的結構，但是以線性的方式存儲的。

數據的邏輯結構分兩種：

1) 線性結構：比如說數組、隊列、鏈表

啰嗦一點來說，線性結構必須：

a、存在唯一的第一個元素和唯一的最後一個元素。

b、除了第一個元素外都有前驅，除了最後一個元素外都有後驅。

2) 非線性結構：比如樹、圖

2、數據的物理結構

又稱存儲結構。包括以下4種：

1) 順序存儲方法：將邏輯上相連的數據存儲在物理上連續的內存中。

2) 鏈式存儲方法：將邏輯上相連的數據存儲在物理上不連續的內存中，通過指針來連接。

3) 索引存儲方法：形如<關鍵詞，地址>。

4) 散列存儲方法：通過關鍵詞利用散列函數計算出該結點的存儲地址。本質上是順序存儲地拓展。

3、演算法的基本概念

演算法可以看做關於求解問題的一系列步驟的描述。

演算法的特性：有窮性、確定性、輸入、輸出、可行性。

演算法的設計目標：正確定、可讀性、健壯性、高效（時間上）低存儲量要求。

PS：

廣告時間啦~

理工狗不想被人文素養拖後腿？不妨關注微信公眾號：