数据结构与算法b-2014年3月07日课堂listmar

数据结构与算法

—线性结构主讲教员:段凌宇2014年3月7日

北京大学信息科学与技术学院，转载或翻印必究北京大学信息学院，转载或翻印必究Page2大纲2.1线性表(linearlist)2.2顺序表—

向量(vector)2.3链表(linkedlist)2.4线性表实现方法的比较2.5栈(stack)2.6队列(queue)2.7栈与递归(recursivefunction)北京大学信息学院，转载或翻印必究Page3数据的逻辑结构（结点+关系）线性结构（linearstructure）树型结构（treestructure）图结构（graphstructure）数据的存储结构(结点+关系->存储器的映射）顺序(sequential)链接(linked)索引(indexing)散列(hashing)数据的运算(算法->程序->解决问题）

1.2什么是数据结构北京大学信息学院，转载或翻印必究Page4大纲2.1线性表(linearlist)2.1.0线性表的定义和性质2.1.1线性表的抽象数据类型2.1.2线性表的存储结构2.1.3线性表运算分类2.2顺序表—

向量(vector)2.3链表(linkedlist)2.4线性表实现方法的比较2.5栈(stack)2.6队列(queue)2.7栈与递归(recursivefunction)北京大学信息学院，转载或翻印必究Page5线性表的定义线性表(N,r)的定义：由结点集N，以及定义在结点集N上的线性关系r

所组成的线性结构。这些结点称为线性表的元素。线性关系，也称为‘前后关系’，有时也称为‘大小关系’。关系r是有向的，且满足全序性和单索性等约束条件。北京大学信息学院，转载或翻印必究Page6线性表的性质线性表（N,r）的性质：（a）结点集N中有一个唯一的开始结点，它没有前驱，但有一个唯一的后继；（b）对于有限集N，它存在一个唯一的终止结点，该结点有一个唯一的前驱而没有后继；（c）其它的结点皆称为内部结点；每一个内部结点，既有一个唯一的前驱，也有一个唯一的后继；北京大学信息学院，转载或翻印必究Page7线性表的性质（续）（d）线性表所包含的结点个数称为线性表的长度，它是线性表的一个重要参数；长度为0的线性表称为空表；（e）线性表的关系r，简称“前驱关系”，应具有反对称性和传递性(离散数学中的概念)。设R为非空集合N上的二元关系反对称性:(x,y)∈R∧(y,x)∈R→x=y传递性:(x,y)∈R∧(y,z)∈R

→

(x,z)∈R北京大学信息学院，转载或翻印必究Page8大纲2.1线性表(linearlist)2.1.0线性表的定义和性质2.1.1线性表的抽象数据类型2.1.2线性表的存储结构2.1.3线性表运算分类2.2顺序表—

向量(vector)2.3链表(linkedlist)2.4线性表实现方法的比较2.5栈(stack)2.6队列(queue)2.7栈与递归(recursivefunction)北京大学信息学院，转载或翻印必究Page92.1.1线性表的抽象数据类型

取值空间运算集

用类模板表达抽象数据类型北京大学信息学院，转载或翻印必究Page10线性表类模板template<classELEM,intMax_length>classlist//线性表类模板list，模板类型参数ELEM//非类型参数Max_length用于规定所存储线性表的最大长度{private:…

//私有变量，线性表存储空间;例如ELEMelements[Max_length];public: intcurr_len; //公共变量，该线性表的当前长度

intcurr; //公共变量，该线性表的当前“指针”，游标

list(); //构造函数，创建一个空的新线性表

~list();//析构函数,从计算机存储空间删去整个线性表类型参数：用来说明类模板中的属性类型、成员服务的参数类型和返回值类型非类型参数：用来说明类模板中的属性北京大学信息学院，转载或翻印必究Page11 voidclear();//将该线性表的全部元素清除

voidappend(ELEMvalue);//在表的尾部添加一个新元素

voidinsert(inti,ELEMvalue);//第i号位置上插入一个新结点

voidremove(inti);//删去第i号元素，表的长度减1，其后元素前移

ELEMfetch(inti);//读取，返回第i个元素的值}为线性表设计的抽象数据类型并不是唯一的private:ELEM*ptrElement;intsize;public:list(constintsize);北京大学信息学院，转载或翻印必究Page122.1.2线性表的存储结构

定长的一维数组结构即向量型的顺序存储结构，地址相邻存储

缺陷：长度变化不得超过固定长度变长的线性存储结构链接式存储结构，使用指针表示前驱关系串结构、动态数组、以及顺序文件

北京大学信息学院，转载或翻印必究Page132.1.3线性表运算分类

创建线性表的一个实例(list()）线性表消亡（~list()）

获取有关当前线性表的信息

查找、由位置读取等访问线性表并改变线性表的内容或结构添加、更新、删除、清空等线性表的辅助性管理操作游标加减、求表的长度实现算法及其复杂性与采用的存储结构有密切关系北京大学信息学院，转载或翻印必究Page14大纲2.1线性表(linearlist)2.2顺序表—

向量(vector)2.2.1向量的类定义2.2.2向量的运算2.3链表(linkedlist)2.4线性表实现方法的比较2.5栈(stack)2.6队列(queue)2.7栈与递归(recursivefunction)北京大学信息学院，转载或翻印必究Page152.2顺序表—向量(sequentiallist—vector)

采用定长的一维数组存储结构主要特性:元素的类型相同

元素顺序地存储在连续存储空间中，每一个元素有唯一的索引值（下标值）

使用（静态）常数作为向量长度

数组存储；主要优点是读写其元素很方便，通过下标即可指定位置。

北京大学信息学院，转载或翻印必究Page16函数调用过程中涉及的“形参”、“实参”“传递变量指针”、“引用形参”const修饰北京大学信息学院，转载或翻印必究Page17函数调用过程形参与实参voidswap(int,int);//形参为整型变量intmain(){

inti=3,j=4;

cout<<"i="<<i<<",j="<<j<<endl;

swap(i,j);

cout<<"i="<<i<<",j="<<j<<endl;

system("PAUSE");

return0;}

voidswap(inta,intb){//形参为整型变量

inttemp;

temp=a;

a=b;

b=temp;}结果：i=3,j=4i=3,j=4执行函数swap后，形参a和b的改变不会影响实参i和j的值北京大学信息学院，转载或翻印必究Page18函数调用过程形参与实参传给形参的是变量的值传递是单向的；如果在执行函数期间形参的值发生变化，并不传回给实参。因为在调用函数期间，形参和实参不是同一个存储单元。北京大学信息学院，转载或翻印必究Page19函数调用过程形参与实参调用函数时把变量i和j的地址传送给形参p1和p2，因此*p1和i为同一内存单元，*p2和j是同一内存单元。voidswap(int*,int*);//形参为整型指针变量intmain(){

inti=3,j=4;

cout<<"i="<<i<<",j="<<j<<endl;

swap(&i,&j);//变量地址

cout<<"i="<<i<<",j="<<j<<endl;

system("PAUSE");

return0;}

voidswap(int*p1,int*p2){//形参为整型指针变量

inttemp;

temp=*p1;

*p1=*p2;

*p2=temp;}结果：i=3,j=4i=4,j=3北京大学信息学院，转载或翻印必究Page20函数调用过程传递变量指针传给形参的是指针变量，实参是一个变量的地址；调用函数时，形参（指针变量）指向实参变量单元。这种方式还是“值传递”，只不过实参的值是变量的地址而已。在函数中改变的不是实参的值，而是实参地址所指向的变量的值。北京大学信息学院，转载或翻印必究Page21函数调用过程的引用形参voidswap(int

&,

int

&);

//参数为整型变量的引用intmain(){

inti=3,

j=4;

cout<<"i="<<i<<",j="<<j<<endl;

swap(i,

j);

//变量名

cout<<"i="<<i<<",j="<<j<<endl;

system("PAUSE");

return0;}

