数据结构

绪论

数据

数据是描述客观事物的符号，是计算机中可以操作的对象，是能被计算机识别，并输入给计算机处理的符号集合。

数据元素

数据元素是组成数据的，有一定意义的单位，在计算机中通常作为整体处理，也被称为记录。

数据项

数据项是数据不可分割的最小单位，若干个数据项可以组成一个数据元素。

数据对象

数据对象是性质相同的数据元素的组合，是数据的子集。

数据结构

不同的数据元素之间不是独立的，而是存在特定的关系，这种关系就是结构。

数据结构就是相互之间存在一种或多种特定关系的数据元素的集合。

逻辑结构

逻辑结构是指对象中数据元素之间的相互关系。

1. 集合结构
   集合结构就是数据元素除了同属于一个集合外没有其他的关系。
2. 线性结构
   线性结构中的数据元素之间是一对一的关系。
3. 树形结构
   树形结构中的数据元素之间是一对多的层次关系。
4. 图形结构
   图形结构中的数据元素之间是多对多的关系。

物理结构

物理结构是指数据的逻辑结构在计算机中的存储形式。

1. 顺序存储结构
   顺序存储结构意思是把数据元素存放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的。
2. 链式存储结构
   链式存储结构是把数据元素存放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的。

算法

算法是解决特定问题求解步骤的描述，在计算机表现为指令的有限序列，并且每条指令表示一个或多个操作。

算法的特性

1. 输入
2. 输出
3. 有穷性
4. 确定性
5. 可行性

算法设计的要求

1. 正确性
2. 可读性
3. 健壮性
4. 时间效率高和存储量低

算法效率的度量方法

事后统计方法

这种方法主要是通过设计好的测试程序和数据，利用计算机计时器对不同算法编制的程序的运行时间进行比较，从而确定算法效率的高低。

事前分析估算方法

这种方法是在计算机程序编制前依据统计方法对算法进行估算。

推导大O阶方法

1. 用常数1取代运行时间中的所有加法常数
2. 在修改后的运行次数函数中，只保留最高阶项。
3. 如果最高阶项存在且不是1，则去除与这个项目相乘的常数。

以下是一些简单的例子。

//因为运行次数都只是1次，所以为O(1)
	int sum = 0;
	sum = 100*100;

//简单的for循环，循环n次，所以为O(n)
	int i;
	for(i = 0; i < n; i++){
      // O(1)的语句
    }

//count每次与2相乘，故会执行log2n次，O(log2n)
	int count = 1;
	while(count < n){
        count *= 2;
    }

// 两个for循环，每个循环n次，故O(n^2)
	int i,j;
	for(i = 0; i < n; i++){
      for(j = 0; j < n; j++){
          // O(1)的语句
      }
    }
// 两个for循环，一个循环m次一个循环n次，故O(n*m)
	int i,j;
	for(i = 0; i < m; i++){
      for(j = 0; j < n; j++){
          // O(1)的语句
      }
    }
// 两个for循环，一个循环m次，一个每次递减，通过级数之和可得循环了n^2/2+n/2次,故O(n^2)
	int i,j;
	for(i = 0; i < n; i++){
      for(j = i; j < n; j++){
          // O(1)的语句
      }
    }

线性表

线性表的顺序存储结构

线性表的顺序存储结构指的是用一段地址连续的存储单元依次存储线性表的数据元素。

定义存储的结构

# define MAXSIZE 100	// 设置顺序表的最大存储个数
typedef int ElemType;	//存储数据的类型
typedef struct SqList{
    ElemType data[MAXSIZE];
    int length;			//表示顺序表当前长度
}SqList;

获取数据

1. 判断是否为空表。
2. 判断获取数据的下标是否在数组的范围。
3. 获取数组指定位置的数据。

// 时间复杂度为O(1)
int GetElem(SqList L,int i,ElemType *e){
        if(L.length==0)
            return -1;
        if(i-1 < 0 || i > L.length)
            return -1;
        *e = L.data[i-1];
        return 1;  
   }
// -1表示失败，1表示成功

插入数据

1. 判断表是否已经满了。
2. 判断插入的位置是否正确。
3. 判断插入的位置是否在表尾，不在表尾就指定位置之后的数据全部后移一位。
4. 将数据插入指定位置，表长加1。

// 插入的位置在最后，时间复杂度为O(1)
// 插入的位置在最前，时间复杂度为O(n)
int ListInsert(SqList *L,int i,ElemType e){
        int j;
        if(L->length == 0)
            return -1;
        if(i-1 < 0 || i > L->length + 1)
            return -1;
        if(i <= L->length){
            for(j = L->length-1;j >= i-1;j++){
                L->data[j+1] = L->data[j];
            }
        }
        L->data[i-1] = e;
        L->length++;
        return 1;
   }

删除数据

1. 判断表是否为空表
2. 判断删除的位置是否正确。
3. 判断删除的位置是否是最后一位，不是，删除的位置后面的数据全部前移一位。
4. 表长减一。

// 删除的位置在最后，时间复杂度为O(1)
// 删除的位置在最前，时间复杂度为O(n)
int ListDelete(SqList *L,int i){
     	if(L->length == 0)
            return -1;
    	if(i - 1 < 0 || i > L->length)
            return -1;
    	if(i < L->length)
            for(j = i-1;j <= L->length;j++){
                L->data[j] =  L->data[j+1];
            }
    	L->length = -1;
    	return 1;
   }

