数据结构的定义和简介

1.概述

数据结构定义:

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

数据结构=元素+元素的关系算法=对数据结构的操作

算法:

算法就是：解决问题的方法和步骤

衡量算法有如下标准:

时间复杂度程序要执行的次数，并非执行时间空间复杂度算法执行过程中大概要占用的最大内存难易程度(可读性)健壮性

2.数据结构的特点和地位

地位:

数据结构处于软件中核心的地位。

如计算机内存中栈和堆的区别，不懂数据结构的人可能会认为内存就是分两大部分，一块叫栈，一块叫堆，显然这是非常肤浅且不正确的结论。

实际上如果一块内存是以压栈出栈的方式分配的内存，那么这块内存就叫栈内存，如果是以堆排序的方式分配的内存，那么这块内存就叫堆内存，其最根本的区别还是其内存分配算法的不同。

例如，函数的调用方式也是通过压栈出栈的方式来调用的，或者操作系统中多线程操作有队列的概念，队列用于保证多线程的操作顺序，这也是数据结构里面的内容、或者计算机编译原理里面有语法树的概念，这实际上就是数据结构里面的树，比如软件工程、数据库之类都有数据结构的影子。

特点:

数据结构修炼的是内功，并不能直接立竿见影的可以解决现实问题，但是有了这门内功会在其他方面的学习中对你大有益处。

预备知识（C语言）学习数据结构应该具备如下知识：指针结构体动态内存的分配和释放跨函数使用内存本小节主要介绍学习数据结构应该有的基础，并对相关知识稍作讲解。

指针

指针是C语言的灵魂，重要性不需多言。

指针定义

　　地址是内存单元的编号 　　其编号是从0开始的非负整数 　　范围：0–0xFFFFFFFF(-1)注：此指x86平台，x64平台下最大内存地址为(-1)

指针： 　　指针就是地址，地址就是指针。 　　指针变量是存放内存单元地址的变量,它内部保存的值是对应的地址,地址就是内存单元的编号(如内存地址值：0xffc0)。 　　指针的本质是一个操作受限的非负整数 　　在计算机系统中，CPU可以直接操作内存，关于CPU对内存的操作与控制原理可以简单理解如下图

地址线：确定操作哪个地址单元控制线：控制该数据单元的读写属性数据线：传输CPU和内存之间的数据

指针的分类

基本类型的指针

inti=10;//定义一个整形变量i初始值10

int*p=i;//定义一个整形的指针变量p,变量p指向i的地址

int*p;//这两行等价于上面一行p=i;

p存放了i的地址，我们就可以说“p指向了i”，但p和i是两个不同的变量，修改一方不会影响另一个的值。*p等价于i，i等价于*p;两者是一块内存空间，里面的值一变具变。

指针和函数

//修改外部实参的值voidfunc(int*p){*p=;//函数内修改外部变量的值}

//修改外部实参的值，二级指针的值voidfunc2(int**p){*p=;//函数内修改外部变量的值，这里实际修改的是指针的内部的地址，这里直接自己修改并不严谨也不安全，只是为了表达意思}

intmain(void){//修改外部实参inti=10;func(i);printf(“i=%d”,i);

//修改外部二级指针int*p=i;//等价于int*p;p=i;func(p);printf(“i=%d”,i);

return0;}

//通过函数调用，改变函数外部变量（实参）的值

指针和数组

和

inta[5]={1,2,3,4,5};

a[3]==*(a+3)//等价于a[3]==*(3+a)==3[a];//3[a]这种写法只是不常用，从原理上来说是正确的a等价于a[0];//a是数组中第一个元素，每个元素占用内存单位长度相同，//a[i]中的i实际代表的是单位长度的倍数

数组名:

　　一维数组名是个指针常量(它的值不可变) 　　它存放的是该一维数组的第一个元素的地址(一维数组名指向其第一个元素) 　　下标和指针的关系: 　　(1)、a[i]等价于*(a+i) 　　(2)、假设指针变量的名字为p, 　　则p+i的值为p+i*(p所指向的变量所占字节数) 　　(3)、每个下标表示的是第i+1个元素，根据元素类型分配的字节长度不同(int类型4个字节)，每个字节都有对应的内存地址编号，指针变量p保存的是该元素首字节的地址。

指针变量的运算:　

　　指针变量不能相加、相乘、相除 　　如果两指针变量属于同一数组，则可以相减 　　指针变量可以加减一个整数，前提是最终结果不能超过指针最大可访问范围 　　 　　

//指针变量的运算p+i的值是p+i*(所指向的变量所占字节数)p-i的值是p-i*(所指向的变量所占字节数)p++等价于p+1p–等价于p-1

//下面是一个通过函数修改数组内部元素voidmy_Array(int*a,intlength){for(inti=0;ilength;i++){*a[i]++;//给每个元素加1}}