voidswap(int&a,

int&b){//形参为引用类型

inttemp;

temp=a;

a=b;

b=temp;}结果：i=3,j=4i=4,j=3由实参把变量名传给形参。i的名字传给引用变量a，j的名字传给引用变量b。此时a和b就分别与i,j占用同一内存空间。北京大学信息学院，转载或翻印必究Page22函数调用过程的引用形参这种把实参地址传递到形参，使形参的地址取实参的地址，从而使形参与实参共享同一单元的方式，就是地址传递方式。示例(2)中，传递指针变量要另外开辟内存单元，其内容为地址；而示例(3)引用不是一个独立的变量，不单独占内存单元。示例(3)

中，main函数调用swap函数时，实参不必用函数中变量的地址(即&i,

&j)，而直接使用变量名。系统向形参传递的是实参的地址而不是实参的值。北京大学信息学院，转载或翻印必究Page23函数调用过程中涉及的“形参”、“实参”“传递变量指针”、“引用形参”const修饰北京大学信息学院，转载或翻印必究Page24const修饰函数参数“const”修饰函数参数是它最广泛的一种用途，它表示函数体中不能修改参数的值(包括参数本身的值或者参数其中包含的值)。voidfunction(constintVar);

//传递过来的参数在函数内不可以改变

//(意义不大，因为Var本身就是形参)

