当前位置 博文首页 > CW_qian的博客:8月23日笔记数据结构(补7)链表
1.存储数据的时候,先要申请空间
?? ?int[10]; // error
?? ?缺陷:
?? ??? ?1.造成内存资源浪费
?? ??? ?2.不能完全保证分配的空间足够
?? ?按需分配用链表
1.单向链表
?? ?1.链表概述
?? ??? ?链表其实是由一个或者多个结构体通过指针指向的关系构成
?? ??? ?我们把每个结构体的变量称为节点,节点里面由两个成员组成
?? ??? ?一个是数据域,另外一个是指针域,指针域是用于存放下一个节点的地址
?? ??? ?以此类推,我们把这种存储方式称为链式存储
?? ?
?? ?2.链表节点定义
?? ??? ?// 节点
?? ??? ?struct node
?? ??? ?{
?? ??? ??? ?int data; //数据域?
?? ??? ??? ?struct node *next; // 指针域,指向下一个节点(存放下一个节点的地址)
?? ??? ?};
? ? 3.节点的空间分配
?? ??? ?(1)栈空间:过了生存周期自动释放
?? ??? ?(2)堆空间:malloc只需要保存地址即可,生存周期域与程序保持一致
?? ??? ?
?? ?4.首节点(head):链表中唯一一个只指向别的节点,而不被其它节点指向
?? ??? ?首节点的地址其实就是整个链表的首地址,它可以表示整个链表
?? ??? ?
?? ?5.尾节点(tail):链表中唯一一个被别的节点指向,它不指向其它节点
?? ??? ?尾节点的next一般指向NULL,否则为野指针
?? ??? ?
?? ?6.总结:
?? ??? ?只要保存首节点的地址,就可以访问其它节点
?? ??? ?保存新的数据,只需要创建一个新节点即可
?? ??? ?
?? ?7.创建链表步骤
?? ??? ?1.从无到有:第一个节点的诞生,此时的首节点和尾节点都是它本身
?? ??? ?
?? ??? ?2.从少到多(添加节点过程):
?? ??? ??? ?1.在原来链表的后面添加新节点(尾插法)
?? ??? ??? ??? ?新节点接在尾节点后面,即尾节点指向新节点
?? ??? ??? ??? ?原来的尾节点被新节点替代
?? ??? ??? ??? ?特点:先接入的节点在前面,后接入的节点在后面
?? ??? ??? ??? ?
?? ??? ??? ?2.在原来的链表的前面添加新节点(头插法)
?? ??? ??? ??? ?新节点接在原来链表的首节点前面,即新的节点指向原来的首节点,然后首节点
?? ??? ??? ??? ?被新节点替代
?? ??? ??? ??? ?特点:后接入的节点在前面,先接入的节点在后面