C++实现数据结构的手动实现

数据结构已经学习过半，是时候自己动手巩固了，图的结构日后补充

1.单链表

#include<iostream>
#include<string>
using namespace std;
struct ListNode
{
	int val;
    ListNode *next;
	ListNode() : val(NULL), next(NULL){}
    ListNode(int x) : val(x), next(NULL){}//初始化链表，可以使用ListNode(x)来开辟一个新节点
};
void Initialize(ListNode *&head){//初始化
	head->val=NULL;
	head->next=NULL;
}
int length(ListNode *head){//获取当前长度
	ListNode *q=head;
	int i=-1;
	while(q!=NULL){
		q=q->next;
		i++;//i为链表长度
	}
	return i;
}
int GetElem(ListNode *head,int index){//获取单链表第index个元素的值
	ListNode *p=head;
	int Elem=-1;//获取不到就返回-1
	int j=0;
	while(p!=NULL && j<index){
		p=p->next;
		j++;
	}
	if(p!=NULL){
		Elem=p->val;
	}
	return Elem;
}

//在链表中的第 index 个节点之前添加值为val的节点
bool addAtIndex(ListNode *&head,int index, int val) {
	if(index>length(head)){
		return false;
	}
	ListNode *p=head;
	ListNode *q=new ListNode(val);
	int j=1;
	while(p!=NULL && j<index){
		p=p->next;
		++j;
	}
	if(p==NULL || j>index){
		return false;
	}
	q->next=p->next;
	p->next=q;
	return true;
}
//如果索引 index 有效，则删除链表中的第 index 个节点。
bool deleteAtIndex(ListNode *&head,int index) {
	ListNode *p=head;
	int j=1;
	while(p!=NULL && j<index){
		p=p->next;
		j++;
	}
	if(p->next!=NULL && p!=NULL){
		ListNode *q=p->next;
		p->next=p->next->next;
		delete q;
		return true;
	}
	return false;
}
void PrintList(ListNode *head){
	ListNode *p=head;
	while(p->next!=NULL){
		p=p->next;
		cout<<p->val<<" ";
	}
	cout<<endl;
}
void CreateListHead(ListNode *(&head),int num){//头插法建表,输入顺序与实际顺序相反
	cout<<"请输入链表元素:";
	for(int i=0;i<num;i++){
		int val;
		cin>>val;
		ListNode *p=new ListNode(val);
		p->next=head->next;
		head->next=p;
	}
}
void CreateListTail(ListNode *(&head),int num){//尾插法建表,输入顺序与实际顺序相同
	ListNode *p=head;//head的尾结点
	cout<<"请输入链表元素:";
	for(int i=0;i<num;i++){
		int val;
		cin>>val;
		ListNode *q=new ListNode(val);
		p->next=q;
		p=q;
	}
	//p->next=NULL;//尾部置空
}
void DeleteList(ListNode *(&head)){//删除整表
	ListNode *p=head;
	ListNode *q=p->next;
	while(q!=NULL){
	delete p;
	p=q;
	q=p->next;
	}
}
int main(){
	ListNode *head=new ListNode;//创造的是带头节点的链表
	Initialize(head);//初始化链表
	int a;
	cout<<"请输入链表元素个数:";
	cin>>a;//需要创造的元素个数
	CreateListTail(head,a);//尾插法建表
	//cout<<head->val;
	//CreateListHead(head,a);//头插法建表
	addAtIndex(head,3,13);//在第3个元素之前插入13
	deleteAtIndex(head,2);//删除第二个元素
	//DeleteList(head);
	PrintList(head);//打印链表
	//cout<<length(head)<<endl;//链表长度
	cout<<GetElem(head,2);//获取链表第二个元素的值
}

2.双链表

#include<iostream>
#include<string>
using namespace std;
struct ListNode
{
	int val;
    ListNode *next,*prev;//prev是前驱指针
	ListNode() : val(), next(NULL),prev(NULL){}
    ListNode(int x) : val(x), next(NULL),prev(NULL){}//初始化链表，可以使用ListNode(x)来开辟一个新节点
};
ListNode* Initialize(){
	ListNode *head=new ListNode;
	head->next=NULL;
	return *&head;
}
int length(ListNode *head){//获取当前长度
	ListNode *q=head;
	int i=-1;
	while(q!=NULL){
		q=q->next;
		i++;//i为链表长度
	}
	return i;
}
int GetElem(ListNode *head,int index){//获取单链表第index个元素的值
	ListNode *p=head;
	int Elem=-1;//获取不到就返回-1
	int j=0;
	while(p!=NULL && j<index){
		p=p->next;
		j++;
	}
	if(p!=NULL){
		Elem=p->val;
	}
	return Elem;
}

