前言：
这次介绍基本数据结构的线性表和链表，并用C语言进行编写；建议最开始学数据结构时，用C语言；像栈和队列都可以用这两种数据结构来实现。
一、线性表基本介绍
1 概念：
线性表也就是关系户中最简单的一种关系，一对一。
如：学生学号的集合就是一个线性表。
2 特征：
① 有且只有一个“首元素“。
② 有且只有一个“末元素”。
③ 除“末元素”外，其余元素均有唯一的后继元素。
④ 除“首元素”外，其余元素均有唯一的前驱元素。
3 存储划分：
① 如果把线性表用“顺序存储”，那么就是“顺序表”。
② 如果把线性表用“链式存储”，那么就是“链表”。
4 常用操作：
添加，删除，插入，查找，遍历，统计。
二、线性表实现
主要实现线性表的创建、销毁和插入等操作，将接口封装在.h文件中，如下：
复制代码
#ifndef __MY_SEQLIST_H__
#define __MY_SEQLIST_H__
typedef void SeqList;
typedef void SeqListNode;
SeqList* SeqList_Create(int capacity); //创建线性表
void SeqList_Destroy(SeqList* list); //销毁
void SeqList_Clear(SeqList* list); //清空
int SeqList_Length(SeqList* list); //求线性表的长度
int SeqList_Capacity(SeqList* list); //求线性表的容量
int SeqList_Insert(SeqList* list, SeqListNode* node, int pos); //向线性表中插入元素
SeqListNode* SeqList_Get(SeqList* list, int pos); //获取指定位置元素
SeqListNode* SeqList_Delete(SeqList* list, int pos); //删除指定位置元素
#endif //__MY_SEQLIST_H__
复制代码
注意：定义头文件时，要包含“#ifndef”，防止头文件重复包含！
1、线性表创建
主要就是对节点分配内存，代码如下：
复制代码
//在结构体中套1级指针
//
typedef struct _tag_SeqList
{
int length;
int capacity;
unsigned int *node; //int* node[]
}TSeqList;
SeqList* SeqList_Create(int capacity)
{
int ret = 0;
TSeqList *tmp = NULL;
tmp = (TSeqList *)malloc(sizeof(TSeqList));
if (tmp == NULL)
{
ret = -1;
printf("func SeqList_Create() err:%d \n", ret);
return NULL;
}
memset(tmp, 0, sizeof(TSeqList));
//根据capacity 的大小分配节点的空间
tmp->node = (unsigned int *)malloc(sizeof(unsigned int *) * capacity);
if (tmp->node == NULL)
{
ret = -2;
printf("func SeqList_Create() err: malloc err %d \n", ret);
return NULL;
}
tmp->capacity = capacity;
tmp->length = 0;
return tmp;
}
void SeqList_Destroy(SeqList* list)
{
TSeqList *tlist = NULL;
if (list == NULL)
{
return ;
}
tlist = (TSeqList *)list;
if (tlist->node != NULL)
{
free(tlist->node);
}
free(tlist);
return ;
}
复制代码
2、线性表插入
插入在业界有默认的规则吧，下面将要讲到的链表也是用这个规则。用图来讲解一下吧，如下：
讲解：例如，已经有线性表34、33、32、31，在1位置想插入35，想把从1开始的先后移，再插入，插入后的线性表如右图所示。
线性表插入代码如下：
复制代码
int SeqList_Insert(SeqList* list, SeqListNode* node, int pos)
{
int i =0, ret = 0;
TSeqList *tlist = NULL;
if (list == NULL || node==NULL || pos<0)
{
ret = -1;
printf("fun SeqList_Insert() err:%d \n", ret);
return ret;
}
tlist = (TSeqList*)list;
//判断是不是满了
if (tlist->length >= tlist->capacity)
{
ret = -2;
printf("fun SeqList_Insert() (tlist->length >= tlist->capacity) err:%d \n", ret);
return ret;
}
//容错修正 6个长度 容量20;用户pos10位置插入..
if (pos>=tlist->length)
{
pos = tlist->length; //
}
//1 元素后移
for(i=tlist->length; i>pos; i--)
{
tlist->node[i] = tlist->node[i-1];
//a[7] = a[6]
}
// i = 3
// 2插入元素
tlist->node[i] = (unsigned int )node;
tlist->length ++;
return 0;
}
复制代码
3、获取指定位置元素
根据pos位置获取元素，代码如下：
复制代码
SeqListNode* SeqList_Get(SeqList* list, int pos)
{
int i =0;
SeqListNode *ret = 0;
TSeqList *tlist = NULL;
if (list == NULL || pos<0)
{
printf("fun SeqList_Get() err:%d \n", ret);
return NULL;
}
tlist = (TSeqList*)list;
ret = (void *)tlist->node[pos];
return ret;
}
复制代码
4、删除指定位置元素
将指定位置的元素进行删除，代码如下：
复制代码
SeqListNode* SeqList_Delete(SeqList* list, int pos)
{
int i = 0;
SeqListNode *ret = 0;
TSeqList *tlist = NULL;
if (list == NULL || pos<0) //检查
{
printf("fun SeqList_Delete() err:%d \n", ret);
return NULL;
}
tlist = (TSeqList*)list;
ret = (SeqListNode *)tlist->node[pos]; //缓存pos的位置
for (i=pos+1; ilength; i++) //pos位置后面的元素前移
{
tlist->node[i-1] = tlist->node[i];
}
tlist->length --;
return ret;
}
复制代码
5、总体代码
整个seqlist.c代码如下，方便使用与调试：
View Code
6、调试
写一个main函数，进行上面的接口调用与调试，代码如下：
复制代码
#include
#include
#include
#include "seqlist.h"
typedef struct _Teacher
{
int age;
char name[64];
}Teacher;
void main()
{
int ret = 0, i = 0;
SeqList* list = NULL;
Teacher t1, t2, t3, t4,t5;
t1.age = 31;
t2.age = 32;
t3.age = 33;
t4.age = 34;
t5.age = 35;
list = SeqList_Create(10);
if (list == NULL)
{
printf("func SeqList_Create() ret :%d \n", ret);
return ;
}
ret = SeqList_Insert(list, (SeqListNode*) &t1, 0); //头插法
ret = SeqList_Insert(list, (SeqListNode*) &t2, 0); //头插法
ret = SeqList_Insert(list, (SeqListNode*) &t3, 0); //头插法
ret = SeqList_Insert(list, (SeqListNode*) &t4, 0); //头插法
ret = SeqList_Insert(list, (SeqListNode*) &t5, 1); //头插法
//遍历
for (i=0; iage:%d ", tmp->age);
}
//删除链表中的节点
while( SeqList_Length(list) > 0 )
{
SeqList_Delete(list, 0);
}
system("pause");
return ;
}
复制代码
三、链表
1、介绍
链表的大体有三种实现方式，用图进行讲解吧，如下图：
说明：最上面就是最传统链表，每个节点存一个next指针，保存下一个节点的地址
中间是linux内核实现的链表，一般是双向链表，有一个缺点要记录偏移量
最后是改进之后的链表，不需要记录偏移量，这是前人的智慧，我将采用最后一种进行实现。
2、定义头文件
头文件主要包含结构体定义，和接口声明，主要实现链表初始化、插入、遍历等操作，头文件如下：
复制代码
#ifndef LINKLIST_H
#define LINKLIST_H
#include
#include
//链表结点
typedef struct LINKNODE{
void* data; //指向任何类型的数据
struct LINKNODE* next;
}LinkNode;
//链表结构体
typedef struct LINKLIST{
LinkNode* head;
int size;
}LinkList;
//定义函数指针
typedef void(*PRINTLINKNODE)(void*);
//初始化链表
LinkList* Init_LinkList();
//指定位置插入
void Insert_LinkList(LinkList* list,int pos,void* data);
//删除指定位置的值
void RemoveByPos_LinkList(LinkList* list, int pos);
//获得链表的长度
int Size_LinkList(LinkList* list);
//查找
int Find_LinkList(LinkList* list,void* data);
//返回第一个结点
void* Front_LinkList(LinkList* list);
//打印链表结点
void Print_LinkList(LinkList* list, PRINTLINKNODE print);
//释放链表内存
void FreeSpace_LinkList(LinkList* list);
#endif
复制代码
3、插入节点
初始化链表跟线性表类似，就不在过多说明了，主要讲解插入和删除节点，对插入节点进行讲解，如下图：
说明：需要两个指针current、node，假如在3号位置进行插入，要先处理node->next，node指向3号位置，就把3号位置指针付给它，node->next=current->next;
2号位置指向node，把node指针赋值给它，current->next=node;
注意：图片左下角的红字，是理解链表插入、删除等的关键！
代码如下：
复制代码
//指定位置插入
void Insert_LinkList(LinkList* list, int pos, void* data){
if (list == NULL){
return;
}
if (data == NULL){
return;
}
//友好的处理，pos越界
if (pos < 0 || pos > list->size) {
pos = list->size;
}
//创建新的结点
LinkNode* newnode = (LinkNode*)malloc(sizeof(LinkNode));
newnode->data = data;
newnode->next = NULL;
//找结点
//辅助指针变量
LinkNode* pCurrent = list->head;
for (int i = 0; i < pos;i++){
pCurrent = pCurrent->next;
}
//新结点入链表
newnode->next = pCurrent->next;
pCurrent->next = newnode;
list->size++;
}
复制代码
4、删除节点
说明：
删除3号位置，先保存被删除节点的位置，再将2直接指向4；
5、整体代码
整个的代码，方便大家使用和调试，代码如下：
View Code
6、调试代码
写一个main函数进行调试，如下：
View Code
运行结果如下，供参考：
总结
虽然线性表和单向链表是数据结构的基础，但完全掌握之后，再学习栈、队列等数据结构将会得心应手；
喜欢的希望帮忙点赞，不懂的欢迎随时留言！
作者：柳德维
出处：https://www.cnblogs.com/liudw-0215/
-------------------------------------------
个性签名：独学而无友，则孤陋而寡闻。做一个灵魂有趣的人！
如果觉得这篇文章对你有小小的帮助的话，记得在右下角点个“推荐”哦，博主在此感谢！
万水千山总是情，打赏一分行不行，所以如果你心情还比较高兴，也是可以扫码打赏博主，哈哈哈(っ•̀ω•́)っ✎⁾⁾！https://www.cnblogs.com/liudw-0215/p/9843008.html
