北京大学：《数据结构与算法》课程教学资源（实验班PPT课件）第二章线性表、栈和队列

2.1 线性表(linear list) 2.2 顺序表—向量(Sequential list— vector ) 2.3 链表(Linked list) 2.4 线性表实现方法的比较 2.5 栈(Stack) 2.6 队列(Queue)

团购合买资源类别：文库，文档格式：PDF，文档页数：124，文件大小：702.73KB

资源提示作业提交ftp更改实验班作业提交 ftp:/dshonoradsoZhonor@fusiongrids.cn 实习课作业提交 tp:/dsproi:dso7proi@fusion,grids.cn 讲义和作业发布不变实验班讲义和作业发布(包括实习作业) http://db.pku.edu.cn/mzhang/ds/honor/ 实习课讲义和作业发布 http:/db.pkuedu.cn/mzhang/ds/shixil back 北京大学信息学院张铭编写版权所有,转载或翻印必究 Page 2

北京大学信息学院张铭编写 ©版权所有，转载或翻印必究 Page 2 back next 资源提示作业提交ftp更改实验班作业提交 ftp://ds_honor:ds07honor@fusion.grids.cn 实习课作业提交 ftp://ds_proj:ds07proj@fusion.grids.cn 讲义和作业发布不变实验班讲义和作业发布（包括实习作业） http://db.pku.edu.cn/mzhang/ds/honor/ 实习课讲义和作业发布 http://db.pku.edu.cn/mzhang/DS/shixi/

线性结构分类线性结构直接访问型顺序访问型目录索引型向量记录字典散列表顺序文件广义表栈队列

北京大学信息学院张铭编写 ©版权所有，转载或翻印必究 Page 5 back next 2.1 线性表(linear list) 逻辑定义：由结点集N，以及定义在结点集，以及定义在结点集N 上的线性关系r所组成的线性结构所组成的线性结构结点：线性表的元素结点：线性表的元素唯一的起点：没有前驱，有一个唯一的后继唯一的起点：没有前驱，有一个唯一的后继唯一的终点：有一个唯一的前驱而没有后继唯一的终点：有一个唯一的前驱而没有后继内部结点：有唯一的前驱，唯一的后继内部结点：有唯一的前驱，唯一的后继结点个数：线性表的长度结点个数：线性表的长度线性表的关系r，简称前驱关系，简称前驱关系反对称性、传递性反对称性、传递性

implate class list/线性表类模板list,模板参数ELEM listo;∥刨建一个空的新线性表 clist(; ∥/从计算机存储空间删去整个线性表 void clear0;∥将该线性表的全部元素清除,成为空表 void append( ELEM value);∥尾附函数,在表尾加新元素 void insert(int i, ELEM value);∥/插入函数,在第i号位插入 void remove(int 1) ∥删除函数,删去第号元素 baCELEM fetch(int;/读取,返回第i个元素的值 }北京大学信息学院张铭编写版权所有,转载或翻印必究 Page 6

北京大学信息学院张铭编写 ©版权所有，转载或翻印必究 Page 6 back next template class list //线性表类模板list，模板参数ELEM { list(); // 创建一个空的新线性表 ~list(); // 从计算机存储空间删去整个线性表 void clear() ; // 将该线性表的全部元素清除，成为空表 void append(ELEM value) ; // 尾附函数，在表尾加新元素 void insert(int i, ELEM value) ; // 插入函数，在第i号位插入 void remove(int i); // 删除函数，删去第i号元素 ELEM fetch(int i); //读取，返回第i个元素的值 }

顺序表类定义 const int max length=100;/假定最大长度为100 class list i ∥顺序表,向量 private Int maize ∥顺序表最大长度 int curr len;∥顺序表当前长度 ELEM* nodelist;∥私有变量,存储顺序表实例的向量 publIc: ∥以下列出成员函数(顺序表的函数集) int curre;∥当前下标,顺序表的公共变量 ist( const int size);∥ constructor函数,创建新表 cristo ∥ destructor函数,将该表实例删去 void clear(;/清除内容,成为空表 back 北京大学信息学院张铭编写版权所有,转载或翻印必究 Page 8

北京大学信息学院张铭编写 ©版权所有，转载或翻印必究 Page 8 back next 顺序表类定义 const int Max_length = 100; // 假定最大长度为100 class list { // 顺序表，向量 private : int msize; // 顺序表最大长度 int curr_len; // 顺序表当前长度 ELEM* nodelist; //私有变量，存储顺序表实例的向量 public: //以下列出成员函数（顺序表的函数集) int curr; //当前下标，顺序表的公共变量 list(const int size) ; // constructor函数,创建新表 ~list(); //destructor函数，将该表实例删去 void clear(); //清除内容，成为空表

void set First(;∥第一个元素位置赋予当前下标curr void nexto; ∥/curr下移一格,即curr+1 void prevo; 将curr上移一格,即curr-1 bool isIn list(O;∥若curr位置有值时,返回true void append( const ELEM&);∥在表尾增添新元素 void insert( const ELEM&);∥在当前下标cur插入 ELEM remove;/返回cur的位置元素值,并删除 bool isEmpty 0; ∥线性表为空时,返回true ELEM currValueo 返回curr位置的元素值 It length ∥返回此表的当前实际长度北京大学信息学院张铭编写版权所有,转载或翻印必究 Page 9

北京大学信息学院张铭编写 ©版权所有，转载或翻印必究 Page 9 back next void setFirst(); // 第一个元素位置赋予当前下标curr void next(); // curr下移一格，即curr+1 void prev(); //将curr上移一格，即curr-1 bool isInList(); // 若curr位置有值时，返回true void append(const ELEM&); //在表尾增添新元素 void insert(const ELEM&); // 在当前下标curr插入 ELEM remove(); //返回curr的位置元素值，并删除 bool isEmpty(); //当线性表为空时，返回true ELEM currValue(); //返回curr位置的元素值。 int length(); // 返回此表的当前实际长度 }

nodelist k-1 maize nodelist仁 Item 01 k maize (a)在t位置插入元素item nodelist k-1 mize nodelist mize (b)删除t位置的元素

点击进入文档下载页（PDF格式）

共124页，可试读30页，点击继续阅读 ↓↓

点击下载（PDF格式）

浏览记录