#include <stdio.h>
#include <stdlib.h>
#define INIT_SIZE 100 //线性表初始化大小
#define INCRESS_SIZE 20 //顺序表满后的每次扩充大小
#define ERROR -1
#define OK 0
#define MALLOC_ERROR -2
typedef int ElementType; //顺序表元素类型
typedef struct _sqlist
{
ElementType *list; //指向顺序表的指针
int leng; //当前顺序表的长度
int max_len; //顺序表的最大长度
}SqList; //重命名结构体类型
int Init_list(SqList *sqlist)
{
if (sqlist == NULL)
{
return ERROR;
}
//创建顺序表空间
sqlist->list = (ElementType*)malloc(INIT_SIZE*sizeof(ElementType) / sizeof(char));
if (sqlist->list == NULL)
{
return MALLOC_ERROR;
}
sqlist->leng = 0;
sqlist->max_len = INIT_SIZE;
return OK;
}
//扩充空间
int AgainMalloc(SqList *sqlist)
{
if (sqlist == NULL)
{
return ERROR;
}
ElementType *newbase = (ElementType*)realloc((sqlist->list), (sqlist->max_len + INCRESS_SIZE)*sizeof(ElementType) / sizeof(char));
if (newbase == NULL)
{
return MALLOC_ERROR;
}
sqlist->list = newbase;
sqlist->max_len += INCRESS_SIZE;
return OK;
}
//头插法
int Insert_Head(SqList *s, ElementType data)
{
if (s == NULL)
{
return ERROR;
}
if (s->leng == s->max_len)
{
if (AgainMalloc(s) != OK)
{
return MALLOC_ERROR;
}
}
int i;
for (i = s->leng - 1; i >= 0; i--)
{
s->list[i + 1] = s->list[i];
}
//在pos位置插入新数据
s->list[0] = data;
s->leng++;
return OK;
}
//尾插法
int Insert_Last(SqList *sqlist, ElementType newdata)
{
if (sqlist == NULL)
{
return ERROR;
}
//判断顺序表有没有满
if (sqlist->leng == sqlist->max_len)
{
if (AgainMalloc(sqlist) != OK)
{
return MALLOC_ERROR;
}
}
sqlist->list[sqlist->leng] = newdata;
sqlist->leng++;
return OK;
}
//打印顺序表数据
void DisPlay(SqList *sqlist)
{
if (sqlist == NULL)
{
return;
}
int i;
for (i = 0; i < sqlist->leng; i++)
{
printf("M", sqlist->list[i]);
}
printf("\n");
}
//在第pos个位置前插入一个数据
int Insert_Pos(SqList *s, int pos, ElementType data)
{
//入口参数检查
if (s == NULL || pos <= 0 || pos > s->leng + 1)
{
return ERROR;
}
//判断顺序表有没有满
if (s->leng == s->max_len)
{
if (AgainMalloc(s) != OK)
{
return MALLOC_ERROR;
}
}
//将从pos位置开始的数据后移一位
int i;
for (i = s->leng - 1; i >= pos - 1; i--)
{
s->list[i + 1] = s->list[i];
}
//在pos位置插入新数据
s->list[pos - 1] = data;
s->leng++;
return OK;
}
//将第pos位置的数据删除
int Delete_Pos(SqList *s, int pos)
{
if (s == NULL || pos < 1 || pos > s->leng)
{
return ERROR;
}
//从pos位置的数据往前移一位
int i;
for (i = pos; i < s->leng; i++)
{
s->list[i - 1] = s->list[i];
}
s->leng--;
return OK;
}
//查找元素
int Search_Element(SqList *s, ElementType data)
{
if (s == NULL)
{
return ERROR;
}
int i;
for (i = 0; i < s->leng; i++)
{
if (s->list[i] == data)
{
return i + 1;
}
}
return OK;
}
//将顺序表数据倒置
int Inverse_List(SqList *s)
{
if (s == NULL)
{
return ERROR;
}
int front = 0;
int lattar = s->leng - 1;
int temp;
while (front < lattar)
{
temp = s->list[front];
s->list[front++] = s->list[lattar];
s->list[lattar--] = temp;
}
return OK;
}
int main()
{
SqList sqlist; //定义一个顺序表结构变量
sqlist.list = NULL;
//初始化sqlist顺序表
if (Init_list(&sqlist) != OK)
{
return ERROR;
}
printf("打印sqlist:\n");
int i;
for (i = 0; i < 10; i++)
{
//尾插法
Insert_Last(&sqlist, i);
}
DisPlay(&sqlist);
//在第i个位置插入一个数据
if (Insert_Pos(&sqlist, 3, 11) != OK)
{
return ERROR;
}
DisPlay(&sqlist);
//在第i个位置删除一个数据
if (Delete_Pos(&sqlist,3) != OK)
{
return ERROR;
}
DisPlay(&sqlist);
printf("打印s2: \n");
SqList s2;
//初始化s2顺序表
if (Init_list(&s2) != OK)
{
return ERROR;
}
for (i = 0; i < 10; i++)
{
//头插法
Insert_Head(&s2, i);
}
DisPlay(&s2);
//查找s2的第八个元素
int pos = Search_Element(&s2, 8);
printf("s2的第八个元素为 %d\n", pos);
printf("将s2倒序\n");
Inverse_List(&s2);
DisPlay(&s2);
system("pause");
return 0;
}
转载请注明原文地址: https://ju.6miu.com/read-971872.html
