新号别搞：数据结构-顺序表与链表

void SqListInit(SqList* ps); //书上 void SqListInit (SqList & s);

销毁顺序表

void SqListDestroy(SqList* ps);

插入数据插入i位 (头插 尾插)

void SqListInsert(SqList* ps, int i, SqDataType x); //i位 void SqListPushFront(SqList* ps, SqDataType x); //头插 void SqListPushBack(SqList* ps, SqDataType x); //尾插

删除数据 删除中间 （头删 尾删）

SqDataType SqListDelete(SqList* ps, int i); //i位 void SqListPopFront(SqList* ps); //头删 void SqListPopBack(SqList* ps); //尾删

返回i下标的值 + 第一个 值x 的下标，不存在-1

SqDataType GetElem(SqList* ps, int i); //i下标的值 int LocateElem(SqList* ps, SqDataType x); //第一个 值x 的下标

检查顺序表为空否，空作true 不空 false + 获取有效元素个数 + 打印

bool EmptysqList(SqList* ps); //顺序表空否 int SqListSize(SqList* ps); //获取有效元素个数 void SqListPrint(SqList* ps); //打印

3.3.2 实现 （SqList.cpp）

• #include "SqList.h"

初始化接口函数

void SqListInit(SqList* ps) { assert(ps); ps->arr = (SqDataType*)malloc(sizeof(SqDataType) * 4); if (ps->arr == NULL) { perror("SqListInit: malloc failed"); return; } ps->size = 0; ps->capacity = 4; }

销毁接口函数

void SqListDestroy(SqList* ps) { assert(ps); if (ps->arr) { free(ps->arr); ps->arr = NULL; ps->capacity = 0; ps->size = 0; } }

插入接口函数（+头插尾插）

