순서 표 와 링크

순서 표 와 링크 는 기본 적 인 데이터 구조 이자 가장 간단 하면 서도 중요 한 데이터 구조 이다.
    순서 표
    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;
    }

   이상 은 바로 본인 이 학습 과정 에서 의 경험 총화 입 니 다.물론 본인 의 능력 에 한계 가 있어 실수 가 있 을 수 있 으 니 지적 해 주시 기 바 랍 니 다.

좋은 웹페이지 즐겨찾기