《数据结构》课后习题答案.pdf

《《数据结构》课后习题答案.pdf》由会员分享，可在线阅读，更多相关《《数据结构》课后习题答案.pdf（108页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、m_高_等_学_校_精_品_资_源_共享_课程十二五普通高等教育国家级本科规划教材 绪论第 1 章1.1 什么是数据结构？【答】：数据结构是指按定的逻辑结构组成的 批数据，使用某种存储结构将这批数据存储于计算机中，并在这些数据上定义了一个运算集合。1.2 数据结构涉及哪几个方面？【答】：数据结构涉及三个方面的内容，即数据的逻辑结构、数据的存储结构和数据的运算集合。1.3 两个数据结构的逻辑结构和存储结构都相同，但是它们的运算集合中有个运算的定义不一样，它们是否可以认作是同一个数据结构？为什么？【答】：不能，运算集合是数据结构的重要组成部分，不同的运算集合所确定的数据结构是不一样的，例如，栈与队

2、列它们的逻辑结构与存储结构可以相同，但由于它们的运算集合不一样,所以它们是两种不同的数据结构。1.4 线性结构的特点是什么？非线性结构的特点是什么？【答】：线性结构元素之间的关系是一对一的，在线性结构中只有一个开始结点和一个终端结点，其他的每一个结点有且仅有一个前驱和一个后继结点。而非线性结构则没有这个特点，元素之间的关系可以是一对多的或多对多的。1.5 数据结构的存储方式有哪几种？【答】：数据结构的存储方式有顺序存储、链式存储、散列存储和索引存储等四种方式。1.6 算法有哪些特点？它和程序的主要区别是什么？【答】：算法具有（1）有穷性（2）确定性（3）0个或多个输入（4）1个或多个输出（5）

3、可行性等特征。程序是算法的一种描述方式，通过程序可以在计算机上实现算法。1.7 抽象数据类型的是什么？它有什么特点？【答】：抽象数据类型是数据类型的进一步抽象，是大家熟知的基本数据类型的延伸和发展。抽象数据类型是与表示无关的数据类型，是一个数据模型及定义在该模型上的一组运算。对一个抽象数据类型进行定义时，必须给出它的名字及各运算的运算符名，即函数名，并且规定这些函数的参数性质。一旦定义了一个抽象数据类型及具体实现，程序设计中就可以像使用基本数据类型那样，十分方便地使用抽象数据类型。抽象数据类型的设计者根据这些描述给出操作的具体实现，抽象数据类型的使用者依据这些描述使用抽象数据类型。1.8 算法

4、的时间复杂度指的是什么？如何表示？【答】：算法执行时间的度量不是采用算法执行的绝对时间来计算的，因为一个算法在不同的机器上执行所花的时间不一样，在不同时刻也会由于计算机资源占用情况的不同，使得算法在同一台计算机上执行的时间也不一样，另外，算法执行的时间还与输入数据的状态有关，所以对于算法的时间复杂性，采用算法执行过程中其基本操作的执行次数，称为计算量来度量。算法中基本操作的执行次数般是与问题规模有关的，对于结点个数为n的数据处理问题，用T（n）表示算法基本操作的执行次数。为了评价算法的执行效率，通常采用大写O符号表示算法的时间复杂度，大 写0符号给出了函数f的一个上限。其它义如下：3t三五普通

5、高等教育国家级本科规划教材 高等学校精品资源共享课程定义：f (n)=0 (g (n)当且仅当存在正的常数c和no,使得对于所有的n n o,W f (n)n o),g是f的一个上限(不考虑常数因子c)。在为函数f提供一个上限函数g时，通常使用比较简单的函数形式。比较典型的形式是含有n的单个项(带一个常数系数)。表1-1列出了一些常用的g函数及其名称。对于表1-1中的对数函数l o g n,没有给出对数基，原因是对于任何大于1的常数a和b都 有l o g a n =l o g b n/l o g b a,所 以l o g,n和l o g b n都有一个相对的乘法系数1/l o g b a,其

