Python 구현 링크 인 스 턴 스 코드

Python 구현 링크 인 스 턴 스 코드
머리말
알고리즘 과 데이터 구 조 는 영원히 변 하지 않 는 화제 로 프로그래머 로 서 자주 사용 하 는 데이터 구 조 를 파악 하 는 것 이 매우 필요 하 다.
구현 목록
링크 를 실현 하 는 것 은 본질 적 으로 언어 와 무관 하 다.그러나 유연성 은 그 언어 를 실현 하 는 것 과 밀접 한 관 계 를 가진다.오늘 은 Python 으로 다음 작업 을 수행 합 니 다.

['addNode(self, data)']
['append(self, value)']
['prepend(self, value)']
['insert(self, index, value)']
['delNode(self, index)']
['delValue(self, value)']
['isempty(self)']
['truncate(self)']
['getvalue(self, index)']
['peek(self)']
['pop(self)']
['reverse(self)']
['delDuplecate(self)']
['updateNode(self, index, value)']
['size(self)']
['print(self)']

이런 방법 목록 을 만 드 는 것 은 틀림없이 수 동 으로 쓸 수 없 을 것 이다.그렇지 않 으 면 얼마나 번 거 로 울 까.그래서 나 는 프로그램 을 써 서 자신 이 실현 하 는 방법 과 일치 하도록 했다.코드 가 비교적 간단 하고 핵심 적 인 사 고 는 원본 파일 의 모든 줄 과 일치 하 며 일치 하 는 규칙 에 맞 는 내용 을 찾 아 전체 결과 에 집중 하 는 것 입 니 다.
코드 는 다음 과 같 습 니 다:

# coding: utf8

# @Author:    
# @File: getmethods.py                                 
# @Time: 2017/4/5                  
# @Contact: [email protected]
# @blog: http://blog.csdn.net/marksinoberg
# @Description:                     

import re

def parse(filepath, repattern):
  with open(filepath, 'rb') as f:
    lines = f.readlines()
  #      
  rep = re.compile(repattern)
  #                  
  result = []
  #          
  for line in lines:
    res = re.findall(rep, str(line))
    print("{}     {}".format(str(line), res))
    if len(res)!=0 or res is not None:
      result.append(res)
    else:
      continue
  return [item for item in result if item !=[]]


if __name__ == '__main__':
  repattern = "def (.[^_0-9]+\(.*?\)):"
  filepath = './SingleChain.py'
  result = parse(filepath, repattern)
  for item in result:
    print(str(item))

링크 구현

# coding: utf8

# @Author:    
# @File: SingleChain.py                                 
# @Time: 2017/4/5                  
# @Contact: [email protected]
# @blog: http://blog.csdn.net/marksinoberg
# @Description:      

class Node(object):
  def __init__(self, data, next):
    self.data = data
    self.next = next

class LianBiao(object):

  def __init__(self):
    self.root = None

  #           
  def addNode(self, data):
    if self.root==None:
      self.root = Node(data=data, next=None)
      return self.root
    else:
      #     ，          ，        
      cursor = self.root
      while cursor.next!= None:
        cursor = cursor.next
      cursor.next = Node(data=data, next=None)
      return self.root

  #            ，    addNode    
  def append(self, value):
    self.addNode(data=value)

  #          
  def prepend(self, value):
    if self.root == None:
      self.root = Node(value, None)
    else:
      newroot = Node(value, None)
      #   root  
      newroot.next = self.root
      self.root = newroot

  #             
  def insert(self, index, value):
    if self.root == None:
      return
    if index<=0 or index >self.size():
      print('index %d   ，                     ！')
      return
    elif index==1:
      #   index==1，           
      self.prepend(value)
    elif index == self.size()+1:
      #   index           ，        
      self.append(value)
    else:
      #   ，          ，        。              
      counter = 2
      pre = self.root
      cursor = self.root.next
      while cursor!=None:
        if counter == index:
          temp = Node(value, None)
          pre.next = temp
          temp.next = cursor
          break
        else:
          counter += 1
          pre = cursor
          cursor = cursor.next

  #           
  def delNode(self, index):
    if self.root == None:
      return
    if index<=0 or index > self.size():
      return
    #             
    if index == 1:
      self.root = self.root.next
    else:
      pre = self.root
      cursor = pre.next
      counter = 2
      while cursor!= None:
        if index == counter:
          print('can be here!')
          pre.next = cursor.next
          break
        else:
          pre = cursor
          cursor = cursor.next
          counter += 1

  #     value       
  def delValue(self, value):
    if self.root == None:
      return
    #             
    if self.root.data == value:
      self.root = self.root.next
    else:
      pre = self.root
      cursor = pre.next
      while cursor!=None:
        if cursor.data == value:
          pre.next = cursor.next
          #           ，        。。。
          cursor = cursor.next
          continue
        else:
          pre = cursor
          cursor = cursor.next

  #         
  def isempty(self):
    if self.root == None or self.size()==0:
      return True
    else:
      return False

  #             
  def truncate(self):
    if self.root == None or self.size()==0:
      return
    else:
      cursor = self.root
      while cursor!= None:
        cursor.data = None
        cursor = cursor.next
      self.root = None
      cursor = None

  #            
  def getvalue(self, index):
    if self.root is None or self.size()==0:
      print('      ！')
      return None
    if index<=0 or index>self.size():
      print("index %d   ！"%index)
      return None
    else:
      counter = 1
      cursor = self.root
      while cursor is not None:
        if index == counter:
          return cursor.data
        else:
          counter += 1
          cursor = cursor.next

  #         ，         
  def peek(self):
    return self.getvalue(self.size())

  #           ，        
  def pop(self):
    if self.root is None or self.size()==0:
      print('        ！')
      return None
    elif self.size()==1:
      top = self.root.data
      self.root = None
      return top
    else:
      pre = self.root
      cursor = pre.next
      while cursor.next is not None:
        pre = cursor
        cursor = cursor.next
      top = cursor.data
      cursor = None
      pre.next = None
      return top

  #        
  def reverse(self):
    if self.root is None:
      return
    if self.size()==1:
      return
    else:
      # post = None
      pre = None
      cursor = self.root
      while cursor is not None:
        # print('        ')
        post = cursor.next
        cursor.next = pre
        pre = cursor
        cursor = post
      #                   root，        
      self.root = pre

  #           
  def delDuplecate(self):
    #     map     ，      “   ”
    dic = {}
    if self.root == None:
      return
    if self.size() == 1:
      return
    pre = self.root
    cursor = pre.next
    dic = {}
    #      
    temp = self.root
    while temp!=None:
      dic[str(temp.data)] = 0
      temp = temp.next
    temp = None
    #              
    while cursor!=None:
      if dic[str(cursor.data)] == 1:
        pre.next = cursor.next
        cursor = cursor.next
      else:
        dic[str(cursor.data)] += 1
        pre = cursor
        cursor = cursor.next


  #           
  def updateNode(self, index, value):
    if self.root == None:
      return
    if index<0 or index>self.size():
      return
    if index == 1:
      self.root.data = value
      return
    else:
      cursor = self.root.next
      counter = 2
      while cursor!=None:
        if counter == index:
          cursor.data = value
          break
        cursor = cursor.next
        counter += 1


  #         
  def size(self):
    counter = 0
    if self.root == None:
      return counter
    else:
      cursor = self.root
      while cursor!=None:
        counter +=1
        cursor = cursor.next
      return counter


  #         
  def print(self):
    if(self.root==None):
      return
    else:
      cursor = self.root
      while cursor!=None:
        print(cursor.data, end='\t')
        cursor = cursor.next
      print()


