Part1:回顾

1.线性表

这里引用老师的介绍。

线性表比较常用，比如python中的list的就是线性表，由于python自带，所以这里没有自己实现一遍。

2.堆栈(Stack)

堆栈是一种特殊的线性表，只在栈顶插入删除数据，插入操作称为入栈(Push)，删除操作称为出栈(Pop)。栈的最大特点为后入先出Last In First Out(LIFO)。栈在生活中也是比较常见的，例如碗，我们一般会将新的碗放在最上面，用碗的时候也会拿最上面的碗，还有一个例子是夏天冰箱里的饮料，我们一般会拿最外层的，放饮料的时候也会放在最外层。
下面是老师的介绍。

第一周的部分使用c语言实现的，但是我指针后面部分都不大会，正在恶补，故这里使用python实现。

# -*- coding: utf-8 -*-
"""
Created on Sat Mar 24 11:11:38 2018

@author: Administrator
"""

#实现栈
class Stack():
    def __init__(self,size):
        self.size=size
        self.stack=[]
        self.top=-1
        
    def isfull(self):
        return self.size==(self.top+1)
    
    def push(self,x):
        if self.isfull():
            return 'stack is full'
        else:
            self.stack.append(x)
            self.top+=1
    
    def isempty(self):
        return self.top==(-1)
    
    def pop(self):
        if self.isempty():
            return 'stack is empty'
        else:
            self.top-=1
            b=self.stack.pop()
            return b
            
    def show(self):
        return self.stack
    
a=Stack(5)
print a.isfull()
print a.isempty()

a.push(4)
print a.show()

b=a.pop()
print a.show(),b

3.队列(Queue)

队列也是一种特殊的线性表，在一端插入数据，另一端删除数据。插入操作称为入队列(AddQ)，删除操作称为出队列(DeleteQ)。队列的最大特点为先入先出(FIFO)。这是和栈很大的不同之处。队列在生活中也非常常见，例如排队的例子。
下面是老师的介绍。

# -*- coding: utf-8 -*-
"""
Created on Sat Mar 24 12:15:02 2018

@author: Administrator
"""

class Queue():
    def __init__(self,size):
        self.size=size
        self.queue=[]
        self.front=0
        self.rear=0
        
    def isfull(self):
        return self.size==(self.rear-self.front+1)
    
    def addq(self,x):
        if self.isfull():
            return 'queue is full'
        else:
            self.queue.append(x)
            self.rear+=1
    
    def isempty(self):
        return self.front==self.rear
    
    def deleteq(self):
        if self.isempty():
            return 'queue is empty'
        else:
            self.front+=1
            b=self.queue.pop(0)
            return b
            
    def show(self):
        return self.queue
    
q=Queue(10)
for i in range(5):
    q.addq(i)
    print q.show(),q.front,q.rear
for i in range(5):
    print q.deleteq()
    print q.show(),q.front,q.rear

Part2:作业

再来看下这周的几个习题。

作业1
一元多项式的乘法与加法运算

设计函数分别求两个一元多项式的乘积与和。
输入格式:

输入分2行，每行分别先给出多项式非零项的个数，再以指数递降方式输入一个多项式非零项系数和指数（绝对值均为不超过1000的整数）。数字间以空格分隔。
输出格式:

输出分2行，分别以指数递降方式输出乘积多项式以及和多项式非零项的系数和指数。数字间以空格分隔，但结尾不能有多余空格。零多项式应输出0 0。
输入样例:

4 3 4 -5 2 6 1 -2 0
3 5 20 -7 4 3 1
输出样例:

15 24 -25 22 30 21 -10 20 -21 8 35 6 -33 5 14 4 -15 3 18 2 -6 1
5 20 -4 4 -5 2 9 1 -2 0

加法比较容易，使用数组完成。从最高次数n开始，如果两个多项式都有次数n的项，则系数相加，如果系数为不为0，记录下此项。如果只有一个多项式有n次项，则直接记录，以此类推。值得注意的一点是，测试案例中零多项式表示为0，这点要单独处理。
乘法的思路是拆为多个加法，先将多项式a的每项依次乘以多项式b，再相加即可。

# -*- coding: utf-8 -*-
"""
Created on Thu Mar 22 20:47:01 2018

@author: Administrator
"""

a=raw_input()
b=raw_input()

a=a.split(' ')
b=b.split(' ')


poly_1=[]
poly_2=[]

for i in a:
    if i!=' ' and i!='':
        poly_1.append(i)

for i in b:
    if i!=' ' and i!='':
        poly_2.append(i)

poly1=map(int,poly_1)
poly2=map(int,poly_2)

