第二章線性表

2.1 線性表的基本概念

線性結構是一種最簡單且最常用的資料結構，

線性結構的基本特點是節點之間滿足線性關系，

1．存在唯一的一個“第一元素”；

2．存在唯一的一個**“最后元素”** ；

3．除最后元素之外，均有唯一的后繼；

4．除第一個元素之外，均有唯一的前驅，

動態陣列，鏈表，堆疊，佇列都屬于線性結構，其共同之處，是節點中有且只有一個開始節點和終端節點，按照這種關系，可以把它們的所有節點排列成一個線性序列，（他們分別屬于幾種不同的抽象資料型別實作），

線性表是零個或者多個資料元素的有限數列，

資料結構之間是有順序的，資料元素個數是有限的，資料元素的型別必須相同，

線性表的實作

1. 順序存盤結構
2. 鏈式存盤結構

2.2 線性表順序存盤（動態陣列）的設計與實作

基本操作：

1. 線性表的定義

#define LTST_INIT_SIZE 100	//線性表存盤空間的初始分配量
#define LISTINCREMENT 10  //線性表存盤空間的分配增量

typedef struct 
{
	int *elem;		 // 存盤空間的基址(注意:陣列是一塊連續的記憶體空間)
	int length;		 //當前長度
	int listsize;	 //當前分配的存盤容量
} SqList;

//對typedef的理解: typedef 是C語言關鍵字，可以使用它來為資料型別取一個新的名字，
typedef unsigned int u32;
typedef struct _PERSON{
	char name[64];
	int age;
}Person;

void test(){
	u32 val; //相當于 unsigned int val;
	Person person; //相當于 struct PERSON person;
}

注意：(來源于菜鳥教程)

#define 是 C 指令，用于為各種資料型別定義別名，與 typedef 類似，但是它們有以下幾點不同：

typedef 僅限于為型別定義符號名稱，#define 不僅可以為型別定義別名，也能為數值定義別名，比如您可以定義 1 為 ONE，
typedef 是由編譯器執行解釋的，#define 陳述句是由預編譯器進行處理的，

2. 線性表的初始化

//初始化
//C 庫函式 void *malloc(size_t size) 分配所需的記憶體空間，并回傳一個指向它的指標
//引數：size -- 記憶體塊的大小，以位元組為單位，
//回傳值：該函式回傳一個指標（void*） ，指向已分配大小的記憶體，如果請求失敗，則回傳 NULL
//在 C 語言中，sizeof() 是一個判斷資料型別或者運算式長度的運算子,以位元組為單位，
Status InitList_Sq(SqList &L)
{
	//構造一個空的線性表 
	L.elem = (int*)malloc(LTST_INIT_SIZE*sizeof(int));
	if (!L.elem) //判斷空間是否分配成功 相當于 if(L.elem==NULL)  NULL在C語言宏定義為 0/(void*)0
		exit(OVERFLOW);   
	L.length = 0;
	L.listsize = LTST_INIT_SIZE;  //當前分配的存盤容量 = 線性表存盤空間的初始分配量
	return OK;
}

結構銷毀操作

3. 線性表的銷毀

void DestroyList_Sq(SqList &L){
	if (L.elem){  //相當于if(L.elem != NULL)
		delete [] L.elem;
		L.length = 0;
		L.elem = NULL;
	}
}

//拓展知識：
//C++釋放堆區陣列時：delete [] 陣列名
	person* pArray = new person[10];
    delete [] pArray;
//如果不加[]，則只釋放第一個，

4. 線性表的清空

void ClearList(SqList &L){
	L.length = 0;
	printf("順序表清空成功"); 
} 

//拓展知識：
//C++參考：參考變數是一個別名，也就是說，它是某個已存在變數的另一個名字，一旦把參考初始化為某個變數，就可以使用該參考名稱或變數名稱來指向變數，

5. 判斷線性表是否為空

//判斷順序表是否為空表 
//在C89 (ANSI C）標準中沒有定義與布爾型別相關的內容
//但在C99標準中新定義了一個新的關鍵字_Bool ，以及新增了一個頭檔案 <stdbool.h>規范了布爾型別的操作，方便程式員進行呼叫！
//但有些編譯器中不支持C99型別
bool IsEmpty(SqList L){
	if(L.length==0)
		return true;
	else
		return false;
}

6. 回傳資料元素的個數

typedef int Status;
//求順序表的長度
Status GetLength(SqList L){
	return L.length;
}

7. 給線性表元素賦值

//賦值 
Status AssignList_Sq(SqList &L)
{
	int n,m; //輸入個數 
	printf("請輸入集合元素個數:");
	scanf("%d",&n); 
	for(int i = 0;i < n;i++){
		printf("請輸入第%d個元素:",i+1);
		scanf("%d",&m);
		L.elem[i] = m;
		L.length++;
	}
	printf("賦值成功"); 
}

8. 線性表的列印

