顺序表的基本操作

目录

一、实验要求

二、代码实现

三、运行结果

---

一、实验要求

    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。

 

二、代码实现

/*
    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;
}

三、运行结果