연결리스트 활용 문제

연결리스트의 개념은 이해했지만 아직 구현은 낯설다... 계속 헤드를 잃어버린다. 그리고 내가 사용하는 단순연결리스트는 노드의 정보를 역순으로 알수업다?는 점이 항상 골치덩어리였다... 

---

[1] 원소값이 0이 아닌 것만 표현하는 하나의 행렬을 입력받아 입력행렬과 전치행렬을 출력하는 프로그램을 작성하되 연결리스트를 사용하여 fast_transpose 논리를 적용한 프로그램을 작성

---

문제를 보고 어떻게 하면 좋을지 끄적여 본 굳노트.

먼저 입력행렬을 연결리스트로 구현하려고 했다. fast_transpose를 사용하려면 행렬을 입력할때 행 올림차순으로 입력된다는 사실을 이용해야하기 때문에 행렬을 입력받은 순서대로 저장하는 것이 중요하다. 저번과제에서는 그냥 insert_f 를 써서 역순으로 저장된것은 다시 역순으로 배열해주는 함수를 써서 했지만 이번에는 첫번째 노드를 dummy 값으로 설정해서 수고를 덜었다. insert(새로운 노드의 앞노드를 가리키는 포인터 변수, 새로삽입하는 데이터) 함수를 사용했다.

 

fast_transpose는 저번 과제에서 배열로 구현해본 경험이 있어 논리는 알고있었다.

 

 

 

 

 

 

 

 

 

starting pos[index]에는 전치전 index번째 행렬이 전치 후에 저장되어야 하는 순서가 저장되는데, 배열을 사용해서 구현할때는 이미 만들어진 배열에 순서에 맞게 집어넣었다. 연결리스트를 사용해서 구현할때 이부분을 어떻게 해결할지 많이 고민했다.

일단 제일 간단한 방법이 미리 비어있는 연결리스트를 만들어 놓고 자리에 맞게 요소값을 넣어 주는 것이다. 제일 먼저 생각났고 제일 쉽게 구현할 수 있을 것 같았다. 

 

 

 

 

 

 

 

 

 

---

이제 코드를 보도록 합시당

typedef struct info{
	int row;
	int col;
	int value;
}Info;

typedef struct Listnode{
	Info data;
	Listnode *link;
}Listnode;

int main(){
	Listnode *matrix=(Listnode*)malloc(sizeof(Listnode));
	Listnode *result=(Listnode*)malloc(sizeof(Listnode));
	Info firstnode={0,0,0};		//첫번째노드에는 행렬의 정보를 저장한다. 
	Info input;
	Listnode *pre;				
	Listnode *temp;
	int *rowterms;				//for fast_transpose			
	int *startingpos;			//for fast_transpose
	int i, j, k;
    
    }

matrix는 행렬을 입력받아 저장하는 연결리스트인데 이 연결리스트의 첫번째 노드는 행령의 정보(제일큰행, 제일큰열, 원소의 갯수)를 저장한다. result는 matrix와 다르게 첫번째노드부터 전치행령을 저장한다. 그래도 result에 빈공간을 행렬의 원소의 갯수만큼 만들어주기위해 일단 동적할당으로 하나의 노드공간의 메모리를 할당해주었다. 

int main()
{
	matrix->link=NULL;			//첫번째노드 초기화 
	matrix->data=firstnode;
	
	//입력받기 
	pre=matrix;
	while(scanf("%d-%d-%d", &input.row, &input.col, &input.value)!=EOF){
		pre=insert(pre, input);
		matrix->data.value++;		//행렬원소의 갯수세기 
		if(pre->data.row>matrix->data.row) matrix->data.row=pre->data.row;
		if(pre->data.col>matrix->data.col) matrix->data.col=pre->data.col;
	}
}

Listnode* insert(Listnode *pre, Info value){
	Listnode *p=(Listnode*)malloc(sizeof(Listnode));
	p->data=value;
	p->link=pre->link;
	pre->link=p;
	return p;	 
}

이후의 메인함수에서는 행렬을 입력받는다. 이때 쓰이는 insert함수는 저번연결리스트 기초공부에서 공부했던 insert함수이다. 인수로 삽입되어야하는 위치의 이전노드와 삽입되어야 하는 내용을 전달한다. 

int main(){
	rowterms=(int*)malloc(sizeof(int)*(matrix->data.col));
	startingpos=(int*)malloc(sizeof(int)*(matrix->data.col));
	
	for(i=0;i< (matrix->data.col);i++){
		rowterms[i]=0;
	}
	
	for(Listnode *i=matrix->link ; i!=NULL ; i=i->link){
		rowterms[i->data.col]++;
	}
	
	startingpos[0]=1;
	
	for(i=1; i<=matrix->data.col; i++){
		startingpos[i]=startingpos[i-1]+rowterms[i-1];
	}
}

그후 fast_transpose.... 이때 쓰이는 배열은 필요한 메모리 사이즈가 분명해서 동적할당 해주었다.

int main(){
	result->link=NULL;			//첫번째노드 초기화 
	result->data=firstnode;	
	
	for(i=1;i<matrix->data.value;i++){
		pre=insert(result,firstnode);		//result 노드 미리 만들기 
	}
	
	for(Listnode *i=matrix->link;i!=NULL;i=i->link){
		j=startingpos[i->data.col]++;
		input.row=i->data.col;
    	input.col=i->data.row;
        input.value=i->data.value;
		temp=result;
		for(int k=0;k<j-1;k++){
			temp=temp->link;
		}
		temp->data=input;
	}
}

그런 다음 결과를 저장할 result연결리스트를 만들어야 한다. 이때 insert함수를 이용해서 만들기 위해 첫번째 노드를 만든다음 이후의 노드는 insert함수를 이용해서 만들었다. 그리고 넣어야 할 정보를 input에 저장한 후 맞는 위치까지 for문을 돌려 넣어주었다. 이부분이 효율적이지 않은 것 같은게 맞는 위치까지 반복문을 돌려야 하기 때문이다. 행렬에 따라서 for문을 돌리는 횟수가 변수가 된다.....일단 다음 과제를 마친 후 더 생각해보아야겠다...