数据结构(C语言描述)-线性表

第二章线性表线性结构特点：在数据元素的非空有限集中·存在唯一的一个被称作“第一个”的数据元素·存在唯一的一个被称作“最后一个”的数据元素·除第一个外，集合中的每个数据元素均只有一个前驱·除最后一个外，集合中的每个数据元素均只有一个后继2.1线性表的逻辑结构·定义:一个线性表是n个数据元素的有限序列例英文字母表(A,B,C,…..Z)是一个线性表例数据元素·特征:·元素个数n—表长度，n=0空表·1<i<n时ai的直接前驱是ai-1，a1无直接前驱ai的直接后继是ai+1，an无直接后继·元素同构，且不能出现缺项2.2线性表的顺序存储结构·顺序表:·定义:用一组地址连续的存储单元存放一个线性表叫~·元素地址计算方法:LOC(ai)=LOC(a1)+(i-1)*LLOC(ai+1)=LOC(ai)+L其中:L—一个元素占用的存储单元个数LOC(ai)—线性表第i个元素的地址·特点:实现逻辑上相邻—物理地址相邻实现随机存取·实现:可用C语言的一维数组实现a1a2an01n-112n内存V数组下标元素序号M-1线性表的动态分配顺序存储结构#define

LIST_SIZE

100#define

LISTINCREMENT

10typedef

struct

{ElemType

*elem;length;listsize;intint}Sqlist;备用空间·插入·定义：线性表的插入是指在第I（1 i n+1)个元素前插入一个新的数据元素x，使长度为n的线性表变成长度为n+1的线性表需将第i至第n共(n-i+1)个元素后移·算法Ch2_1.ca1a2aiai+1an01i-1V数组下标in-1n12i内存 元素序号i+1nn+1a1a2ai+101i-1V数组下标in-1n12i内存 元素序号i+1nn+1an-1anxai·算法时间复杂度T(n)设Pi是在第i个元素之前插入一个元素的概率，则在长度为n的线性表中插入一个元素时，所需移动的元素次数的平均次数为:i n)个元素删·删除·定义：线性表的删除是指将第i(1使长度为n的线性表变成长度为n-1的线性表需将第i+1至第n共(n-i)个元素前移·算法Ch2_2.ca1a2aiai+1an01i-1V数组下标in-1n12i内存 元素序号i+1nn+1a1a2ai+1V数组下标01i-1in-2n-112i内存 元素序号i+1n-1nanai+2·算法评价设Qi是删除第i个元素的概率，则在长度为n的线性表中删除一个元素所需移动的元素次数的平均次数为:故在顺序表中插入或删除一个元素时,平均移动表的一半元素,当n很大时,效率很低·顺序存储结构的优缺点·优点逻辑相邻,物理相邻可随机存取任一元素存储空间使用紧凑·缺点插入、删除操作需要移动大量的元素预先分配空间需按最大空间分配,利用不充分表容量难以扩充2.3线性表的链式存储结构特点:·用一组任意的存储单元存储线性表的数据元素·利用指针实现了用不相邻的存储单元存放逻辑上相邻的元素·每个数据元素ai，除存储本身信息外，还需存储其直接后继的信息·结点数据域:元素本身信息指针域:指示直接后继的存储位置结点数据域指针域ZHAOQIANSUNLIZHOUWUZHENGWANG^H例线性表

(ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)43131NULL3771925数据域

指针域LIQIANSUNWANGWUZHAOZHENGZHOU存储地址17131925313743H31头指针·实现typedef

struct

Lnode

{ElemType

data;struct

Lnode

*next;}Lnode,*LinkList;生成一个LinkList型新结点:p=(LinkList)malloc(sizeof(Lnode));系统回收p结点:free(p)·线性链表·定义:结点中只含一个指针域的链表叫~，也叫单链表头结点:在单链表第一个结点前附设一个结点叫~头结点指针域为空表示线性表为空ha1a2头结点an

^…...h空表^·单链表的基本运算px查找：查找单链表中是否存在结点X，若有则返回指向X结点的指针;否则返回NULL算法描述算法评价若找到结点X，为结点X在表中的序号While循环中语句频度为否则，为n插入：在线性表两个数据元素a和b间插入x，已知p指向abs->next=p->next;ap->next=ss;算法描述算法评价算法描述算法评价删除:单链表中删除b，设p指向ap a b cp->next=p->next->next;动态建立单链表算法:设线性表n个元素已存放在数组a中，建立一个单链表，h为头指针算法描述算法评价anan-1a12

^ana…2

..^.an

^an…-1

...Ch2_3.ch头结点0^·单链表特点它是一种动态结构,整个存储空间为多个链表共用不需预先分配空间指针占用额外存储空间不能随机存取,查找速度慢·循环链表(circular

linked

list)·循环链表是表中最后一个结点的指针指向头结点，使链表构成环状·特点:从表中任一结点出发均可找到表中其他结点，提高查找效率·操作与单链表基本一致,循环条件不同单链表p或p->next=NULL循环链表p或p->next=Hhh空表·双向链表（doublelinkedlist)单链表具有单向性的缺点·结点定义typedef

struct

Dulnode

{elemtype

data;struct

Dulnode

*prior,*next;}

Dulnode,*Dulinklist;priordatanextL空双向循环链表:ABbc非空双向循环链表a:Lpp->prior->next=

p=

p->next->proir;b

cavoid

del_dulist(Dulinklist

p){p->prior->next=p->next;p->next->prior=p->prior;free(p);}·删除算法描述算法评价:T(n)=O(1)p->prior->next=p->next;p->next->prior=p->priorPvoid

ins_dulist(Dulinklist

p,int

x){Dulinklist

s;s=(Dulinklist)malloc(sizeof(Dulnode

s->data=x;s->prior=p->prior;p->prior->next=s;s->next=p;p->prior=s;}算法描述算法评价:T(n)=O(1)xSbaP·插入2.4线性表的应用举例一元多项式的表示及相加·一元多项式的表示:可用线性表P表示但对S(x)这样的多项式浪费空间一般其中用数据域含两个数据项的线性表表示其存储结构可以用顺序存储结构，也可以用单链表·单链表的结点定义typedef

struct

node{

int

coef,exp;struct

node

*next;coefexpnextABC-1703198517^-181227-98^-170111227517^}JD;·一元多项式相加比较p->exp与q->exp设p,q分别指向A,B中某一结点,p,q初值是第一结点p->exp<q->exp:p结点是和多项式中的一项p后移,q不动p->exp=q->exp:系数相加p->exp>q->exp:q结点是和多项式中的一项将q插在p之前,q后移,p不动0:从A表中删去p,释放p,q,p,q后移0:修改p系数域,释放q，p,q后移若q==NULL,结束直到p或q为NULL若p==