顺序表和链表的各种代码实现

一、线性表

在日常生活中，线性表的例子比比皆是。例如，26个英文字母的字母表（A,B,C,……，Z）是一个线性表，表中的数据元素式单个字母。在稍复杂的线性表中，一个数据元素可以包含若干个数据项。例如在第一章中提到的学生基本信息表，每个学生为一个数据元素，包括学号、姓名、性别、籍贯、专业等数据项。

由以上两例可以看出，它们的数据元素虽然不同，但同一线性表中的元素必定具有相同的特性，即属于同一数据对象，相邻数据元素之间存在这序偶关系。诸如此类由n个数据特性相同的元素构成的有限序列成为线性表。对于非空的线性表或线性结构，其特点是：

（1）、存在唯一的一个被称作”第一个“的数据元素；

（2）、存在唯一的一个被称作”最后一个“的数据元素；

（3）、除第一个之外，结构中的每个数据元素均只有一个前驱；

（4）、除最后一个之外，结构中的每个数据元素均只有一个后继。

二、顺序表和链表

1、顺序表的定义:

顺序表是用一段 物理地址连续 的存储单元依次存储数据元素的线性结构，一般情况下采用数组存

储。在数组上完成数据的增删查改。

顺序表可以分为静态顺序表和动态顺序表：

静态顺序表：

静态顺序表：使用定长数组存储元素 。

存储结构

typedef struct SeqList
{SLDataType x;int size;
}SeqList

动态顺序表： 

动态顺序表：使用动态开辟的数组存储。

typedef struct SeqList
{SLDataType* Array;int size;     //顺序表当前的元素个数int capacity; //顺序表的最大容量
}

以下是实现顺序表的接口代码:

头文件：

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>typedef int SLDateType;
typedef struct SeqList
{SLDateType* a;int size;int capacity;
}SeqList;// 对数据的管理:增删查改 
void SeqListInit(SeqList* ps);
void SeqListDestroy(SeqList* ps);void SeqListPrint(SeqList* ps);
void SeqListPushBack(SeqList* ps, SLDateType x);
void SeqListPushFront(SeqList* ps, SLDateType x);
void SeqListPopFront(SeqList* ps);
void SeqListPopBack(SeqList* ps);// 顺序表查找
int SeqListFind(SeqList* ps, SLDateType x);
// 顺序表在pos位置插入x
void SeqListInsert(SeqList* ps, int pos, SLDateType x);
// 顺序表删除pos位置的值
void SeqListErase(SeqList* ps, int pos);
//修改顺序表pos位置的值
void SeqListModify(SeqList* ps, int pos, SLDateType x);

函数实现文件：

#define _CRT_SECURE_NO_WARNINGS 1
#include "SList.h"void SeqListInit(SeqList* ps)
{assert(ps);ps->a = (SLDateType*)malloc(sizeof(SLDateType)*4);ps->capacity = 4;ps->size = 0;
}
void SeqListDestroy(SeqList* ps)
{assert(ps);free(ps->a);ps->size = 0;ps->capacity = 0;
}void SeqListPrint(SeqList* ps)
{assert(ps);int i = 0;for (i = 0; i < ps->size; i++){printf("%d ", ps->a[i]);}printf("\n");
}
//检查增容的函数
void CheckCapacity(SeqList* ps)
{if (ps->capacity == ps->size){SLDateType* temp = (SLDateType*)realloc(ps->a, (ps->capacity * 2) * sizeof(SLDateType));if (temp == NULL){perror("mallco fail");return;}else{ps->a = temp;ps->capacity = ps->capacity * 2;}}
}
void SeqListPushBack(SeqList* ps, SLDateType x)
{//尾插首先检查增容CheckCapacity(ps);//增容完毕后开始插入数据ps->a[ps->size++] = x;
}
void SeqListPushFront(SeqList* ps, SLDateType x)
{//头插首先检查增容CheckCapacity(ps);//开始头插//往后面移动数据，从后往前移int end = 0;for (end = ps->size; end > 0; end--){ps->a[end] = ps->a[end - 1];}ps->a[end] = x;ps->size++;
}
void SeqListPopFront(SeqList* ps)
{assert(ps);assert(ps->size > 0);//头删int end = 0;for (end = 0; end < ps->size-1; end++){ps->a[end] = ps->a[end + 1];}ps->size--;
}
void SeqListPopBack(SeqList* ps)
{assert(ps->size > 0);assert(ps);ps->size--;
}
// 顺序表查找
int SeqListFind(SeqList* ps, SLDateType x)
{assert(ps);int i = 0;while (i < ps->size){if (ps->a[i] == x){return i;}i++;}//下标不可能是-1return -1;
}
// 顺序表在pos位置插入x
void SeqListInsert(SeqList* ps, int pos, SLDateType x)
{assert(ps);assert(pos >= 0 && pos <= ps->size);//检查增容CheckCapacity(ps);int end = 0;for (end = ps->size; end > pos; end--){ps->a[end] = ps->a[end - 1];}ps->a[pos] = x;ps->size++;
}
// 顺序表删除pos位置的值
void SeqListErase(SeqList* ps, int pos)
{assert(ps);assert(pos >= 0 && pos < ps->size);int end = 0;for (end = pos; end < ps->size - 1; end++){ps->a[end] = ps->a[end + 1];}ps->size--;
}
//修改函数
void SeqListModify(SeqList* ps,int pos,SLDateType x)
{assert(ps);assert(pos >= 0 && pos < ps->size);ps->a[pos] = x;
}

