데이터 구조 학습 (2) - 단일 체인 시트 의 조작 헤드 삽입 법 과 꼬리 삽입 법 으로 링크 를 만 듭 니 다.

링크 도 선형 표 의 하나 로 순서 표 와 달리 메모리 에 연속 으로 저장 되 지 않 습 니 다.C 언어 에서 체인 시 계 는 지침 을 통 해 이 루어 진다.한편, 단일 체인 표 는 체인 표 의 하나 로 단일 체인 표 는 바로 그 노드 에 데이터 도 메 인 이 있 고 다음 노드 를 가리 키 는 지침 도 메 인 만 있다.단일 체인 표를 만 드 는 방법 은 두 가지 가 있 는데 그것 이 바로 머리 삽입 법 과 꼬리 삽입 법 이다.
머리 삽입 법 이란 노드 의 역순 방법 에 따라 점 을 링크 의 머리 에 점차적으로 삽입 하 는 것 이다.반면에 꼬리 삽입 법 은 노드 의 순서에 따라 노드 를 링크 의 꼬리 부분 에 점차적으로 삽입 하 는 것 이다.상대 적 으로 헤드 삽입 법 은 꼬리 삽입 법 알고리즘 보다 간단 하지만 마지막 에 발생 하 는 링크 는 역순 이다. 즉, 첫 번 째 입력 노드 는 실제 적 으로 링크 의 마지막 노드 이다.습관 을 들 이기 위해 서 는, 보통 꼬리 삽입 법 으로 링크 를 만든다.아래 의 코드 는 바로 머리 삽입 법 과 꼬리 삽입 법 을 실현 한 것 이다.코드 는 Linux 에서 디 버 깅 을 통 과 했 습 니 다.

#include <stdio.h>
#include <stdlib.h>

typedef struct link
{
	char data;
	struct link *next;
}linklist;

linklist *CreateList_Front();	//        
linklist *CreateList_End();		//        
void ShowLinklist(linklist *h); //      

int main(void)
{
	int choice;
	linklist *head;

	//head = (linklist*)malloc(sizeof(linklist));
	while(1)
	{
		printf("      
");
		printf("1.          
");
		printf("2.          
");
		printf("3.      
");
		printf("4.  
");
		printf("    ：
");
		scanf("%d",&choice);
		switch(choice)
		{
		//   
		case 1:
			head = CreateList_Front();
			break;
		//   
		case 2:
			head = CreateList_End();
			break;
		//    
		case 3:
			ShowLinklist(head);
			break;
		//    
		case 4:
			return 0;
			break;
		default:
			break;
		}
	}
	return 1;
}

linklist *CreateList_Front()
{
	linklist *head, *p;
	char ch;

	head = NULL;
	printf("        (‘#’      ):
");
	ch = getchar();
	while(ch != '#')
	{
		p = (linklist*)malloc(sizeof(linklist));
		p->data = ch;
		p->next = head;
		head = p;
		ch = getchar();				//             p->next = head;head = p;
	}
	return head;
}

linklist *CreateList_End()
{
	linklist *head, *p, *e;
	char ch;

	head = NULL;
	e = NULL;
	printf("         ('#'      ):
");
	ch = getchar();
	while(ch != '#')
	{
		p = (linklist*)malloc(sizeof(linklist));
		p->data = ch;
		if(head == NULL)		//              
		{
			head = p;			
		}
		else
		{
			e->next = p;		//e             
		}
		e = p;
		ch = getchar();			
	}
	if(e != NULL)				//       ，             
	{
		e->next = NULL;
	}
	return head;				//           ，         ，                    。          e。
}

void ShowLinklist(linklist *h)
{
	linklist *p;

	p = h;
	while(p != NULL)
	{
		printf("%c ", p->data);
		p = p->next;
	}
	printf("
");
}

상기 코드 를 통 해 알 수 있 듯 이 꼬리 삽입 법 은 확실히 머리 삽입 법 보다 복잡 하고 두 가지 판단 이 많다.그러나 이것 은 해결 할 수 있 습 니 다. 머리 노드 를 추가 하면 이 노드 는 데이터 도 메 인 을 저장 하지 않 고 다음 노드 를 가리 키 는 지침 도 메 인 만 저장 하면 됩 니 다.이렇게 하면 두 번 의 판단 을 면 할 수 있다.전체적으로 도 또렷 해 져 야 겠 다.다음은 머리 노드 를 추가 한 후 꼬리 삽입 법의 실현 코드 입 니 다.

#include <stdio.h>
#include <stdlib.h>

typedef struct list
{
	char data;
	struct list *next;
}linklist;

linklist *CreateList_End();		//       
void ShowLinklist(linklist *h);	//      

int main(void)
{
	linklist *head;

	printf("         (   )
");
	printf("         (‘#’      ):
");
	head = CreateList_End();		//    
	ShowLinklist(head);				//    
}

linklist *CreateList_End()
{
	linklist *head, *p, *e;
	char ch;

	head = (linklist*)malloc(sizeof(linklist));
	e = head;			// e     
	ch = getchar();
	while(ch != '#')
	{
		p = (linklist*)malloc(sizeof(linklist));
		p->data = ch; 
		e->next = p;		//         
		e = p;				//        
		ch = getchar();
	}	
	e->next = NULL;			//         
	return head;
}

void ShowLinklist(linklist *h)
{
	linklist *p;

	p = h->next;
	while(p != NULL)
	{
		printf("%c ", p->data);
		p = p->next;
	}
	printf("
");
}

머리 노드 하 나 를 추가 하면 코드 가 선명 해 져 야 하지 않 을까요?