[데이터 구조] 헤드 노드 를 포함 한 단일 체인 표
18819 단어 shujujiegou
각 부분 실현
싱글 체인 테이블 구조 체
typedef struct tagNode
{
int data;//
struct tagNode *next;// ,
}Node,*LinkList;/*LinkList */
헤드 삽입 법 구축 싱글 체인 시트:
L 은 선두 결점 을 가 진 빈 사슬 시계 헤드 포인터 이 고 n 은 단일 사슬 표 에 입력 할 요소 갯 수 입 니 다.L - > next 는 항상 단일 체인 시트 의 첫 번 째 요 소 를 가리 키 며 처음에는 빈 곳 을 가리 키 고 있 습 니 다.헤드 삽입 법 을 사용 하려 면 삽입 할 요 소 를 새로운 노드 저장 소 를 만 들 고 L - > next 가 가리 키 는 노드 를 s - > next 에 부여 해 야 합 니 다. 마지막 으로 L - > next 가 새로 삽 입 된 노드 s 를 가리 키 면 헤드 삽입 법 이 완 료 됩 니 다.
void CreateHeadList(LinkList L,int n)//
{
LinkList s;
while(n--)
{
s=(LinkList)malloc(sizeof(Node));/* */
scanf("%d",&s->data);
s->next=L->next;/* , */
L->next=s;
}
}
꼬리 삽입 법 구축 싱글 체인 시트
L 은 선두 결점 을 가 진 빈 사슬 시계 헤드 포인터 이 고 n 은 단일 사슬 표 에 입력 할 요소 갯 수 입 니 다.꼬리 삽입 법 을 실현 하려 면 구조 체 포인터 p 가 링크 의 마지막 요 소 를 항상 가리 키 고 링크 에 요 소 를 사용 하지 않 을 때 머리 결 점 을 가리 키 는 것 을 정의 해 야 합 니 다.매번 삽입 할 때마다 삽입 할 새로운 노드 저장 소 를 만 듭 니 다.p - > next 로 하여 금 새로 만 든 결점 을 가리 키 게 하면 끝 삽입 법 이 완성 되 고 마지막 으로 포인터 p 로 하여 금 새로운 마지막 결점 을 가리 키 게 합 니 다.
void CreateTailList(LinkList L,int n)//
{
LinkList p,s;
p=L;/* p */
while(n--)
{
s=(LinkList)malloc(sizeof(Node));
scanf("%d",&s->data);
p->next=s,p=s;/* */
}
p->next=NULL;/* */
}
링크
끝 점 이 비어 있 을 때 까지 처음부터 포인터 의 다음 노드 를 옮 겨 다 니 기 시작 합 니 다.
void ListTraverse(LinkList L)//
{
LinkList p=L->next;/* , ,
*/
while(p)/* */
{
printf("%d ",p->data);
p=p->next;/* */
}
printf("
");
}
두 개의 링크 를 직접 병합 하 다.
두 개의 단일 체인 테이블 L, O 는 먼저 체인 테이블 L 의 마지막 결점 을 찾 아서 이 결점 의 지침 역 이 체인 테이블 O 의 머리 결점 후의 첫 번 째 결점 을 가리 키 게 하면 합병 을 완성 할 수 있다.
void ListContact1(LinkList L,LinkList O)
{
LinkList p=L;
while(p->next)
{
p=p->next;
}/* */
p->next=O->next;
}
병합 순서 링크
두 개의 단일 체인 표 의 질서 있 는 선형 표 로 합병 하 는 방법 은 순서 표 가 합 쳐 진 홍보 이 고 꼬리 삽입 법 으로 합 쳐 진 링크 에 새로운 요 소 를 삽입 하 는 것 이다.
void ListContact2(LinkList L,LinkList O,LinkList H)
{
LinkList l,o,h,s;
l=L->next;
o=O->next;
h=H;/* h */
while(l&&o)/* l o , , */
{
s=(LinkList)malloc(sizeof(Node));/* */
s->next=NULL;
if(l->data<o->data)
{
s->data=l->data;
l=l->next;
}
else
{
s->data=o->data;
o=o->next;
}
h->next=s;/* */
h=s;
}
while(l)/* */
{
s=(LinkList)malloc(sizeof(Node));
s->next=NULL;
s->data=l->data;
h->next=s;
h=s;
l=l->next;
}
while(o)
{
s=(LinkList)malloc(sizeof(Node));
s->next=NULL;
s->data=o->data;
h->next=s;
h=s;
o=o->next;
}
}
단일 체인 시트 에 위 치 를 정 하고 요 소 를 삽입 합 니 다.
void ListInsert(LinkList L,int i,int e)
{
LinkList p=L,s;
while(p&&i>1)
{
p=p->next;
i--;
}
s=(LinkList)malloc(sizeof(Node));
s->data=e;
s->next=p->next;
p->next=s;
}
주 함수 호출
int main()
{
int n,m,i,e;
LinkList L,O,H;
L=(LinkList)malloc(sizeof(Node));
L->next=NULL;/* */
O=(LinkList)malloc(sizeof(Node));
O->next=NULL;
H=(LinkList)malloc(sizeof(Node));
H->next=NULL;
printf(" , , , , :");
scanf("%d%d%d%d",&n,&m,&i,&e);//n L ,m O ,i ,e
printf(" , :");
CreateHeadList(L,n);//
ListTraverse(L);
printf(" , :");
CreateTailList(O,m);//
ListTraverse(O);
ListContact2(L,O,H);
ListTraverse(H);
ListContact1(L,O);
ListTraverse(L);
ListInsert(H,i,e);
ListTraverse(H);
return 0;
}
모든 코드
#include <stdio.h>
#include <stdlib.h>
typedef struct tagNode
{
int data;
struct tagNode *next;
}Node,*LinkList;
void CreateHeadList(LinkList L,int n)//
{
LinkList s;
while(n--)
{
s=(LinkList)malloc(sizeof(Node));
scanf("%d",&s->data);
s->next=L->next;
L->next=s;
}
}
void CreateTailList(LinkList L,int n)//
{
LinkList p,s;
p=L;
while(n--)
{
s=(LinkList)malloc(sizeof(Node));
scanf("%d",&s->data);
p->next=s,p=s;
}
p->next=NULL;
}
void ListTraverse(LinkList L)//
{
LinkList p=L->next;
while(p)
{
printf("%d ",p->data);
p=p->next;
}
printf("
");
}
void ListContact1(LinkList L,LinkList O)
{
LinkList p=L;
while(p->next)
{
p=p->next;
}
p->next=O->next;
}
void ListContact2(LinkList L,LinkList O,LinkList H)
{
LinkList l,o,h,s;
l=L->next;
o=O->next;
h=H;
while(l&&o)
{
s=(LinkList)malloc(sizeof(Node));
s->next=NULL;
if(l->data<o->data)
{
s->data=l->data;
l=l->next;
}
else
{
s->data=o->data;
o=o->next;
}
h->next=s;
h=s;
}
while(l)
{
s=(LinkList)malloc(sizeof(Node));
s->next=NULL;
s->data=l->data;
h->next=s;
h=s;
l=l->next;
}
while(o)
{
s=(LinkList)malloc(sizeof(Node));
s->next=NULL;
s->data=o->data;
h->next=s;
h=s;
o=o->next;
}
}
void ListInsert(LinkList L,int i,int e)
{
LinkList p=L,s;
while(p&&i>1)
{
p=p->next;
i--;
}
s=(LinkList)malloc(sizeof(Node));
s->data=e;
s->next=p->next;
p->next=s;
}
int main()
{
int n,m,i,e;
LinkList L,O,H;
L=(LinkList)malloc(sizeof(Node));
L->next=NULL;
O=(LinkList)malloc(sizeof(Node));
O->next=NULL;
H=(LinkList)malloc(sizeof(Node));
H->next=NULL;
printf(" , , , , :");
scanf("%d%d%d%d",&n,&m,&i,&e);//n L ,m O ,i ,e
printf(" , :");
CreateHeadList(L,n);//
ListTraverse(L);
printf(" , :");
CreateTailList(O,m);//
ListTraverse(O);
ListContact2(L,O,H);
ListTraverse(H);
ListContact1(L,O);
ListTraverse(L);
ListInsert(H,i,e);
ListTraverse(H);
return 0;
}