##線性結(jié)構(gòu)
基本特點(diǎn)：結(jié)構(gòu)中各元素之間滿足線性關(guān)系。
線性關(guān)系：數(shù)據(jù)元素之間存在一對(duì)一的關(guān)系
1.存在唯一的開始元素
2.存在唯一的終止元素
3.除了開始元素和終止元素，其他元素均有且僅有一個(gè)直接前驅(qū)元素和一個(gè)直接后驅(qū)元素。

讓客戶滿意是我們工作的目標(biāo)，不斷超越客戶的期望值來自于我們對(duì)這個(gè)行業(yè)的熱愛。我們立志把好的技術(shù)通過有效、簡(jiǎn)單的方式提供給客戶，將通過不懈努力成為客戶在信息化領(lǐng)域值得信任、有價(jià)值的長(zhǎng)期合作伙伴，公司提供的服務(wù)項(xiàng)目有：空間域名、網(wǎng)絡(luò)空間、營(yíng)銷軟件、網(wǎng)站建設(shè)、承德網(wǎng)站維護(hù)、網(wǎng)站推廣。

所有元素可排成一個(gè)線性序列

##線性表的定義和特點(diǎn)
a1, a2, …ai-1, ai , ai+1 , …an

a1線性起點(diǎn)， ai-1是ai的前驅(qū)， ai+1是ai的后驅(qū)。
N = 0時(shí)稱為空表，下標(biāo)是元素的序號(hào)，表示元素在表中的位置。

對(duì)于非空的線性表或線性結(jié)構(gòu)，其特點(diǎn)是：
1．存在唯一的一個(gè)被稱作“第一個(gè)”的數(shù)據(jù)元素。
2．存在唯一的一個(gè)被稱作“最后一個(gè)”的數(shù)據(jù)元素。
3．除第個(gè)數(shù)據(jù)元素之外，結(jié)構(gòu)中的每個(gè)數(shù)據(jù)元素均只有個(gè)前驅(qū)。
4．除最后一個(gè)數(shù)據(jù)元素之外，結(jié)構(gòu)中的每個(gè)數(shù)據(jù)元素均只有一個(gè)后繼。

##常見的線性表的基本運(yùn)算:

1.lnitList(&L):構(gòu)造一個(gè)空的線性表L,即表的初始化。

2.ListLength(L):返回L中數(shù)據(jù)元素個(gè)數(shù)，即求表長(zhǎng)。

3.GetElem(L, i,&e):用e返回L中第i個(gè)數(shù)據(jù)元素的值,1

4.ListInsert(&L，i, e):在L中第i個(gè)位置之前插人新的數(shù)據(jù)元素e,L的長(zhǎng)度加1。

5.ListDelete(&L，i):刪除L的第i個(gè)數(shù)據(jù)元素,L的長(zhǎng)度減1。

##線性表的順序存儲(chǔ)結(jié)構(gòu):
1.線性表的順序表示又稱為 順序存儲(chǔ)結(jié)構(gòu) 或 順序映像。順序存儲(chǔ)定義:把邏輯上相鄰的數(shù)據(jù)元素存儲(chǔ)在物理上相鄰的存儲(chǔ)單元中的存儲(chǔ)結(jié)構(gòu)。
2.簡(jiǎn)言之，邏輯上相鄰，物理上也相鄰
3.順序存儲(chǔ)方法:用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的元素，可通過數(shù)組V[n]來實(shí)現(xiàn)。

##順序表的類型定義

#define MAXSIZE 100   //順序表可能達(dá)到的大長(zhǎng)度
typedef struct{ElemType *elem; 	//指向數(shù)據(jù)元素的基地址
	int length;   		//線性表的當(dāng)前長(zhǎng)度 
}SqList;              //順序表的結(jié)構(gòu)類型為 SqList

1.初始化線性表L（參數(shù)引用）

Status InitList_Sq(SqList &L){//構(gòu)造一個(gè)空的順序表 
	L.elem = new ElemType[MAXSIZE]; //分配空間
	if(！L.elem) exit(OVERFLOW); //存儲(chǔ)匹配失敗 
	L.length = 0; //空間長(zhǎng)度為0
	return ok; 
}

2.初始化線性表L（參數(shù)用指針）

Status InitList_Sq(SqList *L){//構(gòu)造一個(gè)空的順序表 
	L->elem = new ElemType[MAXSIZE]; //分配空間
	if(！L->elem) exit(OVERFLOW); //存儲(chǔ)匹配失敗 
	L->length = 0; //空間長(zhǎng)度為0
	return ok; 
}

3.取值（根據(jù)位置i獲取相應(yīng)位置數(shù)據(jù)元素的內(nèi)容）

int GetElem(SqList L, int i ,ElemType &e){if(i< 1 || i >L.length) return ERROR; //判斷i值是否合理，若不合理，返回ERROR
	e = L.elem[i - 1]; // i-1的單元存儲(chǔ)著第i個(gè)數(shù)據(jù)
	return ok; 
}

4.查找（根據(jù)指定數(shù)據(jù)獲取數(shù)據(jù)所在的位置）

int LocateElem(SqList L,ElemType e){for(int i=0;i< L.length;i++){if(L.elem[i] == e) return i+1; //查找成功，返回序號(hào)i+1 
	}
	return 0;  //查找失敗，返回0 
}

5.插入（插在第i個(gè)節(jié)點(diǎn)之前）
（在線性表L中第i個(gè)數(shù)據(jù)元素之前插入數(shù)據(jù)元素e）

