데이터 구조 - 링크 의 앞 삽입 법 과 뒤 삽입 법

단일 체인 표 의 기본 연산 을 하기 전에 반드시 단일 체인 표를 만들어 야 한다. 단일 체인 표를 구축 하 는 데 자주 사용 하 는 방법 은 두 가지 가 있다. 머리 삽입 법 건축 표 와 꼬리 삽입 법 건축 표 이다.
머리 삽입 법 은 표를 만 듭 니 다. 빈 표 부터 문자 배열 a 의 문 자 를 읽 고 새 노드 를 생 성 합 니 다. 읽 은 데 이 터 를 새 노드 의 데이터 필드 에 저장 한 다음 에 새 노드 를 현재 링크 의 표 머리 에 삽입 합 니 다. 문자 배열 a 의 모든 요 소 를 읽 을 때 까지 입 니 다.
머리 삽입 법 건축 표 는 간단 하지만 생 성 된 링크 에서 노드 의 순서 와 원래 배열 의 순서 가 반대 되 고 이들 의 순서 가 일치 하 기 를 원한 다 면 꼬리 삽입 법 으로 구축 할 수 있다.
꼬리 삽입 법 구성 표 입 니 다. 이 알고리즘 은 현재 링크 의 표 끝 에 새 노드 를 삽입 하 는 것 입 니 다. 이 를 위해 꼬리 포인터 r 를 추가 하여 현재 링크 의 끝 노드 를 가리 키 도록 해 야 합 니 다.
앞 삽 법

#include 
#include 
 
typedef int ElemType;
 
typedef struct Node {
    ElemType data;               
    struct Node *next;          
}Node,*LinkedList;

LinkedList LinkedListInit() {
    Node *L;
    L = (Node *)malloc(sizeof(Node)); 
    if(L == NULL) { 
        printf("        
");
    }
    L->next = NULL;                  
 	return L;
}

LinkedList LinkedListCreatH() {
    Node *L;
    L = (Node *)malloc(sizeof(Node));   
    L->next = NULL;                     
     
    ElemType x;                         
    while(scanf("%d",&x) != EOF) {
        Node *p;
        p = (Node *)malloc(sizeof(Node));    
        p->data = x;                      
        p->next = L->next;                    
        L->next = p; 
    }
    return L; 
} 

LinkedList LinkedListInsert(LinkedList L,int i,ElemType x) {
    Node *pre;                     
    pre = L;
    int tempi = 0;
    for (tempi = 1; tempi < i; tempi++) {
    	pre = pre->next;                  
	}
    Node *p;                                
    p = (Node *)malloc(sizeof(Node));
    p->data = x; 
    p->next = pre->next;
    pre->next = p;
     
    return L;                           
} 

LinkedList LinkedListDelete(LinkedList L,ElemType x)
{
    Node *p,*pre;                    
    p = L->next;
    pre = L; 
	/**************************     per = L;        :     per                     per                ***************************/
	while(p->data != x) {               
        pre = p; 
        p = p->next;
    }
    pre->next = p->next;          
    free(p);
    return L;
} 

int findder(LinkedList L,int x) { //     
	/* * @ x        * @ L         *    -1              */ 
	LinkedList start; int i = 1;
	L = L->next;
	for (start = L;start != NULL;start = start->next) {
		if ( start->data == x ) {
			return i;
		}
		i++;
	} 
	return -1;
}

LinkedList Delete(LinkedList L,int st,int en) { //          
	/* * @ st         * @ en         * @ L          */
	bool flag1 = false;
	Node *per,*p;
	per = L;
	L = L->next; int i = 1;
	LinkedList start;
	for (start = L;start != NULL ; start = start->next ) {
		if ( st == i ) {
			flag1 = true;
		}
		if ( en == i ) {
			per->next = start->next;
			break;
		}
		i++;
		if ( !flag1 )
			per = start;
	}
	return L;
}

int main() {
    LinkedList list,start;
 	printf("         ："); 
   	list = LinkedListCreatH();
	for(start = list->next; start != NULL; start = start->next) {
		printf("%d ",start->data);
	}
	printf("
");
    int i;
    ElemType x;
    printf("          ：");
    scanf("%d",&i);
    printf("         ：");
    scanf("%d",&x);
    LinkedListInsert(list,i,x);
    for(start = list->next; start != NULL; start = start->next) {
    	printf("%d ",start->data);
	}
    printf("
");
    printf("           ：");
    scanf("%d",&x);
    LinkedListDelete(list,x); 
    for(start = list->next; start != NULL; start = start->next) {
    	printf("%d ",start->data);
	}
    printf("
"); 
    return 0;
}

후 삽 법

#include 
#include 
 
typedef int ElemType;
 
typedef struct Node {
    ElemType data;               
    struct Node *next;          
}Node,*LinkedList;

LinkedList LinkedListInit() {
    Node *L;
    L = (Node *)malloc(sizeof(Node)); 
    if(L == NULL) { 
        printf("        
");
    }
    L->next = NULL;                  
 	return L;
}

void LinkedListCreatH(LinkedList &list) {
    Node *L,*s;
    list = new Node; list->next = NULL;
    L = list; ElemType x;
    while ( ~scanf("%d",&x) ) {
    	s = new Node;	
    	s->data = x; s->next = L->next; L->next = s;
    	L = s;
	}
} 

LinkedList LinkedListInsert(LinkedList L,int i,ElemType x) {
    Node *pre;                     
    pre = L;
    int tempi = 0;
    for (tempi = 1; tempi < i; tempi++) {
    	pre = pre->next;                  
	}
    Node *p;                                
    p = (Node *)malloc(sizeof(Node));
    p->data = x; 
    p->next = pre->next;
    pre->next = p;
     
    return L;                           
} 

LinkedList LinkedListDelete(LinkedList L,ElemType x)
{
    Node *p,*pre;                    
    p = L->next;
    pre = L;
    while(p->data != x) {               
        pre = p; 
        p = p->next;
    }
    pre->next = p->next;          
    free(p);
    return L;
} 

int main() {
    LinkedList list,start;
 	printf("         ："); 
   	LinkedListCreatH(list);
	for(start = list->next; start != NULL; start = start->next) {
		printf("%d ",start->data);
	}
	printf("
");
    int i;
    ElemType x;
    printf("          ：");
    scanf("%d",&i);
    printf("         ：");
    scanf("%d",&x);
    LinkedListInsert(list,i,x);
    for(start = list->next; start != NULL; start = start->next) {
    	printf("%d ",start->data);
	}
    printf("
");
    printf("           ：");
    scanf("%d",&x);
    LinkedListDelete(list,x); 
    for(start = list->next; start != NULL; start = start->next) {
    	printf("%d ",start->data);
	}
    printf("
"); 
    return 0;
}