精华内容
下载资源
问答
  • 数据结构顺序表代码
    千次阅读
    2022-04-01 19:17:55

    提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档

    系列文章目录

    数据结构——顺序表的C语言代码实现
    数据结构——八种链表的C语言代码实现
    数据结构——栈的C语言代码实现
    数据结构——队列的C语言代码实现
    数据结构——堆的C语言代码实现


    前言

    使用C语言实现顺序表,重点实现动态顺序表。加强模块化实现功能的能力,了解并熟练使用realloc(),assert()等函数。

    一、基础知识

    1.顺序表的概念(Sequential List)

    鬼话:顺序表 就是把线性表中的所有元素按照其逻辑顺序,依次储存到从指定的储存位置开始的一块 连续 的储存空间中。
    人话:自我理解,特殊的数组!即将连续的数据存储在数组中,注意连续性,不可跳跃式存储。

    2.常用的接口函数

    在进行数据结构的代码实现时,最常用的接口函数便是:增、删、查、改。
    增:尾插、头插、指定位置插入;
    删:尾删、头删、指定位置删除;
    查:遍历查找;
    改:先找后改;

    3.realloc()函数使用细节

    realloc()函数:
    void* realloc (void* ptr, size_t size);
    注意:
    1.返回值是void*,实际使用中应合理使用强制类型转换;
    2.size_t size 是字节数,即所需要开辟的空间大小,此处应和calloc()结合记忆,注意区别!
    3.引用<stdlib.h>
    戳此处,查看realloc函数标准形式
    realloc()是C语言中最常用的扩容或缩容函数,其改变已开辟的内存空间大小的工作实质是:
    在已有空间的末尾寻找空余的连续空间,若末尾的空余空间足够开辟,则便在此处进行开辟,返回的指针为原指针,即所开辟的空间的起始地址没有发生改变;若末尾的空余空间不足以开辟,则对已开辟空间所存储的内容进行拷贝,然后在内存的其它位置寻找足够大的连续空间进行开辟,而原有空间被系统释放,故此时该函数的返回值不再是原指针,即所开辟的空间的起始地址发生了改变;
    但实际使用时,未避免引用过多指针,常使用以下方式进行操作:

    (DataType*) ptr=(DataType*)realloc(p,sizeof(DataType)*size_t);
    if(ptr!=NULL)
    	p=ptr;
    

    4.assert( )函数

    assert()函数:

    void assert (int expression);
    

    戳此处,查看assert()函数标准形式
    注意引用<assert.h>
    条件为真,继续向下执行;
    条件为假,终止程序。

    二、代码实现

    1.SepList.h

    (1)引用函数库

    #include<stdio.h>
    #include<stdlib.h>
    #include<assert.h>
    

    (2)定义动态顺序表

    建议遵循命名规则,将动态数组命名为arr等名字,p总是带来误解,但我懒得改了。。。

    typedef int SLDataType;
    //便于更改所存储数据的类型
    typedef struct SeqLIst
    {
    	SLDataType* p;
    	int size;
    	int capacity;
    }SL;
    

    (3)接口函数声明

    注意在设计接口函数时应使用传址的参数

    //初始顺序表
    void SeqListInit(SL* ps);
    
    //顺序表的尾插法
    void SeqListPushBack(SL* ps, SLDataType n);
    
    //顺序表的尾删法
    void SeqListPopBack(SL* ps);
    
    //顺序表的头插法
    void SeqListPushFront(SL* ps, SLDataType n);
    
    //顺序表的头删法
    void SeqListPopFront(SL* ps);
    
    //查找顺序表中的数据位置
    int Find(SL* ps,SLDataType n);
    
    //指定位置插入
    void SeqListInsert(SL* ps, int location, SLDataType n);
    
    //指定位置删除
    void SeqListDelete(SL* ps, int location);
    
    //检测顺序表容量是否足够
    void CheckCapacity(SL* ps);
    
    //接口函数测试函数
    void PrintSeqList(SL* ps);
    
    //删除顺序表
    void DestroySeqList(SL* ps);
    

    2.SepList.c

    此文件用于实现各接口函数。

    (1)引用头文件

    #include"SeqList.h"
    

    (2)初始顺序表

    //初始顺序表
    void SeqListInit(SL* ps)
    {
    	(*ps).p = NULL;
    	ps->capacity = 0;
    	ps->size = 0;
    }
    

    (3)检测顺序表容量是否足够

    //检测顺序表容量是否足够
    void CheckCapacity(SL* ps)
    {
    	//进行扩容,两种情况:1.没有开辟空间;2.容量用尽
    	if (ps->size == ps->capacity)
    	{
    		int Newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
    		SLDataType* ptr = (SLDataType*)realloc(ps->p, sizeof(SLDataType) * Newcapacity);
    		if (ptr != NULL)
    			//扩容成功
    			ps->p = ptr;
    		else
    		{
    			printf("realloc fail !");
    			//异常退出,终止程序,使用return的话,只是退出该函数
    			exit(-1);
    		}
    		ps->capacity = Newcapacity;
    	}
    }
    

    (4)顺序表的尾插法

    //顺序表的尾插法
    void SeqListPushBack(SL* ps, SLDataType n)
    {
    	CheckCapacity(ps);
    	ps->p[ps->size] = n;
    	ps->size += 1;
    }
    
    

    (5)顺序表的尾删法

    <1>使用if判断的温和法

    void SeqListPopBack(SL* ps)
    {
    	if(ps->size>0)
    	ps->size--;
    }
    

    <2>使用assert()断言的暴躁法

    何为暴躁?
    assert(条件)条件为假,直接终止函数!

    void SeqListPopBack(SL* ps)
    {
    	assert(ps->size>0)
    	ps->size--;
    }
    

    (6)全部删除

    //删除顺序表
    void DestroySeqList(SL* ps)
    {
    	free(ps->p);
    	//防止该指针成为野指针
    	ps->p = NULL;
    	ps->capacity = ps->size = 0;
    }
    

    (7)头插法

    //顺序表的头插法
    void SeqListPushFront(SL* ps, SLDataType n)
    {
    	CheckCapacity(ps);
    	//用前值覆盖后值,实现整体后移,必须从后向前两两操作
    	ps->size += 1;
    	int end = ps->size - 1;
    	while (end > 0)
    	{
    		//实现插入前的数组的整体后移
    		ps->p[end] = ps->p[end - 1];
    		end--;
    	}
    	ps->p[0] = n;
    }
    

    (8)头删法

    //顺序表的头删法
    void SeqListPopFront(SL* ps)
    {      
    	assert(ps->size > 0);
    	//将已有数组整体前移
    	int head = 0;
    	while (head < ps->size - 1)
    	{
    		ps->p[head] = ps->p[head + 1];
    		head++;
    	}
    	ps->size--;
    }
    

    (9)查找某个数值的位置

    int Find(SL* ps, SLDataType n)
    {
    	if (ps->size == 0)
    	{
    		printf("顺序表为空!\n");
    		exit(-1);
    	}
    	int tem = 0;
    	while (tem < ps->size)
    	{
    		if (ps->p[tem] == n)
    		{
    			return tem;
    		}
    		tem++;
    	}
    	printf("顺序表中没有该值!\n");
    	return -1;
    }
    

    (10)指定位置插入

    注意判断所要插入的位置,进而合理使用已有的接口函数,该程序设计中输入的位置是从1开始的!

    //指定位置插入
    void SeqListInsert(SL* ps, int location,SLDataType n)
    {
    	//因为输入的位置是从1开始数的
    	int L = location - 1;
    	//确保所要插入的位置合法
    	assert(L>=0&&L<=ps->size);
    	//确保顺序表不为空
    	assert(ps->size > 0);
    	CheckCapacity(ps);
    	//如果插入位置在头部
    	if (L == 0)
    	{
    		SeqListPushFront(ps, n);
    	}
    	//如果插入位置在尾部
    	else if (L == ps->size)
    	{
    		SeqListPushBack(ps, n);
    	}
    	//如果插入位置在已有数组内部
    	else
    	{
    		ps->size++;
    		int temend = ps->size - 1;
    		while (temend > L)
    		{
    			ps->p[temend] = ps->p[temend - 1];
    			temend--;
    		}
    		ps->p[L] = n;
    	}
    }
    

    (11)指定位置删除

    //指定位置删除
    void SeqListDelete(SL* ps, int location)
    {
    	int L = location - 1;
    	//确保输入的位置合法
    	assert(L>=0&&L<=ps->size-1);
    	//确保顺序表不为空
    	assert(ps->size > 0);
    	if (L == 0)
    	{
    		SeqListPopFront(ps);
    	}
    	else if (L == ps->size - 1)
    	{
    		SeqListPopBack(ps);
    	}
    	else
    	{
    		int temend = L;
    		while (temend < ps->size - 1)
    		{
    			ps->p[temend] = ps->p[temend+1];
    			temend++;
    		}
    		ps->size -= 1;
    	}
    }
    
    

    (12)打印函数

    //接口函数测试
    void PrintSeqList(SL* ps)
    {
    	int i = 0;
    	for (i = 0; i < ps->size; i++)
    	{
    		printf("%d ", ps->p[i]);
    	}
    
    }
    

    3.test.c

    该文件用于存放主函数,本程序只研究如何代码实现顺序表,故多为测试语句,不具有参考价值。具体使用时,可在此处代码实现菜单功能!

    (1)引用头文件

    #include"SeqList.h"
    

    (2)各种测试函数

    该处无参考价值,大家随意设置

    void testSeqList()
    {
    	SL sl;
    	SeqListInit(&sl);
    	SeqListPushBack(&sl, 1);
    	SeqListPushBack(&sl, 2);
    	SeqListPushBack(&sl, 3);
    	SeqListPushBack(&sl, 4);
    	/*SeqListPopBack(&sl,5);
    	SeqListPushFront(&sl, 0);*/
    	//用来测试接口函数
    	PrintSeqList(&sl);
    	DestroySeqList(&sl);
    }
    void testSeqListPushFront()
    {
    	SL sl;
    	SeqListInit(&sl);
    	SeqListPushFront(&sl, 1);
     	SeqListPushFront(&sl, 2);
    	SeqListPushFront(&sl, 3);
    	SeqListPushFront(&sl, 4);
    	SeqListPopFront(&sl);
    	//int ret=Find(&sl, 2);
    	 PrintSeqList(&sl);
    	/* printf("\n");
    	 printf("%d", ret);*/
    	 SeqListDelete(&sl,3);
    	 PrintSeqList(&sl);
    
    }
    

    (3)主函数

    亦无实际价值

    int main()
    {
    	//testSeqList();
    	testSeqListPushFront();
    	return 0;
    }
    

    三、总结

    数据结构的学习在于实际操作,大学课堂的教学偏向于理论学习,如若只是浅尝辄止地了解一些名词概念毫无作用,故特此逐一实现数据结构的C语言代码,进而鞭策自己迎难而上!
    与君共勉!

    更多相关内容
  • 自己写的王道考研数据结构顺序表例题和习题代码,所有函数运行都没问题。
  • 小甲鱼数据结构视频之顺序表代码,可运行,全代码 顺序表的初始化,增加,插入,重置等
  • 18级合工大数据结构实验
  • 这是讲解代码中函数关系的Keynote 为了大家方便,已转换为ppt 博客地址blog.csdn.net/u012350104
  • 数据结构基础入门】顺序表的概念、结构和接口实现
                              你们的每个赞和支持都能让我开心好几天!😉
    

    今天起开始编写数据结构中的各种数据结构及算法的实现,说到顺序表,我们首先得了解下线性表。

    1.线性表

    线性表(linear list)是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构,常见的线性表:顺序表、链表、栈、队列、字符串…
    线性表在逻辑上是线性结构,也就说是连续的一条直线。但是在物理结构上并不一定是连续的,线性表在物理上存储时,通常以数组链式结构的形式存储。
    线性表的存储

    2.顺序表

    2.1概念及结构

    顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般情况下采用数组存储。在数组上完成数据的增删查改。顺序表一般可分为:

    1.静态顺序表:使用定长数组存储。
    2.动态顺序表:使用动态开辟的数组存储。

    //顺序表的静态存储 
    #define N 100
    struct SeqList
    {
    	int a[N];//定长存储
    	int size;//有效数据的个数
    };
    
    //顺序表的动态存储
    typedef struct SeqList
    {
    	SeqDataType* a;//指向动态开辟的数组
    	int size;	  //有效数据个数
    	int capacity; //容量
    }SeqList;
    

    顺序表本质上是数组,在数组上增加了两个要求:

    1.插入数据的过程中,可以动态增长
    2.并且要求里面存储的数据必须是从左往右,是连续的

    顺序表的缺陷

    1.动态增容有性能消耗
    2.头部插入数据时,需要挪动数据

    2.2 提供接口

    静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了,空间开多了浪费,开少了不够用。所以现实中基本都是使用动态顺序表,根据需要动态的分配空间大小,所以下面我们来实现动态顺序表。

    首先在头文件<SeqList.h>中提供接口:

    typedef int SeqDataType; //需要插入什么类型的数据,就改成对应类型
    
    typedef struct SeqList
    {
    	SeqDataType* a;//指向动态开辟的数组
    	int size;	  //有效数据个数
    	int capacity; //容量
    }SeqList;
    
    //内存中管理数据结构 提供增删查改的接口
    //顺序表初始化
    void SeqListInit(SeqList* pq);
    //顺序表销毁
    void SeqListDestory(SeqList* pq);
    //顺序表打印
    void SeqListPrint(SeqList* pq);//打印数组
    //检查空间,如果满了,进行增容
    void SeqCheckCapacity(SeqList* pq)
    //顺序表尾插
    void SeqListPushBack(SeqList* pq, SeqDataType x);
    //顺序表头插
    void SeqListPushFront(SeqList* pq, SeqDataType x);
    //顺序表尾删
    void SeqListPopBack(SeqList* pq);
    //顺序表头删
    void SeqListPopFront(SeqList* pq);
    //顺序表查找x
    int SeqListFind(SeqList* pq, SeqDataType x);//查找 查到返回下标,没查到返回-1
    //顺序表在指定位置插入数据
    void SeqListInsert(SeqList* pq, int pos, SeqDataType x);//在下标pos位置处插入数据
    //顺序表在指定位置删除数据
    void SeqListErase(SeqList* pq, int pos);//把下标为pos位置处的数据删除
    //顺序表在指定位置替换数据
    void SeqListModify(SeqList* pq, int pos, SeqDataType x);//把小标为pos位置的值改为x
    
    

    2.4 接口实现

    在源文件SeqList.c中实现接口功能
    (1)顺序表初始化

    void SeqListInit(SeqList* pq)
    {
    	assert(pq != NULL);//或者 assert(pq); 断言 防止传入空指针
    	pq->a = NULL;
    	pq->size = 0;
    	pq->capacity = 0;
    }
    

    (2)顺序表销毁

    void SeqListDestory(SeqList* pq)
    {
    	assert(pq);
    	free(pq->a);
    	pq->a = NULL;
    	pq->size = 0;
    	pq->capacity = 0;
    }
    

    (3)顺序表打印

    void SeqListPrint(SeqList* pq)
    {
    	assert(pq);
    	for (int i = 0; i < pq->size; ++i)
    	{
    		printf("%d ", pq->a[i]);
    	}
    	printf("\n");
    }
    

    (4)检查空间,如果满了,进行增容

    //检查是否需要扩容
    void SeqCheckCapacity(SeqList* pq)
    {
    	//满了,需要增容
    	if (pq->size == pq->capacity)
    	{
    		int newcapacity = (pq->capacity == 0 ? 4 : pq->capacity * 2);
    
    		//realloc接收的地址如果为空,将像malloc一样,开辟一块新空间
    		SeqDataType* newA = realloc(pq->a, sizeof(SeqDataType) * newcapacity);//realloc返回 开辟的新空间的地址
    		if (newA == NULL)
    		{
    			printf("realloc fail\n");
    			exit(-1);//失败了就退出
    		}
    		pq->a = newA;
    		pq->capacity = newcapacity;
    	}
    }
    

    (5)顺序表尾插

    void SeqListPushBack(SeqList* pq, SeqDataType x)//尾插
    {
    	assert(pq);
    
    	SeqCheckCapacity(pq);
    
    	pq->a[pq->size] = x;
    	pq->size++;
    }
    

    (6)顺序表头插

    void SeqListPushFront(SeqList* pq, SeqDataType x)
    {
    	assert(pq);
    
    	SeqCheckCapacity(pq);
    
    	int end = pq->size - 1;
    	while (end >= 0)
    	{
    		pq->a[end + 1] = pq->a[end];
    		end--;
    	}
    	pq->a[0] = x;
    	pq->size++;
    }
    

    (7)顺序表尾删

    void SeqListPopBack(SeqList* pq)
    {
    	assert(pq);
    	assert(pq->size > 0);
    	pq->size--;
    }
    

    (8)顺序表头删

    void SeqListPopFront(SeqList* pq)
    {
    	assert(pq);
    	assert(pq->size > 0);
    
    	int begin = 0;
    	while (begin < pq->size - 1)
    	{
    		pq->a[begin] = pq->a[begin + 1];
    		begin++;
    	}
    	pq->size--;
    }
    

    (9)顺序表查找x

    int SeqListFind(SeqList* pq, SeqDataType x)
    {
    	assert(pq);
    	for (int i = 0; i < pq->size; ++i)
    	{
    		if (pq->a[i] == x)
    		{
    			return x;
    		}
    	}
    	return -1;//没找到
    }
    

    (10)顺序表在指定位置插入数据

    void SeqListInsert(SeqList* pq, int pos, SeqDataType x)
    {
    	assert(pq);
    	assert(pos >= 0 && pos < pq->size);
    
    	SeqCheckCapacity(pq);//检查是否需要扩容
    
    	int end = pq->size - 1;
    	while (end >= pos)
    	{
    		pq->a[end + 1] = pq->a[end];
    		end--;
    	}
    	pq->a[pos] = x;
    	pq->size++;
    }
    

    (11)顺序表在指定位置删除数据

    void SeqListErase(SeqList* pq, int pos)
    {
    	assert(pq);
    	assert(pos >= 0 && pos < pq->size);
    	int begin = pos;
    	while (begin <= pq->size - 1)
    	{
    		pq->a[begin] = pq->a[begin + 1];
    		begin++;
    	}
    	pq->size--;
    }
    

    (12)顺序表在指定位置替换数据

    void SeqListModify(SeqList* pq, int pos, SeqDataType x)
    {
    	assert(pq);
    	assert(pos >= 0 && pos < pq->size);
    
    	pq->a[pos] = x;
    }
    

    主函数的设计大家可以自由发挥,做个简单的测试功能调用函数或是创建菜单栏实现交互都可以。我水平有限,请朋友们谅解!写的不好的地方还请大佬们指出。最后,如果这篇文章对你有帮助,就点个赞或者收藏评论一下吧,谢谢大家支持😁。

    下期预告——单链表

    展开全文
  • 这是数据结构和算法设计课程设计一个选题。实践了顺序表的基本操作的封装,及实践中的调用。特别的对顺序表上的插入和删除操作做出详细的介绍。课设采用静态存储,按值查找。希望能够对其他同学有所帮助
    1. 课程设计题目

    设计出顺序表结构的相关函数库,以便在程序设计中调用。

    1. 题目要求

    (1)包括线性表的各种基本函数以及常用函数(自己确定函数、函数形式及理由)

    (2)最好能借助语言环境实现图形显示功能,以便能将抽象的数据结构以图形方式显示出来,将复杂的运行过程以动态方式显示出来。

    (3)给出若干例程,演示通过调用自己的库函数来实现相关问题的求解。

    1. 题目分析

    基于在《数据结构与算法设计》课程的学习,学习物理结构之顺序存储结构,结合线性表的特点和逻辑结构以及基于线性表实际设计的基本操作。我们设计出以函数为核心、C语言实现、顺序表结构的相关数据库,并通过main主函数进行了集合,能够通过实践的演示,利用对相关函数的调用来实现相关问题解决。

          这里我们选用静态存储作为数组存储方式。

        这里我们需要说明顺序表结构(元素)与数组(元素)联系:

    1. 地址连续
    2. 依次存储
    3. 数据类型相同
    4. 随机存取

    这里我们需要充分了解C语言中利用指针、数组名做参数进行传址方式及传值方式

    这里我们设计的顺序表所完成的基本操作并以函数封装:

    • 创建顺序表CreateList()
    • 顺序表初始化InitList()
    • 按数值进行查找LocateElem()
    • 插入元素操作InsertList()
    • 删除元素数值操作ListDelete ()
    • 清空顺序表ClearList ()
    • 打印顺序表PrintList()

    最后对一些准备工作的介绍

    我们使用了cstdio等6个头文件,3个宏定义进行常量和类型定义以及对顺序表数据结构的表示

    #include<cstdio>
    
    #include<cstdlib>
    
    #include<cstring>
    
    #include<cmath>
    
    #include<algorithm>
    
    #include<iostream>
    
    #define MaxSize 100
    
    #define ElemType int
    
    #define Status int
    
    using namespace std;
    
    typedef struct
    
    {
    
          ElemType data[MaxSize]
    
          Int length;
    
    }SqList;
    1. 课题设计

    1. 函数的模块化设计

    1. 顺序表插入元素

    InsertList(SqList &L,int i,ElemType e)

    【算法步骤】

    • 判断插入位置i是否合法(1<=i<=L.length+1)
    • 判断顺序表的存储空间是否已满
    • 将第L.length至第i序号上的元素依次向后移动一个位置,直至空出第i个位置
    • 将待插入元素e放入第i个位置
    • L.length++
    1. 顺序表上的删除

    ListDelete (SqList &L,int i)

    【算法步骤】

    • 判断删除位置i是否合法(1<=i<=L.length)
    • 将第i+1至第L.length个的元素依次向前移动一个位置

    • L.length--

    这里对典型的插入和删除函数设计思路进行描述。ASL(平均查找长度)因位置不同存在较大差异。

    1. 函数功能的描述

    CreateList(SqList &l,int n):

    参数:顺序表L,顺序表长度n

    功能:创建长度为n的顺序表L

    时间复杂度:O(n)

    操作前提:L是一个未初始化的线性表

            操作结果:将L初始化为一个空的线性表

    InitList(SqList &L)

    参数:表L

    功能:对表L进行初识化

    时间复杂度:O(1)

    操作前提:L是一个已初始化的空表

    操作结果:建立一个非空的线性表L

    InsertList(SqList &L,int i,ElemType e)

    参数:表L,位置i,元素e

    功能:在位置i处插入元素e

    时间复杂度:O(n)

    操作前提:线性表L已存在

    操作结果:将元素s插入到线性表L的i位置

    ListDelete (SqList &L,int i)

    参数:表L,位置i

    功能:删除位置i处元素

    时间复杂度:O(n)

    操作前提:线性表L已存在

    操作结果:将线性表L中i位置的元素删除,

    LocateList (SqList L,int i,ElemType &e)

    参数:表L,位置i,

    功能:返回i序号上的元素,并以e返回其值

    时间复杂度:O(n)

    操作前提:线性表L已存在

    操作结果:在线性表L中查找i位置上元素,若存在,返回元素;若不存在,返回-1

    PrintList(SqList L)

    参数:表L,

    功能:输出L

    操作前提:

    操作结果:在屏幕上显示表中元素

    ClearList (SqList &L)

    参数:表L

    功能:清空顺序表L

    操作前提:

    操作结果:空表

    1. 代码实现
    1. 源代码
    
    #define  _CRT_SECURE_NO_WARNINGS
    #include<cstdio>
    #include<cstdlib>
    #include<cstring>
    #include<cmath>
    #include<algorithm>
    #include<iostream>
    #define MaxSize 100
    #define ElemType int
    #define Status int
    using namespace std;
    //顺序表数据结构
    typedef struct
    {
    	ElemType data[MaxSize];//顺序表元素
    	int length;            //顺序表当前长度
    }SqList;
    //***************************基本操作函数*******************************//
    //初始化顺序表函数,构造一个空的顺序表 
    Status InitList(SqList& L)
    {
    	memset(L.data, 0, sizeof(L));//初始化数据为0
    	L.length = 0;                //初始化长度为0
    	return 0;
    }
    //创建顺序表函数 初始化前n个数据
    bool CreateList(SqList& L, int n)
    {
    	if (n<0 || n>MaxSize)false;//n非法
    	for (int i = 0; i < n; i++)
    	{
    		scanf("%d", &L.data[i]);
    		L.length++;
    	}
    	return true;
    }
    //插入函数 位置i插入数据 i及之后元素后移  1=<i<=length+1 
    bool InsertList(SqList& L, int i, ElemType e)
    {
    	if (i<1 || i>L.length + 1) //判断位置是否有效
    	{
    		printf("位置无效!!!\n");
    		return false;
    	}
    	if (L.length >= MaxSize)//判断存储空间是否已满
    	{
    		printf("当前存储空间已满!!!\n");
    		return false;
    	}
    	for (int j = L.length; j >= i; j--)//位置i及之后元素后移
    	{
    		L.data[j] = L.data[j - 1];
    	}
    	L.data[i - 1] = e;
    	L.length++;
    	return true;
    }
    //删除函数 删除位置i的元素 i之后的元素依次前移
    bool  ListDelete(SqList& L, int i)
    {
    	if (i<1 || i>L.length)
    	{
    		printf("位置无效!!!\n");
    		return false;
    	}
    	for (int j = i; j <= L.length - 1; j++)//位置i之后元素依次前移覆盖
    	{
    		L.data[j - 1] = L.data[j];
    	}
    	L.length--;
    	return true;
    }
    //查找函数 按位置从小到大查找第一个值等于e的元素 并返回位置
    int LocateElem(SqList L, ElemType e)
    {
    	for (int i = 0; i < L.length; i++)//从低位置查找
    	{
    		if (L.data[i] == e)
    			return i + 1;
    	}
    	return 0;
    }
    
    //清空顺序表
    void ClearList(SqList& L) {
    	L.length = 0;
    }
    //********************************功能函数*****************************************//
    //输出功能函数 按位置从小到大输出顺序表所有元素
    void PrintList(SqList L)
    {
    	printf("当前顺序表所有元素:");
    	for (int i = 0; i < L.length; i++)
    	{
    		printf("%d ", L.data[i]);
    	}
    	printf("\n");
    }
    //创建顺序表函数
    void Create(SqList& L)
    {
    	int n; bool flag;
    	L.length = 0;
    	printf("请输入要创建的顺序表长度(>1):");
    	scanf("%d", &n);
    	printf("请输入%d个数(空格隔开):", n);
    	flag = CreateList(L, n);
    	if (flag) {
    		printf("创建成功!\n");
    		PrintList(L);
    	}
    	else printf("输入长度非法!\n");
    
    }
    //插入功能函数 调用InsertList完成顺序表元素插入 调用PrintList函数显示插入成功后的结果
    void Insert(SqList& L)
    {
    	int place; ElemType e; bool flag;
    	printf("请输入要插入的位置(从1开始)及元素:\n");
    	scanf("%d%d", &place, &e);
    	flag = InsertList(L, place, e);
    	if (flag)
    	{
    		printf("插入成功!!!\n");
    		PrintList(L);
    	}
    }
    //删除功能函数 调用ListDelete函数完成顺序表的删除 调用PrintList函数显示插入成功后的结果
    void Delete(SqList& L)
    {
    	int place; bool flag;
    	printf("请输入要删除的位置(从1开始):\n");
    	scanf("%d", &place);
    	flag = ListDelete(L, place);
    	if (flag)
    	{
    		printf("删除成功!!!\n");
    		PrintList(L);
    	}
    }
    //查找功能函数 调用LocateElem查找元素
    void Search(SqList L)
    {
    	ElemType e; int flag;
    	printf("请输入要查找的值:\n");
    	scanf("%d", &e);
    	flag = LocateElem(L, e);
    	if (flag)
    	{
    		printf("该元素位置为:%d\n", flag);
    	}
    	else
    		printf("未找到该元素!\n");
    }
    //菜单
    void menu()
    {
    	printf("********1.创建                        2.插入*********\n");
    	printf("********3.删除                        4.查找*********\n");
    	printf("********5.输出                        6.清空*********\n");
    	printf("********7.退出                              *********\n");
    }
    int main()
    {
    	SqList L; int choice;
    	InitList(L);
    	while (1)
    	{
    		menu();
    		printf("请输入菜单序号:\n");
    		scanf("%d", &choice);
    		if (9 == choice) break;
    		switch (choice)
    		{
    		case 1:Create(L); break;
    		case 2:Insert(L); break;
    		case 3:Delete(L); break;
    		case 4:Search(L); break;
    		case 5:PrintList(L); break;
    		case 6:ClearList(L); break;
    		default:printf("输入错误!!!\n");
    		}
    	}
    	return 0;
    
    
    1. 程序运行结果

    1. 课程设计感悟

    在课程设计中,巩固了知识,锻炼了实践能力,在ASL和时间复杂度上的考虑,更能接感受到顺序表的特点:
    随机访问,既可以在O(1)时间内找到第i个元素。可以像数组是一样利用存储位置直接访问元素
    存储密度高,每个节点只存储数据元素。
    扩展容量不方便(即便采用动态分配的方式实现,扩展长度的时间复杂度也比较高)。
    插入、删除操作不方便,当头插法、和尾插法时,相对好理解简单。但当在中间插入时需要移动大量元素。但是链式存储结构在这方面做的很好。

           总的来说,在C语言的学习时非常有必要的,是理解和掌握数据结构和算法的直接逻辑和语言基础。当然目前接触的数据结构和算法只是冰山一角,一定会存在优化程度更高的算法和数据结构,要怀有空杯心态,进一步学习数据库、kafka、hadoop等等,再者也要注重合作能力的提升,人尽其责,物尽其用。

    1. 参考资料

    《数据结构C语言版第二版》/严蔚敏,李冬梅,吴伟民编

    《数据结构与算法设计》/张小艳,李占利编

    《c/c++语言程序设计》/龚尚福,贾澎涛编

    目录

    课程设计题目

    题目要求

    题目分析

    课题设计

    函数的模块化设计

    函数功能的描述

    《数据结构C语言版第二版》/严蔚敏,李冬梅,吴伟民编

    《数据结构与算法设计》/张小艳,李占利编

    《c/c++语言程序设计》/龚尚福,贾澎涛编


    展开全文
  • 数据结构-顺序表基本操作的实现(含全部代码

    万次阅读 多人点赞 2018-09-13 22:14:57
    今天起开始编写数据结构中的各种数据结构及其算法的实现。 主要依据严蔚敏版数据结构教材以及王道数据结构考研辅导书。 今天是线性表中的顺序表的实现,主要实现函数如下,读者有需要可以评论,我可以适当加几个。...

    今天起开始编写数据结构中的各种数据结构及其算法的实现。

    主要依据严蔚敏版数据结构教材以及王道数据结构考研辅导书。

    今天是线性表中的顺序表的实现,主要实现函数如下,读者有需要可以评论,我可以适当加几个。

    • CreateList(SqList &L,int n) 参数:顺序表L,顺序表长度n 功能:创建长度为的顺序表 时间复杂度:O(n)
    • InitList(SqList &L) 参数:顺序表L 功能:初始化 时间复杂度:O(1)
    • InsertList(SqList &L,int i,ElemType e) 参数:顺序表L,位置i,元素e 功能:位置i处插入元素e 时间复杂度:O(n)
    • ListDelete(SqList &L,int i) 参数:顺序表L,位置i 功能:删除位置i处元素 时间复杂度:O(n)
    • LocateElem(SqList L,ElemType e) 参数:顺序表L,元素e 功能:返回第一个等于e的元素的位置 时间复杂度:O(n)
    • Reverse(SqList &L) 参数:顺序表L 倒置函数 将原顺序表直接倒置
    • PrintList(SqList L) 参数:顺序表L 功能:遍历L,并输出
    • SplitSort(SqList &L) 参数:顺序表L 功能:分开奇偶,并分开排序
    • ClearList(SqList &L) 参数:顺序表L 功能:清空顺序表

    代码如下:

    /*
    Project: sequence_list(数据结构-顺序表)
    Date:    2018/09/12  20191012修改 添加Reverse  20200819修改 添加ClearList
    Author:  Frank Yu
    CreateList(SqList &L,int n) 参数:顺序表L,顺序表长度n 功能:创建长度为的顺序表 时间复杂度:O(n)
    InitList(SqList &L) 参数:顺序表L 功能:初始化 时间复杂度:O(1)
    InsertList(SqList &L,int i,ElemType e) 参数:顺序表L,位置i,元素e 功能:位置i处插入元素e 时间复杂度:O(n)
    ListDelete(SqList &L,int i) 参数:顺序表L,位置i 功能:删除位置i处元素 时间复杂度:O(n)
    LocateElem(SqList L,ElemType e) 参数:顺序表L,元素e 功能:返回第一个等于e的元素的位置 时间复杂度:O(n)
    Reverse(SqList &L) 参数:顺序表L 倒置函数 将原顺序表直接倒置
    PrintList(SqList L) 参数:顺序表L 功能:遍历L,并输出
    SplitSort(SqList &L) 参数:顺序表L 功能:分开奇偶,并分开排序
    ClearList(SqList &L) 参数:顺序表L 功能:清空顺序表
    */
    #include<cstdio>
    #include<cstdlib>
    #include<cstring>
    #include<cmath>
    #include<algorithm>
    #include<iostream>
    #define MaxSize 100
    #define ElemType int
    #define Status int
    using namespace std;
    //顺序表数据结构
    typedef struct
    {
    	ElemType data[MaxSize];//顺序表元素
    	int length;            //顺序表当前长度
    }SqList;
    //***************************基本操作函数*******************************//
    //初始化顺序表函数,构造一个空的顺序表 
    Status InitList(SqList &L)
    {
    	memset(L.data, 0, sizeof(L));//初始化数据为0
    	L.length = 0;                //初始化长度为0
    	return 0;
    }
    //创建顺序表函数 初始化前n个数据
    bool CreateList(SqList &L, int n)
    {
    	if (n<0 || n>MaxSize)false;//n非法
    	for (int i = 0; i<n; i++)
    	{
    		scanf("%d", &L.data[i]);
    		L.length++;
    	}
    	return true;
    }
    //插入函数 位置i插入数据 i及之后元素后移  1=<i<=length+1 
    bool InsertList(SqList &L, int i, ElemType e)
    {
    	if (i<1 || i>L.length + 1) //判断位置是否有效
    	{
    		printf("位置无效!!!\n");
    		return false;
    	}
    	if (L.length >= MaxSize)//判断存储空间是否已满
    	{
    		printf("当前存储空间已满!!!\n");
    		return false;
    	}
    	for (int j = L.length; j >= i; j--)//位置i及之后元素后移
    	{
    		L.data[j] = L.data[j - 1];
    	}
    	L.data[i - 1] = e;
    	L.length++;
    	return true;
    }
    //删除函数 删除位置i的元素 i之后的元素依次前移
    bool  ListDelete(SqList &L, int i)
    {
    	if (i<1 || i>L.length)
    	{
    		printf("位置无效!!!\n");
    		return false;
    	}
    	for (int j = i; j <= L.length - 1; j++)//位置i之后元素依次前移覆盖
    	{
    		L.data[j - 1] = L.data[j];
    	}
    	L.length--;
    	return true;
    }
    //查找函数 按位置从小到大查找第一个值等于e的元素 并返回位置
    int LocateElem(SqList L, ElemType e)
    {
    	for (int i = 0; i<L.length; i++)//从低位置查找
    	{
    		if (L.data[i] == e)
    			return i + 1;
    	}
    	return 0;
    }
    //倒置函数 将原顺序表直接倒置
    void Reverse(SqList &L)
    {
    	if (L.length)
    		for (int i = 0; i<L.length - 1 - i; i++)
    		{
    			int t = L.data[i];
    			L.data[i] = L.data[L.length - 1 - i];
    			L.data[L.length - 1 - i] = t;
    		}
    }
    //奇偶分开并排序
    void SplitSort(SqList &L)
    {
    	int Even = 0;
    	int Odd = L.length - 1;
    	int i = 0;
    	int j = L.length - 1;
    	bool flag = false; // 交换标志
    	if (L.length)
    		for (; i < j; i++, j--)
    		{
    			while (L.data[i] % 2 != 0 && i<L.length - 1)i++;
    			while (L.data[j] % 2 == 0 && j>0)j--;
    			if (L.data[i] % 2 == 0 && L.data[j] % 2 != 0 && i<j)
    			{
    				int temp = L.data[i];
    				L.data[i] = L.data[j];
    				L.data[j] = temp;
    				flag = true;
    			}
    			if (!flag) //没有交换
    			{
    				if (i > j) { // 恰好奇偶分开
    					Even = j;
    					Odd = i;
    				}
    				else {
    					Even = L.length - 1;//全奇数
    					Odd = 0; //全偶数
    				}
    			}
    		}
    	if (flag)//有交换
    	{
    		for (int i = 0; i<L.length; i++)
    			if (L.data[i] % 2 == 0)
    			{
    				Odd = i;
    				Even = i - 1;
    				break;
    			}
    	}
    	sort(L.data, L.data + Even + 1);
    	sort(L.data + Odd, L.data + L.length);
    }
    //清空顺序表
    void ClearList(SqList &L) {
    	L.length = 0;
    }
    //********************************功能函数*****************************************//
    //输出功能函数 按位置从小到大输出顺序表所有元素
    void PrintList(SqList L)
    {
    	printf("当前顺序表所有元素:");
    	for (int i = 0; i<L.length; i++)
    	{
    		printf("%d ", L.data[i]);
    	}
    	printf("\n");
    }
    //创建顺序表函数
    void Create(SqList &L)
    {
    	int n; bool flag;
    	L.length = 0;
    	printf("请输入要创建的顺序表长度(>1):");
    	scanf("%d", &n);
    	printf("请输入%d个数(空格隔开):", n);
    	flag = CreateList(L, n);
    	if (flag) {
    		printf("创建成功!\n");
    		PrintList(L);
    	}
    	else printf("输入长度非法!\n");
    
    }
    //插入功能函数 调用InsertList完成顺序表元素插入 调用PrintList函数显示插入成功后的结果
    void Insert(SqList &L)
    {
    	int place; ElemType e; bool flag;
    	printf("请输入要插入的位置(从1开始)及元素:\n");
    	scanf("%d%d", &place, &e);
    	flag = InsertList(L, place, e);
    	if (flag)
    	{
    		printf("插入成功!!!\n");
    		PrintList(L);
    	}
    }
    //删除功能函数 调用ListDelete函数完成顺序表的删除 调用PrintList函数显示插入成功后的结果
    void Delete(SqList &L)
    {
    	int place; bool flag;
    	printf("请输入要删除的位置(从1开始):\n");
    	scanf("%d", &place);
    	flag = ListDelete(L, place);
    	if (flag)
    	{
    		printf("删除成功!!!\n");
    		PrintList(L);
    	}
    }
    //查找功能函数 调用LocateElem查找元素
    void Search(SqList L)
    {
    	ElemType e; int flag;
    	printf("请输入要查找的值:\n");
    	scanf("%d", &e);
    	flag = LocateElem(L, e);
    	if (flag)
    	{
    		printf("该元素位置为:%d\n", flag);
    	}
    	else
    		printf("未找到该元素!\n");
    }
    //菜单
    void menu()
    {
    	printf("********1.创建                        2.插入*********\n");
    	printf("********3.删除                        4.查找*********\n");
    	printf("********5.倒置                        6.分奇偶排序***\n");
    	printf("********7.输出                        8.清空*********\n");
    	printf("********9.退出                              *********\n");
    }
    int main()
    {
    	SqList L; int choice;
    	InitList(L);
    	while (1)
    	{
    		menu();
    		printf("请输入菜单序号:\n");
    		scanf("%d", &choice);
    		if (9 == choice) break;
    		switch (choice)
    		{
    		case 1:Create(L); break;
    		case 2:Insert(L); break;
    		case 3:Delete(L); break;
    		case 4:Search(L); break;
    		case 5:Reverse(L); break;
    		case 6:SplitSort(L); break;
    		case 7:PrintList(L); break;
    		case 8:ClearList(L); break;
    		default:printf("输入错误!!!\n");
    		}
    	}
    	return 0;
    }

    结果截图:

    插入结果截图
    删除结果截图
    查找结果截图
    输出结果截图

    ---------------------------------------------2018-09-18更新 添加创建函数 菜单有改动-----------------------------------------

                                                                     

    ---------------------------------------------20191012更新 添加Reverse函数--------------------------------------------

    根据下方评论,添加了倒置函数,参考stl的Reverse写法

    template <class _RandomAccessIter>
    _STLP_INLINE_LOOP void
    __reverse(_RandomAccessIter __first, _RandomAccessIter __last, const random_access_iterator_tag &) {
      for (; __first < __last; ++__first)
        _STLP_STD::iter_swap(__first, --__last);
    }
    倒置展示

    2019年10月23日更新,应评论区小伙伴的要求,添加了奇偶分开,并排序的函数

    //奇偶分开并排序 前奇数 后偶数
    void SplitSort(SqList &L)
    {
    	int Even = 0;
    	int Odd = L.length - 1;
    	int i = 0;
    	int j = L.length - 1;
    	bool flag = false; // 交换标志
    	if (L.length)
    		for (; i < j; i++, j--)
    		{
    			while (L.data[i] % 2 != 0 && i<L.length - 1)i++;
    			while (L.data[j] % 2 == 0 && j>0)j--;
    			if (L.data[i] % 2 == 0 && L.data[j] % 2 != 0 && i<j)
    			{
    				int temp = L.data[i];
    				L.data[i] = L.data[j];
    				L.data[j] = temp;
    				flag = true;
    			}
    			if (!flag) //没有交换
    			{
    				if (i > j) { // 恰好奇偶分开
    					Even = j;
    					Odd = i;
    				}
    				else {
    					Even = L.length - 1;//全奇数
    					Odd = 0; //全偶数
    				}
    			}
    		}
    	if (flag)//有交换
    	{
    		for (int i = 0; i<L.length; i++)
    			if (L.data[i] % 2 == 0)
    			{
    				Odd = i;
    				Even = i - 1;
    				break;
    			}
    	}
    	sort(L.data, L.data + Even + 1);
    	sort(L.data + Odd, L.data + L.length);
    }
    测试全奇偶

    有奇偶

    代码已更新至上方全部代码!!!

    ------20211201修改-------

    感谢@Cendrillon_提出的bug,上方代码已修改。之前未考虑到没有交换可能是恰好奇偶分开的情况。

    ------20211201修改-------

    -------------------------20200819修改 添加ClearList-------------------------------------

    代码由评论区用户__BlackHole提供,已更新至上方全部代码。

    至于销毁,我是使用的静态分配,如果是new(delete释放)或malloc(free释放)的话,需要释放空间,其实就是堆和栈的区别。

    堆和栈的区别就是申请方式不同:栈是系统自动分配空间,而堆则是程序员根据需要申请空间。由于栈上的空间是自动分配自动回收的,所以,栈内数据的生存周期只是在函数的运行过程中,运行后就释放掉。而堆上的数据只要程序员不释放空间,就一直可以访问到,缺点是一旦忘记释放会造成内存泄露。

    综上,我写的顺序表不需要进行销毁,当然,顺序表最大长度也固定了,各有利弊,如果是动态分配的话记得释放空间呀!

    关注博主公众号,回复 数据结构资源 获取数据结构(C语言版)、数据结构(第二版)课件、所有算法代码。

    更多数据结构与算法的实现:数据结构(严蔚敏版)与算法的实现(含全部代码)

    本人b站账号:lady_killer9

    有问题请下方评论,转载请注明出处,并附有原文链接,谢谢!如有侵权,请及时联系。如果您感觉有所收获,自愿打赏,可选择支付宝18833895206(小于),您的支持是我不断更新的动力。

    展开全文
  • 顺序表的创建、查找、插入、删除等一些基本操作,使用c++编写的简单例子,适用于初学者,通过学习实例,能更好的掌握顺序表
  • 数据结构顺序表和4个链表的代码,对应到我的博客数据结构顺序表和链表
  • 数据结构c++代码顺序表代码,包括静态顺序表和动态顺序表),由devc++软件编写
  • 为了统一顺序表和链表的方法命名,先创建一个接口,里面定义了一般线性表所有方法的名称。 定义接口的原因:1.外部对不论顺序表还是链表的操作是一样的;2.但是顺序表和链表的具体方法实现不一样 using System; ...
  • 数据结构——顺序表

    2016-01-07 22:55:07
    数据结构的一些讲解,供学习者参考,也顺带作为复习。需要源代码的欢迎下载,免积分,共同学习,接下来会每天分享一篇,持续一个星期
  • 实现顺序表的初始化,输出顺序表中各元素的值,在顺序表中插入数据元素,删除数据元素,求顺序表的长度,顺序表的逆置,顺序表的按值从小到大排序,合并有序的两个顺序表等操作。
  • 数据结构实验报告1-顺序表实现简易的学生信息管理系统(C语言),包括实验环境,实验的小结,实验的源代码,实验截图等。 说明:仅供参考,如有bug,还请反馈!
  • 用数组实现数据结构顺序表的几种功能。包括插入,判断顺序表是否为空,遍历顺序表,获取指定位置元素,查找元素,获取元素的前驱、后继,删除、清空、销毁顺序表。
  • C语言实现顺序表数据结构

    千次阅读 多人点赞 2022-04-22 19:00:54
    以下是我们需要实现的顺序表的功能。 以下是写在SeqList.h中的内容,我们将全部需要声明的内容放在此处 pragma once #include <stdio.h> #include <assert.h> #include <stdlib.h> typedef ...
  • 数据结构严蔚敏C语言版—线性表顺序存储结构(顺序表)C语言实现相关代码1.运行环境2.准备工作1)项目构建1>新建一个SeqList项目2>新建两个文件Sources和Headers3>新建两个C/C++ source和一个C/C++ header2...
  • 顺序表,全名顺序存储结构,是线性表的一种。线性表用于存储逻辑关系为“一对一”的数据顺序表自然也不例外。
  • 数据结构】线性表顺序表(全)测试代码用C语言C++实现动态及静态顺序表的定义、插入、删除 定义线性表节点的结构.pdf
  • 以下代码为使用C++完成顺序表的静态实现 后面会尝试顺序表的动态实现 #include<iostream> using namespace std; #define maxSize 10 struct sqlList { int data[maxSize]; //静态的“数组”存放数据 int...
  • #include using namespace std; #define True 11 #define False 0 #define Ok 111 #define Error -111 #define List_Init_Size 10 #define ListIncrement 10 typedef int Status;... //元素类型
  • 源文件 博文链接:https://thebigforest.iteye.com/blog/43206
  • 数据结构C语言完成顺序表基本操作,上数据结构课的时候的任务,可以在vs上实现,用switch函数选择
  • 数据结构顺序表

    千次阅读 多人点赞 2022-03-10 00:30:28
    一、顺序表介绍 二、准备工作 1、创建顺序表 2、初始化顺序表 3、检测是否需要扩容 4、销毁顺序表 5、打印顺序表 三、四大功能 1、增加数据 头插 尾插 指定下标插入 2、删除数据 头删 ...
  • 数据结构学生顺序表解题代码
  • 数据结构链表顺序表

    2018-06-11 20:48:14
    数据结构属虚标链表
  • 简单易懂,大二学生编写的,作为指导自己操作的代码是十分好的~ 实验1为顺序结构 实验2为链式结构
  • 本学期数据结构第一次实验-顺序表C++实现

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 530,475
精华内容 212,190
关键字:

数据结构顺序表代码

数据结构 订阅