Geekerstar

《数据结构(C语言版)》学习笔记总结(二)线性表
线性表概念总结什么是线性表“线性表(Linear List)” :由同类型数据元素构成有序序列的线性结构。表中元素...
扫描右侧二维码阅读全文
17
2018/03

《数据结构(C语言版)》学习笔记总结(二)线性表

线性表概念总结

什么是线性表

“线性表(Linear List)” :由同类型数据元素构成有序序列的线性结构。

  • 表中元素个数称为线性表的长度
  • 线性表没有元素时,称为空表
  • 表起始位置称表头,表结束位置称表尾

定义:n(>0)个数据元素的有限序列,记作(a1,…ai-1,ai,ai+1,…,an),其中,ai是表中数据元素,n是表长度。
特点:

  • 同一线性表中元素具有相同特性
  • 相邻数据元素之间存在序偶关系
  • 除第一个元素外,其他每一个元素有一个且仅有一个直接前驱
  • 除最后一个元素外,其他每一个元素有一个且仅有一个直接后驱

线性表是由n≥0数据元素组成的有限序列
n=0空表非空表只能有一个开始结点,有且只能有一个终端结点。

什么是顺序表

顺序表是按线性表的逻辑结构次序依次存放在一组地址连续的存储单元中。在存储单元中的各元素的物理位置和逻辑结构中各结点相邻关系是一致的。

  • 定义:将线性表中的元素相继存放在一个连续的存储空间中。
  • 存储结构:数组。
  • 特点:线性表的顺序存储方式。
  • 存取方式:顺序存取

顺序存储结构示意图:

顺序存储

顺序表的存储方式

顺序表的存储方式

顺序表(SeqList)的类型定义

#define  LISTSIZE 100      //最大允许长度
typedef  int  ListData;

typedef struct{
    ListData *data;
    int length;
}SeqList;

在顺序表中实现的基本运算:

  • 插入:平均移动结点次数为n/2;平均时间复杂度均为O(n)
  • 删除:平均移动结点次数为(n-1)/2;平均时间复杂度均为O(n)

单链表(Singly Linked List)

定义:用一组地址任意的存储单元存放线性表中的数据元素。

单链表

单链表的结构

每个元素由结点(Node)构成,它包括两个域:数据域Data和指针域Link

单链表的结构

  • 存储结构:链式存储结构
  • 特点:存储单元可以不连续。
  • 存取方式:顺序存取。

线性表的链式存储结构中结点的逻辑次序和物理次序不一定相同,为了能正确表示结点间的逻辑关系,在存储每个结点值的同时,还存储了其后继结点的地址信息(即指针或链)。这两部分信息组成链表中的结点结构。一个单链表由头指针的名字来命名。

单链表运算:

  • 建立单链表·

    • 头插法:s->next=head;head=s;生成的顺序与输入顺序相反。平均时间复杂度均为O(n)。
    • 尾插法:head=rear=null;if(head=null) head=s;else r->next=s;r=s; 平均时间复杂度均为O(n)
  • 加头结点的算法:对开始结点的操作无需特殊处理,统一了空表和非空表。
  • 查找·按序号:与查找位置有关,平均时间复杂度均为O(n)。
  • 按值:与输入实例有关,平均时间复杂度均为O(n)。
  • 插入运算:p=GetNode(L,i-1);s->next=p->next;p->next=s;平均时间复杂度均为O(n)
  • 删除运算:p=GetNode(L,i-1);r=p->next;p->next=r->next;free(r);平均时间复杂度均为O(n)

循环链表

  • 特点:最后一个结点的Link指针不为NULL,而是指向头结点。只要已知表中某一结点的地址,就可以搜寻所有结点的地址。
  • 存储结构:链式存储结构

循环链表

单循环链表是一种首尾相接的单链表,终端结点的指针域指向开始结点或头结点。链表终止条件是以指针等于头指针或尾指针。
采用单循环链表在实用中多采用尾指针表示单循环链表。优点是查找头指针和尾指针的时间都是O(1),不用遍历整个链表。

双向链表(Doubly Linked List)

双链表就是双向链表,就是在单链表的每个结点里再增加一个指向其直接前趋的指针域prior,形成两条不同方向的链。由头指针head惟一确定。

双向链表

双链表也可以头尾相链接构成双(向)循环链表。
双链表上的插入和删除时间复杂度均为O (1)。

顺序表和链表的比较:

  • 基于空间:

    • 顺序表的存储空间是静态分配,存储密度为1;适于线性表事先确定其大小时采用。
    • 链表的存储空间是动态分配,存储密度<1;适于线性表长度变化大时采用。
  • 基于时间:

    • 顺序表是随机存储结构,当线性表的操作主要是查找时,宜采用。
    • 以插入和删除操作为主的线性表宜采用链表做存储结构。
    • 若插入和删除主要发生在表的首尾两端,则宜采用尾指针表示的单循环链表。

说明

由于数据结构这门课程的特殊性,书中涉及了大量代码需要去敲,很难做到每周更新一个章节,因此我做了如下决定:
1.本博客不再完全以章节的形式更新数据结构,取而代之的是:

  • 《数据结构(C语言版)》学习笔记总结(X)XXX的形式更新基础概念。
  • 《数据结构题集(C语言版)》习题解析(X)XXX的形式更新课后基础知识题。
  • 以《数据结构·编程题解》章节-内容的形式更新课本及配套题集的编程题答案。

2.预计两个月内更新完毕,并将所有内容整理至极客文库,以供查阅。在更新完毕之前会一直修改完善,最终以极客文库版本为最终版。


如果您发现了文章有任何错误欢迎指正,有任何意见或建议,或者有疑问需要我提供帮助,也欢迎在下面留言,只需输入昵称+邮箱即可,网站或博客可选填。对于所有留言内容我会及时回复,非常期待与大家的交流![/scode]

版权声明:本文(除特殊标注外)为原创文章,版权归 Geekerstar 所有。

本文链接:http://www.geekerstar.com/technology/554.html

除了有特殊标注文章外欢迎转载,但请务必标明出处,格式如上,谢谢合作。

本作品采用 知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议 进行许可。

最后修改:2018 年 03 月 17 日 02 : 21 PM
如果觉得我的文章对你有用,请随意赞赏

发表评论

1 条评论

  1. Geekerstar

    数据结构是我目前为止写的最痛苦的文章……
    目前还有很多错误或者不合理的地方,此文仅供参考,最终会完善并整理到`极客文库`