조세 프 링 (머리 결 점 없 는 순환 링크)

조세 프 링 (머리 결 점 없 는 순환 링크)
이 프로그램 을 통 해 순환 링크 를 만 드 는 방법 과 지침 에 관 한 많은 문 제 를 익 혔 다.이 문 제 는 헤드 포인터 가 없 는 순환 링크 를 채택 했다.1. 헤드 포인터 가 없 는 순환 링크 와 일반적인 순환 링크 의 차 이 를 알 게 되 었 습 니 다.2. 링크 길이 에 대한 구법.3. 링크 를 만 들 때 보통 꼬리 지침 을 되 돌려 주 고 꼬리 지침 은 머리 지침 을 쉽게 찾 을 수 있 습 니 다.그리고 지침 을 사용 할 때마다 지침 을 저장 하 세 요.4.

typedef struct Node {
	int id;
	int password;
	struct Node *next;
}Nodetype;

구조 체 정의 시 stuct Nodetype * next 를 사용 할 수 없 는 것 은 프로그램 이 이 문 구 를 실 행 했 을 때 type: def 문 구 는 Nodetype 을 정의 하지 않 았 기 때 문 입 니 다.5. YueSeFu 함수 에 두 개의 포인터 가 사용 되 었 습 니 다.

	Nodetype *LA = r;
	Nodetype *LB = r->next;

이 두 개의 포인 터 를 사용 하면 LB 의 앞 구 를 쉽게 찾 아 결점 을 삭제 하 는 작업 을 할 수 있 습 니 다. 매번 반복 해서 현 재 를 삭제 하지 않 아 도 됩 니 다.시간의 복잡 도 를 낮 추 었 다.O(n) -> O(1)。 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 다음은 코드 입 니 다.

#include 
#include
typedef struct Node {
	int id;
	int password;
	struct Node *next;
}Nodetype;

Nodetype *Creatlist(){
	Nodetype *L;
	Nodetype *pNew,*r;
	int ID = 1;
	int m;
	int MAX;
	int count = 0;
	L = (Nodetype*)malloc(sizeof(Nodetype));
	L->next = NULL;
	r= L;
	printf("       ："); 
	scanf("%d",&MAX); 
	while (count < MAX){
		pNew = (Nodetype*)malloc(sizeof(Nodetype));
		printf("please enter the %d th password:
",ID);
		pNew->id = ID++;
		scanf("%d",&m);
		pNew->password = m;
		r->next = pNew;
		r = pNew;
		count = count + 1;
	}
	r->next = L->next;
	return r;
}

void Output(Nodetype *L){
	Nodetype *p;
	p = L->next;
	printf(" %d      %d
",p->id,p->password);
	p = p->next;
	while(p != L->next) {
		printf(" %d      %d
",p->id,p->password);
		p = p->next;
    }
}
int Count(Nodetype *L){
	Nodetype *p;
	int count = 1;
	p = L;
	while(L->next != p){
		L = L->next;
		count = count + 1;
	}
	return count;
}
void YueSeFu(Nodetype *r, int m) {
	int t = m;
	Nodetype *LA = r;
	Nodetype *LB = r->next;
	while (1) {
		if (Count(LA) == 2) {
			if (t % 2 == 1) {
				printf("  :%d   :%d

", LB->id, LB->password);
				printf("  :%d   :%d
", LA->id, LA->password);
				break;
			} else {
				printf("  :%d   :%d

", LA->id, LA->password);
				printf("  :%d   :%d
", LB->id, LB->password);
				break;
			}
		} else {
			for (int i = 1; i < t; i++) {
				LA = LA->next;
				LB = LB->next; 
			}
			printf("  :%d   :%d
", LB->id, LB->password);
			if (Count(LA) == 1) {
				break;
			}
			t = LB->password;
			LB = LB->next;
			printf("
");
			LA->next = LB;
			}
	}
}
	
int main(){
	Nodetype *L;
	int password;
	L =Creatlist();
	Output(L);
	printf("       ：
");
	scanf("%d",&password) ;
	YueSeFu(L,password);
	return 0;
}