if __name__ == '__main__':
  #         
  lianbiao = LianBiao()
  #           
  print("    %d"%lianbiao.isempty())
  #           
  lianbiao.addNode(1)
  print("    %d"%lianbiao.isempty())
  #       ，    
  lianbiao.addNode(2)
  lianbiao.addNode(3)
  lianbiao.addNode(4)
  lianbiao.addNode(6)
  lianbiao.addNode(5)
  lianbiao.addNode(6)
  lianbiao.addNode(7)
  lianbiao.addNode(3)
  #          
  print('         ')
  lianbiao.print()
  #       size   
  print("   size: "+str(lianbiao.size()))
  #             
  print('            ')
  print(lianbiao.getvalue(1))
  print(lianbiao.getvalue(lianbiao.size()))
  print(lianbiao.getvalue(7))
  #           ，       
  print('          ，       ')
  lianbiao.delNode(4)
  lianbiao.print()
  lianbiao.delValue(3)
  lianbiao.print()
  #           
  print('          ')
  lianbiao.delDuplecate()
  lianbiao.print()
  #               
  print('              ')
  lianbiao.updateNode(6, 99)
  lianbiao.print()
  #            
  print('           ')
  lianbiao.prepend(77)
  lianbiao.prepend(108)
  lianbiao.print()
  #            
  print('           ')
  lianbiao.append(99)
  lianbiao.append(100)
  lianbiao.print()
  #            
  print('           ')
  lianbiao.insert(1, 10010)
  lianbiao.insert(3, 333)
  lianbiao.insert(lianbiao.size(), 99999)
  lianbiao.print()
  #   peek   
  print('  peek   ')
  print(lianbiao.peek())
  lianbiao.print()
  #   pop   
  print('  pop   ')
  print(lianbiao.pop())
  lianbiao.print()
  #           
  print('          ')
  lianbiao.reverse()
  lianbiao.print()
  #      truncate  
  print('     truncate  ')
  lianbiao.truncate()
  lianbiao.print()

코드 가 실 행 된 결 과 는 어 떻 습 니까?우리 의 요 구 를 만족 시 킬 수 있 는 지,인쇄 결 과 를 보십시오.

D:\Software\Python3\python.exe E:/Code/Python/Python3/CommonTest/datastructor/SingleChain.py
    1
    0
         
1  2  3  4  6  5  6  7  3  
   size: 9
            
1
3
6
          ，       
can be here!
1  2  3  6  5  6  7  3  
1  2  6  5  6  7  
          
1  2  6  5  7  
              
1  2  6  5  7  
           
108 77 1  2  6  5  7  
           
108 77 1  2  6  5  7  99 100 
           
10010  108 333 77 1  2  6  5  7  99 99999  100 
  peek   
100
10010  108 333 77 1  2  6  5  7  99 99999  100 
  pop   
100
10010  108 333 77 1  2  6  5  7  99 99999  
          
99999  99 7  5  6  2  1  77 333 108 10010  
     truncate  

Process finished with exit code 0

목표 수 요 를 마침 실현 하 였 다.
총결산
오늘 의 내용 은 여전히 비교적 기본 적 이 고 어 려 운 점도 없다.하지만 알 아 보 는 것 과 쓸 줄 아 는 것 은 별 개의 일이 다.일이 없 을 때 이런 코드 를 쓰 는 것 은 수확 이 많다.