前言

畢業(yè)也沒多久的我，發(fā)現(xiàn)大學好多東西都遺忘了或者沒學好。自己打算從數(shù)據(jù)結構與算法開始，一點一滴在簡書記錄我的算法學習和鞏固的歷程。同時，希望能邊和大家分享學習經(jīng)歷的同時，希望能夠得到大家的多多指教~

數(shù)據(jù)結構與算法這一系列我的重點是在算法這一部分，數(shù)據(jù)結構的概念和基礎在本節(jié)會解釋一下，后期會不斷的實驗和更新一些基礎經(jīng)典和有趣的算法。其中使用的編程語言主要是C語言。

數(shù)據(jù)結構與算法概要

重新瀏覽了一遍書，如果讓我來說數(shù)據(jù)結構與算法的一些印象。我清楚的記得是兩個公式。這兩個公式來告訴我們，什么是數(shù)據(jù)結構。

1、程序 = 算法 + 數(shù)據(jù)結構
2、數(shù)據(jù)結構 = 數(shù)據(jù) + 關系

• 數(shù)據(jù)之前存在的基本關系就是數(shù)據(jù)結構了。首先，數(shù)據(jù)有一個類型的特性，一個是基礎數(shù)據(jù)類型（DT），另一個是抽象的數(shù)據(jù)類型（ADT）。
  
  基礎的數(shù)據(jù)類型無非是看你處理的是字符還是數(shù)字，或者是什么精度的整數(shù)。抽象數(shù)據(jù)類型，有點類似類的思想，對一類事物的數(shù)據(jù)進行了封裝。比如，一輛汽車就是一個抽象數(shù)據(jù)類型，其中包括車的顏色、型號、特征等信息，作為對象來研究車這個整體的數(shù)據(jù)集合。
  
  我們最多研究的是抽象數(shù)據(jù)類型，對于抽象數(shù)據(jù)之間的關系，常常使用的基本結構是：
  表（線性表和鏈表)、隊列和棧。
  根據(jù)一些生活常識，延伸出來一些常用的數(shù)據(jù)模型來表現(xiàn)一些邏輯結構：
  樹、圖
  另外，對于數(shù)據(jù)我們還有些常見的數(shù)據(jù)操作值得我們研究：
  查找、排序

• 我們運行的程序處理的對象無非是數(shù)據(jù)，對于數(shù)據(jù)而言，算法決定著數(shù)據(jù)的處理方式。不同的處理方式有不同的效率。我們常見的算法有：
  枚舉、遞歸、遞推、分治、貪心等
  
  算法有兩個重要的考量指標：時間復雜度 和 空間復雜度
  時間復雜度是語句的頻度之和的數(shù)量級，這和問題規(guī)模n有關，故T(n) = O(f(n))。算法的空間復雜度為算法在運行過程中臨時占用存儲空間的度量，記S(n)=O(g(n))。

數(shù)據(jù)結構中的線性表

數(shù)據(jù)結構中線性表是最基礎、最簡單的一種數(shù)據(jù)表示形式。主要用來表示數(shù)據(jù)之間存在著什么樣的關系。主要分為順序表和鏈表。
數(shù)據(jù)結構無非是數(shù)據(jù)和關系（D,R）。D是數(shù)據(jù)元素的集合，當D的數(shù)量是0的時候代表是空表。數(shù)據(jù)之間存在著一種前驅和后繼的關系，a[i]，a[i+1]是前驅和后繼的關系，表頭是沒有直接前驅元素的，表尾是沒有后繼元素的。

順序表

順序表中數(shù)據(jù)是用一組連續(xù)的存儲單元一次存儲線性表中的各個數(shù)據(jù)的。其中的關系如下表示:

Loc(ai) = L(a0) + i x d

順序表的存儲結構

順序表的存儲結構：

#define Maxsize 100
#define ElemType  int
typedef struct {
    ElemType data[Maxsize];  //順序表的元素
    int length;              //順序表當前的長度
}Sqlist;

順序表的基礎操作：

//--------------------------->創(chuàng)建與銷毀
//創(chuàng)建表
void createList (Sqlist *L, int *a , int n) {
    //線性表不需要分配空間。
    //L = (Sqlist*)malloc(sizeof(ElemType));
    for ( int i = 0; i < n; i++) {
        L->data[i] = a[i];
    }
    L->length = n;
}
//初始化空表
void initList(Sqlist *L) {
   // L = (Sqlist*)malloc(sizeof(ElemType));
    L->length = 0;
}
//銷毀表
void destroyList(Sqlist *L) {
    L->length = 0;
}

