数据结构零基础入门篇(C语言实现)

简介: 数据结构零基础入门篇(C语言实现)

前言:数据结构属于C++学习中较难的一部分,对应学习者的要求较高,如基础不扎实,建议着重学习C语言中的指针和结构体,万丈高楼平地起。



 

一,链表

1)单链表的大致结构实现

用C语言实现链表一般是使用结构体,首先我们可以通过链表的结构特性反推结构体的成员。单链表是只能通过前一个节点找到下一个节点,并且是单向的,每一个节点还要存储数据元素,我们实现这个的手段是指针,因此我们需要在前一个结点存储下一个地址。

typedef int SLTDateType;//方便以后修改链表类型
typedef struct STLListNode {
  SLTDateType n;
  struct STLListNode* next;
}SListNode;//减少代码的冗余
2)单链表的思考(然后找到链表和判断链表的结束)

首先是如何找到链表的第一个元素,每次,我们之前的图上给了提示,我们可以用一个head指针来标记第一个结点,但有一个很大的注意事项,我们不能随便改变head的地址,不然我们将会无法找到这个链表。

那如何判断链表的结束呢,看上面的手绘图,最后一个结点所指向的是NULL指针,根据这个特点我们就可以判断链表的结束。

注:我们为什么要考虑这两个问题是因为如果我们不严格的控制指针的指向,当指针指向为开辟的空间,会导致程序出现各种意外甚至无法运行。

3)单链表的程序实现及源代码讲解
1)链表的实现前提准备
#include<stdio.h>
#include<assert.h>
typedef int SLTDateType;//方便以后修改链表类型
typedef struct STLListNode {
  SLTDateType n;
  struct STLListNode* next;
}SListNode;//减少代码的冗余
2)单链表的创建及初始化
SListNode* BuySListNode(SLTDateType x);
SListNode* BuySListNode(SLTDateType x) {
  SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));//分配内存空间
  assert(newnode);//防止分配失败导致的访问非法空间
  newnode->n= x;
  return newnode;//返回创建空间地址
}
3)单链表的尾插

void SListPushBack(SListNode** pplist, SLTDateType x);
void SListPushBack(SListNode** pplist, SLTDateType x) {//链表要传地址用二级指针接受,因为头插的时候是要改变链表的地址,是需要二级指针才能改变一级指针
  SListNode* ptemp = *pplist;
  SListNode** plist = pplist;//防止头指针丢失
  if (*plist == NULL) {
    *plist = BuySListNode(x);
    (*plist)->next = NULL;
    return;
  }//如果是空链表需要单独处理
  while ((*plist)->next != NULL) {
    *plist = (*plist)->next;
  }//找到尾节点
  (*plist)->next  = BuySListNode(x);//分配一个新空间
  (*plist)->next->next = NULL;//置空方便下次找尾结点
  *pplist = ptemp;//维持头指针
}
4)单链表的头插

void SListPushFront(SListNode** pplist, SLTDateType x) {//要改变头指针的地址,需要二级指针
  if (*pplist == NULL) {
    *pplist = BuySListNode(x);
    (*pplist)->next = NULL;
    return;//如果链表为空,单独处理
  }
  SListNode* plist= BuySListNode(x);//分配空间
  plist->next = (*pplist);//将新结点的next指针指向原来的头指针
  *pplist = plist;//改变头指针
}
5)单链表的头删

void SListPopFront(SListNode** pplist){
  assert(*pplist);//判断是否为空链表,防止访问非法空间
  SListNode* plist = *pplist;
  *pplist = (*pplist)->next;//保留新头
  plist->next = NULL;//老的头指针置空,防止通过这个非法访问
  free(plist);//释放老头指针空间
}
6)单链表的尾删

void SListPopBack(SListNode** pplist) {
  assert(*pplist);//判断是否为空链表,防止访问非法空间
  SListNode* plist = (*pplist);//保存头指针,防止丢失
  if (plist->next == NULL) {
    free(plist);
    plist = NULL;
  }//如果只有一个元素,直接释放
  while (plist->next->next != NULL) {
    plist = plist->next;
  }//找到尾结点
  free(plist->next);
  plist->next = NULL;//置空
}
7)在单链表中查找元素
SListNode* SListFind(SListNode* plist, SLTDateType x) {
  assert(plist);//判断是否为空链表,防止访问非法空间
  while (plist->next != NULL) {
    if (plist->n = x)
      return plist;//如果找到直接返回地址
    plist = plist->next;//否则下一个
  }
  return NULL;//找到了尾结点都没找到,返回空指针
}
8)单链表指定结点的后面插入和删除元素
void SListInsertAfter(SListNode* pos, SLTDateType x) {
  assert(pos);//判断是否为空链表,防止访问非法空间
  SListNode* temp = pos->next;
  pos->next = BuySListNode(x);
  pos->next->next = temp;
}
void SListEraseAfter(SListNode* pos) {
  assert(pos);//判断是否为空链表,防止访问非法空间
  assert(pos->next );//判断是否有下一个元素
  SListNode* temp = pos->next;
  pos->next = pos->next->next;//改变前一个指针的next指针,防止断层
  free(temp);
}
9)单链表的内存销毁
void SListDestroy(SListNode* plist) {
  assert(plist);//防止多次释放空间
  SListNode* cur = plist->next;//记录当前指针,因为当前指针释放后无法访问到下一个指针的地址
  while (cur) {
    free(plist);
    plist = cur;
    cur = plist->next;
  }
  plist = NULL;
}
2)带头双向循环链表的提示(自己实现)

