数据结构(1)数据结构基础(单向链表)

2024-09-04 05:20

本文主要是介绍数据结构(1)数据结构基础(单向链表),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

一、什么是数据结构

        数据结构是一组用来保存一种或多种特定关系的数据的集合。其主要目的是组织和存储数据,以便于高效的访问和修改。在程序设计中,将大量而复杂的问题以特定的数据类型和特定的存储结构存储在内存中,并在此基础上实现某个特定的功能的操作,即:

                                程序 = 数据结构 + 算法

二、 数据与数据之间的关系

2.1 数据的逻辑结构
  • 集合:数据元素之间关系平等,常用于处理无关元素的组。
  • 线性结构:元素之间存在一对一的关系,常见的有数组、链表、队列、栈等。
  • 树型结构:元素之间存在一对多的关系,典型的如二叉树。
  • 图形结构:元素之间存在多对多的关系,形成网络状的结构。
2.2 数据的物理结构

数据的逻辑结构在计算机内存中的存储方式是其物理结构,主要包括以下几种存储方式:

  • 顺序存储
    • 利用一段连续的内存空间来保存元素。
    • 优点
      • 空间连续,访问方便(如随机访问)。
    • 缺点
      • 插入与删除操作需要移动大量元素。
      • 需要预分配内存空间。
      • 容易造成存储空间碎片。
  • 链式存储
    • 使用非连续的内存空间保存元素。
    • 优点
      • 插入和删除数据方便。
      • 不需要预分配内存。
    • 缺点
      • 访问元素的效率低。
  • 索引存储
    • 通过关键字构建索引表,通过该索引表找到数据的存储位置。
  • 散列存储(哈希存储)
    • 将数据元素的存储位置与关键码之间建立确定对应关系,以实现快速查找。

三、储备知识

  • 指针:用于存储其他变量的地址,是链式存储结构的关键。
  • 结构体:在编程中,常用结构体定义数据节点,便于管理数据。
  • 动态内存分配:为数据结构中的节点动态分配和释放内存。

四、 链式数据结构:单向链表

4.1 定义

        单向链表是一种线性数据结构,由一系列节点构成,每个节点包含数据部分和指向下一个节点的指针。它是一种灵活的存储方式,相比于数组,单向链表不需要连续的内存空间。

4.2 结构
  • 节点(Node)

    • 数据部分:存储实际的数据。
    • 指针部分:指向下一个节点的指针。
  • 链表头(Head)

    • 链表的起始节点,所有操作通常从此节点开始。
  • 尾节点(Tail)

    • 链表的最后一个节点,其指针部分为空,表示链表的结束。
4.3 主要操作
  • 插入操作

    • 在头部:创建新节点,将其指针指向当前头节点,然后更新头节点。
    • 在尾部:遍历找到最后节点,令其指向新节点,并将新节点的指针设为 null
    • 在指定位置:找到插入位置的前一节点,将新节点连接至该位置。
  • 删除操作

    • 删除头节点:更新头节点为当前头节点的下一个节点。
    • 删除尾节点:遍历找到倒数第二个节点,更新其指针为 null
    • 删除特定位置节点:找到前一节点,调整指针跳过待删除节点。
  • 查找操作

    • 从头节点开始遍历链表,逐个比较数据部分查找特定值。
4.4 优缺点
  • 优点
    • 动态存储,插入和删除方便。
  • 缺点
    • 存储开销大(每个节点额外的指针)。
    • 访问效率低(需要遍历)。

示例:

// 定义数据类型为整型  
typedef int Datatype;  // 定义链表节点结构  
typedef struct node  
{  Datatype data; // 节点存储的数据  struct node * pnext; // 指向下一个节点的指针  
} node_t;  // 定义链表结构  
typedef struct link  
{  struct node* phead; // 指向链表头节点的指针  int clen; // 链表中节点的数量  
} link_t;// 创建链表  
link_t* create_link()  
{  // 分配内存给链表结构  link_t * plink = malloc(sizeof(link_t));  if(NULL == plink )  {  perror("create link error"); // 内存分配失败  return NULL;  }  plink->phead = NULL; // 初始化头指针为空  plink->clen = 0; // 初始化链表长度为0  return plink; // 返回新创建的链表  
}  // 在链表头部插入新节点  
int push_into_link_head(link_t* plink, Datatype data)  
{  // 分配内存给新节点  node_t* pnode = malloc(sizeof(node_t));  if(NULL == pnode)  {  perror("push node error"); // 内存分配失败  return -1;  }  pnode->data = data; // 设置节点数据  pnode->pnext = plink->phead; // 新节点指向当前头节点  plink->phead = pnode; // 更新头节点为新节点  plink->clen++; // 增加链表长度  return 0; // 成功  
}  // 遍历并打印链表中的所有节点数据  
int traverse_print_link(link_t* plink)  
{  node_t* p = plink->phead; // 从头节点开始  while(p)  {  printf("%d ", p->data); // 打印节点数据  p = p->pnext; // 移动到下一个节点  }  printf("\n"); // 打印换行  return 0; // 成功  
}  // 在链表尾部插入新节点  
int push_into_link_tail(link_t * plink, Datatype data)  
{  // 分配内存给新节点  node_t * pnode = malloc(sizeof(node_t));  pnode->data = data; // 设置节点数据  pnode->pnext = NULL; // 新节点的下一个指针为空  if(plink->phead == NULL) // 如果链表为空  {  plink->phead =  pnode; // 头指针指向新节点  }  else  {  node_t* p = plink->phead; // 从头节点开始遍历  while(p->pnext) // 找到最后一个节点  {  p = p->pnext;  }  p->pnext = pnode; // 将最后一个节点的指针指向新节点  }  plink->clen++; // 增加链表长度  return 0; // 成功  
}  // 从链表头部删除节点  
int pop_into_link_head(link_t* plink)  
{  if(NULL == plink->phead) // 如果链表为空  {  return 0; // 无需删除  }  else  {  node_t *pnode = plink->phead; // 获取头节点  plink->phead = pnode->pnext; // 更新头节点为下一个节点  free(pnode); // 释放原头节点内存  }  plink->clen--; // 减少链表长度  return 0; // 成功  
}  // 从链表尾部删除节点  
int pop_into_link_tail(link_t* plink)  
{  if(NULL == plink->phead) // 如果链表为空  {  return 0; // 无需删除  }  else if(plink->phead->pnext == NULL) // 如果只有一个节点  {  pop_into_link_head(plink); // 删除头节点  }  else  {  node_t * pnode = plink->phead; // 从头节点开始遍历  while(pnode->pnext->pnext) // 找到倒数第二个节点  {  pnode = pnode->pnext;  }  free(pnode->pnext); // 释放最后一个节点内存  pnode->pnext = NULL; // 将倒数第二个节点的指针设为NULL  plink->clen--; // 减少链表长度  return 0; // 成功  }  return 0; // 成功  
}  // 在链表中查找特定数据的节点  
node_t * search(link_t* plink, Datatype data)  
{  node_t* pnode = plink->phead; // 从头节点开始  while(pnode)  {  if(pnode->data == data) // 如果找到数据  {  return pnode; // 返回该节点  }  pnode = pnode->pnext; // 移动到下一个节点  }  return NULL; // 未找到  
}  // 修改链表中指定数据的节点数据  
int change_link_data(link_t* plink, Datatype srcdata, Datatype destdata)  
{  node_t * node = search(plink, srcdata); // 查找源数据节点  node->data = destdata; // 修改节点数据  return 0; // 成功  
}  // 销毁链表,释放所有节点内存  
int destory_link(link_t* plink)  
{  while(plink->phead) // 当链表不为空  {  pop_into_link_head(plink); // 删除头节点  }  free(plink); // 释放链表结构内存  return 0; // 成功  
}  // 查找链表中的中间节点  
node_t * search_mid_node(link_t * plink)  
{  node_t * pnode = plink->phead; // 从头节点开始  if(NULL == pnode) // 如果链表为空  {  return NULL; // 返回NULL  }  if(plink->clen == 1) // 如果只有一个节点  {  return pnode; // 返回该节点  }  int i = 0;  while(pnode)  {  pnode = pnode->pnext; // 移动到下一个节点  i++;  if(i == (plink->clen) / 2) // 找到中间节点  {  break;  }  }  return pnode; // 返回中间节点  
}  // 从链表中查找倒数第number个节点  
node_t *search_countdown(link_t* plink, int number)  
{  node_t* pnode = plink->phead; // 从头节点开始  if(NULL == pnode) // 如果链表为空  {  return NULL; // 返回NULL  }  if(plink->clen == 1) // 如果只有一个节点  {  if(number == 1)  {  return pnode; // 返回该节点  }  return NULL; // 返回NULL  }  int i = 0;  while(pnode)  {  pnode = pnode->pnext; // 移动到下一个节点  i++;  if(i == (plink->clen) - number) // 找到倒数第number个节点  {  break;  }  }  return pnode; // 返回该节点  
}  // 删除指定位置的节点  
int pop_appointed_node(link_t* plink, int appointed)   
{  if (plink->phead == NULL) // 如果链表为空  {  return -1; // 返回错误  }  if (appointed < 1 || appointed > plink->clen) // 如果指定位置不合法  {  return -1;   }  node_t* pnode = plink->phead;    if (appointed == 1) // 如果删除的是头节点  {  pop_into_link_head(plink); // 删除头节点  return 0;  }  for (int i = 1; i < appointed - 1; i++) // 遍历到指定位置的前一个节点  {  pnode = pnode->pnext;   }  node_t* temp = pnode->pnext; // 获取要删除的节点  if (temp == NULL) // 如果要删除的节点不存在  {  return -1;  }  pnode->pnext = temp->pnext; // 将前一个节点的指针指向要删除节点的下一个节点  free(temp); // 释放要删除节点的内存  plink->clen--; // 减少链表长度  return 0; // 成功  
}

