【数据结构初阶】顺序表_业界新闻

发布时间:2024-08-07 22:27

阅读量:0

hi，我们又见面啦！happy~~~

————————————— 致回不去的童年 —————————————

正文开始——

前言：

顺序表是线性表的一种，所以在学习顺序表之前先了解下线性表。

一、线性表

线性表，是一类具有相同特性的数据结构的集合。常见的线性表：顺序表、链表、栈、队列、字符串...

相同特性又表现在逻辑结构和物理结构上；逻辑结构：人为想象出来的数据的组织形式，一定是线性的。物理结构：数据在内存上的存储形式，不一定是线性的。

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

二、顺序表

1、概念

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

2、与数组的区别

顺序表的底层逻辑是数组，对数组的封装，实现了常用的增删查改等接口。

3、分类

分为 静态顺序表和 动态顺序表。静态顺序表：使用定长数组存储元素。

#define N 7  typedef int SLDataType;  //方便后续修改数据类型 typedef struct SeqList{     SLDataType a[N];     //定长数组     int size;            //数组内有效数据的个数 }SL;  //为方便对结构体重新命名

缺陷：由于数组空间提前定好长度，空间给小不够用，给大了浪费。

动态顺序表：使用动态开辟的数组存储。所以相比之下，动态顺序表更有优势。

typedef int SLDataType; typedef struct SeqList{     SLDataType* arr;    //指向数组空间的指针      int size;           //有效数据个数     int capacity;       //数组空间容量 }SL;

4、动态顺序表的实现

先创建3个文件

SeqList.h 见下

#pragma once  #include<stdio.h> #include<stdlib.h> #include<assert.h>   //定义动态顺序表结构  typedef int SLDatatype; typedef struct SeqList { 	SLDatatype* arr; 	int size;            //数组内有效数据的个数 	int capacity;        //数组空间容量 }SL;  //typedef struct SeqList SL;  //初始化 void SLInit(SL* ps);  //销毁 void SLDestroy(SL* ps);  //判断空间是否充足 void SLCheck(SL* ps);  //尾插 void SLPushBack(SL* ps, SLDatatype x);  //头插 void SLPushFront(SL* ps, SLDatatype x);  //尾删 void SLPopBack(SL* ps);  //头删 void SLPopFront(SL* ps);  //在指定位置之前插入数据 void SLInsert(SL* ps,SLDatatype x,int pos);  //删除指定位置的数据 void SLErase(SL* ps, int pos);  //查找 int SLFind(SL* ps, SLDatatype x);  //打印 void SLPrint(SL* ps);

SeqList.c 见下

#define _CRT_SECURE_NO_WARNINGS 1  #include "SeqList.h"  //初始化 void SLInit(SL* ps) { 	ps->arr = NULL; 	ps->size = ps->capacity = 0; }  //判断空间是否充足 void SLCheckCapacity(SL* ps) { 	assert(ps); 	if (ps->size == ps->capacity) 	{ 		//增容 		//若ps->capacity==0,给其赋初值，若不为0，直接增大2倍 		int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity; 		SLDatatype* tmp = (SLDatatype*)realloc(ps->arr, newCapacity * sizeof(SLDatatype)); 		if (tmp == NULL) 		{ 			perror("realloc file!"); 			exit(1); 		} 		ps->arr = tmp; 		ps->capacity = newCapacity; 	} }  //尾插 void SLPushBack(SL* ps, SLDatatype x) { 	assert(ps);  	//判断空间是否充足 	SLCheckCapacity(ps);  	ps->arr[ps->size++] = x; }  //头插 void SLPushFront(SL* ps, SLDatatype x) { 	assert(ps);  	//判断空间是否充足 	SLCheckCapacity(ps);  	//数据整体后移一位 	for (int i = ps->size; i > 0; i--) 	{ 		ps->arr[i] = ps->arr[i - 1]; 	} 	//下标为0的位置空出来，插入数据 	ps->arr[0] = x;  	ps->size++; }  //尾删 void SLPopBack(SL* ps) { 	assert(ps); 	//若顺序表为空，不能尾删 	assert(ps->size);   //ps->arr[ps->size - 1] = -1;  多余了，假设原来size为4，这里直接size--，有效数据直接变为3个， 	ps->size--;                 //最后一个数据失效了，并且对之后插入数据无影响，这样操作就可以直接 	                            //达到尾删的效果 }  //头删 void SLPopFront(SL* ps) { 	assert(ps); 	assert(ps->size); 	//将数据整体前移一位 	for (int i=1;i<ps->size;i++) 	{ 		ps->arr[i - 1] = ps->arr[i]; 	} 	ps->size--; }  //在指定位置之前插入数据（空间足够才能直接插入） void SLInsert(SL* ps, SLDatatype x, int pos) { 	assert(ps); 	assert(pos >= 0 && pos <= ps->size);  	SLCheckCapacity(ps);  	//将pos之后的数据从后往前 整体后移一位 	for (int i = ps->size;i>=pos+1;i--) 	{ 		ps->arr[i] = ps->arr[i - 1]; 	} 	ps->arr[pos] = x; 	ps->size++; }  //删除指定位置的数据 void SLErase(SL* ps, int pos) { 	assert(ps); 	assert(pos >= 0 && pos < ps->size);  //注意这里pos不能等于ps->size  	//限制顺序表不能为空 	assert(ps->size);  	//将pos之后的数据从前往后，整体前移一位 	for (int i = pos+1;i<=ps->size-1;i++) 	{ 		ps->arr[i - 1] = ps->arr[i]; 	} 	ps->size--; }  //查找 int SLFind(SL* ps, SLDatatype x) { 	assert(ps); 	for (int i = 0; i < ps->size; i++) 	{ 		if (ps->arr[i] == x) 		{ 			return i; 		} 	} 	//到此说明没有找到,返回一个无用的下标 	return -1; }  //打印 void SLPrint(SL* ps) { 	for (int i = 0; i < ps->size; i++) 	{ 		printf("%d ", ps->arr[i]); 	} 	printf("\n"); }  //销毁 void SLDestroy(SL* ps)  {	 	if (ps->arr) 	{ 		free(ps->arr); 	} 	ps->arr = NULL; 	ps->size = ps->capacity = 0; }

test.c 见下

#define _CRT_SECURE_NO_WARNINGS  #include"SeqList.h"  void SLtest01() { 	SL s; 	SLInit(&s);  	 	SLPushBack(&s, 1); 	SLPushBack(&s, 2); 	SLPushBack(&s, 3); 	SLPushBack(&s, 4); 	 	SLPushFront(&s, 1); 	SLPushFront(&s, 2); 	SLPushFront(&s, 3); 	SLPushFront(&s, 4); 	SLPrint(&s);  	SLPopFront(&s); 	SLPrint(&s); 	SLPopFront(&s); 	SLPrint(&s); 	SLPopFront(&s); 	SLPrint(&s); 	SLPopFront(&s);  	SLInsert(&s, 100,2 );   	SLPrint(&s);  	SLPopBack(&s); 	SLPrint(&s);  	SLErase(&s, 3); 	SLPrint(&s);  	int n = SLFind(&s, 1); 	if (n < 0) 	{ 		printf("没找到\n"); 	} 	else 		printf("找到了,%d\n",n);  	SLDestroy(&s); }  int main() { 	SLtest01(); 	return 0; }