首页 26考研 在职考研 直播好课 大纲冲刺

新东方在线 > 考研 > 计算机 > 考研计算机复习指导 > 正文

扫码加入训练营

牢记核心词

学习得礼盒

2020考研计算机《数据结构(C语言版)》复习笔记(2)

2019-05-23 12:17:15来源：网络

　　2020年计算机考研复习已经开始，新东方在线在此整理了2020考研计算机《数据结构(C语言版)》复习笔记(2)，希望能帮助大家!

　　第二章 线性表知识点整理

　　线性表是由n≥0个数据元素组成的有限序列。

　　n=0是空表;非空表，只能有一个开始结点，有且只能有一个终端结点。

　　线性表上定义的基本运算：

　　·构造空表：Initlist(L)

　　·求表长：Listlength(L)

　　·取结点：GetNode(L，i)

　　·查找：LocateNode(L，x)

　　·插入：InsertList(L，x，i)

　　·删除：Delete(L，i)

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

　　逻辑结构中各结点相邻关系是一致的。地址计算：LOCa(i)=LOCa(1)+(i-1)*d;(首地址为1)

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

　　·插入：平均移动结点次数为n/2;平均时间复杂度均为O(n)。

　　·删除：平均移动结点次数为(n-1)/2;平均时间复杂度均为O(n)。

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

　　一个单链表由头指针的名字来命名。

　　单链表运算：

　　·建立单链表·头插法：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)

　　单循环链表是一种首尾相接的单链表，终端结点的指针域指向开始结点或头结点。链表终止条件是以指针等于头指针或尾指针。

　　采用单循环链表在实用中多采用尾指针表示单循环链表。优点是查找头指针和尾指针的时间都是O(1)，不用

　　遍历整个链表。

　　双链表就是双向链表，就是在单链表的每个结点里再增加一个指向其直接前趋的指针域prior，形成两条不同方

　　向的链。由头指针head惟一确定。

　　双链表也可以头尾相链接构成双(向)循环链表。

　　双链表上的插入和删除时间复杂度均为O (1)。

　　顺序表和链表的比较：　　·基于空间：

　　·顺序表的存储空间是静态分配，存储密度为1;适于线性表事先确定其大小时采用。

　　·链表的存储空间是动态分配，存储密度<1;适于线性表长度变化大时采用。

　　·基于时间：

　　·顺序表是随机存储结构，当线性表的操作主要是查找时，宜采用。

　　·以插入和删除操作为主的线性表宜采用链表做存储结构。

　　·若插入和删除主要发生在表的首尾两端，则宜采用尾指针表示的单循环链表。


本文关键字: 2020考研计算机

考研英语核心词汇营

背词+听课+练习+督学，学习得礼盒

更多资料

添加班主任领资料

添加考研班主任
免费领取考研历年真题等复习干货资料

  • 1.打开手机微信【扫一扫】，识别上方二维码；
  • 2.添加班主任，可领取学习资料。
更多>>
更多内容
看课程 MBA 优惠券 0元学 领资料

关注新东方在线考研服务号

获得21考研真题及答案解析

1. 打开手机微信【扫一扫】，识别上方二维码；
2.点击【关注公众号】，获取资料大礼包。

名师试听

历年考研真题及答案解析下载

英语一 英语二 政治 数学一 数学二 数学三 西医综合 教育综合 心理学综合
立即下载
近10年考研真题及答案免费下载
更多>>
更多公开课>>
更多>>
更多资料
我要
反馈 返回
首页
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10