数据结构2_链表_栈和队列.md

链表

1.结构定义：链表是一串节点，每个节点存储两个信息，第一个信息是数据，第二个信息是下一个节点的地址。head变量指向首地址。程序内部的信息控制内存内部的信息。

2.链表插入元素：node节点指向待插入元素地址，用一个指针指向前一个元素，让新的元素指向后一个元素，再让前一个元素指向新元素。

如果先让前一个元素指向新元素，则后面的元素会内存泄漏

3.无头链表：头部不存储信息，相当于用指针指向链表。

有头链表：头部是一个节点，有存储数据的区域。

链表实现

typedef struct node{
    int data;//数据信息
    struct* next;//指针信息
} Node;
//初始化新链表(给一个值，返回节点)
Node* getNewNode(int val){
    Node *p = (Node *)malloc(sizeof(Node));
    p->data = val;
    p->next = NULL;
    return p;
}
//销毁链表
void clear(Node *head){
    if(head==NULL)
        return;
    for(Node *p = head,q;p;p = p->next){
        q = p->next;//用node q存储下一个节点，防止内存泄漏
        free(p);
    }
}
//插入操作(无头链表插入后返回新链表首地址)
Node *insert(Node *head,int pos,int val){
    if(pos == 0){
        Node *p = getNewNode(val);
        p->next = head;
        return p;
    }
    Node *p = head;//让p指针指向前一个元素
    for(int i = 1;i<pos;i++){
        p = p->next;
    }
    Node *node = getNewNode(val);
    node->next = p->next;
    p->next = node;
    return head;
}
//输出链表
void output_linklist(Node *head){
    int len = 0, n = 0;
    for(Node *p = head;p;p = p-next)
        n += 1;//统计一共有几个节点
    for(int i = 0; i<n; i++){
        printf("%3d", i);
        printf("  ");
    }
    printf("\n");
    for(Node *p = head;p;p = p-next){
        printf("%3d", p->data);
        printf("->");
    }
    printf("\n\n\n");
    return ;
}
//查找链表里的元素
int find(Node *head,int val){
    Node *p = head;
    int n = 0;
    while(p){
        if(p->data == val){
            output_linklist(head);
            int len = n*(3+2)+2;
            for(int i = o; i<len; i++){
                printf(" ");
            }
            printf("^\n");
            for(int i = o; i<len; i++){
                printf(" ");
            }
            printf("|")
        }
        n += 1;
        p = p->next;
    }
}

有头链表的插入操作：

Node *insert(Node *head, int pos, int val){
    Node new_head, *p = &new_head;
    new_head.next = head;//创建虚拟头
    for(int i = 0; i < pos; i++)
        p = p->next;
    node->next = p->next;
    p->next = node;
    return new_head.next;
}

循环链表：1.单向循环链表：最后一个节点指向第一个节点，把head看作整个单向循环链表的尾节点。

2.双向链表：结构定义中多了一个pre指针指向前一个元素

链表的其它操作：1.链表头插法：将元素不断插到new_head后面，可以实现反转链表。

2.判断环形链表：用两个指针，其中一个快另一个慢，若两个指针能相遇，则有环。可解决快乐数等问题。（双指针思想）

3.旋转链表：双指针思想运用，p指向尾元素，q指向待旋转链表前一个元素，得到待插入链表。再令q=p，让q遍历待旋转链表，令q->next指向首元素即可，此时p为首元素，return p

ListNode* rotateRight(ListNode* head, int k) {  
        if(head == NULL){
            return head;
        }
        int n = getlength(head);
        k %= n;
        if(k == 0){
            return head;
        }
        ListNode *p = head, *q = head;
        for(int i = 0;i <= k;i++){
            p = p->next;
        }
        while(p){
            p = p->next;
            q = q->next;
        }
        p = q->next;//p指向待转移链表的第一个元素
        q->next = NULL;//不转移链表的尾部指向空指针
        q = p;
        while(q->next != NULL){
            q = q->next;
        }
        q->next = head;
        return p;
    }

3.删除倒数第N个节点：采用双指针等距移动法加上虚拟头节点（将无头链表变为有头链表）

