선형 표 (단일 체인 표, 더 블 링크, 정적 링크 와 순환 링크) 를 상세 하 게 서술 합 니 다.
323320 단어 데이터 구조
관건:
유한 시퀀스 첫 번 째 요 소 는 하나의 전구 결점 만 있 고 마지막 요 소 는 하나의 후계 결점 만 있 으 며 중간 요 소 는 하나의 전구 결점 과 하나의 후계 결점 이 있다.
선형 표 는 0 개의 데이터 요 소 를 가 질 수 있 는데 빈 표 라 고 부른다.
선형 표 는 순서 저장 구조 와 체인 저장 구조 로 나 뉜 다.
순차 기억 구조:
주소 연속 저장 공간 으로 선형 표 의 데이터 구 조 를 순서대로 저장 합 니 다.
물리 적 관계 상:
메모리 에서 초기 주 소 를 찾 은 다음 에 자 리 를 차지 하 는 방식 으로 일정한 메모리 공간 을 점령 한 다음 에 같은 데이터 형식의 데이터 요 소 를 순서대로 이 메모리 에 저장 하 는 것 입 니 다.
속성:
저장 공간의 시작 위치, 배열 data, 그의 저장 위 치 는 선형 표 저장 공간의 저장 위치 이다.
선형 표 의 최대 저장 용량: 배열 의 길이 MAXSIZE 선형 표 의 현재 길이: length 주의:
배열 의 길이 와 선형 표 의 현재 길 이 는 구분 해 야 한다. 배열 의 길 이 는 선형 표를 저장 하 는 저장 공간의 총 길이 이 고 보통 초기 화 된 후에 변 하지 않 으 며 선형 표 의 현재 길 이 는 선형 표 에서 요소 의 개수 로 변화 할 것 이다.
순서 링크 삽입 동작:
생각:
삽입 위치 가 불합리 하면 이상 던 지기 선형 표 길이 가 배열 길이 보다 크 면 이상 또는 동적 확장 을 던 집 니 다.
마지막 요소 부터 i 번 째 위치 로 옮 겨 다 니 며 각각 한 자 리 를 뒤로 이동 합 니 다
메모: 선형 표 는 1 부터 시작 합 니 다.
순서 링크 삭제 작업:
생각:
삭제 위치 가 불합리 하면 이상 던 지기 삭제 요소 추출 요소 의 위 치 를 삭제 할 때 부터 마지막 요소 의 위 치 를 옮 겨 다 니 며 각각 한 위 치 를 앞으로 이동 합 니 다 .
시계 길이 1 감소
/* ： L ，1<=i<=ListLength(L)*//* ： L i ， e ，L -1*/
Status ListDelete(Sqlite *L, int i, ElemType *e){ int k; if(L -> length == 0) { return ERROR; } if(i < 1 || i > L -> length) { return ERROR; }
*e = L -> data(i - 1);
if(i < L -> length) { for(k = i; k < L -> length; k++) { L -> data(k - 1) = L -> data(k); } }
L -> length --;
return OK;}
：
： ， ， O（1）；
： ， ， O（n）；
：
， 、 ， ， O（1）， ， O（n）。
， ，
：
-
-
：
-
- ，
- ” ”
：
， —— 。
？
， ， ， 。
：
- ，
- ， ， ， （ ）
：
， ， 。 ， 。
？
：
- ， ，
- ， （ ）
- ，
-
：
- ， ， （ ）
- ， 。
-
：
：
- p ， j 1
- j < i ， ， p ， ， j + 1
- p ， i
- ， p
/* ： L ，1<=i<=ListLength(L)*//* ： L i ， e ，L -1*/Status GetElem(LinkList *L, int i, ElemType *e){ int k; LinkList p;
p = L -> next; j = 1;
while(p && j < 1) { p = p -> next; ++j; }
if(!p || j > i) { return ERROR; }
*e = p -> data;
return OK;}
：
：
- p ， j 1
- j < i ， ， p ， ， j ++
- p ， i
- ， s
- e s -> data
-
-
：
/* ： L ，1<=i<=ListLength(L)*//* ： L i ， e ，L -1*/Status GetElem(LinkList *L, int i, ElemType *e){ int k; LinkList p,s;
p = *L; j = 1;
while(p && j < 1) { p = p -> next; j++; }
if(!p || j > i) { return ERROR; }
s = (LinkList)malloc(sizeof(Node)); s -> data = e;
s -> next = p -> next; p -> next = s;
return OK;}
：
：
- p ， j = 1
- j < 1 ， ， p ， ， j++
- p ， i
- ， p -> next q
- ：p -> next = q -> next
- q e，
- q
/* ： L ，1<=i<=ListLength(L)*//* ： L i ， e ，L -1*/Status GetElem(LinkList *L, int i, ElemType *e){ int k; LinkList p,q;
p = *L; j = 1;
while(p && j < 1) { p = p -> next; j++; }
if(!p || j > i) { return ERROR; }
q = p -> next; p -> next = q -> next; *e = q -> data; free(q); return OK;}
：
- ， ， ： i ， ：
- O（n）
- i ， ，
- i ， ， O（1）（ ）
：
：
- 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){ LiskList p, q; p = (*L) -> next;
while(p) { q = p -> next; free(p); p = q; }
(*L) -> next = NULL;
return OK;}
：
-
-
- ，
2.
（1）
- ：O（1）
- ：O（n）
（2）
- ， ：O（n）
- ， ， ：O（1）
3.
- ，
- ，
：
6
5
3
4
5
2
7
……
1
A
C
D
E
B
……
0
1
2
3
4
5
6
……
999
#define MAX_SIZE = 1000 ；
typedef struct{
ElemType data ;
int cur ;
}Component , StaticLinkList[MAX_SIZE];
Status InitList(StaticLinkList L){
for(int i= 0 ; i < MAX_SIZE-1 ; ++i)- {
- space[i].cur = i+1 ;
- }
-
- space[MAX_SIZE-1].cur = 0 ;
-
- return OK ;
}
// int Malloc_SSL(StaticLinkList L )- {
int i = space[MAX_SIZE-1].cur ; //
if(space[0].cur) // - {
- i = space[0].cur ; //
- }
-
- space[0].cur = space[i].cur ; // ，
-
- return i ;
- }
// ：
Status InserList(StaticLinkList L , int i , ElemType e)- {
- int k = MAX_SIZE-1 ;
-
- if( i < 1 || i >Length(L)+1)
- return ERROR ;
-
- int j = Malloc_SSL(L) ; //
if (j) // - {
- L[j].data = e ;
-
- for(int m = 1 ; m < i ; ++m) // i-1
- k = L[k].cur ；
-
- L[j].cur = L[k].cur ; // i-1 cur ， i-1 cur
-
- L[k].cur = j ;
return OK ;
}
return ERROR ;
}
// :
Status DeleteLinkList(StaticLinkList L , int i )- {
- if(i < 1 || i > ListLength(L))
- return ERROR ;
-
- int k = MAX_SIZE - 1 ;
for(int j = 1 ; j < i ; ++j) // i-1 - {
- k = L[k].cur ;
- }
j = L[K].cur ; // i
L[k].cur = L[j].cur ; // i cur i-1 cur
Free_SSL(L , j); // i ， i j
return OK;
}
// Free_SSL 。
void Free_SSL(StaticLinkList L , int i )- {
- L[i].cur = space[0].cur ; // L[i] cur
space[0].cur = i ; // i - }
：
：
， ， ，
：
- （ ）
-
：
：
： L， L / 2
：
*search, *mid ， *search *mid 2 。 *search ，*mid 。
Status GetMidNode(LinkList L, ElemType *e){ LinkList search, mid; mid = search = L;
while(search -> next != NULL) { if(search -> next -> next != NULL) { search = search -> next -> next; mid = mid -> next; } else { search = search -> next; } }
*e = mid -> data; return OK;}
：
head == head -> next
#include #include
/* */typedef struct CLinkList { int data ; struct CLinkList * next ;}node;
int main(){ node * pHead = NULL ; char opp; int find;
printf("
1.
2.
3.
4.
5.
0.
：
"); while(opp != '0'){ scanf("%c",&opp); switch(opp){ case '1': ds_init(&pHead); printf("
"); ds_traverse(pHead) ; break;
case '2': printf(" ？"); scanf("%d", &find); ds_insert(&pHead,find) ; printf(" %d ：
", find) ; ds_traverse(pHead) ; printf("
"); break;
case '3': printf(" ？"); scanf("%d", &find); ds_delete(&pHead,find) ; printf(" %d :
", find) ; ds_traverse(pHead) ; printf("
"); break;
case '4': printf(" ？"); scanf("%d", &find); printf(" %d ：%d
", find, ds_search(pHead,find)) ; //ListTraverse(L); printf("
"); break;
case '5': ds_traverse(pHead) ; printf("
"); break;
case '0': exit(0); } }
return 0 ;}
/************************************************************************//* *//************************************************************************/
/* */void ds_init(node **pNode) { int item ; node *temp ; node *target ;
printf(" ， 0
"); while(1) { scanf("%d",&item) ; fflush(stdin) ; if(item == 0) return ;
if((*pNode) == NULL) { /* */ *pNode = (node*)malloc(sizeof(struct CLinkList)) ; if(!(*pNode)) exit(0) ; (*pNode)->data = item ; (*pNode)->next = *pNode ; } else { /* next */ for(target = (*pNode) ; target->next != (*pNode) ; target = target->next) ;
/* */ temp = (node *) malloc(sizeof(struct CLinkList)) ; if(!temp) exit(0) ; temp->data = item ; temp->next = *pNode ; target->next = temp ; } }}
/* *//* ： ， */void ds_insert(node ** pNode ,int i) { node * temp ; node * target ; node * p ; int item ; int j = 1 ;
printf(" :"); scanf("%d",&item) ;
if(i == 1) { // temp = (node *)malloc(sizeof(struct CLinkList)) ; if(!temp) exit(0) ; temp ->data = item ;
/* */ for(target = (*pNode) ; target->next != (*pNode) ; target = target->next) ; temp->next = (*pNode) ; target->next = temp ; *pNode = temp ; } else { target = *pNode ; for( ; j < (i-1) ; target=target->next,++ j) ; temp = (node *)malloc(sizeof(struct CLinkList)) ; if(!temp) exit(0) ; temp ->data = item ; p = target->next ; target->next = temp ; temp->next = p ; }}
/* */void ds_delete(node ** pNode,int i) { node * target ; node * temp ; int j = 1 ;
if(i == 1) { // /* */ for(target = *pNode ; target->next != *pNode ;target = target->next) ; temp = *pNode ; *pNode = (*pNode)->next ; target->next = *pNode ; free(temp) ; } else { target = *pNode ; for( ; j < i-1 ; target= target->next,++j) ; temp = target->next ; target->next = temp->next ; free(temp) ; }}
/* */int ds_search(node * pNode,int elem) { node * target ; int i = 1 ;
for(target = pNode ; target->data != elem && target->next != pNode ; ++i , target = target->next) ; if(target->next == pNode) /* */ return 0 ; else return i ;}/* */void ds_traverse(node * pNode) { node * temp ; temp = pNode ; printf("*********** ******************
"); do { printf("%4d ",temp->data) ; }while((temp = temp->next) != pNode) ; printf("
") ;}
：
（1）
（2）
（3） ，
typedef struct _DOUBLE_LINK_NODE { int data; struct _DOUBLE_LINK_NODE* prev; struct _DOUBLE_LINK_NODE* next; }DOUBLE_LINK_NODE;
DOUBLE_LINK_NODE* create_double_link_node(int value) { DOUBLE_LINK_NODE* pDLinkNode = NULL; pDLinkNode = (DOUBLE_LINK_NODE*)malloc(sizeof(DOUBLE_LINK_NODE)); assert(NULL != pDLinkNode); memset(pDLinkNode, 0, sizeof(DOUBLE_LINK_NODE)); pDLinkNode->data = value; return pDLinkNode; }
void delete_all_double_link_node(DOUBLE_LINK_NODE** pDLinkNode) { DOUBLE_LINK_NODE* pNode; if(NULL == *pDLinkNode) return ; pNode = *pDLinkNode; *pDLinkNode = pNode->next; free(pNode); delete_all_double_link_node(pDLinkNode); }
DOUBLE_LINK_NODE* find_data_in_double_link(const DOUBLE_LINK_NODE* pDLinkNode, int data) { DOUBLE_LINK_NODE* pNode = NULL; if(NULL == pDLinkNode) return NULL; pNode = (DOUBLE_LINK_NODE*)pDLinkNode; while(NULL != pNode){ if(data == pNode->data) return pNode; pNode = pNode ->next; } return NULL; }
STATUS insert_data_into_double_link(DOUBLE_LINK_NODE** ppDLinkNode, int data) { DOUBLE_LINK_NODE* pNode; DOUBLE_LINK_NODE* pIndex; if(NULL == ppDLinkNode) return FALSE; if(NULL == *ppDLinkNode){ pNode = create_double_link_node(data); assert(NULL != pNode); *ppDLinkNode = pNode; (*ppDLinkNode)->prev = (*ppDLinkNode)->next = NULL; return TRUE; } if(NULL != find_data_in_double_link(*ppDLinkNode, data)) return FALSE; pNode = create_double_link_node(data); assert(NULL != pNode); pIndex = *ppDLinkNode; while(NULL != pIndex->next) pIndex = pIndex->next; pNode->prev = pIndex; pNode->next = pIndex->next; pIndex->next = pNode; return TRUE; }
STATUS delete_data_from_double_link(DOUBLE_LINK_NODE** ppDLinkNode, int data) { DOUBLE_LINK_NODE* pNode; if(NULL == ppDLinkNode || NULL == *ppDLinkNode) return FALSE; pNode = find_data_in_double_link(*ppDLinkNode, data); if(NULL == pNode) return FALSE; if(pNode == *ppDLinkNode){ if(NULL == (*ppDLinkNode)->next){ *ppDLinkNode = NULL; }else{ *ppDLinkNode = pNode->next; (*ppDLinkNode)->prev = NULL; } }else{ if(pNode->next) pNode->next->prev = pNode->prev; pNode->prev->next = pNode->next; } free(pNode); return TRUE; }
int count_number_in_double_link(const DOUBLE_LINK_NODE* pDLinkNode) { int count = 0; DOUBLE_LINK_NODE* pNode = (DOUBLE_LINK_NODE*)pDLinkNode; while(NULL != pNode){ count ++; pNode = pNode->next; } return count; }
void print_double_link_node(const DOUBLE_LINK_NODE* pDLinkNode) { DOUBLE_LINK_NODE* pNode = (DOUBLE_LINK_NODE*)pDLinkNode; while(NULL != pNode){ printf("%d
", pNode->data); pNode = pNode ->next; } }
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
