시간복잡도 좀 알려주세요
마리
#include stdio.h
#include stdlib.h
//단순 연결 리스트 구현
typedef int element;
typedef struct ListNode {
element data;
struct ListNode *link;
} ListNode;
//에러 호출 프로그램
void error(char *message)
{
fprintf(stderr,%s\n,message);
exit(1);
}
//단순 연결 리스트의 삽입 함수 C
void insert_node(ListNode **phead, ListNode *p,
ListNode *new_node)
{
if( *phead == NULL ){// 공백리스트인 경우
new_node-link = NULL;
*phead = new_node;
}
else if( p == NULL ){ // p가 NULL이면 첫번째 노드로 삽입
new_node-link = *phead;
*phead = new_node;
}
else { // p 다음에 삽입
new_node-link = p-link;
p-link = new_node;
}
}
// 노드를 동적으로 생성하는 프로그램
ListNode *create_node(element data, ListNode *link)
{
ListNode *new_node;
new_node = (ListNode *)malloc(sizeof(ListNode));
if( new_node == NULL ) error(메모리 할당 에러);
new_node-data = data;
new_node-link = link;
return(new_node);
}
//반복적인 리스트 방문 알고리즘
void display(ListNode *head)
{
ListNode *p=head;
while( p != NULL ){
printf(%d-, p-data);
p = p-link;
}
printf(\n);
}
//홀수 나누는 함수 split_A
void split_A(ListNode *head)
{
int *list_A = NULL;
//초기값 헤드부터
ListNode *pOddNode = head;
while(pOddNode != NULL)
{
//list_A에 데이터 저장
list_A = &pOddNode-data;
//값 출력
printf(list_A : %d\n, *list_A);
//2칸 건너 뛰어 이동
pOddNode = (pOddNode-link == NULL)?(NULL):(pOddNode-link-link);
}
printf(-------------------------------\n);
}
//짝수 나누는 함수 split_B
void split_B(ListNode *head)
{
int *list_B = NULL;
//초기값 헤드의 다음부터
ListNode *pEvenNode = (head-link == NULL)?(NULL):(head-link);
while(pEvenNode != NULL)
{
//list_B에 데이터 저장
list_B = &pEvenNode-data;
//값 출력
printf(list_B : %d\n, *list_B);
//2칸 건너 뛰어 이동
pEvenNode = (pEvenNode-link == NULL)?(NULL):(pEvenNode-link-link);
}
}
//테스트 프로그램
void main()
{
//단순 연결 리스트 삽입 함수 사용해서 list_C에 노드 삽입
ListNode *list_C = NULL;
insert_node(&list_C, NULL, create_node(10, NULL));
insert_node(&list_C, NULL, create_node(9, NULL));
insert_node(&list_C, NULL, create_node(8, NULL));
insert_node(&list_C, NULL, create_node(7, NULL));
insert_node(&list_C, NULL, create_node(6, NULL));
insert_node(&list_C, NULL, create_node(5, NULL));
insert_node(&list_C, NULL, create_node(4, NULL));
insert_node(&list_C, NULL, create_node(3, NULL));
insert_node(&list_C, NULL, create_node(2, NULL));
insert_node(&list_C, NULL, create_node(1, NULL));
//리스트 방문 알고리즘 사용해서 list_C 출력
display(list_C);
//list_C의 홀수번째 노드를 list_A에 이동시키는 함수 split_A 사용 list_A 출력
split_A(list_C);
//list_C의 짝수번째 노드를 list_B에 이동시키는 함수 split_B 사용 list_B 출력
split_B(list_C);
}단순연결 리스트 C를 두개의 단순 연결 리스트 A와 B로 분리하는 함수 split를 작성하여보자. C의 홀수번째 노드들은 모두 A로 이동되고, C의 짝수 번째 노드들은 모두 B로 이동된다. 이 함수가 C를 변경하여서는 안된다. 작성된 알고리즘의 시간 복잡도를 구하고, 구현하여 수행하여 보자.
위에 문제 푼건데 시간복잡도가 얼만지 잘 모르겠습니다.
시간복잡도가 얼만지 좀 알려주세요~
그리고 맞게 푼건지 확인좀 ㅎㅎ;
번호 | 제 목 | 글쓴이 | 날짜 |
---|---|---|---|
2655576 | 구조체 선언 질문입니다. | 통꽃 | 2024-05-21 |
2655547 | 변수선언과 printf만 사용해서 수식 짜기 (1) | 피리 | 2024-05-20 |
2655523 | 문자열 사이에 문자열삽입 | 바람 | 2024-05-20 |
2655491 | 키보드 인식, 랜덤 함수 or 헤더 (2) | 별 | 2024-05-20 |
2655471 | 링 버퍼 구현된 소스 인데요.. 이해가 잘안되서요.. | 소심한녀자 | 2024-05-20 |
2655440 | test파일이 안 되요. (2) | 리라 | 2024-05-19 |
2655416 | 고수님들 도움이 절실합니다. (2) | 세리 | 2024-05-19 |
2655361 | 엔터 입력받을때까지 기다리는 getchar (1) | 큰모음 | 2024-05-19 |
2655328 | 함수에서 포인터 (3) | 모아 | 2024-05-18 |
2655299 | 아이콘바꾸는법..? | 소 | 2024-05-18 |
2655271 | scanf 입력받으면 쭉 실행되는.. (5) | ComeOn | 2024-05-18 |
2655184 | 이 세개 프로그램좀 해결해주실.... 고수님들???? (3) | 말달리자 | 2024-05-17 |
2655129 | 다차원 배열 원소들 주소계산하는거 질문이요~ | 터전 | 2024-05-17 |
2655103 | AVRstudio MoveAxis. MoveLine 함수질문 | 앨버트 | 2024-05-16 |
2655072 | 콘솔창의 위치와 크기를 정하고 싶습니다. | 딥레드 | 2024-05-16 |
2655044 | 자료구조랑 online judge site에 대해서 질문있습니다... (1) | 뽀송뽀송 | 2024-05-16 |
2655016 | 별찍기 문제 중 이해안되는 부분이 있어요... | 도전중 | 2024-05-16 |
2654986 | 입력받은 성적을 배열에 저장하기 (3) | 안녕나야 | 2024-05-15 |
2654959 | ===========-이런거 미리 지정하는법 (1) | 김자영 | 2024-05-15 |
2654930 | 도와주십시요 ㅜㅜ 자료구조 ㅜㅜ | 도널드 | 2024-05-15 |