数据结构整理总结

本文主要是介绍数据结构整理总结，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

双链表

List

begin()和end()：

通过调用list容器的成员函数begin()得到一个指向容器起始位置的iterator，可以调用list容器的 end() 函数来得到list末端下一位置，相当于：int a[n]中的第n+1个位置a[n]，实际上是不存在的，不能访问，经常作为循环结束判断结束条件使用。

push_back() 和push_front()：

使用list的成员函数push_back和push_front插入一个元素到list中。其中push_back()从list的末端插入，而 push_front()实现的从list的头部插入。

empty()：

利用empty() 判断list是否为空。

front()和back()

pop_back和pop_front()

reverse()：

通过reverse()完成list的逆置。

merge()：

合并两个链表并使之默认升序(也可改)，l1.merge(l2，greater()); 调用结束后l2变为空，l1中元素包含原来l1 和 l2中的元素，并且排好序，降序。另外greater()是可以变的，也可以不按升序排列（比如用在结构体排列）

bool listsort(int a,int b){
	if(a>b)
		return true;
	return false;
}
int main ()
{
    list<int> IntList;
    list<int> IntList2(3,5);
    for( int i=0; i < 10; i++ )
    	IntList.push_front( i);
    IntList.merge(IntList2, listsort);
    for(iter=IntList.begin();iter!=IntList.end();iter++){
    	cout<<*iter<< " ";
    }
	cout<<endl;
	return 0;
}

insert()：

在指定位置插入一个或多个元素(三个重载)：

l1.insert(l1.begin(),100); 在l1的开始位置插入100。
l1.insert(l1.begin(),2,200); 在l1的开始位置插入2个100。
l1.insert(l1.begin(),l2.begin(),l2.end());在l1的开始位置插入l2的从开始到结束的所有位置的元素。

栈

Stack

出栈：push()

压栈：pop()

栈是否为空：empty()

栈的大小：size()

访问栈顶：top()

队列

代码实现

#include <iostream>
#define elemtype int
#define MAX 10
using namespace std;
struct Queue
{
    elemtype q[MAX];
    int front = 0;
    int rear = 0;
};
//判断队列是否满
bool isfull(Queue Q)
{
    if ((Q.rear + 1) % MAX == Q.front)
    {
        return true;
    }
    else
    {
        return false;
    }
}
// 销毁队列
void destroy(Queue &Q)
{
    delete &Q;
    cout << "DESTROYED" << endl;
}
// 清空队列
void erase(Queue &Q)
{
    Q.front = 0;
    Q.rear = 0;
    cout << "ERASED" << endl;
}

// 获取队列队头元素
elemtype Qhead(Queue Q)
{
    return Q.q[Q.front];
}
// 在队尾插入元素
void Qenter(Queue &Q, elemtype n)
{
    if (isfull(Q))
    {
        cout << "QUENE IS FULL" << endl;
    }
    else
    {
        Q.q[Q.rear] = n;
        Q.rear = (Q.rear + 1) % MAX;
        cout << "ENTERED" << endl;
    }
}
// 删除队头元素
elemtype Qdelete(Queue &Q)
{
    if (Qlenth(Q) == 0)
    {
        cout << "QUENE IS EMPTY" << endl;
        return -1;
    }
    else
    {
        int result = Q.front;
        Q.front = (Q.front + 1) % MAX;
        cout << "DELETED" << endl;
        return Q.q[result];
    }
}

Queue

back()返回最后一个元素

empty()如果队列空则返回真

front()返回第一个元素

pop()删除第一个元素

push()在末尾加入一个元素

size()返回队列中元素的个数

排序

sort()

sort函数的模板有三个参数：

void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);

（1）第一个参数first：是要排序的数组的起始地址。

（2）第二个参数last：是结束的地址（最后一个数据的后一个数据的地址）

（3）第三个参数comp是排序的方法：可以是从升序也可是降序。如果第三个参数不写，则默认的排序方法是从小到大排序。

struct node
{
    int data;
};
bool cmp(node a, node b)
{
    return a.data > b.data;//从大到小
}

树与二叉树

二叉树

