专栏首页图灵技术域数据结构顺序表C实现(14个用户接口)

数据结构顺序表C实现(14个用户接口)

将顺序表(ADT SqList)的数据对象,数据关系及基本操作(函数)用C语言实现,并测试。

手机用户点击代码移动可查看未显示内容

1.SqList.h头文件内容

C++

#define LIST_INIT_SIZE 100
#define LISTINCREASEMENT 10
typedef int ElemType;
typedef struct {
	ElemType *elem;
	int length;
	int listsize;
}SqList;
//函数名:
void ListInit(SqList &L);
void ListOutput(SqList &L);
void Listvisit(ElemType e);
int ListInsert(SqList &L,int i,ElemType e);
int ListDelete(SqList &L,int i);
int ListGetLength(SqList L);
int ListClear(SqList &L);
int ListDestroy(SqList &L);
int ListIsEmpty(SqList L);
int ListLocateElem(SqList L,ElemType e);
int ListGetElem(SqList L,int i,ElemType &e);
int ListPriorElem(SqList L, ElemType cur_e, ElemType &pre_e);
int ListNextElem(SqList L, ElemType cur_e, ElemType &next_e);
void ListTraverse(SqList L, void(*visit)(ElemType));
void ListSort(SqList &L,int t);
void ListMerge(SqList La, SqList Lb, SqList &Lc);

函数实现

1.顺序表的初始化

C++

void ListInit(SqList &L){
	L.elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));
	if(!L.elem)
		exit(OVERFLOW);
	L.length=0;
	L.listsize=LIST_INIT_SIZE;
}

注释:为了检查顺序表是否初始化,本人调用了检查顺序表是否为空的函数 (bool ListIsEmpty(SqList L))函数实现在下面会讲到。

2.顺序表的输出

C++

void ListOutput(SqList &L){
	 int i;
         for (i = 0; i < L.length; i++)
		  printf("%d ", L.elem[i]);
	 printf("\n");
}

3.顺序表的长度

C++

int ListGetLength(SqList L){
              if(L.elem!=NULL)
	              return L.length;
	          else
		      return ERROR;
}

4.插入一个值到顺序表中

C++

int ListInsert(SqList &L,int i,ElemType e){
    ElemType *q,*p,*newbase;
	if(i<1||i>L.length+1)return ERROR;
    if(L.length>=L.listsize) {
        newbase=(ElemType *)realloc(L.elem,(L.listsize+LISTINCREASEMENT)*sizeof(ElemType));
        if(!newbase)exit(OVERFLOW);
        L.elem=newbase;
        L.listsize+=LISTINCREASEMENT;
    }
    q=&(L.elem[i-1]);
    for(p=&(L.elem[L.length-1]);p>=q;--p) *(p+1)=*p;
    *q=e;
    ++L.length;
	return OK;
}

5.删除顺序表中的一个值

C++

int ListDelete(SqList &L,int i){
    ElemType *p,*q;
    if(i<1||i>L.length+1)return ERROR;
    p=&(L.elem[i-1]);
    q=L.elem+L.length-1;
	if (i == 1)*p = *(p + 1);
    for(++p;p<=q;++p)
        *(p-1)=*p;
    --L.length;
    return OK;
}

6.顺序表是否为空的判断函数

C++

bool ListIsEmpty(SqList L){
	if(L.length==0)
		return TRUE;
	else
		return FALSE;
}

注释:空为TRUE 非空为FALUSE

7.顺序表数据的位置查询

C++

int ListLocateElem(SqList L, ElemType e){
	int i,k=-1;
	for(i=1;i<=L.length;i++)
	{
		if(*(L.elem+(i-1))==e)
		{
			k=i;
			break;
		}
	}
		return k;
}

8.顺序表某个位置的数据查询

C++

int ListGetElem(SqList L, int i, ElemType &e){
	if(i<1||i>L.length+1)return ERROR;
	int j;
	ElemType *p;
	p=L.elem;
	for(j=0;j<i-1;j++)
		p++;
	e=*p;
	return OK;
}

9.查询某个值的前驱和后继

前驱:

C++

