目錄

一，寫在前面

二，線性表的定義

三，線性表的抽象資料型別

四，線性表的順序存盤結構

4.1，順序存盤的定義

4.2，順序存盤方式

4.3，資料長度與線性長度的區別

4.4，地址計算方法

五，順序存盤結構的插入和洗掉

5.1，獲得元素操作

5.2，插入操作

5.3，洗掉操作

5.4，線性表順序存盤結構的優缺點

六，線性表的鏈式存盤結構

6.1，線性表鏈式存盤結構定義

6.2，頭節點和頭指標的異同

6.3，線性表鏈式存盤結構的代碼描述

七，全部代碼

一，寫在前面

到了下午放學的時候，我們會看到這樣一幕，幼兒園的小朋友排隊整齊的出校門，外面的家長亂糟糟站在外面，小朋友們有序的排隊，就相當于我們在資料結構里面的線性表，

二，線性表的定義

線性表,從名字上你就能感覺到,是具有像線一樣的性質的表，在廣場上,有很多人分散在各處,當中有些是小朋友,可也有很多大人,甚至還有不少寵物,這些小朋友的教抿對干整個廣場人群來說,不能算是線性表的結構，但像剛才提到的那樣,一個班級的小朋友,一個跟著一個排看隊,有一個打頭,有一個收尾,當中的小朋友每一個都知道他前面一個是誰,他后面一個是誰,這樣如同有一根線把他們串聯起來了，就可以稱之為線性表，

線性表( List ):零個或多個資料元素的有限序列，這里需要強調幾個關鍵的地方，
首先它是一個序列，也就是說,元素之間是有順序的,若元素存在多個,則第一個元素無前驅,最后一個元素無后繼,其他每個元素都有且只有一個前驅和后繼，如果一個小朋友去拉兩個小朋友后面的衣服,那就不可以排成一隊了;同樣,如果一個小朋友后面的衣服,被兩個甚至多個小朋友拉扯,這其實是在打架,而不是有序排隊，然后,線性表強調是有限的,小朋友班級人數是有限的,元素個數當然也是有限的，事實上,在計算機中處理的物件都是有限的,那種無限的數列,只存在于數學的概念中，
如果用數學語言來進行定義，可如下:

若將線性表記為( a1,....a(i-1),a(i),a(i+1),....,a(n)),則表中 a (i-1)領先于a(i) , a(i)領先于 a(i+1) 稱 a(i-1) 是 a(i) 的直接前驅元素, a(i+1) 是 a(i) 的直接后繼元素，當i=1,2,…, n-1時, a(i)有且僅有一個直接后繼,當i =2,3,…, n 時, a(i) 有且僅有一個直接前驅，如下圖所示，

三，線性表的抽象資料型別

前面我們已經給了線性表的定義,現在我們來分析一下,線性表應該有一些什么樣的操作呢?
還是回到剛オ幼兒園小朋友的例子,老師為了讓小朋友有秩序地出入,所以就考慮給他們排一個隊,并且是長期使用的順序,這個考慮和安排的程序其實就是一個線性表的創建和初始化的程序，一開始沒經驗,把小朋友排好隊后,發現有的高有的矮,隊伍很難看,于是就讓小朋友解散重新排一這是一個線性表重置為空表的操作，
排好了隊,我們隨時可以叫出隊伍某一位置的小朋友名字及他的具體情況，比如有家長問,隊伍里第五個孩子,怎么這么調皮,他叫什么名字呀,老師可以很快告訴這位家長，這種可以根據位序得到資料元素也是一種很重要的線性表操作，
還有什么呢?有時我們想知道,某個小朋友,比如麥兜是否是班里的小朋友,老師會告訴我說,不是,麥兜在春田花花幼兒園里,不在我們幼兒園，這種查找某個元素是否存在的操作很常用，而后有家長問老師,班里現在到底有多少個小朋友呀,這種獲得線性表長度的問題也很普遍，顯然,對于一個幼兒園來說,加入一個新的小朋友到佇列中,或因某個小朋友生病,需要移除某個位置,都是很正常的情況，對于一個線性表來說,插入資料和洗掉資料都是必須的操作，

