城东书院 www.cdsy.xyz
栈内存(Stack)
- 栈中存放任意类型的变量,但必须是 auto 类型修饰的,即自动类型的局部变量, 随用随开,用完即消。
- 内存的分配和销毁系统自动完成,不需要人工干预
- 栈的最大尺寸固定,超出则引起栈溢出
- 局部变量过多,过大 或 递归层数太多等就会导致栈溢出
- #include <stdio.h>
-
- int main()
- {
-
- int a = 10;
- int b = 20;
- printf("&a = %p\n", &a);
- printf("&b = %p\n", &b);
-
- return 0;
- }
-
堆内存(Heap)
- 堆内存可以存放任意类型的数据,但需要自己申请与释放
- 堆大小,想像中的无穷大,但实际使用中,受限于实际内存的大小和内存是否连续性
- int *p = (int *)malloc(10240 * 1024);
-
- #include <stdio.h>
- #include <stdlib.h>
-
- int main()
- {
-
- int *p1 = malloc(4);
- *p1 = 10;
- int *p2 = malloc(4);
- *p2 = 20;
-
- printf("p1 = %p\n", p1);
- printf("p2 = %p\n", p2);
-
- return 0;
- }
-
malloc函数
函数声明 |
void * malloc(size_t _Size); |
所在文件 |
stdlib.h |
函数功能 |
申请堆内存空间并返回,所申请的空间并未初始化。 |
常见的初始化方法是 |
memset 字节初始化。 |
参数及返回解析 |
|
参数 |
size_t _size 表示要申请的字符数 |
返回值 |
void * 成功返回非空指针指向申请的空间 ,失败返回 NULL |
- #include <stdio.h>
- #include <stdlib.h>
- #include <string.h>
-
- int main()
- {
-
-
- int *p = (int *)malloc(sizeof(int));
- printf("p = %i\n", *p);
-
-
- memset(p, 0, sizeof(int));
- printf("p = %i\n", *p);
- return 0;
- }
-
free函数
- 注意: 通过malloc申请的存储空间一定要释放, 所以malloc和free函数总是成对出现
函数声明 |
void free(void *p); |
所在文件 |
stdlib.h |
函数功能 |
释放申请的堆内存 |
参数及返回解析 |
|
参数 |
void* p 指向手动申请的空间 |
返回值 |
void 无返回 |
- #include <stdio.h>
- #include <stdlib.h>
- #include <string.h>
-
- int main()
- {
-
- int *p = (int *)malloc(sizeof(int));
-
- memset(p, 0, sizeof(int));
-
- free(p);
- return 0;
- }
-
calloc函数
函数声明 |
void *calloc(size_t nmemb, size_t size); |
所在文件 |
stdlib.h |
函数功能 |
申请堆内存空间并返回,所申请的空间,自动清零 |
参数及返回解析 |
|
参数 |
size_t nmemb 所需内存单元数量 |
参数 |
size_t size 内存单元字节数量 |
返回值 |
void * 成功返回非空指针指向申请的空间 ,失败返回 NULL |
- #include <stdio.h>
- #include <stdlib.h>
- #include <string.h>
-
- int main()
- {
-
-
-
-
- int *p = calloc(3, sizeof(int));
-
- p[0] = 1;
- p[1] = 3;
- p[2] = 5;
- printf("p[0] = %i\n", p[0]);
- printf("p[1] = %i\n", p[1]);
- printf("p[2] = %i\n", p[2]);
-
- free(p);
-
- return 0;
- }
-
realloc函数
函数声明 |
void *realloc(void *ptr, size_t size); |
所在文件 |
stdlib.h |
函数功能 |
扩容(缩小)原有内存的大小。通常用于扩容,缩小会会导致内存缩去的部分数据丢失。 |
参数及返回解析 |
|
参数 |
void * ptr 表示待扩容(缩小)的指针, ptr 为之前用 malloc 或者 calloc 分配的内存地址。 |
参数 |
size_t size 表示扩容(缩小)后内存的大小。 |
返回值 |
void* 成功返回非空指针指向申请的空间 ,失败返回 NULL。 |
- 注意点:
- 若参数ptr==NULL,则该函数等同于 malloc
- 返回的指针,可能与 ptr 的值相同,也有可能不同。若相同,则说明在原空间后面申请,否则,则可能后续空间不足,重新申请的新的连续空间,原数据拷贝到新空间, 原有空间自动释放
- #include <stdio.h>
- #include <stdlib.h>
- #include <string.h>
-
- int main()
- {
-
- int *p = NULL;
- p = realloc(p, sizeof(int));
-
- *p = 666;
- printf("*p = %i\n", *p);
-
- free(p);
-
- return 0;
- }
-
- #include <stdio.h>
- #include <stdlib.h>
- #include <string.h>
-
- int main()
- {
-
- int *p = malloc(sizeof(int));
- printf("p = %p\n", p);
-
-
- p = realloc(p, sizeof(int) * 2);
- printf("p = %p\n", p);
-
- *p = 666;
- printf("*p = %i\n", *p);
-
- free(p);
-
- return 0;
- }
-
链表
- 链表实现了,内存零碎数据的有效组织。比如,当我们用 malloc 来进行内存申请的时候,当内存足够,但是由于碎片太多,没有连续内存时,只能以申请失败而告终,而用链表这种数据结构来组织数据,就可以解决上类问题。

