查看: 3309|回复: 12
收起左侧

Microsoft : 数组实现链表

|只看干货 |刷题
头像被屏蔽

分享帖子到朋友圈
wwwyhx | 显示全部楼层 |阅读模式
提示: 作者被禁止或删除 内容自动屏蔽

上一篇:Microsoft : Implement a special stack
下一篇:Amazon : 大量数据排序
Etrnls 2011-5-2 23:36:11 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (7)
 
 
0% (0)    👎
struct Node
{
    Blabla value;
    int prev, next;
};

Node list[xxxxx];
回复

使用道具 举报

Imbalism 2011-5-2 23:42:21 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (42)
 
 
0% (0)    👎
struct Node
{
    Blabla value;
    int prev, next;
};

Node list[xxxxx];
Etrnls 发表于 2011-5-2 23:36

要不要一个flag来标示这个区域有没有人用了?这样的话在插入的时候才好找空闲的地方
回复

使用道具 举报

Etrnls 2011-5-2 23:46:53 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (7)
 
 
0% (0)    👎
回复 3# Imbalism

可以用一个maxId + 一个free list搞定。
用flag的话要扫一扫的 :P
回复

使用道具 举报

头像被屏蔽
 楼主| wwwyhx 2011-5-3 23:51:55 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复

使用道具 举报

darksteel 2011-5-4 06:36:20 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (32)
 
 
0% (0)    👎
回复 5# wwwyhx
节点数据结构2楼的应该就行。另外free list用什么保存?用链表的话就有点怪,因为这题本身就让实现个链表。我再想用2楼的数据结构,free list本身应该也能互相串起来,然后记录一个头的位置就行,有时间还是得写写
回复

使用道具 举报

darksteel 2011-5-4 07:57:08 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (32)
 
 
0% (0)    👎
本帖最后由 darksteel 于 2011-5-4 08:32 编辑

用2楼的数据结构定义实现了一个,有点丑陋,但证明上面讨论的思路是可行的。可以用node本身的指针串起free list,只需要保存free list的head就行。
支持的操作:
insert(x,p) 插入x到位置p之后
remove(x,p) 删除p位置后所有值为x的元素
erase(p) 删除位置为p的元素
find(x,p) 从位置p开始查找,返回第一个值位x的元素的位置
欢迎指出bug。

  1. #include <iostream>
  2. #include <cassert>
  3. using namespace std;
  4. template <typename T>
  5. class myLinkedList
  6. {
  7. public:
  8.         myLinkedList(int size = 100) : ff(1), tail(0), sz(0)
  9.         {
  10.                 assert(size>0);
  11.                 list = new listNode[size+1];
  12.                 ff = 1;
  13.                 for(int i = 1; i < size; i++)
  14.                         list[i].next = i+1;
  15.                 list[size].next = 0;
  16.         }
  17.         bool insert(T elem, int sp)
  18.         {
  19.                 assert(sp>=0&&sp<=sz);
  20.                 if(ff == 0)
  21.                         return false;
  22.                 int p = ff;
  23.                 int now = 0;
  24.                 while(sp--)
  25.                         now = list[now].next;
  26.                 ff = list[ff].next;
  27.                 list[p].val = elem;
  28.                 list[p].prev = now;
  29.                 list[p].next = list[now].next;
  30.                 list[list[now].next].prev = p;
  31.                 list[now].next = p;
  32.                 if(now == tail) tail = p;
  33.                 sz++;
  34.         }
  35.         bool insert(T elem)
  36.         {
  37.                 insert(elem, sz);
  38.         }
  39.         int find(T elem, int sp = 1)
  40.         {
  41.                 assert(sp>0&&sp<=sz);
  42.                 int ret = sp;
  43.                 int now = 0;
  44.                 while(sp--)
  45.                         now = list[now].next;
  46.                 while(now) {
  47.                         if(list[now].val == elem)
  48.                                 return ret;
  49.                         now = list[now].next;
  50.                         ret++;
  51.                 }
  52.                 return -1;
  53.         }
  54.         int remove(T elem, int sp = 1)
  55.         {
  56.                 assert(sp>0&&sp<=sz);
  57.                 int now = 0, ret = 0;
  58.                 while(sp--)
  59.                         now = list[now].next;
  60.                 while(now) {
  61.                         if(list[now].val == elem) {
  62.                                 now = del(now);
  63.                                 ret++;
  64.                         } else
  65.                                 now = list[now].next;
  66.                 }
  67.                 return ret;
  68.         }
  69.         int erase(int p)
  70.         {
  71.                 assert(p>=1&&p<=sz);
  72.                 int now = 0;
  73.                 while(p--)
  74.                         now = list[now].next;
  75.                 del(now);
  76.         }
  77.         int size(){ return sz; }
  78.         void display()
  79.         {
  80.                 cout << "Size: " << sz << endl;
  81.                 cout << "Elements: ";
  82.                 int now = list[0].next;
  83.                 while(now) {
  84.                         cout << list[now].val;
  85.                         if(now != tail) cout << " ";
  86.                         now = list[now].next;
  87.                 }
  88.                 cout << endl;
  89.         }
  90.         ~myLinkedList()
  91.         {
  92.                 delete list;
  93.         }
  94. private:
  95.         class listNode
  96.         {
  97.         public:
  98.                 listNode() : prev(0), next(0) {}
  99.                 T val;
  100.                 int prev, next;
  101.         };
  102.         listNode *list;
  103.         int ff;
  104.         int tail;
  105.         int sz;
  106.         int del(int now)
  107.         {
  108.                 int ret;
  109.                 list[list[now].prev].next = list[now].next;
  110.                 list[list[now].next].prev = list[now].prev;
  111.                 ret = list[now].next;
  112.                 list[now].next = ff;
  113.                 ff = now;
  114.                 if(now == tail)
  115.                         tail = list[now].prev;
  116.                 sz--;
  117.                 return ret;
  118.         }
  119. };
复制代码

回复

使用道具 举报

头像被屏蔽
 楼主| wwwyhx 2011-5-4 17:10:47 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复

使用道具 举报

头像被屏蔽
 楼主| wwwyhx 2011-5-4 17:12:22 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复

使用道具 举报

Etrnls 2011-5-4 17:38:20 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (7)
 
 
0% (0)    👎
回复 8# wwwyhx

他没开新数组当free list而已,用free的node本身串起来当free list
或者可以理解为,一开始有一个list,里面都是free的,然后插入操作就是从这个list里面拿一个出来放进另一个list,删除就是再放回来
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■拉群请前往同学同事飞友|拉群结伴版块,其他版块拉群,帖子会被自动删除
■论坛不能删帖,为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://tools.1point3acres.com/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

>
快速回复 返回顶部 返回列表