《《数据结构(清华版)》2第二章 线性表》由会员分享，可在线阅读，更多相关《《数据结构(清华版)》2第二章 线性表（27页珍藏版）》请在金锄头文库上搜索。
1、第二章 线性表线性结构特点：在数据元素的非空有限集中存在唯一的一个被称作“第一个”的数据元素存在唯一的一个被称作“最后一个”的数据元素除第一个外，集合中的每个数据元素均只有一个 前驱除最后一个外，集合中的每个数据元素均只有一 个后继v2.1 线性表的逻辑结构定义：一个线性表是n个数据元素的有限序列例 英文字母表（A,B,C,.Z)是一个线性表例 数据元素特征：v元素个数n表长度，n=0空表v1data表示p指向结点的数据域 (*p).linkp-link表示p指向结点的指针域生成一个JD型新结点：p=(JD *)malloc(sizeof(JD); 系统回收p结点：free(p)线性链表v定义
2、：结点中只含一个指针域的链表叫，也叫单链表头结点：在单链表第一个结点前附设一个结点叫 头结点指针域为空表示线性表为空ha1a2头结点an .h空表v单链表的基本运算查找：查找单链表中是否存在结点X，若有则返回指向X结点 的指针；否则返回NULLv算法描述While循环中语句频度为若找到结点X，为结点X在表中的序号否则，为npabxsv算法评价插入：在线性表两个数据元素a和b间插入x，已知p指向as-link=p-link;p-link=s;v算法描述v算法评价v算法描述pabcv算法评价删除：单链表中删除b，设p指向ap-link=p-link-link;动态建立单链表算法：设线性表n个元素已
3、存放在数组a中， 建立一个单链表，h为头指针v算法描述v算法评价h头结点 an 0h头结点 an-10an a2.h头结点 an-10an ha1a2头结点an .0Ch2_3.ch头结点 0v单链表特点它是一种动态结构，整个存储空间为多个链表共用不需预先分配空间指针占用额外存储空间不能随机存取，查找速度慢循环链表(circular linked list)v循环链表是表中最后一个结点的指针指向头结点，使 链表构成环状v特点：从表中任一结点出发均可找到表中其他结点， 提高查找效率v操作与单链表基本一致,循环条件不同单链表p或p-link=NULL循环链表p或p-link=Hhh空表双向链表（d
4、ouble linked list）单链表具有单向性的缺点v结点定义 typedef struct node datatype element;struct node *prior,*next; JD;priorelementnextL空双向循环链表：非空双向循环链表： 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删除算法描述算法评价：T(n)=O(1)p-prior-next=p-next;p-next-pr
5、ior=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; 算法描述算法评价：T(n)=O(1)xSbaPv插入v2.4 线性表的应用举例一元多项式的表示及相加一元多项式的表示：可用线性表P表示但对S(x)这样的多项式浪费空间一般其中用数据域含两个数据项的线性表表示其存储结构可以用顺序存储结构，也可以用单链表单链表的结点定义 typedef struct node int coef,ex
6、p;struct node *next; JD;coefexpnext-1A7 0 3 1 9 8 5 17 -1B8 1 22 7 -9 8 -1C7 0 11 1 22 7 5 17 一元多项式相加设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
7、中剩余部分连到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 ppre q-1pa7 0 11 1 9 8 5 17 -1pb8 1 22 7 -9 8 ppreq=NULL-1pa7 0 11 1 9 8 5 17 -1pb8 1 22 7 -9 8 ppreq=NULL-1pa7 0 11 1 9 8 5 17 -1pb8 1 22 7 -9 8 ppre-1pa7 0 11 1 22 7 5 17 Ch2_7.c算法描述
