精华内容
下载资源
问答
  • 链表

    2016-12-04 17:07:44
    链表一、相关概念 链表 1、为什么使用链表先从顺序表的缺点说起,顺序表的插入和删除操作时我们需要移动大量的元素。...单链表、双链表循环链表 这个我们实现的是单链表二、实现分析1、基本属性<1>

    链表

    一、相关概念

    1、为什么要使用链表

    先从顺序表的缺点说起,顺序表的插入和删除操作时我们需要移动大量的元素。有没有什么办法在执行这些操作的时候,不需要移动这么多的元素呢?链表应运而生。

    2、链表

    有若干个结点(元素)组成,每个结点除结点本身的信息外,增加了一个或多个指针字段来表示结点之间的关系。

    常见的链表:单链表、双链表和循环链表

    这个我们实现的是单链表

    二、实现分析

    1、基本属性

    <1>结点的内容:data;
    <2>结点的指针:next;

    2、基本方法

    (1)查找:
    1.通过结点的位置来查找元素,返回元素地址;(这里我们找到的都是你想要操作的元素的前一个元素)
    2.通过值来查找元素返回元素地址;

    (2)插入
    在第i个位置,插入一个值为item的元素;

    1> 在链表为空时插入一个元素
    2> 在链表表头插入一个元素
    3> 在链表中插入一个元素

    (3)删除
    删除第i个位置的元素;
    1> 删除第一个元素,也就是头结点
    2> 删除第其他元素,将找到的元素的next指向你要删除的元素的next元素

    (4)输出

    “先进先出”的原则输出链表中的所有元素

    (5)有序插入
    将元素item按照一定的顺序存入链表

    1> 第一步就是先判断一下head是否是空的;
    1>> 如果是空的就将这个newNode添加成head;
    2>> 如果不是空的,就进行下面的比较

    2> 第二步就是开始比较大小;
    1>> 如果比他大的话,while循环,看是否是最大,若是最大的话就将这个元素添加到最后面;newNode的next指向current,prePtr指向newNode;
    2>> 如果比他小的话,就将这个newNode添加到prePtr的后面,将newNode的next指向current;

    三、代码实现

    //slist.cpp
    #include <cstddef>
    #include <iostream>
    using namespace std;
    
    template <class T>
    struct Node
    {
        T data;         //infomation od node;
        Node<T> *next;  //pointer filed indicating its successor;
        Node()          //constructor;
        {
            next = NULL;
        }
        Node(T item, Node<T> *add_on = NULL)
        {
            data = item;
            next = add_on;
        }
    };
    
    template <class T>
    class slist
    {
        private:
            Node<T>*head;
    
        public:
            slist();
    
            void find(int i, Node<T>* &p);
    
            T find(T key);
    
            void insert(int i, T item);
    
            void remove(int i);
    
            void print()const;
    
            void insert_order(T item);
    
            ~slist();              
    };
    
    
    //constructor:create am empty linked list.
    template <class T>
    slist<T>::slist()
    {
        head = NULL; 
    } 
    
    
    //find i-th node and record its address as p.
    template<class T>
    void slist<T>::find(int i, Node<T>* &p)
    {
        p = head;
        int j = 0; 
        while(p != NULL && (j < i-1))
        {
            p=p->next;
            j++;
        }   
    }
    
    
    //find the node whose value equals key and return it address;
    template<class T>
    T slist<T>::find(T key)
    {
        Node<T> *p = head;
        while((p != NULL) && (p -> data != key))
            p = p -> next;
        return p->data;
    }
    
    
    //insert a node with value item after node i;
    template<class T>
    void slist<T>::insert(int i,T item)
    {
        Node<T>*newnode=new Node<T>(item);
        if(i==0||(head==NULL))
        {
            newnode->next=head;
            head=newnode;
        }
        else
        {
            Node<T>*p=NULL;     
            find(i,p); 
            if(p!=NULL)
            {
                newnode->next = p->next;
                p->next=newnode;
    
            }
            if(p == NULL)
            {
                cout<<"error"<<endl;
            }
    
        }
    }
    
    
    //remove node i(i >= 1)from the link list;
    template<class T>
    void slist<T>::remove(int i)
    {
        Node<T>*p, *q;
        if(i == 1)
        {
            p = head;
            head = head -> next;
        }
        else
        {
            find(i-1, q);
            p = q -> next;
            q ->next = p ->next;
        }   
        delete p;
    } 
    
    
    //output the single-linked list;
    template<class T>
    void slist<T>::print()const
    {
        Node<T> *p = head;
        while(p != NULL)
        {
            cout<<p->data<<"  ";
            p = p -> next;
        }
    }
    
    
    //create an rderedly single-linked list;
    template<class T>
    void slist<T>::insert_order(T item)
    {
        Node<T> *currPtr, *prePtr, *newNode;
        newNode = new Node<T>(item, NULL);
        prePtr = NULL;
        currPtr = head;
        while(currPtr != NULL)
        {
            if(item < currPtr -> data)
            {
                break;
            }
            prePtr = currPtr;
            currPtr = currPtr -> next;
        }
        if(prePtr == NULL)  //如果头是空的话,就将newNode设置为head;
        {
            newNode -> next = head;
            head = newNode;
        }
        else                //如果这个newNode是最大的让就会被添加到最后一个位置;
        {                   //如果这个数比较小的话,也会采用下面的这两段代码;
            newNode -> next = currPtr; //(NULL)
            prePtr -> next = newNode;
        }
    }
    
    
    //destructor--leaving the linked list empty;
    template<class T>
    slist<T>::~slist()
    {
        Node<T> *currPtr, *nextPtr;
        currPtr = head;
        while(currPtr != NULL)
        {
            nextPtr == currPtr -> next;
            delete currPtr;
            currPtr = nextPtr;
        } 
        head = NULL;
    }
    展开全文
  • 链表 概念:链表也是我们最常使用的一种数据结构,它是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序...很明显链表这种数据结构它是通过一种手段将我们的数据串起来,所以数据存储的时候它...

    链表

    • 概念:链表也是我们最常使用的一种数据结构,它是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链
      接次序实现的 。
    • 分类
      单向链表、双向链表
      带头的链表、不带头链表
      循环链表、非循环链表等
    • 让我们来看看链表到底是什么样子的

    在这里插入图片描述
    上图就是我们最常用的单向链表及双选购链表的示意图。很明显链表这种数据结构它是通过一种手段将我们的数据串起来,所以在数据在存储的时候它并不一定要是连续的,我们只需要将当前数据的下一个数据的位置信息保存起来即可,那么链表就是通过指针来保存数据的位置信息的。

    • 话不多说还是上代码,下面我以单链表为例,让我们看看链表到底是如何实现的。
    #include<iostream>
    
    using namespace std;
    
    //用Elemtype代替int  好处就是当int改变时,只需要改变一个int即可
    typedef int Elemtype;
    //链表节点的定义
    typedef struct Node
    {
    	int value;
    	struct Node* next;
    }Node;
    
    //初始化链表,没有一个节点的链表,即为空链表。
    void LinkListInit(Node** p)
    {
    	*p = NULL;
    }
    
    //链表的销毁
    void DestoryLinkList(Node** p)
    {
    	//销毁链表则要找一个临时变量保存当前的位置,这才能保证后面的节点位置信息不丢失
    	Node* ptr;
    	for (Node* cur = *p; cur != NULL; cur = ptr)
    	{
    		ptr = cur->next;
    		free(cur);
    	}
    }
    //打印节点值
    void PrintLinkList(Node* p)
    {
    	if (p == NULL)
    	{
    		cout << "该链表为空链表。" << endl;
    		return ;
    	}
    	while (p != NULL)
    	{
    		cout << p->value << " " << endl;
    		p = p->next;
    	}
    
    }
    //链表的头插法
    void LinkListInsertFront(Node** p,int value)
    {
    	//构造节点
    	Node* node = (Node*)malloc(sizeof(Node));
    	node->value = value;
    	node->next = *p;
    	*p = node;
    }
    
    //链表的尾插法
    void LinkListInsertBack(Node** p, Elemtype value)
    {
    	//构造节点
    	Node* node = (Node*)malloc(sizeof(Node));
    	node->value = value;
    
    	if (*p == NULL) {
    		// 链表中一个结点都没有
    		*p = node;
    		return;
    	}
    
    
    	//既然要尾插那么就要找到尾节点
    	Node* cur = *p;
    	for (; cur->next != NULL; cur = cur->next);
    	//此时cur为尾节点
    	cur->next = node;
    	node->next = NULL;
    }
    
    //链表的中间插入,即插入到某个节点的后面
    void LinkListInsertMid(Elemtype value,Node* pos)
    {
    	//构造节点
    	Node* node = (Node*)malloc(sizeof(Node));
    	node->value = value;
    	//先找到当前的节点位置
    	node->next = pos->next;
    	pos->next = node;
    }
    
    //链表的查找,返回当前节点的地址
    Node* LinkListFind(Node* p, Elemtype value)
    {
    	//参数的合法性检验
    	if (p == NULL)
    	{
    		return NULL;
    	}
    	Node* cur = p;
    	for (; cur != NULL; cur = cur->next)
    	{
    		if (cur->value = value)
    		{
    			//此时cur为当前value的地址
    			return cur;
    		}
    	}
    	return NULL;
    
    }
    
    //头删
    void LinkListDelFront(Node** p)
    {
    	if (*p == NULL)
    	{
    		return;
    	}
    	else
    	{
    		Node *next = (*p)->next;
    		free(*p);
    		*p = next;
    	}
    }
    
    //尾删
    void LinkListPopBack(Node** p)
    {
    	if (*p == NULL)
    	{
    		return;
    	}
    	if ((*p)->next == NULL) 
    	{
    		free(*p);
    		*p = NULL;
    		return;
    	}
    
    	// 找到倒数第二个结点
    	// cur->next->next == NULL 停下来
    	Node *cur = *p;
    	while (cur->next->next != NULL) 
    	{
    		cur = cur->next;
    	}
    
    	// 释放最后一个结点
    	free(cur->next);
    	cur->next = NULL;
    }
    
    //中间删除(某个节点之后删除)
    void LinkListDel(Node* p)
    {
    	Node *next = p->next;
    	p->next = p->next->next;
    	free(next);
    }
    
    int main()
    {
    	Node* node;
    	cout << "链表已经初始化成功" << endl;;
    	LinkListInit(&node);  //初始化
    	PrintLinkList(node);
    
    	cout << "请输入头插入的节点值:";
    	Elemtype value;
    	cin >> value;
    	LinkListInsertFront(&node,value);//头插
    	PrintLinkList(node);
    
    
    	cout << "请输入尾插入的节点值:";
    	Elemtype value1;
    	cin >> value1;
    	LinkListInsertBack(&node, value1);//尾插
    	PrintLinkList(node);
    
    	cout << "请输入您想要查找的节点值:";
    	Elemtype value2;
    	cin >> value2;
    	Node* p = LinkListFind(node,value2);
    	if (p == NULL)
    	{
    		cout << "没有找到该节点" << endl;
    	}
    	else
    	{
    		cout << "找到该节点" << endl;
    	}
    
    	cout << "请输入中间插入的节点值:";
    	Elemtype value3;
    	cin >> value3;
    	cout << "请输入您想要插入的位置节点的值:";
    	Elemtype value4;
    	cin >> value4;
    	Node* pp = LinkListFind(node, value4);
    	LinkListInsertMid(value3,pp);//中间插入
    	PrintLinkList(node);
    	
    	cout << "请输入您要删除节点的值:";
    	int value5;
    	cin >> value5;
    	Node* ppp = LinkListFind(node, value5);
    	cout << "删除" << value5 << "节点";
    	LinkListDel(ppp);
    	PrintLinkList(node);
    	cout << "删除头节点" << endl;
    	LinkListDelFront(&node);
    	PrintLinkList(node);
    	cout << "删除尾节点" << endl;
    	LinkListPopBack(&node);
    	PrintLinkList(node);
    	
    	system("pause");
    	return 0;
    }
    

    自我感觉啊,面对链表的相关问题时还是得画图,有了图,我们的思路才会更加清晰,对于链表而言,它没有随机访问能力,如果要查找某个数,只能遍历一遍,时间相对而言没有顺序表好,但是链表的增删很快,不需要像顺序表一样挪动数据。

    注注注:重要的事说三遍,其实看起来小小的链表没有多难操作,但就是通过这小小链表引申了很多问题,有许多问题值得我们去思考,当你真正理解了链表之后,你会发现链表真的还挺有意思的。后续我会继续与大家分享我遇到的关于链表的一些有意思的问题,我们可以与链表进一步的增进感情嘛!

    展开全文
  • 后来好像也没有用到,倒是一直记得好像老早以前看到ldd上提到双向链表时候有提到个kfifo,只是一直没有用到这个,所以一直没看。倒是无聊的时候想起过printk是否用的就是这个数据结构。  昨天临下班的时候想到...
     忘记了之前是有个什么事情一时想起好像需要用个cycler buffer,手头一时又没有,懒得自己实现。就向同学要了个。后来好像也没有用到,倒是一直记得好像老早以前看到ldd上提到双向链表的时候有提到个kfifo,只是一直没有用到这个,所以一直没看。倒是无聊的时候想起过printk是否用的就是这个数据结构。
    

      昨天临下班的时候想到kfifo这个东东,今天就抽点时间看看。

      刚开始是把双向链表拎出来编一下看看,结果让我大吃一惊。居然没有list.h,看来fc从4以后开始倒退倒是有点佐证了。好在机器上还有Linux-libc-headers的包,解包覆盖一下应该就ok了吧。不要高兴,还是不行。打开list.h一看,居然里面只包含了另一个文件,只扔给我一个#error,超ft。没办法,只好上内核源码里去拷了,于是把include/*都copy到了/usr/include。再编,靠,居然还是不过。nnd,再看list.h,居然还有个宏定义才能使用里面的inline函数,要不就extern reference了,郁闷。只好在源文件中加了:

    #ifdef CONFIG_DEBUG_LIST
    #undef CONFIG_DEBUG_LIST
    #endif

      然后再包含上Linux/autoconf.h,这才一切ok。汗......

      有了上面的折腾,在开始搞kfifo之前就先看看kfifo.h和他的实现吧。结果一看kfifo.h和kfifo.c,头文件里面extern了好几个kfifo.c里面实现的东东不说,还用了spinlock,看来直接用是没有指望了,还是dirty hack到user space算了。于是只能把文件copy出来dirty hack了。吭哧吭哧搞了一气,搞了个可用的东东开列如下:
      kfifo.c:

    #include "kfifo.h"
    #include 
    #include 
    #include 
    #include 
    struct kfifo *kfifo_init(unsigned char *buffer, unsigned int size)
    {
        struct kfifo *fifo;

        fifo = malloc(sizeof(struct kfifo));
        if (!fifo)
            return (void*)(-ENOMEM);

        fifo->buffer = buffer;
        fifo->size = size;
        fifo->in = fifo->out = 0;

        return fifo;
    }

    struct kfifo *kfifo_alloc(unsigned int size)
    {
        unsigned char *buffer;
        struct kfifo *ret;
        if (size & (size - 1)) {
            fprintf(stderr,"size > 0x80000000n");
            size = roundup_pow_of_two(size);
        }

        buffer = malloc(size);
        if (!buffer)
            return (void *)(-ENOMEM);

        ret = kfifo_init(buffer, size);

        if ((unsigned long)ret<=0)
        {
            free(buffer);
        }

        return ret;
    }

    void kfifo_free(struct kfifo *fifo)
    {
        free(fifo->buffer);
        free(fifo);
    }

    unsigned int __kfifo_put(struct kfifo *fifo, unsigned char *buffer, unsigned int len)
    {
        unsigned int l;

        len = min(len, fifo->size - fifo->in + fifo->out);

            l = min(len, fifo->size - (fifo->in & (fifo->size - 1)));
        memcpy(fifo->buffer + (fifo->in & (fifo->size - 1)), buffer, l);
        memcpy(fifo->buffer, buffer + l, len - l);

        fifo->in += len;

        return len;
    }

    unsigned int __kfifo_get(struct kfifo *fifo,
                 unsigned char *buffer, unsigned int len)
    {
        unsigned int l;

        len = min(len, fifo->in - fifo->out);

        l = min(len, fifo->size - (fifo->out & (fifo->size - 1)));
        memcpy(buffer, fifo->buffer + (fifo->out & (fifo->size - 1)), l);

        fifo->out += len;
        return len;
    }

      kfifo.h:
    #ifndef _Linux_KFIFO_H
    #define _Linux_KFIFO_H

    #define __u32 unsigned long
    #define __u64 unsigned long long

    #define min(x,y) ({ 
            typeof(x) _x = (x);     
            typeof(y) _y = (y);     
            (void) (&_x == &_y);            
            _x < _y ? _x : _y; })

    #define max(x,y) ({ 
            typeof(x) _x = (x);     
            typeof(y) _y = (y);     
            (void) (&_x == &_y);            
            _x > _y ? _x : _y; })

    static inline int fls(int x)
    {
        int r;

        __asm__("bsrl %1,%0nt"
                "jnz 1fnt"
                "movl $-1,%0n"
                "1:" : "=r" (r) : "rm" (x));
        return r+1;
    }

    static inline int fls64(__u64 x)
    {
        __u32 h = x >> 32;
        if (h)
            return fls(h) + 32;
        return fls(x);
    }

    static inline unsigned fls_long(unsigned long l)
    {
        if (sizeof(l) == 4)
            return fls(l);
        return fls64(l);
    }

    static inline unsigned long roundup_pow_of_two(unsigned long x)
    {
        return 1UL << fls_long(x - 1);
    }

    struct kfifo {
        unsigned char *buffer;    /* the buffer holding the data */
        unsigned int size;    /* the size of the allocated buffer */
        unsigned int in;    /* data is added at offset (in % size) */
        unsigned int out;    /* data is extracted from off. (out % size) */
    };

    struct kfifo *kfifo_init(unsigned char *buffer, unsigned int size);
    struct kfifo *kfifo_alloc(unsigned int size);
    void kfifo_free(struct kfifo *fifo);
    unsigned int __kfifo_put(struct kfifo *fifo, unsigned char *buffer, unsigned int len);
    unsigned int __kfifo_get(struct kfifo *fifo, unsigned char *buffer, unsigned int len);

    static inline void __kfifo_reset(struct kfifo *fifo)
    {
        fifo->in = fifo->out = 0;
    }

    static inline void kfifo_reset(struct kfifo *fifo)
    {

        __kfifo_reset(fifo);

    }

    static inline unsigned int kfifo_put(struct kfifo *fifo,
                         unsigned char *buffer, unsigned int len)
    {
        unsigned int ret;

        ret = __kfifo_put(fifo, buffer, len);

        return ret;
    }

    static inline unsigned int kfifo_get(struct kfifo *fifo,
                         unsigned char *buffer, unsigned int len)
    {
        unsigned int ret;

        ret = __kfifo_get(fifo, buffer, len);

        if (fifo->in == fifo->out)
            fifo->in = fifo->out = 0;


        return ret;
    }

    static inline unsigned int __kfifo_len(struct kfifo *fifo)
    {
        return fifo->in - fifo->out;
    }

    static inline unsigned int kfifo_len(struct kfifo *fifo)
    {
        unsigned int ret;

        ret = __kfifo_len(fifo);

        return ret;
    }

    #endif

       
      用起来还是不错的,初步测试了一下效果还行,在去掉了spinlock的保护之后还揣测了一段时间是不是把spinlock改成sem用来sync,不过看到代码的实现又觉得这个spinlock不是对fifo的index进行保护的,也就是说这个实现是免锁的。在kernel中的代码也不过是在smp的情况下加了mb而已。

      贴一下测试的代码如下:

    #define FIFO_LENGTH 4096

    struct ll_param
    {
        struct kfifo * fifo;
        int msg_len;
    };

    static struct ll_param fifo;

    void thread_reader(void * param)
    {
        int read_len=0;
        unsigned int counter=0;
        unsigned char buffer[FIFO_LENGTH]=;
        struct ll_param * p=(struct ll_param *)param;
        
        for(;;)
        {
            bzero(buffer,FIFO_LENGTH);
            read_len=kfifo_get(p->fifo,buffer,FIFO_LENGTH);
            if(read_len!=0)
            {
                printf("Read len:%d,buffer is:%sn",read_len,buffer);
            }
            else
            {
                counter++;
            }
            if(counter>20)
            {
                break;
            }
            usleep(50000);
        }
    }

    void thread_writer(void * param)
    {
        unsigned int write_len=0;
        unsigned int counter=0;
        unsigned char buffer[32]=;
        struct ll_param * p=(struct ll_param *)param;
        
        for(counter=0;counter<1000;counter++)
        {
            bzero(buffer,32);
            sprintf((char *)buffer,"This is %d message.n",counter);
            write_len=kfifo_put(p->fifo,buffer,strlen((char *)buffer));
            usleep(100);
        }
    }


    int main(void)
    {
        pthread_t pidr;
        pthread_t pidw;

        fifo.msg_len=10;
        fifo.fifo=kfifo_alloc(FIFO_LENGTH);

        pthread_create(&pidw,NULL,(void *)thread_writer,&fifo);
        pthread_create(&pidr,NULL,(void *)thread_reader,&fifo);

        pthread_join(pidr,NULL);
        pthread_join(pidw,NULL);

        kfifo_free(fifo.fifo);
        printf("nGoodbye!n");
        return 0;
    }


      要说明的是,初步测了一下,似乎reader中用来get的buffer大小对受writer和reader之间不一致的速率的影响较大。比如如果reader里面定义的buffer长度设置为小于fifo长度,在writer和reader个子usleep不同时间时表现会不同。以后再慢慢找吧

    展开全文
  • 面试题五:从尾到头打印链表链表是一种频繁被提及的数据结构,它...分析:当遇见这种题的时候,瞬间感觉自己对于链表的所有认识全部给抛了出来,什么双向链表循环链表了等等,但是额外的想这些只会为你的大脑提供...
    面试题五:从尾到头打印链表


    链表是一种频繁被提及的数据结构,它是通过指针把若干个结点连接成链状的一种数据结构。由于链表的操作是通过指针来实现的,所以在这里指针的正常使用也是面试官所容易提及的一个考点。


    题目:
      输入一个链表的头结点,从尾到头反过来打印出每个节点的值;

    分析:当遇见这种题的时候,瞬间感觉自己对于链表的所有认识全部给抛了出来,什么双向链表,循环链表了等等,但是额外的想这些只会为你的大脑提供更多的负担,解决确实可以解决,但是这样会使链表的结构发现相应的改变。或许有的会想到单链表不是只能从前向后遍历,倒着从后往前遍历不是不可以吗,面试题就是抓住了这点,所以需要你灵活的去巧妙的进行解决这个问题。这里我们是利用了另一种数据结构---栈的特性---先进后出,我们通过先进后出这个特点,把链表中的所有数据结点从前向后遍历,并依次的压入栈中,当遍历完整个链表以后,再从栈顶开始逐个的弹出(出栈),这样我们就实现了链表的从尾到头打印链表了。
    图解:



    相应的栈和链表类的部分功能的实现 

    #include <iostream>
    #include <assert.h>
    using namespace std;
    
    //栈
    class CDstack
    {
    public:
    	CDstack()
    	{
    		//cout<<"CDstack()"<<endl;
    		_elem = new int[INITSIZE];
    		_top = 0;
    		_topsize = INITSIZE;
    	}
    	~CDstack()
    	{
    		delete[]_elem;
    	}
    	bool isfull()//判满
    	{
    		return _top == _topsize;
    	}
    	bool isempty()//判空
    	{
    		return _top == 0;
    	}
    	void resize()//扩容
    	{
    		int *newelem = new int[_topsize*2];
    		for (int i = 0; i<_top; i++)
    		{
    			newelem[i] = _elem[i];
    		}
    		delete []_elem;
    		_elem = newelem;
    		_topsize = _topsize*2;
    	}
    	void push(int val)
    	{
    		if (isfull())
    		{
    			resize();
    		}
    		_elem[_top++] = val;
    	}
    	void pop(int *rtval)//获取值且删除
    	{
    		if (!isempty())
    		{
    			*rtval = _elem[--_top];
    		}
    	}
    	void show()
    	{
    		for (int i = 0; i<_top;i++)
    		{
    			cout<<_elem[i]<<"   ";
    		}
    		cout<<endl;
    	}
    	int max_size()
    	{
    		return _topsize;
    	}
    	int data_size()
    	{
    		return _top;
    	}
    private:
    	enum{INITSIZE = 20};//初始格子大小
    	int *_elem;
    	int _top;//栈顶指针,标记当前可以存放数据的下标
    	int _topsize;//总格子数
    };
    
    //结点
    class Node
    {
    public:
    	Node()
    	{
    		pnext = NULL;
    	}
    
    private:
    	int data;
    	Node *pnext;
    	friend class CList;
    };
    
    //链表
    class CList
    {
    public:
    	CList()
    	{
    		phead = new Node();
    		//cout<<"CList()"<<endl;
    	}
    
    	~CList()
    	{
    		Node* p = phead;
    		while(phead->pnext != NULL)
    		{
    			p = phead->pnext;
    			phead->pnext = p->pnext;
    			delete p;
    		}
    		delete phead;
    	}
    
    	void insert(int val)
    	{
    		Node *p = new Node();
    		p->data = val;
    		p->pnext = phead->pnext;
    		phead->pnext = p;
    	}
    	//获取头结点后面的结点的值,并删除这个结点
    	void gethead_data(int *val)
    	{
    		Node *p = phead->pnext;
    		*val = p->data;
    		phead->pnext = p->pnext;
    		delete p;
    	}
    	bool isempty()
    	{
    		return phead->pnext == NULL;
    	}
    	void show()
    	{
    		Node *p = phead->pnext;
    		while(p != NULL)
    		{
    			cout<<p->data<<"   ";
    			p = p->pnext;
    		}
    		cout<<endl;
    	}
    
    private:
    	Node* phead;
    };

    面试题五代码详解:

    //面试题五:
    void last_front_ShowList(CList *phead)
    {
    	assert(phead != NULL);
    	CDstack stack1;
    	while(!phead->isempty())
    	{
    		int val;
    		phead->gethead_data(&val);
    		stack1.push(val);
    	}
    
    	while(!stack1.isempty())
    	{
    		int retval;
    		stack1.pop(&retval);
    		cout<<retval<<"   ";
    	}
    	cout<<endl;
    }
    int main()
    {
    //-------------------------------面试题五测试用例:------------------------------------
    	
    	//测试链表有多个结点的链表
    	CList list1;
    	for (int i = 10; i>0; i--)
    	{
    		list1.insert(i);
    	}
    	//list1.show();
    	cout<<"链表有多个结点的链表"<<endl;
    	last_front_ShowList(&list1);
    
    	//测试链表有一个结点的链表
    	CList list2;
    	list2.insert(15);
    	cout<<"链表有一个结点的链表"<<endl;
    	last_front_ShowList(&list2);
    
    	//测试链表头结点指针为NULL
    	CList list3;
    	cout<<"链表头结点指针为NULL"<<endl;
    	last_front_ShowList(&list3);
    }

    展开全文
  • 第三章 表栈和队列

    2017-08-12 12:32:47
    这章学习最简单的数据结构,表,栈和队列 什么是表 表就是一个序列A1,A2,A3...链表分为,单链表,双链表循环链表 链表实现的时候需要一个表头以此来消除许多特殊情况 linux内核使用的是:带头的双向循环链表,l
  • 数据结构

    2019-09-05 17:13:16
    总结以下最近一些遇到的一些问题,一般开发中数据结构用的页比较多,一开始都不知道如何使用什么时候用它,什么时候不用它,先讲解一下数据结构的定义吧: 定义:数据结构其实就是另外一种存储数据的方式,和数...
  • 《数据结构 1800题》

    热门讨论 2012-12-27 16:52:03
    17. 有 n个选手参加的单循环赛中,总共将进行______场比赛。【合肥工业大学 1999三、8(2分)】 四、应用题 1. 数据结构是一门研究什么内容的学科?【燕山大学 1999 二、1 (4分)】 2. 数据元素之间的关系...
  • 在什么场景下需要重新实现这两个方法。 4.3.6 在jdk1.5中,引入了泛型,泛型的存在是用来解决什么问题。 4.3.7 这样的a.hashcode() 有什么用,与a.equals(b)有什么关系。 4.3.8 有没有可能2个不相等的对象有相同...
  • 07_课堂答疑什么时候子类的步长和父类的步长一样 08_抽象类基本语法 09_抽象类多继承中的应用 10_面向抽象类编程_计算程序员工资 11_中午课程回顾 12_信息系统框架集成第三方产品案例_背景和需求 13_信息系统框架...
  • 5.10.4 三目运算符字符型变量中的使用 52 5.11 复杂嵌套的if语句 52 第6章 面向对象 54 6.1 面向对象程序语言的主要特征 54 6.2 类、对象和成员 55 6.3 类、对象和成员的使用方法及区别 56 6.3.1 声明一个类...
  • 6.4.1 什么时候可以省略花括号 6.4.2 省略花括号的危险 6.5 for循环的陷阱 6.5.1 分号惹的祸 6.5.2 小心循环计数器的值 6.5.3 浮点数作循环计数器 6.6 foreach循环循环计数器 6.7 小结 第7课 面向对象的...
  • 6.4.1 什么时候可以省略花括号 173 6.4.2 省略花括号的危险 174 6.5 for循环的陷阱 175 6.5.1 分号惹的祸 175 6.5.2 小心循环计数器的值 178 6.5.3 浮点数作循环计数器 179 6.6 foreach循环循环...

空空如也

空空如也

1 2
收藏数 39
精华内容 15
关键字:

在什么时候使用循环双链表