Day 1 数据结构(1)

今天学习数据结构的顺序结构同时了解数据结构就是用来描述数据的结构数据的时间复杂度是随着数据量的增加程序运行时间与之有对应关系空间复杂度就是随着数据的增加所占用的空间与之有关系顺序结构有点像数组顺序结构的实现是通过定义一个结构体里面包含指向顺序表的指针以及总共可以放多少个数据和当前有多少个数据通过对指向顺序表的指针和当前有多少个数据来对顺序表进行例如创建顺序表添加删除插入等操作。下面是如何创建顺序表以及如何操作顺序表的方法#include seqlist.h #include stdio.h #include stdlib.h #include string.h /*************************************** *函数名:CreateSeqList *功能: * 创建空的顺序表 *参数: * Len:能够存放元素的个数 *返回值: * 成功返回 创建的顺序表的空间首地址 * 失败返回 NULL **************************************/ SeqList_t *CreateSeqList(int Len) { SeqList_t *pTmpList NULL; //1.申请标签空间 pTmpList malloc(sizeof(SeqList_t)); if (NULL pTmpList) { printf(malloc failed\n); return NULL; } //2.申请存放数据的空间 pTmpList-pData malloc(Len * sizeof(DataType)); if (NULL pTmpList-pData) { printf(malloc failed\n); return NULL; } //3.对标签的空间赋值 pTmpList-tLen Len; pTmpList-cLen 0; //4.对申请的数据空间赋值 memset(pTmpList-pData, 0, Len * sizeof(DataType)); //5.返回标签的首地址 return pTmpList; } /*************************************** *函数名:IsEmptySeqList *功能: * 判断顺序表是否为空 *参数: * pTmpList: 顺序表标签的首地址 *返回值: * 顺序表满 返回1 * 顺序表没满 返回0 **************************************/ int IsEmptySeqList(SeqList_t *pTmpList) { return pTmpList-cLen 0 ? 1 : 0; } /*************************************** *函数名:IsFullSeqList *功能: * 判断顺序表是否为满 *参数: * pTmpList: 顺序表标签的首地址 *返回值: * 顺序表满 返回1 * 顺序表没满 返回0 **************************************/ int IsFullSeqList(SeqList_t *pTmpList) { return pTmpList-cLen pTmpList-tLen ? 1 : 0; } /*************************************** *函数名:AppendSeqList *功能: * 在顺序表所有元素末尾添加一个元素 *参数: * pTmpList: 顺序表标签的首地址 * TmpData:要插入的元素 *返回值: * 成功返回0 * 失败返回-1 **************************************/ int AppendSeqList(SeqList_t *pTmpList, DataType TmpData) { //1.检测是否能够插入元素 if (IsFullSeqList(pTmpList)) { return -1; } //2.将元素插入在clen作为下标的位置处 pTmpList-pData[pTmpList-cLen] TmpData; //3.clen pTmpList-cLen; //4.返回0 return 0; } /*************************************** *函数名:ShowSeqList *功能: * 顺序表遍历查看所有元素的值 *参数: * pTmpList: 顺序表标签的首地址 *返回值: * 缺省 **************************************/ void ShowSeqList(SeqList_t *pTmpList) { int i 0; for (i 0; i pTmpList-cLen; i) { printf(%d , pTmpList-pData[i]); } printf(\n); return; } /*************************************** *函数名:InsertPosSeqList *功能: * 按照指定位置插入元素 *参数: * pTmpList: 顺序表标签的首地址 * TmpData:要插入的元素 * Pos:插入的位置 *返回值: * 成功返回0 * 顺序表已满 插入失败返回 -1 * 插入位置错误 返回 -2 **************************************/ int InsertPosSeqList(SeqList_t *pTmpList, DataType TmpData, int Pos) { int i 0; if (IsFullSeqList(pTmpList)) { return -1; } if (Pos 0 || Pos pTmpList-cLen) { return -2; } for (i pTmpList-cLen; i Pos; i--) { pTmpList-pData[i] pTmpList-pData[i-1]; } pTmpList-pData[Pos] TmpData; pTmpList-cLen; return 0; } /*************************************** *函数名:DeleteSeqList *功能: * 删除顺序表中的元素 *参数: * pTmpList: 顺序表标签的首地址 * TmpData:要删除的元素 *返回值: * 成功返回删除元素的个数 * 失败返回-1 **************************************/ int DeleteSeqList(SeqList_t *pTmpList, DataType TmpData) { int cnt 0; int i 0; int n 0; if (IsEmptySeqList(pTmpList)) { return -1; } for (i 0; i pTmpList-cLen;) { if (pTmpList-pData[i] TmpData) { pTmpList-cLen--; cnt; for (n i; n pTmpList-cLen; n) { pTmpList-pData[n] pTmpList-pData[n1]; } } else { i; } } return cnt; } /*************************************** *函数名:ReplaceSeqList *功能: * 将顺序表中的旧值用新值替换 *参数: * pTmpList: 顺序表标签的首地址 * OldData:旧值 * NewData:新值 *返回值: * 成功返回 修改元素的个数 * 失败返回 -1 **************************************/ int ReplaceSeqList(SeqList_t *pTmpList, DataType OldData, DataType NewData) { int i 0; int cnt 0; for (i 0; i pTmpList-cLen; i) { if (*(pTmpList-pData i) OldData) { *(pTmpList-pData i) NewData; cnt; } } return cnt; } /*************************************** *函数名:FindSeqListPos *功能: * 将顺序表中查找值对应的下标位置 *参数: * pTmpList: 顺序表标签的首地址 * TmpData: 要查找的元素 *返回值: * 成功返回 找到的元素的下标 * 失败返回 -1 * 如果元素不存在 返回 -2 **************************************/ int FindSeqListPos(SeqList_t *pTmpList, DataType TmpData) { int i 0; for (i 0; i pTmpList-cLen; i) { if (*(pTmpList-pData i) TmpData) { return i; } } return -2; } /*************************************** *函数名:DestroySeqList *功能: * 销毁顺序表回收空间 *参数: * ppTmpList 顺序表的首地址 *返回值: * 无 **************************************/ int DestroySeqList(SeqList_t **ppTmpList) { if ((*ppTmpList)-pData ! NULL) { free((*ppTmpList)-pData); } if ((*ppTmpList) ! NULL) { free(*ppTmpList); } *ppTmpList NULL; return 0; }