c언어 자료구조, 배열을 이용한 리스트3(ArrayListTest.cpp)

2009.05.06

배열을 이용한 구조체 파일3가지를 한 프로젝트에 넣어야지 돼용.

*.cpp는 소스에 *.h는 헤더파일에 넣으면 돼용

#include "ArrayList.h"

#include <stdio.h>

void display(ArrayListType *);

// 레포트를 제출할 때는 LIST ADT에 있는 정의되어 있는 모든 operation을 사용하지 예제를 작성하여 제출할 것
void main()
{
 ArrayListType list1;
 ArrayListType *plist;

 init(&list1);
 add(&list1, 0, 10);
 add(&list1, 0, 20);
 add(&list1, 0, 30);
 add_first(&list1, 1777);
 add_last(&list1, 7777);
 remove(&list1,1);
 display(&list1);

 printf("\n\n       is_*()함수를 test합니다.\n");
 printf("\n혹시 list1이 텅 비어있나요??\n");
 ans(is_empty(&list1));
 printf("혹시 list1이 꽉 찼나요??\n");
 ans(is_full(&list1));

 plist = (ArrayListType *)malloc(sizeof(ArrayListType));
 init(plist);
 add(plist, 0, 10);
 add(plist, 0, 20);
 add(plist, 0, 30);
 add_last(plist,9056);
 add_last(plist,6291);
 replace(plist,2 ,22 );

 printf("\n\n       position에 관련된 함수를 test합니다.\n\n");
 printf("plist의 맨앞에는 %d이(가) 있습니다.\n",plist->list[first(plist)]);
 printf("plist의 맨뒤에는 %d이(가) 있습니다.\n",plist->list[last(plist)]);
 printf("plist[2]에는 %d이(가) 있습니다.\n",get_entry(plist,2));
 printf("plist[2] 앞에는 %d이(가) 있습니다.\n",plist->list[before(plist,2)]);
 printf("plist[2] 뒤에는 %d이(가) 있습니다.\n",plist->list[after(plist,2)]);

 printf("\n\n       clear(plist)전의 출력결과.\n\n");
 display(plist);
 printf("plist에 9056이 있습니까?\n");
 ans(is_in_list(plist,9056));
 printf("plist의 길이는 %d입니다.\n",get_length(plist));

 clear(plist);

 printf("\n\n       clear(plist)후의 출력결과.\n\n");
 display(plist);
 printf("plist에 9056이 있습니까?\n");
 ans(is_in_list(plist,9056));
 printf("plist의 길이는 %d입니다.\n",get_length(plist));

 error("\n\n끝~~");
}

void display(ArrayListType *L)
{
 position idx;

 if(is_empty(L)){
  printf("list is empty");
  return;
 }

 printf("folowing items are stored in List\n");
 for(idx = first(L); idx <= last(L); idx++){
  printf("%d  ", get_entry(L, idx));
 }
 printf("\n");
}

c언어 자료구조 - 배열을 이용한 리스트2 (ArrayList.h )

2009.05.06

#pragma once

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

#define MAX_LIST_SIZE 100

typedef int element;
typedef int position;

typedef struct{
 int list[MAX_LIST_SIZE];
 int length;
} ArrayListType;

void error(char *);
void init(ArrayListType *);
int is_empty(ArrayListType *);
int is_full(ArrayListType *);
void add(ArrayListType *, position, element);
//delete 대신 remove로 바꿈 <-- cpp에서는 delete 연산자가 정의되어 있기 때문에
element remove(ArrayListType *, position);
element get_entry(ArrayListType *, position);

position first(ArrayListType *);
position last(ArrayListType *);
position before(ArrayListType *, position);
position after(ArrayListType *, position);

void add_last(ArrayListType *, element );
void add_first(ArrayListType *, element);
void clear(ArrayListType *);
void replace(ArrayListType *, position , element );
int is_in_list(ArrayListType *, element );
int get_length(ArrayListType *);
void ans(int);

c언어 자료구조 -배열을 이용한 리스트1 (ArrayList.cpp )

2009.05.06

#include "ArrayList.h"

void error(char *message)
{
 fprintf(stderr,"%s\n", message);
 exit(1); // exit 추가

}

void init(ArrayListType *L)
{
 L->length = 0;
}

int is_empty(ArrayListType *L)
{
 return L->length == 0;
}

int is_full(ArrayListType *L)
{
 return L->length == MAX_LIST_SIZE;
}

void add(ArrayListType *L, position pos, element item)
{
 int i;

 if(!is_full(L) && (pos >= 0) && (pos <= L->length)){
  for(i = (L->length - 1); i >= pos; i--){
   L->list[i+1] = L->list[i];
  }
  L->list[pos] = item;
  L->length++;
 }
}

element remove(ArrayListType *L, position pos)
{
 int i;
 element item;

 if(pos < 0 || pos >= L->length){
  error("위치오류");
 }
 item = L->list[pos];
 for(i = pos; i < last(L); i++){
  L->list[i] = L->list[i+1];
 }
 L->length--;
 return item;
}

position first(ArrayListType *L)
{
 if(is_empty(L)){
  error("list is empty");
  return -1;
 }
 return 0;
}

position last(ArrayListType *L)
{
 if(is_empty(L)){
  error("list is empty");
  return -1;
 }
 return L->length - 1;
}

