• 数据结构与算法-----顺序表（链表篇）

     目录

    前言

    顺序表

    链表

    概念

    与数组的不同 

    单链表

    1. 创建节点

    2.插入节点

    尾插节点（形成链表结构）

    向指定位置插入节点（链表已有）

    ​编辑

    3.遍历链表数据

    4.获取链表长度

    5.删除节点

    删除尾节点

    删除指定节点

    6.清空链表

    7.链表的数据查找

    8.链表的转置

     测试集

     环形链表

    创建环形链表 

    双向循环链表

    创建双向循环链表

    前言

            在此之前我们学习过了数组，数组也是一种顺序表，连续储存结构，但是数组本质上是一种静态空间，而我们主要讲的是动态空间的顺序表，顾名思义也就是我们常见的链表，链表又分为单链表以及环状链表和双向循环链表，下面我们就一起来看看吧！（我已经上传代码,可下载代码资源）

    顺序表

    定义：

    顺序表，全名顺序存储结构，是线性表的一种。通过《什么是线性表》一节的学习我们知道，线性表用于存储逻辑关系为“一对一”的数据，顺序表自然也不例外。
    不仅如此，顺序表对数据的物理存储结构也有要求。顺序表存储数据时，会提前申请一整块足够大小的物理空间，然后将数据依次存储起来，存储时做到数据元素之间不留一丝缝隙。 

    我们常见的顺序表有数组和链表等，前者是一个静态空间的数据储存结构，后者是一个动态空间数据储存结构。二者都可以去通过引索去实现表的操作，下面就看链表的相关操作。

    链表

    概念

    链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，操作。 

     链表的节点是分为两部分：数据域和指针域

    数据域：存放各种数据，比如int、char类型等等

    指针域：作为指向下一个节点的桥梁 

    1. typedef struct student{
    2.     //数据域
    3.     int index;//作为下标表示第几位
    4.     long num;//学号
    5.     char name[20];//名字
    6.     int score;//分数
    7.     //指针域
    8.     struct student* next;//指向下一位的指针
    9. }Student;

    图解

     

    与数组的不同 

    单链表

      单链表是作为最简单的一种线性表的数据结构，通过动态空间分配可以实现单链表的创建，下面我们就学习单链表的创建以及增删改查等方法。

    1. 创建节点

    这里我们就不去按照之前学习链表时的做法了，之前我们是一次性去创建节点的同时还把节点连接起来，这里我们就把这两个步骤分开来做，让代码更加灵活。 

    1. #include
    2. #include
    3. #include
    4. typedef struct date{
    5.     long num;//学号
    6.     char name[20];//名字
    7.     int score;//分数
    8. }Date;//存放数据
    9. typedef struct student{
    10.     //数据域
    11.     Data x;
    12.     //指针域
    13.     struct student* next;//指向下一位的指针
    14. }Student;
    15.  
    16.  
    17. //创建节点
    18. Student* create_node(Date x) {
    19.     Student* node = (Student*)malloc(sizeof(Student));
    20.     //数据赋值
    21.     node->x = x;
    22.     //指针域指向空
    23.     node->next = NULL;
    24.     //返回这个节点
    25.     return node;
    26. }

    2.插入节点

    尾插节点（形成链表结构）
    1. //把节点连接起来
    2. void create_studentlist(Student**head,Date x) {
    3.     Student* new_node = create_node(x);
    4.     //如果头指针指向空节点的话，那么将头指针指向这个新的节点
    5.     if (*head == NULL) {
    6.         *head = new_node;
    7.     }
    8.     //如果头指针指向一个不为空的节点的话，那么就要顺着这个链表找到最后的节点，把新节点放入
    9.     else {
    10.         Student* move=*head;//创建一个移动节点,找到最后一个节点的位置
    11.         while (move->next != NULL) {
    12.             move = move->next;  //一直往后移
    13.         }
    14.         move->next = new_node;//把新节点放入进去
    15.     }
    16. }
    向指定位置插入节点（链表已有）
    1. //指定位置插入节点
    2. void insert_node(Student** head, Student *new_node,int n) //向链表第n个位置插入节点
    3. {
    4.     Student* move=*head;
    5.     //通过循环找到这个节点
    6.     for (int i = 0; i < n; i++)
    7.     {
    8.         move = move->next;
    9.     }
    10.     //下面这两步的顺序千万不能反过来！！！
    11.     new_node->next = move->next;
    12.     move->next = new_node;
    13. }

    3.遍历链表数据

    1. //输出数据
    2. void listprint(Student**head)
    3. {
    4.     Student* cur=*head;
    5.     while (cur != NULL) {
    6.         printf("%ld %s %d\n", cur->x.num, cur->x.name, cur->x.score);
    7.         cur = cur->next;
    8.     }
    9.     printf("output over!");
    10. }

    4.获取链表长度

    1. //获取链表长度
    2. int get_listlength(Student**head)
    3. {
    4.     int length=0;
    5.     Student* cur = *head;
    6.     while (cur != NULL)
    7.     {
    8.         length++;
    9.         cur = cur->next;
    10.     }
    11.     return length;//返回长度的大小
    12. }

    5.删除节点

    删除节点是链表的基本操作之一，分为删除尾节点和删除指定的节点（不是尾节点），这两种情况要去分类讨论，下面请看代码案例：

    删除尾节点
    1. //删除尾节点
    2. void pop_lastnode(Student** head)
    3. {
    4.     //如果没有节点，就直接返回
    5.     if (*head == NULL)
    6.         return;
    7.     //如果只有一个节点的话，就直接删除
    8.     else if ((*head)->next == NULL)
    9.     {
    10.         free(*head);
    11.         *head = NULL;//重新置空
    12.     }
    13.     /*如果有多个节点的话，要找到最后一个节点的上一个节点，删除掉最后一个节点
    14.     然后再把这个节点的next指向空*/
    15.     else{
    16.         Student* move = *head;
    17.         while (move->next->next!=NULL)
    18.         {
    19.             move = move->next;
    20.         }
    21.         free(move->next);
    22.         move->next = NULL;
    23.     }
    24. }
    删除指定节点

    1. //删除指定节点
    2. void pop_node(Student** head, int n)//删除第n个节点
    3. {
    4.     Student* move = *head;
    5.     Student* p;
    6.     //通过循环依次去找到要删除节点的上一个节点
    7.     for (int i = 0; i < n-1; i++)
    8.     {
    9.         move = move->next;
    10.     }
    11.     p = move->next;//此时要删除的节点标记为p节点
    12.     move->next = p->next;//让p节点的上一个节点指向p节点的下一个节点，此时p节点已经断链
    13.     free(p);
    14. }

    6.清空链表

    1. //清空链表,释放全部的空间
    2. void clear_list(Student**head){
    3.     Student* cur=*head;
    4.     Student* next;
    5.     while (cur != NULL) {
    6.         next = cur->next;
    7.         free(cur);
    8.         cur = next;
    9.     }
    10.     *head = NULL;//头指针置空
    11.     printf("clear over!\n");
    12. }

    7.链表的数据查找

    1. //数据查找
    2.  
    3. //按学号查找
    4. Student* list_search_num(Student** head, int num) {
    5.     Student* cur = *head;
    6.     while (cur!=NULL) {
    7.         if (cur->x.num == num) { 
    8.             return cur; //找到了就返回这个节点
    9.         }
    10.         else
    11.             cur = cur->next;
    12.     }
    13.     printf("No find");
    14.     return NULL;
    15. }
    16.  
    17. //按名字查找
    18. Student* list_search_name(Student** head, char *name) {
    19.     Student* cur = *head;
    20.     while (cur != NULL) {
    21.         if (strcmp(cur->x.name,name)==0) {
    22.             return cur;   //找到了就返回这个节点
    23.         }
    24.         else
    25.             cur = cur->next;
    26.     }
    27.     printf("No find");
    28.     return NULL;
    29. }

    8.链表的转置

    我们已有的链表顺序是: 1->2->3->4->5  现在我想让这个链表顺序变为5->4->3->2->1（如下图所示）   这个过程就是链表的转置，我们可以去通过头插法去实现

    头插法步骤如下： 

    1. //链表的转置(头插法)
    2. void list_reverse(Student** head) {
    3.     Student *L, *start,* p, * q;
    4.     //开辟一个暂存节点L
    5.     L = (Student*)malloc(sizeof(Student));
    6.     //初始化
    7.     start = *head;
    8.     L->next = start;
    9.     p = L->next;
    10.     L->next = NULL;
    11.     while (p!= NULL) {
    12.         q = p->next;
    13.         p->next = L->next;
    14.         L->next = p;
    15.         p = q;
    16.     }
    17.     *head = L->next;//将此时的头结点等于新的头结点
    18.     free(L);//释放掉暂存节点
    19.     printf("reverse over!\n");
    20. }

     测试集

    1. //测试结果
    2. int main()
    3. {
    4.     Date a[4] = { {1,"xiaoming",90} ,{ 2,"Jack",80 } ,{ 3,"Amy",98 } ,{ 4,"John",77 } };
    5.  
    6.     Student* head = NULL;//实例化一个头节点指针
    7.     for (int i = 0; i < 4; i++) {
    8.         //要把实例化的头指针的地址存入进去
    9.         create_studentlist(&head, a[i]);//依次成链
    10.     }
    11.     listprint(&head);//输出数据
    12.     printf("当前节点数量： %d\n", get_listlength(&head));
    13.     list_reverse(&head);//逆转链表
    14.     listprint(&head);//输出数据
    15.     pop_lastnode(&head);//删除最后一个节点
    16.     printf("当前节点数量： %d\n", get_listlength(&head));
    17.     listprint(&head);//输出数据
    18.     clear_list(&head);//清空链表
    19.     printf("当前节点数量： %d\n", get_listlength(&head));
    20.  
    21. }
    22. //输出如下：
    23. /*1 xiaoming 90
    24. 2 Jack 80
    25. 3 Amy 98
    26. 4 John 77
    27. output over!
    28. 当前节点数量： 4
    29. reverse over!
    30. 4 John 77
    31. 3 Amy 98
    32. 2 Jack 80
    33. 1 xiaoming 90
    34. output over!
    35. 当前节点数量： 3
    36. 4 John 77
    37. 3 Amy 98
    38. 2 Jack 80
    39. output over!
    40. clear over!
    41. 当前节点数量： 0
    42. */

     环形链表

    链表，从名字上来看是一条数据链，一般的链表其末尾节点是没有指向的，但当把链表的末尾节点指定为指向头节点时，则构成了一个环形链表。所以要想去建立一个环形链表只需要把最后一个节点重新指向头节点就行了，或者指向其他节点可以形成局部环形链表。下面我就讲讲通过代码去创建环形链表，相关操作方法（增删改查）跟上面所说的基本一样。

    创建环形链表 

    1. #include
    2. #include
    3. typedef struct node {
    4. 	int date;
    5. 	struct node* next;
    6. }Node;
    7. //创建节点
    8. Node *create_node(int date) {
    9. 	Node* node = (Node*)malloc(sizeof(Node));
    10. 	node->date = date;
    11. 	node->next = NULL;
    12. 	return node;
    13. }
    14. //把节点连起来
    15. void create_annuallist(Node** head,int date) {
    16. 	Node* new_node = create_node(date);
    17. 	if (*head == NULL) {
    18. 		*head = new_node;
    19. 	}
    20. 	else
    21. 	{
    22. 		Node* cur = *head;
    23. 		while (cur->next) {
    24. 			cur = cur->next;
    25. 		}
    26. 		cur->next = new_node;
    27. 	}//成链
    28. 	//成环
    29. 	new_node->next = *head;
    30. }

    当你仔细细看的话，前面跟链表的创建基本上没什么区别，实际上就在最后面加上一个尾节点指向头节点就是了！

    双向循环链表

    带头双向循环链表是链表当中结构最复杂的链式结构，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个链表虽然结构复杂，但是使用代码实现以后会发现能带来很多优势。

    创建双向循环链表

    实现思路：

    要想创建双向循环链表，就意味着在单相链表的基础上增加一个前指针来指向上一个节点，然后在成链的过程中后一个节点要指向前一个节点，前一个节点指向后一个节点，最后头尾节点互相指向就可以形成双向循环了。

    代码实现：

    1. #include
    2. #include
    3. #include
    4. //创建双向循环链表
    5. typedef struct node {
    6. 	struct node* prev; //前指针
    7. 	char date[10];//数据域
    8. 	struct node* next; //后指针
    9. }D_node;
    10. D_node* create_D_node(char*date) {
    11. 	D_node* new_node = (D_node*)malloc(sizeof(D_node));
    12. 	strcpy(new_node->date, date);
    13. 	//前后指针都指向空，初始化
    14. 	new_node->prev = NULL;
    15. 	new_node->next = NULL;
    16. 	return new_node;
    17. }
    18. void create_D_list(D_node** head, char* date) {
    19. 	D_node* new_node = create_D_node(date);
    20. 	if (*head == NULL) {  //判断头结点是否为空
    21. 		*head = new_node;
    22. 	}
    23. 	else
    24. 	{
    25. 		D_node* cur = *head;
    26. 		while (cur->next) {
    27. 			cur = cur->next;
    28. 		}
    29. 		//双向指向（前指向后，后指向前）
    30. 		new_node->prev = cur;
    31. 		cur->next = new_node;
    32. 	}
    33. 	//头尾指针互相指向，成环
    34. 	new_node->next = *head;
    35. 	(*head)->prev = new_node;
    36. }

     好了，以上就是本期的全部内容了，我们下一期再见！

    分享一张壁纸：

  • 相关阅读:
    智能边缘小站 CloudPond(低延迟、高带宽和更好的数据隐私保护)
    代碼隨想錄算法訓練營|第六十二天|84.柱状图中最大的矩形。刷题心得（c++）
    使用gstreamer,rtsp拉流，保存图像， jeston，使用硬件加速nvdec/nvenc
    Volatile应用与底层原理
    STL之阶段总结、大作业指导
    大学生《Web课程谁》期末网页制作 HTML+CSS+JavaScript 网页设计实例 瑜伽网站企业网站制作
    大数据学习笔记1.2 登录配置虚拟机
    Mybatis中使用${}和使用#{}
    Redash和Metabase深度比较之四：可视化种类
    Nwafu-OJ-1506 Problem 9 阶段2考试题目3 二分法解方程
  • 原文地址：https://blog.csdn.net/m0_73633088/article/details/132776167