《数据结构》课件1第2章 线性表.pptx
《《数据结构》课件1第2章 线性表.pptx》由会员分享,可在线阅读,更多相关《《数据结构》课件1第2章 线性表.pptx(21页珍藏版)》请在文库网上搜索。
1、第2章 线性表线性表的逻辑结构线性表的顺序表示和实现线性表的链式表示和实现顺序表和链表的比较线性表的应用2.1 线性表的逻辑结构2线性表是由性表是由类型相同型相同的数据元素的数据元素组成的成的有限序列有限序列。线性表的数据元素可以是数字、字符或更复杂的信息。英语字母表:(a,b,c,d,x,y,z)一个人的一年的月收入:(5000,5200,4890,4890,5300)学生成绩表:2.1 线性表的逻辑结构3n 线性表的定义n 二元组表示n 逻辑关系图2.1 线性表的逻辑结构4n 线性表的抽象数据类型定义GetElem(i,&e)初始条件:线性表已存在,1ilength。操作结果:用e返回第i
2、个元素的值。SetElem(i,e)初始条件:线性表已存在,1ilength。操作结果:将线性表的第i个位置的元素赋值为e。Search(e)初始条件:线性表已存在。操作结果:在线性表中查找值为e的元素,若查找成功,返回其所在的位置,否则返回0。Insert(i,e)初始条件:线性表已存在,1iength+1。操作结果:在线性表的第i个元素前插入元素e,线性表长度加1。Delete(i,&e)初始条件:线性表已存在,1ilength。操作结果:删除线性表的第i个元素,并用e返回其值,线性表长度减1。2.2 线性表的顺序表示和实现1.线性表的顺序存储结构顺序表52.2 线性表的顺序表示和实现2.
3、顺序表的实现6template class SqListprivate:int maxsize;/顺序表可能达到的最大长度int length;/顺序表的长度T*elem;/存储空间的基地址public:SqList(int size=DEFAULT_SIZE);/构造函数,DEFAULT_SIZE为符号常量SqList(T a,int n);/构造函数SqList(SqList&sl);/复制构造函数SqList();/析构函数int Length();/求顺序表长度bool Empty();/判断表是否为空void Clear();/清空顺序表void PrintList();/输出表中的
4、各个元素bool GetElem(int i,T&e);/获取指定位置的元素值bool SetElem(int i,T e);/设置指定位置的元素值int Search(T e);/查找元素bool Insert(int i,T e);/插入元素bool Delete(int i,T&e);/删除元素;2.2 线性表的顺序表示和实现2.顺序表的实现7/求顺序表的长度template int SqList:Length()return length;/判断顺序表是否为空template bool SqList:Empty()if(length=0)return true;else return
5、false;/清空顺序表template void SqList:Clear()length=0;/读取元素的值template bool SqList:GetElem(int i,T&e)if(ilength)return false;e=elemi-1;return true;/设置元素的值template bool SqList:SetElem(int i,T e)if(ilength)return false;elemi-1=e;return true;/查找操作template int SqList:Search(T e)int i;for(i=0;ilength;i+)if(e=e
6、lemi)return i+1;return 0;2.2 线性表的顺序表示和实现2.顺序表的实现8template bool SqList:Insert(int i,T e)if(length=maxsize)return false;if(ilength+1)return false;for(int j=length;j=i;j-)elemj=elemj-1;elemi-1=e;length+;return true;算法分析算法分析假设在线性表的任意位置上插入元素的概率相等,即:则:插入算法的时间复杂度为:O(n)2.2 线性表的顺序表示和实现2.顺序表的实现9template bool
7、SqList:Delete(int i,T&e)if(ilength)return false;e=elemi-1;for(int j=i;jdata:该结点的数据元素p-next:指向该结点的后继 data nextp单链表表结构示意构示意图:a1 a2 an head头结点:没有存储任何数据增加头结点:算法实现更简单,效率更高头指针指向单链表的头结点空空链表示意表示意图:head结点定点定义template struct Node T data;/数据域Node*next;/指针域;2.3 线性表的链式表示和实现3.单链表的实现1212/求单链表的长度template int LinkLi
8、st:Length()int len=0;Node*p=head-next;while(p!=NULL)len+;p=p-next;return len;/判断表是否为空template bool LinkList:Empty()return head-next=NULL;/读取元素的值template bool LinkList:GetElem(int i,T&e)if(iLength()return false;Node*p;p=GetPtr(i);e=p-data;return true;/清空单链表template void LinkList:Clear()Node *p=head-n
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 数据结构课件1第2章 线性表 课件 线性