四时宝库

程序员的知识宝库

2024年08月23日

数据结构-线性表之顺序表（数据结构线性表顺序存储）

线性表

（1）逻辑结构和物理结构

物理结构：数据元素在内存中真实的存放次序，有可能是连续存放的，也可能是散落于内存里。
逻辑结构：为了便于描述数据元素之间的关系，我们想象出数据之间应该有某种的对应关系，如果是一对一就是线性结构，不是一对一那就是非线性结构。

（2）线性表

常见的线性结构就是线性表，所以说线性表在逻辑上是线性的，但是在物理上不一定是线性的。常见的线性表有顺序表，链表，栈，队列等。
线性表在物理上存储时，通常以数组和链式的结构存储

顺序表(数组)

1）概念

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

（2）静态顺序表

头文件内结构体的定义如下

#pragma once

typedef int SLDataType;
#define N 10

struct SeqList
{
	SLDataType a[N];//定长数组
	int size;//有效数据个数，也就是数组长度
};

这里一定要注意不要习惯性的定义结构体，所有的数据类型都是int型的，因为数组有时存放的不会是int数据，而是其他数据，为了结构体通用，防止日后反复修改，我们要利用typede和#define进行前定义。可以发现静态存储结构，缺点还是很大的，比如说在做通讯录这种东西的时候，大小无法准确控制，所以日常工作中基本不用静态存储的这种结构

（3）动态顺序表

A：头文件内结构体的定义如下

#pragma once

typedef int SLDataType;

struct SeqList
{
	SLDataType* Array;
	int Size;//有效数据个数
	int Capacity;//容量大小
};
12345678910
  • 动态顺序表所变化的是多了一个表示容量大小的参数，因为如果一旦达到容量上限，就可以用relloc扩容，使用的是指向一片连续空间的指针

B：操作

*说明
这是文件的逻辑


下面是测试文件 SeqList_test.c

#include "SeqList.h"

//测试插入删除元素
void Test1(SeqList* ps)
{
	SeqListInit(ps);//初始化
	SeqListPushBack(ps, 1);
	SeqListPushBack(ps, 2);
	SeqListPushBack(ps, 3);
	SeqListPushBack(ps, 4);
	SeqListPushBack(ps, 5);//尾部插入依次元素
	SeqListPrint(ps);

	SeqListPopBack(&s);
	SeqListPopBack(&s);
	SeqListPopBack(&s);//尾部依次删除元素
	SeqListPrint(&s);

	SeqListPushFront(&s, 9);
	SeqListPushFront(&s, 8);
	SeqListPushFront(&s, 7);
	SeqListPushFront(&s, 6);
	SeqListPushFront(&s, 5);//头部依次插入元素
	SeqListPrint(&s);

	SeqListPopFront(&s);
	SeqListPopFront(&s);
	SeqListPopFront(&s);//头部依次删除元素
	SeqListPrint(&s);

	SeqListInsert(&s, 1, 5);
	SeqListInsert(&s, 1, 6);//向指定位置插入元素
	SeqListPrint(&s);

	SeqListErase(&s, 1);
	SeqListErase(&s, 1);//把指定位置元素删除
	SeqListPrint(&s);

}
//测试接受用户输入删除指定元素删除
void Test2(SeqList* ps)
{
	printf("请输入要删除的元素\n");
	int res = 0;
	scanf_s("%d", &res);
	int index = SeqListFind(ps, res);
	if (index == -1)
		printf("没有此元素");
	else
	{
		printf("删除后为\n");
		SeqListErase(ps, index);
		SeqListPrint(ps);
	}
}
int main()
{
	SeqList s;
	Test1(&s);//测试插入删除元素
	Test2(&s);//测试用户指定元素删除
	return 0;
}

下面是接口声明"SeqList.h"

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLDataType;

typedef struct SeqList
{
	SLDataType* Array;
	int Size;//有效数据个数
	int Capacity;//容量大小
}SeqList;

void SeqListInit(SeqList* ps);//初始化
void SeqListDestory(SeqList* ps);//销毁

void SeqListPrint(SeqList* ps);//屏幕输出操作
void SeqListCheckCapacity(SeqList* ps);//检查容量是否满了


void SeqListPushBack(SeqList* ps, SLDataType x);//尾插（可以与任意位置插入复用）
void SeqListPopBack(SeqList* ps);//尾删除（可以与任意位置删除复用）
void SeqListPushFront(SeqList* ps, SLDataType x);//头插（可以与任意位置插入复用）
void SeqListPopFront(SeqList* ps);//头删（可以与任意位置删除复用）
void SeqListInsert(SeqList* ps, int pos, SLDataType x);//任意位置插入
void SeqListErase(SeqList* ps, int pos);//任意位置删除

int  SeqListFind(SeqList* ps, SLDataType x);//使用顺序查找法查找某个元素的位置
int  SeqListFindvalue_Bind(SeqList* ps, int pos);//使用二分查找法查找某个元素的位置

