数据结构学习

一、什么是数据结构
1、数据结构的起源
1968年,美国高德纳教授,《计算机程序技术艺术》第一卷《基本算法》提出,开创了数据结构和算法的先河。
数据结构是一门研究数据之间关系、操作的学科,而非计算数据方法
数据结构+算法=程序 揭露了程序的本质,沃思凭借这个观点获得图灵奖

2、数据结构中的基本概念
数据:任何能够输入到计算机中,能被程序处理的描述客观事物的符号。
数据项:有独立含义的最小单位,也叫做 数据域、域
数据元素:组成数据的、有一定意义的基本单位也叫做节点、结点、顶点
    一个数据元素是由若干个数据项组成
数据结构:相互之间存在一种或多种特定关系的数据元素的集合
算法:数据结构中所具备的功能,能够解决某种问题的方法。

3、研究数据结构的三个方面
    数据的逻辑结构
        一对一 一对多 多对多
    数据的存储结构(物理结构)
        顺序存储、链式存储
    数据结构的运算

4、数据的逻辑结构
    集合结构:数据元素同一个集合中,但是元素之间没有任何关系
    线型结构(表):数据元素之间存在一对一的关系
    树型结构(树):数据元素之间存在一对多的关系
    图型结构(图):数据元素之间存在多对多的关系

5、数据的存储结构/物理结构
    顺序结构:
        数据元素是存储在连续的内存中,使用操作数据时要确保数据的连续性不被破坏,用数据元素的相对位置来表示数据元素之间的关系。
        内存空间是连续的,并且数据元素之间也要连续。
    优点:支持随机访问,访问效率极高,适合查找数据,不容易产生内存碎片。
    缺点:对数据元素的插入、删除操作效率低,实现不方便。对内存的要求较高。(这里主要体现在插入删除一个数据时,
    为保持数据的连续性,需要进行大量数据的复制操作。并且需要固定大小,因为需要事先分配足够大的内存,所有,会造成内存的浪费)

    链式结构:
        数据元素存储在彼此独立的内存空间中(存储在不确定的内存位置),每个独立的元素称为节点,每个节点中额外增加一块指针域。
        通过该指针可以指向下一个与该节点有关系的节点,以此表示数据节点之间的关系 
    优点:对节点的删除、插入效率高,实现简单,适合增删改查,而且内存要求低 
    缺点: 不支持随机访问,访问效率低,只能从前往后逐一访问,容易产生内存碎片,不适合频繁查找数据

常见面试题:数组和链表的优缺点(就是顺序结构和链式结构的优缺点)

6、逻辑结构和存储结构(物理结构)
表:顺序或者链式
树:链式或者顺序(前后是优先级)
图:链式+顺序
每种逻辑结构采用哪种存储结构,并没有明确的规定,通常根据实现的难度、空间的要求、时间的要求综合选取合适的存储结构

7、数据结构的运算
    1、建立数据结构     create\creat
    2、销毁数据结构     destroy
    3、清空数据结构     clear 
    4、插入元素        insert\add
    5、删除元素        delete
    6、修改元素        modify 
    7、访问元素        access
    8、查询元素        query
    9、遍历数据结构     show\list\ergodic
    10、排序数据结构    sort 

二、顺序表的实现
数据项:
存储元素的内存首地址
表的容量
元素的数量
运算:
创建、销毁、清空、插入、删除、修改、访问、查询、遍历、排序
注意:
1、需要确保数据元素的连续性
2、不能越界

三、链式表(链表)(list)重要程度第一
数据元素(节点)的数据项:
数据域:可以是各种类型的若干项数据项
指针域:指向下一个节点的指针
由若干个节点通过指针域连接起来的叫做链表
指针域:指向下一个节点的指针
一、链式表(链表) No.1 list
数据元素(节点)的数据项:
数据域:可以是各种类型的若干项数据项
指针域:指向下一个节点的指针

由若干个节点通过指针域连接起来就形成了链表

不带头节点的链表:
    定义:第一个节点的数据域存储的是有效数据
    缺点:当插入、删除时可能会改变第一个有效节点,传递的参数需要传递二级指针,实现时需要区分是否是操作第一个有效节点,较为麻烦

带头节点的链表:
    定义:第一个节点作为头节点,数据域不使用不存储有效数据,它的指针域永远指向链表的第一个有效数据节点,就算链表长度为0,头节点依然存在
    优点:当插入、删除时是不会改变头节点的指向,只需要改变它的next,因此无需传递头节点的二级指针,并且实现时无需区分两种情况
    注意:有效节点的处理必须从头节点的next开始
注意:笔试题时,如果题目没有说明链表是否带头节点,应该两种情况都进行分析

二、功能受限的表结构
对表结构的功能加以限制,形成特殊的表结构
栈:
只有一个出入口的表结构,先进后出,FILO表
顺序栈:
数据项:
存储元素的内存首地址
栈的容量
栈顶位置
运算:
创建、销毁、入栈、出栈、栈顶、栈空、栈满、数量

    常见的栈的笔试题:
        1、某序列为入栈序列(并不表示必须全部入完栈,再出栈),判断哪个序列为正确\不正确的出栈序列
                        i
            入栈: 1 2 3 4 5        a
                  3  2  1 4 5        b
                        j
            出栈: 1 2 3 4 5 yes
                  3 2 1 5 4 yes
                   5 4 2 1 3 no
        2、实现一个函数,判断序列b是否是序列a的出栈序列
        int a[5] = {1,2,3,4,5},b[5]={1,2,3,4,5};
        is_pop(a,b,5)
        bool is_pop(int* a,int* b,int len)
        {
            //  创建一个栈
            ArrayStack* stack = create_arrry_stack(len)
            //  按照a的顺序一个个入栈
            for(int i= 0,j=0;i<len;i++)
            {
                push_array_stack(stack,a[i]);
                //  入栈一个就按b的顺序出栈
                int val_top = 0;
                while(top_array_stack(stack,&val_top))
                {
                    if(val_top==b[j])   
                    {
                        pop_array_stack(stack);
                        j++
                    }
                    break;
                }
            }
            //  结束后判断是否栈空
            bool flage = empty_array_stack(stack);
            destory_array_stack;
            return flage;
        }
        3、两个顺序栈,如何安排入栈方向可以让内存使用率最大化?
             让两个顺序栈相邻,且入栈方向相对入栈(也就是,在申请的内存里的,s1和s2的两个栈的栈顶的位置,一个从高到低,一个从低到高),能够让内存空间利用率最大化
        4、栈相关的概念:
            假设栈容量为cal
        空增栈(top栈顶地址从低到高):
            top: 0开始  先入栈,再top++
        满增栈(指top栈顶指向最新入栈的数据 ):
            top: -1开始  先top++,再入栈
        空减栈(top栈顶地址从高到低):
            top: cal-1开始  先入栈,再top--
        满减栈:
            top: cal开始  先top--,再入栈
    
    链式栈:
        数据项:
            栈顶指针
            节点数量
        运算:
            创建、销毁、入栈、出栈、栈顶、栈空、数量
    
    栈的应用:
    1、栈内存的数据存储方式
    2、函数的调用
    3、生产者与消费者模型(仓库:可用栈实现)
    4、表达式解析
        a+b*c/2 中缀表达式
        计算机中以后缀表达式存储 中缀转后缀表达式使用栈

热门相关:恭喜你被逮捕了   危险的课外辅导   出轨2   异世修真邪君   未来兽世:买来的媳妇,不生崽