int ListPriorElem(SqList L, ElemType cur_e, ElemType &pre_e)
{
	int i;
	for (i = 1; i <= L.length; i++)
	{
		if (L.elem[i-1] == cur_e)
			break;
	}
	if (i < 1 || i > L.length+1)return ERROR;
	else
	{
		pre_e = L.elem[i-2];
		return OK;
	}
}

后继:

C++

int ListNextElem(SqList L, ElemType cur_e, ElemType &next_e)
{
	int i;
	for (i = 1; i <= L.length; i++)
	{
		if (L.elem[i-1] == cur_e)
			break;
	}
	if (i>L.length)return ERROR;
	else
	{
		next_e = L.elem[i];
		return OK;
	}
}

10.两个非递减顺序表的合并

C++

void ListMerge(SqList La, SqList Lb, SqList &Lc){
	ElemType *pa, *pb,*pc;
	pa = La.elem; pb = Lb.elem;
	Lc.listsize =Lc.length= La.length + Lb.length;
	pc = Lc.elem = (ElemType*)malloc(Lc.listsize*sizeof(ElemType));
	if (!Lc.elem)exit(OVERFLOW);
	ElemType *pa_last, *pb_last;
	pa_last = La.elem + La.length - 1;
	pb_last = Lb.elem + Lb.length - 1;
	while (pa <= pa_last&&pb <= pb_last)
	{
		if (*pa <= *pb)*pc++ = *pa++;
		else *pc++ = *pb++;
	}
	while (pa <= pa_last)*pc++ = *pa++;
	while (pb <= pb_last)*pc++ = *pb++;
}//非递减归并

11.顺序表的排序

C++

void ListSort(SqList &L,int t)
{
	int i,j;
	ElemType m;
	if (t == 0)
	{
		for (i = 0; i < L.length-1; i++)
		{
			for (j = 0; j < L.length - 1 - i; j++)
			{
				if (L.elem[j]>L.elem[j + 1])
				{
					m = L.elem[j];
					L.elem[j] = L.elem[j + 1];
					L.elem[j + 1] = m;
				}
			}
		}
	}
	else
	{
		for (i = 0; i < L.length - 1; i++)
		{
			for (j = 0; j < L.length - 1 - i; j++)
			{
				if (L.elem[j]<L.elem[j + 1])
				{
					m = L.elem[j];
					L.elem[j] = L.elem[j + 1];
					L.elem[j + 1] = m;
				}
			}
		}
	}
}//冒泡法排序

12.顺序表的清除和销毁

清除:

C++

int ListClear(SqList &L)
{
     if(L.elem==NULL)
	    return ERROR;
	 else
	 {
		 L.length=0;
		 return OK;
	 }
}

销毁:

C++

int ListDestroy(SqList &L)
{
	if(L.elem==NULL)
	    return ERROR;
	else
	{
		free(L.elem);
		return OK;
	}
}

注释:清除后使用LISTISEMPTY函数判断是否清空。

MAIN函数:

C++

