数据结构---线性表之动/静态顺序表

2024-04-17 05:32
文章标签 数据结构 静态 顺序 线性表 之动

本文主要是介绍数据结构---线性表之动/静态顺序表，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

线性表（linear list）：

是n个具有相同特性的数据元素的有限序列。
线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。
在这里插入图片描述
本片文章主要讲述线性表中的静态顺序表和动态顺序表。

1. 静态顺序表：使用定长数组存储。
2. 动态顺序表：使用动态开辟的数组存储。
// 顺序表的静态存储
#define N 100
typedef int SLDataType;
typedef struct SeqList
{SLDataType array[N]; // 定长数组size_t size; // 有效数据的个数 
}SeqList;// 顺序表的动态存储
typedef struct SeqList
{SLDataType* array; // 指向动态开辟的数组size_t size ; // 有效数据个数size_t capicity ; // 容量空间的大小}SeqList;

静态顺序表和动态顺序表，我们可以清楚的看到两者之间的差异：
静态顺序表采用定长数组；而动态顺序表采用动态开辟的数组，当size==capacity的时候，此时插入元素的话就要就行扩容（对capacity进行更新，具体见代码）。

静态顺序表的相关操作：

#define _CRT_SECURE_NO_WARNINGS 1
#define MAX 10
typedef int DateType;
typedef unsigned int size_t;typedef struct seqlist
{DateType array[MAX];int size;//数组中有效元素的个数
}Seqlist,*pSeqlist;
//Seqlist===struct seqlist     pSeqlist===struct seqlist*//顺序表的初始化
void InitSeqlist(pSeqlist);
//顺序表的打印
void Printf(pSeqlist);
//顺序表尾插
void PushBack(pSeqlist, DateType);
//顺序尾删
void PopBack(pSeqlist);
//顺序头插
void PushFront(pSeqlist,DateType);
//顺序头删
void PopFront(pSeqlist);
//插入任意位置的操作
void Insert(pSeqlist, size_t, DateType);
//删除任意位置的操作
void Erase(pSeqlist, size_t);
// 在顺序表中查找值为data的元素，返回该元素在顺序表中的下标
int SeqListFind(pSeqList, DataType);
// 删除顺序表中值为data的元素
void SeqListRemove(pSeqList, DataType);
// 删除顺序表中所有值为data的元素
void SeqListRemoveAll(pSeqList, DataType);
// 判断顺序表是否为空
int SeqListEmpty(pSeqlist);
// 获取顺序表中元素的个数
int SeqListSize(pSeqlist);
// 用冒泡排序对顺序表中的元素进行排序
void BubbleSort(int* array, int size);
// 用选择排序对顺序表中的元素进行排序
void SelectSort(int* array, int size);
// 选择排序优化---一次找出最大最小元素所在的位置
void SelectSort_OP(int* array, int size);
seqlist.c#include "Seqlist.h"
#include<stdio.h>
#include<memory.h>
#include<assert.h>
//顺序表的初始化
void InitSeqlist(pSeqlist seq)
{seq->size = 0;memset(seq->array, 0, sizeof(seq));
}
//顺序表的打印
void Printf(pSeqlist seq)
{int i = 0;assert(seq);for (i = 0; i< seq->size;i++){printf("%d ", seq->array[i]);}printf("\n");
}
//顺序表尾插
void PushBack(pSeqlist seq, DateType data)
{ assert(seq);if (seq->size>MAX){return;}seq->array[seq->size] = data;seq->size++;
}
//顺序尾删
void PopBack(pSeqlist seq){assert(seq);if (seq->size==0){return;}seq->size--;
}
//顺序头插
void PushFront(pSeqlist seq, DateType data)
{ int i = 0;assert (seq);if (seq->size>MAX){return;}for (i = seq->size; i >0;i--){seq->array[i] = seq->array[i-1];}seq->array[0] = data;seq->size++;
}
//顺序头删
void PopFront(pSeqlist seq){int i = 0;assert(seq);for (; i< seq->size-1; i++){seq->array[i] = seq->array[i + 1];}seq->size--;
}
//插入任意位置的操作
void Insert(pSeqlist seq,size_t pos,DateType data){int i = 0;assert(seq);if (pos>=MAX){return;}for (i = seq->size; i>pos;i--){seq->array[i] = seq->array[i-1];}seq->array[pos] = data;seq->size++;
}
//删除任意位置的操作
void Erase(pSeqlist seq,size_t pos){int i = 0;assert(seq);if (pos>MAX){return;}for (i = pos; i < seq->size-1;i++){seq->array[i] = seq->array[i + 1];}seq->size--;
}
// 在顺序表中查找值为data的元素，返回该元素在顺序表中的下标
int SeqListFind(pSeqlist seq, DateType data){int i = 0;assert(seq);for (i = 0; i < seq->size;i++){if (seq->array[i]==data){return i;}}return -1;
}
// 删除顺序表中值为data的元素
void SeqListRemove(pSeqlist seq, DateType data){int ret = 0;assert(seq);ret = SeqListFind(seq,data);if (ret==-1){return;}Erase(seq, ret);
}
// 删除顺序表中所有值为data的元素
void SeqListRemoveAll(pSeqlist seq, DateType data){int count = 0;int i = 0;for (i = 0; i < seq->size;i++){if (seq->array[i]==data){count++;}else{seq->array[i - count] = seq->array[i];}}seq->size = seq->size - count;
}
// 判断顺序表是否为空
int SeqListEmpty(pSeqlist seq){assert(seq);if (seq->size==0){return 0;}return 1;
}
// 获取顺序表中元素的个数
int SeqListSize(pSeqlist seq){assert(seq);return seq->size;
}
// 用冒泡排序对顺序表中的元素进行排序
void BubbleSort(int* array, int size){int i = 0;int j = 0;int ret = 0;for (i = 0; i < size-1 ; i++){for (j = 0; j <size-1-i; j++){if (array[j]>array[j+1]){ret = array[j];array[j] = array[j + 1];array[j + 1] = ret;}}}
}// 用选择排序对顺序表中的元素进行排序
//初始序列：{49 27 65 97 76 12 38}
//第1趟：12与49交换：12{ 27 65 97 76 49 38 }
//第2趟：27不动　：12 27{65 97 76 49 38}
//第3趟：65与38交换：12 27 38{97 76 49 65}
//第4趟：97与49交换：12 27 38 49{76 97 65}
//第5趟：76与65交换：12 27 38 49 65{97 76}
//第6趟：97与76交换：12 27 38 49 65 76 97 完成
void SelectSort(int* array, int size){int i = 0;int j = 0;int flag = 0;int ret = 0;for (i = 0; i < size - 1;i++){flag = i;for (j = i; j<size-1;j++){if (array[flag]>array[j + 1]){flag = j+1;}}if (flag != i){ret = array[flag];array[flag] = array[i];array[i] = ret;}}
}
// 选择排序优化---一次找出最大最小元素所在的位置
void swap(int *a,int *b){int p;p = *a;*a = *b;*b = p;
}
void SelectSort_OP(int* array, int size){int i = 0;int left = 0;int right = size - 1;while (left<=right){int min = left;int max = right;for (i = left; i <=right;i++){if (array[i]<array[min]){min = i;}if (array[i]>array[max]){max = i;}}swap(&array[left], &array[min]);if (left == max)//最大的在最小位置上,最小的在最大max = min;swap(&array[right], &array[max]);left++;right--;}
}

OK,以上就是静态顺序表的基本接口了。

动态顺序表的相关操作：

#pragma once
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>typedef int SLDataType ;typedef struct SeqList
{SLDataType* array ;int capacity ;int size ;
}SeqList ;//初始化&销毁
void SeqListInit(SeqList* sl, size_t capacity) ;
void SeqListDestroy(SeqList* sl) ;//增删查改
//尾插
void SeqListPushBack(SeqList* sl, SLDataType data) ;//头插
void SeqListPushFront(SeqList* sl, SLDataType data) ;//尾删
void SeqListPopBack(SeqList* sl) ;//头删
void SeqListPopFront(SeqList* sl) ;//打印
void SeqListPrint(SeqList* sl) ;//内部接口
void CheckCapacity(SeqList* sl) ;//获取元素
void GetElem(SeqList* sl, int i, SLDataType* e) ;//表中间插入操作
void SeqListInsert(SeqList* sl, size_t pos, SLDataType data) ;//表中间删除操作
void SeqListDelete(SeqList* sl, size_t pos) ;//在顺序表中查询元素
int SeqListFind(SeqList* sl, SLDataType data) ;//删除遇到的指定的第一个元素
void SeqListRemove(SeqList* sl, SLDataType data) ;//修改pos所在下标对应的元素
void SeqListModify(SeqList* sl, size_t pos, SLDataType data) ;//删除遇到所有的指定元素
void SeqListRemoveAll(SeqList* sl, SLDataType data) ;//冒泡排序
void SeqListBubbleSort(SeqList* sl) ;//折半查找（二分查找）
int SeqListBinarySearch(SeqList* sl, SLDataType data) ;//SeqList.c
#include "SeqList.h"//初始化
void SeqListInit(SeqList* sl, size_t capacity) 
{sl->capacity = capacity ;sl->size = 0 ;sl->array = (SLDataType *) malloc (capacity * sizeof(SLDataType)) ;assert(sl->array != NULL) ;printf("初始化成功！元素个数为%d\n",sl->size) ;
}//销毁
void SeqListDestroy(SeqList* sl) 
{assert(sl != NULL) ;free(sl->array) ;sl->array = NULL ; //防御性代码sl->capacity = sl->size = 0 ;printf("销毁成功！元素个数为%d\n",sl->size) ;
}//尾插
void SeqListPushBack(SeqList* sl, SLDataType data) 
{assert(sl != NULL) ;CheckCapacity(sl) ;sl->array[sl->size] = data ;sl->size++ ;//printf("尾插成功！元素个数为%d\n",sl->size) ;
}//尾删
void SeqListPopBack(SeqList* sl)
{assert(sl != NULL) ;if(sl->size == 0){printf("此表本为空，无法删除!\n") ;}else{sl->size-- ;printf("尾删成功！元素个数为%d\n",sl->size) ;}
}//头插
void SeqListPushFront(SeqList* sl, SLDataType data)
{int i = 0 ;assert(sl != NULL) ;CheckCapacity(sl) ;for(i=sl->size-1; i>=0; i--){sl->array[i+1] = sl->array[i] ;  /****************************/ }sl->array[0] = data ;sl->size++ ;printf("头插成功！元素个数为%d\n",sl->size) ;
}//打印
void SeqListPrint(SeqList* sl)
{int i = 0 ;for(i=0; i<sl->size; i++){printf(" %d ", sl->array[i]) ;}printf("\n打印成功！元素个数为: %d\n",sl->size) ;
}//内部接口
void CheckCapacity(SeqList* sl) 
{int i = 0 ;//申请空间int newCapacity = sl->capacity * 2 ;SLDataType * newArray = (SLDataType*) malloc (newCapacity * sizeof(SLDataType)) ;assert(newArray) ;//搬运//int i = 0 ;for(i=0; i<sl->size; i++){newArray[i] = sl->array[i] ;}//释放旧的空间free(sl->array) ;//再保存新的sl->array = newArray ;sl->capacity = newCapacity ;
}//获得某位置的元素
void GetElem(SeqList* sl, int i, SLDataType* e)
{//若表长为0，或者i不在正确的范围内，则提示操作错误if(sl->size == 0 || i<1 || i>sl->size){printf("获取操作失败！\n") ;}//若i的位置合法，则打印else{*e = sl->array[i-1] ;printf("获取成功，array[%d]为: %d\n", i-1,*e) ;}
}//表中间插入操作
void SeqListInsert(SeqList* sl, size_t pos, SLDataType data)
{//i为数据下标int i = 0 ;assert(sl) ;CheckCapacity(sl) ;assert((int)pos >= 0 && (int)pos <= sl->size) ;for(i=sl->size-1; i>=pos; i--){sl->array[i+1] = sl->array[i] ;}sl->array[pos] = data ;sl->size++ ;
}//表中间删除操作
void SeqListDelete(SeqList* sl, size_t pos) 
{//i 为数据下标int i = 0 ;assert(sl) ;assert((int)pos>=0 && (int)pos<=sl->size-1) ;for(i=pos+1; i<sl->size; i++){sl->array[i-1] = sl->array[i] ;}sl->size-- ;
}//在顺序表中查询元素
int SeqListFind(SeqList* sl, SLDataType data)
{//若在顺序表中找到该元素，则返回其下标，否则返回-1int i = 0 ;assert(sl != NULL) ;for(i=0; i<sl->size; i++){if(sl->array[i] == data){return i ;}}return -1 ;
}//删除遇到的指定的第一个元素
void SeqListRemove(SeqList* sl, SLDataType data) 
{int pos = SeqListFind(sl, data) ;if(pos != -1){SeqListDelete(sl, pos) ;}
}//修改pos所在下标对应的元素
void SeqListModify(SeqList* sl, size_t pos, SLDataType data) 
{assert(sl != NULL) ;assert((int)pos>=0 && (int)pos<=sl->size-1) ;sl->array[pos] = data ;
}//删除遇到所有的指定元素
void SeqListRemoveAll(SeqList* sl, SLDataType data) 
{int j = 0 ;int i = 0 ;for(i=0; i<sl->size; i++){if(sl->array[i] != data){sl->array[j++] = sl->array [i] ;}}sl->size = j ;
}//比较大小
static void Swap(int* a, int* b)
{int tmp = *a ;*a = *b ;*b = tmp ;
}//冒泡排序
void SeqListBubbleSort(SeqList* sl)
{int i = 0 ;int j = 0 ;assert(sl != NULL) ;for(i=0; i<sl->size-1; i++){for(j=0; j<sl->size-1-i; j++){if(sl->array[j] > sl->array[j+1]){Swap(sl->array+j, sl->array+j+1) ;//与 Swap(&sl->array[j],&sl->array[j+1])等价}}}
}//折半查找（二分查找）
int SeqListBinarySearch(SeqList* sl, SLDataType data)
{//left和right均为下标，范围是[left, right] ,左闭右闭区间int left = 0 ;int right = sl->size-1 ;int mid = 0 ;while(left <= right){mid = (right-left)/2 + left ;if(data == sl->array[mid]){return mid ;}else if(data < sl->array[mid]){right = mid - 1 ;}else {left = mid+ 1 ;}}return -1 ;
}//main.c
#include "SeqList.h"int main()
{SeqList sl ;SLDataType e ;int BinarySearchRet = 0 ;printf("----------顺序表的基本操作----------\n") ;printf("\n初始化：\n") ;SeqListInit(&sl, 10) ;printf("\n尾插: \n") ;SeqListPushBack(&sl, 1) ;SeqListPushBack(&sl, 2) ;SeqListPushBack(&sl, 3) ;SeqListPushBack(&sl, 4) ;SeqListPushBack(&sl, 5) ;SeqListPushBack(&sl, 9) ;SeqListPushBack(&sl, 5) ;SeqListPushBack(&sl, 8) ;SeqListPushBack(&sl, 5) ;SeqListPushBack(&sl, 5) ;SeqListPushBack(&sl, 5) ;SeqListPrint(&sl) ;printf("\n尾删: \n") ;SeqListPopBack(&sl) ;SeqListPrint(&sl) ;printf("\n头插: \n") ;SeqListPushFront(&sl, 10) ;SeqListPrint(&sl) ;printf("\n获取元素: \n") ;GetElem(&sl, 1,&e) ;printf("\n插入元素:\n") ;SeqListInsert( &sl, 3, 99) ;SeqListPrint(&sl) ;printf("\n删除元素:\n") ;SeqListDelete(&sl, 2) ;SeqListPrint(&sl) ;printf("\n删除遇到的第一个元素:\n") ;SeqListRemove(&sl, 5) ;SeqListPrint(&sl) ;printf("\n修改指定位置的元素: \n") ;SeqListModify(&sl, 3, 333) ;SeqListPrint(&sl) ;printf("\n删除遇到的指定的所有元素:\n") ;SeqListRemoveAll(&sl, 5) ;SeqListPrint(&sl) ;printf("\n排序\n") ;SeqListBubbleSort(&sl) ;SeqListPrint(&sl) ;printf("\n二分查找:\n") ;BinarySearchRet = SeqListBinarySearch(&sl, 333) ;printf("\n二分查找到的下标是:[%d]\n", BinarySearchRet) ;printf("\n销毁：\n") ;SeqListDestroy(&sl) ;printf("\n") ;return 0 ;
}

测试结果：
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
OK，以上就是关于顺序表的所有操作了，希望可以对你有所帮助。链表的相关操作会在后续与大家分享❥(^_-)

这篇关于数据结构---线性表之动/静态顺序表的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/910901。

相关文章

JAVA利用顺序表实现“杨辉三角”的思路及代码示例

JAVA利用顺序表实现“杨辉三角”的思路及代码示例

《JAVA利用顺序表实现“杨辉三角”的思路及代码示例》杨辉三角形是中国古代数学的杰出研究成果之一,是我国北宋数学家贾宪于1050年首先发现并使用的,：本文主要介绍JAVA利用顺序表实现杨辉三角的思... 目录一：“杨辉三角”题目链接二：题解代码：三：题解思路：总结一：“杨辉三角”题目链接题目链接：点击这里
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小)： 2.2 C语言代码（手写堆） 2.3 C++代码（使用优先级队列 priority_queue）
阅读更多...
顺序表之创建，判满，插入，输出

顺序表之创建，判满，插入，输出

文章目录 🍊自我介绍🍊创建一个空的顺序表，为结构体在堆区分配空间🍊插入数据🍊输出数据🍊判断顺序表是否满了，满了返回值1，否则返回0🍊main函数 你的点赞评论就是对博主最大的鼓励 当然喜欢的小伙伴可以：点赞+关注+评论+收藏（一键四连）哦~ 🍊自我介绍   Hello,大家好，我是小珑也要变强（也是小珑），我是易编程·终身成长社群的一名“创始团队·嘉宾”
阅读更多...
《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多，算法平均时间性能比直接插入排序差。当初始记录无序，n较大时， 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In
阅读更多...
Thymeleaf：生成静态文件及异常处理java.lang.NoClassDefFoundError: ognl/PropertyAccessor

Thymeleaf：生成静态文件及异常处理java.lang.NoClassDefFoundError: ognl/PropertyAccessor

我们需要引入包： <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-thymeleaf</artifactId></dependency><dependency><groupId>org.springframework</groupId><artifactId>sp
阅读更多...
web群集--nginx配置文件location匹配符的优先级顺序详解及验证

web群集--nginx配置文件location匹配符的优先级顺序详解及验证

文章目录 前言优先级顺序优先级顺序(详解)1. 精确匹配（Exact Match）2. 正则表达式匹配（Regex Match）3. 前缀匹配（Prefix Match） 匹配规则的综合应用验证优先级 前言 location的作用 在 NGINX 中，location 指令用于定义如何处理特定的请求 URI。由于网站往往需要不同的处理方式来适应各种请求，NGINX 提供了多种匹
阅读更多...
【408数据结构】散列 （哈希）知识点集合复习考点题目

【408数据结构】散列 （哈希）知识点集合复习考点题目

苏泽  “弃工从研”的路上很孤独，于是我记下了些许笔记相伴，希望能够帮助到大家    知识点 1. 散列查找 散列查找是一种高效的查找方法，它通过散列函数将关键字映射到数组的一个位置，从而实现快速查找。这种方法的时间复杂度平均为(
阅读更多...
浙大数据结构：树的定义与操作

浙大数据结构：树的定义与操作

四种遍历 #include<iostream>#include<queue>using namespace std;typedef struct treenode *BinTree;typedef BinTree position;typedef int ElementType;struct treenode{ElementType data;BinTree left;BinTre
阅读更多...
Python 内置的一些数据结构

Python 内置的一些数据结构

文章目录 1. 列表 (List)2. 元组 (Tuple)3. 字典 (Dictionary)4. 集合 (Set)5. 字符串 (String) Python 提供了几种内置的数据结构来存储和操作数据，每种都有其独特的特点和用途。下面是一些常用的数据结构及其简要说明： 1. 列表 (List) 列表是一种可变的有序集合，可以存放任意类型的数据。列表中的元素可以通过索
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2