初阶数据结构（C语言实现）——3顺序表和链表（1）

目录 【本节目标】1. 线性表2.顺序表2.1概念及结构2.2 接口实现2.2.0 动态顺序表2.2.1 顺序表初始化SLInit（）2.2.2 销毁和打印2.2.3 尾插SLPushBack（）2.2.4 尾删SLPopBack（）2.2.5 头插2.2.6 头删2.2.7 插入2.2.8 删除2.2.9 查找函数 2.3 源代码2.3.1 SeqList20250226.h2.3.2 SeqList20250226.c2.3.3 FileName20250226.c

【本节目标】

1.线性表 2.顺序表 3.链表 4.顺序表和链表的区别和联系

1. 线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串… 线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储

2.顺序表 2.1概念及结构

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。顺序表一般可以分为：

静态顺序表：使用定长数组存储元素。

动态顺序表：使用动态开辟的数组存储。

2.2 接口实现

静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下面我们实现动态顺序表。

2.2.0 动态顺序表 //seqList.h #pragma once #include<stdio.h> typedef int SLDataType; #define INIT_CAPACITY 4 //默认初始化大小 //动态顺序表——按需申请 typedef struct SeqList { SLDataType* a; int size; //有效数据个数 int capacity;//空间容量 }SL; 2.2.1 顺序表初始化SLInit（）

版本1

//seqList.c #include"SeqList20250226.h" //顺序表初始化1 void seqInit(SL s) { s.a = (SLDataType*)malloc(sizeof(SLDataType)* INIT_CAPACITY); if (s.a == NULL) { perror("seqInit"); return; } s.size = 0; s.capacity = INIT_CAPACITY; } //test.c #define _CRT_SECURE_NO_WARNINGS 1 #include"SeqList20250226.h" SL s; void TestSeqList1(SL s) { seqInit(s); } int main() { TestSeqList1(s); return 0; }

初始化结果：单步调试

版本2(后续都使用版本2)

//顺序表初始化2 void SLInit(SL* ps) { ps->a = ((SLDataType*)malloc(sizeof(SLDataType) * INIT_CAPACITY)); if (ps->a == NULL) { perror("SLInit"); return; } ps->size = 0; ps->capacity = INIT_CAPACITY; } 2.2.2 销毁和打印 //seqList.h //销毁 void SLDestroy(SL* ps); //打印 void SLPrint(SL* ps); //seqList.c //销毁 void SLDestroy(SL* ps) { free(ps->a); ps->a = NULL; ps->size = ps->capacity = 0; } //打印 void SLPrint(SL* ps) { int i = 0; for (i = 0; i < ps->size; i++) { printf("%d", ps->a[i]); } printf("\n"); } 2.2.3 尾插SLPushBack（）

seqList.h

#include<stdlib.h> //尾插 void SLPushBack(SL* ps, SLDataType x);

seqList.c

//尾插 void SLPushBack(SL* ps, SLDataType x) { //扩容 这里扩容了2倍，是自己定的，是一个比较合理的值，具体需要开辟多大是要和自己的实际问题结合 if (ps->size == ps->capacity) { SLDataType* tem = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * ((ps->capacity) * 2)); if (tem == NULL) { perror("SLPushBack::realloc"); return; } ps->a = tem; ps->capacity *= 2; } //ps->a[ps->size] = x; //ps->size++; 这两行可以合并为下面的1行 ps->a[ps->size++] = x; }

尾插验证

#define _CRT_SECURE_NO_WARNINGS 1 #include"SeqList20250226.h" void TestSeqList1() { SL s; SLInit(&s); SLPushBack(&s, 1); SLPushBack(&s, 2); SLPushBack(&s, 3); SLPushBack(&s, 4); SLPushBack(&s, 5); SLPushBack(&s, 6); SLPushBack(&s, 7); SLPushBack(&s, 8); SLPushBack(&s, 9); SLPrint(&s); } int main() { TestSeqList1(); return 0; }

