您的位置: 首页  >  文章  >  顺序表

顺序表

分类: 文章 • 2022-10-06 14:17:05

一、基础知识

  • 1、顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般采用数组存储，在数组上完成增删改查等。
  • 2、线性表可以采用线性存储和链式存储
    （1）线性存储是在一片连续的单元中连续进行存储，它把逻辑上相邻的数据元素存储在物理上相邻的存储单元
    （2）链式存储是在每个结点中包含指针域，它可把逻辑上相邻的元素放在物理上不相邻的存储单元
  • 3、顺序表的线性存储示意图
    假设线性表中有n个元素，每个元素占k的存储空间，其中loc(a1)称为基地址
    顺序表

二、顺序表的分类

（1）静态顺序表：使用定长数组存储
静态定义一个顺序表，顺序表所占的内存空间开辟在内存的静态区，即栈上
顺序表
（2）动态顺序表：使用动态开辟的数组存储
动态定义一个顺序表，顺序表所占的内存空间开辟在内存的动态区，即堆上
顺序表

三、顺序表代码实现

头文件seqlist.h

#pragma once

#include<stdio.h>
#include<assert.h>
#include<string.h>
#include<stdlib.h>

typedef int SLDataType;
//顺序表的动态存储
typedef struct seqlist
{
	SLDataType* array;//指向动态开辟的数组
	size_t _size;//有效数据个数
	size_t _capacity;//容量空间的大小
}seqlist;

void seqlistInit(seqlist* psl, size_t capacity);   //初始化
void seqlistDestory(seqlist* psl);    //销毁 
void Checkcapacity(seqlist* psl);    //增容
void Pushback(seqlist* psl, SLDataType x);   //尾插
void Popback(seqlist* psl);	//尾删
void Pushfront(seqlist* psl, SLDataType x);	//头插
void Popfront(seqlist* psl);	//头删

int seqlistFind(seqlist* psl, SLDataType x);	//查找顺序表中的某个元素
void seqlistInsert(seqlist* psl, size_t pos, SLDataType x);	//在pos位置处插入一个元素
void seqlistErase(seqlist* psl, size_t pos);	//删除pos处的元素
void seqlistRemove(seqlist* psl, SLDataType x);	//删除值为x的元素
void seqlistModify(seqlist* psl, size_t pos, SLDataType x);	//将pos处的元素的值修改为x
void seqlistPrint(seqlist* psl);	//打印顺序表中的元素
void seqlistBubblesort(seqlist* psl);	//通过冒泡排序对顺序表的元素进行排序
int seqlistBinaryfind(seqlist* psl, SLDataType x);	//二分查找一个元素的位置
void seqlistRemoveAll(seqlist* psl,SLDataType x);	//移除顺序表中为x的所有元素

void seqlisttext1();	//测试顺序表的相关接口

实现文件seqlist.c

#include"seqlist.h"

//顺序表的初始化
void seqlistInit(seqlist* psl, size_t capacity)
{
	assert(psl != NULL);
	//给顺序表创建初始空间
	psl->array = (SLDataType*) malloc (capacity *sizeof(SLDataType));
	psl->_size = 0;
	psl->_capacity = capacity;
}

//顺序表的销毁 
void seqlistDestory(seqlist* psl)
{
	assert(psl != NULL);
	if (psl->_capacity)    //判断是否为顺序表开辟空间，有则释放
	{
		free(psl);
		psl->array = NULL;
		psl->_size = 0;
		psl->_capacity = 0;
	}
}

//检查是否需要增容
void Checkcapacity(seqlist* psl)
{
	assert(psl != NULL);
	if (psl->_size==psl->_capacity)
	{
		psl->_capacity *= 2;
		psl->array = (SLDataType*)realloc(psl->array,psl->_capacity*sizeof(SLDataType));//
		assert(psl->array);
	}
}

//顺序表的尾插
void Pushback(seqlist* psl, SLDataType x)
{
	assert(psl);
	Checkcapacity(psl);
	psl->array[psl->_size] = x;
	psl->_size++;
}

//顺序表的尾删
void Popback(seqlist* psl)
{
	assert(psl);
	psl->array[psl->_size] = 0;
	psl->_size--;
}

//顺序表的头插
void Pushfront(seqlist* psl, SLDataType x)
{
	assert(psl);
	Checkcapacity(psl);
	int end = psl->_size-1;
	while (end > 0)
	{
		psl->array[end+1] = psl->array[end];
		end--;
	}
	psl->array[0] = x;
	psl->_size++;
}

//顺序表的头删
void Popfront(seqlist* psl)
{
	assert(psl);
	for (size_t i = 0; i < psl->_size; i++)
	{
		psl->array[i] = psl->array[i + 1];
	}
	psl->_size--;
}

//查找顺序表中的某个元素
int seqlistFind(seqlist* psl, SLDataType x)
{
	assert(psl);
	for (size_t i = 0; i < psl->_size; i++)
	{
		if (psl->array[i]==x)
			return i;
	}
	return -1;
}

//在pos位置处插入一个元素
void seqlistInsert(seqlist* psl, size_t pos, SLDataType x)
{
	assert(psl&&pos <= psl->_size);
	Checkcapacity(psl);
	int end = psl->_size - 1;
	while (end >= (int)pos)
	{
		psl->array[end + 1] = psl->array[end];
		end--;
	}
	psl->array[pos] = x;
	psl->_size++;
}

//删除pos处的元素
void seqlistErase(seqlist* psl, size_t pos)
{
	assert(psl&&pos <= psl->_size);
	while (pos < psl->_size)
	{
		psl->array[pos] = psl->array[pos + 1];
		pos++;
	}
	psl->_size--;
}

//删除值为x的元素
void seqlistRemove(seqlist* psl, SLDataType x)
{
	assert(psl);
	int pos = seqlistFind(psl, x);
	if (pos != -1)
	{
		while (pos < (int)psl->_size)
		{
			psl->array[pos] = psl->array[pos + 1];
			pos++;
		}
		psl->_size--;
	}
	else
		printf("该数据不存在！\n");
}

//将pos处的元素的值修改为x
void seqlistModify(seqlist* psl, size_t pos, SLDataType x)
{
	assert(psl&&pos <= psl->_size);
	psl->array[pos] = x;
}

//打印顺序表中的元素
void seqlistPrint(seqlist* psl)
{
	assert(psl);
	if (psl->array != NULL)
	{
		for (size_t i = 0; i <= psl->_size-1; i++)
		{
			printf("%d ", psl->array[i]);
		}
	}
	printf("\n");
}

//通过冒泡排序对顺序表的元素进行排序
void seqlistBubblesort(seqlist* psl)
{
	assert(psl);
	size_t finish = psl->_size-1;
	while (finish > 0)
	{
		for (size_t i = 0; i<finish; i++)
		{
			if (psl->array[i]>psl->array[i + 1])
			{
				SLDataType tmp = psl->array[i];
				psl->array[i] = psl->array[i + 1];
				psl->array[i + 1] = tmp;
			}
		}
		finish--;    //不能改变psl->_size的值，所以定义finish
	}
}

//二分查找一个元素的位置
int seqlistBinaryfind(seqlist* psl, SLDataType x)
{
	assert(psl);
	int mid;
	int begin = 0;
	int end = psl->_size - 1;
	while (begin <= end)
	{
		mid = begin + (end - begin) / 2;
		if (psl->array[mid] > x)
		{
			end = mid - 1;
		}
		else if (psl->array[mid]<x)
		{
			begin = mid + 1;
		}
		else
			return mid;
	}
	if (begin>end)
		return -1;
	else
		return mid;
}

//移除顺序表中为x的所有元素
void seqlistRemoveAll(seqlist* psl,SLDataType x)
{
	assert(psl);
	size_t cur = 0;
	size_t dst = 0;
	while (cur < psl->_size - 1)
	{
		if (psl->array[cur] != x)
		{
			psl->array[dst] = psl->array[cur];
			++dst;
		}
		++cur;
	}
	psl->_size = dst;
}

//测试顺序表的相关接口
void seqlisttext1()
{
	seqlist s;
	seqlistInit(&s, 5);
	Pushfront(&s, 2);
	Pushback(&s, 1);
	Pushfront(&s, 2);
	Pushfront(&s, 2);
	Pushback(&s, 4);
	Pushfront(&s, 2);
	Pushback(&s, 1);
	Pushback(&s, 4);
	Pushback(&s, 6);
	Pushback(&s, 3);
	Pushback(&s, 7);
	//Popfront(&s);
	//Popback(&s);
	//int i = seqlistFind(&s, 4);
	//printf("%d\n", i);
	//seqlistInsert(&s, 2, 9);
	//seqlistErase(&s, 2);
	//seqlistRemove(&s, 2);
	//seqlistModify(&s, 2, 10);
	//seqlistBubblesort(&s);
	//int mid = seqlistBinaryfind(&s, 2);
	//printf("%d\n", mid);

	seqlistRemoveAll(&s, 2);
	seqlistPrint(&s);
	//seqlistDestory(&s);
}
int main()
{
	seqlisttext1();
	return 0;
}

相关推荐