实现顺序表各种基本运算的算法

左手的ㄟ右手 2022-05-05 10:58 314阅读 0赞

编写一个头文件SqList.h，实现顺序表的各种基本操作，并在此基础上设计一个主程序（exp2\_1.cpp）完成如下功能：

1.  初始化顺序表L
2.  依次采用尾插法插入a,b,c,d,e元素
3.  输出顺序表L
4.  输出顺序表L的长度
5.  判断顺序表L是否为空
6.  输出顺序表L的第3个元素
7.  输出元素a的位置
8.  在第4个元素位置上插入f元素
9.  输出顺序表L
10. 删除L的第3个元素
11. 输出顺序表L
12. 释放顺序表

**头文件****：**

/*文件名:SqList.h*/
    # include<stdio.h>
    # include<malloc.h>
    # include<stdlib.h>
    
    # define TRUE 1
    # define FALSE 0
    # define OK 1
    # define ERROR 0
    # define INFEASIBLE -1
    # define OVERFLOW -2
    
    //定义函数返回类型
    typedef int Status;
    # define LIST_INIT_SIZE 100 //线性表存储空间的初始分配量
    # define LISTINCREMENT 10 //线性表存储空间的分配增量
    typedef char ElemType; //定义数据元素的类型为字符型
    
    
    //定义顺序表的存储结构
    typedef struct
    {
    	ElemType* elem;
    	int length;
    	int listsize;
    }SqList;
    
    
    //构造一个空的顺序表L
    Status InitList(SqList &L)
    {
    	L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
    	if(!L.elem)
    		exit(OVERFLOW);
    	L.length = 0;
    	L.listsize = LIST_INIT_SIZE;
    	return OK;
    }
    
    
    int DestroyList(SqList &L)
    {
    	if(!L.elem)
    	{
    		return ERROR;  //表不存在
    	}
    	free(L.elem);      //释放内存
    }
    
    
    //判断顺序表是否为空，为空就返回true,否则返回false
    Status ListEmpty(SqList &L)
    {
    	if(!L.elem)
    	{
    		return ERROR;  //表不存在
    	}
    	if(L.length == 0)
    		return TRUE;
    	else
    		return FALSE;
    }
    
    
    //返回线性表L的长度
    int ListLength(SqList &L)
    {
    	if(!L.elem)
    	{
    		return ERROR;
    	}
    	int i;
    	while(i < L.length)
    	{
    		i++;
    	}
    	return L.length;
    }
    
    
    //打印单链表中的元素
    void DispList(SqList &L)
    {
    	int i;
    	if(ListEmpty(L))
    		printf("数组为空");
    	for(i = 0 ; i < 10 ; i++)
    		printf("%c" , L.elem[i]);
    		printf("%c\n");
    }
    
    
    //从顺序表L中查找第i个元素，由参数e返回其元素的值
    Status GetElem(SqList L , int i , char &e)
    {
    	if(!L.elem)
    	{
    		return ERROR;
    	}
    	if(i<1 || i>=L.length-1)
    	{
    		return ERROR;     //i值不合法
    	}
    	char *q = L.elem;
    	e = *(q + i - 1);     //把第i个元素给e
    	return OK;
    }
    
    
    //在顺序表L中查找元素e的位置，不存在则返回0
    int LocateElem(SqList L , int e)
    {
    	if(!L.elem)
    	{
    		return ERROR;
    	}
    	int i = 1;
    	char *p = L.elem;
    	while(i<L.length && *p++!=e)  //查找与e相等的值的位置
    	{
    		++i;
    	}
    	if(i <= L.length) //判断i的值在不在L.length里面
    	{
    		return i;
    	}
    	return 0;
    }
    
    
    //在顺序表L中第i个位置前插入元素e
    Status ListInsert(SqList &L , int i , char e)
    {
    	int k;
    	if(!L.elem)
    	{
    		return ERROR;
    	}
    	if(i>L.length+1 || i<1)
    	{
    		return ERROR;    //i值不合法
    	}
    	if(L.length >= L.listsize)
    	{
    		char *newbase;   //空间不足，重新分配
    		newbase = (char*)realloc(L.elem , sizeof(char)*(L.listsize + LISTINCREMENT));
    		L.elem = newbase;
    		if(!L.elem)
    		{
    			return OVERFLOW; //分配失败
    		}
    		L.elem = newbase;
    		L.listsize+=LISTINCREMENT; //新空间容量
    	}
    //插入元素e
    	for(k = L.length-1 ; k >= i-1 ; k--)
    		L.elem[k+1] = L.elem[k];
    	L.elem[i-1] = e;
    	L.length++;                //多一个元素长度加1
    	return OK;
    }
    
    
    //在顺序表L中删除第i个值并用e返回这个值
    Status ListDelete(SqList &L , int i , char &e)
    {
    	int k;
    	if(!L.elem)
    	{
    		return ERROR;
    	}
    	if(i<1 || i>L.length)
    	{
    		return ERROR;  //i值不合法
    	}
    	e = L.elem[i-1];
    	for(k = i ; k <= L.length ; k++)  //将自i-1后面的所有元素向前移动一位
    		L.elem[k-1] = L.elem[k];
    	L.length--;        //当遍历到L.length即最后一个元素的下一个元素时，将空元素赋给最后一个元素（L.length-1)，然后链表L长度减1
    	return OK;
    }

**主函数****：**

# include"SqList.h"
    int main()
    {
    	SqList(L);
    	ElemType e;
    	printf("初始化顺序表L\n");
    	InitList(L);
    	printf("依次采用尾插法插入a , b , c , d , e元素\n");
    	ListInsert(L , 1 , 'a');
    	ListInsert(L , 2 , 'b');
    	ListInsert(L , 3 , 'c');
    	ListInsert(L , 4 , 'd');
    	ListInsert(L , 5 , 'e');
    	printf("输出数序表L:");
    	DispList(L);
    	printf("顺序表长度L = %d\n" , L.length);
    	printf("顺序表L为%s\n" , (ListEmpty(L)?"空":"非空"));
    	GetElem(L , 3 , e);
    	printf("顺序表的第3个元素 = %c\n" , e);
    	printf("元素a的位置 = %d\n" , LocateElem(L , 'a'));
    	printf("在第4个元素位置上插入f元素\n");
    	ListInsert(L , 4 , 'f');
    	printf("输出顺序表L:");
    	DispList(L);
    	printf("删除L的第3个元素\n");
    	ListDelete(L , 3 , e);
    	printf("输出顺序表L:");
    	DispList(L);
    	printf("释放顺序表L\n");
    	free(L.elem);
    }

结果

![70][]

[70]: /images/20220505/d01a1d0cbde54013954f7636a394c59b.png