数据结构习题集答案_C语言版(严蔚敏 吴伟民)

16void Descend(int &x, int &y, int &z){int t;if(x<y) {t=x;x=y;y=t;}if(x<z) {t=x;x=z;z=t;}if(y<z) {t=y;y=z;z=t;}}17Status Fibonacci(int k, int m, int &f)/* 求k阶斐波那契序列的第m项的值f */{int i,j,sum,temp[20];if(k<2||m<0) return ERROR;if(m<k-1) f=0;else if(m==k-1) f=1;else{for(i=0;i<=k-2;i++)temp[i]=0;temp[k-1]=1;for(i=k;i<=m;i++){sum=0;for(j=i-k;j<i;j++)sum+=temp[j];temp[i]=sum;}f=temp[m];}return OK;}// Fibonacci18void Scores(ResultType *result, ScoreType *score)/* 求各校的男、女总分和团体总分, 并依次存入数组score */ /* 假设比赛结果已经储存在result[ ]数组中, *//* 并以特殊记录{"", male, ' ', "", 0 }（域scorce=0）*//* 表示结束*/ {int i=0;while(result[i].sport!=NULL){switch(result[i].schoolname){case 'A':score[0].totalscore+=result[i].score;if(result[i].gender==male) score[0].malescore+=result[i].score;else score[0].femalescore+=result[i].score;break;case 'B':score[1].totalscore+=result[i].score;if(result[i].gender==male) score[1].malescore+=result[i].score;else score[1].femalescore+=result[i].score;break;case 'C':score[2].totalscore+=result[i].score;if(result[i].gender==male) score[2].malescore+=result[i].score;else score[2].femalescore+=result[i].score;break;case 'D':score[3].totalscore+=result[i].score;if(result[i].gender==male) score[3].malescore+=result[i].score;else score[3].femalescore+=result[i].score;break;case 'E':score[4].totalscore+=result[i].score;if(result[i].gender==male) score[4].malescore+=result[i].score;else score[4].femalescore+=result[i].score;break;}i++;}for(s='A';s<='E';s++){printf("School %c:\n",s);printf("Total score of male:%d\n",score[i].malescore);printf("Total score of female:%d\n",score[i].femalescore);printf("Total score of all:%d\n\n",score[i].totalscore);}}19Status Series(int ARRSIZE, int a[])/* 求i!*2^i序列的值并依次存入长度为ARRSIZE的数组a； */ /* 若所有值均不超过MAXINT，则返回OK，否则返回OVERFLOW */ {int last,i;last=1;for (i=1;i<=ARRSIZE;i++){a[i-1]=last*2*i;if (a[i-1]>MAXINT)return OVERFLOW;last=a[i-1];}return OK;}20float Polynomial(int n, int a[], float x)/* 求一元多项式的值P(x)。

《数据结构-C语⾔版》（严蔚敏,吴伟民版）课本源码+习题集解析使⽤说明《数据结构-C语⾔版》（严蔚敏,吴伟民版）课本源码+习题集解析使⽤说明先附上⽂档归类⽬录：课本源码合辑链接☛☛☛习题集全解析链接☛☛☛★教材及习题源码下载★链接☛☛☛（GitHub仓库）欢迎Star项⽬，如有疑问，请在Issues反馈。

博主有话说：01.⾃学编程，难免思路阻塞，故我在本博客陆续更新了严蔚敏,吴伟民版《数据结构-C语⾔版》各章节的课本源码和配套习题集答案解析，⽬的是为了整理数据结构中的知识点，并与⽹友交流意见，集思⼴益，共同进步。

（⽬前已更新完毕，细节待完善）★注★左侧随笔分类下⽤两个栏⽬：<课本源码>、<习题解析>来存放本主题⽂档。

<课本源码>⽬录下实现了三种数据结构源码：⼀：课本中重点描述过的数据结构与算法；⼆：课本中提到，但没有详细描述的数据结构；三：课本中未提到，但在习题集中涉及到的数据结构。

<习题解析>⽬录下存放了配套习题集中每章的习题解答，但对于算法设计题，要注意其相对路径，因为涉及到了别的⽂档的引⽤。

各⽂档的组织⽅式参见附录⼆中的图⽰，有疑问联系博主。

02.本源码与解析涵盖了《数据结构》课本和习题集两部分，课本和习题集分别以下图书籍为参照（我有左边的纸质版和右边的电⼦版，貌似内容没区别）：03.所有源码实现均使⽤C语⾔，遵循C99标准，使⽤C-Free 5（C-Free置gcc编译器，编译时，需要在菜单栏，定位到构建-->构建选项-->类别-->C Language，勾选第三个："ISO C99 plus GNU extensions [-std=gnu99]"，即编译选项⽤-std=gnu99，⽽不是-std=c89或者-std=c99）测试通过（不要在CFree⾥创建⼯程，如果确实想在⼯程⾥运⾏，那⽂件互相引⽤的⽅式需要改写）。

数据结构（C语言版）严蔚敏第1章绪论1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。

解：数据是对客观事物的符号表示。

在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。

数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

数据对象是性质相同的数据元素的集合，是数据的一个子集。

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。

存储结构是数据结构在计算机中的表示。

数据类型是一个值的集合和定义在这个值集上的一组操作的总称。

抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。

是对一般数据类型的扩展。

1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。

解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。

一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。

抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。

在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。

1.3 设有数据结构(D,R)，其中{}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r =试按图论中图的画法惯例画出其逻辑结构图。

解：1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。

解：ADT Complex{数据对象：D={r,i|r,i 为实数}数据关系：R={<r,i>}基本操作： InitComplex(&C,re,im)操作结果：构造一个复数C ，其实部和虚部分别为re和imDestroyCmoplex(&C)操作结果：销毁复数CGet(C,k,&e)操作结果：用e返回复数C的第k元的值Put(&C,k,e)操作结果：改变复数C的第k元的值为eIsAscending(C)操作结果：如果复数C的两个元素按升序排列，则返回1，否则返回0IsDescending(C)操作结果：如果复数C的两个元素按降序排列，则返回1，否则返回0Max(C,&e)操作结果：用e返回复数C的两个元素中值较大的一个Min(C,&e)操作结果：用e返回复数C的两个元素中值较小的一个}ADT ComplexADT RationalNumber{数据对象：D={s,m|s,m为自然数，且m不为0}数据关系：R={<s,m>}基本操作：InitRationalNumber(&R,s,m)操作结果：构造一个有理数R，其分子和分母分别为s和mDestroyRationalNumber(&R)操作结果：销毁有理数RGet(R,k,&e)操作结果：用e返回有理数R的第k元的值Put(&R,k,e)操作结果：改变有理数R的第k元的值为eIsAscending(R)操作结果：若有理数R的两个元素按升序排列，则返回1，否则返回0IsDescending(R)操作结果：若有理数R的两个元素按降序排列，则返回1，否则返回0Max(R,&e)操作结果：用e返回有理数R的两个元素中值较大的一个Min(R,&e)操作结果：用e返回有理数R的两个元素中值较小的一个}ADT RationalNumber1.5 试画出与下列程序段等价的框图。

