C语言链表的基本操作

一、链表介绍

链表是一个数据结构，通常用来存储具有相同数据类型的一系列元素。链表中的每个元素都包含一个指向相邻元素的指针，这些指针将链表内的元素连接在一起，形成一个链式结构。

二、链表的基本操作

1. 创建链表

struct Node{
    int data;
    struct Node *next;
};

struct Node *create_list(int n){
    struct Node *head=NULL, *p, *prev;
    int i=0;

    for(i;idata);
        p->next=NULL;

        if(head==NULL){
            head=p;
            prev=p;
        }
        else{
            prev->next=p;
            prev=p;
        }
    }

    return head;
}

  

创建链表的基本思想是遍历用户输入的元素数据，将每个元素创建成一个节点，并通过指针将它们串联成链表。本代码中使用的是头插法，即每次创建新节点都插入到链表头部。

2. 插入节点

struct Node *insert_node(struct Node *head, int pos, int data){
    struct Node *p, *prev, *cur;
    int i;

    p = (struct Node*)malloc(sizeof(struct Node));
    p->data=data;
    p->next=NULL;

    if(head==NULL){
        head=p;
        return head;
    }

    if(pos==1){
        p->next=head;
        head=p;
        return head;
    }

    cur=head;
    prev=NULL;
    for(i=1;i<=pos-1 && cur!=NULL;i++){
        prev=cur;
        cur=cur->next;
    }

    p->next=cur;
    prev->next=p;

    return head;
}

插入节点的基本思想是找到要插入节点的位置，并将要插入节点的指针指向该位置后面的节点。本代码中实现的插入功能只能在链表中间插入一个节点，如果想在链表尾插入节点，则需要重新为方法设计代码。

3. 删除节点

struct Node *delete_node(struct Node *head, int pos){
    struct Node *prev, *cur;

    if(head==NULL){
        return head;
    }

    if(pos==1){
        cur=head;
        head=head->next;
        free(cur);
        return head;
    }

    cur=head;
    prev=NULL;
    int i;
    for(i=1;i<=pos-1 && cur!=NULL;i++){
        prev=cur;
        cur=cur->next;
    }

    if(cur==NULL){
        return head;
    }

    prev->next=cur->next;
    free(cur);

    return head;
}

删除节点的基本思想是找到要删除节点的位置，并将其前一个节点的指针指向其后一个节点。本代码中实现的删除功能只能删除链表中间的一个节点。

4. 查找节点

int find_node(struct Node *head, int data){
    struct Node *p=head;
    int i=0;

    while(p!=NULL){
        i++;
        if(p->data==data){
            return i;
        }
        p=p->next;
    }

    return -1;
}

查找节点的基本思想是遍历整个链表，逐一比对所有节点中是否有值和目标值相等的节点。本代码中查找的是第一个等于目标值的节点。

三、链表的应用

1. 使用链表实现栈数据结构

struct StackNode{
    int data;
    struct StackNode *next;
};
typedef struct StackNode StackNode;

struct StackList{
    StackNode *top;
};
typedef struct StackList StackList;

void init_stack(StackList *stack){
    stack->top = NULL;
}
int is_empty(StackList *stack){
    if(stack->top == NULL){
        return 1;
    }
    else{
        return 0;
    }
}

int push(StackList *stack, int data){
    StackNode *new_node = (StackNode*)malloc(sizeof(StackNode));
    if(new_node == NULL){
        return -1;
    }
    new_node->data = data;
    new_node->next = stack->top;
    stack->top = new_node;
    return 0;
}

int pop(StackList *stack){
    StackNode *p;
    int data;
    if(is_empty(stack)){
        return -1;
    }
    p = stack->top;
    stack->top = p->next;
    data = p->data;
    free(p);
    return data;
}

int get_top(StackList *stack){
    if(is_empty(stack)){
        return -1;
    }
    return stack->top->data;
}

栈是一种数据结构，常用操作包括入栈、出栈、查看栈顶元素等。

2. 使用链表实现队列数据结构

struct QueueNode{
    int data;
    struct QueueNode *next;
};

struct Queue{
    QueueNode *front;
    QueueNode *rear;
};
typedef struct Queue Queue;


void init_queue(Queue *queue){
    queue->front = NULL;
    queue->rear = NULL;
}

int is_empty(Queue *queue){
    if(queue->front == NULL){
        return 1;
    }
    else{
        return 0;
    }
}

int enqueue(Queue *queue, int data){
    QueueNode *new_node = (QueueNode*)malloc(sizeof(QueueNode));
    if(new_node == NULL){
        return -1;
    }
    new_node->data = data;
    new_node->next = NULL;
    if(queue->front == NULL){
        queue->front = new_node;
        queue->rear = new_node;
    }
    else{
        queue->rear->next = new_node;
        queue->rear = new_node;
    }
    return 0;
}

int dequeue(Queue *queue){
    QueueNode *p;
    int data;
    if(is_empty(queue)){
        return -1;
    }
    p = queue->front;
    queue->front = p->next;
    if(queue->front == NULL){
        queue->rear = NULL;
    }
    data = p->data;
    free(p);
    return data;
}

int get_front(Queue *queue){
    if(is_empty(queue)){
        return -1;
    }
    return queue->front->data;
}

队列是一种数据结构，常用操作包括入队、出队、查看队首元素等。