1 基础

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

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

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

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

5.时间复杂度的分析:
(1)大致的时间复杂度O(n^2),O(n),O(nlogn)为多数
(2)递归或者循环调用时,调用的每个语句都要算进去
(3)计算语句频度的方法?

6.空间复杂度分析:
(1)递归:有栈存储,至少O(n)的空间
(2)有递归次数:O(nm)

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.栈顶的几个定义法:a_na_n的上一个单元:空栈时分别对应-1和0

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

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

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

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)计算方式:

    \[\frac{有效字符}{开辟的总空间}\]

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

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

5 数组

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

从左到右&从右到左

例子:三维数组a[1..p,1..m,1..n],假定无0页0行0列
1)以行序为主序,a[k][i][j]的地址为
Loc(k,i,j)=Loc(1,1,1)+(m<em>n</em>(k-1)+n(i-1)+j-1)<em>s =h+(m</em>n<em>(k-1)+n(i-1)+j-1)</em>s 1\lek\lep, 1\lei\lem, 1\lej\len

(2)以列序为主序,a[k][i][j]的地址为
Loc(k,i,j)=Loc(1,1,1)+(p<em>m</em>(j-1)+p<em>(i-1)+k-1)</em>s=h+(p<em>m</em>(j-1)+p<em>(i-1)+k-1)</em>s

1\lek\lep, 1\lei\lem, 1\lej\len

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

2.矩阵压缩存储

(1)对称矩阵与三对角

k= (3*(i-1)-1)+(j-i+2) = 2(i-1)+j

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

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

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

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

最后修改日期:2020年11月25日