怎么样给自己做网站,施工员证书查询网站,品牌设计包括,ftp网站备份本栏目致力于从0开始使用纯C语言将经典算法转换成能够直接上机运行的程序#xff0c;以项目的形式详细描述数据存储结构、算法实现和程序运行过程。
参考书目如下#xff1a; 《数据结构C语言版-严蔚敏》 《数据结构算法解析第2版-高一凡》
软件工具#xff1a; dev-cpp 0…本栏目致力于从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位置上 1in // 需要修改线性表分配空间已占满的时候需要扩容传入线性表地址
// 插入元素 1in
// 需要修改线性表传入线性表地址
Status InsertList(SqList *L,int i,ElemType e)
{ElemType *newbase,*p,*q; // 下标不合适返回失败 if(i1 || 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).length1];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(i0;iL.length;i){v(L.elemi);} printf(\n);return OK;
} 1.6 删除数据
// 删除元素 1in
// 需要修改线性表传入线性表地址
// 通过e返回要删除的数值
Status ListDelete(SqList *L,int i,ElemType *e)
{ ElemType *p NULL,*qNULL; // 下标不合适返回失败 if(i1 || i (*L).length) return ERROR;// 定位到要删除的位置p (*L).elem[i-1];*e *p;q (*L).elem[(*L).length-1];// 将p指向空间后面的数据向前移动。while(p q){*p *(p1);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(i0;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 获取某个位置的数据
// 获取某个下标对应的元素 1in
// 不需要修改线性表仅用于访问传入线性表即可
Status GetElem(SqList L,int i,ElemType *e)
{// 下标不合适返回失败 if(i1 || i L.length) return ERROR;*e L.elem[i-1];return OK;
}
1.12 按照条件查找某个元素所在位置
将条件判断关系封装在函数内部通过函数指针的形式传入到查找函数内。
// 查找元素e所在的位序 1in如果找不到返回0
Status LocateElem(SqList L,ElemType e,Status (*compare)(ElemType,ElemType))
{int i;for(i0;iL.length;i){if(compare(L.elem[i],e)){return i1;} } return 0;
}
1.13 查找元素的前驱元素
// 查找元素的前驱
// 不是第一个元素有前驱 如果是第一个或者找不到则没有意义
Status PriorElem(SqList L,ElemType cur_e,ElemType *prev_e)
{// idx为位序 1inint 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为位序 1inint 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(i1;ilb_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 i1,j1,k0;ElemType ai,bj;while((iLa.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(i1;i5;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(i0;i10;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(j0;j5;j){l1.elem[j] rand() % 10;} l1.length 5; printf(线性表1); ListTraverse(l1,visit);for(j0;j3;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