//在链表中的第 index 个节点之前添加值为val的节点
bool addAtIndex(ListNode *&head,int index, int val) {
	if(index>length(head)){
		return false;
	}
	ListNode *p=head;
	ListNode *q=new ListNode(val);
	int j=1;
	while(p!=NULL && j<index){
		p=p->next;
		++j;
	}
	if(p==NULL || j>index){
		return false;
	}
	if(p->next!=NULL){
		p->next->prev=q;
	}
	q->next=p->next;
	q->prev=p;
	p->next=q;
	return true;
}
//如果索引 index 有效，则删除链表中的第 index 个节点。
bool deleteAtIndex(ListNode *&head,int index) {
	ListNode *p=head;
	int j=1;
	while(p!=NULL && j<index){
		p=p->next;
		j++;
	}
	if(p->next!=NULL && p!=NULL){
		p->next=p->next->next;
		return true;
	}
	return false;
}
void PrintList(ListNode *head){
	ListNode *p=head;
	while(p->next!=NULL){
		p=p->next;
		cout<<p->val<<" ";
	}
	cout<<endl;
}
void CreateListHead(ListNode *(&head),int num){//头插法建表,输入顺序与实际顺序相反
	cout<<"请输入链表元素:";
	for(int i=0;i<num;i++){
		int val;
		cin>>val;
		ListNode *p=new ListNode(val);
		p->next=head->next;
		if(head->next!=NULL){
			head->next->prev=p;
		}
		head->next=p;
		p->prev=head;
	}
}
void CreateListTail(ListNode *(&head),int num){//尾插法建表,输入顺序与实际顺序相同
	ListNode *p=head;//head的尾结点
	cout<<"请输入链表元素:";
	for(int i=0;i<num;i++){
		int val;
		cin>>val;
		ListNode *q=new ListNode(val);
		p->next=q;
		q->prev=p;
		p=q;
	}
	p->next=NULL;//尾部置空
}
void DeleteList(ListNode *(&head)){//删除整表
	ListNode *p=head;
	ListNode *q=p->next;
	while(q!=NULL){
	delete p;
	p=q;
	q=p->next;
	}
}
int main(){
	ListNode *head=Initialize();//创造的是带头节点的链表
	int a;
	cout<<"请输入链表元素个数:";
	cin>>a;//需要创造的元素个数
	CreateListTail(head,a);//尾插法建表
	//CreateListHead(head,a);//头插法建表
	addAtIndex(head,3,13);//在第3个元素之前插入13
	//deleteAtIndex(head,2);//删除第二个元素
	//DeleteList(head);
	PrintList(head);//打印链表
	cout<<head->next->next->next->next->prev->val;
	//cout<<length(head)<<endl;//链表长度
	//cout<<GetElem(head,2);//获取链表第二个元素的值
}

3.线性表的顺序储存

#include<iostream>
#include<string>
using namespace std;
const int Maxsize=20;
struct List
{
	int data[Maxsize];
	int length;
	List():length(0),data(){};
};
int length(List L){//获取当前长度
	return L.length;
}

bool GetElem(List L,int index,int &Elem){//获取单链表第index个元素的值
	if(index>L.length || L.length==0 || index<1){
		Elem=-1;
		return false;
	}
	Elem=L.data[index-1];
	return true;
}
bool addAtIndex(List *&L,int index,int val) {//在顺序表中的第 index 个节点之前添加值为val的节点
	if(index<1 || index>L->length+1 || L->length==Maxsize){
		return false;
	}
	if(index<=L->length){
		for(int i=L->length-1;i>=index-1;i--){
			L->data[i+1]=L->data[i];
		}
	}
	L->length++;
	L->data[index-1]=val;
	return true;
}
bool DeleteIndex(List *&L,int index){//删除第i个元素
	if(index<1 || index>L->length+1 || L->length==Maxsize){
		return false;
	}
	if(i<=L->length){
		for(int i=index-1;i<L->length;i++){
		L->data[i]=L->data[i+1];
		}
	}
	return true;
}
int main(){
	List *L=new List();
	cout<<L->length;
}

4.栈的顺序储存

#include<iostream>
#include<string>
using namespace std;
const int Maxsize=5;
struct Stack{
	int data[Maxsize];//数据类型可以更改数组大小也可以更改
	int top;//栈顶指针
};
Stack* Initialize(){
	Stack* s1=new Stack;
	s1->top=-1;
	return *&s1;
}
bool push(Stack *mystack,int val){
	if(mystack->top==Maxsize-1){//栈满
	return false;
	}
	mystack->top++;
	mystack->data[mystack->top]=val;
	return true;
}
bool pop(Stack *mystack){
	if(mystack->top==-1){
	return false;
	}
	mystack->top--;
	return true;
}
int top(Stack *mystack){
	if(mystack->top==-1){//栈空
		return NULL;
	}
	return mystack->data[mystack->top];
}
bool empty(Stack *mystack){
	if(mystack->top==-1){
		return true;
	}
	return false;
}
int main(){
	Stack* mystack=Initialize();
	push(mystack,5);
	push(mystack,5);
	push(mystack,5);
	push(mystack,5);
	push(mystack,5);
	push(mystack,5);
	while(!empty(mystack)){
	cout<<top(mystack)<<endl;
	pop(mystack);
	}
	if(empty(mystack)){
	cout<<"nmsl"<<endl;
	}
}

