文档章节

【数据结构】回顾表、栈、队列

NoMasp
 NoMasp
发布于 2015/09/08 21:46
字数 1042
阅读 11
收藏 0

1.如何通过调整链而不是数据来交换两个相邻的元素?

    // 单向链表
    Node *p,*afterp;
    p=beforep->next;
    afterp=p->next;

    p->next=afterp->next;
    beforep->next=afterp;
    afterp->next=p;

    // 双向链表
    Node *beforep,*afterp;
    beforep=p->prev;
    afterp=p->next;

    p->next=afterp->next;
    beforep->next=afterp;
    afterp->next=p;
    p->next->prev=p;
    p->prev=afterp;
    afterp->prev=beforep;

2.如何求出两个已排序的表L1和L2的交集和并集。

// 交集
template <typename Object>
list<Object> intersection( const list<Object> & L1,
const list<Object> & L2)
{
    list<Object> intersect;
    typename list<Object>:: const_iterator iterL1 = L1.begin();
    typename list<Object>:: const_iterator iterL2 = L2.begin();
    while(iterL1 != L1.end() && iterL2 != L2.end())
    {
        if (*iterL1 == *iterL2)
        {
            intersect.push_back(*iterL1);
            iterL1++;
            iterL2++;
        }
        else if (*iterL1 < *iterL2)
            iterL1++;
        else
            iterL2++;
    }
    return intersect;
}
// 并集
// Assumes both input lists are sorted
template <typename Object>
list<Object> listUnion( const list<Object> & L1,
const list<Object> & L2)
{
    list<Object> result;
    typename list<Object>:: const_iterator iterL1 = L1.begin();
    typename list<Object>:: const_iterator iterL2= L2.begin();
    while(iterL1 != L1.end() && iterL2 != L2.end())
    {
        if (*iterL1 == *iterL2)
        {
            result.push_back(*iterL1);
            iterL1++;
            iterL2++;
        }
        else if (*iterL1 < *iterL2)
        {
            result.push_back(*iterL1);
            iterL1++;
        }
        else
        {
            result.push_back(*iterL2);
            iterL2++;
        }
    }
    return result;
}

3.一个有表头结点,没有尾结点,还有一个指向表头结点的指针的单向链表,写一个类包括以下函数:
返回链表的大小,
打印链表,
检测值x是否在链表中,
如果x不在链表中则加入链表,
如果x在链表中则删除它。

template <typename Object>
struct Node
{
    Object data;
    Node *next;
    Node (const Object & d = Object(),Node *n=NULL)
        :data(d),next(n){}
};

template <typename Object>
class singleList {
public:
    singleList(){init();}
    ~singleList()
    {
        eraseList(head);
    }

    singleList(const singleList & rhs)
    {
        eraseList(head);
        init();
        *this=rhs;
    }

    bool add(Object x)
    {
        if(contains(x))
        {
            return false;
        }
        else
        {
            Node<Object> *ptr =new Node<Object>(x);
            ptr->next=head->next;
            head->next=ptr;
            theSize++;
        }
        return true;
    }

    bool remove(Object x)
    {
        if(!contains(x))
            return false;
        else 
        {
            Node<Object>*ptr=head->next;
            Node<Object>*trailer;
            while(ptr->data!=x)
            {
                trailer=ptr;
                ptr=ptr->next;
            }
            trailer->next=ptr->next;
            delete ptr;
            theSize--;
        }
        return true;
    }

    int size()
    {
        return theSize;
    }

    void print()
    {
        Node<Object> *ptr=head->next;
        while(ptr!=NULL)
        {
            count<<ptr->data<<" ";
            ptr=ptr->next;
        }
        count<<endl;
    }

    bool contains(const Object & x)
    {
        Node<Object> * ptr=head->next;
        while(ptr!=NULL)
        {
            if(x==ptr->data)
                return true;
            else 
                ptr=ptr->next;
        }
        return false;
    }

    void init()
    {
        theSize=0;
        head=new Node<Object>;
        head->next=NULL;
    }

    void eraseList(Node<Object> * h)
    {
        Node<Object> *ptr=h;
        Node<Object> *nextPtr;
        while(ptr!=NULL)
        {
            nextPtr=ptr->next;
            delete ptr;
            ptr=nextPtr;
        }
    }

private:
    Node<Object> *head;
    int theSize;
};

4.如何给List迭代器类添加对operator–的支持。

const_iterator & operator-- ()
{
    current=current->prev;
    return *this;
}

const_iterator operator-- (int)
{
    const_iterator old=*this;
    --(*this);
    return old;
}

5.前面谈到过的双端队列(deque),给它添加以下功能:

函数 备注
push(x) 将项x插入到双端队列的前段
pop() 从双端队列删除前段项并返回
inject(x) 将项x插入到双端队列的尾端
eject() 从双端队列中删除尾端项并将其返回
template <typename Object>
class deque
{
public:
    deque(){ l();}
    void push (Object obj) {l.push_front(obj);}
    Object pop () {Object obj=l.front();pop_front();return obj;}
    void inject (Object obj) {l.push_back(obj);}
    Object eject() {pop_back(obj);}
private:
    list<Object> l;
}

6.不包含表头结点和尾结点,用单向链表高效地实现栈类。

template<typename Object>
struct node
{
    node() {next=NULL;}
    node(Object obj):data(obj){}
    node(Object obj,node * ptr):data(obj),next(ptr){}
    Object data;
    node *next;
};

