数据结构和算法问题分析及源代码之顺序表.doc
文本预览下载声明
顺序表
1 题目
编写一个程序,实现顺序表的各种基本运算,包括:
表操作:初始化顺序表、输出顺序表和释放顺序表
表元素操作:插入元素、删除元素、输出元素(注意元素的位置)
2 目标
熟悉顺序表的定义及其基本操作的实现
3 设计思想
设计顺序表的数据结构,表包括三个部分:表长度、表大小、数据区。数据进行顺序存放,在相邻的存储单元分配空间。
4 算法描述
初始化顺序表:申请一块默认大小的空间,给表长、表大小附初值。
插入元素:追加存储空间,指针下移指定位,后面元素从后往前依次后移,元素赋值插入。
删除元素:指针下移指定位,保存元素,后面元素从前往后依次前移,覆盖删除,释放数据元素空间。
获取元素:指针下移指定位,保存元素。
5 程序结构图
6 源程序
#define OK 1
#define ERROR 0
#define OVERFLOW -1
#define LIST_INIT_SIZE 100
#define LISTNCREMENT 10
typedef struct{
int * elem;
int length;
int listsize;
}SqList;
int InitList_Sq(SqList L){
L.elem=(int *)malloc(LIST_INIT_SIZE*sizeof(int));
if(!L.elem)exit(OVERFLOW);
L.length=0;
L.listsize=LIST_INIT_SIZE;
return OK;
}
int ListInsert_Sq(SqList L,int i,int e){
if(i1||iL.length+1)return ERROR;
if(L.length=L.listsize)
{
int * newbase=(int *)realloc(L.elem,(L.listsize+LISTNCREMENT)*sizeof(int));
if(!newbase)exit(OVERFLOW);
L.elem=newbase;
L.listsize+=LISTNCREMENT;
}
int * q=(L.elem[i-1]);
for(int *p=(L.elem[L.length-1]);p=q;--p)*(p+1)=*p;
*q=e;
++L.length;
return OK;
}
int ListDelete_Sq(SqList L,int i,int *e){
if((i1||iL.length))return ERROR;
int * p=(L.elem[i-1]);
*e=*p;
int *q=L.elem+L.length;
for(++p;pq;p++)*(p-1)=*p;
--L.length;
return OK;
}
int ListGet_Sq(SqList L,int i,int *e){
if((i1||iL.length))return ERROR;
*e=L.elem[i-1];
return OK;
}
int ListTrverse_Sq(SqList L){
if(!L.elem)return ERROR;
free(L.elem);
return OK;
}
int showlist(SqList L){
if(!L.elem||L.listsize0){
printf(顺序表不存在);
return 0;}
if(L.length==0)
{
printf(顺序表为空\n);
return 0;
}
printf(当前顺序表为:);
for(int i=0;iL.length;i++)
printf(%d,* (L.elem+i));
return 1;
}
显示全部