6、中a是一个常量。表1-1常用的渐进函数函数名称1常数l o g n对数n线性n l o g nn 个 l o g n2n平方3n立方2指数n!阶乘1.9 算法的空间复杂度指的是什么？如何表示？【答】：算法的空间复杂度是指算法在执行过程中占用的额外的辅助空间的个数。可以将它表示为问题规模的函数，并通过大写0符号表示空间复杂度。1.1 0 对于下面的程序段，分析带下划线的语句的执行次数，并给出它们的时间复杂度T(n)。(1)i+；(2)f b r(i=0;i n;i+)i f(a i x)x=a i ;(3)f o r(i=0;i n;i+)f o r(j=Oy n;j+)p r i n t f(

7、d”,i+i);(4)f o r(i=l;i =n-l;i+)k=i；f o r d=i+l u a U+l )k=j;t=a k ;a k =a i ;a i =t;)(5)f o r(i=0;i n;i-H-)f o r(j=0;j n;j+)+x;s=s+x;【答】：(1)O (1)；(2)O (n)；(3)O(D 2)；(4)O (n z)；(5)O (m)4十二五普通高等教育国家级本科规划教材高等学校精品资源共享课程第2章线性表及其顺序存储2.1 选择题(1)表长为n 的顺序存储的线性表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均个数为(E),删除一

8、个元素所需移动元素的平均个数为(A)。A.(n-1)/2 B.n C.n+1 D.n-1E.nil F.(n+1)/2 G.(-2)/2(2)设 栈 5 和队列Q 的初始状态为空，元 素 e l、e2、e3、e4、e 5 和 e 6 依次通过栈S,一个元素出栈后即进入队列Q,若 6 个元素出队的序列为e2、e4、e3、e6、e 5 和 e l,则 栈 S的容量至少应该为(C)。A.6 B.4 C.3 D.2(3)设栈的输入序列为1、2、3，若输出序列的第一个元素为，则 第 i 个输出的元素为(B),A.不确定 B.n-i+C./D.n-i(4)在一个长度为n 的顺序表中删除第i 个元素(1=/

9、=)时，需向前移动(A)个元素。A.n-i B.n-i+1 C.n i 1 D.i(5)若长度为的线性表采用顺序存储结构存储，在 第 i 个位置上插入一个新元素的时间复杂度为(A)。A.。()B.0(1)C.。(吟 D.。(公)(6)表达式a*(b+c)-d 的后缀表达式是(B)。A.ahcd*+-B.ahc+*d-C.abc*+d-D.-+*abcd(7)队列是种特殊的线性表，其特殊性在于(C)。A.插入和删除在表的不同位置执行B.插入和删除在表的两端位置执行C.插入和删除分别在表的两端执行D.插入和删除都在表的某一端执行(8)栈是一种特殊的线性表，具 有(B)性质。A.先进先出 B.先进后

10、出 C.后进后出 D.顺序进出(9)顺序循环队列中(数组的大小为n),队头指示fiont指向队列的第1 个元素，队尾指 示 rear指向队列最后元素的后1 个位置，则循环队列中存放了 I 1 个元素，即循环队列满的条件为(B).A.(rear+l)%n=front-l B.(rear+l)%n=frontC.(rear)%n=front D.rear+l=front(1 0)顺序循环队列中(数组的大小为6),队头指示front和队尾指示rear的值分别为3和 0,当从队列中删除1 个元素，再插入2 个元素后，front和 rear的值分别为(D)。A.5 和 1 B.2 和 4 C.1 和 5

11、 D.4 和 22.2 什么是顺序表？什么是栈？什么是队列？5t 三五普通高等教育国家级本科规划教材 高等学校精品资源共享课程,*4.【春】：当线性表采用顺序存储结构时，即为顺序表。栈是一种特殊的线性表，它的特殊性表现在约定了在这种线性表中数据的插入与删除操作只能在这种线性表的同一端 进 行(即 栈 顶)，因此，栈具有先进后出、后进先出的特点。队列也是一种特殊的线性表，它的特殊性表现在约定了在这种线性表中数据的插入在表的端进行，数据的删除在表的另一端进行，因此队列具有先进先出，后进后出的特点。2.3 设计一个算法，求顺序表中值为x 的结点的个数。【答】：顺序表的存储结构定义如下(文件名seql

12、ist.h)：#includ e#d efine N 100typed ef int d atatype;typed ef struct d atatype d ataN;int length;seqlist;/*预定义最大的数据域空间*/产假设数据类型为整型*/产此处假设数据元素只包含一个整型的关键字域*/*线性表长度*/片预定义的顺序表类型*/算 法 countx(L,x)用于求顺序表L 中 值 为 x 的结点的个数。int countx(seqlist*L,d atatype x)int c=0;inti;for(i=0;ilength;i+)if(L-d atai=x)c+;retur

13、n c;2.4 设计一个算法，将一个顺序表倒置。即，如果顺序表各个结点值存储在一维 数 组 a 中，倒置的结果是使得数组a 中 的 a0等于原来的最后一个元素，a l 等于原来的倒数第2 个元素，a 的最后一个元素等于原来的第一个元素。【答】：顺序表的存储结构定义同题2.3,实现顺序表倒置的算法程序如K：void verge(seqlist*L)inti=0;j=L-length-l;while(id atai;L-d atai-H-=L-d ataj;L-d ataj-=t;)2.5 已知一个顺序表中的各结点值是从小到大有序的，设计一个算法，插入一个 值 为 x 的结点,使顺序表中的结点仍然

14、是从小到大有序。【答】：顺序表的定义同题2.3,实现本题要求的算法程序如下：6十二五普通高等教育国家级本科规划教材高等学校精品资源共享课程w -,void insertx(seqlist*L,d atatype x)intj;if(L-lengthlength-l;while(j=0&L-d atajx)L-d ata j+1=L-d ataj;J-；)L-d ataj+l=x;L-length+；)2.6 将下列中缀表达式转换为等价的后缀表达式。(1)5+6*7(2)(5-6)/7(3)5-6*7*8(4)5*7-8(5)5*(7-6)+8/9(6)7*(5-6*8)-9【答】：(7)5+6

15、*7(8)(5-6)/7(9)5-6*7*8(10)5*7-8(11)5*(7-6)+8/9(12)7*(5-6*8)-9后缀表达式：5 6 7*+后缀表达式：5 6-7/后缀表达式：5 6 7*8*-后缀表达式：5 7*8-后缀表达式：5 7 6-*8 9/+后缀表达式:7 5 68*-*%2.7 循环队列存储在一个数组中，数组大小为n,队首指针和队尾指针分别为fro n t和re a r,请写出求循环队列中当前结点个数的表达式。【答】：循环队列中当前结点个数的计算公式是：(n+rear-fh)nt)%n2.8 编 号 为1,2,3,4的四列火车通过一个栈式的列车调度站，可能得到的调度结果有

16、哪些？如果有n列火车通过调度站，请设计一个算法，输出所有可能的调度结果。【答】：方法一:算法思想：逐次输出所有可能，用回溯法。即：总体：对原始序列中的每一个元素，总是先入栈，后出栈1.入栈后的操作：a.该元素出栈；b.下一个元素入栈；2.出栈后的操作：a.(栈中其他元素)继续出栈；b.(原始序列中)下一个数入栈；注意：回溯法，关键在于回溯，即在某分支结点X：处 理X的一个子分支，再退回分支X,接着处理X的下个子分支,若所有X的子分支处理完，再退回上 层分支节点。所 谓“退回”，7十二五普通高等教育国家级本科规划教材 高等学校精品资源共享课程“实院上就是恢复。程序代码：(2_8_Lc)#incl

