[데이터 구조 와 알고리즘 분석] 단일 체인 표 기본 작업 의 실현

요 며칠 동안 Weiss 책의 Ch. 3 을 뜯 고 있 었 습 니 다. 책 에 있 는 싱글 체인 시트 의 기본 적 인 조작 코드 를 한 번 쳤 습 니 다. 그리고 자신 이 쓴 것 (주석 과 함수 몇 개) 을 보충 하 였 습 니 다. 테스트 를 통 해 문제 가 없 을 것 입 니 다.
이번 에는 이른바 '구 글 스타일' 로 코드 를 쓰 려 고 했 는데, 4 칸 들 어 가 는 윈도 스타일 에 익숙해 져 서 2 칸 들 어 가 는 것 이 익숙 하지 않 았 다.원래 Google Style 에서 변 수 는 모두 소문 자 일 것 입 니 다. 그러나 저 는 소문 자의 L 과 P 를 정말 좋아 하지 않 습 니 다. 변 수 는 이름 을 바 꾸 어도 자신의 습관 인 알파벳 변수 대문자, 다 중 알파벳 소문 자 를 고수 합 니 다.
주의해 야 할 부분:
1, 몇몇 함수 에 while (P! = NULL & & & P - > Element! = X) 와 같은 코드 가 나 타 났 습 니 다. 논리 연산 자의 단락 규칙 에 따라 P! =NULL (링크 끝 점) 은 뒤의 불 표현 식 을 다시 검사 하지 않 습 니 다.
2, 원서 사용  Position tmp = malloc (sizeof (struct Node)) 와 같은 코드 는 Google Style 의 제안 에 따라 'malloc (sizeof (tmp)' 로 변경 하면 동기 화 에 유리 합 니 다 (tmp 의 데이터 형식 이 변 경 될 수 있 음 을 감안 하여).
　　Code is here~
. h 헤더 파일:

#ifndef LINKLIST_H_INCLUDED
#define LINKLIST_H_INCLUDED

struct Node;
typedef struct Node *PtrToNode;
//  List and Position are pointers
typedef PtrToNode List;
typedef PtrToNode Position;

#define ElementType int//set the type of element as Integer

//  Functions:
List MakeEmpty(List L);
List InitialList();
int IsEmpty(List L);
int IsLast(Position P, List L);
Position Find(ElementType X, List L);
void Delete(ElementType X, List L);
Position FindPrevious(ElementType X, List L);
void Insert(ElementType X, List L, Position P);
void DeleteList(List L);
Position Header(List L);
Position First(List L);
Position Last(List L);
Position Advance(Position P);//not implemented yet
ElementType Retrive(Position P);//not implemented yet
void PrintElement(Position P);
void PrintList(List L);
int SizeOfList(List L);
int FindIndex(ElementType X, List L);
int InsertAsTail(ElementType X, List L);
int InsertAsHead(ElementType X, List L);

#endif // LINKLIST_H_INCLUDED

　　
. c 파일:

#include "LinkList.h"
#include<stdio.h>
#include<stdlib.h>

struct Node {
  ElementType Element;
  Position Next;
};