16void Descend(int &x, int &y, int &z){int t;if(x<y) {t=x;x=y;y=t;}if(x<z) {t=x;x=z;z=t;}if(y<z) {t=y;y=z;z=t;}}17Status Fibonacci(int k, int m, int &f)/* 求k阶斐波那契序列的第m项的值f */{int i,j,sum,temp[20];if(k<2||m<0) return ERROR;if(m<k-1) f=0;else if(m==k-1) f=1;else{for(i=0;i<=k-2;i++)temp[i]=0;temp[k-1]=1;for(i=k;i<=m;i++){sum=0;for(j=i-k;j<i;j++)sum+=temp[j];temp[i]=sum;}f=temp[m];}return OK;}// Fibonacci18void Scores(ResultType *result, ScoreType *score)/* 求各校的男、女总分和团体总分, 并依次存入数组score */ /* 假设比赛结果已经储存在result[ ]数组中, *//* 并以特殊记录{"", male, ' ', "", 0 }（域scorce=0）*//* 表示结束*/ {int i=0;while(result[i].sport!=NULL){switch(result[i].schoolname){case 'A':score[0].totalscore+=result[i].score;if(result[i].gender==male) score[0].malescore+=result[i].score;else score[0].femalescore+=result[i].score;break;case 'B':score[1].totalscore+=result[i].score;if(result[i].gender==male) score[1].malescore+=result[i].score;else score[1].femalescore+=result[i].score;break;case 'C':score[2].totalscore+=result[i].score;if(result[i].gender==male) score[2].malescore+=result[i].score;else score[2].femalescore+=result[i].score;break;case 'D':score[3].totalscore+=result[i].score;if(result[i].gender==male) score[3].malescore+=result[i].score;else score[3].femalescore+=result[i].score;break;case 'E':score[4].totalscore+=result[i].score;if(result[i].gender==male) score[4].malescore+=result[i].score;else score[4].femalescore+=result[i].score;break;}i++;}for(s='A';s<='E';s++){printf("School %c:\n",s);printf("Total score of male:%d\n",score[i].malescore);printf("Total score of female:%d\n",score[i].femalescore);printf("Total score of all:%d\n\n",score[i].totalscore);}}19Status Series(int ARRSIZE, int a[])/* 求i!*2^i序列的值并依次存入长度为ARRSIZE的数组a； */ /* 若所有值均不超过MAXINT，则返回OK，否则返回OVERFLOW */ {int last,i;last=1;for (i=1;i<=ARRSIZE;i++){a[i-1]=last*2*i;if (a[i-1]>MAXINT)return OVERFLOW;last=a[i-1];}return OK;}20float Polynomial(int n, int a[], float x)/* 求一元多项式的值P(x)。

吉首大学题库一、一、单选题（每题 2 分，共20分）1. 1.对一个算法的评价，不包括如下（）方面的内容。

A．健壮性和可读性B．并行性C．正确性D．时空复杂度2. 2.在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行( )。

A. p->next=HL->next; HL->next=p;B. p->next=HL; HL=p;C. p->next=HL; p=HL;D. HL=p; p->next=HL;3. 3.对线性表，在下列哪种情况下应当采用链表表示？( )A.经常需要随机地存取元素B.经常需要进行插入和删除操作C.表中元素需要占据一片连续的存储空间D.表中元素的个数不变4. 4.一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是( )A. 2 3 1B. 3 2 1C. 3 1 2D. 1 2 35. 5.AOV网是一种（）。

A．有向图B．无向图C．无向无环图D．有向无环图6. 6.采用开放定址法处理散列表的冲突时，其平均查找长度（）。

A．低于链接法处理冲突 B. 高于链接法处理冲突C．与链接法处理冲突相同D．高于二分查找7.7.若需要利用形参直接访问实参时，应将形参变量说明为（）参数。

A．值B．函数C．指针D．引用8.8.在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（）。

A．行号B．列号C．元素值D．非零元素个数9.9.快速排序在最坏情况下的时间复杂度为（）。

A．O(log2n) B．O(nlog2n) C．0(n) D．0(n2)10.10.从二叉搜索树中查找一个元素时，其时间复杂度大致为( )。

A. O(n)B. O(1)C. O(log2n)D. O(n2)二、二、运算题（每题 6 分，共24分）1. 1.数据结构是指数据及其相互之间的______________。

当结点之间存在M对N（M：N）的联系时，称这种结构为_____________________。

第1章绪论1、1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型与抽象数据类型。

解：数据就是对客观事物得符号表示。

在计算机科学中就是指所有能输入到计算机中并被计算机程序处理得符号得总称。

数据元素就是数据得基本单位，在计算机程序中通常作为一个整体进行考虑与处理。

数据对象就是性质相同得数据元素得集合，就是数据得一个子集。

数据结构就是相互之间存在一种或多种特定关系得数据元素得集合。

存储结构就是数据结构在计算机中得表示。

数据类型就是一个值得集合与定义在这个值集上得一组操作得总称。

抽象数据类型就是指一个数学模型以及定义在该模型上得一组操作。

就是对一般数据类型得扩展。

1、2 试描述数据结构与抽象数据类型得概念与程序设计语言中数据类型概念得区别。

解：抽象数据类型包含一般数据类型得概念，但含义比一般数据类型更广、更抽象。

一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。

抽象数据类型通常由编程者定义，包括定义它所使用得数据与在这些数据上所进行得操作。

在定义抽象数据类型中得数据部分与操作部分时，要求只定义到数据得逻辑结构与操作说明，不考虑数据得存储结构与操作得具体实现，这样抽象层次更高，更能为其她用户提供良好得使用接口。

1、3 设有数据结构(D,R)，其中{}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r =试按图论中图得画法惯例画出其逻辑结构图。

解：1、4 试仿照三元组得抽象数据类型分别写出抽象数据类型复数与有理数得定义（有理数就是其分子、分母均为自然数且分母不为零得分数）。

