資料結構-----順序表的靜态分布實作

資料結構入門—線性表（順續表的靜态配置設定）

線性表順序存儲的基本知識

1概念

線性表是具有相同資料類型的n（n>=0）個資料元素的有限序列，n為表長，n=0時為空表。

2特點

1表中元素個數有限。

2表中元素有邏輯上的順序性，有先後次序。

3表中元素都是資料元素，每個元素都是單個元素。

4資料元素資料類型相同（每個元素具有相同大小的存儲空間）。

5表中元素有抽象性，僅讨論其邏輯關系，不考慮元素究竟表示的内容。

3順序表的定義

線性表的順序存儲稱為順序表。它是用一組連續的存儲單元依次存儲線性表中的資料元素，使邏輯上相鄰的兩個元素在實體位置上也相鄰。

順序表的基本操作的實作

順序表可以是靜态配置設定的，也可以是動态配置設定的，本文先來讨論靜态配置設定的實作。

一個資料結構最基礎最核心的的操作，是其基本操作。複雜的操作可以調用其基本操作來實作。

1初始化

#define MAXSIZE 20//存儲空間初始配置設定量
#define false 0
#define true 1
#define ERROR -1//異常傳回值
#define ElemType int//資料元素類型
typedef struct 
{
	ElemType data[MAXSIZE];
	int length;
}SqList;
SqList sqList;
// 初始化一個線性表
int initList(SqList *L){
	for(int i=0;i<MAXSIZE;i++){
		L->data[i]=NULL;
		//由于記憶體中"髒資料"的存在，将表的每一個元素的初值設為0
	}
	L->length=0;
	return true;

}
           

2求表長

//
int listLength(SqList L){
	return L.length;
}
           

3按值查找

//
int locateElem(SqList L,ElemType e){
	int i;
	for(i=0;i<L.length;i++){
		if(L.data[i]==e) break;
	}
	return i;
}

           

4按位查找

//
int getElem(SqList L,int i){
	int length=L.length;
	if(length==0||i>length||i<0){
		return ERROR;
	}//檢查i合法性
	return 	L.data[i];
}
           

5插入操作

//
int insertElem(SqList *L,int i,ElemType	e){
	if(L->length>=MAXSIZE || i<1 || i>L->length+1{
		return ERROR;
	}//判斷i的範圍是否有效 以及是否存儲區滿
	int j=0;
	for(j=L->length;j>i;j--){
		L->data[j]=L->data[j-1];
	}
	L->data[i]=e;
	L->length++;
	return true;
}
           

6删除操作

//
int deleteElem(SqList *L,int i){
	int length=L->length; 
	if(i>length||i<1){
		return ERROR;
	}//同上
	for(int j=i;j<L->length;j++){
		L->data[j-1]=L->data[j];
	}
	L->length--;
	return true;
}
           

7判空操作

//
int listEmpty(SqList L){
	return L.length==0?true:false;
}
           

插入操作和删除操作的時間複雜度

1插入

（1）最好情況：在表尾插入（i=n+1）時，不需要後移，T(n)=O(1);

（2）最壞情況：在表頭插入（i=1）時，後移語句執行n次，T(n)=O(n);

（3）平均情況：設 Pi(1/n+1)為插入到每個結點的機率,很容易求得插入一個結點是平均動次數為n/2，T(n)=O(n);

2删除

（1）最好情況：删除表尾插元素（i=n），不需要前移，T(n)=O(1);

（2）最壞情況：删除表頭插入（i=1）時，前移語句執行n次，T(n)=O(n);

（3）平均情況：設 Pi(1/n)為删除每個結點的機率,平均動次數為(n-1)/2，T(n)=O(n);