超级详细数据结构代码实现（C语言）后续持续更新
6 个月前
· 来自专栏
数据结构
启明
菜鸟的网络安全成长记
欢迎各位知友评论区友善相互学习交流，欢迎大佬批评指正~
感觉有用的话，就点一个赞赞~
建议打开目录食用~
数据结构学习之初确实遇到了比较大困难：
1、C语言基础特别不牢固，特别是指针、结构体由于时间有限，当时学校讲得非常仓促。
2、上课老师讲解伪代码，只讲解每一个函数内的算法，但是我并不会知道主函数部分怎么写，具体算法的代码实现也很有问题，这就导致很长一段时间我对数据结构的理解一直很抽象，讲半天也不知道这些操作到底实在干什么，实现了怎样的效果，有什么用。
3、走了很多弯路，花费很多不必要的时间。接上一点，实际上在学习数据结构的过程中并不需要把每一个代码都给实现一遍，数据结构最重要的一部分还是抽象的算法，关键在于理解，而我在数据结构学习初期在代码事先上面耗费了太多的时间，而这在应付期末考试的时候完全没有必要。
4、在我学习数据结构初期，其实最高效的帮助肯定是他人的具体化、针对性的帮助，而不是什么教程。现在看开，很多问题其实只需要别人简单解释一下后面就会轻松很多。但是事实就是这样，越是什么都不会越是不知道自己该问什么，越是没有充足的胆量向老师打破砂锅问到底。（虽然在现在想来这些担忧完全是没有必要）
以上我遇到的困难供大家参考，针对困难的解决方法就是更快速高效轻松的入门数据结构的一些建议了。
开始之前，尽管这是数据结构C语言的实现过程，参考的是严蔚敏老师的《数据结构》教材等。
但是，但是！为了方便起见，还是会用到一点点点点的C++的知识，用一点点就会方便很多。
- 引用符号&：在C语言中，形参的改变无法影响到实参，函数内部的变化传不出来，只能通过指针来解决。但是C++ 的引用符号可以很好的解决这个问题。
- 布尔类型：C语言中没有布尔类型，都是用一个flag值来表示，0和1分别表示true和false。但是C++中用布尔值，bool、true、false都是关键字。因此函数前面的状态值可以直接用bool类型，返回值用true和false。
单链表操作集
#define _CRT_SECURE_NO_WARNINGS 1
//【1】预编译部分
#include<stdio.h>
#include<stdlib.h>//主要含有内存分配等一系列的函数
//【2】宏定义部分
#define bool char
#define true 1
#define faulse 0
//【3】自定义数据元素类型
typedef int ElemType;
//【4】单链表的结构体
typedef struct LNode {
ElemType data;
struct LNode* next;//这里一定写全，因为结构体还没定义完成下面无法重命名
}LNode,*LinkList;//LinkList是头指针
//【5】单链表的初始化(即头节点的初始化)
void InitLinkList(LinkList L) {
L->data = 0;//头节点的data域用来存储表长
L->next = NULL;//头节点的next域用来指向链表第一个节点
//【6】单链表的打印
bool PrintLinkList(LinkList L) {
LNode* p;
p = L;
while (p->next!=NULL) {
p = p->next;
printf("%d-->", p->data);
如果是以下内容：
（p=L->next;//p指向第一个节点）
printf("%d", p->data);//输出当前节点内容
p = p->next;
最后一个节点无法打印出来
所以，可以利用头指针使打印下一个节点的data
printf("NULL\n");
return true;
//【7】单链表的头插法创建链表
bool HeadInsertLinkList(LinkList L){
LNode *NewNode;//新结点
ElemType NewNode_data;//新结点的数据域
printf("Please enter a number(9999 means the end)");
scanf("%d", &NewNode_data);
while (NewNode_data!=9999)
//进行插入操作
NewNode = (LNode*)malloc(sizeof(LNode));
NewNode->next = L->next;
L->next = NewNode;
NewNode->data = NewNode_data;
L->data++;
printf("Please enter a number(9999 means the end)");
scanf("%d", &NewNode_data);
return true;
//【8】单链表的尾插法创建链表
//一种想法：每次都循环找到最后一个结点，把它插到最后一个，但是这样太慢了
//考虑增加一个尾指针，指向尾结点
bool TailInsertLinkList(LinkList L) {
LNode *NewNode;//新结点
LNode *TailNode=L;//指向尾结点的指针（头指针typedef的时候定义过了，尾指针没有）
ElemType NewNode_data;//新结点的data域
//使尾指针指向最后一位
while (TailNode->next != NULL) {
TailNode = TailNode->next;
printf("Please enter a number(9999 means the end)");
scanf("%d", &NewNode_data);
while (NewNode_data != 9999) {
NewNode = (LNode*)malloc(sizeof(LNode));
NewNode->data = NewNode_data;
//第一步
NewNode->next = NULL;
//第二步
TailNode->next = NewNode;
//使尾指针指向最后一个元素
TailNode = NewNode;
L->data++;
printf("Please enter a number(9999 means the end)");
scanf("%d", &NewNode_data);
return true;
//【9】按位查找（找到第i位结点并返回它的指针）
LNode* GetElem(LinkList L, int i) {
//[1]判断i的合法性
if (i == 0) {
printf("The LinkList's element you are looking for does not exist!\nReturn the head pointer of the LinkList!\n ");
return L;
if (i<1 || i>L->data) {
printf("The LinkList's element you are looking for does not exist!\nReturn the head pointer of the NULL!\n");
return NULL;
//[2]查找数据元素
LNode* p = L;
for (int j = 0; j < i; j++) {
p = p->next;
return p;
//【10】按值查找（找到要查找值的结点并返回它的指针）
LNode* LocateElem(LinkList L, ElemType e) {
if (!L->next) {
printf("This LinkList is empty!\n");
return L;
LNode* p = L;
while (p->next) {
p = p->next;
if (p->data == e)
return p;
printf("The LinkList's element you are looking for is not exist! ");
return NULL;
//【11】单链表的按位插入（在链表的第i位插入新的元素）
//由于链表由前驱找后驱方便，后驱找前驱并不方便，所以要先找到要插入结点前面那一个
bool LocateInsertElem(LinkList L, int i, ElemType e) {
//[1]判断i的合法性
if (i<1 || i>(L->data + 1))//可以插入第data+1个结点，但是不能大于
printf("The position of the element to be inserted is invalid!\n");
return false;
//[2]插入新元素
//(先定位到要插入位置的前一位)
LNode* p = GetElem(L,i-1);//这就是前面GetElem函数判断i的合法性时i=0要单独说一下地原因
//第一步：生成新的结点，让新结点的next指向下一个结点
LNode* NewNode =(LNode*) malloc(sizeof(LNode));
NewNode->data = e;
NewNode->next = p->next;
//第二步：要插入前面结点的next指向新结点
p->next = NewNode;
L->data++;//表长++
return true;
//【12】单链表的按位删除(找到第i位并删除)
//第一步：找到前驱
//第二步：q=p->next
//第三步：p->next=q->next
//第四步：free(q)
bool LocalDeletElem(LinkList L, int i, ElemType *e) {//e的作用是把要删除的元素带出来
//[1]检查i的合法性（①空表放弃删除②超过合理范围）
if (!L->next) {
printf("This Linklist is empty!\n");
*e = 9999;
return false;
if (i<1 || i>L->data) {
printf("The position of the element to be deleted is invalid!\n");
*e = 9999;
return false;
//[2]删除指定元素
LNode* p = GetElem(L, i - 1);//带删除元素前驱结点
LNode* q = p->next;//待删除元素
p->next = q->next;
*e = q->data;
free(q);
L->data--;
return true;
//【13】销毁单链表
//从头开始，一直删除第一个即可
bool DestroyLinkList(LinkList L) {
int e;//e没有太大意义
while (L->data) {
LocalDeletElem(L, 1,&e);
PrintLinkList(L);//为了显示出代码的变化
free(L);
return true;
int main() {
LinkList L;
/*注意这是个指针，指针一定要进行初始化，使其指向某个空间。
如果没有实体化，接下来也无法使用初始化函数
（C6001 使用未初始化的内存“L”。）
所以把malloc初始化部分放在主函数中
L = (LNode*)malloc(sizeof(LNode));//分配空间后强制转化为LNode类型
InitLinkList(L);
//HeadInsertLinkList(L);
//PrintLinkList(L);
TailInsertLinkList(L);
PrintLinkList(L);
//printf("L[4]=%d", GetElem(L, 4)->data);
//printf("L[4]=%d",LocateElem(L, 4)->data);
//LocateInsertElem(L, 1, 1000);
//PrintLinkList(L);
/*ElemType e;
LocalDeletElem(L, 2, &e); \
printf("e=%d\n", e);
PrintLinkList(L);*/
DestroyLinkList(L);
return 0;
关于栈和队列的形象表示，见如上文章。
栈和队列常见的操作
核心操作：入队、出队、遍历
顺序栈
#define _CRT_SECURE_NO_WARNINGS 1
// 栈的数据结构
// 出栈
// 入栈
// 判栈空
// 读栈顶
// 【1】预编译部分
#include<stdio.h>
#include<stdlib.h>
// 【2】宏定义部分
#define bool char
#define true 1
#define false 0
// 【3】 自定义变量部分
#define MaxSize 50 //定义栈中元素的最大个数
// 【4】顺序栈数据结构
typedef int Elemtype;
typedef struct SqStack {
Elemtype data[MaxSize];//存数据的数组就有了
int top;//栈顶指针始终指向最上方(对于数组而言，这里把下标叫为了指针)
}SqStack;//用typedef定义一下在C语言中之后使用SqStack就不用再加struct了
// 【5】顺序栈初始化（只是使栈顶指针=-1即可）
bool Initstack(SqStack* S) {
S->top = -1;//初始化栈顶指针（判空条件S->top=-1）
return true;
//【6】判栈空
bool StackEmpty(SqStack S) {
if (S.top == -1)
return true;//栈空
return false;//栈不空
// 【8】进栈（压栈）
//①当栈不满时，②top+1使栈顶指针指向下一个存储空间③入栈
bool Push(SqStack* S, Elemtype e) {
if (S->top == MaxSize - 1)
return false;
S->data[++S->top] = e; //指针先+1，再入栈
return true;
//【9】出栈
//①当栈不空时，②top-1使栈顶指针指向上一个存储空间③出栈
bool Pop(SqStack* s, Elemtype *e) {//e的作用是返回所弹出栈的值的
if (StackEmpty(*s))
return false;
*e = s->data[s->top--];//先出栈指针再-1
return true;
//【读栈顶元素】
bool GetTop(SqStack S, Elemtype* e) {//只有需要对顺序栈进行更改时才需要使用指针
if (StackEmpty(S))
return false;
*e = S.data[S.top];
return true;
int main() {
SqStack S;
Initstack(&S);
Push(&S, 1);
Push(&S, 2);
Push(&S, 3);
Push(&S, 4);
Push(&S, 5);
Push(&S, 6);
Elemtype x;//用于保存出栈和读栈顶元素返回元素的值
int count = S.top;
for (int i = 0; i <= count; i++) {
printf("i=%d\n", i);//看一下在第几层循环内
GetTop(S, &x);
printf("GetTop x=%d\n",x);
Pop(&S, &x);
printf("Pop x=%d\n", x);
return 0;
链栈
#define _CRT_SECURE_NO_WARNINGS 1
//【1】预处理部分
#include<stdio.h>
#include<stdlib.h>
//【2】宏定义部分
#define bool char
#define true 1
#define false 0
//【3】链栈的数据结构
//知识点：
// 链表的头指针可以当作链栈的栈顶指针
// 链栈也可以有头节点，只不过后来会被压入栈的底部
//链栈的每个结点也是有一个data域，一个指针域
typedef int Elemtype;
typedef struct StackNode {
Elemtype data;
struct StackNode* next;
} StackNode,* LinkStackPtr;//定义每一个结点的结构
//【4】初始化头节点
void InitStack(LinkStackPtr &L) {//1、加引用 2、return
/*说明：函数只能单向传递参数的值.对于普通变量通过指针来传出；但是如果参数本身就是指针，就要通过C++中的引用或者return语句来传出来*/
L=(StackNode *)malloc(sizeof(StackNode));
//知识点：malloc函数开辟连续可用空间（开辟成功，返回一个指向开辟空间的指针；开辟不成功，返回NULL）所以malloc的返回值一定要做检查
if (L == NULL)//检查是否开辟空间成功
printf("Not enough space！");
else {
L->data = 0;
L->next = NULL;
//【5】判断是否为空栈
bool IsEmpty(StackNode* S) {
if (S->data == 0)//S->data == 0 || S->data == NULL会warning：代码冗余，所以去掉一个
return true;
return false;
//【6】压栈
void push(StackNode* L, int data) {//要传入函数之前栈的栈顶指针以及要压入的数据
//[1]创建新结点并为新结点分配内存空间
StackNode* NewNode = (StackNode*)malloc(sizeof(StackNode));
if(NewNode==NULL)
printf("Not enough space！");
else{ //[2]传入数据,变换指针
NewNode->data = data;
NewNode->next = L->next;
L->next = NewNode;
L->data++;}
//【7】弹栈(删除指针所指向的结点，并返回该结点的值)
Elemtype Pop(StackNode* L) {//还是把头结点传进去
//[1]判断是否为空链栈
if(IsEmpty(L)){
return 0;
//[2]
else {
StackNode* node=L->next;
Elemtype data = node->data;
L->next = node->next;
free(node);
L->data--;
return data;
//【8】输出链栈
bool PrintLinkStack(StackNode* stack) {
StackNode* node = stack->next;//用node来存放stack的下一个结点
while (node) {
printf("%d -->", node->data);
node = node->next;
printf("NULL\n");
return true;
//【9】主函数
int main() {
StackNode* stack;
InitStack(stack);
push(stack, 1);
push(stack, 2);
push(stack, 3);
push(stack, 4);