与单链表相比,带头双向循环链表,会有多开辟一个空间,不用来存储数据,用来指向head指针,这样可以简化许多操作。还要多一个指针指向前一个结点,并且尾指针不在置空,而且指向第一个结点。

二,队列和栈

1)队列特性

就像如图的核酸检测,你先进入队列,你就能比别人先做完核酸离开。因此队列的特性是先进先出。

2)栈的特性

栈的特性就像往一个一次只能拿出一个石头的瓶子里面投石头,你想要拿到最下面的石头你就需要先拿出前面所有的石头,因此栈的特性就是先进后出。

3)队列用链表实现(源代码及详细讲解)
1)队列结构和功能实现前准备

和链表一样,我们队列也使用结构体指针的方法实现,与链表实现大同小异,但会有一个另外的结构体用来存储队列的第一个元素指针的地址,和最后一个元素指针的地址,这样方便我们接下来的各个功能实现,可以省下很多代码量。

#include<stdio.h>
#include<assert.h>
typedef int QDataType;//方便以后将队列修改为其他类型
typedef struct QListNode
{
  struct QListNode* _next;//下一个队列的指针
  QDataType _data;//数据元素
}QNode;//减少代码长度
typedef struct Queue
{
  QNode* _front;//队列第一个元素指针
  QNode* _rear;//队列最后一个元素指针
}Queue;
2)初始化队列
void QueueInit(Queue* q) {
  q->_front = (QNode*)malloc(sizeof(QNode));//开辟空间
  q->_front->_data = -1;//数据随意初始化
  q->_rear = q->_front ;//此时只有一个元素,头和尾相等
}
3)入列数据
void QueuePush(Queue* q, QDataType data) {
  q->_rear->_data = data;//从尾开始入列
  q->_rear->_next = (QNode*)malloc(sizeof(QNode));//给下一个队列分配空间
  q->_rear = q->_rear->_next;//移动尾指针
}
4)出列数据
void QueuePop(Queue* q) {
  assert(q->_front!=q->_rear );//防止出列空队列
  QNode* list = q->_front ;//保存头指针,防止丢失
  while (list->_next != q->_rear) {
    list = list->_next;
  }//找到尾指针
  free(q->_rear);//释放尾指针
  q->_rear = list;//重新恢复尾指针
}
5)获取队列头部元素
QDataType QueueFront(Queue* q) {
  assert(q->_front != q->_rear);
  return q->_front->_data;
}
6)获取队列尾部元素
QDataType QueueBack(Queue* q) {
  assert(q->_front != q->_rear);//判断是否有至少两个元素,防止数组越界
  QNode* list = q->_front;//保存头指针,防止丢失
  while (list->_next != q->_rear) {
    list = list->_next;
  }//找到尾结点,队列最后一个元素指针
  return list->_data;
}
7)销毁队列元素
void QueueDestroy(Queue* q) {
  while (q->_front != q->_rear) {
    QNode* list = q->_front;//利用list来销毁上一个指针,防止销毁之后找不到下一个元素
    q->_front = q->_front->_next;//头指针换为下一个元素
    free(list);//销毁
  }
  free(q->_rear);//不要忘记还落下了一个尾结点
  q->_front = NULL;
  q->_rear = NULL;//置空,防止非法访问
}
4)栈的代码实现(提供另外一种思路,自己实现)

之前说过栈就像往一次只够拿一个石头的瓶子里放石头和取石头,有没有发现栈和数组有很大的相似,当我们打开这个思路,我们会发现如果用数组实现的话,我们的代码思路和代码量突然就小了很多。我这里只提供结构和功能实现前的准备,其他望诸君自己勤练。

#include<stdio.h>
#include<assert.h>
// 支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{
  STDataType* _a; //到时候用maolloc开辟空间,可以随时调节数组大小
  int _top;   // 栈顶
  int _capacity;  // 容量 
}Stack;

