#include
#include
double function1(double x)//被积函数
{
double s;
s=x/(4+x*x);
return s;
}
double function2(double x)//被积函数
{
double s;
s=sqrt(x);
return s;
}
double ReiterationOfTrapezoidal(double a,double b,double n,double f(double x))//复化梯形公式
{
double h,fa,fb,xk,t;
h=(b-a)/n;//步长
fa=f(a);
fb=f(b);
double s=0.0;
for(int k=1;k
xk=a+k*h;
s=s+f(xk);
}
t=h*(fa+fb)/2+h*s;//复化梯形公式
return t;
}
double ReiterationOfSimpson(double a,double b,double n,double f(double x))//复化Simpson公式
{
double h,fa,fb,xk,xj;
h=(b-a)/n;
fa=f(a);
fb=f(b);
double s1=0.0;
double s2=0.0;
for(int k=1;k
xk=a+k*h;
s1=s1+f(xk);
}
for(int j=0;j
xj=a+(j+0.5)*h;
s2=s2+f(xj);
}
double sn;//和
sn=h/6*(fa+fb+2*s1+4*s2);//复化Simpson公式
return sn;
}
main()
{
double a,b,Result,n;
/*第一小题*/
cout<<"请输入第一小题积分下限:"<
cout<<"请输入第一小题积分上限:"<
cout<<"请输入第一小题分割区间数n:"<
cout<<"第一小题复化梯形公式计算结果:";
Result=ReiterationOfTrapezoidal(a, b, n,function1);
cout<
cout<<"第一小题复化Simpson公式计算结果:";
Result=ReiterationOfSimpson(a, b, n,function1);
cout<
/*第二小题*/
cout<<"请输入第二小题积分下限:"<
cout<<"请输入第二小题积分上限:"<
cout<<"请输入第二小题分割区间数n:"<
cout<<"第二小题复化梯形公式计算结果:";
Result=ReiterationOfTrapezoidal(a, b, n,function2);
cout<
cout<<"第二小题复化Simpson公式计算结果:";
Result=ReiterationOfSimpson(a, b, n,function2);
cout<
}
本文来自CSDN博客，转载请标明出处：https://www.doczj.com/doc/9816969883.html,/liuhongyi666/archive/2008/12/22/3584482.aspx
#include
#include
float N,A,B,X;
float F(float x);
float Ti() //复化梯形公式
{
float i,n,h,t,g=0;
n=N;
h=(B-A)/n;
for(i=1;i
g=F(X)+g;
}
t=h*(F(A)+2*g+F(B))/2;
return(t);
}
float Si() //复化辛普生公式
{float i,n,h,t,p=0,g=0;
n=N;
h=(B-A)/n;
for(i=1;i<(1+n/2);i=i+2)
{X=A+i*h;
g=F(X)+g;
}
i=0;
for(i=2;i<(n/2);i=i+2)
{X=A+i*h;
p=F(X)+p;
}
t=h*(F(A)+4*g+2*p+F(B))/3;
return(t);
}
float F(float x) //被积分函数f(x)
{float
f;
f=4/(1+x*x);
return(f);
}
double main() //主函数
{float z;
int i;
loop:printf("\n\n\n1为复化梯形公式,2为复化辛普生公式.\n请输入你要用的公式的代码:\n");
scanf("%d",&i);
if(i!=1&&i!=2)
{printf("输入错误代码!");
goto loop;
}
else {printf("输入积分上下限:\n");
scanf("%f%f",&A,&B);
printf("\n输入子区间个数:\n");
scanf("%f",&N);
// printf("\n\n%f,%f,%f",A,B,N);
if(i==1)
{z=Ti();
printf("利用复化梯形公式计算");
}
else if(i==2)
{z=Si();
printf("利用复化辛普生公式计算");
}
printf("结果为:%f",z);
goto loop;
getch(); /* 此语句请不要删除*/
}
return 0;
}
typedef struct node
{
int data;
struct node *next;
}*Linklist,Node;
void paixu(Linklist head)
{
Linklist p,q,small;
int temp;
for(p=head->next;p->next!=NULL;p=p->next) /* for（循环变量初值，循环条件，循环变量增量）*/
{ small=p;
//*****起始时设置small与首元数据一致；
for(q=p->next;q;q=q->next) /* q作为条件，是何用意？*/
//*****以q为指针，从链表次元结点遍历到尾。
if(q->data
small=q; /*执行这句之后又回到for(q=p->next;q;q=q->next)?还是到下一个if?*/
//*****先将q指向后一结点，再回到循环判断语句，条件
//*****满足则在进循环体（if语句是循环体）
if(small!=p) /*不懂这个if所有的内容*/
//*****如果找到的表中最小元不是p结点，则交换p结点和small结点的元素
//*****所以下面语句少一个small->data=temp;
{
temp=p->data;
p->data=small->data;
small->data=temp;//*****加上语句
}
}//******这里要加一个大括号
printf("输出排序后的数字:\n");
output(head);
}
有谁能详细分析这个算法？
给出第一次循环和第二次循环的详解？
//*****这里有嵌套循环
//*****你说的是外层的循环吧？
//*****例如初始序列为3451209
//****1次循环后0451239
//****2次循环后0154239
第二章
--------------------------------------------------------------------------------
一、单项选择题
1. 线性表是________。
A．一个有限序列，可以为空 B．一个有限序列，不可以为空
C．一个无限序列，可以为空 D．一个无限序列，不可以为空
2. 在一个长度为n的顺序表中删除第i个元素(0<=i<=n)时，需向前移动 个元素。
A．n-i B．n-i+l C．n-i-1 D．i
3. 线性表采用链式存储时，其地址________。
A．必须是连续的 B．一定是不连续的
C．部分地址必须是连续的 D．连续与否均可以
4. 从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较________个元素结点。
A．n/2 B．n C．（n+1）/2 D．（n-1）/2
5. 在双向循环链表中，在p所指的结点之后插入s指针所指的结点，其操作是____。
A． p->next=s; s->prior=p;
p->next->prior=s; s->next=p->next;
B． s->prior=p; s->next=p->next;
p->next=s; p->next->prior=s;
C． p->next=s; p->next->prior=s;
s->prior=p; s->next=p->next;
D． s->prior=p; s->next=p->next;
p->next->prior=s; p->next=s;
6. 设单链表中指针p指向结点m，若要删除m之后的结点（若存在），则需修改指针的操作为________。
A．p->next=p->next->next; B．p=p->next;
C．p=p->next->next; D．p->next=p;
7. 在一个长度为n的顺序表中向第i个元素(0< i之前插入一个新元素时，需向后移动______个元素。
A．n-i B．n-i+l C．n-i-1 D．i
8. 在一个单链表中，已知q结点是p结点的前趋结点，若在q和p之间插入s结点，则须执行
A．s->next=p->next; p->next=s
B．q->next=s; s->next=p
C．p->next=s->next; s->next=p
D．p->next=s; s->next=q
9. 以下关于线性表的说法不正确的是______。
A．线性表中的数据元素可以是数字、字符、记录等不同类型。
B．线性表中包含的数据元素个数不是任意的。
C．线性表中的每个结点都有且只有一个直接前趋和直接后继。
D．存在这样的线性表：表中各结点都没有直接前趋和直接后继。
10. 线性表的顺序存储结构是一种_______的存储结构。
A．随机存取 B．顺序存取 C．索引存取 D．散列存取
11. 在顺序表中，只要知道_______，就可在相同时间内求出任一结点的存储地址。
A．基地址 B．结点大小
C．向量大小 D．基地址和结点大小
12. 在等概率情况下，顺序表的插入操作要移动______结点。
A．全部 B．一半
C．三分之一 D．四分之一
13. 在______运算中，使用顺序表比链表好。
A．插入 B．删除
C．根据序号查找 D．根据元素值查找
14. 在一个具有n个结点的有序单链表中插入一个新结点并保持该表有序的时间复杂度是_______。
A．O(1) B．O(n)
C．O(n2) D．O(log2n)
15. 设有一个栈，元素的进栈次序为A, B, C, D, E,下列是不可能的出栈序列__________。
A．A, B, C, D, E B．B, C, D, E, A
C．E, A, B, C, D D．E, D, C, B, A
16. 在一个具有n个单元的顺序栈中，假定以地址低端（即0单元）作为栈底，以top作为栈顶指针，当做出栈处理时，top变化为______。
A．top不变 B．top=0 C．top-- D．top++
17. 向一个栈顶指针为hs的链栈中插入一个s结点时，应执行______。
A．hs->next=s;
B．s->next=hs; hs=s;
C．s->next=hs->next;hs->next=s;
D．s->next=hs; hs=hs->next;
18. 在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队满的条件为________。
A．rear％n= = front B．（front+l）％n= = rear
C．rear％n -1= = front D．(rear+l)％n= = front
19. 在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队空的条件为________。
A．rear％n= = front B．front+l= rear
C．rear= = front D．(rear+l)％n= front
20. 在一个链队列中，假定front和rear分别为队首和队尾指针，则删除一个结点的操作为________。
A．front=front->next B．rear=rear->next
C．rear=front->next D．front=rear->next
二、填空题
1. 线性表是一种典型的_________结构。
2. 在一个长度为n的顺序表的第i个元素之前插入一个元素，需要后移____个元素。
3. 顺序表中逻辑上相邻的元素的物理位置________。
4. 要从一个顺序表删除一个元素时，被删除元素之后的所有元素均需_______一个位置，移动过程是从_______向_______依次移动每一个元素。
5. 在线性表的顺序存储中，元素之间的逻辑关系是通过_______决定的；在线性表的链接存储中，元素之间的逻辑关系是通过_______决定的。
6. 在双向链表中，每个结点含有两个指针域，一个指向_______结点，另一个指向_______结点。
7. 当对一个线性表经常进行存取操作，而很少进行插入和删除操作时，则采用_______存储结构为宜。相反，当经常进行的是插入和删除操作时，则采用_______存储结构为宜。
8. 顺序表中逻辑上相邻的元素，物理位置_______相邻，单链表中逻辑上相邻的元素，物理位置_______相邻。
9. 线性表、栈和队列都是_______结构，可以在线性表的______位置插入和删除元素；对于栈只能在_______位置插入和删除元素；对于队列只能在_______位置插入元素和在_______位置删除元素。
10. 根据线性表的链式存储结构中每个结点所含指针的个数，链表可分为_________和_______；而根据指针的联接方式，链表又可分为________和_________。
11. 在单链表中设置头结点的作用是________。
12. 对于一个具有n个结点的单链表，在已知的结点p后插入一个新结点的时间复杂度为______，在给定值为x的结点后插入
一个新结点的时间复杂度为_______。
13. 对于一个栈作进栈运算时，应先判别栈是否为_______，作退栈运算时，应先判别栈是否为_______，当栈中元素为m时，作进栈运算时发生上溢，则说明栈的可用最大容量为_______。为了增加内存空间的利用率和减少发生上溢的可能性，由两个栈共享一片连续的内存空间时，应将两栈的_______分别设在这片内存空间的两端，这样只有当_______时才产生上溢。
14. 设有一空栈，现有输入序列1，2，3，4，5，经过push, push, pop, push, pop, push, push后，输出序列是_________。
15. 无论对于顺序存储还是链式存储的栈和队列来说，进行插入或删除运算的时间复杂度均相同为__________。
三、简答题
1. 描述以下三个概念的区别：头指针，头结点，表头结点。
2. 线性表的两种存储结构各有哪些优缺点？
3. 对于线性表的两种存储结构，如果有n个线性表同时并存，而且在处理过程中各表的长度会动态发生变化，线性表的总数也会自动改变，在此情况下，应选用哪一种存储结构？为什么？
4. 对于线性表的两种存储结构，若线性表的总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素，应选用何种存储结构？试说明理由。
5. 在单循环链表中设置尾指针比设置头指针好吗？为什么?
6. 假定有四个元素A, B, C, D依次进栈，进栈过程中允许出栈，试写出所有可能的出栈序列。
7. 什么是队列的上溢现象？一般有几种解决方法，试简述之。
8. 下述算法的功能是什么?
LinkList *Demo(LinkList *L)
{ // L是无头结点的单链表
LinkList *q,*p;
if(L&&L->next)
{ q=L; L=L->next; p=L;
while (p->next)
p=p->next;
p->next=q; q->next=NULL;
}
return (L);
}
四、算法设计题
1. 设计在无头结点的单链表中删除第i个结点的算法。
2. 在单链表上实现线性表的求表长ListLength(L)运算。
3. 设计将带表头的链表逆置算法。
4. 假设有一个带表头结点的链表，表头指针为head，每个结点含三个域：data, next和prior。其中data为整型数域，next和prior均为指针域。现在所有结点已经由next域连接起来，试编一个算法，利用prior域（此域初值为NULL）把所有结点按照其值从小到大的顺序链接起来。
5. 已知线性表的元素按递增顺序排列，并以带头结点的单链表作存储结构。试编写一个删除表中所有值大于min且小于max的元素（若表中存在这样的元素）的算法。
6. 已知线性表的元素是无序的，且以带头结点的单链表作为存储结构。设计一个删除表中所有值小于max但大于min的元素的算法。
7. 假定用一个单循环
链表来表示队列（也称为循环队列），该队列只设一个队尾指针，不设队首指针，试编写下列各种运算的算法：
（1）向循环链队列插入一个元素值为x的结点；
（2）从循环链队列中删除一个结点。
8. 设顺序表L是一个递减有序表，试写一算法，将x插入其后仍保持L的有序性。
第二章参考答案
一、单项选择题
1．A 2．A 3．D 4．C 5．D 6．A 7．B 8．B 9．C 10．A 11．D 12．B 13．C 14．B 15．C 16．C 17．B 18．D 19．C 20．A
二、填空题
1．线性
2．n-i+1
3．相邻
4．前移，前，后
5．物理存储位置，链域的指针值
6．前趋，后继
7．顺序，链接
8．一定，不一定
9．线性，任何，栈顶，队尾，队头
10．单链表，双链表，非循环链表，循环链表
11．使空表和非空表统一；算法处理一致
12．O(1)，O(n)
13．栈满，栈空，m，栈底，两个栈的栈顶在栈空间的某一位置相遇
14．2、3
15．O(1)
三、简答题
1．头指针是指向链表中第一个结点（即表头结点）的指针；在表头结点之前附设的结点称为头结点；表头结点为链表中存储线性表中第一个数据元素的结点。若链表中附设头结点，则不管线性表是否为空表，头指针均不为空，否则表示空表的链表的头指针为空。
2．线性表具有两种存储结构即顺序存储结构和链接存储结构。线性表的顺序存储结构可以直接存取数据元素，方便灵活、效率高，但插入、删除操作时将会引起元素的大量移动，因而降低效率：而在链接存储结构中内存采用动态分配，利用率高，但需增设指示结点之间关系的指针域，存取数据元素不如顺序存储方便，但结点的插入、删除操作较简单。
3．应选用链接存储结构，因为链式存储结构是用一组任意的存储单元依次存储线性表中的各元素，这里存储单元可以是连续的，也可以是不连续的：这种存储结构对于元素的删除或插入运算是不需要移动元素的，只需修改指针即可，所以很容易实现表的容量的扩充。
4．应选用顺序存储结构，因为每个数据元素的存储位置和线性表的起始位置相差一个和数据元素在线性表中的序号成正比的常数。因此，只要确定了其起始位置，线性表中的任一个数据元素都可随机存取，因此，线性表的顺序存储结构是一种随机存取的存储结构，而链表则是一种顺序存取的存储结构。
5．设尾指针比设头指针好。尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为rear，则开始结点和终端结点
的位置分别是rear->next->next 和 rear, 查找时间都是O(1)。若用头指针来表示该链表，则查找终端结点的时间为O(n)。
6．共有14种可能的出栈序列，即为：
ABCD, ABDC，ACBD, ACDB，BACD，ADCB，BADC，BCAD, BCDA，BDCA,CBAD, CBDA，CDBA, DCBA
7．在队列的顺序存储结构中，设队头指针为front，队尾指针为rear，队列的容量（即存储的空间大小）为maxnum。当有元素要加入队列（即入队）时，若rear=maxnum，则会发生队列的上溢现象，此时就不能将该元素加入队列。对于队列，还有一种“假溢出”现象，队列中尚余有足够的空间，但元素却不能入队，一般是由于队列的存储结构或操作方式的选择不当所致，可以用循环队列解决。
一般地，要解决队列的上溢现象可有以下几种方法：
（1）可建立一个足够大的存储空间以避免溢出，但这样做往往会造成空间使用率低，浪费存储空间。
（2）要避免出现“假溢出”现象可用以下方法解决：
第一种：采用移动元素的方法。每当有一个新元素入队，就将队列中已有的元素向队头移动一个位置，假定空余空间足够。
第二种：每当删去一个队头元素，则可依次移动队列中的元素总是使front指针指向队列中的第一个位置。
第三种：采用循环队列方式。将队头、队尾看作是一个首尾相接的循环队列，即用循环数组实现，此时队首仍在队尾之前，作插入和删除运算时仍遵循“先进先出”的原则。
8．该算法的功能是：将开始结点摘下链接到终端结点之后成为新的终端结点，而原来的第二个结点成为新的开始结点，返回新链表的头指针。
四、算法设计题
1．算法思想为：
（1）应判断删除位置的合法性，当i<0或i>n-1时，不允许进行删除操作；
（2）当i=0时，删除第一个结点：
（3）当０时，允许进行删除操作，但在查找被删除结点时，须用指针记住该结点的前趋结点。算法描述如下：
delete(LinkList *q,int i)
{ //在无头结点的单链表中删除第i个结点
LinkList *p,*s;
int j;
if(i<0)
printf("Can't delete");
else if(i= =0)
{ s=q;
q=q->next;
free(s);
}
else
{ j=0; s=q;
while((j
{ p=s;
s=s->next;
j++;
}
if (s= =NULL)
printf("Cant't delete");
else
{ p->next=s->next;
free(s);
}
}
}
2．由于在单链表中只给出一个头指针，所以只能用遍历的方法来数单链表中的结点个数了。算法描述如下：
int ListLength ( LinkList *L )
{ //求带头结点的单链表的表长
int len=0;
ListList *p;
p=L;
while ( p->next!=NULL )
{ p=p->next;
len++;
}
return (len);
}
3．设单循环链表的头指针为head，类型为LinkList。逆置时需将每一个结点的指针域作以修改，使其原前趋结点成为后继。如要更改q结点的指针域时，设s指向其原前趋结点，p指向其原后继结点，则只需进行q->next=s;操作即可，算法描述如下：
void invert(LinkList *head)
{ //逆置head指针所指向的单循环链表
linklist *p, *q, *s;
q=head;
p=head->next;
while (p!=head) //当表不为空时，逐个结点逆置
{ s=q;
q=p;
p=p->next;
q->next=s;
}
p->next=q;
}
4．定义类型LinkList如下：
typedef struct node
{ int data;
struct node *next,*prior;
}LinkList;
此题可采用插入排序的方法，设p指向待插入的结点，用q搜索已由prior域链接的有序表找到合适位置将p结点链入。算法描述如下：
insert (LinkList *head)
{ LinkList *p,*s,*q;
p=head->next; //p指向待插入的结点，初始时指向第一个结点
while(p!=NULL)
{ s=head; // s指向q结点的前趋结点
q=head->prior; //q指向由prior域构成的链表中待比较的结点
while((q!=NULL) && (p->data>q->data)) //查找插入结点p的合适的插入位置
{ s=q;
q=q->prior;
}
s->prior=p;
p->prior=q; //结点p插入到结点s和结点q之间
p=p->next;
}
}
5．算法描述如下：
delete(LinkList *head, int max, int min)
{ linklist *p, *q;
if (head!=NULL)
{ q=head;
p=head->next;
while((p!=NULL) && (p->data<=min))
{ q=p;
p=p->next;
}
while((p!=NULL) && (p->data
p=p->next;
q->next=p;
}
}
6．算法描述如下：
delete(LinkList *head, int max, int min)
{ LinkList *p,*q;
q=head;
p=head->next;
while (p!=NULL)
if((p->data<=min) || (p->data>=max))
{ q=p;
p=p->next;
}
else
{ q->next=p->next;
free(p);
p=q->next;
}
}
7．本题是对一个循环链队列做插入和删除运算，假设不需要保留被删结点的值和不需要回收结点，算法描述如下：
（1）插入（即入队）算法：
insert(LinkList *rear, elemtype x)
{ //设循环链队列的队尾指针为rear,x为待插入的元素
LinkList *p;
p=(LinkList *)malloc(sizeof(LinkList));
if(rear= =NULL) //如为空队，建立循环链队列的第一个结点
{ rear=p;
rear->next=p; //链接成循环链表
}
else //否则在队尾插入p结点
{ p->next=rear->next;
rear->next=p;
rear=p;
}
}
（2）删除（即出队）算法：
delete(LinkList *rear)
{ //设循环链队列的队尾指针为rear
if (rear= =NULL) //空队
printf("underflow\n");
if(rear->next= =rear) //队中只有一个结点
rear=NULL;
else
rear->next=rear->next->next; //rear->next指向的结点为循环链队列的队头结点
}
8．只要从终端结点开始往前找到第一个比x大(或相等)的结点数据，在这个位置插入就可以了。算法描述如下：
int InsertDecreaseList( SqList *L, elemtype x )
{ int i;
if ( (*L).len>= maxlen)
{ printf(“overflow");
return(0);
}
for ( i=(*L).len ; i>0 && (*L).elem[ i-1 ] < x ; i--)
(*L).elem[ i ]=(*L).elem[ i-1 ] ; // 比较并移动元素
(*L).elem[ i ] =x;
(*L).len++;
return(1);
}
你如今所在位置是>>目录>>第二章线性表
习 题 二
一、单选题
1.在一个长度为n的顺序存储的线性表中，向第i个元素(1≤i≤n+1)之前插入一个新元素时，
需要从年向前依次移 B 个元素。
A n-i B n-i+1 C n-i-1 D i
2.在一个长度为n的顺序存储的线性表中，删除第i个元素(1≤i≤n+1)时，需要从前向后依次
前移 A 个元素。
3.在一个长度为n的线性表中顺序查找值为x的元素时，查找成功的平均查找长度（即x同元素
的平均比较次数，假定查找每个元素的概率都相等）为 C 。
A n B n/2 C (n+1)/2 D (n-1)/2
4.在一个单链表HL中，若要向表头插入一个自由指针p指向的结点，则执行 B 。
A HL=p;p->next=HL; B p=next=HL; HL=p;
C p->next=HL; p=HL; D p->next=HL->next;HL->next=p;
5.在一个单链表HL中，若要在指针q所指结点的后面插入一个自由指针p所指向的结点，则执行
D 。
A q->next=p->next;p->next=q; B p->next=q->next;q=p;
C q->next=p->next;p->next=q D p->next=q->next;q->next=p;
6.在一个单链表HL中，若要删除由指针q所指向结点的后继结点，则执行 C 。
A p=q->next;p->next=q->next; B p=q->next;q->next=p;
C p=q->next;q->next;q->next=q; D q->next=q=->next->next;q->next=q;
二、填空题
1.在线性表的单链接存储结构中，每个结点包含有两个域，一个叫 值 ，另一个叫 指针 域。
2.在下面数组a中链接存储着一个线性表，表头指针为a[0].next，则该线性表为 (38,56,25,
60,42,74) 。
a 0 1 2 3 4 5 6 7 8
data 60 56 42 38 74 25 next 4 3 7 6 2 0 1
3.对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为 o(n) ，在表尾插
入元素的时间复杂度为 O(1) 。
4.对于一个单链接存储的线性表，在表头插入结点的时话里有话复杂度为 o(1) ，在表尾插入
元素的时间复杂度为 o(n) 。
5.在线性表的顺序存储中，若一个元素的下标为i，则它的前驱元素的下标为 i-1 ，后继元素
的下标为 i+1 。
6.在线性表的单链接存储中，若一个元素所在结点的地址为p，则
后继结点的地址为 p->next ，
若假定p为一个数组a中的下标，则其后继结点的下标为 a[p].next 。
7.在循环单链接表中，最后一个结点的指针域指向 表头 结点。
8.在双向链接表中每个结点包含有两个针域，一个指向其 前驱 结点，另一个指向其 后继
结点。
9.在循环双向链接表中表头结点的左指针域指向 表尾 结点，最后一个结点的右指针域指
向 表头 结点。
10.在以HL为表头指针的带表头附加结点的单链接表中，链表为空的条件分别为 HL->next==NULL
HL->next==HL 。
11.在由数组a中元素结点构成的单链表中，删除下标为i的结点后，需要把该结点插入到空闲表的
表头，具体操作为 a[i].next=a[1].next;a[1].next=i; 。
12.在由数组a中元素结点构成的单链表中，在插入下标为i的结点后，需要从空闲表头中删除一个
结点，并将该结点下标赋给i，具体操作为 i=a[1].next;a[1].next=a[i].next; 。
13.在由数组a中元素结点构成的单链表中，删除下标为i的后继结点并将被删除结点的下标赋给i时
，所进行的操作描述为 p=a[i].next;a[i].next=a[p].next;i=p; 。
14.在由数组a中元素结点构成的单链表中，在下标为i的结点的后面插入一个下标为j的结点时，需
要进行的操作为 a[j].next=a[i].next;a[i].next=j; 。
三、普通题
1.
⑴解：(79,62,34,57,26,48)
⑵解：(26,34,48,57,62,79)
⑶解：(48,56,57,62,79,34)
⑷解：(56,57,79,34)
⑸解：(26,34,39,48,57,62)
2.
解：
为了排版方便，假定采用以下输出格式表示单链接表的示意图；每个括号内的数据表示一个元
素结点，其中第一个数据为元素值，第二个数据为后继结点的指针，第一个元素结点前的数值为
表头指针。
⒈(7(79,6),(62,5),(34,4),(57,3),(26,2),(48,0))
⒉(3(26,5),(34,2),(48,4),(57,6),(62,7),(79,0))
⒊(2(48,8),(56,4),(57,6),(62,7),(79,5),(34,0))
⒋(8(56,4),(57,7),(79,5),(34,0))
3.对于List类型的线性表,编写出下列每个算法。
⑴ 从线性表中删除具有最小值的元素并由函数返回，空出的位置由最后一个元素填补，若
线性表为空则显示出错信息并退出运行。
解： ElemType DMValue(List&L)
//从线性表中删除具有最小值的元素并由函数返回,空出的位置
//由最后一个元素填补,若线性表为空则显示出错信息并退出运行
{
if(ListEmpty(L)){
cerr<<"List is Empty!"<
}
ElemType x;
x=L.list[0];
int k=0;
for(int i=1;i
if(y
L.list[k]=L.list[L.size-1];
L.size--;
return x;
}
⑵ 从线性表中删除第i
个元素并由函数返回。
解：int Deletel(List& L,int i)
//从线性表中删除第i个元素并由函数返回
{
if(i<1||i>L.size){
cerr<<"Index is out range!"<
}
ElemType x;
x=L.list[i-1];
for(int j=i-1;j
L.size--;
return x;
}
⑶ 向线性表中第i个元素位置插入一个元素。
解：void Inser1(List& L,int i,ElemType x)
//向线性表中第i个元素位置插入一个元素
{
if(i<1||i>L.size+1){
cerr<<"Index is out range!"<
}
if(L.size==MaxSize)
{
cerr<<"List overflow!"<
}
for(int j=L.size-1;j>i-1;j--)
L.list[j+1]=L.list[j];
L.list[i-1]=x;
L.size++;
}
⑷ 从线性表中删除具有给定值x的所有元素。
解：void Delete2(List& L,ElemType x)
//从线性表中删除具有给定值x的所有元素
{
int i=0;
while(i
for(int j=i+1;j
L.size--;
}
else
i++;
}
⑸ 从线性表中删除其值在给定值s和t之间(要求s小于t)的所有元素。
解：void Delete3(List& L,ElemType s,ElemType t)
//从线性表中删除其值在给定值s和t之间的所有元素
{
int i=0;
while(i
for(int j=i+1;j
L.size--;
}
else
i++;
}
⑹ 从有序表中删除其值在给定值s和t之间(要求s小于t)的所有元素。
解：void Delete4(List& L,ElemType s,ElemType t)
//从有序表中删除其值在给定值s和t之间的所有元素
{
int i=0;
while(i
if(i
for(int k=i+j;k
L.size-=j;
}
}
⑺ 将两个有序表合并成一个新的有序表并由变量返回。
解：void Merge(List& L1,List& L2,List& L3)
//将两个有序表合并成一个新的有序表并由变量返回
{
if(L1.size+L2.size>MaxSize){
cerr<<"List overflow!"<
}
int i=0,j=0,k=0;
while((i
{ //将L1中的元素赋给L
L.list[k]=L1.list[i];
i++;
}
else{ //将L2中的元素赋给L
L.list[k]=L2.list[j];
j++;
}
k++;
}
while(i
i++;k++;
}
while(j
j++;k++;
}
L.size=k;
}
⑻ 从线性表中删除所有其值重复的元素，使其所有元素的值均不同，如对于线性表(2,8,9,
2,5,5,6,8,7,2)，则执行此算法后变为(2,8,9,5,6,7)。
解：void Delete5(List& L)
//从线性表中删除所有其值重复的元素,使其所有元素的值均不同
{
int i=0;
while(i
while(j
if(L.list[j]==L.list[i]){
for(int k=j+1;k
L.size--;
}
else
j++;
}
i++;
}
}
4.对于结点类型为LNode的单链接表,编写出下列每个算法。
⑴ 将一个单链接表按逆序链接,即若原单链表中存储元素的次序为a1,a2,...,an,则
逆序链接后变为an,an-1,...a1。
解：void Contrary(LNode*&HL)
//将一个单多办实事有按逆序链接
{
LNode*p=HL;//p指向待逆序的第一个结点，初始指向原表头结点
HL=NULL;//HL仍为逆序后的表头指针，禄始值为空
while(p!=NULL)
{ //把原单链表中的结点依次进行逆序链接
LNode*q=p; //q指向待处理的结点
p=p->next; //p指向下一个待逆序的结点
//将q结点插入到已陈序单链表的表头
q->next=HL;
HL=q;
}
}
⑵ 删除单链表中的第i个结点。
解：void Delete1(LNode*&HL,int i)
//删除单链表中的第i个结点
{
if(i<1||HL==NULL){
cerr<<"Index is out range!"<
}
LNode*ap,*cp;
ap=NULL;cp=HL; //cp指向当前结点，ap指向其前驱结点
int j=1;
while(cp!=NULL)
if(j==i)
break; //cp结点即为第i个结点
else{ //继续向后寻找
ap=cp;
cp=cp->next;
j++;
}
if(cp==NULL){
cerr<<"Index is out range!"<
}
if(ap==NUL
L)
HL=HL->next;
else
ap->next=cp->next;
delete cp;
}
⑶ 从单链表中查找出所有元素的最大值，该值由函数返回，若单链表为空，则显示出错信息
并停止运行。
解：ElemType MaxValue(LNode*HL)
//从单链表中查找出所有元素的最大值，该值由函数返回
{
if(HL==NULL){
cerr<<"Linked list is empty!"<
}
ElemType max=HL->data;
LNode*p=HL->next;
while(p!=NULL){
if(max
p=p->next;
}
return max;
}
⑷ 统计出单链表中结点的值等于给定值x的结点数。
解：int Count(LNode*HL,ElemType x)
//统计出单链表中结点的值等于给定值x的结点数
{
int n=0;
while(HL!=NULL){
if(HL->data==x) n++;
HL=HL->next;
}
return n;
}
⑸ 根据一维数组a[n]建立一个单链表，使单链表中元素的次序与a[n]中元素的次序相同，
并使该算法的时间复杂度为O(n)。
解：void Create(LNode*&HL,ElemType a[],int n)
//根据一维数组a[n]建立一个单链表
{
InitList(HL);
for(int i=n-1;i>=0;i--)
InsertFront(HL,a[i];
}
⑹ 将一个单链表重新链接成有序单链表。
解：void OrderList(LNode*&HL)
//将一个单链表重新链接成有序单链表
{
LNode* p=HL;//p指向待处理的第一个结点，初始指向原表头结点
HL=NULL; //HL仍为待建立的有序表的表头指针，禄始值为空
while(p!=NULL)
{ //把原单链表中的结点依次进行有序链接
LNode* q=p; //q指向待处理的结点
p=p->next; //p指向下一个待处理的结点
LNode* ap=NULL,*cp=HL;
//cp指向有序表中待比较的结点，ap指向其前驱结点
while(cp!=NULL)
{ //为插入q结点寻找插入位置
if(q->data
break;
else{
ap=cp;
cp=cp->next;
}
} //将q结点插入到ap和cpxf hko pp uj
q->next=cp;
if(ap==NULL)
HL=q;
else
ap->next=q;
}
}
⑺ 将两个有序单链表合并成一个有序单链表，合并后使原有单链表为空。
解：LNode*Mergel(LNode*&p1,LNode*&p2)
//将两个有序单链表合并成一个有序单链表
{
LNode a; //a结点作为结果的有序单链表的表头附加结点，
这样便于处理，处理
//结束后返回a结点的镄针域的值
LNode*p=&a; //p指向结果的有序单链表的表尾结点
p->next=NULL;//初始指向表头附加结点
while((p1!=NULL)&&(p2!=NULL))
{//处理两个表非空的情况
if(p1->data
p->next=p1;p1=p1->next;
}
else{
p->next=p2;p2=p2->;
}
p=p->next;
}
if(p1!=NULL)p->next=p1;
if(p2!=NULL)p->next=p2;
p1=p2=NULL;
return a.next;
}
⑻ 根据两个有序单链表生成一个新的有序单链表，原有单链表保持不变。如假定两个有序单链
表中的元素为(2,8,10,20)和(3,8,9,15,16)，则生成的新单链表中的元素为(2,3,8,8,9,10,15,
16,20)。
解：LNode*Merge2(LNode*p1,LNode*p2)
//根据两个有序单链表生成一个新的有序单链表
{
LNode a; //用a作为新的有序单链表的表头附加结点
LNode*p=&a; //p指向结果有序单链表的表尾结点
p->next=NULL; //初始指向表头附加结点
while((p1!=NULL&&(p2!=NULL))
{ //处理两个表非空时的情况
LNode*newptr=new LNode;
if(p1->data
{ //由p1->data建立新结点，然后p1指针后移
newptr->data=p1->data;
p1=p1->next;
}
else
{ //由p2->data建立新结点，然后p2指针后移
newptr->data=p2->data;
p2=p2->next;
}
//将newptr结点插入到结果的有序表的表尾
p->next=newptr;
p=newptr;
}
while(p1!=NULL)
{ //继续处理p1单链表中剩余的结点
LNode*newptr=new LNode;
newptr->data=p1->data;
p1=p1->next;
p->next=newptr;
p=newptr;
}
while(p2!=NULL)
{ //继续处理p2单链表中剩余的结点
LNode*newptr=new LNode;
newptr->data=p2->data;
p2=p2->next;
p->next=newptr;
p=newptr;
}
p->next=NULL;
return a.next;
}
⑼ 根据一个元素类型为整型的单链表生成两个单链表，使得第一个单链表中包含原单链表中所有
元素值为奇数的结点，使得第二个单链表中包含原单链表中所有元素值为偶数的结点。原有单链表
保持不变。
解：void Separate(LNode*HL,LNode*&p1,LNode*&p2)
//根据一个单链表HL按条件拆分生成两个单链表p1和p2
{
LNode a,b; //a和b结点分别作为p1和p2单链表的表头附加结点
LNode*t1=&a,*t2=&b; //t1和t2分别作为指
向p1和p2单链表的
//表尾结点，初始指向表头附加结点
Lnode*p=HL;
while(p!=NULL)
{ //每循环一次产生一个新结点，并把它加入到p1或p2单链表
//的未尾
LNode*newptr=new LNode;
if(p->data%2==1){
newptr->data=p->data;
t1->next=newptr;
t1=newptr;
}
else{
newptr->data=p->data;
t2->next=newptr;
t2=newptr;
}
p=p->next;
}
t1->next=t2->next=NULL;
p1=a.next;p2=b.next; //把指向两个单链表的表头结点的指针分别赋给
//p1和p2返回
}
6.编写一个算法，使用表头附加结点的循环单链表解决约瑟夫(Josephus)问题。其问题是
：设有n个人围坐在一张圆桌周围，现从某个人开始从1报数，数到m的人出列(即离开坐位，
不参加以后的报数)，接着从出列的下一个人开始重新从1报数，数到m的人又出列，如此下
去直到所有人都出列为止，试求出它们的出列次序。
假如，当n=8、m=4时，若从第一个人(假定每个人的编号依次为1,2...,n)开始报数，则得
到的出列次序为:4,8,5,2,1,3,7,6。
此算法要求以n、m和s(假定从第s个人开始第一次报数)作为值参。
解：
void Josephus(int n,int m,int s)
//使用带表头附加结点的循环单链表解决约瑟夫问题
{
//生成表头附加结点，此时循环单链表为空
LNode*HL=new LNode;
HL->next=HL;
int i;
//生成含有n个结点、结点依次为1,2,...n的带表头结点的循环单链表
for(i=n;i>=1;i--){
//生成新的结点
LNode*newptr=new LNode;
newptr->data=i;
//把新的结点插入到表头
newptr->next=HL->next;
HL->next=newptr;
}
//从表头开始顺序查找出第s个结点，对应第一个开始报数的人
LNode*ap=HL,*cp=HL->next;
for(i=1;i
ap=cp;
cp=cp->next;
//若cp指向了表头附加结点，则仍需后移ap和cp指针，使之指向表头结点
if(cp==HL){ap=HL;cp=HL->next;}
}
//依次使n-1个人出列
for(i=1;i
for(int j=1;j
cp=cp->next;
if(cp==HL){ap=HL;cp=HL->next;}
}
//输出cp结点的值，即出列的人
cout<
//从单链表中删除cp结点
ap->next=cp->next;
delete cp;
//使cp指向被删除结点的后继结点
cp=ap->next;
//若cp指向了表头附加结点，则后移ap和cp指针
if(cp==HL){ap
=HL;cp=HL->next;}
}
//使最后一个人出列
cout<
delete HL->next;
delete HL;
}
7.对于在线性表抽象数据类型中定义的每一个操作，写出结点类型为LNode的带头附加结点
的循环单链表上实现的对应算法。
⑴初始化单链表
解：void InitList(LNode*HL)
{
HL->next=HL;//将单链表置空
}
⑵删除单链表中的所有结点，使之成为一个空表
void ClearList(LNode*HL)
{
LNode*cp,*np;
cp=HL->next;//将指向第一个结点的指针赋给cp
while(cp!=HL)//遍历单链表，向系统交回每一个结点。
{
np=cp->next;//保存下一个结点的指针。
delete cp;//删除当前结点。
cp=np;//使下一个结点成为当前结点。
}
HL->next=HL;//置单链表为空
}
⑶得到单链表的长度
int ListSize(LNode*HL)
{
LNode*p=HL->next;
int i=0;
while(p!=HL){i++;p=p->next;}
return i;
}
⑷检查单链表是否为空
int ListEmpty(LNode*hl)
{
return(HL->next==HL);
}
⑸得到单链表中第pos个结点中的元素
ElemType GetElem(LNode*HL,int pos)
{
if(pos<1){
cerr<<"pos is out range!"<
}
LNode* p=HL->next;
int i=0;
while(p!=HL){
i++;
if(i==pos)break;
p=p->next;
}
if(p!=HL)return p->data;
else{
cerr<<"pos is out range!"<
}
}
⑹遍历单链表
void TraverseList(LNode*HL)
{
LNode* p=HL->next;
while(p!=HL){
cout<
p=p->next;
}
cout<
⑺从单链表查找具有给定值的第一个元素
int Find(LNode* HL,ElemType& item)
{
LNode* p=HL->next;
while(p!=HL)
if(p->data==item){
item=p->data;
return 1;
}
else
p=p->next;
return 0;
}
⑻更新单链表中具有给定值的第一个元素
int Updata(LNode* HL,const ElemType& item)
{
LNode* p=HL->next;
while(p!=HL)//查找元素
if(p->data==item)break;
else p=p->next;
if(p==HL)return 0;
else{//更新元素
p->data=item;
return 1;
}
}
⑼向单链表的未尾插入一个元素
void InsertRear(LNode* HL,const ElemType& item)
{
LNode* newptr;
newptr=new LNode;
newptr->data=item;//把新元素赋给动态结点*newptr的值域。
LNode* p=HL;
while(p->next!=HL)//从表头开始遍历到最后一个结点为止。
p=p->next;
newptr->next=HL;p->next=newptr;//把新结点链接到表尾。
}
⑽向单链表的表头插
入一个元素
void InsertFront(LNode* HL,const ElemType& item)
{
LNode* newptr;
newptr=new LNode;
newptr->data=item;
newptr->next=HL->next;
HL->next=newptr;
}
(11)向单链表中插入一个元素
void Insert(LNode* HL,const ElemType& item)
{
LNode* newptr;
newptr=new LNode;
newptr->data=item;
LNode *ap,*cp;
ap=HL;cp=HL->next;
while(cp!=HL)
if(item
else{ap=cp;cp=cp->next;}
newptr->next=cp;
ap->next=newptr;
}
(12)从单链表中删除表头元素
ElemType DeleteFront(LNode* HL)
{
if(HL->next==HL){
cerr<<"Deleteing from an empty list!"<
}
LNode* p=HL->next;
HL->next=p->next;
ElemType temp=p->data;
delete p;
return temp;
}
(13)从单链表中删除等于给定值的第一个元素
int Delete(LNode* HL,const ElemType& item)
{
LNode*ap=HL,*cp=HL->next;
while(cp!=HL)
if(cp->data==item)break;
else{ap=cp;cp=cp->next;}
if(cp==HL){
cerr<<"Deleted element is not exitst!"<
}
else{
ap->next=cp->next;
delete cp;
return 1;
}
}
(14)利用单链表进行数据排序
void LinkSort(ElemType a[],int n)
{
LNode* head=new LNode;
InitList(head);
int i;
for(i=0;i
LNode* p=head->next;
i=0;
while(p!=head){
a[i++]=p->data;
p=p->next;
}
ClearList(head);
delete head;
}
*8.对于结点类型为DNode的双向链表，编写出下列每一个算法。
⑴向双向链表的未尾插入一个值为x的结点。
解：void InsertRear(DNode*&DL,ElemType x)
{
//建立值为x的结点
DNode* newptr=new DNode;
newptr->data=x;
newptr->left=newptr->right=newptr;
//当链表为空时完成插入
if(DL==NULL){DL=newptr;return;}
//当链表不为空时完成插入
DNode*p=DL->left;
newptr->right=p->right;
DL->left=newptr;
newptr->left=p;
p->right=newptr;
}
⑵向双向循环表的第i个结点位置插入一个值为x的结点。
解：void Insert(DNode*&DL,int i, ElemType x)
{
//i值越界，退出执行
if(i<=0){
cerr<<"i is out range!"<
}
//建立值为x的新结点
DNode*newptr=new DNode;
newptr->data=x;
newptr->left=newptr->right=newptr;
//当链表为空同时i等于1时进行插入，i不为1则退出
if(DL==NULL)if(i==1){DL=newptr;return;}
else{out<<"i is range!"<
}
//实现i等
于1时的插入
if(i==1){newptr->right=DL;
newptr->left=DL->left;
DL->left->right=newptr;
DL->left=newptr;
DL=newptr;
return;
}
//查找第i个结点
int k=1;
DNode*p=DL->right;
while(p!=DL){
k++;
if(k==i)break;
p=p->right;
}
//i值越界，退出执行
if(i>k+1){
cerr<<"i is out range!"<
}
//把newptr结点插入到p结点之前
newptr->right=p;
newptr->left=p->left;
p->left->right=newptr;
p->left=newptr;
return;
}
⑶从双向循环链表中删除值为x的结点。
解：bool Delete(DNode*&DL,ElemType x)
{
if(DL==NULL)return 0;
//当表头结点为x时则删除之
DNode*p=DL;
if(DL->data==x){
DL=DL->right;
p->left->right=DL;
DL->left=p->left;
delete p;
return 1;
}
//查找值为x的结点
p=p->right;
while(p!=DL){
if(p->data==x)break;
else p=p->right;
}
//不存在值为x的结点则返回0
if(p==DL)return 0;
//删除值为x的结点
p->left->right=p->right;
p->right->left=p->left;
delete p;
return 1;
}
9.假定有一种带头附加结点的链表，每个结点含三个域：data、next和range，其中data
为整型值域，next和range均为指针域，现在所有结点已经由next域链接起来，试编一算法
，利用range域把所有结点按照其值从小到大的顺序链接起来，当然由此域链接得到的单链
表的表头指针保存在表头附加结点的range域中。
解：void OrderList(SLNode* SL)
//假定SLNode类型为按题目要求所定义的结点类型，SL为指向表头附加结点的指针
{
SL->range=NULL;
for(SLNode*p=SL->next;p!=NULL;p=p->next)
{ //每循环一次把p所指向的结点按序插入到以range域链接的有序表中
SLNode*ap,*cp;
//为p结点寻找合适的插入位置
ap=SL;cp=ap->range;
while(cp!=NULL)
if(p->data
break;
else{
ap=cp;
cp=cp->range;
}
//插入位置在ap和cp之间，把结点插入其中
p->range=cp;
ap->range=p;
}
}
10.编一程序，实现下列功能：
⒈按照9题对结点的要求生成一个具有10个整数元素结点的带表头附加结点的根据next域
链接的链表，
元素值由随机函数产生；
⒉按照next域链接的次序输出链表中每个结点的值；
⒊调用按第9题要求编写的操作算法；
⒋按照range域链接的次序输出链表中每个结点的值。
解：
//lx2-7.cpp
#include
#include
typedef int ElemType;//规定元素类型为整型
struct SLNode//定义单链表结点
{
ElemType data;
SLNode*next;
SLNode*range;
};
void OrderList(SLNode* SL)
{
SL->range=NULL;
for(SLNode*p=SL->next;p!=NULL;p=p->next)
{
SLNode *ap,*cp;
//为p结点寻找合适的插入位置
ap=SL;cp=ap->range;
while(cp!=NULL)
if(p->data
break;
else{
ap=cp;
cp=cp->range;
}
//插入位置在ap和cp之间，把p结点插入其中
p->range=cp;
ap->range=p;
}
}
void main()
{
//按next域链接生成具有10个整数元素结点的链表
SLNode*a=new SLNode;
a->next=NULL;
int i;
SLNode* p;
for(i=0;i<10;i++){
p=new SLNode;
p->data=range()%30; //假定产生30以内的随机整数
p->next=a->next;
a->next=p;
}
//按next域链接的次序输出单链表
for(p=a->next;p!=NULL;p=p->next)
cout<
cout<
orderList(a);
//按range域链接的次序输出单链表
for(p=a->range;p!=NULL;p=p->range)
cout<
cout<
typedef struct node
{
int data;
struct node *next;
}*Linklist,Node;
void paixu(Linklist head)
{
Linklist p,q,small;
int temp;
for(p=head->next;p->next!=NULL;p=p->next) /* for（循环变量初值，循环条件，循环变量增量）*/
{ small=p;
for(q=p->next;q;q=q->next) /* q作为条件，是何用意？*/
if(q->data
small=q; /*执行这句之后又回到for(q=p->next;q;q=q->next)?还是到下一个if?*/
if(small!=p) /*不懂这个if所有的内容*/
{
temp=p->data;
p->data=small->data;
}
printf("输出排序后的数字:\n");
output(head);
}