數據結構之線性表

02-22

作為大二上學期所學專業課程之一，任課老師不斷強調這門課對我們未來無論是找工作還是讀研都起著很大的作用，於是，在這個假期中我決定將《數據結構》這門課上所學過的核心知識做一個總結概括，一方面是為了日後的複習查閱方便，另一方面，希望能夠幫助大家一點點的忙，也算是學習的收穫了吧！

----------------------------------------------------------分界線----------------------------------------------------

線性表

是最常用最簡單的一種數據結構，一個線性表是n個數據元素的有限序列。

一．存儲結構

1.線性表的順序表示和實現

線性表的存儲結構是一種隨機存儲的存儲結構，便於隨機訪問。

//----------------------線性表的動態分配順序存儲結構--------------------

#define LIST_INIT_SIZE 100 //線性表存儲空間的初始分配量

#define LISTINCREMENT 10 //線性表存儲空間的分配增量

typedef struct{

ElemType *elem; //存儲空間基址

Int length; //當前長度

Int listsize; //當前分配的存儲容量（以sizeof（ElemType）為單位）

}SqList;

//----------------------------線性表順序結構的相關操作-----------------------------

//T(n) = O(1) 創建空線性表的操作

Status InitList_Sq(Sqlist &L){

L.elem = (ElemType *)malloc(List_INIT_SIZE*sizeof(ElemType));

if(! L.elem) exit(OVERFLOW); //存儲分配失敗

L.length = 0; //空表長度為0

L.listsize = LIST_INIT_SIZE; //初始存儲容量

return OK;

}

//T(n) = O(L.length) 查找

Int LocateElem_Sq(SqList L, ElemType e,Status(*compare)(ElemType,Elemtype) ){

i = 1; //i的初值為第1個元素的位序

p = L.elem; //p的位置為第一個元素的存儲位置

while(i<=L.length && (*compare)(*p++,e)) ++i;

if(i<=L.length) return i;

else return 0;

}

插入刪除元素演算法的思想：

在指定位置前插入元素，順序存儲在指定位置之後的元素都依次往右，即設一個循環，首先定位在線性表的末尾，再由後面依次遞減往右移；刪除元素則相反，在指定位置開始循環往後讓元素一次向左移。

//T(n) = O(L.length) 在i之前插入元素

線性表的插入操作是指在線性表的第i-1個數據元素和第i個數據元素之間插入一個新的數據元素，就是要使長度為n的線性表

（a1,...,ai-1,ai,...an）

變成長度為n+1的線性表

（a1,...,ai-1,b,ai,...,an）

思想：將插入元素後的元素均後移一位

//----------------------插入元素演算法操作-----------------

Status ListInsert_Sq(SqList &L,int i,ElemType e){

if(i<1||i>L.length+1) return ERROR; //i值不合法

if(L.length>=L.listsize){ //當存儲空間已滿，增加分配

newbase = (ElemType*)malloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));

if(!newbase) exit(OVERFLOW);

L.elem = newbase;

L.listsize+=LISTINCREMENT;

}

q = &(L.elem[i-1]); //q為插入位置

for(p=&(L.elem[L.length-1]);p>=q;--p)

*(p+1) = *p; //插入位置及之後的元素右移

*q=e;

++L.length;

return OK;

}

//---------------------------刪除元素演算法操作-------------------------

Status ListDelete_Sq(SqList &L,int i,ElemType e){

if(i<1||i>L.length) return ERROR;

p = &(L.elem[i-1]); //p為被刪元素位置

e = *p;

q = L.elem+L.length-1; //表尾元素的位置

for(++p;p<=q;++p)

*(p-1) = *p; //左移

--L.length;

return OK;

}

關於線性表的順序存儲的優點和缺點

優點：1、邏輯相鄰，物理存儲

2、可隨機存取任一元素

3、存儲空間使用緊湊

缺點：1、插入刪除需要移動大量的元素

2、預先分配空間需按最大空間分配