int main()
{
	printf("------------------------------------------\n");
	SqList L;
	printf("顺序表L初始化......\n");
	ListInit(L);
	printf("------------------------------------------\n");
	printf("检查顺序表是否为空:\n");
	if (ListIsEmpty(L) == TRUE)
		printf("EMPTY\n");
	else
		printf("SUBFULL\n");
	printf("------------------------------------------\n");
	int i,n;
	printf("输入顺序表的长度(小于100):\n");
	scanf("%d", &n);
	printf("输入%d个值:\n",n);
	for (i = 0; i < n; i++,L.length++)
		scanf("%d", &L.elem[i]);
	printf("检查顺序表:\n");
	ListOutput(L);
	printf("------------------------------------------\n");
	printf("顺序表当前长度为%d。\n", ListGetLength(L));
	printf("------------------------------------------\n");
	printf("插入一个值到当前顺序表中:\n");
	printf("输入插入的位置:\n");
	int p;
	scanf("%d", &p);
	printf("输入插入的值:\n");
	ElemType e;
	scanf("%d", &e);
	ListInsert(L, p, e);
	printf("顺序表的值:\n");
	ListOutput(L);
	printf("顺序表当前长度为%d\n", ListGetLength(L));
	printf("------------------------------------------\n");
	printf("删除当前顺序表中的一个值:\n");
	printf("输入删除的位置:\n");
	scanf("%d", &p);
	ListDelete(L, p);
	printf("顺序表的值:\n");
	ListOutput(L);
	printf("顺序表当前长度为%d\n", ListGetLength(L));
	printf("------------------------------------------\n");
	printf("检查顺序表是否为空:\n");
	if (ListIsEmpty(L) == TRUE)
		printf("EMPTY\n");
	else
		printf("SUBFULL\n");
	printf("------------------------------------------\n");
	printf("顺序表数据的位置查询:\n");
	printf("输入需要查询的值:\n");
	ElemType d;
	scanf("%d", &e);
	if (ListLocateElem(L, e) >= 1)
		printf("%d在第%d个位置。\n",e,ListLocateElem(L,e));
	else
		printf("ERROR");
	printf("------------------------------------------\n");
	printf("顺序表位置的数据查询:\n");
	printf("输入需要查询的位置:\n");
	scanf("%d", &p);
	if (ListGetElem(L,p,e) == OK)
		printf("第%d个元素是%d。\n",p,e);
	else
		printf("ERROR");
	printf("------------------------------------------\n");
	printf("查询某个值的前驱和后继:\n");
	ElemType pre_e, next_e;
	printf("输入此值:\n");
	scanf("%d", &e);
	ListPriorElem(L, e, pre_e);
	ListNextElem(L, e, next_e);
	printf("%d的前驱是%d,后继是%d。\n", e,pre_e,next_e);
	printf("------------------------------------------\n");
	printf("若顺序表L为非递减排列,\n请创建非递减顺序表M\n并使用非递减归并函数(Y/N)?\n");
	char flag;
	getchar();
	scanf("%c", &flag);
	if (flag == 'Y')
	{
		SqList M, N;
		printf("顺序表M初始化......\n");
		ListInit(M);
		printf("输入顺序表的长度(小于100):\n");
		scanf("%d", &n);
		printf("输入%d个值:\n", n);
		for (i = 0; i < n; i++, M.length++)
			scanf("%d", &M.elem[i]);
		printf("检查顺序表L和M:\n");
		printf("L: ");
		ListOutput(L);
		printf("M: ");
		ListOutput(M);
		printf("非递减归并后:\n");
		ListMerge(L, M, N);
		ListOutput(N);
	}
	system("pause");
	printf("------------------------------------------\n");
	printf("顺序表排序:\n");
	printf("降序排列为:\n");
	ListSort(L, -1);
	ListOutput(L);
	printf("升序排列为:\n");
	ListSort(L, 0);
	ListOutput(L);
	printf("------------------------------------------\n");
	printf("顺序表清除中......\n");
	ListClear(L);
	printf("检查顺序表是否为空:\n");
	if (ListIsEmpty(L) == TRUE)
		printf("EMPTY\n");
	else
		printf("SUBFULL\n");
	printf("\n");
	printf("顺序表销毁中......\n");
	ListDestroy(L);
	printf("------------------------------------------\n");
	system("pause");
	return 0;
}

小结:

1. 实验中使用工程文件使得代码文件更有可移植性并程序化,更加规范。 2. 试验中代码文件由VC++6.0转移到VS或Code::Blocks时应打开工程文件的.dsp文件使得代码自动导入。

3. 顺序表中Merge函数应注意要对新的归并顺序表进行实时的Malloc动态分配,且调用该函数时应注意两个顺序表必须是非递减的。 4. 在顺序表的输入时,for语句最好实时对L.length进行修改,同样地在Insert和Delete函数中也应采取同样地措施。 5. 在本人实现的顺序表中,要注意内部存储是从0开始的,但是在面向用户时是从1开始。 6. 对&引用标识符在函数调用时要注意。 7. 由于函数只能return一个值,可以使用地址来返回其它值(增加一个变量)如前驱函数后继函数等。 8. 由于ElemType在程序中被定义为int,因此可以使用scanf(%d) 类型不同时要注意。推荐使用C++ cin函数。

