//정적 할당은 시퀀스 테이블을 정의하며, 저장 공간은 정적이며 크기는 처음부터 고정되어 있습니다. #define MaxSize 10//최대 길이 정의 형식 정의 구조체{ ElemType data[MaxSize]; //정적 "배열"을 사용하여 데이터 요소 저장 int length; //시퀀스 테이블의 현재 길이 }SqList; //시퀀스 목록의 유형 정의(정적 할당 방법) ElemType은 int, double 등 직접 정의한 데이터 유형을 나타냅니다. //초기화 순서 테이블 #include<stdio.h> #define MaxSize10 형식 정의 구조체{ 정수 데이터[최대 크기]; 정수 길이; }SqList; 무효 InitList(SqList &L){ for(int i=0;i<MaxSize;i) L.data[i]=0; //모든 데이터 요소를 기본 초기값으로 설정 L.length=0; //시퀀스 테이블의 초기 길이를 0으로 설정합니다. } 정수 메인(){ SqList L; //시퀀스 목록 선언 InitList(L): //초기화 시퀀스 목록 ... 0을 반환합니다. } //동적 할당 구현 순서 테이블, 크기 변경 가능 #include<stiod.h> #define InitSize 10 //기본 최대 길이 형식 정의 구조체{ int *data; //동적으로 할당된 배열을 나타내는 포인터 int MaxSize; //시퀀스 테이블의 최대 용량 int length; //시퀀스 테이블의 현재 길이 }SeqList; //시퀀스 목록 정의 정수 메인(){ SeqList L; //시퀀스 목록 선언 초기화목록(L): //네트워크 시퀀스 테이블에 무작위로 여러 요소를 삽입합니다. 증가크기(L,5); 0을 반환합니다. } 무효 InitList(SeqList &L){ //malloc 함수를 이용하여 지속적인 저장공간을 신청한다. L.data(int *)malloc(InitSize*sizeof(int)); L.길이=0; L.MaxSize=초기화 크기; } //동적 배열의 길이를 늘린다. 무효 증가 크기(SeqList &L,int len){ int *p=L.data; L.data(int *)malloc((L.MaxSize len)*sizeof(int)): for(int i=0;i<L.length;i ){ L.data[i]=p[i]; //새 영역에 데이터를 복사합니다. } L.MaxSize=L.MaxSize len; //시퀀스 테이블의 최대 길이는 len만큼 증가합니다. free(p); //원래 메모리 공간을 해제합니다. }

L.data=(ElemType *)malloc(ElemType의 크기 *InitSize) malloc 함수는 정의한 데이터 요소 유형에 대한 포인터로 캐스팅되어야 하는 포인터를 반환합니다.

ListInsert(&L,I,e), i번째 위치에 지정된 요소 e를 삽입합니다.

//순차적 테이블 요소 삽입 #define 최대 크기 10 형식 정의 구조체{ ElemType 데이터[MaxSize]; 정수 길이; }SqList; void ListInsert(SqList &L,int I,int e){ for(int j=L.length;j>I;j--){ //i번째 요소와 후속 요소를 뒤로 이동 L.data[j]=L.data[j-1]; } L.data[i-1]=e; //i번째 위치에 e를 넣습니다. L.길이; //길이 1 } 정수 메인(){ SqList L; 초기화목록(L): //여기에서는 생략되었으며 일련의 요소를 삽입할 수 있습니다. ListInsert(L,3,3); 0을 반환합니다. } //피드백 없이 요소를 삽입하는 것을 방지하려면, 예를 들어 메모리가 가득 찬 경우 Insert 함수를 수정하여 반환 값을 갖도록 해야 합니다. bool ListInsert(SqList &L,int I,int e){ if(i<1 || i>L.길이 1) 거짓을 반환; if(L.길이>=최대크기) 거짓을 반환; for(int j=L.length;j>i;j--) L.data[j]=L.data[j-1]; L.data[i-1]=e; L. 길이; 거짓을 반환; }

ListDelete(SqList &L,int i,int &e), 테이블 L의 i 위치에 있는 요소를 삭제하고 해당 요소의 값을 반환합니다.

//시퀀스 테이블 삭제 bool ListDelete(SqList &L,int i,int &e){ if(i<1 || i>L.length 1) //i의 범위가 유효한지 확인 거짓을 반환; e=L.data[i-1]; for(int j=1;j<L.길이;j) L.data[j-1]=L.data[j]; L.길이--; 사실을 반환; } 정수 메인(){ SqList L; 초기화목록(L); int e=-1; if(목록삭제(L,3,e)) printf("세 번째 요소를 삭제합니다. 삭제된 요소 값은 =%d/n입니다.",e); 또 다른 pprintf("비트 순서 i가 잘못되었습니다. 삭제에 실패했습니다. "); 0을 반환합니다. }