'''
poly1=[]
poly2=[]
'''
'''for i in poly_1:
    if i!=' ':
        poly1.append(i)

for i in poly_2:
    if i!=' ':
        poly2.append(i)'''

#读取每项对应的系数，要考虑常数项的情形
#a为次数，b为系数
if len(poly1)>1 and len(poly2)>1:
    poly1_a=poly1[1::2]
    poly1_b=poly1[2::2]    
    poly2_a=poly2[1::2]
    poly2_b=poly2[2::2]
elif len(poly1)==1 and len(poly2)>1:
    poly2_a=poly2[1::2]
    poly2_b=poly2[2::2]   
    poly1_a=[0]
    poly1_b=[0]
elif len(poly2)==1 and len(poly1)>1:
    poly1_a=poly1[1::2]
    poly1_b=poly1[2::2]
    poly2_a=[0]
    poly2_b=[0]        
else:
    poly2_a=[0] 
    poly2_b=[0]
    poly1_a=[0]    
    poly1_b=[0]
    
def polyplus(poly1a,poly1b,poly2a,poly2b):
    if poly1a[0]==0 and poly1b[0]==0:
        return poly2a,poly2b
    elif poly2a[0]==0 and poly2b[0]==0:
        return poly1a,poly1b
    else:
        l1=len(poly1a)
        l2=len(poly2a)
        
        #polya表示系数，polyb表示指数    
        poly3a=[]
        poly3b=[]
        
        i=0
        j=0
        while(i<l1 and j<l2):
            if poly1b[i]>poly2b[j]:
                poly3b.append(poly1b[i])
                poly3a.append(poly1a[i])
                i+=1
            elif poly1b[i]<poly2b[j]:
                poly3b.append(poly2b[j])
                poly3a.append(poly2a[j])
                j+=1
            else:
                temp=poly2a[j]+poly1a[i]
                if temp!=0:
                    poly3b.append(poly2b[j])
                    poly3a.append(temp)
                i+=1
                j+=1
        if i==l1:
            poly3b+=poly2b[j:]
            poly3a+=poly2a[j:]
        else:
            poly3b+=poly1b[i:]
            poly3a+=poly1a[i:]
        if poly3a!=[] and poly3b!=[]:
            return poly3a,poly3b
        else:
            return 0,0
        #print poly3a,poly3b

def polymultiply(poly1a,poly1b,poly2a,poly2b):
    if poly1a[0]==0 and poly1b[0]==0:
        return 0,0
    elif poly2a[0]==0 and poly2b[0]==0:
        return 0,0
    else:
        l1=len(poly1a)
        l2=len(poly2a)
        
        poly3_a=map(lambda x:x*poly1a[0],poly2a)
        poly3_b=map(lambda x:x+poly1b[0],poly2b)
        
        i=1
        while (i<l1):
            tempa=map(lambda x:x*poly1a[i],poly2a)
            tempb=map(lambda x:x+poly1b[i],poly2b)
            poly3_a,poly3_b=polyplus(poly3_a,poly3_b,tempa,tempb)
            i+=1
        return poly3_a,poly3_b

p1,p2=polyplus(poly1_a,poly1_b,poly2_a,poly2_b)
m1,m2=polymultiply(poly1_a,poly1_b,poly2_a,poly2_b)
if m1==0 and m2==0:
    print '0 0'
else:
    leng=len(m1)
    for i in range(leng):
        if i<leng-1:
            print m1[i],m2[i],
        else:
            print m1[i],m2[i]
if p1==0 and p2==0:
    print '0 0'
else:
    leng=len(p1)
    for i in range(leng):
        if i<leng-1:
            print p1[i],p2[i],
        else:
            print p1[i],p2[i]

作业2
Reversing Linked List

Given a constant K and a singly linked list L, you are supposed to reverse the links of every K elements on L. For example, given L being 1→2→3→4→5→6, if K=3, then you must output 3→2→1→6→5→4; if K=4, you must output 4→3→2→1→5→6.
Input Specification:

Each input file contains one test case. For each case, the first line contains the address of the first node, a positive N (≤10^5 ) which is the total number of nodes, and a positive K (≤N) which is the length of the sublist to be reversed. The address of a node is a 5-digit nonnegative integer, and NULL is represented by -1.

Then N lines follow, each describes a node in the format:
Address Data Next
where Address is the position of the node, Data is an integer, and Next is the position of the next node.

Output Specification:
For each case, output the resulting ordered linked list. Each node occupies a line, and is printed in the same format as in the input.

Sample Input:
00100 6 4
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218

Sample Output:
00000 4 33218
33218 3 12309
12309 2 00100
00100 1 99999
99999 5 68237
68237 6 -1

