定义常量 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INIT_SIZE 10 //初始化表长 #define INCREMENT_SIZE 5 //分配增量创建一个顺序表结构体SqList typedef struct { Elemtype *elem; //存储空间基址 int length; //当前长度 int size; //当前分配的表长大小 }SqList; 初始化一个空的线性表函数 Status InitList(SqList *L) { L->elem = (Elemtype *) malloc(INIT_SIZE * sizeof(Elemtype));//通过malloc函数分配存储空间 if (!L->elem) { return ERROR;//返回分配空间失败错误代码 } L->length = 0;//初始化长度 L->size = INIT_SIZE;//初始化大小 return OK;//返回初始化成功代码 } 销毁线性表函数 Status DestroyList(SqList *L) { free(L->elem);//释放分配空间 L->length = 0;//长度归0 L->size = 0;//大小归0 return OK;//返回初始化成功代码 } 清空线性表函数 Status ClearList(SqList *L) { L->length = 0;//长度归0 return OK;//返回初始化成功代码 } 判断线性表是否为空 Status isEmpty(const SqList L) { if (0 == L.length) //如果长度为0 { return TRUE;//返回该表为空代码 } else { return FALSE;//否则返回表不为空代码 } } 获取长度 Status getLength(const SqList L) { return L.length;//返回顺序表长度 } 根据位置获取元素 Status GetElem(const SqList L, int i, Elemtype *e) { if (i < 1 || i > L.length) { return ERROR;//越界获取元素失败,返回错误代码 } *e = L.elem[i-1];//根据位置返回对应元素 return OK;//返回成功代码 } 比较两个元素是否相等 Status compare(Elemtype e1, Elemtype e2) { if (e1 == e2) { return 0; } else if (e1 < e2) { return -1; } else { return 1; } } 查找元素 Status FindElem(const 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;//成功返回位置 } } if (i >= L.length) { return ERROR;//遍历完没找到返回错误代码 } } 查找前驱元素 Status PreElem(const SqList L, Elemtype cur_e, Elemtype *pre_e) { int i; for (i = 0; i < L.length; i++)//遍历顺序表元素 { if (cur_e == L.elem[i])//找到该元素 { if (i != 0) { *pre_e = L.elem[i - 1];//指针指向该元素的前一位 } else { return ERROR;//第一位元素没有前驱元素 } } } if (i >= L.length) { return ERROR;//没找到返回错误代码 } } 查找后继元素 Status NextElem(const SqList L, Elemtype cur_e, Elemtype *next_e) { int i; for (i = 0; i < L.length; i++)//遍历顺序表元素 { if (cur_e == L.elem[i])//找到该元素 { if (i < L.length - 1) { *next_e = L.elem[i + 1];//指针指向该元素后一位元素 return OK; } else { return ERROR;//最后一位元素没有后驱元素 } } } if (i >= L.length) { return ERROR;//没找到返回错误代码 } } 插入元素 Status InsertElem(SqList *L, int i, Elemtype e) { Elemtype *new; if (i < 1 || i > L->length + 1) { return ERROR;//无效位置 } if (L->length >= L->size) { new = (Elemtype*) realloc(L->elem, (L->size + INCREMENT_SIZE) * sizeof(Elemtype));//新分配一块空间 if (!new) { return ERROR;//分配失败报错 } L->elem = new;//顺序表加入新空间 L->size += INCREMENT_SIZE;//增加大小 } Elemtype *p = &L->elem[i - 1];//该元素前驱指针 Elemtype *q = &L->elem[L->length - 1];//顺序表最后一位元素指针 for (; q >= p; q--) { *(q + 1) = *q;//后移指针 } *p = e;//插入元素 ++L->length;//长度增加 return OK; } * 删除元素并返回其值 */ Status DeleteElem(SqList *L, int i, Elemtype *e) { if (i < 1 || i > L->length) { return ERROR;//无效的位置 } Elemtype *p = &L->elem[i - 1];//该元素指针 *e = *p;//记录删除元素 for (; p < &L->elem[L->length]; p++) { *(p) = *(p + 1);//后一位覆盖前一位元素 } --L->length;//长度减一 return OK; } * 访问元素 */ void visit(Elemtype e) { printf("%d ", e); } /* * 遍历线性表 */ Status TraverseList(const SqList L, void (*visit)(Elemtype)) { int i; for(i = 0; i < L.length; i++) { visit(L.elem[i]); } return OK; } ![图片描述](https://dn-simplecloud.shiyanlou.com/courses/uid2439598-20230309-1678351976000) 初始化的算法步骤：（1）生成新结点作头结点，用头指针 L 指向头结点。（2）头结点的指针域置空。 /* * 初始化线性表 */ void InitList(LinkList *L) { *L = (LinkList) malloc(sizeof(LNode)); if (!L) { exit(OVERFLOW); } (*L)->next = NULL; } 销毁链表的算法步骤：（1）创建一个新的空表（2）释放原链表的空间（3）将空表赋值给原来的链表 /* * 销毁线性表 */ void DestroyList(LinkList *L) { LinkList temp; while (*L) { temp = (*L)->next; free(*L); *L = temp; } } /* * 插入元素 */ Status InsertElem(LinkList L, int i, ElemType e) { int j = 0; LinkList s, p = L; while (p && j < i - 1) { j++; p = p->next; } if (!p || j > i - 1) { return ERROR; } s = (LinkList) malloc(sizeof(LNode)); s->data = e; s->next = p->next; p->next = s; return OK; } /* * 删除元素并返回值 */ Status DeleteElem(LinkList L, int i, ElemType *e) { int j = 0; LinkList q, p = L; while (p->next && j < i - 1) { j++; p = p->next; } if (!p->next || j > i - 1) { return ERROR; } q = p->next; p->next = q->next; *e = q->data; free(q); return OK; } /* * 根据位置获取元素 */ Status GetElem(LinkList L, int i, ElemType *e) { int j = 1; LinkList p = L->next; while (p && j < i) { j++; p = p->next; } if (!p || j > i) { return ERROR; } *e = p->data; return OK; }

“数据结构实验1班”实验报告