线性表的链式存储结构

定义存储结构

typedef struct Node {
	int data;
	struct Node *next;
} Node;

获取数据

1. 从头查找，一直找到第i个结点
2. 计数到i就停止，返回数据
3. 没到i链表就结束了，就返回-1

int getElem(Node *L,int i) {
    int j = 1;
    Node *pre = L->next;
    while (pre!=null && j<i) {
		pre = pre->next;
        j++;
    }
    if (pre==null || j>i) {
		return -1;
    }
    return pre->data;
}

插入数据

1. 首先遍历到第i-1个结点

2. 然后创建一个结点，next指向第i个结点

3. 第i-1个结点的next指向新创建的结点

int insert(Node *L,int i,int e) {
    int j = 1;
    Node *pre = L;
    while (pre!=null && j<i) {
		pre = pre->next;
        j++;
    }
    if(pre==null || j>i) {
		return -1;
    }
    Node *p = (Node*)malloc(sizeof(Node));
    p->data = e;
    p->next = pre->next;
    pre->next = p;
    return 1;
}

删除数据

1. 首先遍历到第i-1个结点
2. 第i-1个结点的next指向第i个结点的next
3. 释放第i个结点

int delete(Node *L,int i) {
    int j = 1;
    Node *pre = L;
    while (pre!=null && j<i) {
		pre = pre->next;
        j++;
    }
    if(pre==null || j>i) {
		return -1;
    }
    Node *p = pre->next;
    pre->next = p->next;
    free(p);
    return 1;
}

树

• 结点拥有的子树数称为结点的度，度为0称为叶结点，树的度是整个树度的最大值
• 树中结点的最大层次称为树的深度或高度
• 如果树中的结点的各个子树看成从左到右是有次序的，就称为有序树，反之为无序树

定义二叉树存储结构

typedef struct BiTree{
    TElemType data;
    struct BiTree *lchild,*rchild;
}BiTree;

二叉树的遍历

• 前序遍历
  先访问根节点，然后前序遍历左子树，再前序遍历右子树。
• 中序遍历
  先中序遍历左子树，然后访问根节点，再中序遍历右子树。
• 后序遍历
  先后序遍历左子树，再后序遍历右子树，然后再访问根结点。
• 层序遍历
  从上到下，从左到右的顺序访问结点。

创建二叉树

1. 输入根节点数据
2. 递归创建左子树，递归创建右子树

void CreaterBiTree (BiTree *T){
    char ch;
    scanf("%c",&ch);
    if ('#' == ch) {
        T = NULL;
        return;
    } else {
        T = (BiTree*) malloc(sizeof(BiTree));
        T->data = ch;
        CreaterBiTree(T->lchild);
        CreaterBiTree(T->rchild);
    }
}

BiTree* CreaterBiTree (){
    BiTree * T = (BiTree*) malloc(sizeof(BiTree));
    char ch;
    scanf("%c",&ch);
    if ('#' == ch) {
        T = NULL;
        return;
    } else {
        T->data = ch;
        T->lchild = CreaterBiTree();
        T->rchild = CreaterBiTree();
    }
}

前序遍历

1. 判断是否为空结点
2. 打印根节点数据，递归左子树，递归右子树

void PreOrderTraverse (BiTree* T){
    if(NULL == T){
        return;
    }
    printf("%d",T->data);
    PreOrderTraverse(T->lchild);
    PreOrderTraverse(T->rchild);
}

中序遍历

1. 判断是否为空结点
2. 递归左子树，打印根节点数据，递归右子树

void InOrderTraverse (BiTree* T){
    if(NULL == T){
        return;
    }
    InOrderTraverse(T->lchild);
    printf("%d",T->data);
    InOrderTraverse(T->rchild);
}

后序遍历

1. 判断是否为空结点
2. 递归左子树，递归右子树，打印根节点数据

void PostOrderTraverse (BiTree* T){
    if(NULL == T){
        return;
    }
    PostOrderTraverse(T->lchild);
    PostOrderTraverse(T->rchild);
    printf("%d",T->data);
}

层次遍历

typedef struct queue {
	int front,rear;
	BiTree* data[20];
	
}queue;
//初始化队列
queue* initqueue() {
	queue* q = (queue*)malloc(sizeof(queue));
	q->front = 0;
	q->rear = 0;
}
//判断队列是否为空
int emptyqueue(queue* q) {
	if(q->rear==q->front)
		return 1;
	else
		return 0;
}
//出队
bitree* dequeue(queue* q) {
	return q->data[(q->front)++];
}
//入队 
void inqueue(queue* q,BiTree* root) {
	if(q->rear==19)
		return;
	else
		q->data[(q->rear)++]=root;
}
void levorder(BiTree* root,queue* q) {
	BiTree *p;
	p = root;
	if(p!=NULL)
		inqueue(q,p);
	while(!emptyqueue(q)){
		p = dequeue(q);
		printf("%d",p->data);
		if(p->lchild!=NULL)
			inqueue(q,p->lchild);
		if(p->rchild!=NULL)
			inqueue(q,p->rchild);
	 } 
}

性质

• 知道前序遍历的顺序和中序遍历的顺序可以确定一颗二叉树
• 知道中序遍历的顺序和后序遍历的顺序可以确定一颗二叉树
• 知道前序序遍历的顺序和后序遍历的顺序是不可以确定一颗二叉树的