目录
/*
1、验证性实验：实现顺序表的基本操作
实验内容：编写一个程序sqlist.cpp (或.c)，
实现顺序表的各种基本运算和整体建表算法（假设顺序表的内容类型ElemType为char），
并在此基础上设计一个程序exp1.cpp (或.c)完成一下功能。
(1) 初始化顺序表L。
(2) 将元素a、b、c、d、e依次插入顺序表L中。
(3) 输出顺序表L。
(4) 输出顺序表L的长度。
(5) 判断顺序表L是否为空。
(6) 输出顺序表L的第3个元素。
(7) 输出元素a的位置。
(8) 在第4个元素位置上插入元素f。
(9) 输出顺序表L。
(10) 删除顺序表L的第3个元素。
(11) 输出顺序表L。
(12) 销毁顺序表L。
*/
#include<stdio.h>
#include<stdlib.h>
#define OK 1
#define ERROR 0
#define LIST_INIT_SIZE 100 //线性表最大分配容量
#define LISTINCREMENT 10 //线性表扩展容量
typedef char ElemType; //数据元素为字符型
typedef struct
{
/* data */
ElemType *data;
int length;
int listsize;
}sqlist;
//初始化顺序表
int InitList(sqlist *L)
{
//动态分配：malloc函数申请一片连续的存储空间
L->data=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
if(!L->data)
{
return ERROR;
}
L->length=0; //初始表长为0
L->listsize=LIST_INIT_SIZE;
return OK;
}
//将元素e插入到顺序表L的第k个位置。
int List_Insert(sqlist *L,int k,ElemType e)
{
int i=0;
if(!L->data)
return ERROR;
if (k>L->length+1|| k<1)//判断插入位置的合法性
{
return ERROR;
}
if (L->length >= L->listsize)
{
char *new_base; //空间不足，重新分配
new_base = (char*)realloc(L->data, sizeof(char)*(L->listsize + LISTINCREMENT));
L->data = new_base;
if (!L->data)
{
return ERROR;
}
L->data = new_base;
L->listsize += LISTINCREMENT;
}
//插入元素e
if(k<L->length)
{
for (i = L->length - 1 ; i>= k - 1; i--)
L->data[i + 1] = L->data[i];
}
L->data[k - 1] = e;
L->length++; //多一个元素长度加1
return OK;
}
//输出顺序表L。
int print_List_data(sqlist *L)
{
if(!L->data)
return ERROR;
for (int i = 0; i < L->length; i++)
{
/* code */
printf("%c ",L->data[i]);
}
printf("\n");
return OK;
}
//输出顺序表L的长度。
int print_List_Length(sqlist *L)
{
if(!L->data)
return ERROR;
printf("%d\n",L->length);
return OK;
}
//判断顺序表L是否为空。
int ListEmpty(sqlist *L)
{
if(!L->data||L->length!=0)
return ERROR;
else
return OK;
}
//输出顺序表L的第i个元素。（该元素e是需要返回给用户的）
int GetElem(sqlist *L, int i, ElemType *e)
{
if (!L->data)
{
return ERROR;
}
if (i < 1 || i >= L->length-1)
{
return ERROR; //i值不合法
}
*e =L->data[i-1];
return OK;
}
//输出元素a的位置。（该元素e是不需要返回给用户的）
int LocateElem(sqlist *L, char e)
{
if (!L->data)
{
return ERROR;
}
for (int i = 0; i < L->length; i++)
{
if (L->data[i]==e)
{
return i+1; //返回元素所在位置
}
}
return OK;
}
// 删除顺序表L的第i个元素。（该元素e是不需要返回给用户的）
int ListDelete(sqlist *L, int i, char e)
{
int k;
if (!L->data)
{
return ERROR;
}
if (i<1 || i>L->length)
{
return ERROR; //i值不合法
}
e = L->data[i - 1];
for (k = i; k <= L->length ;k++)
L->data[k - 1] = L->data[k];
L->length--;
return OK;
}
// 销毁顺序表L。
int DestroyList(sqlist *L)
{
if (!L->data)
{
return ERROR; //表不存在
}
else
free(L->data); //释放内存 销毁线性表
printf(" 线性表销毁成功！");
return 0;
}
int main()
{
sqlist L;
ElemType e;
printf("1:初始化顺序表L\n");
InitList(&L);
printf("2:依次采用尾插法插入a , b , c , d , e元素\n");
List_Insert(&L, 1, 'a');
List_Insert(&L, 2, 'b');
List_Insert(&L, 3, 'c');
List_Insert(&L, 4, 'd');
List_Insert(&L, 5, 'e');
printf("3:顺序表L:");
print_List_data(&L);
printf("4:线性表L表长为:");
print_List_Length(&L);
printf("5:顺序表L为:%s\n", (ListEmpty(&L) ? "空" : "非空"));
GetElem(&L, 3, &e);
printf("6:顺序表的第3个元素是:%c\n", e);
printf("7:线性表L中元素a的位置为: %d\n", LocateElem(&L, 'a'));
printf("8:在第4个元素位置上插入f元素\n");
List_Insert(&L, 4, 'f');
printf(" 顺序表L为:");
print_List_data(&L);
printf("9:删除L的第3个元素\n");
ListDelete(&L, 3, e);
printf(" 顺序表L为:");
print_List_data(&L);
printf("10:销毁顺序表L\n");
DestroyList(&L);
return 0;
}