C 언어 단 방향 링크 의 표시 와 실현 사례 에 대한 상세 한 설명
C 언어 중의 단 방향 링크(단일 링크)는 링크 의 하나 로 링크 의 링크 방향 이 단 방향 이 고 링크 에 대한 방문 은 순서대로 읽 어야 머리 부터 시작 하 는 것 이 특징 이다.
링크 에서 가장 간단 한 것 은 단 방향 링크 로 두 개의 도 메 인,하나의 정보 도 메 인 과 하나의 지침 도 메 인 을 포함한다.이 링크 는 목록 의 다음 노드 를 가리 키 고 마지막 노드 는 빈 값 을 가리킨다.
다음 그림 에서 보 듯 이:
하나의 단 방향 링크 는 두 개의 값 을 포함 합 니 다.현재 노드 의 값 과 다음 노드 를 가리 키 는 링크 입 니 다.
단 방향 링크 의 노드 는 두 부분 으로 나 뉜 다.첫 번 째 부분 은 노드 에 대한 정 보 를 저장 하거나 표시 하고 두 번 째 부분 은 다음 노드 의 주 소 를 저장 합 니 다.단 방향 체인 시 계 는 한 방향 으로 만 옮 겨 다 닐 수 있다.
링크 의 가장 기본 적 인 구 조 는 모든 노드 에 데 이 터 를 저장 하고 다음 노드 의 주 소 를 저장 하 는 것 이다.마지막 노드 에 특수 한 끝 표 시 를 저장 하 는 것 이다.또한 고정된 위치 에 첫 번 째 노드 를 가리 키 는 지침 을 저장 하고 마지막 노드 를 가리 키 는 지침 도 동시에 저장 할 수 있다.보통 한 노드 를 찾 을 때 첫 번 째 노드 부터 다음 노드 를 방문 하고 필요 한 위치 까지 방문 해 야 합 니 다.그러나 한 노드 의 위 치 를 미리 저장 한 다음 에 직접 방문 할 수도 있다.물론 데이터 에 만 접근 할 필요 가 없다 면 링크 에 실제 데 이 터 를 가리 키 는 지침 을 저장 하 는 것 이 바람 직 하 다.이렇게 하면 일반적으로 링크 의 다음 노드 나 이전 노드 에 접근 하기 위해 서 입 니 다.
양 방향 링크 에 비해 모든 노드 에 지침 이 하나 밖 에 없 는 링크 는 단 방향 링크 라 고도 부 르 거나 단일 링크 라 고도 부 릅 니 다.보통 매번 순서대로 이 링크 를 옮 겨 다 닐 때(예 를 들 어 그림 의 인접 표 는 보통 고정 적 인 순서에 따라 방문 합 니 다).
2.프로그램 구현:
/* c2-2.h */
struct LNode
{
ElemType data;
struct LNode *next;
};
typedef struct LNode *LinkList; /* LinkList */
/* bo2-2.c ( c2-2.h ) (12 ) */
Status InitList(LinkList *L)
{ /* : L */
*L=(LinkList)malloc(sizeof(struct LNode)); /* , L */
if(!*L) /* */
exit(OVERFLOW);
(*L)->next=NULL; /* */
return OK;
}
Status DestroyList(LinkList *L)
{ /* : L 。 : L */
LinkList q;
while(*L)
{
q=(*L)->next;
free(*L);
*L=q;
}
return OK;
}
Status ClearList(LinkList L) /* L */
{ /* : L 。 : L */
LinkList p,q;
p=L->next; /* p */
while(p) /* */
{
q=p->next;
free(p);
p=q;
}
L->next=NULL; /* */
return OK;
}
Status ListEmpty(LinkList L)
{ /* : L 。 : L , TRUE, FALSE */
if(L->next) /* */
return FALSE;
else
return TRUE;
}
int ListLength(LinkList L)
{ /* : L 。 : L */
int i=0;
LinkList p=L->next; /* p */
while(p) /* */
{
i++;
p=p->next;
}
return i;
}
Status GetElem(LinkList L,int i,ElemType *e) /* 2.8 */
{ /* L 。 i , e OK, ERROR */
int j=1; /* j */
LinkList p=L->next; /* p */
while(p&&j<i) /* , p i p */
{
p=p->next;
j++;
}
if(!p||j>i) /* i */
return ERROR;
*e=p->data; /* i */
return OK;
}
int LocateElem(LinkList L,ElemType e,Status(*compare)(ElemType,ElemType))
{ /* : L ,compare() ( 1, 0) */
/* : L 1 e compare() 。 */
/* , 0 */
int i=0;
LinkList p=L->next;
while(p)
{
i++;
if(compare(p->data,e)) /* */
return i;
p=p->next;
}
return 0;
}
Status PriorElem(LinkList L,ElemType cur_e,ElemType *pre_e)
{ /* : L */
/* : cur_e L , , pre_e , */
/* OK; ,pre_e , INFEASIBLE */
LinkList q,p=L->next; /* p */
while(p->next) /* p */
{
q=p->next; /* q p */
if(q->data==cur_e)
{
*pre_e=p->data;
return OK;
}
p=q; /* p */
}
return INFEASIBLE;
}
Status NextElem(LinkList L,ElemType cur_e,ElemType *next_e)
{ /* : L */
/* : cur_e L , , next_e , */
/* OK; ,next_e , INFEASIBLE */
LinkList p=L->next; /* p */
while(p->next) /* p */
{
if(p->data==cur_e)
{
*next_e=p->next->data;
return OK;
}
p=p->next;
}
return INFEASIBLE;
}
Status ListInsert(LinkList L,int i,ElemType e) /* 2.9。 L */
{ /* L i e */
int j=0;
LinkList p=L,s;
while(p&&j<i-1) /* i-1 */
{
p=p->next;
j++;
}
if(!p||j>i-1) /* i 1 */
return ERROR;
s=(LinkList)malloc(sizeof(struct LNode)); /* */
s->data=e; /* L */
s->next=p->next;
p->next=s;
return OK;
}
Status ListDelete(LinkList L,int i,ElemType *e) /* 2.10。 L */
{ /* L , i , e */
int j=0;
LinkList p=L,q;
while(p->next&&j<i-1) /* i , p */
{
p=p->next;
j++;
}
if(!p->next||j>i-1) /* */
return ERROR;
q=p->next; /* */
p->next=q->next;
*e=q->data;
free(q);
return OK;
}
Status ListTraverse(LinkList L,void(*vi)(ElemType))
/* vi ElemType, bo2-1.c ElemType& */
{ /* : L */
/* : L vi()。 vi() , */
LinkList p=L->next;
while(p)
{
vi(p->data);
p=p->next;
}
printf("
");
return OK;
}
/* algo2-5.c */
#include"c1.h"
typedef int ElemType;
#include"c2-2.h"
#include"bo2-2.c"
void CreateList(LinkList *L,int n) /* 2.11 */
{ /* ( ) n , L */
int i;
LinkList p;
*L=(LinkList)malloc(sizeof(struct LNode));
(*L)->next=NULL; /* */
printf(" %d
",n);
for(i=n;i>0;--i)
{
p=(LinkList)malloc(sizeof(struct LNode)); /* */
scanf("%d",&p->data); /* */
p->next=(*L)->next; /* */
(*L)->next=p;
}
}
void CreateList2(LinkList *L,int n)
{ /* ( ) n , */
int i;
LinkList p,q;
*L=(LinkList)malloc(sizeof(struct LNode)); /* */
(*L)->next=NULL;
q=*L;
printf(" %d
",n);
for(i=1;i<=n;i++)
{
p=(LinkList)malloc(sizeof(struct LNode));
scanf("%d",&p->data);
q->next=p;
q=q->next;
}
p->next=NULL;
}
void MergeList(LinkList La,LinkList *Lb,LinkList *Lc)/* 2.12 */
{ /* La Lb 。 */
/* La Lb Lc,Lc */
LinkList pa=La->next,pb=(*Lb)->next,pc;
*Lc=pc=La; /* La Lc */
while(pa&&pb)
if(pa->data<=pb->data)
{
pc->next=pa;
pc=pa;
pa=pa->next;
}
else
{
pc->next=pb;
pc=pb;
pb=pb->next;
}
pc->next=pa?pa:pb; /* */
free(*Lb); /* Lb */
Lb=NULL;
}
void visit(ElemType c) /* ListTraverse() ( ) */
{
printf("%d ",c);
}
void main()
{
int n=5;
LinkList La,Lb,Lc;
printf(" , ");
CreateList2(&La,n); /* n */
printf("La="); /* La */
ListTraverse(La,visit);
printf(" , ");
CreateList(&Lb,n); /* n */
printf("Lb="); /* Lb */
ListTraverse(Lb,visit);
MergeList(La,&Lb,&Lc); /* La Lb, Lc */
printf("Lc="); /* Lc */
ListTraverse(Lc,visit);
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
C 언어 구현 천둥 제거 게임 상세 정보먼저 작은 메뉴를 표시하고 게임을 할지 여부를 선택하십시오.사용자가 종료를 선택하면 프로그램 실행이 끝나고, 사용자가 게임을 선택하면 지뢰 제거 위치 좌표를 입력하라는 메시지가 표시됩니다.사용자가 입력한 좌표가 바둑...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.