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

线性表的插入与删除的实现 一.算法的基本概念 1.算法的基本特征：可行性，确定性，有穷性，拥有足够的情报。 2.算法的基本要素：算法中对数据的运算和操作、算法的控制结构。 3.算法设计的基本方法：列举法、归纳法、递推、递归、减半递推技术、回溯法。 4.算法设计的要求：正确性、可读性、健壮性、效率与低存储量需求 .数据结构的定义 1.数据的逻辑结构：反映数据元素之间的关系的数据元素集合的表示。数据的逻辑结构包括集合、线形结构、树形结构和图形结构四种。 2.数据的存储结构：数据的逻辑结构在计算机存储空间种的存放形式称为数据的存储结构。常用的存储结构有顺序、链接、索引等存储结构。 五.线性结构和非线性结构 线性结构：非空数据结构满足：有且只有一个根结点；每个结点最多有一个前件，最多只有一个后件。非线性结构：如果一个数据结构不是线性结构，称之为非线性结构。 常见的线性结构：线性表、栈、队列 七.线性表的顺序存储结构 线性表的顺序存储结构具备如下两个基本特征： 1.线性表中的所有元素所占的存储空间是连续的； 2.线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。 假设线性表的每个元素需占用K个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。则线性表中第i+1个数据元素的存储位置LOC(ai+1)和第i个数据元素的存储位置LOC(ai)之间满足下列关系: LOC(ai+1)=LOC(ai)+K LOC(ai)=LOC(a1)+(i-1)*K ① LOC(a1)是线性表的第一个数据元素a1的存储位置，通常称做线性表的起始位置或基地址。 在线性表的顺序存储结构下，可以对线性表做以下运算： 插入、删除、查找、排序、分解、合并、复制、逆转 #include stdio.h #include stdlib.h #define LIST_INIT_SIZE 100 //线性表初始分配的空间 #define LISTINCREMENT 10 //线性表存储空间的分配增量 #define ElemType int typedef struct { ElemType *elem; //存储空间基址 int length; //当前长度 int listsize; //当前分配的存储容量（以sizeof(ElemType)为单位） }SqList; void initList_Sq(SqList L); //构造一个空的线性表L int listInsert_Sq(SqList L, int i, ElemType e); //插入元素 int listDelete_Sq(SqList L, int i, ElemType e); //将第i个元素删除，并用e返回 int main() { SqList L; int i; initList_Sq(L); for(i=1; i6; ++i) { listInsert_Sq(L, i, i); } for(i=0; iL.length; ++i) { printf(%d , L.elem[i]); } printf(\n); listInsert_Sq(L, 4, 6); printf(After insert:\n); for(i=0; iL.length; ++i) { printf(%d , L.elem[i]); } printf(\n); ElemType e; listDelete_Sq(L, 2, e); printf(delete the num %d, e); printf(\n); for(i=0; iL.length; ++i) { printf(%d , L.elem[i]); } printf(\n); return 0; } void initList_Sq(SqList L) {//构造一个空的线性表L L.elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemTyp