순서 표 와 링크
순서 표
1. 배열 크기 를 직접 주 는 경우
typedef int DataType;
typedef struct SeqList
{
Datatype array[MAXSIZE];
size_t size;
}SeqList
2. 용량 을 늘 려 야 한다
typedef int Datatype;
typedef struct SeqList_D
{
Datatype *array; //
size_t size; //
Datatype capacity; //
}SeqList_D;
분석:
1). 두 가지 상황, 두 번 째 상황 은 첫 번 째 상황 보다 현저히 우수 하고 메모리 낭비 상황 이 존재 하지 않 습 니 다.컴퓨터 사용 가능 한 메모리 중 두 번 째 는 상한 없 이 확장 할 수 있 으 며, 첫 번 째 는 MAXSIZE 의 제한 을 받는다.
2). 두 가지 상황 의 초기 화 에 차이 가 있 습 니 다.배열 크기 에 유효 데 이 터 를 0 으로 직접 설정 하면 됩 니 다. 데 이 터 를 삽입 할 때마다 유효 데이터 와 배열 크기 만 판단 해 야 합 니 다.용량 을 늘 리 려 면 동적 으로 메모 리 를 열 어야 하고 데 이 터 를 삽입 할 때 유효한 데이터 와 용량 의 크기 를 판단 해 야 한다.
3). 삭제 와 검 사 를 막론하고 정 의 된 구조의 변수의 주 소 를 조작 함수 에 전달 해 야 한다.
단 방향 링크
typedef int DataType;
typedef struct ListNode
{
DataType data; //
struct ListNode* next; //
}ListNode;
분석: 단 방향 링크 는 링크 가 비어 있 고 하나의 노드 와 여러 개의 노드 만 있 는 상황 에 주의해 야 한다.
1). 단 방향 링크 는 초기 화 할 필요 가 없 이 삽입 작업 을 하면 됩 니 다.
2). 삭제 와 검 사 를 하 는 작업 에서 주 소 를 입 는 작업 을 통 해 이 루어 집 니 다. 함수 의 형 삼 에 서 는 2 급 포인터 로 받 을 수 있 고 c + 에서 인용 한 개념 도 사용 할 수 있 습 니 다.
3). 함 수 를 쓸 때 주의해 야 할 것 은 더 이상 말 하지 않 고 원래 의 블 로그 에 있 습 니 다.
4). 테스트 용례 가 중요 하 다.
5). 자신의 작은 프로그램 을 보 여 줍 니 다.
헤더 파일
#ifndef __LinkedList_12_31_H__
#define __LinkedList_12_31_H__
#include
#include
typedef int Datatype;
typedef struct ListNode
{
Datatype data;
struct ListNode *next;
}ListNode;
// , ,
ListNode* _BuyNode(Datatype x);
void print(ListNode *pHead);
//void Pushback(ListNode **pHead,Datatype x);
void Pushback(ListNode*& pHead,Datatype x);
void Popback(ListNode*& pHead);
void pushFront(ListNode*& pHead,Datatype x);
void PopFront(ListNode*& pHead);
ListNode* Find(ListNode* phead, Datatype x);
void Insert(ListNode* pos, Datatype x);
void Erase(ListNode*pHead, ListNode* pos);
#endif //__LinkedList_12_31_H__
실현 함수
#include
#include"LinkedList_12_31.h"
ListNode* _BuyNode(Datatype x)
{
ListNode *tmp = (ListNode*)malloc(sizeof(ListNode));
if (tmp != NULL)
{
tmp->data = x;
tmp->next = NULL;
}
return tmp;
}
//
//void Pushback(ListNode **pHead, Datatype x)
//{
// assert(pHead);
// if (*pHead == NULL)
// {
// *pHead = _BuyNode(x);
// }
// else
// {
// ListNode* tail = *pHead;
// while (tail->next != NULL)
// {
// tail = tail->next;
// }
// tail->next = _BuyNode(x);
// }
//}
void Pushback(ListNode*& pHead, Datatype x)
{
if (pHead == NULL)
{
pHead = _BuyNode(x);
}
else
{
ListNode*tail = pHead;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = _BuyNode(x);
}
}
void Popback(ListNode*& pHead)
{
if (pHead == NULL)
{
printf("empty
");
return;
}
else if (pHead->next == NULL)
{
free(pHead);
pHead = NULL;
}
else
{
ListNode* tail = pHead;
ListNode* cur = NULL;
while (tail->next)
{
cur = tail;
tail = tail->next;
}
free(tail);
cur->next = NULL;
}
}
void pushFront(ListNode*& pHead, Datatype x)
{
if (pHead == NULL)
{
pHead = _BuyNode(x);
}
else
{
ListNode*tmp = _BuyNode(x);
tmp->next = pHead;
pHead = tmp;
}
}
void PopFront(ListNode*& pHead)
{
if (pHead == NULL)
{
printf("empty LinkedList
");
return;
}
else if (pHead->next == NULL)
{
free(pHead);
pHead = NULL;
}
else
{
ListNode* tmp = pHead;
pHead = pHead->next;
free(tmp);
}
}
ListNode* Find(ListNode* pHead, Datatype x)
{
assert(pHead);//
ListNode* tail = pHead;
while (tail->next)//
{
if (tail->data == x)
{
return tail;
}
tail = tail->next;
}
if (tail->next == NULL)//
{
return tail;
}
return NULL;
}
void Insert(ListNode* pos, Datatype x)
{
assert(pos);
ListNode*tmp = _BuyNode(x);
ListNode*cur = pos->next;
pos->next = tmp;
tmp->next = cur;
}
void Erase(ListNode*pHead, ListNode* pos)
{
assert(pos);
if (pos->next == NULL)
{
free(pos);
//
}
else
{
ListNode*cur = NULL;
ListNode*tail = pos;
while (pHead->data != tail->data)
{
cur = pHead;
pHead = pHead->next;
}
ListNode*tmp = pos->next;
cur->next = tmp;
free(pos);
}
}
void print(ListNode *pHead)
{
//assert(pHead);
ListNode* cur = pHead;
while (cur) // while(cur->next);
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL
");
}
테스트 용례
#include
#include"LinkedList_12_31.h"
//
//void Test1()
//{
// ListNode* list = NULL;
// Pushback(&list,1);
// Pushback(&list, 2);
// Pushback(&list, 3);
// Pushback(&list, 4);
// print(list);
//}
//Pushback()/Popback()
void Test2()
{
ListNode* list = NULL;
Pushback(list, 1);
Pushback(list, 2);
Pushback(list, 3);
Pushback(list, 4);
Pushback(list, 5);
print(list);
Popback(list);
Popback(list);
Popback(list);
Popback(list);
Popback(list);
Popback(list);
print(list);
}
void Test3()
{
ListNode* list = NULL;
pushFront(list, 5);
pushFront(list, 4);
pushFront(list, 3);
pushFront(list, 2);
pushFront(list, 1);
print(list);
PopFront(list);
PopFront(list);
PopFront(list);
PopFront(list);
PopFront(list);
PopFront(list);
print(list);
}
void Test4()
{
ListNode* list = NULL;
pushFront(list, 5);
pushFront(list, 4);
pushFront(list, 3);
pushFront(list, 2);
pushFront(list, 1);
print(list);
//ListNode*tmp = Find(list, 2);
//ListNode*tmp = Find(NULL, 2);
ListNode*tmp = Find(list, 5);
printf("%d->", tmp->data);
}
void Test5()
{
ListNode* list = NULL;
pushFront(list, 5);
pushFront(list, 4);
pushFront(list, 3);
pushFront(list, 2);
pushFront(list, 1);
print(list);
ListNode*tmp = Find(list, 2);
Insert(tmp, 2);
print(list);
}
void Test6()
{
ListNode* list = NULL;
pushFront(list, 5);
pushFront(list, 4);
pushFront(list, 3);
pushFront(list, 2);
pushFront(list, 1);
print(list);
ListNode*tmp = Find(list, 2);
Insert(tmp, 2);
print(list);
Erase(list, tmp);
print(list);
}
int main()
{
Test6();
system("pause");
return 0;
}
이상 은 바로 본인 이 학습 과정 에서 의 경험 총화 입 니 다.물론 본인 의 능력 에 한계 가 있어 실수 가 있 을 수 있 으 니 지적 해 주시 기 바 랍 니 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
하나의 단일 체인 테이블의 순환과 귀속 실현을 반전시키다텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.