"C语言-内存分配、指针实现链表"

  "C语言基础复习七"

Posted by Xu on January 25, 2018

动态分配内存

void *malloc(size_t size);//分配一个指定大小内存块,并返回内存指针(void *),使用类型转换,还需要进行初始化
void free(void pointer);//释放指定内存到内存池,参数为之前使用malloc,calloc,realloc返回的指针
void *calloc(size_t num_elements,size_t element_size);//参数为所需元素的数量和每个元素的字节数,且在分配内存的时候就进行了初始化,初始化为0
void realloc(void *ptr,size_t new_size);//修改一个已经分配的内存块的大小,可扩大和缩小,但远内存块无法改变大小时,realloc将分配另一块正确大小的 内存,并把原内存的内容复制到新内存上,如果ptr参数为空则realloc函数和malloc的行为一模一样。

动态分配内存的常见错误

  1. 检查所请求内存是否成功分配 if (new_mem == NULL){ … }

  2. 操作内存时越界
  3. free释放时操作的指针不合法,必须要是之前malloc,calloc,realloc操作返回的指针,且不能释放部分内存
  4. 内存泄漏:分配内存使用完毕时却不释放,会导致内存池逐步消耗完。

使用结构和指针

链表的插入主要分为三个部分:

  1. 寻找插入位置
  2. 配置新节点
  3. 进行插入指针操作(单链表使用指向头节点指针的指针来统一插入操作,双链表使用标示头节点的根节点,并利用是否为起始节点及是否为末端节点条件组合分别进行相应指针操作)

单链表:

将一个数插入到一个有序链表中

typedef struct NODE{
    struct NODE *ptr;
    int value;
} Node;

-----------------------------------

# include<stdlib.h>
# include<stdio.h>
# include<sslinsert.h>

int sslinsert(Node ** linkp,int new_value){
    Node *current;
    Node *new;
    
    //遍历链表
    while ((current = *linkp)!=NULL&&current->value<new_value){
          linkp = &current->link;
    }
    //确定插入位置后,配置新节点
    new = malloc(sizeof(Node));
    new->value = new_value;
    //插入链表操作
    new->link = current;
    *linkp = new;
    return TRUE;
    

}

插入操作和查找,删除,修改操作都类似,首先要找到指定位置,然后利用指针变动完成操作

双链表

将一个数插入到有序双链表中,双链表会有一个根节点,它的bwd(前一个节点)指向链表末节点,它的fwd(指向链表第一个节点),由于是双向循环链表,所以我们需要一个根节点作为链表的起始点。

double_list

插入操作:情况分析

  1. 中间位置 [(!起始节点)&(!末段节点)]
  2. 起始节点 [ 起始节点&(!末段节点) ]
  3. 末段节点 [ (!起始节点)&末段节点 ]
  4. 起始节点&末段节点

相当于: if(起始节点) X if(末端节点)

typedef NODE{
   struct NODE *fwd;
   struct NODE *bwd;
   int value;
} Node;

# include<stdlib.h>
# include<stdio.h>
# include<double_list.h>

int dll_insert(Node *rootp,int new_value){
    Node * this;//从root开始遍历,this指向new_node前一个节点
    Node * next;//next指向new_node下一个节点
    Node * new_node;
    //遍历寻找插入位置
    for(this = rootp;(next = *this.fwd)!=null;this = next){
        if(next->value>new_value){
              break;
        }
    }
    //构建新节点
    new_node = (Node *)malloc(sizeof(Node));
    new_node->value = new_value;
    
    //插入操作
    new_node->fwd = next;
    this.fwd = new_node;//无论在哪个位置,都存在新节点的前节点为this,后面节点为next
    
    //if(起始节点)
    if(this!=rootp){
      new_node->bwd = this;//插入到中间位置
    }else{
      new_node->bwd = 0;//插入到链表头
    }
    
    //if(末端节点)
    if (next!=NULL){
       next->bwd  = new_node;//没有插入到链表末段   
    }else{
       rootp->bwd = new_node;//插入到链表末段   
    }
    
    return 1;

}