数据结构之线性表的链式存储实现（链表）

线性表的链式存储实现
线性表的链式存储实现通常单链表. 单链表由一系列在内存中相连的结点组成, 每个结点均含有数据域和指针域, 数据域存储数据, 指针域存储指向下一个结点的指针. 单链表的结构如图:

单链表数据结构中的概念:
结点 node: 结点由数据域和指针域组成, 数据域中可以是任意类型的数据包括结构体甚至其他数据结构, 指针域中是指向链表下一个结点的指针.
头结点 head node: 头结点也称表头哑结点, 数据域无意义, 指针域存储指向链表第一结点的指针, 并将其看作指向当前链表的指针, 注意约定头结点是链表的第0个结点, 而非第1个.
头指针 head pointer: 指向链表头结点的指针, 无头结点时指向链表第一个结点.
位置 position: 一个结点在链表中占据一个位置, 头结点的位置为0.
表长 list length:表中结点的个数(除头结点)
前驱 previous node: 当前结点的前一个结点.
后继 next node: 当前结点的下一个结点.
空表 empty list: 只有头结点的的链表, 表长为0.
存储结构伪代码

struct node;
typedef struct node *ptr_to_node;
typedef ptr_to_node list;
typedef ptr_to_node nodeptr; // 指向结点的指针

int is_empty(list l); // 判断链表l是否为空
int is_last(list l, nodeptr node); // 判断pos所指向的结点是否为最后一个结点
int get_length(list l); // 获取链表长度
int get_position(list l, element_type data); // 获取数据域为data的结点的位置
nodeptr get_current(list l, int pos); // 获取指向pos位置的结点的指针
nodeptr get_previous(list l, int pos); // 获取指向pos位置前一个结点的指针
void init_list(); // 初始化链表
nodeptr find_node(list l, element_type data); // 查找数据域为data的结点, 返回指向其的指针
bool insert_node(list l, int pos, int data); // 在位置pos处插入一个数据域为data的结点
bool delete_node(list l, element_type data); // 删除数据域为data的结点
bool delete_list(list l); // 删除整个链表

struct node {
    element_type element;
    nodeptr next;
};

链表结构如图:
数据结构之线性表的链式存储实现（链表）

实现 is_empty 函数
思路: 头结点的next指针指向NULL时链表为空表.

int is_empty(list l)
{
    return l->next == NULL;
}

实现 is_last 函数
思路: pos结点的next指针指向NULL时, pos指向最后一个结点.

int is_last(list l, nodeptr node)
{
    return node->next == NULL;
}

实现 get_length 函数
思路: 从指向第1个结点的指针开始, 逐个访问结点直到遇到NULL指针.

int get_length(list l)
{
    nodeptr node_ptr = l->next;
    int count = 0;
    while(node_ptr != NULL) {
        node_ptr = node_ptr->next;
        count++;
    }
    return count;

实现 get_position 函数
思路: 从从指向第1个结点的指针开始, 逐个访问结点直到数据域为data的结点

int get_position(list l, element_type data)
{
    nodeptr node_ptr = l->next;
    int count = 0;
    while(node_ptr->element != data) { node_ptr = node_ptr->next; count++; }
}

实现 get_current 函数
思路: 从第1个位置开始, 逐个访问结点直到pos位置.

nodeptr get_current(list ;, int pos)
{
    if(pos >= 1 && pos <= get_length()) {
        nodeptr node_ptr = l->next;
        for(int i = 1; i < pos; i++) {
            nodeptr = nodeptr->next;
        }
        return node_ptr;
    }
    else {
        error("Wrong position!");
        return NULL;
    }
}

实现 get_previous 函数
思路: 从第1个位置开始, 逐个访问结点直到pos位置的前一个位置.

nodeptr get_previous(list ;, int pos)
{
    if(pos >= 1 && pos <= get_length()) {
        nodeptr node_ptr = l;
        for(int i = 0; i < pos - 1; i++) {
            nodeptr = nodeptr->next;
        }
        return node_ptr;
    }
    else {
        error("Wrong position!");
        return NULL;
    }
}

实现 init_list 函数
思路: 分配头结点的内存, 并将其指针域指向NULL.

list init_list()
{
    list l = malloc(sizeof(struct node));
    if( l != NULL) {
        l->element = 0;
        l->next = NULL;
    }
    return l;
}

实现 find_node 函数
思路: 从链表l的第1个结点开始, 将结点的数据域与data比较, 若相同返回当前节点的指针node_ptr, 若不同将node_ptr后移, 继续比较直到链表末尾.

nodeptr find_node(list l, element_type data)
{
    nodeptr node_ptr = l->next; // 从链表第1个结点开始
    while(tmp_node != NULL && node_ptr->element != data)
        node_ptr = node_ptr->next;
    return node_ptr;
}

实现 insert_node 函数
思路:

step1: 获取指向插入位置前一个结点的指针previous
step2: 创建要插入的结点, 并设置数据域为data
step3: 设置要插入结点的指针域为previous->next(指向原位置3的结点)
step4: 设置previous的指针域设置为指向要插入的结点

bool insert_element(list l, int pos, element_type data)
{
    if(pos >= 1 && pos <= get_length(l) + 1) {
        nodeptr previous = get_previous(l, pos);
        nodeptr tmp_node = malloc(sizeof(struct node));
        if(tmp_node != NULL) {
            tmp_node->element = data;
            tmp_node->next = previous->next;
            previous->next = tmp_node;
            retur true;
        }
        else {
            error("Out of space!");
            return false;
        }
    }
    else {
        error("Wrong position!");
    }
}

实现 delete_element 函数
思路:
step1: 获取指向删除位置前一个结点的指针previous
step2: 获取指向删除位置结点的指针current
step3: 设置删除位置前一个结点的指针域指向删除位置后一个结点
step4: free当前位置结点内存

void delete_element(list l, int pos)
{
    if (pos >= 1 && pos <= get_length(l)) {
        nodeptr previous = get_previous(l, pos);
        nodeptr current = previous->next;
        previous->next = current->next;
        free(current);
        return true;
    }
    else {
        printf("Position is wrong!\n");
        return false;
    }
}

实现 delete_list 函数
step1: 记录头指针指向的位置, 并将头指针指向NULL
step2: 逐个free结点内存

void delete_list(list l)
{
    nodeptr recorder = l->next;
        nodeptr tmp_node = NULL;
        l->next = NULL;
        while (recorder != NULL) {
            tmp_node = recorder->next;
            free(recorder);
            recorder = tmp_node;
        }
}

秒客网

数据结构之线性表的链式存储实现（链表）

相关文章