//列印
void printf_Sq(SqList L)
{
	if(L.elem == NULL){
		printf("該順序表已被銷毀"); 
	}
	for(int i = 0; i < GetLength(L); i++){
		printf("%d ",L.elem[i]);
	}
	
	printf("\n");
}

9. 用e回傳線性表中第i個元素

//用e回傳L中第i個元素
Status GetElem(SqList L,int i, int &e) 
{
	if(i < 1||i > GetLength(L))
		return ERROR;
	
	e = L.elem[i-1];
	return OK;
}

10. 在表中查找第一個值與e滿足compare()元素的位序

Status equal_e(int a,int b)
{
	if(a==b)
		return OK;
	else
		return ERROR;
}

//在表中查找第一個值與e滿足compare()元素的位序 
Status LocateElem(SqList L, int e,int (*compare)(int,int)){
	int i = 1;
	//int *p = L.elem; 
	while(i<=GetLength(L)&&!(*compare)(L.elem[i-1],e)){  //*p++
		++i;
	}
	if(i<=GetLength(L))
		return i;
	else
		return 0;
}

//拓展知識:函式指標
//函式指標做函式引數(回呼函式)

拓展知識：函式指標(指向函式的指標)

函式指標定義方式(先定義函式型別，根據型別定義指標變數);

先定義函式指標型別，根據型別定義指標變數;

直接定義函式指標變數;

int my_func(int a,int b){
	printf("ret:%d\n", a + b);
	return 0;
}

//1. 先定義函式型別，通過型別定義指標
void test01(){
	typedef int(FUNC_TYPE)(int, int);
	FUNC_TYPE* f = my_func;
	//如何呼叫？
	(*f)(10, 20);
	f(10, 20);
}

//2. 定義函式指標型別
void test02(){
	typedef int(*FUNC_POINTER)(int, int);
	FUNC_POINTER f = my_func;
	//如何呼叫？
	(*f)(10, 20);
	f(10, 20);
}

//3. 直接定義函式指標變數
void test03(){
	int(*f)(int, int) = my_func;
	//如何呼叫
	(*f)(10, 20);
	f(10, 20);
}

函式指標做函式引數(回呼函式)

函式引數除了是普通變數，還可以是函式指標變數，

 //形參為普通變數  
void fun(int x ){}
 //形參為函式指標變數  
void fun(int(*p)(int a)){}

函式指標變數常見的用途之一是把指標作為引數傳遞到其他函式，指向函式的指標也可以作為引數，以實作函式地址的傳遞，

11. 獲取順序表指定元素的后繼

//獲取順序表指定元素的后繼
Status Next_elem(SqList L,int i,int &e){
	if(i<1||i>L.length){
		return ERROR;
	}
	if(i==GetLength(L)){
		printf("最后一個元素沒有后繼");
		return ERROR; 
	}
	
	e = L.elem[i];
}

12. 獲取順序表指定元素的前驅

//獲取順序表指定元素的前驅 
Status Prior_elem(SqList L,int i,int &e){
	if(i<1||i>L.length){
		return ERROR;
	}
	if(i==1){
		printf("第一個元素沒有前驅");
		return ERROR; 
	}
	
	e = L.elem[i-2];
}

13. 插入演算法實作

//在順序表中插入指定的元素
Status ListInsert_Sq(SqList &L,int i,int e){
	if(i<1||i>GetLength(L)+1)
		return ERROR;
	if(GetLength(L)>=L.listsize){
		int *newspace = (int*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(int)); //重新分配記憶體空間 
		if(!newspace){
			exit(OVERFLOW);
		} 
		L.elem = newspace;
		L.listsize+=LISTINCREMENT;            
	}
	
//書上的 
//	int *q,*p;
//	q = &(L.elem[i-1]);
//	for(p=&(L.elem[L.length-1]);p>=q;p--)
//		*(p+1)=*p;
//	*q=e;
//	++L.length;
//	return OK;
	int k,j;
	for(k = 0,j=L.length-1;j>=k;k++,j--){
		L.elem[j+1] = L.elem[j];
	} 
	L.elem[k] = e;
	++L.length;
	return OK;
	
}

考慮移動元素的平均情況:

假設在第 i 個元素之前插入的概率為,則在長度為n 的線性表中插入一個元素所需移動元素次數的期望值為：
在這里插入代碼片 在這里插入圖片描述
若假定在線性表中任何一個位置上進行插入的概率都是相等的，則移動元素的期望值為：

14. 洗掉演算法實作

//洗掉順序表指定位置元素
Status DeleteList_Sq(SqList &L,int i,int &e)
{
    int j=0;
    if(i<1||i>L.length)
    {
        return ERROR;;
    }
    else
    {
    	e = L.elem[i-1];
        for(j=i; j<=L.length-1; j++)
        {
            L.elem[j-1]=L.elem[j];
        }
        --L.length;
    }

}