静态链表
- #include <stdio.h>
- #include <stdlib.h>
- #include <string.h>
-
-
- typedef struct node{
- int data;
- struct node *next;
- }Node;
- int main()
- {
-
-
- Node a;
- Node b;
- Node c;
-
-
- a.data = 1;
- b.data = 3;
- c.data = 5;
-
-
- a.next = &b;
- b.next = &c;
- c.next = NULL;
-
-
- Node *head = &a;
-
-
- while(head != NULL){
- int currentData = head->data;
- printf("currentData = %i\n", currentData);
- head = head->next;
- }
- return 0;
- }
-
动态链表
- 静态链表的意义不是很大,主要原因,数据存储在栈上,栈的存储空间有限,不能动态分配。所以链表要实现存储的自由,要动态的申请堆里的空间。
- 有一个点要说清楚,我们的实现的链表是带头节点。至于,为什么带头节点,需等大家对链表有个整体的的认知以后,再来体会,会更有意义。
- 空链表
- 头指针带了一个空链表节点, 空链表节点中的next指向NULL

- #include <stdio.h>
- #include <stdlib.h>
-
-
- typedef struct node{
- int data;
- struct node *next;
- }Node;
- int main()
- {
- Node *head = createList();
- return 0;
- }
-
- Node *createList(){
-
- Node *node = (Node *)malloc(sizeof(Node));
- if(node == NULL){
- exit(-1);
- }
-
- node->next = NULL;
-
- return node;
- }
-
- 头指针带了一个非空节点, 最后一个节点中的next指向NULL

动态链表头插法
- 1.让新节点的下一个节点等于头结点的下一个节点
- 2.让头节点的下一个节点等于新节点
- #include <stdio.h>
- #include <stdlib.h>
-
-
- typedef struct node{
- int data;
- struct node *next;
- }Node;
- Node *createList();
- void printNodeList(Node *node);
- int main()
- {
- Node *head = createList();
- printNodeList(head);
- return 0;
- }
-
- Node *createList(){
-
- Node *head = (Node *)malloc(sizeof(Node));
- if(head == NULL){
- return NULL;
- }
- head->next = NULL;
-
-
- int num = -1;
- printf("请输入节点数据\n");
- scanf("%i", &num);
-
-
- while(num != -1){
-
- Node *cur = (Node *)malloc(sizeof(Node));
- cur->data = num;
-
-
- cur->next = head->next;
-
- head->next = cur;
-
-
- scanf("%i", &num);
- }
-
-
- return head;
- }
-
- void printNodeList(Node *node){
- Node *head = node->next;
- while(head != NULL){
- int currentData = head->data;
- printf("currentData = %i\n", currentData);
- head = head->next;
- }
- }
-
动态链表尾插法
- 1.定义变量记录新节点的上一个节点
- 2.将新节点添加到上一个节点后面
- 3.让新节点成为下一个节点的上一个节点
- #include <stdio.h>
- #include <stdlib.h>
-
-
- typedef struct node{
- int data;
- struct node *next;
- }Node;
- Node *createList();
- void printNodeList(Node *node);
- int main()
- {
- Node *head = createList();
- printNodeList(head);
- return 0;
- }
-
- Node *createList(){
-
- Node *head = (Node *)malloc(sizeof(Node));
- if(head == NULL){
- return NULL;
- }
- head->next = NULL;
-
-
- int num = -1;
- printf("请输入节点数据\n");
- scanf("%i", &num);
-
-
-
- Node *pre = head;
- while(num != -1){
-
- Node *cur = (Node *)malloc(sizeof(Node));
- cur->data = num;
-
-
- pre->next = cur;
-
- cur->next = NULL;
-
- pre = cur;
-
-
- scanf("%i", &num);
- }
-
-
- return head;
- }
-
- void printNodeList(Node *node){
- Node *head = node->next;
- while(head != NULL){
- int currentData = head->data;
- printf("currentData = %i\n", currentData);
- head = head->next;
- }
- }
-
动态链优化
-
-
-
-
- typedef struct node{
- int data;
- struct node *next;
- }Node;
- Node *createList();
- void printNodeList(Node *node);
- void insertNode1(Node *head, int data);
- void insertNode2(Node *head, int data);
- int main()
- {
-
- Node *head = createList();
-
- insertNode1(head, 1);
- insertNode1(head, 3);
- insertNode1(head, 5);
- printNodeList(head);
- return 0;
- }
-
- Node *createList(){
-
- Node *head = (Node *)malloc(sizeof(Node));
- if(head == NULL){
- return NULL;
- }
- head->next = NULL;
-
- return head;
- }
-
- void insertNode1(Node *head, int data){
-
- Node *pre = head;
- while(pre != NULL && pre->next != NULL){
- pre = pre->next;
- }
-
- Node *cur = (Node *)malloc(sizeof(Node));
- cur->data = data;
-
-
- pre->next = cur;
-
- cur->next = NULL;
-
- pre = cur;
- }
-
- void insertNode2(Node *head, int data){
-
- Node *cur = (Node *)malloc(sizeof(Node));
- cur->data = data;
-
-
- cur->next = head->next;
-
- head->next = cur;
- }
-
- void printNodeList(Node *node){
- Node *head = node->next;
- while(head != NULL){
- int currentData = head->data;
- printf("currentData = %i\n", currentData);
- head = head->next;
- }
- }
-
链表销毁
-
- void destroyList(Node *head){
- Node *cur = NULL;
- while(head != NULL){
- cur = head->next;
- free(head);
- head = cur;
- }
- }
-
链表长度计算
-
- int listLength(Node *head){
- int count = 0;
- head = head->next;
- while(head){
- count++;
- head = head->next;
- }
- return count;
- }
-
链表查找
-
- Node *searchList(Node *head, int key){
- head = head->next;
- while(head){
- if(head->data == key){
- break;
- }else{
- head = head->next;
- }
- }
- return head;
- }
-
城东书院 www.cdsy.xyz