List MakeEmpty(List L) {
  //used for initialization
  Position P = Header(L);
  P->Next = NULL;
  P->Element = 0;
}
List InitialList() {//return a new List (header)

  List tmp;
  tmp = malloc(sizeof(tmp));//standard malloc way for "tmp"
  tmp->Next = NULL;
  //  tmp = MakeEmpty(tmp);
  return tmp;
}
int IsEmpty(List L) {//Return true if L is empty
  return L->Next == NULL;
}
int IsLast(Position P, List L) {//Return true if P is the last position of the list L
  return P->Next == NULL;
}
Position Header(List L) {
  Position P = L;
}
Position First(List L) {
  Position P = L->Next;
}
Position Last(List L) {
  Position P = Header(L);
  while (!IsLast(P,L)) {
    P = P->Next;
  }
  return P;
}
Position Find(ElementType X, List L) {
//  Return Position of X in L;NULL if not found;
  Position P = L->Next;
  while (P != NULL && P->Element != X)
    //  You should first know if P is NULL, here we use shortcut "&&"
    P = P->Next;
  return P;
}
int FindIndex(ElementType X, List L) {
  //Return Index of X in L;-1 if not found;Index starts from 1(not 0).
  int index = 1;
  Position P = L->Next;
  while (P != NULL && P->Element != X) {
    //  You should first know if P is NULL, here we use shortcut "&&"
    P = P->Next;
    index++;
  }
  return index; //header node is not counted in index
}
void Delete(ElementType X, List L) {//Delete the first occurrence of X in List L
  Position P,tmp;
  P = FindPrevious(X,L);
  if (!IsLast(P,L)) {
    tmp = P->Next;  //Now "tmp" is just which node you want to "delete" here
    P->Next = tmp->Next;
    free(tmp);  //the data at address tmp is meaningless after free it
  }
}
Position FindPrevious(ElementType X, List L) {
  //If X is not found, then Next Field of Returned Position is NULL
  Position P = L;
  while(P->Next != NULL && P->Next->Element != X)
    P = P->Next;
  return P; //If X not found in this List, P is the last node, P->Next is NULL
}
void Insert(ElementType X, List L, Position P) {//Insert After Position P
  Position tmp = malloc(sizeof(tmp));
  if (tmp == NULL) {
    printf("Out of space!");  //  TODO(AllZY): Use a variable to indicate the state.
  } else {
    tmp->Element = X;
    tmp->Next = P->Next;
    P->Next = tmp;  //tmp should never be "NULL" when this line executed
  }
}
int InsertAsTail(ElementType X, List L) {
//  return index if inserted successfully, otherwise return -1
//  Insert it after the last ele.
  Position Tail = Last(L);
  Position tmp = malloc(sizeof(tmp));
  if (tmp == NULL) {
    return -1;
  } else {
    tmp->Element = X;
    tmp->Next = Tail->Next;
    Tail->Next = tmp;
  } //Is this what they called "google style"? I think it's a bit odd...
}
int InsertAsHead(ElementType X, List L) {
//  return index if inserted successfully, otherwise return -1
//  Insert it before the first ele.
  Position Head = Header(L);
  Position tmp = malloc(sizeof(tmp));
  if (tmp == NULL) {
    return -1;
  } else {
    tmp->Element = X;
    tmp->Next = Head->Next;
    Head->Next = tmp;
  }
}
void DeleteList(List L) {
  Position P,tmp;
  P = L->Next;
  L->Next = NULL;
  while (P != NULL) {
    tmp = P->Next;
    free(P);
    P = tmp;
  }
  /*
  //an unreliable version, not recommended
  while(P!=NULL)
  {
    free(P);
    P = P->Next;
  }
  */
}
void PrintElement(Position P) {//Print one Element
  ElementType e = P->Element;
  printf("%d ",e);
}
void PrintList(List L) {//Print all elements in the List
  Position P = First(L);
  while (P != NULL) {
    PrintElement(P);
    P = P->Next;
  }
}
int SizeOfList(List L) {
  int count = 0;
  Position P = First(L);
  while (P != NULL) {
    count++;
    P = P->Next;
  }
  return count;
}

int main()
{
//  List L = malloc(sizeof (List));
//  MakeEmpty(L);
  List L = InitialList();
  Position P = Header(L);
  int i;
  for (i = 1; i <= 10; i++) {
    InsertAsTail(i,L);
  }
  for ( ; i <= 20; i++) {
    InsertAsHead(i,L);
  }

  PrintList(L);
  printf("
Size of list is %d",SizeOfList(L));
  Position p10 = Find(10,L);
  printf("
The element in the Position of value \"10\" is %d
",p10->Element);
  printf("The index of Element 11 is %d
",FindIndex(11,L));

  DeleteList(L);
  return 0;
}

테스트 실행 결과:
　　
 
참고 자료:
《 데이터 구조 와 알고리즘 분석 》.
http://google.github.io/styleguide/cppguide.html
http://zh-google-styleguide.readthedocs.org/en/latest/google-cpp-styleguide/
———————————————————————————————————————————
오리지널 글, 전재 출처 를 밝 혀 주세요.http://www.cnblogs.com/allzy/