//顺序表的实现--静态分配

#include<stdio.h>
#define MaxSize 10   //定义表的最大长度 
typedef struct{
	int data[MaxSize];//用静态的"数组"存放数据元素
	int length; //顺序表的当前长度  
}SqList;        //顺序表的类型定义（静态分配方式） 
void InitList(SqList &L){
	 for(int i=0;i<MaxSize;i++){
	 	L.data[i]=0;  //将所有数据元素设置为默认初始值
		  
	 }
	 L.length=0;
}
int main(){
	SqList L;//声明一个顺序表
	InitList(L);//初始化一个顺序表
	for(int i=0;i<MaxSize;i++){
		printf("data[%d]=%d\n",i,L.data[i]);
	}
	return 0; 
}

2.2.2动态分配

//顺序表的实现——动态分配
#include<stdio.h>
#include<stdlib.h>//malloc、free函数的头文件 
#define InitSize 10 //默认的最大长度
typedef struct{
	int  *data;//指示动态分配数组的指针
	int MaxSize; //顺序表的最大容量
	int length;  //顺序表的当前长度 
}SeqList; 
//初始化
void InitList(SeqList &L){
	//用malloc 函数申请一片连续的存储空间
	L.data =(int*)malloc(InitSize*sizeof(int)) ;
	L.length=0;
	L.MaxSize=InitSize;
} 
//增加动态数组的长度
void IncreaseSize(SeqList &L,int len){
	int *p=L.data;
	L.data=(int*)malloc((L.MaxSize+len)*sizeof(int));
	for(int i=0;i<L.length;i++){
		L.data[i]=p[i];   //将数据复制到新区域 
	}
	L.MaxSize=L.MaxSize+len; //顺序表最大长度增加len
	free(p);  //释放原来的内存空间 
	
} 
int main(void){
	SeqList L; //声明一个顺序表
	InitList(L);//初始化顺序表
	IncreaseSize(L,5);
	return 0; 
}

顺序表的特点：

随机访问，可以在O(1)时间内找到第i个元素。
存储密度高，每个节点只存储数据元素
拓展容量不方便
插入、删除操作不方便，需要移动大量元素

2.3顺序表的基本操作

1.插入操作：平均时间复杂度O(n)

bool ListInsert(SqList &L, int i, int e){ 
    //判断i的范围是否有效
    if(i<1||i>L.length+1) 
        return false;
    if(L.length>MaxSize) //当前存储空间已满，不能插入  
        return false;

    for(int j=L.length; j>=i; j--){    //将第i个元素及其之后的元素后移
        L.data[j]=L.data[j-1];
    }
    L.data[i-1]=e;  //在位置i处放入e
    L.length++;      //长度加1
    return true;
}

2.删除操作：平均时间复杂度O(n)

bool LisDelete(SqList &L, int i, int &e){ // e用引用型参数 
    //判断i的范围是否有效
    if(i<1||i>L.length) 
        return false;

    e = L.data[i-1]    //将被删除的元素赋值给e

    for(int j=L.length; j>=i; j--){    //将第i个后的元素前移
        L.data[j-1]=L.data[j];
    }
    L.length--;      //长度减1
    return true;
}

3.按位查找(获取L表中第i个位置的值)：平均时间复杂度O(1)

#define MaxSize 10            //定义最大长度 
typedef struct{
    ElemType data[MaxSize];  //用静态的“数组”存放数据元素 
    int Length;              //顺序表的当前长度
}SqList;                     //顺序表的类型定义

ElemType GetElem(SqList L, int i){
    // ...判断i的值是否合法
    return L.data[i-1];      //注意是i-1
}

4.按值查找：平均时间复杂度O（n）

#define InitSize 10            //定义最大长度 
typedef struct{
    ElemTyp *data;  //用静态的“数组”存放数据元素 
    int Length;              //顺序表的当前长度
}SqList;   

//在顺序表L中查找第一个元素值等于e的元素，并返回其位序
int LocateElem(SqList L, ElemType e){
    for(int i=0; i<L.lengthl i++)
        if(L.data[i] == e)  
            return i+1;     //数组下标为i的元素值等于e，返回其位序i+1
    return 0;               //推出循环，说明查找失败
}

第三章：栈和队列

3.1栈（stack）

1.栈的定义

栈是特殊的线性表：只允许在一端进行插入或删- 除操作，其逻辑结构与普通线性表相同；
栈顶（Top）：允许进行插入和删除的一端（最上面的为栈顶元素）；
栈底（Bottom）：固定的，不允许进行插入和删除的一端（最下面的为栈底元素）；
空栈：不含任何元素的空表；
特点：后进先出（后进栈的元素先出栈）；
缺点：栈的大小不可变，解决方法——共享栈；

2.栈的基本操作

“创建&销毁”

InitStack(&S) 初始化栈：构造一个空栈S，分配内存空间；
DestroyStack(&S) 销毁栈：销毁并释放栈S所占用的内存空间；
“增&删”

Push(&S, x) 进栈：若栈S未满，则将x加入使其成为新栈顶；
Pop(&S, &x) 出栈：若栈S非空，则弹出（删除）栈顶元素，并用x返回；
“查&其他”
GetTop(S, &x) 读取栈顶元素：若栈S非空，则用x-返回栈顶元素；（栈的使用场景大多只访问栈顶元素）；
StackEmpty(S) 判空：断一个栈S是否为空，若S为空，则返回true,否则返回false；

3.2队列（Queue）

1. 队列的基本概念

1.定义：队列（Queue）简称队，是一种操作受限的线性表，只允许在表的一端进行插入，而在表的另一端进行删除。
2.特点

队列是操作受限的线性表，只允许在一端进行插入 (入队)，另一端进行删除 (出队)
操作特性：先进先出 FIFO
队头：允许删除的一端
队尾：允许插入的一端
空队列：不含任何元素的空表

2.队列的基本操作

“创建&销毁”
InitQueue(&Q): 初始化队列，构造一个空列表Q
DestroyQueue(&Q): 销毁队列，并释放队列Q所占用的内存空间
“增&删”
EnQueue(&Q, x): 入队，若队列Q未满，将x加入，使之成为新的队尾
DeQueue(&Q, &x): 出队，若队列Q非空，删除队头元素，并用x返回
“查&其他”
GetHead(Q,&x): 读队头元素，若队列Q非空，则将队头元素赋值给x
QueueEmpty(Q): 判队列空，若队列Q为空，则返回

3.队列的顺序存储结构

队头指针：指向队头元素
队尾指针：指向队尾元素的下一个位置
队列存储的基本操作

//队列的顺序存储类型
# define MaxSize 10;     //定义队列中元素的最大个数
typedef struct{
    ElemType data[MaxSize];   //用静态数组存放队列元素
                              //连续的存储空间，大小为——MaxSize*sizeof(ElemType)
    int front, rear;          //队头指针和队尾指针
}SqQueue;

//初始化队列
void InitQueue(SqQueue &Q){
    //初始化时，队头、队尾指针指向0
    Q.rear = Q.front = 0;
}

void test{
    SqQueue Q;                //声明一个队列
    InitQueue(Q);
    //...
}

// 判空
bool QueueEmpty(SqQueue 0){
    if(Q.rear == Q.front)    //判空条件后
        return true;
    else 
        return false;
}