第四章 ALDS1_3_C:Doubly Linked List 链表

知识点

链表

• 链表类型
  
  • 单向链表： 数据本体和指向后一元素的指针next
  • 双向链表： 数据本体、指向前一元素的指针prev和指向后一元素的指针next
  • 循环链表： 在单向链表或者双向链表的前提下加上循环利用数组的机制的链表
• STL的list类（双向链表）的成员函数
  
  • size():返回表的元素数
  • begin():返回指向表开头的迭代器
  • end():返回表末尾的迭代器
  • push_front(x):在表的开头添加元素x
  • push_back(x):在表的末尾添加元素x
  • pop_front():删除表头的元素
  • pop_back():删除表尾的元素
  • insert(p,x):在表的位置p插入元素x
  • erase(p):删除表中位置p的元素
  • clear():删除表中的所有元素

问题链接

ALDS1_3_C:Doubly Linked List

问题内容

模拟链表的插入删除功能，输出链表的元素

思路

模拟链表的插入删除功能

代码

实现双向链表功能

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;

const int maxx = 100000 + 10;
struct Node {
    int key;
    Node *prev, *next;
};

Node *nil;

// 链表初始化
void init() {
    nil = (Node *)malloc(sizeof(Node));
    //C++ nil = new Node();
    nil->next = nil;
    nil->prev = nil;
}

// 从链表搜索出值为key的结点 O(n)
Node* listSearch(int key) {
    // 从链表头结点开始访问
    Node *cur = nil->next;
    while (cur != nil && cur->key != key) {
        cur = cur->next;
    }
    return cur;
}

// 打印链表
void printList() {
    Node *cur = nil->next;
    int flag = 0;
    while (cur != nil) {
        if (flag++ > 0)
            printf(" ");
        printf("%d", cur->key);
        cur = cur->next;
    }
    printf("\n");
}

// 删除结点t
void deleteNode(Node *t) {
    // t为头结点不做处理
    if (t == nil)
        return;
    t->prev->next = t->next;
    t->next->prev = t->prev;
    free(t);
    //C++ delete(t);
}

// 删除头结点
void deleteFirst() {
    deleteNode(nil->next);
}

// 删除尾结点
void deleteLast() {
    deleteNode(nil->prev);
}

// 删除指定的key O(n)
void deleteKey(int key) {
    deleteNode(listSearch(key));
}

// 在链表头部添加元素key
void insert(int key) {
    Node *x = (Node *)malloc(sizeof(Node));
    //C++ Node *x = new Node();
    x->key = key;

    x->next = nil->next;
    nil->next->prev = x;
    nil->next = x;
    x->prev = nil;
}
int main() {
    int n, key, size = 0;
    char op[20];
    scanf("%d", &n);
    getchar();
    // 初始化链表
    init();
    for (int i = 0; i < n; i++) {
        scanf("%s %d", op, &key);
        if (op[0] == 'i') {
            insert(key);
            size++;
        }
        else {
            if (strlen(op) > 6) {
                if (op[6] == 'F') {//删除头结点
                    deleteFirst();
                }
                else {//删除尾结点
                    deleteLast();
                }
            }
            else { //删除结点
                deleteKey(key);
            }
            size--;
        }
    }
    printList();
    return 0;
}

利用STL的list类

#include<iostream>
#include<cstdio>
#include<cstring>
#include<list>
using namespace std;

int main() {
    int n, key;
    char op[20];
    list<int> List;
    scanf("%d", &n);
    getchar();

    for (int i = 0; i < n; i++) {
        scanf("%s %d", op, &key);
        if (op[0] == 'i') {
            List.push_front(key);
        }
        else {
            if (strlen(op) > 6) {
                if (op[6] == 'F') {//删除头结点
                    List.pop_front();
                }
                else {//删除尾结点
                    List.pop_back();
                }
            }
            else { //删除结点
                for (list<int>::iterator it = List.begin(); it != List.end(); it++) {
                    if (*it == key) {
                        List.erase(it);
                        break;
                    }
                }
            }
        }
    }
    int flag = 0;
    for (list<int>::iterator it = List.begin(); it != List.end(); it++) {
        if (flag != 0)
            printf(" ");
        flag++;
        printf("%d", (*it));
    }
    printf("\n");
    return 0;
}