2.2.4 尾删SLPopBack（） //尾删 void SLPopBack(SL* ps) { assert(ps); //判断是否为空 if (ps->size == 0) { return 0; } //不为空就直接size-1 ps->size--; }

验证插入4个元素，删掉1个元素

2.2.5 头插

头插思路

扩容函数封装

void SLCheckCapacity(SL* ps) { assert(ps); if (ps->size == ps->capacity)//判断目前是大小是否和容量大小一样，一样的话，就需要扩容 { SLDataType* tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * (ps->capacity) * 2); //扩容原来容量的两倍 if (tmp == NULL) { perror("SLCheckCapacity::realloc fail!"); return; } ps->a = tmp; ps->capacity *= 2; } }

代码实现

void SLPushFront(SL* ps, SLDataType x) { assert(ps); //这里要考虑扩容的事情，所以我们需要封装一个扩容函数， SLCheckCapacity(ps); int end =ps->size-1; while (end>=0) { ps->a[end+1] = ps->a[end ];//从后往前依次向后挪 end--; } ps->a[0] = x; ps->size++; }

头插验证

2.2.6 头删

思路

void SLPopFront(SL* ps) { assert(ps); assert(ps->size > 0);//size小于0 直接断言报错。 int begin = 1; while (begin < ps->size) { ps->a[begin - 1] = ps->a[begin]; begin++; } ps->size--; }

头删验证

2.2.7 插入

思路

void SLInsert(SL* ps, int pos, SLDataType x) { assert(ps); assert(pos >= 0 && pos <= ps->size); SLCheckCapacity(ps); int end = ps->size - 1; while (pos < end) { ps->a[end + 1] = ps->a[end]; end--; } ps->a[pos] = x; ps->size++; }

验证

2.2.8 删除

思路

void SLErase(SL* ps, int pos) { assert(ps); assert(pos >= 0 && pos < ps->size); int begin = pos + 1; while (begin <ps->size) { ps->a[begin-1] = ps->a[begin]; begin++; } ps->size--; }

验证

2.2.9 查找函数

思路：比较简单，直接遍历即可

int SLFind(SL* ps, SLDataType x)//直接遍历即可 { assert(ps); int i = 0; for (i = 0; i < ps->size; i++) { if (ps->a[i] == x) { printf("找到了"); return i; } } return -1; } 2.3 源代码 2.3.1 SeqList20250226.h #pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> //#define N 100 //typedef int SLDataType; // 静态顺序表 -- 开少了不够用 开多了浪费 //struct SeqList //{ // SLDataType a[N]; // int sise; //}; typedef int SLDataType; #define INIT_CAPACITY 4 //默认初始化大小 //动态顺序表——按需申请 typedef struct SeqList { SLDataType* a; int size; //有效数据个数 int capacity;//空间容量 }SL; //基础的增删查改函数 //初始化 void seqInit(SL* ps); void SLInit(SL* ps); //销毁 void SLDestroy(SL* ps); //打印 void SLPrint(SL* ps); //尾插 void SLPushBack(SL* ps, SLDataType x); //尾删 void SLPopBack(SL* ps); 头插 void SLPushFront(SL* ps, SLDataType x); 头删 void SLPopFront(SL* ps); // 顺序表在pos位置插入x void SLInsert(SL* ps, int pos, SLDataType x); // 顺序表删除pos位置的值 void SLErase(SL* ps, int pos); //查找表中有没有某个值 int SLFind(SL* ps, SLDataType x); 2.3.2 SeqList20250226.c #define _CRT_SECURE_NO_WARNINGS 1 #include"SeqList20250226.h" //顺序表初始化1 void seqInit(SL s) { s.a = (SLDataType*)malloc(sizeof(SLDataType)* INIT_CAPACITY); if (s.a == NULL) { perror("seqInit"); return; } s.size = 0; s.capacity = INIT_CAPACITY; } //顺序表初始化2 void SLInit(SL* ps) { ps->a = (SLDataType*)malloc(sizeof(SLDataType) * INIT_CAPACITY); if (ps->a == NULL) { perror("SLInit"); return; } ps->size = 0; ps->capacity = INIT_CAPACITY; } //销毁 void SLDestroy(SL* ps) { free(ps->a); ps->a = NULL; ps->size = ps->capacity = 0; } //打印 void SLPrint(SL* ps) { int i = 0; for (i = 0; i < ps->size; i++) { printf("%d ", ps->a[i]); } printf("\n"); } //尾插 void SLPushBack(SL* ps, SLDataType x) { //判断是否要扩容 if (ps->size == ps->capacity) { SLDataType* tem = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * (ps->capacity) * 2); if (tem == NULL) { perror("SLPushBack::realloc fail"); return; } ps->a = tem; ps->capacity *= 2; } //ps->a[ps->size] = x; //ps->size++; //这两行可以合并为下面的1行 ps->a[ps->size++] = x; } //尾删 void SLPopBack(SL* ps) { assert(ps); //判断是否为空 if (ps->size == 0) { return 0; } //不为空就直接size-1 ps->size--; } void SLCheckCapacity(SL* ps) { assert(ps); if (ps->size == ps->capacity) { SLDataType* tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * (ps->capacity) * 2); if (tmp == NULL) { perror("SLCheckCapacity::realloc fail!"); return; } ps->a = tmp; ps->capacity *= 2; } } void SLPushFront(SL* ps, SLDataType x) { assert(ps); //这里要考虑扩容的事情，所以我们需要封装一个扩容函数， SLCheckCapacity(ps); int end =ps->size-1; while (end>=0) { ps->a[end+1] = ps->a[end ];//从后往前依次向后挪 end--; } ps->a[0] = x; ps->size++; } void SLPopFront(SL* ps) { assert(ps); assert(ps->size > 0);//size小于0 直接断言报错。 int begin = 1; while (begin < ps->size) { ps->a[begin - 1] = ps->a[begin]; begin++; } ps->size--; } void SLInsert(SL* ps, int pos, SLDataType x) { assert(ps); assert(pos >= 0 && pos < ps->size); SLCheckCapacity(ps); int end = ps->size - 1; while (pos <= end) { ps->a[end + 1] = ps->a[end]; end--; } ps->a[pos] = x; ps->size++; } void SLErase(SL* ps, int pos) { assert(ps); assert(pos >= 0 && pos < ps->size); int begin = pos + 1; while (begin <ps->size) { ps->a[begin-1] = ps->a[begin]; begin++; } ps->size--; } int SLFind(SL* ps, SLDataType x)//直接遍历即可 { assert(ps); int i = 0; for (i = 0; i < ps->size; i++) { if (ps->a[i] == x) { printf("找到了"); return i; } } return -1; } 2.3.3 FileName20250226.c #define _CRT_SECURE_NO_WARNINGS 1 #include"SeqList20250226.h" void TestSeqList1() { SL s; SLInit(&s); SLPushBack(&s, 0); SLPushBack(&s, 1); SLPushBack(&s, 2); SLPushBack(&s, 3); SLPushBack(&s, 4); // SLPopBack(&s); // // SLPushFront(&s,5); // SLPopFront(&s); // SLInsert(&s, 2, 20); SLErase(&s, 2); SLPrint(&s); SLDestroy(&s); } void manu() { printf("**************************\n"); printf("****1:头插 2.尾插****\n"); printf("****3.头删 4.尾删****\n"); printf("****5.插入 -1.退出****\n"); printf("**************************\n"); } int main() { SL s; SLInit(&s); int input = 0; while (input != -1) { manu(); scanf("%d", &input); printf("请输入您的选择：\n"); if (input == 1) { printf("请输入您想要插入的数据，并以-1结尾\n"); int x = 0; while (x != -1) { scanf("%d", &x); SLPushBack(&s, x); } } else if (input == 7) { SLPrint(&s); } } //TestSeqList1(); return 0; }