'더블링크드리스트'에 해당되는 글 2건

  1. 2012.06.01 C++ - 더블 링크드리스트로 구현한 삽입, 버블정렬 (1)
  2. 2010.06.01 C - 알고리즘 - 더블링크드리스트(상)


지난번처럼 설명을 자세하게 적고 싶었는데.. 하다보니 코드가 너무 길어졌네요 ;ㅁ;


리스트를 이용하여 구현한 삽입정렬, 버블정렬입니다.


배열로 구현한 삽입정렬(http://topnanis.tistory.com/12)과 버블정렬(http://topnanis.tistory.com/11)은  링크를 참조하세요.


싱글로 할 걸 굳이 더블 링크로 구현 한 이유는.. 퀵정렬을 구현하려다.. 그만 두었기 때문이죠.. 막판에 넣은 스왑 디파인아까워..ㅠ

퀵정렬시에는 재귀 함수에 인자값으로 배열의 크기(+피봇), 시작지점이 필요하므로 더블링크드가 더 적합하겠다 싶었습니다(배열쪽이 훨씬 편리한 것 같아요)

 

아래에 소스 첨부하였습니다.  


sort.cpp






#include <iostream>

#include <Windows.h>


#define SWAP(x,y,t) (t=x), (x=y), (y=t)                 //스왑을 정의(못써먹음,아까워;ㅁ;)


using namespace std;


class Node         //노드를 정의

{

public:

int val;

Node *head;

Node *tail;

};


class Link         //더블리스트클래스

{

private:

bool BubbleOrderAscending();         //버블(오름)

bool BubbleOrderDescending();         //버블(내림)

void InsertOrderAscending();         //삽입(오름)

void InsertOrderDescending();         //삽입(내림)


void Col(int color);

void ShowAll();         //링크출력


public:

Node *lHead;         //링크전체의 헤더

Node *tempPoint;         //생성시 동적할당을 위한 노드


Link()         //초기화

{

lHead = new Node();

lHead->head=NULL;         //초기화 하지 않으면 값 넣을때 에러발생

lHead->tail=NULL;         //초기화 하지 않으면 검색시 에러발생

}


void AddLilk(int val)             //노드추가

{

cout<<"add"<<endl;

tempPoint= new Node();         //노드 생성시 동적할당


lHead->head=tempPoint;         //링크 헤더연결


tempPoint->val=val;         //링크 값

tempPoint->tail=lHead;         //링크 테일연결


lHead=tempPoint;         //주소저장


ShowAll();

}


void revShowAll()         //링크 역출력

{

cout<<endl<<"Show Reverse"<<endl;

Node *schPoint= lHead;


while(schPoint->tail->val!=NULL) schPoint=schPoint->tail;

while(schPoint->head!=NULL)

{

if(schPoint->val>=100)Col(15);         //값 크기에 따라 색상(10:녹, 14:황, 15:백)

else if(schPoint->val>=10)Col(14); else Col(10);

cout<<schPoint->val<<"->";

schPoint=schPoint->head;

}

cout<<schPoint->val<<"->";

Col(15);

cout<<endl;


}


void InsertUp() //삽입정렬(오름)스위치

{

cout<<endl<<"Ascending(Insert)"<<endl;

InsertOrderAscending();

}


void InsertDown() //삽입정렬(내림)스위치

{

cout<<endl<<"Decending(Insert)"<<endl;

InsertOrderDescending();

}


void BubbleUp() //버블정렬(오름)스위치

{

cout<<endl<<"Ascending(bubble)"<<endl;

while(BubbleOrderAscending());

}


void BubbleDown() //버블정렬(내림)스위치

{

cout<<endl<<"Decending(bubble)"<<endl;

while(BubbleOrderDescending());

}

};


void Link::InsertOrderAscending()

{

tempPoint=lHead; //기준포인트

tempPoint=tempPoint->tail;         //삽입정렬 초기- 두 수를 비교하기 위해 기준블럭을 한 칸 이동 


while(tempPoint->tail!=NULL)

{

ShowAll();

//노드를 이용한 for문 참조_ serchP는 시작지점에서 기준블럭전 까지 비교하기 위한 포인터

for(Node *serchP = lHead; serchP->val!=tempPoint->val; serchP=serchP->tail)

{

if(serchP->val>tempPoint->val)

{

int tempVal = serchP->val;

serchP->val = tempPoint->val;

tempPoint->val = tempVal;

}

}

tempPoint=tempPoint->tail;

}

ShowAll();

}


void Link::InsertOrderDescending()

{

tempPoint=lHead;

tempPoint=tempPoint->tail;


while(tempPoint->tail!=NULL)

{

ShowAll();


for(Node *serchP = lHead; serchP->val!=tempPoint->val; serchP=serchP->tail)

{

if(serchP->val<tempPoint->val)

{

int tempVal = serchP->val;

serchP->val = tempPoint->val;

tempPoint->val = tempVal;

}

}

tempPoint=tempPoint->tail;

}

ShowAll();

}


bool Link::BubbleOrderAscending()

{

ShowAll();


bool isContinue=false;

tempPoint= lHead;


while(tempPoint->tail->tail!=NULL)

{

if(tempPoint->val>tempPoint->tail->val)

{

isContinue=true;


int temp=tempPoint->val;

tempPoint->val=tempPoint->tail->val;

tempPoint->tail->val=temp;

}

tempPoint=tempPoint->tail;

}

return isContinue;

}

bool Link::BubbleOrderDescending()

{

bool isContinue=false;

tempPoint= lHead;


while(tempPoint->tail!=NULL)

{

if(tempPoint->val<tempPoint->tail->val)

{

isContinue=true;


int temp=tempPoint->val;

tempPoint->val=tempPoint->tail->val;

tempPoint->tail->val=temp;

}

tempPoint=tempPoint->tail;

}

ShowAll();

return isContinue;

}


void Link::ShowAll()

{

Node *schPoint= lHead;


while(schPoint->tail!=NULL)

{

if(schPoint->val>=100)Col(15);else if(schPoint->val>=10)Col(14); else Col(10);

cout<<schPoint->val<<"->";

schPoint=schPoint->tail;

}

Col(15);

cout<<endl;

}


void Link::Col(int color) 

{

int bgcolor=NULL;

color &= 0xf;

bgcolor &= 0xf;

SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), (bgcolor << 4) | color);

}