最后言:数据结构是需要大量题目来练手的,单纯的理论知识是纸上谈兵,真正实现的时候是变化万千。牢记:纸上得来终觉浅,绝知此事要躬行。

目录
打赏
0
0
0
0
10
分享
相关文章
【趣学C语言和数据结构100例】11-15
本文介绍了五个C语言编程问题及其实现,包括矩阵对角线元素之和、有序数组插入、数组逆序、杨辉三角输出和魔方阵生成。每个问题不仅涉及基本的数组操作,还涵盖了算法设计的核心思想,如循环、条件判断和递归。通过解决这些问题,读者可以加深对C语言和数据结构的理解,提升编程技能。这些问题的解决过程展示了如何有效处理数组和矩阵,以及如何利用算法优化程序性能,为实际应用提供了宝贵的实践经验。
70 4
【趣学C语言和数据结构100例】11-15
C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合
本文深入解析了C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合,旨在帮助读者掌握这一高效的数据处理方法。
68 1
【趣学C语言和数据结构100例】91-95
本文涵盖多个经典算法问题的C语言实现,包括堆排序、归并排序、从长整型变量中提取偶数位数、工人信息排序及无向图是否为树的判断。通过这些问题,读者可以深入了解排序算法、数据处理方法和图论基础知识,提升编程能力和算法理解。
65 4
【趣学C语言和数据结构100例】86-90
本文介绍并用C语言实现了五种经典排序算法:直接插入排序、折半插入排序、冒泡排序、快速排序和简单选择排序。每种算法都有其特点和适用场景,如直接插入排序适合小规模或基本有序的数据,快速排序则适用于大规模数据集,具有较高的效率。通过学习这些算法,读者可以加深对数据结构和算法设计的理解,提升解决实际问题的能力。
54 4
【趣学C语言和数据结构100例】81-85
本文介绍了五个经典算法问题及其C语言实现,涵盖图论与树结构的基础知识。包括使用BFS求解单源最短路径、统计有向图中入度或出度为0的点数、统计无向无权图各顶点的度、折半查找及二叉排序树的查找。这些算法不仅理论意义重大,且在实际应用中极为广泛,有助于提升编程能力和数据结构理解。
56 4
【趣学C语言和数据结构100例】76-80
本文介绍了五种图论算法的C语言实现,涵盖二叉树的层次遍历及广度优先搜索(BFS)和深度优先搜索(DFS)的邻接表与邻接矩阵实现。层次遍历使用队列按层访问二叉树节点;BFS利用队列从源节点逐层遍历图节点,适用于最短路径等问题;DFS通过递归或栈深入图的分支,适合拓扑排序等场景。这些算法是数据结构和算法学习的基础,对提升编程能力和解决实际问题至关重要。
58 4
|
2月前
|
【趣学C语言和数据结构100例】71-75
本文介绍了五个C语言数据结构问题及其实现,涵盖链表与二叉树操作,包括按奇偶分解链表、交换二叉树左右子树、查找节点的双亲节点、计算二叉树深度及求最大关键值。通过递归和遍历等方法,解决了理论与实际应用中的常见问题,有助于提升编程能力和数据结构理解。
50 4
|
2月前
|
【趣学C语言和数据结构100例】66-70
本书《趣学C语言和数据结构100例》精选了5个典型的数据结构问题及C语言实现,涵盖链表与数组操作,如有序集合的集合运算、有序序列表的合并、数组中两顺序表位置互换、三递增序列公共元素查找及奇偶数重排。通过详细解析与代码示例,帮助读者深入理解数据结构与算法设计的核心思想,提升编程技能。
39 4
|
2月前
|
【趣学C语言和数据结构100例】51-55
本文介绍了五个关于链表操作的C语言实现案例,包括删除单链表中的重复元素、从两个有序链表中查找公共元素、判断一个链表是否为另一链表的连续子序列、判断循环双链表是否对称及合并两个循环单链表。每个案例都详细解析了算法思路与实现方法,涵盖了链表操作的多种场景,旨在帮助读者深入理解链表数据结构的应用,提升算法设计与编程能力。
50 4
|
2月前
|
【趣学C语言和数据结构100例】16-20
本文精选了五个C语言编程问题,涵盖数组操作、字符串处理等基础领域。包括查找二维数组中的鞍点、折半查找法、统计文章中字符数量、电文解密及字符串连接。每个问题都附有详细的代码实现与分析,旨在帮助读者理解算法逻辑,提升编程技巧。通过这些实践,不仅能锻炼编程能力,还能加深对数据结构和算法的理解,为未来的学习和工作打下坚实基础。
70 4

热门文章

最新文章