解：ADT Complex{数据对象：D={r,i|r,i 为实数}数据关系：R={<r,i>}基本操作：InitComplex(&C,re,im)操作结果：构造一个复数C ，其实部与虚部分别为re 与imDestroyCmoplex(&C)操作结果：销毁复数CGet(C,k,&e)操作结果：用e 返回复数C 得第k 元得值Put(&C,k,e)操作结果：改变复数C 得第k 元得值为eIsAscending(C)操作结果：如果复数C 得两个元素按升序排列，则返回1，否则返回0IsDescending(C)操作结果：如果复数C 得两个元素按降序排列，则返回1，否则返回0Max(C,&e)操作结果：用e 返回复数C 得两个元素中值较大得一个 Min(C,&e)操作结果：用e 返回复数C 得两个元素中值较小得一个}ADT ComplexADT RationalNumber{数据对象：D={s,m|s,m为自然数，且m不为0}数据关系：R={<s,m>}基本操作：InitRationalNumber(&R,s,m)操作结果：构造一个有理数R，其分子与分母分别为s与m DestroyRationalNumber(&R)操作结果：销毁有理数RGet(R,k,&e)操作结果：用e返回有理数R得第k元得值Put(&R,k,e)操作结果：改变有理数R得第k元得值为eIsAscending(R)操作结果：若有理数R得两个元素按升序排列，则返回1，否则返回0IsDescending(R)操作结果：若有理数R得两个元素按降序排列，则返回1，否则返回0Max(R,&e)操作结果：用e返回有理数R得两个元素中值较大得一个Min(R,&e)操作结果：用e返回有理数R得两个元素中值较小得一个}ADT RationalNumber1、5 试画出与下列程序段等价得框图。

第1章绪论1.1简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。

解：数据是对客观事物的符号表示。

在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。

数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

数据对象是性质相同的数据元素的集合，是数据的一个子集。

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。

存储结构是数据结构在计算机中的表示。

数据类型是一个值的集合和定义在这个值集上的一组操作的总称。

抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。

是对一般数据类型的扩展。

1.2试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。

解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。

一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。

抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。

在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。

1.3设有数据结构(D,R)，其中{}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r =试按图论中图的画法惯例画出其逻辑结构图。

解：1.4试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。

解：ADTComplex{数据对象：D={r,i|r,i 为实数}数据关系：R={<r,i>}基本操作：InitComplex(&C,re,im)操作结果：构造一个复数C ，其实部和虚部分别为re 和imDestroyCmoplex(&C)操作结果：销毁复数CGet(C,k,&e)操作结果：用e 返回复数C 的第k 元的值Put(&C,k,e)操作结果：改变复数C 的第k 元的值为eIsAscending(C)操作结果：如果复数C的两个元素按升序排列，则返回1，否则返回0IsDescending(C)操作结果：如果复数C的两个元素按降序排列，则返回1，否则返回0Max(C,&e)操作结果：用e返回复数C的两个元素中值较大的一个Min(C,&e)操作结果：用e返回复数C的两个元素中值较小的一个}ADTComplexADTRationalNumber{数据对象：D={s,m|s,m为自然数，且m不为0}数据关系：R={<s,m>}基本操作：InitRationalNumber(&R,s,m)操作结果：构造一个有理数R，其分子和分母分别为s和m DestroyRationalNumber(&R)操作结果：销毁有理数RGet(R,k,&e)操作结果：用e返回有理数R的第k元的值Put(&R,k,e)操作结果：改变有理数R的第k元的值为eIsAscending(R)操作结果：若有理数R的两个元素按升序排列，则返回1，否则返回0IsDescending(R)操作结果：若有理数R的两个元素按降序排列，则返回1，否则返回0Max(R,&e)操作结果：用e返回有理数R的两个元素中值较大的一个Min(R,&e)操作结果：用e返回有理数R的两个元素中值较小的一个}ADTRationalNumber1.5试画出与下列程序段等价的框图。

数据结构c语言版严蔚敏课后习题答案数据结构是计算机科学中的一个重要领域，它涉及到数据的组织、管理和存储方式，以便可以高效地访问和修改数据。

C语言作为一种广泛使用的编程语言，提供了丰富的数据结构实现方法。

严蔚敏教授编写的《数据结构（C语言版）》是许多计算机专业学生的必读教材。

以下是对该书课后习题的一些参考答案，供学习者参考。

第一章：绪论1. 数据结构的定义：数据结构是计算机中存储、组织数据的方式，它不仅包括数据元素的类型和关系，还包括数据操作的函数。

2. 数据结构的重要性：数据结构对于提高程序的效率至关重要。

合理的数据结构可以减少算法的时间复杂度和空间复杂度。

第二章：线性表1. 线性表的定义：线性表是由n个元素组成的有限序列，其中n称为线性表的长度。

2. 线性表的顺序存储结构：使用数组来存储线性表的元素，元素的存储关系是连续的。

3. 线性表的链式存储结构：使用链表来存储线性表的元素，每个元素包含数据部分和指向下一个元素的指针。

第三章：栈和队列1. 栈的定义：栈是一种特殊的线性表，只能在一端（栈顶）进行插入和删除操作。

2. 队列的定义：队列是一种特殊的线性表，允许在一端（队尾）进行插入操作，在另一端（队首）进行删除操作。

第四章：串1. 串的定义：串是由零个或多个字符组成的有限序列。

2. 串的存储结构：串可以采用顺序存储结构或链式存储结构。

第五章：数组和广义表1. 数组的定义：数组是由具有相同类型的多个元素组成的集合，这些元素按照索引顺序排列。

2. 广义表的定义：广义表是线性表的推广，其中的元素可以是数据也可以是子表。

第六章：树和二叉树1. 树的定义：树是由节点组成的，其中有一个特定的节点称为根，其余每个节点有且仅有一个父节点。

2. 二叉树的定义：二叉树是每个节点最多有两个子节点的树。

第七章：图1. 图的定义：图是由顶点和边组成的数据结构，可以表示复杂的关系。

2. 图的存储结构：图可以用邻接矩阵或邻接表来存储。

数据结构(C语言版)严蔚敏课后习题答案数据结构（C语言版）严蔚敏课后习题答案一、线性表1. 顺序表顺序表是一种存储结构，它将元素顺序存放在一块连续的存储区域中。

C语言中常用数组来实现顺序表。

以下是一些常见题目的解答：题目1：已知顺序表中存储了n个整数，请编写一个算法，将这个顺序表中的所有负数挑选出来，并将它们按照原有顺序存放在新的顺序表中。

解答：```#include <stdio.h>#define MAX_SIZE 100int main() {int A[MAX_SIZE], neg[MAX_SIZE];int n, i, j = 0;printf("Enter the number of elements: ");scanf("%d", &n);printf("Enter the elements: ");for (i = 0; i < n; i++) {scanf("%d", &A[i]);if (A[i] < 0) {neg[j] = A[i];j++;}}printf("Negative numbers: ");for (i = 0; i < j; i++) {printf("%d ", neg[i]);}return 0;}```题目2：假设顺序表A和B中的元素递增有序排列，编写一个算法合并这两个顺序表，并使合并后的顺序表仍然递增有序。

