数据结构知识学习小结

一、动态内存分配基本步骤

1、内存分配简单示例：

个人对于示例的理解：

        定义一个整型的指针变量p（着重认为它是一个“变量”我觉得可能会更好理解），这个变量用来存地址的，而不是“值”，malloc函数参数给空间字节数，图中就是四个字节32位，这个函数返回值是那片数据类型的一个指针，你用强制转换（int*)之后，那片数据类型的一个指针就是整数类型。15赋值给变量*p，打印变量值，释放内存，将地址p传过去。

        可以看到p指向了那片空间的地址，*p变量存在101地址，它的值是15，根据地址，15被指向了那片空间的地址（500），这样值就存在了500地址那里。

        实际测试也可以发现，变量*p的值是16，p地址被存在一个地方，但是其指向那一片开辟出来的空间的地址，那一片地址就放着变量的值，所以第二行地址跟第四行的地址是一样的。

2、结构体的内存分配

        首先理解一下结构体。typedef ：给数据类型换个别名。，本身结构体应该是

typedef struct 结构体名字

{

}

别名；

这样来定义的，不过都有别名了，为了简便，可以省去结构体名字。

然后第二个知识点，malloc分配了多少个字节？换成char x;int y;呢？答案都是八个字节，因为c语言有补位原理要遵循（附讲解）。

第三个、p->元素，是c语言为了简便的又一种写法，跟(*p).元素是一样的（附有实际测试图）。

第四、类比上面那个示例，这里就是malloc开辟了一片8个字节的空间，数据类型是po这个结构体类型，地址则被赋值给p，由p指向这片空间(附实际测试图)。可以看到，其实就是指向第一个元素的地址。然后8到C刚好是12-8=4个字节，说明char x的大小也补成了4个字节。

二、绪论（概念性的，无聊）

1、

        程序 = 算法 + 数据结构；算法的五个重要特性：有穷性，确定性，可行性，输入，输出。

2、f(n)是什么

3、常量阶

        f(n)计算出来是常量，那都是O(1)，不管常量有多大，算法的时间复杂度都是O(1)。

4、线性阶

5、平方阶

        后面的例题我感觉都挺难的，应该不会出。我们有个阶的概念就行。重点是理解上面的动态内存分配。

三、线性表（顺序表和链式表）

1、一些基本概念

2、顺序表

初步理解顺序表

        几点说明：将int重命名为ElemType很有必要，方便以后统一修改数据类型。

以后的函数我感觉习惯上都要有返回值，来验证有没有正确执行。

只是单纯定义了一个变量list，而不是*list指针变量，但是函数都是要接收指针，所以传参的时候都是取地址&。

#include <stdio.h>
#include "stdlib.h"
#include "string.h"#define MAXSIZE 100typedef int ElemType;typedef struct
{ElemType data[MAXSIZE];int length;
}Seglist;void initlist(Seglist* L)//初始化长度
{L->length = 0;
}int appendElem(Seglist* L, ElemType e)//在尾部添加一个元素
{if (L->length >= MAXSIZE){printf("顺序表满了！\n");return 0;}L->data[L->length] = e;L->length++;return 1;
}int listElem(Seglist* L)//遍历元素
{int i = 0;for (i = 0; i < L->length; i++){printf("%d ", L->data[i]);}return 1;
}int main(void)
{Seglist list;initlist(&list);printf("初始化成功，目前使用长度为%d\n", list.length);printf("目前占用内存：%d\n", sizeof(list.data));appendElem(&list, 88);appendElem(&list, 16);appendElem(&list, 57);appendElem(&list, 15);listElem(&list);return 0;
}