ADT性表( List )

Data
線性表的資料物件集合為(a1,a2,a3,....a(n)),每個元素的型別均為 DataType ，其中,除第一個元素 a1,外,毎一個元素有且只有一個直接前驅元素,除了最后一個元素 a(n) ,外,每一個元素有且只有一個直接后繼元素，資料元素之間的關系是一對一的關系，
Operation
InitList (* L ):初始化操作,建立一個空的線性表 L ，
ListEmpty ( L ):若線性表為空,回傳 true ,否則回傳 false ，

ClearList (* L ):將線性表清空，
GetElem ( L , i ,*e ):將線性表中的第1個位置元素値回傳給 e ，
LocateElem ( L , e ):在線性表ム中查撥與給定値 e 相等的元素,如果查找成功,回傳該元素在表中序號表示成功;否則,回傳0表示失敗，
ListInsert (*L , i , e ):在線性表中的第1個位置插入新元素 e ，
ListDelete (* L , i ,* e ):瀏除線性表中第1個位置元素,并用 e 回傳其值，

ListLength (1):回傳線性表 L 的元素個數，

endADT

對于不同的應用,線性表的基本操作是不同的,上述操作是最基本的題中涉及的關于線性表的更復雜操作,完全可以用這些基本操作的組合來實作，
比如,要實作兩個線性表集合 A 和 B 的并集操作，即要使得集合 A = AUB 就是把存在集合 B 中但并不存在集合 A 中的資料元素插入到集合 A 中即可，
仔細分析一下這個操作,發現我們只要回圈集合 B 中的每個元素,判斷存在集合 A 中,若不存在,則插入到集合 A 中即可，思路應該是很容易想到
我們假設 La 表示集合 A , Lb 表示集合 B ,則實作的代碼如下:

/*將所有的在線性表Lb中但不在La中的資料元素插入到La中*/
void unionL(SqList* La, SqList Lb)
{
	int La_len, Lb_len, i;
	ElemType e;                        /*宣告與La和Lb相同的資料元素e*/
	La_len = ListLength(*La);            /*求線性表的長度 */
	Lb_len = ListLength(Lb);
	for (i = 1; i <= Lb_len; i++)
	{
		GetElem(Lb, i, &e);              /*取Lb中第i個資料元素賦給e*/
		if (!LocateElem(*La, e))        /*La中不存在和e相同資料元素*/
			ListInsert(La, ++La_len, e); /*插入*/
	}
}

注意：

當你傳遞一個引數給函式的時候,這個引數會不會在隨數內被改動決定了使用什么引數形式，
如果需要被改動,則需要傳遞指向這個引數的指標，
如果不用被改動,可以直接傳遞這個引數，

四，線性表的順序存盤結構

4.1，順序存盤的定義

線性表的順序存盤結構，指用的是用一段地址連續的存盤單元依次存盤線性表的資料元素，

線性表如下：

4.2，順序存盤方式

線性表的順序存盤結構，說白了，就是在記憶體中找一塊，通過占有的方式，把一定記憶體空間給占了，然后依次把相同的資料型別的資料元素依次存放在這塊空地中，資料型別相同，建立一個線性表，起始位置，最大存盤容量，增加資料，洗掉資料等非常重要，

來看線性表的順序存盤代碼：

#define MAXSIZE 20          /* 存盤空間初始分配量 */
typedef int ElemType;       /* ElemType型別根據實際情況而定，這里假設為int */
typedef struct
{
    ElemType data[MAXSIZE]; /* 陣列，存盤資料元素 */
    int length;             /* 線性表當前長度 */
}SqList;

注意：

存盤空間的起始位置：陣列data，他的存盤位置就是存盤空間的起始位置，

線性表的最大存盤容量：陣列長度MAXSIZE，

線性表當前的長度：length，

4.3，資料長度與線性長度的區別

