python 알고리즘 과 데이터 구조의 단일 체인 테이블 의 실현 코드

링크
링크 는 물리 적 저장 장치 에서 비 연속 적 이 고 비 순서 적 인 저장 구조 로 데이터 요소 의 논리 적 순 서 는 링크 의 포인터 링크 순 서 를 통 해 이 루어 진다.체인 테이블 은 일련의 결점(체인 테이블 의 모든 원 소 를 결점 이 라 고 부른다)으로 구성 되 어 있 으 며 결점 은 운행 할 때 동적 으로 생 성 될 수 있다.각 노드 는 두 부분 을 포함한다.하 나 는 데이터 요 소 를 저장 하 는 데이터 필드 이 고 다른 하 나 는 다음 노드 주 소 를 저장 하 는 포인터 필드 이다.선형 표 순서 구조 에 비해 조작 이 복잡 하 다.순서대로 저장 하지 않 아 도 되 기 때문에 링크 는 삽입 할 때 O(1)의 복잡 도 에 이 를 수 있 고 다른 선형 표 순서 표 보다 훨씬 빠 르 지만 한 노드 를 찾 거나 특정한 번 호 를 방문 하 는 노드 는 O(n)의 시간 이 필요 하 며 선형 표 와 순서 표 에 해당 하 는 시간 복잡 도 는 각각 O(logn)와 O(1)이다.
링크 구 조 를 사용 하면 배열 링크 는 데이터 크기 의 단점 을 미리 알 아야 한다.링크 구 조 는 컴퓨터 메모리 공간 을 충분히 이용 하여 유연 한 메모리 동적 관 리 를 실현 할 수 있다.그러나 링크 는 배열 이 무 작위 로 읽 는 장점 을 잃 었 고 링크 는 결점 의 지침 도 메 인 을 증가 하기 때문에 공간 비용 이 비교적 크다.링크 의 가장 뚜렷 한 장점 은 일반적인 배열 과 관련 된 항목 을 배열 하 는 방식 이 메모리 나 디스크 에서 의 순서 와 다 를 수 있 고 데이터 의 액세스 가 서로 다른 배열 순서 에서 전환 되 어야 한 다 는 것 이다.링크 는 표 의 임의의 위치 에 있 는 노드 를 삽입 하고 제거 할 수 있 으 나 무 작위 액세스 가 허용 되 지 않 습 니 다.링크 는 여러 가지 유형 이 있 는데 그것 이 바로 단 방향 링크,양 방향 링크 와 순환 링크 이다.
2.단일 체인 표 소개
단 방향 링크(단일 링크)는 링크 의 하나 로 링크 의 링크 방향 이 단 방향 이 고 링크 에 대한 방문 은 순서대로 읽 어야 머리 부터 시작 하 는 것 이 특징 이다.단일 체인 테이블 은 체인 액세스 의 데이터 구조 로 주소 가 임의의 저장 장치 로 선형 테이블 의 데이터 요 소 를 저장 합 니 다.링크 의 데 이 터 는 노드 로 표 시 됩 니 다.모든 노드 의 구성:요소(데이터 요소 의 이미지)+포인터(후계 요소 의 저장 위 치 를 표시 합 니 다)요 소 는 데 이 터 를 저장 하 는 저장 장치 이 고 지침 은 모든 노드 를 연결 하 는 주소 데이터 입 니 다.그것 의 각 노드 는 두 개의 도 메 인,하나의 정보 도 메 인(원소 도 메 인)과 하나의 링크 도 메 인 을 포함한다.이 링크 는 링크 의 다음 노드 를 가리 키 고 마지막 노드 의 링크 도 메 인 은 빈 값 을 가리킨다.
체인 식 저장 구조의 선형 표 는 임의의 저장 장치 로 선형 표 의 데이터 요 소 를 저장 할 것 이다.순서대로 저장 할 필요 가 없 기 때문에 링크 는 데이터 요 소 를 삽입 하고 삭제 할 때 순서 적 으로 저장 하 는 것 보다 빠 르 지만 한 노드 를 찾 을 때 순서 적 으로 저장 하 는 것 보다 느 리 고 체인 식 저장 을 사용 하면 순서 선형 표를 극복 할 수 있 으 며 데이터 크기 의 단점 을 미리 알 아야 한다.링크 구 조 는 메모리 공간 을 충분히 이용 하여 유연 한 메모리 동적 관 리 를 실현 할 수 있다.그러나 체인 저장 소 는 배열 의 랜 덤 액세스 특징 을 잃 었 고 노드 의 지침 도 메 인 을 추 가 했 기 때문에 공간 비용 이 비교적 크다.
3.단일 체인 표 구조

