计算机软件及应用线性表

会计学1计算机软件及应用线性表计算机软件及应用线性表2022年5月11日星期三 链表是本章的重点和难点。扎实的指针操作和内存动态分配的编程技术是学好本章的基本要求，分清链表中指针链表是本章的重点和难点。扎实的指针操作和内存动态分配的编程技术是学好本章的基本要求，分清链表中指针 p p 和结点和结点 * *p p 之间的对应关系，区分链表中的头结点、头指针和首元结点的不同所指以及循环链表、双向链表的特点等。之间的对应关系，区分链表中的头结点、头指针和首元结点的不同所指以及循环链表、双向链表的特点等。【知识点知识点】线性表、顺序表、链表、有序表线性表、顺序表、链表、有序表第1页/共118页2022年5月11日星期三线性结构的线性结构的基本特征基本特征为为: :1集合中必存在唯一的一个集合中必存在唯一的一个“第一元素第一元素”；2集合中必存在唯一的一个集合中必存在唯一的一个 “最后元素最后元素” ；3除最后元素在外，均有除最后元素在外，均有 唯一的后继唯一的后继；4除第一元素之外，均有除第一元素之外，均有 唯一的前驱唯一的前驱。 线性结构线性结构 是是 一个数据元素的一个数据元素的有序（次序）集有序（次序）集线性表线性表是一种最简单的线性结构线性结构第2页/共118页2022年5月11日星期三1 线性表的类型定义线性表的类型定义3 线性表类型的实现线性表类型的实现 链式映象链式映象4 一元多项式的表示一元多项式的表示2 线性表类型的实现线性表类型的实现 顺序映象顺序映象第3页/共118页2022年5月11日星期三线性表的类型定义线性表的类型定义第4页/共118页2022年5月11日星期三niaaaaai11i,21a,例 英文字母表（A,B,C,.Z)例学号 姓名 年龄 001 张三 18 002 李四 19 数据元素l特征： i为元素的序号 元素个数n表长度，n=0空表 1in时 ai的直接前驱是ai-1，a1无直接前驱 ai的直接后继是ai+1，an无直接后继第5页/共118页2022年5月11日星期三 数据对象数据对象：D ai | ai D0, i=1,2,.,n, n0 称 n 为线性表的表长表长; 称 n=0 时的线性表为空表空表。数据关系数据关系：R |ai-1 ,aiD, i=2,.,n 设线性表为 (a1，a2, . . . ，ai，. . . ，an), 称 i 为 ai 在线性表中的位序位序。第6页/共118页2022年5月11日星期三第7页/共118页2022年5月11日星期三第8页/共118页2022年5月11日星期三利用上述定义的线性表线性表 可以实现其它更复杂的操作例例 2-2例例 2-1第9页/共118页2022年5月11日星期三求两个集合的并，即A=AB例例 2-1 第10页/共118页2022年5月11日星期三 要求对线性表作如下操作：扩大线性表 LA，将存在于线性表存在于线性表LB 中中而不存在于线性表不存在于线性表 LA 中中的数据元素插入到线性表插入到线性表 LA 中中去。上述问题可演绎为：第11页/共118页2022年5月11日星期三1从线性表LB中依次察看每个数据元素;2依值在线性表LA中进行查访; 3若不存在，则插入之。get (LB, i)e locate (LA, e) insert(LA, n+1, e)操作步骤：操作步骤：第12页/共118页2022年5月11日星期三 e =get(Lb, i); / 取取Lb中第中第i个数据元素赋给个数据元素赋给e if (!locate (La, e) ) insert(La, +La_len, e); / La中不存在和中不存在和 e 相同的数据元素，则插入之相同的数据元素，则插入之void union(La, Lb) La_len = length(La); / 求线性表的长度求线性表的长度 Lb_len = length(Lb); for (i = 1; i = Lb_len; i+) / union第13页/共118页2022年5月11日星期三 已知已知一个非纯集合非纯集合 B，试构造构造一个纯集合纯集合 A，使使 A中只包含中只包含 B 中所有值中所有值各不相各不相 同的数据元素同的数据元素。仍选用线性表线性表表示集合。例例 2-2第14页/共118页2022年5月11日星期三集合集合 B集合集合 A从集合 B 取出物件放入集合 A要求集合A中同样物件不能有两件以上同样物件不能有两件以上因此，算法的策略应该和例算法的策略应该和例2-1相同相同第15页/共118页2022年5月11日星期三void union(List &La, List Lb) La_len=length(La); Lb_len=length(Lb); / union e=get(Lb, i); / 取取Lb中第中第 i 个数据元素赋给个数据元素赋给 e if (!locate(La, e) ) insert(La, +La_len, e); / La中不存在和中不存在和 e 相同的数据元素，则插入之相同的数据元素，则插入之for (i = 1; i = Lb_len; i+) setnull(La); / 构造(空的)线性表LA第16页/共118页2022年5月11日星期三若线性表中的数据元素相互之间可以比较比较，并且数据元素在线性表中依值非递减或非依值非递减或非递增有序递增有序排列，即 aiai-1 或 aiai-1(i = 2,3, n)，则称该线性表为有序表有序表(Ordered List)(Ordered List)。我们再来看看有序表有序表表示的集合。第17页/共118页2022年5月11日星期三例如例如：LA=(3,5,8,11)LB=(2,6,8,9,11,15,20)对集合LA和LB 而言， 值相同的数据元素必定相邻。值相同的数据元素必定相邻。要求生成一个新表LC，使LC中的数据元素仍按值非递减有有序排列。第18页/共118页2022年5月11日星期三void MergeList(List La, List Lb, List &Lc) / 本算法将非递减的有序表 La 和 Lb 归并为 Lc / merge_listwhile (i = La_len) & (j = Lb_len) / La 和和 Lb 均不空均不空 while (i=La_len) / 若 La 不空while (j=Lb_len) / 若 Lb 不空setnull(Lc); / 构造空的线性表 Lci = j = 1; k = 0;La_len = length(La);Lb_len = length(Lb);例例 2-3第19页/共118页2022年5月11日星期三 while (i = La_len) / 当La不空时 ai= get(La, i+); insert(Lc, +k, ai); / 插入插入 La 表中剩余元素表中剩余元素 while (j = Lb_len) / 当Lb不空时 bj= get(Lb, j+); insert(Lc, +k, bj); / 插入插入 Lb 表中剩余元素表中剩余元素While( (i = La_len)& (j = Lb_len) / 当La,Lb都不空时 ai =get(La, i); bj= get(Lb, j); if(ailast = 0;第28页/共118页2022年5月11日星期三线性表的基本操作在顺序表中的实现线性表的基本操作在顺序表中的实现Locate(L, x) / 查找查找第29页/共118页2022年5月11日星期三例如：顺序表的查找操作23 75 41 38 54 62 17L.dataL.lastMAXSIZEx =38pppppi 1 2 3 4 1 850p可见，基本操作是：将顺序表中的元素逐个和给定值 x 相比较。第30页/共118页2022年5月11日星期三 int locate (sequenlist L, elemtype x) / 在顺序表中查询第一个满足判定条件的数据元素，在顺序表中查询第一个满足判定条件的数据元素， / 若存在，则返回它的位序，否则返回若存在，则返回它的位序，否则返回 0 0 O( ListLength(L) )算法的算法的时间复杂度时间复杂度为：为：int i = 1; / i i 的初值为第的初值为第 1 1 元素的位序元素的位序while (i = L.last & (L.datai!=x) +i;if (i = L.last) return i;else return 0;第31页/共118页2022年5月11日星期三线性表操作insert(L, i, x)的实现：首先分析首先分析:插入元素时，线性表的逻辑结构逻辑结构发生什么变化发生什么变化？第32页/共118页2022年5月11日星期三 (a1, , ai-1, ai, , an) 改变为 (a1, , ai-1, x, ai, , an)a1 a2 ai-1 ai ana1 a2 ai-1 ai xan, 表的长度增加第33页/共118页2022年5月11日星期三第34页/共118页2022年5月11日星期三第35页/共118页2022年5月11日星期三考虑插入算法的时间复杂度考虑插入算法的时间复杂度: :第36页/共118页2022年5月11日星期三线性表操作 delete(&L, i)的实现：首先分析：删除元素时，线性表的逻辑结构发生什么变化？第37页/共118页2022年5月11日星期三 (a1, , ai-1, ai, ai+1, , an) 改变为 (a1, , ai-1, ai+1, , an)ai+1 an, 表的长度减少a1 a2 ai-1 ai ai+1 ana1 a2 ai-1 第38页/共118页2022年5月11日星期三第39页/共118页2022年5月11日星期三 / /* *deletedelete* */ /第40页/共118页2022年5月11日星期三考虑删除算法的时间复杂度考虑删除算法的时间复杂度: :第41页/共118页2022年5月11日星期三第42页/共118页2022年5月11日星期三第43页/共118页2022年5月11日星期三第44页/共118页2022年5月11日星期三第45页/共118页2022年5月11日星期三第46页/共118页2022年5月11日星期三 用一组地址任意地址任意的存储单元存放存放线性表中的数据元素。一、单链表一、单链表以数据域数据域(数据元素的信息数据元素的信息) + 指针指针(指示后继元素存储位置指示后继元素存储位置) = 结点结点以“结点的序列结点的序列”表示线性表 称作链表链表第47页/共118页2022年5月11日星期三 以线性表中第一个数据元素 的存储地址作为线性表的地址，称作线性表的头指针。1a a1 a2 . an 头指针空指针第48页/共118页2022年5月11日星期三 typedef struct node elemtype data; / 数据域 struct node *next; / 指针域 LinkList; 二、结点和单链表的二、结点和单链表的 C 语言描述语言描述LinkList *H,*P； / H,P为单链表的头指针为单链表的头指针第49页/共118页2022年5月11日星期三头结点头结点 a1 a2 . an 头指针头指针 有时为了操作方便，在第一个结点之前虚加一个“头结点”，以指向头结点的指针为链表的头指针。空指针线性表为空表时，头结点的指针域为空 第50页/共118页2022年5月11日星期三第51页/共118页2022年5月11日星期三L 线性表的操作 GetLinkList(L,i)在单链表中的实现(找到第3个元素):211830754256pppj1 2 3第52页/共118页2022年5月11日星期三 因此，查找第因此，查找第 i 个数据元素的基本个数据元素的基本操作为：操作为：移动指针，比较移动指针，比较 j 和和 i 。 单链表不是一种顺序存取的结构，为找第单链表不是一种顺序存取的结构，为找第 i 个数据元素，必须先找到第个数据元素，必须先找到第 i-1 个数据元个数据元素。素。 令指针令指针 p p 始终始终指向指向线性表中第线性表中第 j j 个数据元素。个数据元素。第53页/共118页2022年5月11日星期三 return NULL; 第54页/共118页2022年5月11日星期三 return 0; 第55页/共118页2022年5月11日星期三第56页/共118页2022年5月11日星期三p = L; j = 0; / p p指向头结点，指向头结点，j j为计数器为计数器while (jnext!=NULL) p = p-next; +j; 这两种情况有六种组合1. p-next=NULL且j0或者i表长，异常2. p-next =NULL且j=i 空表且i=0或者i=表长3. p-next =NULL且ji 空表且inext !=NULL且jnext !=NULL且j=i 确定第i个结点 正常出循环6. p-next! =NULL且ji 异常出循环第57页/共118页2022年5月11日星期三L211830754256pLocateLinkList(L,x) 第58页/共118页2022年5月11日星期三如果要返回位序，程序怎么修改第59页/共118页2022年5月11日星期三第60页/共118页2022年5月11日星期三ai-1 线性表的操作 insertLinkList(L, x ,i)在单链表中的实现： 有序对有序对 改变为改变为 和和 xaiai-1第61页/共118页2022年5月11日星期三s-data = e; s-next = p-next; p-next = s; / 插入 eai-1aiai-1sp第62页/共118页2022年5月11日星期三 因此，在单链表中第因此，在单链表中第 i 个结点之前进个结点之前进行插入的基本操作为行插入的基本操作为: 找到线性表中第找到线性表中第i-1i-1个结点，然后修个结点，然后修改其指向后继的指针。改其指向后继的指针。 可见，在链表中插入结点只需要修改可见，在链表中插入结点只需要修改指针。但同时，若要在第指针。但同时，若要在第 i 个结点之前个结点之前插入元素，修改的是第插入元素，修改的是第 i-1 个结点的指个结点的指针。针。第63页/共118页2022年5月11日星期三第64页/共118页2022年5月11日星期三int insertLinkList (LinkList *L, ElemType e, int i) LinkList *p = L; int j = 0;while (p & j next; +j; / 寻找第寻找第 i-1 个结点个结点if (!p | j i-1) return 0; / i 大于表长或者小于大于表长或者小于1 第65页/共118页2022年5月11日星期三s = (LinkList*) malloc ( sizeof (node); / 生成新结点s-data = e; s-next = p-next; p-next = s; / 插入return 1; eai-1aiai-1sp第66页/共118页2022年5月11日星期三循环条件的分析第一次循环p!=NULL,j有三种可能1.ji-1 i1不合法1.p=!NULL且ji-1 继续循环2.p=!NULL且j=i-1 已经定位 正常出循环3.p=NULL且j=表长+2），出循环第二次循环后，p有可能NULL,但是ji-1不可能，出现的各种可能情况：第67页/共118页2022年5月11日星期三第68页/共118页2022年5月11日星期三线性表的操作deleteLinkList (L, i)在链表中的实现:有序对有序对 和和 改变为改变为 ai-1aiai+1ai-1第69页/共118页2022年5月11日星期三 在单链表中删除第删除第 i i 个结点个结点的基本基本操作操作为:找到线性表中第找到线性表中第i-1i-1个结点，修个结点，修改其指向后继的指针。改其指向后继的指针。ai-1aiai+1ai-1q = p-next; p-next = q-next; e = q-data; free(q);pq第70页/共118页2022年5月11日星期三第71页/共118页2022年5月11日星期三 int deleteLinkList (LinkList *L, int i, ElemType &e) LinkList *p = L; int j = 0;while (p-next!=NULL & j next; / 寻找第 i 个结点，并令 p 指向其前趋 +j; if (!(p-next) | j i-1) return 0; / 删除位置不合理q = p-next; p-next = q-next; / 删除并释放结点e = q-data; free(q);return 1;第72页/共118页2022年5月11日星期三第73页/共118页2022年5月11日星期三度为O(n)。第74页/共118页2022年5月11日星期三第75页/共118页2022年5月11日星期三如何从得到单链表？如何从得到单链表？链表是一个动态的结构，它不需要链表是一个动态的结构，它不需要予分配空间，因此予分配空间，因此生成链表的过程生成链表的过程是一个结点是一个结点“逐个插入逐个插入” ” 的过程。的过程。第76页/共118页2022年5月11日星期三例如：逆位序输入例如：逆位序输入 n n 个数据元素的值，个数据元素的值， 建立带头结点的单链表。建立带头结点的单链表。( (头插法头插法) )操作步骤：操作步骤：一、建立一个一、建立一个“空表空表”；二、输入数据元素二、输入数据元素an， 建立结点并插入；建立结点并插入；三、输入数据元素三、输入数据元素an-1， 建立结点并插入；建立结点并插入；ananan-1四、依次类推，直至输入四、依次类推，直至输入a a1 1为止。为止。第77页/共118页2022年5月11日星期三adcbi=0i=1i=2i=3head采用头插法建立单链表的过程采用头插法建立单链表的过程headaheaddaheadcdaheadbcda第第1 1步步: :建头结点建头结点第第2 2步步:i:i0,0,新建新建a a结点结点, ,插入到头结点之后插入到头结点之后第第3 3步步:i:i1,1,新建新建d d结点结点, ,插入到头结点之后插入到头结点之后第第4 4步步:i:i2,2,新建新建c c结点结点, ,插入到头结点之后插入到头结点之后第第5 5步步:i:i3,3,新建新建b b结点结点, ,插入到头结点之后插入到头结点之后第78页/共118页2022年5月11日星期三void CreateList (LinkList *&L, int n) / 逆序输入 n 个数据元素，建立带头结点的单链表算法的算法的时间复杂度时间复杂度为:O(Listlength(L)L = (LinkList*) malloc (sizeof (node);L-next = NULL; / 先建立一个带头结点的单链表for (i = n; i 0; -i) p = (LinkList*) malloc (sizeof (node); scanf(“%d”,&p-data); / 输入元素值 p-next = L-next; L-next = p; / 插入第79页/共118页2022年5月11日星期三第80页/共118页2022年5月11日星期三r=head; /*尾指针初始化*/ch=getchar(); while(ch!=*) /“*”为输入 数据结束 符 号*/ scanf(“%d”,&x); P=(LinkList*)malloc(sizeof(LinkList); P-data=x; P-next=NULL; r-next=P; r=r-next; ch=getchar();return head;第81页/共118页2022年5月11日星期三第82页/共118页2022年5月11日星期三LinkList * CreateList(int n) /* 正位序(插在表尾)输入n个元素的值，建立带表头结构的单链线性表 */int i;LinkList *L;LinkList * p,*r;L=(LinkList *)malloc(sizeof(LinkList); /* 生成头结点 */L-next=NULL;r=L;printf(请输入%d个数据n,n);for(i=1;idata);p-next=NULL;r-next=p;r=p;return L 第83页/共118页2022年5月11日星期三Lb26891115 La35811 第84页/共118页2022年5月11日星期三第85页/共118页2022年5月11日星期三 例例 设设C=a1,b1,a2,b2,an,bn为一线性表为一线性表,采用带头结采用带头结点的点的hc单链表存放单链表存放,编写一个算法编写一个算法,将其拆分为两个将其拆分为两个线性表线性表,使得使得: A=a1,a2,an,B=b1,b2,bn 解解:设拆分后的两个线性表都用带头结点的单链表设拆分后的两个线性表都用带头结点的单链表存放。先建立两个头结点存放。先建立两个头结点*ha和和*hb,它们用于它们用于存放存放拆分拆分后的线性表后的线性表A和和B, ra和和rb分别分别指向指向这两个单链表的这两个单链表的表表尾尾。用用p指针扫描单链表指针扫描单链表hc,将当前结点将当前结点*p链到链到ha未未尾尾, p沿沿next域下移一个结点域下移一个结点,若不为空若不为空, 则当前结点则当前结点*p链到链到hb未尾未尾, p沿沿next域下移一个结点域下移一个结点, 如此这样如此这样, 直到直到p为空。最后将两个尾结点的为空。最后将两个尾结点的next域置空。域置空。 第86页/共118页2022年5月11日星期三 void fun(LinkList *hc, LinkList *&ha, LinkList *&hb) LinkList *p=hc-next,*ra,*rb; ha=hc; /*ha的头结点利用的头结点利用hc的头结点的头结点*/ ra=ha; /*ra始终指向始终指向ha的末尾结点的末尾结点*/ hb=(LinkList *)malloc(sizeof(LinkList); /*创建创建hb头结点头结点*/ rb=hb; /*rb始终指向始终指向hb的末尾结点的末尾结点*/ 本算法实际上是采用尾插法建立两个新表。本算法实际上是采用尾插法建立两个新表。所以所以, ,尾插法建表算法是很多类似习题的基础！尾插法建表算法是很多类似习题的基础！第87页/共118页2022年5月11日星期三 while (p!=NULL) ra-next=p;ra=p; /*将将*p链到链到ha单链表未尾单链表未尾*/ p=p-next; if (p!=NULL) rb-next=p; rb=p; /*将将*p链到链到hb单链表未尾单链表未尾*/ p=p-next; ra-next=rb-next=NULL; /*两个尾结点的两个尾结点的next域置空域置空*/第88页/共118页2022年5月11日星期三第89页/共118页2022年5月11日星期三第90页/共118页2022年5月11日星期三第91页/共118页2022年5月11日星期三第92页/共118页2022年5月11日星期三顺序存储结构的优缺点第93页/共118页2022年5月11日星期三第94页/共118页2022年5月11日星期三h空表v特点：从表中任一结点出发均可找到表中其他结点，提高查找效率v操作与单链表基本一致,循环条件不同l单链表p或p-next=NULLl循环链表p或p-next=Hh第95页/共118页2022年5月11日星期三r空表设置尾指针的循环链表设置尾指针的循环链表，在对两个单循环链表进行连接使可以提高效率。r2b1bnr1a1anr1-next=r2-next-next;r2-next=p;rpp=r1-next;第96页/共118页2022年5月11日星期三typedef struct dupnode elemtype data; struct dupnode *prior,*next;duplinklist;priordatanextL空双向循环链表：非空双向循环链表： LABbcapp-prior-next= p= p-next-proir;第97页/共118页2022年5月11日星期三双向链表的操作特点：双向链表的操作特点：“查询查询” ” 和单链表相同。和单链表相同。“插入插入” ” 和和“删除删除”时需要同时修改两个方向上的指针。时需要同时修改两个方向上的指针。第98页/共118页2022年5月11日星期三void ins_dlinklist(duplinklist * p,int x)duplinklist *s; s=(duplinklist *)malloc(sizeof(duplinklist ); s-data=x; s-prior=p-prior; p-prior-next=s; s-next=p; p-prior=s; 算法描述 算法评价：T(n)=O(1)xSbaP 插入p-prior-next=s;s-prior=p-prior;s-next=p;p-prior=s;第99页/共118页2022年5月11日星期三ai-1aies-next = p-next; p-next = s;s-next-prior = s; s-prior = p;psai-1ai插入插入第100页/共118页2022年5月11日星期三bcaPvoid del_dlinklist(duplinklist *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-prior;第101页/共118页2022年5月11日星期三ai-1删除删除aiai+1p-next = p-next-next;p-next-prior = p;pai-1第102页/共118页2022年5月11日星期三用上述定义的单链表实现线性表的操作时，用上述定义的单链表实现线性表的操作时，存在的存在的问题问题： 改进链表的设置改进链表的设置1单链表的表长是一个隐含的值；单链表的表长是一个隐含的值； 1增加增加“表长表长”、“表尾指针表尾指针” 和和 “当前当前位置的位置的 指针指针” 三个数据域；三个数据域；2在单链表的最后一个元素之后插入元素时，在单链表的最后一个元素之后插入元素时， 需遍历整个链表；需遍历整个链表；3在链表中，元素的在链表中，元素的“位序位序”概念淡化，结点的概念淡化，结点的 “位置位置”概念加强。概念加强。2将基本操作中的将基本操作中的“位序位序 i ”改变为改变为“指针指针 p ”。第103页/共118页2022年5月11日星期三一个带头结点的线性链表类型一个带头结点的线性链表类型typedef struct node / 结点类型结点类型 ElemType data; struct node *next; Link;typedef struct / 链表类型链表类型 Link * head, *tail; / 分别指向头结点和 /最后一个结点的指针 int len; / 指示链表长度 Link* current; / 指向当前被访问的结点 /的指针，初始位置指向头结点 LinkList;第104页/共118页2022年5月11日星期三第105页/共118页2022年5月11日星期三nnnxpxpxppxp.)(2210在计算机中，可以用一个线性表来表示在计算机中，可以用一个线性表来表示: P = (p0, p1, ，pn)一元多项式一元多项式但是对于形如但是对于形如 S(x) = 1 + 3x10000 2x20000的多项式，上述表示方法是否合适？的多项式，上述表示方法是否合适？第106页/共118页2022年5月11日星期三 一般情况下的一元稀疏多项式一元稀疏多项式可写成 Pn(x) = p1xe1 + p2xe2 + + pmxem其中其中：pi 是指数为ei 的项的非零系数， 0 e1 e2 em = n可以下列线性表表示：（p1, e1）, (p2, e2), , (pm,em) ）第107页/共118页2022年5月11日星期三 P999(x) = 7x3 - 2x12 - 8x999例如例如:可用线性表 ( (7, 3), (-2, 12), (-8, 999) )表示第108页/共118页2022年5月11日星期三释放q结点第109页/共118页2022年5月11日星期三第110页/共118页2022年5月11日星期三第111页/共118页2022年5月11日星期三第112页/共118页2022年5月11日星期三第113页/共118页2022年5月11日星期三第114页/共118页2022年5月11日星期三第115页/共118页2022年5月11日星期三第116页/共118页2022年5月11日星期三第117页/共118页