线性结构--->线性表实现

算法介绍本篇代码中常见的 为什么有三种 请先阅读这一部分这个是重点 需看 代码实现 下面的只可以在 DevC win10 64位运行在这个可以在 VS 运行也可在 DevC 运行最近一次更改 我的代码 需要的 直接看这一个 仅供参考 有错误望指出

算法介绍

对线性表进行:

创建 initList 追加 appendList 遍历 traverseList 插入 insertList 删除 deleteList 排序 sortList 反转 inversionList

本篇代码中常见的 ???

为什么有三种? 请先阅读这一部分

最初是在 DevC++上写的成功后发现 不能在 VS2010上运行 所以做了改进 可以在 vs2010 运行, 后来发现我写的 代码规范 和 严太太所编书上的 不太相同 所以又做了改进, 也就是 最下边 那个 所以 请直接看 目录—>3.3 !!!

这个是重点, 需看

因为 习惯问题, 所有的函数 采用了 驼峰命名法 (严太太书上 的 都是所有单词的 首字母大写) 在 void 类型的函数中 同样也写了 return 语句

原因: 即使函数无返回值, 也要加上 return语句, 以表明, 此函数体的代码 到此结束结束

测试时 基本都是 用的 int 类型

其他的 请自行更改相应代码, 更改为 其他类型, 例如 char 类型, 请注意 要把 输出的格式 要更改

代码实现

下面的只可以在 DevC++ (win10 64位)运行

写的 不太规范, 但主要算法都已实现

#include <stdio.h> #include <stdbool.h> //包含 bool #include <malloc.h> #define LISTLENGTH 6 //初始长度 6 #define LISTINCREMENT 6 //自增长长度 为 10, 单位 sizeof(ElemType) typedef char ElemType; //测试 为 char 类型 typedef struct { int cnt; // 有效长度 int len; //线性表长度 ElemType *pBase; //基地址 } LIST; bool initList(LIST *pList); //创建 bool appendList(LIST *pList, ElemType val);//追加 bool isFull(LIST *pList);//是否 满 bool isEmpty(LIST *pList);//是否 空 void showList(LIST *pList);// 显示 bool insertList(LIST *pList, int pos, ElemType insert_val);//插 bool deleteList(LIST *pList, int pos, ElemType *pDelete_val);//删 bool inverseList( LIST *pList); //反转 int main() { LIST list; ElemType delete_val; initList(&list); //以下为测试 // appendList(&list, 1); // appendList(&list, 2); // appendList(&list, 3); // appendList(&list, 4); // appendList(&list, 5); // appendList(&list, 6); appendList(&list, 'a'); appendList(&list, 'b'); appendList(&list, 'c'); appendList(&list, 'd'); appendList(&list, 'e'); appendList(&list, 'f'); // appendList(&list, 1.1); // appendList(&list, 2.2); // appendList(&list, 3.3); // appendList(&list, 4.4); // appendList(&list, 5.5); // appendList(&list, 6.6); showList(&list); if( insertList(&list, 6, 'w')) { printf("插入成功!!\n显示: "); showList(&list); } if( deleteList(&list, 6, &delete_val)) { // printf("删除成功, 你删除的值为: %d\n删除后的线性表为: ", delete_val); printf("删除成功, 你删除的值为: %c\n删除后的线性表为: ", delete_val); // printf("删除成功, 你删除的值为: %.2f\n删除后的线性表为: ", delete_val); // printf("删除成功, 你删除的值为: %.2lf\n删除后的线性表为: ", delete_val); showList(&list); } if(inverseList(&list)){ printf("反转成功!!\n显示: "); showList(&list); } return 0; } bool inverseList( LIST *pList){ int i = 0; int j = pList->cnt - 1; ElemType temp; if( isEmpty(pList) ){ printf("线性表为空,反转失败!!\n"); return false; } while(i < j){ temp = pList->pBase[i]; pList->pBase[i] = pList->pBase[j]; pList->pBase[j] = temp; i++; j--; } return true; } bool deleteList(LIST *pList, int pos, ElemType *pDelete_val) { int i; if(pos < 0 || pos > pList->cnt) { printf("输入的位置无效,删除失败!!\n"); return false; } if(isEmpty(pList)) { printf("线性表为空,删除失败!!\n"); return false; } *pDelete_val = pList->pBase[pos-1]; for(i = pos-1; i < pList->cnt; i++) { pList->pBase[i] = pList->pBase[i+1]; } (pList->cnt)--; return true; } bool insertList(LIST *pList, int pos, ElemType insert_val) { int i; //这两个 被注释掉 的if 是 线性表 未实现 自增长 前的 判断代码 // if(pos < 0 || pos > pList->cnt){ // printf("输入的位置无效,插入失败!!\n"); // return false; // } // if(isFull(pList)){ // printf("线性表已满,插入失败!!\n"); // return false; // } //这两个 的if 是 线性表 实现 自增长 后的 判断代码 if(pos < 0 || pos > pList->cnt+1) { printf("输入的位置无效,插入失败!!\n"); return false; } if( pList->cnt >= pList->len) { ElemType * pNewBase = (ElemType *)realloc(pList->pBase,sizeof(ElemType)*LISTINCREMENT); if(pNewBase == NULL) { printf("内存分配失败!!--线性表自增长失败--插入失败\n"); return false; } pList->pBase = pNewBase; pList->len += LISTINCREMENT; } for(i = pList->cnt; i >= pos; i--) pList->pBase[i] = pList->pBase[i-1]; pList->pBase[pos-1] = insert_val; (pList->cnt)++; return true; } void showList(LIST *pList) { int i = 0; while(i < pList->cnt) { // printf("%d ", pList->pBase[i]); printf("%c ", pList->pBase[i]); // printf("%.2f ", pList->pBase[i]); // printf("%.2lf ", pList->pBase[i]); i++; } printf("\n"); return; } bool isEmpty(LIST *pList) { if(pList->cnt == 0) return true; else return false; } bool isFull(LIST *pList){ if(pList->len == pList->cnt) return true; else return false; } bool appendList(LIST *pList, ElemType val) { if(isFull(pList)){ printf("线性表已满!!\n"); return false; }else{ pList->pBase[pList->cnt] = val; (pList->cnt)++; printf("追加成功!!\n"); return true; } } bool initList(LIST *pList) { pList->pBase = (ElemType *)malloc(sizeof(ElemType) * LISTLENGTH); if(pList != NULL){ pList->cnt = 0; pList->len = LISTLENGTH; return true; }else{ printf("分配失败!\n"); return false; } }

