顺序表 订阅
顺序表是在计算机内存中以数组的形式保存的线性表,线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素、使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中,即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系,采用顺序存储结构的线性表通常称为顺序表。顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。 [1] 展开全文
顺序表是在计算机内存中以数组的形式保存的线性表,线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素、使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中,即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系,采用顺序存储结构的线性表通常称为顺序表。顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。 [1]
信息
结    构
存储结构
外文名
Contiguous List
中文名
顺序表
形    式
数组
顺序表简介
将表中元素一个接一个的存入一组连续的存储单元中,这种存储结构是顺序结构。采用顺序存储结构的线性表简称为“ 顺序表”。顺序表的存储特点是:只要确定了起始位置,表中任一元素的地址都通过下列公式得到:LOC(ai)=LOC(a1)+(i-1)*L  1≤i≤n 其中,L是元素占用存储单元的长度。顺序表的结构定义:#define maxlen 50 //定义顺序表中元素个数最多有几个 typedef struct{elementtype data[maxlen]; //elementtype是元素的类型 依具体情况而定int listlen; //便于时刻了解顺序表里元素的个数}seqlist; //顺序表的名称 不妨为seqlist声明顺序表类型变量:seqlist L,L1;如顺序表的每个结点占用len个内存单元,用location (ki)表示顺序表中第i个结点ki所占内存空间的第1个单元的地址。则有如下的关系:location (ki+1) = location (ki) +lenlocation (ki) = location(k1) + (i-1)len存储结构要体现数据的逻辑结构,顺序表的存储结构中,内存中物理地址相邻的结点一定具有顺序表中的逻辑关系。 [2] 
收起全文
精华内容
下载资源
问答
  • 顺序表

    千次阅读 多人点赞 2021-04-02 20:02:57
    顺序表的基本概念 顺序表是在计算机内存中以数组的形式保存的线性表,线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素、使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元...

    顺序表的基本概念

    顺序表是在计算机内存中以数组的形式保存的线性表,线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素、使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中,即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系,采用顺序存储结构的线性表通常称为顺序表。顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中

    顺序表的实现方式

    顺序表一般利用数组+动态内存管理实现,一般设置特定的接口方便后续调用;
    我们要利用顺序表实现简单数据的增删查改,即头插头删,尾插尾删,中间插入中间删除;
    下面是常用的接口函数

    //尾插
    void SeqListPushBack(SeqList* pq, SeqDateType);
    //头插
    void SeqListPushFront(SeqList* pq, SeqDateType);
    //尾删
    void SeqListPopBack(SeqList* pq);
    //头删
    void SeqListPopFront(SeqList* pq);
    //打印
    void SeqListPrint(SeqList* pq);
    //检查容量是否满
    void SeqListCheckCapacity(SeqList* pq);
    //进行初始化
    void SeqListInit(SeqList* pq);
    //销毁线性表
    void SeqListDestory(SeqList* pq);
    // 顺序表查找
    void SeqListFind(SeqList* ps, SeqDateType x);
    // 顺序表在pos位置插入x
    void SeqListInsert(SeqList* ps, size_t pos, SeqDateType x);
    // 顺序表删除pos位置的值
    //void SeqListErase(SeqList* ps, size_t pos);
    
    
    

    顺序表接口的实现

    下面我们通过具体的函数来实现顺序表:

    首先搭建基本环境,创建一个结构体,并将其命名为SeqLIst,结构体内创建3个数据,一个数组,一个是当前数组容量大小,最后一个是数组最大容量

    typedef int SeqDateType;
    typedef struct SeqList
    {
    	SeqDateType* a;
    	int size;
    	int capacity;
    }SeqList;
    

    接下来初始化顺序表,让其刚开始大小为0

    //初始化顺序表
    void SeqListInit(SeqList* pq)
    {
    	assert(pq);
    	pq->a = NULL;
    	pq->size = 0;
    	pq->capacity = 0;
    }
    

    按照正常思路接下来就是插入数据了,但是在每次插入数据前我们都要判断以下当前顺序表所存储的数据和容量进行比较,如果空间不够进行扩容:
    void SeqListCheckCapacity(SeqList* pq);检查数组容量,判断数组容量是否满了

    //检查容量
    void SeqListCheckCapacity(SeqList* pq)
    {
    	if (pq->size == pq->capacity)
    	{
    		int newcapacity = (pq->capacity == 0 ? 4 : pq->capacity * 2);
    		SeqDateType* p = realloc(pq->a,newcapacity * sizeof(SeqDateType));
    		if (p != NULL)
    		{
    			pq->a = p;
    			pq->capacity = newcapacity;
    		}
    		else
    		{
    			printf("realloc fail\n");
    			exit(-1);
    		}
    	}
    	
    }
    

    接下来就该实现我们的插入删除数据了:
    void SeqListPushBack(SeqList* pq, SeqDateType);在数组尾部进行插入**

    //尾部插入数据
    void SeqListPushBack(SeqList* pq,SeqDateType x)
    {
    	assert(pq);
    	//每次插入数据都要检查容量
    	SeqListCheckCapacity(pq);
    	pq->a[pq->size] = x;
    	pq->size++;
    }
    

    头部插入数据:void SeqListPushFront(SeqList* pq, SeqDateType x)

    //头部插入数据
    void SeqListPushFront(SeqList* pq, SeqDateType x)
    {
    	assert(pq);
    	SeqListCheckCapacity(pq);
    	int end = pq->size - 1;
    	for (;end>=0;end--)
    	{
    		pq->a[end+1] = pq->a[end];
    	}
    	pq->a[0] = x;
    	pq->size++;
    }
    

    尾部删除数据:void SeqListPopBack(SeqList* pq)

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

    头部删除数据:void SeqListPopFront(SeqList* pq)

    //头删
    void SeqListPopFront(SeqList* pq)
    {
    	assert(pq);
    	assert(pq->size > 0);
    	for (int i = 0; i < pq->size-1; i++)
    	{
    		pq->a[i] = pq->a[i + 1];
    	}
    	pq->size--;
    }
    

    打印数据:void SeqListPrint(SeqList* pq)

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

    销毁数据:void SeqListDestory(SeqList* pq)

    
    ```c
    
    ```bash
    //销毁数据
    void SeqListDestory(SeqList* pq)
    {
    	assert(pq);
    	pq->a = NULL;
    	pq->capacity = 0;
    	pq->size = 0;
    }
    

    查找指定内容:void SeqListFind(SeqList* ps, SeqDateType x)

    //查找指定内容
    void SeqListFind(SeqList* ps, SeqDateType x)
    {
    	assert(ps);
    	int i = 0;
    	for (; i < ps->size; i++)
    	{
    		if (x == ps->a[i])
    		{
    			break;
    		}
    	}
    	if (i == ps->size)
    	{
    		printf("未找到该成员\n");
    		return;
    	}
    	else
    	{
    		printf("%d的下标为%d\n", ps->a[i], i);
    	}
    }
    

    指定位置插入数据:void SeqListInsert(SeqList* ps, size_t pos, SeqDateType x)

    //指定位置插入数据
    void SeqListInsert(SeqList* ps, size_t pos, SeqDateType x)
    {
    	assert(ps);
    	//assert(pos<=ps->size);
    
    	SeqListCheckCapacity(ps);
    	if (pos == 0)
    	{
    
    	}
    
    	//int end = ps->size - 1;
    	//while (end >= (int)pos)
    	//{
    	//	ps->a[end + 1] = ps->a[end];
    	//	--end;
    	//}
    
    	size_t end = ps->size;
    	while (end >= pos)
    	{
    		ps->a[end] = ps->a[end - 1];
    		--end;
    	}
    
    
    	ps->a[pos] = x;
    	ps->size++;
    }
    
    

    指定位置删除数据:void SeqListErase(SeqList* ps, size_t pos)

    // 顺序表删除pos位置的值
    void SeqListErase(SeqList* ps, size_t pos)
    {
    	//assert(ps && (pos <ps->size));
    
    	//size_t start = pos;
    	//while (start < ps->size-1)
    	//{
    	//	ps->a[start] = ps->a[start + 1];
    	//	++start;
    	//}
    	//asserr(ps);
    	//assert(pos >=0 && pos<=ps.size);
    	size_t start = pos + 1;
    	while (start < ps->size)
    	{
    		ps->a[start - 1] = ps->a[start];
    		++start;
    	}
    	ps->size--;
    }
    

    如果搞懂顺序表的话不妨自己动手利用顺序表写一个动态通讯录检验一下自己,如果你喜欢小编的文章的话请多多一键三连吧,谢谢大家的支持

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

    万次阅读 多人点赞 2018-09-13 22:14:57
    今天起开始编写数据结构中的各种数据结构及其算法的实现。 主要依据严蔚敏版数据结构教材以及王道数据结构...L,int n) 参数:顺序表L,顺序表长度n 功能:创建长度为的顺序表 时间复杂度:O(n) InitList(SqList &...

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

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

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

    • 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++;
    			while (L.data[j] % 2 == 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) //没有交换
    			{
    				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++;
    			while (L.data[j] % 2 == 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) //没有交换
    			{
    				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);
    }
    测试全奇偶

     

    有奇偶

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

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

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

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

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

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

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

    本人b站账号:lady_killer9

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

    展开全文
  • C语言顺序表的插入删除

    万次阅读 多人点赞 2018-09-13 22:08:41
    首先声明一个顺序表的结构 (数组的第一个元素是0,但是顺序表的第一个一般 从1(人为设定)开始) #include &lt;stdio.h&gt; #include &lt;stdlib.h&gt; #define MAXSIZE 10 #define OK 1 #define ...

    首先声明一个顺序表的结构 (数组的第一个元素是0,但是顺序表的第一个一般 从1(人为设定)开始)

    #include <stdio.h>
    #include <stdlib.h>
    
    #define MAXSIZE 10
    #define OK	  1
    #define FALSE 0 
    
    typedef int Elemtype;
    typedef bool Status;
    
    typedef struct list
    {
    	Elemtype *elem;
    	int len;        //数据个数
    	int listsize;   //顺序表长度
    }List;
    

    listsize 代表这个顺序表的最大容量,可以随时扩容

    len 代表在你创建的这个顺序表中有几个有效的数据,总是小于等于listsize

    一、初始化顺序表属性

    void list_init(List *L)
    {
    	L->elem=(Elemtype *)malloc(MAXSIZE*sizeof(Elemtype));//开辟空间
    	if(L->elem==NULL)//判断空间是否开辟成功
    	{
    		printf("malloc fail\n");
    		exit(0);
    	}
    
    	L->len=0;	//初始化数据有效数据为0
    	L->listsize=MAXSIZE;	//初始化数组长度为MAXSIZE
    }

    二、顺序表的插入

    Status list_insert(List *L,int i,Elemtype data)
    {
    	Elemtype *base,*insert,*p;
    	if(i<1 || i>L->len+1 || L==NULL)
    	{
    		printf("位置输入错误\n");
    		return FALSE;
    	}
    	if(L->len > L->listsize)
    	{
    		base=(Elemtype *)realloc(L->elem,(L->listsize+MAXSIZE)*sizeof(Elemtype));//动态扩容
    		L->elem=base;
    		L->listsize+=MAXSIZE;//更新顺序表大小
    	}
    	insert=&(L->elem[i-1]);//目标指针指向要插入的目标地址
    	  //指向最后一个元素的地址
    	for(p=L->elem + L->len-1;p>=insert;p--)
    	{
    		*(p+1)=*p;
    	}
    	*insert=data;
    	L->len++;
    	return OK;
    }

    三、删除 

    Status delete_list(List *L,int i)
    {
    	ElemType *q,*delete_i;
    	if(L==NULL||i<0||i>L->len)
    	return FALSE;
    	delete_i=&(L->elem[i-1]);//用指针指向要删除位置的地址
    	q=L->elem + L->len-1;    //q指针指向顺序表最后一个位置的地址   首地址加上数组长度就是最后一个元素地址
    	for(delete_i=delete_i+1;delete_i<=q;++delete_i)//从删除位置的地址的下一个元素开始,每个往前移动一位
    	{
    		*(delete_i-1)=*delete_i;		//前一个位置等于后一个
    	}
    	L->len--;
    	
    	return OK;
    }

     

     全部程序

    #include <stdio.h>
    #include <stdlib.h>
    
    #define MAXSIZE 10
    #define OK	  1
    #define FALSE 0 
    
    typedef int Elemtype;
    typedef bool Status;
    
    typedef struct list
    {
    	Elemtype *elem;
    	int len;
    	int listsize;
    }List;
    
    
    void list_init(List *L)
    {
    	L->elem=(Elemtype *)malloc(MAXSIZE*sizeof(Elemtype));//开辟空间
    	if(L->elem==NULL)//判断空间是否开辟成功
    	{
    		printf("malloc fail\n");
    		exit(0);
    	}
    
    	L->len=0;	//初始化数据有效数据为0
    	L->listsize=MAXSIZE;	//初始化数组长度为MAXSIZE
    }
    
    Status list_insert(List *L,int i,Elemtype data)
    {
    	Elemtype *base,*insert,*p;
    	if(i<1 || i>L->len+1 || L==NULL)
    	{
    		printf("位置输入错误\n");
    		return FALSE;
    	}
    	if(L->len > L->listsize)
    	{
    		base=(Elemtype *)realloc(L->elem,(L->listsize+MAXSIZE)*sizeof(Elemtype));
    		L->elem=base;
    		L->listsize+=MAXSIZE;
    	}
    	insert=&(L->elem[i-1]);//目标指针指向要插入的目标地址
    	  //指向最后一个元素的地址
    	for(p=L->elem + L->len-1;p>=insert;p--)
    	{
    		*(p+1)=*p;
    	}
    	*insert=data;
    	L->len++;
    	return OK;
    }
    
    Status list_delete(List *L,int i)
    {
    	Elemtype *aim,*p;
    	if(i<0 || i>L->len)
    	{
    		printf("位置输入错误\n");
    		return FALSE;
    	}
    	aim=&(L->elem[i-1]);//目标指针指向要删除的目标地址
    	p=(L->elem+L->len-1); //指向最后一个元素的地址
    	for(aim=aim+1;aim<=p;++aim) //目标地址滑动删除
    	{
    		*(aim-1)=*aim;
    	}
    	L->len--;
    	return OK;
    }
    void show_list(List *L)
    {
    	int i;
    	for(i=0;i<L->len;i++)
    	{
    		printf("elem[%d]=%d\n",i+1,L->elem[i]);
    	}
    	printf("\n");
    }
    int main()
    {
    	int i;
    	List L;
    	list_init(&L);
    	for(i=0;i<10;i++)
    	{
    		list_insert(&L,i+1,i+1);
    	}
    	printf("插入前的顺序表\n");
    	show_list(&L);
    
    	printf("插入后的顺序表  在5位置插入99\n");
    	list_insert(&L,5,99);
    	show_list(&L);
    
    	printf("删除后的顺序表  把5位置删除\n");
    	list_delete(&L,5);
    	show_list(&L);
    	return 0;
    }
    
    

     

    展开全文
  • 创建有若干个元素(可以是整型数值)的顺序表,实现对顺序表的初始化,对已建立的顺序表插入操作、删除操作、遍历输出顺序表。 要求各个操作均以函数的形式实现,在主函数中调用各个函数实现以下操作: ( 1...
  • 顺序表与链表

    千次阅读 2019-07-10 14:47:43
    一、顺序表和链表的比较 1.存取方式 顺序表可以顺序存取,也可以随机存取,链表只能从表头顺序存取元素。 2.逻辑结构与物理结构 顺序存储时,逻辑上相邻的元素,对应的物理存储位置也相邻; 链式存储时,...

    一、顺序表和链表的比较

    1.存取方式

           顺序表可以顺序存取,也可以随机存取,链表只能从表头顺序存取元素。

     

    2.逻辑结构与物理结构

           顺序存储时,逻辑上相邻的元素,对应的物理存储位置也相邻;

           链式存储时,逻辑上相邻的元素,物理存储位置不一定相邻,其逻辑关系是通过指针链接来表示的。

     

    3.查找、插入和删除操作

           对于按值查找,顺序表无序时,两者的时间复杂度均为O(n);顺序表有序时,可采用折半查找,此时的时间复杂度为O(

           对于按序号查找,顺序表支持随机访问,时间复杂度仅为O(1),而链表的平均时间复杂度为O(n)。

           顺序表的插入、删除操作,平均需要移动半个表长的元素。

           链表的插入、删除操作,只需要修改相关结点的指针域既可。由于链表的每个结点都有指针域,所以在存储空间上要比顺序表付出的代价大,存储密度不够大。

     

    4.空间分配

           顺序存储在静态存储分配情况下,一旦存储空间装满就不能扩充,若再加入新元素,则会出现溢出,所以需要预先分配足够大的存储空间。预先分配过大,可能会导致顺序表候补大量闲置;预先分配过小,又会造成溢出。

           动态存储分配虽然存储空间可以扩充,但需要移动大量元素,导致操作效率降低,而且若内存中没有更大的连续存储空间,则会导致分配失败、

     

    二、如何选取存储结构?

    1.基于存储的考虑

           难以估计线性表的长度或存储规模时,不宜采用顺序表;链表不用事先估计存储规模,但链表的存储密度较低,显然链式存储结构的存储密度是小于1的。

     

    2.基于运算的考虑

           在顺序表中按序号访问元素的时间复杂度为O(1),而链表中按序号访问的时间复杂度为O(n),所以若经常做的运算是按序号访问数据元素,顺序表优于链表。

           但是如果在运算中需要进行大量的数据增加和删除操作的时候,链表优于顺序表。

     

    3.基于环境的考虑

           顺序表容易实现,任何语言中都有数组的类型。链表的操作基于指针,会相对复杂些,逻辑性强一些。

     

    展开全文
  • 创建一个顺序表, 向顺序表中插入元素,查找顺序表中的元素(按值查找和按序号查找),删除顺序表中的某个元素,输出顺序表中的元素算法: #include <stdio.h> #include <stdlib.h> #define ListSize ...
  • 顺序表算法】设顺序表 A,元素的个数是 n,没有重复。如果 A 中前 k 个元 素有序,后 n-k 个元素有序,设计一个算法使得整个顺序表有序,要求算法的空 间复杂度为 O(1)。 solution: 由于题目要求空间复杂度为O(1...
  • 顺序表顺序表的就地逆置

    千次阅读 2020-06-23 16:37:15
    编写算法实现顺序表的就地逆置,即利用原顺序表的存储单位把数据元素顺序反向,例如:1,5,6,9,8逆置为 8,9,6,5,1 题目分析:   就地逆置,就是指借用顺序表自身实现顺序逆置,不借助其他线性表。   如果...
  • 顺序表——有序顺序表的插入

    千次阅读 2017-11-10 11:13:16
    本题要求实现递增顺序表的有序插入函数。L是一个递增的有序顺序表,函数Status ListInsert_SortedSq(SqList &L, ElemType e)用于向顺序表中按递增的顺序插入一个数据。 比如:原数据有:2 5,要插入一个元素3,那么...
  • 实际过程中应该不断取下两个顺序表表头较小的结点存在新的顺序表中,然后,将其中某个表中的剩余数据直接加到新的顺序表后面。 二 代码实现 /*合并两个有序顺序表*/ #include <iostream> using namespace ...
  • 顺序表与链表的比较

    千次阅读 2020-06-16 22:17:05
    顺序表与链表的适用情况
  • 将两个有序顺序表合并为一个新的有序顺序表

    万次阅读 多人点赞 2019-06-28 21:31:16
    将两个有序顺序表合并为一个新的有序顺序表题目要求基本思想核心代码完整代码(C++) 题目要求 将两个有序顺序表合并为一个新的有序顺序表,并由函数返回合并后的顺序表。 基本思想 非常经典的题目,哪怕死记硬背也...
  • (2.2.4-7)将两个有序顺序表合并为一个新的有序顺序表。 思路:有序顺序表L1,L2各用j、k两个指针从第一个元素进行遍历比较,一旦k指向的元素大于或者等于j指向的元素就将k指向的元素插在j元素之后。在此首先得默认L1...
  • 顺序表查找有序表查找 对顺序表进行二分查找 索引顺序查找表 索引顺序查找表也就是分块查找 把线性表分为若干块,每一块的关键字都小于下一块的最小关键字。 索引按顺序排列进行二分查找,在对找到的块进行顺序查找
  • 顺序表和链表的比较

    千次阅读 2020-06-14 17:53:39
    2.6 顺序表和链表的比较   大家好,我叫亓官劼(qí guān jié ),在CSDN中记录学习的点滴历程,时光荏苒,未来可期,加油~博客地址为:亓官劼的博客 本文原创为亓官劼,请大家支持原创,部分平台一直在盗取博...
  • 问题描述:将两个有序顺序表合并为一个新的有序顺序表,并有函数返回结果顺序表。要求时间复杂度O(n) 算法设计思想:首先,按顺序取两个顺序表表头较小的结点存入新的线性表中直到某一个表遍历完;然后将还有剩余...
  • 数据结构~02.顺序表的操作

    万次阅读 热门讨论 2020-07-14 22:30:52
    例题:已知一个顺序表list,其中的元素递增有序排列,设计一个算法,插入一个元素(int型)x,然后保持该顺序表依然递增有序排列。        我们要完成这个需求,首先就要先找到那个...
  • 顺序表和链表

    千次阅读 2018-03-18 19:39:17
    本文和大家讨论一下关于线性表有关的问题,包括实现等 ...顺序表有个特点:除第一个和最后一个元素之外,每个元素都有唯一的直接前驱和唯一的直接后继,第一个元素有唯一后继,最后一个元素有唯一前驱链表和顺
  • 顺序表应用6:有序顺序表查询

    千次阅读 2017-08-09 09:15:07
    顺序表内按照由小到大的次序存放着n个互不相同的整数,任意输入一个整数,判断该整数在顺序表中是否存在。如果在顺序表中存在该整数,输出其在表中的序号;否则输出“No Found!"。 Input 第一行输入整数n (1 ),...
  • 顺序表应用5:有序顺序表归并

    千次阅读 2016-09-26 21:00:48
    顺序表应用5:有序顺序表归并 Time Limit: 100MS Memory Limit: 800KB Problem Description 已知顺序表A与B是两个有序的顺序表,其中存放的数据元素皆为普通整型,将A与B表归并为C表,要求C表包含了A、B...
  • 数据结构之顺序表

    千次阅读 多人点赞 2021-04-03 18:56:21
    1.顺序表的概念及结构二、顺序表的接口实现1.自定义顺序表:struct SeqList2.顺序表的初始化:SeqListInit3.顺序表的检查容量:SeqListCheckCapacity3.顺序表的尾上插入数据:SeqListPushBack4.顺序表的头上插入数据:...
  • L是一个顺序表,函数ListCreate_Sq(SqList &L)用于创建一个顺序表,函数ListReverse_Sq(SqList &L)是在不引入辅助数组的前提下将顺序表中的元素进行逆置,如原顺序表元素依次为1,2,3,4,则逆置后为4,3,2,1。...
  • 目录一、数据结构1.1 算法与数据结构的区别二、顺序表2.1 顺序表的基本形式【重点】2.2 顺序表的两种基本实现方式【重点】1、一体式结构:2、分离式结构:2.3 元素存储区替换与扩充1. 元素存储区的替换2. 元素存储区...
  • 顺序表之有序顺序表重复元素删除

    千次阅读 2020-06-16 21:12:37
    (2.2.4-6)从有序顺序表中删除所有其值重复的元素,使表中所有元素的值均不同。 不考虑时间复杂度,空间复杂度为o(1) 思路:例SqList L = { 1, 2, 2, 3, 4, 4 },将每一个元素与之后面的元素进行比较,1与2比较...
  • 题目:将两个有序顺序表合并为一个新的顺序表,并由函数返回结果顺序表 (非常典型的算法方法) 算法思想: 第一步:按顺序不断取下两个顺序表中表头较小的结点,存到新的顺序表中 第二步:看哪个顺序表有剩余,将...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 99,278
精华内容 39,711
关键字:

顺序表