GetElem(L,i), 테이블 L의 i번째 위치에 있는 요소의 값을 가져옵니다.

//비트별로 검색 //정적 할당 #define MaxSize 형식 정의 구조체{ ElemType data[MaxSize]; //정적 "배열"을 사용하여 데이터 요소 저장 int length; //시퀀스 테이블의 현재 길이 }SqList; //시퀀스 목록의 유형 정의(정적 할당 방법) ElemType GetElem(SqList L,int i){ return L.data[i-1]; //i번째 요소의 값을 반환하려면 GetElem() 함수를 호출하세요. } //동적 할당 #defineInitSize 형식 정의 구조체{ ElemType *데이터; int MaxSize; 정수 길이; }순차목록; ElemType GetElem(SeqList L,int i){ L.data[i-1]을 반환합니다. }

LocateElem(L,e), 테이블 L에서 주어진 키워드 값을 가진 요소를 찾습니다.

//값으로 검색 #defineInitSize 10 형식 정의 구조체{ ElemType *데이터; int MaxSize; 정수 길이; }순차목록; //시퀀스 목록 L에서 첫 번째 요소 값이 e와 동일한 요소를 찾아 비트 순서를 반환합니다. int LocateElem(SeqList L,ElemType e){ for(int i=0;i<L.length,i) if(int i=0;o<L.길이;i) return i 1; //배열에서 i로 표시된 요소의 값은 e와 동일하며 해당 비트 순서는 i 1로 반환됩니다. return 0; //루프를 종료하여 검색이 실패했음을 나타냅니다. }

시간 복잡도: 최고 O(1), 최악 O(n), 평균 O(n)

데이터 요소를 저장하는 것 외에도 각 노드는 다음 노드에 대한 포인터도 저장합니다.

