数据结构与算法

• 概述
• 常见数据结构

 
#define LIST_INIT_SIZE 100 
#define LIST_INCREMENT 50 

struct SqList 
{
    /* data */
    ElemType* elem; // addr 
    int length; //当前长度
    int listsize; //容量，最大可存长度，以sizeof(ElemType)为单位 
};

 
这种结构是与存储结构一一对应的，比如elem是一个指针/地址数据，就是一个地址，
后面跟两个int类型的数据，
看到这个结构，脑海中要想到它在计算机中是如何存储的，
- 数据类型是什么
- 占多少个字节

也就是说，逻辑结构与存储结构是分不开的，具有强关联
    

 
计算方法 
计算 数据 的方法 
计算机 计算 数据 的方法 

这个数据指计算机中的数据，这个方法也是计算机中的方法 

 
计算机中的数据是什么？
最底层由0与1组成，大致分为整数，小数，总之，就是 数/数字/数值  

1,2,3,0.1,0.3 等等都是计算机中的数，也是数据 

 
三角形结构，就是三条线段首尾相连形成的结构
线，大马路左拐右拐，连通两个地方，这两个地方之间就是线型/线性结构
树，一根线有很多枝
    
一类事物都能抽象出一个结构出来，比如人体结构，树的结构，道路的结构
万物有类别，有结构，对应哲学上那句“万物有特性，也有共性”
这里用线来描绘万物的共性，就跟用画描绘世界差不多，画的就是这世界的结构... 

结构是一个事物抽象出来的虚拟线性框架
(不是线也行，比如断续的点或其他的,比如泼墨也能出画，但线可以表示这个....
线 是一种表示方法上，但不是唯一表示结构的方法)

了解了一类事物的结构，就容易抓住其本质/把握其规律

 
计算机可以模拟/表述世界，比如，声音，图像，影视等，
这些也叫数据
这些数据对应着现实世界的人与物

这些数据在计算机中有 “结构”：主要有

物理结构：静态存储结构，断电也还在
逻辑结构：内存中的结构，断电就没了

 
1. 数组（Array）
2. 链表（Linked List）
3. 栈（Stack）
4. 队列（Queue）
5. 树（Tree）
6. 图（Graph）
7. 哈希表（Hash Table）
8. 堆（Heap）
    

链式队列 C语言

link.h

 
#ifndef LINK_H 
#define LINK_H
#define ERROR_VALUE -2147483648  //使用Int最小值做为错误处理

//结点结构体
struct Node{
    int data;             //数据域
    struct Node* next;     //指针域
};

//链式队列结构体
typedef struct LQ{
    int size;            //队列大小
    struct Node out;     //头结点,本身data不存储数据，仅使用其next，其next永远指向队列的第一个节点
    struct Node* in;     //尾结点指针,指向队列最后一个节点，其数据就是队列最后一个节点的数据 
    
}LkQueue, *LinkQueue;    //定义两个类型，一个LQ结构体，一个LQ结构体指针



LinkQueue init_lq(){
    //创建队列结构体
    LkQueue* myQueue = (LkQueue*)malloc(sizeof(LkQueue));
    
    if (!myQueue){
        return NULL;
    }
    
    //初始化队列长度
    myQueue->size = 0;
    
    //初始化队列头指针的指针域
    myQueue->out.next = NULL;
    myQueue->in = &myQueue->out;
    
    return myQueue;
}

void push_lq(LinkQueue queue, int data){

    if (!queue){
        printf("队列未初始化\n");
        return;
    }
    
    //创建新结点
    struct Node * newNode = (struct Node *)malloc(sizeof(struct Node));
    if (!newNode){
        return;
    }
    
    newNode->data = data;
    
    //更新指针的指向
    
    queue->in->next = newNode;  //新节点追加到队列尾节点的next上,首先执行就是out->next = newNode
    newNode->next = NULL;       //newNode成为新的尾节点，其next为NULL
    queue->in = newNode;        //队列的尾节点后移一位 

    queue->size++;
    
}


int pop_lq(LinkQueue queue){
    int data = ERROR_VALUE;
    
    if (!queue){
        return data;
    }
    
    if (queue->size == 0){
        printf("空队，无法出队\n");
        return data;
    }
    
    //记录第一个结点
    struct Node* pFirst = queue->out.next;
    
    //更新指针的指向
    queue->out.next = pFirst->next;
    
    //队列中只有一个结点的时候，再出队会影响尾指针，需要特判
    if (queue->size == 1){
        queue->in = &queue->out; //相当于队列空了，没有数据了 
    }
    
    queue->size--;

    //判断结点存在并释放结点
    if (pFirst){
        data = pFirst->data;
        free(pFirst);
    }
    return data; 
}

#endif

main.c

 
#include <stdio.h>
#include <stdlib.h>
#include "link.h"

int main(){

    LinkQueue q =  init_lq();
    push_lq(q,11);
    push_lq(q,12);
    push_lq(q,13);

    printf("query size = %d\n",q->size);

    int data = pop_lq(q);
    printf("res1 = %d\n",data);
    printf("query size = %d\n",q->size);

    data = pop_lq(q);
    printf("res2 = %d\n",data);

    data = pop_lq(q);
    printf("res3 = %d\n",data);
    return 0;
}
            

优化队列

 
可以用数组来实现链式队列，
两个指针在有效数据的两端，控制开始结束的位置 

参考

    C语言-队列 
    顺序队列详解（C语言实现）