数据结构与算法解析(C语言版)--线性表

本栏目致力于从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