c语言数据结构题集解答集.doc

佳构文档
你我共享
天佑自助者，你要你就能。
第1章绪论
1.1简述以下术语：数据
数据元素、数据工具、数据结构、存储结构、数据范例跟笼统数据范例
解：数据是对客不雅事物的标记表现
在盘算机迷信中是指一切能输入到盘算机中并被盘算机次序处置的标记的总称
数据元素是数据的根本单位
在盘算机次序中平日作为一个全体进展思索跟处置
数据工具是性子一样的数据元素的聚集
是数据的一个子集
数据结构是互相之间存在一种或多种特定关联的数据元素的聚集
存储结构是数据结构在盘算机中的表现
数据范例是一个值的聚集跟界说在那个值集上的一组操纵的总称
笼统数据范例是指一个数学模子以及界说在该模子上的一组操纵
是对普通数据范例的扩年夜
1.2试描绘数据结构跟笼统数据范例的不雅点与次序计划言语中数据范例不雅点的区不
解：笼统数据范例包含普通数据范例的不雅点
但含意比普通数据范例更广、更笼统
普通数据范例由详细言语零碎外部界说
直截了当供给应编程者界说用户数据
因而称它们为预约义数据范例
笼统数据范例平日由编程者界说
包含界说它所运用的数据跟在这些数据上所进展的操纵
在界说笼统数据范例中的数据部分跟操纵部分时
请求只界说到数据的逻辑结构跟操纵阐明
不思索数据的存储结构跟操纵的详细实现
如斯笼统档次更高
更能为其余用户供给精良的运用接口
1.3设有数据结构(D
R)
此中
AAAAAA

佳构文档
你我共享
试按图论中图的画法常规画出其逻辑结构图
解：
1.4试模仿三元组的笼统数据范例分不写出笼统数据范例单数跟有理数的界说〔有理数是其
分子、分母均为天然数且分母不为零的分数〕
解：
ADTComplex{
数据工具：D={r
i|r
i为实数}
数据关联：R={<r
i>}
根本操纵：
InitComplex(&C
re
im)
操纵后果：结构一个单数
C
事实上部跟虚部分不为
re跟im
DestroyCmoplex(&C)
操纵后果：烧毁单数
C
Get(C
k
&e)
操纵后果：用e前往单数C的第k元的值
Put(&C
k
e)
操纵后果：改动单数
C的第k元的值为e
IsAscending(C)
操纵后果：假如单数
C的两个元素按升序陈列
那么前往1
否那么前往0
IsDescending(C)
操纵后果：假如单数
C的两个元素按落序陈列
那么前往1
否那么前往0
Max(C
&e)
操纵后果：用e前往单数C的两个元素中值较年夜的一个
Min(C
AAAAAA

佳构文档
你我共享
&e)
操纵后果：用e前往单数C的两个元素中值较小的一个
}ADTComplex
ADTRationalNumber{
数据工具：D={s
m|s
m为天然数
且m不为0}
数据关联：R={<s
m>}
根本操纵：
InitRationalNumber(&R
s
m)
操纵后果：结构一个有理数
R
其分子跟分母分不为
s跟m
DestroyRationalNumber(&R)
操纵后果：烧毁有理数
R
Get(R
k
&e)
操纵后果：用e前往有理数R的第k元的值
Put(&R
k
e)
操纵后果：改动有理数
R的第k元的值为e
IsAscending(R)
操纵后果：假设有理数
R的两个元素按升序陈列
那么前往1
否那么前往0
IsDescending(R)
操纵后果：假设有理数
R的两个元素按落序陈列
那么前往1
否那么前往0
Max(R
&e)
操纵后果：用e前往有理数R的两个元素中值较年夜的一个
Min(R
&e)
操纵后果：用e前往有理数R的两个元素中值较小的一个
}ADTRationalNumber
1.5试画出与以下次序段等价的框图
AAAAAA

