数据结构的学习马上就会告一段落，这里打算用C++去挨个的写一遍也就算是做复习了，文章会持续更新。
链表
常规链表
//
// linklist.cpp
// 链表
//
// Created by edisoncgh on 2020/4/4.
// Copyright © 2020 edisoncgh. All rights reserved.
//
#include <cstdio>
#include <iostream>
#include <cstdlib>
using namespace std;
//构建节点类
class Node
{
public:
int data;//数据域
Node* next;//指针域
};
class List//构建链表类
{
public:
List();//构建函数
~List();//析构函数
void createList(int n);//创建一个n结点的链表
void travelList();//遍历链表
int getLength();//获取链表长度
bool isEmpty();//链表判空
Node* findNode(int data);//查找指定数据域的结点
int searchNode(int n);//查找第n个结点的值;
void endInsert(int data);//尾插
void headInsert(int data);//头插
void listInsert(int data, int n);//插入第n个结点
void nodeDelete(int data);//删除指定数据域的结点
void findDelete(int n);//删除第n个结点
private:
Node* head;//头结点
};
//初始化链表类
List::List()
{
head = (Node*)malloc(sizeof(Node));
head->data = -1;
head->next = NULL;
}
//销毁链表类
List::~List()
{
delete head;
}
//创建一个长n个结点的链表
void List::createList(int n)
{
Node *temp = nullptr, *newp = nullptr;
temp = head;
if(n < 0)
{
printf("输入有误\n");
return ;
}
for (int i = 0; i < n; i++)
{
newp = (Node*)malloc(sizeof(Node));
printf("输入第%d个值\n", i+1);
cin >> newp->data;
newp->next = NULL;
temp->next = newp;
temp = newp;
}
}
//遍历链表
void List::travelList()
{
if(head == NULL || head->next == NULL)
{
printf("链表为空\n");
return ;
}
Node *t;
t = head->next;
while(t != NULL)
{
cout << t->data << " ";
t = t->next;
}
cout << endl;
}
//返回链表长度
int List::getLength()
{
int length = 0;
Node *t;
t = head;
while(t->next != NULL)
{
length++;
t = t->next;
}
return length;
}
//链表判空
bool List::isEmpty()
{
return head->next == NULL;
}
//查找数据域为data的结点
Node* List::findNode(int data)
{
Node *p = head;
if(p == NULL || p->next == NULL)
{
printf("链表为空\n");
return NULL;
}
else
{
while(p->next != NULL)
{
if(p->data == data) return p;
p = p->next;
}
return NULL;//表里没有这个结点
}
}
//查找第n个结点的值
int List::searchNode(int n)
{
Node *p = head;
int i = 1;
while(n >= i)
{
p = p->next;
i++;
}
return p->data;
}
//尾插
void List::endInsert(int data)
{
Node *newp;
newp = (Node*)malloc(sizeof(Node));
newp->next = NULL;
newp->data = data;
Node *p = head;
if(head == NULL) head = newp;//若链表为空则此结点为头结点
else//找到之前的尾结点，将新结点设置为新尾结点
{
while(p->next != NULL)
p = p->next;
p->next = newp;
}
}
//头插
void List::headInsert(int data)
{
Node *newp;
newp = (Node*)malloc(sizeof(Node));
newp->data = data;
Node *p = head;
if(head == NULL) head = newp;//若链表为空则此结点为头结点
else
{
newp->next = p->next;
p->next = newp;
}
}
//指定位置插入
void List::listInsert(int data, int n)
{
if(n < 1 || n > getLength())
{
printf("输入有误\n");
return ;
}
else
{
Node *temp;
temp = (Node*)malloc(sizeof(Node));
temp->data = data;
Node *p = head;
int i = 1;
while(n > i)//从第1个结点遍历到指定结点
{
p = p->next;
i++;
}
temp->next = p->next;
p->next = temp;
}
}
//删除指定数据
void List::nodeDelete(int data)
{
Node *temp = findNode(data);//找到指定数据位置;
Node *p = head->next;
while(p->next != temp)//遍历到指定结点
p = p->next;
p->next = temp->next;//挤掉
delete temp;//删掉
temp = NULL;
}
//删除第n个结点
void List::findDelete(int n)
{
Node *p = head;
Node *pre = (Node*)malloc(sizeof(Node));
int i = 1;
while(n >= i)
{
i++;
pre = p;
p = p->next;
}
pre->next = p->next;
delete p;
p = NULL;
}
int main()
{
List l1;
int n;
printf("输入链表长度：\n");
cin >> n;
l1.createList(n);
if(l1.isEmpty() == 1) printf("此表为空\n");
else printf("链表长为%d\n", l1.getLength());
int i;
printf("输入查找第几位结点的值\n");
cin >> i;
printf("第%d位结点的值为%d\n", i, l1.searchNode(i));
int data, datap;
printf("输入要要插入的数据与它的位置：\n");
cin >> data >> datap;
l1.listInsert(data, datap);
printf("插入后链表为：\n");
l1.travelList();
int headdata;
printf("输入要在头部插入的值：\n");
cin >> headdata;
l1.headInsert(headdata);
printf("插入后链表为：\n");
l1.travelList();
int taildata;
printf("输入要在尾部插入的值：\n");
cin >> taildata;
l1.endInsert(taildata);
printf("插入后链表为：\n");
l1.travelList();
int deldata;
printf("输入要删除的值：\n");
cin >> deldata;
l1.nodeDelete(deldata);
printf("删除后链表为：\n");
l1.travelList();
int nodel;
printf("输入要删除的结点：\n");
cin >> nodel;
l1.findDelete(nodel);
printf("删除后链表为：\n");
l1.travelList();
return 0;
}
栈
常规栈
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
using namespace std;
//栈的容量
const int SIZE = 5;
template <typename T>
class Stack
{
private:
T *elem;
int top;
public:
Stack()
{
top = -1;
elem = new T(SIZE);
}
~Stack()
{
delete elem;
}
bool push(T x)
{
if (top == SIZE - 1)
return false;
elem[++top] = x;
return true;
}
bool pop()
{
if (top == -1)
return false;
top--;
return true;
}
T head()
{
return (top == -1) ? -1 : elem[top];
}
bool isFull()
{
return (top == SIZE - 1) ? 1 : 0;
}
bool isEmpty()
{
return (top == -1) ? 1 : 0;
}
};
int main()
{
Stack<int> sta;
for (int i = 1; i <= 5; i++)
sta.push(i);
if (sta.isFull())
cout << "The Stack is Full now" << endl;
else
cout << "There's space left" << endl;
cout << "以下是栈内所有元素:\n";
while (!sta.isEmpty())
{
cout << sta.head() << " ";
sta.pop();
}
}
队列
顺序队列
#include <iostream>
#include <cstdio>
using namespace std;
template <typename T>
class SeQueue
{
private:
T *elem;
int rear;
int front;
unsigned int qsize;
public:
SeQueue()
{
rear = 0;
front = 0;
elem = new T(qsize);
}
~SeQueue()
{
delete[] elem;
}
bool Push_SeQueue(T x)
{
if (Full_SeQueue())
return false;
elem[rear++] = x;
return true;
}
T Pop_SeQueue()
{
if (Empty_SeQueue())
return -1;
T tmp = elem[front];
front++;
return tmp;
}
T Front()
{
return front;
}
bool Empty_SeQueue()
{
return (front == rear) ? 1 : 0;
}
bool Full_SeQueue()
{
return (rear == qsize) ? 1 : 0;
}
T Rear()
{
return rear;
}
void setSize(int x)
{
qsize = x;
}
};
int main()
{
SeQueue<int> q;
q.setSize(10);
int data[12] = {7, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12};
for(int i = 0 ; i < 12; i++)
q.Push_SeQueue(data[i]);
int x = q.Pop_SeQueue();
cout << "rear=" << q.Rear() << endl;
cout << "front=" << q.Front() << endl;
return 0;
}
循环队列
#include <bits/stdc++.h>
using namespace std;
class SeQueue
{
private:
int rear, front;
int maxsize;
int *arr;
public:
SeQueue(int size)
{
maxsize = size;
front = rear = 0;
}
~SeQueue()
{
delete []arr;
}
bool Empty_SeQueue();
bool Full_SeQueue();
void Push_SeQueue(int value);
int Pop_SeQueue();
int Get_front();
int Get_rear();
};
bool SeQueue::Empty_SeQueue()
{
return front == rear;
}
bool SeQueue::Full_SeQueue()
{
return abs(rear-front) == maxsize && rear != 0;
}
void SeQueue::Push_SeQueue(int value)
{
if(Full_SeQueue() == false)
{
arr[rear] = value;
rear = (rear+1) % maxsize;
}
}
int SeQueue::Pop_SeQueue()
{
int value = -1;
if(Empty_SeQueue() == false)
{
value = arr[front];
front = (front+1) % maxsize;
}
return value;
}
int SeQueue::Get_front()
{
return front;
}
int SeQueue::Get_rear()
{
return rear;
}
int main()
{
SeQueue q(10);
int data[12] = {7, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12};
for(int i = 0 ; i < 12; i++)
q.Push_SeQueue(data[i]);
int x = q.Pop_SeQueue();
cout << "rear=" << q.Get_rear() << endl;
cout << "front=" << q.Get_front() << endl;
return 0;
}