- 1、本文档共28页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
(课件)数据结构第二章线性表
第二章 线性表;2.1 线性表的类型定义(P18-19)
定义:一个线性表是n个数据元素的有限序列;2.2 线性表的顺序存储结构
顺序表:
定义:用一组地址连续的存储单元存放一个线性表叫~
元素地址计算方法:
LOC(ai)=LOC(a1)+(i-1)*L
LOC(ai+1)=LOC(ai)+L
其中:
L—一个元素占用的存储单元个数
LOC(ai)—线性表第i个元素的地址
LOC(a1)—起始地址,基地址
特点:
实现逻辑上相邻—物理地址相邻
实现随机存取
实现:可用C语言的一维数组实现
;#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
Typedef struct{
ElemType * elem;
int length;
int listsize;
}SqList;
;插入
定义:线性表的插入是指在第i(1?i ? n+1)个元素之前插入一个新的数据元素x,使长度为n的线性表;内存;算法时间复杂度T(n)
设Pi是在第i个元素之前插入一个元素的概率,则在长度为n的线性表中插入一个元素时,所需移动的元素次数的平均次数为:;删除
定义:线性表的删除是指将第i(1?i ? n)个元素删除,使长度为n的线性表;内存;算法评价
设Qi是删除第i个元素的概率,则在长度为n的线性表中删除一个元素所需移动的元素次数的平均次数为:;合并顺序表
已知顺序表La和Lb的顺序按值非递减排列,归并La和Lb得到新的顺序表Lc,Lc的元素也按值非递减排列
基本操作是“复制”,设2个指针i和j,分别指向2个表当前处理的元素,当i不大于j时复制i所指元素到Lc中,否则复制j所指元素到Lc中;顺序存储结构的优缺点
优点
逻辑相邻,物理相邻
可随机存取任一元素
存储空间使用紧凑
缺点
插入、删除操作需要移动大量的元素
预先分配空间需按最大空间分配,利用不充分
表容量难以扩充;2.3 线性表的链式存储结构
特点:
用一组任意的存储单元存储线性表的数据元素
利用指针实现了用不相邻的存储单元存放逻辑上相邻的元素
每个数据元素ai,除存储本身信息外,还需存储其直接后继的信息
结点
数据域:元素本身信息
指针域:指示直接后继的存储位置;ZHAO;实现;头结点:在单链表第一个结点前附设一个结点叫~
头结点指针域为空表示线性表为空;单链表的基本运算
查找:查找单链表中是否??在结点X,若有则返回指向X结点的指针;否则返回NULL
算法描述;算法描述;动态建立单链表算法:设线性表n个元素已存放在数组a中,建立一个单链表,h为头指针;单链表特点
它是一种动态结构,整个存储空间为多个链表共用
不需预先分配空间
指针占用额外存储空间
不能随机存取,查找速度慢;循环链表(circular linked list)
循环链表是表中最后一个结点的指针指向头结点,使链表构成环状
特点:从表中任一结点出发均可找到表中其他结点,提高查找效率
操作与单链表基本一致,循环条件不同
单链表p或p-next=NULL
循环链表p或p-next=h;双向链表(double linked list)
单链表具有单向性的缺点
结点定义;b;Status ListInsert_Dul(DuLinkList L,int i,ElemType e)
{
if (! (p=GetElemP_Dul(L,i))) return ERROR;
if (! (s= (DuLinkList)malloc(sizeof(DuLNode)))) return ERROR
s-data=e;
s-prior=p-prior; p-prior-next=s;
s-next=p;
p-prior=s;
return OK
};2.4 线性表的应用举例
一元多项式的表示及相加
一元多项式的表示:;单链表的结点定义;设p,q分别指向A,B中某一结点,p,q初值是第一结点,结果保存在A中;q
您可能关注的文档
最近下载
- 分公司营销部门薪酬与绩效方案.docx VIP
- 哲学与人生-第8课《在实践中提高认识能力》第二框《明辨是非,追求真理》教案.docx
- 2024-2025人教版小学1一年级数学上册(全册)教案【新教材】.doc
- 宝洁麦克销售模式Ⅱ.pdf
- GB-T 3511-2018硫化橡胶或热塑性橡胶 耐候性(新版本).pdf
- 春节后复产复工“六个一”安全工作台帐.docx
- XXX200MW.400MWh储能电站项目技术规范书-(20230415).docx VIP
- 清华特奖教你怎么用学术不端来走上学术巅峰.pdf
- ISO TR 17671-1-02焊接—金属材料焊接的推荐1:电弧焊一般指导.pdf
- 互联网医院建设方案.pptx
文档评论(0)