5.栈的链式储存

#include<iostream>
#include<string>
using namespace std;
struct LinkStack{
	int data;//存值
	LinkStack *next;//指向下一个的指针
};
void Initialize(LinkStack *&L1){//初始化
	L1=new LinkStack;
	L1->next=NULL;
}
bool empty(LinkStack *L1){
	if(L1->next==NULL){
		return true;
	}
	return false;
}
void push(LinkStack *&L1,int val){
	LinkStack* p=new LinkStack;
	p->data=val;
	p->next=L1->next;
	L1->next=p;
}
bool pop(LinkStack *&L1){
	if(empty(L1)){
		return false;
	}
	LinkStack *p=L1;
	L1=L1->next;
	delete p;
	return true;
}
int top(LinkStack *&L1){
	if(empty(L1)){
		return NULL;
	}
	return L1->next->data;
}
void DestroyStack(LinkStack *&L1){
	while(!empty(L1)){
	LinkStack *p=L1;
	L1=L1->next;
	delete p;
	}
}
int main(){
	LinkStack *L1;
	Initialize(L1);
	if(empty(L1)){
		cout<<"nmsl!!!!"<<endl;
	}
	push(L1,5);
	push(L1,4);
	push(L1,3);
	push(L1,2);
	push(L1,1);
	pop(L1);
	pop(L1);
	pop(L1);
	pop(L1);
	pop(L1);
	pop(L1);
	pop(L1);
	pop(L1);
	while(!empty(L1)){
		cout<<top(L1)<<endl;
		//cout<<L1->next->data<<endl;
		pop(L1);
	}
	//DestroyStack(L1);
	if(empty(L1)){
		cout<<"nmsl!!!!"<<endl;
	}
}

6.队列的顺序储存

#include<iostream>
#include<string>
using namespace std;
const int Maxsize=20;
struct Queue
{
	int data[Maxsize];
	int tail;
	int head;
};
void Initialize(Queue *&Q){
	Q=new Queue;
	Q->head=-1;
	Q->tail=-1;
}
bool empty(Queue *&Q) {
	if(Q->tail==-1){
		return true;
	}
	return false;
}
bool push(Queue *&Q,int val) {//入队
	if(Q->tail==Maxsize-1){//队满
		return false;
	}
	if(Q->head==-1 && Q->tail==-1){
		Q->head++;
		Q->tail++;
		Q->data[Q->tail]=val;
		return true;
	}
	Q->tail++;
	Q->data[Q->tail]=val;
		return true;
}
bool pop(Queue *&Q){//出队
	if(empty(Q)){//队空
		return false;
	}
	if(Q->head==Q->tail){
		Q->head=-1;
		Q->tail=-1;
		return true;
	}
	Q->head++;
	return true;
}
int front(Queue *&Q){//获得队头元素
	if(empty(Q)){//队空
		return NULL;
	}
	return Q->data[Q->head];
}
int main(){
	Queue *Q;
	Initialize(Q);
	if(empty(Q)){
	cout<<"NMSL"<<endl;
	}
	push(Q,1);
	push(Q,2);
	push(Q,3);
	push(Q,4);
	pop(Q);
	while(!empty(Q)){
		cout<<front(Q)<<endl;
		pop(Q);
	}
	if(empty(Q)){
	cout<<"NMSL"<<endl;
	}
	cout<<Q->head<<endl;
	cout<<Q->tail<<endl;
}

7.队列的链式储存

#include<iostream>
#include<string>
using namespace std;
struct QueueNode
{
	int data;
	QueueNode *next;
};
struct ListQueue{
	QueueNode *tail;
	QueueNode *head;
};
void Initialize(ListQueue *&Q){//初始化
	Q=new ListQueue;
	Q->head=NULL;
	Q->tail=NULL;
}
bool empty(ListQueue *&Q) {//判空
	if(Q->tail==NULL){
		return true;
	}
	return false;
}
void push(ListQueue *&Q,int val) {//入队
	QueueNode *p=new QueueNode;
	p->data=val;
	p->next=NULL;
	if(empty(Q)){//队空时进行插入，队头就是队尾
		Q->head=p;
		Q->tail=p;
	}
	else{
		Q->tail->next=p;//连接到队尾
		Q->tail=p;
	}
}
bool pop(ListQueue *&Q){//出队
	if(empty(Q)){//队空
		return false;
	}
	if(Q->head==Q->tail){
		Q->head=NULL;
		Q->tail=NULL;
		return true;
	}
	QueueNode *p=Q->head;
	Q->head=Q->head->next;
	delete p;
	return true;
}
int front(ListQueue *&Q){//获得队头元素
	if(empty(Q)){//队空
		return NULL;
	}
	return Q->head->data;
}
int main(){
	ListQueue *Q;
	Initialize(Q);
	if(empty(Q)){
		cout<<"NMSL!"<<endl;
	}
	push(Q,1);
	push(Q,2);
	push(Q,3);
	push(Q,4);
	pop(Q);
	while(!empty(Q)){
		cout<<front(Q)<<endl;
		pop(Q);
	}
	if(empty(Q)){
		cout<<"NMSL!"<<endl;
	}
}