template<typename Object>
class stack { public: stack(){head=NULL;} ~stack(){while(head) pop();} void push(Object obj) { node<object> *ptr=new node<Object>(obj,head); head=ptr; } Object top() { return (head->data); } void pop() { node<Object> *ptr=head->next; delete head; head=ptr; } private: node<Object> *head; }

7.不包含表头结点和尾结点,用单向链表高效地实现队列类。

template<typename Object>
class queue
{
public:
    queue(){front=NULL;rear=NULL;}
    ~queue(){while(front)deque();}
    void deque(Object obj)
    {
        node<Object> *ptr=new node<Object>(obj,NULL);
        if(rear)
            rear=rear->next=ptr;
        else
            front=rear=ptr;
    }
    Object deque()
    {
        Object temp=front->data;
        node<Object> *ptr=front;
        if(front->next==NULL)
            front=rear=NULL;
        else
            front=front->next;
        delete ptr;
        return temp;
    }
private:
    node<Object> *front;
    node<Object> *rear;
}

8.使用由vector作为基本的数据结构的循环数组高效地实现队列类。

template<typename Object>
class queue
{
public:
    queue(int s):maxSize(s),front(0),rear(0){elements.resize(maxSize);}
    queue(){maxSize=100;front=0;rear=0;elements.resize(maxSize);}
    ~queue(){while(front!=rear) deque();}
    void enque(Object obj)
    {
        if(!full())
        {
            elements[rear]=obj;
            rear=(rear+1)%maxSize;
        }
    }
    Object deque()
    {
        Object temp;
        if(!empty())
        {
            temp=elements[front];
            front=(front+1)%maxSize;
            return temp;
        }
    }
    bool empty(){return front==rear;}
    bool full(){return (rear+1)%maxSize==front;}
private:
    int front,rear;
    int maxSize;
    vector<Object> elements;
}



感谢您的访问,希望对您有所帮助。

欢迎大家关注或收藏、评论或点赞。


为使本文得到斧正和提问,转载请注明出处:
http://blog.csdn.net/nomasp


版权声明:本文为 NoMasp柯于旺 原创文章,未经许可严禁转载!欢迎访问我的博客:http://blog.csdn.net/nomasp

本文转载自:http://blog.csdn.net/nomasp/article/details/45601767

NoMasp
粉丝 7
博文 334
码字总数 0
作品 0
镇江
程序员
私信 提问
数据结构历险记(持更)

最近在看《深入理解操作系统》这本书的时候,发现里面涉及了好多关于数据结构的东西。而自己却又半桶水(此时此刻有些悔恨大一没有好好听数据结构的课以及没有好好学C语言,导致现在都是在补...

youngiii
2017/06/11
0
0
【数据结构】数组、链表、队列、栈的区别和联系

目录 本文主要总结下数组、链表、队列、栈的区别和联系。 其实将这四个数据结构放在一起比较不是非常合适: 联系: 这四种数据结构都是线性表数据结构。 区别: 数组与链表是更加偏向数据存储...

写代码的木公
09/09
0
0
nomasp 博客导读:Lisp/Emacs、Algorithm、Android

版权声明:转载请联系本人,感谢配合!本站地址:http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/44966625 Profile Introduction to Blog 您能看到这篇博客导读...

nomasp
2015/09/17
0
0
LeetCode算法题-Implement Queue Using Stacks(Java实现)

这是悦乐书的第195次更新,第201篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第57题(顺位题号是232)。使用栈实现队列的以下操作。 push(x) - 将元素x推送到队列的后面。...

小川94
2018/12/08
0
0
LeetCode算法题-Implement Stack Using Queues

这是悦乐书的第193次更新,第198篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第54题(顺位题号是225)。使用队列实现栈的以下操作: push(x) - 将元素x推入栈。 pop() ...

小川94
2018/12/06
0
0

没有更多内容

加载失败,请刷新页面

加载更多

程序设计基础(C)第06讲例程

1summing.c /* summing.c -- 根据用户键入的整数求和 */#include <stdio.h>int main(void){ long num; long sum = 0L; /* 把sum 初始化为0 */ int status; p......

树人大学数字媒体吴凡
30分钟前
6
0
聊聊nacos config的publishConfig

序 本文主要研究一下nacos config的publishConfig ConfigController nacos-1.1.3/config/src/main/java/com/alibaba/nacos/config/server/controller/ConfigController.java @Controller@R......

go4it
58分钟前
5
0
Eureka应用注册与集群数据同步源码解析

在之前的EurekaClient自动装配及启动流程解析一文中我们提到过,在构造DiscoveryClient类时,会把自身注册到服务端,本文就来分析一下这个注册流程 客户端发起注册 boolean register() t...

Java学习录
今天
11
0
Java描述设计模式(15):责任链模式

本文源码:GitHub·点这里 || GitEE·点这里 一、生活场景描述 1、请假审批流程 公司常见的请假审批流程:请假天数 当 day<=3 天,项目经理审批当 3<day<=5 天,部门经理审批当 day>5 天...

知了一笑
今天
11
0
总结:数组与链表

1、内存申请:数组在内存上是连续的空间;链表,内存地址上可以是不连续的。 2、查询速度:数组可以随机访问,链表必须顺序访问,即从首个元素开始遍历,逐个查找,所以数组查询很快。 3、写入...

浮躁的码农
今天
9
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部