当前位置：网站首页>线性表之顺序表

线性表之顺序表

2022-08-09 15:07:00 【R h yyy】

目录

1.线性表概念

2.顺序表实现

2.1概念及结构

2.2 接口实现：

3.顺序表相关OJ题练习

1.线性表概念

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使
用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串...
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，
线性表在物理上存储时，通常以数组和链式结构的形式存储。
        

         

 

2.顺序表实现

2.1概念及结构

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存
储。在数组上完成数据的增删查改

2.2 接口实现：

静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大
了，空间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态
的分配空间大小，所以下面我们实现动态顺序表。
顺序表一般可以分为：
1. 静态顺序表：使用定长数组存储。

 

//顺序表的静态储存


#define MAX_SIZE 10
typedef int SQDataType;
struct SeqList
{
	SQDataType arr[MAX_SIZE];
	int size;
};
typedef struct SeqList SL;



void SeqListInit(SL *ps)        //初始化顺序表
{
	memset(ps->arr, 0, sizeof(SQDateSizeType)*MAX_SIZE);
	ps->size = 0;
}	


//实现增删查改等接口函数
//尾插   头插  尾删   头删
void SeqListPushBack(SL *ps, SQDateSizeType x)
{
	if (ps->size >= MAX_SIZE)
	{
		printf("SeqList is full\n");
	}
	ps->arr[ps->size] = x;
	ps->size++;
	
}
void SeqListPushPront(SL *ps, SQDateSizeType x)
{

}
void SeqListPopBack(SL *ps)
{
}
void SeqListPopPront(SL *ps)
{

}

2. 动态顺序表：使用动态开辟的数组存储。

 

//   动态顺序表

typedef int SQDateType;
struct SeqList
{
	SQDateType *arr;
	int size;
	int capacity;
};
typedef struct SeqList SL;
void SeqListInit(SL *ps)    //初始化数组
{
	ps->arr = NULL;
	ps->size = 0;
	ps->capacity = 0;
}
 //内存检查函数
void SeqListCheckCapacity(SL *ps)   
{
	//内存满了  就自动扩容
	if (ps->size == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SQDateType* tmp = (SQDateType*)realloc(ps->arr, newcapacity * sizeof(SQDateType));
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		else
		{
			ps->arr = tmp;
			ps->capacity = newcapacity;
		}
	}
}
 //打印函数
void SeqListPrint(SL *ps)   //打印函数
{

	for (int i = 0; i < ps->size; ++i)
	{
		printf("%d ", ps->arr[i]);

	}
	printf("\n");
}
//尾插函数
void SeqListPushBack(SL *ps, SQDateType x)
{
	SeqListCheckCapacity(ps);
	ps->arr[ps->size] = x;
	ps->size++;
}
//头插函数
void SeqListPushPront(SL *ps, SQDateType x)
{
	SeqListCheckCapacity(ps);
	for (int i = ps->size - 1; i >= 0; i--)
	{
		ps->arr[i+1] = ps->arr[i];
		
	}
	ps->arr[0] = x;
	ps->size++;
}
//尾删函数
void SeqListPopBack(SL *ps)
{
	assert(ps->size > 0);
	ps->size--;		//调用一次从尾部删一个数据
}
//头删函数
void SeqListPopPront(SL *ps)
{	
	int start = 1;
	assert( ps->size>0);
	for (int start = 1; start < ps->size; start++)
	{
		ps->arr[start - 1] = ps->arr[start];
	}
	ps->size--;
}
//任意pos位置插入
void SeqListPosInsert(SL*ps,int pos,SQDateType x)
{
	assert(pos<ps->size);
	int end = ps->size - 1;
	while (end >= pos)
	{
		ps->arr[end] = ps->arr[end - 1];
		end--;
	}
	ps->arr[pos] = x;
	ps->size++;
}
//任意pos位置删除
void SeqListPosErase(SL*ps,int pos)
{
	assert(pos<ps->size);
	int end = pos + 1;
	while (end<ps->size)
	{
		ps->arr[end - 1] = ps->arr[end];
		end++;
	}
	ps->size--;
}
//查找元素
int SeqListFinds(SL*ps, SQDateType x)
{
	int i = 0;
	assert(i < ps->size);
	for (i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == x)
		{
			return i;
		}
		
	}
	return -1;
}
//修改函数
void SeqListMidfy(SL*ps, int pos, SQDateType x)
{
	assert(pos < ps->size);
	x=ps->arr[pos];
}
void SeqListDestroy(SL* ps)
{
	free(ps);
	ps->arr = NULL;
	ps->size = 0;
	ps->capacity = 0;
}

3.顺序表相关OJ题练习

 

int removeElement(int* nums, int numsSize, int val)
{
   int up=0;
   int down=0;
    for(int i =0;i<numsSize;i++)
    {
        if(nums[up]!=val)
        {
            nums[down++]=nums[up++];
            
        }
        else
        {
            up++;
        }
    }
    return down;
}

 

原网站

版权声明
本文为[R h yyy]所创，转载请带上原文链接，感谢
https://blog.csdn.net/LibraRhy/article/details/125885360

边栏推荐

猜你喜欢

随机推荐