ListNode* removeNthFromEnd(ListNode* head, int n){
    ListNode new_head, *p = &new_head, *q = p;
    new_head.next = head;//创建有头链表
    for(int i = 0; i<=n; i++)
        q = q->next;
    while(q)
        p = p->next,q = q->next;
    p->next = p->next->next;//跳过待删除节点
    return new_head.next;
}

栈和队列

队列

1.结构定义：队列保持从队首出元素，尾部加入元素。指向队首和队尾的指针左闭右开。类比现实生活的排队买票

循环队列：对队列的存储空间可以循环使用，tail超出空间时指向0号元素。

2.队列实现：

用顺序表实现队列：

typedef struct Queue{
    vector *data;
    int size, head, tail//空间大小，头指针。尾指针，元素个数
} Queue;
//初始化操作
Queue *initQueue(int n){
    Queue *q = (Queue *)malloc(sizeof(Queue))
    q->data = initVector(n);
    q->size = n;
    q->head = q->tail = q->count;
}
//压入操作
int push(Queue *q, int val){
    if(q->count == q->size)
        return 0;
    insertVector(q->data, q->tail, val);
    q->tail += 1;
    if(q->tail == q->size)
        q->tail = 0;//已经到队尾，则重新指向队首
    return 1;
}
//弹出操作
int pop(Queue *q){
    if(empty(q))
        return 0;
    q->head += 1;
    q->count -= 1;
    return 1;
}
//查看队首元素
int front(Queue *q){
    return vectorSeek(q->data, q->head);
}
//判空操作
int empty(Queue *q){
    return q->count == 0;
}
//清除队列
void clearQueue(Queue *q){
    if(q == NULL)
       return ;
    clearVector(q->data);
    free(q);
    return;
}

改成链表实现时不需要循环队列和首尾指针。

栈

1.结构定义：先进后出，只能一头进，一头出，想把先放进去的元素取出来必须先把后放进去的元素取出来。入栈和出栈顺序可能不一样。

2.栈实现：

typedef struct Stack{
    int *data;
    int size, top;//top记录栈顶的下标
} Stack;
//初始化
Stack *initStack(int n){
    Stack *s = (Stack *)malloc(sizeof(Stack));
    s->data = (int *)malloc(sizeof(int)*n);
    s->size = n;
    s->top = -1;
    return s;
}
//清除栈
void clearStack(Stack *s){
    if(s == NULL)
        return;
    free(s->data);
    free(s);
    return;
}
//栈判空
int empty(Stack *s){
    return s->top == -1;
}
//查看栈顶
int top(Stack *s){
    if(empty(s))
        return 0;
    return s->data[s->top];
}
//入栈
int push(Stack *s, int val){
    if(s->top + 1 == s->size)
        return 0;
    s->top += 1;
    s->data[s->top] = val;
    return 1;
}
//出栈
int pop(Stack *s){
    if(empty(s))
        return 0;
    s->top -= 1;
    return 1;
}

栈的其它操作：

1.辅助栈法，利用栈先出后入的特点解决问题。eg1：有效的括号问题，遇到左括号则进栈，遇到匹配的右括号则让左括号出栈，最后判断栈是否为空。同时可以用数组，列表代替栈。

eg2（HZOJ595）：

int main(){
    int flag = 0,n;
    cin >> n;
    vector<string> ops(n), s;//用数组s模拟栈
    string target;
    for(int i = 0;i < n;i++)
        cin >> ops[i];
    cin >> target;
    for(int i = 0;i < n;i++){
        if(target == ops[i]){
            s.push_back(ops[i])//将数组尾端当成栈顶
            flag = 1;
            break;
        }
        if(ops[i] == "return")
            s.pop_back();//popback模拟出栈操作
        else s.pushback(ops[i])
    }
    if(flag){
        for(int i = 0;i<s.size();i++){
            if(i)
        }
    }
}

2.C++自带的栈stack操作：s.pop(), s.empty(), s.push().

3.验证栈序列:给定入栈顺序的元素,判断能不能按照给定的顺序进行出栈.(eg:给定[1 2 3 4 5], popped = [4 5 3 2 1]可行)