在这个可以在 VS 运行(也可在 DevC++ 运行)

#include <stdio.h> #include <malloc.h> #define LISTLENGTH 6 //初始长度 6 #define LISTINCREMENT 6 //自增长长度 为 10, 单位 sizeof(ElemType) #define true 1 #define false 0 typedef int boolean; typedef char ElemType; //测试 为 char 类型 typedef struct { int cnt; // 有效长度 int len; //线性表长度 ElemType *pBase; //基地址 } LIST; boolean initList(LIST *pList); //创建 boolean appendList(LIST *pList, ElemType val);//追加 boolean isFull(LIST *pList);//是否 满 boolean isEmpty(LIST *pList);//是否 空 void showList(LIST *pList);// 显示 boolean insertList(LIST *pList, int pos, ElemType insert_val);//插 boolean deleteList(LIST *pList, int pos, ElemType *pDelete_val);//删 boolean inverseList( LIST *pList); //反转 int main() { LIST list; ElemType delete_val; initList(&list); //以下为测试 // appendList(&list, 1); // appendList(&list, 2); // appendList(&list, 3); // appendList(&list, 4); // appendList(&list, 5); // appendList(&list, 6); appendList(&list, 'a'); appendList(&list, 'b'); appendList(&list, 'c'); appendList(&list, 'd'); appendList(&list, 'e'); appendList(&list, 'f'); // appendList(&list, 1.1); // appendList(&list, 2.2); // appendList(&list, 3.3); // appendList(&list, 4.4); // appendList(&list, 5.5); // appendList(&list, 6.6); showList(&list); if( insertList(&list, 6, 'w')) { printf("插入成功!!\n显示: "); showList(&list); } if( deleteList(&list, 6, &delete_val)) { // printf("删除成功, 你删除的值为: %d\n删除后的线性表为: ", delete_val); printf("删除成功, 你删除的值为: %c\n删除后的线性表为: ", delete_val); // printf("删除成功, 你删除的值为: %.2f\n删除后的线性表为: ", delete_val); // printf("删除成功, 你删除的值为: %.2lf\n删除后的线性表为: ", delete_val); showList(&list); } if(inverseList(&list)){ printf("反转成功!!\n显示: "); showList(&list); } return 0; } boolean inverseList( LIST *pList){ int i = 0; int j = pList->cnt - 1; ElemType temp; if( isEmpty(pList) ){ printf("线性表为空,反转失败!!\n"); return false; } while(i < j){ temp = pList->pBase[i]; pList->pBase[i] = pList->pBase[j]; pList->pBase[j] = temp; i++; j--; } return true; } boolean deleteList(LIST *pList, int pos, ElemType *pDelete_val) { int i; if(pos < 0 || pos > pList->cnt) { printf("输入的位置无效,删除失败!!\n"); return false; } if(isEmpty(pList)) { printf("线性表为空,删除失败!!\n"); return false; } *pDelete_val = pList->pBase[pos-1]; for(i = pos-1; i < pList->cnt; i++) { pList->pBase[i] = pList->pBase[i+1]; } (pList->cnt)--; return true; } boolean insertList(LIST *pList, int pos, ElemType insert_val) { int i; //这两个 被注释掉 的if 是 线性表 未实现 自增长 前的 判断代码 // if(pos < 0 || pos > pList->cnt){ // printf("输入的位置无效,插入失败!!\n"); // return false; // } // if(isFull(pList)){ // printf("线性表已满,插入失败!!\n"); // return false; // } //这两个 的if 是 线性表 实现 自增长 后的 判断代码 if(pos < 0 || pos > pList->cnt+1) { printf("输入的位置无效,插入失败!!\n"); return false; } if( pList->cnt >= pList->len) { ElemType * pNewBase = (ElemType *)realloc(pList->pBase,sizeof(ElemType)*LISTINCREMENT); if(pNewBase == NULL) { printf("内存分配失败!!--线性表自增长失败--插入失败\n"); return false; } pList->pBase = pNewBase; pList->len += LISTINCREMENT; } for(i = pList->cnt; i >= pos; i--) pList->pBase[i] = pList->pBase[i-1]; pList->pBase[pos-1] = insert_val; (pList->cnt)++; return true; } void showList(LIST *pList) { int i = 0; while(i < pList->cnt) { // printf("%d ", pList->pBase[i]); printf("%c ", pList->pBase[i]); // printf("%.2f ", pList->pBase[i]); // printf("%.2lf ", pList->pBase[i]); i++; } printf("\n"); return; } boolean isEmpty(LIST *pList) { if(pList->cnt == 0) return true; else return false; } boolean isFull(LIST *pList){ if(pList->len == pList->cnt) return true; else return false; } boolean appendList(LIST *pList, ElemType val) { if(isFull(pList)){ printf("线性表已满!!\n"); return false; }else{ pList->pBase[pList->cnt] = val; (pList->cnt)++; printf("追加成功!!\n"); return true; } } boolean initList(LIST *pList) { pList->pBase = (ElemType *)malloc(sizeof(ElemType) * LISTLENGTH); if(pList != NULL){ pList->cnt = 0; pList->len = LISTLENGTH; return true; }else{ printf("分配失败!\n"); return false; } } -------------------------2016年9月6日-------------------------

