当前位置: 首页 > news >正文

数据结构学习:单链表

单链表简介

将线性表L = (a_{0},.....a_{i-1},a_{i},a_{i+1} ..... a_{n-1})中的个元素分布在存储器的不同存储块,每个部分称为节点,通过地址或指针建立元素之间的联系。

节点的示意图如下,

节点的data域存放数据元素 a_{i},而next域是一个指针,指针指向a_{i}的直接后继a_{i+1}所在的节点。

一个链表的图示如下,

头节点和头指针

头节点就是在编程时,在单链表的第一个结点前附设一个结点就称为头结点。

头指针指的就是链表中第一个结点的存储位置

头节点和头指针的异同如下,

 

单链表C语言编写

单链表在C语言下编写的结构代码如下,

/*线性表的单链表存储结构*/
tγpedef struct node
{data_t data;        /*节点的数据域*/struct node *next;  /*节点的后继指针域*/
}listnode,*linklist;

        下面我们将编写一些顺序表相关的函数,在编写时我们一般会创建三个文件,分别是sqlist.h,sqlist.c,test.c,其中sqlist.h用于编写一些数据结构的定义和函数结构,sqlist.c用于编写函数具体实现,test.c用于测试每个函数是否正确。

在sqlist.h文件中,编写的程序如下,

typedef int data_t;/*此处的类型视情况而定,此处为简单选用整型*/typedef struct node
{data_t data;struct node *next;   
}listnode,*linklist;linklist list_creat();
int list_tail_insert(linklist H,data_t value);
int list_show(linklist H);
linklist list_get(linklist H,int pos);
int list_insert(linklist H,data_t value,int pos);
int list_delete(linklist H,int pos);
linklist list_free(linklist H);

在sqlist.h文件中,我们编写相关函数的具体实现,以下是每个操作API函数的实现,

创建单链表

/*建立单链表*/
/*依次读入表中的每一个元素,如果ai != 结束符-1,则表示创建一个节点
然后插入表尾,返回链表头节点指针*/
linklist list_creat()
{linklist H;//为单链表申请内存H = (linklist)malloc(sizeof(listnode));if(H == NULL){printf("malloc fail\n");return H;}/*赋初值*/H->data = 0;H->next = NULL;return NULL;
}

尾部插入元素 

/*尾部插入元素到链表*/
int list_tail_insert(linklist H,data_t value)
{linklist p;linklist q;if(H == NULL){printf("H is enpty\n");return -1;}/*1,首先我们得将传入的数据封装成一个新节点,其实就是创建新节点*/p = (linklist)malloc(sizeof(listnode));if(p == NULL){printf("malloc fail\n");return H;}    p->data = value;p->next = NULL;/*由于是尾部节点,所以next为空*//*2,然后我们需要找到之前的尾节点的位置,通过判断节点的next是否为空可以找到*/q = H;while(q->next != NULL){q = q->next;}/*3,最后将新节点插入到尾部*/q->next = p;/*将之前链表的最后一个next由NULL变成指向p,也就是新插入尾部的链表*/return 0;
}

遍历单链表 

/*遍历单链表*/
int list_show(linklist H)
{linklist p;if(H == NULL){printf("H is enpty\n");return -1;}p = H;while (p->next != NULL){printf("%d\n",p->next->data);}puts("");return 0;}

元素查找 

/*链表查找*/
/*(1)按序号查找     (2)按值查找*/
/*查找某个位置上的节点*/
/*其中初始头节点对应的值是 -1 依次往后分别是 0 1 2 ...*/
linklist list_get(linklist H,int pos)
{linklist p;int i;if(H == NULL){printf("H is enpty\n");return NULL;}if(pos < -1){printf("pos is invalid\n");return NULL;}p = H;for(i=-1;i<pos;i++){p = p->next; if(p = NULL){printf("pos is invalid\n");return NULL;}}return p;}

元素插入

将元素插入到链表中,示意图如下,

/*链表插入,将x插入到节点ai之前*/
int list_insert(linklist H,data_t value,int pos)
{linklist p;linklist q;if(H == NULL){printf("H is enpty\n");return NULL;} /*查找插入位置前一个*/q = list_get(H,pos-1);if(q == NULL)return -1;/*创建要插入的新节点*/p = (linklist)malloc(sizeof(listnode));if(p == NULL){printf("malloc fail\n");return p;}  p->data = value;p->next = NULL;/*调整节点的链接*/p->next = q->next;/*由于是尾部节点,所以next为空*/q->next = p;return 0;
}

元素删除 

元素删除示意图如下,

/*链表删除*/
/*同插入法,按位置删除*/
int list_delete(linklist H,int pos)
{linklist p;if(H == NULL){printf("H is enpty\n");return NULL;} /*找到要删除节点位置的前一个节点*/p = list_get(H,pos-1);if(p = NULL)return -1;if (p->next = NULL){printf("delete pos is invalid\n");return -1;}/*更新链表,重新进行连接*/p->next = p->next->next;/*把节点的内存进行释放,因为通过malloc在堆山申请的,不释放会导致内存泄漏*/free(p->next);p->next =NULL;return 0;}

 

释放链表 

/*链表释放*/
/*也就是删除链表所有的元素*/
linklist list_free(linklist H)
{linklist p;if(H == NULL){printf("H is enpty\n");return NULL;} p = H;while (H != NULL){p = H;H = H->next;free(p);}return NULL;}

上述是编写的关于单链表的相关函数,当然,单链表的操作函数众多,大家可以按照自己的理解进行编写。


http://www.mrgr.cn/news/10840.html

相关文章:

  • 四川财谷通,信息科技引领者!
  • Ps:首选项
  • css设置三个div宽度占据三分之一
  • .NET Razor类库 - 静态资源组件化
  • MVVM分层思想
  • PHP农场扶农系统智慧认养智慧乡村系统农场系统小程序源码
  • AI大模型编写多线程并发框架(六十一):从零开始搭建框架
  • pg数据库的三种不同数据持久性解读
  • Buildroot构建Qt根文件系统-思维导图-学习笔记-基于正点原子阿尔法开发板
  • 华东师范大学学报(教育科学版)
  • Java设计模式【组合模式】-结构型
  • AI大语言模型之分布式训练概述
  • 【C++ 面试 - 内存管理】每日 3 题(一)
  • tortoisegit突然停止工作
  • docker-harbor私有仓库部署和管理
  • Ps:首选项 - 工具
  • 【Midjourney】Midjourney全面开放网站版,所有用户每天可免费生成25次
  • LeetCode Hot100:283、移动零
  • Tomcat的配置文件中有哪些关键的配置项,它们分别有什么作用?
  • 【html+css 绚丽Loading】 000018 五行伸缩剑