首页 > 编程语言 >C++常用数据结构

C++常用数据结构

时间：2023-06-18 23:23:49浏览次数：42  
标签：node 常用 ListNode temp int void C++ next 数据结构

数据结构

1. 线性表

由n个具有相同性质的数据元素

image

1.1 顺序表(数组)

定义：用一组地址连续的存储单元依次存储线性表中每个数据元素

特点：逻辑关系相邻的两个元素在物理位置上也相邻

# c++实现
template<typename T>
class sqlist{
    public:
    sqlist(int maxsize=10):Maxsize(maxsize)
    {
        elements=new T[maxsize];
        length=0;
    }
    private:
    int Maxsize;//最大容量
    T *elements;//元素初始地址
    int length;//当前有效长度
}

基本操作

# 初始化顺序表

//初始化顺序表，表的长度设置为0
void InitList(SqList *L)
{
    L->length=0;
}

# 求顺序表中当前元素的个数
//顺序表的长度
int ListLength(SqList * L)
{
    return  L->length;
}


# 判断顺序表是否为空
//判断顺序表是否为空
bool ListEmpty(SqList *L)
{
    if(L->length==0)
        return true;
    else
        return false;
}


# 向顺序表中插入数据元素
//向顺序表中插入数据元素
bool ListInsert(SqList *L,int pos,int item)
{
    int i;
    if(L->length==LISTSIZE)
    {
        printf("顺序列表已满，无法进行插入操作");
        return false;
    }
    if(pos<1||pos>L->length+1)
    {
        printf("插入位置不合法");
        return false;
    }
    for(i=L->length-1;i>=pos-1;i--)
    {
        L->items[i+1]=L->items[i];
    }
    L->items[pos-1]=item;
    L->length++;
 
    return true;
 
}

# 删除顺序表中的元素
bool ListDelete(SqList *L,int pos,int *item)
{
    int i;
    if(L->length==0)
    {
        printf("顺序表为空表");
        return false;
    }
    if(pos<1||pos>L->length)
    {
        printf("删除位置无效");
    }
    *item=L->items[pos-1];
    for(int i=pos-1;i<L->length-1;i++)
    {
        L->items[i]=L->items[i+1];
    }
    L->length--;
    return true;
}

# 查找制定元素在顺序表中的位置
int Find(SqList L,int item)
{
    int pos=0;
    if(ListEmpty(&L))
    {
        printf("顺序表为空表，无法进行查找操作");
        return 0;
    }
    while(pos<L.length&&L.items[pos]!=item)
    {
        pos++;
    }
    if(pos<L.length)
        return pos+1;
    else
        return 0;
}


# //获得顺序表中指定位置上的数据元素
int GetElem(SqList *L,int pos,int *item)
{
    if(ListEmpty(L))
        return 0;
    if(pos<1||pos>L->length)
        return 0;
    *item=L->items[pos-1];
    return 1;
}


# //遍历顺序表
void TravereList(SqList *L)
{
    int pos =0;
    while(pos<L->length)
    {
        printf("item1: %d",L->items[pos]);
        pos++;
    }
}

C++版本

#include <iostream>
using namespace std;
class ListNode{
	public:		
		ListNode * next;
		int data;
};
class LinkList
{
public:
	LinkList()
	{
		node=new ListNode;
		node->next=NULL;
	}
	~LinkList()
	{
		delete node;
	}
	void CreateLinkListBack(int n);
	void CreateLinkListHead(int n);
	void InsertNode(int position,int elem);
	void removeNode(ListNode* p); 
	ListNode* findNode(int value);
	void PrintLinkList();
public:
		ListNode *node;
};
//头插 
void LinkList::CreateLinkListHead(int n)
{
	while(n--)
	{
		//插入的数据 
		ListNode* l=new ListNode;
		cin>>l->data;
		l->next=node->next;
		node->next=l;
	}
}
//尾插 
void LinkList::CreateLinkListBack(int n)
{
	ListNode* r=node;
	while(n--)
	{
		ListNode* l=new ListNode;
		cin>>l->data;
		l->next=NULL;
		r->next=l;
		r=l;
	}
	
}
//在第i个位置插入元素 
void LinkList::InsertNode(int position,int elem)
{
	int j;
	ListNode* p=node->next;
	for(j=1;j<position-1;j++)
	{
		p=p->next;
		if(p==NULL)
			break;
	}
	if(p==NULL &&j<(position-1))
		return ;
//	while(p)
//	{
//		j++;
//		if(j==position)
//			break;
//		p=p->next;
//	}
	ListNode* q=new ListNode;
	q->data=elem;
	q->next=p->next;
	p->next=q;
}
//移除节点 
void LinkList::removeNode(ListNode* p)
{
	if(p==NULL)
		return;
	ListNode* temp=node;
	while(temp->next!=p)
	{
		temp=temp->next;		
	}
	temp->next=p->next;
	delete p;
}
//寻找某节点 
ListNode* LinkList::findNode(int value)
{
	ListNode* temp=node->next;
	while(temp)
	{
		if(temp->data==value)
			return temp;
		temp=temp->next;
	}
	return NULL;
	
}
//打印链表 
void LinkList::PrintLinkList()
{
	ListNode* temp=node->next;
	while(temp)
	{
		cout<<temp->data<<"->";
		temp=temp->next;
	}
	std::cout<<std::endl;
}
 