voidfunction(constchar*Var);

//参数指针所指内容为常量不可变voidfunction(char*constVar);

//参数指针本身为常量不可变

//(意义不大，因为char*Var也是形参)

参数为引用，为了增加效率同时防止修改。

北京大学信息学院，转载或翻印必究Page25const修饰函数参数“const”修饰函数参数是它最广泛的一种用途，它表示函数体中不能修改参数的值(包括参数本身的值或者参数其中包含的值)。参数为引用，为了增加效率同时防止修改。voidfunction(constClass&Var);//引用参数在函数内不可以改变，

//

Class为定义的某个类voidfunction(constTYPE&Var);//引用参数在函数内为常量不可变，

//

TYPE为定义的某个基本或复合类型

北京大学信息学院，转载或翻印必究Page26enumBoolean{False,True};constintMax_length=100;//假定最大长度为100template<classELEM>//类型参数ELEM表示元素类型Tclasslist{private: intmsize;//私有变量，顺序表实例的最大长度

intcurr_len; //私有变量，顺序表实例的当前长度

ELEM*nodelist;//私有变量，存储顺序表实例的向量public:

intcurr;//当前下标，顺序表的公共变量

list(constintsize);//创建一个新的顺序表，实参传递表实例的最大长度~list();//用于将该表实例从内存中删去2.2.1向量的类定义北京大学信息学院，转载或翻印必究Page27BooleanisEmpty();//当线性表为空时，返回Trueintlength();//返回此顺序表的当前实际长度ELEMcurrValue();//返回当前curr位置的元素值BooleanisInList();//若当前下标curr位置有值时，返回Truevoidappend(constELEM&);//在表尾增添一个新元素，顺序表实际长度加1voidinsert(constELEM&);//在当前下标curr位置插入元素新值ELEMremove();//当前下标curr位置的元素值作为返回值，并删去该元素voidclear();//将顺序表存储的内容清除，成为空表voidsetFirst();//将当前下标curr赋值为第一个元素的位置voidnext();

//将当前下标curr下移一格，即curr+1voidprev();//将当前下标curr上移一格，即curr-1}获取访问辅助管理北京大学信息学院，转载或翻印必究Page282.2.2向量的运算（示例）插入元素运算voidinsert(constELEM&item)

删除元素运算

ELEMremove()

北京大学信息学院，转载或翻印必究Page29插入算法/*

设元素类型为ELEM，nodelist是存储顺序表向量，msize是此向量的最大长度，curr_len是此向量的当前长度，curr为此向量当前下标）*/＃include<assert.h>…template<classELEM>voidlist<ELEM>::insert(constELEM&item){

//需要检查当前长度不能大于或等于msize;//当前游标指针curr不能小于0,也不能大于或等于当前长度;

//此条件不满足时，程序异常，退出运行。

assert((curr_len<msize)&&(curr>=0)&&(curr<curr_len));北京大学信息学院，转载或翻印必究Page30

//从表尾curr_len-1起往右移动直到curr

for

(inti=curr_len;i>curr;i--) nodelist[i]=nodelist[i-1];

//当前指针处插入新元素

nodelist[curr]=item;

//表的实际长度curr_len加1

curr_len++;}循环至i=curr+1，最后一次移动是nodelist[curr]北京大学信息学院，转载或翻印必究Page31插入算法执行时间

元素总个数为k，各个位置插入的概率（可能性）相等，即p＝1/k平均移动元素次数为

:总时间开销估计为：

O（k）

北京大学信息学院，转载或翻印必究Page32删除算法/*设元素类型为ELEM，nodelist是存储顺序表向量，msize是此向量的最大长度，curr_len是此向量的当前长度，curr为此向量当前下标*///返回curr所指的元素值，并从表中删去此元素＃include<assert.h>…template<classELEM>ELEMlist<ELEM>::remove(){

//需要检查当前长度不能大于msize;//当前游标指针curr不能小于0,也不能大于等于当前长度;

//此条件不满足时，程序异常，退出运行。

assert((curr_len<=msize)&&(curr>=0)&&(curr<curr_len));北京大学信息学院，转载或翻印必究Page33ELEMtemp＝

nodelist[curr];//从指针curr到curr_len每个元素往前移一格for(inti=curr;i<curr_len-1;i++)nodelist[i]=nodelist[i+1];curr_len--;//表的实际长度cur