测试文件：

define _CRT_SECURE_NO_WARNINGS 1
#include "SList.h"void test1()
{SeqList s;SeqListInit(&s);SeqListPushBack(&s, 1);SeqListPushBack(&s, 2);SeqListPushBack(&s, 3);SeqListPushBack(&s, 4);SeqListPushBack(&s, 5);SeqListPrint(&s);SeqListPushFront(&s, 5);SeqListPushFront(&s, 4);SeqListPushFront(&s, 3);SeqListPrint(&s);SeqListPopFront(&s);SeqListPopFront(&s);SeqListPopFront(&s);SeqListPrint(&s);SeqListPopBack(&s);SeqListPopBack(&s);SeqListPopBack(&s);SeqListPopBack(&s);SeqListPopBack(&s);//SeqListPopBack(&s);SeqListPrint(&s);SeqListDestroy(&s);
}
void test2()
{SeqList s;SeqListInit(&s);SeqListPushBack(&s, 1);SeqListPushBack(&s, 2);SeqListPushBack(&s, 3);SeqListPushBack(&s, 4);SeqListPushBack(&s, 5);SeqListInsert(&s, 1, 2);SeqListPrint(&s);
}void test3()
{SeqList s;SeqListInit(&s);SeqListPushBack(&s, 1);SeqListPushBack(&s, 2);SeqListPushBack(&s, 3);SeqListPushBack(&s, 4);SeqListPushBack(&s, 5);/*SeqListInsert(&s, 1, 2);SeqListInsert(&s, 6, 6);SeqListInsert(&s, 0, 0);SeqListErase(&s, 0);SeqListErase(&s, 6);*/SeqListPrint(&s);int pos = SeqListFind(&s, 2);SeqListInsert(&s, pos, 3);SeqListPrint(&s);SeqListModify(&s, 1, 2);SeqListPrint(&s);
}
int main()
{//test1();//test2();test3();return 0;
}

2、单链表的定义：

概念：链表是一种 物理存储结构上非连续 、非顺序的存储结构，数据元素的 逻辑顺序 是通过链表 中的指针链接 次序实现的 。

链表实现代码：

头文件：

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLTypeData;
typedef struct SList
{SLTypeData data;struct SList* next;
}SList;
//打印函数
void SListPrint(SList* phead);
//头插函数
void SListPushFront(SList** pphead,SLTypeData x);
//头删函数
void SListPopFront(SList** pphead);
//尾插函数
void SListPushBack(SList** pphead,SLTypeData x);
//尾删函数
void SListPopBack(SList** pphead);
//查找单链表
SList* SListFind(SList* plist, SLTypeData x);
// 单链表在pos位置之后插入x
// 分析思考为什么不在pos位置之前插入？
void SListInsertAfter(SList* pos, SLTypeData x);
//单链表的修改
void SListModify(SList* pos, SLTypeData x);
// 单链表删除pos位置之后的值
// 分析思考为什么不删除pos位置？
void SListEraseAfter(SList* pos);
// 单链表的销毁
void SListDestroy(SList* plist);

