단일 체인 표 의 C 언어 실현

학습 데이터 구조 에서 순서 표 에 이 어 접촉 하 는 것 이 바로 단일 체인 표 입 니 다. 그러면 단일 체인 표 는 무엇 입 니까?1. 단일 체인 시계 란 무엇 인가?단일 체인 테이블 은 체인 액세스 의 데이터 구조 로 주소 가 임의의 저장 장치 로 선형 테이블 의 데이터 요 소 를 저장 합 니 다.
2. 구조?링크 의 데 이 터 는 노드 로 표 시 됩 니 다. 모든 노드 의 구성: 요소 (데이터 요소 의 이미지) + 포인터 (후계 요소 의 저장 위 치 를 표시 합 니 다) 요 소 는 데 이 터 를 저장 하 는 저장 장치 이 고 지침 은 모든 노드 를 연결 하 는 주소 데이터 입 니 다.'결점 의 서열' 로 선형 표를 나타 내 는 것 을 선형 링크 (단일 링크) 라 고 한다.단일 체인 테이블 은 체인 액세스 의 구조 로 i 번 째 데이터 요 소 를 찾기 위해 서 는 i - 1 번 째 데이터 요 소 를 먼저 찾 아야 합 니 다.
단일 체인 표 의 특징 을 분명하게 말 한 후에 우 리 는 단일 체인 표 의 기능 을 실현 하기 시작 했다.가장 기본 적 인 기능 은 증가, 삭제, 찾기 등 을 실현 하 는 것 이다. 선형 특징 때문에 증가 할 때 머리 삽입, 꼬리 삽입 이 존재 하고 삭제 도 마찬가지 이다.

SListNode.h

#define _CRT_SECURE_NO_WARNINGS 1

#include
#include
#include

typedef int DataType;

typedef struct SListNode
{
    DataType data;
    struct SListNode* next;
}SListNode;

void InitSList(SListNode*& pHead);   //   
SListNode* BuyNode(DataType data);   //    
void Print(SListNode*& pHead);   //  
void Destory(SListNode*& pHead);   //  

void PushBack(SListNode*& pHead, DataType data);   //  
void PopBack(SListNode*& pHead);    //  

void PushFront(SListNode*& pHead, DataType data);   //  
void PopFront(SListNode*& pHead);    //  

void Insert(SListNode*& pos,DataType data);//           
void Erase(SListNode*& pHead,SListNode* pos);//         
void Remove(SListNode*& pHead,DataType data); //           
SListNode* Find(SListNode*& pHead,DataType data); //           

SListNode.c

#include"SListNode.h"

void InitSList(SListNode*& pHead)   //   
{
    pHead = NULL;
}

SListNode* BuyNode(DataType data)   //    
{
    SListNode* node = (SListNode*)malloc(sizeof(SListNode));
    assert(node);
    node->data = data;
    node->next = NULL;
    return node;
}

