C++链表基本操作

C 链表基本操作 我们知道 数组式计算机根据事先定义好的数组类型与长度自动为其分配一连续的存储单元 相同数组的 位置和距离都是固定的 链表是一种动态数据结构 他的特点是用一组任意的存储单元 可以是连续的 也可以是不连续的 存放 数据元素 链表中每一个元素成为 结点 每一个结点都是由数据域和指针域组成的 每个结点中的指针 域指向下一个结点 Head 是 头指针 表示链表的开始 用来指向第一个结点 而最后一个指针的指针 域为 NULL 空地址 表示链表的结束 可以看出链表结构必须利用指针才能实现 即一个结点中必须 包含一个指针变量 用来存放下一个结点的地址 实际上 链表中的每个结点可以用若干个数据和若干个 指针 结点中只有一个指针的链表称为单链表 这是最简单的链表结构 struct Node int Data Node next 这里用到了结构体类型 其中 next 是指针域 用来指向该结点的下一个结点 Data 是一个整形变 量 用来存放结点中的数据 当然 Data 可以是任何数据类型 包括结构体类型或类类型 在此基础上 我们在定义一个链表类 list 其中包含链表结点的插入 删除 输出等功能的成员函数 class list Node head public list head NULL void insertlist int aDate int bDate 链表结点的插入 void Deletelist int aDate 链表结点的删除 void Outputlist 链表结点的输出 Node Gethead return head 2 链表结点的访问 由于链表中的各个结点是由指针链接在一起的 其存储单元文笔是连续的 因此 对其中任意结点的地址 无法向数组一样 用一个简单的公式计算出来 进行随机访问 只能从链表的头指针 即 head 开始 用一个指针 p 先指向第一个结点 然后根据结点 p 找到下一个结点 以此类推 直至找到所要访问的结 点或到最后一个结点 指针为空 为止 下面我们给出上述链表的输出函数 void list outputlist Node current head while current NULL cout Data next cout Data bDate 设 b 为此结点 p head if head NULL 若是空表 使 b 作为第一个结点 head s s next NULL else if p Data aDate 若 a 是第一个结点 s next p head s else while p Data aDate p p next if p Data aDate 若有结点 a q next s s next p else 若没有结点 a p next s s next NULL 4 链表结点的删除 如果要在链表中删除结点 a 并释放被删除的结点所占的存储空间 则需要考虑下列几种情况 1 若要删除的结点 a 是第一个结点 则把 head 指向 a 的下一个结点 2 若要删除的结点 a 存在于链表中 但不是第一个结点 则应使 a 得上一个结点 a k 1 的指针域指 向 a 的下一个结点 a k 1 3 空表或要删除的结点 a 不存在 则不做任何改变 void list deletelist int aDate 设 aDate 是要删除的结点 a 中的数据成员 Node p q p 用于指向结点 a q 用于指向结 a 的前一个结点 p head if p NULL 若是空表 return if p Data aDate 若 a 是第一个结点 head p next delete p else while p Data aDate p p next if p Data aDate 若有结点 a q next p next delete p 例题 利用以上三个链表操作成员函数 insertlist deletelist outputlist 可形成以下的简单链表操作 include iostream h struct Node int Data Node next class list Node head public list head NULL void insertlist int aData int bData void deletelist int aData void outputlist Node gethead return head void list insertlist int aData int bData 设 aData 是结点 a 中的数据 bData 是结点 b 中的数据 Node p q s p 指向结点 a q 指向结点 a k s 指向结点 b s Node new Node 动态分配一个新结点 s Data bData 设 b 为此结点 p head if head NULL 若是空表 使 b 作为第一个结点 head s s next NULL else if p Data aData 若 a 是第一个结点 s next p head s else while p Data aData p p next if p Data aData 若有结点 a q next s s next p else 若没有结点 a p next s s next NULL void list deletelist int aData 设 aData 是要删除的结点 a 中的数据成员 Node p q p 用于指向结点 a q 用于指向结 a 的前一个结点 p head if p NULL 若是空表 return if p Data aData 若 a 是第一个结点 head p next delete p else while p Data aData p p next if p Data aData 若有结点 a q next p next delete p void list outputlist Node current head while current NULL cout Data next cout endl void main list A B int Data 10 25 41 16 98 5 67 9 55 1 121 A insertlist 0 Data 0 建立链表 A 首结点 for int i 1 i 10 i A insertlist 0 Data i 顺序向后插入 cout n 链表 A A outputlist A deletelist Data 7 cout 删除元素 Data 7 后 A outputlist B insertlist 0 Data 0 建立链表 B 首结点 for i 0 iData Data i 在首结点处顺序向后插入 cout n 链表 B B outputlist B deletelist 67 cout 删除元素 67 后 B outputlist 程序运行结果为 链表 A 25 41 16 98 5 67 9 55 1 121 删除元素 Data 7 后 25 41 16 98 5 67 9 1 121 链表 B 121 1 55 9 67 5 98 16 41 25 删除元素 67 后 121 1 55 9 5 98 16 41 25 下面是杨辉三角的代码 include include using namespace std int main const int n 11 int i j a n n for i 1 i n i a i i 1 a i 1 1 for i 3 i n i for j 2 j i 1 j a i j a i 1 j 1 a i 1 j for i 1 i n i for j 1 j i j cout setw 5 a i j cout endl cout endl return 0 include include struct Node int num Node next Node Create 链表创建 int n 0 Node p1 p2 head p1 p2 new Node cin p1 num head NULL while p1 num 0 if n 1 head p1 else p2 next p1 p2 p1 p1 new Node cin p1 num n p2 next NULL return head int ListLength Node L 链表的计数 Node p L int count 0 while p next count p p next return count int Search Node int index 0 while p if p num value return index p p next index return 0 void Print Node head 输出链表 Node p head while p cout num next cout next delete temp Node ReverseList Node head 链表逆序 循环方法 Node p q r p head 一开始 p 指向第一个节点 q p next q 指向第二个节点 while q NULL 如果没到链尾 以第一次循环为例 r q next r 暂时存储第三个节点 q next p 没执行此句前 q next 指向第三个节点 执行之后 q next 指向第一个节点 p p q 之后 p 指向第二个节点 q r q 指向第三个节点 即 p q r 变为 p qnext NULL 最后原来的链头变为链尾 把它指向 NULL head p 原来的链尾变成链头 return head Node ReverseList2 Node head 链表逆序 递归方法 if head return NULL Node temp ReverseList2 head next if temp return head head next next head head next NULL return temp 递归时 head 可以分别用 head head1 head2 headn 1 headn 来表示总共 n 1 个节点 temp ReverseList2 head next 此句的递归一直将参数传进来的 Node head 递归到 headn 然后判断下列语句 else if headn next return headn 将返回值传给 temp 此时 temp 指向链尾 由于在此次返回 故此次没有执行最后的 else 的那部分的语 句 返回上一级即是 headn 1 那一级 继续执行 下面的 headn 1 next next headn 1 headn 1 next NULL 此两句将最后两个逆序连接 return temp 之后返回 temp 比上一层的 temp 即是执行 temp ReverseList2 head next 赋值 因为 递归的口都是在这里的 如果说好理解点也可以将 temp 来编号 同理 在返回 temp 后 继续执行 headn 2 next next headn 2 headn 2 next NULL return temp 一直到 head 时 即是原链表的第一个节点 在对其 head next NULL 后 此时以 temp 所指向 的节点为链头的逆序链表就形成了 已知两个链表 head1 和 head2 各自有序 请把它们合并成一个链表依然有序 循环方法 保留所有结点 即便大小相同 Node Merge Node head1 Node head2 if head1 NULL return head2 if head2 NULL return head1 if head1 num num head head1 head1 head1 next else head head2 head2 head2 next Node temp head while head1 NULL head1 head1 next temp temp next else temp next head2 head2 head2 next temp temp next if head1 NULL temp next head2 if head2 NULL temp next head1 return head 已知两个链表 head1 和 head2 各自有序 请把它们合并成一个链表依然有序 递归方法 Node MergeRecursive Node head1 Node head2 if head1 NULL return head2 if head2 NULL return head1 Node head NULL if head1 num num head head1 head next MergeRecursive head1 next head2 else head head2 head next MergeRecursive head1 head2 next return head 从递归函数的定义不难看出 这个函数定义中递归调用时形参发生改变 即是当前节 点的下一个节点 每一次递归都按照这个规律逐次遍历两个有序链表的每一个节点 判断 大小后使 head 指向数据域较小的节点 由堆栈空间的思想可知递归到最后指向 NULL 时才 返回两个链表的某一个头节点 而此时 head next head2 head head1 链表的最后一个节 点 该语句就使得这样一个指向关系确立起来 以上均通过理想的有序链表 即链表 1 的任何一个数据值都小于链表 2 来做分析 其他的 情况讨论方式类似 Node Delete Node head int num 删除节点 if head NULL cout List is Null num num p1 p1 next if p1 num num if p1 head head p1 next else p2 next p1 next else cout Do not Find The Num num num num if head NULL head p0 p0 next NULL return head while p1 numnum p1 p1 next if p1 num p0 num if p1 head head p0 else p2 next p0 p0 next p1 else p1 next p0 p0 next NULL return head void main 省略不写