动态顺序表
顺序表基本概念顺序表基本数据结构用数组表示用指针表示
线性表基本操作初始化动态分配内存插入元素删除元素
完整的测试用例
顺序表基本概念
顺序表是用一组连输地址实现的线性表,其优点是可以随机访问表中元素和修改指定位置元素比较简单,但插入和删除元素需要移动元素,表长扩展也比较麻烦.
顺序表基本数据结构
用数组表示
用一维数组来表示顺序表，这样实现方法较为简单但数组大小确定后无法更改难以适应表长的变化。
typedef struct{
ElenType data[MaxSize]; //用长度为MaxSize的数组来存储元素
int length; //length表示表中数据个数
｝SeqList;
用指针表示
使用指针的好处是可以动态的分配线性表的长度，但使用时要注意指针越界和指针悬空的情况。
typedef struct{
ElemType *data; //定义线性表指针用以动态分配内存
int MaxSize,Length;
//MaxSize表示线性表最大长度，Length表是表内元素个数
}SeqList;
用指针的好处是可以动态的分配内存.来增加表的长度
线性表基本操作
初始化
初始化线性表，为线性表分配空间。用size记录线性表空间大小，用Length记录线性表中元素的个数。
//初始化线性表
SeqList intList(int Size){
SeqList T;
//分配空间
T.data = (ElemType*)malloc(sizeof(ElemType)*Size);
T.MaxSize = Size; //更新数组参数
T.Length = 0; //更新数组参数
return T;
}
动态分配内存
当线性表内存不足时再给线性表分配size个存贮空间，注意重定位使原来表中的元素不至于丢失。
//增加线性表长度
SeqList toLong(SeqList T){
ElemType *p = T.data;
int SizeNew = T.MaxSize+MAXSIZE;
//重新分配空间
T.data = (ElemType*)malloc(sizeof(ElemType)*SizeNew);
T.data = p; //重新定位
T.MaxSize = SizeNew; //更新参数
return T;
}
插入元素
在表尾插入元素时只需将元素添加到表的末端即可（相当于添加元素），若在表中插入元素则需要后移元素，同时当表空间不足时当掉用增加空间的函数。
//插入元素e
SeqList listInsert (SeqList T,int i,ElemType e){
int j;
if(i<1){
//输入参数小于1
printf("\n参数不合法\n");
return T;
}else{
if(i<=T.MaxSize){
if(T.Length<T.MaxSize){
if(i>T.Length){
//表未满，插入位置在表尾后
for(j=T.Length;j<i-1;j++){
T.data[j] = 0;
}
T.data[i-1] = e;
T.Length = i;
return T;
}else{
//表未满，插入位置在表中
for(j=T.Length;j>=i;j--){
T.data[j] = T.data[j-1];
}
T.data[i-1] = e;
T.Length = T.Length +1;
return T;
}
}else{
//表满，在表尾插入
T = toLong(T);
T.data[T.Length] = T.data[T.Length-1];
T.data[T.Length] = e;
T.Length++;
return T;
}
}else{
//在表最大长度后插入
while(i>T.MaxSize){
T = toLong(T);
}
for(j=T.Length;j<i-1;j++){
T.data[j] = 0;
}
T.data[i-1] = e;
T.Length = i;
return T;
}
}
}
删除元素
与插入操作类似，在表中插入元素需要移动元素。
SeqList listDelete (SeqList T,int i){
int j;
if(i<1 || i>T.Length){
printf("参数不合法");
return T;
}else{
for(j=i-1;j<T.Length-1;j++){
T.data[j] = T.data[j+1];
}
T.data[T.Length-1] = 0;
T.Length--;
return T;
}
}
完整的测试用例
/*此程序用以动态分配顺序线性表，主函数已作出测试。
若使用可将整数类型替换为指针来建立广义表。
作者：姚帅 未经允许不得转载*/
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h> //载入分配空间的头文件
#define MAXSIZE 10 //定义每次线性表增加长度
typedef int ElemType;
typedef struct{
ElemType *data; //定义线性表指针用以动态分配内存
int MaxSize,Length;
//MaxSize表示线性表最大长度，Length表是表内元素个数
}SeqList;
SeqList intList (int Size); //初始化线性表
SeqList toLong (SeqList T); //增加线性表长度
int getMaxSize (SeqList T); //获得表最大长度
int getLength (SeqList T); //获得表中元素个数
ElemType getElem (SeqList T,int i); //获得表中第i个元素
SeqList setElem (SeqList T,int i,ElemType e); //替换T中i位置的元素为e
int locateElem (SeqList T, ElemType e); //找出e在表中的位置
SeqList listInsert (SeqList T,int i,ElemType e); //在表中位置i处插入元素e
SeqList listDelete (SeqList T,int i); //删除表中位置i上的元素
bool empty (SeqList T); //检查表 是否为空
void destroyList (SeqList T); //销毁表
int main(){
int i,j;
//scanf("请输入初始数组长度",&i); //用i储存输入的初始长度
i = 10;
SeqList T = intList(i); //初始化线性表T
//设置T中元素为自然数列
for(j=1;j<=T.MaxSize;j++){
T = listInsert(T,j,j);
}
printf("\n设置数组初始状态\n");
//输出T所有元素
for(j=1;j<=T.Length;j++){
printf("%d_",getElem(T,j));
}
T = setElem(T,15 ,11);
printf("\n替换元素后数组状态\n");
//输出T所有元素
for(j=1;j<=T.Length;j++){
printf("%d_",getElem(T,j));
}
T = listInsert (T,25,12);
printf("\n插入元素后数组状态\n");
//输出T所有元素
for(j=1;j<=T.Length;j++){
printf("%d_",getElem(T,j));
}
T = listDelete(T,9);
printf("\n删除元素后数组状态\n");
for(j=1;j<=T.Length;j++){
printf("%d_",getElem(T,j));
}
printf("\n%d处的元素是%d",6,getElem(T,6));
printf("\n%d所在的位置是%d",11,locateElem(T,11));
getchar();
}
//初始化线性表
SeqList intList(int Size){
SeqList T;
//分配空间
T.data = (ElemType*)malloc(sizeof(ElemType)*Size);
T.MaxSize = Size; //更新数组参数
T.Length = 0; //更新数组参数
return T;
}
//增加线性表长度
SeqList toLong(SeqList T){
ElemType *p = T.data;
int SizeNew = T.MaxSize+MAXSIZE;
//重新分配空间
T.data = (ElemType*)malloc(sizeof(ElemType)*SizeNew);
T.data = p; //重新定位
T.MaxSize = SizeNew; //更新参数
return T;
}
//获得最大表长
int getMaxSize (SeqList T){
return T.MaxSize;
}
//获得表中元素个数
int getLength (SeqList T){
return T.Length;
}
//获得i处的元素
ElemType getElem (SeqList T, int i){
if(i>0 && i<=T.Length){
return T.data[i-1];
}else{
return 0;
}
}
//找到元素e的位置
int locateElem (SeqList T, ElemType e){
int i;
for(i = 0;i<T.Length;i++){
if(T.data[i] == e){
break;
}
}
if(i == T.Length){
return -1;
}else{
return i+1;
}
}
//插入元素e
SeqList listInsert (SeqList T,int i,ElemType e){
int j;
if(i<1){
//输入参数小于1
printf("\n参数不合法\n");
return T;
}else{
if(i<=T.MaxSize){
if(T.Length<T.MaxSize){
if(i>T.Length){
//表未满，插入位置在表尾后
for(j=T.Length;j<i-1;j++){
T.data[j] = 0;
}
T.data[i-1] = e;
T.Length = i;
return T;
}else{
//表未满，插入位置在表中
for(j=T.Length;j>=i;j--){
T.data[j] = T.data[j-1];
}
T.data[i-1] = e;
T.Length = T.Length +1;
return T;
}
}else{
//表满，在表尾插入
T = toLong(T);
T.data[T.Length] = T.data[T.Length-1];
T.data[T.Length] = e;
T.Length++;
return T;
}
}else{
//在表最大长度后插入
while(i>T.MaxSize){
T = toLong(T);
}
for(j=T.Length;j<i-1;j++){
T.data[j] = 0;
}
T.data[i-1] = e;
T.Length = i;
return T;
}
}
}
//删除i位置的元素
SeqList listDelete (SeqList T,int i){
int j;
if(i<1 || i>T.Length){
printf("参数不合法");
return T;
}else{
for(j=i-1;j<T.Length-1;j++){
T.data[j] = T.data[j+1];
}
T.data[T.Length-1] = 0;
T.Length--;
return T;
}
}
//判断表是否为空
bool empty (SeqList T){
if(T.Length == 0){
return true;
}else{
return false;
}
}
void destroyList (SeqList T){
free(T.data);
T.Length = 0;
T.MaxSize = 0;
}
//设置i位置的元素
SeqList setElem (SeqList T,int i,ElemType e){
int j;
if(i<1){
printf("参数不合法");
return T;
}else{
if(i<=T.Length){
//在表中设置元素
T.data[i-1] = e;
return T;
}else{
if(i<=T.MaxSize){
//在表尾后，最大表长内设置
for(j=T.Length;j<i-1;j++){
T.data[j] = 0;
}
T.data[i-1] = e;
T.Length = i;
return T;
}else{
//在最大表长后设置
while(T.MaxSize<i){
T = toLong(T);
}
for(j=T.Length;j<i-1;j++){
T.data[j] = 0;
}
T.data[i-1] = e;
T.Length = i;
return T;
}
}
}
}
测试用例运行效果图
