数据结构–线性结构专题

于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.动态静态分配的顺序存储结构

静态存取

代码语言：javascript复制

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

动态存取:

代码语言：javascript复制

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

有增量#define LISTINCREMENT 10

溢出时扩充的方法

代码语言：javascript复制

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.双向循环链表:没有哪一个指针域是空