선형 표 (사상 + 위조 코드 + 부분 코드 실현)
6826 단어 데이터 구조의 선형 표
1. 선형 표 의 추상 적 인 데이터 형식
ADT (List)
Data
Operation
Initlist (*L ) L
ListEmpty ( L ) ture , flash
ClearList (*L )
GetElem (L,i,*e) i e
LocateElem (L,e) e
ListInsert (*L,i,e) i e
ListDelete (*L,i,*e) i , e
ListLength (L)
endDT
2. La 가 집합 A 를 나타 낸다 고 가정 하면 Lb 는 집합 B 를 나타 낸다. 코드 는 다음 과 같은 기능 을 실현 합 니 다. : 선형 표 Lb 에 있 지만 La 에 없 는 모든 요 소 를 La 에 삽입 합 니 다.
void unionL(list *La,list Lb)
{
int La_len,Lb_len,i;
ElemType e; // La,Lb e
La_len=strlen(*La);
Lb_len=strlen(Lb);
for(i=1;i<=Lb_len;i++)
{
GetElem(Lb,i,&e); // Lb i e
if(!LocateElem(*La,e)) //*La e
ListTnstrt(La,++La,e); //
}
}
3. 선형 표 의 순서 저장 구조
선형 표 의 순서 저장 구 조 는 주소 의 저장 장치 로 선형 표 의 데이터 요 소 를 순서대로 저장 하 는 것 을 말한다.
/* */
#define MAXSIZE 20 //
typedef int ElemType; //ELemType , int
typedef struct
{
ElemType data[MAXSIZE];// , MAXZIZE
int lenght; //
}SqList;
4. 선형 표 삽입 및 삭제 작업
우 리 는 여기 서 앞 당 겨 규정 하고, 다음 글 은 상세 하 게 서술 하지 않 는 다.
#define OK 1 #define EEEOR 0 #define TUER 1 #define FALSE 0
코드 구현: L 의 i 번 째 요소 의 값 을 e 로 되 돌려 줍 니 다. 하면, 만약, 만약... 이 곳 에 있 는 배열 의 값 을 되 돌려 줍 니 다. 그렇지 않 으 면 되돌아오다 0 )
/* : L 1<=i<=ListLength(L)*/
/* : e L i */
ststue GetElem(SqList L,int i,ElemType *e)
{
if(L.lenght==0||i<1||i>L.lenght)
return ERROR;// ERROR=0
*e=L.data[i-1];
return OK; // OK=1
}
단일 체인 테이블 찾기
Ststue GetElem(LinkList L,int i,ElemType *e)
{
int j;
LinkList p; // p
p=L->next; // p L
j=i; //
while(p&&jnext; // p
++j;
}
if(!p||j>i) // i
return ERROR;
*e=p->data; // i
return ok;
}
정적 링크 구현:
int Malloc_SLL(staticLinkList space)
{
int i=space[0].cur;// cur ;
if(space[0].cur) // ,
space[0].cur=space[i].cur;
return i;
}
선형 표 의 i 번 째 위치 에 새 요소 e 를 삽입 하고 L 길이 에 1 을 추가 합 니 다.
의사 코드:
Status ListInsert(SqList *L,int i,ElemType e)
{
int k;
if(L->lenght==MAXSIZE) //
return ERROR;
if(i<1||i>L->lengght+1) // i
return ERROR; // 0
if(i<=L->lenght) //
{
for(k=L->lenght-1;k>=i-1;k--) //
L->data[k+1]=L->data[k];
}
L->data[i-1]=e; //
L->lenght++;
return ok;
}
}
단일 링크 코드 구현:
Statue ListInsert(LinkList *L,int i,ElemType e)
{
int j;
LinkList p,s;
p=*L;
j=1;
while(p&&jnext;
++j;
}
if(!p||jdata=e;
s->next=p->next; // p s
p->next=s; // s p
return ok;
}
정적 링크 구현:
status ListInsert(StaticLinkList L,int i,ElemType e)
{
int j,k,l;
k=MAX_SIZE-1; // k
if(i<1||i>ListLength(L)+1)
return ERROR;
j=Malloc_SSL(L); //
if(j)
{
L[j].data=e; // data
for(l=1;l<=i-1;l++) // i
k=L[k].cur;
L[j].cur=L[k].cur; // i cur cur
L[k].cur=j; // i cur
return ok;
}
return ERRIR;
}
선형 표 의 i 번 째 위치 에서 새 요소 e 를 삭제 하고 L 길 이 를 1 로 줄 입 니 다.
의사 코드:
Status LIstDelete(SqList *L,int i,ElemType *e)
{
int k;
if(L->lenght==0) //
return ERROR;
if(i<1||i>L->lenght) //
return ERROE;
*e=L->data[i-1];
if(ilenght) //
{
for(k=i;klenght;k++) //
L->data[k-1]=L->data[k];
}
L->lenght--;
return ok;
}
단일 링크 코드 구현:
Status ListDelete(LinkList *L,int i,ElemType *e)
{
int j;
LinkList p,q;
p=*L;
j=1;
while(p->next&&jnext;
++j;
}
if(!(p->naxt)||j>i)
return ERROR; // i
q=p->next;
p->next=q->next; // q p
*e=q->data; // q e
free(q); // ,
return ok;
}
5. 단일 체인 테이블 의 전체 테이블 생 성
헤드 삽입 법
/* n , L( )*/
void CreateListHead(LinkList *L,int n)
{
LinkLIst p;
int i;
srand(time(0));//
*L=(Linklist)malloc(sizeof(Node));
(*L)->next=NULL;//
for(i=0;idata=rand()%100+1; // 100
p->next=(*L)->next;
(*L)->next=p; //
}
}
미 삽 법
void CreateListTail(LinkList *t,int n)
{
LinkList p,r;
int i;
srand(time(0));//
*L=(LinkList)malloc(sizeof(Node));//
r=*L; //r
for(i=0;idata=rand()%100+1;// 100
r->next=p;//
r=p;//
}
r->next=NULL;//
}
6. 싱글 체인 시트 의 전체 시트 삭제
L 을 빈 테이블 로 초기 화
status ClearList(LinkList *L)
{
LinkList p,q;
p=(*L)->next; //p
while(p) //
{
q=p->next;
free(p);
p=q;
}
(*L)->next=NULL;//
return 0k;
}
정적 링크 구현:
int Malloc_SLL(staticLinkList space)
{
int i=space[0].cur;// cur ;
if(space[0].cur) // ,
space[0].cur=space[i].cur;
return i;
}