《大话数据结构源代码》由会员分享，可在线阅读，更多相关《大话数据结构源代码（130页珍藏版）》请在金锄头文库上搜索。
1、第 一 章 线 性 表1. 01 线 性 表 顺 序 存 储 _List#include stdio.h#include stdlib.h#include io.h#include math.h#include time.h#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#define MAXSIZE 20 /* 存 储空间 初始 分配 量 */typedef int Status; /* Status 是函数 的类 型, 其值是 函数 结果 状态 代码 ，如OK 等 */typedef int ElemType; /* Elem
2、Type 类型 根据 实际 情 况而 定， 这里 假设 为 int*/Status visit(ElemType c)printf(%d ,c);return OK;typedef structElemType dataMAXSIZE; /* 数组 ，存 储数 据 元素 */int length; /* 线 性表 当 前长 度 */SqList;/* 初 始化 顺序 线性 表 * / Status InitList(SqList *L)L-length=0;return OK;/* 初 始条 件： 顺序 线性表 L 已存在 。操 作结 果：若 L 为空 表 ，则 返回 TRUE， 否则 返回
3、FALSE */Status ListEmpty(SqList L)if(L.length=0)return TRUE;elsereturn FALSE;/* 初 始条 件： 顺序 线性 表 L 已存 在。 操作 结果 ：将 L 重置 为 空表 */Status ClearList(SqList *L)L-length=0;return OK;/* 初 始条 件： 顺序 线性 表 L 已存 在。 操作 结果 ：返 回 L 中 数据 元素 个数 */int ListLength(SqList L)return L.length;/* 初 始条 件： 顺序 线性 表 L 已存 在， 1i Lis
4、tLength(L) */* 操 作结 果： 用 e 返回 L 中第 i 个数 据元 素的 值, 注 意 i 是 指位 置， 第 1 个位 置 的数 组是 从 0 开始 */Status GetElem(SqList L,int i,ElemType *e)if(L.length=0 | iL.length)return ERROR;*e=L.datai-1;return OK;/* 初 始条 件： 顺序 线性 表 L 已存 在 * /* 操 作结 果： 返回 L 中 第 1 个 与 e 满足 关系 的数 据 元素的 位序 。 */* 若 这样 的数 据元 素不 存 在，则 返回 值 为 0
5、*/int LocateElem(SqList L,ElemType e)int i;if (L.length=0)return 0;for(i=0;i=L.length)return 0;return i+1;/* 初 始条 件： 顺序 线性 表 L 已存 在, 1i Li stLength(L)， */* 操 作结 果： 在 L 中第 i 个位置 之前 插入 新的 数据 元素 e，L 的长 度加 1 */ Status ListInsert(SqList *L,int i,ElemType e)int k;if (L-length=MAXSIZE) /* 顺 序 线性 表已 经满 */re
6、turn ERROR;if (iL-length+1)/* 当 i 比 第一 位置 小或 者比 最后一 位置 后一 位置 还要 大 时*/return ERROR;if (ilength) /* 若插 入数 据位 置不 在表 尾 */for(k=L-length-1;k=i-1;k-) /* 将 要 插 入 位 置 之 后 的 数 据 元 素 向 后 移 动 一 位*/L-datak+1=L-datak;L-datai-1=e; /* 将 新元 素插 入 */ L-length+;return OK;/* 初 始条 件： 顺序 线性 表 L 已存 在， 1i Lis tLength(L) */
7、* 操 作结 果： 删除 L 的 第 i 个数 据元 素，并 用 e 返 回 其值， L 的 长度 减 1 */ Status ListDelete(SqList *L,int i,ElemType *e)int k;if (L-length=0) /* 线性 表为 空 */return ERROR;if (iL-length) /* 删 除位 置不 正 确 */return ERROR;*e=L-datai-1;if (ilength) /* 如果 删除 不 是最后 位置 */for(k=i;klength;k+)/* 将删 除位 置后 继元 素前移 */ L-datak-1=L-datak
8、;L-length-;return OK;/* 初 始条 件： 顺序 线性 表 L 已存 在 * /* 操 作结 果： 依次 对 L 的 每个 数 据元 素输 出 */ Status ListTraverse(SqList L)int i;for(i=0;i=k;j-)i=ListDelete( /* 删除 第 j 个 数 据 */if(i=ERROR)elseprintf(删除 第%d 个数 据失 败 n,j);printf(删除 第%d 个的 元素 值 为：%d n,j,e);printf(依 次输 出 L 的 元素： ); ListTraverse(L);j=5;ListDelete(
9、/* 删除 第 5 个数 据 */printf(删 除第 %d 个 的 元素值 为： %dn,j,e);printf(依 次输 出 L 的 元素： ); ListTraverse(L);/构造 一个 有 10 个数 的 LbSqList Lb; i=InitList( for(j=6;jnext=NULL; /* 指 针域为 空 */return OK;/* 初 始条 件： 顺序 线性 表 L 已 存 在。 操作 结果 ： 若 L 为空表 ， 则 返 回 TRUE， 否 则返 回 FALSE*/Status ListEmpty(LinkList L)if(L-next)return FALSE
10、;elsereturn TRUE;/* 初 始条 件： 顺序 线性 表 L 已存 在。 操作 结果 ：将 L 重置 为 空表 */Status ClearList(LinkList *L)LinkList p,q;p=(*L)-next; /* p 指向 第一 个结 点 */while(p) /* 没到 表尾 */q=p-next; free(p); p=q;(*L)-next=NULL; /* 头 结点 指针 域为 空 */return OK;/* 初 始条 件： 顺序 线性 表 L 已存 在。 操作 结果 ：返 回 L 中 数据 元素 个数 */int ListLength(LinkLis
11、t L)int i=0;LinkList p=L-next; /* p 指向第 一个 结点 */while(p)i+;p=p-next;return i;/* 初 始条 件： 顺序 线性 表 L 已存 在， 1i Lis tLength(L) */* 操 作结 果： 用 e 返 回 L 中第 i 个数 据元 素的 值 */ Status GetElem(LinkList L,int i,ElemType *e)int j;LinkList p; /* 声 明一 结点 p */p = L-next; /* 让 p 指 向链 表 L 的第 一 个结点 */j = 1; /* j 为计 数器 */w
12、hile (p & jnext; /* 让 p 指 向 下一 个 结点 */+j;if ( !p | ji )return ERROR; /* 第 i 个 元素 不 存在 */*e = p-data; /* 取 第 i 个元 素 的数 据 */return OK;/* 初 始条 件： 顺序 线性 表 L 已存 在 * /* 操 作结 果： 返回 L 中 第 1 个 与 e 满足 关系 的数 据 元素的 位序 。 */* 若 这样 的数 据元 素不 存 在，则 返回 值 为 0 */int LocateElem(LinkList L,ElemType e)int i=0;LinkList p=L
13、-next;while(p)i+;if(p-data=e) /* 找到这 样的 数据 元素 */return i;p=p-next;return 0;/* 初 始条 件： 顺序 线性 表 L 已存 在, 1i Li stLength(L)， */* 操 作结 果： 在 L 中第 i 个位置 之前 插入 新的 数据 元素 e，L 的长 度加 1 */ Status ListInsert(LinkList *L,int i,ElemType e)int j;LinkList p,s;p = *L;j = 1;while (p & j next;+j;if (!p | j i)return ERRO
14、R; /* 第 i 个 元素不 存在 */s = (LinkList)malloc(sizeof(Node); /* 生成 新结 点( C 语言 标 准函 数) */s-data = e;s-next = p-next; /* 将 p 的 后继 结点 赋值 给 s 的后继 */p-next = s; /* 将 s 赋 值给 p 的后 继 * /return OK;/* 初 始条 件： 顺序 线性 表 L 已存 在， 1i Lis tLength(L) */* 操 作结 果： 删除 L 的 第 i 个数 据元 素，并 用 e 返 回 其值， L 的 长度 减 1 */ Status ListDe
15、lete(LinkList *L,int i,ElemType *e)int j;LinkList p,q;p = *L;j = 1;while (p-next & j next;+j;if (!(p-next) | j i)return ERROR; /* 第 i 个元 素不 存在 */q = p-next;p-next = q-next; /* 将 q 的 后继 赋值 给 p 的 后继 */*e = q-data; /* 将 q 结点 中的 数据 给 e */free(q); /* 让 系统 回收 此结 点 ，释放 内存 */return OK;/* 初 始条 件： 顺序 线性 表 L 已存 在 * /* 操 作结 果： 依次 对 L 的 每个 数 据元 素输 出 */ Status ListTraverse(LinkList L)LinkList p=L-next;while(p)visit(p-data);p=p-next;printf(n);return OK;/* 随机 产生 n 个元 素的 值，建 立带 表头 结点 的单 链线性 表 L（头 插法 ） * /void CreateListHead(
