杭州紫金港培训学校(紫金港专升本)杭州紫金港培训学校(紫金港专升本)
同等学力申硕控制科学与工程学科综合考前辅导计算机软件技术第 25 节 / 共 32 节约 35 分钟报名学员看全文

软件(二):数据结构基本概念、线性表、栈和队列、数组

对应计算机软件技术「二、数据结构」前四条:数据结构的基本概念与存储方式,线性表的顺序存储与链表,栈和队列(含循环队列),数组的地址计算与特殊矩阵的压缩存储。

本节考点:数据结构的基本概念线性表与链表栈和队列数组

本节导读

这一节对应「二、数据结构」的前四条:「数据结构的基本概念、主要类型和主要数据存储方式」「线性数据结构和链表」「栈和队列」「数组」。它们都是线性结构:数据元素之间是一对一的前后关系。下一节讲非线性的树和图,以及检索与排序。

学完要做到:分清逻辑结构和存储结构;会算顺序表插入删除要移动的元素个数,会写链表的插入删除;会判断出栈序列是否可能,会算循环队列的元素个数;会算二维数组元素的地址和对称矩阵压缩存储的下标。

数据结构的基本概念

数据结构研究数据元素之间的关系以及在计算机中的存储和运算。

  • 逻辑结构(主要类型):集合、线性结构(一对一)、树形结构(一对多)、图状结构(多对多)。
  • 存储结构(主要存储方式):顺序存储(逻辑上相邻的元素在存储器中也相邻)、链式存储(用指针表示前后关系)、索引存储(另建索引表)、散列存储(按关键字计算地址)。

同一种逻辑结构可以采用不同的存储结构,运算的效率随之不同。

线性表与链表

线性表是 nnn 个数据元素的有限序列。顺序表用一组地址连续的单元依次存放,可以按序号随机存取;在长度为 nnn 的表中第 iii 个位置前插入,要把第 iii 到第 nnn 个元素后移,共 n−i+1n-i+1n−i+1 个;删除第 iii 个元素要前移 n−in-in−i 个。等概率时插入平均移动 n/2n/2n/2 个,删除平均移动 (n−1)/2(n-1)/2(n−1)/2 个。

链表的每个结点包括数据域和指针域,插入删除不移动元素,只改指针,但不能随机存取。单链表中在结点 p 之后插入结点 s:

s->next = p->next;
p->next = s;

两句次序不能颠倒。删除 p 的后继:q = p->next; p->next = q->next; 再释放 q。为了让空表与非空表、第一个元素结点与其他结点的操作一致,常在第一个元素结点之前加一个不存数据的头结点,头指针指向它。另有循环链表(尾结点的指针指回头结点,表中没有空指针)和双向链表(每个结点有前驱、后继两个指针)。

栈和队列

栈只在一端(栈顶)插入删除,后进先出;队列在队尾插入、队头删除,先进先出。栈用于表达式求值、括号匹配、函数调用与递归;队列用于排队服务、缓冲区和按层遍历。

判断出栈序列:按入栈次序模拟,出栈序列中某元素出栈时,比它先入栈、还没出栈的元素必须按逆序出栈。

循环队列用长度为 mmm 的数组首尾相接。约定 front 指向队头元素、rear 指向队尾元素的下一个位置,空出一个单元区分空和满:

量公式
队空front == rear
队满(rear + 1) % m == front
元素个数(rear - front + m) % m

数组

二维数组 A[1..m][1..n]A[1..m][1..n]A[1..m][1..n],每个元素占 LLL 个单元,首元素地址为 LOC(1,1)\mathrm{LOC}(1,1)LOC(1,1):

本节后面还有约 1300 字:报名学员看全文

每门课前 10 节免费看全文;从第 11 节起,完整教程要报名后由顾问在后台为你的账号开通才能看。

题库账号可以直接登录,但第 11 节起的完整教程要报名后由后台开通才能看。

学完练一练

按本节考点从本课的课后练习里抽题(每次 10 道以内),做完看解析、错题自动进错题本。第 11 节起的课后练习报名学员才能练。

本节内容由 AI 辅助编写,配图由 AI 生成,仅供备考参考;考试要求以《全国各类成人高等学校招生考试大纲(2024 年版)》及浙江省教育考试院当年公布为准。

我要提问免费报名咨询