用C說話舉例講授數據構造中的算法龐雜度結與次序表

用C說話舉例講授數據構造中的算法龐雜度結與次序表。本站提示廣大學習愛好者：（用C說話舉例講授數據構造中的算法龐雜度結與次序表）文章只能為提供參考，不一定能成為您想要的結果。以下是用C說話舉例講授數據構造中的算法龐雜度結與次序表正文

數據構造算法龐雜度
1、影響算法效力的重要身分
（1）算法采取的戰略和辦法；

（2）成績的輸出范圍；

（3）編譯器所發生的代碼；

（4）盤算機履行速度。

2、時光龐雜度

// 時光龐雜度：2n + 5 
long sum1(int n) 
{ 
  long ret = 0; \\1 
  int* array = (int*)malloc(n * sizeof(int)); \\1 
  int i = 0; \\1 
   
  for(i=0; i<n; i++) \\n 
  { 
    array[i] = i + 1; 
  } 
   
  for(i=0; i<n; i++) \\n 
  { 
    ret += array[i]; 
  } 
   
  free(array); \\1 
   
  return ret; \\1 
} 
 
 
\\時光龐雜度: n + 3 
long sum2(int n) 
{ 
  long ret = 0; \\1 
  int i = 0; \\1 
   
  for(i=1; i<=n; i++) \\n 
  { 
    ret += i; 
  } 
   
  return ret; \\1 
} 
 
\\時光龐雜度: 3 
long sum3(int n) 
{ 
  long ret = 0; \\1 
   
  if( n > 0 ) 
  { 
    ret = (1 + n) * n / 2; \\1 
  } 
   
  return ret; \\1 
} 

跟著成績范圍n的增年夜，它們操作數目的差別會愈來愈年夜，是以現實算法在時光效力上的差別也會變得異常顯著！

斷定一個算法的效力時，常常只須要存眷操作數目的最高次項，其它主要項和常數項可以疏忽。

在沒有特別解釋時，我們所剖析的算法的時光龐雜度都是指最壞時光龐雜度。

 3、空間龐雜度

//空間龐雜度：12 + n 
long sum1(int n) 
{ 
  long ret = 0; \\4 
  int* array = (int*)malloc(n * sizeof(int)); \\4 + 4 * n 
  int i = 0; \\4 
   
  for(i=0; i<n; i++) 
  { 
    array[i] = i + 1; 
  } 
   
  for(i=0; i<n; i++) 
  { 
    ret += array[i]; 
  } 
   
  free(array); 
   
  return ret; 
} 
 
 
\\空間龐雜度: 8 
long sum2(int n) 
{ 
  long ret = 0; \\4 
  int i = 0; \\4 
   
  for(i=1; i<=n; i++) 
  { 
    ret += i; 
  } 
   
  return ret; 
} 
 
\\空間龐雜度: 4 
long sum3(int n) 
{ 
  long ret = 0; \\4 
   
  if( n > 0 ) 
  { 
    ret = (1 + n) * n / 2; 
  } 
   
  return ret; 
} 

    多半情形下，算法履行時所用的時光更使人存眷,假如有需要，可以經由過程增長空間龐雜度來下降時光龐雜度,同理，也能夠經由過程增長時光龐雜度來下降空間龐雜度，詳細成績，詳細剖析。

數據構造次序表
表是具有雷同類型的n（n >= 0）個數據元素的無限序列,即：

•     線性表(List)是零個或多個數據元素的聚集
•     線性表中的數據元素之間是有次序的
•     線性表中的數據元素個數是無限的
•     線性表中的數據元素的類型必需雷同

//seq_list.h 
#ifndef _SEQ_LIST_H_ 
#define _SEQ_LIST_H_ 
 
struct seq_list 
{ 
  int capacity; 
  int length; 
  unsigned int *node; 
}; 
 
struct seq_list* seq_list_create(int capacity); 
int seq_list_capacity(struct seq_list* list); 
int seq_list_length(struct seq_list* list); 
int seq_list_insert(struct seq_list* list, int position, void* data); 
void* seq_list_get(struct seq_list* list, int position); 
void* seq_list_remove(struct seq_list* list, int position); 
void seq_list_clear(); 
void seq_list_destroy(struct seq_list* list); 
 
