数据结构–线性结构专题

于2020年11月25日由Sukuna发布

1 基础

1.数据,数据元素,数据对象,数据项,数据结构的概念 什么是基本单位,什么是最小单位,什么是所有能输入到计算机中并被计算机程序处理的符号总称?性质相同的元素的集合?

2.结构的分类? 逻辑结构:集合,线性表,树,图 物理结构:顺序存储结构,物理存储结构,索引存储结构,哈希存储结构

3.引用参数:&:可以扩展为指针

4.算法的五个特征 (1)有穷性 (2)可读性 (3)健壮性 (4)可行性 (5)高效性

5.时间复杂度的分析: (1)大致的时间复杂度

为多数 (2)递归或者循环调用时,调用的每个语句都要算进去 (3)计算语句频度的方法?

6.空间复杂度分析: (1)递归:有栈存储,至少

的空间 (2)有递归次数:

2 线性表

1.表长:表长与存储的长度区别,maxlength和size的区别 2.直接前驱后继:首元素没有前驱,尾元素没有后继 3.抽象数据类型:了解(跟class一样)

4.存储特征: 顺序存储结构:可以随机读取元素,插入删除复杂 链式存储结构:不可以随机读取元素,插入删除较为简单

5.自由区:空闲的空间 6.首地址+偏移量选址法 (见数组)

7.动态静态分配的顺序存储结构

静态存取

#define maxleng 100
 typedef struct     
   { ElemType elem[maxleng]；//下标:0,1,...,maxleng-1
     int length；            //表长
    } SqList；
   SqList La；

动态存取:

#define LIST_INIT_SIZE 100
 #define LISTINCREMENT 10
typedef struct     
   { ElemType *elem；//存储空间基地址
     int length；    //表长
     int listsize;   //当前分配的存储容量
                     //（以sizeof(ElemType)为单位
    } SqList；
   SqList Lb；

有增量#define LISTINCREMENT 10

溢出时扩充的方法

if (L.length>=L.listsize)    /*溢出时扩充*/
      { 
     ElemType *newbase;
     newbase=(ElemType *) realloc(L.elem,
        (L.listsize+LISTINCREMENT)*sizeof(ElemType));
      if (newbase==NULL) return OVERFLOW;   //扩充失败
     L.elem=newbase;
     L.listsize+=LISTINCREMENT;
      }

9.链表 1.带头结点和不带头结点 带头结点的作用:需要额外开辟一个空间,但是插入和删除首元素时不用进行特殊处理

10.静态链表:用数组模拟,数组里面有data域和下一个元素的编号,head->0,尾元素指向0

11.循环链表: 尾指针:有头:指向表头 无头:指向第一个元素 head:设置任意一个指 只需要设一个尾指针就可以满足,可以找到链表的任何一个值

12.双向链表

首结点前驱是空,尾结点后继是空 表头结点前驱是尾结点,后继指头结点 会考一些操作

13.双向循环链表:没有哪一个指针域是空

3 栈和队列

3.1 栈

1.先进后出

2.栈顶和栈底的定义

3.栈顶的几个定义法:

和

的上一个单元:空栈时分别对应-1和0

4.进展顺序判断:第二斯特林数,溢出和下溢的判断

5.符号表达式和代替递归函数

6.存储形式 (1)数组,加个top (2)链式存储,用表头插入:搞清楚插入删除的复杂度:

3.2 队列

1.先进先出

2.双向队列:中间值不能动 输入受限:只允许在表的一端插入、在两端删除元素的线性表 输出受限:只许在表的两端插入、在一端删除元素的线性表

3.循环队列: 溢出判断:(Q.rear+1)% MAXLENGQ.front 下溢判断:Q.front==Q.rear 算队列长的方法:(Q.rearQ.front+maxlength)%maxlength 改进:有6个空间,只存5个元素

还要记住几个插入删除的算法怎么写

4 串

1.’\0’C语言 a[0]存指定的串长 Pascal

2.字符堆:指针指向一个地址(第一个字母的地址),还有一个元素存长度

3.链式堆的存储密度 (1)多字符和单字符 (2)计算方式:

,开辟的总空间=字符数+指针域

4.KMP算法,求那个next数组的值

5 数组

1.行存储和列存储: 首元素寻址法:有0行0列和无0行0列

从左到右&从右到左

例子:三维数组a[1..p,1..m,1..n],假定无0页0行0列 1)以行序为主序，

的地址为

(2)以列序为主序，

的地址为

如果有0行0列:所有-1去掉

2.矩阵压缩存储

(1)对称矩阵与三对角

3.稀疏矩阵 (1)三元组表:存行列值和元素值 (2)十字链表

4.广义表:加递归,元素可以是单独的值也可以是新的广义表

结构位置表示:a,b,c,d 都表明好 (1)广义表的图型表示—-树型结构 约定 □—-单元素/原子 ○—-列表,若有表名,附表名：对应（） (2)存储结构

(3)表头:第一个元素:可元素,可表 (4)表尾:剩下的元素都是表尾,一定是广义表