int main()
{
	LinkList list;
	list.CreateLinkListHead(5);
	list.PrintLinkList();
	list.InsertNode(4,9);
	list.PrintLinkList();
	ListNode* address=list.findNode(2);
	list.removeNode(address);
	list.PrintLinkList();
	return 0;
}

1.2 链表

定义：用一组任意的存储单元存储线性表中的数据元素

特点：

相比顺序存储结构，链式存储结构中，除了需要存储数据元素信息之外，还需要存储它的后继元素的存储地址(指针)。
单链表结点的物理位置不一定连续，单链表逻辑上通过指针实现连续。
单链表有一个头结点和一个尾结点，并且只有尾结点没有后继结点，其他结点有且仅有一个后继结点。
只要知道了链表的头结点，就可以遍历整个链表。

c++定义

class ListNode{
	public:		
		ListNode * next;
		int data;
};
class LinkList
{
public:
	LinkList()
	{
		node=new ListNode;
		node->next=NULL;
	}
	~LinkList()
	{
		delete node;
	}
	void CreateLinkListBack(int n);
	void CreateLinkListHead(int n);
	void InsertNode(int position,int elem);
	void removeNode(ListNode* p); 
	ListNode* findNode(int value);
	void PrintLinkList();
public:
		ListNode *node;
};

C++版本

#include <iostream>
using namespace std;
class ListNode{
	public:		
		ListNode * next;
		int data;
};
class LinkList
{
public:
	LinkList()
	{
		node=new ListNode;
		node->next=NULL;
	}
	~LinkList()
	{
		delete node;
	}
	void CreateLinkListBack(int n);
	void CreateLinkListHead(int n);
	void InsertNode(int position,int elem);
	void removeNode(ListNode* p); 
	ListNode* findNode(int value);
	void PrintLinkList();
public:
		ListNode *node;
};
//头插 
void LinkList::CreateLinkListHead(int n)
{
	while(n--)
	{
		//插入的数据 
		ListNode* l=new ListNode;
		cin>>l->data;
		l->next=node->next;
		node->next=l;
	}
}
//尾插 
void LinkList::CreateLinkListBack(int n)
{
	ListNode* r=node;
	while(n--)
	{
		ListNode* l=new ListNode;
		cin>>l->data;
		l->next=NULL;
		r->next=l;
		r=l;
	}
	
}
//在第i个位置插入元素 
void LinkList::InsertNode(int position,int elem)
{
	int j;
	ListNode* p=node->next;
	for(j=1;j<position-1;j++)
	{
		p=p->next;
		if(p==NULL)
			break;
	}
	if(p==NULL &&j<(position-1))
		return ;
//	while(p)
//	{
//		j++;
//		if(j==position)
//			break;
//		p=p->next;
//	}
	ListNode* q=new ListNode;
	q->data=elem;
	q->next=p->next;
	p->next=q;
}
//移除节点 
void LinkList::removeNode(ListNode* p)
{
	if(p==NULL)
		return;
	ListNode* temp=node;
	while(temp->next!=p)
	{
		temp=temp->next;		
	}
	temp->next=p->next;
	delete p;
}
//寻找某节点 
ListNode* LinkList::findNode(int value)
{
	ListNode* temp=node->next;
	while(temp)
	{
		if(temp->data==value)
			return temp;
		temp=temp->next;
	}
	return NULL;
	
}
//打印链表 
void LinkList::PrintLinkList()
{
	ListNode* temp=node->next;
	while(temp)
	{
		cout<<temp->data<<"->";
		temp=temp->next;
	}
	std::cout<<std::endl;
}
 
int main()
{
	LinkList list;
	list.CreateLinkListHead(5);
	list.PrintLinkList();
	list.InsertNode(4,9);
	list.PrintLinkList();
	ListNode* address=list.findNode(2);
	list.removeNode(address);
	list.PrintLinkList();
	return 0;
}

2. 栈

定义：栈（stack）是一种元素满足后进先出（Last in first out， LIFO）规则的线性表。

