数据结构第二章教学.ppt

第二章 线性表 线性结构特点：在数据元素的非空有限集中 存在唯一的一个被称作“第一个”的数据元素 存在唯一的一个被称作“最后一个”的数据元素 除第一个外，集合中的每个数据元素均只有一个 前驱 除最后一个外，集合中的每个数据元素均只有一 个后继 主讲教师：戴磊 2.1 线性表的类型定义 定义：一个线性表是n个数据元素的有限序列 , ,a,() ni aaa 21如 例 英文字母表（A,B,C,Z)是一个线性表 例 数据元素 特征： v元素个数n表长度，n=0空表 v1L.length+1) return ERROR;/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+=LISTINCREMENT; /增加存储容量 q= /q为插入位置 for (p=p=q;-p) *(p+1)=*p; /插入位置及之后的元素右移 *q=e; /插入e +L.length; /表长增1 return OK; /ListInsert_Sq C源代码： int sxbcr(int i,int x,int v,int *p) int j,n; n=*p; if(in+1) return (0); else for(j=n;j=i;j-) vj=vj-1; vj=x; *p=+n; return (1); 内存 a1 a2 ai ai+1 an 0 1 i-1 V数组下标 n-1 i n 1 2 i 元素序号 i+1 n n+1 内存 a1 a2 ai ai+1 an 0 1 i-1 V数组下标 n-1 i n 1 2 i 元素序号 i+1 n n+1 an-1 x v算法时间复杂度T(n) l设Pi是在第i个元素之前插入一个元素的概率，则在长度为n 的线性表中插入一个元素时，所需移动的元素次数的平均次 数为： 删除 v定义：线性表的删除是指将第i（1i n）个元素删除 ，使长度为n的线性表 变成长度为n-1的线性表 需将第i+1至第n共（n-i)个元素前移 v算法 Ch2_2.c 此算法的时间复杂度为: O( ListLength(L) ) Status ListDelete_Sq(SqList p= e=*p; q=L.elem+L.length-1; for (+p;pn) return (0); else for(j=i;jdata表示p指向结点的数据域 (*p).nextp-next表示p指向结点的指针域 生成一个LNode型新结点：p=(LinkList )malloc(sizeof(LNode); 系统回收p结点：free(p) 线性链表 v定义：结点中只含一个指针域的链表叫，也叫单链表 头结点：在单链表第一个结点前附设一个结点叫 头结点指针域为空表示线性表为空 ha1a2 头结点 an . h 空表 v单链表的基本运算 l查找：查找单链表中是否存在结点X，若有则返回指向X结点 的指针；否则返回NULL u算法描述 While循环中语句频度为 若找到结点X，为结点X在表中的序号 否则，为n pab xs u算法评价 l插入：在线性表两个数据元素a和b间插入x，已知p指向a s-next=p-next; p-next=s; u算法描述 u算法评价 Status GetElem_L(LinkList L, int pos, ElemType j = 1; / 初始化，p指向第一个结点，j为计数器 while (p +j; if ( !p | jpos ) return ERROR; / 第pos个元素不存在 e = p-data; / 取第pos个元素 return OK; / GetElem_L 算法的时间复杂度为:O(ListLength(L) 查找 C源代码: LNode *dlbcz(LNode *h,int x) LNode *p; p=h; while(p!=NULL return (p); /在带头结点的单链线性表L中第i个位置之前插入元素e Status ListInsert_L(LinkList j=0; while (p+j; if (!p |ji-1) return ERROR; s=(LinkList) malloc (sizeof(LNode); s-data=e; s-next=p-next; p-next=s; return OK; /ListInsert_L 插入 C源代码： void dlbcr(LNode *p,int x) LNode *s; s=(LNode*)malloc(sizeof(LNode); s-data=x; s-next=p-next; p-next=s; u算法描述 pabc u算法评价 l删除：单链表中删除b，设p指向a p-next=p-next-next; /在带头结点的单链线性表L中，删除第i个元素，并由e返回其值 Status ListDelete_L(LinkList j=0; while (p-next +j; if (!(p-next) |ji-1) return ERROR; q=p-next; p-next=q-next; e=q-data; free(q); return OK; /ListDelete_L 删除 C源代码： void dlbsc(LNode *p) LNode *q; if(p-next!=NULL) q=p-next; p-next=q-next; free(q); l动态建立单链表算法：设线性表n个元素已存放在数组a中， 建立一个单链表，h为头指针 u算法描述 u算法评价 h 头结点 an 0 h 头结点 an-10an a2 .h 头结点 an-10an ha1a2 头结点 an . 0 Ch2_3.c h 头结点 0 /逆位序输入n个元素的值，建立带头结点的单链线性表L void CreateList_L(LinkList L-next=NULL; for (i=n;i0;-i) p=(LinkList) malloc (sizeof(LNode); scanf( p-next=L-next; L-next=p; /CreateList_L 建单链表 C源代码： LNode *dlbjl(int a,int n) LNode *s,*h; int i; h=(LNode*)malloc(sizeof(LNode); h-data=0; h-next=NULL; for(i=n;i0;i-) s=(LNode*)malloc(sizeof(LNode); s-data=ai-1; s-next=h-next; h-next=s; return (h); u算法描述 u算法评价 l两个有序链表并为一个有序链表 算法思想：需设立3个指针pa、pb和pc，其中pa和pb分别指 向La表和Lb表中当前待比较插入的结点，而pc指向Lc表中 当前最后一个结点，若pa-datapb-data，则将pa所指结 点链接到pc所指结点之后，否则将pb所指结点链接到pc所 指结点之后。 T(n)=O(La.length+Lb.length) void MergeList_L(LinkList pb=Lb-next; Lc=pc=La; /用La的头结点作为Lc的头结点 while (pa pc=pa; pa=pa-next; else pc-next=pb;pc=pb;pb=pb-next; pc-next=pa?pa:pb; /插入剩余段 free(Lb); /释放Lb的头结点 /MergeList_L 合并 v单链表特点 l它是一种动态结构，整个存储空间为多个链表共用 l不需预先分配空间 l指针占用额外存储空间 l不能随机存取，查找速度慢 循环链表(circular linked list) v循环链表是表中最后一个结点的指针指向头结点，使 链表构成环状 v特点：从表中任一结点出发均可找到表中其他结点， 提高查找效率 v操作与单链表基本一致,循环条件不同 l单链表p或p-next=NULL l循环链表p或p-next=H h h 空表 双向链表（double linked list） 单链表具有单向性的缺点 v结点定义 typedef struct DuLNode ElemType data; struct DuLNode *prior,*next; DuLNode,*DuLinkList; priordata next L空双向循环链表： 非空双向循环链表： LAB bca p p-prior-next= p= p-next-proir; bca P void del_dulist(DuLNode *p) p-prior-next=p-next; p-next-prior=p-prior; free(p); v删除 l算法描述 l算法评价：T(n)=O(1) p-prior-next=p-next; p-next-prior=p-prior; void ins_dulist(DuLNode* p,int x) DuLNode *s; s=(DuLNode*)malloc(sizeof(DuLNode); s-data=x; s-prior=p-prior; p-prior-next=s; s-next=p; p-prior=s; l算法描述 l算法评价：T(n)=O(1) x S ba Pv插入 2.4 线性表的应用举例 一元多项式的表示及相加 一元多项式的表示： 可用线性表P表示 但对S(x)这样的多项式浪费空间 一般 其中 用数据域含两个数据项的线性表表示 其存储结构可以用顺序存储结构，也可以用单链表 单链表的结点定义 typedef struct node int coef,exp; struct node *next; JD; coefexp next x= x + 7 ( x - 17 x+ )x 87 ) = 97 )xx x +522117) 3 xBAxC x x + 9228(xxB+= 178 5(A+= -1 A 7 0 3 1 9 8 5 17 -1 B 8 1 22 7 -9 8 -1 C 7 0 11 1 22 7 5 17 一元多项式相加 设p,q分别指向A,B中某一结点，p,q初值是第一结点 比较 p-exp与q-exp p-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 -1 pa 7 0 3 1 9 8 5 17 -1 pb 8 1 22 7 -9 8 p pre q -1 pa 7 0 3 1 9 8 5 17 -1 pb 8 1 22 7 -9 8 ppre q -1 pa 7 0 11 1 9 8 5 17 -1 pb 8 1 22 7 -9 8 p pre q -1 pa 7 0 11 1 9 8 5 17 -1 pb 8 1 22 7 -9 8 p pre q=NULL -1 pa 7 0 11 1 9 8 5 17 -1 pb 8 1 22 7 -9 8 p pre q=NULL -1 pa 7 0 11 1 9 8 5 17 -1 pb 8 1 22 7 -9 8 p pre -1 pa 7 0 11 1 22 7 5 17 Ch2_7.c 算法描述 void add_poly(LNode *pa,LNode *pb) LNode *p,*q,*u,*pre; int x;