下面是接口实现"SeqList.c"

#include "SeqList.h"

void SeqListInit(SeqList* ps)//初始化
{
	/*也可以这样申请
	s.Size = 0;
	s.Array = NULL;
	s.Capacity = 0;
	*/
	ps->Array = (SLDataType*)malloc(sizeof(SLDataType) * 4);
	if (ps->Array == NULL)
	{
		printf("申请失败\n");
		exit(-1);
	}
	ps->Size = 0;
	ps->Capacity = 4;
}
void SeqListDestory(SeqList* ps)//销毁
{
	free(ps->Array);
	ps = NULL;
	ps->Capacity = ps->Size = 0;
}
void SeqListPrint(SeqList* ps)//打印
{
	assert(ps);
	for (int i = 0; i < ps->Size; ++i)
	{
		printf("%d ", ps->Array[i]);
	}
	printf("\n");


}
void SeqListCheckCapacity(SeqList* ps)//检查容量是否满了
{
	if (ps->Size == ps->Capacity)
	{
		ps->Capacity *= 2;
		ps->Array = (SLDataType*)realloc(ps->Array, sizeof(SLDataType)*ps->Capacity);
		if (ps->Array == NULL)//扩容失败
		{
			printf("扩容失败\n");
			exit(-1);
		}
	}
	

}

void SeqListPushBack(SeqList* ps, SLDataType x)//尾插
{
	/*尾插就是size位置上的插入
	assert(ps);//警告，指针为空
	SeqListCheckCapacity(ps);//满了就扩容
	ps->Array[ps->Size] = x;//size表示有效个数，但同时是下一个元素的下标
	ps->Size++;//元素加1
	*/
	SeqListInsert(ps,ps->Size, x);
}
void SeqListPopBack(SeqList* ps)//尾删除
{
	assert(ps);
	ps->Size--;

}
void SeqListPushFront(SeqList* ps, SLDataType x)//头插
{
	/*头插是0位置上的插入
	assert(ps);
	SeqListCheckCapacity(ps);//满了就扩容
	for (int i = ps->Size-1; i >= 0; i--)//头插法：从最后一个元素开始，依次向后移，把0的位置空出来
	{
		ps->Array[i+1] = ps->Array[i];
	}
	ps->Array[0] = x;
	ps->Size++;
	*/
	SeqListInsert(ps, 0, x);

}
void SeqListPopFront(SeqList* ps)//头删
{
	/*头删是0位置的删除
	assert(ps);
	for (int i = 0; i < ps->Size; i++)
	{
		ps->Array[i] = ps->Array[i + 1];//删除时直接覆盖即可
	}
	ps->Size--;
	*/
	SeqListErase(ps, 0);
	

}
void SeqListInsert(SeqList* ps, int pos, SLDataType x)//任意位置插入
{
	assert(ps);
	assert(pos <= ps->Size && pos>= 0);//插入位置有误
	SeqListCheckCapacity(ps);
	for (int i = ps->Size - 1; i >= pos; i--)//从插入位置以后依次向后挪动
	{
		ps->Array[i + 1] = ps->Array[i];
	}
	ps->Array[pos] = x;
	ps->Size++;

}
void SeqListErase(SeqList* ps, int pos)//任意位置删除
{
	assert(ps);
	assert(pos < ps->Size && pos >= 0);//删除位置有误
	for (int i = pos; i < ps->Size; i++)
	{
		ps->Array[i] = ps->Array[i + 1];
	}
	ps->Size--;
}

int  SeqListFind(SeqList* ps, SLDataType x)//顺序查找法
{
	assert(ps);
	int i = 0;
	while (i<ps->Size)
	{
		if (ps->Array[i] == x)
			return i;
		++i;
	}
	return -1;


}
int  SeqListFindvalue_Bind(SeqList* ps, int pos)//二分查找法（前提要排序）
{
	int low = 0;
	int high = ps->Size - 1;
	while (low < high)
	{
		int mid = (low + high) / 2;
		if (pos < ps->Array[mid])
			high = mid - 1;
		else if (pos > ps->Array[mid])
			low = mid + 1;
		else
			return mid;
	}
}

结果展示

尾部依次插入五个元素后，再删除两个元素

头部依次插入五个元素后，再删除两个元素

在原有序列的某个位置插入两个元素，再把元素删除

接受用户删除元素

结语

顺序表的优点在于：

  • 可以随机访问
  • 缓存命中率比较高(这是因为其数据是连续的，依靠预加载的就有了优势)

顺序表的缺点在于：

  • 中间或者头部的插入删除很慢，需要移动数据，时间复杂度为O(N)
  • 空间不够时，增容会导致一定空间的浪费

标签：assert.h 

作者:sishi88 , 分类:技术教程 , 浏览:11 , 评论:0

发表评论:

控制面板
您好，欢迎到访网站！
  查看权限
网站分类
最新留言
    友情链接