//------------------------------------>查詢與遍歷
//判斷是否表空
int isEmpty(Sqlist *L) {
    return L->length == 0;
}
//計算表長度
int lengthOfList(Sqlist *L) {
    return L->length;
}
//輸出表中數(shù)據(jù)（遍歷順序表）
void mapList(Sqlist *L) {
    for (int i = 0 ; i < L->length; i++) {
        printf("%d \n", L->data[i]);
    }
}
//得到表中第N個元素的值
int getElemOfN(Sqlist *L, int n) {
    if (n < 0 || n >= L->length) {
        return  0;
    } else {
        n = L->data[n-1];
        return n;
    }
}
//判斷某數(shù)據(jù)是否在順序表中的位置
int findNumberList(Sqlist *L , ElemType e) {
    for (int i = 0; i < L->length; i++) {
        if (L->data[i] == e) {
            return i+1;
        }
    }
    
    return 0;
}

//----------------------------------->修改和刪除
//在一個位置上插入一個數(shù)據(jù)（前插）
int insertDataList(Sqlist *L, int pos, ElemType e) {
    if (pos < 0 || pos > L->length) {
        return 0;
    }
    
    for (int i = L->length; i >= pos; i--) {
        L->data[i] = L->data[i-1];
    }
    L->data[pos-1] = e;
    L->length++;
    
    return 1;
}
//刪除某個位置上的一個數(shù)據(jù)
void deleteDataOfN(Sqlist *L, int n) {
    for (int i = n; i < L->length; i++) {
        L->data[i-1] = L->data[i];
    }
    L->length--;
}

順序表優(yōu)缺點

優(yōu)點：
1、順序表的邏輯結構和存儲結構理解方便，編寫也方便；
2、順序表的因為是隨機存取的存儲結構，當我們知道起始位置，差值，很容易確定指定元素；
缺點：
1、由于這種存儲結構需要系統(tǒng)提供連續(xù)的地址空間，對于系統(tǒng)緊缺的機器，可能會導致不能滿足當前需求；
2、由于數(shù)據(jù)元素一般都是按照最大的數(shù)進行確定的，當實際應用中沒有用到這么多數(shù)據(jù)，不必要的空間會導致資源的浪費；
3、由于表中是連續(xù)分布的，這使得我們在插入和刪除做數(shù)據(jù)修改的過程中，需要把修改之后的數(shù)據(jù)進行大量的移動，極大的影響了系統(tǒng)的運行速度。

鏈表

鏈表的出現(xiàn)可以解決順序表的一些不足。鏈表分為單鏈表、單向循環(huán)鏈表、雙向鏈表、靜態(tài)鏈表等。主要講解單鏈表為主，首先單鏈表提出了節(jié)點的概念，一個節(jié)點存儲一個數(shù)據(jù)單元并且占用一個存儲塊，這個節(jié)點除了存儲數(shù)據(jù)元之外還有一個節(jié)點指針，這個指針對象是下一個鏈表元素。單鏈表也是通過這個節(jié)點指針對一系列的數(shù)據(jù)進行聯(lián)系。

單鏈表節(jié)點和結構示意圖

單鏈表的存儲結構：

#define Maxsize 100
#define ElemType  int
typedef struct LNode{
    ElemType data;
    struct LNode *next;
} LinkList;

單鏈表的基本操作：

//------------------------------>單鏈表的創(chuàng)建
LinkList* createLinkHead(LinkList *L) {
    LinkList *t;
    ElemType inputNum;
    //先初始化一個空的鏈表
    L = (LinkList*)malloc(sizeof(LinkList));
    L->data = 999;  //999代表的是頭
    L->next = NULL;
    //開始添加
    printf("please input:\n");
    scanf("%d", &inputNum);
//    循環(huán)添加，只到“-1”結束
    while (inputNum != -1) {
        t = (LinkList*)malloc(sizeof(LinkList));
        t->data = inputNum;
        t->next = L->next;
        L->next = t;
        scanf("%d", &inputNum);
    }
    return L;
}
//------------------------------>單鏈表的查詢
//得出第i個元素的值
LinkList* getValueLinklistOfPos(LinkList *L, int pos) {
    LinkList *t = L;
    int i = 0;
    if (pos > lengthOfLinklist(L) || pos < 0) {
        return 0;
    }
    while (pos > i) {
        i++;
        t = t->next;
    }
    return t;
}
//遍歷
void mapLinklist(LinkList *L) {
    LinkList *t = L;
    while (t->next != NULL) {
        printf("%d ", t->next->data);
        t = t->next;
    }
    printf("\n");
}
//得出元素的長度
int lengthOfLinklist(LinkList *L) {
    int l = 0;
    LinkList *t = L;
    while(t->next != NULL) {
        l++;
        t = t->next;
    }
    return l;
}

