数据结构预备知识

数据结构预备知识

在进行数据结构讲解时，我们需要把一些基础知识进行复习和巩固，目的是为了方便数据结构的学习，主要涉及到的基础知识是指针、结构体、指针和数组的关系以及内存分配空间，接下来我们一起来简单的看看。

指针的重要性

  • 指针是C语言的灵魂
    • 定义：指针就是用来存储地址的，例如：int *p;p就是一个指针变量。
    • 地址：地址是内存单元的编号,从0开始的非负整数，范围：0-FFFFFFFFH

那么我们的CPU（中央处理器）和我们内存空间进行访问时的原理是什么？
原理：在CPU和内存中间存在地址线、控制线、数据线,地址线是CPU找到内存空间的地址，控制线主要用来控制数据的读和写的一个操作，比如0就是读，1就是写，数据线是CPU和内存空间进行数据的传递过程。

  • 指针是什么？
    • 指针就是地址，地址就是指针。
    • 指针变量是存放内存单元地址的变量。
    • 指针的本质是一个操作受限的非负整数。
  • 指针的分类分类：
    • 基本类型的指针
    • 指针和数组的关系
    • 构造数据类型指针

注意一点：变量并不一定连续分配，随机分配内存。

内存

  • 概念：内存是多字节组成的线性一维存储空间。
  • 单位：内存的基本划分单位是字节。每个字节含有8位，每一位存放1个0或1个1，内存和编号是一一对应的。
  • 软件在运行前需要向操作系统申请存储空间。在软件运行期间，该软件所占空间不再分配给其他软件。当软件运行完毕后，操作系统将回收该内存空间（操作系统并不清空该内存空间中遗留下来的数据）。

注意：

  • 指针变量也是变量，普通变量前不能加*，常亮和表达式前不能加&。
  • 局部变量只在本函数内部使用。

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

  • 实参为相关变量的地址；
  • 形参为以该变量的类型为类型的指针变量；
  • 在被调函数中通过 *形参变量名的形式 的形式就可以修改主函数。
#include<stdio.h>
int main(void)
{
    int *p; //p是个变量名字，int*表示该p变量只能存储int类型变量的地址
    int i=10;
    int j;

//  j=*p;
//  printf("%d\n",j);   //error,p未指定

//  char ch='A';
//  p=&ch;  //error，类型不一致   
    p=&i;   //p保存i的地址，p指向i；修改p的值不影响i的值，修改i的值不影响p的值；任何场合下，*p和i可以互换。*p等价于i。
    //p=10; //error
    j=*p;//等价于j=i;
    printf("i=%d,j=%d,*p=%d\n",i,j,*p);
    return 0;
}
例子二：
#include<stdio.h>
void fun(int * i)//不是定义了一个名字叫做*i的形参，而是定义了一个形参，该形参名字叫做i，它的类型是int*
{
    *i=100; 
}

int main(void)
{
    int i=9;
    fun(&i);    //局部变量只在本函数内部使用。
    printf("i=%d\n",i);
}

指针和数组之间的关系

数组名：一维数组名是个指针变量，它存放的是一维数组第一个元素的地址，它的值不能被改变，一维数组名指向的是数组的第一个元素。
结论：

  • a[3]等价于*(3+a); (a+3)等价于(3+a);

int a[5]={1,2,3,4,5};
Show_Aarry(a,5);//a等价于&a[0],&a[0]本身就是int*类型

void Show_Array(int * p,int len)
{
    int i;
    //P[2]=-1;//p[0]=*p ;  p[2]==*(p+2)==*(a+2)==a[2] ; p[i]就是主函数的a[i]
    for (i=0;i<lem;i++)
    printf(“%d\n”,p[i]);
}

注意：

  • 指针变量的运算

  • 指针变量不能相加，不能相乘，不能相除。

  • 如果两指针变量属于同一数组，则可以相减。

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

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

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

  • p++等价于p+1 p--等价于P-1

  • 所有的指针变量只占4个子节 用第一个字节的地址表示整个变量的地址

double *p;
double x=66.6;  //一个double占8个字节
p=&x;//x占8个字节，1个字节是8位，1个字节一个地址，p内只存放了一个地址，通常是字节的首地址
double arr[3]={1.1,2.2,3.3};
double *q;
q=&arr[0];
printf(“%p\n”,q);   //%p实际就是以十六进制输出
q=&arr[1];
q=printf(“%p\n”,q); //p,q相差8

注意：无论指针指向的变量占多少个字节，指针变量统一都只占4个字节

如何通过函数修改实参的值

  • 发送地址
  • 修改指针变量的值，只能修改地址
void fun(int **);
int main(void)
{
    int i=9;
    int *p=&i;//    *p;p=&i;
    printf(“%p\n”,p);
    f(&p);  
    printf(“%p\n”,p);
    return 0;
}
//void fun(int *q)
//{
//  q=(int *)0xffffffff;  //错误，不会改变p的值
//}
void fun(int ** q)
{
    *q=(int *)0xffffffff;//这里需要强转一下。 
}

结构体的使用概述

为什么会出现结构体：

  • 为了表示一些复杂的数据，而普通的基本类型变量无法满足要求
  • 结构体的定义：
    • 结构体是用户根据实际需要自己定义的复合数据类型
  • 如何使用结构体：
    struct Student st={1000,”zhagnsan”,20};
    struct Student*pst=&st;
    • 通过结构体变量名来实现
      st.sid
    • 通过指向结构体变量的指针来实现【重点】
      pst->sid
      pst所指向的结构体变量中的sid这个成员


