D2-读论文D2&算法题D2（复习：单链表、双链表、模拟栈）

---------0702读了4篇论文~现在做一下算法题，然后去干饭！！！

注意删除头结点时，h已经指向第一个节点了，只需要将h赋值为ne[h]（第二个节点即可）

m = int(input())
N = 100010
idx,h=1,-1
e,ne = [0]*N, [0]*N

def insert_h(x):
    global h,idx
    e[idx] = x
    ne[idx] = h
    h = idx
    idx += 1

def rem(k):
    global h
    if k==0:
        # h已经指向下一个了，所以擅长出的时候直接赋值ne[h]即可
        h = ne[h]
    else:  
        ne[k] = ne[ne[k]]

def insert(k,x):
    global idx
    e[idx] = x
    ne[idx] = ne[k]
    ne[k] = idx
    idx += 1

for _ in range(m):
    op, *pt = input().split()
    if op=='H':
        x = int(pt[0])
        insert_h(x)
    elif op=='D':
        k = int(pt[0])
        rem(k)
    else:
        k,x = map(int, pt)
        insert(k, x)

while h!=-1:
    print(e[h], end=' ')
    h = ne[h]
    


    

问题非常多，需要加练！
1、idx是从2开始，所以第k个数的idx是k+1
2、insert时赋值的顺序要明确，不要忘记写，确保有4个线
3、rem时明确赋值对象是谁，脑子里要有图。

m = int(input())
N = 100010
h,t = 0,1
e,l,r =[0]*N,[0]*N,[0]*N
# idx从k开始，所以第k个数是k+1
idx = 2

# 初始化
r[h] = 1
l[t] = 0

def insert(k,x):
    # 从第k个数的右侧插入一个数x
    global idx
    e[idx] = x
    r[idx] = r[k]
    # 没有写l[idx]
    l[idx] = k
    l[r[k]] = idx
    # 是r[k]，而不是k
    r[k] = idx
    idx += 1

def rem(k):
    # 写反了
    # r[k] = r[l[k]]
    # l[k] = l[r[k]]
    l[r[k]] = l[k]
    r[l[k]] = r[k]
for _  in range(m):
    op, *pt = input().split()
    if op=='L':
        x = int(pt[0])
        insert(0,x)
    elif op=='R':
        x = int(pt[0])
        insert(l[1],x)
    elif op=='D':
        k = int(pt[0])+1
        rem(k)
    elif op=='IL':
        k,x = map(int, pt)
        insert(l[k+1], x)
    else:
        k,x = map(int,pt)
        insert(k+1, x)
h = r[h]
while h!=1:
    print(e[h], end=' ')
    h = r[h]

模拟栈做的很顺畅！！！但需要注意以下问题：
1、tt从0开始；是否为空，用tt>0判断，>0是不为空
；push元素时，tt先+1
2、试了一下，把global tt在所有函数外声明还是不管用，需要在函数内进行global声明。【有时间应该去弄清楚python的变量定义域机制是怎么work的】

m = int(input())
N = 100010
stk = [0]*N
tt = 0

def push(x):
    global tt
    tt += 1
    stk[tt] = x

def pop():
    global tt
    tt -= 1

def empty():
    global tt
    if tt>0:
        return False
    else:
        return True

def query():
    global tt
    return stk[tt]

for _ in range(m):
    op, *pt = input().split()
    if op=='push':
        x = int(pt[0])
        push(x)
    elif op=='pop':
        pop()
    elif op=='empty':
        if empty():
            print('YES')
        else:
            print('NO')
    else:
        print(query())

—0747今天已经在算法上用了40~50分钟（没错，45min）了，就不学新的了。明天继续复习一下双链表（今天做的不好），再写一道新题。吃早饭去啦！！！

----2007跑完步，洗完澡，边吃豆干边写总结。打算一会看会图论。