解答：```#include <stdio.h>#define MAX_SIZE 100int main() {int A[MAX_SIZE], B[MAX_SIZE], C[MAX_SIZE * 2]; int m, n, i, j, k;printf("Enter the number of elements in the first list: "); scanf("%d", &m);printf("Enter the elements in increasing order: ");for (i = 0; i < m; i++) {scanf("%d", &A[i]);C[i] = A[i];}printf("Enter the number of elements in the second list: "); scanf("%d", &n);printf("Enter the elements in increasing order: ");for (i = 0; i < n; i++) {scanf("%d", &B[i]);C[m + i] = B[i];}// Merge A and B into Ci = j = k = 0;while (i < m && j < n) { if (A[i] < B[j]) {C[k] = A[i];i++;} else {C[k] = B[j];j++;}k++;}while (i < m) {C[k] = A[i];i++;k++;}while (j < n) {C[k] = B[j];j++;k++;}printf("Merged list in increasing order: ");for (i = 0; i < m + n; i++) {printf("%d ", C[i]);}return 0;}```2. 链表链表是一种动态的数据结构，它通过结点之间的指针联系起来。

数据结构习题集答案(C语言版严蔚敏)第2章线性表2.1 描述以下三个概念的区别：头指针，头结点，首元结点（第一个元素结点）。

解：头指针是指向链表中第一个结点的指针。

首元结点是指链表中存储第一个数据元素的结点。

头结点是在首元结点之前附设的一个结点，该结点不存储数据元素，其指针域指向首元结点，其作用主要是为了方便对链表的操作。

它可以对空表、非空表以及首元结点的操作进行统一处理。

2.2 填空题。

解：(1) 在顺序表中插入或删除一个元素，需要平均移动表中一半元素，具体移动的元素个数与元素在表中的位置有关。

(2) 顺序表中逻辑上相邻的元素的物理位置必定紧邻。

单链表中逻辑上相邻的元素的物理位置不一定紧邻。

(3) 在单链表中，除了首元结点外，任一结点的存储位置由其前驱结点的链域的值指示。

(4) 在单链表中设置头结点的作用是插入和删除首元结点时不用进行特殊处理。

2.3 在什么情况下用顺序表比链表好？解：当线性表的数据元素在物理位置上是连续存储的时候，用顺序表比用链表好，其特点是可以进行随机存取。

2.4 对以下单链表分别执行下列各程序段，并画出结果示意图。

解：2.5 画出执行下列各行语句后各指针及链表的示意图。

L=(LinkList)malloc(sizeof(LNode)); P=L;for(i=1;i<=4;i++){P->next=(LinkList)malloc(sizeof(LNode));P=P->next; P->data=i*2-1;}P->next=NULL;for(i=4;i>=1;i--) Ins_LinkList(L,i+1,i*2);for(i=1;i<=3;i++) Del_LinkList(L,i);解：2.6 已知L是无表头结点的单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。

a. 在P结点后插入S结点的语句序列是__________________。

第1章绪论习题1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。

2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。

3．简述逻辑结构的四种基本关系并画出它们的关系图。

4．存储结构由哪两种基本的存储方法实现？5．选择题（1）在数据结构中，从逻辑上可以把数据结构分成（）。

A．动态结构和静态结构B．紧凑结构和非紧凑结构C．线性结构和非线性结构D．内部结构和外部结构（2）与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）。

A．存储结构B．存储实现C．逻辑结构D．运算实现（3）通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（）。

A．数据具有同一特点B．不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致C．每个数据元素都一样D．数据元素所包含的数据项的个数要相等（4）以下说法正确的是（）。

A．数据元素是数据的最小单位B．数据项是数据的基本单位C．数据结构是带有结构的各数据项的集合D．一些表面上很不相同的数据可以有相同的逻辑结构（5）以下与数据的存储结构无关的术语是（）。

A．顺序队列 B. 链表 C.有序表 D. 链栈（6）以下数据结构中，（）是非线性数据结构A．树B．字符串C．队D．栈6．试分析下面各程序段的时间复杂度。

（1）x=90; y=100;while(y>0)if(x>100){x=x-10;y--;}else x++;（2）for (i=0; i<n; i++)for (j=0; j<m; j++)a[i][j]=0;（3）s=0;for i=0; i<n; i++)for(j=0; j<n; j++)s+=B[i][j];sum=s;（4）i=1;while(i<=n)i=i*3;（5）x=0;for(i=1; i<n; i++)for (j=1; j<=n-i; j++)x++;（6）x=n; //n>1y=0;while(x≥(y+1)* (y+1))y++;（1）O（1）（2）O（m*n）（3）O（n2）（4）O（log3n）（5）因为x++共执行了n-1+n-2+……＋1= n(n-1)/2，所以执行时间为O（n2）（6）O(n)第2章线性表1．选择题（1）一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（）。

数据结构c语言版严蔚敏课后习题答案数据结构是计算机科学中非常重要的一门学科，它研究的是数据的组织、存储和管理方式。

而C语言作为一种广泛应用于系统编程和嵌入式开发的高级编程语言，与数据结构的学习息息相关。

本文将针对《数据结构（C语言版）》严蔚敏教材的课后习题提供一些答案，希望能够帮助读者更好地理解和掌握数据结构。

第一章：绪论在第一章中，主要介绍了数据结构的基本概念和基本术语。

课后习题主要是一些概念性的问题，例如数据结构与算法的关系、数据的逻辑结构和物理结构等。

这些问题的答案可以通过仔细阅读教材中的相关内容来得到。

第二章：线性表线性表是数据结构中最基本、最常用的一种结构。

课后习题主要涉及线性表的基本操作，如插入、删除、查找等。

这些问题的答案可以通过编写相应的C语言代码来实现。

第三章：栈和队列栈和队列是线性表的特殊形式，具有后进先出（LIFO）和先进先出（FIFO）的特点。

课后习题主要涉及栈和队列的基本操作，如进栈、出栈、入队、出队等。

这些问题的答案同样可以通过编写相应的C语言代码来实现。

第四章：串串是由零个或多个字符组成的有限序列，是一种特殊的线性表。

课后习题主要涉及串的模式匹配、串的替换等操作。

这些问题的答案可以通过使用C语言的字符串处理函数来实现。

第五章：数组和广义表数组是一种线性表的顺序存储结构，广义表是线性表的扩展。

课后习题主要涉及数组和广义表的创建、访问和操作等。

这些问题的答案可以通过编写相应的C语言代码来实现。

第六章：树树是一种非线性的数据结构，具有层次关系。

课后习题主要涉及树的遍历、节点的插入和删除等操作。

这些问题的答案可以通过使用C语言的指针和递归来实现。

第七章：图图是一种非线性的数据结构，由节点和边组成。

课后习题主要涉及图的遍历、最短路径、最小生成树等操作。

