数据结构入门
2019-11-18杂谈搜奇网23°c
A+ A-定义：我们怎样把现实中大批而庞杂的题目以特定的数据范例和特定的存储构造保留到主内存器中(内存)，以及在此基础上为完成某个功用(比方查找某个元素，删除某个元素，对一切元素举行排序)而实行的响应操纵，这个响应的操纵也叫算法
数据构造 = 个别 + 个别的关联
算法 = 对存储构造的操纵
算法：解题的要领和步骤
权衡算法的规范：
- 时刻庞杂度：也许顺序实行要实行的次数，而非实行的时刻
- 空间庞杂度：算法实行过程当中也许所占用的最大内存
- 难易水平
- 建壮性
一、指针
地点：内存单位的编号，从0最先的非负整数
指针：指针就是地点，指针变量是寄存内存单位地点的变量，指针的实质是一个操纵受限的非负整数
分类：
- 基础范例指针(重点看解释)
#include <stdio.h>
int main(void)
{
// p是一个变量名字，int * 示意p变量只能存储int范例变量的地点
int *p;
int i = 10;
int j;
p = &i;
// p保留了i的地点，p指向i
// 修正p的值不影响i的值，修正i的值不影响p的值
// *p即是i
j = *p; // 等价于 j = i
printf("%d\n", *p);
printf("%d\n", j);
return 0;
}- 指针与函数
#include <stdio.h>
// 不是定义了一个名字叫做 *p的形参，而是定义了一个形参，该形参的名字p，它的范例是int *
void f(int *p)
{
*p = 100;
}
int main(void)
{
int i = 9;
int *p = &i;
f(p);
printf("%d\n", i );
return 0;
}- 指针与数组(重点看解释)
#include <stdio.h>
void show_array(int *p , int len)
{
// p[0] == *p
p[0] = -1;
// p[i]就是主函数a[i]
int i = 0;
for (i = 0; i < len; i++)
{
printf("%d\n",p[i] );
}
}
int main(void)
{
/*
一唯数组名是个指针常量，它寄存的是一唯数组第一个元素的地点，
它的值不能转变，一唯数组名指向的是数组的第一个元素，也就是
a执向a[0]
下标和指针的关联
a[i] <==> *(a+i)
*/
int a[5] = {1,2.3,4,5,};
// a等价于&a[0] , &a[0]自身就是int * 范例
show_array(a,5);
printf("%d\n", a[0]);
return 0;
}一切的指针变量只占4个字节，用第一个字节的地点示意全部变量的地点
#include <stdio.h>
int main(void)
{
double *p;
double x = 99.9;
// x占8个字节，1字节是8位，1字节一个地点 ，p内里寄存了首地点
p = &x;
double arr[3] = {1.1,2.2,3.3,};
double *q;
double *q1;
q = &arr[0];
printf("%p\n", q); // %p现实就是以十六进制输出
q1 = &arr[1];
printf("%p\n", q1); // 相差了8个字节
return 0;
}二、怎样经由过程函数修正实参的值
#include <stdio.h>
void f(int **q);
int main(int argc, char const *argv[])
{
int i = 9;
int *p = &i; // int *p , p = &i;
printf("%p\n",p );
f(&p);
printf("%p\n",p );
return 0;
}
void f(int **q)
{
*q = (int*)0XFFFFF;
}如许写是不安全的，然则这个理是如许的，不是修正指针的很简单，
#include <stdio.h>
void f(int *p);
int main(void)
{
int i =10;
f(&i);
printf("%d\n", i);
return 0;
}
void f(int *p)
{
*p = 20;
}三、构造体
为何会涌现构造体
为了示意一些庞杂的数据，而一般的基础范例变量没法满足要求
什么叫构造体
构造体是用户依据现实须要，本身定义的复合数据范例
怎样运用构造体
#include <stdio.h>
#include <string.h>
struct Student
{
int sid;
char name[200];
int age;
}; // 分号不能省
int main(void)
{
// 第一种体式格局，然则如许很贫苦
struct Student st = {10 , "张三" ,20};
printf("%d %s %d\n", st.sid , st.name , st.age);
// 字符串不能直接赋值，必需挪用响应的函数
st.sid = 20;
strcpy(st.name , "李四");
st.age = 21;
printf("%d %s %d\n", st.sid , st.name , st.age);
// 第二种体式格局，这个最经常使用
struct Student *pst;
pst = &st;
pst -> sid = 99; // pst->sid 等价于 (*pst).sid 等价于 st.sid
return 0;
}pst -> sid : pst所指向的构造体中变量中的sid这个成员
注意事项
- 构造体变量不能加减乘除，然则能够互相赋值
- 一般构造体变量和构造体指针变量作为函数传参的题目
#include <stdio.h>
#include <string.h>
struct Student
{
int sid;
char name[200];
int age;
};
void f(struct Student * pst);
void g(struct Student st);
void g1(struct Student * pst);
int main(void)
{
struct Student st;
f(&st);
//printf("%d %s %d\n", st.sid , st.name , st.age);
//g(st);
g1(&st);
return 0;
}
// 用于数据的输入
void f(struct Student * pst)
{
(*pst).sid = 99;
strcpy(pst -> name , "张三");
pst -> age = 30;
}
// 用于数据的输出,然则这类要领费时刻，不引荐
void g(struct Student st)
{
printf("%d %s %d\n", st.sid , st.name , st.age);
}
// 用于数据的输出，引荐运用这类体式格局
void g1(struct Student * pst)
{
printf("%d %s %d\n", pst->sid , pst->name , pst->age);
}四、动态内存的分派和开释
重点看代码和解释
#include <stdio.h>
#include <stdlib.h>
int main(void)
{
int a[5] = {3,9,5,6,2};
int len;
printf("请输入你须要的分派数组的长度：\n");
scanf("%d" , &len);
int * PArr = (int *)malloc(sizeof(int)*len);
// *PArr = 3; //类似于a[0] = 3
// PArr[1] = 9; //类似于a[1] = 9
// printf("%d %d\n", *PArr , PArr[1]);
// 固然了，这个时刻我们能够把pArr看成一个一般的数组来运用
int i;
for (i = 0; i < len; ++i)
{
scanf("%d" , &PArr[i]);
}
int j;
for (j = 0; j < len; ++j)
{
printf("%d\n", PArr[j]);
}
free(PArr); // 把Parr所代表的动态分派的20个字节内存开释
return 0;
}五、跨函数运用内存
重点看代码和解释
#include <stdio.h>
#include <stdlib.h>
struct Student
{
int sid;
int age;
};
struct Student * CreateStudent(void);
void ShowStudent(struct Student * ps);
int main(void)
{
struct Student * ps;
ps = CreateStudent();
ShowStudent(ps);
return 0;
}
struct Student * CreateStudent(void)
{
// 拓荒一个新空间，运用malloc函数，范例是我们想要的范例
struct Student * p = (struct Student * )malloc(sizeof(struct Student));
p->sid = 88;
p->age = 99;
return p;
}
void ShowStudent(struct Student * pst)
{
printf("%d %d\n", pst->sid , pst->age);
}
未定义标签