//BinaryTree
struct Tree
{
    char data;
    Tree *lchild;
    Tree *rchild;
};
//先序遍历二叉树
void PreOrder(Tree *T)
{
    if (T != NULL)
    {
        cout << T->data << ' ';
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
}
//按层遍历二叉树
void LevelOrder(Tree *T)
{
    queue<Tree *> Q;
    Q.push(T);
    while (!Q.empty())
    {
        Tree *t = Q.front();
        Q.pop();
        cout << t->data << ' ';
        if (t->lchild != NULL)
        {
            Q.push(t->lchild);
        }
        if (t->rchild != NULL)
        {
            Q.push(t->rchild);
        }
    }
}
//复制二叉树
Tree* Tcopy(Tree *T)
{
    if (T == NULL)
    {
        return NULL;
    }
    else
    {
        Tree *copy = new Tree;
        copy->data = T->data;
        copy->lchild=Tcopy(T->lchild);
        copy->rchild=Tcopy(T->rchild);
        return copy;
    }
}
//统计结点数
int Tcount_node(Tree*T)
{
    if(T==NULL)
    {
        return 0;
    }
    else
    {
        return Tcount_node(T->lchild) + Tcount_node(T->rchild) + 1;
    }
}
//统计叶子数
int Tcount_leaf(Tree*T)
{
    if(T==NULL)
    {
        return 0;
    }
    if(T->lchild==NULL&&T->rchild==NULL)
    {
        return 1;
    }
    else
    {
        return Tcount_leaf(T->lchild) + Tcount_leaf(T->rchild);
    }
}

散列表

结构体用map重载<运算符，结构体用unordered_map重载==运算符

unordered_map

unordered_map的迭代器是一个指针，指向这个元素，通过迭代器来取得它的值。

1 unordered_map<Key,T>::iterator it;
2 (*it).first;             // the key value (of type Key)
3 (*it).second;            // the mapped value (of type T)
4 (*it);                   // the "element value" (of type pair<const Key,T>) 
它的键值分别是迭代器的first和second属性。 

1 it->first;               // same as (*it).first   (the key value)
2 it->second;              // same as (*it).second  (the mapped value) 
成员函数：
=================迭代器========================= 
begin 　　返回指向容器起始位置的迭代器（iterator） 
end 　　   返回指向容器末尾位置的迭代器 
cbegin　   返回指向容器起始位置的常迭代器（const_iterator） 
cend 　　 返回指向容器末尾位置的常迭代器 
=================Capacity================ 
size  　　 返回有效元素个数 
max_size  返回 unordered_map 支持的最大元素个数 
empty        判断是否为空 
=================元素访问================= 
operator[]  　　   访问元素 
at  　　 　　　　访问元素 
=================元素修改================= 
insert  　　插入元素 
erase　　   删除元素 
swap 　　   交换内容 
clear　　   清空内容 

int main()  
{  
	//注意：C++11才开始支持括号初始化
    unordered_map<int, string> myMap={{ 5, "张大" },{ 6, "李五" }};//使用{}赋值
    myMap[2] = "李四";  //使用[ ]进行单个插入，若已存在键值2，则赋值修改，若无则插入。
    myMap.insert(pair<int, string>(3, "陈二"));//使用insert和pair插入
  
	//遍历输出+迭代器的使用
    auto iter = myMap.begin();//auto自动识别为迭代器类型unordered_map<int,string>::iterator
    while (iter!= myMap.end())
    {  
        cout << iter->first << "," << iter->second << endl;  
        ++iter;  
    }  
	
	//查找元素并输出+迭代器的使用
    auto iterator = myMap.find(2);//find()返回一个指向2的迭代器
    if (iterator != myMap.end())
	    cout << endl<< iterator->first << "," << iterator->second << endl;  
    system("pause");  
    return 0;  
}  

map

begin() 返回指向map头部的迭代器

clear(） 删除所有元素

count() 返回指定元素出现的次数

empty() 如果map为空则返回true

end() 返回指向map末尾的迭代器

erase() 删除一个元素

find() 查找一个元素

lower_bound() 返回键值>=给定元素的第一个位置

rbegin() 返回一个指向map尾部的逆向迭代器

rend() 返回一个指向map头部的逆向迭代器

size() 返回map中元素的个数

upper_bound() 返回键值>给定元素的第一个位置

要判定一个数据（关键字）是否在map中出

第一种：用count函数来判定关键字是否出现，其缺点是无法定位数据出现位置,由于map的特性，一对一的映射关系，就决定了count函数的返回值只有两个，要么是0，要么是1，出现的情况，当然是返回1了

第二种：用find函数来定位数据出现位置，它返回的一个迭代器，当数据出现时，它返回数据所在位置的迭代器，如果map中没有要查找的数据，它返回的迭代器等于end函数返回的迭代器。

优先队列

在优先队列中，优先级高的元素先出队列。
标准库默认使用元素类型的<操作符来确定它们之间的优先级关系。

priority_queue<int>q;

把元素从小到大输出

这时我们可以传入一个比较函数

priority_queue<int, vector<int>, greater<int> >q;

自定义优先级

通过自定义operator<操作符来比较元素中的优先级

struct node
{
    friend bool operator< (node n1, node n2)
    {
        return n1.priority < n2.priority;
    }
    int priority;
    int value;
};

在该结构中，value为值，priority为优先级。

并查集

初始化

int fa[MAXN];
inline void init(int n)
{
    for (int i = 1; i <= n; ++i)
        fa[i] = i;
}

查询

int find(int x)
{
    if(fa[x] == x)
        return x;
    else
        return find(fa[x]);
}

合并（路径压缩）

int find(int x)
{
    if(x == fa[x])
        return x;
    else{
        fa[x] = find(fa[x]);  //父节点设为根节点
        return fa[x];         //返回父节点
    }
}

图

dijkstra算法(最短路径)

#include <bits/stdc++.h>
#define INF 1000000
using namespace std;
int flag[1010];
int dis[1010];
int graph[1010][1010];
int n;
void dijkstra()
{
    memset(flag, 0, sizeof(flag));
    for (int i = 1; i <= n; i++)
    {
        dis[i] = INF;
    }
    dis[1]= 0;
    for (int i = 1; i <= n; i++)
    {
        int find, min = INF;
        for (int j = 1; j <= n; j++)
        {
            if (!flag[j] && dis[j] <= min)
            {
                min = dis[j];
                find = j;
            }
        }
        flag[find] = 1;
        for (int j = 1; j <= n; j++)
        {
            if (dis[j] > dis[find] + graph[find][j])
            {
                dis[j] = dis[find] + graph[find][j];
            }
        }
    }
}
int main()
{
    int m;
    cin >> n >> m;
    memset(graph, INF, sizeof(graph));
    for (int i = 0; i < m; i++)
    {
        int x, y, d;
        cin >> x >> y >> d;
        if (d < graph[x][y])
        {
            graph[x][y] = graph[y][x] = d;
        }
    }
    dijkstra();
    if (dis[n] != INF)
    {
        cout << dis[n]<<endl;
    }
    else
    {
        cout << "-1" << endl;
    }
    return 0;
}

prime算法（最小生成树）

#include <iostream>
#include <fstream>
using namespace std;

#define MAX 100
#define MAXCOST 0x7fffffff

int graph[MAX][MAX];

int prim(int graph[][MAX], int n)
{
    int lowcost[MAX];
    int mst[MAX];
    int i, j, min, minid, sum = 0;
    for (i = 2; i <= n; i++)
    {
        lowcost[i] = graph[1][i];
        mst[i] = 1;
    }
    mst[1] = 0;
    for (i = 2; i <= n; i++)
    {
        min = MAXCOST;
        minid = 0;
        for (j = 2; j <= n; j++)
        {
            if (lowcost[j] < min && lowcost[j] != 0)
            {
                min = lowcost[j];
                minid = j;
            }
        }
        cout << "V" << mst[minid] << "-V" << minid << "=" << min << endl;
        sum += min;
        lowcost[minid] = 0;
        for (j = 2; j <= n; j++)
        {
            if (graph[minid][j] < lowcost[j])
            {
                lowcost[j] = graph[minid][j];
                mst[j] = minid;
            }
        }
    }
    return sum;
}

这篇关于数据结构整理总结的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！