//------------------------------>單鏈表的添加
//尾插法
LinkList* createLinkTail(LinkList *L) {
    LinkList *t, *r;
    ElemType inputNum;
    //先初始化一個空的鏈表
    L = (LinkList*)malloc(sizeof(LinkList));
    L->data = 999;  //999代表的是頭
    r = L;
    //開始添加
    printf("please input:\n");
    scanf("%d", &inputNum);
    //    循環(huán)添加，只到“-1”結束
    while (inputNum != -1) {
        t = (LinkList*)malloc(sizeof(LinkList));
        t->data = inputNum;
        r->next = t;
        r = t;
        scanf("%d", &inputNum);
    }
    r->next = NULL;
    return L;
}
//插入操作，將值e插入到單鏈表的第i個位置前面
int insertLinkList(LinkList *L, ElemType e, int pos) {
    LinkList *t = L;
    int i = 0;
    if (pos > lengthOfLinklist(L) || pos < 0) {
        return 0;
    }
    // 循環(huán)跳出，pos=i;
    while (pos > i+1) {
        t = t->next;
        i++;
    }
    LinkList *s = (LinkList*)malloc(sizeof(LinkList));
    s->data = e;
    s->next = t->next;
    t->next = s;
    return 1;
}

//------------------------------>單鏈表的刪除
//刪除第i個元素的操作節(jié)點
int deleteLinkList(LinkList *L, int pos) {
    if (pos > lengthOfLinklist(L) || pos < 0) {
        return 0;
    }
    LinkList *p = getValueLinklistOfPos(L, pos-1);
    p->next = p->next->next;
    free(p->next);
    return 1;
}
//------------------------------>單鏈表的修改
//修改第i個元素的操作節(jié)點
int alterLinkListFromPos(LinkList *L, int pos, ElemType e) {
    if (pos > lengthOfLinklist(L) || pos < 0) {
        return 0;
    }
    LinkList *t = getValueLinklistOfPos(L, pos);
    t->data = e;
    return 1;
}
//修改第一個值為e的元素的值
int alterLinkListFromValue(LinkList *L, ElemType e, ElemType ex) {
    LinkList *t = L;
    while (1) {
        if (t->next == NULL) {
            return 0;
        } else {
            if (t->data == e) {
                t->data = ex;
                return 1;
            } else {
                t = t->next;
            }
        }
    }
}

鏈表的優(yōu)缺點

優(yōu)點：
1、最大的優(yōu)點就是克服了順序表的最大存儲空間申請的特點，用數(shù)據(jù)的時候進行分配，不使用的時候就進行釋放，相對的節(jié)省了一定的空間；
2、存儲的時候是靠指針的鏈接來進行實現(xiàn)的，所以克服了插入和刪除元素大量移動的缺點；
缺點：
1、每個節(jié)點的指針域也會帶來一定的空間占用，當Data所占空間比較少的時候，指針域的比重相對較大。所以，當考慮使用順序表還是鏈表所占空間的時候，還需要具體分析；
2、鏈表插入和刪除相對簡單了，帶來的問題就是查找變的相對麻煩，往往需要從頭結點進行查找，增加了算法的復雜程度。

線性表小結
順序表和鏈表比較基礎一節(jié)。我們可以通過比較優(yōu)缺點，他們是相互取長補短的，優(yōu)點和缺點都是相互對稱的。我們可以通過實際情況來進行選取數(shù)據(jù)的存儲方式。

本章小結

我想做的是記錄算法的一個系列，各種基礎的、經(jīng)典的算法稍微偏重一些。線性表是比較基礎的一節(jié)，但是牽扯到的思路都比較明顯，不算太難。另外，鏈表這邊還包括單向循環(huán)鏈表、雙向鏈表和靜態(tài)鏈表，這不再一一說明。我的Git上有單鏈表、順序表、雙向鏈表的測試代碼，可以進行簡單參考。
（PS：如果哪里寫的不好和有誤，還希望大家指出，及時改正，希望和大家一起進步~~ > _ < ~~ ！??！)
Git地址(僅供參考)