算法与数据结构C语言习题参考答案6-9章

数据结构(c语言版)课后习题答案完整版数据结构(C语言版)课后习题答案完整版一、数据结构概述数据结构是计算机科学中一个重要的概念，用来组织和存储数据，使之可以高效地访问和操作。

在C语言中，我们可以使用不同的数据结构来解决各种问题。

本文将提供完整版本的C语言数据结构的课后习题答案。

二、顺序表1. 顺序表的定义和基本操作顺序表是一种线性表，其中的元素在物理内存中连续地存储。

在C 语言中，我们可以通过定义结构体和使用指针来实现顺序表。

以下是顺序表的一些基本操作的答案：（1）初始化顺序表```ctypedef struct{int data[MAX_SIZE];int length;} SeqList;void InitList(SeqList *L){L->length = 0;}```（2）插入元素到顺序表中```cbool Insert(SeqList *L, int pos, int elem){if(L->length == MAX_SIZE){return false; // 顺序表已满}if(pos < 1 || pos > L->length + 1){return false; // 位置不合法}for(int i = L->length; i >= pos; i--){L->data[i] = L->data[i-1]; // 向后移动元素 }L->data[pos-1] = elem;L->length++;return true;}```（3）删除顺序表中的元素```cbool Delete(SeqList *L, int pos){if(pos < 1 || pos > L->length){return false; // 位置不合法}for(int i = pos; i < L->length; i++){L->data[i-1] = L->data[i]; // 向前移动元素 }L->length--;return true;}```（4）查找顺序表中的元素```cint Search(SeqList L, int elem){for(int i = 0; i < L.length; i++){if(L.data[i] == elem){return i + 1; // 找到元素，返回位置 }}return -1; // 未找到元素}```2. 顺序表习题解答（1）逆置顺序表```cvoid Reverse(SeqList *L){for(int i = 0; i < L->length / 2; i++){int temp = L->data[i];L->data[i] = L->data[L->length - 1 - i]; L->data[L->length - 1 - i] = temp;}}```（2）顺序表元素去重```cvoid RemoveDuplicates(SeqList *L){for(int i = 0; i < L->length; i++){for(int j = i + 1; j < L->length; j++){if(L->data[i] == L->data[j]){Delete(L, j + 1);j--;}}}}```三、链表1. 单链表单链表是一种常见的链式存储结构，每个节点包含数据和指向下一个节点的指针。

习题答案1.填空题（1）序列有序（2）块内无序、块间有序（3）存储地址（4）内部排序、外部排序2.选择题（1）D （2）C （3）A （4）C （5）C （6）C （7）B （8）A3.思考题（1）重复遍历整个序列，从第一个元素开始，两两比较相邻元素的大小，如果反序则交换，直到整个序列变为有序为止。

