【数据结构】链表与顺序表的优缺点,和2道经典的题
这两道题是:1.从尾到头打印单链表。 2.单链表实现约瑟夫环的问题。 首先我们在面试时可能会遇到说明一下顺序表和链表的优缺点,说说他们分别在什么场景下使用: 1.首先我们从2种结构的结构上来进行分析: (1)对于顺序表。不论是静态的还是动态的,他们都是连续的存储空间,在读取上时间效率比较快,可以通过地址之间的运算来进行访问,但是在插入和删除操作会出现比较麻烦的负载操作。 (2)对于链表,因为他是链式存储。在我们需要的时候才在堆上开辟空间,对于插入查找的方式比较便携。但是对于遍历的话需要多次的空间跳转。 2.从2中结构的空间申请方式来看: (1)顺序表的空间开辟是在满的时候进行多空间的申请开辟。往往存在着2^n的开辟原则。在开辟次数比较多的时候,会出现比较大的空间浪费。 (2)链表的空间开辟是针对于单个节点的空间开辟访问,不存在多余的空间浪费。并且在碎片内存池的机制下。可以有效地利用空间。 通过上面的总结,可以分析出顺序表往往用于查找遍历操作比较频繁的情况下使用。链表则针对于数据删除修改的多操作性上的情况下使用。 分别是空间上和时间上的优势与缺陷的不同。 下面我们来看一下题。 1.从尾到头打印单链表: 这个题十分的简单,在前面我们也从高位到低位打印一个数字: 同样的。我们也可以用递归的方式来实现这个问题: 思路简单,直接来看一下代码: voidPrintFailToHead(PLinkNodepHead) { if(pHead!=NULL) { PrintFailToHead(pHead->_next); printf("%d->",pHead->_data); } if(pHead==NULL) { printf("NULL->"); return; } return; } 2.单链表实现约瑟夫环的问题。 这个题的前提是当前的单链表已经是一个环。我们只用考虑删除的节点就OK了。 至于什么是约瑟夫环,大家可以自行百度: 直接上代码。理解约瑟夫环的思维后就是单链表的操作问题,也比较简单: voidJosephRing(PLinkNode&pHead,DataTypex) { intcount=0; PLinkNodeindex=pHead,del; assert(pHead); while(index->_next!=index) { for(count=0;count<x-1;count++) { index=index->_next; } del=index->_next; index->_data=index->_next->_data; index->_next=index->_next->_next; pHead=index; free(del); del=NULL; } printf("%d",pHead->_data); } ok,大家一起学习进步~ (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |