东北大学数据结构.pdf

数据结构考研辅导材料 同学们，2007年考研专业课的辅导开始了。为使大家在准备过程中少走弯路，取得事半功倍的效果。首先我给大家谈几点意见，供同学们参考。一 基本概念二基本结构的算法描述方式:顺序;链表;串;树;图.三基本操作类型:建立;查找；移动;插入;删除;合并淮I置;连接 理解逻辑概念与物理表示之间的对应(或转换)关系 学会把逻辑描述用形式语言实现的方法 要求你们:深刻理解基本概念；熟练掌握基本结构；灵活运用基本算法绪论基本概念：一、数据与数据结构1、数据在计算机科学领域，凡是计算机能识别与处理的数字、符号、图形(象)、语音以及它们的汇集通称数据。2、数据结构数据本身以及数据与数据之间的关系。在数据处理时，为了用户存取、查找、修改、更新、插入、删除等操作方，对系统中提供的原始数据必须进行加工与组织，而经过人们加工得到的数据型式称为数据结构。它是一种抽象的逻辑结构(logical structure)Data-Structure=(D,S)D 是数据元素的有限集合；S 是 D 上关系的有限集。计算机科学领域常用的四种基本的数据结(1)集合结构 数据元素之间没有固定关系。O OO O O OO O(2)线性结构数据元素之间有一对一应关系。（3）树型结构数据元素之间有一对多的关系。（4）图形结构数据元素之间有多对多的关系二、存储结构存储结构是数据结构在存储介质上的具体表现形式。数据结构与存储结构关系举例例如原始数据：9,7,4,5,3,6,1,2,8,0数据结构：0,123,4,5,6,7,8,9顺序存储链式存储数据结构与存储结构的关系：1）一种数据结构可以对应多种存储结构。但是，在一个系统中一种数据结构只能使用一种存储结构。2）存储结构在表现形式上可以与数据结构相同，也可以不同。但是，它们都必须能准确无误地保证原数据结构的逻辑关系。两种基本的存储结构1、顺序存储顺序存储是按照数据结构中元素的顺序把数据依次存储到地址连续的存储区间。特点：1）必须预知最大空间量。2）每个数据元素都占用相同的存储单元。3）逻辑上相邻的元素，它们在存储介质上的物理位置一定相邻。4）在任意位置上的插入与删除元素浪费时间。5）可以随机查找。2、链式存储是按照数据结构中元素的顺序把数据依次存储到任意的地址单元.特 点：1）可用任意空闲地址单元实现对线性表的存储；2）线性表中元素的逻辑关系，是用指针来保证的；3）在任意位置上插入与删除数据元素方便；4）在单链表中查找数据只能用顺序查找方式；5）空 间 利 用 率 比 顺 序 存 储 低；3、抽象数据类型（abstract data type,ADT）是指一个数学模型以及定义在该模型上的一组操作.其定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关,即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部的使用.一般用三元组表示：（D,S,P）D 数据对象;S 是 D 上的关系;P 是 对 D 的基本操作.格式定义：A D T 抽象数据类型名数据对象:（数据对象的定义）数据关系：（数据关系的定义）基本操作：（基本操作的定义）基本操作名（参数表）初始条件：（初始条件描述）操作结果:（操作结果描述）例，抽象数据类型三元组的定义:A D T Triplet 数据对 象:D=el,e2,e3|el,e2,e3 GElemset（定义了关系运算的集合）数据关系:Rl=,（数据关系的定义）基本操作：（InitTriplet(&T,v 1 ,v 2,v 3)结果把 el,e2,e3 分别赋给参数 vl,v2,v3。DestroyTriplet（&T）结 果 三 元 组T销毁.Get（T,i,&e）初始条件:三 元 组T存在,lWiW3;in操作结果:用e返 回T的 第i元的值.Put（&T,i,e,）初始条件:三 元 组T存在,lW i3;操作结果:改变T的 第i元 的 值 为e.Max（T,&e）初始条件:三 元 组T存在；操作结果:用e返 回T的3个元素中的最大值.Min（T,&e）operationsdataInitgetputmaxdesmintripletelempositionerror初始条件:三元组T 存在；操作结果:用e 返回T 的 3 个元素中的最小值.ADT Triplet三、算法的时间复杂度与空间复杂度1 算法的定义:算法是对某类特定问题求解步骤的描述.它应满足下列特性：(1)有零个或多个输入量；(2)每一步都有唯一确定的含义；(3)至少有一个输出量；(4)执行有限步后自动停止；(5)能用现有的程序语言实现编程上机运行；2 算法的描述方式自然语言；流程框图；伪形式语言(pascal,c,c+)3 算法的时间复杂度*程序时间复杂性的计算一个程序P,所占用的时间T(P)=编译时间+运行时间。编译时间与程序的特征无关。因此主要讨论程序的运行时间，运行时间通常用T P表示。令 n 代表程序的特征(即对程序时间有影响的参数)。那么，T P的计算公式为：TP(n)=ClADD(n)+C2SUB(n)+C3MUL(n)+C4DIV(n)+-其中，C l,C2、C3、C 4分别表示，一次加、减、乘、除操作所需的时间。函数A D D(n)、S U B(n)、M U L(n)、DIV(n)分别表示程序P 中，所使用的加、减、乘、除操作的次数。在应用中大都是估算运行时间。估算的方法往往用所有操作之中，最多的操作次数，作为该程序的时间复杂性。算法的时间相当于程序时间中的运行时间部分。同样，关键操作的次数对时间复杂性的影响最大。假设，算法中关键操作执行的次数是问题特征(规模)n 的某个函数f(n)。那么，算法的时间量度(复杂性)记作：T(n)=O(f(n)它表示随问题特征n 的增大，算法中关键操作执行次数(时间)与f(n)也增大，而且算法中关键操作执行时间的增长率和f(n)的增长率相同。所 以 称 f(n)为算法的时间复杂性。算法中语句操作执行的次数又称为频度.在实际中，用算法中语句的最大频度，作为算法的时间复杂性。4 算法的空间复杂度算法的空间相当于程序所需空间中的可变空间部分SP。所以，算法所需空间的量度记作：S(n)=O(f(n)其中N 为问题特征。表示除输入和程序之外所需的额外空间。四、关于算法时间在考试中的类型：1,给定一个算法，估算其时间复杂度;时间与空间的关系.2,给定两个算法，比较它们的语句最大频度及时间复杂度；3,限定算法时间复杂度，编写完成功能的算法；例如，设计用时间复杂度为。(n)级的算法，完成稀疏矩阵的转置阵.Status TransposcMatrix M,TSMatrix&T)M 为原阵 T 为转置T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu)存在非零元素q=l；/转置矩阵T 的下标初值for(col=l;col=M.nu;+col)从 M 阵的第一列开始查找for(p=l;p=M.tu;+p)从第一个非零元素开始if(M.datap.j=col)找到非零元素所在列号T.dataq.i=M.datap.j;T.dataq.j=M.datap.i；T.dataq.v=M.datap.v;+q；return OK;算法的时间复杂性为0 (nu*tu).若用其求m*n矩阵的转置阵算法的时间复杂性为 O(m*n*n).Status FstTransposeSMatrix(TSMatrix M,TSMatrix&T)T.mu=M.nu;T.nu=M.mu;T,tu=M.tu;if(T.tu)for(col=l;col=M.nu;4-+col)numcol=0;/置初值，清空for(t=1;t=M.tu;4-+t)-H-numM.datat.j;/计算每列非零个数copt=l;/得到第一列中第一个非零元素的位置for(col=2;col=Mnu;+col)/算每歹ij中第个元素在T 中的序号cpotcol=cpotcol-1+numcol-1;for(p=l;p=m.tu;+p)col=M.datap.j;q=cpotcol;/当前列第一非零元素地址Tdataq.i=M.datap.j;T.dataq.j=M.darap.i;T.dataq.v=M.datap.v;-H-cpotcol;fbrifReturn OK;该算法的时间复杂度为O(n)或 O(m).Operation data第二部分线性表的顺序存储一、线性表的顺序存储线性表的定义：有限序列1、线性表的抽象数据模型线 性 表(al,a2,a3,an)的数据结构：Linear List=(D,R)其 中,D=ai I ai D0,i=l,2,3.n,n=0 R=N,N=I ai-l,aie DO i=2,3,n。DO为某个数据对象。2、顺序存储的实现在高级程序语言中，一般都用数组来描述顺序存储。creat empty length。first olast oprior onext oretrieve aupdata find oInsert r adeletelocatelistpositionerror在 c 语言中可用动态分配的一维数组描述如下。define LIST_INIT IZE 100 初次分配用户预估空间量define LISTINCREAENT 10 每次分配增量，一 个 元素占Typeset struct 用空间量ElemType*elem;/数组指针表的基址int length;/当前长度，实际已存元素个数int listsize;任何时刻能存最多元素个数JSqList;空 间 量=最多元素个数*每次分配增量(每个元素占用空间量)。3、顺序存储上的运算1)查找-随机查找随机查找是利用下面两个计算公式计算所要求元素物理地址.A)已知要查找元素的逻辑地址号.逻辑地址(相对地址)是元素的位置序号；物理地址是元素在存储介质上真正的存储地址.逻辑地址号转换成物理地址的公式：LOC(ai)=LOC(aO)+i*L(L=1)i 为元素在存储空间的位置序号(逻辑地址，i 从 0 开始)。B F，知要查找元素在表中的下标号.由元素的下标号计算物理地址的公式：LOC(ai)=LOC(al)+(i-l)*L (L=1)i 为元素在表中数据a i的 下 标.(i 从 1开始)注：L 为每个元素占有的存储单元数(增量)举 例：有线性表(al a2 a3 a4.am),求元素a 3 的物理地址;在表中该元素的下标是3,所以根据公式：LOC(ai)=LOC(al)+(i-1)*L(L=1)有LOC(a3)=LOC(al)+(3-1)*L(L=1)=99+2*1=101又a 3 在内存的逻辑地址是2,所以根据公式：LOC(ai)=LOC(aO)+i*L (L=1)有LOC(a3)=LOC(aO)+2*L(L=1)=99+2*1=101逻辑地址0 1 2 3.m-1ala2a3a4am物理 地 址 99 100 101 102 103.2)顺序查找条件：不知要查找元素的逻辑地址和其在表中的元素下标，已知要查找元素的值和表的长度.只能从表的一端开始逐一比较.Status ListSearch-Sq(SqList&L,int i,ElemTypee)i=l;(i 为线性表元素的下标)While(i=L.length&L.elem i-1 e)i+;if(i L.length)return ERROR;else return(i 1);该算法的时间复杂度为。(n)。查找的有效范围是0length-10 1 2 3 length-1ala2a3a4 an问题：若要求时间复杂度不变，而要提高该算法的运算速度，应如何修改该算法？为提高实际查找速度，1)查找的有效范围改为1length；2)将控制循环查找的两个条件去掉一个；3)引入辅助单元(0单元作为辅助空间)。其算法如下：Status ListSearch-Sq(SqList,&L,key,Type key)L.elem0=key;将被查数据存放到0 单元i=length;查找起始位置为高端While(!EQ(L.elemi.key,key)循环查找i；if(il)return ERROR;超处查找范围查找失败return i;查找成功 Search-seq0 1 2 3 4.lengthcabcd n3)插入运算(1)在给定表中查找插入位置.(顺序或结合其他查找方式)(2)移动相关数据为新数据准备空间.(3)插入新数据.修改当前长度.例题知线性表顺序存储，设计算法查找一个值为X 的元素，若不存在将新元素X 插入到表的首部;若存在将其删除.Status ListInsert-Sq(SqList&L,int i,ElemenType e)i=l；(i 为逻辑线性表的下标)While(i=L.length&L.elem i-1 x)i+;if(i L.length)p=&(L.elem i-1 );P 要被删除数据的地址 x=*p;/把删除的数据放到x 中q=L.elem+L.length-1;/需移动的最后数据的位置0 for(+p;p=L.listsize)预定义空间用完newbase=(ElemType*)realloc(L.eletTi,(L.listsize+LISTINCREMENT)*sizeofiElemType);/动态再分配if(!newbase)exit(OVERFLOW);L.elem=newbase;L.listsize+=LISTINCREMENT;ifq=&(L.elemi-l);for(p=&(L.elemL.length-1);p=q;-p)*(p+l)=*p;*q=x;+L.length;return OK;(i 为逻辑线性表元素的下标4)删除运算条件：删除表中第i 个元素与该元素的逻辑地址差/再分配失败新基值 增加存储容量/保存插入位置/移动相关数据为新数据插入准备空间/插入新数据/长度增加11)Status ListDelete-Sq(SqList&L,int,ElemType&x)if(L.length=0)return ERROR;if(i L.length)return ERROR;p=&(L.elem i-1 );/P 要被删除的位置 x=*p;/把删除的数据放到x 中q=L.elem+L.length-1;需移动的最后数据的位置。for(+p;p=q;+p)*(p-l)=*p;/移动数据-L.length;/长度减 1 return OK;(i 为逻辑线性表元素的下标与该元素的逻辑地址差1)例题顺序存储，且元素递增有序.，若不存在插入，保持原序;若存在删除.(要求省时间)void InsertSq-list(SqList&L)low=0;high=L.length-1;while(low=L.length-1;+j)L.elemj-1=L.elemj;删除L.length=L.length-l;else high=m-1;/插入点在低半区else low=m+1;whilefor(j=L.length-1;j=h ig h+1 j)L.elemj+1=L.elemfj;记录后移L.elemhigh+1=x;/插入L.length=L.length+l;)设 有 N 个大小不等的数据组，顺序存放在空间区D 内，总占用空间量为m,每个数据占有一个存储单元.编写将元素X 插到第i 个数据组末尾且属该于数据组的算法.(15)1)若 第 i(i=n)个数据组直接插入。修改Si的长度。2)i n从数据组1开始查找i,然后移动相关数据，为新元素插入准备位置，修改Si+I到Sn数据如地址与S i l 的长度。void insert-x(sqlist&L,int i,ElemType x)If(i=l&i=L.length)for(j=0,p=L.elem j；j=q;-p)/q=L.elem i第 i 个数据组的首址，*(p+l)=*p;/将(p-1)位置数据移到(p)位置*p=X;/插入，修改从第i+1个数据组开始到Sn数据组地址for(q=&L.elem i,p=&L.elemL.length-l;p=q;q+)/后边位置加 1(*q)+；)m+;)例 题 知顺序存储,且数据元素递增有序.设计算法查找值为X 的元素，若存在与直接前驱元素交换.若不存在将X 插入,仍保持原序;.(要求省时间)void InsertSq-list(SqList&L)low=0;high=L.length-1;while(low=high+1;j)L.elemj+1=L.elemj;/记录后移L.elemhigh+1=x;/插入L.length=L.length+l;例：编写把从线性表(al a2 a3an)中值为X 的元素开始到an的所有元素顺序倒置的算法。从 a5=e开始到a9=I0 1 2 3 4 5678abcdefghi0 1 2 3 4 5 6 7 8倒置后abcdihgfefor(i；i next=NULL三、循环单链表：1、不带头结点的循环单链表;Lc2、带头结点循环单链表;标准形式：四、双向链表（循环，不循环）1、不带头结点的循环双向链表;（略）2、带头结点循环双向链表；*基本运算和例题一、单链表的插入运算1,首部插入（生成结点，插入结点）2,尾部插入（查找尾部结点，生成结点，插入结点）3,条件插入（查找条件结点,保存前驱结点，生成结点，插入结点）La bc,da eA将y插入到x之前Status insert-list()P=h；if p=null return ERROR;if(p-datax&p-nextnull)q=p-next;while(q-datax&q-nextnull)P=q;q=q-next;if(q-data=x)s=(LinkList)malloc(sizeof(LNode)s-data=y;s-next=p-next;P-next=s;Status insert-list()P=L;q=p-next;while(q-datax&q-nextonull)P=q;q=q-next;if(q-data=x)s=(LinkList)malloc(sizeof(LNode)；s-data=y;s-next=p-next;P-next=s;）二、单链表的删除运算1,首部删除（结点，释放结点）.2,尾部删除（查找尾部结点，保存前驱结点,释放结点）.3,条件删除（查找条件结点，保存前驱结点,释放结点）.三、循环单链表的插入与删除:可以从表中任意已知地址查遍全表Status insert-list(L)(不循环)P=L;q=p-next;while(q-data x&q-nextnull)P=q;q=q-next;if(q-data=x)s=(LinkList)malloc(sizeof(LNode)s-data=y;s-next=p-next;P-next=s;Status insert-list(Lc)P=Lc;q=p-next;(循环)while(q-datax&q-next Lc)P=q;q=q-next;if(q-data=x)s=(LinkList)malloc(sizeof(LNode)；s-data=y;s-next=p-next;P-next=s;Av为可用链表,1c为一数据无用的循环链表.要求用最少的时间把1c表与Av连接在一起.LcAv=p例题：Josephus问题:n 个人围成圆圈，从第s 个开始计数到m,便将其删除，从下个开始，重复上述过程,直到所有人都删除.(1)建立一个含有n 个结点的循环单链表jos-clist.(2)从第s 个开始查找，输出和删除m 由josephus-clist完成.#define false 0#define true 1Typedef int datatype;Stuct Node;Typedef stuct Node*PNode;Stuct Nodedatatype inf;PNode link;Typedef stuct Node*LinkList;Int init_clink(PLinklist pclist,int,n)voidJosephus(PLinklist pelist,int s,int m)PNode p,pre;int I;p=*pelist;if(s=l)pre=p;p=p-link;While(p!=*pelink)pre=p;p=p-link;else fbr(i=l;ilink;While(p!=p-link)fbr(i=l;ilink;prinef(Uout element:p-infb)if(*pelist=p)*pelist=p-link;PNode p,q;(构成循环链表)Int I;q=(PNode)malloc(sizeofstuct Node);If(q=null)return(false);*pclist=q;Q-inf l;q-link=q;Ifi(n=l)return(true);For(i=2;i n+l;i+)p=(PNode)malloc(sizeof(stuct Node);If(p=null)return(false);p-inf=l;p-link;q-link=p;q=p;尾部插入Pre-link=p-link;Free(p);p=Pre-link;prinefif Uout element:p-infb);*pelist=nullFree(p);主程序 Mia()linklist jos-clist;int n,s m;Print或 input n);Scanf(&n);Prints“input s);Scanfif&s);Prints“input m);Scanf(&m);If(init-clink(&jos-clist,n)Josephus-clink(&jos-clist,s,m);Else print/out of space);四、循环双向链表上的操作1、循环双向链表上的插入P 为双循环链表中任意一结点地址，设计用最少的辅助空间将P 与其直接后继结点交换的语句2、循环双向链表上的删除插在P 的后S-next=p-next;S-priou=p;P-next-priou=s;P-next=s;插在p 的前S-priou=P-priou;S-next=p;P-priou-next=s;P-priou=s;PP-next-priou=p-priou;(1)P-priou-next=p-next;(2)p-priou=P-next;(3)例题：1、假设A B为按元素值递增排列的单链表.编写算法将A B归并成一个按元素值递减的 C 表(C 中可以有相同元素;没有相同元素).1)AB保留，生成C 表;2)AB不保存，用其空间生成C 表.算法描述:(1)设定A 为 C 表.并将其倒置.qa,qb分别为两表中当前结点指针.(3)当 qa,qb都存在时重复：比较qa,qb结点数值，若 qa qb,将 qb插到C 表之前.若 qa=qb,将 qaqb分别插到C 表之前.(4)当 qa空时，把 qb剩余逐个插到C 表之前;(5)当 q b 空时，把 qa剩余逐个插到C 表之前;1230A50Avoid mrege(linklist&pa,linklist&pb)Lc=la;/A 表作为结果表qa=la-next;第一个结点lcnext=null;结果表置空qb=lb-next;while(!qa)/A 表倒置ra=qa-next;qa-next=lc-next;lc-next=qa;qa=ra;)qa=lc-next;pre=Lc;while(!qb)while(qa-dataqb-data&qa-next)/qa 的数大pre=qa;qa=qa-next;if(qa-next=null)u=qb-next;qb-next=qa-next;qa-next=qb;qb=u);if(qa-datadata)/qa 的数值小,qb 前插入 u=qb-next;qb-next=pre-next;pre-next=qb;pre=qb;qb=u;)例 2 知 A,B,C为三个单链表数据递增有序，要求对A 作如下处理:删除与B C 中相同的数据；LA-I I虫历 TM32 I“48 八 ILB V/2 1 4口2|7 卜21 I 4/0 I 4 4 5 0 1 ILC 一-T H 3 2 I 工46 I八Iviod delet(linklist&la)pa=la;qa=la-next;qb=lb-next;qc=lc-next;while(!qc&qb-dataqc-data&!qb)找出 BC H 所有相同元素qb=qb-next;if(qb-data=qc-data)qb=qb-next;修改 qbwhile(!qa&qa-dataoqc-data)找出 C 中 A 中所有相同元素 pa=qa;qa=qa-next;并删除if(qa-data=qc-data)pa-next=qa-next;free(qa);qa=pa-next;qc=qc-next;修改 3、（12分）假设一个有向图G 已经以十字链表形式存储在内存中，试写一个判断该有向图中是否有环（回路）的算法。解：对十字链表储存结构的有向图采用拓扑排序Status toposort(OLGraph G)(findindegree(G,indegree);对各顶点求入度InitQueue(Q);队列初始化Count=0;/计数器初始化fbr(i=O;iG.Vemum;i+)ifi(G.Ver i.indegree=O)Enqueue(Q,i);入度为零的顶点入队While(!QueueEmpty(Q)(Dequeue(Q,i);队头出队Count+;P=G.ver i.firstout;取邻接点while(p)处理邻接点的入度j=p f headvex;G.ver j.indegree;if(G.ver j.indegree=O)Enqueue(Q,j);顶点 j 入队 p=p tlink;指针后移 /while /while if(countG.vemum)有环 return ERROR;else return OK;/toposort Status findindegree（G,indegree）（根据十字表计算每个顶点的入度数填到入度域）Count=0；fdr(i=0;inext;q-freq=O;While(q-priould)置所有频度初值q-ferq=O;q=q-next;scanfifx);while(x0)if LOCATE(L,X)q-freq=q-freq+l;p=q-priou;while(pold&p-freqfreq)P=p-freq;if(!(p-freqfreq)q-next-priou=q-priou;q-priou-next=q-next;q-next=p-next;q-priou=p;p-next-priou=q;p-next=q;scanf(x)十字链表静态链表其构成：是按顺序方式分配空间，是由用户自己构造的结点来形成的一种链表。其结构类型说明如下：#define MAXSIZE 100/所需的最大空间量typedef struct ElemType data;/数据域int cur;指针域 Q component,SLinkListMAXSIZE;1void Initspace_SL(SLinkList&space)for(i=0;i-1-C-523-4-5-670当用户申请一个结点时，下边的算法就把备用链中的第一个空闲结点分配给用户。Int Malloc SL(SLinkList&space)i=spaceO.cur;if(spaceO.cur)spaceO.cur=spacei.cur;return i;Malloc SL备用链上的插入运算 把用户释放的一个结点返回备用链供用户再次使用。void Free_SL(SLinkList&space,mt k)spacek.cur=spaceO.cur;spaceO.cur=k;/采用首部插入 Free SL假设集合 A=(c,b,e,g,f,d);B=(a,b,n,f),那 么(A-B)U(B-A)void difference(SLinkList&space,intInitSpace_SL(spacc);&s)/初始备用空间链s=Malloc_S L(Space);r=s;scanf(m,n);for(j=l;jnext;保存第一个结点L-next=NULL;/将原表置成空表While(p)s=p-next;保存直接后继p-next=Lnext;首部插入L-next=p;P=s；return OK;该算法是达到同样要求的所有算法中利用辅助空间最少的一个。俩表合并A=x+2x2-4x3+3x4B=2+3x+4x3-x 5A=(1,1),(2,2),(-4,3),(3,4);B=(2,0),(3,1),(4,3),(-1,5);多项式各项生成的单链表假 设 La,Lb分别为两个单链表的头结点指针，m,n 分别为两表的长度。要求把两表联接成一个表(需 要 较 少 的 时 间)。实现算法如下：void UnionList_L(LinkList&La,LinkList&Lb,linklist&Lc)if(m next;Lc=La;q=Lb；if把两表联接else p=Lb-next;Lc=Lb;q=La La -Fl T-rwhile(!P-next)p=p-next;p-next=q-next;优以 G；Lb-卜 b HF c Ireturn(Lc);例：(17分)设有个正整数序列组成的有序单链表(按递增次序有序，且允许有相等的整数存在)，试编写能实现下列功能的算法:(要求用最少的时间和最小的空间)(00)(1)确定在序列中比正整数x 大的数有几个(相同的数只计算一次，如序列(20,20,17,16,15,15,11,10,8,7,7,5,4)中比 10 大的数有 5 个)；(2)在单链表中将比正整数x 小的数按递减次序排列；(3)在单链表中将比正整数x 大的偶数从单链表中删除；解：void exam(Linklist,La,int,x)p=La-next;q=p;k=0;/p 为工作指针pre=la;la-next=NULL;./q 指最小元素while(p&p-*datanext;La-*next=p;p=r;置逆/whileq-*next=p;pre=q;重新链接while(p-data=x)/考察等于x 的情况pre=p;p=p-next;/whilewhile(p)k 为计数器k+;x=p-data;避免重复计算if(x%2=0)删除偶数while(p-data=x)/考察等于x 的情况u=p;p=pf next;free(u);/whilepre-next=p;/ifelse/处理奇数while(p-data=x)pre f next=p;pre=p;p=p-next;/while /while(p)/exam例：已 知 L 为没有头结点的单链表中第一个结点的指针，每个结点数据域存放一个字符，该字符可能是英文字母字符或数字字符或其它字符。编写算法构造三个以带头结点的单循环链表表示的线性表，使每个表中只含有同一个类字符。(要求用最少的时间和最少的空间)(15 分)解：PROC A(L：linkisttp;VAR Letter,Digit,Other:linkisttp);new(Letter);new(Digit);new(Other);Letter.next:=Letter;DigitA.next:=Digit;Other.ncxt:=Other;While lnil dop:=L;L:=L.next;if(p*.data=,a,And pdata=,A,And p二 data=,O And p/.datadatap-*data)q=q next;/查找插入位置p fnext=q f next;插入q next=p;P=r;/whilc/if/InsertSortL例：(20分)某商店有一批手机，按价格从高价到底构成一个单链表，结点包括数量、价格、指针。现新到n 台价格不同的手机，编写将新到手机插入到原链表中的算法。解：定义此单链表的结点结构：typedef struct Lnodeint number:数量域int value：价格域struct Lnode next;/指针域Lnode,*Linklist;void insert link(Linklist&L,int n)/将新到n 台价格不同的手机插到有序链表中fbr(i=l;i=n;i+)Scanf(&price);读入每台手机价格S=(Linklist)malloc(sifeof(Lnode);S f value=price;s-*number=1;P=L next;if(p-*valuenext=s;/ifelse(while(p-*next&(p next-*values-*value)p=p next;if(!p-next)插入表尾s-*next=p-*next;p-next=s;/ifelse iRp f next-*value=s value)p next-*number+;else(s-*next=p-*next;p-next=s;/else/fbr练习题：1、把上题以单链表的存储形式再编写算法.2、知有正整数组成的无序单链表,编写完成下列功能的算法:(1)找出最小值结点,并打印输出.(2)若该数值是奇数,将其与直接后继交换.(3)若该数值是偶数,将其与直接后继删除.()()3、单链表存储的数据是按递增有序且都是正整数，编写完成下列功能的算法（用最少的时间和空间）:（1）计算比X 大的数有几个？（相同的计算一次）.（2）将小于X 的部分表倒置.（3）将大于X 的部分表中的偶数删除.（01）4、L 为无头结点单链表的第 个结点指针，每个结点存放一个字符，该字符可能是英文字母或数字或其他字符.编写构造三个带头结点循环单链表的算法.每个表中只含一类字符.（时空）.（02）5、L 为单链表头结点指针，数据都是正整数，设计算法按递增就地排序.（03）6、知手机价格按递减构成单链表，现 有 N 台新的价格不同的手机，编写把它们插到表中合适位置的算法.（04）7、（15分）已知递增有序的单链表A,B分别存储了一个集合，请设计算法以求出两个集合A 和 B 的差集A-B（即仅由在A 中而不在B 中出现的元素所构成的集合），并以同样的形式存储。要求用最少的时间。（05）8、（17分）设单链表的表头指针为h,结点结构由data和 next两个域构成，其中data域为字符型。编写算法，判断该链表的前n 个字符组成的是否为回文，要求使用栈和队列。（回文是指正读反读均相同的字符序列，如“abba”和“abdba”均是回文，但“good”不是回文。）（06）第四部分栈队列一、栈栈是允许数据元素的插入与删除从表的同一端进行的一种线性表（即输入、输出受限的一种线性表）栈上运算的最大特点是：先进后出或后进先出（FILO、LIFO）。栈可以用顺序方式实现，也可以用链式实现。opreation data允许数据元素插入、删除的一端称为栈顶另一端称为栈底端；栈顶指示器用top表;stackelementerror一）顺序存储的栈:用C 语言栈的顺序存储表示如卜:#define STACKNIT_SIZE 100;#define STACKINCREMENT 10;typedef struct SElemType*bot;SElemType*top;int stacksize;SqStack;1、栈 顶 动 进栈退栈时栈顶指示器移动1)Top=boot=0;boot不动，数据进退栈由T op指示,退栈数据进栈后Top+1,Top静态位置为新数据要存放的位置。退栈