实现文件：

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLTypeData;
typedef struct SList
{SLTypeData data;struct SList* next;
}SList;
//打印函数
void SListPrint(SList* phead);
//头插函数
void SListPushFront(SList** pphead,SLTypeData x);
//头删函数
void SListPopFront(SList** pphead);
//尾插函数
void SListPushBack(SList** pphead,SLTypeData x);
//尾删函数
void SListPopBack(SList** pphead);
//查找单链表
SList* SListFind(SList* plist, SLTypeData x);
// 单链表在pos位置之后插入x
// 分析思考为什么不在pos位置之前插入？
void SListInsertAfter(SList* pos, SLTypeData x);
//单链表的修改
void SListModify(SList* pos, SLTypeData x);
// 单链表删除pos位置之后的值
// 分析思考为什么不删除pos位置？
void SListEraseAfter(SList* pos);
// 单链表的销毁
void SListDestroy(SList* plist);

测试文件：

#define _CRT_SECURE_NO_WARNINGS 1
#include "SList.h"
void test1()
{SList* plist = NULL;SListPushFront(&plist, 1);SListPushFront(&plist, 2);SListPushFront(&plist, 3);SListPushFront(&plist, 4);SListPushFront(&plist, 5);SListPrint(plist);SListPopFront(&plist);SListPopFront(&plist);SListPopFront(&plist);SListPopFront(&plist);SListPopFront(&plist);//SListPopFront(&plist);SListPrint(plist);
}
void test2()
{SList* plist = NULL;SListPushBack(&plist, 1);SListPushBack(&plist, 2);SListPushBack(&plist, 3);SListPushBack(&plist, 4);SListPushBack(&plist, 5);SListPrint(plist);SListPopBack(&plist);SListPopBack(&plist);SListPopBack(&plist);SListPopBack(&plist);SListPopBack(&plist);//SListPopBack(&plist);SListPrint(plist);
}void test3()
{SList* plist = NULL;SListPushBack(&plist, 1);SListPushBack(&plist, 2);SListPushBack(&plist, 3);SListPushBack(&plist, 4);SListPushBack(&plist, 5);SListPrint(plist);SList* pos = SListFind(plist,5);if (pos == NULL){printf("没有找到\n");}else{printf("%d\n", pos->data);}SListInsertAfter(pos, 6);SListPrint(plist);pos = SListFind(plist, 5);SListEraseAfter(pos);SListPrint(plist);SListModify(pos, 4);SListPrint(plist);SListDestroy(plist);
}
int main()
{//test1();//test2();test3();return 0;
}

双向带头循环链表的实现：

头文件：

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int STListType;
typedef struct STList
{STListType val;struct STList* prev;struct STList* next;
}STList;
//初始化链表的函数
STList* initSTList();
//新建节点的函数
STList* BuyNode(STListType x);
//头插函数
void STListPushFront(STList* phead, STListType x);
//头删函数
void STListPopFront(STList* phead);
//尾插函数
void STListPushBack(STList* phead, STListType x);
//尾删函数
void STListPopBack(STList* phead);
//判空函数
bool EmptySTList(STList* phead);
//打印函数
void PrintSTList(STList* phead);
//查找函数
STList* FindSTList(STList* phead, STListType x);
//在任意位置插入
void STListPosInsert(STList* phead, STListType x);
//在任意位置删除
void STListPosErase(STList* phead);
//销毁函数
void DesSTList(STList* phead);

函数的实现：

