【单向链表】数据结构——单向链表的介绍与代码实现&笔记

简介: 【单向链表】数据结构——单向链表的介绍与代码实现&笔记

一、数据结构

1、什么是数据结构?

数据结构:计算机存储,组织数据的方式,数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。

简单来说:程序 = 数据结构 + 算法

2、逻辑结构和物理结构

1)逻辑结构:研究数据结构之间的逻辑关系

线性结构

②非线性结构

树状结构、集合结构、图状结构

2)物理结构:数据在物理内存上的存储形式(连续、非连续)

好了概念就介绍到这里,下面我们进入今天的正文——链表的学习

二、链表——线性结构

1、首先介绍下链表和数组的区别

1)数组:

  • 数组空间是连续的,每个元素存储的类型都是一样的。
  • 通过数组名+下标访问数组成员。
  • 数组大小固定,在定义之后不允许重新改变数组大小,对数组的增加元素减少元素比较麻烦,效率低。

2)链表:

  • 链表存储空间不连续
  • 没有固定的大小,添加节点和删除节点非常方便
  • 链表的大小不固定,是通过一系列的节点组成,链表节点就是链表用来存放数据的结构,本质是一个结构体。
  • 链表的前后成员是通过指针来寻找的,所以想要删除一个链表成员 只要找到它,free掉其空间,前后链式关系上,可以让删除节点前后成员直接连接
  • 增加成员,除了在堆空间malloc外,在链表成员前后关系,只要处理好成员间的链接关系 即可在链表任意位置上添加新成员-----灵活
  • 成员的访问因为是通过指针寻找再访问的,访问速度会很慢(相对于数组来说)

2、链表的结构示意图


2、链表节点——节点本身是一个结构体

节点结构体分为两个区域:

数据域:存放数据

指针域:存放指向下一个成员或上一个成员的地址

例子:

记录图书馆的所有图书信息

typedef struct book
{
//数据域
char bookname[64];//书名
char Author[32];//作者
float  price;//价格

//指针域
struct book *next;//指向下个和当前类型一致的成员
}BOOK,*pBOOK;

3、单向链表的一般性结构

4、单向链表节点的添加——插入节点

头插法:新的节点插入到头节点的下一个

尾插法:新的节点插入到最后一个节点的下一个

5、单向链表节点的查找——查找结点

6、单向链表删除节点

步骤:

1)遍历链表,找到需要被删除的节点p以及他的前一个节点q

2)从逻辑上删除节点p:q->next = p->next

3)从物理上删除节点p:free§

7、单向链表节点的销毁

遍历链表,销毁每一个节点

步骤:

1)使用两个指针对链表进行遍历:p(销毁节点)、q(记录p的下一个节点的地址)

2)释放节点空间free(p)

Node *p, *q;
p = head;
q = p->next;
while(q != NULL)  //释放head后面所有节点
{
  p = q;
  q = q->next;
  free(p);
}
free(head); //最后释放头节点

8、最后附上示例代码

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
//0,设计链表节点
typedef struct node{
  int data;     //数据域
  struct node *next;  //指针域
}Node;    //Node 等价于  struct node

//1,创建链表  -->创建一个链表头
Node *List_Create(void)
{
  //1)对链表头结点空间申请 --> malloc
  Node *list = (Node *)malloc(sizeof(Node));
  if ( list == NULL )
  {
    perror("malloc failed "); //打印出错信息
    return NULL;        //结束函数
  }

  //2)对链表头结点进行赋值
  list->next = NULL;  

  //3)返回链表头结点地址
  return list;  
}

//2,链表节点插入 (头插法)
bool List_Add_Node_Head(Node *head, int data)
{
  //1)给新节点申请堆内存
  Node *newnode = (Node *)malloc(sizeof(Node));
  if (newnode == NULL)
  {
    perror("newnode malloc failed");
    return false;
  }

  //2)新节点赋值
  newnode->data = data;
  newnode->next = NULL;

  //3)头插法插入链表
  newnode->next = head->next;
  head->next = newnode;

  return true;
}
//尾插法
bool List_Add_Node_End(Node *head, int data)
{
  //1)给新节点申请堆内存
  Node *newnode = (Node *)malloc(sizeof(Node));
  if ( newnode == NULL)
  {
    perror("malloc newnode failed");
    return false;
  }

  //2)给新节点赋值
  newnode->data = data;
  newnode->next = NULL;

  //3)尾插法插入链表
    //找到链表的最后一个节点 p (while(p->next !=NULL)p=p->next)
  Node *p = head;
  while(p->next != NULL)    //当这个循环结束时,p节点就是最后一个节点
  {
    p = p->next;
  }
    //新节点插入到p节点的后面
  p->next = newnode;
  return true;
}


