线性结构

线性表（Linear List）

由同类型的数据元素构成的有序序列的线性结构

  1. 元素个数称为线性表的长度
  2. 线性表没有元素时，称为空表
  3. 表的起始位置称为表头，表的结束位置称为表尾

###有序线性表

抽象数据类型（ADT）

createNewList(*list)//创建新的线性表
makeListEmpty(*list)//将线性表置空
isEmpty(list)//判断是否为空
getElement(position,list)//获取某个位置的元素    
locateElement(value,list)//获取某个值所在的位置
listInsertValue(value,position,list)//将某个值插入到某个位置
listDeleteElement(position,list)//将某个位置的元素删除
listLength(list)//获取线性表的长度

有序线性表结构原型

typedef struct
{
    elementType arry[maxSize];
    int currentPosition;//当前所在位置（当前长度）
    
}List;

线性表的链式存储

不要求逻辑上相邻的两个元素在物理上也相邻，插入删除不需要移动数据元素，只需要修改链

结构原型

typedef struct
{
    int value;
    strcut List *next;
}List;

抽象数据类型(ADT)

listLength(list)//求表长
listFindPosition(list,position)//求某个位置的元素
listFindValue(list,value)//查找某个值，返回指针
listInsertNode(list,position)//将节点插入到某个位置
listDeleteNode(list,position)//删除节点

广义表(多重链表)

  1. 是线性表的推广
  2. 线性表的n个元素都是基本的单元素
  3. 广义表中，不仅可以是单元素，也可以是另一个广义表

结构原型

typedef struct
{
    int flag;//用作标记，0为单元素，1为广义表
    union
    {
        listType value;
        struct List *gNext;
    }gList;
    struct List *next;
}List;

多重链表的指针域有多个，包含两个指针域的链表不一定是多重链表，比方说双向链表

栈（stack）

栈(stack)，遵循后入先出，先进后出（Last In First Out----LIFO）的基本原则

栈顶为最上面的元素，即最后插入的元素

栈底为最底下的元素，即最先插入的元素

抽象数据类型（ADT）

push()//入栈，添加数据
pop()//出栈，删除并返回栈顶数据
createStack()//创建空栈
stackIsFull()//是否已满
stackIsEmpty()//是否为空

堆栈原型

typedef struct
{
    int top;//栈顶
    elementType arry[maxSize];//最大元素个数的数组
}stack;

栈

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>

#define maxSize 10
typedef struct
{
    int pos;
    int a[maxSize];
} stack;

void creatStack(stack *p)
{
    p->pos = -1;
}

bool stackIsFull(stack *p)
{
    if (p->pos == maxSize - 1)
        return true;
    return false;
}

void push(stack *p)
{
    printf("input value:");
    int n;
    scanf("%d", &n);
    if (stackIsFull(p))
    {
        printf("stack is full");
        return;
    } else
    {
        p->a[++(p->pos)] = n;
    }
}

bool stackIsEmpty(stack *p)
{
    if (p->pos == -1)
        return true;
    return false;
}

void pop(stack *p)
{
    if (stackIsEmpty(p))
    {
        printf("Stack is empty");
        return;
    }
    printf("\n%d", p->a[(p->pos)--]);
}

int main()
{
    stack list;
    creatStack(&list);
    for (int i = 0; i < 10; i++)
    {
        push(&list);
    }
    push(&list);
    for (int i = 0; i < 10; i++)
    {
        pop(&list);
    }
    pop(&list);
    return 0;
}

第二种链表实现栈

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>

#define maxSize 10
typedef struct
{
    int value;
    struct stack *next;
} stack;
bool stackIsFull(stack *p)
{
    int cnt = 0;
    for (; p; p = p->next)
        cnt++;
    return cnt > maxSize - 1;
}

stack *push(stack *p, int n)
{
    if (stackIsFull(p))
    {
        puts("errrors");
        return p;
    }
    stack *temp = malloc(sizeof(stack));
    temp->value=n;
    temp->next=p;
    puts("success");
    return temp;
}
bool stackIsEmpty(stack *p)
{
    return p==NULL;
}
stack *pop(stack *p)
{
    if(stackIsEmpty(p))
    {
        puts("stack is empty");
        return p;
    }
    stack *c=p;
    printf("%d",c->value);
    p=p->next;
    free(c);
    return p;
}
int main()
{
    stack *a=NULL;
    for(int i=0;i<11;i++)
    {
        int n;
        scanf("%d",&n);
        a=push(a,n);
    }
    for(int i=0;i<13;i++)
    {
        a=pop(a);
    }
    return 0;
}

#队列(queue)

概念

只允许在其中一端插入数据，另一端删除数据的线性表

插入数据称为入队

删除数据称为出队

遵循先入先出（First In First Out）FIFO

**空队列：**是指没有任何元素的队列

**队头：**允许删除元素的一端，靠近队头的第一个元素称为队头元素

**队尾：**允许插入数据的一端，靠近队尾的最后一个元素称为队尾元素

抽象数据类型

createQueue()//创建一个队列 并初始化
freeQueue()//销毁队列
enterQueue()//入队
deQueue()//出队，并删除队头元素
readQueue()//读取队头元素
queueIsEmpty()//队列是否为空

队列的顺序实现

方法1-浪费一个存储空间

#include <stdio.h>
#include<stdbool.h>
#include <stdlib.h>

#define maxSize 10
typedef struct
{
    int a[maxSize];
    int front, rear;
} queue;

bool isEmpty(queue *p)
{
    if (p->front == p->rear)
        return true;
    return false;
}

void createQueue(queue *p)
{
    p->rear = p->front = 0;
}

bool isFull(queue *p)
{
    return (p->rear + 1) % maxSize == p->front % maxSize;//因为判断为空的条件是尾部的值等于头部的，只能牺牲一个元素作为判断是否已满的条件
}

bool enQueue(queue *p, int n)
{
    if (isFull(p))
        return false;
    p->a[p->rear] = n;
    p->rear = (p->rear + 1) % maxSize;
    return true;
}

bool deQueue(queue *p, int *e)
{
    if (isEmpty(p))
        return false;
    *e = p->a[p->front];
    p->front = (p->front + 1) % maxSize;
    return true;
}

bool readHead(queue *p)
{
    if (isEmpty(p))
        return false;
    printf("%d", p->a[p->front]);
    return true;
}
int queueSize(queue p)
{
    return (p.rear+maxSize-p.front)%maxSize;
}
int main()
{
    queue qu;
    createQueue(&qu);
    if (isEmpty(&qu))
        puts("yes");
    for (int i = 0; i < 12; i++)
    {
        int n;
        scanf("%d", &n);
        if (enQueue(&qu, n))
            printf("success\n");
        else
            printf("error\n");
    }
    printf("\n\n\n\n");
    if(readHead(&qu))
        printf("read success\n");
    else
        printf("read error\n");
    for (int i = 0; i < 12; i++)
    {
        int n;
        if (deQueue(&qu, &n))
        {
            printf("success\n");
            printf("%d\n", n);
            printf("len=%d\n",queueSize(qu));
        } else
            printf("error\n");
    }
    return 0;
}

第二种-不浪费一个存储空间

#include <stdio.h>
#include<stdbool.h>
#include <stdlib.h>

#define maxSize 10
typedef struct
{
    int a[maxSize];
    int front, rear,size;
} queue;

bool isEmpty(queue *p)
{
    if (p->front == p->rear)
        return true;
    return false;
}

void createQueue(queue *p)
{
    p->size=0;
}

bool isFull(queue *p)
{
    return p->size==maxSize;
}

bool enQueue(queue *p, int n)
{
    if (isFull(p))
        return false;
    p->a[p->rear] = n;
    p->rear = (p->rear + 1) % maxSize;
    p->size++;
    return true;
}