17、ud e#d efine MAX 26typed ef struct schar aMAX;int top;Stack;/*定义一些全局变量*/Stack S;/*定义全局性的栈*/chard MAX,seqMAX;/*d MAX用于存储原始入栈序歹lj,seqMAX用于存储输出序列*/int len;/*定义将通过栈的元素个数*/int count=0;/*用于统计输出序列的个数*/void initStack(Stack*S)/*初始化空栈*/S-top=-l;void push(Stack*S,char x)/*进栈*/if(S-top=MAX)return;S-top+;S-aS-to

18、p=x;char pop(Stack*S)/*出栈*/if(S-top=-l)printfinERROR,POP Empty Stack”)；return-1;)S-top-;return S-aS-top+l;)int isEmpty(Stack*S)/*判断栈是否为空*/if(S-top=-l)return 1;return 0;void outSeq(char*seq,int Icn)/*输出顶点序列*/int i;for(i=0;ilen;i+)printf(M%2c,seqi);printf(nnn);void sched uler(int pos,int seq_pos)8十三五普

19、通高等教育国家级本科规划教材高等学校精品资源共享课程po s:处理到原始数据中的第p o s个元素，seq_pos：若出栈，应放在当前输出数组的第seq_pos个位置*/int i=0;char t;/*对任何一个数，总是先进栈，再出栈。另外，这里不需要循环，类似于“查找数组中元素”用递归*/if(pos=len&isEmpty(&S)outSeq(seq,len);count+;int main()int i;printftunplease input the num be sched uled:)；scanf(u%dn,&len);/*ffl le n 存储待调度的火车数量*/fbr(i=

20、O;ilen;i+)d i=R+i;/*创建火车编号，如 a、b、c、等*/printf(nthe original seq is:);outSeq(d,len);initStack(&S);sched uler(0,0);printffn count=%5dM,count);return 0;方法二:解题思路：栈具有先进后出、后进先出的特点，因此，任何个调度结果应该是1,2,3,4 全排列中的一个元素。由于进栈的顺序是由小到大的，所以出栈序列应该满足以下条件：对于序列中的任何个数其后面所有比它小的数应该是倒序的，例 如 4321是个有效的出栈序9t三五普通高等教育国家级本科规划教材 高等学校

21、精品资源共享课程演 ，1423不是个有效的出栈结果(4后面比它小的两个数2,3不是倒序)。据此，本题可以通过算法产生n个数的全排列，然后将满足出栈规则的序列输出。产 生n个数的全排列有递归与非递归两种实现算法。产生全排列的递归算法：设R=n,n,rn是要进行排列的n个元素,Ri=R-ril 时,perm(R)由(n)perm(Ri),(r2)perm(R2),(n)perm(Rn)构成。依此递归定义，可设计产生perm(R)的递归算法如下：递归解法：(2_8_2.c)#includ eint cont=l;/*全局变量，用于记录所有可能的出栈序列个数*/void print(int str,i

