数据结构英文教学课件：Linked List-exercise

1、Linked list Data StructureSoftware College Northeastern University问题：在一个有序表中插入一个数据元素 Data StructureSoftware College Northeastern UniversitySequence List Solutionstemplate class SeqList Type *data; int MaxSize; int last; /index of the last elementpublic: SeqList ( int MaxSize = defaultSize ); SeqList

2、 ( ) delete data; int Length ( ) const return last+1; int Find ( Type & x ) const; Data StructureSoftware College Northeastern UniversityProgramming Exercise int SeqList:Insert_sorted(Type value) 插入成功时返回0 表内有相同的数据元素时插入失败返回1Data StructureSoftware College Northeastern Universitytemplate int SeqList:In

3、sert_sorted( Type value) i=0; while(i = last & datai value) i+; if( ii-1;j-) dataj+1=dataj; datai= value; last+; return 0;Data StructureSoftware College Northeastern UniversityProgramming Exercise int List:Insert_sorted(Type value) 插入成功时返回0 表内有相同的数据元素时插入失败返回1Data StructureSoftware College Northeaste

4、rn UniversityTemplate of linked list(1)template class List;template class ListNode friend class List; Type data; /结点数据 ListNode *link; /结点链接指针public: ListNode ( ); /链表结点构造函数 ListNode ( const Type& item ); ListNode *NextNode ( ) return link; /给出当前结点的下一结点地址Data StructureSoftware College Northeastern U

5、niversityvoid InsertAfter ( ListNode *p ); /在当前结点后插入结点p ListNode *RemoveAfter ( ); /摘下当前结点的下一结点;template class List ListNode *first, *last;public: ListNode *GetNode ( const Type& item, ListNode *next ); /创建数据为item，指针为next的新结点Template of linked list(2)Data StructureSoftware College Northeastern Unive

6、rsity List ( const Type & value ) last =first = new ListNode( value ); /构造函数 List ( ); /析构函数 void MakeEmpty ( ); /链表置空 int Length ( ) const; /求链表长度 ListNode *Find ( Type value ); ListNode *Find ( int i ); int Insert ( Type value, int i ); Type *Remove ( int i ); Type *Get ( int i ); int Insert_sorte

7、d(Type value); Template of linked list(3)Data StructureSoftware College Northeastern UniversityLinked List SolutionsFirst1234Prep1、从前向后查找大于等于待插入数据元素的位置2、如果有相同数据元素，返回1 否则在该位置之前插入新数据元素，返回0Data StructureSoftware College Northeastern Universitytemplate int List:Insert_sorted( Type value) ListNode *pre =

8、first,*p=first-link; while(p != NULL & p-data link; if( p != NULL & p-data = value) return 1; q = new ListNode( value ); q-link = pre-link; pre-link = q; return 0;Data StructureSoftware College Northeastern UniversityProgramming Exercise int List:If_sorted() 如果是有序的返回0 如果是无序的返回1Data StructureSoftware

9、 College Northeastern UniversityLinked List SolutionsFirst1234pre借助冒泡排序的思想 两两相邻的结点中存储的数据进行比较 一旦发现不是由小到大的，则判断链表是无序的问题解决的关键： 相邻的结点的获取Data StructureSoftware College Northeastern Universitytemplate int List:If_sorted( Type value) ListNode *pre =first-link,*p; while(pre != NULL) p = pre-link; if(p = NULL

10、 ) return 0; else if (pre-data p-data) return 1; else pre = p; return 0;Data StructureSoftware College Northeastern UniversityProgramming Exercise void List:Delete_Same() 链表中的数据元素按照元素值由大到小存储，去掉表中数值相同的数据元素Data StructureSoftware College Northeastern UniversityLinked List SolutionsFirst5533p对链表上的每一个元素结

11、点 检查后面相邻的结点是否和其值相同， 如果相同删除其后面的结点Data StructureSoftware College Northeastern Universitytemplate void List:delete_same( Type value) ListNode *p =first-link,q; while(p != NULL) q = p-link; while(q != NULL & p-data = q-data) p-link = q-link; delete q; q = p-link; p = p-link; return;Data StructureSoftwar

12、e College Northeastern Universitytemplate class DblList;template class DblNode friend class DblList;private: Type data; int freq; /数据 DblNode *lLink, *rLink; /指针 DblNode ( Type value, /构造函数 DblNode *left, DblNode *right ) : data (value), lLink (left), rLink (right) Doubly linked lists(1)Data Structu

13、reSoftware College Northeastern University DblNode ( Type value ) : data (value), lLink (NULL), rLink (NULL) ;template class DblList public: DblList ( Type uniqueVal ); DblList ( ); int Length ( ) const; int IsEmpty ( ) return firstrlink = first; int Find ( const Type & target ); Type getData ( ) co

14、nst;Doubly linked lists(2)Data StructureSoftware College Northeastern University void Firster ( ) current = first; int First ( ); int Next ( ); int Prior ( ); int operator ! ( ) return current != NULL; void Insert ( const Type & value ); void Remove ( );private: DblNode *first, *current;Implementati

15、on of Doubly linked lists(3)Data StructureSoftware College Northeastern UniversityDoubly linked lists:SearchingData StructureSoftware College Northeastern UniversityProgramming Exercise DblNode * DblList :Locate(Type value) 双向链表中数据元素按照访问频度由大到小进行排序 获取元素在双向链表中的位置 如果不存在，返回空 如果存在， 把访问频度加1，并按照访问频度对结点调整位置

16、 （查找插入位置，删除结点，插入结点）Data StructureSoftware College Northeastern UniversityProgramming Exercise DblNode * DblList :Locate(Type value) 过程： （1）查找元素位置 （2）根据查找结果处理 不存在 存在，频度加1，判断是否需要移动 如需要移动，逆向查找合适的移动位置Data StructureSoftware College Northeastern Universitytemplate DblNode * DblList :Locate(Type value) DblNode *p =first-right,; while(p != first & p-data != value) p = p-right; if(p = first) return NULL; else p-freq+; pre = p-left; while(pre != first & pre-freq freq) pre=pre-left;Data Struc