bool deQueue(queue *p, int *e)
{
    if (isEmpty(p))
        return false;
    *e = p->a[p->front];
    p->front = (p->front + 1) % maxSize;
    p->size--;
    return true;
}

bool readHead(queue *p)
{
    if (isEmpty(p))
        return false;
    printf("%d", p->a[p->front]);
    return true;
}
int queueSize(queue p)
{
    return (p.rear+maxSize-p.front)%maxSize;
}
int main()
{
    queue qu;
    createQueue(&qu);
    if (isEmpty(&qu))
        puts("yes");
    for (int i = 0; i < 12; i++)
    {
        int n;
        scanf("%d", &n);
        if (enQueue(&qu, n))
            printf("success\n");
        else
            printf("error\n");
    }
    printf("\n\n\n\n");
    if(readHead(&qu))
        printf("read success\n");
    else
        printf("read error\n");
    for (int i = 0; i < 12; i++)
    {
        int n;
        if (deQueue(&qu, &n))
        {
            printf("success\n");
            printf("%d\n", n);
            printf("len=%d\n",queueSize(qu));
        } else
            printf("error\n");
    }
    return 0;
}

链式队列

带头节点

#include <stdio.h>
#include<stdbool.h>
#include <stdlib.h>

#define maxSize 10
typedef struct queue
{
    int value;
    struct queue *next;
} queue;
typedef struct
{
    queue *front, *rear;
} linkQueue;

void create(linkQueue *pp)
{
    pp->front = pp->rear = malloc(sizeof(linkQueue));
    pp->front->next = NULL;
}

bool isEmpty(linkQueue *p)
{
    if (p->front == p->rear)
        return true;
    return false;
}

bool enQueue(linkQueue *p)
{
    queue *n = malloc(sizeof(queue));
    scanf("%d", &n->value);
    n->next = NULL;
    p->rear->next = n;
    p->rear = n;
    return true;
}

bool deQueue(linkQueue *p)
{
    if (isEmpty(p))
        return false;
    queue *t = p->front->next;
    printf("%d ", t->value);
    p->front->next = t->next;
    if(p->rear==t)
        p->front=p->rear;
    free(t);
    return true;
}

int main()
{
    linkQueue qu;
    create(&qu);
    for (int i = 0; i < 5; i++)
        enQueue(&qu);
    for (int i = 0; i < 6; i++)
    {
        if (deQueue(&qu));
        else
            printf("error\n");
    }

    return 0;
}

不带头节点

#include <stdio.h>
#include<stdbool.h>
#include <stdlib.h>

#define maxSize 10
typedef struct queue
{
    int value;
    struct queue *next;
} queue;
typedef struct
{
    queue *front, *rear;
} linkQueue;

void create(linkQueue *pp)
{
    pp->front = NULL;
    pp->rear = NULL;
}

bool isEmpty(linkQueue *p)
{
    if (p->front == NULL)
        return true;
    return false;
}

bool enQueue(linkQueue *p)
{
    queue *n=malloc(sizeof(queue));
    n->next=NULL;
    scanf("%d", &n->value);
    if(isEmpty(p))//因为此时的rear和front都为空，要使rear始终位于最后一个元素，所以要特殊处理
    {
        p->rear=n;
        p->front=n;
    }
    p->rear->next=n;
    p->rear=n;
    return true;
}

bool deQueue(linkQueue *p)
{
    if (isEmpty(p))
        return false;
    queue *t=p->front;
    printf("%d ",t->value);
    p->front=t->next;
    free(t);
    return true;
}

int main()
{
    linkQueue qu;
    create(&qu);
    for (int i = 0; i < 5; i++)
        enQueue(&qu);
    for (int i = 0; i < 16; i++)
    {
        if (deQueue(&qu));
        else
            printf("error\n");
    }

    return 0;
}

双端队列

可以从两端进行插入删除，只要是栈能实现的功能，双端队列都能实现

也分为输入受限队列和输出受限队列

即一端只能插入或者删除，另一端可以同时插入删除

Q.E.D.

念念不忘，必有回响。