这题刚看的时候感觉挺难，后来想了下只要找到每个元素对应的头结点，按照头尾的关系排序，然后将数组反过来，数组的尾节点指向下一个元素即可。但这题遗留了一个问题，当输入量太大的时候运行会超时，也尝试将列表改为字典，但是依旧超时，只能暂时保留了。

# -*- coding: utf-8 -*-
"""
Created on Fri Mar 23 12:38:13 2018

@author: 715073608
"""

'''
00100 7 4
00000 4 99999
00100 1 12309
68237 6 -1
11111  8  44444
33218 3 00000
99999 5 68237
12309 2 33218
'''

##读取数据
a=raw_input('')
a=a.split(' ')

b=[]
for i in range(int(a[1])):
    temp=raw_input('')
    temp=temp.split(' ')
    b.append(temp)

##按顺序重新排列
c=[]
pos=a[0]
for i in range(int(a[1])):
    for j in b:
        if j[0]==pos:
            #c.append(i)
            c.append(j[:-1])
            pos=j[2]
            break

##reverse数据
k=int(a[2])
m=len(c)
n=m/k

d=[]
for i in range(n):
    temp=c[i*k:(i+1)*k][:]
    temp.reverse()
    d+=temp
d+=c[n*k:]

#输出结果
for i in range(m-1):
    print d[i][0]+' '+d[i][1]+' '+d[i+1][0]
print d[-1][0]+' '+d[-1][1]+' '+'-1'

作业3
Pop Sequence

Given a stack which can keep M numbers at most. Push N numbers in the order of 1, 2, 3, …, N and pop randomly. You are supposed to tell if a given sequence of numbers is a possible pop sequence of the stack. For example, if M is 5 and N is 7, we can obtain 1, 2, 3, 4, 5, 6, 7 from the stack, but not 3, 2, 1, 7, 5, 6, 4.

Input Specification:
Each input file contains one test case. For each case, the first line contains 3 numbers (all no more than 1000): M (the maximum capacity of the stack), N (the length of push sequence), and K (the number of pop sequences to be checked). Then K lines follow, each contains a pop sequence of N numbers. All the numbers in a line are separated by a space.

Output Specification:
For each pop sequence, print in one line “YES” if it is indeed a possible pop sequence of the stack, or “NO” if not.

Sample Input:
5 7 5
1 2 3 4 5 6 7
3 2 1 7 5 6 4
7 6 5 4 3 2 1
5 6 4 3 7 2 1
1 7 6 5 4 3 2

Sample Output:
YES
NO
NO
YES
NO

这题的意思是判断这些序列能否按照堆栈的后进后出的规则输出。思路是先按照题目的顺序入栈，如果栈顶的元素和目标队列第一个元素相同，那么该元素出栈，删除目标的第一个元素，重复此操作即可。

# -*- coding: utf-8 -*-
"""
Created on Sat Mar 24 11:23:23 2018

@author: Administrator
"""

#定义栈
class Stack():
    def __init__(self,size):
        self.size=size
        self.stack=[]
        self.top=-1
        
    def isfull(self):
        return self.size==(self.top+1)
    
    def push(self,x):
        if self.isfull():
            return 'stack is full'
        else:
            self.stack.append(x)
            self.top+=1
    
    def isempty(self):
        return self.top==(-1)
    
    def pop(self):
        if self.isempty():
            return 'stack is empty'
        else:
            self.top-=1
            self.stack.pop()
            #return b
            
    def show(self):
        return self.stack
    
#读取数据 
a=raw_input()
b=map(int,a.split(' '))
c=[]

for i in range(b[2]):
    temp=raw_input()
    c.append(map(int,temp.split(' ')))


#思路是按照1到n输入，如果碰到栈尾的元素和给出的序列相同，则抛出这个元素，序列删除这个元素，以此循环

def isstack(x,size,num):
    b=[]
    a=Stack(size)
    for i in range(1,num+1):
        if not a.isfull():
            a.push(i)
        while not a.isempty() and a.show()[-1]==x[0]:
            del x[0]
            a.pop()
    if len(a.show())==0:
        print 'YES'
    else:
        print 'NO'

for i in c:
    isstack(i,b[0],b[1])    
'''
[1,2,3,4,5,6,7]
[3,2,1,7,5,6,4]
[7,6,5,4,3,2,1]
[5,6,4,3,7,2,1]
[1,7,6,5,4,3,2]
'''
'''
isstack([1,2,3,4,5,6,7],5,7)
isstack([3,2,1,7,5,6,4],5,7)
isstack([7,6,5,4,3,2,1],5,7)
isstack([5,6,4,3,7,2,1],5,7)
isstack([1,7,6,5,4,3,2],5,7)
'''