本栏目致力于从0开始使用纯C语言将经典算法转换成能够直接上机运行的程序，以项目的形式详细描述数据存储结构、算法实现和程序运行过程。
参考书目如下：
《数据结构C语言版-严蔚敏》
《数据结构算法解析第2版-高一凡》
软件工具：
dev-cpp
0、准备工作
在项目下创建line.c和line.h文件。
1、线性表操作
1.1 准备工作line.h
定义线性表数组的长度和扩容量
// 线性表长度
#define LIST_INIT_SIZE 100
// 线性表扩容量
#define LISTINCREMENT 10定义线性表结构体，存储线性表其实地址和线性表元素个数和线性表总长度。
typedef struct
{ElemType *elem; // 线性表的起始地址 int length; // 表中元素个数 int listsize; // 表的总长度
}SqList;1.2 初始化链表
按照线性表的长度申请空间，并且初始化线性表元素个数和表的总长度。
// 初始化线型数组链表
// 需要修改线性表，传入线性表地址
Status InitList(SqList *L)
{// 按照表的长度申请空间，并赋值给*L的elem (*L).elem = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));// 申请失败，直接结束程序 if(!((*L).elem)){printf("数据空间申请失败!\n"); exit(OVERFLOW);}(*L).length = 0;(*L).listsize = LIST_INIT_SIZE;return OK;
}1.3 插入数据
// 插入数据e在线性表的i位置上 1<=i<=n
// 需要修改线性表（分配空间已占满的时候需要扩容），传入线性表地址
// 插入元素 1<=i<=n
// 需要修改线性表，传入线性表地址
Status InsertList(SqList *L,int i,ElemType e)
{ElemType *newbase,*p,*q; // 下标不合适返回失败 if(i<1 || i > (*L).length + 1) return ERROR;// 当前分配的空间已占满,按增量重新分配 if((*L).length >= (*L).listsize) {newbase = (ElemType *)realloc((*L).elem,((*L).listsize + LISTINCREMENT) * sizeof(ElemType));if(!newbase){ printf("数据空间增量申请失败!\n"); exit(OVERFLOW); }(*L).elem = newbase;(*L).listsize = (*L).listsize + LISTINCREMENT;}// 插入数据p = &(*L).elem[i-1];q = &(*L).elem[(*L).length+1];while(q > p){*q = *(q-1);q--; }*q = e;(*L).length++;return OK;
}1.4 遍历列表
遍历列表过程中可能要做的事情不一样，因此将功能封装进函数中，然后将函数传入遍历函数中，进行执行。
// 链表的遍历
Status ListTraverse(SqList L,void (*v)(ElemType *))
{int i;for(i=0;i<L.length;i++){v(L.elem+i);} printf("\n");return OK;
}1.6 删除数据
// 删除元素 1<=i<=n
// 需要修改线性表，传入线性表地址
// 通过e返回要删除的数值
Status ListDelete(SqList *L,int i,ElemType *e)
{ ElemType *p = NULL,*q=NULL; // 下标不合适返回失败 if(i<1 || i > (*L).length) return ERROR;// 定位到要删除的位置p = &(*L).elem[i-1];*e = *p;q = &(*L).elem[(*L).length-1];// 将p指向空间，后面的数据向前移动。while(p <= q){*p = *(p+1);p++;} // 改变长度(*L).length--;return OK;
}1.7 销毁线性表
// 销毁线性表
// 需要修改线性表，传入线性表地址
// 释放动态申请空间即可。
Status DestroyList(SqList *L)
{// 释放堆区空间 free((*L).elem);// 将指针指向NULL,避免野指针。 (*L).elem = NULL;// 将线性表的长度的尺寸清0 (*L).length = 0;(*L).listsize = 0;return OK;
}1.8 清空线性表
// 清空线性表
// 需要修改线性表，传入线性表地址
// 将所有空间清为0
Status ClearList(SqList *L)
{// 将空间里面的数据清0 int i;for(i=0;i<(*L).listsize;i++){(*L).elem[i] = 0;}// 将长度清0；(*L).length = 0; return OK;
}1.9 判断线性表是否为空
// 判断线性表是否为空， 空表返回TRUE,否则返回FALSE
// 不需要修改线性表，仅用于访问，传入线性表即可
Status ListEmpty(SqList L)
{return L.length == 0 ? TRUE : FALSE;
}1.10 获取线性表的长度
// 获取 线性表长度
// 不需要修改线性表，仅用于访问，传入线性表即可
Status ListLength(SqList L)
{return L.length;
}
1.11 获取某个位置的数据
// 获取某个下标对应的元素 1<=i<=n
// 不需要修改线性表，仅用于访问，传入线性表即可
Status GetElem(SqList L,int i,ElemType *e)
{// 下标不合适返回失败 if(i<1 || i > L.length) return ERROR;*e = L.elem[i-1];return OK;
}1.12 按照条件查找某个元素所在位置
将条件判断关系封装在函数内部，通过函数指针的形式传入到查找函数内。
// 查找元素e所在的位序， 1<=i<=n；如果找不到，返回0
Status LocateElem(SqList L,ElemType e,Status (*compare)(ElemType,ElemType))
{int i;for(i=0;i<L.length;i++){if(compare(L.elem[i],e)){return i+1;} } return 0;
}1.13 查找元素的前驱元素
// 查找元素的前驱
// 不是第一个元素有前驱 ，如果是第一个或者找不到则没有意义
Status PriorElem(SqList L,ElemType cur_e,ElemType *prev_e)
{// idx为位序 1<=i<=n；int idx = LocateElem(L,cur_e,equal);if(idx <= 1) {return INFEASIBLE;}else{*prev_e = L.elem[idx-2];return OK;}
}1.14 查找元素的后驱元素
// 查找元素的后继
Status NextElem(SqList L,ElemType cur_e,ElemType *next_e)
{// idx为位序 1<=i<=n；int idx = LocateElem(L,cur_e,equal);if(idx >= L.length) { return INFEASIBLE;}else{*next_e = L.elem[idx];return OK;}
}
1.15 两个线性表的并集
// 求两个线性表的并集
void unionList(SqList *La,SqList Lb)
{int la_len = ListLength(*La);int lb_len = ListLength(Lb);int i;ElemType e;for(i=1;i<=lb_len;i++){// 将数据从Lb中读出放入到e里面去 GetElem(Lb,i,&e);// 检测e数据在不在La中。if(!LocateElem(*La,e,equal)) {// 不在将e放入到La中InsertList(La,++la_len,e); }}
}1.16 两个有序线性表的合并
// 两个递增有序链表的合并。
void MergeList(SqList La,SqList Lb,SqList *Lc)
{// 初始化LcInitList(Lc);int la_len = ListLength(La);int lb_len = ListLength(Lb); int i=1,j=1,k=0;ElemType ai,bj;while((i<=La.length) && (j <= Lb.length)){GetElem(La,i,&ai);GetElem(Lb,j,&bj);if(ai <= bj){InsertList(Lc,++k,ai);++i;}else{InsertList(Lc,++k,bj);++j;}}while(i <= La.length){GetElem(La,i++,&ai);InsertList(Lc,++k,ai);}while(j <= Lb.length){GetElem(Lb,j++,&bj);InsertList(Lc,++k,bj);}
}1.17 判断两个数是否相等-查找辅助函数
// 辅助函数 -- 两个数据的相等判断
Status equal(ElemType e1,ElemType e2)
{return e1 == e2 ? TRUE : FALSE;
}1.18 访问数据--遍历的辅助函数
// 遍历辅助函数
void visit(ElemType *e)
{printf("%d ",*e);
} 1.19 测试功能代码
void line_test(void)
{SqList l;InitList(&l);srand((unsigned int)time(NULL)); // 测试插入 int i;for(i=1;i<=5;i++){InsertList(&l,i,rand() % 10);} l.length = 5; printf("原始数据如下：");ListTraverse(l,visit); // 接受删除的数据 int res;// 删除位置 int idx = rand() % 5 + 1; printf("删除位置：%d\n",idx);ListDelete(&l,idx,&res);printf("删除的数字是：%d,删除后：",res);ListTraverse(l,visit);// ClearList(&l);
// for(i=0;i<10;i++)
// {
// printf("%d ",l.elem[i]);
// }
// printf("\n");// 线性表为空和 线性表长度测试if(ListEmpty(l)){printf("当前链表为空\n");} else{printf("链表当前的长度为：%d\n",ListLength(l));}// 获取某个元素测试int val;GetElem(l,1,&val);printf("第1个元素是：%d\n",val); // 查找元素的位序 测试int index = LocateElem(l,5,equal);printf("查找到5在数组的位序为：%d\n",index); // 查找元素的前驱测试Status res1;res1 = PriorElem(l,l.elem[0],&val);if(res1 != INFEASIBLE){printf("l.elem[3]的前驱是：%d\n",val);}// 查找元素的后继测试res1 = NextElem(l,l.elem[0],&val);if(res1 != INFEASIBLE){printf("l.elem[3]的后继是：%d\n",val);}// 两个线性表合并测试SqList l1,l2;InitList(&l1); InitList(&l2);int j;for(j=0;j<5;j++){l1.elem[j] = rand() % 10;} l1.length = 5; printf("线性表1："); ListTraverse(l1,visit);for(j=0;j<3;j++){l2.elem[j] = rand() % 10;} l2.length = 3; printf("线性表2：");ListTraverse(l2,visit);unionList(&l1,l2);printf("合并后，线性表1："); ListTraverse(l1,visit);// 两个增序线性表合并检测SqList l3,l4,l5;InitList(&l3); InitList(&l4); InitList(&l5); l3.elem[0] = 3;l3.elem[1] = 5;l3.elem[2] = 8;l3.elem[3] = 11;l3.length = 4;printf("线性表l3为：");ListTraverse(l3,visit);l4.elem[0] = 2;l4.elem[1] = 6;l4.elem[2] = 8;l4.elem[3] = 9;l4.elem[4] = 11;l4.elem[5] = 15;l4.elem[6] = 20;l4.length = 7;printf("线性表l4为：");ListTraverse(l4,visit);MergeList(l3,l4,&l5);printf("合并有序线性表l3和l4后为：");ListTraverse(l5,visit);
} 项目仓库地址
https://gitee.com/amyliyanice/data_struct.git
