南京大学：《数据结构 Data Structures》课程教学资源（PPT课件讲稿）第二章 线性表

DATA STRUCTURES 第2章线性表 线性表 顺序表 单链表 循环链表 双向链表 多项式 Department of Computer Science Technology, Nanjing University fall 2008

Department of Computer Science & Technology, Nanjing University fall 2008 DATA STRUCTURES 1 第2章 线性表 ◼线性表 ◼顺序表 ◼单链表 ◼循环链表 ◼双向链表 ◼多项式

DATA STRUCTURES 21线性表( Linear list 线性表的定义 g线性表是nC0)个数据元素的有限序列 19u29 a1是表中数据元素,n是表长度。 a原则上讲,线性表中表元素的数据类型可以不 相同。但采用的存储表示可能会对其有限制。 a为简单起见,假定各元素类型相同。 Department of Computer Science Technology, Nanjing University fall

Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES ◼ 线性表的定义  线性表是 n (≥0) 个数据元素的有限序列 （a1 , a2 , …, an） ai 是表中数据元素，n 是表长度。  原则上讲，线性表中表元素的数据类型可以不 相同。但采用的存储表示可能会对其有限制。  为简单起见，假定各元素类型相同。 2.1 线性表 (Linear List)

DATA STRUCTURES 线性表的特点 除第一个元素外,其他每一个元素有一个且 仅有一个直接前驱。 口除最后一个元素外,其他每一个元素有一个 且仅有一个直接后继。 →a2 直接前驱和直接后继描述了结点之间的逻辑关系 即邻接关系) Department of Computer Science Technology, Nanjing University fall

Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES 直接前驱和直接后继描述了结点之间的逻辑关系 （即邻接关系） a1 a2 a3 a4 a5 a6 ◼ 线性表的特点  除第一个元素外，其他每一个元素有一个且 仅有一个直接前驱。  除最后一个元素外，其他每一个元素有一个 且仅有一个直接后继

DATA STRUCTURES 线性表的抽象基类(ADT) template class linearlist i public Linearlisto 1构造函数 w Linearlisto: 析构函数 virtual int size0 const=0,/求表最大体积 virtual int Length0 const=0;求表长度 virtual int search(Tx) const=0;搜索 virtual int locate(inti) const=0;定位 virtual E* getData(inti) const=0;/取值 Ⅵ irtual void setdata(inti,Ex)=0;∥赋值 Department of Computer Science Technology, Nanjing University fall

Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES 线性表的抽象基类(ADT) template class LinearList { public: LinearList(); //构造函数 ～LinearList(); //析构函数 virtual int Size() const = 0; //求表最大体积 virtual int Length() const = 0; //求表长度 virtual int Search(T x) const = 0; //搜索 virtual int Locate(int i) const = 0; //定位 virtual E* getData(int i) const = 0; //取值 virtual void setData(int i, E x) = 0; //赋值

DATA STRUCTURES virtual bool Insert(int i,E x)=0 1插入 irtual bool remove(inti,E&x)=0;/删除 virtual bool Isempty0 const=0;判表空 virtual bool s fu0 const=0;判表满 virtual void Sorto=0 排序 virtual void input=0 入 virtual void output=0 i 出 virtual linearlistoperator= Linearlist'&L=0,/复制 Department of Computer Science Technology, Nanjing University fall

Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES virtual bool Insert(int i, E x) = 0; //插入 virtual bool Remove(int i, E& x) = 0; //删除 virtual bool IsEmpty() const = 0; //判表空 virtual bool IsFull() const = 0; //判表满 virtual void Sort() = 0； //排序 virtual void input() = 0； //输入 virtual void output() = 0； //输出 virtual LinearListoperator= (LinearList& L) = 0; //复制 };

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 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 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 last？NULL : data[i]; } }

DATA STRUCTURES 顺序表部分公共操作的实现 template //构造函数 Seqlist: 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 //构造函数 SeqList :: SeqList ( int sz ) { if ( sz > 0 ) { MaxSize = sz; last = -1; data = new Type[MaxSize]; if ( data == NULL ) { cerr << “存储分配错” << endl; } } }