这些问题的答案可以通过使用C语言的图算法来实现。

通过以上的简要介绍，读者可以了解到《数据结构（C语言版）》严蔚敏教材的课后习题主要涵盖了线性表、栈和队列、串、数组和广义表、树、图等各个方面。

说明: 1. 本文是对严蔚敏?数据构造(c语言版)习题集?一书中所有算法设计题目的解决方案,主要作者为kaoyan.计算机版版主一具.以下网友:siice,龙抬头,iamkent,zames,birdthinking等为答案的修订和完善工作提出了珍贵意见,在此表示感;2. 本解答中的所有算法均采用类c语言描述,设计原那么为面向交流、面向阅读,作者不保证程序能够上机正常运行(这种保证实际上也没有任何意义);3. 本解答原那么上只给出源代码以及必要的注释,对于一些难度较高或思路特殊的题目将给出简要的分析说明,对于作者无法解决的题目将给出必要的讨论.目前尚未解决的题目有: 5.20, 10.40;4. 请读者在自己已经解决了某个题目或进展了充分的思考之后,再参考本解答,以保证复习效果;5. 由于作者水平所限,本解答中一定存在不少这样或者那样的错误和缺乏,希望读者们在阅读中多动脑、勤思考,争取发现和纠正这些错误,写出更好的算法来.请将你发现的错误或其它值得改良之处向作者报告: 第一章绪论1.16void print_descending(int x,int y,int z)//按从大到小顺序输出三个数{scanf("%d,%d,%d",&x,&y,&z);if(x<y) x<->y; //<->为表示交换的双目运算符,以下同if(y<z) y<->z;if(x<y) x<->y; //冒泡排序printf("%d %d %d",x,y,z);}//print_descending1.17Status fib(int k,int m,int &f)//求k阶斐波那契序列的第m项的值f{int tempd;if(k<2||m<0) return ERROR;if(m<k-1) f=0;else if (m==k-1) f=1;else{for(i=0;i<=k-2;i++) temp[i]=0;temp[k-1]=1; //初始化for(i=k;i<=m;i++) //求出序列第k至第m个元素的值{sum=0;for(j=i-k;j<i;j++) sum+=temp[j];temp[i]=sum;}f=temp[m];}return OK;}//fib分析:通过保存已经计算出来的结果,此方法的时间复杂度仅为O(m^2).如果采用递归编程(大多数人都会首先想到递归方法),那么时间复杂度将高达O(k^m).1.18typedef struct{char *sport;enum{male,female} gender;char schoolname; //校名为'A','B','C','D'或'E'char *result;int score;} resulttype;typedef struct{int malescore;int femalescore;int totalscore;} scoretype;void summary(resulttype result[ ])//求各校的男女总分和团体总分,假设结果已经储存在result[ ]数组中{scoretype score;i=0;while(result[i].sport!=NULL){switch(result[i].schoolname){case 'A':score[ 0 ].totalscore+=result[i].score; if(result[i].gender==0) score[ 0 ].malescore+=result[i].score; else score[ 0 ].femalescore+=result[i].score;break;case 'B':score.totalscore+=result[i].score;if(result[i].gender==0) score.malescore+=result[i].score;else score.femalescore+=result[i].score;break;……………… }i++；}for(i=0;i<5;i++){printf("School %d:\n",i);printf("Total score of male:%d\n",score[i].malescore);printf("Total score of female:%d\n",score[i].femalescore);printf("Total score of all:%d\n\n",score[i].totalscore);}}//summary1.19Status algo119(int a[ARRSIZE])//求i!*2^i序列的值且不超过maxint{last=1;for(i=1;i<=ARRSIZE;i++){a[i-1]=last*2*i;if((a[i-1]/last)!=(2*i)) reurn OVERFLOW;last=a[i-1];return OK;}}//algo119分析:当某一项的结果超过了maxint时,它除以前面一项的商会发生异常.1.20void polyvalue(){float ad;float *p=a;printf("Input number of terms:");scanf("%d",&n);printf("Input the %d coefficients from a0 to a%d:\n",n,n);for(i=0;i<=n;i++) scanf("%f",p++);printf("Input value of x:");scanf("%f",&x);p=a;xp=1;sum=0; //xp用于存放x的i次方for(i=0;i<=n;i++){sum+=xp*(*p++);xp*=x;}printf("Value is:%f",sum);}//polyvalue第二章线性表2.10Status DeleteK(SqList &a,int i,int k)//删除线性表a中第i个元素起的k个元素{if(i<1||k<0||i+k-1>a.length) return INFEASIBLE;for(count=1;i+count-1<=a.length-k;count++) //注意循环完毕的条件a.elem[i+count-1]=a.elem[i+count+k-1];a.length-=k;return OK;}//DeleteK2.11Status Insert_SqList(SqList &va,int x)//把x插入递增有序表va中{if(va.length+1>va.listsize) return ERROR;va.length++;for(i=va.length-1;va.elem[i]>x&&i>=0;i--)va.elem[i+1]=va.elem[i];va.elem[i+1]=x;return OK;}//Insert_SqList2.12int Listp(SqList A,SqList B)//比拟字符表A和B,并用返回值表示结果,值为正,表示A>B;值为负,表示A<B;值为零,表示A=B {for(i=1;A.elem[i]||B.elem[i];i++)if(A.elem[i]!=B.elem[i]) return A.elem[i]-B.elem[i];return 0;}//Listp2.13LNode* Locate(LinkList L,int x)//链表上的元素查找,返回指针{for(p=l->next;p&&p->data!=x;p=p->next);return p;}//Locate2.14int Length(LinkList L)//求链表的长度{for(k=0,p=L;p->next;p=p->next,k++);return k;}//Length2.15void ListConcat(LinkList ha,LinkList hb,LinkList &hc)//把链表hb接在ha后面形成链表hc{while(p->next) p=p->next;p->next=hb;}//ListConcat2.16见书后答案.2.17Status Insert(LinkList &L,int i,int b)//在无头结点链表L的第i个元素之前插入元素b{p=L;q=(LinkList*)malloc(sizeof(LNode));q.data=b;if(i==1){q.next=p;L=q; //插入在链表头部}else{while(--i>1) p=p->next;q->next=p->next;p->next=q; //插入在第i个元素的位置}}//Insert2.18Status Delete(LinkList &L,int i)//在无头结点链表L中删除第i个元素{if(i==1) L=L->next; //删除第一个元素else{p=L;while(--i>1) p=p->next;p->next=p->next->next; //删除第i个元素}}//Delete2.19Status Delete_Between(Linklist &L,int mink,int maxk)//删除元素递增排列的链表L中值大于mink且小于maxk的所有元素{p=L;while(p->next->data<=mink) p=p->next; //p是最后一个不大于mink的元素if(p->next) //如果还有比mink更大的元素{q=p->next;while(q->data<maxk) q=q->next; //q是第一个不小于maxk的元素p->next=q;}}//Delete_Between2.20Status Delete_Equal(Linklist &L)//删除元素递增排列的链表L中所有值一样的元素{p=L->next;q=p->next; //p,q指向相邻两元素while(p->next){p=p->next;q=p->next; //当相邻两元素不相等时,p,q都向后推一步}else{while(q->data==p->data){free(q);q=q->next;}p->next=q;p=q;q=p->next; //当相邻元素相等时删除多余元素}//else}//while}//Delete_Equal2.21void reverse(SqList &A)//顺序表的就地逆置{for(i=1,j=A.length;i<j;i++,j--)A.elem[i]<->A.elem[j];}//reverse2.22void LinkList_reverse(Linklist &L)//链表的就地逆置;为简化算法,假设表长大于2{p=L->next;q=p->next;s=q->next;p->next=NULL;while(s->next){q->next=p;p=q;q=s;s=s->next; //把L的元素逐个插入新表表头}q->next=p;s->next=q;L->next=s;}//LinkList_reverse分析:本算法的思想是,逐个地把L的当前元素q插入新的链表头部,p为新表表头.2.23void merge1(LinkList &A,LinkList &B,LinkList &C)//把链表A和B合并为C,A和B的元素间隔排列,且使用原存储空间{p=A->next;q=B->next;C=A;while(p&&q){s=p->next;p->next=q; //将B的元素插入if(s){t=q->next;q->next=s; //如A非空,将A的元素插入}p=s;q=t;}//while}//merge12.24void reverse_merge(LinkList &A,LinkList &B,LinkList &C)//把元素递增排列的链表A和B合并为C,且C中元素递减排列,使用原空间{pa=A->next;pb=B->next;pre=NULL; //pa和pb分别指向A,B的当前元素while(pa||pb){pc=pa;q=pa->next;pa->next=pre;pa=q; //将A的元素插入新表}else{pc=pb;q=pb->next;pb->next=pre;pb=q; //将B的元素插入新表}pre=pc;}C=A;A->next=pc; //构造新表头}//reverse_merge分析:本算法的思想是,按从小到大的顺序依次把A和B的元素插入新表的头部pc处,最后处理A或B的剩余元素.2.25void SqList_Intersect(SqList A,SqList B,SqList &C)//求元素递增排列的线性表A和B的元素的交集并存入C中{i=1;j=1;k=0;while(A.elem[i]&&B.elem[j]){if(A.elem[i]<B.elem[j]) i++;if(A.elem[i]>B.elem[j]) j++;if(A.elem[i]==B.elem[j]){C.elem[++k]=A.elem[i]; //当发现了一个在A,B中都存在的元素,i++;j++; //就添加到C中}}//while}//SqList_Intersect2.26void LinkList_Intersect(LinkList A,LinkList B,LinkList &C)//在链表构造上重做上题{p=A->next;q=B->next;pc=(LNode*)malloc(sizeof(LNode));while(p&&q){if(p->data<q->data) p=p->next;else if(p->data>q->data) q=q->next;else{s=(LNode*)malloc(sizeof(LNode));s->data=p->data;pc->next=s;pc=s;p=p->next;q=q->next;}}//whileC=pc;}//LinkList_Intersect2.27void SqList_Intersect_True(SqList &A,SqList B)//求元素递增排列的线性表A和B的元素的交集并存回A中{i=1;j=1;k=0;while(A.elem[i]&&B.elem[j]){if(A.elem[i]<B.elem[j]) i++;else if(A.elem[i]>B.elem[j]) j++;A.elem[++k]=A.elem[i]; //当发现了一个在A,B中都存在的元素i++;j++; //且C中没有,就添加到C中}}//whilewhile(A.elem[k]) A.elem[k++]=0;}//SqList_Intersect_True2.28void LinkList_Intersect_True(LinkList &A,LinkList B)//在链表构造上重做上题{p=A->next;q=B->next;pc=A;while(p&&q){if(p->data<q->data) p=p->next;else if(p->data>q->data) q=q->next;else if(p->data!=pc->data){pc=pc->next;pc->data=p->data;p=p->next;q=q->next;}}//while}//LinkList_Intersect_True2.29void SqList_Intersect_Delete(SqList &A,SqList B,SqList C){i=0;j=0;k=0;m=0; //i指示A中元素原来的位置,m为移动后的位置while(i<A.length&&j<B.length&& k<C.length){if(B.elem[j]<C.elem[k]) j++;else if(B.elem[j]>C.elem[k]) k++;else{same=B.elem[j]; //找到了一样元素samewhile(B.elem[j]==same) j++;while(C.elem[k]==same) k++; //j,k后移到新的元素while(i<A.length&&A.elem[i]<same)A.elem[m++]=A.elem[i++]; //需保存的元素移动到新位置while(i<A.length&&A.elem[i]==same) i++; //跳过一样的元素}}//whilewhile(i<A.length)A.elem[m++]=A.elem[i++];//A的剩余元素重新存储。