原创非商业转载请注明出处,商业转载请联系。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 数据结构--顺序栈--C++实现

    风骨散人Chiam
  • [PHP] 数据结构-线性表的顺序存储结构PHP实现

    1.PHP中的数组实际上是有序映射,可以当成数组,列表,散列表,字典,集合,栈,队列,不是固定的长度 2.数组定义中多个单元都使用了同一个键名,则只使用了最后一...

    陶士涵
  • 数据结构----线性表顺序和链式结构的使用(c)

    PS:在学习数据结构之前,我相信很多博友也都学习过一些语言,比如说java,c语言,c++,web等,我们之前用的一些方法大都是封装好的,就java而言,里面使...

    cMusketeer
  • 数据结构-顺序表的定义及python实现

    1 顺序表的定义 线性表 是具有相同数据类型的n个数据元素的有限序列。 顺序表 使用组地址连续的存储单元、依次存储线性表中的数据元素,从而使得逻辑上相邻的两...

    致Great
  • 数据结构回顾之顺序存储结构中的线性表(栈与队列顺序线性表实现)

    说到数据结构呢,对于一个Coder来说还是蛮重要的啦,每次看数据结构的东西都有新的收获,这两天在回顾数据结构的知识。当然啦,虽然数据结构有些是理论的东西,如...

    lizelu
  • 经典数据结构实现与分析:顺序表,单链表,栈,队列,树结构,图结构;

    本博客在在这里重新总结了一下,当前常用的经典数据结构;这里只针对链表,顺序表,简单树和图进行总结;具体实现请参考:https://github.com/yaow...

    xuyaowen
  • 数据结构【第一篇】线性表之顺序表的实现与讲解

    新生安排体检,为了 便管理与统一数据,学校特地规定了排队的方式,即按照学号排队,谁在前谁在后,这都是规定好的,所以谁在谁不在,都是非常方便统计的,同学们就像被一...

    BWH_Steven
  • 【数据结构】C++用链表实现一个箱子排序附源代码详解

    分配排序的基本思想:排序过程无须比较关键字,而是通过"分配"和"收集"过程来实现排序.它们的时间复杂度可达到线性阶:O(n)。

    短短的路走走停停
  • 【数据结构】C++用链表实现一个箱子排序附源代码详解

    分配排序的基本思想:排序过程无须比较关键字,而是通过"分配"和"收集"过程来实现排序.它们的时间复杂度可达到线性阶:O(n)。

    短短的路走走停停
  • 数据结构 c++实现顺序表的基本操作/初始化/输入/输出/插入/删除

    int InSert_SeqList(SeqList *L,int i,DataType x);

    用户7886150
  • 2019年腾讯PHP工程师面试题

    第1题: PHP执行的时候有如下执行过程:Scanning(Lexing) - Compilation - Execution - Parsing,其含义分别为...

    码农编程进阶笔记
  • java基础学习_集合类03_用户登录注册案例(集合版)、Set集合、Collection集合总结_day17总结

    ============================================================================= ==...

    黑泽君
  • 集合(下)

    HashSet 是 Set 接口的实现类,底层数据结构是哈希表。HashSet 是线程不安全的(不保证同步)。优点:添加、删除、查询效率高;缺点:无序

    Carlos Ouyang
  • 【数据结构与算法】详解什么是链表,并用代码手动实现一个链表结构

    本文将来讲解一下一种常见的线性数据结构—链表,因为链表和数组一样都是一种线性的数据结构,但是它俩的实现原理是完全不同的,所以在讲解链表之前,我们来回顾一下数组结...

    @零一
  • 【架构师修炼之路】Redis 极简教程 : 基本数据结构, 跳表原理

    Github: https://github.com/antirez/redis

    一个会写诗的程序员
  • python面向对象之继承与派生

    python到底是如何实现继承的,对于你定义的每一个类,python会计算出一个方法解析顺序(MRO)列表,这个MRO列表就是一个简单的所有基类的线性顺序列表,...

    菲宇
  • 滴滴面试

    牛客网
  • Java基础——集合框架

      Java的集合框架是Java中很重要的一环,Java平台提供了一个全新的集合框架。“集合框架”主要由一组用来操作对象的接口组成。不同接口描述一组不同数据类型...

    mukekeheart
  • 全国计算机二级C语言考试知识点及2009样题

    用C语言编写的程序称为C语言源程序,源程序文件的后缀名为“.c”。源程序经编译后生成后缀名为“.obj”的目标文件,再把目标文件与各种库函数连接起来,生成“....

    用户6755376

扫码关注云+社区

领取腾讯云代金券