void SqListInsert(SqList* ps, int i, SqDataType x) { assert(ps); assert(i >= 0 && i <= ps->size); if (ps->size == ps->capacity) { SqDataType* tmp = (SqDataType*)realloc(ps->arr, sizeof(SqDataType) * ps->capacity * 2); if (tmp == NULL) { perror("malloc failed");return; } ps->arr = tmp; ps->capacity *= 2; } // j为下标 ， i 为位序 for (int j = ps->size - 1; j >= i; j--) { ps->arr[j + 1] = ps->arr[j]; } ps->arr[i] = x; ps->size++; } //头插 void SqListPushFront(SqList* ps, SqDataType x) { SqListInsert(ps, 0, x); } //尾插 void SqListPushBack(SqList* ps, SqDataType x) { SqListInsert(ps, ps->size, x); }

删除接口函数（+头删尾删）

SqDataType SqListDelete(SqList* ps, int i) { assert(ps); assert(i >= 0 && i <= ps->size); SqDataType x = ps->arr[i]; for (int j = i + 1; j < ps->size; j++) { ps->arr[j - 1] = ps->arr[j]; } ps->size--; return x; } //头删 void SqListPopFront(SqList* ps) { SqListDelete(ps, 0); } //尾删 void SqListPopBack(SqList* ps) { SqListDelete(ps, ps->size-1); }

返回i下标的值 + 第一个 值x 的下标，不存在-1

//下标i的值 SqDataType GetElem(SqList* ps, int i) { assert(ps); assert(i >= 0 && i < ps->size); return ps->arr[i]; } //值i的下标 int LocateElem(SqList* ps, SqDataType x) { assert(ps); for (int i = 0; i < ps->size; ++i) { if(ps->arr[i] == x) return i; } return -1; }

检查顺序表为空否，空作true 不空 false + 获取有效元素个数 + 打印顺序表元素

//检查顺序表为空否，空作true 不空 false bool EmptysqList(SqList* ps) { assert(ps); return ps->size == 0; } //获取有效元素个数 int SqListSize(SqList* ps) { assert(ps); return ps->size; } //打印顺序表元素 void SqListPrint(SqList* ps) { assert(ps); for (int i = 0; i < ps->size; i++) { printf("%d ", ps->arr[i]); }printf("\n"); }

3.3.3 测试（text.cpp）

• #include "SqList.h"

void TestSqList1()

(初始化)

SqList sl; //SqListInit(sl); //cpp SqListInit(&sl);

(插入测试）

// 尾插 SqListInsert(&sl, 0, 1); SqListInsert(&sl, 1, 2); SqListInsert(&sl, 2, 3); SqListInsert(&sl, 3, 4); SqListInsert(&sl, 4, 5); SqListInsert(&sl, 5, 6); SqListPrint(&sl); // 头插 SqListInsert(&sl, 0, 100); SqListPrint(&sl); // 中间插入 SqListInsert(&sl, 1, 200); SqListPrint(&sl);

（删除测试）

//删除顺序表第1个位置上的元素 printf("顺序表中有效元素个数为：%d \n", SqListSize(&sl)); SqListPrint(&sl); // 删除末尾的数据 printf("删除的元素是:%d \n", SqListDelete(&sl, SqListSize(&sl) - 1)); SqListPrint(&sl); // 删除中间的数据 printf("删除的元素是:%d \n", SqListDelete(&sl, 2)); SqListPrint(&sl);

（返回测试）

//i 下标的元素 printf("顺序表中第%d个元素是：%d\n", 1, GetElem(&sl, 1)); SqListPrint(&sl); // x值的下标 printf("40 的下标是%d\n", LocateElem(&sl, 40)); SqListPrint(&sl); SqListDestroy(&sl);

4.链表

4.1 优势及相关概念

• 可以按需申请空间，不再需要扩容
• 插入和删除效率高
• 结点存储数据和下一个结点指针
• 头指针: 指向第⼀个结点的指针;尾结点的指针指向空
• 带头结点+不带头结点两种结构。头结点⼀个哨兵位,不存有效数据

4.2 单链表实现

4.2.1 接口函数实现(List.h)

• #include<stdio.h> #include<stdlib.h>#include<stdbool.h> #include<assert.h>头文件
• typedef int LDataType;重命名类型

创建新结点

LNode* BuyListNode(int data);

初始化

LNode* ListInit(); //书上 void ListInit(LinkList& L);

i位置插入元素x 头插 尾插

void ListInsert(LNode* L, int i, LDataType x); void ListPushFront(LNode* L, LDataType x); void ListPushBack(LNode* L, LDataType x);

删除i结点，用 x 带出结点值 头删 尾删

LDataType ListDelete(LNode* L, int i); LDataType ListPopFront(LNode* L); LDataType ListPopBack(LNode* L);

判断链表空否

bool ListEmpty(LNode* L);

打印

void ListPrint(LNode* L); //(LinkList* L)

获取有效元素个数

int ListSize(LNode* L);

返回第一个数据 = x结点 的地址 ，反之回NULL

LNode* ListLocateElem(LNode* L, LDataType x);

返回下标i的结点

LNode* ListGetElem(LNode* L, int i);

销毁

void ListDestroy(LNode* L);

4.2.2 实现（List.c）

• 包含头文件#include"List.h"

创建新结点

LNode* BuyListNode(int data) { LNode* newNode = (LNode*)malloc(sizeof(LNode)); if (newNode == NULL) { perror("malloc fail"); exit(-1); } newNode->data = data; newNode->next = NULL; return newNode; }

初始化

LNode* ListInit() { LNode* node = BuyListNode(-1); return node; }

打印链表

void ListPrint(LNode* L) //(LinkList* L) { assert(L); printf("头结点->"); LNode* cur = L->next; while (cur) { printf("%d->", cur->data); cur = cur->next; //后移指针 } printf("NULL\n"); }

判空

bool ListEmpty(LNode* L) { return L->next == NULL; }

有效元素个数

int ListSize(LNode* L) { assert(L); int size = 0; LNode* cur = L->next; while (cur) { size++; cur = cur->next; } return size; }

i位置插入

void ListInsert(LNode* L, int i, LDataType x) { assert(L && i >= 0);//断言：头结点非空，插入位置非负 int j = -1;//从头结点（下标 -1）开始 LNode* i_1Node = L;//i_1Node 用于定位第 i-1 个结点，初始指向头结点 while (i_1Node != NULL && j < i - 1) { ++j; i_1Node = i_1Node->next; } assert(i_1Node);//如果循环后 i_1Node 为 NULL，说明链表长度不够，i 越界 LNode* newNode = BuyListNode(x); //先将新结点的 next 指向前驱的 next（即原第 i 个结点地址，可能为 NULL） newNode->next = i_1Node->next; //再将前驱的 next 指向新结点，完成插入 i_1Node->next = newNode; }【

头插

void ListPushFront(LNode* L, LDataType x) { ListInsert(L, 0, x);//相当于在 0 位置插入，即头结点的后面 }

尾插

void ListPushBack(LNode* L, LDataType x) { assert(L); LNode* cur = L; while (cur->next) { cur = cur->next; } LNode* newNode = BuyListNode(x); //将尾结点的 next 指向新结点，新结点自动成为新尾 cur->next = newNode; }

删除结点，返回值

LDataType ListDelete(LNode* L, int i) { assert(i >= 0); int j = -1; LNode* i_1Node = L; while (i_1Node != NULL && j < i - 1) { ++j; i_1Node = i_1Node->next; } //检查前驱和前驱的 next 是否存在，任一为空说明 i 非法 assert(i_1Node != NULL && i_1Node->next != NULL); //iNode 指向待删除的第 i 个结点 LNode* iNode = i_1Node->next; //将前驱的 next 指向被删结点的下一个结点，从链表中移除 iNode i_1Node->next = iNode->next; //取出被删数据，释放结点内存 LDataType x = iNode->data; free(iNode); return x; }

头删

LDataType ListPopFront(LNode* L) { return ListDelete(L, 0); }

尾删

LDataType ListPopBack(LNode* L) { assert(L && L->next); LNode* cur = L; //cur->next 存在 — 当前有后继 //cur->next->next 存在 — 后继的后继存在，说明 cur 还不是倒数第二个 //循环退出时，cur->next 为尾结点，cur 为倒数第二个结点（或头结点） while (cur->next && cur->next->next) { cur = cur->next; } LNode* del = cur->next; LDataType x = del->data; free(del); cur->next = NULL; return x; }

按值查找

LNode* ListLocateElem(LNode* L, LDataType x) { assert(L); LNode* cur = L->next; while (cur) { if (cur->data == x) return cur; cur = cur->next; } return NULL; }

按位查找

LNode* ListGetElem(LNode* L, int i) { assert(L && i >= 0); int j = 0; LNode* iNode = L->next; //遍历，直到 iNode 越界或 j 到达 i while (iNode != NULL && j < i) { ++j; iNode = iNode->next; } //如果 iNode 为 NULL，说明 i 超出链表长度，返回 NULL //否则返回第 i 个结点地址 return iNode; }

销毁

void ListDestroy(LNode* L) { LNode* cur = L->next; while (cur) { LNode* next = cur->next; //先保存下一个结点地址，否则释放后丢失 free(cur); cur = next; } free(L); }

4.2.3 测试（test.c）

• 头文件#include "List.h"

手动链一个CreateList

LNode* CreateList() { // 创建头结点 LNode* L = BuyListNode(-1); // 先快速构造5个结点，⽅便测试 LNode* node1 = BuyListNode(1); LNode* node2 = BuyListNode(2); LNode* node3 = BuyListNode(3); LNode* node4 = BuyListNode(4); LNode* node5 = BuyListNode(5); // 然后通过⼿动的⽅式将结点链接起来 L->next = node1; node1->next = node2; node2->next = node3; node3->next = node4; node4->next = node5; return L; }

TestList1来测试

void TestList1() { LNode* LT = NULL; LT = CreateList(); // 测试打印⽅法和获取结点个数⽅法 printf("链表LT中总共有%d个结点\n", ListSize(LT)); ListPrint(LT); // 测试按值获取 printf("链表中值%d结点为%p\n", 1, ListLocateElem(LT, 1)); // 测试按下标获取 printf("链表中下标%d的结点的值为%d\n", 0, ListGetElem(LT, 0)->data); ListInsert(LT, 5, 6); // 尾插 ListPrint(LT); ListInsert(LT, 2, 30); // 中间插 ListPrint(LT); ListInsert(LT, 0, 0); // 头插 ListPrint(LT); ListDelete(LT, 0); // 头删 ListPrint(LT); ListDelete(LT, 2); // 中间删 ListPrint(LT); ListDelete(LT, 5); // 尾删 ListPrint(LT); // 销毁链表 ListDestroy(LT); }

完~走过路过不要错过，有错请指出谢谢！