资源描述：
《《数据结构教程》第2章 线性表 C语言版.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、数据结构C语言版内容2.1线性表的定义2.2基于抽象数据类型线性表的操作2.3线性表的存储结构2.4基于顺序存储结构的线性表操作算法2.5基于链式存储的线性表操作算法2.6循环链表的操作算法2.7双向链表的操作算法2.8顺序存储线性表与链式存储线性表的比较2.9一元多项式的表示及相加第2章 线性表2.1线性表的定义1、名词术语·线性表--n个数据元素的有限序列.记为(a1,a2,……,ai-1,ai,ai+1,……，an)。例如：26英文字母表(A,B,C,……,X,Y,Z)、一个班级的学生成绩报表等 ·表长--线性表中元素的个数 ·直接前驱元素--线
2、性表中ai-1领先于ai，则ai-1是ai的直接前驱元素 ·直接后继元素--线性表中ai领先于ai+1，则ai+1是ai的直接后继元素2、线性表的抽象数据类型定义ADTList{数据对象：D={ai
3、ai∈ElemSet,i=1,2,……,n,n≥0}数据关系：R1={
4、ai-1,ai∈D,i=2,……,n}基本操作：InitList(&L)操作结果：构造一个空的线性表L。……}ADTList2.2基于抽象数据类型线性表的操作1、建立一个空的线性表2、求线性表中元素个数3、判断线性表L是否为空4、取线性表L中第i个元素5、在线性表中插
5、入某元素6、在线性表中删除某元素7、求线性表中某元素的前驱元素8、求线性表中某元素的后继元素9、在线性表中查找某元素10、两个线性表进行合并2.3线性表的存储结构1、两种存储结构：顺序存储--数组链式存储--链表2、线性表的顺序存储结构示意图：存储地址内存状态数据元素在线性表中的位序b1b+l2……b+(i-1)li……b+(n-1)lnb+nl空闲…b+(maxlen-1)l类型定义：//---线性表的动态分配顺序存储结构---#defineLIST_INIT_SIZE100//线性表存储空间的初始分配量#defineLISTINCREMENT10/
6、/线性表存储空间的分配增量typedefstruct{ElemType*elem;//存储空间基址intlength;//当前长度intlistsize;//当前分配的存储容量（以sizeof(ElemType)为单位）}SqList;3、线性表的链式存储结构L=(a1,a2,……,an)示意图：注：(a)为非空表，(b)为空表。类型定义：//---线性表的单链表存储结构---typedefstructLNode{ElemTypedata;structLNode*next; }LNode,*LinkList;2.4基于顺序存储结构的线性表操作算法1
7、、创建一个空的线性表StatusInitList_Sq(SqList&L){//构造一个空的线性表L。L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!L.elem)exit(OVERFLOW);//存储分配失败L.length=0;//空表长度为0L.listsize=LIST_INIT_SIZE;//初始存储容量returnOK;}//InitList_Sq2、插入元素算法StatusListInsert_Sq(SqList&L,inti,ElemTypee){//在顺序线性
8、表L中第i个位置之前插入新的元素e,//i的合法值为1≤i≤Listlength_Sq(L)+1if(i<1
9、
10、i>L.length+1)returnERROR;//i的值不合法if(L.length>=L.listsize){//当前存储空间已满，增加分配newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));if(!newbase)exit(OVERFLOW);//存储分配失败L.elem=newbase;//新基址L.listsize+=LIST
11、INCREMENT;//增加存储容量}q=&(L.elem[i-1]);//q为插入位置for(p=&(L.elem[L.length-1]);p>=q;--p)*(p+1)=*p;//插入位置及之后的元素右移*q=e;//插入e++L.length;//表长增1returnOK;}//ListInsert_Sq3、删除元素算法StatusListDelete_Sq(SqList&L,inti,ElemType&e){ //在顺序线性表L中删除第i个元素，并用e返回其值//i的合法值为1≤i≤Listlength_Sq(L)
12、 if((i<1)
13、
14、(i>L.length))returnERROR;//i的值不合法p