最近一次更改 我的代码, 需要的 直接看这一个

#include <stdio.h> #include <stdlib.h> #include <malloc.h> #define LISTSIZE 6 //线性表 初始长度 #define LISTINCREMENT 6 //线性表 自动增长长度 #define false 0 #define true 1 typedef int Status; typedef int ElemType; //定义 一个结构体 typedef struct{ ElemType *pBase; //线性表 基地址 int cnt; //线性表 有效长度 (即线性表 中 元素的 个数) int len; //线性表 长度 (即线性表 所能容纳 元素 的最大个数) } *PLIST, LIST; /* 一个线性表的基本操作 有; 1.创建表 //需考虑 系统为线性表 分配的内存 是否 为 NULL 2.追加元素 //追加元素就是 在末尾 添加元素 *这时候 你就要考虑 线性表长度 是否够用* 3.插入元素 // 也需要考虑 线性表 是否考虑 线性表长度 是否够用 4.删除元素 // 需考虑 参数 的 位置 是否存在, 5.遍历线性表元素 // 需考虑 线性表 是否为空表 或者再加上 6. 对线性表元素 进行排序 7. 对线性表元素 进行反转 等 ..... 其他操作 */ void initList(PLIST plist); void appendList(PLIST plist, ElemType e); Status listEmpty(PLIST plist); void traverseList( PLIST pList); Status insertList(PLIST pList, int pos, ElemType e); Status deleteList(PLIST pList, int pos, ElemType *e); void sortList(PLIST pList); void inversionList(PLIST pList); int main(){ LIST list; ElemType delete_e; //创建一个线性表 initList(&list); //追加元素 appendList(&list, 12); appendList(&list, 11); appendList(&list, 31); appendList(&list, 4); appendList(&list, 53); appendList(&list, 612); //appendList(&list, 7); //遍历 线性表 traverseList(&list); //插入元素 if( insertList(&list, 6, 99) ){ printf("插入成功!!!\n"); traverseList(&list); }else{ printf("插入失败!!!\n"); } //删除元素 if( deleteList(&list, 6, &delete_e) ){ printf("删除成功!!! 删除的元素的值为: %d\n删除元素后的表为:\n", delete_e); traverseList(&list); }else{ printf("删除失败!!!\n"); } //对线性表元素进行 排序, sortList(&list); traverseList(&list); //对线性表元素进行 反转 inversionList(&list); traverseList(&list); return 0; } //线性表 反转函数 void inversionList(PLIST pList){ int i = 0; int j = pList->cnt-1; ElemType temp; if(pList->cnt < 2){ return; } while(i < j){ temp = pList->pBase[i]; pList->pBase[i] = pList->pBase[j]; pList->pBase[j] = temp; ++i; --j; } return ; } //线性表 排序函数 void sortList(PLIST pList){ //这里我选择了最简单的 冒泡排序 int i, j; ElemType temp; if( pList->cnt < 2){ return ; } for(i = 0; i < pList->cnt; i++){ for(j = i+1; j <= pList->cnt -1; ++j ){ if(pList->pBase[i] > pList->pBase[j]){ temp = pList->pBase[j]; pList->pBase[j] = pList->pBase[i]; pList->pBase[i] = temp; } } } return; } 线性表 删除特定位置元素函数 Status deleteList(PLIST pList, int pos, ElemType *e){ if(pos < 1 && pos > pList->cnt){ printf("删除位置无效!!!\n"); return false; } *e = pList->pBase[pos-1]; for(; pos < pList->cnt; pos++){ pList->pBase[pos-1] = pList->pBase[pos]; } (pList->cnt)--; return true; } //线性表 特定位置插入元素函数 Status insertList(PLIST pList, int pos, ElemType e){ int i; //首先要判断 插入位置是否合理 if(pos < 1 && pos > pList->cnt + 1){ printf("插入位置无效!!!\n"); return false; } //之后再判断 线性表 是否 已满 if(pList->cnt >= pList->len){ ElemType *newBase; newBase = (ElemType *)realloc(pList->pBase, sizeof(ElemType) * (pList->len + LISTINCREMENT)); if(newBase == NULL){ printf("线性表自动增长: 内存分配失败!!\n程序终止........"); exit(-1); } pList->pBase = newBase; pList->len += LISTINCREMENT; } for(i = pList->cnt; i >= pos ; --i){ pList->pBase[i] = pList->pBase[i-1]; } pList->pBase[pos-1] = e; ++(pList->cnt); return true; } //线性表 遍历元素函数 void traverseList( PLIST pList){ int i; //先判断 线性表 是否 为 空 if( listEmpty(pList) ){ return; } for(i = 0; i < pList->cnt; i++){ if(i != pList->cnt -1) printf("%d ", pList->pBase[i]); else printf("%d\n\n", pList->pBase[i]); } return; } //判断线性表 是否为空函数 Status listEmpty(PLIST pList){ if(pList->cnt == 0){ printf("线性表: 为空!!!!!!\n"); return true; } return false; } //线性表 追加元素函数 void appendList(PLIST pList, ElemType e){ //先判断线性表 是否已满, 已满则自动增长长度 if(pList->cnt == pList->len){ ElemType *newBase; //新的基地址 newBase = (ElemType *)realloc(pList->pBase, sizeof(ElemType)*(pList->len + LISTINCREMENT)); //realloc 函数的 用法请自行查阅文档 ,以便更好理解程序 if(newBase == NULL){ printf("线性表自动增长: 内存分配失败!!\n程序终止........"); exit(-1); } pList->pBase = newBase; pList->len += LISTINCREMENT; } pList->pBase[pList->cnt] = e; ++(pList->cnt); return; } //线性表 创建函数 void initList(PLIST plist){ plist->pBase = (ElemType *)malloc(sizeof(ElemType) * LISTSIZE); if(plist->pBase == NULL){ printf("初始线性表: 内存分配失败!!\n程序终止........"); exit(-1); //此函数 含于 stdlib.h 头文件中, }else{ plist->cnt = 0; plist->len = LISTSIZE; } return ; //因为 此函数 无返回值, 但是加上 return 更好, 以此表名:此函数代码 已写完 }

仅供参考 ,有错误望指出.

有大神路过请指点一下。 菜鸟求飞 ！!! 有什么疑问 也可以在 下边 提问 ! （有点托大了）或者发邮件 E-Mail:ppbboddqq.qq@qq.com