표 요소 도 메 인 elem 은 구체 적 인 데 이 터 를 저장 하 는 데 사 용 됩 니 다

링크 도 메 인 next 는 다음 노드 의 위치(python 의 표지)를 저장 하 는 데 사 용 됩 니 다

4.567917.변수 p 는 링크 의 머리 노드(첫 번 째 노드)의 위 치 를 가리 키 고 p 에서 출발 하여 표 의 임 의 노드 를 찾 을 수 있 습 니 다4.단일 체인 표 의 상용 조작 도해
1.플러그

2.꼬리 꽂 기

3.삽입 으로 지정

4.삭제

5.단일 체인 시트 의 python 코드 구현

#     
class Node(object):
  def __init__(self,item):
    self.element = item
    self.next = None
#       
class SingleLinkList(object):
  def __init__(self):
    self.header = None
    self.length = 0
  # 1、      
  def is_empty(self):
    if self.header == None:
      return True
    else:
      return False
  # 2、    
  def add(self,node):
    if self.is_empty():
      self.header = node
    else:
      node.next = self.header
      self.header = node
      # currentNode = self.header
    self.length += 1
  # 3、    
  def appent(self,node):
    currentNode = self.header
    if self.is_empty():
      self.add(node)
    else:
      while (currentNode.next != None):
        currentNode = currentNode.next
      currentNode.next = node
      self.length += 1
  # 4、      
  def insert(self,node,index):
    currentNode = self.header
    if index>self.length+1 or index<=0:
      print("         ，       ")
    if index == 1:
      self.add(node)
    elif index == 2:
      node.next = self.header.next
      self.header.next = node
      self.length += 1
    else:
      for i in range(1,index-1):
        currentNode = currentNode.next
      node.next = currentNode.next
      currentNode.next = node
      self.length += 1
  # 5、  
  def travel(self):
    currentNode = self.header
    if self.length == 0:
      print("           
")
    else:
      print("             :",end=" ")
      for i in range(self.length):
        print("%s "%currentNode.element,end=" ")
        currentNode = currentNode.next
      print("
")
  # 6、           ，            
  def list_sort(self):
    for i in range(0,self.length-1):
      currentNode = self.header
      for j in range(0,self.length-i-1):
        if currentNode.element > currentNode.next.element:
          temp = currentNode.element
          currentNode.element = currentNode.next.element
          currentNode.next.element = temp
        currentNode = currentNode.next
  # 7、     
  def remove(self,index):
    if index<=0 or index>self.length:
      print("        ，     ")
      return
    else:
      if index == 1:
        self.header = self.header.next
        currentNode = self.header
      elif index == 2:
        currentNode = self.header
        currentNode.next = currentNode.next.next
      else:
        currentNode = self.header
        for i in range(1,index-1):
          currentNode = currentNode.next
        currentNode.next = currentNode.next.next
    self.length -= 1
  # 8、      ,     
  def isContain(self,num):
    contain = 0
    currentNode = self.header
    for i in range(self.length):
      if currentNode.element == num:
        print("%d    %d 
"%(num,i))
        contain = 1
      currentNode = currentNode.next
    if contain == 0:
      print("%d     
"%num)
  # 9、       
  def searchNodeByIndex(self,index):
    currentNode = self.header
    if index<=0 or index>self.length:
      print("        ，     
")
      return 0
    else:
      for i in range(index-1):
        currentNode = currentNode.next
      return currentNode
  # 10、          
  def modifyByIndex(self,index,num):
    currentNode = self.header
    if index<=0 or index>self.length:
      print("        ，     
")
    else:
      for i in range(index-1):
        currentNode = currentNode.next
      currentNode.element = num
def main():
  #         
  node1 = Node(1)
  #          
  single_link_list = SingleLinkList()
  print("        ")
  single_link_list.travel()
  print("    ")
  single_link_list.add(node1)
  single_link_list.travel()
  print("    ")
  node2 = Node(2)
  single_link_list.appent(node2)
  single_link_list.travel()
  print("       ")
  node3 = Node(3)
  single_link_list.insert(node3,1)
  single_link_list.travel()
  print("      ")
  node4 = Node(5)
  single_link_list.add(node4)
  single_link_list.travel()
  print("         ")
  node5 = Node(4)
  single_link_list.insert(node5,4)
  single_link_list.travel()
  print("    ")
  single_link_list.remove(3)
  single_link_list.travel()
  print("              ")
  single_link_list.isContain(8)
  print("         ")
  node = single_link_list.searchNodeByIndex(2)
  print("        ：%s"%node.element)
  print("
    ")
  single_link_list.list_sort()
  single_link_list.travel()
  print("    ")
  single_link_list.modifyByIndex(2,10)
  single_link_list.travel()
if __name__ == '__main__':
  main()

실행 결 과 는:
빈 링크 의 반복 을 검증 합 니 다.
네가 옮 겨 다 니 려 는 링크 는 데이터 가 없다.
인증 플러그
당신 이 옮 겨 다 니 려 는 링크 안의 요 소 는 다음 과 같 습 니 다. 
검증 꼬리 삽입
당신 이 옮 겨 다 니 려 는 링크 안의 요 소 는 다음 과 같 습 니 다.  2 
위치 별 삽입 검증
당신 이 옮 겨 다 니 려 는 링크 의 요 소 는:3 입 니 다.  1  2 
계속 검증 헤드 삽입
당신 이 옮 겨 다 니 려 는 링크 안의 요 소 는 5 입 니 다.  3  1  2 
위치 에 따라 삽입 하 는 것 을 계속 검증 합 니 다.
당신 이 옮 겨 다 니 려 는 링크 안의 요 소 는 5 입 니 다.  3  1  4  2 
인증 삭제
당신 이 옮 겨 다 니 려 는 링크 안의 요 소 는 5 입 니 다.  3  4  2 
링크 에 노드 가 있 는 지 확인 하기
8.링크 에 없습니다.
인증 아래 표 시 를 누 르 면 노드 찾기
두 번 째 노드 의 값 은:3 입 니 다.
검증 정렬
당신 이 옮 겨 다 니 려 는 링크 안의 요 소 는:2 입 니 다.  3  4  5 
검증 수정
당신 이 옮 겨 다 니 려 는 링크 안의 요 소 는:2 입 니 다.  10  4  5 
6.단일 체인 표 의 C 언어 코드 실현

#include <stdio.h>
typedef struct N
{
  int element;
  struct N *next;
}Node;
// 1、    
Node *createNode(int num)
{
  Node *node;
  node = (Node *)malloc(sizeof(Node));
  node->element = num;
  node->next = NULL;
  return node;
}
// 2、    
Node *createSingleLinkList(Node *node)
{
  Node *head = node;
  return head;
}
// 3、      
int getlength(Node *head)
{
  if (head == NULL)
  {
    return 0;
  }
  int count = 1;
  Node *current = head;
  while (current->next != NULL)
  {
    count++;
    current = current->next;
  }
  return count;
}
// 4、    
Node * add(Node *head, Node *node)
{
  if(head == NULL)
  {
    head = node;
    return head;
  }
  else
  {
    node->next = head;
    head = node;
    return head;
  }
}
// 5、    
Node * append(Node *head,Node *node)
{
  Node *current = head;
  if (current->next == NULL)
  {
    add(head, node);
  }
  else
  {
    int len = getlength(head);
    for (int i = 0; i<len-1; i++)
    {
      current = current->next;
    }
    current->next = node;
  }
  return head;
}
// 6、       
Node * insert(Node *head,Node *node,int index)
{
  int len = getlength(head);
  if (index<=0||index>len+1)
  {
    printf("         ，       ");
  }
  Node *current = head;
  if (index == 1)
  {
    head = add(head, node);
  }
  else if (index == 2)
  {
    node->next = head->next;
    head->next = node;
  }
  else
  {
    for (int i = 1; i<index-1; i++)
    {
      current = current->next;
    }
    node->next = current->next;
    current->next = node;
  }
  return head;
}
// 7、  
void travel(Node *head)
{
  int len = getlength(head);
  printf("len = %d
",len);
  Node *current = head;
  if (len == 0)
  {
    printf("           
");
  }
  else
  {
    printf("             : ");
    for (int i = 0; i<len; i++)
    {
      printf("%d ",current->element);
      current = current->next;
    }
    printf("
");
  }
}
// 8、      
Node * delect(Node *head,int index)
{
  int len = getlength(head);
  if (index<=0||index>len)
  {
    printf("        ，     ");
    return head;
  }
  else
  {
    if (index == 1)
    {
      head = head->next;
    }
    else if (index == 2)
    {
      head->next = head->next->next;
    }
    else
    {
      Node *current = head;
      for (int i = 1; i<index-1; i++)
      {
        current = current->next;
      }
      current->next = current->next->next;
    }
  }
  return head;
}
// 9、      ，     
void isContain(Node *head,int num)
{
  int contain = 0;
  Node *current = head;
  int len = getlength(head);
  for (int i = 0; i<len; i++)
  {
    if (current->element == num)
    {
      printf("%d     %d 
",num,i+1);
      contain = 1;
    }
    current = current->next;
  }
  if (contain == 0)
  {
     printf("%d     
",num);
  }
}
// 10、       
Node *searchByIndex(Node *head , int index)
{
  int len = getlength(head);
  Node *current = head;
  if (index<=0||index>len)
  {
    printf("        ，     ");
    return head;
  }
  else
  {
    for (int i = 0; i<index-1; i++)
    {
      current = current->next;
    }
    return current;
  }
}
// 11、          
void modifyByIndex(Node *head,int index,int num)
{
  int len = getlength(head);
  Node *current = head;
  if (index<=0||index>len)
  {
    printf("        ，     ");
  }
  else
  {
    for (int i = 0; i<index-1; i++)
    {
      current = current->next;
    }
    current->element = num;
  }
}
int main(int argc, const char * argv[])
{
  printf("==========1、    ==========
");
  Node * node1 = createNode(1);
  printf("==========2、     ==========
");
  Node * head = createSingleLinkList(node1);
  travel(head);
  printf("==========3、    ==========
");
  Node *node2 = createNode(0);
  head = add(head, node2);
  travel(head);
  Node *node3 = createNode(2);
  head = add(head, node3);
  travel(head);
  printf("==========4、    ==========
");
  Node *node4 = createNode(4);
  head = append(head,node4);
  travel(head);
  Node *node5 = createNode(5);
  head = append(head,node5);
  travel(head);
  printf("==========5、       ==========
");
  Node *node6 = createNode(6);
  head = insert(head, node6, 1);
  travel(head);
  printf("==========6、       ==========
");
  head = delect(head, 2);
  travel(head);
  printf("==========7、      ==========
");
  isContain(head, 8);
  printf("==========8、         ==========
");
  Node *n = searchByIndex(head, 1);
  printf("      %d
",n->element);
  printf("==========9、        ==========
");
  modifyByIndex
(head, 3, 9);
    travel(head);
    return 0;
}

실행 결 과 는:
=========1,창설 노드===================
===========2,싱글 체인 테이블 만 들 기==============
len = 1
당신 이 옮 겨 다 니 려 는 링크 안의 요 소 는 다음 과 같 습 니 다.
===========3,검증 헤드 삽입=================
len = 2
당신 이 옮 겨 다 니 려 는 링크 안의 요 소 는 0 1 입 니 다.
len = 3
당신 이 옮 겨 다 니 려 는 링크 의 요 소 는:21 입 니 다.
===========4,검증 꼬리 삽입==================
len = 4
당신 이 옮 겨 다 니 려 는 링크 의 요 소 는 다음 과 같 습 니 다.
len = 5
당신 이 옮 겨 다 니 려 는 링크 의 요 소 는:20,1,4,5 입 니 다.
===========5.검증 은 아래 에 표 시 된 대로 삽입===================
len = 6
당신 이 옮 겨 다 니 려 는 링크 의 요 소 는 6,2,0,1,4,5 입 니 다.
===========6.검증 은 아래 표 시 를 누 르 고 삭제=================
len = 5
당신 이 옮 겨 다 니 려 는 링크 의 요 소 는:6,0,1,4,5 입 니 다.
===========7,포함 여부 검증===================
8.링크 에 없습니다.
===========8.검증 은 아래 표 에 따라 노드 를 찾는다==================
첫 번 째 노드 는 6.
===========9.검증 은 아래 표 에 따라 수정====================
len = 5
당신 이 옮 겨 다 니 려 는 링크 의 요 소 는:609,445 입 니 다.
총결산
위 에서 말 한 것 은 소 편 이 소개 한 python 알고리즘 과 데이터 구조의 단일 체인 표 의 실현 코드 입 니 다.여러분 께 도움 이 되 기 를 바 랍 니 다.궁금 한 점 이 있 으 시 면 메 시 지 를 남 겨 주세요.소 편 은 제때에 답 해 드 리 겠 습 니 다.여기 서도 저희 사이트 에 대한 여러분 의 지지 에 감 사 드 립 니 다!
만약 당신 이 본문 이 당신 에 게 도움 이 된다 고 생각한다 면,전 재 를 환영 합 니 다.번 거 로 우 시 겠 지만 출처 를 밝 혀 주 십시오.감사합니다!