데이터 구조 대학원 (전재 출처 표시, 학습 고생 정리)
25177 단어 데이터 구조 와 알고리즘
목차
선형 표
순서 저장
1. 순차 적 으로 저 장 된 정적 할당
2. 순차 저장 소 동적 할당
3. 선형 표 삽입 순서 저장
4. 선형 테이블 의 순서 저장 삭제
2. 체인 저장 소
5. 체인 식 저장 선형 표 의 구조
6. 헤드 삽입 법 으로 단일 체인 테이블 만 들 기
7. 꼬리 삽입 법 으로 단일 체인 테이블 만 들 기
8. 체인 저장 소 번호 로 노드 찾기
9. 체인 식 저장 소 는 값 에 따라 노드 를 찾 습 니 다.
10. 체인 저장 소 삽입 노드
11. 체인 저장 소 삭제 노드
12. 더 블 링크 의 구조
13. 더 블 링크 의 삽입
14. 더 블 링크 삭제
15. 정적 링크 의 구조
창고 와 대열
순서 창고
16. 창고 의 구조
17. 스 택 비 움 판단
18. 창고 에 들어가다
19. 출고
20. 스 택 상단 요소 읽 기
21. 공유 창고 의 구조
22. 공유 창고 의 입고
체인 스 택
23. 체인 스 택 의 저장 구조
24. 체인 스 택 의 입고
25. 체인 스 택 의 출고
3. 순서 대기 열
26. 대기 열의 저장 구조
27. 대열 의 입대
28. 대열 의 출전
4. 체인 대기 열
29. 체인 대기 열의 저장 구조
30. 체인 대열 의 입대
31. 체인 식 대열 의 출전
5. 창고 의 응용
32. 창고 의 응용: 괄호 일치
34. 스 택 의 응용: 피 보 나치 수열 의 n 항
나무 와 이 진 트 리
1. 나무의 저장 구조
35. 나무의 부모 표현법
36. 나무의 아이 표현법
37. 아이 형제
38. 이 진 트 리 의 체인 저장 소
나무
39. 이 진 트 리 의 재 귀 선착순 옮 겨 다 니 기
40. 이 진 트 리 의 재 귀 중 순 서 를 옮 겨 다 닌 다.
41. 이 진 트 리 의 재 귀 후 순 서 를 옮 겨 다 닌 다.
42. 이 진 트 리 의 비 재 귀적 우선 순위 옮 겨 다 니 기
43. 이 진 트 리 의 비 재 귀 중 서 를 옮 겨 다 닌 다.
44. 이 진 트 리 의 비 재 귀적 후 차례 옮 겨 다 니 기
45. 이 진 트 리 의 층 차 를 옮 겨 다 닌 다.
3. 단서 이 진 트 리
46. 단서 이 진 트 리 의 구조
47. 이 진 트 리 에 대한 단서 화 된 재 귀 알고리즘
48. 단서 이 진 트 리 옮 겨 다 니 기
그림.
1. 그림 의 저장 구조
49. 그림 의 인접 행렬 저장
50. 그림 의 인접 표 저장 소
2. 그림 의 옮 겨 다 니 기
51. 그림 의 넓이 우선 검색 (BFS)
52. BFS 응용: 단일 소스 비 대역 권 그림 의 최 단 경로
53. 그림 의 깊이 우선 옮 겨 다 니 기 (DFS)
3. 그림 의 최소 생 성 트 리
54. 그림 의 최소 생 성 트 리 (Prim 알고리즘)
55. 집합 찾기: 어떤 집합의 루트 노드 찾기 (Kruskal 알고리즘 에 사용)
56. 집합 검사: 두 개의 집합 을 합 친다 (Kruskal 알고리즘 사용)
57. 그림 의 최소 생 성 트 리: (Kruskal 알고리즘) 크 루스 칼
4. 그림 의 최 단 경로
58. 그림 의 최 단 경로 알고리즘 (Dijkstra 알고리즘) 디 제 스 트 라
59. 그림 의 최 단 경로 알고리즘 (Floyd 알고리즘) 프로 이 드
찾다
60. 반 으로 나 누 어 찾다
61. 두 갈래 정렬 트 리 키워드 찾기 (귀속)
62. 두 갈래 정렬 트 리 키워드 찾기 (비 귀속)
63. 이 진 트 리 키워드 삽입
64. 이 진 트 리 구조 코드
정렬
65. 정렬 직접 삽입
66. 힐 정렬
67. 거품 정렬
68. 빠 른 정렬
69. 정렬 선택
70. 더미 정렬
71. 정렬
73. 토폴로지 정렬
선형 표
순서 저장
1. 순차 적 으로 저 장 된 정적 할당
#define MaxSize 50//
typedef int Elemtype// int
typedef struct{
ElemType data[MaxSize];// （ ）
int length ;// 2. 순차 저장 소 동적 할당
typedef int Elemtype
typedef struct
{
ElemType *data ;//
int MaxSize , length ;//
};
/* c */
#define InitSize 100
SeqList L;
L.data=(ElemType*)malloc(sizeof(ElemType)*InitSzie);3. 선형 표 삽입 순서 저장
bool ListInset(Sqlist &L, int i , ElemType e){
if(i<1 || i>L.length+1) return false ;// i
if(L.length >= MaxSize) return false ;// ，
for(int j=L.length ; j>=i ; j--){// i
L.data[j]=L.data[j-1];
}
L.data[i-1] = e ;// i e
L.length++ ; // 1
return true ;
}4. 선형 테이블 의 순서 저장 삭제
bool ListDelete(SqList &L , int i ,Elemtype &e){
if(i<1 || i>=L.length) return false;// i
e = L.data[i];// e
for(int j=i ; j<=L.length ; j++){// i
L.data[j]=L.data[j+1] ;
}
L.length--; // 1
return true ;
}2. 체인 저장 소
5. 체인 식 저장 선형 표 의 구조
typedef struct LNode //
{
ElemType data ;//
struct LNode *next; //
}LNode, *LinkList;
6. 헤드 삽입 법 으로 단일 체인 테이블 만 들 기
LinkList CreatLinkList(LinkList &L){
LNode *s ; //
int x ;
L=(LinkList)malloc(sizeof(LNode)) ; //
L->next = NULL ;//
scanf("%d" , &x) ;//
while(x != 9999){// 9999
s= (LNode*)malloc(sizeof(LNode)); //
s->data = x ;
s->next = L->next ;
L->next = s ;// ，L
scanf("%d" , &x) ;//
}
return L;
}7. 꼬리 삽입 법 으로 단일 체인 테이블 만 들 기
LinkList CreatLinkList(LinkList &L){
int x ;
L=(LinkList)malloc(sizeof(LNode));
LNode *s , *r = L; //r
scanf("%d" , x) ; //
while(x != 9999){// 9999
s=(LNode*)malloc(sizeof(LNode)) ;
s->data = x ;
r->next = s ;
r= s ;//r
scanf("%d" , x) ;
}
r->next = NULL ;//
return L;
}8. 체인 저장 소 번호 로 노드 찾기
LNode * GetElem(LInkList L , int i){
int j = 1;// ， 1
LNode *p = L->next ;// p
if(i==0) return L ;// i 0，
if(i<1) return NULL; // i ， NULL
while (p && jnext ;
j++;
}
return p; // i ， i ， p
}
9. 체인 식 저장 소 는 값 에 따라 노드 를 찾 습 니 다.
LNode * LocateElem(LinkList L, ElemType e){
LNode *p = L->next;
while(p!=NULL && p->data!=e){// 1 data e
p = p->next ;
}
return p;// ， NULL
}10. 체인 저장 소 삽입 노드
： 1. ① p=GetElem(L,i-1);
2. *s *p ② s->next=p->next;
3. *p *s ③ p->next=s;
bool LinkListInsert(LInkList &L , int i ,ElemType e){
if( i<1 || i>=L.length) return false ;
int j = 1;
LNode *p = L->next , *s;
s = (LNode*)malloc(sizeof(LNode));
while (p && jnext ;
j++;
}
s->next = p->next;
p->next = s ;
return true ;
} 11. 체인 저장 소 삭제 노드
： 1. p=GetElem(L,i-1);
2. q=p->next;
3.p p->next=q->next
4. free(q);
bool LinkListDelete(LInkList &L , int i ,ElemType &e){
if( i<1 || i>=L.length) return false ;
int j = 1;
LNode *p = L->next ，*q ;
while (p && jnext ;
j++;
}
q = p->next ;
p->next = q->next;
e = q->data;
free(q) ;
return true ;
} 12. 더 블 링크 의 구조
typedef struct DNode //
{
ElemType data ; //
struct DNode *prior ,*next ;//
}DNode ,*DLinkList;13. 더 블 링크 의 삽입
bool DLinListInsert(DLInkList &L , int i ,ElemType e){
if( i<1 || i>=L.length) return false ;
int j = 1;
DNode *p = L->next , *s;
s = (DNode*)malloc(sizeof(DNode));
while (p && jnext ;
j++;
}
s->next = p->next;
p->next->prior = s ;
s->prior = p ;
p->next = s;
return true ;
} 14. 더 블 링크 삭제
bool DLinkListDelete(DLinkList &L , int i ,ElemType &e){
if( i<1 || i>=L.length) return false ;
int j = 1;
DNode *p = L->next ，*q ;
while (p && jnext ;
j++;
}
q = p->next ;
p ->next = q->next ;
q ->next->prior = p;
e = q->data;
free(q) ;
return true ;
} 15. 정적 링크 의 구조
#define MaxSize 50 //
typedef int ElemType // int
typedef struct //
{
ElemType data ; // ：
int next ;// ：
}SLinkList[MaxSize];창고 와 대열
순서 창고
16. 창고 의 구조
#define MaxSize 50 //
typedef struct
{
ElemType data[MaxSize] ;//
int top ;//
}SqStack; // 17. 스 택 비 움 판단
bool StackEmpty(SqStack S){
if(s.top == -1) return true ;
else return false ;
}18. 창고 에 들어가다
bool Push(SqStack &S , ElemType x){
if(S.top == MaxSize-1) return false ;
S.data[++top] = x ;
return true ;
}19. 출고
bool Pop(SqStack &S,ElemType &x) {
if(S.top == -1) return false ;
x = S.data[top--] ;
return true ;
}20. 스 택 상단 요소 읽 기
bool Pop(SqStack &S,ElemType &x) {
if(S.top == -1) return false ;
x = S.data[top] ;
return true ;
}21. 공유 창고 의 구조
#define MaxSize 100 //
typedef struct
{
ElemType data[MaxSize] ;//
int top1 ;// 1
int top2 ;// 2
}SqDoubleStack; // 22. 공유 창고 의 입고
bool Push(SqDoubleStack &S , ElemType x , int stackNum){
if(S.top1+1 == S.top2) return false ; //
if(stackNum == 1) // 1
S.data[++top1] = x;
else(stackNum == 2)// 2
S.data[--top2] = x;
return true ;
}체인 스 택
23. 체인 스 택 의 저장 구조
typedef struct SNode
{
ElemType data ;//
struct SNode *next ; //
}SNode , *SLink; //
typedef struct LinkStack
{
Slink top ; //
int count ; //
}LinkStack; // 24. 체인 스 택 의 입고
bool Push(LinkStck &S, ElemType x){
SLink p = (Slink)malloc(sizeof(SNode)) ; //
p->data = x ;//
p->next = S->top ; //p
S->top = p ; //
S->count++ ; // 1
return true ;
}25. 체인 스 택 의 출고
bool Pop(LinkStack *S , ElemType &x) {
if(S->top == NULL) return false ;
x = S->top->data ; //
Slink p = S->top ; //
S->top = S->top->next ; //
free(p); //
S->count-- ;//
return true ;
}3. 순서 대기 열
26. 대기 열의 저장 구조
#define MaxSize 50//
typedef struct
{
ElemType data[MaxSize] ;//
int front ,rear ;//
}SqQueue;27. 대열 의 입대
bool EnQueue(SqQueue &Q , ElemType x){
if((Q.rear+1)%MaxSize == Q.front ) return false ;//
Q.data[Q.rear] = x;
Q.rear = (Q.rear+1)%MaxSize ;
return true ;
}28. 대열 의 출전
bool DeQueue(SqQueue &Q ,ElemType &x){
if(Q.front == Q.rear) return false ; // ，
x = Q.data[Q.front] ;
Q.front = (Q.front+1)%MaxSize ;
return true ;
}4. 체인 대기 열
29. 체인 대기 열의 저장 구조
typedef struct //
{
ElemType data ;
struct LinkNode *next ;
}LinkNode;
typedef struct //
{
LinkNode *front,*rear ; //
}LinkQueue;30. 체인 대열 의 입대
void EnQueue(LinkQueue &Q, ElemType x){
s=(LinkNode *)malloc(sizeof(LinkNode)) ;
s->data = x ;
s->next = NULL ;
Q.rear->next = s ;
Q.rear = s ;
}31. 체인 식 대열 의 출전
bool DeQueue(LinkQueue &Q , ElemType &x){
if(Q.rear == Q.front ) return false ; //
p = Q.front->next ;
x = p->data ;
Q.front->next = p->next ;
if(Q.rear == p) // ，
Q.rear = Q.front ;
free(p) ;
return true ;
}5. 창고 의 응용
32. 창고 의 응용: 괄호 일치
bool Check(char *str){
Stack s ;
InitStck(s) ;
int len = strlen(str) ; // len
for (int i = 0; i34. 스 택 의 응용: 피 보 나치 수열 의 n 항
int Fib(int n){
if( n== 0 ) return 0 ; //1. Fib(0)==0, Fib(1)==1
else if(n == 1) return 1 ; //2. Fib(n)=Fib(n-1)+Fib(n-2)
else return Fib(n-1)+Fib(n-2) ;
}나무 와 이 진 트 리
1. 나무의 저장 구조
35. 나무의 부모 표현법
typedef char ElemType ;
typedef struct TNode
{
ElemType data ; //
int parent ; //
}TNode; //
#define MaxSize 100
typedef struct
{
TNode nodes[MaxSize] ; //
int n; //
}Tree;//
36. 나무의 아이 표현법
typedef char ElemType ;
typedef struct CNode
{
int chlid ;//
struct CNode *Next ; //
}CNode ,*child ;//
typedef struct
{
ElemType data ; //
child firstchild ;//
}TNode ;//
#define MaxSize 100
typedef struct
{
TNode nodes[MaxSize] ;//
int n ;//
}tree; // 37. 아이 형제
typedef char ElemType ;
typedef struct CSNode
{
ElemType data ;//
struct CSNode *firstchild ,*rightchild ; //
}CSNode ; //
38. 이 진 트 리 의 체인 저장 소
typedef struct BiTNode
{
ElemType data ;//
struct BiTNode *lchild ,*rchild ; // 、
}BiTNode , *BiTree ; // 나무
39. 이 진 트 리 의 재 귀 선착순 옮 겨 다 니 기
void PreOrder(BiTree T){
if(T != NULL) {
print ("%c" , T->data) ; //
PreOrder(T->lchild) ;//
PreOrder(T->rchild) ; //
}
}40. 이 진 트 리 의 재 귀 중 순 서 를 옮 겨 다 닌 다.
void InOrder(BiTree T){
if(T != NULL){
InOrder(T->lchild) ;//
print("%c" , T->data) ;//
InOrder(T->rchild) ; //
}
}41. 이 진 트 리 의 재 귀 후 순 서 를 옮 겨 다 닌 다.
void PostOrder(BiTree T){
if(T != NULL){
PostOrder(T->lchild) ;//
PostOrder(T->rchild) ; //
print("%c" , T->data) ;//
}
}42. 이 진 트 리 의 비 재 귀적 우선 순위 옮 겨 다 니 기
void PreOrderTraverse(BiTree b){
Stack s ;
InitStack(s) ;
BiTree p = b ; // p
while(p || !IsEmpty){
while(p){
printf("%c", p->data) ; //
Push(S,p);
p= p->lchild ;
}
if(!IsEmpty(S)){
p=Pop(s) ;
p= p->rchild ;
}
}
}43. 이 진 트 리 의 비 재 귀 중 서 를 옮 겨 다 닌 다.
void InOrderTraverse(BiTree b){
Stack s;
InitStack(s) ;
BiTree p = b ; // p
while (p || !IsEmpty(s)){
while(p){//
Push(s,p) ;
p = p->lchild ;
}
//
p = Pop(s) ;
printf("%c" , p->data) ;
p = p->rchild ;//
}
}44. 이 진 트 리 의 비 재 귀적 후 차례 옮 겨 다 니 기
void PostOrderTraverse(BiTree T){
InitStack(S) ;
BiTree p = b , r = NULL ;// p r
while(p || !IsEmpty(s)){
//1.
if(p){
Push(S,p) ;
p=p->lchild ;
}
//2.
else{
GetTop(S,p) ;// ！
//① ， ，
if(p->rchild && p->rchild!=r)
p = p->rchild ;
//② ，
else{
Pop(S,p);
printf("%c" , p->data) ;
r = p ; //
p = NULL ;// p
}
}
}
}45. 이 진 트 리 의 층 차 를 옮 겨 다 닌 다.
void LevelOrder(BiTree T){
InitQueue(Q) ;
BiTree p ;
EnQueue(Q , b) ; //
while (!IsEmpty(Q))//
{
DeQueue(Q , p); //
printf("%c" , p->data) ;
if(p->lchild != NULL)
EnQueue(Q,p->lchild) ;
if(p->rchild != NULL)
EnQueue(Q,p->rchild) ;
}
}3. 단서 이 진 트 리
46. 단서 이 진 트 리 의 구조
typedef struct ThreadNode
{
ElemType data ;
struct ThreadNode *lchild , *rchild ;
int ltag ,rtag ;
}ThreadNode ,*ThredTree;// 47. 이 진 트 리 에 대한 단서 화 된 재 귀 알고리즘
void InThread(ThreadTree &p ,ThreadTree &pre){
if(p){//pre NUL
InThread(p->lchild , pre) ;
if(p->lchild == NULL){
p->lchild = pre ;
p->ltag = 1 ;
}
if(pre!=NULL && pre->rchild==NULL){
pre->rchild = p ;
p->rtag = 1 ;
}
pre = p ;
InThread(p->rchild,pre) ;
}
}48. 단서 이 진 트 리 옮 겨 다 니 기
void InOrderTraverse(ThreadTree T){
ThredTree p = T ;
while(p){
while(p->ltag == 0){
p = p->lchild ;
printf("%c", p->data) ;
}
while(p->rtag==1 && p->rchild){
p=p->rchild ;
printf("%c", p->data) ;
}
p = p->rchild ;
}
}그림.
1. 그림 의 저장 구조
49. 그림 의 인접 행렬 저장
#define MaxVertexNum 100//
typedef char VertexType ;//
typedef int EdgeType ;//
typedef struct
{
VertexType Vex[MaxVertexNum];//
EdgeType Edge[MaxVertexNum][MaxVertexNum] ;// ( )，
int vexnum , arcnum ;//
}MGraph;50. 그림 의 인접 표 저장 소
typedef struct VNode//
{
VertexType data ;//
ArcNode *firstedge ;//
}VNode,AdjList[MaxVertexNum];//AdjList
#define MaxVertexNum 100//
typedef struct ArcNode//
{
int adjvex ;//
struct ArcNode *next ;//
}ArcNode;
typedef struct
{
AdjList vertices ;//
int vexnum ,arcnum ;//
}ALGraph;//ALGraph 2. 그림 의 옮 겨 다 니 기
51. 그림 의 넓이 우선 검색 (BFS)
#define MaxSize 100
bool visited[MaxSize] ;
void BFS(Graph G ,int v){
ArcNode *p ;// p
InitQueue(Q) ;//
visited(v) ;// v, print
visited[v] = TRUE ;// v
while(!IsEmpty(Q)){//
DeQueue(Q,v) ;// v
p = G->adjList[v].firstedge ;// p
while(p){
if(!visited[p->adjvex]){//p
visited(p->adjvex) ;// p
visited[p->adjvex] = TRUE ;//
EnQueue(Q, p->adjvex) ;//
}
p=p->next ;//p
}
}
}
void BFSTraverse(Graph G){
int i ;//
for (i=0;ivexnum ; i++){
visited[i] = false ;// ( )
}
for (i=0;ivexnum ; i++){
if(!visited[i]) BFS(G,i);// ，
}
} 52. BFS 응용: 단일 소스 비 대역 권 그림 의 최 단 경로
void BFS_MIN_Distance(Graph G, int u){
for(i=0;iadjList[u].firstedge;
while(p){
if(!visited[p->adjvex]){
visited[p->adjvex] = TRUE ;
d[p->adjvex] = d[u]+1 ;// 1
EnQueue(Q,p->adjvex) ;
}
p=p->next;
}
}
} 53. 그림 의 깊이 우선 옮 겨 다 니 기 (DFS)
#define MaxSize 100
bool visited[MaxSize] ;
void DFS(Graph G, int v){
ArcNode *p ;// p
visit(v);// v( ，printf)
visited[v] = TRUE ;//
p = G->adjList[v].firstarc;// p
while(p!=NULL){//
if(!visited[p->adjvex]){//
DFS(G,p->adjvex);//
}
p=p->nextarc ;//
}
}
void DFSTraverse(Graph G){
int i ;//
for (i=0;ivexnum ; i++){
visited[i] = false ;// ( )
}
for (i=0;ivexnum ; i++){
if(!visited[i]) DFS(G,i);//
}
} 3. 그림 의 최소 생 성 트 리
54. 그림 의 최소 생 성 트 리 (Prim 알고리즘)
void MiniSpanTree_Prim(MGraph G){
int min ,i ,j ,k ;
int adjvex[MAXVEX] ;//
int lowcost[MAXVEX] ;//
lowcost[0] = 0 ;// 0 ( 0 )
adjvex[0] = 0 ;// 0
for(i=0 ;i%d)",adjvex[k],k;//
lowcost[k] = 0 ;//
// 1 lowcost
for(j=0;j 55. 집합 찾기: 어떤 집합의 루트 노드 찾기 (Kruskal 알고리즘 에 사용)
int Find(int *parent, int x){
while (parent[x]>=0) x=parent[x];// x
return x ;// parent 0
}
56. 집합 검사: 두 개의 집합 을 합 친다 (Kruskal 알고리즘 사용)
void Union(inbt *parent,int root1 ,int root2){
parent[root2] = root1 ;
}57. 그림 의 최소 생 성 트 리: (Kruskal 알고리즘) 크 루스 칼
#define 100
typedef struct
{
int a,b ;//
int weight ;//
}Edge;//
int Find(int *parent, int x){
while (parent[x]>=0) x=parent[x];// x
return x ;//while
}
Edge edges[MaxEdge] ;//
int parent[MaxVex] ;// ( )
void MiniSpanTree_Kruskal(MGraph G){
int i,n,m ;
sort(edges) ;//
for (int i=0;i%d)",edges[i].a,edges[i].b);//
}
}
} 4. 그림 의 최 단 경로
58. 그림 의 최 단 경로 알고리즘 (Dijkstra 알고리즘) 디 제 스 트 라
void Dijkstra(MGraph G,int v,int path[],int dist[]){ //v
int s[maxSize]; // s 1 0
int i,j,min,u;
// path dist s
for(i=0 ; i59. 그림 의 최 단 경로 알고리즘 (Floyd 알고리즘) 프로 이 드
void Floyd(MGraph G,int Path[][]){
int i, j, k ;
int A[MaxSize][MaxSize];
// A[][] Path[][]
for(i=0; iA[i][k]+A[k][j]){// i j i k j ， i j ， k k
A[i][j]=A[i][k]+A[k][j];
Path[i][j]=k;
}
}
}
}
} 찾다
60. 반 으로 나 누 어 찾다
int Binary_Search(SeqList L,ElemType key,int n){//L ,key ，n L
int low=0,high=n-1,mid;//low high mid ，
while(low<=high){// low hig ，
mid=(low+high)/2;// low high 2
if(L.elem[mid]==key)//
return mid;
else if(L.elem[mid]>key)// key
high=mid-1; // ， key
else// key
low=mid+1; //key
}
return -1;
}61. 두 갈래 정렬 트 리 키워드 찾기 (귀속)
BiTNode *BST_Search(BiTNode *t,ElemType key){
if(t==NULL)return NULL; //
else{
if(t->key==key) return t;
else if(keykey) return BST_Search(t->lchild,key);
else return BST_Search(t->rchild,key);
} 62. 두 갈래 정렬 트 리 키워드 찾기 (비 귀속)
BiTNode * BST_Search(BiTNode *t,ElemType key){
BiTNode *p=t;//
while(p!=NULL && key!=p->data){//p key
if(keydata) p=p->lchild;// key p ，
else p=p->rchild;// key p ，
}
return p;// key NULL
} 63. 이 진 트 리 키워드 삽입
int BST_Insert(BiTNode* &t,ElemType k){ // ，
if(t==NULL){// ，
t=(BiTNode*)malloc(sizeof(BiTNode));//malloc
t->key=k;// k
t->lchild=t->rhild=NULL;//
return 1;// 1，
}
else if(k==t->key)//
return 0;
else if(kkey)// t
return BST_Insert(t->lchild,k);
else// t
return BST_Insert(t->rchild,k);
} 64. 이 진 트 리 구조 코드
void Creat_BST(BiTNode *&t,ElemType key[ ],int n){
//t key n
t=NULL; // t
int i=0;
while(i정렬
65. 정렬 직접 삽입
void InsertSort(ElemType A[],int n){
int i,j;
for(i=2;i<=n;i++){
if(A[i].key66. 힐 정렬
void ShellSort (ElemType A[],int n){
int i,j;
for(dk=n/2;dk>=1;dk=dk/2){// ， 2 ， 1
for(i=dk+1;i<=n;++i){
if(A[i].key0&&A[0].key67. 거품 정렬
void BubbleSort(ElemType A[],int n){
for(i=0;ii;j--) //
if(A[j-1].key>A[j].key){ // ，
ElemType temp=A[j-1].key;
A[j-1].key=A[j].key;
A[j].key=temp;
flag=true; //
}
if(flag==false)return ; // ，
}
} 68. 빠 른 정렬
int Partition(ElemType A[],int low,int high){//low ，high
ElemType pivot=A[low];//
while(low=pivot) --high;//
A[low]=A[high];// high low
while(low 69. 정렬 선택
void SelectSort(ElemType A[],int n){
for(i=0;i70. 더미 정렬
void BuildMaxHeap(ElemType A[],int len){
for(int i=len/2;i>0;i--) AdjustDown(A,i,len);
}
void AdjustDown(ElemType A[],int k,int len){
A[0]=A[k];
for(i=2*k;i<=len;i*=2){
if(i=A[i]) break;
else{
A[k]=A[i];
k=i;
}
}
A[k]=A[0];
}
void HeapSort(ElemType A[],int len){
BuildMaxHeap(A,len);//
for(i=len;i>1;i--){//n-1
// ( )
ElemType temp=A[i];
A[i]=A[1];
A[1]=temp;
printf(A[i]);
AdjustDown(A,1,i-1);// i-1
}
}
71. 정렬
ElemType *B=(ElemType *)malloc((n+1)*sizeof(ElemType)); // B( )
void Merge(ElemType A[],int low,int mid,int high){
// A A[low…mid] A[mid+1…high] ，
for(int k=low;k<=high;k++) B[k]=A[k];// A B
for(int i=low,j=mid+1,k=i;i<=mid&&j<=high;k++){ //k
if(B[i]<=B[j])// B
A[k]=B[i++];// A
else
A[k]=B[j++];
}
while(i<=mid) A[k++]=B[i++];// ，
while(j<=high) A[k++]=B[j++];// ，
}
void MergeSort(ElemType A[],int low,int high){
if(low73. 토폴로지 정렬
bool TopologicalSort(Graph G){
InitStack(S);// ， 0
for(int i=0;inextarc){
v=p->adjvex; //
if(!(--indegree[v]))Push(S,v);// 1 0，
}
}
if(count 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[JAVA] 배열 회전 출력요소 가 출력 을 시작 하 는 위치 에 주의 하 십시오. 모두 몇 라운드 의 수출 이 있 습 니까? n/2 + 1 매 라 운 드 는 상, 우, 하, 좌 로 나 뉜 다. 각 방향의 시작 위치 와 좌표 의 관 계 를 구...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