特点：

  • 栈的本质是一种线性表， 但是具有其特殊的操作要求——元素后进先出。这种要求也决定了栈的操作是在表尾进行
  • 栈底（bottom）：栈的表头
  • 栈顶（top）：将栈的表尾，所以栈的所有操作都是在栈顶进行的。
  • 添加元素，称为入栈（push）；删除元素，称为出栈（pop）

栈可以用顺序存储实现，也可以用链式存储实现，分别成为顺序栈和链栈。但一般使用顺序存储实现，因为栈不允许在栈中间进行插入和删除，需要准寻栈特有的规则。

动态实现

typedef struct SqStack_dynamic{
	int* base;//栈底 
	int* top;//栈顶 
}SqStack_dynamic;

静态实现

typedef struct SqStack_static{
	int data[Maxsize];
	int top;//栈顶 
}SqStack_static;

c++实现

class stack_static{
	public:
		stack_static()
		{
			MaxSize=10;
			top=0;	
			data= new int[MaxSize];				
		}
		void push(int e);
		void pop(int &e);
		void GetTop(int &e);
	private:
		int MaxSize;
		int top;
		int *data;
};

3.树

标签：node,常用,ListNode,temp,int,void,C++,next,数据结构
From： https://www.cnblogs.com/zhanglanhua/p/17489982.html

相关文章

  • 现代C++学习指南-类型系统
    在前一篇，我们提供了一个方向性的指南，但是学什么，怎么学却没有详细展开。本篇将在前文的基础上，着重介绍下怎样学习C++的类型系统。写在前面在进入类型系统之前，我们应该先达成一项共识——尽可能使用C++的现代语法。众所周知，出于兼容性的考虑，C++中很多语法都是合法的。但是随着新......
  • #yyds干货盘点#C++命名空间
    命名空间命名空间是C++语言的新特性，它能够解决命名冲突问题。例如，小明定义了一个函数swap()，C++标准程序库中也存在一个swap()函数。此时，为了区分调用的是哪个swap()函数，可以通过命名空间进行标识。C++中的命名空间包括两种，具体介绍如下。usingnamespacestd;1.标准命名空间std是C+......
  • C++17特性
    构造函数模板推导在C++17前构造一个模板类对象需要指明类型：pair<int,double>p(1,2.2);//beforec++17C++17就不需要特殊指定，直接可以推导出类型，代码如下：pairp(1,2.2);//c++17自动推导vectorv={1,2,3};//c++17结构化绑定1.获取值//绑定tuplestd::tupl......
  • C++练习题
    多态判断Q1:虚函数可以是内联的？A1:错误。内联是编译时刻决定的，虚函数是运行时刻动态决定的，所以虚函数不能是内联函数。虚函数前加上inline不会报错，但是会被忽略。Q2:一个类内部，可以同时声明staticvoidfun()和virutalvoidfun()两个函数？A2:错误。虽然静态函数......
  • C++面试八股文：什么是RAII？
    C++面试八股文：什么是RAII？某日二师兄参加XXX科技公司的C++工程师开发岗位第13面：面试官：什么是RAII？二师兄：RAII是ResourceAcquisitionIsInitialization的缩写。翻译成中文是资源获取即初始化。面试官：RAII有什么特点和优势？二师兄：主要的特点是，在对象初始化时获取资源，在对......
  • C++基础知识总结
    2023/6/18本篇章记录学习过程C++的基础概念和代码测试实现，还有很多需要补充。一是还不清楚，二是还没有学到。打算学习过程中后面再做补充。先看完《C++primer》书之后再慢慢来添加补充1.函数重载一个函数名可以实现多个功能，这取决于函数参数不同来实现判断对应的功能，与返回......
  • C++面试八股文：std::string是如何实现的？
    某日二师兄参加XXX科技公司的C++工程师开发岗位第18面：面试官：std::string用过吧？二师兄：当然用过（废话，C++程序员就没有没用过std::string的）。面试官：std::string("hello")+"world"、"hello"+std::string("world")和std::string("hello")+std::string("world")的......
  • C++面试八股文：std::string是如何实现的？
    某日二师兄参加XXX科技公司的C++工程师开发岗位第18面：面试官：std::string用过吧？二师兄：当然用过（废话，C++程序员就没有没用过std::string的）。面试官：std::string("hello")+"world"、"hello"+std::string("world")和std::string("hello")+std::string("world")的......
  • 【UE数据传输】UE常用数据格式
    一.Json                           未完待续..........
  • C++构造函数
    RAIIResourceAcquisitionIsInitialization,资源获取即初始化这是一种解决资源管理问题的方法,将资源的有效期与持有资源的对象的生命期严格绑定，由对象的构造函数完成资源的分配，由析构函数完成资源的释放C++借助构造函数和析构函数,解决了传统的malloc&free和new&de......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99