现在的位置: 首页 > 综合 > 正文

《自己整理数据结构总复习》

2017年12月20日 ⁄ 综合 ⁄ 共 5227字 ⁄ 字号 评论关闭

 

 

总复习

二分搜索(写代码)(查找算法

快速排序,归并排序,排序,希尔排序等等(各种排序算法特性比较)

赫夫曼Huffman编码算法

计算器栈

最短路径:图算法

的遍历(二叉搜索树)

AVL树,红黑树,B树

散列表(Hash表)

链表,栈,队列的实现。

AVL树

数据库:B树

文件压缩:Huffman算法

简单的基础的二叉搜索树的代码(编译器表达式树)

 

 

 

 

 

大整数类 和 高精度计算

问题: 纯数字的字符串加法。

 

 

红黑树 - RB-tree

《教你彻底了解红黑树 - CSDN博客》

http://blog.csdn.net/v_JULY_v/article/details/6105630

红黑树:平衡检索二叉树

其统计性能好于一般的二叉树。

 

 

 

 

 

 

 

 

———————————————————————————————————————

http://blog.csdn.net/jsh13417/article/details/8453949

 

通常来说,决定采用何种方式来检索数据是非常重要的,这样便于以后对数据检索时,数据会按照何种的方式顺序输出。栈是用于检索数据的一种常用方式。

栈的一种显著的特征就是它按照后进先出(LIFO)的方式存储和删除数据元素。这就是说,最后一个存入栈中的元素将会被第一个删除。我们可以看下图的表示;

栈的实现方法有2种,一种是顺序栈,一种是链式栈;

下面先介绍下顺序栈的定义和实现(以前写过的代码):

[html] view plaincopyprint?

 

#defineN 8 

  

typedefint datatype; 

  

typedefstruct 

    datatypedata[N]; 

    inttop; 

}seqstack; 

10   

11 seqstack*CreateSeqstack() 

12 

13     seqstack*s; 

14       

15     s =(seqstack *)malloc(sizeof(seqstack)); 

16     s->top =-1; 

17   

18     returns; 

19 

20   

21 intEmptySeqstack(seqstack *s) 

22 

23     return(-1 ==s->top); 

24 

25   

26 intFullSeqstack(seqstack *s) 

27 

28     return(N-1 ==s->top); 

29 

30   

31 voidClearSeqstack(seqstack *s) 

32 

33     s->top =-1; 

34 

35   

36 voidPushSeqstack(seqstack *s, datatype x) 

37 

38     s->data[++s->top] = x; 

39   

40     return; 

41 

42   

43 datatypePopSeqstack(seqstack *s) 

44 

45     returns->data[s->top--]; 

46 

47   

48 datatypeGetTop(seqstack *s) 

49 

50     returns->data[s->top]; 

51 

52   

53 intmain() 

54 

55     inti; 

56     seqstack*s; 

57   

58     s = CreateSeqstack(); 

59     for(i=1;i<=10; i++) 

60     { 

61         if( ! FullSeqstack(s) )  

62             PushSeqstack(s,i); 

63         else  

64             printf("stackis full\n"); 

65     } 

66   

67     while( ! EmptySeqstack(s) ) 

68     { 

69         printf("%d", PopSeqstack(s)); 

70     } 

71     printf("\n"); 

72   

73     return0; 

74 

链式栈的定义和实现:

    前面已经对单链表的实现进行分析过程可以参照博客中单链表部分,栈的结构体的定义和链表是一样的,在初始化和销毁可以直接调用单链表的实现方法。这种方法是栈具有多态性。多态是面向对象的一种特性,她允许某种类型的对象或者变量在使用时用其他的类型的对象进行代理。这就说,除了使用栈本身的操作完,还可以使用链表的操作。这是因为栈本身就是一种链表,它和链表有相同的特性,很多时候可以像链表一样使用它。

    下面是链式栈的定义和实现的过程,

[html] view plaincopyprint?

 

75 /*stack.h*/ 

76 #ifndefSTACK_H 

77 #defineSTACK_H 

78   

79 #include <stdlib.h> 

80   

81 #include"list.h" 

82   

83 typedefList Stack; 

84   

85 #definestack_init list_init 

86 #definestack_destroy list_destory 

87 intstack_push(Stack *stack, const void *data); 

88 intstack_pop(Stack *stack,void *data); 

89   

90 #definestack_peek(stack)    ((stack)->head == NULL ? NULL:(stack)->head->data) 

