DATA STRUCTURES 22顺序表( Sequential List) 顺序表的定义和特点: 定义:顺序存储的n(≥0)个表项的有限序列 (a1,a2,…,an a是表项,n是表长度。 特点:所有元素的逻辑先后顺序与其物理存放顺序 一致; 0 2345 data253457164809 可以进行顺序访问也可以进行随机访问 Department of Computer Science Technology, Nanjing University fall
Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES 25 34 57 16 48 09 0 1 2 3 4 5 data 2.2 顺序表 (Sequential List) ◼ 顺序表的定义和特点： 定义：顺序存储的 n（ 0）个表项的有限序列 （a1 , a2 , …, an） ai是表项，n是表长度。 特点：所有元素的逻辑先后顺序与其物理存放顺序 一致; 可以进行顺序访问,也可以进行随机访问
DATA STRUCTURES 顺序表的静态存储和动态存储 #define max Size 100 typedef int T typedef struct T data maxSize;∥顺序表的静态存储表示 t n Seqlist; typedef int T typedef struct 工 *data 顺序表的动态存储表示 Int maxSize, n; Seqlist Department of Computer Science Technology, Nanjing University fall
Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES 顺序表的静态存储和动态存储 #define maxSize 100 typedef int T; typedef struct { T data[maxSize]; //顺序表的静态存储表示 int n; } SeqList; typedef int T; typedef struct { T *data; //顺序表的动态存储表示 int maxSize, n; } SeqList;
DATA STRUCTURES 顺序表( Sealine类的定义P46 const int defaultsize= 100 template <class Type> class seqlist Type*lata;顺序表存储数组 int max size;/最大允许长度 int last /当前最后元素下标 p publico Seqlist( int sz= defaultSize cSeq list oi delete d data; int Length const return last+1; int Find Type &x)const Department of Computer Science Technology, Nanjing University fall
Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES 顺序表(SeqList)类的定义 P.46 const int defaultSize = 100; template <class Type> class SeqList { Type *data; //顺序表存储数组 int MaxSize; //最大允许长度 int last; //当前最后元素下标 public: SeqList ( int sz = defaultSize ); ~SeqList ( ) { delete [ ] data; } int Length ( ) const { return last+1;} int Find ( Type & x ) const;
DATA STRUCTURES int IsIn Type x); int Insert Type &x, int i) int Remove( type &x; int Next( type &x); int Prior( type &x); int /sEmpty(freturn last ==-1 int IsFullofreturn last = MaxSize-1 pe Get (int y tiC return l ‖i>last?N 0‖i data } Department of Computer Science Technology, Nanjing University fall
Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES int IsIn ( Type & x ); int Insert ( Type & x, int i ); int Remove ( Type & x ); int Next ( Type & x ) ; int Prior ( Type & x ) ; int IsEmpty ( ) { return last ==-1; } int IsFull ( ) { return last == MaxSize-1;} Type Get ( int i ) { return i < 0 || i > last？NULL : data[i]; } }
DATA STRUCTURES 顺序表部分公共操作的实现 template <class Type> //构造函数 Seqlist<Type>: Seqlist(int sz f(sz>0){ Max size = sz last=-1: data=new Type MaxSize if( data== NULL cerr<“存储分配错”<<endl; Department of Computer Science Technology, Nanjing University fall
Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES 顺序表部分公共操作的实现: template <class Type> //构造函数 SeqList<Type> :: SeqList ( int sz ) { if ( sz > 0 ) { MaxSize = sz; last = -1; data = new Type[MaxSize]; if ( data == NULL ) { cerr << “存储分配错” << endl; } } }