#define _CRT_SECURE_NO_WARNINGS 1
#include "STList.h"
//初始化链表的函数
STList* initSTList()
{STList* phead = malloc(sizeof(STList));phead->val = -1;phead->next = phead;phead->prev = phead;return phead;
}
//新建节点的函数
STList* BuyNode(STListType x)
{STList* newnode = (STList*)malloc(sizeof(STList));newnode->prev = NULL;newnode->next = NULL;newnode->val = x;return newnode;
}
//头插函数
void STListPushFront(STList* phead, STListType x)
{assert(phead);STList* newnode = BuyNode(x);newnode->next = phead->next;phead->next->prev = newnode;newnode->prev = phead;phead->next = newnode;
}
//头删函数
void STListPopFront(STList* phead)
{assert(phead);assert(!EmptySTList(phead));STList* cur = phead->next;STList* next = cur->next;phead->next = next;next->prev = phead;free(cur);cur = NULL;
}
//尾插函数
void STListPushBack(STList* phead, STListType x)
{assert(phead);STList* newnode = BuyNode(x);STList* tail = phead->prev;tail->next = newnode;newnode->prev = tail;newnode->next = phead;phead->prev = newnode;
}
//尾删函数
void STListPopBack(STList* phead)
{assert(phead);assert(!EmptySTList(phead));STList* tail = phead->prev;STList* prev = tail->prev;prev->next = phead;phead->prev = prev;
}
//判空函数
bool EmptySTList(STList* phead)
{assert(phead);return phead->next == phead;
}//打印函数
void PrintSTList(STList* phead)
{assert(phead);STList* cur = phead->next;printf("head<==>");while (cur != phead){printf("%d<==>", cur->val);cur = cur->next;}printf("NULL\n");
}//查找函数
STList* FindSTList(STList* phead, STListType x)
{assert(phead);STList* cur = phead->next;while (cur != phead){if (cur->val == x){return cur;}cur = cur->next;}return NULL;
}//在任意位置前插入
void STListPosInsert(STList* pos, STListType x)
{assert(pos);STList* newnode = BuyNode(x);STList* prev = pos->prev;newnode->next = pos;pos->prev = newnode;newnode->prev = prev;prev->next = newnode;
}
//在任意位置删除
void STListPosErase(STList* pos)
{assert(pos);STList* prev = pos->prev;STList* next = pos->next;prev->next = next;next->prev = prev;free(pos);
}
//销毁链表
void DesSTList(STList* phead)
{STList* cur = phead;while (cur != phead){STList* next = cur->next;free(cur);cur = next;}free(phead);
}

测试文件：

#define _CRT_SECURE_NO_WARNINGS 1
#include "STList.h"void test1()
{STList* phead = initSTList();STListPushBack(phead, 1);STListPushBack(phead, 2);STListPushBack(phead, 3);STListPushBack(phead, 4);STListPushBack(phead, 5);PrintSTList(phead);STListPushFront(phead, 5);STListPushFront(phead, 4);STListPushFront(phead, 3);STListPushFront(phead, 2);STListPushFront(phead, 1);STListPopBack(phead);STListPopBack(phead);STListPopBack(phead);STListPopBack(phead);STListPopBack(phead);STListPopBack(phead);STListPopBack(phead);STListPopBack(phead);STListPopBack(phead);STListPopBack(phead);STListPopBack(phead);STListPopBack(phead);STListPopBack(phead);STListPopBack(phead);STListPopBack(phead);PrintSTList(phead);DesSTList(phead);
}
void test2()
{STList* phead = initSTList();STListPushBack(phead, 1);STListPushBack(phead, 2);STListPushBack(phead, 3);STListPushBack(phead, 4);STListPushBack(phead, 5);PrintSTList(phead);STListPushFront(phead, 5);STListPushFront(phead, 4);STListPushFront(phead, 3);STListPushFront(phead, 2);STListPushFront(phead, 1);/*STListPopFront(phead);STListPopFront(phead);STListPopFront(phead);STListPopFront(phead);STListPopFront(phead);STListPopFront(phead);STListPopFront(phead);STListPopFront(phead);STListPopFront(phead);STListPopFront(phead);*/STList* pos = FindSTList(phead, 4);if (pos){STListPosInsert(pos, 40);}PrintSTList(phead);pos = FindSTList(phead, 40);if (pos){STListPosErase(pos);}PrintSTList(phead);
}int main()
{//test1();test2();return 0;
}