구조체 LNode{ ElemType data; //단일 연결리스트 노드 유형 정의 struct LNode *next;//각 노드는 데이터 요소를 저장합니다. } struct LNode *p=(struct LNode *)malloc(sizeof(struct LNode)); //새 노드가 추가될 때마다 메모리에 노드 공간을 적용하고 포인터 p를 사용하여 이 노드를 가리킵니다. LNode *p=(LNode *)maloc(sizeof(LNode)); 대신 typedef struct LNode LNode;를 사용할 수도 있습니다. 이 경우 노드를 추가하는 데 struct LNode가 필요하지 않습니다.

//교과서, 단일 연결 리스트 정의 typedef struct LNode{} //단일 연결 리스트 노드 유형 정의 ElemType 데이터; //데이터 필드 struct LNode *next; 포인터 필드 LNode,*LinkList; //LNode의 이름이 바뀌었습니다. *LinkList는 이 노드에 대한 포인터입니다. LNode *를 사용하여 이것이 노드임을 강조합니다. LinkList를 사용하여 이것이 단일 연결 목록임을 강조합니다.

선두 노드

선행 노드 없음

끼워 넣다

삭제

비트별 검색

값으로 찾기

테이블의 길이를 찾아보세요

1단계: 단일 연결 리스트 초기화 2단계: 한 번에 하나의 데이터 요소를 제거하고 테이블의 머리/바닥에 삽입합니다.

꼬리 삽입 방법

헤드 삽입 방법

단일 연결 목록: 단일 연결 목록은 역방향으로 검색할 수 없으므로 때로는 불편합니다. 이중 연결 리스트: 전진 및 후퇴 가능, 저장 밀도 감소

//이중 연결 리스트(리드 노드) 초기화 bool InitDLinkList(DLinklist &L){ L=(DNode *)malloc(sizeof(DNode)); if(L==NULL) 리턴 플래시; L->이전=NULL; L->다음=NULL; 사실을 반환; } 무효 테스트DLinkList(){ //이중 연결 리스트 초기화 DLinklist L; InitDLinkList(L); //...다음 코드 } typedef 구조체 Dnode{ ElemType 데이터; struct DNode *prior,*next; }Dnode,*DLinklist; //이중 연결 리스트가 비어 있는지 확인(리드 노드) bool 비어있음(DLinklist L){ if(L->다음==NULL) 사실을 반환; 또 다른 거짓을 반환; }

//이중 연결 리스트에 삽입 bool InsertNextDNode(DNode *p,DNode *s){ s->next=p->next; //노드 *p 뒤에 노드 *s를 삽입합니다. p->다음->이전=s; s->이전=p; p->다음=s; }

//이중연결리스트 삭제 bool DeleteNextDNode(DNode *p){ if(p==NULL) return flase; DNode *q=p->next; //p의 후속 노드 q를 찾습니다. if(q==NULL) return false; //p에는 후속 노드가 없습니다. p->다음=q->다음; if(q->next!=NULL) //q 노드는 마지막 노드가 아닙니다. q->다음->이전=p; free(q); //노드 공간 해제 사실을 반환; } 무효 DestoryList(DLinklist &L){ //각 데이터 노드를 해제하는 루프 while(L->다음!=NULL) 삭제NextDnode(L); free(L); //헤드 노드를 해제합니다. L=NULL; //헤드 포인터가 NULL을 가리킴 }

//이중연결리스트 순회 while(p!=NULL){ //역방향 순회 //노드 p에 해당하는 처리를 수행합니다. p=p->다음; } while(p!=NULL){ //정방향 순회 p=p->프리오에; } while(p->prioe!=NULL){ //정방향 순회, 헤드 노드 건너뛰기 p=p->이전; }

단일 연결 리스트: 하나의 노드부터 시작하여 후속 노드만 찾을 수 있으며 이전 노드는 알 수 없습니다. 순환형 단일 연결 리스트: 한 노드에서 시작하여 다른 노드를 찾을 수 있습니다.

//순환형 단일 연결 리스트 정의 typedef struct LNode{ //단일 연결 리스트 노드 유형 정의 ElemType data; //각 노드는 데이터 요소를 저장합니다. struct LNode *next; //데이터는 다음 노드를 가리킵니다. }LNode,*LinkList; //순환형 단일 연결 리스트 초기화 bool InitList(LinkList &L){ L=(LNode *)malloc(sizeof(LNode)); //헤드 노드 할당 if(L==NULL) //메모리 부족, 할당 실패 거짓을 반환; L->next = L; //헤드 노드 Next는 헤드 노드를 가리킵니다. 사실을 반환; } //순환형 단일 연결 리스트가 비어 있는지 확인 bool 비어 있음(LinkList L){ if(L->다음==L) 사실을 반환; 또 다른 리턴 플래시; } //노드 p가 순환 단일 연결 리스트의 끝 노드인지 확인 bool isTail(LinkList L,LNode *p){ if(p->다음==L) 사실을 반환; 또 다른 거짓을 반환; }

//빈 원형 이중 연결 리스트 초기화 bool InitDLinkList(DLinklist &L){ L=(DNode *)malloc(sizeof(DNode)); //헤드 노드 할당 if(L==NULL) //메모리 부족, 할당 실패 거짓을 반환; L->prior=L; //헤드 노드의 우선순위는 헤드 노드를 가리킵니다. L->next=L; //헤드 노드의 다음은 헤드 노드를 가리킵니다. 사실을 반환; } 무효 테스트DLinkList(){ //순환 이중 연결 리스트 초기화 DLinklist L; InitDLinkList(L); //...다음 코드 } //순환 이중 연결 리스트가 비어 있는지 확인 bool 비어있음(DLinklist){ if(L->다음==L) 사실을 반환; 또 다른 거짓을 반환; } //노드 p가 순환 이중 연결 리스트의 끝 노드인지 확인 bool isTail(DLinklist L,Dnode *p){ if(p->다음==L) 사실을 반환; 또 다른 거짓을 반환; } typedef 구조체 Dnode{ ElemType 데이터; struct DNode *prior,*next; }Dnode,*DLinklist;

단일 연결 리스트: 각 노드가 메모리에 무작위로 할당됩니다. 정적 연결 리스트: 연속적인 메모리 공간 전체를 할당하고 각 노드가 중앙에 배치됩니다.

//정적 연결리스트 정의 #define 최대 크기 10 typedef sreuct{} ElemType 데이터; int 다음; } 무효 테스트SLinkList(){ 구조체 노드 a[MaxSize]; //...다음 코드 } //다음 코드를 사용하여 정적 연결 목록을 만들 수도 있습니다. #define MaxSize 10 //정적 연결 리스트의 최대 길이 typedef struct{ //정적 연결리스트 구조 유형 정의 ElemType 데이터; //저장 데이터 요소 int next; //다음 요소의 배열 첨자 } SLinkList[최대 크기]; 무효 테스트SLinkLst(){} SLinkLista; //...다음 코드 }

그것들은 모두 선형 테이블과 선형 구조입니다.

시퀀스 테이블의 장점: 무작위 액세스 및 높은 저장 밀도를 지원합니다. 단점: 연속적인 공간의 큰 면적을 할당하는 것이 불편하고 용량을 변경하는 것이 불편합니다. 연결 목록의 장점: 개별적인 작은 공간을 할당하기 쉽고 용량을 변경하기 쉽습니다. 단점: 무작위 액세스가 불가능하고 저장 밀도가 낮습니다.

시퀀스 테이블 생성: 대규모 연속 공간을 사전 할당해야 합니다. 할당된 공간이 너무 작으면 나중에 용량을 확장하기가 불편하고, 할당된 공간이 너무 크면 메모리 자원이 낭비됩니다. 정적 할당: 정적 배열, 불변 용량 동적 할당: 동적 배열(malloc, free), 용량을 변경할 수 있지만 많은 수의 요소를 이동해야 하므로 시간이 많이 걸립니다. 파기: 길이를 0으로 수정하면 정적으로 할당된 공간이 자동으로 회수되고 동적으로 할당된 malloc 애플리케이션을 수동으로 해제해야 합니다. 요소를 삽입/삭제하려면 후속 요소를 뒤로/앞으로 이동해야 합니다. 시간 복잡도는 O(n)이고 시간 오버헤드는 주로 요소 이동에서 발생합니다. 이동요소가 크면 이동시간 비용이 높다. 검색: 비트별 검색: O(1). 값으로 검색: O(n) 테이블의 요소를 정렬하면 O(log2n) 시간에 찾을 수 있습니다.

연결리스트 생성: 나중에 쉽게 확장할 수 있는 헤드 노드(헤드 노드를 생략하고 헤드 포인터만 선언할 수도 있음)만 할당하면 됩니다. 파괴: 각 노드를 차례로 삭제(무료) 요소를 삽입/삭제하려면 포인터만 수정하면 됩니다. 시간 복잡도는 O(n)이며, 시간 오버헤드는 주로 대상 요소를 찾는 데서 발생합니다. 요소를 찾는 데 드는 시간 비용이 더 낮습니다. 검색: 비트 검색: O(n). 값으로 찾기: O(n).

순차 목록 또는 연결 목록 사용: 목록의 길이를 추정하기 어렵고 요소를 추가, 빼기/삭제해야 하는 경우가 많으므로 연결 목록을 사용하십시오. 테이블 길이를 추정할 수 있고 질의(검색) 작업이 많기 때문에 순차 테이블을 사용합니다. 질문: 시퀀스 목록과 연결 목록에 대해 설명해주세요. 시퀀스 목록과 연결 목록 중 어느 것을 사용하는 것이 더 좋나요? 시퀀스 목록과 연결 목록의 논리적 구조는 선형 결과이며 둘 다 선형 목록에 속합니다. 그러나 둘의 저장 구조는 다릅니다. 시퀀스 테이블은 순차 저장을 사용합니다...(특징, 장점 및 단점) 연결 목록은 체인 저장을 사용합니다...(장점 및 단점) 다양한 저장 방법을 사용하기 때문에 기본 작업의 구현 효율성도 다릅니다. 초기화할 때...데이터 요소를 삽입할 때...데이터 요소를 삭제할 때...데이터 요소를 검색할 때...

"정적 배열"을 사용하여 구현됨

사이즈가 결정되면 변경할 수 없습니다.

"동적 배열"을 사용하여 구현됨

L.data=(ElemType *)malloc (sizeof(El;emType)* 크기)

시퀀스 테이블이 가득 차면 malloc을 사용하여 시퀀스 테이블의 최대 처리량을 동적으로 확장할 수 있습니다.

데이터 요소를 새로운 저장 영역에 복사하고 무료 기능을 사용하여 원래 영역을 해제해야 합니다.

O(1) 시간 안에 i번째 요소를 찾을 수 있습니다.

정의(코드로 구현하는 방법)

기본 작업 구현

단일 목록

이중 연결 리스트

순환 연결 리스트

정적 연결리스트

L의 i번째 위치에 요소 e를 삽입합니다.

최고 O(1), 최악 O(n), 평균 O(n)

L의 i번째 요소를 삭제하고 e로 반환합니다.

최고 O(1), 최악 O(n), 평균 O(n)

테이블 L의 i 위치에 있는 요소의 값을 가져옵니다.

배열 첨자를 사용하여 i번째 요소 L.data[i-1]을 가져옵니다.

최고/최악/평균 시간 복잡도는 O(1)입니다.

시퀀스 목록 L에서 첫 번째 요소 값이 e와 동일한 요소를 찾고 해당 비트 순서를 반환합니다.

첫 번째 요소부터 시작하여 뒤로 검색

가장 좋은 시간 복잡도는 O(1)입니다.

최악의 시간 복잡도 O(n)

평균 시간 복잡도 O(n)

빈 테이블 판단: L==NULL

코드 작성이 쉽다

빈 테이블 판단: L->next==NULL;

코드 작성이 불편하다

선두 노드

선행 노드 없음