22、nt n);/*求整数序列str口从k到n的全排列*/void perm(int str口,int k,int n)int i,temp;if(k=n-1)print(str,n);else for(i=k;in;i+)temp=strk;strk=stri;stri=temp;perm(str,k+1,n);/*递归调用*/temp=stri;stri=strk;strk=temp;)/*本函数判断整数序列str是否满足进出栈规则，若满足则输出*/void print(int str,int n)int ij,k,l,m,flag=l,b2;fbr(i=0;in;i+)/*对每个st巾 判断

23、其后比它小的数是否为降序序列*/m=0;fbr(j=i+l;jstrj)if(m=0)bm-H-=strj;else if(strjbO)flag=0;else bO=strj;设flag)/*满足出栈规则则输出str口中的序列*/10t三五普通高等教育国家级本科规划教材 高等学校精品资源共享课程.lim,printfif%2d:H,cont-H-);fbr(i=O;i4 Y j亨市选出比数字4 大，但又是它们中最小的那一个数字，比如数字5,与 数 字 4 交换。该数字也是从后向前考察过程中第一个比4 人的数字，5 与 4 交换后，得到 排 列 125643。在前面数字1,2,5 固定的情况下

24、，还应选择对应最小整数的那个排列，为此还需将后面那部分数字的排列颠倒，如将数字6,4,3 的排列顺序颠倒，得 到 排 列 125,3,4,6,这才是排列1,2,4,6,5,3 的下 个排列。按照以上想法可以编写非递归程序实现n 个数的全排列，对满足进出栈规则的排列则计数并输出。/*本程序输出1 2 n 个序列进栈出栈的序列*/#includ e int pl(int n)int a100;int flag=l,flag 1=0;FILE*rf;int i,j,k,x,count=0;rf=fbpen(nstack.txtM,uwn);for(i=l;i=n;i+)ai=i；while(flag

25、)flagl=l;for(i=l;i=n;i-H-)j=i+l；/*最大处理范围为9 9 个数*/pl.txt用于存放进出栈序列结果*/*初始序列*/*还剩余未输出的排列*/*判断木次排列是否符合进栈出栈序列*/while(jai)j-H-;/*找 ai后第一个比 ai小的元素 aj*/k=j+l；while(k=n)/*如 果 aj后还有比ai小 且 比 aj大的元素，则此排列无效*/if(ak aj)flagl=0;k+;if(flagl)for(i=l;il&aij&aiaj)i-;12t三五普通高等教育国家级本科规划教材 高等学校精品资源共享课程k=aj;/*交换两元素的值*/aj=a

26、；ai=k;k=j+l；/*对交换后后面的数据由小到大排序*/for(i=k+l;i=k&xaj)aj+l=aj；j-；)aj+l=x;fclose(rf);return count;/*返回排列总个数*/void main()int n,m=0;printffplease input n:);/*输入排列规模*/scanf(%d,&n);m=pl(n);printRnm=%d,m);/*输出满足进出栈的排列总个数*/程序运行时如果输入4,则输出的结果如下图所示。amll222223334e一p443422434114111tn 34243341431422p un.1223341133422

27、43该算法的时间复杂度也是0(n!)。结论：如 果n个数按编号由小到大的顺序进栈，进栈的过程中可以出栈，则所有可能的出栈序列的总数为:(2)！(+)nn13十二五普通高等教育国家级本科规划教材高等学校精品资源共享课程第 3 章线性表的链式存储3.1选择题(1)两个有序线性表分别具有n个元素与m个元素且n n e x t=NU L L B.p=NULL C.p-n e x t=h e a d D.p=h e a d(3)在带头结点的单链表中查找x应选择的程序体是(C )。A.n o d e *p=h e a d-n e x t;w h ile (p&p-in f b!=x)p=p-n e x t

28、;if (p-in f b=x)r e t u r n p e ls e r e t u r n N U L L;B.n o d e *p=h e a d;w h ile (p&p-in f b!=x)p=p-n e x t;r e t u r n p;C.n o d e *p=h e a d-n e x t;w h ile (p&p-in f b!=x)p=p-n e x t;r e t u r n p;D.n o d e *p=h e a d;w h ile (p-in f b!=x)p=p-n e x t;r e t u r n p;(4)线性表若采用链式存储结构时，要求内存中可用存储单

29、元的地址(D )。A.必须是连续的 B.部分地址必须是连续的C.一定是不连续的 D.连续不连续都可以(5)在一个具有个结点的有序单链表中插入一个新结点并保持单链表仍然有序的时间复杂度是(B )。A.。B.。()(6)用不带头结点的单链表存储队列时,尾结点，则在进行删除操作时(D )。A.仅修改队头指针C.队头、队尾指针都要修改C.。(2)D.O(lO g 2n)其队头指针指向队头结点，其队尾指针指向队B.仅修改队尾指针D.队头，队尾指针都可能要修改(7)若从键盘输入个元素，则建立一个有序单向链表的时间复杂度为(B )。A.。()B.。(2)C.0(/73)D.O(n x lo g 2)(8)下

