数据结构-ppt课件-链表部分.ppt
《数据结构-ppt课件-链表部分.ppt》由会员分享,可在线阅读,更多相关《数据结构-ppt课件-链表部分.ppt(59页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、回顾上次课内容回顾上次课内容n数据结构的相关概念n数据的存储结构逻辑结构存储结构集合集合线性结构线性结构树形结构树形结构图状结构或网图状结构或网状结构状结构顺序存储结构顺序存储结构链接存储结构链接存储结构n算法分析方法第二章第二章 线性表线性表主要内容:l 线性表的类型定义线性表的类型定义l 线性表的顺序表示和实现线性表的顺序表示和实现l 线性表的链式表示和实现线性表的链式表示和实现l 线性表的应用举例线性表的应用举例 线性结构的特点线性结构的特点线性结构的特点线性结构的特点存在惟一的一个开始结点,称做存在惟一的一个开始结点,称做“第一个第一个”的数据元素的数据元素存在惟一的一个终端结点,称做
2、存在惟一的一个终端结点,称做“最后一个最后一个”的数据元素的数据元素除第一个外,每个数据元素只有一个前驱除第一个外,每个数据元素只有一个前驱除最后一个外,每个数据元素只有一个后继除最后一个外,每个数据元素只有一个后继1.1.描述描述描述描述:线性表是由线性表是由n(n=0)个数据元素个数据元素(结点结点)a1,a2,.,ai,.,an组成的有限序列。其中,数据元素组成的有限序列。其中,数据元素的个数的个数n定义为表长。当定义为表长。当n=0时称为空表,非空的线性表时称为空表,非空的线性表(n0)记为:记为:(a1,a2,.,ai,.,an)一、逻辑结构一、逻辑结构一、逻辑结构一、逻辑结构注意注
3、意注意注意:1.数据元素数据元素ai是一个抽象的符号是一个抽象的符号2.ai可取各种数据类型可取各种数据类型3.同一线性表中的元素必定具有相同的特性,属于同一数同一线性表中的元素必定具有相同的特性,属于同一数据对象据对象4.相邻数据元素之间存在序偶关系相邻数据元素之间存在序偶关系5.i是数据元素是数据元素ai在线性表中的位序在线性表中的位序(1i n)2.2.2.2.逻辑特征逻辑特征逻辑特征逻辑特征:仅有一个开始结点和一个终端结点,并且所有结:仅有一个开始结点和一个终端结点,并且所有结点都最多只有一个前驱和一个后继点都最多只有一个前驱和一个后继线性表是一个线性结构线性表是一个线性结构线性表是一
4、个线性结构线性表是一个线性结构2.1 线性表的类型定义线性表的类型定义二、抽象数据类型线性表的定义二、抽象数据类型线性表的定义ADTList数据对象:数据对象:D=aiaiElemset,i=1,2,n,n0数据关系:数据关系:R1=ai-1,aiD,i=2,n基本操作:基本操作:构造、销毁、置空、判空、获取元素、插入、删除、构造、销毁、置空、判空、获取元素、插入、删除、定位等。定位等。ADTListna1是第一个元素,有且仅有一个直接后继元素是第一个元素,有且仅有一个直接后继元素a2;nan是最后一个元素,有且仅有一个直接前趋元素是最后一个元素,有且仅有一个直接前趋元素an-1;n其余其余a
5、i(1in)有且仅有一个直接前趋有且仅有一个直接前趋ai-1,有且仅有一,有且仅有一个直接后继个直接后继ai+11顺序表示(存储)顺序表示(存储):指在内存中用地址连续的一块存储空间顺序存放线性表的各元素,用这种存储形式存储的线性表称其为顺序顺序表表。线性表顺序存储结构示意图线性表顺序存储结构示意图2.2 线性表的顺序表示和实现线性表的顺序表示和实现n数据元素存储位置表示数据元素存储位置表示设设 a的存储地址为的存储地址为Loc(a),每个数据元素占每个数据元素占l l个存储地址,则第个存储地址,则第i个数据元素的地址为:个数据元素的地址为:Loc(ai)=Loc(a)+(i-1)*l l,1
6、inn逻辑上相邻的逻辑上相邻的ai和和ai+1以相邻的存储位置。以相邻的存储位置。n确定起始位置后,顺序表中任一数据元素都可确定起始位置后,顺序表中任一数据元素都可随机存取。随机存取。n顺序表是一种随机存取的存储结构。顺序表是一种随机存取的存储结构。n 高级语言中一般用数组来描述顺序存储。高级语言中一般用数组来描述顺序存储。#include#define MAXSIZE 100typedef int ElemType;typedef structElemType aMAXSIZE;int length;Sqlist;因为线性表长度可变,且所需最大空间随问题不同因为线性表长度可变,且所需最大空间
7、随问题不同而不同,所以用动态分配的一维数组而不同,所以用动态分配的一维数组(P22)。为使得。为使得算法简明扼要,暂使用静态数组。算法简明扼要,暂使用静态数组。线性表的建立、输出算法线性表的建立、输出算法初始化初始化void initlist(Sqlist*L)L-length=0;建立顺序表建立顺序表void creat_sqlist(Sqlist&L)int i,n;coutn;L.length=n;for(i=0;iL.ai;void initlist(Sqlist&L)L.length=0;Sqlist Sl;initlist(&Sl);Sqlist Sl;initlist(Sl);输
8、出顺序表输出顺序表void outputl(Sqlist L)int i;coutList length L.lengthendl;for(i=0;iL.length;i+)coutL.ai ;if(i+1)%10=0)coutendl;coutendl;(a1,ai-1,ai,an)改变为(a1,ai-1,e,ai,an)a1a2ai-1aiana1a2ai-1aiean表的长度加11.插入:在线性表第插入:在线性表第i(1i n+1)个位置上插入元)个位置上插入元素素e线性表主要操作的实现线性表主要操作的实现注意:注意:C语言中的数组下标从语言中的数组下标从“0”开始,因此,若开始,因此,
9、若L是是Sqlist类型的顺序表,则表中第类型的顺序表,则表中第i个元素是个元素是L.ai-1。void insert_sq(Sqlist&L,int i,ElemType e)int j;if(L.length=MAXSIZE)coutERROR!endl;elseif(iL.length+1)coutERROR!i-1;j-)L.aj=L.aj-1;L.ai-1=e;L.length+;这里的问题规模是表的长度,设它的值为这里的问题规模是表的长度,设它的值为n。该算。该算法的时间主要花费在循环的元素后移语句上,所需移法的时间主要花费在循环的元素后移语句上,所需移动元素的次数不仅依赖于表的长
10、度,而且还与插入位动元素的次数不仅依赖于表的长度,而且还与插入位置有关。置有关。i位置位置 移动次数移动次数 1n 2 n-1 i n-i+1 n 1 n+10插入操作时间复杂度分析插入操作时间复杂度分析n最好情况下:T(n)=O(1)n最坏情况下:T(n)=O(n)n平均时间复杂度:长度为n的顺序表中,插入一个结点,令E(n)表示移动结点的期望值(移动平均次数),在表中第i个位置插入一个结点移动的次数为n-i+1.其中pi表示在表中第i位置插入结点的概率。Pi1/(n+1)计算得 E(n)=n/2,所以平均时间复杂度为O(n)(a1,ai-1,ai,ai+1,an)改变为(a1,ai-1,a
11、i+1,an)(1 i n)ai+1 an表的长度减1a1a2ai-1aiai+1ana1a2ai-12.2.删除:在线性表中删除第删除:在线性表中删除第i i个元素,使个元素,使ElemType delete_sq(Sqlist&L,int i)int x,j;if(L.length=0)coutERROR!endl;return(-1);else if(iL.length)coutERROR!“endl;return(-1);else x=L.ai-1;for(j=i;j0),否则返回,否则返回-1,表示未找到。,表示未找到。int locate_sq(Sqlist L,ElemType
12、e)int i;i=0;while(i=L.length-1&L.ai!=e)i+;if(i=L.length-1)return(i+1);return(-1);4.合并:两表分别非递减有序合并:两表分别非递减有序(递增或等值递增或等值),合并,合并后仍然非递减有序。后仍然非递减有序。void merge_list(Sqlist a,Sqlist b,Sqlist&c)int i,j,k;i=j=k=0;c.length=a.length+b.length;while(i=a.length-1&j=b.length-1)if(a.ai=b.aj)c.ak=a.ai;i+;k+;else c.a
13、k=b.aj;j+;k+;while(i=a.length-1)c.ak=a.ai;i+;k+;while(jdata 表示数据域表示数据域p-next 表示指针域表示指针域线性表的单链表线性表的单链表线性表的单链表线性表的单链表函数函数mallocfree(p);访问结点访问结点指针赋值的操作指针赋值的操作指针赋值的操作指针赋值的操作P=(LNode*)malloc(sizeof(LNode);产生一个产生一个Lnode类型结点,把首地址送给类型结点,把首地址送给P变量变量系统回收系统回收P所指向的结点(若干字节),所指向的结点(若干字节),P中无中无所指向所指向Lnode*p,s;p-da
14、ta=20;p-next=null;(s.data=20;s.next=null;用的少用的少)指针指向结点指针指向结点p=qq p指针指向后继指针指向后继p=q-next指针移动指针移动p=p-nextqppp指针赋值的操作指针赋值的操作指针赋值的操作指针赋值的操作pqp-next=qp-next=q-nextpq1.创建链表创建链表单链表的基本运算单链表的基本运算void creat_list()ElemType x;LNode*ptr,*p;p=head;coutx;while(x!=999)ptr=new LNode;ptr-data=x;ptr-next=NULL;p-next=pt
15、r;p=ptr;coutx;调用语句:head=new LNode;head-next=NULL;creat_list();定义定义head为全局变量为全局变量void create(LNode*L)int i,n;LNode*s,*p;p=L;coutn;for(i=1;i=n;i+)s=new LNode;couts-data;p-next=s;p=s;p-next=NULL;调用语句:head=new LNode;head-next=NULL;create(head);定义定义head为局部变量为局部变量LNode*Creat_L(int n)int i;LNode*L,*p;L=new
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 ppt 课件 部分
限制150内