8.字符串的模式匹配，见KMP算法

9.二叉树链式存储的七种遍历方法

#include<iostream>
#include<stack>
#include<queue>
using namespace std;
struct TreeNode{
	char data;
	TreeNode *left;//左节点
	TreeNode *right;//右节点
};
void BeforeRecursive(TreeNode *Mytree){//递归前序遍历
	if(Mytree==NULL){
		return;
	}
	cout<<Mytree->data<<" ";
	BeforeRecursive((Mytree->left));
	BeforeRecursive((Mytree->right));
}
void PreBeforeRecursive(TreeNode *Mytree){//非递归前序遍历
	stack<TreeNode *> p;
	while(Mytree!=NULL || !p.empty()){
		while(Mytree!=NULL){
			cout<<Mytree->data<<" ";
			p.push(Mytree);
			Mytree=Mytree->left;
		}
		Mytree=p.top();
		p.pop();
		Mytree=Mytree->right;
	}
}
void MidRecursive(TreeNode *Mytree){//递归中序遍历
	if(Mytree==NULL){
		return;
	}
	MidRecursive((Mytree->left));
	cout<<Mytree->data<<" ";
	MidRecursive((Mytree->right));
}
void PreMidRecursive(TreeNode *Mytree){//非递归中序遍历
	stack<TreeNode *> p;
	while(Mytree!=NULL || !p.empty()){
		while(Mytree!=NULL){
			p.push(Mytree);
			Mytree=Mytree->left;
		}
		Mytree=p.top();
		cout<<Mytree->data<<" ";
		p.pop();
		Mytree=Mytree->right;
	}
}
void AfterRecursive(TreeNode *Mytree){//递归后序遍历
	if(Mytree==NULL){
		return;
	}
	AfterRecursive(Mytree->left);
	AfterRecursive(Mytree->right);
	cout<<Mytree->data<<" ";
}
void PreAfterRecursive(TreeNode *Mytree){//非递归后序遍历
	stack<TreeNode *> p;
	TreeNode *temp=NULL;
	while(Mytree!=NULL || !p.empty()){
		while(Mytree!=NULL){
			p.push(Mytree);
			Mytree=Mytree->left;
		}
		Mytree=p.top();
		if(Mytree->right==NULL || Mytree->right==temp){
			cout<<Mytree->data<<" ";
			temp=Mytree;
			Mytree=NULL;
			p.pop();
		}
		else{
			Mytree=Mytree->right;
		}
	}
}
void LayerRecursive(TreeNode *Mytree){//层序遍历
	queue<TreeNode *> a;
	a.push(Mytree);
	while(!a.empty()){
	int size=a.size();
	for(int i=0;i<size;i++){
		TreeNode *p=a.front();
		a.pop();
		cout<<p->data<<" ";
		if(p->left!=NULL){
			a.push(p->left);
		}
		if(p->right!=NULL){
			a.push(p->right);
		}
	}
	}
	cout<<endl;
}
TreeNode* BuildTree(){
	cout<<"请输入该节点的值:"<<endl;
	char c;
	TreeNode *p;
	cin>>c;
	if(c=='#'){
		return 0;
	}
	p=new TreeNode;;
	p->data=c;
	p->left=BuildTree();
	p->right=BuildTree();
	return p;
}
int main(){
	TreeNode *Mytree=new TreeNode;
	Mytree=BuildTree();
	cout<<"递归前序为:";
	BeforeRecursive(Mytree);
	cout<<endl;
	cout<<"非递归前序为:";
	PreBeforeRecursive(Mytree);
	cout<<endl;
	cout<<"递归中序为:";
	MidRecursive(Mytree);
	cout<<endl;
	cout<<"非递归中序为:";
	PreMidRecursive(Mytree);
	cout<<endl;
	cout<<"递归后序为:";
	AfterRecursive(Mytree);
	cout<<endl;
	cout<<"非递归后序为:";
	PreAfterRecursive(Mytree);
	cout<<endl;
	cout<<"层序为:";
	LayerRecursive(Mytree);
}