데이터 구조 와 알고리즘 (C 언어) 의 선형 표 (연속 식 저장 구조)
선형 표 의 연결 식 저장 구 조 는 데이터 필드 와 포인터 필드 를 포함한다.그 중에서 데이터 도 메 인 은 데이터 요소 정보 포인터 도 메 인 에 지침 을 저장 합 니 다. 저 희 는 이 두 부분 정보 로 구 성 된 데이터 요 소 를 노드 (Node) 라 고 부 릅 니 다.
2.
ADT LinkList
Data
데이터 구 조 는 두 부분 을 포함 하고 일 부 는 데 이 터 를 저장 하 는 데 사용 되 며 다른 일 부 는 다음 구 조 를 가리 키 는 지침 을 저장 하 는 데 사용 된다.
Operation
GetElem (L, i, * e): 단일 체인 테이블 읽 기
링크 i 번 째 데 이 터 를 얻 는 알고리즘 사고: -하나의 노드 p 가 링크 의 첫 번 째 노드 를 가리 키 고 j 를 1 부터 초기 화 합 니 다. -j < i 시 링크 를 옮 겨 다 니 며 p 의 바늘 을 뒤로 이동 시 키 고 다음 노드, j + 1 을 계속 가리 킵 니 다. -링크 끝 p 가 비어 있 으 면 i 번 째 요소 가 존재 하지 않 음 을 나타 낸다. -그렇지 않 으 면 검색 에 성공 하여 결점 p 의 데 이 터 를 되 돌려 줍 니 다.
ListInsert (* L, i, e): 단일 링크 의 삽입
s - > next 와 p - > next 의 지침 을 조금 만 바 꾸 면 됩 니 다. -s->next=p->next; -p->next=s;
ListDelete (* L, i, * e): 단일 링크 의 삭제
원소 a2 의 결점 이 q 라 고 가정 하면 결점 q 에서 단일 체인 테이블 을 삭제 하 는 작업 을 실현 해 야 합 니 다. 사실은 그 이전의 결점 의 바늘 을 가리 키 는 후계 결점 을 돌아 가면 됩 니 다. -p->next=p->next->next; -또는 q = p - > next;p->next=q->next; 단일 체인 테이블 i 번 째 데이터 삭제 노드 의 알고리즘 사고방식: -성명 노드 p 는 링크 의 첫 번 째 노드 를 가리 키 며 j = 1 을 초기 화 합 니 다. -j < 1 시, 체인 시 계 를 옮 겨 다 니 며 p 의 바늘 을 뒤로 이동 시 키 고 다음 노드 를 가리 키 며 j 누적 1; -링크 끝 p 가 비어 있 으 면 i 번 째 요소 가 존재 하지 않 음 을 나타 낸다. -그렇지 않 으 면 찾기 에 성공 하면 결점 p - > next 대 가 를 q 에 삭제 합 니 다. -단일 체인 테이블 의 삭제 표준 문장 p - > next = q - > next; -q 노드 의 데 이 터 를 e 에 게 할당 하여 되 돌려 줍 니 다. -방출 q 결점
Create ListHead (* L, n): 단일 링크 생 성
하나의 동적 으로 링크 를 생 성 하 는 과정 은 '빈 표' 의 초기 상태 부터 각 요소 의 결산 점 을 순서대로 구축 하고 링크 를 하나씩 삽입 합 니 다. -노드 p 와 계수기 변 수 를 설명 합 니 다 i -빈 링크 L 초기 화; -L 의 끝 점 의 바늘 이 NULL 을 가리 키 게 합 니 다. 즉, 앞장 서 는 끝 점 의 단일 체인 표를 만 듭 니 다. -순환 은 후계 결점 의 할당 과 삽입 을 실현 합 니 다.
헤드 삽입 법 은 단일 체인 테이블 을 만 듭 니 다. 헤드 삽입 법 은 빈 테이블 에서 시작 하여 새로운 노드 를 생 성하 고 데 이 터 를 읽 어서 새로운 노드 의 데이터 필드 에 저장 한 다음 에 새 노드 를 당기 체인 테이블 의 헤더 에 삽입 하여 끝 날 때 까지 합 니 다.쉽게 말 하면 새로 추 가 된 요 소 를 시계 머리 뒤에 두 는 첫 번 째 위치 입 니 다. -새로운 노드 의 next 지향 점 을 먼저 만 든 다음 에 -그리고 시계 머리의 next 가 새로운 결점 을 가리 키 게 합 니 다.
CreateListTail(*L,n)
꼬리 삽입 법 은 단일 체인 표를 만 듭 니 다. 머리 삽입 법 이 만 든 체인 표 의 결점 순 서 는 입력 의 순서 와 반대 입 니 다.단일 체인 표 의 꼬리 삽입 방법 은 다음 과 같다. -링크 의 헤드 포인터 만 들 기 -두 개의 포인터 변수 로 차례대로 순환 하여 결점 을 아래로 삽입 합 니 다.
CleareList (* L): 단일 링크 의 전체 시트 삭제
단일 체인 테이블 전체 테이블 삭제 알고리즘 사고방식 은 다음 과 같다. -선언 노드 p 와 q -첫 번 째 결산 점 을 p 에 부여 하고, 다음 결산 점 은 q 에 부여 합 니 다. -p 와 q 값 을 p 에 부여 하 는 동작 을 반복 적 으로 실행 합 니 다.
3. 실현
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
/**
， 。
；
， （Node）
*/
#define OK 1
#define ERROR 0
typedef int Status;
typedef int ElemType;
typedef struct Node
{
ElemType data;
struct Node* next;
}Node;
typedef struct Node* LinkList;
/*
i ：
- p ， j 1 ；
- j<i ， ， p ， ，j+1
- p ， i ；
- ， p 。
*/
Status GetElem(LinkList L,int i,ElemType *e)
{
int j=1;
LinkList p;
p=L->next;
if(!p || j>i)
return ERROR;
while(p && j<i)
{
p=p->next;
++j;
}
*e=p->data;
return OK;
}
/*
：
s->next p->next 。
-s->next=p->next;
-p->next=s;
*/
Status ListInsert(LinkList *L,int i,ElemType e)
{
int j=1;
LinkList p,s;
p=*L;
if(!p || j>i)
return ERROR;
while(p&&j<i)
{
p=p->next;
j++;
}
s=(LinkList)malloc(sizeof(Node));
s->data=e;
s->next=p->next;
p->next=s;
return OK;
}
/*
：
a2 q， q ，
-p->next=p->next->next;
- q=p->next;p->next=q->next;
i ：
- p ， j=1；
- j<1 ， , p ， ，j 1；
- p ， i ；
- ， p->next q；
- p->next=q->next;
- q e， ；
- q
*/
Status ListDelete(LinkList *L,int i,ElemType *e)
{
int j=1;
LinkList p,q;
p=*L;
if(!(p->next)||j>i)
return ERROR;
while((p->next)&&j<i)
{
p=p->next;
++j;
}
q=p->next;
*e=q->data;
p->next=q->next;
free(q);
return OK;
}
/*
：
， “ ” ，
- p i
- L;
- L NULL， ；
- 。
*/
/*
：
， ， ， ， 。
， ：
- next
- next
*/
void CreateListHead(LinkList *L,int n)
{
LinkList p;
int i;
srand(time(0));
*L=(LinkList)malloc(sizeof(Node));
(*L)->next=NULL;
for(i=0;i<n;i++)
{
p=(LinkList)malloc(sizeof(Node));
p->data=rand()%100+1;
p->next=(*L)->next;
(*L)->next=p;
}
}
/*
：
。
：
-
-
*/
void CreateListTail(LinkList *L,int n)
{
LinkList p,r;
int i;
srand(time(0));
*L=(LinkList)malloc(sizeof(Node));
r=*L;
for(i=0;i<n;i++)
{
p=(LinkList)malloc(sizeof(Node));
p->data=rand()%100+1;
r->next=p;
r=p;
}
r->next=NULL;
}
/*
：
- p q
- p， q；
- p q p
*/
Status ClearList(LinkList *L)
{
LinkList p,q;
p=(*L)->next;
while(p)
{
q=p->next;
free(p);
p=q;
}
(*L)->next=NULL;
return OK;
}
/*
1.
-
- ，
2.
-
O(1)
O(n)
-
， O(n)
， O(1)
-
， ， 。
，
*/
int main()
{
printf("Hello world!
");
return 0;
}
4. 단일 링크 구조 와 순서 저장 구조의 장단 점
1. 저장 소 할당 방식 -순차 저장 구 조 는 연속 적 인 저장 장치 로 선형 표 의 데이터 요 소 를 순서대로 저장 합 니 다. -단일 체인 표 는 체인 식 저장 구 조 를 사용 하고 임의의 저장 장치 로 선형 표를 저장 하 는 요소 2. 시간 성능 -찾다 순차 기억 구조 O (1) 단일 체인 테이블 O (n) -삽입 및 삭제 순서 저장 구 조 는 평균 이동 표 의 절반 의 요 소 를 필요 로 하고 시간 은 O (n) 이다. 단일 링크 는 특정한 위치 에 있 는 지침 을 계산 한 후에 출입 과 삭제 시간 은 O (1) 에 불과 합 니 다. -공간 성 이 연하 다 선형 표 가 자주 찾 아야 한다 면 삽입 과 삭제 작업 이 적 고 순서 저장 구 조 를 사용 하 는 것 이 좋다. 잦 은 삽입 과 삭제 가 필요 할 경우 단일 체인 시트 구 조 를 사용 하 는 것 이 좋 습 니 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
C 언어 체인 시계는 뱀을 탐식하는 작은 게임을 실현한다본고의 실례는 여러분에게 C 언어 체인표가 뱀 탐식 게임을 실현하는 구체적인 코드를 공유하여 참고하도록 하였으며, 구체적인 내용은 다음과 같다. 프로젝트 이름: 뱀놀이 운영 환경: Linux 프로그래밍 언어: C 언...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