清华大学严蔚敏数据结构习题集（C版）答案清华大学严蔚敏数据结构习题集（C版）答案第一章绪论1.16void print_descending(int x,int y,int z)//按从大到小顺序输出三个数{scanf("%d,%d,%d",&x,&y,&z);if(x<y) x<->y; //<->为表示交换的双目运算符,以下同if(y<z) y<->z;if(x<y) x<->y; //冒泡排序printf("%d %d %d",x,y,z);}//print_descending1.17Status fib(int k,int m,int &f)//求k阶斐波那契序列的第m项的值f{int tempd;if(k<2||m<0) return ERROR;if(m<k-1) f=0;else if (m==k-1) f=1;else{for(i=0;i<=k-2;i++) temp=0;temp[k-1]=1; //初始化for(i=k;i<=m;i++) //求出序列第k至第m个元素的值{sum=0;for(j=i-k;j<i;j++) sum+=temp[j];temp=sum;}f=temp[m];}return OK;}//fib分析:通过保存已经计算出来的结果,此方法的时间复杂度仅为O(m^2).如果采用递归编程(大多数人都会首先想到递归方法),则时间复杂度将高达O(k^m).1.18typedef struct{char *sport;enum{male,female} gender; char schoolname; //校名为'A','B','C','D'或'E'char *result;int score;} resulttype;typedef struct{int malescore;int femalescore;int totalscore;} scoretype;void summary(resulttype result[ ])//求各校的男女总分和团体总分,假设结果已经储存在result[ ]数组中{scoretype score;i=0;while(result.sport!=NULL){switch(result.schoolname){case 'A':score[ 0 ].totalscore+=result.score;if(result.gender==0)score[ 0 ].malescore+=result.score;elsescore[ 0 ].femalescore+=result.score;break;case 'B':score.totalscore+=result.score;if(result.gender==0)score.malescore+=result.score;else score.femalescore+=result.score;break;………………}i++；}for(i=0;i<5;i++){printf("School %d:\n",i);printf("Total score ofmale:%d\n",score.malescore);printf("Total score offemale:%d\n",score.femalescore);printf("Total score ofall:%d\n\n",score.totalscore);}}//summary1.19Status algo119(int a[ARRSIZE])//求i!*2^i序列的值且不超过maxint{last=1;for(i=1;i<=ARRSIZE;i++){a[i-1]=last*2*i;if((a[i-1]/last)!=(2*i)) reurn OVERFLOW;last=a[i-1];return OK;}}//algo119分析:当某一项的结果超过了maxint时,它除以前面一项的商会发生异常.1.20void polyvalue(){float ad;float *p=a;printf("Input number of terms:");scanf("%d",&n);printf("Input the %d coefficients from a0 toa%d:\n",n,n);for(i=0;i<=n;i++) scanf("%f",p++);printf("Input value of x:");scanf("%f",&x);p=a;xp=1;sum=0; //xp用于存放x的i次方for(i=0;i<=n;i++){sum+=xp*(*p++);xp*=x;}printf("Value is:%f",sum);}//polyvalue第二章线性表2.10Status DeleteK(SqList &a,int i,int k)//删除线性表a中第i个元素起的k个元素{if(i<1||k<0||i+k-1>a.length) returnINFEASIBLE;for(count=1;i+count-1<=a.length-k;c ount++) //注意循环结束的条件a.elem[i+count-1]=a.elem[i+count+k-1];a.length-=k;return OK;}//DeleteK2.11Status Insert_SqList(SqList &va,int x)//把x插入递增有序表va中{if(va.length+1>va.listsize) returnERROR;va.length++;for(i=va.length-1;va.elem>x&&i>=0;i--)va.elem[i+1]=va.elem;va.elem[i+1]=x;return OK;}//Insert_SqList2.12int ListComp(SqList A,SqList B)//比较字符表A和B,并用返回值表示结果,值为正,表示A>B;值为负,表示A<B;值为零,表示A=B{for(i=1;A.elem||B.elem;i++)if(A.elem!=B.elem) returnA.elem-B.elem;return 0;}//ListComp2.13LNode* Locate(LinkList L,int x)//链表上的元素查找,返回指针{for(p=l->next;p&&p->data!=x;p=p->next);return p;}//Locate2.14int Length(LinkList L)//求链表的长度{for(k=0,p=L;p->next;p=p->next,k++);return k;}//Length2.15void ListConcat(LinkList ha,LinkList hb,LinkList &hc)//把链表hb接在ha后面形成链表hc{hc=ha;p=ha;while(p->next) p=p->next;p->next=hb;}//ListConcat2.16见书后答案.2.17Status Insert(LinkList &L,int i,int b)//在无头结点链表L的第i个元素之前插入元素b{p=L;q=(LinkList*)malloc(sizeof(LNode));q.data=b;if(i==1){q.next=p;L=q; //插入在链表头部}else{while(--i>1) p=p->next;q->next=p->next;p->next=q; //插入在第i个元素的位置}}//Insert2.18Status Delete(LinkList &L,int i)//在无头结点链表L中删除第i个元素{if(i==1) L=L->next; //删除第一个元素else{p=L;while(--i>1) p=p->next;p->next=p->next->next; //删除第i个元素}}//Delete2.19Status Delete_Between(Linklist &L,int mink,int maxk)//删除元素递增排列的链表L中值大于mink且小于maxk的所有元素{p=L;while(p->next->data<=mink) p=p->next;//p是最后一个不大于mink的元素if(p->next) //如果还有比mink更大的元素{q=p->next;while(q->data<maxk) q=q->next; //q 是第一个不小于maxk的元素p->next=q;}}//Delete_Between2.20Status Delete_Equal(Linklist &L)//删除元素递增排列的链表L中所有值相同的元素{p=L->next;q=p->next; //p,q指向相邻两元素while(p->next){if(p->data!=q->data){p=p->next;q=p->next; //当相邻两元素不相等时,p,q都向后推一步}else{while(q->data==p->data){free(q);q=q->next;}p->next=q;p=q;q=p->next; //当相邻元素相等时删除多余元素}//else}//while}//Delete_Equal2.21void reverse(SqList &A)//顺序表的就地逆置{for(i=1,j=A.length;i<j;i++,j--)A.elem<->A.elem[j];}//reverse2.22void LinkList_reverse(Linklist &L)//链表的就地逆置;为简化算法,假设表长大于2{p=L->next;q=p->next;s=q->next;p->next=NULL;while(s->next){q->next=p;p=q;q=s;s=s->next; //把L的元素逐个插入新表表头}q->next=p;s->next=q;L->next=s;}//LinkList_reverse分析:本算法的思想是,逐个地把L的当前元素q插入新的链表头部,p为新表表头.2.23void merge1(LinkList &A,LinkList &B,LinkList &C)//把链表A和B合并为C,A 和B的元素间隔排列,且使用原存储空间{p=A->next;q=B->next;C=A;while(p&&q){s=p->next;p->next=q; //将B的元素插入if(s){t=q->next;q->next=s; //如A非空,将A的元素插入}p=s;q=t;}//while}//merge12.24void reverse_merge(LinkList&A,LinkList &B,LinkList &C)//把元素递增排列的链表A和B合并为C,且C中元素递减排列,使用原空间{pa=A->next;pb=B->next;pre=NULL; //pa 和pb分别指向A,B的当前元素while(pa||pb){if(pa->data<pb->data||!pb){pc=pa;q=pa->next;pa->next=pre;p a=q; //将A的元素插入新表}else{pc=pb;q=pb->next;pb->next=pre;p b=q; //将B的元素插入新表}pre=pc;}C=A;A->next=pc; //构造新表头}//reverse_merge分析:本算法的思想是,按从小到大的顺序依次把A和B的元素插入新表的头部pc处,最后处理A或B的剩余元素.2.25void SqList_Intersect(SqList A,SqList B,SqList &C)//求元素递增排列的线性表A 和B的元素的交集并存入C中{i=1;j=1;k=0;while(A.elem&&B.elem[j]){if(A.elem<B.elem[j]) i++;if(A.elem>B.elem[j]) j++;if(A.elem==B.elem[j]){C.elem[++k]=A.elem; //当发现了一个在A,B中都存在的元素,i++;j++; //就添加到C中}}//while}//SqList_Intersect2.26void LinkList_Intersect(LinkList A,LinkList B,LinkList &C)//在链表结构上重做上题{p=A->next;q=B->next;pc=(LNode*)malloc(sizeof(LNode));while(p&&q){if(p->data<q->data) p=p->next;else if(p->data>q->data) q=q->next;else{s=(LNode*)malloc(sizeof(LNode));s->data=p->data;pc->next=s;pc=s;p=p->next;q=q->next;}}//whileC=pc;}//LinkList_Intersect2.27void SqList_Intersect_True(SqList&A,SqList B)//求元素递增排列的线性表A 和B的元素的交集并存回A中{i=1;j=1;k=0;while(A.elem&&B.elem[j]){if(A.elem<B.elem[j]) i++;else if(A.elem>B.elem[j]) j++;else if(A.elem!=A.elem[k]){A.elem[++k]=A.elem; //当发现了一个在A,B中都存在的元素i++;j++; //且C中没有,就添加到C中}}//whilewhile(A.elem[k]) A.elem[k++]=0;}//SqList_Intersect_True2.28void LinkList_Intersect_True(LinkList &A,LinkList B)//在链表结构上重做上题{p=A->next;q=B->next;pc=A;while(p&&q){if(p->data<q->data) p=p->next; else if(p->data>q->data) q=q->next;else if(p->data!=pc->data){pc=pc->next;pc->data=p->data;p=p->next;q=q->next;}}//while}//LinkList_Intersect_True2.29void SqList_Intersect_Delete(SqList&A,SqList B,SqList C){i=0;j=0;k=0;m=0; //i指示A中元素原来的位置,m为移动后的位置while(i<A.length&&j<B.length&&k<C.length){if(B.elem[j]<C.elem[k]) j++;else if(B.elem[j]>C.elem[k]) k++;else{same=B.elem[j];//找到了相同元素same while(B.elem[j]==same) j++;while(C.elem[k]==same)k++; //j,k后移到新的元素while(i<A.length&&A.elem<same)A.elem[m++]=A.elem[i++];//需保留的元素移动到新位置while(i<A.length&&A.elem==same) i++; //跳过相同的元素}}//whilewhile(i<A.length)A.elem[m++]=A.elem[i++]; //A的剩余元素重新存储。

