线性表的插入与删除的实现

《线性表的插入与删除的实现》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、线性表的插入与删除的实现一.算法的基本概念计算机解题的过程实际上是在实施某种算法，这种算法称为计算机算法。1.算法的基本特征：可行性，确定性，有穷性，拥有足够的情报。2.算法的基本要素：算法中对数据的运算和操作、算法的控制结构。3.算法设计的基本方法：列举法、归纳法、递推、递归、减半递推技术、回溯法。4.算法设计的要求：正确性、可读性、健壮性、效率与低存储量需求三.数据结构的定义1.数据的逻辑结构：反映数据元素之间的关系的数据元素集合的表示。数据的逻辑结构包括集合、线形结构、树形结构和图形结构四种。2.数据的存储结构：数据的逻辑结构在计算机存储空间种

2、的存放形式称为数据的存储结构。常用的存储结构有顺序、链接、索引等存储结构。在数据结构中，没有前件的结点称为根结点；没有后件的结点成为终端结点。插入和删除是对数据结构的两种基本运算。还有查找、分类、合并、分解、复制和修改等。五.线性结构和非线性结构根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分为两大类型：线性结构和非线性结构。线性结构：非空数据结构满足：有且只有一个根结点；每个结点最多有一个前件，最多只有一个后件。非线性结构：如果一个数据结构不是线性结构，称之为非线性结构。常见的线性结构：线性表、栈、队列七.线性表的顺序存储结构线性

3、表的顺序表指的是用一组地址连续的存储单元依次存储线性表的数据元素。线性表的顺序存储结构具备如下两个基本特征：1.线性表中的所有元素所占的存储空间是连续的；2.线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。即线性表逻辑上相邻、物理也相邻，则已知第一个元素首地址和每个元素所占字节数，则可求出任一个元素首地址。假设线性表的每个元素需占用K个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。则线性表中第i+1个数据元素的存储位置LOC(ai+1)和第i个数据元素的存储位置LOC(ai)之间满足下列关系:LOC(ai+1)=LOC(ai)

4、+KLOC(ai)=LOC(a1)+(i-1)*K①其中，LOC(a1)是线性表的第一个数据元素a1的存储位置，通常称做线性表的起始位置或基地址。因为在顺序存储结构中，每个数据元素地址可以通过公式①计算得到，所以线性表的顺序存储结构是随机存取的存储结构。在线性表的顺序存储结构下，可以对线性表做以下运算：插入、删除、查找、排序、分解、合并、复制、逆转#include#include#defineLIST_INIT_SIZE100//线性表初始分配的空间#defineLISTINCREMENT10//线性表存储空间的

5、分配增量#defineElemTypeinttypedefstruct{ElemType*elem;//存储空间基址intlength;//当前长度intlistsize;//当前分配的存储容量（以sizeof(ElemType)为单位）}SqList;voidinitList_Sq(SqList&L);//构造一个空的线性表LintlistInsert_Sq(SqList&L,inti,ElemTypee);//插入元素intlistDelete_Sq(SqList&L,inti,ElemType&e);//将第i个元素删除，并用e返回intmai

6、n(){SqListL;inti;initList_Sq(L);for(i=1;i<6;++i){listInsert_Sq(L,i,i);}for(i=0;i

7、deletethenum%d",e);printf("");for(i=0;i

8、储容量}intlistInsert_Sq(SqList&L,inti,ElemTypee){//在第i个元素