一、数据结构概述

       1.定义:

    我们如何把现实中大量而复杂的问题,以特定的数据类型和特定的存储结构保存到主存储器(内存)中,以及在此基础上为实现某个功能(比如查找某个元素,删除某个元素,对所有元素进行排序)而执行的相应操作。这个相应的操作也叫算法。

         数据结构 =个体的存储 + 个体的关系存储

SRE实战 互联网时代守护先锋,助力企业售后服务体系运筹帷幄!一键直达领取阿里云限量特价优惠。

         算法(狭义) = 对存储数据的操作

  2.算法:解题的方法和步骤

          2.1.衡量算法好坏的标准:

      2.1.1.时间复杂度:程序大概执行的次数,而非执行的时间

      2.1.2.空间复杂度:算法执行过程中大概所占用的最大内存

      2.1.3.难易程度(编算法最重要的)

      2.1.4.健壮性

       3.数据结构的地位:数据结构是软件中最核心的课程

         程序 = 数据的存储 + 数据的操作 + 可以被计算机执行的语言

 二、预备知识

  1.指针

    1.1.指针的重要性:指针是c语言的灵魂

    1.2.有关指针概念的定义:

      指针就是地址 地址就是指针,指针和地址是一个概念

      指针变量 是存放内存单元地址的变量,所谓内存单元地址 即为内存单元编号,两者是一个概念

      指针的本质 是一个操作受限的非负整数/从0开始的非负整数          

        范围:0 -- FFFFFFFF【4G-1】

        1.2.1.关于内存和cpu的关系:

          CPU能够直接访问的只有内存,内存是CPU唯一能够访问的大容量储存器,内存的基本划分单位是字节,每个字节有8位,每一位存放1个0或1个1,CPU和内存打交道的方式:地址线、控制线、数据线

          内存可以看做很多小格子,如果是32位,编号从0到4G-1;

          1.2.1.1.地址线 可以确定对哪一个单元编号进行操作,地址没有编号,地址就是编号;重点是地址线,因为地址线是32位的,所以最大只能0到32-1;内存的编号不能重复,但是内容可以重复;

            定义:地址就是内存单元的编号,单元编号是死的,不能改变,但是里面的内容是可以改变的;当一个程序运行完成,内存会被回收(回收和销毁不是一个概念,操作系统会分配内存给程序,程序告诉操作系统,操作系统会把内存中的空间释放出来,原始的数据(遗留的垃圾数字)不会销毁,只是不能使用而已(c存在这个问题,但是java不会,java会自动释放),其中的变量会被清空,但是内存、单元编号依然存在;

          1.2.1.2.控制线 用来确定是:读、写、只读、只写;

          1.2.1.3.数据线 可以进行数据传输

  2.指针的分类:

    2.1.基本类型的指针

      2.1.1基本概念

数据结构笔记1(c++)_指针 算法 第1张
 1 #include <stdio.h>
 2 
 3 int main(void)
 4 {
 5     int * p;    //该p变量只能存储int类型的地址,不能存放一个整数
 6     int i = 10;
 7     int j;
 8 
 9     // char ch = 'A';
10     // p = &ch;    //p只能存放int类型,不能存放char类型的'A',类型不一致,会报错
11     // p = 10; //error p是个变量名字,表示只能存放int型变量地址,10是个整数,不是个地址;
12     // *p = i;        //可以存放i,一定要如下理解才可以
13                 // 1)将i的地址发送给p,意味着p是指向i的;
14                 // 2)修改p、i的值,不会影响另外一个值,相互不会影响;
15                 // 3)*p即为i变量本身,i跟*p可以在任何地方进行互换,i的值改了,*p的值也改了,i原来等于100,*p也就等于100,但是p不是i,i不是p;
16     p = &i;     // 如果这一行被省略掉,会报错;
17                 // 第一步int * p;只是说p可以保存整型变量地址了,但p中并没有保存真正的整型变量地址,所以我们不知道*p真正指向的是谁了
18                 // 虽然p中没有保存真正有效整型数字地址,但是p中还是可以有垃圾数字的,垃圾数字也有可能是某一个变量的地址,所以*p最终指向的是一个不确定的单元,*p不知道指向了哪里,造成了混乱,c语言中不允许这样去写
19                 // 不能将一个不确定单元的值,赋给另外一个变量,这样不合适,所以会报错
20     *p = i;        // 等价于i=i,不会出错,但是没有什么实际意义
21     j = *p;    // 等价于j = i; 若注释掉这一行,则j没有赋值,c会自动赋予一个垃圾数字-2341343;
22     printf("i =  %d, j= %d, *p = %d\n",i, j, *p);
23 
24     //printf();
25     return 0;
26 }
View Code

 

小结:

    1、如果一个指针变量(假定为p)存放了某个普通变量,那我们就可以说:“p指向了i”,但p与i是两个变量;修改p的值不影响i的值,修改i的值不影响p的值

    2、*p等价于I 或者说*p可以与i在任何地方互换

    3、如果一个指针变量指向了某个普通变量,则*指针变量就完全等价于该普通变量

注意:

       指针变量也是变量,只不过它存放的不能是内存单元的内容,只能存放内存单元的地址

       普通变量前不能加*

       常量和表达式前不能加&

如何通过被调函数,修改主调函数中普通变量的值

1.实参为相关变量的地址:&i

2.形参为以该变量的类型为类型的指针变量:*p

3.在被调用函数中通过*形参变量名的方式修改主函数:*p=100


    2.2.指针和数组的关系(一维数组)

数据结构笔记1(c++)_指针 算法 第3张
//Array_point_1.cpp
# include <stdio.h>

int main(void)
{
    int a[5] = {1,2,3,4,5};    // 1)a中存放的不是1~5这5个数字,这5个数字是在a0到a4中存放的。
                            // 2)数组名a存放的是数组的第一个元素的地址
                            // 3)它的值不能被改变
                            // 4)字母a即为一维数组名,指向的是数组的第一个元素,即a指向的是a0
                            // 5)a[3]和*(a+3)的关系:a[i] <<==>> *(a+i) 即数组a[i]的写法,等价于*(a+i)    a[3] == *(3+a), 3[a] == *(a+3), 因a指向第一个元素a[0],故a+3指向第四个元素a[3],则*(a+3)==a[3];
                            // 理论上指针比下标的速度快,但是可以忽略不计
    //a[3] == *(3+a);
    
    printf("%p\n", a+1);
    printf("%p\n", a+2);
    printf("%p\n", a+3);

//[Out]:
//0019FF30
//0019FF34
//0019FF38
    
    printf("%d\n", *a+3);  // *a+3等价于 a[0]+3 = 4
//[Out]:
// 4
    return 0;
}
View Code

      2.2.1.数组名:a[*]中的a

        一维数组名 是个指针常量,它存放的是一维数组第一个元素的地址a[0],它的值不能被改变

        一维数组名指向的是 数组的第一个元素

      2.2.2.下标和指针的关系:a[i]等价于*(a+i)

        a[i] <<==>> *(a+i)

        假设指针变量的名字为p,则p+i的值是p+i*(p所指向的变量所占的字节数)

      2.2.3.指针变量的运算:

        指针变量不能相加,不能相乘, 不能相除,如果两指针变量属于同一数组,则可以相减

        指针变量可以加减一整数,前提是最终结果不能超过指针

          p+i 的值是p+i*(p所指向的变量所占的字节数)  

          p- i 的值是p-i*(p所指向的变量所占的字节数)

          p++ <==> p+1  // 如果是int型,就是4字节,double型,就是8字节,但是都是指向的后一个元素

          p-- <==> p-1

      2.2.4.举例:

        如何通过被调函数修改主调函数中一维数组的内容[如何界定]

          两个参数:1)存放数组首元素的指针变量;2)存放数组元素长度的整型变量

数据结构笔记1(c++)_指针 算法 第5张
//Array_point_2.cpp
# include <stdio.h>

void Show_Array(int * p, int len)    // a发送给了*p
{
//    p[0] = -1;    //p[0] == *p
//    p[2] = -1;    //p[2] == *(p+2) == *(a+2)  p[i]就是主函数的a[i]
    int i = 0;

    for (i=0; i<len; ++i)
        printf("%d\n", p[i]);
}

int main(void)
{
    int a[5] = {1,2,3,4,5};

    Show_Array(a, 5);    // a等价于&a[0], &a[0]本身就是i
                        // 通过写一个数组名,数组长度,就可以确定一个数组, 
                        // 要想通过一个函数,访问另一个函数中的一个数组,只需要知道这个数组的首地址(数组第一个元素地址)和长度,
                        // 在另一个函数中就可以任意访问、修改主函数a[5]的值
//[Out]:1 2 3 4 5    

//    printf("%d\n", a[2]);
//[Out]: -1
//    printf("%d\n", a[0]);
//[Out]: -1
    
    return 0;

}
View Code

 

扫码关注我们
微信号:SRE实战
拒绝背锅 运筹帷幄