数据线性结构、顺序表及链表

1、数据线性结构、数据线性结构、顺序表及链表顺序表及链表数据的线性结构数据的线性结构线性结构线性结构特点特点：在数据元素的非空有限集中：在数据元素的非空有限集中l存在存在唯一唯一的一个被称作的一个被称作“第一个第一个”的数据元素的数据元素l存在存在唯一唯一的一个被称作的一个被称作“最后一个最后一个”的数据元素的数据元素l除第一个外，集合中的每个数据元素均除第一个外，集合中的每个数据元素均只有一个只有一个前驱前驱l除最后一个外，集合中的每个数据元素均除最后一个外，集合中的每个数据元素均只有一只有一个后继个后继l1 线性表的逻辑结构线性表的逻辑结构l定义：一个线性表是定义：一个线性表是n个数据元素的有

2、限序列个数据元素的有限序列niaaaa,21如例 英文字母表（A,B,C,.Z)是一个线性表例学号姓名年龄001张三18002李四19数据元素特征：v元素个数n表长度，n=0空表v1idata表示p指向结点的数据域(*p).linkp-link表示p指向结点的指针域生成一个JD型新结点：p=(JD *)malloc(sizeof(JD);系统回收p结点：free(p)线性链表v定义：结点中只含一个指针域的链表叫，也叫单链表ha1a2头结点an .h空表头结点：在单链表第一个结点前附设一个结点叫头结点指针域为空表示线性表为空单链表的基本运算单链表的基本运算 查找：查找单链表中是否存在结点X，若有

3、则返回指向X结点的指针；否则返回NULL 算法描述While循环中语句频度为若找到结点X，为结点X在表中的序号否则，为n nOnTpabxsu算法评价l插入：在线性表两个数据元素a和b间插入x，已知p指向as-link=p-link;p-link=s; 1OnTu算法描述u算法评价 算法描述pabc 1OnTu算法评价l删除：单链表中删除b，设p指向ap-link=p-link-link; nOnTl动态建立单链表算法：设线性表n个元素已存放在数组a中，建立一个单链表，h为头指针u算法描述u算法评价h头结点an 0h头结点an-10an a2.h头结点an-10an ha1a2头结点an .0

4、h头结点0单链表特点单链表特点 它是一种动态结构，整个存储空间为多个链表共用 不需预先分配空间 指针占用额外存储空间 不能随机存取，查找速度慢l循环链表循环链表(circular linked list)循环链表是表中最后一个结点的指针指向头结点，循环链表是表中最后一个结点的指针指向头结点，使链表构成环状使链表构成环状特点：从表中任一结点出发均可找到表中其他结点特点：从表中任一结点出发均可找到表中其他结点，提高查找效率，提高查找效率操作与单链表基本一致操作与单链表基本一致,循环条件不同循环条件不同 单链表p或p-link=NULL 循环链表p或p-link=Hhh空表l双向链表（双向链表（do

5、uble linked list）单链表具有单向性的缺点单链表具有单向性的缺点结点定义结点定义typedef struct node datatype element; struct node *prior,*next;JD;prior element nextL空双向循环链表：非空双向循环链表：LABbcapp-prior-next= p= p-next-proir;bcaPvoid del_dulist(JD *p)p-prior-next=p-next; p-next-prior=p-prior; free(p);v删除l算法描述l算法评价：T(n)=O(1)p-prior-next=p

6、-next;p-next-prior=p-prior;void ins_dulist(JD* p,int x)JD *s; s=(JD*)malloc(sizeof(JD); s-element=x; s-prior=p-prior; p-prior-next=s; s-next=p; p-prior=s;l算法描述l算法评价：T(n)=O(1)xSbaPv插入l4 线性表的应用举例线性表的应用举例 一元多项式的表示及相加一元多项式的表示及相加l一元多项式的表示：一元多项式的表示：nnnxPxPxPPxP2210)(),(210nPPPPP可用线性表P表示200001000231)(xxxS但

7、对S(x)这样的多项式浪费空间一般emmnxPxPxPxPee2121)(其中为非零系数）（iPemee210用数据域含两个数据项的线性表表示emPePePm，2121其存储结构可以用顺序存储结构，也可以用单链表l单链表的结点定义单链表的结点定义coefexpnext17787172522117)()()(9228)(5937)(xxxxBxAxCxxxxBxxxxA-1A7 0 3 1 9 8 5 17 -1B8 1 22 7 -9 8 -1C7 0 11 1 22 7 5 17 一元多项式相加typedef struct node int coef,exp; struct node *ne

8、xt;JD;设p,q分别指向A,B中某一结点，p,q初值是第一结点比较p-exp与q-expp-exp exp: p结点是和多项式中的一项 p后移,q不动p-exp q-exp: q结点是和多项式中的一项 将q插在p之前,q后移,p不动p-exp = q-exp: 系数相加0：从A表中删去p, 释放p,q，p,q后移0：修改p系数域, 释放q，p,q后移直到p或q为NULL 若q=NULL，结束 若p=NULL，将B中剩余部分连到A上即可运算规则q-1pa7 0 3 1 9 8 5 17 -1pb8 1 22 7 -9 8 ppreq-1pa7 0 3 1 9 8 5 17 -1pb8 1 22 7 -9 8 ppreq-1pa7 0 11 1 9 8 5 17 -1pb8 1 22 7 -9 8 ppreq-1pa7 0 11 1 9 8 5 17 -1pb8 1 22 7 -9 8