一.带头结点单链表类
#include <bits/stdc++.h> using namespace std; class LinkedList { private: struct node { int val; node *next; node(int x, node *next) { this->val = x; this->next = next; } }; node *head; int size; public: LinkedList() { head = new node(0, NULL); size = 0; } int getSize() {return size;} bool isEmpty() {return size == 0;} //[0,size] void insert(int index, int x) { if (index<0 || index>size) { cout << "the index is invalid!" << endl; return; } node *p = head; for (int i=0; i<index; ++i) p = p->next; node *q = new node(x, p->next); p->next = q; size ++; } void insertTail(int x) { insert(size, x); } void insertHead(int x) { insert(0, x); } //[0,size-1] int del(int index) { if (index<0 || index>=size) { cout << "the index is invalid" << endl; return -1; } if (isEmpty()) { cout << "the LinkedList is null!" << endl; return -1; } node *p = head; for (int i=0; i<index; ++i) p = p->next; node *del = p->next; p->next = del->next; int res = del->val; delete del; size --; return res; } int delFirst() {return del(0);} int delLast() {return del(size-1);} int get(int index) { if (index<0 || index>size) { cout << "the index is invalid!" << endl; return -1; } if (isEmpty()) { cout << "the LinkedList is null!" << endl; return -1; } node *p = head->next; for (int i=0; i<index; ++i) p = p->next; return p->val; } int getLast() {return get(size-1);} int getFirst() {return get(0);} void show() { node *p = head->next; while (p) { cout << p->val << " "; p = p->next; } cout << endl; } };二.链栈
#include "LinkedList.h" class LinkedListStack { private: LinkedList list; public: stack() { list = LinkedList(); } bool isEmpty() { return list.isEmpty(); } void push(int x) { list.insertHead(x); } int pop() { return list.delFirst(); } int top() { return list.getFirst(); } }; int main() { int a[] = {1,2,3,4,5}; int n = sizeof(a)/sizeof(int); LinkedListStack s; for (int i=0; i<n; ++i) s.push(a[i]); while (!s.isEmpty()) { cout << s.top() << " "; s.pop(); } return 0; }三.链队列
#include "LinkedList.h" class LinkedListQueue { private: LinkedList list; public: LinkedListQueue() { list = LinkedList(); } bool isEmpty() {return list.isEmpty();} void push(int x) { list.insertTail(x); } int front() { return list.getFirst(); } int pop() { return list.delFirst(); } }; int main() { int a[] = {1,2,3,4,5}; int n = sizeof(a)/sizeof(int); LinkedListQueue q; for (int i=0; i<n; ++i) q.push(a[i]); while (!q.isEmpty()) { cout << q.front() << " "; q.pop(); } cout << endl; return 0; }