佳构文档
你我共享
(1)product=1;i=1;
while(i<=n){
product*=i;
i++;
}
(2)i=0;
do{
i++;
}while((i!=n)&&(a[i]!=x));
(3)switch{
casex<y:z=y-x;break;
casex=y:z=abs(x*y);break;
default:z=(x-y)/abs(x)*abs(y);
}
1.6在次序计划中
常用以下三种差其余犯错处置方法：
(1)
(2)
(3)
用exit语句停止履行并讲演过错；
以函数的前往值区不准确前往或过错前往；
设置一个整型变量的函数参数以区不准确前往或某种过错前往
试探讨这三种办法各自的优缺陷
解：(1)exit
常用于异样过错处置
它能够强行中缀次序的履行
前往操纵零碎
(2)
以函数的前往值推断准确与否常用于子次序的测试
便于实现次序的部分操纵
(3)
用整型函数进展过错处置的长处是能够给犯过错范例
便于敏捷断定过错
1.7在次序计划中
可采纳以下三种办法实现输入跟输入：
(1)
(2)
(3)
经过scanf跟printf
语句；
经过函数的参数显式通报；
经过全局变量隐式通报
试探讨这三种办法的优缺陷
解：(1)用scanf跟printf
直截了当进展输入输入的益处是笼统、直不雅
但缺陷是需求对其进展格局操纵
AAAAAA

