2023计算机考研:数据结构中线性表的核心考点(上)

今天小编为大家整理了数据结构中线性表的核心考点介绍,帮助大家梳理考试内容,提高备考效率,更好地掌握相关知识,以下是详细介绍。

核心1:线性表的顺序定义

顺序表是指用一组连续的存储单元,依次存储线性表中的各个元素,从而使得逻辑上相邻的元素在物理位置上也相邻,因此可以随机存取(根据首元素地址和元素序号)表中任一元素。其结构体定义是:

1  #define  MAX_SIZE  100                //数组最大长度
2  typedef  int  ElemType ;                 //数据类型的别名
3  typedef  struct  sqlist {                   //定义线性表结构体
4     ElemType  data[MAX_SIZE] ;   //线性表存储元素的数组
5     int  length ;                          //记录线性表的长度
6   } SqList ;                               //线性表的名称

核心2:顺序表的插入操作

对于插入算法,若表长为n,则在第i位置插入元素,则从an到ai都要向后移动一个位置,共需移动n-i+1个元素,平均时间复杂度为O(n)。其核心代码是:
计算机考研考点

核心3:顺序表的删除操作

对于删除算法,若表长为n,当删除第i个元素时,从ai+1到an都要向前移动一个位置,则共需移动n-i个元素,平均时间复杂度为O(n)。其核心代码是:
计算机考研考点

核心4:顺序表的查找

(1)按序号查找,顺序表具有随机存取的特点,时间复杂度为O(1)。

(2)按值x查找,主要运算是比较操作,比较的次数与值x在表中的位置有关,也与表长有关,平均比较次数为(n+1)/2,时间复杂度为O(n)。

核心5:单链表的定义

单链表是指通过一组任意的存储单元来存储线性表中的元素。为了建立元素之间的线性关系,对每个链表结点,除了存放元素自身的信息,还需要存放一个指向其后继的指针。其定义格式是:
计算机考研考点

核心6:单链表的查找

单链表的存储单元是不连续的,因此无论是查找第i个结点,还是查找给定值x的结点,都只能从表中第一个结点出发,顺指针next域逐个往下搜索,直到找到满足条件的结点为止。时间复杂度为O(n)。

核心7:头插法建立单链表

从一个空表开始,然后将新结点插入当前链表的表头,即头结点之后,采用头插法建立单链表的算法虽然简单,但读入数据的顺序与生成的链表中元素的顺序是相反的。每个结点插入的时间为O(1),设单链表长为n,总的时间复杂度为O(n)。

详细的实现过程,大家可以参考考点讲解。

核心8:尾插法建立单链表

若希望读入数据的顺序与生成的链表中元素的顺序一致,可采用尾插法。即将新结点插入到当前链表的表尾上,为此必须增加一个尾指针r,使其始终指向当前链表的尾结点。

详细的实现过程,大家可以参考考点讲解。

【23考研黄金期辅导课程推荐】23暑期集训营线上+线下VIP领学计划龙腾一对一专属VIP公共课+专业课全科辅导,这些课程中都会配有内部讲义以及辅导书和资料,同时会有教研教辅双师模式对大家进行教学以及督学,并配有24小时答疑和模拟测试等,具体详情可直接咨询在线客服老师。


免责声明:本平台部分帖子来源于网络整理,不对事件的真实性负责,具体考研相关内容请以各院校的官网通知为准。 如果本站文章侵犯到您的权利,请联系我们(400-108-7500)进行删帖处理。

启航教育热门私房课

MORE
  • 2023考研VIP领学计划

    时间:随报随学
    形式:网课+面授
     

    查看详情

    在线咨询

  • 2023考研全年集训营

    时间:3.1-12.16
    形式:面授
     

    查看详情

    在线咨询

  • 2023考研二战集训营

    3.1-12.16
    形式:面授
     

    查看详情

    在线咨询

姓名

手机号

报考专业

请选择  
  • 计算机
  • 经济学
  • 金融硕士
  • 法律硕士
  • 应用统计
  • 机械工程
  • 管理学
  • 通信工程
  • 教育学
  • 心理学
  • 国际商务
  • 土木工程
  • 其他专业
一键申请
扫描上方二维码免费领取学习资料