数据结构-顺序表

发布于：2025-04-11 ⋅ 阅读:(42) ⋅ 点赞:(0)

目录

基本概念

什么是数据结构？

数据

结构 

线性结构

树形结构

网状结构

第一章绪论 了解概念

几个概念

数据存储方式：

算法的五个重要特性:

算法设计的要求:

总结

线性表

线性表的定义：

顺序表的设计思想

定长顺序表

不定长顺序表

​编辑

实现顺序表的操作

定长顺序表

不定长顺序表

顺序表总结

基本概念

什么是数据结构？

数据

数据，是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。

结构 

线性结构

（比如图书目录文件，一对一的关系）

树形结构

（学校架构图，一对多的关系）

网状结构

（交通示意图，多对多的关系）

数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及他们之间的关系和操作等的科学。

三种数据结构：

线性结构：线性表（顺序表，链表）（栈，队列）（两种特殊的线性表）

树形结构：二叉树（树都可转成二叉树，二叉树的重要性）

网状结构：图

第一章绪论 了解概念

几个概念

数据元素：是数据的基本单位，在计算机程序通常作为一个整体进行考虑和处理。

数据项：是数据的不可分割的最小单位。一个数据元素可由若干个数据项组成。

数据对象：是性质相同的元素的集合，是数据的一个子集。

数据存储方式：

顺序存储：逻辑相邻，物理也相邻

链式存储：逻辑相邻，物理不一定相邻

算法的五个重要特性:

有穷性,确定性,可行性,输入,输出.

算法设计的要求:

正确性,可读性,健壮性(鲁棒性(Robust,健壮)),效率与低存储量需求.

总结

数据结构的基本含义，简单来说，数据结构就是研究数据（不仅仅是数值的数据）之间的关系以及操作。顾名思义，就是数据的结构，只有你清楚了这些结构如何表现如何处理问题的，你就会发现，数据结构不仅仅拘泥于某一种语言，它更多的是一种思想理念，这样你在实际的编程中你才能运用它，使你的代码更加高效。因为你心中有它，心中有数据结构，那么只要能熟能生巧，你就会自然而然的想到使用它，从而你的代码就会更加高效。

线性表

线性表的定义：

  • 存在唯一的一个被称为“第一个”的数据元素；
  • 存在唯一的一个被称为“最后一个”的数据元素；
  • 除第一个之外，集合中的每一个数据元素都只有一个前驱；
  • 除最后一个之外，集合中的每一个数据元素都只有一个后继；
  • 线性表是最简单最常用的一种线性表。
  • 线性表分为顺序表和链表。
  • 顺序表又分为定长顺序表和不定长顺序表。
  • 线性表的顺序表，

顺序表的设计思想

定长顺序表

加入length和左端连续。

struct SqLsit
{
     int elem[10];
     int length;
}SqList

结构示意图如下:

不定长顺序表

typedef struct DSQList{	
     int* elem;//动态内存的地址	
     int length;//有效数据的个数
     int listsize;//总容量
}DSQList,*DPSQList;

很明显,为了能实现扩容(否则如何实现再次判满呢?),我们必须要在定长顺序表的基础上增加一个总容量;结构示意图如下:

实现顺序表的操作

定长顺序表

.h文件

#pragma once
//预防头文件被重复引用
//定义与声明

//定长的顺序表
typedef struct SQList
{
	int elem[10];//存放数据，固定长度位10
	int length;//有效数据个数
} SQList, * PSQList;

//SQList *==PSQList

//初始化
void InitSqlist(PSQList ps);

//插入数据，在ps顺序表的pos位置插入val;
bool Insert(PSQList ps, int pos, int val);

//判空
bool IsEmpty(PSQList ps);

//在ps中查找第一个key值，找到返回下标，没有找到返回-1；
int Search(PSQList ps, int key);

//删除pos位置的值
bool DelPos(PSQList ps, int pos);

//删除第一个val的值
bool DelVal(PSQList ps, int val);

//返回key的前驱下标，如果不存在返回-1；
int GetPrio(PSQList ps, int key);

//返回key的后继下标，如果不存在返回-1；
int GetNext(PSQList ps, int key);

//输出
void Show(PSQList ps);

//清空数据
void Clear(PSQList ps);

//销毁整个内存
void Destroy(PSQList ps);

.cpp文件

#include "sqlist.h"
#include <assert.h>
#include <stdio.h>

//初始化
void InitSqlist(PSQList ps)
{
	assert(ps != NULL);
	if (ps == NULL)
		return;
	ps->length = 0;
}

static bool isFul(PSQList ps)
{
	return ps->length == 10;
}

//插入数据，在ps顺序表的pos位置插入val;
bool Insert(PSQList ps, int pos, int val)
{
	assert(ps != NULL);
	if (ps == NULL)
		return false;
	//参数判断
	if (ps->length < pos || pos < 0 || isFul(ps))
		return false;

	
	for (int i= ps->length; i >= pos; i--)
	{
		ps->elem[i+1] = ps->elem[i];
	}
	ps->length++;
	ps->elem[pos] = val;
	
	return true;
}