严蔚敏《数据结构（C语言版）习题集》答案第一章绪论void print_descending(int x,int y,int z)....+f[m-k]=f[m-1]+f[m-2]+......+f[m-k]+f[m-k-1]-f[m-k-1]=2*f[m-1]-f[m-k-1]所以上述算法的时间复杂度仅为O(m). 如果采用递归设计,将达到O(k^m). 即使采用暂存中间结果的方法,也将达到O(m^2).typedef struct{char *sport;enum{male,female} gender;char schoolname; port!=NULL){switch(result[i].schoolname){case 'A':score[ 0 ].totalscore+=result[i].score;if(result[i].gender==0) score[ 0 ].malescore+=result[i].score;else score[ 0 ].femalescore+=result[i].score;break;case 'B':score[ 0 ].totalscore+=result[i].score;if(result[i].gender==0) score[ 0 ].malescore+=result[i].score;else score[ 0 ].femalescore+=result[i].score;break;………………}i++；}for(i=0;i<5;i++){printf("School %d:\n",i);printf("Total score of male:%d\n",score[i].malescore);printf("Total score of female:%d\n",score[i].femalescore);printf("Total score of all:%d\n\n",score[i].totalscore);}}void polyvalue(){float temp;float *p=a;printf("Input number of terms:");scanf("%d",&n);printf("Input value of x:");scanf("%f",&x);printf("Input the %d coefficients from a0 to a%d:\n",n+1,n);p=a;xp=1;sum=0;Status Insert(LinkList &L,int i,int b)void merge1(LinkList &A,LinkList &B,LinkList &C)void SqList_Intersect(SqList A,SqList B,SqList &C)void LinkList_Intersect_Delete(LinkList &A,LinkList B,LinkList C)iList为带头结点的单循环链表类型.{s=L->next;A=(CiList*)malloc(sizeof(CiLNode));p=A;B=(CiList*)malloc(sizeof(CiLNode));q=B;C=(CiList*)malloc(sizeof(CiLNode));r=C; .4,2的顺序重排双向循环链表L中的所有结点{p=;while(p->next!=L&&p->next->next!=L){p->next=p->next->next;p=p->next;} 同时进行调整的话,必须使用堆栈保存偶数结点的指针,否则将会破坏链表结构,造成结点丢失.DuLNode * Locate_DuList(DuLinkedList &L,int x) int x;int y;} coordinate;void Repaint_Color(int g[m][n],int i,int j,int color)归形式的算法该怎么写呢?void NiBoLan(char *str,char *new)题中暂不考虑串的具体操作的实现,而将其看作一种抽象数据类型stringtype,对其可以进行连接操作:c=link(a,b).Status g(int m,int n,int &s)void InitCiQueue(CiQueue &Q)Status EnCyQueue(CyQueue &Q,int x)省掉这一句,则在某些情况下,会引起不希望的后果,虽然在大多数情况下没有影响.请思考:设S='place', T='ace', V='face',则省掉i+=Strlen(V);运行时会出现什么结果?int Delete_SubString(Stringtype &s,Stringtype t)读者用此程序取代作者早些时候对题给出的程序.void StrAssign(Stringtype &T,char chars&#;)h&&T[j].ch!=c) j++; h) T[j].num++;else T[j]={c,1};}h;j++)printf("%c: %d\n",T[j].ch,T[j].num);}前一个程序的区别在于,串s业已存在.{for(p=s->next,q=t->next;p&&q;p=p->next,q=q->next){p->ch=q->ch;pre=p;}while(q){p=(LStrNode*)malloc(sizeof(LStrNode));p->ch=q->ch;pre->next=p;pre=p;}p->next=NULL;}算法的思想是,依次把串S的一个副本S2向右错位平移1格,2格,3格,...与自身S1相匹配,如果存在最长重复子串,则必然能在此过程中被发现.用变量lrs1,lrs2,maxlen来记录已发现的最长重复子串第一次出现位置,第二次出现位置和长度.题目中未说明"重复子串"是否允许有重叠部分,本算法假定允许.如不允许,只需在第二个for语句的循环条件中加上k<=i即可.本算法时间复杂度为O(Strlen(S)^2).void Get_LPubSub(Stringtype S,Stringtype T) for(k=0,j=jmin;j<=jmax;j++){if(A[j]==B[j-i]) k++;else k=0;if(k>maxlen){lps1=j-k+1;lps2=j-i-k+1;maxlen=k;}}一的区别是,由于A,B互不相同,因此B不仅要向右错位,而且还要向左错位,以保证不漏掉一些情况.当B相对于A的位置不同时,需要匹配的区间的计算公式也各不相同,请读者自己画图以帮助理解.本算法的时间复杂度是o（strlrn（s）*strlen（t））。