void Print(SListNode*& pHead)   //  
{
    SListNode* cur = pHead;
    if (cur == NULL)
        printf("null
");
    while (cur)
    {
        printf("%d  ", cur->data);
        cur = cur->next;
    }
    printf("
");
}

void PushBack(SListNode*& pHead, DataType data)   //  
{
    if (pHead == NULL)
        pHead = BuyNode(data);
    else
    {
        SListNode* cur = pHead;
        while (cur->next)
        {
            cur = cur->next;
        }
        cur->next = BuyNode(data);
    }
}

void PopBack(SListNode*& pHead)   //  
{
    assert(pHead);
    if (pHead->next == NULL)
    {
        free(pHead);
        pHead = NULL;
    }

    else
    {
        SListNode* cur = pHead;
        SListNode* pcur = cur;
        while(cur->next)
        {
            pcur = cur;
            cur = cur->next;
        }
        free(cur);
        cur = NULL;
        pcur->next = NULL;
    }


}

void PushFront(SListNode*& pHead, DataType data)   //  
{
    if (pHead == NULL)
        pHead=BuyNode(data);
    else
    {
        SListNode* newHead = BuyNode(data);
        newHead->next = pHead;
        pHead = newHead;
    }
}

void PopFront(SListNode*& pHead)    //  
{
    if (pHead == NULL)   //pHead  
        return;
    else if (pHead->next == NULL)    //pHead->next  
    {
        free(pHead);
        pHead = NULL;
    }
    else     //     
    {
        SListNode* cur = pHead;
        pHead = pHead->next;
        free(cur);
    }
}

void Insert(SListNode*& pos, DataType data)   //           
{
    if (NULL == pos)
        return;
    SListNode* newNode = BuyNode(data);
    newNode->next = pos->next;
    pos->next = newNode;
}

void Erase(SListNode*& pHead, SListNode* pos) //         
{
    assert(pHead&&pos);
    if (pos == pHead)
    {
        SListNode* tmp = pHead;
        pHead = pHead->next;
        free(tmp);
        tmp = NULL;
    }
    else
    {
        SListNode* cur = pHead;
        while (cur->next != pos)
        {
            cur = cur->next;
        }
        cur->next = pos->next;
        free(pos);
        pos = NULL;
    }
}

void Remove(SListNode*& pHead, DataType data)  //           
{
    assert(pHead);
    SListNode* pos = Find(pHead, data);
    if (pos == pHead)
    {
        SListNode* tmp = pHead;
        pHead = pHead->next;
        free(tmp);
        tmp = NULL;
    }

    else
    {
        SListNode* cur = pHead;
        while (cur->next!=pos)
        {
            cur = cur->next;
        }
        cur->next = pos->next;
        free(pos);
        pos = NULL;
    }

}

SListNode* Find(SListNode*& pHead, DataType data) //           
{
    SListNode* cur = pHead;
    assert(pHead);
    while(cur)
    {
        if(cur->data == data)
            return cur;
        cur = cur->next;
    }
    return NULL;
}

void Destory(SListNode*& pHead)   //  
{
    assert(pHead);
    free(pHead);
    pHead = NULL;
}

    
#include"SListNode.h"

void Test1()   //    
{
    SListNode* Slistnode;
    InitSList(Slistnode);
    PushBack(Slistnode, 1);
    PushBack(Slistnode, 2); 
    PushBack(Slistnode, 3);
    PushBack(Slistnode, 4);
    PushBack(Slistnode, 5);
    Print(Slistnode);

    PopBack(Slistnode);
    PopBack(Slistnode);
    PopBack(Slistnode);
    PopBack(Slistnode);
    Print(Slistnode);
}

void Test2()   //    
{
    SListNode* Slistnode;
    InitSList(Slistnode);
    PushFront(Slistnode, 1);
    PushFront(Slistnode, 2);
    PushFront(Slistnode, 3);
    PushFront(Slistnode, 4);
    PushFront(Slistnode, 5);
    Print(Slistnode);

    PopFront(Slistnode);
    PopFront(Slistnode);
    PopFront(Slistnode);
    PopFront(Slistnode);
    Print(Slistnode);
}

void Test3()   //         
{
    SListNode* Slistnode;
    InitSList(Slistnode);
    PushFront(Slistnode, 1);
    PushFront(Slistnode, 2);
    PushFront(Slistnode, 3);
    PushFront(Slistnode, 4);
    PushFront(Slistnode, 5);
    Print(Slistnode);

    SListNode* pos1 = Find(Slistnode, 3);
    Insert(pos1, 7);
    Print(Slistnode);

    SListNode* pos2 = Find(Slistnode, 4);
    Erase(Slistnode, pos2);
    Print(Slistnode);

    Remove(Slistnode, 1);
    Print(Slistnode);

    Destory(Slistnode);
    Print(Slistnode);
}

int main()
{
    Test1();
    Test2();
    Test3();
    system("pause");
}

요약: 전체 코드 부분 은 위 와 같 습 니 다. 여기 서 몇 가 지 를 주의해 야 합 니 다. 1. 링크 를 삽입 하고 삭제 할 때 발생 할 수 있 는 상황 을 분석 해 야 합 니 다. 예 를 들 어 머리 를 꽂 을 때 세 가지 상황 이 있 을 수 있 고 링크 가 비어 있 을 때.링크 가 가리 키 는 다음 이 비어 있 을 때;정상 적 인 플러그.상황 을 분명하게 분석 해야만 너 는 논리 에 따라 코드 를 쓸 수 있다.
2. 링크 를 실현 할 때 코드 가 많 지 않 지만 많은 세부 사항 은 우리 가 주의해 야 한다.이 단언 은 assert, 필요 없 는 부분 으로 판단 하면 된다.
3. 비교적 많은 기능 을 테스트 할 때 단계별 로 모듈 을 나 누 어 테스트 할 수 있 고 문제 가 있 으 면 디 버 깅 하기 좋다.