//3,链表数据输出
void List_Display(Node *head)
{
  //1)定义一个指针用来遍历链表
  Node *p = head->next; //头结点不存放数据
  printf("链表数据:");
  //2)遍历链表,输出链表中的每一个节点的数据
  while(p != NULL)
  {
    printf("%d ", p->data);
    p = p->next;    //把p节点下一个节点的地址赋值给p
  }
  printf("\n");
}

//4,链表节点查找
int List_Search(Node *head, int data)
{
  int i = 1;
  Node *p = head->next;   //遍历链表指针
  while(p != NULL)
  {
    if(p->data == data) //找到这个节点
    {
      printf("Find Node[%d]!\n", i);
      //return i; //返回序号值
    }
    p = p->next;
    i++;
  }
  //printf("No such Node!\n");
  return 0;
}

//5,链表节点删除 ==>删除节点时只能删除一个节点,思考:如何同时删除多个节点?
bool List_Remove(Node *head, int data)
{
  int i = 1;
  //1)找到需要被删除的节点p和p的前一个节点q
  Node *p = head->next;
  Node *q = head;   //q是p的前一个节点

  while(p != NULL)
  {
    if(p->data == data)//2)找到之后,删除节点p
    {
      q->next = p->next;  //从逻辑上删除p节点
      free(p);
      printf("删除节点[%d]成功!\n", i);
      return true;
    }
    q = q->next;  //遍历链表
    p = q->next;
    i++;
  }
  //3)如果遍历完链表都没有找到,那就说明链表中没有这个节点
  printf("链表中没有这个节点!\n");
  return false;
}
//6,删除链表中所有节点数据 data的节点
bool List_Remove_All(Node *head, int data)
{
  int i = 1;
  //1)找到需要被删除的节点p和p的前一个节点q
  Node *p = head->next;
  Node *q = head;   //q是p的前一个节点

  while(p != NULL)
  {
    if(p->data == data)//2)找到之后,删除节点p
    {
      q->next = p->next;  //从逻辑上删除p节点
      free(p);
      printf("删除节点[%d]成功!\n", i);
      i++;
      p = q->next;
      continue;
      //return true;
    }
    q = q->next;  //遍历链表
    p = q->next;
    i++;
  }
  //3)如果遍历完链表都没有找到,那就说明链表中没有这个节点
  //printf("链表中没有这个节点!\n");
  return false;
}

//7,链表销毁
void List_Destroy(Node *head)
{
  int i = 0;
  Node *p = head;
  Node *q = p->next;

  while(q != NULL)  //释放头结点后面的所有节点
  {
    p = q;
    q = q->next;
    free(p);
    i++;
  }
  free(head);   //最后释放头结点
  printf("成功释放[%d]个节点\n", i);
}








相关文章
|
14天前
|
算法 安全 大数据
揭秘!Python堆与优先队列:数据结构的秘密武器,让你的代码秒变高效战士!
【7月更文挑战第8天】Python的heapq模块和queue.PriorityQueue提供堆与优先队列功能,助你提升算法效率。堆用于快速找大数据集的第K大元素,如示例所示,时间复杂度O(n log k)。PriorityQueue在多线程中智能调度任务,如模拟下载管理器,按优先级处理任务。掌握这些工具,让代码运行更高效!
34 1
|
3天前
【数据结构OJ题】环形链表
力扣题目——环形链表
13 3
【数据结构OJ题】环形链表
|
3天前
【数据结构OJ题】复制带随机指针的链表
力扣题目——复制带随机指针的链表
10 1
【数据结构OJ题】复制带随机指针的链表
|
3天前
【数据结构OJ题】环形链表II
力扣题目——环形链表II
9 1
【数据结构OJ题】环形链表II
|
3天前
【数据结构OJ题】相交链表
力扣题目——相交链表
14 1
【数据结构OJ题】相交链表
|
13天前
【数据结构OJ题】移除链表元素
力扣题目——移除链表元素
15 2
【数据结构OJ题】移除链表元素
|
13天前
【数据结构OJ题】链表中倒数第k个结点
牛客题目——链表中倒数第k个结点
13 1
【数据结构OJ题】链表中倒数第k个结点
|
6天前
|
算法 计算机视觉 开发者
燃爆全场!Python并查集:数据结构界的网红,让你的代码炫酷无比!
【7月更文挑战第16天】并查集,Python中的效率明星,处理不相交集合合并与查询。用于社交网络分析、图像处理、图论算法等领域。优雅实现结合路径压缩和按秩合并
9 1
|
10天前
【数据结构OJ题】链表分割
牛客题目——链表分割
11 0
【数据结构OJ题】链表分割
|
11天前
【数据结构OJ题】链表的回文结构
牛客题目——链表的回文结构
16 0
【数据结构OJ题】链表的回文结构