簡介
數據結構是一門研究非數值計算的程式設計問題中的操作對象，以及它們之間的關係和操作相關問題的學科。數據結構是相互之間存在一種或者多種特定關係的元素的集合。指數據的邏輯結構在計算機中的存儲形式分為順序存儲結構和鏈式存儲結構。順序數據結構是指把數據元素放在地址連續的存儲單元里，其數據間的邏輯關係和物理關係是一致的。鏈式存儲結構是指數據元素放在任意的存儲單元中，存儲單元可以是連續的，也可以是不連續的。
線性表
定義
線性表（List）:零個或者多個數據元素的有限序列。如果用數學語言來進行定義：若線性表記作(a1,...ai-1,ai,ai+1,...,an)，則表中ai-1領先於ai，ai領先於ai+1，稱ai-1是ai的直接前驅元素，ai+1是ai的直接後繼元素。當i=1,2,...,n-1時，ai有且僅有一個直接後期，當i=2,3,...,n時，ai有且僅有一個直接前驅。如下圖所示：
順序數據結構線性表的個數n（n>=0）定義為線性表的長度，當n=0時，成為空表。在較複雜的線性表中，一個數據元素可以由若干數據項組成。
順序存儲結構
線性表的順序存儲結構，指的是用用一段地址連續的存儲單元依次存儲線性表的數據元素。
順序數據結構線性表的順序存儲的結構代碼：
#define MAXSIZE 20 /*存儲空間初始化分配量*/
typedef int ElemType; /*ElemType 類根據實際情況而定，這裡假設為int*/
typedef struct
{
ElemType data[MAXSIZE]; /*數組存儲數據元素，最大值為MAXSIZE*/
int length; /*線性表當前長度*/
}SqList;
三個屬性：
1、存儲空間其實位置：數組data，他的存儲位置就是空間的存儲位置。
2、線性表的最大存儲容量：數組長度MaxSize。
3、線性表的當前長度：length。
插入和刪除
順序結構獲得元素操作為實現GetElem操作，即將線性表L中的第i個位置元素值返回，代碼如下：
#defineOK1
#defineERROR0
#defineTRUE1
#defineFALSE0
typedefintStatus; /*Status是函式的類型，其值是函式結果狀態代碼，如OK等*/
/*初始條件：順序線性表L已存在，1<=i<=ListLength(L)*/
/*操作結果：用e返回L中第i個數據元素的值*/
StatusGetElem(SqListL,inti,ElemType*e)
{
if(L.length==0||i<1||i>L.length)
returnERROR;
*e=L.data(i-1);
returnOK;
}
順序結構插入的思路為：如果插入位置不合理，拋出異常；如果線性表長度大於等於數組長度，拋出異常或者動態增加容量；從最後一個元素開始向前遍歷到第i個位置，分別將他們都向後移動一個位置；將要插入元素填入位置i處；表長加1。這裡我們實現ListInsert(*L,i,e)，代碼實現：
/*初始條件：順序線性表L已經存在，1<=i<=ListLength(L)*/
/*操作結果：在L中第i個位置之前插入新的數據元素e，L的長度加1*/
Status ListInsert(SqList *L,int i,ElemType e){
int k;
if(L->length == MAXSIZE) /*順序線性表已經滿*/
return ERROR;
if(i<1||i>L->length+1) /*當i不在範圍內時*/
return ERROR;
if(i<=L->length)
{
for(k = L->length-1;k>=i-1;k-- /*將要插入位置後數據元素向後移動一位*/)
L->data[k+1] = L->data[k];
}
L->data[i-1] = e; /*將新元素插入*/
L->length++;
return OK;
}
順序結構刪除的思路為：如果刪除位置不合理，拋出異常；取出刪除元素；從刪除元素位置開始遍歷到最後一個元素位置，分別將他們都向前移動一個位置；·表長減1。代碼如下：
/*初始條件：順序線性表L已經存在，i<=i<=ListLength(L)*/
/*操作結果：刪除L的第i個數據元素，並用e返回其值，L的長度減1*/
Status ListDelete(SqList *L,int i,ElemType *e){
int k;
if(L -> length == 0) /*線性表為空*/
return ERROR;
if(i<1 || i>L->length) /*刪除位置不正確*/
return ERROR;
*e = L->data[i-1];
if(i<L->length)
{
for(k = i;k<L->length;k++) /*將刪除位置後繼元素前移*/
L->data[k-1] = L->data[k];
}
L->length--;
return OK;
}
優缺點
優點為無需為表中元素之間的邏輯關係而增加額外的存儲空間；可以快速的存取表中任一位置的元素。
缺點為插入和刪除需要移動大量的元素；長度變化較大時，無法確定存儲空間的容量；造成存儲空間的“碎片”。
二叉樹
定義
順序數據結構
順序數據結構
順序數據結構
順序數據結構
順序數據結構二叉樹是每個節點最多有兩個子樹的樹結構，二叉樹的每個結點至多只有二棵子樹(不存在度大於2的結點)，二叉樹的子樹有左右之分，次序不能顛倒。二叉樹的第i層至多有個結點；深度為k的二叉樹至多有個結點；對任何一棵二叉樹T，如果其終端結點數為，度為2的結點數為，則。
順序結構描述
常用的二叉樹的順序存儲結構是利用下面的方法來實現的。
假設現在需要順序存儲一棵完全二叉樹。一般的處理步驟是：首先從上至下、從左向右依次對完全二叉樹中的結點進行編號(即按層次編號)，編號從1開始；然後用一個一維數組來存放所有結點的值(一維數組的類型即為結點值的類型)，結點的值在一維數組中的存放位置由它們的編號來決定。類型定義如下：
#defme MAX 100
typedef struct
{
DataType nodes[MAXl；
int n；
為了讓一般的二叉樹也能採用這種順序存儲結構進行存儲，需要進行如下的處理過程：通過在二叉樹中添加外部結點(二叉樹原有的結點稱為內部結構)將其補充為一棵完全二叉樹。這個完全二叉樹由內部結點和外部結點構成．且最後一個葉子一定是原二叉樹最大層上最右邊的葉子：然後對其進行按層次編號，用一個一維數組來存放所有結點的值。結點的值存放在一維數組中以它們編號為下標的位置上。內部結點存儲它的值。外部結點的值統一用一個特殊的符號或值表示 。