注意哦,這里有兩個概念“陣列的長度”和“線性表的長度”需要區分，
陣列的長度是存放線性表的存盤空間的長度存盤分配后這個量一般是不變的，有個別同學可能會問,陣列的大小一定不可以變嗎?可以動態分配的一維陣列，是的,一般高級語言如C ，VB ，C ++都可以用編程手段實作動態分配陣列,不過這會帶來性能上的損耗，
線性表的長度是線性表中資料元素的個數,隨著線性表插入和洗掉操作的進行,這個量是變化的，
在任意時刻,線性表的長度應該小于等于陣列的長度，

4.4，地址計算方法

由于我們數數都是從1開始數的,線性表的定義也不能免俗,起始也是1,可 C 語言中的陣列卻是從0開始第一個下標的,于是線性表的第i個元素是要存盤在陣列下標為i-1的位置,即資料元素的序號和存放它的陣列下標之間存在對應關系，

用陣列存盤順序表意味著要分配固定長度的陣列空間,由于線性表中可以進行行插入和翻除操作,因此分配的陣列空間要大于等于當前線性表的長度，
其實,記憶體中的地址,就和圖書館或電影院里的座位一樣,都是有編號的，存盤器中的每個存盤單元都有自己的編號,這個編號稱為地址，當我們占座后,占座的第一個位置確定后,后面的位置都是可以計算的，試想一下,我是班級成績第五名,我后面的10名同學成績名次是多少呢?當然是6,7,…,15,由于每個資料元素,不管它是整型、實型還是字符型,它都是需要占用一定的存盤單元空間的，假設占用的是個存盤單元,那么線性表中第+1個資料元素的存盤位置和第個資料元素的存盤位置滿足下列關系( LOC 表示獲得存盤位置的函式)，

