【順序表實作方式】靜态配置設定與動态配置設定

1、順序表的實作——靜态配置設定

靜态配置設定定義模闆代碼

#define MaxSize 10          //定義最大長度
typedef struct
{
	ElemType data[MaxSize];	//用靜态的“數組”存放資料元素，ElemType：Element Type（填寫元素類型）
	int length;			    //順序表的目前長度
}SqList;				    //順序表的類型定義，SqList:Sequence List(順序表)
           

靜态配置設定完整代碼

/*順序表的靜态配置設定*/
#include <stdio.h>
#define MaxSize 10		//定義最大長度
typedef struct
{
	int data[MaxSize];	//用靜态的“數組”存放資料元素
	int length;			//順序表的目前長度
}SqList;				//順序表的類型定義，SqList:Sequence List(順序表)

//初始化一個順序表
void InitList(SqList &L)
{
	for(int i=0; i<MaxSize;i++)
		L.data[i]=0;	//将所有資料元素設定為預設初始值0
	L.length=0;			//順序表初始長度為0
}

int main()
{
	SqList L;			//聲明一個順序表
	InitList(L);		//初始化順序表
	for(int i=0;i<MaxSize;i++)
		printf("data[%d]=%d\n",i,L.data[i]); 
    return 0;
}
           

2、順序表的實作——動态配置設定

動态配置設定定義模闆代碼

#define InitSize 10          //順序表的初始長度
typedef struct
{
	ElemType *data;	        //訓示動态配置設定數組的指針，ElemType：Element Type（填寫元素類型）
    int MaxSize;	        //順序表的最大容量
    int length;			    //順序表的目前長度
}SqList;				    //順序表的類型定義，SqList:Sequence List(順序表)
           

動态申請和釋放記憶體空間

C —— malloc、free函數

L.data=(ElemType *)malloc(InitSize*sizeof(ElemType));
//malloc函數傳回一個指針，需要強制轉型為你定義的資料類型指針
//malloc函數的參數，指明要配置設定多大的連續記憶體空間
           

C++ —— new、delete關鍵字

動态配置設定完整代碼

/*順序表的動态配置設定*/
#include <stdio.h>
#include<stdlib.h>		//malloc、free函數的頭檔案
#define InitSize 10		//預設的最大長度
typedef struct
{
	int *data;			//訓示動态配置設定數組的指針
	int MaxSize;		//順序表的最大容量
	int length;			//順序表的目前長度
}SqList;				
 
//初始化一個順序表
void InitList(SqList &L)
{
	//用malloc函數申請一片連續的存儲空間
	L.data=(int *)malloc(InitSize*sizeof(int));
	for(int i=0; i<InitSize;i++)
		L.data[i]=0;	//将所有資料元素設定為預設初始值0
	L.length=0;			//順序表初始長度為0
	L.MaxSize=InitSize;	
}

//增加動态數組的長度
void IncreaseSize(SqList &L,int len)
{
	int *p=L.data;
	L.data=(int *)malloc((L.MaxSize+len)*sizeof(int));
	for(int i=0;i<L.length;i++)
		L.data[i]=p[i];         //将資料複制到新區域
	L.MaxSize=L.MaxSize+len;    //順序表最大長度增加len
	free(p);                    //釋放原來的記憶體空間
}

int main()
{
	SqList L;			//聲明一個順序表
	InitList(L);		//初始化順序表
	IncreaseSize(L,5);
	for(int i= 0;i<L.MaxSize;i++)
		printf("data[%d]=%d\n",i,L.data[i]); 
    return 0;
}
           

3、知識回顧