从顺序表到链表再到队列和栈

1.顺序表       

        顺序表，简单的说，就是一种用结构体储存的数组。只是一般顺序表还有着记录存入数据个数size和数组总空间位置个数capacity

        我们要定义一个顺序表的结构体，就要先确定顺序表的储存的数据，然后假设数组是固定长度，就使用定长数组来存储数据，否则使用长度变化的动态数组。这里我们只介绍长度动态变化的数组。

typedef int DataType;
typedef struct SqList
{DataType* arr;  //储存所有数据的数组int size;       //数组实际数据的个数int capacity;   //数组空间个数
}SqList;

        这里定义了一个顺序表，只需要使用一个结构体，一个arr储存数组的首元素地址，size储存数组实际储存的有效元素个数，capacity储存这个动态变化的数组的最大可储存的元素个数，也就是这个数组当前的长度。

        我们需要使用一些函数实现我们的顺序表的功能，下面就是大概的需要实现的函数：

//顺序表初始化
void SqLInit(SqList* ps);
//顺序表判断是否需要扩容
void SqLBigger(SqList* ps);
//顺序表的尾插
void SqLPushBack(SqList* ps, DataType x);
//顺序表头插
void SqLPushFront(SqList* ps, DataType x);
//顺序表的头删
void SqLPopFront(SqList* ps);
//顺序表的尾删
void SqLPopBack(SqList* ps);
//顺序表的打印
void SqLPrint(SqList* ps);
//顺序表的查找
int SqLFind(SqList* ps, DataType num);
//顺序表的摧毁
void SqLDestory(SqList* ps);

函数实现：

//顺序表初始化
void SqLInit(SqList* ps)
{ps->arr = NULL;ps->capacity = ps->size = 0;
}//顺序表判断是否需要扩容
void SqLBigger(SqList* ps)
{if (ps->capacity == ps->size)//判断容量是否充足来包含了判断是否为空{int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;//初始为空就初始化为4，否则变为原来容量的两倍ps->arr = (DataType*)realloc(ps->arr, sizeof(DataType) * newcapacity);//realloc的第一个参数为空的时候，相当于mallocif (ps->arr == NULL){perror("realloc fail!");//判断是否申请成功，不成功就报错}}
}//顺序表的尾插
void SqLPushBack(SqList* ps, DataType x)
{//每次增加元素都要判断是否要扩容SqLBigger(ps);ps->arr[ps->size] = x;ps->size++;
}
//顺序表头插
void SqLPushFront(SqList* ps, DataType x)
{//每次增加元素都要判断是否要扩容SqLBigger(ps);//移位，腾出首元素的位置for (int i = ps->size - 1; i >= 0; i--){ps->arr[i + 1] = ps->arr[i];}ps->arr[0] = x;ps->size++;
}
//顺序表的头删
void SqLPopFront(SqList* ps)
{//判断是否为空assert(ps->arr && ps->size);//直接覆盖首元素即可for (int i = 1; i < ps->size ; i++){ps->arr[i - 1] = ps->arr[i];}ps->size--;
}
//顺序表的尾删
void SqLPopBack(SqList* ps)
{//判断是否为空assert(ps->arr && ps->size);//直接把有效元素个数-1即可ps->size--;
}
//顺序表的打印
void SqLPrint(SqList* ps)
{//判断是否为空assert(ps->arr && ps->size);for (int i = 0; i < ps->size; i++){printf("%d ", ps->arr[i]);}printf("\n");
}
//顺序表的查找
int SqLFind(SqList* ps,DataType num)
{//判断是否为空assert(ps->arr && ps->size);for (int i = 0; i < ps->size; i++){if (ps->arr[i] == num){return i;}}return -1;
}
//顺序表的摧毁
void SqLDestory(SqList* ps)
{if (ps->arr != NULL){ps->capacity = ps->size = 0;ps->arr = NULL;}
}

 测试一下：

 2.单链表

        单链表是顺序表的进阶版本，也是链表系列的入门款，我们使用链表可以更加灵活方便地操作各种问题。

        链表有很多种版本：带头和不带头，单向和双向，循环和不循环，可以组合成无数种款式。这里单链表是不带头单向链表

        单链表一般使用“结点”（“节点”）的形式连接，一个结点就是单链表的一个成员，单链表的每个结点都是一个储存值的一个单元，同时，我们可以通过这个结点找到下一个结点。抽象起来就像很多个火车车厢相互连接起来，从第一个火车车厢可以找到第二个车厢，再找到第三个，第四个...

        我们使用结构体定义这样的结点，所以我们就需要定义一个可以储存数据和找到下一个结点的结构体：

