数据结构预备知识

数据结构预备知识

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

指针的重要性

• 指针是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);
}