C 언어 가 단일 체인 표 데이터 구 조 를 만 들 고 조작 하 는 인 스 턴 스 튜 토리 얼
배열 은 같은 데 이 터 를 저장 하 는 집합 으로서 우리 에 게 프로그램 디자인 에 많은 편 의 를 가 져 다 주 고 유연성 을 높 였 다.그러나 수조 에 도 폐단 이 있다.만약 에 배열 의 크기 가 정 의 될 때 미리 규정 해 야 하고 프로그램 에서 조정 할 수 없다.그러면 프로그램 설계 에서 서로 다른 문제 에 대해 30 개의 크기 의 배열 이 필요 하고 50 개의 배열 의 크기 가 필요 하 며 통일 하기 어렵다.우 리 는 가능 한 최대 수요 에 따라 배열 을 정의 할 수 있 을 뿐 일정한 저장 공간의 낭 비 를 초래 할 수 있다.
우 리 는 동태 적 인 배열 을 구성 하여 수시로 배열 의 크기 를 조정 하여 서로 다른 문제 의 수 요 를 만족 시 킬 수 있 기 를 바란다.링크 는 우리 가 필요 로 하 는 동적 배열 이다.이것 은 프로그램의 실행 과정 에서 필요 에 따라 데이터 저장 이 있 으 면 시스템 에 저장 공간 을 신청 하 는 것 으로 저장 구역 에 대한 낭 비 는 결코 구성 되 지 않 는 다.
체인 테이블 은 복잡 한 데이터 구조 로 그 데이터 간 의 상호 관 계 는 체인 테이블 을 세 가지 로 나눈다.그것 이 바로 단일 체인 테이블,순환 체인 테이블,양 방향 체인 테이블 이다.다음은 하나씩 소개 할 것 이다.
2,단 방향 링크
단일 체인 시트 는 메모리 의 첫 번 째 주 소 를 가리 키 는 헤드 노드 헤드 가 있 습 니 다.링크 의 모든 노드 의 데이터 유형 은 구조 체 유형 이 고 노드 는 두 개의 구성원 이 있다.전체 구성원(실제 저장 해 야 할 데이터)과 다음 구조 체 유형 노드 를 가리 키 는 지침,즉 다음 노드 의 주소(사실은 이 단일 링크 는 전체 데 이 터 를 저장 하 는 동적 배열)이다.링크 는 이 구조 에 따라 각 노드 에 대한 방문 은 링크 의 머리 에서 찾 아야 하고 후속 노드 의 주 소 는 현재 노드 에서 제시 해 야 한다.표 에서 그 노드 를 방문 하 더 라 도 링크 의 머리 부터 순 서 를 뒤로 찾 아야 합 니 다.링크 의 끝 노드 는 후속 노드 가 없 기 때문에 포인터 필드 가 비어 있 고 NULL 로 쓰 입 니 다.
그림 에서 보 듯 이:
위의 그림 은 이러한 의 미 를 보 여 준다.링크 의 각 노드 가 메모리 에 저 장 된 주 소 는 연속 적 인 것 이 아니 라 각 노드 의 주 소 는 필요 할 때 시스템 에 분 배 를 신청 하 는 것 이다.시스템 은 메모리 의 현재 상황 에 따라 주 소 를 연속 으로 분배 할 수도 있 고 점프 식 으로 주 소 를 분배 할 수도 있다.
3.단 방향 링크 프로그램의 실현
(1)링크 노드 의 데이터 구조 정의
struct node
{
int num;
struct node *p;
} ;
링크 노드 의 데이터 구조 에서 매우 특수 한 점 은 구조 체 내의 포인터 필드 의 데이터 형식 이 정의 되 지 않 은 성공 적 인 데이터 형식 을 사용 한 것 이다.이것 은 C 에서 먼저 사용 한 후에 정의 할 수 있 는 데이터 구 조 를 유일 하 게 규정 한 것 이다.
(2)링크 생 성,출력 절차
단일 체인 시트 의 생 성 과정 은 다음 과 같은 몇 단계 가 있 습 니 다.
1)링크 의 데이터 구 조 를 정의 합 니 다.
2)빈 테이블 만 들 기;
3)malloc()함 수 를 이용 하여 시스템 에 노드 를 분배 할 것 을 신청 합 니 다.
4)새 노드 의 포인터 구성원 을 빈 값 으로 지정 합 니 다.빈 시계 라면 새 노드 를 표 머리 에 연결 합 니 다.만약 빈 시계 가 아니라면,새로
노드 가 표 끝 을 받 습 니 다.
5)후속 노드 가 링크 에 접속 해 야 하 는 지 판단 하고 3 으로 이동 하면 끝 납 니 다.
단일 체인 시트 의 출력 과정 은 다음 과 같은 몇 단계 가 있다.
1)시계 머리 찾기;
2)빈 테이블 이 아니면 출력 노드 의 값 구성원 이 빈 테이블 이면 종료 합 니 다.
3)링크 의 증 가 를 추적 하면 다음 노드 의 주 소 를 찾 을 수 있다.
4)2 로 이동).
(3)프로그램 코드 예:
정수 단일 체인 표를 만 들 고 0 이하 의 수 를 입력 하 며 링크 를 만 들 고 링크 의 값 을 출력 합 니 다.프로그램 은 다음 과 같 습 니 다.
#include <stdlib.h> /* ma l l o c ( ) */
#include <stdio.h>
//①
struct node
{
int num;
struct node *next;
};
//
struct node *creat();
void print();
main( )
{
struct node *head;
head=NULL; //②
head=creat(head);/* */
print(head);/* */
}
/******************************************/
struct node*creat(struct node *head)/* */
{
struct node*p1,*p2;
int i=1;
//③ malloc ( )
p1=p2=(struct node*)malloc(sizeof(struct node));/* */
printf(" ， 0 ， ：p1_ADDR= %d
",p1);
scanf("%d",&p1->num);/* */
p1->next=NULL;/* */
while(p1->num>0)/* 0*/
{
//④ 。 ， ； ， ;
if(head==NULL)
head=p1;/* ， */
else
p2->next=p1;/* ， */
p2=p1;
p1=(struct node*)malloc(sizeof(struct node));/* */
i=i+1;
printf(" ， 0 ， ：p%d_ADDR= %d
",i,p2);
scanf("%d",&p1->num);/* */
//⑤ ， 3 )， ;
}
//============== ：（ @daling_datou ）================================
free(p1); // ，
p1=NULL; //
p2->next = NULL; // ，
printf(" （END）
");
//==============================================
return head;/* */
}
/*******************************************/
void print(struct node*head)/* head */
{
struct node *temp;
temp=head;/* */
printf("
：
");
while(temp!=NULL)/* */
{
printf("%6d
",temp->num);/* */
temp=temp->next;/* */
}
printf(" !!");
}
링크 를 만 드 는 과정 에서 링크 의 헤드 포인터 가 매우 중요 한 매개 변수 입 니 다.링크 에 대한 출력 과 검색 은 모두 링크 의 머리 에서 시작 해 야 하기 때문에 링크 를 만 든 후에 체인 헤더 노드 의 주소,즉 헤드 포인터 로 돌아 가 야 합 니 다.
프로그램 실행 절차:
4,단일 체인 테이블 작업 기초 예시
#include <stdio.h>
#include <malloc.h>
#define LEN sizeof(NODE)
typedef struct _NODE//
{
int val;
struct _NODE* next;
} NODE, *PNODE;
void print(PNODE head){//
while (head)
{
printf("%3d",head->val);
head = head->next;
}
printf("
");
}
void insertHead(PNODE *pHead, int val){//
PNODE n = (PNODE)malloc(LEN);
n->val = val;
n->next = *pHead;
*pHead = n;
}
void insertTail(PNODE *pHead, int val){//
PNODE t = *pHead;
PNODE n = (PNODE)malloc(LEN);
n->val = val;
n->next = NULL;
if (*pHead == NULL)
{
n->next = *pHead;
*pHead = n;
}else{
while (t->next)
{
t = t->next;
}
t->next = n;
}
}
void deleteHead(PNODE *pHead){//
if (*pHead == NULL)
{
return;
}
else
{
PNODE t = *pHead;
*pHead = (*pHead)->next;
free(t);
}
}
void deleteTail(PNODE *pHead){//
PNODE t = *pHead;
if (t == NULL)
{
return;
}
else if (t->next == NULL)
{
free(t);
*pHead = NULL;
}
else{
while (t->next->next != NULL)
{
t = t->next;
}
free(t->next);
t->next = NULL;
}
}
PNODE findByVal(PNODE head, int val){//
while (head != NULL && head->val != val)
{
head = head->next;
}
return head;
}
PNODE findByIndex(PNODE head, int index){//
if (index == 1)
{
return head;
}
else
{
int c = 1;
while (head != NULL && index != c)
{
head = head->next;
c++;
}
}
return head;
}
void insertByIndex(PNODE *pHead, int index, int val){//
if (index == 1)
{
insertHead(pHead, val);
}
else
{
PNODE t = findByIndex(*pHead,index - 1);
if (t == NULL)
{
return;
}
else
{
PNODE n = t->next;
t->next = (PNODE)malloc(LEN);
t->next->next = n;
t->next->val = val;
}
}
}
void deleteByIndex(PNODE *pHead, int index)//
{
if (index == 1)
{
deleteHead(pHead);
}
else
{
PNODE t= findByIndex(*pHead, index - 1);
if (t == NULL || t->next == NULL)
{
return;
}else{
PNODE n = t->next->next;
free(t->next);
t->next = n;
}
}
}
void deleteByVal(PNODE *pHead, int val)//
{
if (*pHead == NULL)//
{
return;
}
else
{
if ((*pHead)->val == val)// ，
{
deleteHead(pHead);
}
else
{
PNODE t = *pHead;
while (t->next != NULL && t->next->val != val)// ， t next next
{
t = t->next;
}
if (t->next)// t
{
PNODE n = t->next->next;//
free(t->next);
t->next = n;
}
}
}
}
void clear(PNODE *pHead)//
{
while ((*pHead) != NULL)
{
deleteHead(pHead);//
}
}
void main()
{
PNODE head = NULL;
insertTail(&head,1);
deleteHead(&head);
insertTail(&head,2);
insertTail(&head,3);
insertTail(&head,4);
insertTail(&head,5);
insertTail(&head,6);
print(head);
insertByIndex(&head, 6, 9);
print(head);
//deleteByIndex(&head,3);
deleteByVal(&head, 2);
print(head);
clear(&head);
print(head);
insertByIndex(&head,1,12);
print(head);
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
C 언어 구현 천둥 제거 게임 상세 정보먼저 작은 메뉴를 표시하고 게임을 할지 여부를 선택하십시오.사용자가 종료를 선택하면 프로그램 실행이 끝나고, 사용자가 게임을 선택하면 지뢰 제거 위치 좌표를 입력하라는 메시지가 표시됩니다.사용자가 입력한 좌표가 바둑...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
