次序表和链表知识点
1 次序表次序表是指用一段物理所在一连的空间去存储数据的线性布局。
次序表有两种：静态次序表，动态次序表。
https://i-blog.csdnimg.cn/direct/1667f033ce32422fabb2fb112fe27a59.png
1.1 静态次序表布局体定义
typedef int ElemDataSL;
typedef struct SequeList {
ElemDataSL arr;
int size;
}SL; 静态次序表在创建布局体的时候就已经把容量固定，后期空间不敷，不允许增长新空间，以是并不方便实际使用。
例子：通讯录（C语言实现）-CSDN博客
1.2 动态次序表布局体定义
typedef int ElemDataSL;
typedef struct SequeList {
ElemDataSL* arr;
int size;
int capatity;
}SL; 动态次序表在创建布局体的时候定义了arr的指针作为一段一连内存空间的首所在，如果有需要可以用realloc开辟新空间进行扩容处理。
1.2.1 接口声明
//初始化
void InitSequeList(SL* s);
//尾插
void SequeListPushBack(SL* s,ElemDataSL num);
//尾删
void SequeListPopBack(SL* s);
//头插
void SequeListPushFront(SL* s, ElemDataSL num);
//头删
void SequeListPopFront(SL* s);
//pos处插
void SequeListPushInsert(SL* s,ElemDataSL num,int pos);
//pos处删
void SequeListPopInsert(SL* s,int pos);
//显示
void SequeListShowData(SL* s);
// 顺序表删除pos位置的值
void SequeListErase(SL*s, size_t pos);
// 顺序表销毁
void SequeListDestory(SL* s);
1.2.2 初始化
//初始化
void InitSequeList(SL* s) {
assert(s);
s->arr = (ElemDataSL*)malloc(DefaultData * sizeof(ElemDataSL));
s->capatity = DefaultData;
s->size = 0;
} 1.2.3 尾插
//尾插
void SequeListPushBack(SL* s,ElemDataSL num) {
assert(s);
AddCapatity(s);
s->arr = num;
s->size++;
} 1.2.4 尾删
//尾删
void SequeListPopBack(SL* s)
{
assert(s);
s->size--;
} 1.2.5 头插
//头插
void SequeListPushFront(SL* s,ElemDataSL num) {
AddCapatity(s);
for (int i = s->size-1; i >=0; i--)
{
s->arr = s->arr;
}
s->arr = num;
s->size++;
} 1.2.6 头删
//头删
void SequeListPopFront(SL* s)
{
for (int i = 0; i <= s->size - 1; i++)
{
s->arr = s->arr;
}
s->size--;
} 1.2.7 中间插入
//pos处插
void SequeListPushInsert(SL* s,ElemDataSL num,int pos)
{
AddCapatity(s);
for (int i = s->size - 1; i >= pos-1; i--)
{
s->arr = s->arr;
}
s->arr = num;
s->size++;
} 1.2.8 中间删除
//pos处删
void SequeListPopInsert(SL* s, int pos) {
for (int i = pos-1; i <= s->size - 1; i++)
{
s->arr = s->arr;
}
s->size--;
} 1.2.9 打印次序表
//显示
void SequeListShowData(SL* s)
{
assert(s);
for (int i = 0; i < s->size; i++)
{
printf("%d ", s->arr);
}
printf("\n");
} 1.3 次序表烧毁
// 顺序表销毁
void SequeListDestory(SL* s) {
free(s->arr);
s->arr = NULL;
} 次序表优点：可以使用随机访问。
缺点：开辟空间可能会导致空间浪费，增删改查的时间复杂度为O（N）。
2 链表
链表是一种物理存储布局上非一连、非次序的存储布局，数据元素的逻辑次序是通过链表中的指针链接次序实现的 。
https://i-blog.csdnimg.cn/direct/360772849e424e618ddaac525e377af1.png
留意：
1、链式布局在逻辑上是一连的，但在物理上非一连。
2、在堆上开辟空间。
3、在堆上申请空间，按照一定战略进行的，两次开辟的空间可能一连也可能不一连。
2.1 单链表
https://i-blog.csdnimg.cn/direct/7fc3a913a3cd466292abe2cab34f9816.png
无头单向非循环链表：布局简单，一般不会单独用来存数据。实际中更多是作为其他数据布局的子布局，如哈希桶、图的邻接表等等。
2.2 接口声明
typedef int SLDATATYPE;
typedef struct SListNode {
int data;
struct SListNode* next;
}SListNode;
//尾插
void SListPushBack(SListNode** pphead, SLDATATYPE num);
//尾删
void SListPopBack(SListNode* phead);
//头插
void SListPushFront(SListNode** pphead, SLDATATYPE num);
//头删
void SListPopFront(SListNode* phead);
//查找
SListNode* SListFind(SListNode* phead, SLDATATYPE num);
//中间后插
void SListInsertAfter(SListNode* pos, SLDATATYPE num);
//中间删
void SListEraseAfter(SListNode* pos);
//打印
void SListPrint(SListNode* phead);
//销毁链表
void SListDistory(SListNode** phead); 2.3 尾插
//尾插
void SListPushBack(SListNode* *pphead, SLDATATYPE num) {
SListNode* NewNode = BuySListNode(num);
if (*pphead == NULL)
{
*pphead= NewNode;
}
else
{ SListNode* tail = *pphead;
while (tail->next!=NULL)
{
tail = tail->next;
}
tail->next= NewNode;
}
} 2.4 尾删
//尾删
void SListPopBack(SListNode** phead)
{
SListNode* tail = *phead;
SListNode* prev = tail;
if (*phead == NULL)
{
return;
}
else if ((*phead)->next == NULL)
{
free(*phead);
*phead = NULL;
}
else
{
while (tail->next != NULL)
{
prev = tail;
tail = tail->next;
}
free(tail);
prev->next = NULL;
}
} 2.5 头插
//头插
void SListPushFront(SListNode** pphead, SLDATATYPE num)
{
SListNode* newNode = BuySListNode(num);
if ((*pphead) == NULL)
{
*pphead = newNode;
}
else
{
newNode->next = *pphead;
}
*pphead = newNode;
} 2.6 头删
//头删
void SListPopFront(SListNode* *pphead)
{
SListNode* head = *pphead;
if (head == NULL)
{
return;
}
else if (head->next == NULL)
{
*pphead = NULL;
}
else
{
(*pphead) = (*pphead)->next;
free(head);
}
} 2.7 查找
SListNode* SListFind(SListNode* phead, SLDATATYPE num) {
SListNode* ptr = phead;
while (ptr)
{
if (ptr->data == num)
{
printf("%d找到了!\n",ptr->data);
returnptr;
}
ptr = ptr->next;
}
printf("%d没找到!\n",num);
return NULL;
} 2.8 中间后插
void SListInsertAfter(SListNode* *pos, SLDATATYPE num)
{
SListNode* newNode = BuySListNode(num);
newNode->next = (*pos)->next;
(*pos)->next = newNode;
} 2.9 中间后删
void SListEraseAfter(SListNode* pos)
{
assert(pos);
assert(pos->next);
SListNode* next = pos->next;
pos->next = next->next;
free(next);
} 3 打印
//打印
void SListPrint(SListNode* phead)
{
SListNode* cur = phead;
while (cur)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
} 3.1 烧毁链表
void SListDistory(SListNode** phead)
{
assert(*phead);
SListNode* next = (*phead)->next;
while (next)
{
free(*phead);
*phead = next;
next = next->next;
}
free(*phead);
*phead = NULL;
} 单链表优点：需要增长多少个元素就开辟多少空间不会导致空间浪费，插入时间复杂度低。
缺点：不能随机访问，只能依次往后访问，无法实现从后往前。
2.2 双链表
https://i-blog.csdnimg.cn/direct/ae3b239fde3e4d81acf0c1df13aa9741.png
头节点不存储有效数据。
2.2.1 接口声明
typedef int ListData;
typedef struct ListNode
{
ListData data;
struct ListNode* next;
struct ListNode* prev;
}ListNode;
//链表创建
ListNode* ListCreate();
//尾插
void ListPushBack(ListNode* phead, ListData x);
//尾删
void ListPopBack(ListNode* phead);
//头插
void ListPushFront(ListNode* phead, ListData x);
//头删
void ListPopFront(ListNode* phead);
//查找
ListNode* ListFind(ListNode* phead, ListData x);
//中间插
void ListInsert(ListNode* pos,ListData x);
//中间删
void ListErase(ListNode* pos);
//显示
void ListPrint(ListNode* phead);
//清空链表
void ListClear(ListNode** phead);
//销毁链表
void ListDestory(ListNode* phead); 2.2.2 创建新节点
ListNode* BuyListNode(ListData x)
{
ListNode* node = (ListNode*)malloc(sizeof(ListNode));
node->data = x;
node->next = NULL;
node->prev = NULL;
return node;
} 2.2.3 双链表创建
ListNode* ListCreate() {
ListNode* phead = BuyListNode(0);
phead->next = phead;
phead->prev = phead;
return phead;
} 2.2.4 尾插
//尾插
void ListPushBack(ListNode* phead, ListData x)
{
assert(phead);
ListNode* tail = phead->prev;
ListNode* newNode = BuyListNode(x);
tail->next = newNode;
newNode->prev = tail;
newNode->next = phead;
phead->prev = newNode;
} 2.2.5 尾删
//尾删
void ListPopBack(ListNode* phead)
{
assert(phead->next != phead);
/*ListNode* tail = phead->prev;
ListNode* tailPrev = tail->prev;
tailPrev->next = phead;
phead->prev = tailPrev;*/
ListErase(phead->prev);
} 2.2.6 头插
//头插
void ListPushFront(ListNode* phead, ListData x)
{
ListNode* newNode = BuyListNode(x);
ListNode* pheadNext = phead->next;
phead->next = newNode;
newNode->prev = phead;
newNode->next = pheadNext;
pheadNext->prev = newNode;
} 2.2.7 头删
//头删
void ListPopFront(ListNode* phead)
{
ListNode* pheadNext = phead->next;
phead->next = pheadNext->next;
pheadNext->next->prev = phead;
free(pheadNext);
} 2.2.8 查找
//查找
ListNode* ListFind(ListNode* phead, ListData x)
{
ListNode* pos = NULL;
ListNode* cur = phead->next;
while (cur != phead)
{
if (cur->data == x)
{
pos = cur;
break;
}
cur = cur->next;
}
return pos;
} 2.2.9 中间插
//中间插
void ListInsert(ListNode* pos, ListData x)
{
assert(pos);
/*ListNode* newNode = BuyListNode(x);
ListNode* posPrev = pos->prev;
newNode->next = pos;
pos->prev = newNode;
posPrev->next = newNode;
newNode->prev = posPrev;*/
ListPushFront(pos->prev, x);
} 2.3 中间删
//中间删
void ListErase(ListNode* pos)
{
ListNode* posPrev = pos->prev;
ListNode* posNext = pos->next;
posPrev->next = posNext;
posNext->prev = posPrev;
free(pos);
} 2.3.1 表现
//显示
void ListPrint(ListNode* phead)
{
assert(phead);
ListNode* tail = phead->next;
while (tail != phead)
{
printf("%d ", tail->data);
tail = tail->next;
}
printf("\n");
} 2.3.2 清空链表
void ListClear(ListNode** phead)
{
ListNode* cur = (*phead)->next;
while (cur != *phead)
{
ListNode* next = cur->next;
free(cur);
cur = next;
}
(*phead)->next = *phead;
(*phead)->prev = *phead;
} 2.3.3 烧毁链表
//销毁链表
void ListDestory(ListNode** phead)
{
ListClear(phead);
free(*phead);
}
双链表优点：插入时间复杂度比单链表更低，可以前驱访问。
缺点：不能随机访问。
3 次序表和链表的区别
差异点次序表链表存储空间上物理上一定一连逻辑上一连，物理上不一定一连随机访问支持O（1）不支持O（N）任意位置插入或者删除元素可能需要搬移元素，效率低O（N）只需修改指针指向插入动态次序表，空间不敷时需要扩容没有容量概念应用场景元素高效存储+频繁访问任意位置插入和删除频繁缓存使用率高低
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]