数据结构--不定长顺序表

1.不定长顺序表

与定长顺序表相比不定长顺序表的区别在于我们可以通过扩容来进行增添元素的存储单元。

2.结构

是对定长顺序表的一种改进，在初始时开辟内存被利用完后，还要继续插入数据时，这时候据需要扩容。故顺序表的结构设计就要发生变化。

顺序表的特点:
        插入数据的时间复杂度是O(n),如果是尾插时间复杂度是O(1)
        删除数据的时间复杂度是O(n),如果是尾删时间复杂度是O(1)
        通过下标访问数据时间复杂度是O(1)

3.代码

1.dsqlist.h

#pragma once
 
#define INIT_SIZE  10
//可扩容的顺序表 
typedef struct DSQList
{
	int* elem;//动态内存的地址
	int length;//有效数据的个数
	int listsize;//总容量
}DSQList,*DPSQList;
 
//初始化
void InitSqlist(DPSQList ps);
 
//插入数据,在ps顺序表的pos位置插入val
bool Insert(DPSQList ps, int pos, int val);
 
//判空
bool IsEmpty(DPSQList ps);
 
//在ps中查找第一个val.找到返回下标,没有找到返回-1
int Search(DPSQList ps, int key);
 
//删除pos位置的值
bool DelPos(DPSQList ps, int pos);
 
//删除第一个val的值
bool DelVal(DPSQList ps, int val);
 
//返回key的前驱下标,如果不存在返回-1
int GetPrio(DPSQList ps, int key);
 
//返回key的后继下标,如果不存在返回-1
int GetNext(DPSQList ps, int key);
 
//输出
void Show(DPSQList ps);
 
//清空数据
void Clear(DPSQList ps);
 
//销毁整个内存
void Destroy(DPSQList ps);
 
 

2.dsqlist.cpp

1.初始化

void InitSqlist(DPSQList ps)
{
	assert(ps != NULL);
	if (ps == NULL)
	{
		return;
	}
	ps->elem = (int*)malloc(sizeof(int) * INIT_SIZE);
	assert(ps->elem != NULL);
	ps->length = 0;
	ps->listsize = INIT_SIZE;
}
static  bool IsFull(DPSQList ps)
{
	return ps->length == ps->listsize;
}
 
static bool Inc(DPSQList ps)
{
	ps->elem=(int *)realloc(ps->elem, ps->listsize * 2 * sizeof(int));
	assert(ps->elem != NULL);
	ps->listsize *= 2;
	//ps->length;//不变
	return true;
}

2.插入数据,在ps顺序表的pos位置插入val

bool Insert(DPSQList ps, int pos, int val)
{
	assert(ps != NULL);
	if (ps == NULL)
	{
		return false;
	}
	if (pos<0 || pos>ps->length)
	{
		return false;
	}
	if (IsFull(ps))
	{
		Inc(ps);
	}
	//把数据往后移动
	for (int i = ps->length - 1; i >= pos; i--)
	{
		ps->elem[i + 1] = ps->elem[i];
	}
	//插入数据
	ps->elem[pos] = val;
	//有效数据个数++
	ps->length++;
 
	return true;	
}

3.判空

bool IsEmpty(DPSQList ps)
{
	return ps->length == 0;
}

4.在ps中查找第一个val.找到返回下标,没有找到返回-1

int Search(DPSQList ps, int key)
{
	for (int i = 0; i < ps->length; i++)
	{
		if (key == ps->elem[i])
		{
			return i;
		}
	}
 
	return -1;
}

5.删除pos位置的值

bool DelPos(DPSQList ps, int pos)
{
	assert(ps != NULL);
	if (ps == NULL)
	{
		return false;
	}
	if (pos < 0 || pos >= ps->length)
	{
		return false;
	}
 
	for (int i = pos; i < ps->length - 1; i++)
	{
		ps->elem[i] = ps->elem[i + 1];
	}
	//有效数据--
	ps->length--;
	return true;
}

6.删除第一个val的值

bool DelVal(DPSQList ps, int val)
{
	int i = Search(ps, val);
	if (i < 0)
	{
		return false;
	}
 
	return DelPos(ps, i);
}

7.返回key的前驱下标,如果不存在返回-1

int GetPrio(DPSQList ps, int key)
{
	int i = Search(ps, key);
	if (i <= 0)
	{
		return -1;
	}
	return i - 1;
}

8.返回key的后继下标,如果不存在返回-1

int GetNext(DPSQList ps, int key)
{
	int i = Search(ps, key);
	if (i < 0 || i == ps->length - 1)
	{
		return -1;
	}
 
	return i + 1;
}

9.输出

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

10.清空数据

void Clear(DPSQList ps)
{
	ps->length = 0;
}

11.销毁整个内存

void Destroy(DPSQList ps)
{
	free(ps->elem);//1
	ps->elem = NULL;//2
	ps->length = 0;//3
	ps->listsize = 0;//4
	//ps = NULL;//5无效的代码
}

3.test.cpp

int main()
{
	DSQList ds;
	InitSQList(&ds);
	for (int i = 0; i < 20; i++)
	{
		Insert(&ds, i, i);
	}
	Show(&ds);
	Delpos(&ds, 11);
	Show(&ds);
 
	/*Search(&ds, 9);
	Show(&ds);
	Delpos(&ds, 11);*/
	return 0;
}

运行结果：