数据结构-第3次课第二章线性表(链表).ppt

一、建立单链表 问题：假设线性表中结点的数据类型是字符，逐个输入这些字符型的数据，并以换行符‘$’为输入结束标记。 动态地建立单链表的常用方法有如下两种： 1、头插法建表 该方法从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直到读入结束标志 比如$）为止。 p new LNode; p- data ch; p- next head; head p; cin ch; /* void List::CreateList1 List h char ch; LNode *p; cin ch; while ch! $ p new LNode; p- data ch; p- next head; 四、删除运算 删除运算是将表的第i个结点删去。因为在单链表中结点ai的存储地址是在其直接前趋结点ai-1的指针域next中，所以必须首先找到ai-1的存储位置p。然后令p– next指向ai的直接后继结点，即把ai从链上摘下。最后释放结点ai的空间。此过程为： ai-1 ai ai+1 p p- next p- next- next; 四、删除运算 删除运算是将表的第i个结点删去。因为在单链表中结点ai的存储地址是在其直接前趋结点ai-1的指针域next中，所以必须首先找到ai-1的存储位置p。然后令p– next指向ai的直接后继结点，即把ai从链上摘下。最后释放结点ai的空间。此过程为： ai-1 ai ai+1 p p- next p- next- next; 问题：链表的逻辑结构已正确了，但结点ai空间丢了。 四、删除运算 删除运算是将表的第i个结点删去。因为在单链表中结点ai的存储地址是在其直接前趋结点ai-1的指针域next中，所以必须首先找到ai-1的存储位置p。然后令p– next指向ai的直接后继结点，即把ai从链上摘下。最后释放结点ai的空间。此过程为： ai-1 ai ai+1 p p- next p- next- next; r p- next; p- next r- next; delete r; 四、删除运算 删除运算是将表的第i个结点删去。因为在单链表中结点ai的存储地址是在其直接前趋结点ai-1的指针域next中，所以必须首先找到ai-1的存储位置p。然后令p– next指向ai的直接后继结点，即把ai从链上摘下。最后释放结点ai的空间。此过程为： ai-1 ai ai+1 p p- next p- next- next; r p- next; p- next r- next; delete r; r 以元素（数据元素的映象）+指针（指示后继元素存储位置） 结点（表示数据元素）。 List可访问类LNode中得所有成员 #include class List; class LNode public: char data; LNode *next; ; class List LNode *head; public: List head NULL; void CreateList ; void CreateList1 List h ; void print ; ; void List:: CreateList char ch; LNode *p; cin ch; while ch! $ p new LNode; p- data ch; p- next head; head p; cin ch; /* void List::CreateList1 List h char ch; LNode *p; cin ch; while ch! $ p new LNode; p- data ch; p- next head; h.head p; cin ch; */ void List::print LNode *p head; while p! NULL cout p- data ; p p- next; cout endl; void main List h1,h2; h1.CreateList ; h1.print ; //h2.CreateList1 h2 ; //h2.print ; 2.3 线性表的链式表示和实现 线性链表 链表是指用一组地址任意的存储单元来依次存放线