当前位置：首页 › 做题 › 几大基础DS模板的C++实现

几大基础DS模板的C++实现

做题 • 728 • 0

edisoncgh 4年前

正文索引 [隐藏]

链表
常规链表
栈
常规栈
队列
顺序队列
循环队列

数据结构的学习马上就会告一段落，这里打算用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;
}

2 赏

请作者吃个鸡腿！

作者尚未添加打赏二维码！

‹ 上一篇

下一篇 ›

几大基础DS模板的C++实现

链表

常规链表

栈

常规栈

队列

顺序队列

循环队列

作者尚未添加打赏二维码！

相关文章

评论

with sifour for:

文章

最近访客

评论