데이터 구조 복습 - 제2 장: 선형 표
7011 단어 데이터 구조 기 말 복습데이터 구조선형 표싱글 체인 리스트
2. 선형 표 의 기본 연산 은 다음 과 같다.
1) InitList (L), 구조 빈 표, 즉 표 의 초기 화;
2) ListLength (L), 표 의 결점 개수, 즉 표 의 길이 구하 기;
3) GetNode (L, i), 표 중의 i 번 째 결점 을 취하 여 1 ≤ i ≤ ListLength (L) 를 요구한다.
4) LocateNode (L, x) 는 L 의 중간 값 이 x 인 결점 을 찾 고 결점 이 L 에 있 는 위 치 를 되 돌려 줍 니 다. 여러 개의 x 는 첫 번 째 로 되 돌려 주 고 없 으 면 특수 로 되 돌려 줍 니 다. 값 은 찾기 에 실 패 했 음 을 나타 낸다.
5) InsertList (L, x, i) 는 표 의 i 번 째 위치 에 x 의 새로운 결점 을 삽입 하고 1 ≤ i ≤ ListLength (L) + 1 을 요구한다.
6) DeleteList (L, i) 표 의 i 번 째 위치의 결점 을 삭제 하고 1 ≤ i ≤ ListLength (L) 를 요구한다.
3. 순서 표: 선형 표 의 결점 을 논리 적 인 순서에 따라 주소 연속 저장 장치 에 저장 합 니 다.
4. 순서 표 결점 의 저장 주소 계산 공식: Loc (ai) = Loc (a1) + (i - 1) * C;1≤i≤n
5. 순서 표 의 기본 연산
(1) 삽입
Status ListInsert_Sq(SqList &L, int i, ElemType e){
if (i<1 || i>L.length + 1) return ERROR; //i
if (L.length == MAXSIZE) return ERROR;
//
for (j = L.length - 1; j >= i - 1; j--)
L.elem[j + 1] = L.elem[j]; //
L.elem[i - 1] = e; // e i
++L.length; // 1
return OK;
}
n/2 ， O(n)。
（2）
Status ListDelete_Sq(SqList &L,int i,ElemType &e){
if((i<1)||(i>L.length)) return ERROR; //i
e=L.elem[i-1]; // e
for (j=i;j<=L.length-1;j++)
L.elem[j-1]=L.elem[j];
//
--L.length; // 1
return OK;
}
（n+1）/2 ， O(n)。
6. ： 。
，data next data ，next 。
（1） 。 O(n)。
：
1） ；
2） 。
（2） 。 O(n)。
1） 。
Status GetElem(LinkList &L, int i, ElemType &e){
p = L->next; j = 1; //
while (p&&jnext; ++j;
}
if (!p || j>i)return ERROR; // i
e = p->data; // i
return OK;
}
2） 。
LNode *LocateELem(LinkList &L，Elemtype e)
{
p = L->next;
while (p &&p->data != e)
p = p->next;
return p;
// L e ， NULL
}
(3) 연산 삽입.시간 복잡 도 는 O (n) 이다.Status ListInsert_L(LinkList &L, int i, ElemType e){
p = L; j = 0;
while (p&&jnext; ++j; }
// i−1
if (!p || j>i−1)return ERROR;//i + 1 1
s = new LNode; // s
s->data = e; // s e
s->next = p->next; // s L
p->next = s;
return OK;
}//ListInsert_L
(4) 연산 삭제.시간 복잡 도 는 O (n) 이다.Status ListDelete_L(LinkList &L, int i, ElemType &e){
p = L; j = 0;
while (p->next &&jnext; ++j;
}
if (!(p->next) || j>i - 1) return ERROR; //
q = p->next; //
p->next = q->next; //
e = q->data; //
delete q; //
return OK;
}//ListDelete_L
7. 순환 링크: 앞 뒤 가 연 결 된 링크 입 니 다.저장량 을 늘 리 지 않 고 표 의 링크 방식 만 수정 하여 표 의 처 리 를 유연 하고 편리 하 게 하 는 것 이 특징 이다.
8. 빈 순환 체인 시 계 는 하나의 자성 순환 의 두 결점 으로 만 표시 된다.
9. 시계의 조작 은 시계의 맨 끝 위치 에서 이 루어 지 는 경우 가 많 습 니 다. 이때 헤드 포인터 가 표시 하 는 단일 순환 링크 는 편리 하지 않 고 꼬리 포인터 로 바 꿉 니 다. rear 는 단일 순환 링크 를 표시 합 니 다.
헤드 포인터 로 표 시 된 단일 순환 링크 에서 시작 점 을 찾 는 시간 은 O (1) 이 고 끝 점 을 찾 는 시간 은 O (n) 입 니 다.
꼬리 포인터 로 표 시 된 단일 순환 링크 에서 시작 점 과 끝 점 을 찾 는 시간 은 모두 O (1) 입 니 다.
10. 결점 에 포인터 필드, prior | data | next 를 추가 합 니 다.형 성 된 링크 중 두 개의 서로 다른 방향의 체인 을 더 블 링크 라 고 부른다.
1) 더 블 링크 의 앞 삽입 작업.시간 복잡 도 는 O (1) 이다.Status ListInsert_DuL(DuLinkList &L, int i, ElemType e){
if (!(p = GetElemP_DuL(L, i))) return ERROR;
s = new DuLNode;
s->data = e;
s->prior = p->prior;
p->prior->next = s;
s->next = p;
p->prior = s;
return OK;
}
2) 더 블 링크 의 삭제 작업.시간 복잡 도 는 O (1) 이다.Status ListDelete_DuL(DuLinkList &L, int i, ElemType &e){
if (!(p = GetElemP_DuL(L, i)))
return ERROR;
e = p->data;
p->prior->next = p->next;
p->next->prior = p->prior;
delete p;
return OK;
}
11. 순서 표 와 링크 의 비교
1) 공간 에 대한 고려: 순서 표 의 저장 공간 은 정적 으로 분배 되 고 링크 의 저장 공간 은 동적 으로 분배 된다.순서 표 의 저장 밀 도 는 링크 보다 크다.따라서 선형 표 의 길이 변화 가 크 지 않 고 미리 시간 을 정 하기 쉬 우 므 로 순서 표를 저장 구조 로 하 는 것 이 좋다.
2) 시간 에 대한 고려: 순서 표 는 무 작위 액세스 구조 로 선형 표 의 조작 이 주로 검색 되 고 삽입, 삭제 작업 이 적 을 때 순서 표 구 조 를 사용 하 는 것 이 좋다.잦 은 삽입, 삭제 작업 을 하 는 선형 표 는 링크 를 사용 하 는 것 이 좋다.만약 에 조작 이 주로 표 의 처음 과 끝 에 발생 할 때 꼬리 지침 으로 표시 하 는 단일 순환 링크 를 사용한다.
12. 저장 밀도 = (노드 데이터 자체 가 차지 하 는 저장량) / (전체 노드 구조 가 차지 하 는 저장 총량)
저장 밀도: 순서 표 = 1, 체인 표 < 1.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Sparse Table을 아십니까? 나는 알고 있다.Sparse Table을 지금 배웠으므로, 메모를 겸해 씁니다. 불변의 수열의 임의의 구간에 대한 최소치/최대치를, 전처리 $O(N\log N)$, 쿼리 마다 $O(1)$ 로 구하는 데이터 구조입니다. 숫자 열의 값...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
