1.顺序表定义
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
顺序表又分为：静态顺序表和动态顺序表。
结构体定义
结构体定义：
//定义变量类型 #define DataType int #define MAX 100 //顺序表结构声明 静态顺序表 //struct SeqList { // DataType data[MAX]; // int size; //}; //动态顺序表 typedef struct SeqList { DataType* data; int size; //顺序表当前大小 int capacity; //容量 }SeqList;
本文主要实现动态结构体
初始化
在使用数据之前，我们需要将数据进行初始化：
//顺序表初始化 void SeqListInit(SeqList* psl) { assert(psl); psl->data = NULL; psl->capacity = 0; psl->size = 0; }
扩容函数
动态顺序表有随时扩容的优点，因此当容量不足时，要能随时扩容
//空间不足，开辟空间 void CheckCapacity(SeqList* psl) { //空间满了 if (psl->capacity == psl->size) { //首次开辟默认4，以后开辟会多2倍 int newcapacity = psl->capacity == 0 ? 4 : psl->capacity * 2; DataType* tem = realloc(psl->data, sizeof(DataType) * newcapacity); if (tem == NULL) { //开辟失败，中止程序 printf("开辟空间失败"); //开辟不足直接中止函数 exit(-1); } psl->data = tem; psl->capacity = newcapacity; } }
打印函数
为了方便观察代码的逻辑还写了一个打印函数
//打印顺序表 void SeqListPrint(SeqList* psl) { //断言的作用：防止传进来的指针为空！ assert(psl); for (int i = 0; i < psl->size; i++) { printf("%d ", psl->data[i]); } printf("\n"); }
尾插和尾删
直接在尾部插入和删除数据。
//尾插 void SeqListPushBack(SeqList* psl, DataType x) { //断言的作用：防止传进来的指针为空！ assert(psl); //空间不够开辟空间 CheckCapacity(psl); psl->data[psl->size] = x; psl->size++; } //尾删 void SeqListPopBack(SeqList* psl) { //断言的作用：防止传进来的指针为空！ assert(psl); assert(psl->size > 0); psl->size--; }
头插和头删
在头部插入和删除数据。
//头插 void SeqListPushFront(SeqList* psl, DataType x) { //断言的作用：防止传进来的指针为空！ assert(psl); CheckCapacity(psl); //尾坐标 int end = psl->size - 1; while (end >= 0) { psl->data[end + 1] = psl->data[end]; end--; } psl->data[0] = x; psl->size++; } //头删 void SeqListPopFront(SeqList* psl) { //断言的作用：防止传进来的指针为空！ assert(psl); assert(psl->size > 0); int end = 1; while (end < psl->size) { psl->data[end - 1] = psl->data[end]; end++; } psl->size--; }
查找函数
按值查找，查找成功返回下标，查找失败返回-1.
//顺序表查找 int SeqListFind(SeqList* psl, DataType x) { //成功找到返回下标 for (int i = 0; i < psl->size; i++) { if (psl->data[i] == x) { return i; } } //找不到返回-1 return -1; }
指定位置插入和删除
在指定的位置插入和删除数据
//在pos位置插入 void SeqListInsert(SeqList* psl, int pos, DataType x) { //断言的作用防止指针为空，防止传进来的pos非法！ assert(psl); assert(pos >= 0 && pos <= psl->size); CheckCapacity(psl); int end = psl->size - 1; while (end >= pos) { psl->data[end + 1] = psl->data[end]; end--; } psl->data[pos] = x; psl->size++; } //在pos位置删除 void SeqListErase(SeqList* psl, int pos) { //断言的作用防止指针为空，防止传进来的pos非法！ assert(psl); assert(pos >= 0 && pos < psl->size); int end = pos + 1; while (end < psl->size) { psl->data[end - 1] = psl->data[end]; end++; } psl->size--; }
顺序表销毁
在使用完之后，要及时销毁顺序表。
//顺序表销毁 void SeqListDestory(SeqList* psl) { assert(psl); free(psl->data); psl->data = NULL; psl->size = psl->capacity = 0; }
2.单链表定义
链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
结构体定义（无头单向非循环链表）
typedef int SLDateType; //数据类型 //无头，单向，非循环链表增删改查 typedef struct SListNode { SLDateType data; struct SListNode* next; }SListNode; //结构体定义
打印函数
//打印函数 void SListPrint(SListNode* phead) { SListNode* cur = phead; while (cur != NULL) { printf("%d -> ", cur->data); cur = cur->next; } printf("NULL\n"); }
申请新节点
//申请一个新节点 SListNode* BuyNewNode(SLDateType x) { SListNode* newnode = (SListNode*)malloc(sizeof(SListNode)); if (newnode == NULL) { printf("申请新结点失败"); exit(-1); } newnode->data = x; newnode->next = NULL; return newnode; }
尾插
//尾插 void SListPushBack(SListNode** pphead, SLDateType x) { assert(pphead); //申请新节点 SListNode* newnode = BuyNewNode(x); //链表为空时 if (*pphead == NULL) { *pphead = newnode; } else { //找到最后一个结点 SListNode* tail = *pphead; while (tail->next != NULL) { tail = tail->next; } //最后一个节点指向新节点 tail->next = newnode; } }
头插
//头插 void SListPushFront(SListNode** pphead, SLDateType x) { assert(pphead); SListNode* newnode = BuyNewNode(x); //新节点指向头指针，然后头指针指向新节点. newnode->next = *pphead; (*pphead) = newnode; }
尾删
//尾删 void SListPopBack(SListNode** pphead) { assert(pphead); assert(*pphead); //只有一个结点 if ((*pphead)->next == NULL) { free(*pphead); *pphead = NULL; } else { //找到保存尾结点的前一个结点 SListNode* tailPrv = *pphead; SListNode* tail = *pphead; while (tail->next != NULL) { //保存tail的前一个结点 tailPrv = tail; tail = tail->next; } tailPrv->next = NULL; free(tail); tail = NULL; //好习惯 } }
头删
//头删 void SListPopFront(SListNode** pphead) { assert(pphead); assert(*pphead); SListNode* del = *pphead; *pphead = (*pphead)->next; free(del); del = NULL; }
按值查找
//查找 SListNode* SListFind(SListNode* phead, SLDateType x) { assert(phead); //用cur去遍历 SListNode* cur = phead; while (cur != NULL) { if (cur->data == x) { //printf("找到啦\n"); return cur; } cur = cur->next; } //printf("没找到\n"); //买找到返回空指针 return NULL; }
在pos前面插入（不推荐效率低）
//在pos前面插入 void SListInsert(SListNode** pphead, SListNode* pos, SLDateType x) { assert(pos); assert(pphead); assert(*pphead); //第一个位置插入变成头插 if ((*pphead)==pos) { SListPushFront(pphead, x); } else { SListNode* cur = *pphead; SListNode* newnode = BuyNewNode(x); while (cur->next != pos) { cur = cur->next; } newnode->next = pos; cur->next = newnode; } }
删除pos位置（不推荐效率低）
//删除pos位置 void SListEraser(SListNode** pphead, SListNode* pos) { assert(pos); assert(pphead); assert(*pphead); //头删 if (*pphead == pos) { SListPopFront(pphead); } else { SListNode* cur = *pphead; while (cur->next != pos) { cur = cur->next; } cur->next = pos->next; free(pos); pos = NULL; } }
在pos后面插入（推荐效率高）
//在pos后面插入 void SListInsertAfter(SListNode** pphead, SListNode* pos, SLDateType x) { assert(pos); assert(pphead); assert(*pphead); SListNode* newnode = BuyNewNode(x); newnode->next = pos->next; pos->next = newnode; }
删除pos后的值（推荐效率高）
//删除pos之后的值 void SListEraserAfter(SListNode** pphead, SListNode* pos) { assert(pos); assert(pphead); assert(*pphead); assert(pos->next); //保证pos后面必须有元素 SListNode* del = pos->next; pos->next = del->next; free(del); del = NULL; }
