线性链表 单链表的结点类 lListNode class)和链表类 List class)的类定义。 template <class Type>class list //前视的类定义 template <class Type>class ListNode i //链表结点类的定义 friend class List<Type> //List类作为友元类定义 ListNode <Type >*link /链指针域 ListNode(): link (NULL)(] //仅初始化指针成员的构造函数 ListNode( const Type& item) data (item), link (NULL)I /初始化数据与指针成员的构造函数 ListNode<Type>* getNode const Type item, ListNode<Type>*next NULL /以item和next建立一个新结点 ListNode<Type>* getLink ()i return link; 取得结点的下一结点地址 Type getData()i return data; F //取得结点中的数据 void setLink( ListNode<Type>* next) link next 修改结点的1ink指针 void setData Type value)i data value: K //修改结点的data值 template <class Type>class List /单链表类定义 ListNode<type> *first, *current //链表的表头指针和当前元素指针 const Type& value )(first new ListNode<Type>( //构造函数 List() Make Empty ( delete first: 1 //析构函数 void Make Empty ( //将链表置为空表 int Length ()const //计算链表的长度
10 } 线性链表 单链表的结点类(ListNode class)和链表类(List class)的类定义。 template <class Type> class List; //前视的类定义 template <class Type> class ListNode { //链表结点类的定义 friend class List<Type>; //List 类作为友元类定义 private: Type data; //数据域 ListNode<Type> *link; //链指针域 public: ListNode ( ) : link (NULL) { } //仅初始化指针成员的构造函数 ListNode ( const Type& item ) : data (item), link (NULL) { } //初始化数据与指针成员的构造函数 ListNode<Type> * getNode ( const Type& item, ListNode<Type> *next = NULL ) //以 item 和 next 建立一个新结点 ListNode<Type> * getLink ( ) { return link; } //取得结点的下一结点地址 Type getData ( ) { return data; } //取得结点中的数据 void setLink ( ListNode<Type> * next ) { link = next; } //修改结点的 link 指针 void setData ( Type value ) { data = value; } //修改结点的 data 值 }; template <class Type> class List { //单链表类定义 private: ListNode<Type> *first, *current; //链表的表头指针和当前元素指针 public: List ( const Type& value ) { first = current = new ListNode<Type> ( value ); } //构造函数 ~List ( ) { MakeEmpty ( ); delete first; } //析构函数 void MakeEmpty ( ); //将链表置为空表 int Length ( ) const; //计算链表的长度
ListNode<Type>* Find( Type value ) //搜索含数据 value的元素并成为当前元素 ListNode<Type>* Locate( int i //搜索第i个元素的地址并置为当前元素 Type GetData () //取出表中当前元素的值 int Insert( Type value //将 value插在表当前位置之后并成为当前元素 //将链表中的当前元素删去,填补者为当前元素 Listnode<Type)* Firster(){ current= first; return first;}//当前指针定位于表头结点 Type *First () /当前指针定位于表中第一个元素并返回其值 Type米Next( //将当前指针进到表中下一个元素并返回其值 int NotNull(){ return current!=NULL;}//表中当前元素空否?空返回1,不空返回0 int NextNotNull() return current ! NULL & current->link ! NULL: 1 //当前元素下一元素空否?空返回1,不空返回0 2-6线性表可用顺序表或链表存储。试问: (1)两种存储表示各有哪些主要优缺点? (2)如果有n个表同时并存,并且在处理过程中各表的长度会动态发生变化,表的总数也可能自 动改变、在此情况下,应选用哪种存储表示?为什么? (3)若表的总数基本稳定,且很少进行插入和删除,但要求以最快的速度存取表中的元素,这时 应采用哪种存储表示?为什么? 【解答】 (1)顺序存储表示是将数据元素存放于一个连续的存储空间中,实现顺序存取或(按下标)直接存 取。它的存储效率高,存取速度快。但它的空间大小一经定义,在程序整个运行期间不会发生改变, 因此,不易扩充。同时,由于在插入或删除时,为保持原有次序,平均需要移动一半(或近一半)元素, 修改效率不高 链接存储表示的存储空间一般在程序的运行过程中动态分配和释放,且只要存储器中还有空间, 就不会产生存储溢出的问题。同时在插入和删除时不需要保持数据元素原来的物理顺序,只需要保持 原来的逻辑顺序,因此不必移动数据,只需修改它们的链接指针,修改效率较高。但存取表中的数据 元素时,只能循链顺序访问,因此存取效率不高 (2)如果有n个表同时并存,并且在处理过程中各表的长度会动态发生变化,表的总数也可能自 动改变、在此情况下,应选用链接存储表示 如果采用顺序存储表示,必须在一个连续的可用空间中为这n个表分配空间。初始时因不知道哪 个表增长得快,必须平均分配空间。在程序运行过程中,有的表占用的空间增长得快,有的表占用的 空间增长得慢;有的表很快就用完了分配给它的空间,有的表才用了少量的空间,在进行元素的插入 时就必须成片地移动其他的表的空间,以空出位置进行插入;在元素删除时,为填补空白,也可能移 动许多元素。这个处理过程极其繁琐和低效。 如果采用链接存储表示,一个表的存储空间可以连续,可以不连续。表的增长通过动态存储分配 解决,只要存储器未满,就不会有表溢出的问题;表的收缩可以通过动态存储释放实现,释放的空间 还可以在以后动态分配给其他的存储申请要求,非常灵活方便。对于n个表(包括表的总数可能变化 共存的情形,处理十分简便和快捷。所以选用链接存储表示较好 (3)应采用顺序存储表示。因为顺序存储表示的存取速度快,但修改效率低。若表的总数基本稳 定,且很少进行插入和删除,但要求以最快的速度存取表中的元素,这时采用顺序存储表示较好。 2-7针对带表头结点的单链表,试编写下列函数。 (1)定位函数 Locate:在单链表中寻找第i个结点。若找到,则函数返回第i个结点的地址:若
11 ListNode<Type> * Find ( Type value ); //搜索含数据 value 的元素并成为当前元素 ListNode<Type> * Locate( int i ); //搜索第 i 个元素的地址并置为当前元素 Type * GetData ( ); //取出表中当前元素的值 int Insert ( Type value ); //将 value 插在表当前位置之后并成为当前元素 Type *Remove ( ); //将链表中的当前元素删去, 填补者为当前元素 ListNode<Type> * Firster ( ) { current = first; return first; } //当前指针定位于表头结点 Type *First ( ); //当前指针定位于表中第一个元素并返回其值 Type *Next ( ); //将当前指针进到表中下一个元素并返回其值 int NotNull ( ) { return current != NULL; } //表中当前元素空否？空返回 1, 不空返回 0 int NextNotNull ( ) { return current != NULL && current->link != NULL; } //当前元素下一元素空否？空返回 1, 不空返回 0 }; 2-6 线性表可用顺序表或链表存储。试问： (1) 两种存储表示各有哪些主要优缺点? (2) 如果有 n 个表同时并存，并且在处理过程中各表的长度会动态发生变化，表的总数也可能自 动改变、在此情况下，应选用哪种存储表示？为什么？ (3) 若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，这时， 应采用哪种存储表示？为什么？ 【解答】 (1) 顺序存储表示是将数据元素存放于一个连续的存储空间中，实现顺序存取或(按下标)直接存 取。它的存储效率高，存取速度快。但它的空间大小一经定义，在程序整个运行期间不会发生改变， 因此，不易扩充。同时，由于在插入或删除时，为保持原有次序，平均需要移动一半(或近一半)元素， 修改效率不高。 链接存储表示的存储空间一般在程序的运行过程中动态分配和释放，且只要存储器中还有空间， 就不会产生存储溢出的问题。同时在插入和删除时不需要保持数据元素原来的物理顺序，只需要保持 原来的逻辑顺序，因此不必移动数据，只需修改它们的链接指针，修改效率较高。但存取表中的数据 元素时，只能循链顺序访问，因此存取效率不高。 (2) 如果有 n 个表同时并存，并且在处理过程中各表的长度会动态发生变化，表的总数也可能自 动改变、在此情况下，应选用链接存储表示。 如果采用顺序存储表示，必须在一个连续的可用空间中为这 n 个表分配空间。初始时因不知道哪 个表增长得快，必须平均分配空间。在程序运行过程中，有的表占用的空间增长得快，有的表占用的 空间增长得慢；有的表很快就用完了分配给它的空间，有的表才用了少量的空间，在进行元素的插入 时就必须成片地移动其他的表的空间，以空出位置进行插入；在元素删除时，为填补空白，也可能移 动许多元素。这个处理过程极其繁琐和低效。 如果采用链接存储表示，一个表的存储空间可以连续，可以不连续。表的增长通过动态存储分配 解决，只要存储器未满，就不会有表溢出的问题；表的收缩可以通过动态存储释放实现，释放的空间 还可以在以后动态分配给其他的存储申请要求，非常灵活方便。对于 n 个表(包括表的总数可能变化) 共存的情形，处理十分简便和快捷。所以选用链接存储表示较好。 (3) 应采用顺序存储表示。因为顺序存储表示的存取速度快，但修改效率低。若表的总数基本稳 定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，这时采用顺序存储表示较好。 2-7 针对带表头结点的单链表，试编写下列函数。 (1) 定位函数 Locate：在单链表中寻找第 i 个结点。若找到，则函数返回第 i 个结点的地址；若