intmain(void){

inta[5]={1,2,3,4,5};my_Array(a,5);//调用}

结构体

为什么会出现结构体?

为了表示一些复杂的数据，而普通的基本数据无法满足要求.

什么叫结构体

结构体是用户根据实际需要，自己定义的复合数据类型

//如学生类型structStudent{intage;char*name;//name不同，赋值方法不同charname2[];//这个只能strcpy(s.name2,“zhangwangdsd”);字符串拷贝doubleheight;};

如何使用结构体

总结起来有两种结构体的使用方式：直接使用通过指针使用structStudentss={12,”xiaoyou”,1.73,”xiaozhang”};structStudent*pst=ss;

ss.name;这里直接操作结构体本身pst-name;这里通过指针地址操作，更加节省空间

structStudent{//自定义结构体intage;char*name;doubleheight;charname2[];};

intmain(void){

structStudents={12,”xiaoyou”,1.73,”xiaozhang”};

//直接使用printf(”age=%d\nname=%s\nheight=%.2f\n”,s.age,s.name,s.height);

s.age=21;s.name=“xiaozhu”;strcpy(s.name2,“zhangwangdsd”);//字符串拷贝s.height=1.70;

printf(”age=%d\nname=%s\nheight=%.2f\n%s\n”,s.age,s.name,s.height,s.name2);

//以指针的方式使用structStudent*pst=ss;pst-name=“mynewname”;

printf(”name=%s\n”,pst-name);printf(”name=%s\n”,(*pst)-name);

//pst-name等价于(*pst).name,//而(*pst).name又等价于ss.name//所以pst-name等价于ss.name

return0;}

注意事项

结构体变量的类型为：structStudent结构体变量不能加减乘除，但是能够相互赋值普通结构体变量和结构体指针变量作为函数传参的问题

typedefstructStudent{//结构体定义intage;char*name;charname2[];doubleheight;}myStudent;

//直接传递整个结构体数据，耗时浪费内存空间voidfunc(structStudentst);//直接传递只占用4byte的指针，省时效率也高推荐用法voidfunc2(structStudent*pst);

intmain(void){

myStudentss={12,"xiaoyou",1.73};func(ss);func2(ss);return0;}

voidfunc(structStudentst){

printf("age=%d\nname=%s",st.age,st.name);}

voidfunc2(structStudent*pst){

printf("age=%d\nname=%s",(*pst).age,(*pst).name);printf("age=%d\nname=%s",pst-age,pst-name);}

动态内存分配和释放

平时直接创建数组的写法都是静态创建，创建完毕之后在整个程序的运行过程中，会固定占用对应的内存，不仅会造成内存空间浪费，还无法动态添加元素，所以局限性很大，而程序中我们为了避免这种情况，应该使用动态的方式创建和销毁数组。

//静态创建数组inta[5]={1,2,3,4,5};

动态构造一维数组

动态构造一个int型的一维数组。

intp=(int)malloc(intlength);

void*malloc(size_t__size)函数,只有一个int类型的形参，表示要求系统分配的字节数malloc函数的功能是请求系统length个字节的内存空间，如果请求完成则返回的是第一个字节的地址，如果请求不成功，则返回NULLmalloc函数能且只能返回第一个字节的地址，所以我们需要把没有实际意义的第一个字节地址（干地址）转化为一个有实际意义的地址，所以malloc前面必须加(数据类型*)，表示把这个无意义的地址转化为对应类型的地址

实例：

intp=(int)malloc(50);表示将系统分配的50个字节的第一个字节的地址转化为int类型的地址，准确的说是转化为4个一组的地址的首地址，这样p就指向了第一个四个字节···p+i就指向了第i+1个四个字节，p[0],p[i]也就分别是第一个，第i+1个元素。

double*p=(double*)malloc(80);表示将系统分配的80个字节的第一个字节的地址转化为double类型的地址，准确的说是转化为8个一组的地址的首地址，这样p就指向了第一个八个字节···p+i就指向了第i+1个八个字节，p[0],p[i]也就分别是第一个，第i+1个元素。free(p);释放p所指向的内存，而不是释放p本身所占用的内存

代码示例如下：

voidtest2(void){intlen;printf(“请输入你要动态创建的数组长度:”);scanf(“%d”,len);

int*pArr=(int*)malloc(len);//动态创建数组*pArr=4;//相当于a[0]=4;这里pArr就等于数组首地址，等于数组名pArr[2]=5;//相当于a[2]=5;

printf("pArr[0]=%d\npArr[2]=%d\n",pArr[0],pArr[2]);

free(pArr);//使用完毕，释放对应的数组空间}

跨函数使用内存

在函数内部分配的局部变量，在函数调用完成之后就会被系统回收，其内存也会消失。但是程序中常常需要定义一块内存，当我们用完之后再会回收。如OC语言中对象。所以需要保存住分配的内存，应该用动态分配内存，当用完之后再手动释放。这也是C语言的一个不足之处：内存需要我们手动创建和手动释放，这也是OC语言在开发iOS程序时候，我们所讲的MRC。

下面是一个跨函数使用内存的例子：

//这个例子已经非常有面向对象的味道了

typedefstructStudent{//自定义student结构体intage;char*name;}myStudent;

myStudent*createStudent(void);//创建studentvoidshowStudent(myStudent*);//输出student

intmain(void){

myStudent*p=createStudent();//创建studentshowStudent(p);//输出student

return0;}

myStudent*createStudent(void){myStudentp=(myStudent)malloc(sizeof(myStudent));p-age=20;p-name=“xiaoyou”;returnp;}

voidshowStudent(myStudent*p){printf(“student.age=%d\nstudent.name=%s\n”,p-age,p-name);}

小结

本文主要讲解了数据结构的定义和简介。回顾了学习数据结构应该具备的一些C语言的基础知识，如指针、结构体、和内存等。

版权归原作者所有（如有侵权请联系删除）

赞赏

长按向我转账

受苹果公司新规定影响，iOS版的赞赏功能被关闭，可通过转账支持。

转载请注明：http://www.92nongye.com/hxjs/204620187.html