LOC(a(i+1)) = LOC(a(i)）+ c

LOC(a(i)) = LOC(a(i)) + (i - 1)* c

下面我們從圖理解：

通過這個公式,你可以隨時算出線性表中任意位置的地址,不管它是第一個還是最后一個,都是相同的時間，那么我們對每個線性表位置的存入或者取出資料,對于計算機來說都是相等的時間,也就是一個常數,因此用我們演算法中學到的時間復雜度的概念來說,它的存取時間性能為O(1)，我們通常把具有這一特點的存盤結構稱為隨機存取結構，

五，順序存盤結構的插入和洗掉

5.1，獲得元素操作

對于線性表的順序存盤結構來說，如果我們要實作GetElem操作，就程式而言，只要i的數值在陣列下標范圍內，就是把陣列i-1下標回傳即可，代碼如下：

#define OK 1
#define ERROR 0
typedef int ElemType;       /* ElemType型別根據實際情況而定，這里假設為int */

/* 初始條件：順序線性表L已存在，1≤i≤ListLength(L) */
/* 操作結果：用e回傳L中第i個資料元素的值,注意i是指位置，第1個位置的陣列是從0開始 */
Status GetElem(SqList L,int i,ElemType *e)
{
    if(L.length==0 || i<1 || i>L.length)
            return ERROR;
    *e=L.data[i-1];

    return OK;
}

5.2，插入操作

插入演算法的思路:

(1)如果插入位置不合理,拋出例外;

(2)如果線性表長度大于等于陣列長度,則拋出例外或動態増加容量;

(3)從最后一個元素開始向前遍歷到第i個位置,分別將它們都向后移動一個位置;

(4)將要插入元素填入位置i處;

(5)表長加1，代碼如下：

/* 初始條件：順序線性表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;
}

5.3，洗掉操作

洗掉演算法的思路:

(1)如果洗掉位置不合理,拋出例外:

(2)取出洗掉元素

(3)從洗掉元素位置開始遍歷到最后一個元素位置,分別將它們都向前移動一個
位營

(4)表長減1，實作代碼如下:

/* 初始條件：順序線性表L已存在，1≤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;
}

5.4，線性表順序存盤結構的優缺點

六，線性表的鏈式存盤結構

6.1，線性表鏈式存盤結構定義

以前在順序結構中,每個資料元素只需要存盤教據元素資訊就可以了，現在鏈式結構中,除了要存儲資料元素資訊外,還要存盤它的后継元素的存盤地址，

其本身的資訊之外,還需存盤一個指示其直接后維的資訊(即直接后繼的存盤位置)，我們把存盤資料元素資訊的域稱為資料域,把存盤直接后繼位置的域稱為指標域，指標域中存盤的資訊稱作指標或鏈，這兩部分資訊組成資料元素 a (i)的存盤映像,稱為結點( Node )

n 個結點( a (i)的存盤映像)鏈結成一個鏈表,即為線性表( a1, a2 ,.… an .)的鏈式存盤結構,因為此鏈表的每個結點中只包含一個指標域,所以叫做單鏈表,單鏈表正是通過每個結點的指標域將線性表的資料元素按其邏輯次序鏈接在一起，

對于線性表來說,總得有個頭有個尾,鏈表也不例外，我們把鏈表中第一個結點的存盤位置叫做頭指標,那么整個鏈表的存取就必須是從頭指標開始進行了，之后的每一個結點,其實就是上一個的后繼指標指向的位置，想象一下,最后一個結點,它的指標指向哪里?
最后一個,當然就意味著直接后繼不存在了,所以我們規定,線性鏈表的最后一個結點指標為“空”(通常用 NULL 或“”符號表示,如下圖所示，

有時,我們為了更加方便地對鏈表進行操作,會在單鏈表的第一個結點前附設一個結點,稱為頭結點，頭結點的資料域可以不存盤任何資訊,誰叫它是第一個呢,有這個特權，也可以存盤如線性表的長度等附加資訊,頭結點的指標域存盤指向第一個結點的指標,如下圖所示，

6.2，頭節點和頭指標的異同

6.3，線性表鏈式存盤結構的代碼描述

空鏈表

為了表示線性表中資料元素及資料元素之間的關系，我們改用如下：

帶有頭結點的單鏈表和空鏈表

從這個結構定義中,我們也就知道,結點由存放資料元素的資料域和存放后繼結點地址的指標域組成，假設 p 是指向線性表第個元素的指標,則該結點 a 的資料域我們可以 p -> data 來表示, p -> data 的值是一個資料元素,結點 a 的指標域可以用 p -> next 來表示, P -> next 的值是一個指標， p -> next 指向誰呢?當然是指向第社1個元素,即指向 a .的指標，也就是說,如果 p -> data 等于 a ,那么 p -> next -> data 等于 a ,(如下圖所示)，

七，全部代碼

#include "stdio.h"    
#include "stdlib.h"  
#include "math.h"  
#include "time.h"

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20          /* 存盤空間初始分配量 */

typedef int* ElemType      /* ElemType型別根據實際情況而定，這里假設為int */
typedef struct
{
    ElemType data[MAXSIZE]; /* 陣列，存盤資料元素 */
    int length;             /* 線性表當前長度 */
}SqList;

typedef int Status;         /* Status是函式的型別,其值是函式結果狀態代碼，如OK等 */
Status visit(ElemType c)
{
    printf("%d ",c);
    return OK;
}
/* 初始化順序線性表 */
Status InitList(SqList *L) 
{ 
    L->length=0;
    return OK;
}
/* 初始條件：順序線性表L已存在，操作結果：若L為空表，則回傳TRUE，否則回傳FALSE */
Status ListEmpty(SqList L)
{ 
	if(L.length==0)
		return TRUE;
	else
		return FALSE;
}
/* 初始條件：順序線性表L已存在，操作結果：將L重置為空表 */
Status ClearList(SqList *L)
{ 
    L->length=0;
    return OK;
}
/* 初始條件：順序線性表L已存在，操作結果：回傳L中資料元素個數 */
int ListLength(SqList L)
{
	return L.length;
}
/* 初始條件：順序線性表L已存在，1≤i≤ListLength(L) */
/* 操作結果：用e回傳L中第i個資料元素的值,注意i是指位置，第1個位置的陣列是從0開始 */
Status GetElem(SqList L,int i,ElemType *e)
{
    if(L.length==0 || i<1 || i>L.length)
            return ERROR;
    *e=L.data[i-1];

    return OK;
}
/* 初始條件：順序線性表L已存在 */
/* 操作結果：回傳L中第1個與e滿足關系的資料元素的位序， */
/* 若這樣的資料元素不存在，則回傳值為0 */
int LocateElem(SqList L,ElemType e)
{
    int i;
    if (L.length==0)
            return 0;
    for(i=0;i<L.length;i++)
    {
            if (L.data[i]==e)
                    break;
    }
    if(i>=L.length)
            return 0;

    return i+1;
}

/* 初始條件：順序線性表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;
}

/* 初始條件：順序線性表L已存在，1≤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;
}
/* 初始條件：順序線性表L已存在 */
/* 操作結果：依次對L的每個資料元素輸出 */
Status ListTraverse(SqList L)
{
	int i;
    for(i=0;i<L.length;i++)
            visit(L.data[i]);
    printf("\n");
    return OK;
}

/*將所有的在線性表Lb中但不在La中的資料元素插入到La中*/
void unionL(SqList *La,SqList Lb)
{
	int La_len,Lb_len,i;
	ElemType e;                        /*宣告與La和Lb相同的資料元素e*/
	La_len=ListLength(*La);            /*求線性表的長度 */
	Lb_len=ListLength(Lb);
	for (i=1;i<=Lb_len;i++)
	{
		GetElem(Lb,i,&e);              /*取Lb中第i個資料元素賦給e*/
		if (!LocateElem(*La,e))        /*La中不存在和e相同資料元素*/
			ListInsert(La,++La_len,e); /*插入*/
	}
}
int main()
{
        
    SqList L;
	SqList Lb;
    ElemType e;
    Status i;
    int j,k;
    i=InitList(&L);
    printf("初始化L后：L.length=%d\n",L.length);
    for(j=1;j<=5;j++)
            i=ListInsert(&L,1,j);
    printf("在L的表頭依次插入1～5后：L.data=");
    ListTraverse(L); 
    printf("L.length=%d \n",L.length);
    i=ListEmpty(L);
    printf("L是否空：i=%d(1:是 0:否)\n",i);
    i=ClearList(&L);
    printf("清空L后：L.length=%d\n",L.length);
    i=ListEmpty(L);
    printf("L是否空：i=%d(1:是 0:否)\n",i);
    for(j=1;j<=10;j++)
            ListInsert(&L,j,j);
    printf("在L的表尾依次插入1～10后：L.data=");
    ListTraverse(L); 
    printf("L.length=%d \n",L.length);
    ListInsert(&L,1,0);
    printf("在L的表頭插入0后：L.data=");
    ListTraverse(L); 
    printf("L.length=%d \n", L.length);
    GetElem(L,5,&e);
    printf("第5個元素的值為：%d\n",e);
    for(j=3;j<=4;j++)
    {
            k=LocateElem(L,j);
            if(k)
                    printf("第%d個元素的值為%d\n",k,j);
            else
                    printf("沒有值為%d的元素\n",j);
    }
    k=ListLength(L); /* k為表長 */
    for(j=k+1;j>=k;j--)
    {
            i=ListDelete(&L,j,&e); /* 洗掉第j個資料 */
            if(i==ERROR)
                    printf("洗掉第%d個資料失敗\n",j);
            else
                    printf("洗掉第%d個的元素值為：%d\n",j,e);
    }
    printf("依次輸出L的元素：");
    ListTraverse(L); 
    j=5;
    ListDelete(&L,j,&e); /* 洗掉第5個資料 */
    printf("洗掉第%d個的元素值為：%d\n",j,e);
    printf("依次輸出L的元素：");
    ListTraverse(L); 
	//構造一個有10個數的Lb
	i=InitList(&Lb);
    for(j=6;j<=15;j++)
            i=ListInsert(&Lb,1,j);
	unionL(&L,Lb);
	printf("依次輸出合并了Lb的L的元素：");
    ListTraverse(L); 
    return 0;
}