C 언어 구현 단일 체인 테이블

  ：n          ，     （a1,a2,...,an）       ，                  ，       。

헤드 포인터: 링크 의 첫 번 째 노드 의 저장 위 치 를 헤드 포인터 라 고 합 니 다.
두 결점: 단 사슬 표 의 첫 번 째 결점 앞 에 하나의 결점 을 부설 하여 두 결점 이 라 고 한다. '
 
C 언어의 구조 지침 으로 단일 체인 표 의 저장 구 조 를 설명 할 수 있 습 니 다. 다음 과 같 습 니 다.

struct Node
{
	ElemType data;
	struct Node * next;
};
typedef struct Node * LinkList;

 위 에서 알 수 있 듯 이 노드 는 데이터 요 소 를 저장 하 는 데이터 필드 와 후계 노드 주 소 를 저장 하 는 포인터 필드 로 구성 된다.
 
단일 체인 테이블 의 전체 테이블 생 성
선두 결점 을 가 진 단일 체인 표를 만 듭 니 다.
방법 1: 머리 삽입 법 은 항상 새로운 결점 을 첫 번 째 위치 에 두 는 것 이다.
코드 는 다음 과 같다.

void CreateListHead(LinkList *L,int n)
{
	LinkList p;
	int i;
	srand(time(0));
	*L = (LinkList)malloc(sizeof(struct Node));
    (*L)->next = NULL;
	for (i = 0; i < n; i++)
	{
		p = (LinkList)malloc(sizeof(struct Node));
		p->data = rand() % 100 + 1;
		p->next = (*L)->next;
		(*L)->next = p;
	}
}

방법 2: 꼬리 삽입 법 즉 새로운 결점 은 항상 마지막 에 있다.
코드 는 다음 과 같 습 니 다:
 

/    n     ，           L(   )
void CreateListTail(LinkList *L, int n)
{
	LinkList p, r;
	int i;
	srand(time(0));
	*L = (LinkList)malloc(sizeof(struct Node));
	r = *L;
	for (i = 0; i < n; i++)
	{
		p = (LinkList)malloc(sizeof(struct Node));
		p->data= rand()%100+1;
		r->next = p;
		r = p;
	}
	r->next = NULL;
} 

 
단일 체인 테이블 읽 기

/*    ： e  L  i       */
 int GetElem(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)
	{
		return 0;
	}
	
	*e = p->data;
	return 1;
 }

시간 복잡 도 O (n)
 
싱글 체인 시트 삽입

/*    ： L  i             e，L    1*/
 int ListInsert(LinkList L, int i, ElemType e)
 {
 	 int j;
	 LinkList p, s;
	 p = L;
	 j = 1;
	 while (p && j < i)
	 {
	 	p = p->next;
 		++j;
  	 }		
  	 if (!p || j > i)
  	 {
 	 	return 0; 	
     }
     
     s = (LinkList)malloc(sizeof(struct Node));
     s->data = e;
     s->next = p->next;
     p->next = s;
     return 1;
 } 

단일 체인 시트 삭제

/*    ：  L  i     ，  e    ，L    1*/
 int ListDelete(LinkList L, int i, ElemType *e)
 {
 	int j;
 	LinkList p, q;
 	p = L;
 	j = 1;
 	while (p->next && j < i)
 	{
		p = p->next;
		++j; 	
    }
    if (!(p->next) || j > i)
    {
    	return 0;
    }
    
    q = p->next;
    p->next = q->next;
    *e = q->data;
	free(q);
	return 1; 
 } 
 

단일 링크 삽입 과 삭제 분석: 그들의 시간 복잡 도 는 모두 O (n) 이지 만 한 위치 에 여러 요 소 를 삽입 하려 면 단일 링크 에 대해 처음으로 삽입 한 위 치 를 찾 아야 한다. 이때 O (n) 이 고 그 다음은 간단 한 할당 이동 지침 일 뿐 시간 복 잡 도 는 모두 O (1) 이다.따라서 데 이 터 를 삽입 하거나 삭제 하 는 작업 이 빈번 할 수록 단일 체인 시트 의 효율 적 인 장점 이 뚜렷 합 니 다.
 
전체 코드 는 다음 과 같다.

#include<stdio.h>
#include<stdlib.h>
#include<time.h> 
typedef int ElemType;

struct Node
{
	ElemType data;
	struct Node * next;
};
typedef struct Node * LinkList;
int main()
{
	void CreateListHead(LinkList *L, int n);
	void CreateListTail(LinkList *L, int n);
	int GetElem(LinkList L, int i, ElemType *e);
	int ListInsert(LinkList p, int i, ElemType e);
	int ListDelete(LinkList p, int i, ElemType *e);
	LinkList *L = (LinkList *)malloc(4);
	int n = 5;
	CreateListTail(L, n);
	
	ListInsert(*L, 3, 1000);
	
	ElemType *e = &n;
	int i = 3;
	GetElem(*L, i, e);
	printf("%d
", *e);
	
	ListDelete(*L, 3, e);
	printf("%d", *e);
}

void CreateListHead(LinkList *L,int n)
{
	LinkList p;
	int i;
	srand(time(0));
	*L = (LinkList)malloc(sizeof(struct Node));
    (*L)->next = NULL;
	for (i = 0; i < n; i++)
	{
		p = (LinkList)malloc(sizeof(struct Node));
		p->data = rand() % 100 + 1;
		p->next = (*L)->next;
		(*L)->next = p;
	}
}

//    n     ，           L(   )
void CreateListTail(LinkList *L, int n)
{
	LinkList p, r;
	int i;
	srand(time(0));
	*L = (LinkList)malloc(sizeof(struct Node));
	r = *L;
	for (i = 0; i < n; i++)
	{
		p = (LinkList)malloc(sizeof(struct Node));
		p->data= rand()%100+1;
		r->next = p;
		r = p;
	}
	r->next = NULL;
} 

/*    ： e  L  i       */
 int GetElem(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)
	{
		return 0;
	}
	
	*e = p->data;
	return 1;
 }
 
 /*    ： L  i             e，L    1*/
 int ListInsert(LinkList L, int i, ElemType e)
 {
 	 int j;
	 LinkList p, s;
	 p = L;
	 j = 1;
	 while (p && j < i)
	 {
	 	p = p->next;
 		++j;
  	 }		
  	 if (!p || j > i)
  	 {
 	 	return 0; 	
     }
     
     s = (LinkList)malloc(sizeof(struct Node));
     s->data = e;
     s->next = p->next;
     p->next = s;
     return 1;
 } 
 
 /*    ：  L  i     ，  e    ，L    1*/
 int ListDelete(LinkList L, int i, ElemType *e)
 {
 	int j;
 	LinkList p, q;
 	p = L;
 	j = 1;
 	while (p->next && j < i)
 	{
		p = p->next;
		++j; 	
    }
    if (!(p->next) || j > i)
    {
    	return 0;
    }
    
    q = p->next;
    p->next = q->next;
    *e = q->data;
	free(q);
	return 1; 
 } 
 

참고 문헌: 큰소리 데이터 구조