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;inext;
    }

    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;inext;
    }

    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;
}

隊列是一種數據結構，常用操作包括入隊、出隊、查看隊首元素等。