线性表演示文稿

线性表演示文稿目前一页\总数三十一页\编于八点优选线性表目前二页\总数三十一页\编于八点数据结构概论知识点2.1.线性表的概念线性表的抽象数据类型线性表的存储结构线性表运算分类2.2.顺序表(向量)顺序表的类定义顺序表的运算实现2.3.链表单链表双链表循环链表2.4.线性表实现方法的比较目前三页\总数三十一页\编于八点本章讨论几种常用的线性数据结构(统称为线性表)：顺序表（也称为向量，是用顺序结构实现的线性表），类似于C/C++语言中的数组，实现了封装、提供了丰富的功能。链表（用链式结构实现的线性表）：链式结构的线性表，在结点中附件指针域来表达结点之间的前驱/后继关系。单链表；双链表；循环链表：循环单链表，循环双链表。目前四页\总数三十一页\编于八点2.1线性表线性表是一类线性（区别于树形结构和图结构）数据结构，它有多种存储结构和应用方法，从而可以细分为顺序表、链表、队列、栈等。“线性表”是从逻辑结构的角度来描述数据结构的，它主要有两种存储结构：顺序存储结构和链式存储结构。目前五页\总数三十一页\编于八点2.1.1线性表的抽象数据类型线性表：直观地讲，线性表的特点是它的所有结点可以排列成一个线性序列，n0→n1→n2→…→nk。在线性表中：有唯一的开始结点，它没有前驱；其他结点都有唯一的前驱结点。有唯一的末尾结点，它没有后继；其他结点都有唯一的后继结点。除开始结点和末尾结点外，其他结点称为中间结点，中间结点有唯一的前驱和后继。可以从离散数学的角度对线性表进行严格定义(略)。目前六页\总数三十一页\编于八点2.1.3线性表的存储结构线性表的存储结构：如何开辟存储空间，各结点存储空间的联系，如何实现等。线性表的存储结构主要有两种：定长的顺序存储结构。特点是线性表结点可以按地址相邻的顺序存储在一片连续的存储空间中，线性表的固定长度限制了线性表结点个数变化不能超过该固定长度。变长的线性存储结构。具体形式有链式存储结构，动态数组等。在链式存储结构中，各结点的存储空间动态申请和释放，通过指针域来表达结点的前驱/后继关系。动态数组：定长数组的变形，当结点个数超出最大限度时，重新申请更长的数组（new和delete运算符）。目前七页\总数三十一页\编于八点2.1.2线性表运算分类典型的运算：增(加)、删(除)、查(找)、(修)改。目前八页\总数三十一页\编于八点2.2顺序表－向量顺序表(sequentiallist)又称为向量(vector)，它采用定长的一维数组存储结构。向量的主要特性：元素的类型相同。元素顺序地存储在一块有连续地址的存储空间中，每一个元素按其顺序有唯一的索引值，又称下标值，用它可以方便地访问元素内容。顺序表类似于C/C++语言中的数组，将各种操作封装一个类。目前九页\总数三十一页\编于八点向量的抽象数据类型向量的抽象数据类型数据成员：向量长度，当前元素个数，指向元素所占存储空间的指针。函数成员(操作)：追加元素、插入元素、删除元素、查找、判空、判满、输出所有结点的值。目前十页\总数三十一页\编于八点顺序表的类定义//顺序表的类定义template<classT>classarrList{private: T*aList;//int*aList; intmaxSize; intcurLen; intposition;public: arrList(constintsize){ maxSize=size; aList=newT[maxSize];//aList=newint[maxSize]; curLen=position=0; } ~arrList(){ delete[]aList; }

voidclear(){ delete[]aList; curLen=position=0; aList=newT[maxSize];} intlength(); boolappend(constTvalue); boolinsert(constintp,constTvalue); booldeletion(constintp); boolsetValue(constintp,constTvalue); boolgetValue(constintp,T&value); boolgetPos(int&p,constTvalue);};目前十一页\总数三十一页\编于八点template<classT>boolarrList<T>::setValue(constintp,constTvalue){ if(…) … T[p]=value; returntrue;}template<classT>boolarrList<T>::getValue(constintp,T&value){ if(…) … value=T[p]; returntrue;}目前十二页\总数三十一页\编于八点顺序表的运算实现顺序表的检索//arrList_getPos线性表的检索template<classT>boolarrList<T>::getPos(int&p,constTvalue){ inti; for(i=0;i<n;i++) if(value==aList[i]){ p=i; returntrue; } returnfalse;}

目前十三页\总数三十一页\编于八点顺序表的运算实现顺序表的插入//arrList_insert线性表的插入template<classT>boolarrList<T>::insert(constintp,constTvalue){ inti; if(curLen>=maxSize){ cout<<"Thelistisoverflow"<<endl; returnfalse; } if(p<0||p>curLen){ cout<<"Insertionpointisillegal"<<endl; returnfalse; } for(i=curLen;i>p;i--) aList[i]=aList[i-1]; aList[p]=value; curLen++; returntrue;}

目前十四页\总数三十一页\编于八点15插入算法的执行时间插入操作的主要代价体现在表中元素的移动