#include<stdio.h>
#include <string.h>
//全局结构体定义
struct Student
{
    int sid；
    char name[200];
    int age;
};  //分号不能省
int main(void)
{
    struct Student st={1000,”zhagnsan”,20};
    printf(“%d,%s%d\n,”,st.sid,st.name,st.age);
    printf(“%d,%s%d\n,”,st);        //error
    st.sid=99;      //第一种
    //st.name=”lisi”;       //error 
    strcpy(st.name,”lisi”);
    st.age=22;  
    struct Student*pst;
    pst=&st;        //第二种
    pst->sid=99;    //pst->等价于(*pst).sid，而(*pst).sid等价于st.sid，所以pst->sid等价于st.sid
    return 0;
}

注意：

  • 结构体变量不能加减乘除，但可以相互赋值
  • 普通结构体变量和结构体指针变量作为函数传参的问题
#include<stdio.h>
struct Student
{
    int sid；
    char name[200];
    int age;
};  
void f(struct Student *pst);
void g(struct Student st);
void g2(struct Student *pst);
int main (void)
{
struct Student st;      //已经为st分配好了内存
f(&st);
//g(st);
g2(&st);
//  printf(“%d %s %d\n”,st.sid,st.name,st.age); //输出方法一
return 0;
}
void g(struct Student st)   //整体变量赋值//输出方法二，速度慢，耗空间，耗内存，不推荐
{
    printf(“%d %s %d\n”,st.sid,st.name,st.age); 
}
void g2(struct Student *pst)
{
printf(“%d %s %d\n”,pst->sid,pst->name,pst->age);   
}
void f(struct Student *pst)
{
(*pst).sid=99;
strcpy(pst->name,”zhagnsan”);
pst->age=22;
}

malloc()动态分配内存概述

  • 动态内存的分配和释放
#icclude<stdio.h>
#include<malloc.h>
int main(void)
{
    int a[5]={1,2,3,4,5};   //静态数组

    int len;
    printf(“请输入你需要分配的数组长度：len=”);
    scanf(“%d”,&len);
    int *pArr=(int *)malloc(sizeof(int)*len);   //(int *)为强制转换，强制使pArr指向前四个字节。可以将pArr当做数组名来操作
    //*pArr=4;//类似于a[0]=4;
//  pArr[1]=10;//类似于a[1]=10;
//  printf(“%d %d\n”,*pArr,pArr[1]);
//我们可以把pArr当做一个普通数组来使用
    for (int i=0;i<len;++i)
        scanf(“%d”,&pArr);
    for (i=0;i<len;++i)
        printf(“%d\n”,*(pArr+i));

    free(pArr); //把pArr所代表的的动态分配的20个字节的内存释放
    return 0;
}
  • 跨函数使用内存讲解及其示例
#include <stdio.h>
int f();
int main(void)
{
    int i=10;
    i=f();
    printf(“i=%d\n”,i);
    for(i=0;i<2000;++i)
        f();
    return 0;
}
int f()
{
    int j=20;
    return j;
}

#include <stdio.h>
 int main ()
{
    int *p;
fun(&p);
...
}
int fun (int **q)
{
    int s;  //s为局部变量。调用完毕后s就没有了，最终p没有指向一个合法的整型单元
    *q=&s;
}

#include <stdio.h>
int main()
{
    int *p;
    fun(&p);
    ...
}
int fun(int **q)
{
    *q=(int *)malloc(4);    //返回4个字节，只取第1个字节地址赋给*q，*q==p。执行完后，因为没有free()，内存没有释放。如果没有free()，整个程序彻底终止时才能释放
}

Java程序内部类定义方法
A aa=new A();
A pa=(A)malloc(sizeof(A));

#include<stdio.h>
#include<malloc.h>
struct Student
{
    int sid;
    int age;
}
struct Student *  CreatStudent(void);
void ShowStudent(struct Student *);
int main(void)
{
    struct Student *ps;
    ps=CreatStudent();
    ShowStudent(ps);
    return 0;
}
struct Student *  CreatStudent(void)
{
    struct Student *P=(struct Student *)malloc(sizeof(struct Student));
    p->sid=99;
    p->age=88;
return p;
}
void ShowStudent(struct Student *pst)
{
    printf(“%d %d\n”,pst->sid,pst->age);
}
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容

  • 数据结构预备知识
    一、数据结构概述 1.什么是数据结构？ 我们如何把现实中大量而复杂的问题以特定的数据类型和特定的存储结构保存到主存...
    卖报的女孩阅读 348评论 0赞 0
  • C语言指针
    指针是Ｃ语言中广泛使用的一种数据类型。 运用指针编程是Ｃ语言最主要的风格之一。利用指针变量可以表示各种数据结构； ...
    朱森阅读 3,530评论 3赞 44
  • C框架概览及基础知识总结
    一、框架 1、Mac系统及常用工具、进制;C数据类型、常量变量、运算符、表达式、格式化输入输出 2、关系运算符、逻...
    师景福阅读 765评论 0赞 2
  • 面试题
    Swift1> Swift和OC的区别1.1> Swift没有地址/指针的概念1.2> 泛型1.3> 类型严谨 对...
    cosWriter阅读 11,167评论 1赞 32
  • c语言经典面试题目知识点详解（经典，非常详细）
    前段时间有同学评论说，指针方面的问题不太懂，今天小编就给大家带来非常详细的c语言之指针学习资料。 前言:复杂类型说...
    诸葛青云999阅读 31,080评论 0赞 16