91 #definestack_size   list_size 

92   

93 #endif 

 

[html] view plaincopyprint?

 

94 /*stack.c*/ 

95   

96 #include <stblib.h> 

97 #include"../include/list.h" 

98 #include"../include/stack.h" 

99   

100 /*stack_push*/ 

101 intstack_push(Stack * stack, const void * data) 

102 

103     returnlist_ins_next(stack, NULL, const void * data) 

104   

105 

106   

107 /*stack_pop*/ 

108 intstack_pop(Stack * stack, void * data) 

109 

110      returnlist_rem_next(stack, NULL, void * data) 

111 

 

 

队列

http://blog.csdn.net/jsh13417/article/details/8455175

 

队列的一个显著的特征正好的和栈是相反的,它是按照先进先出(FIFO)的方式存储和检索元素,这就是说,对线插入队列的要先删除。还有就是队列是限制在两端进行插入和删除操作的线性表,允许进行存入操作的一端就叫“队尾”,允许进行删除操作的就是“对头”。当线性表中没有元素时,称为“空队“。那么,我们可以吧队列想象地理解成银行办理业务的一队人。

  下面介绍顺序队列的定义和实现(以前写的代码)

[csharp] view plaincopyprint?

 

/*sequeue.h*/ 

#defineN 8 

  

typedef int datatyde; 

typedef struct { 

    datatydedata[N]; 

    int front,rear; 

 }sequeue; 

  

10 sequeue*Createsequeue(); 

11 int Emptysequeue(sequeue *sq); 

12 int Fullsequeue(sequeue *sq); 

13 void Clearsequeue(sequeue *sq); 

14 void Ensequeue(sequeue *sq,datatydex); 

15 datatydeDesequeue(sequeue *sq); 

[csharp] view plaincopyprint?

 

16 /*sequeue.c 

17 #include"sequeue.h" 

18 #include<stdio.h> 

19 #include<stdlib.h> 

20   

21   

22   

23 sequeue*Createsequeue() 

24 

25     sequeue*sq; 

26     sq=(sequeue*)malloc(sizeof(sequeue)); 

27   sq->  front = sq -> rear=0; 

28     return sq; 

29 

30   

31 int Emptysequeue(sequeue *sq) 

32 

33     return (sq -> front == sq -> rear); 

34 

35 int Fullsequeue(sequeue *sq) 

36 

37     return ((sq -> rear+1)%N == sq -> front); 

38 

39 void Clearsequeue(sequeue *sq) 

40 

41    sq-> front = sq -> rear; 

42     return

43 

44 void Ensequeue(sequeue *sq,datatyde x) 

45 

46     sq-> rear = (sq -> rear+1) % N; 

47     sq-> data[sq -> rear]=x; 

48 

49   

50 datatydeDesequeue(sequeue *sq) 

51 

52   sq-> front = (sq -> front + 1) % N; 

53  return (sq ->data[sq -> front]); 

54 

下面是链式队的定义和实现

 队列的定义的和实现和栈的定义和实现差不多。好多函数接口在单链表定义的时候已经实现,具体可以参照单链表的实现和定义。单链表博客链接:点击打开链接

   

[csharp] view plaincopyprint?

 

55 /*queue.h*/ 

56  

57 #ifndefQUEUE_H 

58 #defineQUEUE_H 

59  

60 #include<stdlib.h> 

61 #include"list.h" 

62   

63 /*inplementas linked lists */ 

64 typedefList Queue; 

65   

66 /*Publicinerface */ 

67 #definequeue_init list_init   

68 #definequeue_destroy list_destory   

69   

70 int queue_enqueue(Queue *queue,const void *data); 

71 int queue_dequeue(Queue *queue,void *data); 

72 #definequeue_peek(queue)  ((queue) ->head == NULL? NULL:(queue)->head->data) 

73 #definequeue_size list_size 

74  

75 #endif 

 

[csharp] view plaincopyprint?

 

76 /*queue.c*/ 

77  

78 #include<stdlib.h> 

79  

80 #include"../include/list.h" 

81 #include"../include/queue.h" 

82   

83 /*queue_enqueue*/ 

84 int queue_enqueue(Queue * queue, const void * data) 

85 

86     return list_ins_next(queue, list_tail(queue), data); 

87 

88   

89 /*queue_dequeue*/ 

90 int queue_dequeue(Queue * queue, void * data) 

91 

92     return list_rem_next(queue, NULL, data); 

93 

 

 

 

抱歉!评论已关闭.