在位置i插入元素，需移动k-i个元素元素总个数为k，假设各个位置插入的概率相等，均为p＝1/k平均移动元素次数为总时间开销估计为O(k)目前十五页\总数三十一页\编于八点顺序表的运算实现顺序表的删除//arrList_deletion线性表的删除template<classT>boolarrList<T>::deletion(constintp){ inti; if(curLen<=0){ cout<<"Noelementtodelete\n"<<endl; returnfalse; } if(p<0||p>curLen-1){ cout<<"deletionisillegal\n"<<endl; returnfalse; } for(i=p;i<curLen-1;i++) aList[i]=aList[i+1]; curLen--; returntrue;}

目前十六页\总数三十一页\编于八点2.3链表链表(linked

list)的特点是动态申请内存空间，并通过指针来链接结点，按照线性表的前驱/后继关系把一个个结点链接起来。几种用于线性表的链式存储结构：单链表；双链表；循环单链表；循环双链表。链表存储是最常用的存储方式之一，它不仅可以用来表示线性表，而且也可以用于其他非线性的数据结构中，如树结构和图结构。目前十七页\总数三十一页\编于八点2.3.1单链表在单链表中，每个结点由两部分组成：存放结点数据的data域；存放指向后继结点的next指针域。因为每个结点中只有指向后继结点的指针，因此由这种结点链接而成的链表，称为单链表。表首指针head：指向单链表中第0个结点(结点序号从0开始计起)。template<classT>classLink //单链表中的结点类{public: Tdata; Link<T>*next; Link();};目前十八页\总数三十一页\编于八点单链表的抽象数据类型数据成员：表首指针head，单链表长度len。函数成员(操作)：查找结点、插入结点、删除结点、求单链表长度、输出所有结点的值。目前十九页\总数三十一页\编于八点20单链表的结点类型template<classT>classLink{public: T data; //用于保存结点元素的内容 Link<T> *next; //指向后继结点的指针

Link(constTinfo,constLink<T>*nextValue=NULL){ data=info; next=nextValue; } Link(constLink<T>*nextValue){ next=nextValue; }};目前二十页\总数三十一页\编于八点21单链表的定义template<classT>classlnkList:publicList<T>{ private: Link<T>*head; //单链表的头 intlength; Link<T>*setPos(constintp); //返回线性表指向第p个元素的指针值public: lnkList(ints); //构造函数 ~lnkList(); //析构函数 boolisEmpty(); //判断链表是否为空 voidclear(); //将链表存储的内容清除，成为空表 intlength(); //返回此顺序表的当前实际长度 boolappend(cosntTvalue); //在表尾添加一个元素value，表的长度增1 boolinsert(cosntintp,cosntTvalue); //在位置p上插入一个元素value，表的长度增1 booldelete(cosntintp); //删除位置p上的元素，表的长度减1 boolgetValue(cosntintp,T&value); //返回位置p的元素值 boolgetPos(int&p,constTvalue); //查找值为value的元素，返回第1次出现的位置}目前二十一页\总数三十一页\编于八点查找单链表中第i个结点讲解：查找结点数据为指定值的结点。setPos函数：查找第i个结点，并返回该结点的指针。查找的实现：通过结点的指针实现遍历(即扫描)所有的结点，直至找到满足要求的结点为止。目前二十二页\总数三十一页\编于八点23查找单链表中第i个结点//函数返回值是找到的结点指针template<classT> //线性表的元素类型为TLink<T>*lnkList<T>::setPos(inti){

intcount=0;if(i==-1) //i为-1则定位到头结点 returnhead; //循链定位，若i为0则定位到第一个结点

Link<T>*p=newLink<T>(head->next); while(p!=NULL&&count<i){ p=p->next; count++;};returnp;//指向第i结点，i＝0,1,…，当链表中结点数小于i时返回NULL}目前二十三页\总数三十一页\编于八点在单链表中插入结点讲解：在指针p所指向结点的后面插入新结点。insert函数：插入新结点，使之成为第i个结点，返回该结点的指针插入结点的实现：特别需要注意修改相关指针的值。目前二十四页\总数三十一页\编于八点25单链表的插入20231215headtail在23和12之间插入1020231215headtail10创建新结点新结点指向右边的结点左边结点指向新结点目前二十五页\总数三十一页\编于八点26单链表插入算法//插入数据内容为value的新结点作为第i个结点

template<classT> //线性表的元素类型为TboollnkList<T>::insert(constinti,constTvalue){ Link<T>*p,*q;

if((p=setPos(i-1))==NULL){ //p是第i个结点的前驱 cout<<"非法插入点"<<endl; returnfalse; } q=newLink<T>(value,p->next); p->next=q; if(p==tail) //插入点在链尾，插入结点成为新的链尾 tail=q; returntrue;}目前二十六页\总数三十一页\编于八点在单链表中删除结点讲解：删除指针p所指向的结点。deletion函数：删除第i个结点。删除结点的实现：特别需要注意修改相关指针的值。目前二十七页\总数三十一页\编于八点28

用p指向元素x的结点,可以吗?

….

….xhead

p

….x

p

单链表删除示意目前二十八页\总数三十一页\编于八点29

x

pppnext=qne