30、面哪个术语与数据的存储结构无关(D )。A.顺序表 B.链表 C.散列表 D.队列(9)在一个单链表中，若删除p所指结点的后续结点，则执行(A)。A.p-n e x t=p-n e x t-n e x t;B.p=p-n e x t;p-n e x t=p-n e x t-n e x t;C.p-n e x t=p-n e x t;D.p =p-n e x t-n e x t;(1 0)在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行(B )。A.s-n e x t=p;p-n e x t=s;B.s-n e x t=p-n e x t;p-n e x t=s;C.s-

31、n e x t=p-n e x t;p=s;D.p-n e x t=s;s-n e x t=p;3.2设计一个算法，求一个单链表中的结点个数。【答】：单链表存储结构定义如下(相关文件：lin k lis t.h)#in c lu d e 14t三五普通高等教育国家级本科规划教材 高等学校精品资源共享课程/includ e typed ef struct nod e int d ata;struct nod e*next;linknod e;typed ef linknod e*linklist;/*尾插法创建带头结点的单链表*/linklist creatlinklist()linklist

32、head,r,s;int x;head=r=(linklist)malloc(sizeofi(linknod e);printfCn请输入组以0结束的整数序列:nH);scanf(%d,&x);while(x)s=(linklist)malloc(sizeoflinknod e);s-d ata=x;r-next=s;r=s;scanff%d”,&x);r-next=NULL;return head;/*输出带头结点的单链表*/void print(linklist head)linklist p;p=head-next;printffList is:nM);while(p)printf(,%

33、5d,p-d ata);p=p-next;printf(,n);基于上述结构定义，求单链表中的结点个数的算法程序如下：int count(linklist head)int c=0;linklist p=head;while(p)15t三五普通高等教育国家级本科规划教材 高等学校精品资源共享课程C+；p=p-next;return c;)3.3 设计一个算法，求个带头结点单链表中的结点个数。【答】：带头结点的单链表的存储结构定义同题3.2,实现木题功能的算法程序如下(3_3.c)#includ e linklist.h*int count(linklist head)int c=0;linkl

34、ist p=head-next;while(p)c+；p=p-next;return c;main()/*测试函数*/linklist head;head=creatlinklist();print(head);printf(MnLength of head is:%dn,count(head);getch();当输入5个数据时，产生的输出结果如下图所示：情输入一组以。结束的整数序列:tL0 20 30 40 50 0List is：10 20 30 40 50DLength of head is：53.4 设计一个算法，在一个单链表中值为y的结点前面插入一个值为x的结点。即使值为x的新结点成

35、为值为y的结点的前驱结点。【答】：includ e linklist.hvoid insert(linklist head,int y,int x)/*在值为y的结点前插入一个值为x的结点*/linklist pre,p,s;pre=head;16十二五普通高等教育国家级本科规划教材p=head-next;while(p&p-d ata!=y)pre=p;高等学校精品资源共享课程p=p-next;)if(p)/*找到了值为y 的结点*/s=(linklist)malloc(sizeof(linknod e);s-d ata=x;s-next=p;pre-next=s;void main()li

36、nklist head;int y,x;head=creatlinklist();print(head);/*测试程序*/*创建单链表*/*输出单链表*/printffW 请 输 入y与x的值:n”);scanff%d%d”,&y,&x);insert(head,y,x);print(head);程序的一种运行结果如卜.图所示:请输入一组以0结束的整数序列：3 1 9 6 4 5 8 0L ist i s：3 1 9 6 4 5 8请输入y与x的值：6 7L ist i s：319764583.5 设计一个算法，判断一个单链表中各个结点值是否有序。【答】：#includ e ulinklist