这篇关于数据结构(1)数据结构基础(单向链表)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1135105

相关文章

MySQL中my.ini文件的基础配置和优化配置方式

《MySQL中my.ini文件的基础配置和优化配置方式》文章讨论了数据库异步同步的优化思路,包括三个主要方面:幂等性、时序和延迟,作者还分享了MySQL配置文件的优化经验,并鼓励读者提供支持... 目录mysql my.ini文件的配置和优化配置优化思路MySQL配置文件优化总结MySQL my.ini文件

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

csu1329(双向链表)

题意:给n个盒子,编号为1到n,四个操作:1、将x盒子移到y的左边;2、将x盒子移到y的右边;3、交换x和y盒子的位置;4、将所有的盒子反过来放。 思路分析:用双向链表解决。每个操作的时间复杂度为O(1),用数组来模拟链表,下面的代码是参考刘老师的标程写的。 代码如下: #include<iostream>#include<algorithm>#include<stdio.h>#

零基础学习Redis(10) -- zset类型命令使用

zset是有序集合,内部除了存储元素外,还会存储一个score,存储在zset中的元素会按照score的大小升序排列,不同元素的score可以重复,score相同的元素会按照元素的字典序排列。 1. zset常用命令 1.1 zadd  zadd key [NX | XX] [GT | LT]   [CH] [INCR] score member [score member ...]

6.1.数据结构-c/c++堆详解下篇(堆排序,TopK问题)

上篇:6.1.数据结构-c/c++模拟实现堆上篇(向下,上调整算法,建堆,增删数据)-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小): 2.2 C语言代码(手写堆) 2.3 C++代码(使用优先级队列 priority_queue)

【Linux 从基础到进阶】Ansible自动化运维工具使用

Ansible自动化运维工具使用 Ansible 是一款开源的自动化运维工具,采用无代理架构(agentless),基于 SSH 连接进行管理,具有简单易用、灵活强大、可扩展性高等特点。它广泛用于服务器管理、应用部署、配置管理等任务。本文将介绍 Ansible 的安装、基本使用方法及一些实际运维场景中的应用,旨在帮助运维人员快速上手并熟练运用 Ansible。 1. Ansible的核心概念

深入手撕链表

链表 分类概念单链表增尾插头插插入 删尾删头删删除 查完整实现带头不带头 双向链表初始化增尾插头插插入 删查完整代码 数组 分类 #mermaid-svg-qKD178fTiiaYeKjl {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-

AI基础 L9 Local Search II 局部搜索

Local Beam search 对于当前的所有k个状态,生成它们的所有可能后继状态。 检查生成的后继状态中是否有任何状态是解决方案。 如果所有后继状态都不是解决方案,则从所有后继状态中选择k个最佳状态。 当达到预设的迭代次数或满足某个终止条件时,算法停止。 — Choose k successors randomly, biased towards good ones — Close

建立升序链表

题目1181:遍历链表 时间限制:1 秒 内存限制:32 兆 特殊判题:否 提交:2744 解决:1186 题目描述: 建立一个升序链表并遍历输出。 输入: 输入的每个案例中第一行包括1个整数:n(1<=n<=1000),接下来的一行包括n个整数。 输出: 可能有多组测试数据,对于每组数据, 将n个整数建立升序链表,之后遍历链表并输出。 样例输

《数据结构(C语言版)第二版》第八章-排序(8.3-交换排序、8.4-选择排序)

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多,算法平均时间性能比直接插入排序差。当初始记录无序,n较大时, 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In