一组简单的代码练习，实现了基本的容器类型。
小小的活动手指，了解相关的运行调试编译环境。
* 代码练习一，简单的双向链表。
增删元素时，节点对前后节点的引用可千万别弄错呦。
包括自己的以及前后节点的都得修改，有遗漏就糟糕了。
依赖调试就不好了，得能够手写一遍就正确才可以的。
class DList(object):
"""
Doubly linked list
link: http://www.w3schools.com/jsref/jsref_obj_array.asp
"""
class Node:
def __init__(self,item,prev,next):
self.item = item
self.prev = prev
self.next = next
def __init__(self):
self.sentinel = self.Node(None,None,None)
self.sentinel.prev = self.sentinel
self.sentinel.next = self.sentinel
self.len = 0
def length(self):
for k,v in enumerate(self,1):
pass
else:
assert k == self.len
return k
def __len__(self):
return self.len
def shift(self):
if self.sentinel.next is self.sentinel:
raise Exception("empty")
self.len -= 1
node = self.sentinel.next
self._remove(node)
return node.item
def unshift(self,item):
self.len += 1
#self._insert(item,self.sentinel.next)
self.sentinel.next = self.Node(item,self.sentinel,self.sentinel.next)
self.sentinel.next.next.prev = self.sentinel.next
return self.len
def push(self,item):
self.len += 1
self._insert(item,self.sentinel)
#self.sentinel.prev = self.Node(item,self.sentinel.prev,self.sentinel)
#self.sentinel.prev.prev.next = self.sentinel.prev
return self.len
def pop(self):
if self.sentinel.prev is self.sentinel:
raise Exception("empty")
self.len -= 1
node = self.sentinel.prev
self._remove(node)
#self.sentinel.prev.prev.next = self.sentinel.prev.next
#self.sentinel.prev = self.sentinel.prev.prev
return node.item
def indexOf(self,item):
for k,v in enumerate(self):
if v==item:
return k
else:
return -1
def lastIndexOf(self,item):
for k,v in enumerate(reversed(self)):
if v==item:
return k
else:
return -1
def slice(self,start,end):
l = self.__class__()
length = self.length()
begin = start+length if start<0 else start
stop = end+length if end<0 else end
for k,v in enumerate(self):
if k >= stop:
break
if k >= begin:
l.push(v)
return l
@classmethod
def _remove(cls,node):
node.prev.next = node.next
node.next.prev = node.prev
@classmethod
def _insert(cls,item,node):
node.prev.next = cls.Node(item,node.prev,node)
node.prev = node.prev.next
def splice(self,start,howmany,*items):
l = self.__class__()
length = self.length()
begin = start+length if start<0 else start
stop = begin + howmany
k, p = 0, self.sentinel.next
while p is not self.sentinel:
if k >= stop:
break
if k >= begin:
l.push(p.item)
self._remove(p)
self.len -= 1
p = p.next
k += 1
for i in items:
self.len += 1
self._insert(i,p)
return l
def _copy(self):
l = self.__class__()
for i in self:
l.push(i)
return l
def concat(self,*lists):
l = self._copy()
for i in lists:
for j in i:
l.push(j)
return l
def join(self,sep):
assert hasattr(sep,'join')
return sep.join(map(str,self))
def reverse(self):
p = self.sentinel
while True:
q = p.next
p.prev, p.next = p.next, p.prev
p = q
if p is self.sentinel:
break
def sort(self,cmp=lambda x,y:x-y):
rest = self.sentinel.next
while rest is not self.sentinel:
m, p =rest, rest.next
while p is not self.sentinel:
if cmp(p.item,m.item)<0:
m = p
p = p.next
if rest is m:
rest = m.next
#self._remove(m);self._insert(m.item,rest)
m.prev.next, m.next.prev = m.next, m.prev
m.prev, m.next = rest.prev, rest
rest.prev.next, rest.prev = m, m
def __iter__(self):
p = self.sentinel.next
while p is not self.sentinel:
yield p.item
p = p.next
def __reversed__(self):
p = self.sentinel.prev
while p is not self.sentinel:
yield p.item
p = p.prev
def __str__(self):
return ','.join(map(str,self))
def __repr__(self):
return '[%s]'%', '.join(map(str,self))
def valueOf(self):
return str(self)
def toString(self):
return repr(self)
def map(self,proc):
l = self.__class__()
for i in self:
l.push(proc(i))
return l
def forEach(self,proc):
for i in self:
proc(i)
这里通过私有的remove和insert方法来增删节点比直接增删节点要不容易错一些。
* 代码小练习二，仿JavaScript数组的实现。
接着前面的那一个再做个小练习，不过咱好菜呀，居然写得好费尽的感觉（沮丧。
下标和范围什么的总是搞错，单个函数一长的话就头晕晕的了，而且最后还是依赖调试了。
这样是不行的，真的不行的，在非类型安全的语言或者纸张上书写的话这样就写不出正确的代码是不行的。
嘛，或许再熟练一些就会好一些吧，对于常见的情况抽象为函数或固定的代码。恩，或许就是这样的。
<script>
var print = function(x) {
document.write(x);
document.writeln("<br>");
};
var p = print;
print("hello world");
function JArray() {
var that = (this instanceof arguments.callee) ? this : new arguments.callee();
if(arguments.length == 1 && this instanceof arguments.callee)
that.length = arguments[0];
else {
that.length = 0;
for(var i = 0; i < arguments.length; i++)
that.push(arguments[i])
}
return that;
};
JArray.prototype.push = function(item) {
this[this.length] = item;
return ++this.length;
};
JArray.prototype.pop = function(item) {
if(this.length == 0)
return undefined;
this.length--;
var item = this[this.length];
delete this[this.length];
return item;
};
JArray.prototype.shift = function() {
if(this.length == 0)
return undefined;
var item = this[0];
for(var i = 0; i < this.length; i++)
this[i] = this[i + 1];
this.length--;
delete this[this.length]
return item;
};
JArray.prototype.unshift = function(item) {
for(var i = this.length; i > 0; i--)
this[i] = this[i - 1];
this[0] = item;
return ++this.length;
};
JArray.prototype.join = function(sep) {
var sep = sep || ',';
var string = this.length == 0 ? "" : this[0];
for(var i = 1; i < this.length; i++) {
string += sep + this[i];
};
return string;
};
JArray.prototype.toString = function(item) {
return this.join();
};
JArray.prototype.slice = function(start, end) {
var array = new this.constructor();
var start = start < 0 ? start + this.length : start;
var end = end || this.length;
end = end < 0 ? end + this.length : end;
for(var i = start; i < end && i < this.length; i++)
array.push(this[i]);
return array;
};
JArray.prototype.indexOf = function(item) {
for(var i = 0; i < this.length; i++)
if(this[i] == item)
return i;
return -1;
};
JArray.prototype.lastIndexOf = function(item) {
for(var i = this.length - 1; i >= 0; i--)
if(this[i] == item)
return i;
return -1;
};
JArray.prototype.concat = function() {
var array = new this.constructor();
for(var i = 0; i < this.length; i++)
array.push(this[i]);
for(var i = 0; i < arguments.length; i++)
for(var j = 0; j < arguments[i].length; j++)
array.push(arguments[i][j]);
return array;
};
JArray.prototype.splice = function(index, howmany, item1) {
var array = new this.constructor();
var index = index < 0 ? index + this.length : index;
var howmany = Math.min(this.length - index, howmany);
var end = index + howmany;
for(var i = index; i < end; i++)
array.push(this[i]);
var itemnum = arguments.length - 2;
if(howmany > itemnum) {
var eat = howmany - itemnum;
for(var i = end; i < this.length; i++)
this[i - eat] = this[i];
for(var i = this.length - eat; i < this.length; i++)
delete this[i];
this.length -= eat;
} else {
var room = itemnum - howmany;
for(var i = this.length - 1; i >= index; i--)
this[i + room] = this[i];
this.length += room;
}
for(var i = 0; i < itemnum; i++)
this[index + i] = arguments[i + 2];
return array;
};
JArray.prototype.reverse = function(start, howmany, item1) {
for(var i = 0, j = this.length - 1; i < j; i++, j--) {
var tmp = this[i];
this[i] = this[j];
this[j] = tmp
};
};
JArray.prototype.sort = function(cmp) {
var cmp = cmp || (function(x, y) {
return x < y ? -1 : 1
});
var partition = function(array, x, y) {
var pivot = array[x];
var z = x;
for(var i = x + 1; i < y; i++) {
var tmp = array[i];
if(cmp(tmp, pivot) < 0) {
z++;
array[i] = array[z];
array[z] = tmp;
}
}
array[x] = array[z];
array[z] = pivot;
return z;
};
var qsort = function(array, x, y) {
if(x < y) {
var z = partition(array, x, y);
qsort(array, x, z);
qsort(array, z + 1, y);
}
};
qsort(this, 0, this.length);
return this;
};
JArray.prototype.forEach = function(proc) {
for(var i = 0; i < this.length; i++)
proc(this[i])
};
JArray.prototype.every = function(proc) {
for(var i = 0; i < this.length; i++)
if(!proc(this[i]))
return false;
return true;
};
</script>
测试代码没有贴，不过最好其实还是给每个方法都对应几种情况写好自动测试为好吧这样。
好写细节和js本身的Array不一样，比如一些可选参数的情况，这里仅做拙劣的练习就不完善它了。
link: https://developer.mozilla.org/en/JavaScript/New_in_JavaScript/1.6#Array_extras
* 代码小练习三，简单的关联数组。
一个简单的关联数组，key限定为字符串类型。
#include <iostream>
#include <cstring>
using namespace std;
template<class T>
class Hash{
class NotFound{};
class Full{};
struct Entry{
const char* key;
T value;
};
int _capacity;
Entry* table;
Entry* search(const char* key){
int hash = strhash(key)%_capacity;
for(int i=hash;i<hash+_capacity;i++){
Entry* entry = &table[i%_capacity];
if(entry->key==NULL || streq(entry->key,key))
return entry;
}
return NULL;
}
public:
static int strhash(const char* str){
int hash = 0;
for(const char* p = str; *p; p++)
hash = 31 * hash + *p;
return hash;
}
static bool streq(const char* str1,const char* str2){
return !strcmp(str1,str2);
}
Hash(int capacity)
:_capacity(capacity),table(new Entry[capacity]){
for(int i=0;i<capacity;i++)
table[i].key = NULL;
}
~Hash(){
delete[] table;
}
void put(const char* key,T value){
Entry* entry = this->search(key);
if(entry){
if(entry->key==NULL)
entry->key = key;
entry->value = value;
}else
throw Full();//"Full";
}
void del(const char* key){
Entry* entry = this->search(key);
if(entry && entry->key){
entry->key=NULL;
entry->value=NULL;
}
}
T get(const char* key){
Entry* entry = this->search(key);
if(entry && entry->key)
return entry->value;
else
throw NotFound();//"Not Found";
}
bool has(const char* key){
Entry* entry = this->search(key);
return entry && entry->key;
}
};
int main(int argc, char **argv)
{
cout<<"hello world"<<endl;
Hash<int> hash(100);
cout<<hash.has("a")<<endl;
hash.put("a",125);
hash.put("b",128);
cout<<hash.has("a")<<endl;
cout<<hash.has("b")<<endl;
cout<<hash.get("b")<<endl;
hash.del("b");
cout<<hash.has("b")<<endl;
//cout<<hash.get("c")<<endl;
return 0;
}
* 代码练习四，优先队列。
没有评论:
发表评论