python 알고리즘 과 데이터 구조의 단일 체인 테이블 의 실현 코드
링크 는 물리 적 저장 장치 에서 비 연속 적 이 고 비 순서 적 인 저장 구조 로 데이터 요소 의 논리 적 순 서 는 링크 의 포인터 링크 순 서 를 통 해 이 루어 진다.체인 테이블 은 일련의 결점(체인 테이블 의 모든 원 소 를 결점 이 라 고 부른다)으로 구성 되 어 있 으 며 결점 은 운행 할 때 동적 으로 생 성 될 수 있다.각 노드 는 두 부분 을 포함한다.하 나 는 데이터 요 소 를 저장 하 는 데이터 필드 이 고 다른 하 나 는 다음 노드 주 소 를 저장 하 는 포인터 필드 이다.선형 표 순서 구조 에 비해 조작 이 복잡 하 다.순서대로 저장 하지 않 아 도 되 기 때문에 링크 는 삽입 할 때 O(1)의 복잡 도 에 이 를 수 있 고 다른 선형 표 순서 표 보다 훨씬 빠 르 지만 한 노드 를 찾 거나 특정한 번 호 를 방문 하 는 노드 는 O(n)의 시간 이 필요 하 며 선형 표 와 순서 표 에 해당 하 는 시간 복잡 도 는 각각 O(logn)와 O(1)이다.
링크 구 조 를 사용 하면 배열 링크 는 데이터 크기 의 단점 을 미리 알 아야 한다.링크 구 조 는 컴퓨터 메모리 공간 을 충분히 이용 하여 유연 한 메모리 동적 관 리 를 실현 할 수 있다.그러나 링크 는 배열 이 무 작위 로 읽 는 장점 을 잃 었 고 링크 는 결점 의 지침 도 메 인 을 증가 하기 때문에 공간 비용 이 비교적 크다.링크 의 가장 뚜렷 한 장점 은 일반적인 배열 과 관련 된 항목 을 배열 하 는 방식 이 메모리 나 디스크 에서 의 순서 와 다 를 수 있 고 데이터 의 액세스 가 서로 다른 배열 순서 에서 전환 되 어야 한 다 는 것 이다.링크 는 표 의 임의의 위치 에 있 는 노드 를 삽입 하고 제거 할 수 있 으 나 무 작위 액세스 가 허용 되 지 않 습 니 다.링크 는 여러 가지 유형 이 있 는데 그것 이 바로 단 방향 링크,양 방향 링크 와 순환 링크 이다.
2.단일 체인 표 소개
단 방향 링크(단일 링크)는 링크 의 하나 로 링크 의 링크 방향 이 단 방향 이 고 링크 에 대한 방문 은 순서대로 읽 어야 머리 부터 시작 하 는 것 이 특징 이다.단일 체인 테이블 은 체인 액세스 의 데이터 구조 로 주소 가 임의의 저장 장치 로 선형 테이블 의 데이터 요 소 를 저장 합 니 다.링크 의 데 이 터 는 노드 로 표 시 됩 니 다.모든 노드 의 구성:요소(데이터 요소 의 이미지)+포인터(후계 요소 의 저장 위 치 를 표시 합 니 다)요 소 는 데 이 터 를 저장 하 는 저장 장치 이 고 지침 은 모든 노드 를 연결 하 는 주소 데이터 입 니 다.그것 의 각 노드 는 두 개의 도 메 인,하나의 정보 도 메 인(원소 도 메 인)과 하나의 링크 도 메 인 을 포함한다.이 링크 는 링크 의 다음 노드 를 가리 키 고 마지막 노드 의 링크 도 메 인 은 빈 값 을 가리킨다.
체인 식 저장 구조의 선형 표 는 임의의 저장 장치 로 선형 표 의 데이터 요 소 를 저장 할 것 이다.순서대로 저장 할 필요 가 없 기 때문에 링크 는 데이터 요 소 를 삽입 하고 삭제 할 때 순서 적 으로 저장 하 는 것 보다 빠 르 지만 한 노드 를 찾 을 때 순서 적 으로 저장 하 는 것 보다 느 리 고 체인 식 저장 을 사용 하면 순서 선형 표를 극복 할 수 있 으 며 데이터 크기 의 단점 을 미리 알 아야 한다.링크 구 조 는 메모리 공간 을 충분히 이용 하여 유연 한 메모리 동적 관 리 를 실현 할 수 있다.그러나 체인 저장 소 는 배열 의 랜 덤 액세스 특징 을 잃 었 고 노드 의 지침 도 메 인 을 추 가 했 기 때문에 공간 비용 이 비교적 크다.
3.단일 체인 표 구조
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 알고리즘 과 데이터 구조의 단일 체인 표 의 실현 코드 입 니 다.여러분 께 도움 이 되 기 를 바 랍 니 다.궁금 한 점 이 있 으 시 면 메 시 지 를 남 겨 주세요.소 편 은 제때에 답 해 드 리 겠 습 니 다.여기 서도 저희 사이트 에 대한 여러분 의 지지 에 감 사 드 립 니 다!
만약 당신 이 본문 이 당신 에 게 도움 이 된다 고 생각한다 면,전 재 를 환영 합 니 다.번 거 로 우 시 겠 지만 출처 를 밝 혀 주 십시오.감사합니다!
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
로마 숫자를 정수로 또는 그 반대로 변환그 중 하나는 로마 숫자를 정수로 변환하는 함수를 만드는 것이었고 두 번째는 그 반대를 수행하는 함수를 만드는 것이었습니다. 문자만 포함합니다'I', 'V', 'X', 'L', 'C', 'D', 'M' ; 문자열이 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
