데이터 구조 정리 - 제2 장 선형 표

대학원 에 진학 할 때 개인 적 으로 정리 한 것 은 왕도, 엄 울 민 등 데이터 구 조 를 참고 한다.
지난 장 - 서문: https://blog.csdn.net/mooe1011/article/details/87894843
다음 장 -- 창고 와 대기 열:https://blog.csdn.net/mooe1011/article/details/88089325
 
선형 표

문자열 은 특수 한 선형 표 로 그 특수성 은 데이터 요소 에 나타 나 는 문자

이다.
1. 순서 표

무 작위 로 접근 할 수 있 고 끝부분 에 삭제 시간 을 O (1) 로 삽입 할 수 있 으 며 다른 위 치 는 요 소 를 이동 해 야 합 니 다

저장 밀도 가 높 고 결점 은 데이터 요소

논리 적 순 서 는 물리 적 순서 와 같다

비 선형 구 조 를 저장 할 수 있다. 예 를 들 어 이 진 트 리 의 순서 저장

한 점 을 삽입 하여 이동 하 는 평균 횟수 는 n/2 이다.(n - 1)/2 로 삭제 하기;찾기 (n + 1)/2

주의사항:

아래 표 시 는 0 부터 시작 하면 마지막 요 소 는 L. data [L. length - 1] 이 고 요소 의 위 치 를 되 돌려 주 려 면 i + 1

을 기억 하 세 요.

함수 인터페이스 에 인용 순서 표 가 있 으 면 SqList &L, L. length 수정 하 세 요

#define MaxSize 50
typedef struct{
    int data[MaxSize];
    int length;
}SqList;

크로스 L. length = = 0 | i > L. length

검사

삽입 bool ListInsert

O (1) 가 가장 좋다.평균 O (n);L. length > = MaxSize

를 검사 해 야 합 니 다.

판단 합 법, length + 1

주의

if(i<1||i>L.length+1||L.length>=MaxSize)  //   1  
    return false;

//         ，  length

for (int j=L.length;j>=i;j--)
    L.data[j]=L.data[j-1];
L.data[i-1]=e;
L.length++;
return true;

삭제

bool ListDelete(SqList &L;int i,int &e){
    if (i<1 ||i>L.length)
        return false;
    e=L.data[i-1];
    for(int j=i;j

k 개 원소 삭제

if (L.data[i]   ) k++;
else L.data[i-k]=L.data[i];
L.length -=k；

k 개 요 소 를 삭제 하지 않 음 (위 개선)

if (L.data[i]    ) L.data[k++]=L.data[i];
L.length =k;

합병 Merge

  C.MaxSize  A、B   
while(i

절반 으로 찾기 Binary Search

int low=0,high=L.length-1,mid;
while(low<=high) {
    mid=(low+high)/2;
    if(  )break;
    else if(   ) low=mid+1;
    else high=mid-1;
}

배열 ab 가 ba

로 역전 되 었 다.

void Reverse(int R[],int from,int to){
    int i,temp;
    for(i=0;i

2. 링크

꼬리 삽입 법 은 꼬리 노드 포인터 가 비어 있 는 것 을 기억 합 니 다. r -> next = NULL;

더 블 링크 삽입 삭제 복잡 도 는 모두 O (1) 이다.질서 있 는 단일 체인 표를 만 드 는 최저 시간 복잡 도 는 O (nlog2N)

이다.

순환 싱글 체인 표 의 빈 조건 은 두 결점 지침 이 자신 과 같다.모든 위치 삽입 삭제 작업 은 표 끝 여 부 를 판단 할 필요 가 없습니다

정적 링크 의 지침 은 다음 요 소 를 배열 에서 표시 하 는 것 을 가리 키 는 것 으로 커서

라 고도 부른다.

순환 목록 의 장점 은 임의의 노드 에서 출발 하여 전체 링크

에 접근 할 수 있다.

헤더 노드 L = (LinkList) malloc (sizeof (LNode) 를 만 듭 니 다.L->next=NULL;

옮 겨 다 니 기 1. 첫 번 째 LNode * p = L -> next 를 가리킨다.2.p=p->next;

귀속 delx(L->next,x);

typedef struct DNode{
    int data;
    struct DNode *prior,*next;
}DNode,*Dlinklist;

재 귀적 삭제 값 이 x 의 결점

void del_x (Linklist &L,int x) {
    LNode *p;
    if(L==NULL) return;
    if(L->data==x){
        p=L;
        L=L->next;
        free(p);
        del_x(L,x);
    }
    else del_x(L->next,x);
}

선두 결점 단일 체인 표 값 이 x 인 결점 삭제

pre 를 사용 하여 전구 결점 을 가리 키 기

LNode *p=L->next,*pre=L,*q;
while(p!=NULL){
    if(p->data==x){
        q=p;
        p=p->next;
        pre->next=p;
        free(q);
    } else {
        pre=p;
        p=p->next;
    }
}

 ：    p  pre,p->next  p
LNode *p=L,*q;  //   
while(p->next!=NULL）{
    if(p->next->data==x){
        q=p->next;
        p->next=p->next->next;
        free(q);
    } else p=p->next;
}

꼬리 삽입 법 기억 r -> next = NULL

LNode *p=L->next,*r=L,*q;  //r     
while(p!=NULL){
    if(p->data!==x){
        r->next=p;
        r=p;
        p=p->next;
    } else {
        q=p;
        p=p->next;
        free(q);
    }
}
r->next=NULL;

재 귀 역전

void R(LinkList L){
    if(L->next!=NULL)
        R(L->next);
    print(L->data);
}

역전

LNode *p,*r;
p=L->next;
L->next=NULL;
whlie(p!=NULL){
    r=p->next;
    p->next=L->next;
    L->next=p;
    p=r;
}