数据结构代码之顺序表(一)
数据结构代码的C实现以便以后参考,复习
#include <stdlib.h>
#define INIT_SIZE 5
#define INCREMENT 10
#define ElemType int
//链表结构体
typedef struct
{
//指向存储内容的指针
ElemType *elem;
//链表当前长度
int length;
//链表总长度
int size;
}List;
//初始化链表
int InitList(List *L)
{
//申请空间(连续的)
L->elem = (ElemType *)malloc(INIT_SIZE*sizeof(ElemType));
if(!L->elem)
return 0;
L->length = 0;
L->size = INIT_SIZE;
return 1;
}
//插入元素
int Insert(List *L,int i,ElemType e)
{
int j;
ElemType *newbase;
//判断插入点是否合法
if(i<1||i>L->length+1)
return 0;
//如果空间不够重新分配空间
if(L->length>=L->size)
{
newbase = (ElemType *)realloc(L->elem,(L->size+INCREMENT)*sizeof(ElemType));
if(!newbase)
return 0;
L->elem = newbase;
L->size += INCREMENT;
}
//把插入点以及之后的元素向后移动1位
for(j = L->length - 1;j >= i-1;j--)
{
L->elem[j+1] = L->elem[j];
}
//插入元素
L->elem[i-1]=e;
L->length++;
return 1;
}
//删除元素
int Delete(List *L,int i,ElemType *e)
{
int j;
//判断插入点是否合法
if(i<1 || i>L->length + 1)
return 0;
//得到删除元素的值
*e = L->elem[i-1];
//把删除点之后的元素向前移动1位
for(j = i - 1;j<L->length - 1;j++)
{
L->elem[j] = L->elem[j+1];
}
//长度减1
L->length--;
return 1;
}
//查找元素
int Find(List L,ElemType e)
{
int i = 1;
//从头开始找,直到不满足条件
while(i <= L.length&&L.elem[i-1] != e)
{
i++;
}
//找到,返回位置
if(i <= L.length)
return i;
else
return 0;
}
//输入元素
void InputList(List *L)
{
int i,n;
printf("请输入线性表元素个数:");
scanf("%d",&n);
//如果不满足条件一直提示重新输入
while(n>L->size)
{
printf("超出了线性表的存储空间,请重新输入:");
scanf("%d",&n);
}
L->length = n;
printf("请依次输入线性表的值:");
for(i = 0;i < n;i++)
{
scanf("%d",&L->elem[i]);
}
}
//输出链表内容
void PrintList(List L)
{
int i;
printf("线性表的元素依次为:\n");
for(i =0;i<L.length;i++)
{
printf("%d ",L.elem[i]);
}
printf("\n");
}
int main()
{
List L;
int status,e,i;
status = InitList(&L);
if(status)
{
printf("顺序表初始化成功!\n");
}
else
{
printf("顺序表初始化失败!\n");
}
InputList(&L);
PrintList(L);
status = Insert(&L,3,50);
if(status)
{
printf("进行插入操作后:\n");
PrintList(L);
}
else
{
printf("插入失败!\n");
return 0;
}
status = Delete(&L,4,&e);
if(status)
{
printf("被删除元素的值为:%d\n",e);
printf("进行删除操作后:\n");
PrintList(L);
}
else
{
printf("删除失败!\n");
return 0;
}
i = Find(L,15);
printf("与15相等的元素在线性表中的位置为%d\n",i);
//释放空间
free(L.elem);
return 0;
}