typedef int DataType;
typedef struct SList
{DataType val;		//储存的数据struct SList* next; //指向下一个结点的指针
}SLNode;

        这样我们就定义好了单链表的结点，在链表尾部时，指向空指针NULL。

        那么，我们就还需要像顺序表一样，写出各种函数实现增删查改等功能，不过这里有一点是和顺序表不一样的，比如单链表是不需要初始化的

        顺序表需要初始化是因为当顺序表为空时，传入的是一个没有初始化的结构体，要保证其中的指针arr为NULL，size  == 0，以及capacity ==0

        但是，这里我们使用单链表就不太一样了，我们需要传入或者说我们需要在main函数定义的应该是一个指针，指向头结点的一个指针，当链表为空，即没有任何结点的时候，就要我们把头指针指向NULL，然后再进行其它操作

        与此同时，由于我们传入的是头指针，所以当我们需要改变头指针的时候我们就需要传入二级指针修改头指针指向的结点，一级指针和二级指针的变化也是链表一个较为绕的点

        我们模仿顺序表可以写出下面的这些操作函数：

//头插
void SLPushFront(SLNode** pphead, DataType x);
//尾插
void SLPushBack(SLNode* phead, DataType x);
//头删
void SLPopFront(SLNode** pphead);
//尾删
void SLPopBack(SLNode** pphead);
//单链表打印
void SLPrint(SLNode* phead);
//查找
bool SLFind(SLNode* phead, DataType num);
//单链表销毁
void SLDestory(SLNode** pphead);

        实现这些函数就是：

//创建新节点
SLNode* NewNode(DataType x)
{SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));if (newnode == NULL){perror("malloc fail!");return;}newnode->val = x;newnode->next = NULL;return newnode;
}
//头插
void SLPushFront(SLNode** pphead, DataType x)
{SLNode* newnode = NewNode(x);newnode->next = *pphead;*pphead = newnode;
}
//尾插
void SLPushBack(SLNode* phead, DataType x)
{assert(phead);SLNode* cur = phead;while (cur->next){cur = cur->next;}SLNode* newnode = NewNode(x);cur->next = newnode;
}
//头删
void SLPopFront(SLNode** pphead)
{assert(*pphead);SLNode* del = *pphead;*pphead = (*pphead)->next;free(del);
}//尾删
void SLPopBack(SLNode** pphead)
{assert(*pphead);SLNode* cur = *pphead;if (cur->next == NULL){*pphead = NULL;free(cur);return;}while (cur->next->next){cur = cur->next;}SLNode* del = cur->next;cur->next = NULL;free(del);
}
//单链表打印
void SLPrint(SLNode* phead)
{SLNode* cur = phead;while (cur){printf("%d -> ", cur->val);cur = cur->next;}printf("NULL\n");
}
//查找
bool SLFind(SLNode* phead, DataType num)
{SLNode* cur = phead;while (cur){if (cur->val == num){return true;}cur = cur->next;}return false;
}//单链表销毁
void SLDestory(SLNode** pphead)
{if (*pphead == NULL){return;}SLNode* cur = *pphead;SLNode* next = cur;while (next){next = cur->next;free(cur);cur = next;}free(cur);
}

        这样就得到了我们的单链表的基本操作，这里操作一下：

        这里主要说一下函数传入指针是一级还是二级指针的问题：

        我们使用一级指针就是改变一级指针指向的那个元素，此元素由该一级指针的地址找到，比如我们想要改变一个结点的val值，就要使用一级指针改变就可以了，因为val就是由这个一级指针得到的元素，而不是这个指针本身。那如果我们想要改变指针本身，就要传入二级指针，就像写的头插操作里面就是需要改变一级指针（指向头结点的指针），所以需要传入二级指针

        假设我们需要改变头指针指向的结点里面的next指针，我们只需要使用一级指针就可以了，因为我们可以通过一级指针找到这个next指针的地址，却不是改变传入的指针本身，我们就能够使用一级指针改变，传入一级指针就可以改变除了传入指针以外的所有能够通过这个指针找到的全部元素。

        这同时也是我们在使用destory函数的的时候需要传入二级指针的原因：我们需要把所有非空节点都释放，就这一点来说使用一级指针是可以完成大部分操作的，使用一级指针可以释放掉全部节点，但是我们最后出函数之后这个头指针就还是有一个地址的，这就需要我们在函数外部操作吧头指针置为空。这很麻烦，所以我们使用二级指针在这个函数里面的目的就是把头指针也置为空，一步到位。

        还有一种方法，那就是把所有的都传入二级指针，但是这样对自己是没有任何提升的，所以不到万不得已是最好不要这样做。