position before(ArrayListType *L, position pos)
{
 if(is_empty(L)){
  error("list is empty");
  return -1;
 }

 if(pos == first(L)){
  error("current position is first");
  return -1;
 }

 return pos - 1;

}

position after(ArrayListType *L, position pos)
{
 if(is_empty(L)){
  error("list is empty");
  return -1;
 }

 if(pos == last(L)){
  error("current position is last");
  return -1;
 }

 return pos + 1;
}

element get_entry(ArrayListType *L, position pos)
{
 if(is_empty(L) || (pos < first(L)) || (pos > last(L))){
  error("position is out of range");
  return -1;
 }
 return L->list[pos];
}
  void add_last(ArrayListType *L, element item)
{
 add(L,L->length,item);
 

}

       //add_first(list, item) ::= 맨끝에 요소를 추가한다.
void add_first(ArrayListType *L, element item)
{
 add(L,0,item);
 

}

       //clear(list) ::= 리스트의 모든 요소를 제거한다.
void clear(ArrayListType *L)
{
 L->length=NULL;
 free(L->list);

}

       //replace(list, pos, item) ::= pos 위치의 요소를 item로 바꾼다
void replace(ArrayListType *L, position pos, element item)
{
 L->list[pos]=item;

}

       //is_in_list(list, item) ::= item이 리스트안에 있는지를 검사한다.
int is_in_list(ArrayListType *L, element wts)
{
 int i;
 for(i=0;i<L->length;i++){
  if(L->list[i]==wts){
   return 1;}}
 return 0;

}

       //get_length(list) ::= 리스트의 길이를 구한다.

int get_length(ArrayListType *L)
{
 return L->length;

}

void ans(int n)
{
 if(n){
  printf("예!!!그렇습니다!!\n");}
 else{
  printf("아니요... 그렇지 않습니당...\n");}
}

c언어 자료구조론 - 다항식의 덧셈

2009.04.26.

#include <stdio.h>
typedef struct{
 int deg;
 int po[10];
}poly;

poly p_add(poly a,poly b){
 poly c;
 int ap=0,bp=0,cp=0;
 int ai=a.deg,bi=b.deg;

 while(ap<=a.deg && bp<=b.deg){
  if(ai>bi){
   c.deg=a.deg;
   c.po[cp++]=a.po[ap++];
   ai--;}
 
  else if(ai<bi){
   c.deg=b.deg;
   c.po[cp++]=b.po[bp++];
   bi--;}
  else{
   c.deg=a.deg;
   c.po[cp++]=a.po[ap++]+b.po[bp++];}
 }

 return c;
}

void main(){
 poly a={3,{1,2,3,4}};
 poly b={2,{  1,2,3}};
 

 poly ans=p_add(a,b);

 int i=ans.deg;
 int p=0;

 for(;i>1;i--){
  printf("%dX^%d  +  ",ans.po[p],i);
  p++;}

 printf("%dX  +  %d\n",ans.po[p],ans.po[p+1]);

}

c언어 자료구조론 - 피보나치수열2 (구조체사용)

2009-04-26

high-ordered recursion으로 구성되어 시간복잡도가 컸던 함수를

이전 게시글에 있는 피보나치수열과 마찬가지로 linear recursion으로 구성한것이에용.

이전과는 다르게 구조체를 사용하여 표현하였습니다.

#include <stdio.h>

typedef struct{
 int n0;
 int n1;
}Two;   // 구조체선언할때도 ;를 붙이는구낭...

Two fib(int n){

 Two bef;
 Two pre;

 if(n<2){
  bef.n0=0;
  bef.n1=1;
  return bef;}   // }뒤에 ;있어도 같은결과를 출력

 bef=fib(n-1);
 pre.n0=bef.n1;
 pre.n1=bef.n0+bef.n1;

 return pre;}

void main(){
 int n;
 Two tem;

 printf("피보나치수열의 n번째항을 구해드립니당.\nn을 입력하세요.\n");
 scanf("%d",&n);

 tem=fib(n);

 printf("피보나치수열의 %d번째 항은 %d입나다.^3^\n",n,tem.n1);
}

c언어 피보나치수열

2009.04.06작성

재귀함수를 사용한 피보나치 수열이당.

binary recursion으로 작성된 피보나치 함수의 비효율성을 개선한 Linear recursion 방식의 피보나치 함수를 작성하고

피보나치값을 구해서 출력하는 프로그램 작성하는 과제였다.

사실 구조체를 이용하여 구하고 싶었는데 구조체에 대한 공부가 부족하고 제출기한이 다가와서 if를 사용했다 ㅠㅠ

#include<stdio.h>

void fib(int n, int a, int b, int t);
void main()
{

int n,a=1,b=0,t=0;

printf("피보나치수열의 알고싶은 항을 입력하세용! \n");
printf("n번째 항과 n-1번째 항이 순서대로 출력됩니다^3^ \n");
scanf("%d",&n);

fib(n,a,b,t);

return;
}

void fib(int n, int a, int b, int t)
{

 if(n==1) {
  printf("(%d,%d)\n",a,b);
  return;}
 if(n<0) {
  a=0;
  printf("(%d,%d)\n",a,b);
  return;}

 t=a;
 a=a+b;
 b=t;

 fib(n-1,a,b,t);
 return;
}