資料結構之動态開辟順序表

**

1.定義一個動态順序表

由于定長開辟順序表的大小依賴于存儲空間的初始配置設定量 SIZE，要想解決此問題，需要在順序表存儲空間不足時進行動态擴容

**

#define INIT_SIZE 10  // 存儲空間的初始配置設定量
typedef struct Dsqlist
{ 
	int *elem;     // 數組存儲資料元素,需在初始化時動态開辟記憶體
	int usedsize;  // 順序表的目前長度
	int size;      // 順序表存儲空間的大小
}Dsqlist,*PDSqlist;
           

：

2.動态順序表的各種操作

void InitList(PDSqlist psq);

bool Insert(PDSqlist psq,int pos,int val);

int Search(PDSqlist Psq,int pos,int key);//查找 key 值

bool DeletePos(PDSqlist Psq,int pos,int *rtv);//删除 pos 位置的值

bool Delete(PDSqlist Psq,int pos,int key);//删除一個 key 值

void Clear(PDSqlist psq);

void Destroy(PDSqlist psq);

void Show(PDSqlist psq)

①初始化

順序表的初始化就是把順序表初始化為空的順序表，需為數組elem動态開辟存儲空間，并把順序表的長度usedsize置為0，size置為初始配置設定量INIT_SIZ即可

void InitList(PDSqlist psq)
    {
    	assert(psq != NULL);
    	psq->elem = (int *)malloc(sizeof(int) * INIT_SIZE);
    	assert(psq->elem != NULL);//判斷是否開辟成功
    	psq->usedsize = 0;
    	psq->size = INIT_SIZE;
    }
           

②判斷順序表是否為滿

static bool isFull(PDSqlist psq)
{
	if (psq->usedsize == psq->size)
	{
		return true;
	}
	return false;
}
           

③為順序表動态擴容

當順序表為滿時，需要調用動态擴容函數對順序表的elem數組進行動态擴容，這裡采用二倍擴容的方式

static void Inc(PDSqlist psq)
{
	int *p = (int *)realloc(psq->elem, psq->size*sizeof(int) * 2);
	if (p != NULL)
	{
		psq->elem = p;
	}
	psq->size *= 2;
}
           

4、在 pos 位置插入 val 值

與之前的 Insert()函數 不同的是，當順序表為滿時，需要調用動态擴容函數對順序表的elem數組進行動态擴容

bool Insert(PDSqlist psq, int pos, int val)
{
	if (isFull(psq))
	{
		Inc(psq);
	}
	for (int i = psq->usedsize - 1; i >= pos; i--)
	{
		psq->elem[i + 1] = psq->elem[i];
	}
	psq->elem[pos] = val;
	psq->usedsize++;
	return true;
}
           

5、釋放動态開辟的存儲空間

由于elem數組是動态開辟的，是以具有動态擴容順序表與普通順序表不同的是需要專門設立一個函數對動态開辟的存儲空間進行釋放，否則會在程式運作過程中産生記憶體洩露。

void Destroy(PDSqlist psq)
{
	free(psq->elem);
	psq->elem = NULL;
	psq->usedsize = 0;
	psq->size = 0;
}
           

以下操作和定長開辟順序表完全一緻

static bool isEmpty(PDSqlist Psq)//判斷是否為空
{
	return Psq->usedsize == 0;
}
int Search(PDSqlist Psq,int pos,int key)//查找 key 值
{
	if(pos < 0 || pos >= Psq->usedsize || isEmpty(Psq))
	{
		return -1;
	}
	for(int i = pos;i < Psq->usedsize;i++)
	{
		if(Psq->elem[i] == key)
		{
			return i;
		}
	}
	return -1;
}

bool DeletePos(PDSqlist Psq,int pos,int *rtv)//删除 pos 位置的值
{
	if(pos < 0 || pos >= Psq->usedsize || isEmpty(Psq))
	{
		return false;
	}
	if(rtv != NULL)
	{
		*rtv = Psq->elem[pos];
	}
	for(int i = pos;i < Psq->usedsize-1;i++)
	{
		Psq->elem[i] = Psq->elem[i+1];
	}
	Psq->usedsize--;
	return true;
}

bool Delete(PDSqlist Psq,int pos,int key)//删除一個 key 值
{
	int index = Search(Psq,pos,key);
	if(index == -1)
	{
		return false;
	}
	return DeletePos(Psq,index,NULL);
}

void Clear(PDSqlist psq)//清空
{
	psq->usedsize = 0;
	//psq->size = 0;
}


void Show(PDSqlist psq)
{
	for (int i = 0; i < psq->usedsize; i++)
	{
		printf("%d ",psq->elem[i]);
	}
	printf("\n");
}
           

