[데이터 구조 시리즈] 단일 체인 표 의 기본 조작

DATE: 2020.4.14
1. 참고
C 언어 설명 체인 테이블 의 실현 및 조작 선형 테이블 의 기본 조작 및 응용 (단일 체인 테이블 의 생 성, 삽입, 삭제, 찾기, 표시)
2. 단일 링크 의 기본 동작 (생 성, 찾기, 삽입, 삭제, 옮 겨 다 니 기)
선형 표 는 중요 한 데이터 구조 이다.선형 표 의 체인 식 저장 구 조 는 바로 단일 체인 표 이다.선형 표 의 순서 저장 구 조 는 바로 배열 이다.
다음은 C 언어 로 이 루어 진 단일 체인 시트 의 코드 입 니 다.

#include 
#include 

typedef int ElemType;
//       
typedef struct _Node_S
{
	ElemType data;			//    
	struct  _Node_S *next;	//    
} Node, *LinkList;

// 1、  ：         （   ）
LinkList CreateLinkListTail(int n)
{
	int i = 0;
	int x = 0;
	Node *L, *pTail;
	L = (Node*) malloc(sizeof(Node)); //     
	pTail = L;  //   
	pTail->next = NULL;
	printf("      : 
");
	
	for (i = 0; i < n; ++i)
	{
		Node* p; //the node to inserted
		p = (Node*) malloc(sizeof(Node));
		scanf("%d", &x);
		//                 
		p->data = x;     //      
		pTail->next = p; //           
		p->next = NULL;  //         
		pTail = p;		 //           
	}

	//pTail->next = NULL;
	return L;
}

// 2、  ：         （   ）
LinkList CreateLinkListHead(int n)
{
	int i;
	int x;
	Node* L, *pTail;
	L = (Node*) malloc(sizeof(Node)); //    
	L->next = NULL;
	printf("      : 
");

	for (i = 0; i < n; ++i)
	{
		Node* p; //the node to inserted
		p = (Node*) malloc(sizeof(Node));
		scanf("%d", &x);
		//                 
		p->data = x;     //      
		p->next = L->next; //                
		L->next = p;	   //             
	}

	return L;
}

//  3、  ：       i   
int GetEleInLinkList(LinkList l, int i, ElemType* e)
{
	int j;
	LinkList p;
	p = l->next;

	j = 1;
	//          
	while(p && j<i)
	{
		p = p->next;
		j++;
	}

	if (!p || j>i)
	{
		printf("     
");
		return -1;
	}
	*e = p->data;
	printf("The %dth element: %d 
",i, *e);
	return 0;
}

// 4、  ：     i       
int InsertNodeInLinkList(LinkList ll, int i, ElemType* m)
{
	int j = 1;
	LinkList p;
	Node* newNode;
	p = ll->next;

	while (p && j<i)
	{
		p = p->next;
		j++;
	}
	if (!p || j<i)
	{
		printf("      %d   
", i);
		return -1;
	}
	
	//     ，     
	newNode = (Node*) malloc(sizeof(Node));
	if (NULL == newNode)
	{
		printf("malloc error!
");
		return -1;
	}
	newNode->data = *m;
	newNode->next = p->next;
	p->next = newNode;

	return 0;
}

// 5、    ：              
int TranvesalLinkList(LinkList ll)
{
	LinkList p;
	p = ll->next;

	if (!p)
	{
		printf("   ！
");
		return -1;
	}
	while (p)
	{
		printf("%d\t", p->data);
		p = p->next;
	}
	printf("
");

	return 0;
}

// 6、  ：       i   ，        
int DeleteNodeInLinkList(LinkList ll, int i, ElemType *e)
{
	int j = 1;
	LinkList p, q;
	p = ll->next;

	while (p && j < i)
	{
		j++;
		p = p->next;
	}

	if (!p || j>i)
	{
		printf("     %d   ！
", i);
	}

	q = p->next;
	p->next = q->next;
	*e = q->data;

	printf("The deleted node data: %d
", *e);
	free(q);
	
	return 0;
}

// 7、    
int DeletedAllNodeInLinkList(LinkList ll)
{
	LinkList p = ll->next;
	LinkList q;

	while (p)
	{	
		q = p->next;  //          q
		free(p);	  //      p
		p = q;		 
	}
	ll->next = NULL;

	return 0;
}

int main(int argc, int argv[])
{
	LinkList ll;
	int elem = 0;
	int value = 50;

	//      
	ll = CreateLinkListTail(5);

	//        
	TranvesalLinkList(ll);

	//         
	GetEleInLinkList(ll, 4, &elem);

	//     
	InsertNodeInLinkList(ll, 1, &value);

	//        
	TranvesalLinkList(ll);

	//     
	DeleteNodeInLinkList(ll, 1, &elem);
	
	//        
	TranvesalLinkList(ll);

	//       
	DeletedAllNodeInLinkList (ll);

	//        
	TranvesalLinkList(ll);

	return 0;
}

THE END!