文档介绍：线性结构线性结构是数据结构中最简单、最常用的数据结构。特点:数据元素有序并有限。线性结构中数据元素的逻辑关系:1)有且仅有一个起始元素(无直接前趋,只有一个直接后继的元素)。2)有且仅有一个终点元素(无直接后继,只有一个直接前趋的元素)。3)其他元素,皆只有一个直接前趋和一个直接后继。线性结构包括:线性表、堆栈、队列、数组、串等。*§:线性表是由n(n0)个具有相同类型的元素a1,a2,,ai,,an,所构成的一个有限的线性序列。其中n为表长,ai为线性表中的第i个元素,ai可以是一个数,符号或其它更复杂的信息,但ai必须具有相同的数据类型,即属同一数据对象。n=0时为空表,非空时每个数据元素都有一个确定的位置。线性表的基本操作:设L是一个线性表 INITIATE(L):初始化线性表。LENGTH(L);求表长,返回值为int型。GET(L,i):访问表中的第i个元素。*LOCATE(L,X):定位,查找表中等于X的元素的位置,返回值为int型。返回表中等于X的元素的序号i。若表中有m(m>1)个元素等于X,则返回序号最小的i。若ai≠X,则返回一特殊值(比如-1,有的定义返回0)。INSERT(L,i,X):在表L的第i个位置上插入X。 if(1i(LENGTH(L)+1) {则在L的第i个位置上插入X; n++; return(true); } elsereturn(flase);*DELETE(L,i):删除表L中的第i个元素。 if(1iLENGTH(L)) {删除L中的第i个元素; n--; return(true); } elsereturn(false);*#rue1#definefalse0voidunion(Linear_ListLA,Linear_ListLB){inti,k,n;elemtypex;n=LENGTH(LA);/*取LA表的表长*/for(i=1;iLENGTH(LB);i++){x=GET(LB,i);/*取LB表中的第i个元素*/k=LOCATE(LA,x);/*x在LA中定位*/if(k==false)/*若LA中的元素aix*/{INSERT(LA,n+1,x);/*将x插入LA的后面*/n++;/*表长加1*/}}}例:已知线性表LA,LB,求LA=LA∪LB。假设两线性表中的元素的数据类型同为elemtype。*线性表的存储方式:顺序存储结构——顺序表链式存储结构——链表定义:在顺序表的存储结构中,各元素是以一组地址连续的存储单元来依次存放的。顺序表中的任一元素ai的存储地址可用下式来表示:Loc(ai)=Loc(a1)+(i-1)*kLoc(ai)和i呈线性关系,读取元素方便,因此称顺序表为随机存储结构。顺序表中逻辑关系相邻的元素ai,ai+1的物理位置也相邻,即是利用了元素在计算机中的物理位置之间的关系来反映数据元素之间的逻辑关系。顺序表存储地址内存序号Loc(a1)Loc(a1)+kLoc(a1)+(i-1)*kLoc(a1)+(n-1)*k12inmaxnuma1a2aian*用数组实现线性表(顺序存储)线性表元素:a1、a2、a3、a4....数组元素:a[0]、a[1]、a[2]、a[3]线性关系:a1a2a3a4数组下标大小*data[i–1]定义元素类型线性表名称[线性表长度]例intdata[max_length];以a0开始的线性表--a0、a1、a2、a3……data[i]以a1开始的线性表--a1、a2、a3、a4……aiai*顺序表的C语言描述:typedefstruct{elemtypedata[Maxnum];intnum;}Listtype;Listtype*list;data数组用于存放类型为elemtype的数据元素最大表长实际表长结构类型名list->data[i-1]以a0开始的a?i-1以a1开始的a?都是线性表的第?个元素ii*对list这个顺序表初始化:voidinitiatelist(listtype*l){l->num=0;}算法1、顺序表的插入。已知顺序表L=(a1,a2,,ai-1,ai,,an,),INSERT(L,i,x)的物理含义是:在ai-1和ai之间插入元素x。表长变为n+1。即L=(a1,a2,,ai-1,x,ai,,an,)。*问题描述以a1开始的线性表中在第i个元素前插入一个新元素x。顺序表操作*