dsqlist.h:

#pragma once
#define INIT_SIZE 10
typedef struct Dsqlist
{
	int *elem;
	int usedsize;
	int size;
}Dsqlist,*PDSqlist; 
 
void InitList(PDSqlist Psq);
 
bool Insert(PDSqlist Psq,int pos,int val);
 
int Search(PDSqlist Psq,int pos,int key);
 
bool DeletePos(PDSqlist Psq,int pos,int *rtv);
 
bool Delete(PDSqlist Psq,int pos,int key);
 
bool GetElem(PDSqlist Psq,int pos,int *rtv); 
 
int GetLength(PDSqlist Psq);
 
void Clear(PDSqlist Psq);
 
void Destroy(PDSqlist Psq);
 
void Show(PDSqlist Psq);
           

dsqlist.cpp:

#include "dsqlist.h"
#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
 
void InitList(PDSqlist Psq)
{
	assert(Psq != NULL);
	Psq->elem = (int *)malloc(INIT_SIZE * sizeof(int));
	assert(Psq->elem != NULL);
	Psq->usedsize = 0;
	Psq->size = INIT_SIZE;
}
 
 
static void Inc(PDSqlist Psq)
{
	int *p = (int *)realloc(Psq->elem,Psq->size *2 *sizeof(int));
	assert(p != NULL);
	if (p != NULL)
	{
		Psq->elem = p;
	}
	assert(Psq->elem != NULL);
	Psq->size *= 2;
}
 
static bool IsFull(PDSqlist Psq)
{
	return Psq->usedsize == Psq->size;
}
 
 
bool Insert(PDSqlist Psq,int pos,int val)
{
	assert(Psq != NULL);
	if (pos < 0 || pos > Psq->usedsize)
	{
		return false;
	}
	if (IsFull(Psq))
	{
		Inc(Psq);
	}
	for (int i = Psq->usedsize-1; i >= pos; i--)
	{
		Psq->elem[i+1] = Psq->elem[i];
	}
	Psq->elem[pos] = val;
	Psq->usedsize++;
	return true;
}
 
static bool IsEmpty(PDSqlist Psq)
{
	return Psq->usedsize == 0;
}
 
int Search(PDSqlist Psq,int pos,int key)
{
	assert(Psq != NULL);
	if (pos < 0 || pos > Psq->usedsize || IsEmpty(Psq))
	{
		return -1;
	}
	for (int i = pos; i < Psq->usedsize; i++)
	{
		if (Psq->elem[i] == key)
		{
			return i;
		}
	}
	return -1;
 
}
 
bool DeletePos(PDSqlist Psq,int pos,int *rtv)
{
	assert(Psq != NULL);
	if (pos < 0 || pos >= Psq->usedsize || IsEmpty(Psq))
	{
		return false;
	}
	if (rtv != NULL)
	{
		*rtv = Psq->elem[pos];
	}
	for (int i = pos; i < Psq->usedsize; i++)
	{
		Psq->elem[i] = Psq->elem[i+1];
	}
	Psq->usedsize--;
	return true;
 
}
 
bool Delete(PDSqlist Psq,int pos,int key)
{
	assert(Psq != NULL);
	int index = Search(Psq,pos,key);
	if (index == -1)
	{
		return false;
	}
	return DeletePos(Psq,index,NULL);
}
 
bool GetElem(PDSqlist Psq,int pos,int *rtv)
{
	assert(Psq != NULL);
	*rtv = Psq->elem[pos];
	return true;
}
 
int GetLength(PDSqlist Psq)
{
	assert(Psq !=NULL);
	return Psq->usedsize;
}
 
void Clear(PDSqlist Psq)
{
	assert(Psq != NULL);
	Psq->usedsize = 0;
}
 
void Destroy(PDSqlist Psq)
{
	assert(Psq != NULL);
	free(Psq->elem);
	Psq->elem = NULL;
	Psq->size = 0;
	Psq->usedsize = 0;
}
 
void Show(PDSqlist Psq)
{
	assert(Psq !=NULL);
	for (int i = 0; i < Psq->usedsize; i++)
	{
		printf("%d ",Psq->elem[i]);
	}
	printf("\n");
}
           

test.cpp

#include<stdio.h>
#include<vld.h>
#include "dsqlist.h"
int main()
{
	Dsqlist ds;
	InitList(&ds);
	for (int i = 0; i < 70; i++)
	{
		Insert(&ds,i,i);
	}
	Show(&ds);
	Delete(&ds,0,2);
	Delete(&ds,0,9);
	Delete(&ds,0,0);
	Show(&ds);
	Destroy(&ds);
	return 0;
}