C和指针-6


结构体

注意:

struct {
    int a;
    char b;
} x;

struct {
    int a;
    char b;
} y[20], *z;

这两个声明被编译器当作两种不同的类型,即使他们成员列表相同,因此z = &x;是非法的。

typedef 声明

typedef struct{
    int a;
    char b;
} Simple;

Simple x;

结构体的边界对齐

struct ALIGN{   
    char a;
    int b;
    char c;
};

占用12个字节

struct ALIGN2{
    int b;
    char a;
    char c;
};

只占用8个字节

在声明中对结构的成员列表重新排列,让那些对边界要求严格的成员首先出现,对边界要求最弱的成员最后出现,可以减少因边界对齐带来的空间损失。

sizeof 操作符能够得出一个结构的整体长度,包括因边界对齐而跳过的那些字节,如果必须确定结构某个成员的实际位置,应该要考虑边界对齐因素,可以使用 offset 宏(定义于 stddef.h)

offsetof( type, member)

比如 offsetof( struct ALIGN, b)返回4,指定成员开始存储的位置距离结构开始存储的位置偏移几个字节。

结构体作为函数参数

尽量传递指针,可以把参数声明为寄存器变量,进一步提高参数传递效率。

void compute(register Transaction *trans)
{
    ...
}

联合

联合(union)的所有成员引用的是内存中相同位置。

联合可以被初始化,但是初始化的值必须是联合的第一个成员的类型,而且它必须位于一对花括号里。

uinon{
    int a;
    float b;
    char c[4];
} x = {5};

动态内存分配

void *malloc(size_t size);
void free(void *pointer);

malloc 的参数就是需要分配的内存字节数,如果内存池中的可用内存可以满足要求,malloc 就返回一个指向被分配的内存块起始位置的指针,失败则返回 NULL .
free 的参数是 NULL 或者先前从 malloc\calloc 或 realloc 返回值。

void *calloc(size_t num_elements,
            size_t element_size);
void realloc(void *ptr, size_t new_size);

calloc 与 malloc 区别是在返回指向内存的指针之前把它初始化为0,第一个参数是元素数量,第二个参数是元素字节数。

realloc 用于修改一个原先已经分配的内存大小,如果原来的内存块无法改变大小,realloc 将分配一块正确大小的内存块,并把原先内存块的内容复制到新块上。因此,在使用 realloc 之后,只能使用 realloc 返回的新指针

释放一块内存的一部分是不允许的。

分配内存但在使用完毕后不释放内存将引起内存泄漏(memory leak)。

结构和指针

链表

在单链表中,每个节点包含一个指向链表下一个节点的指针,链表最后一个节点的指针字段的值为NULL,提示链表后面不再有其它节点,链表的起始位置使用根指针标记。

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

## 单链表插入
``` c
#include <stdio.h>
#include <stdio.h>
#include "sll_node.h" 

#define FALSE 0
#define TRUE 1

//使用指针的指针,可以将根指针传入而不是值传入
//使用 register 声明,提高代码运行效率
int sll_insert(register Node **linkp, int new_value)
{
    register Node *current;
    register Node *new;

    //查找插入位置,访问链表,直到找到一个大于等于新值的节点
    //NULL 为链表尾
    while((current = *linkp) != NULL && 
    current-> <new_value )
    linkp = &current->link; //获得link指针的地址 指向下一个

    //为新节点分配内存,并把新值储存到新节点中
    new = (Node *)malloc( sizeof(Node));
    if( new == NULL)
        return FALSE;
    new -> value = new_value; 

    //在链表中插入新节点
    new->link = current;
    *linkp = new;
    return TRUE;
}
</code></pre>

<h2>双链表</h2>

单链表的替代方案就是双链表,双链表中每个节点包含两个指针,指向前一个节点的指针和指向后一个节点的指针。

<pre><code class="language-c line-numbers">typedef struct NODE
{
    struct NODE *fwd;
    strcut NODE *bwd;
    int value;
}Node;

为根指针声明一个完整的节点,它的值字段为空。根节点的 pwd 指针指向链表的第一个节点,bwd 指针指向链表的最后一个节点。 

``` c
#include <stdio.h>
#include <stdlib.h>
#include "doubly_linked_list_node.h"

int dll_insert(register Node *rootp, int value)
{
    register Node *this;
    register Node *next;
    register Node *newnode;

    //判断 value 是否在链表中,在则返回
    //this 指向新节点之前的那个节点
    //next 指向新节点之后的那个节点
    //fwd 等于 NULL 时,已到链表尾
    fir(this = rootp;(next = this->fwd) != NULL; this = next)
    {
        if(next->value == value)
        {
            return 0;
        }
        if(next->value > value)
        {
            break;
        }
    }

    newnode = (Node *)malloc(sizeof(Node));
    if(newnode == NULL)
    {
        return -1;
    }
    newnode->value = value;

    //把新节点加入链表
    newnode->fwd = next;
    this->fwd = newnode;

    if(this != rootp)
        newnode->bwd = this;
    else
        newnode->bwd = NULL;

    if(next != NULL)
        next->bwd = newnode;
    else
        rootp->bwd = newnode;

    return 1;
}

注意 fwd 前向实际是链表的下一个

  • 分享:
评论
还没有评论
    发表评论 说点什么