【嵌入式软件-数据结构与算法】01-数据结构

摘录于老师的教学课程~~(*๓´╰╯`๓)~~内含链表、队列、栈、循环队列等详细介绍~~

基础知识系列 有空再继续更~~~

目录

【链表】

一、单链表

1、存储结构：带头结点的单链表

2、单链表结点类型的定义

3、创建单链表

        1）头插法

        2）尾插法

4、单链表插入结点

5、单链表删除结点​编辑

6、单链表的遍历模型

        1）模型1：指向头结点

        2）模型2：指向首结点

二、双链表

1、存储结构：带头结点的双链表

2、双链表结点类型的定义

3、创建双链表

        1）头插法

        2）尾插法

4、双链表插入结点

        方法1：在第 i 位置插入，先定位到第 i-1 位置​编辑

        方法2：在第 i 位置插入，定位到第 i 位置

5、双链表删除结点

        方法1：删除第 i 位置结点，先定位到第 i-1 位置

        方法2：删除第 i 位置结点，定位到第 i 位置​编辑

三、循环链表

1、循环单链表

2、循环双链表

3、其他操作方法与单链表和双链表操作一样

【栈】

一、顺序栈

1、存储结构

2、顺序栈类型的定义

3、顺序栈的 四 要素

4、顺序栈的运算（节选）

二、共享栈

1、存储结构

2、共享栈类型的定义

3、共享栈的 四 要素

三、链栈

1、存储结构：带头结点的链栈

2、链栈结点类型的定义

3、链栈的 四 要素

4、链栈的运算（节选）

        1）进栈 Push(&s, e)

        2）出栈 Pop(&s, &e)

        3）取栈顶元素 GetTop(s, &e)

【队列】

一、顺序队

1、存储结构

2、顺序队类型的定义

3、顺序队的 四 要素

4、顺序队的运算（节选）

二、链队

1、存储结构

2、链队结点类型的定义

3、链队的 四 要素

4、链队的运算（节选）

        1）进队 enQueue(q , e)

        2）出队 deQueue(q , e)

三、变形链队

1、变化要点

2、存储结构

3、变形链队的 四 要素

四、双端队列

1、不受限的双端队列：两端都可以进行进队和出队操作的队列

2、输出受限的双端队列：一端允许进队和出队，另一端只允许进队

3、输入受限的双端队列：一端允许进队和出队，另一端只允许出队

五、环形队列（循环队列）

1、环形队列（循环队列） 四 要素 

六、变形环形队列

1、变化要点

2、变形环形队列类型的定义

3、变形环形队列的 四 要素

---

【链表】

一、单链表

1、存储结构：带头结点的单链表

2、单链表结点类型的定义

typedef struct LNode    // 定义单链表节点类型
{ElemType data;      // 节点的数据部分，类型为 ElemType（通常是自定义的数据类型）struct LNode *next; // 指向后继结点
}LinkNode;              // 将结构体命名为 LinkNode

  如图：  

3、创建单链表

        1）头插法

        

        代码理解：先接s后面，再接s前面

        2）尾插法

        代码理解：先接s前面，再收s后面

4、单链表插入结点

        代码理解：先cv后面(先接s后面)，再接s前面

5、单链表删除结点

        代码理解：直指后一位，跳过中间

6、单链表的遍历模型

        1）模型1：指向头结点

       

           循环初始条件：p 指向链表的头节点 L 。（意味着循环将从头节点开始）

           循环结束条件：循环在当前节点的下一个节点不为空时继续执行。（意味着循环会只遍历到倒数第二个节点，并且不会打印最后一个节点的数据）

        2）模型2：指向首结点

        

           循环初始条件：p 指向链表的第一个有效节点（即 L ->next ，意味着循环将从第一个有效节点开始，跳过了头节点）。

           循环结束条件：循环在 p 不为空时继续执行。（意味着循环会遍历整个链表，包括最后一个节点）

二、双链表

1、存储结构：带头结点的双链表

  

2、双链表结点类型的定义

typedef struct DNode        //双链表结点类型
{ElemType data;struct DNode *prior;    //指向前驱结点struct DNode *next;     //指向后继结点
}DlinkNode;

3、创建双链表

        1）头插法

     

        代码理解：先接s后面，判断是否后能回扣s，再接s前面，前回扣s

        2）尾插法

      

        代码理解：先接s前面，后s回扣前面，最后r（即旧的s，新的r）指空

4、双链表插入结点

        方法1：在第 i 位置插入，先定位到第 i-1 位置

        代码理解：先s接，后回扣；先接后，再接前

        方法2：在第 i 位置插入，定位到第 i 位置

    

    

5、双链表删除结点

        方法1：删除第 i 位置结点，先定位到第 i-1 位置

        代码理解：跳过结点，往下直指下一位，下一位回扣上一位

        方法2：删除第 i 位置结点，定位到第 i 位置

三、循环链表

1、循环单链表

     

2、循环双链表

3、其他操作方法与单链表和双链表操作一样

---

【栈】

一、顺序栈

1、存储结构

        

2、顺序栈类型的定义

typedef struct
{ElemType data[MaxSize]; //大小为 MaxSize,用于存储栈中的元素int top;                //栈顶指针
}SqStack;

3、顺序栈的 四 要素

   

        代码理解：由于栈从0开始记，所以栈空为-1，栈满为最大（MaxSize）减一；

                          进栈，先加后进；退栈，先取后减；

4、顺序栈的运算（节选）

        要记得判断是否栈满与栈空

二、共享栈

1、存储结构

  

        两头往中间增，空间共享

2、共享栈类型的定义

typedef struct
{ElemType data[MaxSize]; //存放共享栈中元素int top1,top2;          //两个栈的栈顶指针
}DStack;

3、共享栈的 四 要素

  

        代码理解：

        栈空为两指针至两栈外（-1，MaxSize）；

        栈满为两指针相邻；

        进栈，top1进则先加再进（top1为左），top2进则先减再进（top2为右），都为向中靠拢

        出栈，top1出则先取再减（top1为左），top2出则先取再加（top2为右），都为向两边取

三、链栈

1、存储结构：带头结点的链栈

  

2、链栈结点类型的定义

typedef struct linknode
{ElemType data;         //数据域struct linknode *next; //指针域
}LinkStNode;

3、链栈的 四 要素

  

        链栈栈满取决于电脑的内存设置，所以不考虑；

        栈空即为头结点s下一位为空；

        

4、链栈的运算（节选）

        1）进栈 Push(&s, e)：  要点：链表的头插法插入结点

        

        代码理解：头插-先接后再接前

        2）出栈 Pop(&s, &e)：  要点：删除链表的首结点

        

        代码理解：跳过删除结点连上，释放节点

        3）取栈顶元素 GetTop(s, &e)：

        

        代码理解：取栈顶赋值于e

---

【队列】

一、顺序队

1、存储结构

  

2、顺序队类型的定义

typedef struct
{ElemtType data[MaxSize];int front,rear;            //队首和队尾指针
}SqQueue;

3、顺序队的 四 要素

        rear指向队尾元素；front指向队头元素的前一个位置。

  

        代码理解：队空为重合，队满尾最高；进队尾加后入，出队前加后出；

4、顺序队的运算（节选）

1)进队列 enQueue(q，e):在队列不满的条件下，将队尾指针 rear 增 1,然后将元素添加到该位置。

2)出队列 deQueue(q，e):在队列不为空的条件下，将队首指针 front 循环增 1，并将该位置的元素值赋给 e。

          

二、链队

1、存储结构

   

        一个链队的组成，包含两种类型的结点:

           （1）存储队列数据元素的链表结点
           （2）存储队头和队尾指针的链队头结点

2、链队结点类型的定义

        链队的数据节点类型DataNode 

typedef qnode
{ElemType data;      //数据元素struct qnode *next;
}DataNode;

      链队的头结点类型LinkQuNode

typedef struct
{DataNode *front;  //指向单链表队头结点DataNode *rear;   //指向单链表队尾结点
}LinkQuNode;

3、链队的 四 要素

    代码理解：队空为前后指向空；链队队满取决于内存大小，不考虑；进队尾插法，出队从头删；

4、链队的运算（节选）

        1）进队 enQueue(q , e)

        代码理解：先判队是否为空，是则既头又尾，否则尾插进入，接前再接尾；

        2）出队 deQueue(q , e)

        

        代码理解：删前先判断，为空则回错（return false），t指首结点；为独则设空，前后都指空；为多则好删，跳格接前再存值，最后再释放；

三、变形链队

1、变化要点

        使用循环双链表，保留队尾指针rear。（队头指针可通过rear->next得出）

2、存储结构

                

        尾指针rear会回指到队头

3、变形链队的 四 要素

                  

        代码理解：队满看内存，不考虑；队空则尾指为空；进队则尾插法；出队则删头；

四、双端队列

1、不受限的双端队列：两端都可以进行进队和出队操作的队列

       

        两端都可进出

2、输出受限的双端队列：一端允许进队和出队，另一端只允许进队

         

        出口唯一，两端可进；后进为两边，先进在中间；

3、输入受限的双端队列：一端允许进队和出队，另一端只允许出队

        

        进口唯一，两端可进；出队结果看两边；

五、环形队列（循环队列）

1、环形队列（循环队列） 四 要素      

        代码理解：队空为重叠；队满则相邻（尾指针的下一个位置等于头指针的位置，牺牲一个元素）；进队从尾进，出队从头出；

        涉及环形更新指针解析：

六、变形环形队列

1、变化要点：

        取消尾指针，利用队列中元素个数代替队尾指针

2、变形环形队列类型的定义

typedef struct
{ElemType data[MaxSize];int front;              //队头指针int count;              //队列中元素个数
}QuType;

3、变形环形队列的 四 要素

        

        代码解析：可参照环形队列；多了一个count来作为计数（记空与满），方便很多；

---