c中文课件程序设计顺序表

1、9/22/20221C+程序设计_顺序表9/22/20222Applied Arrays: Lists and Strings9/22/20223What is a List?A list is a varying-length, linear collection of homogeneous elements.linear means each list element (except the first) has a unique predecessor, and each element (except the last) has a unique successor 9/22/202

2、243 Basic Kinds of ADT OperationsConstructor - creates a new instance (object) of an ADT Transformer - changes the state of one or more of the data values of an instance Observer - allows us to observe the state of one or more of the data values of an instance without changing them 49/22/20225ADT Li

3、st OperationsTransformers Insert DeleteSelSortObservers IsEmptyIsFullLengthIsPresentPrintchange stateobserve state59/22/20226ADT Unsorted List Data Componentslengthdata 0 . . MAX_LENGTH -1 number of elements in listarray of list elementsnumber of elements in listarray of list elements9/22/20227 Arra

4、y-based class ListIsFull Length SelSortIsPresentDelete IsEmptyInsert PrintPrivate data:lengthdata 0 1 2 MAX_LENGTH-19/22/20228/ SPECIFICATION FILE ARRAY-BASED LIST( list.h )const int MAX_LENGTH = 50 ;typedef int ItemType ;class List/ declares a class data typepublic : / public member functionsList (

5、 ) ;/ constructorbool IsEmpty ( ) const ;bool IsFull ( ) const ; int Length ( ) const ; / returns length of list void Insert ( ItemType item ) ; void Delete ( ItemType item ) ; bool IsPresent( ItemType item ) const ;void SelSort ( );void Print ( ) ; private :/ private data membersint length ; / numb

6、er of values currently storedItemTypedataMAX_LENGTH ; ;9/22/20229Sorted and Unsorted Lists UNSORTED LISTElements are placed into the list in no particular order. SORTED LISTList elements are in an order that is sorted in some way - either numerically or alphabetically.9/22/202210/ IMPLEMENTATION FIL

7、E ARRAY-BASED LIST ( list.cpp )#include “list.h”#include using namespace std;int List : Length ( ) const/ Post:Function value = length return length ;bool List : IsFull ( ) const/ Post:Function value = true, if list = MAX_LENGTH /= false, otherwisereturn ( length = MAX_LENGTH ) ;9/22/202211List : Li

8、st ( )/ Constructor/ Post: length = 0length = 0 ;void List : Insert ( /* in */ ItemType item )/ Pre: length MAX_LENGTH & item is assigned/ Post: datalengthentry = item & length = lengthentry + 1data length = item ;length+ ;9/22/202212Before Inserting 64 into anUnsorted Listlength 3data 0 15 1 39 2 -

9、90 3 . . . MAX_LENGTH-1The item willbe placed intothe length location,and length will beincremented.item 649/22/202213After Inserting 64 into anUnsorted Listlength 4data 0 15 1 39 2 -90 3 64 . . . MAX_LENGTH-1The item willbe placed intothe length location,and length will beincremented.item 649/22/20

10、2214bool List : IsEmpty ( ) const/ Post:Function value = true, if length = 0/= false, otherwisereturn ( length = 0 ) ;bool List : IsPresent ( /* in */ ItemType item ) const / Searches the list for item, reporting whether it was found/ Post:Function value = true, if item is in data 0 . . length-1 / =

11、 false, otherwise int index = 0 ;while ( index length & item != data index )index+ ; return ( index 0 & item is assigned/ Post:IF item is in data array at entry/First occurrence of item is no longer in array/ & length = lengthentry - 1/ELSE/ length and data array are unchanged int index = 0 ; while

12、( index length & item != data index )index+;/ if item found, move last element into items placeif ( index length ) data index = data length - 1 ;length- ; 9/22/202216Deleting 39 from anUnsorted Listindex : 0 39 hasnot been matched.item 39length 4data 0 15 1 39 2 -90 3 64 . . . MAX_LENGTH-19/22/20221

13、7Deleting 39 from anUnsorted Listindex : 1 item 39length 4data 0 15 1 39 2 -90 3 64 . . . MAX_LENGTH-139 hasbeen matched.9/22/202218Deleting 39 from anUnsorted Listindex : 1 item 39length 3data 0 15 1 64 2 -90 3 64 . . . MAX_LENGTH-1Decremented length.9/22/202219void List : Print ( ) / Prints the li

14、st/ Post:Contents of data 0 . . length-1 have been output int index ;for ( index = 0 ; index length ; index+ )cout data index endl ;Printing the List9/22/202220Sorting什么是排序？设有n个结点的一个序列R1，R2，Rn，它们对应的关键字值序列为K1，K2，Kn，排序就是要确定出这n个结点的一个新的序列Rq1,Rq2, Rqn，这个新序列中结点的关键字Kq1，Kq2，Kqn满足递增或递减的关系，即Kq1Kq2Kqn; 或Kq1Kq2

15、Kqn；9/22/202221排序方法的稳定性排序的过程中，如果具有相同关键字的那些结点排序前后它们在结点序列中的先后相对次序保持不变，则称这种排序方法是稳定的；否则，称这种排序方法是不稳定的。例如：一组数 5，2，6，3， 2 ，用一种排序方法排序后，这组数成为：2， 2 ，3，5，6则这种排序方法是稳定的。而用另一种排序方法排序后，这组数成为： 2 ， 2 ，3，5，6则这种排序方法是不稳定的。9/22/202222选择排序 选择排序的方法是：每次从待排序结点序列中选出结点值最小或最大的，然后将它放在已排好序的结点序列的尾部或前部，直到待排序序列已无任何结点。一种算法是：对n个待排序结点做

16、n-1次的扫描，第一次扫描找出整个结点序列中结点值最小的，并且将它与第一个结点交换位置。第二次扫描从第二个结点开始，找出剩余的n-1个结点中结点值最小的，并把它与第二个结点交换位置，如此重复至n-1次。则整个结点序列已是排好序。 9/22/202223选择排序执行过程(不稳定的) 9/22/202224void List : SelSort ( ) / Sorts list into ascending order using selection sort ItemType temp ;int passCount ;int sIndx ;int minIndx ; / index of min

17、imum so far for ( passCount = 0 ; passCount length - 1 ; passCount+ )minIndx = passCount ; / find index of smallest of data passCount . . length-1 for ( sIndx = passCount + 1 ; sIndx length ; sIndx+ ) if ( data sIndx = 0 & item data index )data index + 1 = data index ;index- ; / insert item into arr

18、aydata index + 1 = item ; length+ ;9/22/202230Delete Algorithm for SortedList ADTfind the position of the element to be deleted from the sorted list eliminate space occupied by the item being deleted by shifting up all the larger list elements decrement length 9/22/202231void SortedList : Delete ( /

19、* in */ ItemType item ) bool found ;/ true, if item is foundint position ;/ position of item, if foundint index ;/ find location of element to be deletedBinSearch ( item, found, position) ;if ( found )/ shift up elements that follow deleted item in sorted listfor ( index = position ; index = first & !found )middle = ( first + last ) / 2 ;/ INDEX OF M