真实的国产乱ⅩXXX66竹夫人,五月香六月婷婷激情综合,亚洲日本VA一区二区三区,亚洲精品一区二区三区麻豆

成都創(chuàng)新互聯(lián)網(wǎng)站制作重慶分公司

王道數(shù)據(jù)結(jié)構(gòu)（C語言）持續(xù)更新?。。?/h1>

第一章-緒論

一、數(shù)據(jù)結(jié)構(gòu)的三要素

1、邏輯結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)著重關(guān)注的是數(shù)據(jù)元素之間的關(guān)系，和對這些數(shù)據(jù)元素的操作，而不關(guān)心具體的數(shù)據(jù)項內(nèi)容

冀州網(wǎng)站建設(shè)公司成都創(chuàng)新互聯(lián)公司,冀州網(wǎng)站設(shè)計制作，有大型網(wǎng)站制作公司豐富經(jīng)驗。已為冀州上千提供企業(yè)網(wǎng)站建設(shè)服務(wù)。企業(yè)網(wǎng)站搭建\成都外貿(mào)網(wǎng)站建設(shè)公司要多少錢，請找那個售后服務(wù)好的冀州做網(wǎng)站的公司定做！

  1. 集合結(jié)構(gòu)

定義：各個元素同屬于一個集合，別無其他關(guān)系；

  1. 線性結(jié)構(gòu)（一對一）——>第二、三章

定義：

  • 除了第一個元素，所有元素都有唯一前驅(qū)；
  • 除了最后一個元素，所有元素都有唯一后繼；

  1. 樹形結(jié)構(gòu)（一對多）——>第四章

  2. 圖狀結(jié)構(gòu)（多對多）——>第五章

2、數(shù)據(jù)的運算

定義：針對于某種邏輯結(jié)構(gòu)，結(jié)合實際需求，定義基本運算

基本運算：

  • 查找第i個數(shù)據(jù)元素
  • 在第i個位置插入新的數(shù)據(jù)元素
  • 是刪除第i個位置的數(shù)據(jù)元素

3、物理結(jié)構(gòu)（存儲結(jié)構(gòu)）

  1. 順序存儲
  2. 鏈?zhǔn)酱鎯?/li>
  3. 索引存儲
  4. 散列存儲（Hash存儲）

總結(jié):

  • 若采用順序存儲，則各個數(shù)據(jù)元素在物理上必修是連續(xù)的；若采用非順序存儲，則各個數(shù)據(jù)元素在物理上可以是離散的；
  • 數(shù)據(jù)的存儲結(jié)構(gòu)會影響存儲空間分配的方便程度；
  • 數(shù)據(jù)的存儲結(jié)構(gòu)會影響對數(shù)據(jù)運算的速度；

二、算法的基本概念

1、什么是算法

程序 = 數(shù)據(jù)結(jié)構(gòu) + 算法

算法（Algorithm）是對特定問題求解步驟的一種描述，它是指令的有限序列，其中的每條指令表示一個或多個操作；

2、算法的五個特征

  • 有窮性：有窮步驟，有窮時間
  • 確定性：相同輸入——>相同輸出
  • 可行性：基本運算執(zhí)行有限次
  • 輸入：有零個或多個輸入
  • 輸出：有一個或多個輸出

3、“好”算法的特質(zhì)

  • 正確性：算法能夠正確地解決求解問題；
  • 可讀性：具有良好的可讀性，以幫助人理解；
  • 健壯性：輸入非法數(shù)據(jù)時，算法能夠做出反應(yīng)，而不會產(chǎn)生莫名其妙的輸出結(jié)果；
  • 高效率與低存儲量需求；

三、算法效率的度量

1、時間復(fù)雜度

事前預(yù)估算法時間開銷T(n)與問題規(guī)模n的關(guān)系（T表示“time”）

例題：