int main() //메인

{

Link *link = new Link();


link->AddLilk(86);

link->AddLilk(1);

link->AddLilk(13);

link->AddLilk(4);

link->AddLilk(11);

link->AddLilk(226);

link->AddLilk(104);


link->BubbleUp();

link->BubbleDown();


link->revShowAll();


link->InsertUp();

link->InsertDown();


return 0;

}




신고
Creative Commons License
Creative Commons License
Posted by 준환이형님

댓글을 달아 주세요

  1. c++ 삽입 2014.04.14 19:07 신고 Address Modify/Delete Reply

    c++ 삽입정렬

링크드리스트에는 현재위치를 뿅! 뛰어넘는 부분이 있답니다.(start=start->next)  이런 부분이 오기 전에 포인터에 잠시 이전주소를 저장시켰다가 뿅 넘고 나서는 저장 시켜뒀던 이전 주소를 새로 만들어진 구조체에 연결 시켜줍니다. 언제든 돌아 갈 수 있도록 말이예요~ㅎ
 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct linked_list
{
 int data;
 linked_list *prev;
 linked_list *next; //새로나온 아이 (구조체 머리)
}link;

int main(void)
{
 int data_box[]={5,6,4,7,3,8,2,9,1,0,10};
 int length=sizeof data_box/ sizeof data_box[0];
 int num=NULL; 

 link* start;
 link* temp; //다음 만들어질 방
 link* temp_head; //이전 위치를 잠시 저장해 둘 포인터
 link* Front;
 
 temp = (link*)malloc(sizeof(link));
 start = (link*)malloc(sizeof(link));
 
 start->data=NULL;
 temp_head=start;

 Front=start;

 for(int i=0; i<length; i++)
 {
  start->data=data_box[i];

  start->next=temp;
  
  temp=(link*)malloc(sizeof(link));

  start->next=temp;

  temp_head=start; //미리 포인터에 현재위치를 저장

  start=start->next; // 넘겨주는 시점. 뿅뿅 

  start->prev=temp_head; //새로워진 위치의 -> 머리에 = 예전 위치를 매칭
 }
 start=Front;

for(int i=0; i<length; i++)
{
printf("%d ",start->data);
if(i==length-1){continue;} //마지막에는 꼬리를 달 이유가 없으므로
start=start->next;}printf("\n");

for(int i=0; i<length; i++){printf("%d ",start->data);start=start->prev;}printf("\n"); //다시 돌아오면서 출력

저작자 표시
신고
Creative Commons License
Creative Commons License
Posted by 준환이형님

댓글을 달아 주세요

티스토리 툴바