（2）无序序列：29–18–25–47–58–12–51–10归并排序：第一次归并后的顺序为：18–29–25–47–12–58–10–51第二次归并后的顺序为：18–25–29–47–10–12–51–58第三次归并后的顺序为：10–12–18–25–29–47–51–58快速排序：第一次划分后的顺序为：10–18–25–12–29–58–51–47第二次划分后的顺序为：10–12–18–25–29–58–51–47第三次划分后的顺序为：10–12–18–25–29–47–51–58堆排序：第一次构造大顶堆：58–47–51–29–18–12–25–104.编程题（1）1void Bubble_Sort(int a[], int n){2 int i, j, temp; //定义三个整型变量3 for(j = 0; j < n-1; j++){ //按轮次进行判断4 //每一轮判断完成后，最后一个元素都是当前未排序序列的最大值5 //每一轮排序，未排序的元素都会减16 for(i = 0;i < n-1-j; i++){ //从第一个元素开始依次向后判断7 if(a[i] > a[i+1]){ //判断元素余后一个元素8 temp = a[i]; //数据交换9 a[i] = a[i+1];10 a[i+1] = temp;11 }12 }13 }14}。

附录习题参考答案习题1参考答案1.1.选择题(1). A. (2). A. (3). A. (4). B.,C. (5). A. (6). A. (7). C. (8). A. (9). B. (10.)A.1.2.填空题(1). 数据关系(2). 逻辑结构物理结构(3). 线性数据结构树型结构图结构(4). 顺序存储链式存储索引存储散列表（Hash）存储(5). 变量的取值范围操作的类别(6). 数据元素间的逻辑关系数据元素存储方式或者数据元素的物理关系(7). 关系网状结构树结构(8). 空间复杂度和时间复杂度(9). 空间时间(10). Ο(n)1.3 名词解释如下：数据：数据是信息的载体，是计算机程序加工和处理的对象，包括数值数据和非数值数据。

数据项：数据项指不可分割的、具有独立意义的最小数据单位，数据项有时也称为字段或域。

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

数据逻辑结构：数据的逻辑结构就是指数据元素间的关系。

数据存储结构：数据的物理结构表示数据元素的存储方式或者数据元素的物理关系。

数据类型：是指变量的取值范围和所能够进行的操作的总和。

算法：是对特定问题求解步骤的一种描述，是指令的有限序列。

1.4 语句的时间复杂度为：(1) Ο(n2)(2) Ο(n2)(3) Ο(n2)(4) Ο(n-1)(5) Ο(n3)1.5 参考程序：main(){int X,Y,Z；scanf(“%d, %d, %d”,&X,&Y,Z)；if (X>=Y)if(X>=Z)if (Y>=Z){ printf(“%d, %d, %d”,X,Y,Z);}else{ printf(“%d, %d, %d”,X,Z,Y);}else{ printf(“%d, %d, %d”,Z,X,Y);}elseif(Z>=X)if (Y>=Z){ printf(“%d, %d, %d”,Y,Z,X);}else{ printf(“%d, %d, %d”,Z,Y,X);}else{ printf(“%d, %d, %d”,Y,X,Z);}}1.6 参考程序：main(){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]);p=a[0];for(i=1;i<=n;i++){ p=p+a[i]*x;x=x*x;}printf(“%f”,p)’}习题2参考答案2.1选择题(1). C. (2). B. (3). B. (4). B. 5. D. 6. B. 7. B. 8. A. 9. A. 10. D.2.2.填空题(1). 有限序列(2). 顺序存储和链式存储(3). Ｏ(n) O(n)(4). n-i+1 n-i(5). 链式(6). 数据指针(7). 前驱后继(8). Ο(1) Ο(n)(9). s->next=p->next; p->next=s ;(10). s->next2.3. 解题思路：将顺序表A中的元素输入数组a，若数组a中元素个数为n,将下标为0，1,2,…,（n-1）/2的元素依次与下标为n,n-1,…, （n-1）/2的元素交换，输出数组a的元素。

国家计算机等级考试二级C语言公共基础知识总结第一章数据结构与算法1.1 算法算法：是指解题方案的准确而完整的描述。

算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。

算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。

特征包括：（1）可行性；（2）确定性，算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性；（3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义；（4）拥有足够的情报。

算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。

指令系统：一个计算机系统能执行的所有指令的集合。

基本运算包括：算术运算、逻辑运算、关系运算、数据传输。

算法的控制结构：顺序结构、选择结构、循环结构。

算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。

算法复杂度：算法时间复杂度和算法空间复杂度。

算法时间复杂度是指执行算法所需要的计算工作量。

算法空间复杂度是指执行这个算法所需要的内存空间。

1.2 数据结构的基本基本概念数据结构研究的三个方面：（1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；（2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。

数据结构是指相互有关联的数据元素的集合。

数据的逻辑结构包含：（1）表示数据元素的信息；（2）表示各数据元素之间的前后件关系。

数据的存储结构有顺序、链接、索引等。

线性结构条件：（1）有且只有一个根结点；（2）每一个结点最多有一个前件，也最多有一个后件。

非线性结构：不满足线性结构条件的数据结构。

1．3 线性表及其顺序存储结构线性表是由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。

在复杂线性表中，由若干项数据元素组成的数据元素称为记录，而由多个记录构成的线性表又称为文件。

1.3设n是正整数。

试写出下列程序段中用记号“△”标注的语句的频度：(2) i=1; k=0;do {△k+=10*i;i++;}while(i<=n-1)当n=1时，执行1；当n>=2时，执行n-1次；(3)i=1; k=0;do {△k+ = 10*i; i++;}while(i==n);当n=2时，执行2次；当n!=2时，执行1次；(4) i=1; j=0;while(i+j≤n) {△if(i<j) i++; else j++;}执行n次；(5) x=n; y=0; //n是不小于1的常数while(x>=(y+1)*(y+1)){△y++;}执行向下取整)(6) x=91; y=100;while ( y>0 )△if(x>100) { x-=10; y--; }else x++ ;}If语句执行100次(7) for( i=0; i<n; i++)for( j=i; j<n; j++)for( k=j; k<n; k++)△x+=2;过程：n1n1i0j in(n1)(n2) (n j)6--==++ -=∑∑第二章2.3 已知顺序表La中数据元素按非递减有序排列。

试写一个算法，将元素x插到La的合适位置上，保持该表的有序性。

思路：先判断线性表的存储空间是否满，若满返回Error；否则从后向前先移动数据，找到合适的位置插入。

Status Insert_SqList(SqList &La,int x)//把x 插入递增有序表La 中{if(La.length==La.listsize) return ERROR;for(i=La.length-1;La.elem[i]>x&&i>=0;i--)La.elem[i+1]=La.elem[i];La.elem[i+1]=x;La.length++;return OK;}//Insert_SqList2.5 试写一个算法，实现顺序表的就地逆置，即在原表的存储空间将线性表（a1,a2, ..., an-1,an）逆置为(an,an-1, ..., a2,a1)//思路就是两个指示变量i，j同时分别从顺序表的开始和结尾处相向改变void reverse(SqList &A)//顺序表的就地逆置{ElemType p;for(i=1,j=A.length;i<j;i++,j--){//A.elem[i]<->A.elem[j];p=A.elem[i];A.elem[i[=A.elem[j];A.elem[j]=p;}}//reverse2.7 已知线性表L采用顺序存储结构存放，对两种不同情况分别写出算法，删除L中多余的元素，使得L中没有重复元素：（1）L中数据元素无序排列；(2)L中数据元素非递减有序排列。

严蔚敏《数据结构（c语言版）习题集》算法设计题第九章答案第九章查找int Search_Sq(SSTable ST int key)//在有序表上顺序查找的算法监视哨设在高下标端{ST elem[ST length+ ] key=key;for(i= ;ST elem[i] key>key;i++);if(i>ST length||ST elem[i] keyreturn i;}//Search_Sq分析:本算法查找成功情况下的平均查找长度为ST.length/2,不成功情况下为ST.length.9.26int Search_Bin_Recursive(SSTable ST,int key,int low,int high)//折半查找的递归算法{if(low>high) return 0; //查找不到时返回0mid=(low+high)/2;if(ST.elem[mid].key==key) return mid;else if(ST.elem[mid].key>key)return Search_Bin_Recursive(ST,key,low,mid-1);else return Search_Bin_Recursive(ST,key,mid+1,high);}}//Search_Bin_Recursive9.27int Locate_Bin(SST able ST,int key)//折半查找,返回小于或等于待查元素的最后一个结点号{int *r;r=ST.elem;if(keyelse if(key>=r[ST.length].key) return ST.length;low=1;high=ST.length;while(low<=high){mid=(low+high)/2;if(key>=r[mid].key&&keyreturn mid;else if(keyelse low=mid;} //本算法不存在查找失败的情况,不需要return 0;}//Locate_Bin9.28typedef struct {int maxkey;int firstloc;} Index;typedef struct {int *elem;int length;Index idx[MAXBLOCK]; //每块起始位置和最大元素,其中idx[0]不利用,其内容初始化为{0,0}以利于折半查找int blknum; //块的数目} IdxSqList; //索引顺序表类型int Search_IdxSeq(IdxSqList L,int key)//分块查找,用折半查找法确定记录所在块,块内采用顺序查找法{if(key>L.idx[L.blknum].maxkey) return ERROR; //超过最大元素low=1;high=L.blknum;found=0;while(low<=high&&!found) //折半查找记录所在块号mid{mid=(low+high)/2;if(key<=L.idx[mid].maxkey&&key>L.idx[mid-1].maxkey)found=1;else if(key>L.idx[mid].maxkey)low=mid+1;else high=mid-1;}i=L.idx[mid].firstloc; //块的下界j=i+blksize-1; //块的上界temp=L.elem[i-1]; //保存相邻元素L.elem[i-1]=key; //设置监视哨for(k=j;L.elem[k]!=key;k--); //顺序查找L.elem[i-1]=temp; //恢复元素if(kreturn k;}//Search_IdxSeq分析:在块内进行顺序查找时,如果需要设置监视哨,则必须先保存相邻块的相邻元素,以免数据丢失.9.29typedef struct {LNode *h; //h指向最小元素LNode *t; //t指向上次查找的结点} CSList;LNode *Search_CSList(CSList &L,int key)//在有序单循环链表存储结构上的查找算法,假定每次查找都成功{if(L.t->data==key) return L.t;else if(L.t->data>key)for(p=L.h,i=1;p->data!=key;p=p->next,i++);elsefor(p=L.t,i=L.tpos;p->data!=key;p=p->next,i++);L.t=p; //更新t指针return p;}//Search_CSList分析:由于题目中假定每次查找都是成功的,所以本算法中没有关于查找失败的处理.由微积分可得,在等概率情况下,平均查找长度约为n/3.9.30typedef struct {DLNode *pre;int data;DLNode *next;} DLNode;typedef struct {DLNode *sp;int length;} DSList; //供查找的双向循环链表类型DLNode *Search_DSList(DSList &L,int key)//在有序双向循环链表存储结构上的查找算法,假定每次查找都成功{p=L.sp;if(p->data>key){while(p->data>key) p=p->pre;L.sp=p;}{while(p->data next;L.sp=p;}return p;}//Search_DSList分析:本题的平均查找长度与上一题相同,也是n/3.9.31int last=0,flag=1;int Is_BSTree(Bitree T)//判断二叉树T是否二叉排序树,是则返回1,否则返回0{if(T->lchild&&flag) Is_BSTree(T->lchild);if(T->datalast=T->data;if(T->rchild&&flag) Is_BSTree(T->rchild);return flag;}//Is_BSTree9.32int last=0;void MaxLT_MinGT(BiTree T,int x)//找到二叉排序树T中小于x 的最大元素和大于x的最小元素{if(T->lchild) MaxLT_MinGT(T->lchild,x); //本算法仍是借助中序遍历来实现if(last data>=x) //找到了小于x的最大元素printf("a=%d\n",last);if(last<=x&&T->data>x) //找到了大于x的最小元素printf("b=%d\n",T->data);if(T->rchild) MaxLT_MinGT(T->rchild,x);}//MaxLT_MinGT9.33void Print_NLT(BiTree T,int x)//从大到小输出二叉排序树T中所有不小于x的元素{if(T->rchild) Print_NLT(T->rchild,x);if(T->dataprintf("%d\n",T->data);if(T->lchild) Print_NLT(T->lchild,x); //先右后左的中序遍历}//Print_NLT9.34void Delete_NLT(BiTree &T,int x)//删除二叉排序树T中所有不小于x元素结点,并释放空间{if(T->rchild) Delete_NLT(T->rchild,x);if(T->dataq=T;T=T->lchild;free(q); //如果树根不小于x,则删除树根,并以左子树的根作为新的树根if(T) Delete_NLT(T,x); //继续在左子树中执行算法}//Delete_NLT9.35void Print_Beeen(BiThrTree T,int a,int b)//打印输出后继线索二叉排序树T中所有大于a且小于b的元素{p=T;while(!p->ltag) p=p->lchild; //找到最小元素while(p&&p->data{if(p->data>a) printf("%d\n",p->data); //输出符合条件的元素if(p->rtag) p=p->rtag;else{p=p->rchild;while(!p->ltag) p=p->lchild;} //转到中序后继}//while}//Print_Beeen9.36void BSTree_Insert_Key(BiThrTree &T,int x)//在后继线索二叉排序树T中插入元素x{if(T->data{if(T->rtag) //T没有右子树时,作为右孩子插入{p=T->rchild;q=(BiThrNode*)malloc(sizeof(BiThrNode));q->data=x;T->rchild=q;T->rtag=0;q->rtag=1;q->rchild=p; //修改原线索}else BSTree_Insert_Key(T->rchild,x);//T有右子树时,插入右子树中}//ifelse if(T->data>x) //插入到左子树中{if(!T->lchild) //T没有左子树时,作为左孩子插入{q=(BiThrNode*)malloc(sizeof(BiThrNode));q->data=x;T->lchild=q;q->rtag=1;q->rchild=T; //修改自身的线索}else BSTree_Insert_Key(T->lchild,x);//T有左子树时,插入左子树中}//if}//BSTree_Insert_Key9.37。

数据结构(C语言版)第三版__清华大学出版社_习题参考答案数据结构(C语言版)第三版__清华大学出版社_习题参考答案引言：数据结构是计算机科学的基础，对于学习和理解数据结构的相关概念和算法非常重要。

本文将对清华大学出版社出版的《数据结构(C语言版)第三版》中的习题进行参考答案的提供。

通过正确的理解和掌握这些习题的解答，读者可以加深对数据结构的认识，并提高自己的编程能力。

第一章：绪论1.1 数据结构的定义与作用数据结构是指数据对象以及数据对象之间的关系、运算和存储结构的总称。

数据结构的作用是在计算机中高效地组织和存储数据，同时支持常见的数据操作和算法。

1.2 算法的定义与特性算法是解决特定问题的一系列步骤和规则。

算法具有确定性、有穷性、可行性和输入输出性等特点。

第二章：线性表2.1 线性表的定义和基本操作线性表是同类型数据元素的一个有限序列。

线性表的基本操作包括初始化、查找、插入、删除和遍历等。

2.2 顺序存储结构顺序存储结构是将线性表中的元素按顺序存放在一块连续的存储空间中。

顺序存储结构的特点是随机存取、插入和删除操作需要移动大量元素。

2.3 链式存储结构链式存储结构通过结点之间的指针链表来表示线性表。

链式存储结构的特点是插入和删除操作方便，但查找操作需要遍历整个链表。

第三章：栈和队列3.1 栈的定义和基本操作栈是只能在一端进行插入和删除操作的线性表。

栈的基本操作包括初始化、入栈、出栈和获取栈顶元素等。

3.2 队列的定义和基本操作队列是只能在一端插入操作，在另一端进行删除操作的线性表。

队列的基本操作包括初始化、入队、出队和获取队头元素等。

第四章：串4.1 串的定义和基本操作串是由零个或多个字符组成的有限序列。

串的基本操作包括初始化、串的赋值、串的连接和串的比较等。

第五章：树5.1 树的基本概念和术语树是n（n>=0）个结点的有限集。

树的基本概念包括根结点、子树、深度和高度等。

5.2 二叉树二叉树是每个结点最多有两个子树的树结构。

第6章 树和二叉树（参考答案）6.1(1)根结点a6.2三个结点的树的形态： 三个结点的二叉树的形态：（1） （1） （2） （4） （5）6．3 设树的结点数是n ，则n=n0+n1+n2+……+nm+ (1)设树的分支数为B ，有n=B+1n=1n1+2n2+……+mnm+1 (2)由（1）和（2）有：n0=n2+2n3+……+(m-1)nm+16.4(1) k i-1 (i 为层数)(2) (n-2)/k+1(3) (n-1)*k+i+1(4) (n-1)%k !=0; 其右兄弟的编号 n+16.5（1）顺序存储结构注：#为空结点6.6(1) 前序 ABDGCEFH(2) 中序 DGBAECHF(3) 后序 GDBEHFCA6.7(1) 空二叉树或任何结点均无左子树的非空二叉树(2) 空二叉树或任何结点均无右子树的非空二叉树(3) 空二叉树或只有根结点的二叉树6.8int height(bitree bt)// bt是以二叉链表为存储结构的二叉树，本算法求二叉树bt的高度{ int bl,br; // 局部变量，分别表示二叉树左、右子树的高度if (bt==null) return(0);else { bl=height(bt->lchild);br=height(bt->rchild);return(bl>br? bl+1: br+1); // 左右子树高度的大者加1（根） }}// 算法结束6.9void preorder(cbt[],int n,int i);// cbt是以完全二叉树形式存储的n个结点的二叉树，i是数// 组下标，初始调用时为1。

本算法以非递归形式前序遍历该二叉树{ int i=1,s[],top=0; // s是栈，栈中元素是二叉树结点在cbt中的序号 // top是栈顶指针，栈空时top=0if (n<=0) { printf(“输入错误”);exit（0）；}while (i<=n ||top>0){ while(i<=n){visit(cbt[i]); // 访问根结点if (2*i+1<=n) s[++top]=2*i+1; //若右子树非空，其编号进栈i=2*i;// 先序访问左子树}if (top>0) i=s[top--]; // 退栈，先序访问右子树} // END OF while (i<=n ||top>0)}// 算法结束//以下是非完全二叉树顺序存储时的递归遍历算法，“虚结点”用‘*’表示void preorder(bt[],int n,int i);// bt是以完全二叉树形式存储的一维数组，n是数组元素个数。

第1章绪论5．： CCBDCA6．剖析下边各程序段的复度。

（1）O（1）（2）O（m*n ）（3）O（n2）（4）O（log 3n）（ 5）因 x++ 共行了n-1+n-2+ ⋯⋯＋ 1= n(n-1)/2 ，因此行O（ n2）（ 6）O(n )第 2章线性表1．babadbcabdcddac2．算法（6）一个算法，通一趟遍在表中确立最大的点。

ElemType Max (LinkList L ){if(L->next==NULL) return NULL;pmax=L->next;法（ 2）回文是指正反均同样的字符序列，如“abba”和“abdba”均是回文，但“good”不是回文。

写一个算法判断定的字符向量能否回文。

(提示：将一半字符入)?依据提示，算法可设计为：（ 1）已知模式串合用t= ‘ abcaabbabcab ’写出用KMP法求得的每个字符的模式串 t 的 next 和 nextval以下：next和nextval函数。

j 1 2 3 4 5 67 8910 11 12 t 串 a b c a a b b a b c a b next[j]0 1 1 1 2 2 3 1 2 345 nextval[j]0 1 1 0 2 1 3 0 1 105（ 3）数 A 中，每个元素A[i,j]的度均32 个二位 , 行下从 -1 到 9，列下从 1 到开始寄存主存器中，主存器字16 位。

求：① 寄存数所需多少元？②寄存数第 4 列全部元素起码需多少元？③数按行寄存，元素A[7,4]的开端地点是多少？④数按列寄存，元素A[4,7]的开端地点是多少？每个元素32 个二制位，主存字16 位，故每个元素占 2 个字，行下可平移至（ 1） 242（2）22（3）s+182（4）s+142(4) 将香蕉banana 用工具 H( )—Head( )，T( )—Tail( )从L中拿出。

11，从首地点1到 11。

第1 章绪论5．选择题：C CBDCA6．试分析下面各程序段的时间复杂度。

（1）O（1）（2）O（m*n）（3）O（n2）（4）O（log3n）O（n （5）因为x++ 共执行了n-1+n-2+⋯⋯＋1= n(n-1)/2 ，所以执行时间为2）（6）O( n )第2 章线性表1．选择题babadbcabdcddac2．算法设计题（6）设计一个算法，通过一趟遍历在单链表中确定值最大的结点。

ElemType Max (LinkList L ){if(L->next==NULL) return NULL;pmax=L->next; // 假定第一个结点中数据具有最大值p=L->next->next;while(p != NULL ){// 如果下一个结点存在if(p->data > pmax->data) pmax=p;p=p->next;}return pmax->data;原表（7）设计一个算法，通过遍历一趟，将链表中所有结点的链接方向逆转，仍利用的存储空间。

void inverse(LinkList &L) {// 逆置带头结点的单链表Lp=L->next; L->next=NULL;while ( p) {q=p->next; // q 指向*p 的后继p->next=L->next;L->next=p; // *p 插入在头结点之后p = q;}}（10）已知长度为n 的线性表 A 采用顺序存储结构，请写一时间复杂度为O (n) 、空间复杂度为O (1) 的算法，该算法删除线性表中所有值为item 的数据元素。

[ 题目分析] 在顺序存储的线性表上删除元素，通常要涉及到一系列元素的移动（删第i 个元素，第i+1 至第n 个元素要依次前移）。

本题要求删除线性表中所有值为item 的数据元素，并未要求元素间的相对位置不变。