回溯法 数据结构
2015-11-06 11:31:53 Novemser 阅读数 1586

列车调度(Train)
Description
Figure 1 shows the structure of a station for train dispatching.

这里写图片描述
Figure 1

In this station, A is the entrance for each train and B is the exit. S is the transfer end. All single tracks are one-way, which means that the train can enter the station from A to S, and pull out from S to B. Note that the overtaking is not allowed. Because the compartments can reside in S, the order that they pull out at B may differ from that they enter at A. However, because of the limited capacity of S, no more that m compartments can reside at S simultaneously.

Assume that a train consist of n compartments labeled {1, 2, …, n}. A dispatcher wants to know whether these compartments can pull out at B in the order of {a1, a2, …, an} (a sequence). If can, in what order he should operate it?

Input
Two lines:

1st line: two integers n and m;

2nd line: n integers separated by spaces, which is a permutation of {1, 2, …, n}. This is a compartment sequence that is to be judged regarding the feasibility.

Output
If the sequence is feasible, output the sequence. “Push” means one compartment goes from A to S, while “pop” means one compartment goes from S to B. Each operation takes up one line.

If the sequence is infeasible, output a “no”.

Example 1
Input

5 2
1 2 3 5 4
Output

push
pop
push
pop
push
pop
push
push
pop
pop
Example 2
Input

5 5
3 1 2 4 5
Output

No
Restrictions
1 <= n <= 1,600,000

0 <= m <= 1,600,000

Time: 2 sec

Memory: 256 MB

95分代码

#include <cstdio>
#include <cstring>
int out[1600010];
char print[3200010][5];
int stack[1600010];
int sHead = 0;

void push( int n )
{
    stack[++sHead] = n;
}

int top()
{
    return stack[sHead];
}

int pop()
{
    return stack[sHead--];
}

int main()
{
    int m, n;
    int op = 0;
    scanf( "%d%d", &n, &m );

    int i;
    for (i = 1; i <= n; i++)
        scanf( "%d", &out[i] );
    int j = 1;
    i = 1;
    while (i <= n)
    {
        if (j <= n && sHead <= m && out[i] >= j)
        {
            push( j++ );
            strcpy( print[op++], "push" );
        }
        else
        {
            if (out[i] == top())
            {
                pop();
                strcpy( print[op++], "pop" );
                i++;
            }
            else
            {
                puts( "No" );
                return 0;
            }
        }
    }

    for (int k = 0; k < op; k++)
    {
        puts( print[k] );
    }
}
2016-09-07 22:49:23 Robot__Man 阅读数 7232

计算机程序设计 = 数据结构 + 算法
数据结构研究变量的管理方式,算法研究解决特定问题的方法。
数据结构分三个层次:逻辑结构(抽象层)、物理结构(结构层)、运算结构(实现层)。

1.1 数据结构的逻辑结构

逻辑结构指人对数据之间关系的理解和看法,逻辑结构和计算机无关。
逻辑结构:
1、集合结构:这种结构表示数据可以合并成一个整体。
  这是数据之间关系最弱的一种,就仅比那个一点关系都没有的强一点。
2、线性结构:这种结构中数据之间有一对一的关系(如排队)。
3、树型结构:这种结构中数据之间有一对多的关系,这个关系称为父子关系(典型的如细胞分裂)。
4、网状结构:这种结构中数据之间有多对多的交叉映射关系。

(我们主要研究线性结构和树型结构。)

1.2 数据结构的物理结构

物理结构描述计算机内部数据之间实际的关系。
物理结构:
1、顺序结构:结构中的数据元素存放在一段连续的内存空间中,典型代表就是数组。随机访问方便,插入删除复杂。
2、链式结构:这种结构中不同的数据被存储在计算机里不同的地方,他们的物理位置之间完全没有关系。链式结构由多个节点构成,每个节点中包括有效数据和至少一个指针变量。
对链式结构进行操作时,如果不会修改结构则使用一级指针变量就可以了,如果会修改结构则需要使用二级指针变量,其实,一级指针变量也可以修改链式结构。
链式结构适合进行插入删除操作,不适合进行随机访问。

/*链式结构练习*/
#include <stdio.h>

typedef struct node{
    int num;
    struct node *p_next;//void *p_next;
}node;
node node1 = {1,NULL};

int main(){
    node *p_head = NULL;//头指针
    node node2 = {2,NULL};
    static node node3 = {3,NULL};
    node node5 = {5,NULL};//新添一个节点,把它加入链表中

    p_head = &node1;
    node1.p_next = &node2;
    node2.p_next = &node3;
    //用二级指针把新增节点5挂上去
    /*node **pp_tmp = &p_head;
    while (*pp_tmp){
        pp_tmp = &((*pp_tmp)->p_next);
    }
    *pp_tmp = &node5;*/

    //第二种把新增节点5加进去的方法
    node *p_tmp = NULL;
    if (p_head){
        p_tmp = p_head;
        while (p_tmp->p_next){
            p_tmp = p_tmp->p_next;
        }
        p_tmp->p_next = &node5;
    }
    else {
        p_head = &node5;
    }
   //显示所有节点数据
    p_tmp = p_head;
    while (p_tmp){
        printf("%-3d",p_tmp->num);
        p_tmp = p_tmp->p_next;
    }
    printf("\n");
    return 0;
}

