3.双链表
结构体定义（带头双向循环链表）
这种链表结构非常完美，能在O(1)时间内完成插入删除的任务。
typedef int DataType; //带头双向循环链表 typedef struct ListNode { DataType data; //存储数据 struct ListNode* next; //指向下一结点 struct ListNode* prev; //指向前一结点 }ListNode;
初始化接口
//新型初始化接口(带头循环链表) ListNode* ListInit() { ListNode* newnode = BuyListNode(); newnode->next = newnode; newnode->prev = newnode; return newnode; }
申请新结点
//申请结点 ListNode* BuyListNode() { ListNode* newnode = (ListNode*)malloc(sizeof(ListNode)); if (newnode == NULL) { //申请失败，报错终止程序. perror("mallocc:"); exit(-1); } newnode->next = NULL; newnode->prev = NULL; return newnode; }
打印链表
// 打印链表 void ListPrint(ListNode* phead) { assert(phead); //cur为遍历指针 ListNode* cur = phead->next; //当cur等于phead时，遍历完毕 while (cur != phead) { printf("%d-> ", cur->data); cur = cur->next; } //最后打印空指针 printf("NULL\n"); }
尾插和头插
//尾插 void ListPushBack(ListNode* phead, DataType x) { assert(phead); //申请新节点 ListNode* newnode = BuyListNode(); newnode->data = x; //找到尾结点 ListNode* tail = phead->prev; //链接 tail->next = newnode; newnode->prev = tail; newnode->next = phead; phead->prev = newnode; } //头插 void ListPushFront(ListNode* phead, DataType x) { assert(phead); //申请新节点 ListNode* newnode = BuyListNode(); newnode->data = x; //存住第一个结点 ListNode* next = phead->next; //链接 phead->next = newnode; newnode->prev = phead; newnode->next = next; next->prev = newnode; }
尾删和头删
//尾删 void ListPopBack(ListNode* phead) { assert(phead); assert(phead->next!=phead); //保存尾结点和尾结点的前一个结点 ListNode* tail = phead->prev; ListNode* PrevTail = tail->prev; //链接 PrevTail->next = phead; phead->prev = PrevTail; //释放尾结点 free(tail); tail = NULL; } //头删 void ListPopFront(ListNode* phead) { assert(phead); assert(phead->next != phead); //保存第一个节点和第一个结点的下一个结点 ListNode* cur = phead->next; ListNode* next = cur->next; //链接加释放 phead->next = next; next->prev = phead; free(cur); cur = NULL; }
查找函数
//查找 ListNode* ListFind(ListNode* phead, DataType x) { assert(phead); //cur为遍历指针 ListNode* cur = phead->next; while (cur != phead) { //找到了 if (cur->data == x) { return cur; } cur = cur->next; } //没找到 return NULL; }
在pos前插入
//在pos前面进行插入 void ListInsert(ListNode* pos, DataType x) { assert(pos); //申请新节点 ListNode* newnode = BuyListNode(); newnode->data = x; //保存前一个结点 ListNode* prevPos = pos->prev; //链接 prevPos->next = newnode; newnode->prev = prevPos; newnode->next = pos; pos->prev = newnode; }
删除pos位置的值
//删除pos位置的结点 void ListErase(ListNode* pos) { assert(pos); //保存pos的前一结点 ListNode* prevPos = pos->prev; //链接加释放 prevPos->next = pos->next; pos->next->prev = prevPos; free(pos); pos = NULL; }
链表判空
//链表判空 int ListEmpty(ListNode* phead) { assert(phead); return phead->next == phead; }
链表销毁
//链表销毁 void ListDestory(ListNode* phead) { assert(phead); ListNode* cur = phead->next; while (cur != phead) { ListNode* tem = cur->next; free(cur); cur = tem; } free(phead); phead = NULL; }
4.顺序表和链表对比
| 不同点 | 顺序表 | 链表 |
| 存储空间上 | 物理上一定连续 | 逻辑上连续，但物理上不一定连续 |
| 随机访问 | 支持O(1) | 不支持O(N) |
| 任意位置插入或者删除元素 | 可能需要搬移元素，效率低O(N) | 只需修改指针指向 |
| 插入 | 动态顺序表，空间不够时需要扩容 | 没有容量的概念 |
| 应用场景 | 元素高效存储+频繁访问 | 任意位置插入和删除频繁 |
| 缓存利用率 | 高 | 低 |
5.栈
一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
结构体定义
栈一般用顺序表来实现，因为链表在队尾不易删除元素，本文用动态顺序表实现。
//数据类型命名 typedef int DataType; //支持动态增长 typedef struct Stack { DataType* data; int top; //栈顶指针 int capacity; //容量 }Stack;
栈初始化
//初始化栈 void StackInit(Stack* ps) { assert(ps); ps->data = NULL; //指针置空 ps->capacity = ps->top = 0; }
入栈
//入栈 void StackPush(Stack* ps, DataType x) { assert(ps); //栈满 if (ps->top == ps->capacity) { int newcapacity = (ps->capacity == 0 ? 4 : (ps->capacity = (ps->capacity * 2))); DataType* tem = (DataType*)realloc(ps->data, newcapacity*sizeof(DataType)); if (tem == NULL) { perror("realloc Failed:"); exit(-1); } ps->data = tem; ps->capacity = newcapacity; } ps->data[ps->top] = x; ps->top++; }
出栈
//出栈 void StackPop(Stack* ps) { assert(ps); assert(!StackEmpty(ps)); //栈为空则断言 ps->top--; }
栈判空
//判空：空返回1，非空返回0 bool StackEmpty(Stack* ps) { assert(ps); //非空 if (ps->top > 0) { return false; } //空 return true; }
获取栈顶元素
//获取栈顶元素 DataType StackTop(Stack* ps) { assert(ps); assert(!StackEmpty(ps)); return ps->data[ps->top - 1]; }
销毁栈
//销毁栈 void StackDestroy(Stack* ps) { assert(ps); free(ps->data); ps->data = NULL; //不是申请的空间不能free //free(ps); //ps = NULL; }
6.队列
只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出
FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一端称为队头。
队列结构体定义
因为队列的首尾都需要操作，如果用顺序表实现，出队后对头的空间不易利用的缺点。因此，本文使用单链表来实现队列。
typedef int DataType; //链式队列 //结点结构体 typedef struct QueueNode { DataType data; struct QueueNode* next; }QueueNode; //队列头尾指针 typedef struct Queue { struct QueueNode* head; struct QueueNode* tail; }Queue;
初始化队列
//初始化队列 void QueueInit(Queue* ps) { assert(ps); //QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode)); //if (newnode == NULL) //{ // perror("malloc Failed"); // exit(-1); //} //newnode->next = NULL; //指向空结点 ps->head = NULL; ps->tail = NULL; }
入队
//入队 void QueuePush(Queue* ps, DataType x) { assert(ps); QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode)); if (newnode == NULL) { perror("malloc Failed"); exit(-1); } newnode->data = x; newnode->next = NULL; //尾插 if (ps->head == NULL) { ps->head = ps->tail = newnode; } else { ps->tail->next = newnode; ps->tail = ps->tail->next; } }
出队
//出队 void QueuePop(Queue* ps) { assert(ps); assert(!QueueEmpty(ps)); //1.只有一个结点 //2.有多个结点 if (ps->head->next == NULL) { free(ps->head); ps->head = ps->tail = NULL; } else { //暂存头节点，head指向下一个结点 QueueNode* tem = ps->head; ps->head = ps->head->next; free(tem); } }
队列判空
//判空 bool QueueEmpty(Queue* ps) { assert(ps); return ps->head == NULL; }
获取头部元素
//获取头部元素 DataType QueueFront(Queue* ps) { assert(ps); assert(!QueueEmpty(ps)); return ps->head->data; }
获取尾部元素
//获取尾部元素 DataType QueueBack(Queue* ps) { assert(ps); assert(!QueueEmpty(ps)); return ps->tail->data; }
销毁队列
//销毁队列 void QueueDestroy(Queue* ps) { assert(ps); while (!QueueEmpty(ps)) { QueuePop(ps); } }
以上是线性表、栈和队里欸实现的相关接口，如有问题，恳请大佬们指点！💞
