数据结构与算法-算法

Java工程师知识树

---

算法

算法是用于解决特定问题的明确定义的步骤的过程。

算法是有限的逻辑或指令集，它是为了完成某个预定义的任务而编写的。 它不是完整的程序或代码，它只是问题的解决方案(逻辑)，可以使用流程图或伪代码表示为非正式描述。

主要的算法类别：

• 排序：为按特定顺序排序项目而开发的算法。
• 搜索：为搜索数据结构内的数据项而开发的算法。
• 删除：为从数据结构中删除现有元素而开发的算法。
• 插入：为在数据结构中插入项目而开发的算法。
• 更新：为更新数据结构中的现有元素而开发的算法。

算法的性能是基于以下属性来衡量的：

• 时间复杂度：它是表示程序运行到完成所需时间的一种方式。
• 空间复杂度：它是算法在执行过程中所需的内存空间量。 在有限的内存可用和多用户系统的情况下，需要空间复杂性。

每个算法必须具有：

• 规范：计算过程的描述。
• 前提条件：输入条件。
• 算法的主体：一系列清晰明确的指令。
• 后置条件：输出条件。

示例：设计一个算法，将两个数字x和y相乘，并赋值到z中，最后显示结果。

第1步，开始
第2步，声明三个整数x，y和z
第3步，定义x和y的值
第4步，乘以x和y的值
第5步，将第4步的输出存储在z中
第6步，打印z
第7步，停止完成
或者，算法可以写成 -
第1步，开始相乘
第2步，获取x和y的值
第3步， z ← x * y
第4步，显示z
第5步，停止

算法的特征

算法必须遵循以下提到的特征：

• 输入：算法必须具有0个或明确定义的输入。
• 输出：算法必须具有1个或明确定义的输出，并且应与所需的输出匹配。
• 可行性：必须在有限步数后终止算法。
• 独立性：算法必须具有独立于任何编程代码的逐步指导。
• 明确无误：算法必须明确无误。每个步骤和输入/输出必须清晰，并且只能产生一个含义。

---

指针

指针用于指向存储在计算机内存中任何位置的值的地址。

获取存储在该位置的值称为解除引用指针。

指针提高了重复过程的性能，

例如：
遍历字符串
查找表
控制表
树结构

指针详细信息：

• 指针算术：指针中有四个算术运算符：++， -- ，+，-
• 指针数组：可以定义数组以容纳多个指针。
• 指针的指针：C语言允许指针的指针等等。
• 将指针传递给C语言的函数：通过引用或地址传递参数使得被调用函数可以在调用函数中更改传递的参数。
• 从C语言函数返回指针：允许函数返回指向局部变量，静态变量和动态分配内存的指针。

指针示例程序

#include <stdio.h>  
int main()
{
    int a = 5;
    int *b;
    b = &a;
    printf("value of a = %d\n", a);
    printf("value of a = %d\n", *(&a));
    printf("value of a = %d\n", *b);
    printf("address of a = %u\n", &a);
    printf("address of a = %d\n", b);
    printf("address of b = %u\n", &b);
    printf("value of b = address of a = %u", b);
    system("pause");
    return 0;
}
//执行上面示例代码，得到以下结果 -
value of a = 5
value of a = 5
value of a = 5
address of a = 13630708
address of a = 13630708
address of b = 13630696
value of b = address of a = 13630708

//指针的指针示例程序
#include <stdio.h>  

int main()
{
    int a = 5;
    int *b;
    int **c;
    b = &a;
    c = &b;
    printf("value of a = %d\n", a);
    printf("value of a = %d\n", *(&a));
    printf("value of a = %d\n", *b);
    printf("value of a = %d\n", **c);
    printf("value of b = address of a = %u\n", b);
    printf("value of c = address of b = %u\n", c);
    printf("address of a = %u\n", &a);
    printf("address of a = %u\n", b);
    printf("address of a = %u\n", *c);
    printf("address of b = %u\n", &b);
    printf("address of b = %u\n", c);
    printf("address of c = %u\n", &c);
    system("pause");
    return 0;
}

//执行上面示例代码，得到以下结果 -
value of a = 5
value of a = 5
value of a = 5
value of a = 5
value of b = address of a = 16252636
value of c = address of b = 16252624
address of a = 16252636
address of a = 16252636
address of a = 16252636
address of b = 16252624
address of b = 16252624
address of c = 16252612

---

结构体

结构是一种复合数据类型，它定义了一组变量列表，这些变量将放在一个内存块中的一个名称下。

它允许通过使用指向结构的一个指针来访问不同的变量。

struct structure_name   
{  
    data_type member1;  
    data_type member2;  
    ...  
    ...
    data_type memeber;  
};

结构体优点

• 可以保存不同数据类型的变量。
• 可以创建包含不同类型属性的对象。
• 允许跨程序重用数据布局。
• 用于实现其他数据结构，如链表，堆栈，队列，树，图等。

示例程序
#include<stdio.h>  
#include<conio.h>  
void main( )  
{  
    struct employee  
    {  
        int id ;  
        float salary ;  
        int mobile ;  
    };
    // 定义结构体变量
    struct employee e1,e2,e3 ;  
    clrscr();  
    printf ("\nEnter ids, salary & mobile no. of 3 employee\n"  
    scanf ("%d %f %d", &e1.id, &e1.salary, &e1.mobile);  
    scanf ("%d%f %d", &e2.id, &e2.salary, &e2.mobile);  
    scanf ("%d %f %d", &e3.id, &e3.salary, &e3.mobile);  
    printf ("\n Entered Result ");  
    printf ("\n%d %f %d", e1.id, e1.salary, e1.mobile);  
    printf ("\n%d%f %d", e2.id, e2.salary, e2.mobile);  
    printf ("\n%d %f %d", e3.id, e3.salary, e3.mobile);  
    getch();  
}