C语言线性表基本操作

纯C语言写的线性表基本操作 程序段：/*线性表的操作*/ #include<stdio.h> #include<stdlib.h> typedef int ElemType; struct List { ElemType *list; int size; int MaxSize; }; /*初始化列表,即动态存储空间分配并置L为一个空列表*/ void initList(struct List *L,int ms) { if(ms<=0) { printf("MaxSize 非法！"); exit(1); } L->MaxSize = ms; L->size = 0; L->list=malloc(ms * sizeof(ElemType)); if(!L->list) { printf("空间分配失败！"); exit(1); } /*printf("%d\n",sizeof(ElemType));*//*暂用字节数*/ return ; } 《C语言线性表基本操作》 在C语言中，线性表是一种常见的数据结构，它是由n（n>=0）个相同类型元素构成的有限序列。本文将介绍如何使用C语言实现线性表的基本操作，包括初始化、插入、获取元素、遍历以及更新元素。 线性表的实现通常采用链表或数组的形式。这里采用数组来存储线性表，因为数组具有随机访问的优势，且在某些场景下，如内存管理更简单。线性表的结构定义如下： ```c typedef int ElemType; struct List{ ElemType *list; // 存储线性表元素的指针 int size; // 当前元素数量 int MaxSize; // 线性表的最大容量 }; ``` 线性表的初始化是创建一个空列表，动态分配内存空间，并设置最大容量。`initList`函数完成了这个任务： ```c void initList(struct List *L, int ms){ if(ms <= 0){ printf("MaxSize 非法！"); exit(1); } L->MaxSize = ms; L->size = 0; L->list = malloc(ms * sizeof(ElemType)); if(!L->list){ printf("空间分配失败！"); exit(1); } return ; } ``` 当线性表满时，需要扩展存储空间。`againMalloc`函数用于重新分配更大的内存空间，将原容量翻倍： ```c void againMalloc(struct List *L){ ElemType *p = realloc(L->list, 2*L->MaxSize * sizeof(ElemType)); if(!p){ printf("存储空间分配失败！"); exit(1); } L->list = p; // 使 list 指向新线性表空间 L->MaxSize = 2 * L->MaxSize; // 把线性空间大小修改为新的长度 } ``` 线性表的插入操作有两种：在表尾插入和在任意位置插入。`insertLastList`函数实现了在表尾插入元素： ```c void insertLastList(struct List *L, ElemType x){ if(L->size == L->MaxSize){ printf("max"); } L->list[L->size] = x; L->size++; printf("x=%d\n", x); } ``` 而`insertPostList`函数允许在指定位置插入元素： ```c int insertPostList(struct List *L, int pos, ElemType x){ int i; if(pos < 1 || pos > L->size + 1){ return 0; // 若 Pos 越界则插入失败 } if(L->size == L->MaxSize){ againMalloc(L); // 重新分配更大的存储空间 } for(i = L->size; i >= pos; i--){ L->list[i] = L->list[i - 1]; } L->list[pos - 1] = x; L->size++; } ``` 获取线性表中指定位置的元素，通过`GetElem`函数实现： ```c ElemType GetElem(struct List *L, int pos){ if(pos < 1 || pos > L->size){ printf("元素序号越界！"); exit(1); } return L->list[pos - 1]; // 返回线性表中序号为 Pos 值的元素 } ``` 遍历输出线性表中的所有元素，`traverseList`函数可以完成这个功能： ```c void traverseList(struct List *L){ int i; for(i = 0; i < L->size; i++){ printf("%d ", L->list[i]); } printf("\n"); } ``` 查找线性表中等于特定值的元素，`findList`函数返回该元素的位置： ```c int findList(struct List *L, ElemType x){ int i; for(i = 0; i < L->size; i++){ if(L->list[i] == x){ return i; } } return -1; // 查找失败返回 -1 } ``` 更新线性表中指定位置的元素值，`updatePostList`函数完成此操作： ```c int updatePostList(struct List *L, int pos, ElemType x){ if(pos < 1 || pos > L->size){ return 0; // 位置越界，返回0 } L->list[pos - 1] = x; return 1; // 更新成功，返回1 } ``` 总结，上述代码实现了一个基于数组的线性表数据结构，包含了初始化、插入、获取、遍历、查找和更新等基本操作。这些操作对于理解和实现线性表的概念至关重要，也是C语言数据结构学习的基础。