1、链表
#include <iostream>
using namespace std;
class Node{
public:
int data;
Node* next;
};
class LinkList{
public:
int length;
Node* head;
LinkList();
~LinkList();
void reverse();
void addFront(int data);
void add(int data);
int findk(int k);
void print();
};
LinkList::LinkList()
{
this->length = 0;
this->head = NULL;
}
LinkList::~LinkList(){
std::cout << "LIST DELETED";
}
//头插法
void LinkList::addFront(int data)
{
Node* node = new Node();
node->data = data;
node->next = this->head;
this->head = node;
this->length++;
}
//尾插法
void LinkList::add(int data)
{
Node *node = new Node();
Node *last = head;
node->data = data;
node->next = NULL;
if(head == NULL)
{
head = node;
return;
}
while(last->next !=NULL)
{
last = last->next;
}
last->next = node;
this->length++;
}
void LinkList::print()
{
Node* temp = head;
for(;temp!=NULL;temp = temp->next)
{
std::cout<<"data = "<<temp->data<<endl;
}
}
void LinkList::reverse()
{
Node *current = head;
Node *prev = NULL, *next = NULL;
while (current != NULL)
{
// Store next
next = current->next;
// Reverse current node's pointer
current->next = prev;
// Move pointers one position ahead.
prev = current;
current = next;
}
head = prev;
}
int LinkList::findk(int k)
{
if(k > length)
throw k;
Node* p = head;
Node* q;
while((k-1)!= 0)
{
head = head->next;
k--;
}
q = head;
while(q->next != NULL)
{
q = q->next;
p = p->next;
}
return p->data;
}
int main(int arg,char* argv[])
{
try{
LinkList* l = new LinkList();
l->add(1);
l->add(2);
l->add(3);
l->add(4);
l->reverse();
l->print();
cout<<"倒数第3个是"<<l->findk(3)<< endl;
cout<<"length = "<<l->length <<endl;
delete l;
}
catch(int k)
{
cout<<"k is illegal!!"<<endl;
}
return 0;
}
2、数组
#ifndef ARRAY_H
#define ARRAY_H
#include <cassert>
#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
using namespace std;
template<class T>
class Array{
private:
T* list;//动态分配数组的首地址
int size;
public:
Array(int sz = 50);
Array(const Array<T> &a);
~Array();
//why return reference when overloading " = "?
// Array<T>& operator=(const Array<T> &rhs);
T & operator [] (int i);
const T & operator [] (int i) const;
// operator T* ();
// operator const T* () const;
int getSize() const;
void show();
void delete_same();
// void resize(int sz);
};
template<class T>
Array<T>::Array(int sz)
{
assert(sz >= 0);
size = sz;
list = new T[size];
}
template<class T>
Array<T>::~Array()
{
delete [] list;
}
template<class T>
Array<T>::Array(const Array<T> &a)
{
// Array<T> arr = new Array<T>(a.size);
size = a.size;
list = new T[size];//apply mem for new object
//从对象a复制数组元素到本对象
for(int i = 0;i<size;i++)
{
list[i] = a.list[i];
}
}
//重载‘= ’
//template<class T>
//Array<T>& Array<T>::operator=(const Array<T> &rhs)
//{
//
//}
//重载[]
template<class T>
T & Array<T>:: operator [] (int i)
{
assert(i >= 0 && i<size);
return list[i];
}
template<class T>
const T & Array<T>:: operator [] (int i) const
{
assert(i >= 0 && i<size);
return list[i];
}
template<class T>
int Array<T>::getSize() const
{
return size;
}
template<class T>
void Array<T>::show()
{
int i = 0;
while(i < size)
{
cout<<list[i]<<endl;
i++;
}
}
template<class T>
void Array<T>::delete_same()
{
vector<int> v(size);
for(int i = 0;i<size;i++)
{
v[i] = list[i];
}
sort(v.begin(),v.end());
int j = 0;
int size_reduce = 0;
for(int i = 0;i<size - 1;i++)
{
if(v[i] != v[i+1])
list[j++] = v[i];
else
size_reduce++;
}
list[j] = v[size - 1];
cout<<"size_reduce = "<<size_reduce<<endl;
size -= size_reduce;
}
int main()
{
Array<int> arr(4);
arr[0] = 8;
arr[1] = 7;
arr[2] = 6;
arr[3] = 6;
arr.delete_same();
arr.show();
cout<<"arr.length = "<<arr.getSize()<<endl;
return 0;
}
#endif
3、顺序栈
#ifndef STACK_H
#define STACK_H
#include <cassert>
template <class T,int SIZE = 50>
class Stack_{
private:
T list[SIZE];
int top;
public:
Stack_();
void push(const T &item);
T pop();
void clear();
const T &peek() const;
bool isEmpty() const;
bool isFull() const;
};
template <class T,int SIZE>
Stack_<T,SIZE>::Stack_():top(-1){
}
template <class T,int SIZE>
void Stack_<T,SIZE>::push(const T &item)
{
assert(!isFull());
list[++top] = item;
}
template <class T,int SIZE>
T Stack_<T,SIZE>::pop()
{
return list[top--];
}
template <class T,int SIZE>
const T &Stack_<T,SIZE>::peek() const
{
assert(!isEmpty());
return list[top];
}
template <class T,int SIZE>
bool Stack_<T,SIZE>::isEmpty() const{
return top == -1;
}
template <class T,int SIZE>
bool Stack_<T,SIZE>::isFull() const{
return top == SIZE -1;
}
template <class T,int SIZE>
void Stack_<T,SIZE>::clear()
{
top = -1;
}
#endif
4、链栈
#include <iostream>
#include <stdio.h>
using namespace std;
template<class T>
class Node{
public:
T data;
Node* next;
Node(const T &value)
: next(NULL), data(value)
{
}
};
template<class T,int SIZE = 50>
class LinkStack{
public:
Node<T>* top;
LinkStack():top(NULL)
{
}
~LinkStack()
{
std::cout << "LIST DELETED";
}
void push(const T& data)
{
Node<T>* node = new Node<T>(data);
node->next = this->top;
this->top = node;
}
T pop()
{
Node<T> *temp = top;
top = top->next;
return temp->data;
}
bool isEmpty()
{
return top == NULL;
}
};
int main(int arg,char* argv[])
{
LinkStack<int> l;
l.push(1);
l.push(2);
l.push(3);
l.push(4);
cout<<"delete: "<<l.pop()<<endl;
cout<<"delete: "<<l.pop()<<endl;
cout<<"delete: "<<l.pop()<<endl;
cout<<"delete: "<<l.pop()<<endl;
cout<<l.isEmpty()<<endl;
return 0;
}
