关于线性表的概念, 等相关描述请参看《大话数据结构》第三章的内容,
1 概念
线性表 list: 零个或多个数据的有限序列.
可以这么理解: 糖葫芦都吃过吧, 它就相当于一个线性表, 每个山楂就相当于线性表中的数据.(这很类似与线性表的顺序存储结构)
线性表有两种存储结构, 顺序存储结构和链式存储结构, 对线性表的操作包括: 初始化, 判空, 清空, 查找元素(返回元素和返回元素位置), 插入, 删除, 线性表长度等, 今天先放线性表顺序存储结构操作的代码实现, 有参考高一凡大师的代码.
2 代码
代码分成三个文件, 一个头文件, 两个 cpp 文件, sqlist.h 头文件, 实现线性表顺序存储结构, 函数的声明, 宏定义等, 其中一个 sqlist.cpp 文件实现对线性表的操作, 另一个 sqlist_main.cpp 文件实现测试功能.
以下代码在 vs2013 中亲测有效
头文件 sqlist.h
- #ifndef _SQLIST_H
- #define _SQLIST_H
- #define MAXSIZE 10
- #define LISTINSREMENT 2
- #define OK 1
- #define ERROR 0
- #define FALSE 0
- #define TRUE 1
- typedef int Status;
- typedef int ElemType;
- typedef struct
- {
- ElemType *elem;
- int length;// 当前长度
- int listsize;// 分配的总大小 (按 sizeof(ElemType) 的整数倍计)
- }Sqlist;
- Status InitList(Sqlist* L);
- Status DestroyList(Sqlist* L);
- Status ListEmpty(Sqlist L);
- Status CleanList(Sqlist* L);
- int ListLength(Sqlist L);
- Status ListInsert(Sqlist* L, int i, ElemType e);
- Status ListDelete(Sqlist* L, int i, ElemType* e);
- Status GetElem(Sqlist* L, int i, ElemType *e);
- Status LocateElem(Sqlist L, ElemType e);
- #endif
sqlist.cpp 文件
- #include "sqlist.h"
- #include <iostream>
- #include <assert.h>
- using namespace std;
- /*init sqlist*/
- Status InitList(Sqlist* L)
- {
- (*L).elem = (ElemType*)malloc(MAXSIZE * sizeof(ElemType));
- assert(NULL != (*L).elem);
- (*L).length = 0;
- (*L).listsize = MAXSIZE;
- return OK;
- }
- //destroy list
- Status DestroyList(Sqlist* L)
- {
- free((*L).elem);
- (*L).elem = NULL;
- (*L).length = 0;
- (*L).listsize = 0;
- return OK;
- }
- //list is empty return true
- Status ListEmpty(Sqlist L)
- {
- if (0 == L.length)
- return TRUE;
- else
- return FALSE;
- }
- //clean list
- // 前提: 顺序表存在
- Status CleanList(Sqlist* L)
- {
- if (NULL != (*L).elem)
- {
- (*L).length = 0;
- return OK;
- }
- else
- return ERROR;
- }
- //return list length
- int ListLength(Sqlist L)
- {
- if (NULL != L.elem)
- {
- return L.length;
- }
- else
- return ERROR;
- }
- //insert elem
- // 前提: 顺序表存在
- //1 判断 i 合法
- //2 顺序表未满, 若满, 增加内存分配
- //3 插入时, 第 i 个及之后元素后移
- // 操作结果在第 i 个前面插入新元素, 长度加 1
- Status ListInsert(Sqlist* L, int i, ElemType e)
- {
- ElemType *newbase = NULL, *p = NULL, *q = NULL;
- if (NULL != (*L).elem)// 顺序表存在
- {
- assert(!(i <1 || i>(*L).length + 1));// i 不合法
- if ((*L).listsize <= (*L).length)// 分配内存不够
- {
- newbase = (ElemType*)realloc((*L).elem, (((*L).listsize + LISTINSREMENT) * sizeof(ElemType)));
- assert(NULL != newbase);
- (*L).elem = newbase;
- (*L).listsize += LISTINSREMENT;
- }
- q = (*L).elem + i - 1;// 新元素存放位置
- for (p = (*L).elem + (*L).length - 1; p>= q; p--)// 第 i 个元素后的元素后移一位
- {
- *(p + 1) = *p;
- }
- *q = e;
- (*L).length++;
- return OK;
- }
- else
- return ERROR;
- }
- //delete elem
- // 前提: 顺序表存在
- //i 是否合法
- // 删除第 i 个位置的元素并返回这个值
- Status ListDelete(Sqlist* L, int i, ElemType* e)
- {
- ElemType *p = NULL;
- if (NULL != (*L).elem)
- {
- assert(!(i <1 || i>(*L).length));
- p = (*L).elem + i - 1;
- *e = *p;
- for (p; p <(*L).elem + (*L).length - 1; p++)
- {
- *p = *(p + 1);
- }
- (*L).length--;
- return OK;
- }
- else
- return ERROR;
- }
- //get elem
- // 前提: 顺序表存在
- // 判断 i 的合法性
- // 获得第 i 个位置的元素并返回其值
- Status GetElem(Sqlist* L, int i, ElemType *e)
- {
- ElemType *p = NULL;
- if (NULL != (*L).elem)
- {
- assert(!(i<1 || i>(*L).length));
- p = (*L).elem + i - 1;
- *e = *p;
- return OK;
- }
- else
- return ERROR;
- }
- //find elem
- // 前提: 顺序表存在
- // 查找结束后 i 时候在正确范围内
- // 返回元素在表中的序号
- Status LocateElem(Sqlist L, ElemType e)
- {
- int i = 1;
- if (NULL != L.elem)
- {
- while (i <= L.length && !(*L.elem++ == e))
- i++;
- return i;
- /*for (i = 0; i <L.length; i++)
- {
- if (e == L.elem[i])
- break;
- }
- if(i+1 <= L.length )
- return i+1;
- else
- return ERROR;
- 思路正确, 但不够简练
- */
- }
- else
- return ERROR;
- }
sqlist_main.cpp 文件
- #include "sqlist.h"
- #include <iostream>
- #include <assert.h>
- using namespace std;
- int main()
- {
- Sqlist SL;
- Status ret;
- int i = 0;
- ElemType e;
- ret = InitList(&SL);
- cout << "init success,ret is:" << ret << endl;
- ret = ListEmpty(SL);
- cout << "return 1 is empty, ret is:" << ret << endl;
- ret = CleanList(&SL);
- cout << "return 1 mean clean success, ret is:" << ret << endl;
- for (i = 1; i < 10; i++)
- {
- ret = ListInsert(&SL, i, i);// 从头到尾插入 9 个数
- //cout << ret << endl;
- }
- ret = ListDelete(&SL, 2, &e);
- cout << "delete success return 1, ret is" << ret << "e is:" << e << endl;
- for (i = 0; i < SL.length; i++)// 打印
- {
- cout << SL.elem[i] << endl;
- }
- ret = ListLength(SL);
- cout << "SL length is:" << ret << endl;
- ret = GetElem(&SL, 3, &e);
- cout << "get success return 1, ret is" << ret << "e is:" << e << endl;
- ret = LocateElem(SL, 4);
- cout << "e loctation is:" << ret << endl;
- ret = DestroyList(&SL);
- cout << "destroy success, ret is:" << ret << endl;
- system("pause");
- return 0;
- }
不当之处请多多指点.
来源: https://www.cnblogs.com/MisterXu/p/11173044.html