线性表
线性表是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构。
- 常见的线性结构：顺序表、链表、栈、队列、字符串……
线性表在逻辑上是线性结构，也就是说是连续的一条直线，但是在物理结构上并不一定是连续的，线性表在物理存储时，通常以数组和链式结构的形式存储。
顺序表
顺序表从开始连续存储size个
顺序表时用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组数据存储，在数组上完成数组的增删查改。
顺序表一般分为：
1.静态顺序表
缺点：保存数据的数组较小不够使用，较大浪费
//静态顺序表 typedef int SLDateType; #define N 10 struct Seqlist { SLDateType a[N]; int size; };
2.动态顺序表
可以实现按需申请
- 此时，如果free出现问题，原因可能是指针为野指针，指针未从初始地址释放或者指针越界
//动态顺序表 typedef int SLDateType; struct Seqlist { SLDateType* a; int size; int capacity; };
- 使用顺序表完成增删查改
seqlist.h文件
#define _CRT_SECURE_NO_WARNINGS 1 //头文件 #include<stdio.h> #include<stdlib.h> #include<assert.h> 静态顺序表 //typedef int SLDateType; //#define N 10 //struct Seqlist //{ // SLDateType a[N]; // int size; //}; //动态顺序表 //定义类型 typedef int SLDataType; //设置初始容量 #define INIT_CAPACITY 5 typedef struct Seqlist { SLDataType* a; //有效数据个数 int size; //容量 int capacity; }SL; //初始化顺序表 void SLInit(SL* ps); //销毁顺序表 void SLDestroy(SL* ps); //打印顺序表 void SLPrint(SL* ps); //增 //后增 void SLPushBack(SL* ps, SLDataType X); //前增 void SLPushFront(SL* ps, SLDataType X); //插入 void SLInsert(SL* ps, int pos, SLDataType X); //删 //后删 void SLPopBack(SL* ps); //前删 void SLPopFront(SL* ps); //中间删除 void SLErase(SL* ps, int pos); //查 int SLFind(SL* ps, SLDataType X); //改 int SLChange(SL* ps, SLDataType X,SLDataType Y); //扩容 void SLCheckCap
seqlist.c文件
#include"seqlist.h" //初始化顺序表 void SLInit(SL* ps) { assert(ps->a); ps->a = (SLDataType*)malloc(sizeof(SLDataType) * INIT_CAPACITY); if (ps->a == NULL) { perror("Malloc fail"); } ps->size = 0; ps->capacity = INIT_CAPACITY; } //销毁顺序表 void SLDestroy(SL* ps) { assert(ps->a); free(ps->a); ps->a = NULL; ps->size = ps->capacity = 0; } //打印顺序表 void SLPrint(SL* ps) { assert(ps->a); int i = 0; for (i = 0; i < ps->size; i++) { printf("%d ",ps->a[i]); } printf("\n"); } //后增 void SLPushBack(SL* ps, SLDataType X) { assert(ps->a); SLCheckCapacity(ps); ps->a[ps->size] = X; ps->size++; } //后删 void SLPopBack(SL* ps) { assert(ps->a); assert(ps->size>0); /*if (ps->size == 0) { return; }*/ ps->size--; } //前增 void SLPushFront(SL* ps, SLDataType X) { assert(ps->a); SLCheckCapacity(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->a); int begin = 0; while (begin >= 0 && begin < ps->size) { ps->a[begin] = ps->a[begin + 1]; begin++; } ps->size--; } //中间插入 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->a[end + 1] = ps->a[end]; end--; } ps->a[pos] = X; ps->size++; } //中间删除 void SLErase(SL* ps, int pos) { assert(ps->a); assert(pos >= 0 && pos <= ps->size); int begin = pos; while (begin >= pos && begin <= ps->size) { ps->a[begin] = ps->a[begin + 1]; begin++; } ps->size--; } //查找 int SLFind(SL* ps, SLDataType X) { assert(ps->a); int i = 0; for (i = 0; i < ps->size; i++) { if (ps->a[i] == X) { return i; } } return -1; } //改 int SLChange(SL* ps, SLDataType X , SLDataType Y) { assert(ps->a); int i = 0; for (i = 0; i < ps->size; i++) { if (ps->a[i] == X) { ps->a[i] = Y; return 0; } } return -1; } //扩容 void SLCheckCapacity(SL* ps) { if (ps->size == ps->capacity) { SLDataType* p = (SLDataType*)realloc((void*)ps->a, ps->capacity * sizeof(SLDataType)*2); if (p == NULL) { printf("Realloc fail"); return; } ps->a = p; p = NULL; ps->capacity *= 2; } }
main.c文件
#include"seqlist.h" //测试顺序表 void TestSeqlist1() { //定义顺序表 SL s; //初始化顺序表 SLInit(&s); //后增 SLPushBack(&s,1); SLPushBack(&s, 2); SLPushBack(&s, 3); SLPushBack(&s, 4); //后删 SLPopBack(&s); //打印 SLPrint(&s); //前增 SLPushFront(&s, 10); SLPushFront(&s, 20); SLPushFront(&s, 40); //打印 SLPrint(&s); //前删 SLPopFront(&s); //打印 SLPrint(&s); //中间插入 SLInsert(&s, 1, 6); //打印 SLPrint(&s); //中间删除 SLErase(&s, 2); //打印 SLPrint(&s); //改 SLChange(&s, 2, 9); //打印 SLPrint(&s); //销毁顺序表 SLDestroy(&s); } int main(void) { //测试顺序表 TestSeqlist1(); return 0; }
链表
了解完顺序表之后，可以明显发现顺序的缺点：
- 中间与头部的插入删除，时间复杂度为O(N)
- 增容需要申请空间，拷贝数据，释放旧空间，会有不小的消耗
- 增容一般是呈2倍增长，会有一定的空间浪费
链表的概念
链表是一种物理存储的结构上非连续，非顺序的存储结构，数据元素的逻辑是通过链表中的指针链接次序实现的
注意：
1.链式结构在逻辑上是连续的，但是在物理上不一定连续。
2.现实中的结点一边拿都是从堆上申请出来的
3.从堆上申请的空间是按照一定的策略来分配的，俩次申请的空间可能连续，也可能不连续
链表的分类
- 链表的分类大致分为：
1.单向或者双向
2.带头或者不带头
3.循环或者非循环
其中最常用的是不带头单向非循环链表与带头双向循环链表
- 不带头单向非循环链表：
结构简单，一般不会单独用来存数据，实际中更多是作为其他数据结构的子结构，如哈希桶，图的邻接表等等
- 带头双向循环链表：
结构最复杂，一般用来单独存储数据，实际中使用的链表数据结构，都是双向循环链表
不带头单向非循环链表的实现
- slist.h文件
#define _CRT_SECURE_NO_WARNINGS 1 #pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> typedef int SLTDatatype; typedef struct SLinklistNode { SLTDatatype date; struct SLinklistNode* next; }SLTNode; //增加结点 SLTNode* SLTNewNode(SLTDatatype X); //打印 void SLTPrintf(SLTNode* phead); //头插 void SLTPushFront(SLTNode** pphead, SLTDatatype X); //头删 void SLTPopFront(SLTNode** pphead); //尾插 void SLTPushBack(SLTNode** pphead, SLTDatatype X); //尾删 void SLTPopBack(SLTNode** pphead); //查找 SLTNode* SLTFind(SLTNode* pphead,SLTDatatype X); //前插 void SLTInsertBefore(SLTNode** pphead, SLTNode* pos ,SLTDatatype X); //pos位置删 void SLTEraseBefore(SLTNode** pphead, SLTNode* pos); //后插 void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDatatype X); //后删 void SLTEraseAfter(SLTNode** pphead, SLTNode* pos); //销毁 void SLTDestory(SLTNode** pphead);
- slist.c文件
#include"slist.h" //打印 void SLTPrintf(SLTNode* phead) { SLTNode* cur = phead; while (cur) { printf("%d->", cur->date); cur = cur->next; } printf("NULL\n"); } //新增加一个结点 SLTNode* SLTNewNode( SLTDatatype X) { SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); if (newnode == NULL) { perror("malloc fail"); return NULL; } newnode->date = X; newnode->next = NULL; return newnode; } //头插 void SLTPushFront(SLTNode** pphead, SLTDatatype X) { //动态增加一个结点 SLTNode* newnode = SLTNewNode(X); newnode->next = *pphead; *pphead = newnode; } //头删 void SLTPopFront(SLTNode** pphead) { //温柔 /*if (*pphead == NULL) { return; }*/ //断言 assert(*pphead); SLTNode* first = *pphead; *pphead = first->next; free(first); first = NULL; } //尾删 void SLTPopBack(SLTNode** pphead) { if (*pphead == NULL) { return; } assert(*pphead); if ((*pphead)->next == NULL) { free(*pphead); *pphead = NULL; } else { SLTNode* tail = *pphead; while (tail->next->next != NULL) { tail = tail->next; } free(tail->next); tail->next = NULL; } } //尾增 void SLTPushBack(SLTNode** pphead, SLTDatatype X) { //新增一个结点 SLTNode* newnode = SLTNewNode(X); SLTNode* tail = *pphead; if (*pphead == NULL) { *pphead = newnode; } else { while (tail->next != NULL) { tail = tail->next; } tail->next = newnode; } } //查找 SLTNode* SLTFind(SLTNode* pphead,SLTDatatype X) { SLTNode* cur = pphead; while (cur) { if (cur->date == X) { return cur; } cur = cur->next; } return NULL; } //前插 void SLTInsertBefore(SLTNode** pphead, SLTNode* pos, SLTDatatype X) { assert(pos); assert(pphead); if (*pphead == pos) { SLTPushFront(pphead, X); } else { SLTNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } SLTNode* newnode = SLTNewNode(X); prev->next = newnode; newnode->next = pos; } } //pos位置删 void SLTEraseBefore(SLTNode** pphead, SLTNode* pos) { assert(pphead); assert(pos); assert(*pphead); if (*pphead == pos) { SLTPopFront(pphead); } SLTNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } prev->next = pos->next; free(pos); } //后插 void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDatatype X) { assert(pos); SLTNode* newnode = SLTNewNode(X); newnode->next = pos->next; pos->next = newnode; } //后删 void SLTEraseAfter(SLTNode** pphead, SLTNode* pos) { assert(pos); assert(pos->next); SLTNode* del = pos->next; pos->next = del->next; free(del); del = NULL; } //销毁 void SLTDestory(SLTNode** pphead) { SLTNode* cur = *pphead; while(cur) { SLTNode* tmp = cur->NEXT; free(cur); cur = tmp; } *pphead = NULL; }
带头双向循环链表的实现
Dlist.h文件
#define _CRT_SECURE_NO_WARNINGS 1 //带头双向循环链表的增删查改 #include<stdio.h> #include<stdlib.h> #include<assert.h> //定义类型 typedef int LTDataType; //定义结构体 typedef struct ListNode { LTDataType data; struct ListNode* prev; struct ListNode* next; }ListNode; //创建一个返回链表的头结点（哨兵） ListNode* ListCreate(); //双向链表的销毁 void ListDestory(ListNode* phead); //双向链表的打印 void ListPrintf(ListNode* phead); //创造一个newnode ListNode* ListNewNode(LTDataType x); //双向链表的尾插 void ListPushBack(ListNode* phead, LTDataType x); //双向链表的尾删 void ListPopBack(ListNode* phead); //双向链表的头插 void ListPushFront(ListNode* phead, LTDataType x); //双向链表的头删 void ListPopFront(ListNode* phead); //双向链表的查找 ListNode* ListFind(ListNode* phead, LTDataType x); //双向链表在pos前插入 void ListInsert(ListNode* phead, LTDataType x); //双向链表在pos删除 void ListErase(ListNode* pos);
Dlist.c文件
#include"DList.h" //创建一个返回链表的头结点（哨兵） ListNode* ListCreate() { ListNode* phead = ListNewNode(-1); phead->next = phead; phead->prev = phead; return phead; } //双向链表的销毁(需自行释放哨兵头) void ListDestory(ListNode* phead) { assert(phead); ListNode* cur = phead->next; while (cur != phead) { ListNode* tail = cur; cur = cur->next; free(tail); tail = NULL; } } //双向链表的打印 void ListPrintf(ListNode* phead) { assert(phead); ListNode* cur = phead->next; printf("->NULL->"); while (cur != phead) { printf("%d->", cur->data); cur = cur->next; } printf("\n"); } //创造一个newnode ListNode* ListNewNode(LTDataType x) { ListNode* newnode = (ListNode*)malloc(sizeof(ListNode)); if (newnode == NULL) { perror("malloc fail"); return NULL; } newnode->data = x; newnode->next = NULL; newnode->prev = NULL; return newnode; } //双向链表的尾插 void ListPushBack(ListNode* phead, LTDataType x) { assert(phead); ListNode* newnode = ListNewNode(x); newnode->next = phead; newnode->prev = phead->prev; phead->prev->next = newnode; phead->prev = newnode; } //双向链表的尾删 void ListPopBack(ListNode* phead) { assert(phead); assert(phead->next != phead); ListNode* tail = phead->prev; phead->prev = tail->prev; tail->prev->next = phead; free(tail); tail = NULL; } //双向链表的头插 void ListPushFront(ListNode* phead, LTDataType x) { assert(phead); ListNode* newnode = ListNewNode(x); newnode->next = phead->next; newnode->prev = phead; phead->next->prev = newnode; phead->next = newnode; } //双向链表的头删 void ListPopFront(ListNode* phead) { assert(phead); assert(phead->next != phead); ListNode* first = phead->next; phead->next = first->next; first->next->prev = phead; free(first); first = NULL; } //双向链表的查找 ListNode* ListFind(ListNode* phead, LTDataType x) { assert(phead); ListNode* cur = phead->next; while (cur != phead) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; } //双向链表在pos前插入 void ListInsert(ListNode* pos, LTDataType x) { assert(pos); ListNode* newnode = ListNewNode(x); ListNode* front = pos->prev; newnode->prev = front; newnode->next = pos; front->next = newnode; pos->prev = newnode; } //双向链表在pos删除(自行释放指针) void ListErase(ListNode* pos) { assert(pos); pos->prev->next = pos->next; pos->next->prev = pos->prev; free(pos); }
顺序表与链表的区别
| 不同点 | 顺序表 | 链表 |
| 存储空间上 | 物理上连续 | 逻辑上连续，物理上不一定连续 |
| 随机访问 | 支持：O(1) | 不支持：O(N) |
| 任意位置插入或者删除元素 | 可能需要移动元素，效率低O(N) | 只需要修改指针指向 |
| 插入 | 动态顺序表，空间不够需要扩容 | 没有容量的概念 |
| 应用场景 | 元素高效访问，频繁访问 | 任意位置插入和删除频繁 |
| 缓存利用率 | 高 | 低 |
