线性表

Posted by Joel on April 19,2018

线性表

存取结构与存储结构

存储结构：逻辑结构在计算机中的映射。

存取结构：在一个数据结构上对查找操作性能的描述，通常有两种存取结构：

  1. 随机存取：进行查找的时间复杂度为Ø(1)，查找任意一个元素的时间为常数。
  2. 顺序存取：进行查找的时间复杂度为Ø(n)，与位置有关。

顺序存储结构的C语言描述

ps: 有可能题目中会要求写出数据结构的定义，所以数据比较好

静态分配

1
2
3
4
5
#define INIT_SIZE 100
typedef struct {
    int data[INIT_SIze];
    int length;
} staticSqList;

缺点：长度不能再改变。

动态分配

1
2
3
4
5
6
7
8
9
10
#define INIT_SIZE 50
typedef struct {
    int *data;
    int length;
    int maxLength
} dynamicSqList;
// 使用时

dynamicSqList *L;
L->data = (int*)malloc(sizeof(int) * INIT_SIZE)

存储结构C语言描述

单链表

1
2
3
4
typedef struct LNode {
    int data;
    struct LNode *next;
} LNode, LinkList;

双链表

1
2
3
4
5
typedef struct DNode {
    int data;
    struct DNode *prev;
    struct DNode *next;
} DNode, DLinkList;

EOF

FEATURED TAGS
FRIENDS
>