数据结构(C语言描述)

教与学|数据结构一C语言描述（教学大纲）一、课程基本信息二、课程描述和目标1•课程描述本课程是高等院校计算机类相关专业一门重要的学科基础课，也是本校计算机科学与技术、软件工程、网络工程、大数据与科学技术等专业的计算机大类平台必修课。

本课程主要讨论各种数据的抽象表示、实现方法、处理数据的算法设计以及对算法性能的分析。

它的先修课程是：高级语言程序设计，后继课程是：数据库原理、操作系统等。

本课程的教学依赖于其先修课程，又能为其后续课程及进一步的软件开发奠定良好的理论与实践基础。

2.课程目标结合专业人才培养方案，并基于新工科专业OBE理念，力求通过本课程的系统学习促进学生在知识、能力和素质三方面得到一定程度的提升。

课程目标1:能够清楚表述数据结构和算法的基本概念，并能判断计算机处理不同数据时所采用的组织方法、操作原理和实现方法。

课程目标2:能够针对具体问题，运用数据结构课程相关知识和批判思维，分析计算机处理对象的结构特征，选择合适的数据存储结构，设计高效的操作算法。

课程目标3:能够综合运用数据结构的基本原理和设计方法，研究复杂问题的特征，自主设计可行的求解方案，并能运用高级语言编写实现问题求解的应用程序，再验证其正确性。

三、课程目标对毕业要求的支撑关系四、教学内容、基本要求及学时分配本课程教学内容主要包括线性表、栈和队列、串与数组、树和图等主要数据结构的特点、在计算机内部的表示和实现原理与方法分析，以及查找和排序两种主要操作的各种实线性表的应用奋斗一我自己励志的故事栈的应用奉献-开源技术背后的故事10分钟矩阵的压缩存储节约-提升资源复用水平、降低资源消耗的相关故事10分钟哈夫曼树与哈夫曼编码（压创新-工匠精神，余立平冒着巨大的危险雕刻火药的10分钟缩技术）航天人的故事拓扑排序、关键路径分布式-跨地域信息沟通水平，是升社会安全的故事10分钟二叉排序树上的查找快速排序效率-有关提升计算资源利用率以及社会生产效率10分钟的故事协作一有关专业分工、各司其职的螺丝钉精神的故10分钟五、课程重难点六、课程要求及成绩评定1.教学环节及其组织形式本课程采用线上线下相结合的混合式教学模式实施教学，整个教学分课前、课中、课后三个环节进行组织教学活动。

第1章绪论习题一、问答题1. 什么是数据结构？2. 四类基本数据结构的名称与含义。

3. 算法的定义与特性。

4. 算法的时间复杂度。

5. 数据类型的概念。

6. 线性结构与非线性结构的差别。

7. 面向对象程序设计语言的特点。

8. 在面向对象程序设计中，类的作用是什么？9. 参数传递的主要方式及特点。

10. 抽象数据类型的概念。

二、判断题1. 线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。

2. 算法就是程序。

3. 在高级语言（如C、或PASCAL）中，指针类型是原子类型。

三、计算下列程序段中X=X+1的语句频度for(i=1;i<=n;i++)for(j=1;j<=i;j++)for(k=1;k<=j;k++)x=x+1;[提示]：i=1时：1 = (1+1)×1/2 = (1+12)/2i=2时：1+2 = (1+2)×2/2 = (2+22)/2i=3时：1+2+3 = (1+3)×3/2 = (3+32)/2…i=n时：1+2+3+……+n = (1+n)×n/2 = (n+n2)/2f(n) = [ (1+2+3+……+n) + (12 + 22 + 32 + …… + n2 ) ] / 2 =[ (1+n)n/2 + n(n+1)(2n+1)/6 ] / 2=n(n+1)(n+2)/6=n3/6+n2/2+n/3区分语句频度和算法复杂度：O(f(n)) = O(n3)四、试编写算法求一元多项式Pn(x)=a0+a1x+a2x2+a3x3+…a n x n的值P n(x0)，并确定算法中的每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能的小，规定算法中不能使用求幂函数。

注意：本题中的输入a i(i=0,1,…,n), x和n，输出为P n(x0).通常算法的输入和输出可采用下列两种方式之一：（1）通过参数表中的参数显式传递；（2）通过全局变量隐式传递。

第1章绪论习题一、问答题1. 什么是数据结构?2. 四类基本数据结构的名称与含义。

3. 算法的定义与特性。

4. 算法的时间复杂度。

5. 数据类型的概念。

6. 线性结构与非线性结构的差别。

7. 面向对象程序设计语言的特点。

8. 在面向对象程序设计中,类的作用是什么?9. 参数传递的主要方式及特点。

10.抽象数据类型的概念。

二、判断题1. 线性结构只能用顺序结构来存放,非线性结构只能用非顺序结构来存放。

2. 算法就是程序。

3. 在高级语言(如C、或PASCAL)中,指针类型是原子类型。

三、计算下列程序段中XX1 的语句频度fori1iltni forj1jltij fork1kltjk xx1 提示: i1 时:1 11×1/2 112/2 i2 时:12 12×2/2 222/2 i3 时:123 13×3/2 332/2 … in 时:123……n 1n×n/2 nn2/2 fn 123……n 12 22 32 …… n2 / 2 1nn/2 nn12n1/6 / 2 nn1n2/6 n3/6n2/2n/3区分语句频度和算法复杂度:Ofn On3 四、试编写算法求一元多项式Pnxa0a1xa2x2a3x3…anxn 的值Pnx0,并确定算法中的每一语句的执行次数和整个算法的时间复杂度,要求时间复杂度尽可能的小,规定算法中不能使用求幂函数。

注意:本题中的输入aii01…n x 和n,输出为Pnx0.通常算法的输入和输出可采用下列两种方式之一:(1)通过参数表中的参数显式传递;(2)通过全局变量隐式传递。

试讨论这两种方法的优缺点,并在本题算法中以你认为较好的一种方式实现输入和输出。

提示:floatPolyValuefloat a float x int n…… 核心语句:p1 x 的零次幂s0 i 从0 到n 循环ssaip ppx 或:px x 的一次幂sa0 i 从1 到n 循环ssaip ppx 实习题设计实现抽象数据类型“有理数”。

数据结构(C语言)数据组织（数据、数据元素、数据项）的三个层次：数据可由若干个数据元素构成，而数据元素又可以由一个或若干个数据项组成。

四种基本的数据结构：集合、线性结构、树形结构、图状结构。

顺序存储的特点是在内存中开辟一组连续的空间来存放数据，数据元素之间的逻辑关系通过元素在内存中存放的相对位置来确定。

链式存储的特点是通过指针反映数据元素之间的逻辑关系。

数据类型：原子类型、结构类型。

线性表定义：线性表是n个数据元素的有限序列。

线性表的顺序存储结构：表中相邻的元素a和b所对应的存储地址A和B 也是相邻的。

（也就是数据都是按照表中情况进行连续存储的情况）线性表的链式存储结构：该线性表中的数据元素可以用任意的存储单元来存储。

表中的各个相邻的数据（元素）是通过一个指针地址来进行链接的，以找到下一个数据（元素）在哪。

其形式一般为：数据地址线性表的顺序和链式存储结构的比较：在线性表的长度变化比较大，预先难以确定的情况下，最好采用动态链表作为存储结构。

当线性表的长度变化不大时，采用顺序存储结构比较节省存储空间。

在顺序表结构的线性表上主要进行查找、读取而很少做插入和删除的操作。

链式结构的线性表中比较适应做插入和删除的操作。

一元多项式的加减法运算可先将一元多项式进行了改变存储之后再进行运算比较适宜，将一元多项式转换为用在内存中的前一项表示阶数，后一项表示对应该阶数的系数。

然后利用这种形式进行加减运算。

栈和队列栈是限定在表的同一端进行插入或删除操作的线性表，即进栈、出栈。

（特殊的线性表）栈的顺序存储结构：利用一组地址连续的存储单元依次从栈底到栈顶存放数据元素，栈底位置固定不变，可将栈底设在向量低下标的一端。

栈的链式存储结构：用单链表作为存储结构的栈称为链栈，链表的最后一个结点表示栈底，第一个结点表示栈顶。

队列也是一种特殊的线性表。

它所有的插入操作均限定在表的一端进行，而所有的删除操作则限定在表的另一端进行。

允许删除元素的一端称为队头，允许插入元素的一端称为队尾，删除元素称为出队，插入元素称为进队。

习题配套第一章2．C、A、B、B、A、A、D3．D={A,B,C,E,F,G,H,I,J};R={<A,B>,<A,C>,<A,E>,<B,F>,<B,G>,<E,H>,<E,I>,<E,J>,<H,I>,<I,J>}题1-3图4．顺序、链式、索引、哈希。

*5．解：100n2>2n n至少要多大6.Ｏ(n)、Ｏ(n)、Ｏ(n)、Ｏ(n)、(5)当n>m，Ｏ(n),当m>n，Ｏ(m)7．n!2100>lgn>n1/2>n3/2>(3/2)n>2n>n lgn>n n第二章1．×、√、×、√、√2．AAD4．顺序表void Delete_SeqListx(SeqList *L,ElemType x)/*删除表中值为x元素*/{inti,j;for(i=1;i<=L->length;i++){if(L->elem[i]==x){for(j=i;j<=L->length-1;j++)L->elem[j]=L->elem[j+1];L->length--;}/*向上移动*/}O(n2)链表void del_link(LinkList H，int x)/*删除数据域为x的结点*/ {LNode *p，*q;p=H;q=H->next;while(q!=NULL){if(q->data==x){p->next=q->next;free(q);q=p->next;}else{p=q;q=q->next;}}}O(n)5．int Delete_SeqListx(SeqList *L,int i,int k)/*删除表中删除自第i个结点开始的k个结点*/{intj;if(i<1||k<0||i+k-1>L->length)/*检查空表及删除位置的合法性*/{printf(＂不存在第i个元素＂);return ERROR;}for(j=i;j<=L->length-k;j++)L->elem[j]=L->elem[j+k]; /*向上移动*/L->length-=k;Return OK;/*删除成功*/}O(n)6．void Delete_SeqListx(SeqList *L,ElemType x)/*将表中值为x元素换成y*/{inti,j;for(i=1;i<=L->length;i++){if(L->elem[]==x){L->elem[i]=y;}/* */}O(n)7．写一算法在循环单链表上实现线性表的CList_length(L)运算。

第1章绪论之阳早格格创做习题一、问问题1. 什么是数据结构？2. 四类基础数据结构的称呼与含意.3. 算法的定义与个性.4. 算法的时间搀纯度.5. 数据典型的观念.6. 线性结构与非线性结构的不共.7. 里背对于象步调安排谈话的个性.8. 正在里背对于象步调安排中，类的效率是什么？9. 参数传播的主要办法及个性.10. 抽象数据典型的观念.二、推断题1. 线性结构只可用程序结构去存搁，非线性结构只可用非程序结构去存搁.2. 算法便是步调.3. 正在下档谈话（如C、大概 PASCAL）中，指针典型是本子典型.三、估计下列步调段中X=X+1的语句频度for(i=1;i<=n;i++)for(j=1;j<=i;j++)for(k=1;k<=j;k++)x=x+1;[提示]：i=1时： 1 = (1+1)×1/2 = (1+12)/2i=2时： 1+2 = (1+2)×2/2 = (2+22)/2i=3时： 1+2+3 = (1+3)×3/2 = (3+32)/2…i=n时：1+2+3+……+n = (1+n)×n/2 = (n+n2)/2f(n) = [ (1+2+3+……+n) + (12 + 22 + 32 + …… + n2 ) ] / 2=[ (1+n)n/2 + n(n+1)(2n+1)/6 ] / 2=n(n+1)(n+2)/6=n3/6+n2/2+n/3区别语句频度战算法搀纯度：O(f(n)) = O(n3)四、试编写算法供一元多项式Pn(x)=a0+a1x+a2x2+a3x3+…a n x n的值P n(x0)，并决定算法中的每一语句的真止次数战所有算法的时间搀纯度，央供时间搀纯度尽大概的小，确定算法中不克不迭使用供幂函数.注意：本题中的输进a i(i=0,1,…,n), x战n，输出为P n(x0).常常算法的输进战输出可采与下列二种办法之一：（1）通过参数表中的参数隐式传播；（2）通过局部变量隐式传播.试计划那二种要领的劣缺面，并正在本题算法中以您认为较佳的一种办法真止输进战输出.[提示]：float PolyValue(float a[ ], float x, int n) {……}核心语句：p=1; (x的整次幂)s=0;i从0到n循环s=s+a[i]*p;p=p*x;大概：p=x; (x的一次幂)s=a[0];i从1到n循环s=s+a[i]*p;p=p*x;真习题安排真止抽象数据典型“有理数”.基础支配包罗有理数的加法、减法、乘法、除法，以及供有理数的分子、分母.第一章问案估计下列步调中x=x+1的语句频度for(i=1;i<=n;i++)for(j=1;j<=i;j++)for(k=1;k<=j;k++)x=x+1;【解问】x=x+1的语句频度为：T(n)=1+(1+2)+（1+2+3）+……+（1+2+……+n）=n(n+1)(n+2)/6 1.4试编写算法，供p n(x)=a0+a1x+a2x2+…….+a n x n的值p n(x0),并决定算法中每一语句的真止次数战所有算法的时间搀纯度，央供时间搀纯度尽大概小，确定算法中不克不迭使用供幂函数.注意：本题中的输进为a i(i=0,1,…n)、x战n,输出为P n(x0).算法的输进战输出采与下列要领（1）通过参数表中的参数隐式传播（2）通过局部变量隐式传播.计划二种要领的劣缺面，并正在算法中以您认为较佳的一种真止输进输出.【解问】（1）通过参数表中的参数隐式传播便宜：当不调用函数时，不占用内存，调用中断后形参被释搁，真参保护，函数通用性强，移置性强.缺面：形参须与真参对于应，且返回值数量有限.（2）通过局部变量隐式传播便宜：缩小真介进形参的个数，进而缩小内存空间以及传播数据时的时间消耗缺面：函数通用性落矮，移植性好算法如下：通过局部变量隐式传播参数PolyValue(){ int i,n;float x,a[],p;printf(“\nn=”);scanf(“%f”,&n);printf(“\nx=”);scanf(“%f”,&x);for(i=0;i<n;i++)scanf(“%f ”,&a[i]); /*真止次数：n次 */p=a[0];for(i=1;i<=n;i++){ p=p+a[i]*x; /*真止次数：n次*/x=x*x;}printf(“%f”,p);}算法的时间搀纯度：T(n)=O(n)通过参数表中的参数隐式传播float PolyValue(float a[ ], float x, int n){float p,s;int i;p=x;s=a[0];for(i=1;i<=n;i++){s=s+a[i]*p; /*真止次数:n次*/p=p*x;}return(p);}算法的时间搀纯度：T(n)=O(n)第2章线性表习题2.1 形貌以下三个观念的辨别：头指针，头结面，尾元素结面.2.2 挖空：（1）正在程序表中拔出大概简略一个元素，需要仄衡移动＿＿一半＿＿元素，简曲移动的元素个数与＿＿拔出大概简略的位子＿＿有闭.（2）正在程序表中，逻辑上相邻的元素，其物理位子＿＿＿＿＿＿相邻.正在单链表中，逻辑上相邻的元素，其物理位子＿＿＿＿＿＿相邻.（3）正在戴头结面的非空单链表中，头结面的保存位子由＿＿＿＿＿＿指示，尾元素结面的保存位子由＿＿＿＿＿＿指示，除尾元素结面中，其余任一元素结面的保存位子由＿＿其间接前趋的next 域＿＿指示.2.3 已知L是无表头结面的单链表，且P结面既不是尾元素结面，也不是尾元素结面.按央供从下列语句中采用符合的语句序列.a. 正在P结面后拔出S结面的语句序列是：＿（4）、（1）＿.b. 正在P结面前拔出S结面的语句序列是：（7）、（11）、（8）、（4）、（1）.c. 正在表尾拔出S结面的语句序列是：（5）、（12）.d. 正在表尾拔出S结面的语句序列是：（11）、（9）、（1）、（6）.供采用的语句有：（1）P->next=S;（2）P->next= P->next->next;（3）P->next= S->next;（4）S->next= P->next;（5）S->next= L;（6）S->next= NULL;（7）Q= P;（8）while(P->next!=Q) P=P->next;（9）while(P->next!=NULL) P=P->next;（10）P= Q;（11）P= L;（12）L= S;（13）L= P;2.4 已知线性表L递加有序.试写一算法，将X拔出到L的适合位子上，以脆持线性表L的有序性.[提示]：void insert(SeqList *L; ElemType x)< 要领1 >（1）找出应拔出位子i，（2）移位，（3）……< 要领2 > 参P. 2292.5 写一算法，从程序表中简略自第i个元素启初的k个元素.[提示]：注意查看i战k的合法性.（普遍搬家，“新房”、“旧房”）< 要领1 > 以待移动元素下标m（“旧房号”）为核心，估计应移进位子（“新房号”）：for ( m= i－1+k; m<= L－>last; m++)L－>elem[ m－k ] = L－>elem[ m ];< 要领2 > 共时以待移动元素下标m战应移进位子j为核心：< 要领3 > 以应移进位子j为核心，估计待移动元素下标：已知线性表中的元素（整数）以值递加有序排列，并以单链表做保存结构.试写一下效算法，简略表中所有大于mink且小于maxk的元素（若表中存留那样的元素），领会您的算法的时间搀纯度（注意：mink战maxk是给定的二个参变量，它们的值为任性的整数）.[提示]：注意查看mink战maxk的合法性：mink < maxk不要一个一个的简略（多次建改next域）.（1）找到第一个应删结面的前驱prepre=L; p=L－>next;while (p!=NULL && p－>data <= mink){ pre=p; p=p－>next; }（2）找到末尾一个应删结面的后继s，边找边释搁应删结面s=p;while (s!=NULL && s－>data < maxk){ t =s; s=s－>next; free(t); }（3）pre－>next = s;试分别以分歧的保存结构真止线性表的便天顺置算法，即正在本表的保存空间将线性表（a1, a2..., a n）顺置为（a n, a n-1,..., a1）.（1）以一维数组做保存结构，设线性表存于a(1:arrsize)的前elenum个分量中.（2）以单链表做保存结构.[要领1]：正在本头结面后沉新头插一遍[要领2]：可设三个共步移动的指针p, q, r，将q的后继r改为p2.8 假设二个按元素值递加有序排列的线性表A战B，均以单链表动做保存结构，请编写算法，将A表战B表归并成一个按元素值递减有序的排列的线性表C，并央供利用本表（即A表战B表的）结面空间存搁表C.[提示]：参P.28 例2-1< 要领1 >void merge(LinkList A; LinkList B; LinkList *C){ ……pa=A－>next; pb=B－>next;*C=A; (*C)－>next=NULL;while ( pa!=NULL && pb!=NULL ){if ( pa－>data <= pb－>data ){smaller=pa; pa=pa－>next;smaller－>next = (*C)－>next; /* 头插法 */(*C)－>next = smaller;}else{smaller=pb; pb=pb－>next;smaller－>next = (*C)－>next;(*C)－>next = smaller;}}while ( pa!=NULL){smaller=pa; pa=pa－>next;smaller－>next = (*C)－>next;(*C)－>next = smaller;}while ( pb!=NULL){smaller=pb; pb=pb－>next;smaller－>next = (*C)－>next;(*C)－>next = smaller;}< 要领2 >LinkList merge(LinkList A; LinkList B){ ……LinkList C；pa=A－>next; pb=B－>next;C=A; C－>next=NULL;…………return C;2.9 假设有一个循环链表的少度大于1，且表中既无头结面也无头指针.已知s为指背链表某个结面的指针，试编写算法正在链表中简略指针s 所指结面的前趋结面.[提示]：设指针p指背s结面的前趋的前趋，则p与s有何闭系？2.10 已知有单链表表示的线性表中含有三类字符的数据元素（如字母字符、数字字符战其余字符），试编写算法去构制三个以循环链表表示的线性表，使每个表中只含共一类的字符，且利用本表中的结面空间动做那三个表的结面空间，头结面可另辟空间.2.11 设线性表A=(a1, a2,…,a m)，B=(b1, b2,…,b n)，试写一个按下列准则合并A、B为线性表C的算法，使得：C= (a1, b1,…,a m, b m, b m+1,…,b n)当m≤n时；大概者 C= (a1, b1,…,a n, b n, a n+1,…,a m) 当m>n时.线性表A、B、C均以单链表动做保存结构，且C表利用A表战B 表中的结面空间形成.注意：单链表的少度值m战n均已隐式保存.[提示]：void merge(LinkList A; LinkList B; LinkList *C)大概：LinkList merge(LinkList A; LinkList B)2.12 将一个用循环链表表示的稠稀多项式领会成二个多项式，使那二个多项式中各自仅含奇次项大概奇次项，并央供利用本链表中的结面空间去形成那二个链表.[提示]：证明用头指针仍旧尾指针.2.13 建坐一个戴头结面的线性链表，用以存搁输进的二进制数，链表中每个结面的data域存搁一个二进制位.并正在此链表上真止对于二进制数加1的运算.[提示]：可将矮位搁正在前里.2.14 设多项式P(x)采与课本中所述链接要领保存.写一算法，对于给定的x值，供P(x)的值.[提示]：float PolyValue(Polylist p; float x) {……}真习题1．将若搞皆会的疑息存进一个戴头结面的单链表，结面中的皆会疑息包罗皆会名、皆会的位子坐标.央供：（1）给定一个皆会名，返回其位子坐标；（2）给定一个位子坐标P战一个距离D，返回所有与P的距离小于等于D的皆会.2．约瑟妇环问题.约瑟妇问题的一种形貌是：编号为1，2，…，n的n部分按顺时针目标围坐一圈，每人持有一个暗号（正整数）.一启初任选一个整数动做报数上限值m,从第一部分启初顺时针自1启初程序报数，报到m时停止报数.报m的人出列，将他的暗号动做新的m值，从他正在顺时针目标上的下一部分启初沉新从1报数，如许下去，曲至所有的人局部出列为止.试安排一个步调，供出出列程序.利用单背循环链表动做保存结构模拟此历程，依照出列程序挨印出各人的编号.比圆m的初值为20；n=7，7部分的暗号依次是：3，1，7，2，4，8，4，出列的程序为6，1，4，7，2，3，5.第二章问案真习题二：约瑟妇环问题约瑟妇问题的一种形貌为：编号1,2,…,n的n部分按顺时针目标围坐一圈，每部分持有一个暗号（正整数）.一启初任选一个报数上限值m,从第一部分启初顺时针自1启初程序报数，报到m时停止报数.报m 的人出列，将他的暗号动做新的m值，从他正在顺时针目标上的下一部分启初沉新从1报数，如许下去，曲至所有的人局部出列为止.试安排一个步调，供出出列程序.利用单背循环链表动做保存结构模拟此历程，依照出列程序挨印出各人的编号.比圆，m的初值为20；n=7，7部分的暗号依次是：3,1,7,2,4,8,4，出列程序为6,1,4,7,2,3,5.【解问】算法如下：typedef struct Node{int password;int num;struct Node *next;} Node,*Linklist;void Josephus(){Linklist L;Node *p,*r,*q;int m,n,C,j;L=(Node*)malloc(sizeof(Node)); /*初初化单背循环链表*/if(L==NULL) { printf("\n链表申请不到空间!");return;}L->next=NULL;r=L;printf("请输进数据n的值(n>0):");scanf("%d",&n);for(j=1;j<=n;j++) /*建坐链表*/{p=(Node*)malloc(sizeof(Node));if(p!=NULL){printf("请输进第%d部分的暗号:",j);scanf("%d",&C);p->password=C;p->num=j;r->next=p;r=p;}}r->next=L->next;printf("请输进第一个报数上限值m(m>0):");scanf("%d",&m);printf("*****************************************\n"); printf("出列的程序为:\n");q=L;p=L->next;while(n!=1) /*估计出列的程序*/{j=1;while(j<m) /*估计目前出列的人选p*/{q=p; /*q为目前结面p的前驱结面*/p=p->next;j++;}printf("%d->",p->num);m=p->password; /*赢得新暗号*/n--;q->next=p->next; /*p出列*/r=p;p=p->next;free(r);}printf("%d\n",p->num);}试分别以分歧的保存结构真止单线表的便天顺置算法，即正在本表的保存空间将线性表（a1,a2,…,a n）顺置为(a n,a n-1,…,a1).【解问】（1）用一维数组动做保存结构void invert(SeqList *L, int *num){int j;ElemType tmp;for(j=0;j<=(*num-1)/2;j++){tmp=L[j];L[j]=L[*num-j-1];L[*num-j-1]=tmp;}}}（2）用单链表动做保存结构void invert(LinkList L){Node *p, *q, *r;if(L->next ==NULL) return; /*链表为空*/p=L->next;q=p->next;p->next=NULL; /* 戴下第一个结面，死成初初顺置表 */while(q!=NULL) /* 从第二个结面起依次头拔出目前顺置表 */{r=q->next;q->next=L->next;L->next=q;q=r;}}将线性表A=(a1,a2,……am), B=(b1,b2,……bn)合并成线性表C, C=(a1,b1,……am,bm,bm+1,…….bn)当m<=n时，大概C=(a1,b1, ……an,bn,an+1,……am)当m>n时,线性表A、B、C以单链表动做保存结构，且C表利用A表战B表中的结面空间形成.注意：单链表的少度值m战n均已隐式保存.【解问】算法如下：LinkList merge(LinkList A, LinkList B, LinkList C){Node *pa, *qa, *pb, *qb, *p;pa=A->next; /*pa表示A的目前结面*/pb=B->next;p=A; / *利用p去指背新对接的表的表尾，初初值指背表A的头结面*/while(pa!=NULL && pb!=NULL) /*利用尾插法建坐对接之后的链表*/{qa=pa->next;qb=qb->next;p->next=pa; /*接替采用表A战表B中的结面对接到新链表中；*/ p=pa;p->next=pb;p=pb;pa=qa;pb=qb;}if(pa!=NULL) p->next=pa; /*A的少度大于B的少度*/if(pb!=NULL) p->next=pb; /*B的少度大于A的少度*/C=A;return(C);}第3章规定性线性表—栈战行列习题1. 按图3.1(b)所示铁讲（二侧铁讲均为单背止驶讲）举止车厢调动，回问：⑴如进站的车厢序列为123，则大概得到的出站车厢序列是什么？123、213、132、231、321（312）⑵如进站的车厢序列为123456，是可得到435612战135426的出站序列，并证明本果.（即写出以“S”表示进栈、以“X”表示出栈的栈支配序列）.SXSS XSSX XXSX 大概 S1X1S2S3X3S4S5X5X4X2S6X62. 设行列中有A、B、C、D、E那5个元素，其中队尾元素为A.如果对于那个行列沉复真止下列4步支配：（1）输出队尾元素；（2）把队尾元素值拔出到队尾；（3）简略队尾元素；（4）再次简略队尾元素.曲到行列成为空行列为止，则是可大概得到输出序列：（1）A、C、E、C、C （2） A、C、E（3） A、C、E、C、C、C （4） A、C、E、C[提示]：A、B、C、D、E （输出队尾元素A）A、B、C、D、E、A （把队尾元素A拔出到队尾）B、C、D、E、A （简略队尾元素A）C、D、E、A （再次简略队尾元素B）C、D、E、A （输出队尾元素C）C、D、E、A、C （把队尾元素C拔出到队尾）D、E、A、C （简略队尾元素C）E、A、C （再次简略队尾元素D）3. 给出栈的二种保存结构形式称呼，正在那二种栈的保存结构中怎么样判别栈空与栈谦？4. 依照四则运算加、减、乘、除战幂运算（↑）劣先闭系的惯例，绘出对于下列算术表白式供值时支配数栈战运算符栈的变更历程：A－B＊Ｃ／Ｄ＋Ｅ↑Ｆ5. 试写一个算法，推断依次读进的一个以@为中断符的字母序列，是可为形如‘序列1&序列2’模式的字符序列.其中序列1战序列2中皆不含字符’&’，且序列2是序列1的顺序列.比圆，‘a+b&b+a’是属该模式的字符序列，而‘１+３&３－１’则不是.[提示]：（1）边读边进栈，曲到&（2）边读边出栈边比较，曲到……6. 假设表白式由单字母变量战单目四则运算算符形成.试写一个算法，将一个常常书籍写形式（中缀）且书籍写精确的表白式变换为顺波兰式（后缀）.[提示]：例：中缀表白式：a+b后缀表白式: ab+中缀表白式：a+b×c后缀表白式: abc×+中缀表白式：a+b×c-d后缀表白式: abc×+d-中缀表白式：a+b×c-d/e后缀表白式: abc×+de/-中缀表白式：a+b×(c-d)-e/f后缀表白式: abcd-×+ef/-•后缀表白式的估计历程：（烦琐）程序扫描表白式，（1）如果是支配数，间接进栈；（2）如果是支配符op，则连绝退栈二次，得支配数X, Y，估计X op Y，并将截止进栈.•怎么样将中缀表白式变换为后缀表白式？程序扫描中缀表白式，（1）如果是支配数，间接输出；（2）如果是支配符op2，则与栈顶支配符op1比较：如果op2 > op1，则op2进栈；如果op2 = op1，则脱括号；如果op2 < op1，则输出op1；7. 假设以戴头结面的循环链表表示行列，而且只设一个指针指背队尾元素结面（注意不设头指针），试编写相映的行列初初化、进行列战出行列的算法.[提示]：参P.56 P.70 先绘图.typedef LinkListCLQueue;int InitQueue(CLQueue * Q)int EnterQueue(CLQueue Q, QueueElementType x)int DeleteQueue(CLQueue Q, QueueElementType *x)8. 央供循环行列不益坏一个空间局部皆能得到利用, 树坐一个标记域tag , 以tag为0大概1去区别头尾指针相共时的行列状态的空与谦，请编写与此结构相映的进队与出队算法.[提示]：初初状态：front==0, rear==0, tag==0队空条件：front==rear, tag==0队谦条件：front==rear, tag==1其余状态：front !=rear, tag==0（大概1、2）进队支配：……（进队）if (front==rear) tag=1；（大概间接tag=1）出队支配：……（出队）tag=0；[问题]：怎么样精确区别队空、队谦、非空非谦三种情况？9. 简述以下算法的功能（其中栈战行列的元素典型均为int）：（1）void proc_1(Stack S){ iint i, n, A[255];n=0;while(!EmptyStack(S)){n++;Pop(&S, &A[n]);}for(i=1; i<=n; i++)Push(&S, A[i]);}将栈S顺序.（2）void proc_2(Stack S, int e) {Stack T; int d;InitStack(&T);while(!EmptyStack(S)){Pop(&S, &d);if (d!=e) Push( &T, d);}while(!EmptyStack(T)){Pop(&T, &d);Push( &S, d);}}简略栈S中所有等于e的元素.（3）void proc_3(Queue *Q){Stack S; int d;InitStack(&S);while(!EmptyQueue(*Q)){DeleteQueue(Q, &d);Push( &S, d);}while(!EmptyStack(S)){Pop(&S, &d);EnterQueue(Q，d)}}将行列Q顺序.真习题1．回文推断.称正读与反读皆相共的字符序列为“回文”序列.试写一个算法，推断依次读进的一个以@为中断符的字母序列，是可为形如‘序列1&序列2’模式的字符序列.其中序列1战序列2中皆不含字符‘&’，且序列2是序列1的顺序列.比圆，‘a+b&b+a’是属该模式的字符序列，而‘１+３&３－１’则不是.2．停车场管制.设停车场是一个可停搁n辆车的狭少通讲，且惟有一个大门可供汽车出进.正在停车场内，汽车按到达的先后序次，由北背北依次排列（假设大门正在最北端）.若车场内已停谦n辆车，则厥后的汽车需正在门中的便讲上期待，当有车启走时，便讲上的第一辆车即可启进.当停车场内某辆车要离启时，正在它之后加进的车辆必须先退出车场为它让路，待该辆车启出大门后，其余车辆再按本序次返回车场.每辆车离启停车场时，应按其停顿时间的少短接费（正在便讲上停顿的时间不支费）.试编写步调，模拟上述管制历程.央供以程序栈模拟停车场，以链行列模拟便讲.从末端读进汽车到达大概拜别的数据，每组数据包罗三项：①是“到达”仍旧“拜别”；②汽车牌照号码；③“到达”大概“拜别”的时刻.与每组输进疑息相映的输出疑息为：如果是到达的车辆，则输出其正在停车场中大概便讲上的位子；如果是拜别的车辆，则输出其正在停车场中停顿的时间战应接的费用.（提示：需另设一个栈，临时停搁为让路而从车场退出的车.）Array3．商品货架管制.的死产日期迩去.在较下的位子..按3.1(b)所示铁讲（二侧铁讲均为单背止驶讲）举止车厢调动，回问：（1）如进站的车厢序列为123，则大概得到的出站车厢序列是什么？（2）如进站的车厢序列为123456，是可得到435612战135426的出站序列，并证明本果（即写出以“S”表示进栈、“X”表示出栈的栈序列支配）.【解问】（1）大概得到的出站车厢序列是：123、132、213、231、321.（2）不克不迭得到435612的出站序列.果为有S(1)S(2)S(3)S(4)X(4)X(3)S(5)X(5)S(6)S(6)，此时依照“后进先出”的准则，出栈的程序必须为X(2)X(1).能得到135426的出站序列.果为有S(1)X(1)S(2)S(3)X(3)S(4)S(5)X(5)X(4)X(2)X(1).给出栈的二种保存结构形式称呼，正在那二种栈的保存结构中怎么样判别栈空与栈谦？【解问】（1）程序栈（top用去存搁栈顶元素的下标）推断栈S空：如果S->top==-1表示栈空.推断栈S谦：如果S->top==Stack_Size-1表示栈谦.（2）链栈（top为栈顶指针，指背目前栈顶元素前里的头结面）推断栈空：如果top->next==NULL表示栈空.推断栈谦：当系统不可用空间时，申请不到空间存搁要进栈的元素，此时栈谦.3.4 照四则运算加、减、乘、除战幂运算的劣先惯例，绘出对于下列表白式供值时支配数栈战运算符栈的变更历程：A-B*C/D+E↑F【解问】3.5写一个算法，推断依次读进的一个以@为中断符的字母序列，是可形如‘序列1&序列2’的字符序列.序列1战序列2中皆不含‘&’，且序列2是序列1 的顺序列.比圆，’a+b&b+a’是属于该模式的字符序列，而’1+3&3-1’则不是.【解问】算法如下：int IsHuiWen(){Stack *S;Char ch,temp;InitStack(&S);Printf(“\n请输进字符序列：”);Ch=getchar();While( ch!=&) /*序列1进栈*/{Push(&S,ch);ch=getchar();}do /*推断序列2是可是序列1的顺序列*/{ch=getchar();。

【最新整理，下载后即可编辑】第1章 绪 论2.(1)×(2)×(3)√3.（1）A （2）C （3）C5.计算下列程序中x=x+1的语句频度for(i=1;i<=n;i++)for(j=1;j<=i;j++)for(k=1;k<=j;k++) x=x+1;【解答】x=x+1的语句频度为：T(n)=1+(1+2)+（1+2+3）+……+（1+2+……+n ）=n(n+1)(n+2)/66.编写算法，求 一元多项式p n (x)=a 0+a 1x+a 2x 2+…….+a n x n 的值p n (x 0),并确定算法中每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用求幂函数。

注意：本题中的输入为a i (i=0,1,…n)、x 和n,输出为P n (x 0)。

算法的输入和输出采用下列方法（1）通过参数表中的参数显式传递（2）通过全局变量隐式传递。

讨论两种方法的优缺点，并在算法中以你认为较好的一种实现输入输出。

【解答】（1）通过参数表中的参数显式传递优点：当没有调用函数时，不占用内存，调用结束后形参被释放，实参维持，函数通用性强，移置性强。

缺点：形参须与实参对应，且返回值数量有限。

（2）通过全局变量隐式传递优点：减少实参与形参的个数，从而减少内存空间以及传递数据时的时间消耗缺点：函数通用性降低，移植性差算法如下：通过全局变量隐式传递参数PolyValue(){ int i,n;float x,a[],p;printf(“\nn=”);scanf(“%f”,&n);printf(“\nx=”);scanf(“%f”,&x);for(i=0;i<n;i++)scanf(“%f ”,&a[i]); /*执行次数：n次*/p=a[0];for(i=1;i<=n;i++){ p=p+a[i]*x; /*执行次数：n次*/x=x*x;}printf(“%f”,p);}算法的时间复杂度：T(n)=O(n)通过参数表中的参数显式传递float PolyValue(float a[ ], float x, int n){float p,s;int i;p=x;s=a[0];for(i=1;i<=n;i++){s=s+a[i]*p; /*执行次数:n次*/p=p*x;}return(p);}算法的时间复杂度：T(n)=O(n)第2章线性表习题1.填空：(1)在顺序表中插入或删除一个元素，需要平均移动一半元素，具体移动的元素个数与插入或删除的位置有关。