结构_结构体 - CSDN
精华内容
参与话题
  • C语言中的结构体(struct)

    万次阅读 多人点赞 2016-02-15 20:23:39
    C语言中,结构体类型属于一种构造类型(其他的构造类型还有:数组类型,联合类型)。本文主要介绍关于结构体以下几部分。 1、概念为什么要有结构体?因为在实际问题中,一组数据往往有很多种不同的数据类型。...

    C语言中,结构体类型属于一种构造类型(其他的构造类型还有:数组类型,联合类型)。本文主要介绍关于结构体以下几部分。
    这里写图片描述

    1、概念

    为什么要有结构体?

    因为在实际问题中,一组数据往往有很多种不同的数据类型。例如,登记学生的信息,可能需要用到 char型的姓名,int型或 char型的学号,int型的年龄,char型的性别,float型的成绩。又例如,对于记录一本书,需要 char型的书名,char型的作者名,float型的价格。在这些情况下,使用简单的基本数据类型甚至是数组都是很困难的。而结构体(类似Pascal中的“记录”),则可以有效的解决这个问题。
    结构体本质上还是一种数据类型,但它可以包括若干个“成员”,每个成员的类型可以相同也可以不同,也可以是基本数据类型或者又是一个构造类型。
    结构体的优点:结构体不仅可以记录不同类型的数据,而且使得数据结构是“高内聚,低耦合”的,更利于程序的阅读理解和移植,而且结构体的存储方式可以提高CPU对内存的访问速度。

    结构声明(structure declaration)

    结构声明(也见有称做定义一个结构体)是描述结构如何组合的主要方法。
    一般形式是:
    struct 结构名{
    成员列表
    };
    struct关键词表示接下来是一个结构。
    如声明一个学生的结构:

    struct Student{         //声明结构体
        char name[20];      //姓名
        int num;            //学号
        float score;        //成绩
    };

    上面的声明描述了一个包含三个不同类型的成员的结构,但它还没创建一个实际的数据对象,类似C++中的模板。每个成员变量都用自己的声明来描述,以分号结束。花括号之后的分号表示结构声明结束。结构声明可以放在函数外(此时为全局结构体,类似全局变量,在它之后声明的所有函数都可以使用),也可以放在函数内(此时为局部结构体,类似局部变量,只能放在该函数内使用,如果与全局结构体同名,则会暂时屏蔽全局结构体)。

    要定义结构变量,则一般形式是:
    struct 结构体名 结构体变量名;
    如:

    struct Student stu1;    //定义结构体变量

    这里写图片描述
    1)、结构体变量的定义可以放在结构体的声明之后:

    struct Student{         //声明结构体
        char name[20];      //姓名
        int num;            //学号
        float score;        //成绩
    };
    struct Student stu1;    //定义结构体变量

    2)、结构体变量的定义也可以与结构体的声明同时,这样就简化了代码:

    struct Student{        
        char name[20];       
        int num;             
        float score;         
    }stu1;                  //在定义之后跟变量名

    3)、还可以使用匿名结构体来定义结构体变量:

    struct {                //没有结构名
        char name[20];       
        int num;            
        float score;         
    }stu1;  
    

    但要注意的是这样的方式虽然简单,但不能再次定义新的结构体变量了。

    访问结构成员

    虽然结构类似一个数组,只是数组元素的数据类型是相同的,而结构中元素的数据类型是可以不同的。但结构不能像数组那样使用下标去访问其中的各个元素,而应该用结构成员运算符点(.)。即访问成员的一般形式是:
    结构变量名 . 成员名
    如 stu1 . name 表示学生stu1的姓名。

    但如果结构体中的成员又是一个结构体,如:

    struct Birthday{                //声明结构体 Birthday
        int year;
        int month;
        int day;
    };
    struct Student{                 //声明结构体 Student
        char name[20];              
        int num;                    
        float score;                 
        struct Birthday birthday;   //生日
    }stu1;

    则用 stu1.birthday.year 访问出生的年份。

    结构体变量的初始化

    1)、结构体变量的初始化可以放在定义之后:

    可以对结构体的成员逐个赋值:

    struct Student stu1, stu2;      //定义结构体变量
    strcpy(stu1.name, "Jack");
    stu1.num = 18;
    stu1.score = 90.5;

    注意:不能直接给数组名赋值,因为数组名是一个常量。如:

    stu1.name = "Jack"; //…main.c:26:15: Array type 'char [20]' is not assignable

    或者可以对结构体进行整体赋值:

    stu2 = (struct Student){"Tom", 15, 88.0};

    注意:此时要进行强制类型转换,因为数组赋值也是使用{},不转换的话系统无法区分!如:

    int arr[5] = {1, 2, 3, 4, 5};       //数组的初始化
    stu2 = {"Tom", 15, 88.0};           //…main.c:31:12: Expected expression

    2)、结构体变量的初始化也可以与定义同时:

    struct Student{                 //声明结构体 Student
        char name[20];               
        int num;                    
        float score;                 
    }stu = {"Mike", 15, 91};        //注意初始化值的类型和顺序要与结构体声明时成员的类型和顺序一致

    此时不需要强制类型转换
    也可以部分初始化:

    struct Student stu4 = {.name = "Lisa"};

    也可以按照任意的顺序使用指定初始化项目:

        struct Student st = { .name = "Smith",
                              .score = 90.5,
                              .num = 18 };

    3)、可以用一个已经存在的结构体去初始化一个新的相同类型的结构体变量,是整体的拷贝(每一个成员都一一赋值给新的结构体变量),而不是地址赋值。如:

    stu3 = stu1;
    printf("stu1 addr: %p\nstu3 addr: %p\n", &stu1, &stu3);
    printf("stu1.num: %d\nstu3.num: %d\n", stu1.num, stu3.num);
    printf("stu1.num addr: %p\nstu3.num addr: %p\n", &stu1.num, &stu3.num);
    //输出结果:
    stu1 addr: 0x10000104c
    stu3 addr: 0x100001084
    stu1.num: 18
    stu3.num: 18
    stu1.num addr: 0x100001060
    stu3.num addr: 0x100001098

    2、结构体变量的存储原理

    1)结构体数据成员对齐的意义

    内存是以字节为单位编号的,某些硬件平台对特定类型的数据的内存要求从特定的地址开始,如果数据的存放不符合其平台的要求,就会影响到访问效率。所以在内存中各类型的数据按照一定的规则在内存中存放,就是对齐问题。而结构体所占用的内存空间就是每个成员对齐后存放时所占用的字节数之和。
    计算机系统对基本数据类型的数据在内存中存放的限制是:这些数据的起始地址的值要求是某个数K的倍数,这就是内存对齐,而这个数 K 就是该数据类型的对齐模数(alignment modulus)。这样做的目的是为了简化处理器与内存之间传输系统的设计,并且能提升读取数据的速度。
    结构体对齐不仅包括其各成员的内存对齐(即相对结构体的起始位置),还包括结构体的总长度。

    2)结构体大小的计算方法和步骤
    i. 将结构体内所有数据成员的长度值相加,记为 sum_a ;
    ii. 将各数据成员为了内存对齐,按各自对齐模数而填充的字节数累加到sum_a上,记为sum_b。
    对齐模数是 #pragma pack 指定的数值与该数据成员自身长度相比较得到的数值较小者。该数据相对起始位置应该是对齐模数的整数倍。
    iii. 将和 sum_b 向结构体模数对齐。
    该模数则是 #pragma pack 指定的数值与结构体内最大的基本数据类型成员长度相比较得到的数值较小者。结构体的长度应该是该模数的整数倍。

    数据类型自身对齐:
    这里写图片描述
    所谓“对齐在N上”,是指“存放的起始位置是%N = 0”.

    3)在没有#pragma pack宏的情况下:
    例子1:

    这里写图片描述

    内存分配状态为:

    这里写图片描述

    对于结构体的第一个成员 a,起始位置为0x…38 (也为 4 的倍数),所占内存为 0x…38 ~ 0x…3b,共占4个字节;
    对于结构体的第二个成员 b,自身长度为1,对齐模数也为1,所以内存分配可以紧接着a的结尾位置 0x…3b,所以起始位置为 0x…3c,共占1个字节;
    对于结构体的第三个成员 c,自身长度为2,对齐模数也为2,所以起始位置距离a 的起始位置应该是2的倍数,所以 0x…3d处只距离5,不符合要求,所以空着,继续往下找,而在 0x…3e处满足要求,所以可以作为c的起始位置,共占2个字节;
    此时3个成员及其中间空着的位置所占内存单元总和为8,而结构体内最大的基本数据成员是 a,其长度为4,所以结构体模数为 4,而8是4的倍数,满足要求,故不再加内存。

    例子2:
    与例子1相比,三个类型的声明顺序变了:

    这里写图片描述

    内存分配状态为:
    这里写图片描述

    要注意的是,对 a而言,对齐模数为 4,所以当 b的起始位置在0x7f…830之后,0x7f…831、0x7f…832、0x7f…833的位置距离起始位置0x7f…830分别是1,2,3,都不是 4 的倍数,所以那三个位置都空着,直到0x7f…834才满足要求,所以作为 a 的起始位置。当最后 一个成员 c 占的内存末尾在0x7f…839时,所有数据成员及其之间的空位所占内存单元总和为10,而结构体模数为4,10不是4的倍数,所以要扩大到12才满足要求,此时又多了2个空位置,就是0x7f…83a和0x7f…83b。

    例子3:
    当结构体中有数组时:

    这里写图片描述

    内存分配状态为:
    这里写图片描述

    亦即相同类型数据的数组之间多分配的空间会被相邻数组的元素所占用。

    4)在存在#pragma pack宏的情况下:
    方法类似,只是模数可能会按上面说的规则而有所变化。

    这里写图片描述

    内存分配状态为:
    这里写图片描述

    注意,当没有#pragma pack(2)时,成员a要确定自身的q起始位置,是以自身的长度4为对齐模数,但有了#pragma pack(2),则将括号里的2与a的长度4比较,2为较小者,所以以2为a的对齐模数,即地址从0x7f…839往下找到0x7f…83a时,已经距离结构体的起始位置0x7f…838为2,是2的倍数,满足要求(虽然不是4的倍数),可以作为a的起始位置。而最后,所有数据成员及其之间的空位所占内存单元总和为8,因为2和4(结构体中最大的数据成员长度)的较小者为2,而8是2的倍数,所以刚好满足要求,不用在分配空位置,所以结构体总长度即为8。

    3、结构体数组

    结构类型作为一种数据类型,也可以像基本数据类型那样,作为数组的元素的类型。元素属于结构类型的数组成为结构型数组。如开头提出的问题,生活中经常用到结构数组来表示具有相同数据结构的一个群体,如一个班的学生的信息,一个书店或图书馆的书籍信息等。

    1)结构数组定义
    一般格式:
    struct 结构名 {
    成员列表
    } 数组名[数组长度];
    如:

    struct Student{                 //声明结构体 Student
        char name[20];
        int num;
        float score;
    }stu[5];                        //定义一个结构结构数组stu,共有5个元素

    2)结构数组的初始化

    定义结构数组的同时进行初始化

    struct Student stu[2] = {{"Mike", 27, 91},{"Tom", 15, 88.0}};  

    先定义,后初始化
    整体赋值:

    stu[2] = (struct Student){"Jack", 12, 85.0};

    或者将结构体变量的成员逐个赋值:

    strcpy(stu[3].name, "Smith");
    stu[3].num = 18;
    stu[3].score = 90.5;

    输出结构体:

    //结构体数组的长度:
    int length = sizeof(stu) / sizeof(struct Student);
    //逐个输出结构数组的元素
    for (int i = 0; i < length; i++) {
        printf("姓名:%s  学号:%d  成绩:%f \n", stu[i].name, stu[i].num, stu[i].score);
    }

    //输出结果:
    这里写图片描述

    在这个例子中,要注意的是:
    这里写图片描述

    4、结构与指针

    当一个指针变量用来指向了一个结构变量,这个指针就成了结构指针变量。
    结构指针变量中的值是所指向的结构变量的首地址。可以通过指针来访问结构变量。

    1)定义结构指针变量的一般形式:
    struct 结构名 * 结构指针变量名
    如:

    struct Student *pstu;       //定义了一个指针变量,它只能指向Student结构体类型的结构体变量

    结构指针变量的定义也可以与结构体的定义同时。而且它必须先赋值后使用。
    数组名表示的是数组的首地址,可以直接赋值给数组指针。但结构变量名只是表示整个结构体变量,不表示结构体变量的首地址,所以不能直接赋值给结构指针变量,而应该使用 & 运算符把结构变量的的地址赋值给结构指针变量。即:

    这里写图片描述

    注意:结构名、结构变量名、结构体指针的区别。

    2)通过结构指针间接访问成员值

    访问的一般形式:
    (*结构指针变量). 成员名 或 结构指针变量 -> 成员名
    如:

    (*pstu).name    
    pstu->name

    注意(pstu)的小括号不能省略,因为成员符“.”优先级为1,取地址符“”优先级为2,去掉括号就相当于*(pstu.name)了。

    5、结构体的嵌套

    1)结构体中的成员可以又是一个结构体,构成结构体的嵌套:

    struct Birthday{                //声明结构体 Birthday
        int year;
        int month;
        int day;
    };
    struct Student{                 //声明结构体 Student
        char name[20];              
        int num;                    
        float score;                 
        struct Birthday birthday;   //生日
    }; 
    

    这里写图片描述
    2)结构体不可以嵌套跟自己类型相同的结构体,但可以嵌套定义自己的指针。如:

    struct Student{                 //声明结构体 Student
        char name[20];
        int num;
        float score;
        struct Student *friend;     //嵌套定义自己的指针
    }

    3)甚至可以多层嵌套:

    struct Time{                    //声明结构体 Time
        int hh;                     //时
        int mm;                     //分
        int ss;                     //秒
    };
    struct Birthday{                //声明结构体 Birthday
        int year;
        int month;
        int day;
        struct Time dateTime        //嵌套结构
    };
    struct Student{                 //声明结构体 Student
        char name[20];
        int num;
        float score;
        struct Birthday birthday;   //嵌套结构
    }
    //定义并初始化
    struct Student stud = {"Jack", 32, 85, {1990, 12, 3, {12, 43, 23}}};
    //访问嵌套结构的成员并输出
    printf("%s 的出生时刻:%d时 \n", stud.name, stud.birthday.dateTime.hh);
    //输出结果:Jack 的出生时刻:12时 

    注意如何初始化和对嵌套结构的成员进行访问。

    6、结构与函数

    结构体的成员可以作为函数的参数,属于值传递(成员是数组的除外)。如:

    struct Student{                 //声明结构体 Student
        char name[20];
        int num;
        float score;
    };
    void printNum(int num){         //定义一个函数,输出学号
        printf("num = %d \n", num);
    }
        struct Student student0 = {"Mike", 27, 91};
        printNum(student0.num);     //调用printNum 函数,以结构成员作函数的参数
    //运行结果:num = 27 

    注意,函数printNum并不知道也不关心实际参数是不是结构成员,它只要求实参是int类型的就可以了。

    结构变量名也可以作为函数的参数传递,如:

    void PrintStu(struct Student student){      //定义 PrintStu 函数,以结构变量作函数的形参
        student.num = 100;                      //修改学号
        printf("PrintStu 修改后:姓名: %s, 学号: %d, 内存地址: %p \n", student.name, student.num, &student);
    }
        struct Student student0 = {"Mike", 27, 91};
        PrintStu(student0);                     //调用 PrintStu 函数,以结构变量名作函数的参数
        printf("           原来:姓名: %s, 学号: %d,  内存地址: %p \n", student0.name, student0.num, &student0);
    

    //输出结果:
    这里写图片描述

    形参和实参的地址不一样,是在函数中创建了一个局部结构体,然后实参对形参进行全部成员的逐个传送,在函数中对局部结构体变量进行修改并不影响原结构体变量。这样传送的时间空间开销都比较大,特别是当成员有数组的时候,程序效率较低。所以可以考虑使用指针:

    void PrintStu2(struct Student *student){      //定义 PrintStu2 函数,以结构指针作函数的形参
        student->num = 100;                       //修改学号
        printf("PrintStu2 修改后:姓名: %s, 学号: %d, 内存地址: %p \n", student->name, student->num, student);
    }
        struct Student student0 = {"Mike", 27, 91};
        PrintStu2(&student0);                     //调用 PrintStu 函数,以结构变量的地址作函数的参数
        printf("           原来:姓名: %s, 学号: %d,  内存地址: %p \n", student0.name, student0.num, &student0);

    //输出结果:
    这里写图片描述

    形参和实参的地址是一样的,所以是地址传递,在 PrintStu2 函数中,student 与&student0 指向同一块内存单元,用指针student修改结构变量会影响原结构变量。

    展开全文
  • 操作系统结构

    万次阅读 2018-07-13 12:58:45
    操作系统的内部的六种不同的结构设计:单体系统、层次系统、微内核、客户机-服务器系统、虚拟机和exokernels。 一、单体系统 二、层次式系统 三、微内核 四、客户机-服务器模式 五、虚拟机 六、外核...

    操作系统的内部的六种不同的结构设计:单体系统、层次系统、微内核、客户机-服务器系统、虚拟机和exokernels。

    一、单体系统

    在多数常见的组织形式的处理方式中,全部操作系统在内核态中以单一程序的方式运行。整个操作系统以过程集合的方式编写,链接成一个大型可执行二进制程序。
    在单体系统中,也可能有一些结构存在。可以将参数放置在良好定义的位置,通过这种方式,向操作系统请求所能提供的服务(系统调用),然后执行一个陷阱指令,这个指令将机器从用户态切换到内核态并把控制传递给操作系统,然后操作系统取出参数并且确定应该执行哪个系统调用,随后在一个表格中检索,在该表格的k槽中存放着指向执行系统调用k过程的指针。
    对于这类操作系统的基本结构:
    1. 需要一个主程序,用来处理服务过程请求。
    2. 需要一套服务过程,用来执行系统调用。
    3. 需要一套实用过程,用来辅助服务过程。
    在该模型中,每一个系统调用都通过一个服务过程为其工作并运行之。要有一组实用程序来完成一些服务过程所需要用到的功能。
    简单的单体系统结构图示:
    简单的单体系统结构

    二、层次式系统

    单体系统进一步通用化,就变成一个层次式结构的操作系统,它的上层软件都是在下一层软件的基础之上构建的。THE系统是按此模型构造的第一个操作系统。
    THE系统共分为六层。
    0. 处理器分配和多道程序设计
    处理器分配分配在第0层中进行,当中断发生或定时器到期时,由该层进行进程切换。在第0层之上,系统由一些连续的进程所组成,编写这些进程时不用再考虑在单处理器上多进程运行的细节。也就是说,在第0层中提供了基本的CPU多道程序功能。
    1. 存储器和磁鼓管理
    内存管理在第1层中进行,它分配进程的主存空间,当内存用完时则在一个512k字的磁鼓上保留进程的一部分(页面),在第1层上,进程不用考虑它是在磁鼓上还是在内存中进行。第1层软件保证一旦需要访问某一个页面时,该页面必定已在内存中。
    2. 操作员-进程通信
    第2层处理进程与操作员控制台(即用户)之间的通信。在这层的上不,可以认为每个进程都有自己的操作员控制台。
    3. 输入/输出管理
    第3层管理I/O设备和相关的信息流缓冲区。在第3层上,每个进程都与有良好特性的抽象I/O设备打交道,而不必考虑外部设备的物理细节。
    4. 用户程序
    第4层是用户程序层,用户程序不必考虑进程、内存、控制台或I/O设备管理细节。
    5. 操作员
    系统操作员进程位于第5层中。

    MULTICS系统

    该系统由许多的同心环构造而成,而不是采用层次化构造。内层环比外层环有更高的级别。当外环的过程欲调用内环的过程时,它必须执行一条等价于系统调用的TRAP指令。在执行该TRAP指令前,要进行严格的桉树合法性检查。

    三、微内核

    在微内核设计背后的思想是为了实现高可靠性,将操作系统划分成小的、良好定义的模块,只有其中一个模块–微内核–运行在内核态上,其余的模块,由于功能相对弱些,则作为普通用户进程运行。特别地由于把每个设备驱动和文件系统分别作为普通用户,这些模块中的错误虽然会使这些模块崩溃,但是不会使得整系统死机。
    微内核在实时、工业、航空以及军事应用中特别流行。
    MINIX3系统结构图示:
    微内核实例

    再生服务器

    检查其他服务器和驱动器的功能是否正确,一旦检查出一个错误,它自动取代之,无需任何用户的干预。这种方式使得系统具有自修复能力,并且获得了较高的可靠性。
    系统对每个进程的权限有着许多限制。一个与小内核相关联的思想是在内核中的机制与策略分离的原则。一个比较简单的调度算法是,对于每个进程赋予一个优先级,并让内核执行在具有最高优先级进程中可以运行的某个进程。这里机制(在内核中)就是寻找最高优先级的进程并运行之。而策略(赋予进程以优先级)可以由用户态中的进程完成。在这个方式中,机制和策略是分离的,从而使系统内核变得更小。

    四、客户机-服务器模式

    一个微内核思想的略微变体是将进程划分为:
    1. 服务器:每个服务器提供某种服务。
    2. 客户端:使用这些服务。
    这个模式就是所谓的客户机-服务器模式。通常在系统最底层是微内核,这个模式的本质是存在客户端进程和服务器进程。
    在客户端和服务器之间的通信是消息传递。普遍方式是客户端和服务器在不同的计算机上,通过局域网或广域网连接,由于客户端通过发送消息与服务端通信,客户端并不需要知道这些消息是在它们的本地机器上处理,还是通过网络被送到远程机器上处理。
    客户端-服务器模型实例:
    客户端-服务器

    五、虚拟机

    1. VM/370

    最初命名为CP/CMS,后来改名为VM/370,它的目的是为了将多道程序和获取更方便的裸机彻底隔离。它的核心称为虚拟机监控程序,它在裸机上运行并且具备了多道程序功能。该系统向上层提供了若干个虚拟机。它不同于其他操作系统:这些虚拟机不是那种具有文件等优良特征的扩展计算机。它们仅仅是裸机硬件的精确复制品,包含了内核态/用户态、I/O功能、中断及其他真是硬件所具备的全部内容。

    2. 虚拟机的再次发现

    虚拟化的优点:
    1. 一台物理机就可以运行许多虚拟机,每个虚拟机看起来都是一台完全的机器。这样可以节省费用。
    2. 可以同时运行两个或多个操作系统。

    3. Java虚拟机

    它是一种体系结构。Java编译器为JVM生成代码,这些代码以后可以由一个软件JVM解释器质性。这种处理方式的优点在于,JVM代码可以通过Internet传送到任何有JVM解释器的机器上,并在该机器执行。使用JVM的优点就是如果解释器正确地完成,并不意味着结束,还要对所输入的KVM进行安全性检测,然后在一直保护环境下执行,这样,这些程序就不能偷窃数据或进行其他任何有害的操作。

    六、外核

    与虚拟机克隆真实机器不同,另一种策略是对机器进行分区。给每个用户整个资源的一个子集。
    在底层中,一种称为外核的程序在内核态中运行。它的任务是为虚拟机分配资源,并检查试图使用这些资源的企图,以确保没有机器会使用他人资源。每个用户层的虚拟机可以运行自己的操作系统,但限制在只能使用已经申请并且获得分配的那部分资源。
    外核机制的优点是减少了映像层。在其他的设计中,每个虚拟机都认为它有的磁盘,其盘块号从0到最大编号,这样虚拟机监控程序必须维护一张表格用以重映像磁盘地址,有了外核这个重映像处理就不需要了,外核只需要记录已经分配各个虚拟机的有关资源即可。这个方法还有一个优点,它将多道程序(在外核内)与用户操作系统代码(在用户控件内)加以分离,而且相应负载并不重,这是因为外核所做的一切,只是保持多个虚拟机彼此不发生冲突。

    展开全文
  • 树的三种存储结构

    万次阅读 多人点赞 2017-03-19 19:46:38
    之前我们一直在谈的是一对一的线性结构,可现实中,还有很多一对多的情况需要处理,所以我们需要研究这种一对多的数据结构----"树",考虑它的各种特性,来解决我们在编程中碰到的相关问题。 树(Tree)是n(n>=0)个...

    6.2树的定义

    之前我们一直在谈的是一对一的线性结构,可现实中,还有很多一对多的情况需要处理,所以我们需要研究这种一对多的数据结构----"树",考虑它的各种特性,来解决我们在编程中碰到的相关问题。
    树(Tree)是n(n>=0)个结点的有限集。n=0时称为空树。在任意一棵非空树中:(1)有且仅有一个特定的称为根(Root)的结点;(2)当n>1时,其余结点可分为m(m>O)个互不相交的有限集T1、T2、……、 Tm,其中每一个集合本身又是一棵树,并且称为根的子树(SubTree),如图6-2-1所示。

    树的定义其实就是我们在讲解栈时提到的递归的方法。也就是在树的定义之中还用到了树的概念,这是一种比较新的定义方法。图6-2-2的子树T1和子树T2就是根结点A的子树。当然,D、G、H、I组成的树又是B为结点的子树,E、J组成的树是C为结点的子树。

    对于树的定义还需要强调两点:
    1.n>0时根结点是唯一的,不可能存在多个根结点,别和现实中的大树混在一起,现实中的树有很多根须,那是真实的树,数据结构中的树是只能有一个根结点。
    2.m>0时,子树的个数没有限制,但它们一定是互不相交的。像图6-2-3中的两个结构就不符合树的定义,因为它们都有相交的子树。

    6.2.1 结点分类

    树的结点包含一个数据元素及若干指向其子树的分支。结点拥有的子树数称为结点的度(Degree)度为0的结点称为叶结点(Leaf)或终端结点;度不为0的结点称为非终端结点或分支结点。除根结点之外,分支结点也称为内部结点。树的度是树内各结点的度的最大值。如图6-2-4所示,因为这棵树结点的度的最大值是结点D的度,为3,所以树的度也为3。

    6.2.2 结点间关系

    结点的子树的根称为该结点的孩子(Child),相应地,该结点称为孩子的双亲(Parent)。恩,为什么不是父或母,叫双亲呢?对于结点来说其父母同体,唯一的一个,所以只能把它称为双亲了。同一个双亲的孩子之间互称兄弟(Sibling)结点的祖先是从根到该结点所经分支上的所有结点。所以对于H来说,D、B、A都是它的祖先。反之,以某结点为根的子树中的任一结点都称为该结点的子孙。B的子孙有D、G、H、I,如图6-2-5所示。

    6.2.3 树的其他相关概念

    结点的层次(Level)从根开始定义起,根为第一层,根的孩子为第二层。若某结点在第l层,则其子树的根就在第1+1层。其双亲在同一层的结点直为堂兄弟。显然图6-2-6中的D、E、F是堂兄弟,而G、H、I、J也是。树中结点的最大层次称为树的深度(Depth)或高度,当前树的深度为4。

    如果将树中结点的各子树看成从左至右是有次序的,不能互换的,则称该树为有序树,否则称为无序树。
    森林(Forest)是m(m>0)棵互不相交的树的集合。对树中每个结点而言,其子树的集合即为森林。对于图6-2-1中的树而言,图6-2-2中的两棵子树其实就可以理解为森林。
    对比线性表与树的结构,它们有很大的不同,如图6-2-7所示。

    6.4树的存储结构

    说到存储结构,就会想到我们前面章节讲过的顺序存储和链式存储两种结构。
    先来看看顺序存储结构,用一段地址连续的存储单元依次存储线性表的数据元素。这对于线性表来说是很自然的,对于树这样一多对的结构呢?
    树中某个结点的孩子可以有多个,这就意味着,无论按何种顺序将树中所有结点存储到数组中,结点的存储位置都无法直接反映逻辑关系,你想想看,数据元素挨个的存储,谁是谁的双亲,谁是谁的孩子呢?简单的顺序存储结构是不能满足树的实现要求的。
    不过充分利用顺序存储和链式存储结构的特点,完全可以实现对树的存储结构的表示。我们这里要介绍三种不同的表示法:双亲表示法、孩子表示法、孩子兄弟表示法

    6.4.1 双亲表示法

    我们人可能因为种种原因,没有孩子,但无论是谁都不可能是从石头里蹦出来的,孙悟空显然不能算是人,所以是人一定会有父母。树这种结构也不例外,除了根结点外,其余每个结点,它不一定有孩子,但是一定有且仅有一个双亲。
    我们假设以一组连续空间存储树的结点,同时在每个结点中,附设一个指示器指示其双亲结点到链表中的位置。也就是说,每个结点除了知道自己是谁以外,还知道它的双亲在哪里。它的结点结构为表6-4-1所示。

    其中data是数据域,存储结点的数据信息。而parent是指针域,存储该结点的双亲在数组中的下标。
    由于根结点是没有双亲的,所以我们约定根结点的位置域设置为-1,这也就意味着,我们所有的结点都存有它双亲的位置。如图6-4-1中的树结构和表6-4-2中的树双亲表示所示。

    这样的存储结构,我们可以根据结点的parent指针很容易找到它的双亲结点,所用的时间复杂度为O(1),直到parent为-1时,表示找到了树结点的根。可如果我们要知道结点的孩子是什么,对不起,请遍历整个结构才行。
    这真是麻烦,能不能改进一下呢?
    当然可以。我们增加一个结点最左边孩子的域,不妨叫它长子域,这样就可以很容易得到结点的孩子。如果没有孩子的结点,这个长子域就设置为-1,如表6-4-3所示。(表中下标为0的firstchild应该为1)

    对于有0个或1个孩子结点来说,这样的结构是解决了要找结点孩子的问题了。甚至是有2个孩子,知道了长子是谁,另一个当然就是次子了。
    另外一个问题场景,我们很关注各兄弟之间的关系,双亲表示法无法体现这样的关系,那我们怎么办?嗯,可以增加一个右兄弟域来体现兄弟关系,也就是说,每一个结点如果它存在右兄弟,则记录下右兄弟的下标。同样的,如果右兄弟不存在,则赋值为-1 ,如表6-4-4所示。

    但如果结点的孩子很多,超过了2个。我们又关注结点的双亲、又关注结点的孩子、还关注结点的兄弟,而且对时间遍历要求还比较高,那么我们还可以把此结构扩展为有双亲域、长子域、再有右兄弟域。存储结构的设计是一个非常灵活的过程。一个存储结构设计得是否合理,取决于基于该存储结构的运算是否适合、是否方便,时间复杂度好不好等。注意也不是越多越好,有需要时再设计相应的结构。就像再好昕的音乐,不停反复听上千遍也会腻味,再好看的电影,一段时间反复看上百遍,也会无趣,你们说是吧?

    6.4.2 孩子表示法

    换一种完全不同的考虑方法 . 由于树中每个结点可能有多棵子树,可以考虑用多重链表,即每个结点有多个指针域,其中每个指针指向一棵子树的根结点,我们把这种方法叫做多重链表表示法。不过,树的每个结点的度,也就是它的孩子个数是不同的。所以可以设计两种方案来解决。
    方案一
    一种是指针域的个数就等于树的度,复习一下,树的度是树各个结点度的最大值。其结构如表6-4-5所示。

    其中data是数据域。childl到childd是指针域,用来指向该结点的孩子结点。
    对于图6-4-1的树来说,树的度是3,所以我们的指针域的个数是3,这种方法实现如图6-4-2所示。

    这种方法对于树中各结点的度相差很大时,显然是很浪费空间的,因为有很多的结点,它的指针域都是空的。不过如果树的各结点度相差很小时,那就意味着开辟的空间被充分利用了,这时存储结构的缺点反而变成了优点。
    既然很多指针域都可能为空,为什么不按需分配空间呢。于是我们有了第二种方案。
    方案二
    第二种方案每个结点指针域的个数等于该结点的度,我们专门取一个位置来存储结点指针域的个数,其结构如表6-4-6所示。

    其中data为数据域,degree为度域,也就是存储该结点的孩子结点的个数,child1到childd为指针域,指向该结点的各个孩子的结点。
    对于图6-4-2的树来说,这种方法实现如图6-4-3所示。

    这种方法克服了浪费空间的缺点,对空间利用率是很高了,但是由于各个结点的链表是不相同的结构,加上要维护结点的度的数值,在运算上就会带来时间上的损耗。
    能否有更好的方法,既可以减少空指针的浪费又能使结点结构相同。
    仔细观察,我们为了要遍历整棵树,把每个结点放到一个顺序存储结构的数组中是合理的,但每个结点的孩子有多少是不确定的,所以我们再对每个结点的孩子建立一个单链表体现它们的关系 。
    这就是我们要讲的孩子表示法。具体办法是,把每个结点的孩子结点排列起来,以单链表作存储结构,则n个结点有n个孩子链表,如果是叶子结点则此单链表为空。然后n个头指针又组成一个线性表,采用顺序存储结构,存放进一个一维数组中,如图6-4-4所示。

    为此,设计两种结点结构,一个是孩子链表的孩子结点,如表6-4-7所示。

    其中child是数据域,用来存储某个结点在表头数组中的下标。next是指针域,用来存储指向某结点的下一个孩子结点的指针。
    另一个是表头数组的表头结点,如表6-4-8所示。

    其中data是数据域,存储某结点的数据信息。firstchild是头指针域,存储该结点的孩子链表的头指针。
    这样的结构对于我们要查找某个结点的某个孩子,或者找某个结点的兄弟,只需要查找这个结点的孩子单链表即可。对于遍历整棵树也是很方便的,对头结点的数组循环即可。
    但是,这也存在着问题,我如何知道某个结点的双亲是谁呢?比较麻烦,需要整棵树遍历才行,难道就不可以把双亲表示法和孩子表示法综合一下吗?当然是可以。如图6-4-5所示。

    我们把这种方法称为双亲孩子表示法,应该算是孩子表示法的改进。

    6.4.3 孩子兄弟表示法

    刚才我们分别从双亲的角度和从孩子的角度研究树的存储结构,如果我们从树结点的兄弟的角度又会如何呢? 当然,对于树这样的层级结构来说,只研究结点的兄弟是不行的,我们观察后发现,任意一棵树,它的结点的第一个孩子如果存在就是唯一的,它的右兄弟如果存在也是唯一的。 因此,我们设置两个指针,分别指向该结点的第一个孩子和此结点的右兄弟。结点结构如表6-4-9所示。

    其中data是数据域,firstchild为指针域,存储该结点的第一个孩子结点的存储地址,rightsib是指针域,存储该结点的右兄弟结点的存储地址。
    对于图6-4-1的树来说,这种方法实现的示意图如图6-4-6所示。

    这种表示法,给查找某个结点的某个孩子带来了方便,只需要通过firstchild找到此结点的长子,然后再通过长子结点的rightsib找到它的二弟,接着一直下去,直到找到具体的孩子。当然,如果想找某个结点的双亲,这个表示法也是有做陷的,那怎么办呢?
    对,如果真的有必要,完全可以再增加一个parent指针域来解决快速查找双亲的问题,这里就不再细谈了。
    其实这个表示法的最大好处是它把一棵复杂的树变成了一棵二叉树。我们把图6-4-6变变形就成了图6-4-7这个样子。

    这样就可以充分利用二叉树的特性和算法来处理这棵树了。嗯?有人间,二叉树是什么?哈哈,别急,这正是我接下来要重点讲的内容。
    引用《大话数据结构》作者:程杰
    展开全文
  • C语言的四种程序结构

    万次阅读 2018-01-02 12:13:59
    1、顺序结构 顺序结构的程序设计是最简单的,只要按照解决问题的顺序写出相应的语句就行,它的执行顺序是自上而下,依次执行。例如;a = 3,b = 5,现交换a,b的值,这个问题就好像交换两个杯子水,这当然要用到第...

    1、顺序结构
    顺序结构的程序设计是最简单的,只要按照解决问题的顺序写出相应的语句就行,它的执行顺序是自上而下,依次执行。

    例如;a = 3,b = 5,现交换a,b的值,这个问题就好像交换两个杯子水,这当然要用到第三个杯子,假如第三个杯子是c,那么正确的程序为: c = a; a = b; b = c; 执行结果是a = 5,b = c = 3。

    如果改变其顺序,写成:a = b; c = a; b = c; 则执行结果就变成a = b = c = 5,不能达到预期的目的,这是我们初学者最容易犯这种错误,所以一定要多加注意。

    顺序结构可以独立使用构成一个简单的完整程序,常见的输入、计算,输出三步曲的程序就是顺序结构,例如计算圆的面积,其程序的语句顺序就是输入圆的半径r,计算s = 3.14159*r*r,输出圆的面积s。

    不过大多数情况下顺序结构都是作为程序的一部分,与其它结构一起构成一个复杂的程序,例如分支结构中的复合语句、循环结构中的循环体等

    这里写图片描述

    2、分支结构
    顺序结构的程序虽然能解决计算、输出等问题,但不能做判断再选择。对于要先做判断再选择的问题就要使用分支结构。

    分支结构的执行是依据一定的条件选择执行路径,而不是严格按照语句出现的物理顺序。分支结构的程序设计方法的关键在于构造合适的分支条件和分析程序流程,根据不同的程序流程选择适当的分支语句。

    分支结构适合于带有逻辑或关系比较等条件判断的计算,设计这类程序时往往都要先绘制其程序流程图,然后根据程序流程写出源程序,这样做把程序设计分析与语言分开,使得问题简单化,易于理解。

    程序流程图是根据解题分析所绘制的程序执行流程图。

    这里写图片描述

    学习分支结构不要被分支嵌套所迷惑,只要正确绘制出流程图,弄清各分支所要执行的功能,嵌套结构也就不难了。嵌套只不过是分支中又包括分支语句而已,不是新知识,只要对双分支的理解清楚,分支嵌套是不难的。下面我介绍几种基本的分支结构。

    ①if(条件)
    {
    分支体
    }

    这种分支结构中的分支体可以是一条语句,此时“{ }”可以省略,也可以是多条语句即复合语句。

    它有两条分支路径可选,一是当条件为真,执行分支体,否则跳过分支体,这时分支体就不会执行。如:要计算x的绝对值,根据绝对值定义,我们知道,当x>=0时,其绝对值不变,而x<0时其绝对值是为x的反号,因此程序段为:if(x<0) x=-x;

    ②if(条件)
    {分支1}
    else
    {分支2}

    这里写图片描述

    这是典型的分支结构,如果条件成立,执行分支1,否则执行分支2,分支1和分支2都可以是1条或若干条语句构成。如:求ax^2+bx+c=0的根

    分析:因为当b^2-4ac>=0时,方程有两个实根,否则(b^2-4ac<0)有两个共轭复根。其程序段如下:

    d=b*b-4*a*c; 
    if(d>=0) 
    {x1=(-b+sqrt(d))/2a; 
    x1=(-b-sqrt(d))/2a; 
    printf("x1=%8.4f,x2=%8.4f\n",x1,x2); 
    } 
    else 
    {r=-b/(2*a); 
    i =sqrt(-d)/(2*a); 
    printf("x1=%8.4f+%8.4fi\n"r, i); 
    printf("x2=%8.4f-%8.4fi\n"r,i); 
    } 

    ③嵌套分支语句:其语句格式为:
    if(条件1) {分支1};
    else if(条件2) {分支2}
    else if(条件3) {分支3}
    ……
    else if(条件n) {分支n}
    else {分支n+1}

    嵌套分支语句虽可解决多个入口和出口的问题,但超过3重嵌套后,语句结构变得非常复杂,对于程序的阅读和理解都极为不便,建议嵌套在3重以内,超过3重可以用下面的语句。

    ④switch开关语句:该语句也是多分支选择语句,到底执行哪一块,取决于开关设置,也就是表达式的值与常量表达式相匹配的那一路。

    它不同if…else 语句,它的所有分支都是并列的,程序执行时,由第一分支开始查找,如果相匹配,执行其后的块,接着执行第2分支,第3分支……的块,直到遇到break语句;如果不匹配,查找下一个分支是否匹配。

    这个语句在应用时要特别注意开关条件的合理设置以及break语句的合理应用。

    3、循环结构

    循环结构可以减少源程序重复书写的工作量,用来描述重复执行某段算法的问题,这是程序设计中最能发挥计算机特长的程序结构,C语言中提供四种循环,即goto循环、while循环、do –while循环和for循环。

    四种循环可以用来处理同一问题,一般情况下它们可以互相代替换,但一般不提倡用goto循环,因为强制改变程序的顺序经常会给程序的运行带来不可预料的错误,在学习中我们主要学习while、do…while、for三种循环。

    常用的三种循环结构学习的重点在于弄清它们相同与不同之处,以便在不同场合下使用,这就要清楚三种循环的格式和执行顺序,将每种循环的流程图理解透彻后就会明白如何替换使用。

    如把while循环的例题,用for语句重新编写一个程序,这样能更好地理解它们的作用。特别要注意在循环体内应包含趋于结束的语句(即循环变量值的改变),否则就可能成了一个死循环,这是初学者的一个常见错误。

    这里写图片描述

    在学完这三个循环后,应明确它们的异同点:用while和do…while循环时,循环变量的初始化的操作应在循环体之前,而for循环一般在语句1中进行的;

    while 循环和for循环都是先判断表达式,后执行循环体,而do…while循环是先执行循环体后判断表达式,也就是说do…while的循环体最少被执行一次,而while 循环和for就可能一次都不执行。

    另外还要注意的是这三种循环都可以用break语句跳出循环,用continue语句结束本次循环,而goto语句与if构成的循环,是不能用break和 continue语句进行控制的。

    顺序结构、分支结构和循环结构并不彼此孤立的,在循环中可以有分支、顺序结构,分支中也可以有循环、顺序结构,其实不管哪种结构,我们均可广义的把它们看成一个语句。

    这里写图片描述
    4、模块化程序结构

    C语言的模块化程序结构用函数来实现,即将复杂的C程序分为若干模块,每个模块都编写成一个C函数,然后通过主函数调用函数及函数调用函数来实现一大型问题的C程序编写。

    因此常说:C程序=主函数+子函数。 因此,对函数的定义、调用、值的返回等中要尤其注重理解和应用,并通过上机调试加以巩固。

    展开全文
  • 0.引言 ResNet在2015年被提出,在ImageNet比赛classification任务上获得第一名,因为它“简单与实用”并存,之后很多方法都建立在ResNet50或者ResNet101的基础上完成的,检测,分割,识别等领域都纷纷使用ResNet,...
  • 图——基本的图算法(一)图的存储结构 1. 图的表示方法 对于图G=(V, E)来说,可以有两种标准的表示方法,这两种方法都可以表示有向图和无向图: (1)邻接矩阵 (2)邻接链表 ...
  • 哈佛结构/冯诺依曼结构详细分析

    千次阅读 2019-06-16 17:33:56
    CISC与RISC的区别: CISC(复杂指令集):复杂指令集就是CPU在工作的时候需要有很多的汇编指令来完成,它可以用一个汇编指令来完成一件复杂的工作。例如:乘法,加法,乘加,乘减等处理的时候,他会每个处理方式用...
  • 数据结构:八大数据结构分类

    万次阅读 多人点赞 2018-09-05 18:23:28
    数据结构分类 数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成 。 常用的数据结构有:数组,栈,链表,队列,树,图,堆,散列表等,如图所示: 每一种数据结构都...
  • 数据结构分别为逻辑结构、(存储)物理结构和数据的运算三个部分。 为什么要学数据结构? 首先,因为数据结构作为计算机专业的专业基础课程,是计算机考研的必考科目之一,如果打算报考计算机专业的研究生,你...
  • 小猪的数据结构辅助教程——前言

    万次阅读 多人点赞 2019-05-31 13:56:34
    面试给人上了一课,突然感觉数据结构很重要;还有,帮助后来者,刚接触数据结构的 童鞋们一点点方向,不至于学完什么都不知道!大部分学校采用的教程应该是严蔚敏老师的 《数据结构(C语言版)》吧,而讲数据结构课程...
  • 微软等数据结构+算法面试100题全部答案集锦

    万次下载 热门讨论 2020-07-28 11:04:57
    一年之前的10月14日,一个名叫July 的人在一个叫csdn 的论坛上开帖分享微软等公司数据结构+算法 面试100题,自此,与上千网友一起做,一起思考,一起解答这些面试题目,最终成就了一个名为:结构之法 算法之道的编程...
  • 结构化数据、半结构化数据和非结构化数据

    万次阅读 多人点赞 2020-08-20 19:04:49
    结构化数据、半结构化数据和非结构化数据结构化数据结构化的数据是指可以使用关系型数据库表示和存储,表现为二维形式的数据。一般特点是:数据以行为单位,一行数据表示一个实体的信息,每一行数据的属性是相同的。...
  • YOLO v3网络结构分析

    万次阅读 多人点赞 2020-10-10 21:39:12
    相信阅读了YOLO v3论文的小伙伴们会发现为什么这次的论文篇幅这么少?除去参考文献就四面?Excuse me?我是下了篇假文献吧。读完后感觉内容确实不多,而且总感觉写的不够细致,很多地方都比较模糊,可能是作者想让...
  • 为什么要学数据结构

    万次阅读 多人点赞 2019-11-19 13:54:58
    一、前言 在可视化化程序设计的今天,借助于...1) 能够熟练地选择和设计各种数据结构和算法 2) 至少要能够熟练地掌握一门程序设计语言 3) 熟知所涉及的相关应用领域的知识 其中,后两个条件比较容易实现,而第一个...
  • 一、顺序查找:顾名思义,就是从头开始一直找到结束,找到了就返回,否则继续找,找完了没找到就返回-1 普通版 static int SequenceFind(int[] arr,int value) { for (int i = 0; i < arr.Length-1;...
  • 小猪的数据结构辅助教程——1.数据结构与算法绪论标签(空格分隔): 数据结构本节学习路线图与学习要点学习要点: 1.了解数据结构的相关概念 2.了解算法的相关概念 3.熟悉时间复杂度的计算 4.了解空间复杂度...
  • 结构 非常得类似我们之前讲到过的树结构,但前者没有很多的从属关系,更多的是各个数据之间的相关联系。在数学的概念中,后者是前者的一种,不过在数据结构中我们还是认为两者有所区别,尽管如此,我们在学习图...
  • 数据结构与算法思维导图
  • 数据结构

    千次阅读 多人点赞 2018-10-06 18:16:15
    数据结构 数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或者多种特定关系的数据元素集合。通常情况下,精心选择的数据结构可以带来更高效的运行或者存储效率。数据结构往往同高效的检索算法...
  • 数据结构与算法书籍推荐

    万次阅读 多人点赞 2019-03-16 18:49:31
    学习数据结构与算法,还是很有必要看几本相关的书籍,但根据不同基础的人,合适看的书也不一样,因此,针对不同层次、不同语言的人,推荐几本市面上口碑不错的书。 1. 入门级 针对刚入门的同学,建议不要急着去看...
1 2 3 4 5 ... 20
收藏数 5,430,481
精华内容 2,172,192
关键字:

结构