37、.huint issorted(linklist head,char c)/*当 参 数 c=，a，时判断链表是否为升序，当参数c=7T是判断链表是否为降序*/int flag=l;linklist p=head-next;switch(c)17十二五普通高等教育国家级本科规划教材高等学校精品资源共享课程case R:/*判断带头结点的单链表head是否为升序*/while(p&p-next&flag)if(p-d atanext-d ata)p=p-next;else flag=O;break;cased:/*判断带头结点的单链表head是否为降序*/while(p&p-next&flag)

38、if(p-d ata=p-next-d ata)p=p-next;else flag=O;break;return flag;)int main()/*测试程序*/linklist head;head=creatlinklist();print(head);if(issorted(head,a)prin氓”单链表 head 是升序排列的！nn);elseif(issorted(head,d)printf(单链表 head 是降序排列的！nn);else print/单链表head是无序的！n0);程序运行时的三种输出结果如下图所示：请输入一组以0结束的整数序列：10 20 30 40 50 0

39、L i s t x s：10 20 30 40 50单链表head是升序排列的！情输入一组以。结束的整数序列:50 40 30 20 10 0List is：50 40 30 20 10惮链表head是降序排列的！请输入一组以。结束的整数序列：40 30 90 20 10 0List is：40 30 90 20 10单链表head是无序的！3.6设计一个算法，利用单链表原来的结点空间将一个单链表就地转置。【答】：#includ e linklist.hvoid verge(Iinklist head)18t 三五普通高等教育国家级本科规划教材 高等学校精品资源共享课程/.g*_/,*V*本函

40、数的功能是就地倒置带头结点的单链表*/linklist p,q;p=head-next;head-next=NULL;while(p)/*每次从原表取一个结点插入到新表的最前面*/q=p;p=p-next;q-next=head-next;head-next=q;int main()linklist head;head=creatlinklist();print(head);verge(head);print(head);/*测试函数*/*创建单链表*/*输出原单链表*/*就地倒置单链表*/*输出倒置后的单链表*/3.7 设计一个算法,将一个结点值自然数的单链表拆分为两个单链表，原表中保留值为

41、偶数的结点，而值为奇数的结点按它们在原表中的相对次序组成一个新的单链表。【答】：#includ e linklist.h1linklist sprit(linklist head)/*将带头结点的单链表head 中的奇数值结点删除生成新的单链表并返回*/linklist L,pre,p,r;L=r=(linklist)malloc(sizeof(linknod e);r-next=NULL;pre=head;p=hcad-next;while(p)if(pd ata%2=l)/*删除奇数值结点*/pre-next=p-next;r-next=p;r=p;p=pre-next;else/*保留偶

42、数值结点*/pre=p;p=p-next;19十二五普通高等教育国家级本科规划教材高等学校精品资源共享课程r-next=NULL;return L;/*置链表结束标记*/int main()linklist head,L；head=creatlinklist();print(head);L=sprit(head);/*测试函数*/*创建单链表*/*输出原单链表*/*分裂单链表head*/printf(n 原单链表为:n);print(head);/*输出倒置后的单链表*/printf(n分裂所得奇数单链表为:n);print(L);本程序的一组测试情况如卜图所示。请输入一组以。结束的整数序列，

43、1 2 3 4 5 6 7 8 AList is：12345678承单链表为：List is=2 4 6 8分裂所得奇数单链表力：List is:13 5 73.8 设计个算法，对一个有序的单链表，删除所有值大于x 而不大于y 的结点。【答】：#includ e ulinklist.hvoid d eleted ata(linklist head,d atatype x,d atatype y)/*删除带头结点单链表中所有结点值大于x 而不大于y 的结点*/linklist pre=head,p,q;p=head-next;/*初始化*/while(p&p-d atanext;)while(p

