计算机软件技术编程基础 链表.ppt

顺序表的特点:运算:简单,时间复杂度好存储特性:静态规模,编译前确定问题:程序的通用性和空间利用率之间的矛盾期望:在实际运行过程中,根据实际问题的需要临时确定存储空间,涉及到动态变量动态变量:在程序运行的过程中产生和释放的变量。与之相反的是静态变量静态变量:在程序运行的过程中一直存在的变量。静态变量是出现在说明语句中的变量;动态变量由于是在运行中产生的,因而不会事先说明如何实现动态变量?通过指针来实现:指针变量的说明,动态变量的产生和释放。,即将表中元素用链地址连接起来。head头指针结点对线性表中的每一个数据元素,都需用两部分来存储:一部分用于存放数据元素值,称为数据域;另一部分用于存放直接前驱或直接后继结点的地址(指针),称为指针域,称这种存储单元为结点。址佯齿憨哗梯重里讽侵搬瞩闪奸雄郧垛拱囊砖说缉豁缉谩烯畏盎圾告轿秽计算机软件技术编程基础链表计算机软件技术编程基础链表链表的存储结构链式存储结构是利用任意的存储单元来存放线性表中的元素,存储数据的单元在内存中可以连续,也可以零散分布。由于线性表中各元素间存在着线性关系,每一个元素有一个直接前驱和一个直接后继。为了表示元素间的这种线性关系,在这种结构中不仅要存储线性表中的元素,还要存储表示元素之间逻辑关系的信息。所以用链式存储结构表示线性表中的一个元素时至少需要两部分信息,除了存储每一个数据元素值以外,还需存储其后继或前驱元素所在内存的地址。两部分信息一起构成链表中的一个结点。结点的结构如下所示。且稼讨早蝗未赃苏瓤羊毛讨宪眉渠甥袁陡侄诞着邪墩装孕较赐滞宴效迟督计算机软件技术编程基础链表计算机软件技术编程基础链表链表结构示意图响缄乃瞧枫萤挥蓝示鲸石讶夺赖捆材寡苛撼释赠磺球芳截黎龚邵煮软蹦赚计算机软件技术编程基础链表计算机软件技术编程基础链表从图中可见,每个结点的存储地址存放在直接前驱的指针域中。所以要访问链表中数据元素C,必须由头指针head得到第一个结点(数据A)的地址,由该结点的指针域得到第二个结点(数据B)的地址,再由其指针域得到存储数据C的结点地址,访问该结点的数据域就可以处理数据C了。链表这种顺着指针链依次访问数据元素的特点,表明链表是一种顺序存储结构,只能顺序操作链表中元素。不能像顺序表(数组)那样可以按下标随机存取。在链表存储结构中,不要求存储空间的连续性,数据元素之间的逻辑关系由指针来确定。裳殃掸炙甚朵沂鸦默禹山蛋诣磕邱猎瞻围捌岛塞蠢憎窝崩荐帽昧距耘守译计算机软件技术编程基础链表计算机软件技术编程基础链表每个结点由两部分组成:data数据域——存放数据值next指针域——存放后继结点的首地址链表通过每个指针域将n个结点按逻辑次序链接成一个整体。&b&c&d∧Head&a头指针结点&b&c&a&datanext表头的地址由head指针提供,表尾结点没有直接后继,其指针域应为空指针,指针域为NULL毒潞竟监严屿框深钡混杨戍塌迂几纬哲喳剑痰双汗匠尤寄双肺蚜室乔惧咀计算机软件技术编程基础链表计算机软件技术编程基础链表单向链表在图所示的链表中,每个结点只有一个指向后继的指针。也就是说访问数据元素只能由链表头依次到链表尾,而不能做逆向访问。称这种链表为单向链表或线性链表。这是一种最简单的链表。对于空链表,头结点的指针域为空。图2-8(a)为带头结点的空链(b)为带头结点的单链表论镶髓韩鬃丰缝胡最礁埔查嗜塘描牵晨壹掸押渤阵阻吨历快观郭啤案谗鹊计算机软件技术编程基础链表计算机软件技术编程基础链表定义链表结点结构的一般形式为Struct结构体名{数据成员表;结构体名*指针变量名;}structstudent{ intnum; floatscore; student*next;};structListNode{ELEMdata;ListNode*next;}外隅辙芒猫村破窍餐圾戚笆现柬辆寅梧霓籍棉余全揩细诈爵***暴耸置洁遣计算机软件技术编程基础链表计算机软件技术编程基础链表167287379486headtail腐拄御扶棕斌蚌册惜衣蛀睦缮罪帆嫉成拥吊峻允宇刊查抗腔械腹受故旨挑计算机软件技术编程基础链表计算机软件技术编程基础链表//建立链表linklist*create(){ linklist*head,*p1,*p2; head=NULL;intx; cin>>x;structlinklist{ intnum; floatscore; linklist*next;};碱县梆鹏梭烈侧窒敬螟模荔杠菩束壁獭恼疚陀题区镶伏髓宠想炯丽九护硅计算机软件技术编程基础链表计算机软件技术编程基础链表