数据结构

数据结构

📅 2026-04-09 ✏️ 2026-04-16 📝 427 字 ⏱️ 3 分钟
笔记
  • 定义：
    • 在一些特定的、特殊的需求场景下，以往所学的数据类型无法基于需求合理地组织数据，此时就需要自己设计一套新的数据组织形式来解决问题，也就是数据结构
    • 数据结构是一种存储、组织数据的方式，旨在便于访问和修改。没有一种单一的数据结构对所有用途均有效，所以需要知道几种数据结构的优势和局限

数据结构基本认知及相关知识点复习

字符串

  • 纯C语言中没有字符串这样的数据类型 - 需要定义数组，且数组末尾有\0 - C #include<stdio.h> #include<string.h> int main(){ char str1[11]; strcpy(str1,"HelloWorld"); }

数组

  • 使用取地址符&获取数组的地址时，返回的是数组第0个元素的内存地址
int main(){
	int a[] = {14,47,89,42,35};
	printf("%p\n",&a);
	printf("%p\n",&a[0]);
}
//000000063c3ffe30
//000000063c3ffe30
  • sizeof——返回在内存中占多少字节——用于计算数组长度，避免数组越界
int main(){
	int a = 5;
	printf("%zu\n",sizeof(a));
	printf("%zu\n",sizeof(int));
	printf("%zu\n",sizeof(3.14));
	return 0;
}

int main(){
	int a[] = {16,47,89,42,38};
	printf("%zu\n",sizeof(a));
	printf("%zu\n",sizeof(a[0]));
	int len = sizeof(a) / sizeof(a[0]);
	printf("数组长度为%d\n",len);
}

指针

  • 定义：用来存放内存地址的变量
  • 指针的声明
int a;  //声明一个整型变量
int *p; //声明一个指针变量，该指针指向一个int类型值的内存地址
a=5;
p = &a;

int main(){
    int a = 5;
    int *p = &a;
    printf("a的地址为：%p,a的值为:%d\n",&a,a);
    printf("p的地址为：%p,p的值为·:%p\n",&p,p);
}
  • 间接引用操作符*，返回指针变量的指向地址的值，通常把这个操作叫做“解引用指针”——获取值
int a = 5;
int *p = &a;
printf("%d\n",*p);
*p = 100;
printf("%d\n",a);
//5
//100

指针、结构体、动态内存分配、算法时间复杂度

指针

指针与函数

  • 写一个函数，传入两个int参数并交换这两个参数的值
#include<stdio.h>
void swap(int *a,int *b)
{
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
    printf("%d %d",*a,*b);
}
int main()
{
    int a = 5;
    int b = 10;
    swap(&a,&b);
    return 0;
}

指针与数组

  • 在C语言中，指针与数组关系十分密切，通过数组下标能完成的操作都可以用指针完成
#include<stdio.h>

int main()
{
    int a[] = {15,20,32,48,56};
    int* p;
    p=a;
    for (int i=0;i<sizeof(a)/sizeof(a[0]);i++)
    {
        printf("%d\n",a[i]);
    }
    for (int i=0;i<sizeof(a)/sizeof(a[0]);i++)
    {
        printf("%d\n",*(p+i));
    }
    return 0;
}
  • 给指针加上一个整数，实际上加的是这个整数和指针数据类型对应字节数的乘积

结构体

结构体的声明

  • 结构体是一个或多个变量的集合，这些变量可以是不同的类型
\\声明语法
struct point{
	int x;
	int y;
}
\\struct 结构体名{
\\    数据类型 变量名;
\\    数据类型 变量名;
\\}

\\结构体的初始化与调用
struct point p;
\\struct 结构体名 变量名

p.x = 10;
p.y = 15;
\\变量名.结构体内部变量名 = 值

#include<stdio.h>

struct point
{
    int x;
    int y;
};

int main()
{
    struct point p;
    p.x = 10;
    p.y = 15;
    printf("%d\n",p.x);
    printf("%d\n",p.y);
    return 0;
}
  • 结构体实例——创建一个point
    • 编写一个函数，传入两个int参数，在函数创建一个结构体point类型的变量，将传入的两个参数分别赋值给该结构体变量x和y，最后将该结构体变量返回
#include<stdio.h>

struct point
{
    int x;
    int y;
};
struct point createPoint(int x,int y)
{
    struct point temp;
    temp.x = x;
    temp.y = y;
    return temp;
}
int main()
{
    struct point p;
    p = createPoint(5,10);
    printf("%d,%d",p.x,p.y);
    return 0;
}

一般是用指针来传递结构体的地址

结构体与指针

  • 一些场景中，如果传递给函数的结构体很大，使用指针方式的效率通常更高
  • pp指向一个point结构体
struct point *pp;
  • 为pp所指向的结构体中的属性赋值
(*pp).x = 10;
(*pp).y = 5;

\\更简便的方式
pp -> x = 10;
pp -> y = 5;

#include<stdio.h>

struct point
{
    int x;
    int y;
};
int main()
{
    struct point p;
    p.x = 5;
    p.y = 10;
    struct point *pp;
    pp = &p;

    (*pp).x = 10;
    (*pp).y = 5;
    printf("x=%d y=%d\n",p.x,p.y);
    return 0;
}

类型定义

typedef int zx
//typedef 数据类型 别名

#include<stdio.h>

typedef int myType1;
typedef char myType2;

int main()
{
    myType1 a = 5;
    myType2 b = 'o';
    printf("%d\n",a);
    printf("%c\n",b);
    return 0;
}

typeof struct{
	int x;
	int y;
}po;
//typeof struct{
	数据类型 变量名;
	数据类型 变量名;
}别名;

#include<stdio.h>

typedef struct
{
    int x;
    int y;
}po;

int main()
{
    po p;
    p.x = 100;
    p.y = 200;
    printf("%d %d\n",p.x,p.y);
}

内存分类

  • C程序编译后，会以三种形式使用内存：
    • 静态/全局内存
      • 静态声明的变量和全局变量使用这部分内存，这些变量在程序开始运行时分配，直到程序终才消失
    • **自动内存（栈内存）
      • 函数内部声明的变量使用这部分内存，在函数被调用时才创建
    • **动态内存（堆内存）
      • 根据需求编写代码动态分配内存，可以编写代码释放，内存中的内容直到释放才消失

算法分析

算法 + 数据结构 = 程序 算法要满足的5个重要特性——有穷性、确定性、可行性、输入、输出 评价算法优劣的基本标准——正确性、可读性、健壮性、高效性

时间复杂度

也称渐进时间复杂度，T(n) = O(f(n))，随着问题规模n的增大，算法执行时间和增长率和f(n)增长率成正比
程序运行的总时间与执行每条语句的耗时 + 每条语句的执行频率有关

标签： 笔记
分享： Twitter Facebook