44、&p-d atanext;q=pre-next;/*删除大 于 x 而 小 于 y 的结点*/pre-next=p;20t三五普通高等教育国家级本科规划教材 高等学校精品资源共享课程pre=q-next;while(pre!=p)/*释放被删除结点所占用的空间*/free(q);q=pre;pre=pre-next;void main()/*测试函数*/linklist head,L；d atatype x,y;head=creatl ink 1 ist();/*创建单链表*/print(head);/*输出原单链表*/printf(-n请输入要删除的数据区间:n“)；scanf(%d%du,

45、&x,&y);d eleted ata(head,x,y);print(head);/*输出删除后的单链表*/3.9设计一个算法，在双链表中值为y的结点前面插入一个 值 为x的新结点。即使 值 为x的新结点成为值为y的结点的前驱结点。【答】：首先定义双链表的数据结构，相关文件d link.h,内容如下：typed ef int d atatype;/*预定义的数据类型*/typed ef struct d link_nod e/*双链表结点定义*/d atatype d ata;struct d link nod e*llink,*rlink;d nod e;typed ef d nod e*

46、d linklist;/*双链表结点指针类型定义*/*尾插法创建带头结点的双链表*/d linklist creatd linklist(void)d linklist head,r,s;d atatype x;head=r=(d linklist)malloc(sizeofid nod e);/*建立双链表的头结点*/head-Hink=head-rlink=NULL;printf(!n请输入双链表的内容：(整数序列，以0结 束)n“)；scanfif%dM,&x);while(x)/*输入结点值信息，以0结束*/s=(d linklist)malloc(sizeof(d nod e);s-

47、d ata=x;s-rlink=r-rlink;/*将新结点s插入到双链表链尾*/21t 三五普通高等教育国家级本科规划教材 高等学校精品资源共享课程/.llink=r;r-rlink=s;r=s;scanf(”d”,&x);)return head;/*输出双链表的内容*/void print(d linklist head)d linklist p;p=head-rlink;printffW 双链表的内容是：nn);while(p)printf(,%5d,p-d ata);p=p-rlink;)本题的求解程序如下：#includ e#includ e nd link.hvoid inser

48、txaty(d linklist head,d atatype y,d atatype x)d linklist s,p;/*首先在双链表中找y 所在的结点，然 后 在 y 前面插入新结点*/p=head-rlink;while(p&p-d ata!=y)p=p-rlink;if(!p)printf(n n 双链表中不存在值为y 的结点，无法插入新结点!n“)；else/*插入值为x 的新结点*/s=(d linklist)malloc(sizeof(d nod e);s-d ata=x;s-rlink=p;s-llink=p-llink;p-llink-rlink=s;p-llink=s;)

49、void main()/*测试函数*/d linklist head;d atatype x,y;22t 三五普通高等教育国家级本科规划教材 高等学校精品资源共享课程head=creatd 1 i n k I i st();print(head);printf(H n 请输入要输入的位置结点值y:nn);scanfC%dn,&y);printf(n请输入要输入的结点值x:n);scanf(%d,&x);insertxaty(head,y,x);/*在 值 为 y 的结点前插入值为x 的新结点*/print(head);/*输出新的双链表*/getch();本程序的一组测试情况如下图所示。请输入

50、双健表的内容：(整数序列，以。结束)1 29 30 40 5 60(J双箍表的内容是10 20 39 40 50 60请瑜入要输入的位置结点值歹请输入要输入的结点值*35双链表的内容是：10 20 3。35 40 5。603.10设计一个算法，从右向左打印一个双链表中各个结点的值。【答】：本题的双链表定义同题3.9,实现从右向左打印双链表的各个结点的值可以用递归程序实现如下：/includ e includ e“d link.h”void vprint(d linklist head)/*递归方法从右向左打印双链表的值*/if(head-rlink)vprint(head-rlink);pri