网页设计培训学些什么_企业用什么邮箱比较好_整站seo服务_广告接单网站

顺序表代码：SData/SqList/SeqList.h · Hera_Yc/bit_C_学习 - 码云 - 开源中国

链表相关代码：SData/ListLink/main.c · Hera_Yc/bit_C_学习 - 码云 - 开源中国

本文主要讲解的是线性表（逻辑线性），对于非线性表不做补充。

线性表

线性表是n个具有相同类型的数据元素的有限序列。

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

 顺序表

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

• 静态顺序表：使用定长数组存储元素。
• 动态顺序表：动态顺序表能够增容，对空间的利用率必静态数组高。

顺序表接口实现：

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>//顺序表,有效数据中必须是连续存储
// 
//静态数据表(固定大小)
// 把数组简单封装一下
//
// 动态数据表
// malloc开辟内存
//typedef int SLDataType;
#define N 10
#define INC_N  Ntypedef struct SeqList
{SLDataType* arr; int size;		//有效数据的个数int capacity;	//容量
}SL,SeqList;void SeqListInit(SL* s);//尾插
void SeqListPushBack( SeqList* ps, SLDataType x);
//尾删
void SeqListPopBack( SeqList* ps);
//头插
void SeqListPushFront( SeqList* ps, SLDataType x);
//头删
void SeqListPopFront( SeqList* ps);//任意位置的插入删除
void SeqListInsert(SeqList* ps, int pos, SLDataType x);
void SeqListErase(SeqList* ps, int pos);void SeqListPrint(const SL* ps);//查找
int SeqListFind(SL* ps, SLDataType x);//...
/*
1.二分查找
2.排序
诸多操作
*/

顺序表的特性 

1.  可动态增长数组。
2. 数组在数组中存储时必须是连续的。

缺点：

1. 中间或者头部的插入删除很慢，需要挪动数据。时间复杂度是O(N)。
2. 空间不够时，增容会有一定的消耗和空间浪费。（空间碎片化）。

优点：

1. 顺序表支持随机访问。
2. 和链式存储结构相比，缓存命中率比较高。（物理空间连续导致的）。

---

链表

        链表是一种物理上非连续、非顺序，逻辑上是连续的存储结构。链表其实就是针对顺序表的缺点来设计的，补足的就是顺序表的缺点。

结点

结点的定义：

typedef int SListData;//结点
typedef struct SListNode
{SListData data;struct SListNode* next;
}SL;

 链表的分类