//判空
bool IsEmpty(PSQList ps)
{
	return ps->length == 0;
}

//在ps中查找第一个key值，找到返回下标，没有找到返回-1；
int Search(PSQList ps, int key)
{
	for (int i = 0; i < ps->length; i++)
	{
		if (key == ps->elem[i])
			return i;
	}
	return -1;
}

//删除pos位置的值
bool DelPos(PSQList ps, int pos)
{
	assert(ps != NULL);
	if (ps == NULL)
		return false;
	//参数判断
	if (ps->length <= pos || pos < 0)
		return false;


	for (int i = pos; i < ps->length-1; i++)
	{
		ps->elem[i] = ps->elem[i + 1];
	}
	ps->length--;

	return true;
}

//删除第一个val的值
bool DelVal(PSQList ps, int val)
{
	int i = Search(ps, val);
	if (i < 0)
		return false;

	return DelPos(ps, i);
}

//返回key的前驱下标，如果不存在返回-1；
int GetPrio(PSQList ps, int key)
{
	int i = Search(ps, key);
	if (i <= 0)
		return -1;
	
	return i - 1;
}

//返回key的后继下标，如果不存在返回-1；
int GetNext(PSQList ps, int key)
{
	int i = Search(ps, key);

	if (i < 0 || i == ps->length - 1)
		return -1;

	return i + 1;
}

//输出
void Show(PSQList ps)
{
	assert(ps != NULL);
	if (ps == NULL)
		return ;
	
	for (int i = 0; i < ps->length; i++)
	{
		printf("%d ", ps->elem[i]);
	}
	printf("\n");
}

//清空数据
void Clear(PSQList ps)
{
	ps->length = 0;
}

//销毁整个内存(动态内存)
void Destroy(PSQList ps)
{
	Clear(ps);
}

不定长顺序表

.h文件

#pragma once

//可扩容的顺序表
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中查找第一个key值，找到返回下标，没有找到返回-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);

.cpp文件

#include "dsqlist.h"
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

#define INIT_SIZE 100

//初始化
void InitSqlist(DPSQList ps)
{
	assert(ps != NULL);
	if (ps == NULL)
		return;
	ps->elem = (int*)malloc(INIT_SIZE * sizeof(int));
	ps->length = 0;
	ps->listsize = INIT_SIZE;
}

static bool isFul(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;
	return true;
}

//插入数据，在ps顺序表的pos位置插入val;
bool Insert(DPSQList ps, int pos, int val)
{
	assert(ps != NULL);
	if (ps == NULL)
		return false;
	//参数判断
	if (ps->length < pos || pos < 0)
		return false;
	if (isFul(ps))
	{
		Inc(ps);
	}

	for (int i = ps->length; i >= pos; i--)
	{
		ps->elem[i + 1] = ps->elem[i];
	}
	ps->elem[pos] = val;
	ps->length++;
	return true;
}

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

//在ps中查找第一个key值，找到返回下标，没有找到返回-1；
int Search(DPSQList ps, int key)
{
	for (int i = 0; i < ps->length; i++)
	{
		if (key == ps->elem[i])
			return i;
	}
	return -1;
}

//删除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;
}

//删除第一个val的值
bool DelVal(DPSQList ps, int val)
{
	int i = Search(ps, val);
	if(i < 0)
		return false;

	return DelPos(ps, i);
}

//返回key的前驱下标，如果不存在返回-1；
int GetPrio(DPSQList ps, int key)
{
	int i = Search(ps, key);
	if (i <= 0)
		return -1;

	return i - 1;
}

//返回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;
}

//输出
void Show(DPSQList ps)
{
		assert(ps != NULL);
	if (ps == NULL)
		return ;
	
	for (int i = 0; i < ps->length; i++)
	{
		printf("%d ", ps->elem[i]);
	}
	printf("\n");
}

//清空数据
void Clear(DPSQList ps)
{
	ps->length = 0;
}

//销毁整个内存(动态内存)
void Destroy(DPSQList ps)
{
	//必要
	free(ps->elem);
	ps->elem = NULL;

	//可要
	ps->length = 0;
	ps->listsize = 0;
}

顺序表总结

顺序表的特点：

  1. 插入数据的时间复杂度是O(n),如果是尾插时间复杂度是O(1);
  2. 删除数据的时间复杂度是O(n),如果是尾删时间复杂度是O(1);
  3. 通过下标访问数据时间复杂度是O(1);

顺序表逻辑上相邻的元素物理上也相邻,所以插入和删除操作需要移动大量元素; 存储密度大(高),每个结点只存储数据元素(对比链表); 随机访问:顺序表是一种支持随机存取的存储结构,根据起始地址加上元素的序号,可以在O(1)时间内找到指定的元素,这就是随机存取的概念;

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布