[数据结构]顺序表详解

目录

一.线性表

二.顺序表

2.1概念及结构

1. 静态顺序表：使用定长数组存储元素。

2. 动态顺序表：使用动态开辟的数组存储。

2.1按需申请 

2.2 接口实现：增删查改

SeqList.h:

SeqList.c:

test.c

---

一.线性表

线性表 （ linear list ） 是 n 个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使

用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串 ...

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，

线性表在物理上存储时，通常以数组和链式结构的形式存储。

二.顺序表

2.1概念及结构

顺序表是用一段 物理地址连续 的存储单元依次存储数据元素的线性结构，一般情况下采用数组存

储。在数组上完成数据的增删查改。

1. 静态顺序表：使用定长数组存储元素。

开少了不够用开多了浪费

#define N 100
typedef int SLDateType;
struct Seqlist
{SLDateType a[N];int size;
};

2. 动态顺序表：使用动态开辟的数组存储。

2.1按需申请 

typedef int SLDateType;
struct Seqlist
{SLDateType *a;int size;//有效数据个数  这个个数跟空间大小一样的时候就扩容int capacity;//空间的容量
};

2.2 接口实现：增删查改

头插尾插的时间复杂度都为o(1)

头删尾删的时间复杂度都为o(n)

SeqList.h:

#ifndef SEQLIST_H
#define SEQLIST_H
#include <errno.h>
#include <stdlib.h>
#include<assert.h>
#include<stdio.h>
#define INIT_CAPACITY 10
typedef int SLDataType;
typedef struct Seqlist
{SLDataType* a;int size;       // 有效数据个数int capacity;  // 空间的容量
} SL;
//增删改查
void SeqInit(SL* s);  // 初始化
void SLDestroy(SL* ps);//销毁
void SLPushBack(SL* ps, SLDataType x);//插入 尾插
void SLPopBack(SL* ps);//删除 尾删
void SLPushFront(SL* ps, SLDataType x);//插入 头插
void SLPopFront(SL* ps);//删除 尾删
void SLInsert(SL* ps, int pos, SLDataType x);//在某个位置插入
void SLErase(SL* ps, int pos);//在某个位置删除
int SLFind(SL* ps, SLDataType x);//查找x元素的下标
void SLEtdCapacity(SL* ps);//扩容
void SLPrint(SL* ps);//打印
#endif // SEQLIST_H

SeqList.c:

#include "SeqList.h"
//打印
void SLPrint(SL* ps)
{for (int i = 0; i < ps->size; i++){printf("%d ", ps->a[i]);}
}
//扩容
void SLEtdCapacity(SL* ps)
{//如果空间不够，扩容if (ps->size == ps->capacity){SLDataType* tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType) *  ps->capacity);if (tmp == NULL){perror("realloc fail");return;}ps->capacity *= 2;ps->a = tmp;}
}
//初始化
void SeqInit(SL* s)
{s->a = (SLDataType*)malloc(sizeof(SLDataType) * INIT_CAPACITY);if (s->a == NULL){perror("malloc fail");return;}s->size = 0;s->capacity = INIT_CAPACITY;
}
//销毁
void SLDestroy(SL* ps)
{free(ps->a);ps->a = NULL;ps->capacity = ps -> size = 0;
}
//尾插
void SLPushBack(SL* ps, SLDataType x)
{SLEtdCapacity(&ps);//扩容ps->a[ps -> size] = x;ps->size++;
}
//尾删
void SLPopBack(SL* ps)
{assert(ps->size>0);ps->size--;
}
//头插
void SLPushFront(SL* ps, SLDataType x)
{assert(ps);SLEtdCapacity(&ps);//扩容int end = ps->size - 1;while (end >= 0){ps->a[end + 1] = ps->a[end];--end;}ps->a[0] = x;ps->size++;
}
//头删
void SLPopFront(SL* ps)//删除 头删
{assert(ps);assert(ps->size > 0);//表不能为空int begin = 1;while (begin < ps->size){ps->a[begin - 1] = ps->a[begin];begin++;}ps->size--;
}
//在某个位置插入
void SLInsert(SL* ps, int pos, SLDataType x)
{assert(ps);assert(pos >= 0 && pos <= ps->size);//如果pos等于size相当于尾插SLEtdCapacity(&ps);int end = ps->size - 1;while (end >= pos)//类似于头插{ps->a[end + 1] = ps->a[end];end--;}ps->a[pos] = x;ps->size++;
}
//在某个位置删除
void SLErase(SL* ps, int pos)
{assert(ps);assert(pos >= 0 && pos < ps->size);//删除的时候不能等于sizeint begin = pos + 1;while (begin < ps->size){ps->a[begin-1] = ps->a[begin];begin++;}ps->size--;
}
//查找x元素的下标
int SLFind(SL* ps, SLDataType x)
{assert(ps);for (int i = 0; i < ps->size; i++){if (ps->a[i] == x){return i;}}return -1;
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "SeqList.h"
void TestSeqList1()
{SL s;SeqInit(&s);SLPushFront(&s, 1);SLPushFront(&s, 2);SLPushFront(&s, 3);SLPrint(&s);printf("\n");SLPopFront(&s);SLPopFront(&s);SLPrint(&s);
}
int main()
{TestSeqList1();return 0;
}