3.双向链表

        指向单链表的指针是只能单向移动，每当我们需要得到移动后的指针前面的指针，就需要我们把指针重新置为头指针，这么一说，我们就可以使用一个更加方便的结构：双向链表。

        双向链表和单链表的操作基本是一致的，只是说我们的双向链表每个结点多了一个指向上一个结点的链表，方便我们找到上一个结点：

         这样的就是双向链表：

        在这样设计的基础上，我们还可以把首尾相连，构成循环双向链表：

        这里我们所说的双向链表一般使用不循环的，当然，链表还有一个特性：那就是带不带哨兵位，哨兵位就是一个不储存任何值的一个结点，哨兵位的使用取决于我们对链表结构的需求，这里为了演示最纯粹的双向链表就不使用哨兵位了。

        首先还是定义双向链表的结点：

typedef int DataType;
typedef struct DList
{DataType val;struct DList* prev;struct DList* next;
}DList;

        然后就是照猫画虎写出这个需要用的函数，这里缩减了一点 ：

//头插
void DLPushFront(DList** pphead, DataType x);
//尾插
void DLPushAfter(DList** pphead, DataType x);
//头删
void DLPopFront(DList** pphead);
//尾删
void DLPopAfter(DList** pphead);
//打印
void DLPrint(DList* phead);
//摧毁
void DLDestory(DList** pphead);

        然后就是这个函数的实现：

DList* NewANode(DataType x)
{DList* newnode = (DList*)malloc(sizeof(DList));if (newnode == NULL){perror("malloc fail!");return NULL;}newnode->val = x;newnode->prev = newnode->next = NULL;return newnode;
}
//头插
void DLPushFront(DList** pphead, DataType x)
{DList* newnode = NewANode(x);if (*pphead != NULL){newnode->next = *pphead;(*pphead)->prev = newnode;}*pphead = newnode;
}
//尾插
void DLPushAfter(DList** pphead, DataType x)
{DList* newnode = NewANode(x);if (*pphead != NULL){DList* cur = *pphead;while (cur->next){cur = cur->next;}cur->next = newnode;newnode->prev = *pphead;}else{*pphead = newnode;}
}
//头删
void DLPopFront(DList** pphead)
{assert(*pphead);DList* next = (*pphead)->next;free(*pphead);next->prev = NULL;*pphead = next;
}
//尾删
void DLPopAfter(DList** pphead)
{assert(*pphead);DList* cur = *pphead;if ((*pphead)->next != NULL){while (cur->next){cur = cur->next;}cur->prev->next = NULL;free(cur);}else{free(*pphead);*pphead = NULL;}
}
//打印
void DLPrint(DList* phead)
{DList* cur = phead;printf("NULL<->");while (cur){printf("%d<->", cur->val);cur = cur->next;}printf("NULL\n");
}//摧毁
void DLDestory(DList** pphead)
{assert(*pphead);DList* cur = *pphead;DList* next = cur;while (next){next = cur->next;free(cur);cur = next;}free(cur);
}

        看一下效果： 

        到了这里差不多我们就过了一遍这个顺序表+链表，下面我们可以来看一下由这些数据结构衍生出来的数据结构：栈和队列

4.栈

        首先我们需要明白的是：什么是栈？

        栈，就是一种数据结构，是一种先进后出的数据结构。可能会有人把它和我们所说的函数栈帧里面的栈搞混了。其实这两个就像南京的上海路和上海的南京路，毫无关系，非要说这俩条路有啥关系，那就只能是：它俩都是路。同样的，函数栈帧里的栈和数据结构里面的栈其实也是没有关系的，非要找一个关系的话，那就是：它们都叫栈。

        在我们所学的数据结构的栈中，其实就是一种很简单的一种顺序表或者链表，其实只要遵循一个原则：“先进后出”即可，这么说，其实一个数组其实就足够实现栈了。没错，确实是这样，不过我们无法事先知道一个栈会放入几个元素，所以我们就需要使用动态长度的数组。突然就有点熟悉了，我们需要数组长度动态变化，我们还要知道有效数据的下标堆到了哪里，这个时候我们就可把这些信息都封装起来，变成我们前面所学的一种数据结构 ---- 顺序表。当然，我们也可以使用链表完成这个事情，不过，杀鸡焉用牛刀，所以我们就使用一个所占空间最小的顺序表来实现就好了。

        这样，我们就可以开始定义一个顺序表的结构体了。