// 算法1—— 逐步遞增型愛你
void loveYou(int n) {	//n 為問題規(guī)模
    （1） int i=1;	// 愛你的程度
    （2） while(i<=n) {
     (3)	i++;	// 每次+1
     (4)   	printf("I Love You %d\n", i);
	     }
     (5) printf("I Love You More Than %d\n", n);
}

int main(){
    loveYou(3000);
}

語句頻度

（1） ——1次

（2） ——3001次

（3）（4） ——3000次

（5） ——1次

T(3000) = 1 + 3001 + 2 * 3000 + 1

時間開銷與問題規(guī)模n的關(guān)系：

T(n)=3n+3 只關(guān)注復(fù)雜度的數(shù)量級 ——> T(n) = O(n)

復(fù)雜度大小優(yōu)先級排序：

O(1) < O(log2n) < O(n) < O(nlog2n) < O(n2) < O(n3) < O(2n) < O(n!) < O(nn)

口訣：常對冪指階

例題：

// 算法1—— 嵌套循環(huán)型愛你
void loveYou(int n) {	//n 為問題規(guī)模
    （1） int i=1;	// 愛你的程度
    （2） while(i<=n) {
     (3)	i++;	// 每次+1
     (4)   	printf("I Love You %d\n", i);
     (5)    for (int j=1; j<=n; j++){
     (6)       	printf("I am a man!\n") ;
         	}
	     }
     (7) printf("I Love You More Than %d\n", n);
}

int main(){
    loveYou(3000);
}

時間開銷與問題規(guī)模n的關(guān)系：

T(n) = O(n) + O(n2) = O(n2)

例題：

// 算法3——指數(shù)增長型愛你
void loveYou(int n) {
    int i=1;
    while(i<=n0){
        i=i*2;	// 第一次循環(huán) i=2；第二次循環(huán) i=4；第三次循環(huán) i=8......
        printf("I Love You %d\n",i);
    }
    printf("I Love You More Than %d\n",n);
}

通過上述循環(huán)可知 i = 2x

所以想要退出while循環(huán)，x = log2n + 1

所以上述算法的時間復(fù)雜度為T(n) = O(x) = O(log2n)

2、空間復(fù)雜度

空間開銷S(n)與問題規(guī)模n的關(guān)系（S表示“Space”）

例題：

// 算法1——逐步遞增型愛你
void loveYou(int n) {
    int i=1;
    while(i<=n){
        i++;
        printf("I Love You %d\n",i);
    }
    printf("I Love You More Than %d\n",n);
}

轉(zhuǎn)入內(nèi)存 程序代碼 數(shù)據(jù)

綜上所述，上述算法的空間復(fù)雜度為：S(n)=O(1)

算法原地工作——算法所需內(nèi)存空間為常量；

函數(shù)遞歸調(diào)用帶來的內(nèi)存開銷：

// 算法5——遞歸型愛你
void loveYou(int n) {
    int a,b,c;
    if (n > 1) {
        loveYou(n-1);
    }
    printf("I Love You %d\n",n);
}

int main() {
    loveYou(5);
}

上述代碼的空間復(fù)雜度為：S(n)=O(n) O(n)空間復(fù)雜度 = 遞歸調(diào)用的深度

第二章-線性表

一、線性表的定義和基本操作

1、定義

線性表是具有相同數(shù)據(jù)類型的n（n>=0）個數(shù)據(jù)元素的有限 序列，其中n為表長，當(dāng)n=0時線性表是一個空表。若用L命名線性表，則其一般表現(xiàn)為：

L = (a1, a2, ... , ai, ai+1, ... , an) 腳標(biāo)從1開始計數(shù)

  • 幾個概念：
    1. ai是線性表中的“第i個”元素線性表中的位序； 位序是從1開始的，數(shù)組下標(biāo)是從0開始的；
    2. a1是表頭元素；an是表尾元素；
    3. 除第一個元素外，每個元素有且僅有一個直接前驅(qū)；
    4. 除最后一個元素外，每個元素有且僅有一個直接后繼；

