#include <stdio.h>
#include <stdlib.h>
#define INIT_SIZE 100 // 顺序表初始化大小
#define INCESS_SIZE 20 // 顺序表满后的每次扩充大小
#define OK 0
#define ERROR -1
#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+INCESS_SIZE)*sizeof(ElementType)/sizeof(char));
if (newbase == NULL)
{
return MALLOC_ERROR;
}
sqlist->list = newbase;
sqlist->max_len += INCESS_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 < 1 || 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 latter = s->leng -1;
int temp;
while (front < latter)
{
temp = s->list[front];
s->list[front++] = s->list[latter];
s->list[latter--] = temp;
}
return OK;
}
// 顺序表合并
int Merge_List(SqList *s1, SqList *s2, SqList *s3)
{
if (s1 == NULL || s2 == NULL)
{
return ERROR;
}
s3->list = (ElementType*)malloc((s1->leng+s2->leng)*sizeof(ElementType)/sizeof(char));
if (s3->list == NULL)
{
return MALLOC_ERROR;
}
s3->leng = s1->leng + s2->leng;
s3->max_len = s1->leng + s2->leng;
int i = 0; // s1
int j = 0; // s2
int k = 0; // s3
while (i < s1->leng && j < s2->leng)
{
if (s1->list[i] < s2->list[j])
{
s3->list[k++] = s1->list[i++];
}
else
{
s3->list[k++] = s2->list[j++];
}
}
// 判断s1是否结束
while (i < s1->leng)
{
s3->list[k++] = s1->list[i++];
}
// 判断s2是否结束
while(j < s2->leng)
{
s3->list[k++] = s2->list[j++];
}
return OK;
}
int main()
{
SqList s; // 定义一个顺序表结构变量
s.list = NULL;
// 初始化顺序表
if (Init_list(&s) != OK)
{
return ERROR;
}
int i;
for (i = 0; i < 20; i = i+2)
{
// 尾插法
Insert_Last(&s, i);
}
printf ("s1初始化结果:\n");
DisPlay(&s);
/*
// 在第 pos 位置插入一个数据
if(Insert_Pos(&s, 5, 11) != OK)
{
return ERROR;
}
printf ("s1在第5个位置插入11:\n");
DisPlay(&s);
// 将第 pos 位置的数据删除
if (Delete_Pos(&s, 5) != OK)
{
return ERROR;
}
printf ("s1将第5个位置数据删除:\n");
DisPlay(&s); */
SqList s2;
if (Init_list(&s2) != OK)
{
return ERROR;
}
for (i = 1; i < 20; i= i+2)
{
// 头插法
Insert_Head(&s2, i);
}
printf ("s2初始化:\n");
DisPlay(&s2);
// 查找元素
int pos = Search_Element(&s2, 9);
printf ("pos = %d\n", pos);
// 将顺序表数据倒置
if (Inverse_List(&s2) != OK)
{
return ERROR;
}
printf ("s2倒置:\n");
DisPlay(&s2);
SqList s3;
// 将顺序表s和s2合并放s3里
if (Merge_List(&s, &s2, &s3) != OK )
{
return ERROR;
}
printf ("打印s3:\n");
DisPlay(&s3);
return 0;
}
