《数学线性表》PPT课件.ppt

第二章 线性表 线性表的类型定义 线性表的顺序表示和实现 线性表的链式表示和实现 l线性链表 l循环链表 l双向链表 一元多项式的表示及相加 Date1第二章 线性表（数据结构） 线性结构的特点 l存在唯一的一个被称作“第一个”的数据元素。 l存在唯一的一个被称作“最后一个”的数据元素。 l除第一个之外，集合中的每个数据元素只有一个前 驱。 l除最后一个之外，只有一个后驱。 Date2第二章 线性表（数据结构） 1 线性表的类型定义 最常用而且最简单的一种数据结构。 是由n (n0)个类型相同的数据元素a1, a2, ， an组成的有限序列，记作（a1, a2, ，ai-1，ai， ai+1， ，an）。这里的数据元素ai(1in)只是 一个抽象的符号，其具体含义在不同情况下可 以不同， 它既可以是原子类型，也可以是结构 类型，但同一线性表中的数据元素必须属于同 一数据对象。 Date3第二章 线性表（数据结构） 例： 英文字母表(A, B, , Z)就是一个简单的 线性表，表中的每一个英文字母是一个数据元 素， 每个元素之间存在唯一的顺序关系，如在 英文字母表字母B的前面是字母A， 而字母B的 后面是字母C。 在较为复杂的线性表中，数据元素(data elements ) 可由若干数据项组成，如学生成绩 表中，每个学生及其各科成绩是一个数据元素 ，它由学号、姓名、各科成绩及平均成绩等数 据项(item) 组成， 常被称为一个记录(record) ，含有大量记录的线性表称为文件(file)。数据 对象（data object）是性质相同的数据元素集合 。 Date4第二章 线性表（数据结构） 例 学生健康情况登记表如下： 姓 名学 号性 别年龄 健康情况 王小林790631 男 18 健康 陈 红790632 女 20 一般 刘建平790633 男 21 健康 张立立790634 男 17 神经衰弱 . . Date5第二章 线性表（数据结构） 线性表中元素的个数n，定义为线性表的长度 ，n=0时称为空表。 线性表中相邻数据元素之间存在着序偶关系， 即对于非空的线性表（a1, a2, ，ai-1, ai, ai+1, , an）， 表中ai-1 领先于ai，称ai-1 是ai的直接 前驱，而称ai是 ai-1的直接后继。 除了第一个元素a1外，每个元素ai有且仅有一 个被称为其直接前驱的结点ai-1，除了最后一个 元素an外，每个元素ai有且仅有一个被称为其 直接后继的结点ai+1。 可以对线性表进行访问、插入和删除等。 Date6第二章 线性表（数据结构） 线性表的特点可概括如下 同一性：线性表由同类数据元素组成，每一个ai必须属于同一数 据对象。 有穷性：线性表由有限个数据元素组成， 表长度就是表中数据元 素的个数。 有序性：线性表中表中相邻数据元素之间存在着序偶关系。 数据的运算是定义在逻辑结构上的，而运算的具体实 现则是在存储结构上进行的。 Date7第二章 线性表（数据结构） 线性表总结 由此可看出，线性表是一种最简单的数据结构 ，因为数据元素之间是由一前驱一后继的直观 有序的关系确定；线性表又是一种最常见的数 据结构，因为矩阵、数组、字符串、堆栈、 队 列等都符合线性条件。 Date8第二章 线性表（数据结构） 线性表的抽象数据类型定义 ADT LinearList 数据元素： D=ai| aiD0, i=1, 2, ，n, n0 ， D0为某一数据对 象 关系： | ai, ai+1D0，i=1, 2, , n-1 基本操作： （1） InitList（ Lb_len=ListLength(Lb); for(i=1;iL.Length+1) return ERROR; 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= for(p=p=q;-p) *(p+1)=*p; *q=e; +L.length; return OK; Date26第二章 线性表（数据结构） 线性表的删除运算是指将表的第i(1in)个元素删去， 使长度为n的线性表(e1，, ei-1，ei，ei+1，en)变成 长度为n-1的线性表(e1，, ei-1， ei+1，en)。 例如：线性表(4, 9, 15, 21, 28, 30, 30, 42, 51, 62)删除第5 个元素， 则需将第6个元素到第10个元素依次向前移动 一个位置。 删除操作 Date27第二章 线性表（数据结构） 顺序表中删除元素 Date28第二章 线性表（数据结构） Status ListDelete_Sq(SqList p= e=*p; q=L.elem+L.L.length-1; for(+p;pdata的值为ai，则p-next-data的值为 ai+1。 在单链表中，取得某个元素必须从头指针开始 寻找。 需要掌握的单链表重要的运算是插入和删除操 作。 Date42第二章 线性表（数据结构） 用C语言描述的单链表如下 typedef char datatype; typedef struct node datatype data; struct node *next; listnode; typedef listnode *linklist; listnode *p; linklist head; Date43第二章 线性表（数据结构） 注意区分指针变量和结点变量这两个不同的概念。P为 动态变量，它是通过标准函数生成的，即： p=(listnode*)malloc(sizeof(listnode);函数 malloc分配了一个类型为listnode的结点变量的空间 ，并将其首地址放入指针变量p中。一旦p所指的结点 变量不再需要了，又可通过标准函数free(p)释放所指 的结点变量空间。 Date44第二章 线性表（数据结构） 建立单链表 假设线性表中结点的数据类型是字符，我们逐 个输入这些字符型的结点，并以换行符n 为输入结束标记。动态地建立单链表的常用方 法有如下两种。 头插法建表 尾插法建表 Date45第二章 线性表（数据结构） 头插法建表 该方法从一个空表开始，重复读入数据，生成 新结点，将读入数据存放到新结点的数据域中 ，然后将新结点插入到当前链表的表头上，直 到读入结束标志为止。 Date46第二章 线性表（数据结构） 头插法建立单链表图示 Date47第二章 线性表（数据结构） linklist createlistf(void) char ch; linklist head; listnode *p; head=null; ch=getchar( ); while (ch!=n p=(listnode*)malloc(sizeof(listnode); pdata=ch; pnext=headnext; headnext =p; ch=getchar( ); return (head); Date48第二章 线性表（数据结构） listlink createlist(int n) int data; linklist head; listnode *p head=null; for(i=n;i0;-i) p=(listnode*)malloc(sizeof(listnode); scanf(%d， pnext=headnext; headnext =p; return(head); Date49第二章 线性表（数据结构） 尾插法建表 头插法建立链表虽然算法简单，但生成的链表 中结点的次序和输入的顺序相反。若希望二者 次序一致，可采用尾插法建表。该方法是将新 结点插入到当前链表的表尾上，为此必须增加 一个尾指针r，使其始终指向当前链表的尾结 点。 Date50第二章 线性表（数据结构） 尾插法建表图示 Date51第二章 线性表（数据结构） linklist creater( ) char ch; linklist head; listnode *p，*r; head=NULL; r=NULL; while(ch=getchar( )!=n) p=(listnode *)malloc(sizeof(listnode); pdata=ch; if(head=NULL) head=p; else rnext=p; r=p; if (r!=NULL) rnext=NULL; return(head); Date52第二章 线性表（数据结构） 查找运算 按序号查找：在链表中，即使知道被访问结点的序号i ，也不能象顺序表中那样直接按序号i访问结点，而只 能从链表的头指针出发，顺链域next逐个结点往下搜 索，直到搜索到第i个结点为止。因此，链表不是随机 存取结构。设单链表的长度为n，要查找表中第i个结 点，仅当1in时，i的值是合法的。 Date53第二章 线性表（数据结构） 获取链表第i个元素 Status GetElem_L(LinkList L,int i,ElemType j=1; while(p +j; if(!p | ji) return ERROR; e=p-data; return OK; Date54第二章 线性表（数据结构） 按值查找：按值查找是在链表中，查找是否有 结点值等于给定值key的结点，若有的话，则 返回首次找到的其值为key的结点的存储位置 ；否则返回NULL。查找过程从开始结点出发， 顺着链表逐个将结点的值和给定值key作比较 。 Date55第二章 线性表（数据结构） Listnode * locatenode(linklist head，int key) listnode * p=headnext; while( p return p; Date56第二章 线性表（数据结构） 插入运算 插入运算是将值为x的新结点插入到表的第i个结 点的位置上，即插入到ai-1与ai之间。因此，我 们必须首先找到ai-1的存储位置p，然后生成一个 数据域为x的新结点*p，并令结点*p的指针域指 向新结点，新结点的指针域指向结点ai。从而实 现三个结点ai-1，x和ai之间的逻辑关系的变化。 Date57第二章 线性表（数据结构） 在单链表第i个结点前插入一个结点的过程 Date58第二章 线性表（数据结构） 链表中插入结点 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; Date59第二章 线性表（数据结构） 删除运算 删除运算是将表的第i个结点删去。因为在单 链表中结点ai的存储地址是在其直接前趋结点a i-1的指针域next中，所以我们必须首先找到a i -1的存储位置p。然后令pnext指向ai的直接 后继结点，即把ai从链上摘下。最后释放结点 ai的空间，将其归还给“存储池”。 Date60第二章 线性表（数据结构） 单链表的删除过程 Date61第二章 线性表（数据结构） 链表中删除结点 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; Date62第二章 线性表（数据结构） C 原程序 建立链表并显示 #include “stdafx.h“ #include #include void main() int i =1; struct ListEntry int number; struct ListEntry *next; start, *node; Date63第二章 线性表（数据结构） start.next = NULL; node = do node-next = (struct ListEntry *) malloc(sizeof(struct ListEntry); node = node-next; i = getchar(); node-number = i; node-next = NULL; while( i != n); Date64第二章 线性表（数据结构） node = start.next; while (node) printf(“%c“, node-number); node = node-next; 123456789 123456789 Date65第二章 线性表（数据结构） 插入结点 node = int j=0; i=2; while(node +j; Date66第二章 线性表（数据结构） ListEntry *s; s=(struct ListEntry *) malloc(sizeof(struct ListEntry); i = getchar(); s-number = i; s-next=node-next; node-next = s; Date67第二章 线性表（数据结构） if(!node | ji-1) return; node = start.next; while (node) printf(“%c“, node-number); node = node-next; y 1y23456789 Date68第二章 线性表（数据结构） 3.2 循环链表 链表中最后一个结点的指针域指向头结点，整 个链表形成一个环。从表中任一结点出发均可 找到其他结点。其循环条件是移动的指针是否 等于头指针。 Date69第二章 线性表（数据结构） 单循环链表 在单链表中，将终端结点的指针域NULL改为指 向表头结点的或开始结点，就得到了单链形式 的循环链表，并简单称为单循环链表。 为了使空表和非空表的处理一致，循环链表中 也可设置一个头结点。这样，空循环链表仅有 一个自成循环的头结点表示。 Date70第二章 线性表（数据结构） 在用头指针表示的单链表中，找开始结点a1的时间是O(1)然而要找到终端 结点an，则需从头指针开始遍历整个链表，其时间是O(n)。 Date71第二章 线性表（数据结构） 在很多实际问题中，表的操作常常是在表的首 尾位置上进行，此时头指针表示的单循环链表 就显得不够方便.如果改用尾指针rear来表示单 循环链表，则查找开始结点a1和终端结点an都很 方便，它们的存储位置分别是(rearnext) next和rear，显然，查找时间都是O(1)。因 此，实际中多采用尾指针表示单循环链表。 由于循环链表中没有NULL指针，故涉及遍历操 作时，其终止条件就不再像非循环链表那样判 断p或pnext是否为空，而是判断它们是否等 于某一指定指针，如头指什或尾指针等。 Date72第二章 线性表（数据结构） 3.3 双向链表 循环单链表的出现，虽然能够实现从任一结点 出发沿着链能找到其前驱结点，但时间耗费是 O(n) 。如果希望从表中快速确定某一个结点的 前驱，另一个解决方法就是在单链表的每个结 点里再增加一个指向其前驱的指针域prior。 这 样形成的链表中就有两条方向不同的链，我们 可称之为双向链表。 Date73第二章 线性表（数据结构） 结点中有两个指针域，其一指向直接后续，另 一指向直接前驱。 双向链表的循环链表，存在两个环。 typedef struct DuLNode ElemType data; struct DuLNode *prior; struct DuLNode *next; DuLNode, *DuLinkList; Date74第二章 线性表（数据结构） 双链表的结点结构 Date75第二章 线性表（数据结构） 由于在双向链表中既有前向链又有后向链，寻 找任一个结点的直接前驱结点与直接后继结点 变得非常方便。设指针p指向双链表中某一结 点，则有下式成立： p-prior-next = p = p-next-prior Date76第二章 线性表（数据结构） 双向循环链表图示 Date77第二章 线性表（数据结构） 双向链表的前插操作 双向链表插入操作 Date78第二章 线性表（数据结构） 双向链表插入操作 Status ListInsert_DuL(DuLinkList if(!(s=(DuLinkList)malloc(sizeof(DuLNode) return ERROR; s-data=e; s-prior=p-prior; p-prior-next=s; s-next=p;p-prior=s; return OK; Date79第二章 线性表（数据结构） 双向链表的删除操作 双向链表的删除操作 Date80第二章 线性表（数据结构） 双向链表删除操作 Status ListDelete_DuL(DuLinkList e=p-data; p-prior-next=p-next; p-next-prior=p-prior; free(p); return OK; Date81第二章 线性表（数据结构） 顺序表和链表的比较 基于空间的考虑 l在链表中的每个结点，除了数据域外，还要额外设置指针（或光标 ）域， 从存储密度来讲，这是不经济的。所谓存储密度(Storage Density), 是指结点数据本身所占的存储量和整个结点结构所占的存储 量之比. l存储密度=结点数据本身所占的存储量/结点结构所占的存储总量 l一般地，存储密度越大，存储空间的利用率就越高。显然，顺序表 的存储密度为1，而链表的存储密度小于1。例如单链表的结点的数 据均为整数，指针所占空间和整型量相同，则单链表的存储密度为 50%。因此若不考虑顺序表中的备用结点空间， 则顺序表的存储空 间利用率为100%，而单链表的存储空间利用率为50%。由此可知， 当线性表的长度变化不大， 易于事先确定其大小时，为了节约存储 空间，宜采用顺序表作为存储结构。 Date82第二章 线性表（数据结构） 基于时间的考虑 l顺序表是由向量实现的，它是一种随机存取结构， 对表中任一结点都可以在O(1)时间内直接地存取， 而链表中的结点， 需从头指针起顺着链找才能取得 。 因