[C 언어] 단일 체인 표 의 실현
23472 단어 [C 언어] 기초
단일 체인 테이블 은 체인 액세스 의 데이터 구조 로 주소 가 임의의 저장 장치 로 선형 테이블 의 데이터 요 소 를 저장 합 니 다.
단일 체인 표 구 조 는 다음 과 같다.
typedef int DataType;
typedef struct Node
{
struct Node* next; //
DataType data; //
}Node,*pLinkNode;
주의:
Node* plist; pLinkNode pplist;
① PLinkNode 와 Node 는 서로 다른 이름 의 같은 포인터 유형 (이름 이 다 르 면 개념 적 으로 명확 하 게 하기 위해 서) ② * PLinkNode 유형의 포인터 변수 pplist 는 단일 링크 의 헤드 포인터 ③ Node 유형의 포인터 변수 plist 는 특정한 노드 를 가리 키 는 포인터 임 을 나타 낸다.
단일 체인 표 의 일부 기본 조작 은 다음 과 같다.
void InitList(pLinkNode* pplist)
{
assert(pplist);
*pplist = 0; //
}
void PrintList(pLinkNode pplist)
{
assert(pplist);
pLinkNode begin = pplist;
printf("List->");
while (begin)
{
printf("%d->", begin->data);
begin = begin->next;
}
printf("NULL
");
}
pLinkNode GreateNode(DataType data)
{
pLinkNode newplist = (pLinkNode)malloc(sizeof(Node));
newplist->data = data;
newplist->next = NULL;
return newplist;
}
void PushBack(pLinkNode* pplist, DataType data)
{
assert(pplist);
if (*pplist == NULL)
{
*pplist = GreateNode(data);
}
else
{
pLinkNode end = *pplist;
while (end->next != NULL)
{
end = end->next;
}
end->next = GreateNode(data);
}
}
void PopBack(pLinkNode* pplist)
{
assert(pplist);
if (*pplist == NULL)
{
perror("error:");
return;
}
else
{
pLinkNode prev, end;
prev = *pplist;
end = *pplist;
while (end->next != NULL)
{
prev = end;
end = end->next;
}
if (end == (*pplist))
{
*pplist = NULL;
}
else
{
prev->next = NULL;
}
free(end);
}
}
void PushFront(pLinkNode* pplist, DataType data)
{
assert(pplist);
if (*pplist == NULL)
{
*pplist = GreateNode(data);
}
else
{
pLinkNode ret = GreateNode(data);
ret->next = *pplist;
*pplist = ret;
}
}
void PopFront(pLinkNode* pplist)
{
assert(pplist);
if (*pplist == NULL)
{
perror("error:");
return;
}
else
{
pLinkNode begin = *pplist;
if ((*pplist)->next == NULL)
{
*pplist = NULL;
}
else
{
*pplist = (*pplist)->next;
}
free(begin);
}
}
void GetListLength(pLinkNode plist)
{
assert(plist);
int count = 0;
pLinkNode begin = plist;
while (begin)
{
count++;
begin = begin->next;
}
printf("ListLength Is %d
", count);
}
pLinkNode Find(pLinkNode plist, DataType data)
{
assert(plist);
pLinkNode begin = plist;
while (begin)
{
if (begin->data == data)
{
return begin;
}
begin = begin->next;
}
return NULL;
}
void Insert(pLinkNode* pplist, pLinkNode n,DataType data)//n Find
{ // n
assert(pplist);
if (*pplist == NULL || n == NULL)
{
perror("error:");
return;
}
pLinkNode ret = GreateNode(data);
ret->next = n->next;
n->next = ret;
}
void Remove(pLinkNode* pplist, pLinkNode n)// n
{
assert(pplist);
if (*pplist == NULL || n == NULL)
{
perror("error:");
return;
}
if (n == *pplist)
{
*pplist = (*pplist)->next; //
free(n);
return;
}
pLinkNode prev, ret;
prev = *pplist;
ret = *pplist;
while (ret->next != NULL)
{
prev = ret;
ret = ret->next;
if (ret == n)
{
prev->next = ret->next;
free(n);
return;
}
}
}
void Erase(pLinkNode* pplist, DataType data, int flag)
{
assert(pplist);
if (*pplist == NULL)
{
perror("error:");
return;
}
pLinkNode ret;
do
{
ret = Find(*pplist, data);
if (ret != NULL)
{
Remove(pplist, ret);
}
} while (flag != 0 && ret);
}흔히 볼 수 있 는 단일 체인 표면 시험 문 제 는 다음 과 같다.
void PrintBack(pLinkNode plist) //
{
assert(plist);
if (plist->next != NULL)
{
PrintBack(plist->next); //
}
printf("%d->", plist->data);
}
void Del_MidNode(pLinkNode n) // a
{
if (n == NULL)
{
printf("Invaid n
");
return;
}
pLinkNode ret = n->next;
n->data = ret->data;
n->next = ret->next;
free(ret);
}
void PushNode(pLinkNode n, DataType data)//
{
if (n == NULL)
{
printf("Invaid n
");
return;
}
pLinkNode ret = GreateNode(n->data);
pLinkNode tmp = n->next;
n->data = data;
ret->next = tmp;
n->next = ret;
}
void JosephCycle(pLinkNode plist, int Cycle) //
{
assert(plist);
pLinkNode begin = plist;
int k = Cycle;
while (begin->next != begin)
{
int count = 1;
while (count++ != k)
{
begin = begin->next;
}
printf("del :%d->",begin->data);
pLinkNode del = begin->next;
begin->data = del->data;
begin->next = del->next;
}
}
void Reverse(pLinkNode* pplist) // （ ）
{
assert(pplist);
if (*pplist == NULL)
{
perror("error:");
return;
}
pLinkNode begin = (*pplist)->next;
(*pplist)->next = NULL;
while (begin)
{
pLinkNode ret = begin;
begin = begin->next;
ret->next = *pplist;
*pplist = ret;
}
}
void BubbSort(pLinkNode* pplist) //
{
assert(pplist);
if (*pplist == NULL || (*pplist)->next == NULL)
{
return;
}
pLinkNode prev, tmp, end;
end = NULL;
while (end != *pplist)
{
prev = *pplist; //
tmp = (*pplist)->next;
while (tmp != end)
{
if (prev->data > tmp->data)
{
int ret = prev->data;
prev->data = tmp->data;
tmp->data = ret;
}
prev = prev->next;
tmp = tmp->next;
}
end = prev;
}
}
pLinkNode Merge(pLinkNode plist1, pLinkNode plist2)// ，
{
if (plist1 == NULL)
{
return plist2;
}
if (plist2 == NULL)
{
return plist1;
}
if (plist1 == plist2)
{
return plist1;
}
pLinkNode plist,end;
if (plist1->data < plist2->data)
{
plist = plist1;
plist1 = plist1->next;
}
else
{
plist = plist2;
plist2 = plist2->next;
}
end = plist;
while (plist1 && plist2)
{
pLinkNode tmp;
if (plist1->data < plist2->data)
{
tmp = plist1;
plist1 = plist1->next;
}
else
{
tmp = plist2;
plist2 = plist2->next;
}
end->next = tmp;
end = tmp;
}
if (plist1)
{
end->next = plist1;
}
else if (plist2)
{
end->next = plist2;
}
return plist;
}
pLinkNode FindMidNode(pLinkNode plist)// ， 。
{
assert(plist);
pLinkNode slow, fast;
int flag = 0;
slow = plist;
fast = plist;
while (fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
flag = 1;
if (fast == NULL) //
{
return slow;
}
}
if (flag) //
{
return slow;
}
return NULL;
}요약:
단일 체인 표 장점:
단일 체인 테이블 에 하나의 노드 를 삽입 하거나 삭제 하 는 것 은 상대 적 으로 선형 테이블 이 비교적 효율 적 이다. 즉, 체인 테이블 에 있 는 i - 1 의 결점 을 찾 은 다음 에 그 가 가리 키 는 후계 지침 을 수정 하면 대량의 데 이 터 를 이동 할 필요 가 없다.
단일 체인 표 단점:
단일 체인 표 는 체인 액세스 의 구조 로 i 번 째 데이터 요 소 를 찾기 위해 서 는 먼저 i - 1 번 째 데이터 요 소 를 찾 아야 합 니 다. 즉, 무 작위 접근 이 지원 되 지 않 습 니 다.
좋은 웹페이지 즐겨찾기