佳构文档
你我共享
较为繁缛
假如呈现过错
那么会惹起全部零碎的解体
(2)
经过函数的参数通报进展输入输入
便于实现信息的荫蔽
增加犯错的能够
(3)
经过全局变量的隐式通报进展输入输入最为便利
只要修正变量的值即可
但过多的全局变量使次序的保护较为艰苦
1.8设n为正整数
试断定以下各次序段中前置以暗号
(1)i=1;k=0;
while(i<=n-1){
k+=10*i;
i++;
的语句的频度：
}
(2)i=1;k=0;
do{
k+=10*i;
i++;
}while(i<=n-1);
(3)i=1;k=0;
while(i<=n-1){
i++;
k+=10*i;
}
(4)k=0;
for(i=1;i<=n;i++){
for(j=i;j<=n;j++)
k++;
}
(5)for(i=1;i<=n;i++){
for(j=1;j<=i;j++){
for(k=1;k<=j;k++)
x+=delta;
}
(6)i=1;j=0;
while(i+j<=n){
if(i>j)j++;
elsei++;
AAAAAA

佳构文档
你我共享
}
(7)x=n;y=0;//n
while(x>=(y+1)*(y+1)){
y++;
是不小于1的常数
}
(8)x=91;y=100;
while(y>0){
if(x>100){x-=10;y--;}
elsex++;
}
解：(1)n-1
(2)n-1
(3)n-1
(4)n+(n-1)+(n-2)+...+1=
(5)1+(1+2)+(1+2+3)+...+(1+2+3+...+n)=
=
=
(6)n
(7)
向下取整
(8)1100
1.9假设n为2的乘幂
同时n>2
试求以下算法的时间庞杂度及变量
count的值〔以n的函数方法表现〕
intTime(intn){
count=0;
x=2;
while(x<n/2){
x*=2;count++;
}
returncount;
}
解：
count=
1.11曾经明白有实现统一功用的两个算法
其时间庞杂度分不为跟
假设理想盘算机可延续运算的时间为秒〔
100多天〕
又每秒可履行根本操纵〔依照这些操纵来预算算法时间庞杂度〕次
试咨询在此前提下
这两个算法可解咨询题的范围〔即
n值的范畴〕各为几多？哪个算法更适合？请阐明来由
解：
n=40
n=16
那么对于异样的轮回次数
n
AAAAAA

佳构文档
你我共享
在那个范围下
第二种算法所破费的价值要年夜得多
故在那个范围下
第一种算法更适合
1.12设有以下三个函数：
请推断以下断言准确与否：
(1)f(n)
(2)h(n)
(3)g(n)
(4)h(n)
(5)h(n)
是O(g(n))
是O(f(n))
是O(h(n))
是O(n3.5)
是O(nlogn)
解：(1)对(2)错(3)错(4)对(5)错
1.13试设定假设干n值
比拟两函数跟的增加趋向
并断定n在什么范畴内
函数的值年夜于的值
解：的增加趋向快
但在n较小的时分
的值较年夜
当n>438时
1.14推断以下各对函数跟
事先
哪个函数增加更快？
(1)
(2)
(3)
(4)
解：(1)g(n)快(2)g(n)快(3)f(n)快(4)f(n)
快
1.15试用数学归结法证实：
(1)
(2)
(3)
AAAAAA

佳构文档
你我共享
(4)
1.16试写一算法
自卑至小顺次输入次序读入的三个整数
X
Y跟Z的值
解：
intmax3(intx
inty
intz)
{
if(x>y)
if(x>z)returnx;
elsereturnz;
else
if(y>z)returny;
elsereturnz;
}
1.17曾经明白k阶斐波那契序列的界说为
...
；
试编写求k阶斐波那契序列的第m项值的函数算法
k跟m均以值挪用的方法在函数参数表中呈现
解：k>0为阶数
n为数列的第n项
intFibonacci(intk
intn)
{
if(k<1)exit(OVERFLOW);
int*p
x;
p=newint[k+1];
if(!p)exit(OVERFLOW);
inti
j;
for(i=0;i<k+1;i++){
if(i<k-1)p[i]=0;
elsep[i]=1;
}
AAAAAA

佳构文档
你我共享
for(i=k+1;i<n+1;i++){
x=p[0];
for(j=0;j<k;j++)p[j]=p[j+1];
p[k]=2*p[k-1]-x;
}
returnp[k];
}
1.18假设有A
B
C
D
E五个初等院校进展田径对破赛
各院校的单项成果均已存入盘算机
并形成一张表
表中每一行的方法为
工程称号
性不
校名
成果
得分
编写算法
处置上述表格
以统计各院校的男、女总分跟集团总分
并输入
解：
typedefenum{A
B
C
D
E}SchoolName;
typedefenum{Female
Male}SexType;
typedefstruct{
charevent[3];//
SexTypesex;
SchoolNameschool;
intscore;
工程
}Component;
typedefstruct{
intMaleSum;
//男团总分
intFemaleSum;
intTotalSum;
//女团总分
//集团总分
AAAAAA

佳构文档
你我共享
}Sum;
SumSumScore(SchoolNamesn
Componenta[]
intn)
{
Sumtemp;
temp.MaleSum=0;
temp.FemaleSum=0;
temp.TotalSum=0;
inti;
for(i=0;i<n;i++){
if(a[i].school==sn){
if(a[i].sex==Male)temp.MaleSum+=a[i].score;
if(a[i].sex==Female)temp.FemaleSum+=a[i].score;
}
}
temp.TotalSum=temp.MaleSum+temp.FemaleSum;
returntemp;
}
1.19试编写算法
盘算的值并存入数组
a[0..arrsize-1]
的第i-1个重量中(i=1
2
...
n)
假设盘算机中同意的整数最年夜值为
那么当n>arrsize或对某个
使时
maxint
应按犯错处置
留意选择你认为较好的犯错处置办法
解：
#include<iostream.h>
#include<stdlib.h>
#defineMAXINT65535
#defineArrSize100
intfun(inti);
intmain()
{
inti
k;
inta[ArrSize];
cout<<"Enterk:";
AAAAAA

佳构文档
你我共享
cin>>k;
if(k>ArrSize-1)exit(0);
for(i=0;i<=k;i++){
if(i==0)a[i]=1;
else{
if(2*i*a[i-1]>MAXINT)exit(0);
elsea[i]=2*i*a[i-1];
}
}
for(i=0;i<=k;i++){
if(a[i]>MAXINT)exit(0);
elsecout<<a[i]<<"";
}
return0;
}
1.20试编写算法求一元多项式的值的值
并断定算法中每一语句的履行次数跟全部算法的时间庞杂度
留意选择你认为较好的输入跟输入办法
此题的输入为
跟
输入为
解：
#include<iostream.h>
#include<stdlib.h>
#defineN10
doublepolynomail(inta[]
inti
doublex
intn);
intmain()
{
doublex;
intn
i;
inta[N];
cout<<"输入变量的值x:";
cin>>x;
cout<<"输入多项式的阶次n:";
cin>>n;
if(n>N-1)exit(0);
cout<<"输入多项式的系数a[0]--a[n]:";
for(i=0;i<=n;i++)cin>>a[i];
AAAAAA

佳构文档
你我共享
cout<<"Thepolynomailvalueis"<<polynomail(a
n
x
n)<<endl;
return0;
}
doublepolynomail(inta[]
inti
doublex
intn)
{
if(i>0)returna[n-i]+polynomail(a
i-1
x
n)*x;
elsereturna[n];
}
本算法的时间庞杂度为
o(n)
第2章线性表
2.1描绘以下三个不雅点的区不：头指针
头结点
首元结点〔第一个元素结点〕
解：头指针是指向链表中第一个结点的指针
首元结点是指链表中存储第一个数据元素的结点
头结点是在首元结点之前附设的一个结点
该结点不存储数据元素
其指针域指向首元结点
其感化要紧是为了便利对链表的操纵
它能够对空表、非空表以及首元结点的操纵进展一致处置
2.2填空题
解：(1)在次序表中拔出或删除一个元素
需求均匀挪动表中一半元素
详细挪动的元素个数与元素在表中的地位有关
(2)
次序表中逻辑上相邻的元素的物理地位肯定紧邻
单链表中逻辑上相邻的元素的物理地位不必定紧邻
(3)
在单链表中
除了首元结点外
AAAAAA

佳构文档
你我共享
任一结点的存储地位由其先驱结点的链域的值唆使
(4)
在单链表中设置头结点的感化是拔出跟删除首元结点时不必进展专门处置
2.3在什么状况下用次序表比链表好？
解：当线性表的数据元素在物理地位上是延续存储的时分
用次序表比用链表好
其特色是能够进展随机存取
2.4对以下单链表分不履行以下各次序段
并画出后果表现图
解：
2.5画出履行以下各行语句后各指针及链表的表现图
L=(LinkList)malloc(sizeof(LNode));
for(i=1;i<=4;i++){
P=L;
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结点既不是首元结点
也不是尾元结点
试从以下供给的谜底当选择适合的语句序列
AAAAAA

佳构文档
你我共享
a.
b.
c.
d.
在P结点后拔出S结点的语句序列是__________________
在P结点前拔出S结点的语句序列是__________________
在表首拔出S结点的语句序列是__________________
在表尾拔出S结点的语句序列是__________________
(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;
解：a.(4)(1)
b.(7)(11)(8)(4)(1)
c.(5)(12)
d.(9)(1)(6)
2.7曾经明白L是带表头结点的非空单链表
且P结点既不是首元结点
也不是尾元结点
试从以下供给的谜底当选择适合的语句序列
a.
b.
c.
d.
删除P结点的直截了当后继结点的语句序列是
删除P结点的直截了以后驱结点的语句序列是
____________________
____________________
删除P结点的语句序列是____________________
删除首元结点的语句序列是
删除尾元结点的语句序列是
____________________
____________________
e.
(1)P=P->next;
(2)P->next=P;
AAAAAA

佳构文档
你我共享
(3)P->next=P->next->next;
(4)P=P->next->next;
(5)while(P!=NULL)P=P->next;
(6)while(Q->next!=NULL){P=Q;Q=Q->next;}
(7)while(P->next!=Q)P=P->next;
(8)while(P->next->next!=Q)P=P->next;
(9)while(P->next->next!=NULL)P=P->next;
(10)Q=P;
(11)Q=P->next;
(12)P=L;
(13)L=L->next;
(14)free(Q);
解：a.(11)(3)(14)
b.(10)(12)(8)(3)(14)
c.(10)(12)(7)(3)(14)
d.(12)(11)(3)(14)
e.(9)(11)(3)(14)
2.8曾经明白P结点是某双向链表的两头结点
试从以下供给的谜底当选择适合的语句序列
a.
b.
c.
d.
e.
在P结点后拔出S结点的语句序列是_______________________
在P结点前拔出S结点的语句序列是_______________________
删除P结点的直截了当后继结点的语句序列是
删除P结点的直截了以后驱结点的语句序列是
_______________________
_______________________
删除P结点的语句序列是_______________________
(1)P->next=P->next->next;
(2)P->priou=P->priou->priou;
(3)P->next=S;
(4)P->priou=S;
(5)S->next=P;
(6)S->priou=P;
(7)S->next=P->next;
(8)S->priou=P->priou;
(9)P->priou->next=P->next;
(10)P->priou->next=P;
(11)P->next->priou=P;
(12)P->next->priou=S;
(13)P->priou->next=S;
AAAAAA

佳构文档
你我共享
(14)P->next->priou=P->priou;
(15)Q=P->next;
(16)Q=P->priou;
(17)free(P);
(18)free(Q);
解：a.(7)(3)(6)(12)
b.(8)(4)(5)(13)
c.(15)(1)(11)(18)
d.(16)(2)(10)(18)
e.(14)(9)(17)
2.9简述以下算法的功用
(1)StatusA(LinkedListL){//L
是无表头结点的单链表
if(L&&L->next){
Q=L;
L=L->next;
P=L;
while(P->next)P=P->next;
P->next=Q;
Q->next=NULL;
}
returnOK;
}
(2)voidBB(LNode*s
LNode*q){
p=s;
while(p->next!=q)p=p->next;
p->next=s;
}
voidAA(LNode*pa
LNode*pb){
//pa跟pb分不指向单轮回链表中的两个结点
BB(pa
pb);
pa);
BB(pb
}
解：(1)假如L的长度不小于2
将L的首元结点酿成尾元结点
(2)
将单轮回链表拆成两个单轮回链表
2.10指出以下算法中的过错跟低效之处
并将它改写为一个既准确又高效的算法
StatusDeleteK(SqList&a
AAAAAA

佳构文档
你我共享
inti
intk)
{
//本进程从次序存储结构的线性表
a中删除第i个元素起的k个元素
if(i<1||k<0||i+k>a.length)returnINFEASIBLE;//
else{
参数分歧法
for(count=1;count<k;count++){
//删除第一个元素
for(j=a.length;j>=i+1;j--)a.elem[j-i]=a.elem[j];
a.length--;
}
returnOK;
}
解：
StatusDeleteK(SqList&a
inti
intk)
{
//从次序存储结构的线性表
//留意i的编号从0开场
intj;
a中删除第i个元素起的k个元素
if(i<0||i>a.length-1||k<0||k>a.length-i)returnINFEASIBLE;
for(j=0;j<=k;j++)
a.elem[j+i]=a.elem[j+i+k];
a.length=a.length-k;
returnOK;
}
2.11设次序表va中的数据元素递增有序
试写一算法
将x拔出到次序表的恰当地位上
以坚持该表的有序性
解：
StatusInsertOrderList(SqList&va
ElemTypex)
{
//在非递加的次序表va中拔出元素x并使其仍成为次序表的算法
inti;
if(va.length==va.listsize)return(OVERFLOW);
for(i=va.length;i>0
x<va.elem[i-1];i--)
va.elem[i]=va.elem[i-1];
va.elem[i]=x;
AAAAAA

佳构文档
你我共享
va.length++;
returnOK;
}
2.12设跟均为次序表
跟分不为跟中撤除最年夜独特前缀后的子表
假设空表
那么；假设=空表
而空表
或许两者均不为空表
且的首元小于的首元
那么；否那么
试写一个比拟
巨细的算法
解：
StatusCompareOrderList(SqList&A
SqList&B)
{
inti
k
j;
k=A.length>B.lengthA.length:B.length;
for(i=0;i<k;i++){
if(A.elem[i]>B.elem[i])j=1;
if(A.elem[i]<B.elem[i])j=-1;
}
if(A.length>k)j=1;
if(B.length>k)j=-1;
if(A.length==B.length)j=0;
returnj;
}
2.13试写一算法在带头结点的单链表结构上实现线性表操纵
Locate(L
x);
解：
intLocateElem_L(LinkList&L
ElemTypex)
{
inti=0;
LinkListp=L;
while(p&&p->data!=x){
p=p->next;
i++;
}
AAAAAA

佳构文档
你我共享
if(!p)return0;
elsereturni;
}
2.14试写一算法在带头结点的单链表结构上实现线性表操纵
Length(L)
解：
//前往单链表的长度
intListLength_L(LinkList&L)
{
inti=0;
LinkListp=L;
if(p)p=p-next;
while(p){
p=p->next;
i++;
}
returni;
}
2.15曾经明白指针ha跟hb分不指向两个单链表的头结点
同时曾经明白两个链表的长度分不为
m跟n
试写一算法将这两个链表衔接在一同
假设指针hc指向衔接后的链表的头结点
并请求算法以尽能够短的时间实现衔接运算
请剖析你的算法的时间庞杂度
解：
voidMergeList_L(LinkList&ha
LinkList&hb
LinkList&hc)
{
LinkListpa
pb;
pa=ha;
pb=hb;
while(pa->next&&pb->next){
pa=pa->next;
pb=pb->next;
}
if(!pa->next){
hc=hb;
while(pb->next)pb=pb->next;
pb->next=ha->next;
}
AAAAAA

佳构文档
你我共享
else{
hc=ha;
while(pa->next)pa=pa->next;
pa->next=hb->next;
}
}
2.16曾经明白指针la跟lb分不指向两个无头结点单链表中的首元结点
以下算法是从表la中删除自第i个元素起共len个元素后
将它们拔出到表lb中第i个元素之前
试咨询此算法是否准确？假设有错
请矫正之
StatusDeleteAndInsertSub(LinkedListla
LinkedListlb
inti
intj
intlen)
{
if(i<0||j<0||len<0)returnINFEASIBLE;
p=la;
k=1;
while(k<i){p=p->next;
q=p;
k++;
}
}
while(k<=len){
q=q->next;
k++;
}
s=lb;k=1;
while(k<j){s=s->next;
s->next=p;q->next=s->next;
returnOK;
k++;
}
解：
StatusDeleteAndInsertSub(LinkList&la
LinkList&lb
inti
intj
intlen)
{
LinkListp
q
s
prev=NULL;
intk=1;
if(i<0||j<0||len<0)returnINFEASIBLE;
//在la表中查寻第i个结点
p=la;
AAAAAA

佳构文档
你我共享
while(p&&k<i){
prev=p;
p=p->next;
k++;
}
if(!p)returnINFEASIBLE;
//在la表中查寻第i+len-1个结点
q=p;
k=1;
while(q&&k<len){
q=p->next;
k++;
}
if(!q)returnINFEASIBLE;
//实现删除
留意
i=1的状况需求专门处置
if(!prev)la=q->next;
elseprev->next=q->next;
//将从la中删除的结点拔出到lb中
if(j=1){
q->next=lb;
lb=p;
}
else{
s=lb;
k=1;
while(s&&k<j-1){
s=s->next;
k++;
}
if(!s)returnINFEASIBLE;
q->next=s->next;
s->next=p;//
实现拔出
}
returnOK;
}
2.17试写一算法
在无头结点的静态单链表上实现线性表操纵
Insert(L
i
b)
并跟在带头结点的静态单链表上实现一样操纵的算法进展比拟
2.18试写一算法
实现线性表操纵Delete(L
AAAAAA

佳构文档
你我共享
i)
并跟在带头结点的静态单链表上实现一样操纵的算法进展比拟
2.19曾经明白线性表中的元素以值递增有序陈列
并以单链表作存储结构
试写一高效的算法
删除表中一切值年夜于
mink且小于maxk的元素〔假设表中存在如斯的元素〕
同时开释被删结点空间
并剖析你的算法的时间庞杂度〔留意
mink跟maxk是给定的两个参变量
它们的值能够跟表中的元素一样
也能够差别〕
解：
StatusListDelete_L(LinkList&L
ElemTypemink
ElemTypemaxk)
{
LinkListp
q
prev=NULL;
if(mink>maxk)returnERROR;
p=L;
prev=p;
p=p->next;
while(p&&p->data<maxk){
if(p->data<=mink){
prev=p;
p=p->next;
}
else{
prev->next=p->next;
q=p;
p=p->next;
free(q);
}
}
returnOK;
}
2.20同2.19题前提
试写一高效的算法
删除表中一切值一样的过剩元素〔使得操纵后的线性表中一切元素的值均纷歧样〕
同时开释被删结点空间
AAAAAA

佳构文档
你我共享
并剖析你的算法的时间庞杂度
解：
voidListDelete_LSameNode(LinkList&L)
{
LinkListp
q
prev;
p=L;
prev=p;
p=p->next;
while(p){
prev=p;
p=p->next;
if(p&&p->data==prev->data){
prev->next=p->next;
q=p;
p=p->next;
free(q);
}
}
}
2.21试写一算法
实现次序表的当场逆置
即应用原表的存储空间将线性表逆置为
解：
//次序表的逆置
StatusListOppose_Sq(SqList&L)
{
inti;
ElemTypex;
for(i=0;i<L.length/2;i++){
x=L.elem[i];
L.elem[i]=L.elem[L.length-1-i];
L.elem[L.length-1-i]=x;
}
returnOK;
}
2.22试写一算法
对单链表实现当场逆置
解：
AAAAAA

佳构文档
你我共享
//带头结点的单链表的逆置
StatusListOppose_L(LinkList&L)
{
LinkListp
q;
p=L;
p=p->next;
L->next=NULL;
while(p){
q=p;
p=p->next;
q->next=L->next;
L->next=q;
}
returnOK;
}
2.23设线性表
试写一个按以下规那么兼并
B为线性表C的算法
即便得
A
事先；
事先
线性表A
B跟C均以单链表作存储结构
且C表应用A表跟B表中的结点空间形成
留意：单链表的长度值
m跟n均未显式存储
解：
//将兼并后的后果放在C表中
并删除B表
StatusListMerge_L(LinkList&A
LinkList&B
LinkList&C)
{
LinkListpa
pb
qa
qb;
pa=A->next;
pb=B->next;
C=A;
AAAAAA

佳构文档
你我共享
while(pa&&pb){
qa=pa;
qb=pb;
pa=pa->next;
pb=pb->next;
qb->next=qa->next;
qa->next=qb;
}
if(!pa)qb->next=pb;
pb=B;
free(pb);
returnOK;
}
2.24假设有两个按元素值递增有序陈列的线性表
A跟B
均以单链表作存储结构
请编写算法将A表跟B表合并成一个按元素值递加有序〔即非递增有序
同意表中含有值一样的元素〕陈列的线性表
C
并请求应用原表〔即
A表跟B表〕的结点空间结构C表
解：
//将兼并逆置后的后果放在
并删除B表
C表中
StatusListMergeOppose_L(LinkList&A
LinkList&B
LinkList&C)
{
LinkListpa
pb
qa
qb;
pa=A;
pb=B;
qa=pa;
qb=pb;
//保管pa的先驱指针
//保管pb的先驱指针
pa=pa->next;
pb=pb->next;
A->next=NULL;
C=A;
while(pa&&pb){
if(pa->data<pb->data){
qa=pa;
pa=pa->next;
qa->next=A->next;
A->next=qa;
//将以后最小结点拔出A表表头
}
AAAAAA

佳构文档
你我共享
else{
qb=pb;
pb=pb->next;
qb->next=A->next