typedef int DataType;
typedef struct Stack
{DataType* arr;int size;int capacity;
}Stack;

        然后我们就可以通过画图看一下栈是这么实现的：

        先是有一个空栈，然后根据从1 - 8的顺序依次把8个元素都放在这个栈里面去，我们想要移除元素只能从栈顶，也就是只能从现在的8开始移除数据，相当于一个顺序表只能通过尾插和尾删增加减少元素，这同时也减少了我们很多工作量。

        首先需要下面的这些函数实现功能：

//初始化
void StackInit(Stack* ps);
//入栈
void StackPush(Stack* ps, DataType x);
//出栈
void StackPop(Stack* ps);
//得到栈顶数据
DataType StackTop(Stack* ps);
//判断是否为空栈
bool StackEmpty(Stack* ps);
//销毁栈
void StackDestory(Stack* ps);

         下面是实现函数的代码：

//初始化
void StackInit(Stack* ps)
{ps->arr = NULL;ps->capacity = ps->size = 0;
}
//入栈
void StackPush(Stack* ps, DataType x)
{if (ps->capacity == ps->size)//空间不足{int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;ps->arr = (DataType*)realloc(ps->arr,sizeof(DataType) * newcapacity);//ps->arr为空的时候相当于mallocps->capacity = newcapacity;}ps->arr[ps->size] = x;ps->size++;
}
//出栈
void StackPop(Stack* ps)
{assert(!StackEmpty(ps));ps->size--;
}
//得到栈顶数据
DataType StackTop(Stack* ps)
{assert(!StackEmpty(ps));return ps->arr[ps->size - 1];
}
//判断是否为空栈
bool StackEmpty(Stack* ps)
{return ps->size == 0;
}
//销毁栈
void StackDestory(Stack* ps)
{if(ps->arr)free(ps->arr);
}

        然后测试的代码就是下面这样： 

        `

5.队列

        队列和栈很像，只是队列和栈的操作正好是两个极端，栈要求后来者居上，但队列要求先到先得。所以，队列就像我们排队一样，先来的就先出，后来的就等一等。

        队列就是需要我们使用尾插和头删的操作，假设我们还是使用顺序表，那么我们的操作就会变得很复杂，所以我们就使用链表的方式实现队列，这样我们只要有头指针和尾指针就可以很快完成操作。这里使用最简单的链表——单链表实现队列。除此之外，我们还要定义一个结构体储存头指针和尾指针，这样方便我们完成给队列增加元素和减少元素的操作。

typedef int DataType;
//定义节点
typedef struct Queue
{DataType val;struct Queue* next;
}QNode;
//定义首尾指针
typedef struct Que
{QNode* phead;QNode* ptail;
}Que;

        这样我们只要传入整个有着首尾指针的结构体的地址就可以随意操作了，大大降低了我们操作的复杂度。下面就是我们需要使用的函数：

//初始化
void QueInit(Que* pq);
//插入(尾插)
void QuePush(Que* pq ,DataType x);
//删除(头删)
void QuePop(Que* pq);
//判断队列是否为空
bool QueEmpty(Que* pq);
//返回队列首元素
DataType QueTop(Que* pq);
//销毁队列
void QueDestory(Que* pq);

        函数的实现： 

//初始化
void QueInit(Que* pq)
{pq->phead = pq->ptail = NULL;
}
//插入(尾插)
void QuePush(Que* pq, DataType x)
{QNode* newnode = (QNode*)malloc(sizeof(QNode));newnode->next = NULL;newnode->val = x;if (pq->phead == NULL){pq->phead = pq->ptail = newnode;}else{pq->ptail->next = newnode;pq->ptail = newnode;}
}
//删除(头删)
void QuePop(Que* pq)
{assert(!QueEmpty(pq));QNode* del = pq->phead;if (del->next == NULL){pq->phead = pq->ptail = NULL;free(del);}else{pq->phead = del->next;free(del);}
}
//判断队列是否为空
bool QueEmpty(Que* pq)
{return pq->phead == NULL;
}
//返回队列首元素
DataType QueTop(Que* pq)
{return pq->phead->val;
}
//销毁队列
void QueDestory(Que* pq)
{assert(!QueEmpty(pq));QNode* cur = pq->phead;QNode* next = cur;while (next){next = cur->next;free(cur);cur = next;}free(cur);pq->phead = pq->ptail = NULL;
}

        这样，我们就实现了一个队列，测试一下：

        上面就是这几部分代码的总结了！也算入门数据结构了！