2、基本操作

InitList(&L):	//初始化表。構(gòu)造一個空的線性表L，分配內(nèi)存空間；
DestroyList(&L):	//銷毀操作。銷毀線性表，并釋放線性表L所占用的內(nèi)存空間；

ListInsert(&L,i,e):	//插入操作。在表L中的第i個位置上插入指定元素e；
ListDelete(&L,i,&e):	//刪除操作，刪除表L中第i個位置的元素，并用e返回刪除元素的值；

LocateElem(L,e):	//按值查找操作。在表L中查找具有給定關(guān)鍵字的元素；
GetElem(L,i):	//按位查找操作。獲取表L中第i個位置的元素的值；

Tips：

  1. 對數(shù)據(jù)的操作（記憶思路） --創(chuàng)銷、增刪改查；
  2. C語言函數(shù)的定義 --<返回值類型> 函數(shù)名(<參數(shù)1類型>參數(shù)1， <參數(shù)2類型>參數(shù)2,...)
  3. 實際開發(fā)中，可根據(jù)實際需求定義其他的基本操作
  4. 函數(shù)名和參數(shù)的形式、命名都可改變

二、順序表的定義

1、順序表的定義

用順序存儲 的方式實現(xiàn)線性表的順序存儲；把邏輯上相鄰的元素存儲在物理位置上也相鄰的存儲單元中，元素之間的關(guān)系由存儲單元的鄰接關(guān)系來體現(xiàn)；

如何知道一個數(shù)據(jù)元素大??？

C語言 sizeof(ElemType)

sizeof(int) = 4B
sizeof(Customer) = 8B

2、順序表的靜態(tài)分配

#define MaxSize 10	//定義最大長度
typedef struct {
    ElemType data[MaxSize];	//用靜態(tài)的“數(shù)組”存放數(shù)據(jù)元素
    int length;	//順序表的當(dāng)前長度
}SqList;	//順序表的類型定義（靜態(tài)分配方式）

//基本操作---初始化一個順序表
void InitList(SqList &L){
    for(int i=0; i

3、順序表的動態(tài)分配

#define InitSize 10	//順序表的初始長度
typedef struct {
    ElemType *data;	//指針動態(tài)分配數(shù)組的指針
    int MaxSize;	//順序表的最大容量
    int length;		//順序表的當(dāng)前長度
}SqList;		//順序表的類型定義（動態(tài)分配方式）

key：動態(tài)申請和釋放內(nèi)存空間

malloc 和 free 函數(shù)：

L.data = (ElemType *)malloc(sizeof(ElemType)*InitSize);
//malloc函數(shù)申請一整片連續(xù)空間
  • 具體實現(xiàn)：
#define InitSize 10	//順序表的初始長度
typedef struct {
    ElemType *data;	//指針動態(tài)分配數(shù)組的指針
    int MaxSize;	//順序表的最大容量
    int length;		//順序表的當(dāng)前長度
}SqList;

void InitList(SeqList &L){
    //用malloc函數(shù)申請一片連續(xù)的存儲空間
    L.data=(int *)malloc(InitSize*sizeof(int));
    L.length=0;
    L.MaxSize = InitSize;
}

//增加動態(tài)數(shù)組的長度
void IncreaseSize(SeqList &L, int len){
    int *p=L.data;
    L.data=(int *)malloc((L.MaxSize + len)* sizeof(int));
    for(int i=0;i

第三章-棧、隊列和數(shù)組

第四章-串

第五章-樹與二叉樹

第六章-圖

第七章-查找

第八章-排序


網(wǎng)頁標(biāo)題：王道數(shù)據(jù)結(jié)構(gòu)（C語言）持續(xù)更新！??！
分享網(wǎng)址：http://weahome.cn/article/dsopcid.html

在線咨詢

微信咨詢

電話咨詢

028-86922220（工作日）

18980820575（7×24）

提交需求

返回頂部