数据结构与算法分析

伏虓18 贡献于2017-05-08

作者 倪幼纯  创建于2016-09-13 11:38:00   修改者asus-pc  修改于2017-05-07 03:21:00字数6921

文档摘要:
关键词:

Chapter 2 Linear List Section 1 Basic Concept 线性表(Linear List)的定义和特点 定义:n( ³ 0)个数据元素的有限序列,记作 (a1, a2, …, an) ai 是表中数据元素,n 是表长度。 遍历 逐项访问: 从前向后 从后向前 Section 2 Sequential List 顺序表 (Sequential List) 顺序表的定义和特点 定义 将线性表中的元素相继存放在一个连续的存储空间中。 可利用一维数组描述存储结构 特点 线性表的顺序存储方式 遍历 顺序访问 顺序表(SeqList)类的定义 template class SeqList { Type *data; //顺序表存储数组 int MaxSize; //最大允许长度 int last; //当前最后元素下标 public: SeqList ( int MaxSize = defaultSize ); ~SeqList ( ) { delete [ ] data; } int Length ( ) const { return last+1; } 顺序表部分公共操作的实现 template //构造函数 SeqList :: SeqList ( int sz ){ if ( sz > 0 ) { MaxSize = sz; last = -1; data = new Type[MaxSize]; if ( data == NULL ) { MaxSize = 0; last = -1; return; } } } 顺序搜索图示 Method Specifications List ::List( ); Post: The List has been created and is initialized to be empty. void List ::clear( ); Post: All List entries have been removed; the List is empty. bool List ::empty( ) const; Post: The function returns true or false according to whether the List is empty or not. bool List ::full( ) const; Post: The function returns true or false according to whether the List is full or not. int List ::size( ) const; Post: The function returns the number of entries in the List. Error code List :: insert ( int position, const List_entry &x); Post: If the List is not full and 0<= position<=n, where n is the number of entries in the List, the function succeeds: Any entry formerly at position and all later entries have their position numbers increased by 1, and x is inserted at position in the List. Else: The function fails with a diagnostic error code. Error code List :: remove ( int position, List_entry &x); Post: If 0<=position class List; template class ListNode { friend class List; Type data; ListNode *link; public: ListNode ( ); ListNode ( const Type& item ); Simply Linked Implementation Node declaration: template struct Node { Node_entry entry; Node *next; Node( ); Node(Node_entry, Node *link = NULL); }; List declaration: template class List { public: ~List( ); List(const List ©); void operator = (const List ©); protected: int count; Node *head; Node *set_position(int position) const; }; template Node *List::set_position(int position) const /* Pre: position is a valid position in the List ; 0<= position < count . Post: Returns a pointer to the Node in position . */ { Node *q = head; for (int i = 0; i < position; i ++ ) q= q->next; return q; } template Error_code List::insert(int position, const List_entry &x) {if(position<0||position>count)return range_error; Node *new_node, *previous, *following; if(position>0){previous=set_position(position-1); following=previous->next; } else following=head; new_node=new Node(x, following); if(new_node==NULL)return overflow; if(position==0)head=new_node; else previous->next = new_node; count++; return success;} In processing a linked List with n entries clear, insert, remove, retrieve, and replace require time approximately proportional to n. List, empty, full, and size operate in constant time. 循环链表 (Circular List) 循环链表是单链表的变形。 循环链表最后一个结点的link指针不为 0 (NULL),而是指向了表的前端。 为简化操作,在循环链表中往往加入表头结点。 循环链表的特点是:只要知道表中某一结点的地址,就可搜寻到所有其他结点的地址。 循环链表的示例 带表头结点的循环链表 循环链表类的定义 用循环链表求解约瑟夫问题 约瑟夫问题的提法 n 个人围成一个圆圈,首先第2个人从1开始一个人一个人顺时针报数, 报到第m个人,令其出列。然后再从下一个人开始,从1顺时针报数,报到第m个人,再令其出列,…,如此下去, 直到圆圈中只剩一个人为止。此人即为优胜者。 例如 n = 3 m = 8 例如 n = 3 m = 8 多项式及其相加 在多项式的链表表示中每个结点增加了一个数据成员link,作为链接指针。 优点是: 多项式的项数可以动态地增长,不存在存储溢出问题。 插入、删除方便,不移动元素。 双向链表 (Doubly Linked List) 双向链表是指在前驱和后继方向都能游历(遍历)的线性链表。 双向链表每个结点结构: 前驱方向ç è后继方向 双向链表通常采用带表头结点的循环链表形式。 结点指向 p == p→lLink→rLink == p→rLink→lLink Node definition template struct Node{ // data members Node_entry entry; Node *next; Node *back; // constructors Node( ); Node(Node_entry, Node *link_back =NULL, Node *link_next = NULL); }; List definition template class List { public: // Add specifications for methods of the list ADT. // Add methods to replace compiler generated defaults. protected: // Data members for the doubly-linked list implementation follow: int count; mutable int current_position; mutable Node *current; // The auxiliary function to locate list positions follows: void set_position(int position) const; }; template void List::set_position(int position) const /* Pre: position is a valid position in the List:      0<=positionnext; else for(;current_position!=position; current_position--)current=current->back; } template Error_code List::insert(int position, const List_entry &x) {Node*new_node,*following,*preceding; if(position<0||position>count)return range_error; if(position==0){if(count==0)following=NULL; else{ set_position(0); following=current;} preceding=NULL;} else{ set_position(position-1); preceding=current; following=preceding->next;} new_node=new Node(x,preceding, following); if (new_node==NULL)return overflow; if (preceding!=NULL)preceding->next=new_node; if (following!=NULL)following->back=new_node; current=new_node; current_position=position; count++; return success; } Comparison of Implementations Contiguous storage is generally preferable 1.when the entries are individually very small; 2.when the size of the list is known when the program is written; 3.when few insertions or deletions need to be made except at the end of the list; 4.when random access is important. Linked storage proves superior 1.when the entries are large; 2.when the size of the list is not known in advance; 3.when flexibility is needed in inserting, deleting, and rearranging the entries. To choose among linked list implementations, consider 1.Which of the operations will actually be performed on the list and which of these are the most important? 2.Is there locality of reference? That is, if one entry is accessed, is it likely that it will next be accessed again?

下载文档到电脑,查找使用更方便

文档的实际排版效果,会与网站的显示效果略有不同!!

需要 10 金币 [ 分享文档获得金币 ] 0 人已下载

下载文档