#endif 

//seq_list.c 
#include "seq_list.h" 
#include <stddef.h> 
#include <malloc.h> 
 
struct seq_list* seq_list_create(int capacity) 
{ 
  int i = 0; 
  struct seq_list* ret = NULL; 
  if (capacity >= 0) 
  { 
    ret = (struct seq_list*) malloc(sizeof(struct seq_list) + sizeof(unsigned int) * capacity); 
    if (ret != NULL)  
    { 
      ret->capacity = capacity; 
      ret->length = 0; 
      ret->node = (unsigned int*) (ret + 1); 
    } 
  } 
  return ret; 
} 
 
int seq_list_insert(struct seq_list* list, int position, void* data) 
{ 
  int i = 0; 
  int ret; 
  ret = (list != NULL); 
  ret = ret && position >= 0 && position < list->capacity; 
  ret = ret && list->length < list->capacity; 
  if (ret) 
  { 
    for (i = list->length; i > position; i--) 
    { 
      list->node[i] = (list->node[i - 1]); 
    } 
    list->node[i] = (unsigned int)data; 
    double *p = (double *)data; 
    list->length++; 
  } 
  return ret; 
} 
 
void* seq_list_get(struct seq_list* list, int position) 
{ 
  void* ret = NULL; 
   
  if (list != NULL && position >= 0 && position < list->length) 
  { 
    ret = (void *)list->node[position]; 
  } 
  return ret; 
} 
 
void* seq_list_remove(struct seq_list* list, int position) 
{ 
  void* ret = NULL; 
  int i = 0; 
   
  if (list != NULL && position >= 0 && position < list->length) 
  { 
    int i = 0;  
    ret = seq_list_get(list, position); 
    for (i = position + 1; i < list->length; i++) 
    { 
      list->node[i - 1] = list->node[i]; 
    } 
    list->length--; 
  } 
  return ret; 
} 
 
int seq_list_capacity(struct seq_list* list) 
{ 
  int ret = -1; 
  if (list != NULL) 
  { 
    ret = list->capacity; 
  } 
  return ret; 
} 
 
int seq_list_length(struct seq_list* list) 
{ 
  int ret = -1; 
  if (list != NULL) 
  { 
    ret = list->length; 
  } 
  return ret; 
} 
 
void seq_list_clear(struct seq_list* list) 
{ 
  if (list != NULL) 
  { 
    list->length = 0; 
  } 
} 
 
void seq_list_destroy(struct seq_list* list) 
{ 
  free(list); 
  list = NULL; 
} 


//seq_list_main.c 
#include <stdio.h> 
#include "seq_list.h" 
 
int main(void) 
{ 
  struct seq_list* list = seq_list_create(100); 
 
  double *p = NULL; 
  int ret = 0; 
 
  double a = 1.1; 
  double b = 2.2; 
  double c = 3.3; 
  double d = 4.4; 
  double e = 5.5; 
   
  seq_list_insert(list, 0, &a); 
  seq_list_insert(list, 1, &b); 
  seq_list_insert(list, 2, &c); 
  seq_list_insert(list, 3, &d); 
  seq_list_insert(list, 4, &e); 
 
  printf("list capacity = %d, length = %d\n", seq_list_capacity(list), seq_list_length(list)); 
  p = (double *)seq_list_get(list, 0); 
  if (p != NULL) 
  { 
    printf("%lf\n", *p); 
  } 
   
  p = (double *)seq_list_get(list, 3); 
  if (p != NULL) 
  { 
    printf("%lf\n", *p); 
  } 
 
  p = (double *)seq_list_remove(list, 3); 
  if (p != NULL) 
  { 
    printf("remove data %lf, index at 3 , after length: %d\n", *p, seq_list_length(list)); 
  } 
   
  p = (double *)seq_list_get(list, 3); 
  if (p != NULL) 
  { 
    printf("after remove, index at 3: %lf\n", *p); 
  } 
 
  seq_list_clear(list); 
  printf("after clear, list length is %d\n", seq_list_length(list)); 
 
  seq_list_destroy(list); 
 
  return 0; 
}