线性表(linear list)是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构,常见的线性表:顺序表、链表、栈、队列、字符串…
线性表在逻辑上是线性结构,也就说是连续的一条直线。但是在物理结构上并不一定是连续的,线性表在物理上存储时,通常以数组和链式结构的形式存储。
顺序表:本质是数组,动态增长,并且要求里面存储的数据必须是从左到右连续的。
顺序表的缺陷:1、动态增容有性能消耗
2、需要头部插入数据,需要挪动数据
3、逻辑结构和物理结构不一致
#pragma once
#include<stdio.h>
typedef int SeqDataType;
struct SeqList
{
SeqDataType *a;//指向动态开辟的数组
int size;//有效数据的个数
int capacity;//容量的大小
};
void SeqListInit(SeqList seq)
{
seq.a = NULL;
seq.size = seq.capacity = 0;
}
void TestSeqList1()
{
SeqList s;
SeqListInt(&s);
}
int main()
{
TestSeqList1();
return 0;
}
在这里我们传的是结构体的地址否则无法初始化。
void SeqListInit(SeqList* pq)
{
pq->a = NULL;
pq->size = pq->capacity = 0;
}
void SeqListDestory(SeqList* pq)
{
assert(pq);
free(pq->a);
pq->a = NULL;
pq->capacity = pq->size = 0;
}
尾插
void SeqListPushBack(SeqList* pq, SeqDataType x)
{
assert(pq);
//满了,需要增容
if (pq->size == pq->capacity)
{
int newcapacity = pq->capacity==0 ? 4:pq->capacity * 2;
SeqDataType* newA = relloc(pq->a, sizeof(SeqDataType)*newcapacity);
if (newA == NULL)
{
printf("realloc fail\n");
exit(-1);
}
pq->a = newA;
pq->capacity = newcapacity;
}
pq->a[pq->size] = x;
pq->size++;
}
插入数据的时候我们要先判断容量是否够用,不够用的话要动态开辟空间。
头插
void SeqListPushFront(SeqList* pq, SeqDataType x)
{
int end = pq->size - 1;
while (end >= 0)
{
pq->a[end + 1] = pq->a[end];
--end;
}
pq->a[0] = x;
pq->size++;
}
要从头部插入数据,就要先把数据往后移,否则会覆盖后面的数据。
头删
void SeqListPopFront(SeqList* pq)
{
assert(pq);
assert(pq->size > 0);
int begin = 0;
while (begin < pq->size - 1)
{
pq->a[begin] = pq->a[begin+1];
}
}
要从头部删除数据,只能用后面的数将前面的数替换形成头删
从中间插入
void SeqListInsert(SeqList*pq, int pos, SeqDataType x)
{
assert(pq);
assert(pos >= 0 && pos < pq->size);
int end = pq->size - 1;
while (end>=pos)
{
pq->a[end + 1] = pq->a[end];
--end;
}
pq->a[pos] = x;
pq->size++;
}
注意容量空间,要进行扩容。
从中间删除
void SeqListErase(struct SeqList* pq, int pos)
{
assert(pq);
assert(pos >= 0 && pos < pq->size);
int begin = pos;
while (begin <= pq->size - 1)
{
pq->a[begin] = pq->a[begin + 1];
++begin;
}
pq->size--;
}
不少Windows 10用户之前都抱怨一个问题,那就是系统的屏幕出现了渲染问题,而微...
console.log ,作为一个前端开发者,可能每天都会用它来分析调试,但这个简单函...
前言 aop即是面向切面编程,众多Aop框架里Castle是最为人所知的,另外还有死去的...
本文转载自微信公众号「Linux开发那些事儿」,作者 LinuxThings 。转载本文请联...
互联网业务往往使用MySQL数据库作为后台存储,存储引擎使用InnoDB。我们针对互联...
一、Postman背景介绍 用户在开发或者调试网络程序或者是网页B/S模式的程序的时候...
2月26日消息 众所周知,Windows 10 的安全更新和其他重要累计更新通常是在同一天...
简介 “ 大家好我是帅哥欢迎来到帅哥的程序人生我会把经历分享出来助你了解圈内...
继 Australis 和 Photon 之后,Mozilla 现又酝酿为 Firefox 带来名为Proton的全...
开发过程中,我们经常会遇到代码回滚的情况。正常人都知道,git 回滚有两大宝: ...