目录
一、顺序表的概念
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。一般分为动态顺序表和静态顺序表，动态顺序表使用动态开辟的数组存储，静态顺序表使用定长数组存储。
静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以我们实现动态顺序表。
?在头文件声明：
typedef int SLDataType;
// 顺序表的动态存储
typedef struct SeqList
{
SLDataType* a; // 指向动态开辟的数组
int size ; // 有效数据个数
int capicity ; // 容量空间的大小
}SL;
// 基本增删查改接口
// 顺序表初始化
void SeqListInit(SL* ps);
// 检查空间，如果满了，进行增容
void CheckCapacity(SL* ps);
// 顺序表尾插
void SeqListPushBack(SL* ps, SLDataType x);
// 顺序表尾删
void SeqListPopBack(SL* ps);
// 顺序表头插
void SeqListPushFront(SL* ps, SLDataType x);
// 顺序表头删
void SeqListPopFront(SL* ps);
// 顺序表查找
int SeqListFind(SL* ps, SLDataType x);
// 顺序表在pos位置插入x
void SeqListInsert(SL* ps, int pos, SLDataType x);
// 顺序表删除pos位置的值
void SeqListErase(SL* ps, int pos);
// 顺序表销毁
void SeqListDestroy(SL* ps);
// 顺序表打印
void SeqListPrint(SL* ps);
动态顺序表实现
#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"
//顺序表初始化
void SeqListInit(SL* ps)
{
assert(ps);
ps->a = NULL;
ps->capacity = ps->size = 0;
}
//顺序表打印
void SeqListPrint(SL* ps)
{
assert(ps);
for (int i = 0; i <ps->size ; i++)
{
printf("%d ", ps->a[i]);
}
printf("\n");
}
//顺序表销毁
void SeqListDestroy(SL* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->capacity = ps->size = 0;
}
//检查是否需要增容
void SeqListCheckCapacity(SL*ps)
{
assert(ps);
if (ps->capacity == ps->size)
{
//顺序表刚开始为空和插入数据插满了都需要判断
//如果为空就给capacity给4个空间，插满就给原来空间的2倍，在realloc时就方便开辟
int newcapacity = ps->capacity == 0 ? 4:ps->capacity * 2;
//第一次realloc，ps->a是为空的,realloc可以当做malloc使用
SLDataType *new = realloc(ps->a, sizeof(SLDataType)*newcapacity);
if (new == NULL)
{
printf("realloc fail\n");
exit(-1);
}
ps->a = new;
ps->capacity = newcapacity;
}
}
//顺序表尾插
void SeqListPushBack(SL*ps, SLDataType x)
{
assert(ps);
SeqListCheckCapacity(ps);//检查是否扩容
ps->a[ps->size] = x;
ps->size++;
}
//顺序表尾删
void SeqListPopBack(SL*ps)
{
assert(ps);
ps->size--;
}
//顺序表头插
void SeqListPushFront(SL*ps, SLDataType x)
{
assert(ps);
SeqListCheckCapacity(ps);//检查是否扩容
int tail = ps->size - 1;
while (tail >= 0)
{
ps->a[tail + 1] = ps->a[tail];
tail--;
}
ps->a[0] = x;
ps->size++;
}
//顺序表头删
void SeqListPopFront(SL*ps)
{
assert(ps);
assert(ps->size > 0);
int str = 0;
if (ps->size == 1)
ps->size--;
else
{
while (str < ps->size)
{
ps->a[str] = ps->a[str + 1];
str++;
}
ps->size--;
}
}
//查找元素x
int SeqListFind(SL*ps, SLDataType x)
{
assert(ps);
int i=0;
if (ps->size == 0)
return -1;
for ( i = 0; i <ps->size ; i++)
{
if (ps->a[i] == x)
return i;
}
return -1;
}
//指定下标位置插入
void SeqListInsert(SL*ps, int pos, SLDataType x)
{
assert(ps);
assert(pos>=0&&pos<ps->size);//有效位置插入
SeqListCheckCapacity(ps);//检查是否扩容
int tail = ps->size - 1;
while (tail>=pos)
{
ps->a[tail + 1] = ps->a[tail];
tail--;
}
ps->a[pos] = x;
ps->size++;
}
//指定位置删除
void SeqListErase(SL*ps, int pos)
{
assert(ps);
assert(pos >= 0 && pos<ps->size);//有效位置删除
int ptr = pos;
while (ptr<ps->size)
{
ps->a[ptr] = ps->a[ptr + 1];
ptr++;
}
ps->size--;
}代码测试：
#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"
int main()
{
SL sl;
SeqListInit(&sl);
SeqListPushBack(&sl, 1);
SeqListPushBack(&sl, 2);
SeqListPushBack(&sl, 3);
SeqListPushBack(&sl, 4);
SeqListPushBack(&sl, 5);
printf("尾插5个数：");
SeqListPrint(&sl);
SeqListPushFront(&sl, 10);
SeqListPushFront(&sl, 20);
SeqListPushFront(&sl, 30);
printf("头插3个数：");
SeqListPrint(&sl);
SeqListPopFront(&sl);
SeqListPopFront(&sl);
SeqListPopFront(&sl);
printf("头删3个数：");
SeqListPrint(&sl);
SeqListPopBack(&sl);
SeqListPopBack(&sl);
printf("尾删2个数：");
SeqListPrint(&sl);
int pos=SeqListFind(&sl, 3);
SeqListInsert(&sl, pos, 2);
printf("在数值为3的下标插入：");
SeqListPrint(&sl);
SeqListErase(&sl, pos);
printf("删除下标为pos的值：");
SeqListPrint(&sl);
SeqListDestroy(&sl);
return 0;
}? ? ??
———————————————————————————————————————————
?二、链表的概念
链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。我们要注意：
1.链式结构在逻辑上(想象出来的)是连续的，在物理上(计算机内存中)却不一定连续? ? ?
?2.节点一般都是堆上申请的
?实际中链表的结构非常多样，但是我们最常用还是两种结构：
1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。
?2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。
单向链表在头文件的声明：
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLDataType;
typedef struct SListNode
{
SLDataType data;
struct SListNode* next;
}SLTNode;
//链表打印
void SListPrintf(SLTNode* phead);
//链表销毁
void SListDestroy(SLTNode**phead);
//链表尾插
void SListPushBack(SLTNode** phead, SLDataType x);
//链表尾删
void SListPopBack(SLTNode** phead);
//链表头插
void SListPushFront(SLTNode** phead, SLDataType x);
//链表头删
void SListPopFront(SLTNode** phead);
//链表查找
SLTNode*SListFind(SLTNode**phead, SLDataType x);
//链表pos位置前面的插入
void SListInsert(SLTNode**phead, SLTNode* pos, SLDataType x);
//链表pos位置的删除
void SListErase(SLTNode**phead, SLTNode* pos);1、无头单向链表的实现
#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"
//链表打印
void SListPrintf(SLTNode* phead)
{
SLTNode*str = phead;
while (str != NULL)
{
printf("%d->", str->data);
str = str->next;
}
printf("NULL\n");
}
//链表销毁
void SListDestroy(SLTNode**phead)
{
SLTNode*str = *phead;
while (str!=NULL)
{
free(*phead);
*phead = str->next;
str = str->next;
}
}
//链表尾插
void SListPushBack(SLTNode** phead, SLDataType x)
{
SLTNode*new = (SLTNode*)malloc(sizeof(SLTNode));
new->data = x;
new->next = NULL;
if (*phead == NULL)
*phead = new;
else
{
SLTNode*str = *phead;
while (str->next!=NULL)
{
str = str->next;
}
str->next = new;
}
}
//链表尾删
void SListPopBack(SLTNode** phead)
{
assert(*phead);
SLTNode*str = *phead;
SLTNode*prev = NULL;
while (str->next != NULL)
{
prev = str;
str = str->next;
}
if (prev!=NULL)
prev->next = str->next;
free(str);
}
//链表头插
void SListPushFront(SLTNode** phead, SLDataType x)
{
SLTNode*str = *phead;
SLTNode*new = (SLTNode*)malloc(sizeof(SLTNode));
new->data = x;
new->next = NULL;
*phead = new;
new->next = str;
}
//链表头删
void SListPopFront(SLTNode** phead)
{
assert(*phead);
SLTNode*str = (*phead)->next;
free(*phead);
*phead = str;
}
//链表查找
SLTNode*SListFind(SLTNode**phead, SLDataType x)
{
SLTNode*str = *phead;
while (str != NULL)
{
if (str->data == x)
return str;
str = str->next;
}
return NULL;
}
//链表pos位置的前面插入
void SListInsert(SLTNode**phead, SLTNode* pos, SLDataType x)
{
assert(pos);
assert(*phead);
SLTNode*prev = *phead;
SLTNode*cur = *phead;
while (cur->next != pos)
{
prev = cur;
cur = cur->next;
}
prev = cur;
SLTNode*tmp = (SLTNode*)malloc(sizeof(SLTNode));
tmp->data = x;
tmp->next = NULL;
prev->next = tmp;
tmp->next = pos;
}
//链表pos位置的删除
void SListErase(SLTNode**phead, SLTNode* pos)
{
assert(pos != NULL);
SLTNode*prev = *phead;
SLTNode*cur = *phead;
if (cur->next == NULL)
{
//只剩一个节点的时候，pos和*phead指向的是同一个节点
//所以free(pos)之后要把两个指针都置空不然就会有野指针
free(pos);
pos = NULL;
*phead = NULL;
}
else
{
while (cur->next != pos)
{
prev = cur;
cur = cur->next;
}
prev = cur;
prev->next = pos->next;
free(pos);
pos = NULL;
}
}代码测试：
#include"List.h"
void test1()
{
SLTNode*plist = NULL;
SListPushBack(&plist, 1);
SListPushBack(&plist, 2);
SListPushBack(&plist, 3);
SListPushBack(&plist, 4);
SListPushBack(&plist, 5);
printf("尾插5个数：");
SListPrintf(plist);
SListPushFront(&plist, 10);
SListPushFront(&plist, 20);
SListPushFront(&plist, 30);
printf("头插3个数：");
SListPrintf(plist);
SLTNode*pos=SListFind(&plist, 4);
SListInsert(&plist, pos, 40);
printf("pos位置>:4前面插入40: ");
SListPrintf(plist);
pos = SListFind(&plist, 40);
SListErase(&plist, pos);
printf("pos位置删除>:删除40： ");
SListPrintf(plist);
SListDestroy(&plist);
}
void test2()
{
//测试只有一个节点的删除
SLTNode*plist = NULL;
SListPushBack(&plist, 1);
SLTNode*pos = SListFind(&plist, 1);
SListErase(&plist, pos);
SListPrintf(plist);
}
int main()
{
test1();
//test2();
return 0;
}
?——————————————————————————————————————————
双向链表在头文件的声明：
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int LDataType;
typedef struct ListNode
{
struct ListNode*prev;
struct ListNode*next;
LDataType data;
}LTNode;
//初始化
LTNode* ListInit();
//链表打印
void ListPrint(LTNode*phead);
//尾插
void ListPushBack(LTNode*phead, LDataType x);
//尾删
void ListPopBack(LTNode*phead);
//头插
void ListPushFront(LTNode*phead, LDataType x);
//头删
void ListPopFront(LTNode*phead);
//节点值的查找
LTNode*ListFind(LTNode*phead, LDataType x);
//节点的插入
void ListInsert(LTNode*pos, LDataType x);
//节点的删除
void ListErase(LTNode*pos);
//销毁
void ListDestroy(LTNode*phead);2、带头双向循环链表实现
#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"
//初始化
LTNode* ListInit()
{
LTNode*phead = (LTNode*)malloc(sizeof(LTNode));
phead->next = phead;
phead->prev = phead;
return phead;
}
//链表打印
void ListPrint(LTNode*phead)
{
assert(phead);
LTNode*cur = phead->next;
while (cur != phead)
{
printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}
//尾插
void ListPushBack(LTNode*phead, LDataType x)
{
LTNode*tail = phead->prev;
LTNode*newnode = (LTNode*)malloc(sizeof(LTNode));
newnode->data = x;
//插入
tail->next = newnode;
newnode->prev = tail;
newnode->next = phead;
phead->prev = newnode;
}
//尾删
void ListPopBack(LTNode*phead)
{
assert(phead);
assert(phead->next != phead);//防止只有头结点
LTNode*tail = phead->prev;
LTNode*prev_1 = tail->prev;
phead->prev = prev_1;
prev_1->next = phead;
free(tail);
tail = NULL;
}
//头插
void ListPushFront(LTNode*phead, LDataType x)
{
assert(phead);
LTNode*cur = phead->next;
LTNode*newnode = (LTNode*)malloc(sizeof(LTNode));
newnode->data = x;
phead->next = newnode;
newnode->prev = phead;
cur->prev = newnode;
newnode->next = cur;
}
//头删
void ListPopFront(LTNode*phead)
{
assert(phead->next != phead);
LTNode*cur = phead->next;
LTNode*cur_next = cur->next;
phead->next = cur_next;
cur_next->prev = phead;
free(cur);
cur = NULL;
}
//节点值的查找
LTNode*ListFind(LTNode*phead, LDataType x)
{
assert(phead);
LTNode*cur = phead->next;
while (cur != phead)
{
if (cur->data == x)
return cur;
cur = cur->next;
}
return NULL;
}
//节点的插入
void ListInsert(LTNode*pos, LDataType x)
{
assert(pos);
LTNode*prev = pos->prev;
LTNode*newnode = (LTNode*)malloc(sizeof(LTNode));
newnode->data = x;
pos->prev = newnode;
newnode->next = pos;
prev->next = newnode;
newnode->prev = prev;
}
//节点的删除
void ListErase(LTNode*pos)
{
assert(pos);
LTNode*next = pos->next;
LTNode*prev = pos->prev;
prev->next = next;
next->prev = prev;
free(pos);
}
//销毁
void ListDestroy(LTNode*phead)
{
assert(phead);
LTNode*cur = phead->next;
while (cur != phead)
{
LTNode*next = cur->next;
free(cur);
cur = next;
}
free(phead);
phead->next = NULL;
}代码测试：
#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"
void test()
{
LTNode*plist = ListInit();
ListPushBack(plist, 1);
ListPushBack(plist, 2);
ListPushBack(plist, 3);
ListPushBack(plist, 4);
printf("尾插4个数：");
ListPrint(plist);
printf("尾删1个数：");
ListPopBack(plist);
ListPrint(plist);
ListPushFront(plist, 10);
ListPushFront(plist, 20);
printf("头插2个数：");
ListPrint(plist);
ListPopFront(plist);
printf("头删1个数：");
ListPrint(plist);
LTNode*pos = ListFind(plist, 3);
ListInsert(pos, 30);
printf("pos位置插入>:3前面插入30：");
ListPrint(plist);
pos = ListFind(plist, 30);
ListErase(pos);
printf("pos位置删除>删除30：");
ListPrint(plist);
ListDestroy(plist);
}
int main()
{
test();
return 0;
}
三、顺序表与链表的不同点
?