加载中…
个人资料
_陌上花开7_
_陌上花开7_
  • 博客等级:
  • 博客积分:0
  • 博客访问:68,244
  • 关注人气:29
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

线性表

(2013-05-15 18:36:47)
标签:

线性表

顺序表

循环表

双链表

it

分类: 数据结构

线性表简称表,是n(n>=0)个具有相同类型的数据元素的有限序列,线性表中数据元素的个数成为线性表的长度,长度等于零时称为空表。下标一般从1开始,故下标也是其位置或者序号。

线性表的抽象数据类型定义:

ADT List

Data

  线性表中的数据元素具有相同的类型,相邻元素具有前驱和后继的关系

Operation

  InitList

      前置条件:线性表不存在

      输入:无

      功能:线性表的初始化

      输出:无

      后置条件:一个空的线性表

  DestroyList

      前置条件:线性表已存在

      输入:无

      功能:销毁线性表     

      输出:无

      后置条件:释放线性表所占用的存储空间

Length

      前置条件:线性表已存在

      输入:无

      功能:求线性表的长度

      输出:线性表中数据元素的长度

      后置条件:线性表不变

Get

      前置条件:线性表已存在

      输入:元素的序号i

      功能:按位查找,在线性表中查找序号为i的元素

      输出:如果序号合法,返回序号为i的元素值,否则抛出异常

      后置条件:线性表 不变

Locate

      前置条件:线性表已存在

      输入:输入元素x

      功能:按值查找,在线性表中查找值等于x的元素

      输出:如果查找成功,返回元素在表中的序号,否则返回0

      后置条件:线性表不变

Insert

      前置条件:线性表已存在

      输入:插入位置i,待插入元素x

      功能:插入操作,在线性表的第i个位置插入一个新元素x

      输出:若插入不成功,抛出异常

      后置条件:若插入成功,表中增加了一个新元素

Delete

      前置条件:线性表已存在

      输入:删除位置i

      功能:删除操作,删除线性表中第i个元素

      输出:若删除成功,返回被删除的元素,否则抛出异常

      后置条件:若删除成功,表中减少了一个元素

Empty

      前置条件:线性表已存在

      输入:无

      功能:判空操作,判断线性表是否为空表

      输出:若是空表,返回1,否则返回0

      后置条件:线性表不变

PrintList

      前置条件:线性表已存在

      输入:无

      功能:遍历操作,按序号依次输出线性表中的元素

      输出:线性表中的各个数据元素

      后置条件:线性表不变

endADT

线性表的顺序存储结构称为顺序表

单链表是用一组任意的存储单元存放线性表的元素,这组存储单元可以连续也可以不连续,甚至可以零散分布在内存中的任意位置。为了能正确表示元素之间的逻辑关系,每个存储单元在存储数据元素的同时,还必须存储其后继元素所在的地址信息,这个地址信息称为指针。这两部分数据组成了数据元素的存储映像,称为结点,结构是data + next   单链表中每个节点的存储地址存放在其前驱节点的next域中,而第一个元素无前驱,所以设头指针指向第一个元素所在的结点(称为开始结点),由于最后一个元素无后继,故最后一个元素所在的结点(称为终端结点)的指针域为空,即NULL,也称尾标志

在单链表中,如果终端结点的指针域由空指针改向头结点,就使整个单链表形成了一个环,这种头尾相接的单链表称为循环单链表,简称为循环链表

在循环链表中,虽然从任一结点出发可以扫描到其他结点,弹药找到其前驱结点,则需要遍历整个循环链表。如果希望快速确定表中任一结点的前驱结点,可以在单链表的每个节点中再设置一个指向其前驱结点的指针域,这样就形成了双链表,其结构为  prior + data + next

其中data为数据源,存放数据元素;

    prior为前驱指针域,存放该结点的前驱结点的地址;

    next为后继指针域,存放该结点的后继结点的地址;

 

 

 

0

阅读 评论 收藏 转载 喜欢 打印举报/Report
后一篇:栈和队列
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

    后一篇 >栈和队列
      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有