建购物网站如何运营,网站404页面制作方法,wordpress回到顶部,有关于网站建设的论文【数据结构】顺序表 前言#xff1a;一、线性表二、顺序表1.顺序表的概念及结构#xff1a;2.顺序表的分类#xff1a;3.顺序表缺陷#xff1a; 三、顺序表的代码实现#xff1a;1.头文件#xff1a;2.函数文件#xff1a;3.测试文件#xff1a; 四、顺序表的相关OJ题一、线性表二、顺序表1.顺序表的概念及结构2.顺序表的分类3.顺序表缺陷 三、顺序表的代码实现1.头文件2.函数文件3.测试文件 四、顺序表的相关OJ题1原地移除数组中所有的元素val1.题目描述2.思路表述3.代码实现: 2删除有序数组中的重复项1.题目描述2.思路表述3.代码实现 3合并两个有序数组1.题目描述2.思路表述3.代码实现 前言
顺序表是一种常见的数据结构今天就让我来带领大家一起学习一下吧 不会再休息一分一毫了OKlet’s go
一、线性表
线性表linear list是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使 用的数据结构常见的线性表顺序表、链表、栈、队列、字符串…线性表在逻辑上是线性结构也就说是连续的一条直线。但是在物理结构上并不一定是连续的 线性表在物理上存储时通常以数组和链式结构的形式存储。 二、顺序表
1.顺序表的概念及结构
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构一般情况下采用数组存 储。在数组上完成数据的增删查改。
2.顺序表的分类
顺序表一般可以分为
静态顺序表使用定长数组存储元素。
//顺序表的静态存储
#define N 7
typedef int SLDataType;typedef struct SeqList
{SLDataType array[N];//定长数组size_t size;//有效数据的个数
}SeqList;2. 动态顺序表使用动态开辟的数组存储。
typedef struct SeqList
{SLDataType* array;//指向动态开辟的数组size_t size;//有效数据的个数size_t capacity;//容量
}SeqList;3.顺序表缺陷
顺序表缺陷
1动态增容有性能消耗。
2当头部插入数据时需要挪动数据
三、顺序表的代码实现
1.头文件
#pragma once#include stdio.h
#include stdlib.h
#include assert.htypedef int SLDataType;typedef struct SeqList
{SLDataType* s;//顺序表的名称头指针int size;//储存的有效个数int capacity;//整块空间的大小
}SL;//初始化
void SLInit(SL* ps);
//销毁
void SLDestory(SL* ps);
//打印
void SLPrint(SL* ps);//管理数据增删查改//尾插
void PushBack(SL* ps, SLDataType x);
//头插
void PushFront(SL* ps, SLDataType x);//尾删
void PopBack(SL* ps);
//头删
void PopFront(SL* ps);//判断是否扩容
void SLCheckCapacity(SL* ps);//在pos位置之前插入数据
void SLInsert(SL* ps, int pos, SLDataType x);2.函数文件
#define _CRT_SECURE_NO_WARNINGS 1
#include stdio.h
#include SeqList.h//初始化函数
void SLInit(SL* ps)
{assert(ps);//创建空间ps-s (SLDataType*)malloc(sizeof(SLDataType)*4);if (ps-s NULL){perror(malloc fail);exit(-1);}ps-size 0;ps-capacity 4;
}//销毁函数
void SLDestory(SL* ps)
{free(ps);ps-s NULL;ps-size ps-capacity 0;
}//打印函数
void SLPrint(SL* ps)
{int i 0;for (i 0; i ps-size; i){printf(%d , ps-s[i]);}printf(\n);
}//判断是否扩容
void SLCheckCapacity(SL* ps)
{assert(ps);if (ps-size ps-capacity){//需要扩容SLDataType* tmp (SLDataType*)realloc(ps-s, sizeof(SLDataType) * ps-capacity * 2);//扩大了原来容量的二倍。//SLDataType* tmp (SLDataType*)realloc(ps-s, 2 * ps-capacity);标准的错误写法//如果空间不够用要对一些元素进行扩容。我们扩容的标准就是为这些元素申请它 自身大小 整数倍 的空间所以说为什么要sizeof(数据类型)然后再乘以扩大的容量的倍数if (tmp NULL){perror(realloc fail);exit(-1);}ps-s tmp;ps-capacity * 2;}}//尾插
void PushBack(SL* ps, SLDataType x)
{//检查容量SLCheckCapacity(ps);ps-s[ps-size] x;ps-size;
}//尾删
void PopBack(SL* ps)
{assert(ps);ps-size--;}//头插利用一个end指针从后往前拷贝
void PushFront(SL* ps, SLDataType x)
{assert(ps);//检查容量SLCheckCapacity(ps);int end ps-size - 1;while (end 0){ps-s[end1] ps-s[end];end--;}ps-s[0] x;ps-size;
}//头删
void PopFront(SL* ps)
{assert(ps);int begin 0;while (begin ps-size-1){ps-s[begin] ps-s[begin 1];begin;}ps-size--;
}//在pos位置之前插入数据
void SLInsert(SL* ps, int pos, SLDataType x){assert(ps);assert(pos 0 pos ps-size);SLCheckCapacity( ps);int end ps-size - 1;while (end pos){ps-s[end1] ps-s[end];end--;}ps-s[pos] x;ps-size;
}3.测试文件
#define _CRT_SECURE_NO_WARNINGS 1
#include stdio.h
#include SeqList.hvoid test1()
{SL s1;SLInit(s1);PushFront(s1, 1);PushFront(s1, 2);PushFront(s1, 3);PushFront(s1, 4);PushFront(s1, 5);SLPrint(s1);PopFront(s1);PopFront(s1);PopFront(s1);SLPrint(s1);}void test2()
{SL s2;SLInit(s2);PushBack(s2,1);PushBack(s2,2);PushBack(s2,3);PushBack(s2,4);PushBack(s2,5);SLPrint(s2);PopBack(s2);PopBack(s2);PopBack(s2);SLPrint(s2);
}void test3()
{SL s2;SLInit(s2);PushBack(s2, 1);PushBack(s2, 2);PushBack(s2, 3);PushBack(s2, 4);PushBack(s2, 5);SLPrint(s2);SLInsert(s2, 3, 6);//在下标为3的数据之前插入一个6SLPrint(s2);
}int main()
{//test1();//测试头插头删//test2();//测试尾插 尾删test3();//测试在pos位置之前插入数据return 0;}四、顺序表的相关OJ题
1原地移除数组中所有的元素val
1.题目描述
1.原地移除数组中所有的元素val要求时间复杂度为O(N)空间复杂度为O(1)。OJ链接OJ链接
2.思路表述 3.代码实现:
int removeElement(int* nums, int numsSize, int val)
{int src0;int dst0;while(srcnumsSize){if(nums[src]!val){nums[dst]nums[src];}else{src;}}return dst;//返回的是新数组的长度因为最后一步出循环的时候dst已经了所以说直接返回dst就行了
}2删除有序数组中的重复项
1.题目描述 2.思路表述
还使用双下标法
3.代码实现
int removeDuplicates(int* nums, int numsSize)
{int dst1;int src0;while(dstnumsSize){if(nums[dst]!nums[src]){//nums[src]nums[dst];//这里的src一定要是前置,先然后再赋值。src;nums[src]nums[dst];dst;}else{dst;}}return src1;
}3合并两个有序数组
1.题目描述 2.思路表述
使用3下标法
3.代码实现
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{int end1m-1;int end2n-1;int endmn-1;while(end10end20){if(nums1[end1]nums2[end2]){nums1[end--]nums1[end1--];}else{nums1[end--]nums2[end2--];}}//因为用nums1的初始长度是mn所以不会担心数组大小不够用。//下面这个循环是针对:比如说nums1中的所有数字都插到自己数组后面了但是因为两个数组都是有序的所以我只需要把nums2中的全部数字依次放到nums1前面就行了。while(end20){nums1[end--]nums2[end2--];}
}好了今天的分享就到这里了 如果对你有帮助记得点赞关注哦 我的主页还有其他文章欢迎学习指点。关注我让我们一起学习一起成长吧