插在第i個(gè)結(jié)點(diǎn)之前，移動(dòng)（n - i + 1）次。
算法步驟
（1）判斷插入位置i是否合法。
（2）判斷順序表的存儲(chǔ)空間是否已滿。
（3）將第n至第i位的元素依次向后移動(dòng)一個(gè)位置，空出第i個(gè)位置。
（4）將要插入的新元素e放入第i個(gè)位置。
（5）表長(zhǎng)加1，插入成功返回OK。

Status ListInsert_Sq(SqList &L, int i,ElemType e){if(i<1 || i >L.length + 1) return ERROR; // i值不合法
	if(L.length == MAXSIZE) return ERROR; //當(dāng)前存儲(chǔ)空間已滿
	for(j=L.length - 1; j>=i-1; j--){L.elem[j+1] = L.elem[j]; //插入位置及之后的元素后移 
	} 
	L.elem[i-1] = e; //將新元素e放入第i個(gè)位置
	++L.length;  //表長(zhǎng)增1
	return ok; 
}

6.刪除（刪除第i個(gè)結(jié)點(diǎn)）
（將線性表L中第i個(gè)數(shù)據(jù)元素刪除）

刪除第i個(gè)結(jié)點(diǎn)，移動(dòng)(n - i)次。
算法步驟
（1）判斷刪除位置i是否合法（合法值為1≤i≤n) 。
（2）將欲刪除的元素保留在e中。
（3）將第i+1至第n位的元素依次向前移動(dòng)一個(gè)位置。

Status ListDelete_Sq(SqList &L,int i){if(i<1 || i>L.length-1) return ERROR; //i值不合法
	for(j=i;j< L.length - 1; j++)
		L.elem[j-1] = L.elem[j]; //被刪除元素之后的元素前移
	--L.length;  //表長(zhǎng)-1
	return OK; 
}

##線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu):
一組既存儲(chǔ)數(shù)據(jù)又存儲(chǔ)相互連接信息的結(jié)
點(diǎn)集合，不需要存放在連續(xù)的存儲(chǔ)空間中。

數(shù)據(jù)域：存儲(chǔ)元素?cái)?shù)值的數(shù)據(jù)
指針域：存儲(chǔ)直接后繼結(jié)點(diǎn)的存儲(chǔ)位置

##與鏈?zhǔn)酱鎯?chǔ)有關(guān)的術(shù)語
1、結(jié)點(diǎn):數(shù)據(jù)元素的存儲(chǔ)映像。由數(shù)據(jù)域
和指針域兩部分組成。
2、鏈表:n個(gè)結(jié)點(diǎn)由指針鏈組成一個(gè)鏈
表。它是線性表的鏈?zhǔn)酱鎯?chǔ)映像，稱為線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。

##單鏈表、雙鏈表、循環(huán)鏈表:
1.結(jié)點(diǎn)只有一個(gè)指針域的鏈表，稱為單鏈表或線性鏈表。
2.有兩個(gè)指針域的鏈表，稱為雙鏈表·
3.首尾相接的鏈表稱為循環(huán)鏈表循環(huán)鏈表示意圖:

##單鏈表的定義和實(shí)現(xiàn)

1.單鏈表是由表頭唯一確定，因此單鏈表可以用頭指針的名字來命名
2.若頭指針名是L，則把鏈表稱為表L

##單鏈表的存儲(chǔ)結(jié)構(gòu)定義
typedef struct LNode{
ElemType data; // 數(shù)據(jù)域
struct LNode *next; //指針域
}LNode,*LinkList; //*LinkList為L(zhǎng)node類型的指針

##注意區(qū)分指針變量和結(jié)點(diǎn)變量?jī)蓚€(gè)不同的概念

注意區(qū)分指針變量和結(jié)點(diǎn)變量?jī)蓚€(gè)不同的概念
·指針變量p:表示結(jié)點(diǎn)地址
·結(jié)點(diǎn)變量*p:表示一個(gè)結(jié)點(diǎn)

若p->data=a;，則p->next->data=ai+1

1.初始化（構(gòu)造一個(gè)空表）
(1）生成新結(jié)點(diǎn)作頭結(jié)點(diǎn)，用頭指針L指向頭結(jié)點(diǎn)。(2）頭結(jié)點(diǎn)的指針域置空。

Status InitList_L(LinkList &L){L =  new LNode;  
	L->next = NULL;
return OK;
}

例題：分別取出表中i = 3和i = 15的元素

算法步驟：
1.從第1個(gè)結(jié)點(diǎn)(L->next)順鏈掃描，用指針p指向當(dāng)前掃描到的結(jié)點(diǎn)，p初值p = L->next。
2. j做計(jì)數(shù)器，累計(jì)當(dāng)前掃描過的結(jié)點(diǎn)數(shù)，j初值為1。
3.當(dāng)p指向掃描到的下一結(jié)點(diǎn)時(shí)，計(jì)數(shù)器j加1。
4.當(dāng)j= i時(shí)，p所指的結(jié)點(diǎn)就是要找的第i個(gè)結(jié)點(diǎn)。

取值（根據(jù)位置i獲取相應(yīng)位置數(shù)據(jù)元素的內(nèi)容）

Status GetElem_L(LinkList L,int i, ElemType &e){p = L->next;
	int j = 1;
	while(p&&j//向后掃描，直到p指向第i個(gè)元素或p為空 
		p = p->next;
		++j;
	}
	if(!p || j >i) return ERROR; //第i個(gè)元素不存在 
	e = p ->data; //取第i個(gè)元素
	return OK; 
}

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

分享題目：2.線性表-創(chuàng)新互聯(lián)
分享路徑：http://weahome.cn/article/csgjcs.html