数据结构课件ch3.pptxVIP

第三章 链表;§3.1 单链表;单链表的存储映像;单链表的类定义; class List; class ListNode { //链表结点类 friend class List; //链表类为其友元类 private: int data; //结点数据, 整型 ListNode *link; //结点指针 }; class List { //链表类 public: //链表公共操作 ……… private: ListNode *first, *last; //表头和表尾指针 };;单链表中的插入与删除;;;int List::Insert ( const int x, const int i ) { //在链表第 i 个结点处插入新元素 x ListNode *p = first; int k = 0; while ( p != NULL k i -1 ) { p = p→link; k++; } //找第i-1个结点 if ( p == NULL first != NULL ) { cout “无效的插入位置!\n”; return 0; } ListNode *newnode= new ListNode(x, NULL); //创建新结点,其数据为x,指针为0; if ( first == NULL || i == 0 ) { //插在表前 newnode→link = first; if ( first == NULL ) last = newnode; first = newnode; } else { //插在表中或末尾 newnode→link = p→link; if ( p→link == NULL ) last = newnode; p→link = newnode; } return 1; };删除 第一种情况: 删除表中第一个元素 第二种情况: 删除表中或表尾元素;int List::Remove ( int i ) { //在链表中删除第i个结点 Node *p = first, *q; int k = 0; while ( p != NULL k i-1 ) { p = p→link; k++; } //找第i-1个结点 if ( p == NULL || p→link == NULL ) { cout “无效的删除位置!\n”; return 0; } if ( i == 0 ) { //删除表中第 1 个结点 q = first; //q 保存被删结点地址 p = first = first→link; //修改first } ; else { //删除表中或表尾元素 q = p→link; p→link = q→link; //重新链接 } if ( q == last ) last = p; //可能修改last k = q→data; delete q; //删除q return k; };带表头结点的单链表;在带表头结点的单链表 第一个结点前插入新结点; q = p→link; p→link = q→link; delete q; if ( p→link == NULL ) last = p;;单链表的类模板; 用模板定义的单链表类; ListNodeType *GetNode ( const Type item, ListNodeType *next ); //创建数据为item，指针为next的新结点 void InsertAfter ( ListNod