2019数据结构C++第2章第4讲.pptx

第二章 线性表本次重点内容单链表的结构定义在C中定义单链表的结构十分简单： typedef int T;//结点数据的类型 typedef struct node {//结点结构定义 T data;//结点数据域 struct node *link;//结点链接指针域 } LinkNode;//结点命名这是一个递归的定义。在结构定义时不考虑操作，以后在定义和实现链表操作时直接使用结构的成分。单链表的类定义使用面向对象方法，要把数据与操作一起定义和封装，用多个类表达一个单链表。 链表结点(ListNode)类 链表(List)类定义方式 复合方式 嵌套方式 继承方式 结构方式//链表类和链表结点类定义(结构方式) struct ListNode { //链表结点类 int data; ListNode * link; }; class List { //链表类, 直接使用链表结点类的数据和操作 private: ListNode *first; //表头指针 };//链表中的结点属于链表私有，别人无法访问newnodenewnodefirst first单链表中的插入与删除操作插入 第一种情况：在链表最前端插入 newnode-link = first ; first = newnode;（插入前） （插入后）newnodenewnodecurrentcurrent 第二种情况：在链表中间插入 newnode-link = current-link; current-link = newnode；(插入前) (插入后)newnodenewnode?currentcurrent? 第三种情况：在链表末尾插入 newnode-link = current-link; current-link = newnode；(插入前) (插入后)单链表的插入算法bool List::Insert(int i, int x) {//将新元素 x 插入到第 i 个结点之后。i 从1开始，//i = 0 表示插入到首元结点之前。 if (first == NULL || i == 0) { //空表或首元结点前 LinkNode *newNode = new LinkNode(x); //建立一个新结点 newNode-link = first; first = newNode; //新结点成为首元结点 } else {//否则，寻找插入位置 LinkNode *current = first; int k = 1; while (k i current != NULL)//找第i结点 { current = current-link; k++; } if (current == NULL first != NULL)//链短 {cerr “无效的插入位置!\n”; return false;} else { //插入在链表的中间 LinkNode *newNode = new LinkNode(x); newNode-link = current-link; current-link = newNode; } } return true; };删除第一种情况: 删除表中第一个元素第二种情况: 删除表中或表尾元素??ai-1aiai+1删除前??ai-1aiai+1pq删除后在单链表中删除含ai的结点a1an-1firstfirst00带表头结点的单链表表头结点位于表的最前端，本身不带数据，仅标志表头。设置表头结点的目的是统一空表与非空表的操作，简化链表操作的实现。非空表 空表firstfirstpqfirst0first0pq从带表头结点的单链表中删除最前端的结点(非空表） q = p-link; p-link = q-link; delete q; (空表）单链表的删除算法bool List::Remove (int i, int x) {//将链表中的第 i 个元素删去, i 从1开始。 LinkNode *del; //暂存删除结点指针 if (i = 1) { del = first; first = first-link; } else { LinkNode *current = first; k = 1;//找i-1号结点 while (k i-1 current != NULL) { current = current-link; k++; } if (current == NULL || current-link == NULL) { cout “无