逻辑结构可以采用多种物理结构实现,它们之间没有明确的一对一的关系。

1.3 数据结构的运算结构

数据结构的基本操作(运算结构):
1、创建/销毁
  分配资源、建立结构、释放资源
2、插入/删除
  增加、减少数据元素
3、获取/修改
  遍历、迭代、随机访问
(增删改查)
4、排序/查找
  算法应用

2017-08-11 11:54:52 LiuJiuXiaoShiTou 阅读数 669

查看原文点击链接即可

0. 数据结构图文解析系列

数据结构系列文章
数据结构图文解析之:数组、单链表、双链表介绍及C++模板实现
数据结构图文解析之:栈的简介及C++模板实现
数据结构图文解析之:队列详解与C++模板实现
数据结构图文解析之:树的简介及二叉排序树C++模板实现.
数据结构图文解析之:AVL树详解及C++模板实现
数据结构图文解析之:二叉堆详解及C++模板实现
数据结构图文解析之:哈夫曼树与哈夫曼编码详解及C++模板实现
数据结构图文解析之:直接插入排序及其优化(二分插入排序)解析及C++实现

回到顶部

 

 

数据结构图文解析之:数组、单链表、双链表介绍及C++模板实现

阅读目录

 

数据结构图文解析之:栈的简介及C++模板实现

阅读目录

数据结构图文解析之:队列详解与C++模板实现

阅读目录

 

 

数据结构图文解析之:树的简介及二叉排序树C++模板实现.

阅读目录

数据结构图文解析之:AVL树详解及C++模板实现

阅读目录

数据结构图文解析之:二叉堆详解及C++模板实现

阅读目录

数据结构图文解析之:哈夫曼树与哈夫曼编码详解及C++模板实现

阅读目录

 

2018-02-28 10:23:23 qq_33733970 阅读数 382
什么是数据结构?

数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成。简单来说,数据结构就是设计数据以何种方式组织并存储在计算机中。

数据结构的分类

数据结构按照其逻辑结构可分为线性结构、树结构、图结构

线性结构:数据结构中的元素存在一对一的相互关系
树结构:数据结构中的元素存在一对多的相互关系
图结构:数据结构中的元素存在多对多的相互关系

栈(Stack)是一个数据集合,可以理解为只能在一端进行插入或删除操作的列表。
栈的特点:后进先出(last-in, first-out)
栈的基本操作:

进栈(压栈):push
出栈:pop
取栈顶:gettop

栈的Python实现:

不需要自己定义,使用列表结构即可。
1.进栈函数:append
2.出栈函数:pop
3.查看栈顶函数:li[-1]

链表

链表中每一个元素都是一个对象,每个对象称为一个节点,包含有数据域key和指向下一个节点的指针next。通过各个节点之间的相互连接,最终串联成一个链表。
节点定义:

class Node(object):    
    def __init__(self, item):        
        self.item = item        
        self.next = None

建立链表

头插法:
尾插法:

双链表

双链表中每个节点有两个指针:一个指向后面节点、一个指向前面节点。

哈希表(Hash Table,又称为散列表),是一种线性表的存储结构。哈希表由一个顺序表(数组)和一个哈希函数组成。哈希函数h(k)将元素k作为自变量,返回元素的存储下标。

解决哈希冲突——拉链法

拉链法:哈希表每个位置都连接一个链表,当冲突发生时,冲突的元素将被加到该位置链表的最后。

哈希表在Python中的应用:

字典与集合都是通过哈希表来实现的;

二叉树:

二叉树的链式存储:将二叉树的节点定义为一个对象,节点之间通过类似链表的链接方式来连接。
节点定义:

class BiTreeNode:    
    def __init__(self, data): 
        self.data = data
        self.lchild = None
        self.rchild = None

待补充~

2017-12-02 22:58:18 m0_38128121 阅读数 457

传统上数据结构分为逻辑结构和物理结构
逻辑结构:就是数据对象中数据元素之间的相互关系

四大逻辑结构

集合结构:集合结构中的数据元素除了在同属于一个集合外没有别的其他关系

线性结构:线性结构中的数据元素之间的关系是一对一的关系

树形结构:树形结构中的数据元素存在一种一对多的层次关系

图形结构:图形结构中的元素是多对多的关系
这里写图片描述

物理结构:数据的逻辑结构在计算机中的存储形式
数据元素的存储方式有两种 : 顺序存储 链式存储

顺序存储:把数据单元放在地址连续的存储单元里,数据的逻辑关系和物理关系是一致的
链式存储:把数据元素存放在任意的存储单元里,这组存储单元可以是连续的可以是不连续的
这里写图片描述
图片从小甲鱼数据结构视频上面截取下来的 如有侵权 请联系我

如何理解数据结构

阅读数 302

没有更多推荐了,返回首页