📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 4192| 回复: 12
跳转到指定楼层
上一主题 下一主题
收起左侧

Microsoft : 数组实现链表

全局:

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
How do you implement a linked list without using dynamic memory allocation? So basically you need to use an array as a linked list.

上一篇:Microsoft : Implement a special stack
下一篇:Amazon : 大量数据排序
全局:
darksteel 发表于 2011-5-4 22:44
回复 8# wwwyhx
目前这样只能插入到指定位置,复杂度不是O(1)。因为内部的数组index和逻辑上的位置其实是 ...

对,我感觉应该就是这样的,应该是把这个数组的最后1/4部分拿出来当那个迭代器用来存储可用的位置空间就可以解决了
回复

使用道具 举报

🔗
Etrnls 2011-5-2 23:36:11 | 只看该作者
全局:
struct Node
{
    Blabla value;
    int prev, next;
};

Node list[xxxxx];
回复

使用道具 举报

🔗
Imbalism 2011-5-2 23:42:21 | 只看该作者
全局:
struct Node
{
    Blabla value;
    int prev, next;
};

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

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

使用道具 举报

🔗
Etrnls 2011-5-2 23:46:53 | 只看该作者
全局:
回复 3# Imbalism

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

使用道具 举报

🔗
 楼主| wwwyhx 2011-5-3 23:51:55 | 只看该作者
全局:
用静态链表实现,维护一个free list 和一个 used list
插入,删除 时间复杂度为O(1)
回复

使用道具 举报

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

使用道具 举报

🔗
darksteel 2011-5-4 07:57:08 | 只看该作者
全局:
本帖最后由 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 | 只看该作者
全局:
用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。
darksteel 发表于 2011-5-4 07:57


插入删除时间复杂度是O(1)吗??
没有 free list 怎么能一下定位到空的block
回复

使用道具 举报

🔗
 楼主| wwwyhx 2011-5-4 17:12:22 | 只看该作者
全局:
  1. template <class T, const unsigned short size> class TArrayLnk
  2. {
  3. public:
  4.         TArrayLnk() : m_nUsedTail(0), m_nEmptyHead(size+1)
  5.         {
  6.                 for (int i = 1; i < size+2; i++)
  7.                         m_arr[i+1].nNext = i;
  8.         }

  9.         void PrintLink()
  10.         {
  11.                 int i = m_arr[0].nNext;
  12.                 while (i > 1)
  13.                 {
  14.                         cout<<m_arr[i].value<<" ";
  15.                         i = m_arr[i].nNext;
  16.                 }
  17.                 cout<<endl;
  18.         }

  19.         bool IsFull()        { return 1 == m_nEmptyHead; }
  20.         bool IsEmpty()        { return 0 == m_nUsedTail; }

  21.         int Insert(int nIndex, const T& val);
  22.         void Delete(int nIndex);

  23. protected:
  24.         struct Elem
  25.         {
  26.                 Elem() { nNext = -1; bUsed = false; }

  27.                 T value;
  28.                 int nNext;
  29.                 bool bUsed;
  30.         };

  31.         Elem m_arr[2+size];

  32.         //m_arr[0] is used head, m_arr[1] is empty head
  33.         int m_nUsedTail;
  34.         int m_nEmptyHead;
  35. };

  36. template <class T, const unsigned short size> int TArrayLnk<T, size>::Insert(int nIndex, const T& val)
  37. {
  38.         if (IsFull() || (nIndex < 2 && nIndex != 0) || nIndex >= size+2 || (!m_arr[nIndex].bUsed && nIndex != 0))
  39.                 return -1;

  40.         int nNewBlock = m_nEmptyHead;
  41.         m_nEmptyHead = m_arr[m_nEmptyHead].nNext;

  42.         m_arr[nNewBlock].nNext = m_arr[nIndex].nNext;
  43.         m_arr[nIndex].nNext = nNewBlock;

  44.         m_arr[nNewBlock].value = val;
  45.         m_arr[nNewBlock].bUsed = true;

  46.         return nNewBlock;
  47. }

  48. template <class T, const unsigned short size> void TArrayLnk<T, size>::Delete(int nIndex)
  49. {
  50.         if (nIndex == m_nUsedTail || nIndex < 2 || (nIndex < 2 && nIndex != 0) || (!m_arr[nIndex].bUsed && nIndex != 0))
  51.                 return;

  52.         int nDel = m_arr[nIndex].nNext;
  53.         m_arr[nIndex].nNext = m_arr[nDel].nNext;

  54.         m_arr[nDel].nNext = m_nEmptyHead;
  55.         m_nEmptyHead = nDel;
  56.         m_arr[m_nEmptyHead].bUsed = false;
  57. }
复制代码
回复

使用道具 举报

🔗
Etrnls 2011-5-4 17:38:20 | 只看该作者
全局:
回复 8# wwwyhx

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

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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