广工anyview数据结构第二章(2021.12)
广工anyview数据结构习题第二章，
在学习过程中部分题目参考了Giyn 、戮漠、雁过留痕等大佬的代码，在此感谢。
题目解法不是最优解，但希望能给大家有所启发。同时也发了文档资源，需要可自取。
如果对你有帮助，可以给卑微的博主留个赞、关注、收藏 (不是)
(骗一下数据，说不定以后面试就过了，拜谢)
目录
1.DC02PE03
【题目】试写一算法，实现顺序栈的判空操作。StackEmpty_Sq(SqStack S)。
要求实现下列函数∶
Status StackEmpty_Sq(SqStack S);/* 对顺序栈S判空。*/
/* 若S是空栈，则返回TRUE;否则返回FALSE */
顺序栈的类型定义为∶
typedef struct{
ElemType *elem; //存储空间的基址
int top; //栈项元素的下一个位置，简称栈顶位标
int size; //当应分配的存循容量
int increment; //扩容时，增加的存循容量
}SqStack; // 顺序栈
#include "allinclude.h" //DO NOT edit this line
Status StackEmpty_Sq(SqStack S) {
// Add your code here
if(S.top==0)
return true;
return false;
}
2.DC02PE05
【题目】试写一算法，实现顺序栈的取栈顶元素操作。GetTop_Sq(SqStack S,ElemType &e)。
要求实现下列函数∶
Status GetTop_Sq(SqStack S,ElemType &e);
/* 取顺序栈S的栈顶元素到e，并返回OK;*/
/* 若失败，则返回ERROR。*/
顺序栈的类型定义为∶
typedef struct {
ElemType *elem; //存储空间的基址
int top; //栈项元素的下一个位置，简称栈顶位标
int size; //当应分配的存循容量
int increment; //扩容时，增加的存储容量
}SqStack; // 顺序栈
#include "allinclude.h" //DO NOT edit this line
Status GetTop_Sq(SqStack S, ElemType &e) {
// Add your code here
if(S.top==0)
return ERROR;
e=S.elem[S.top-1];
return OK;
}3.DC02PE07
【题目】试写一算法，实现顺序栈的出栈操作。Pop_Sq(SqStack &S,ElemType &e)。
要求实现下列函数∶
Status Pop_Sq(Sqstack &S,ElemType &e);
/* 顺序栈s的栈顶元素出栈到e，并返回OK;*/
/*若失败，则返回ERROR。*/
顺序栈的类型定义为∶
typedef struct {
ElemType *elem; //存储空间的基址
int top; //栈顶元素的下一个位置，简称栈顶位标
int size; //当前分配的存储容量
int increment; // 扩容时，增加的存储容量
} Sqstack; // 顺序栈
#include "allinclude.h" //DO NOT edit this line
Status Pop_Sq(SqStack &S, ElemType &e) {
// Add your code here
if(S.top==0)
return ERROR;
e=S.elem[--S.top];
return OK;
}4.DC02PE11
【题目】若顺序栈的类型重新定义如下。试编写算法，构建初始容量和扩容增量分别为size和inc的空顺序栈S。
typedef struct {
ElemType *elem;//存储空间的基址
ElemType *top; //栈顶元素的下一个位置
int size; //当前分配的存储容量
int increment; //扩容时，增加的存储容量
} SqStack2;
要求实现下列函数∶
Status InitStack_Sq2(SqStack2 &S,int size,int inc);
/* 构建初始容量和扩容增量分别为size和inc的空顺序栈S。*/
/* 若成功，则返回OK;否则返回ERROR。*/
#include "allinclude.h" //DO NOT edit this line
Status InitStack_Sq2(SqStack2 &S, int size, int inc) {
// Add your code here
S.elem=(ElemType*)malloc(size*sizeof(ElemType));
if(S.elem==NULL||size<1||inc<1)
return ERROR;
S.top=&S.elem[0];
S.size=size;
S.increment=inc;
return OK;
}5.DC02PE13
【题目】若顺序栈的类型重新定义如下。试编写算法，实现顺序栈的判空操作。
typedef struct {
ElemType *elem; // 存储空间的基址
ElemType *top; //栈顶元亲的下一个位置
int size;//当前分配的存储容量
int increment; // 扩容时，增加的存储容量
}SqStack2;
要求实现下列函数∶
Status StackEmpty_Sq2(SqStack2 S);
/* 对顺序栈S判空。*/
/* 若S是空栈，则返回TRUE;否则返回FALSE */
#include "allinclude.h" //DO NOT edit this line
Status StackEmpty_Sq2(SqStack2 S) {
// Add your code here
if(S.top==S.elem+0)
return TRUE;
return false;
}
6.DC02PE15
【题目】若顺序栈的类型重新定义如下。试编写算法，实现顺序栈的入栈操作。
typedef struct {
ElemType *elem;//存储空间的基址
ElemType *top; //栈顶元素的下一个位置
int size;//当前分配的存储容量
int increment; //扩容时，增加的存储容量
}SqStack2;
要求实现下列函数∶
Status Push_Sq2(SqStack2 &S,ElemType e);
/* 若顺序栈S是满的，则扩容，若失败则返回ERROR。*/
/*将e压入S，返回OK。*/
#include "allinclude.h" //DO NOT edit this line
Status Push_Sq2(SqStack2 &S, ElemType e) {
// Add your code here
if(S.top==S.elem+S.size)
{
realloc(S.elem,(S.size+S.increment)*sizeof(ElemType));
if(S.elem==NULL)
return ERROR;
S.elem[S.size]=e;
S.size+=S.increment;
S.top++;
return OK;
}
*(S.top++)=e;
return OK;
}7.DC01PE17
【题目】若顺序栈的类型重新定义如下。试编写算法，实现顺序栈的出栈操作。
typedef struct{
ElemType *elem; //存储空间的基址
ElemType *top; //栈顶元亲的下一个位置
int size; //当应分配的存储容量
int increment; //扩容时，增加的存储容量
} SqStack2;
要求实现下列函数∶
Status Pop_Sq2(SqStack2 &S,ElemType &e);
/* 若颇序栈S是空的，则返回ERROR;*/
/* 否则将S的栈顶元素出栈到e，返回OK。*/
#include "allinclude.h" //DO NOT edit this line
Status Pop_Sq2(SqStack2 &S, ElemType &e) {
// Add your code here
if(S.top==S.elem+0)
return ERROR;
e=*(--S.top);
return OK;
}8.DC02PE19
【题目】试写一算法，借助辅助栈，复制顺序栈S1得到s2。
Status CopyStack_Sq(SqStack S1,SqStack &S2)。
要求实现下列函数∶
Status CopyStack_Sq(SqStack S1,SqStack &S2);/* 借助辅助栈，复制顺序栈S1得到S2。
/* 若复制成功，则返回TRUE; 否则FALSE。*/
顺序栈的类型定义为∶typedef struct {
ElemType *elem; //存储空间的基址
int top; //栈顶元素的下一个位置，简称栈顶位标
int size; //当前分配的存储容量
int increment; //扩容时，增加的存循容量
} SqStack;//顺序栈
可调用顺序栈接口中下列函数∶
Status InitStack_Sq（SqStack &S，int size，int inc）; //初始化顺序栈S
Status DestroyStack_Sq（SqStack &S）; //销毁顺序栈S
Status StackEmpty_Sq(SqStack S); //栈S判空，若空则返回TRUE，否则FALSE
Status Push_Sq（Sgstack &S，ElemType e）;// 将元素e压入栈S
Status Pop_Sq（SqStack &S，ElemType &e）;//栈S的栈顶元素出栈到e
#include "allinclude.h" //DO NOT edit this line
Status CopyStack_Sq(SqStack S1, SqStack &S2) {
// Add your code here
SqStack S0;
ElemType temp;
InitStack_Sq(S0,S1.size,S1.increment);
InitStack_Sq(S2,S1.size,S1.increment);
S0.top=0;
S2.top=0;
if(StackEmpty_Sq(S1)==true)
return true;
int i,l=S1.top;
for(i=0;i<l;i++)
{
Pop_Sq(S1,temp);
Push_Sq(S0,temp);
}
for(i=0;i<l;i++)
{
Pop_Sq(S0,temp);
Push_Sq(S2,temp);
}
DestroyStack_Sq(S0);
return true;
}
9.DC02PE20
编写程序，将一个十进制数转换为指定进制的数。
/带*
* 将整数N转换为由rd指定的进制，并将结果打印出来。
@param N∶需要被转换的十进制数
@param rd∶取值为[2-9]，表示具体的进制，例如rd =8时，表示八进制*/
void Conversion(int N,int rd);
注∶请勿打印除了结果之外的其它任何字符，否则可能导致结果校验错误。
有以下数据结构及其操作可用∶
#define MAXSIZE 20
#define INCREMENT 5
typedef int Status;
typedef char ElemType;
typedef struct {
ElemType *elem;// 存储空间的基址
int top; //栈顶元素的下一个位置，简称栈顶位标
int size; //当前分配的存储容量
int increment; //扩容时，增加的产储容量
}SqStack; //顺序栈
// 初始化一个栈，size为栈的初始容量，inc为栈增容时的容量。一般而言，
可令size 为MAXSIZE，inc为INCREMENT
Status InitStack_Sq(SqStack &S,int size,int inc);
//销毁栈
Status DestroyStack_Sq(SqStack S);
/检查栈是否为空。如巢为空，则返回TRUE，否则返回FALSE
Status StackEmpty Sq(SqStack S);
//将元素e进栈
Status Push_Sq(SqStack &S,ElemType e);
//出栈，并且栈顶元素赋给e
status Pop_Sq(SqStack &S,ElemType &e);
#include "allinclude.h"
void Conversion(int N, int rd)
{ // Add your code here
SqStack S;
ElemType temp;
InitStack_Sq(S,MAXSIZE,INCREMENT);
while(N)
{
Push_Sq(S,N%rd);
N/=rd;
}
while(S.top)
{
Pop_Sq(S,temp);
printf("%d",temp);
}
}10.DC02PE21
编写程序，判断一个括号串中的括号是否匹配。括号有3种∶{}、【】、（）。
/**
*判断一个括号串中的括号是否为匹配。
@param exp∶括号串
@param n∶括号串的长度
*/
Status matchBracketSequence(char* exp,int n);
有以下数据结构及其操作可用∶
#define MAXSIZE 20
#define INCREMENT 5
typedef int Status;
typedef char ElemType;
typedef struct {
ElemType *elem;// 存储空间的基址
int top;//栈顶元素的下一个位置，简称栈顶位标
int size;//当前分配的字储容量
int increment;//扩容时，增加的存储容量
} SqStack; //顺序栈
// 初始化一个栈，size为栈的初始容量，inc为栈增容时的容量。一般而言，
可令size 为MAXSIZE，inc为INCREMENT
Status InitStack_Sq(SqStack &S,int size,int inc);
Status DestroyStack Sq(SqStack S); // 销毁栈
//检查栈是否为空。如果为空，则返回TRUE，否则返回FALSE
Status StackEmpty Sq(SqStack S);
Status Push_Sq(SqStack &S,ElemType e); //将元素e进栈
Status Pop_Sq(SqStack &5,ElemType &e); //出栈，并且栈顶元亲赋给e
Status GetTop_Sq(SqStack& S,ElemType& e);//将栈顶元素赋给e，但栈顶元素不出栈
#include "allinclude.h"
Status matchBracketSequence(char* exp, int n)
{ // Add your code here
SqStack S;
InitStack_Sq(S,20,5);
ElemType temp;
for(int i=0;i<n;i++)
{
switch(exp[i])
{
case '(' :
case '[' :
case '{' : {
Push_Sq(S,exp[i]);
break;
}
case ')' :
case ']' :
case '}' : {
if(StackEmpty_Sq(S)==true)
return false;
GetTop_Sq(S,temp);
if(temp=='(' && exp[i]==')' || temp=='{' && exp[i]=='}' || temp=='[' && exp[i]==']' )
Pop_Sq(S,temp);
}
}
}
if(StackEmpty_Sq(S))
return true;
return false;
}11.DC02PE23
【题目】试编写算法，求循环队列的长度。
循环队列的类型定义为∶
typedef struct {
ElemType *base; //存储空间的基址
int front; //队头位标
int rear; //队尾位标，指示队尾元素的下一位置
int maxSize;/ /最大长度
} SqQueue;
要求实现下列函数∶
int QueueLength Sq(SqQueue Q);
/* 返回队列Q中元素个数，即队列的长度。*/
#include "allinclude.h" //DO NOT edit this line
int QueueLength_Sq(SqQueue Q) {
// Add your code here
int length;
if(Q.front==Q.rear)
return 0;
else if (Q.front>Q.rear)
length=(Q.rear+Q.maxSize)-Q.front;
else length= Q.rear-Q.front;
return length;
}
12.DC02PE25
【题目】如果希望循环队列中的元素都能得到利用，则可设置一个标志域tag，并以tag值为0或1来区分尾指针和头指针值相同时的队列状态是"空"还是"满'。试编写与此结构相应的入队列和出队列的算法。
注∶如果队列为空，则需保证标志域tag的值为0;如果队列已满，则需保证标
志域tag的值为1。否则，程序运行后会无输出，导致不能通过。
本题的循环队列CTagQueue的类型定义如下∶
typedef struct {
ElemType elem[AXQSIZE];
int tag;
int front;
int rear;
} CTagQueue;
实现下列函数∶
Status EnCQueue(CTagQueue &0,ElemType x);
/* 将元素x加入队列Q，并返回0K;*/
/*若失败，则返回ERROR。*/
Status DeCQueue(CTagQueue &Q,ElemType &x);
/* 将队列Q的队头元素退队到x，并返回OK; */
/* 若失败，则返回ERROR。*/
#include "allinclude.h" //DO NOT edit this line
Status EnCQueue(CTagQueue &Q, ElemType x) {
// Add your code here
if(Q.tag==1)
return ERROR; //队满
else
Q.elem[Q.rear]=x;
Q.rear=(Q.rear+1)%MAXQSIZE;
if(Q.rear==Q.front) //插入后队满
Q.tag=1;
return OK;
}
Status DeCQueue(CTagQueue &Q, ElemType &x){
// Add your code here
if( Q.rear==Q.front && Q.tag==0)
return ERROR; //队空
else
x=Q.elem[Q.front];
Q.front=(Q.front+1)%MAXQSIZE;
if(Q.rear==Q.front) //出队后队空
Q.tag=0;
return OK;
}
13.DC02PE27
【题目】假设将循环队列定义为∶以域变量rear和length分别指示循环队列中队尾元素的位置和内含元素的个数。试给出此循环队列的队满条件，并写出相应的入队列和出队列的算法（在出队列的算法中要返回队头元素）。
本题的循环队列CLenQueue的类型定义如下∶
typedef struct {
ElemType elem[NAXQSIZE];
int length;
int rear;
} CLenQueue;
实现下列函数∶
Status EnCQueue(CLenQueue &Q, ElemType x);
/*将元素x加入队列Q，并返回OK;*/
/* 若失败，则返回ERROR。*/
Status DeCQueue(CLenQueue &Q,ElemType &x);
/* 将队列Q的队头元素退队到x，并返回OK;*/
/*若失败，则返回ERROR。*/
#include "allinclude.h" //DO NOT edit this line
Status EnCQueue(CLenQueue &Q, ElemType x) {
// Add your code here
if(Q.length==MAXQSIZE)
return ERROR;
Q.rear=(Q.rear+1)%MAXQSIZE;
Q.elem[Q.rear]= x;
Q.length++;
return OK;
}
Status DeCQueue(CLenQueue &Q, ElemType &x){
// Add your code here
if(Q.length==0)
return ERROR;
if(Q.rear>Q.length)
x= Q.elem[Q.rear+1-Q.length];
else
x= Q.elem[Q.rear+1+MAXQSIZE-Q.length] ;
Q.length--;
return OK;
}
14.DC02PE32
【题目】已知k阶斐波那契序列的定义为∶
f0=0,f1=0, .…, fk-2=0,fk-1=1;
fn=fn-1+fn-2+...+fn-k, n=k,k+1, ...
试利用循环队列编写求k阶斐波那契序列中第n+1项fn的算法。
本题的循环队列的类型定义如下∶
typedef struct {
ElemType *base; //存储空间的基址
int front ; //队头位标
int rear; //队尾位标，指示队尾元素的下一位置
int maxSize; //最大长度
} SqQueue;
要求实现下列函数∶long Fib(int k,int n);
/* 求k阶斐波那契数列的第n+1项 fn*/
#include "allinclude.h" //DO NOT edit this line
long Fib(int k, int n) {
// Add your code here
SqQueue Q;
int sum,j;
Q.base=(ElemType *)malloc((n+1)*sizeof(ElemType));
Q.front=Q.rear=0;
Q.maxSize=n+1;
for(Q.rear=0;Q.rear<k-1;Q.rear++)
Q.base[Q.rear]=0; //0~K-2项全为0
Q.base[Q.rear++]=1;
for(Q.rear=k;Q.rear<n+1;Q.rear++) //n+1项即base[n]
{
sum=0;
for(j=Q.rear-k;j<Q.rear;j++)
sum+=Q.base[j];
Q.base[Q.rear]=sum;
}
return Q.base[n];
}15.DC02PE33
【题目】设A=（a1，….，am）和B=（b1，….，bn）均为有序顺序表，A'和B'分别为A和B中除去最大共同前缀后的子表（例如，A=（x，y，y，z，x，z），B=（x，y，y，z，y，x，x，z），则两者中最大的共同前缀为（x，y ，y，z），在两表中除去最大共同前缀后的子表分别为A'=（x，z）和B'=（y，x，x，z ）)。若A'=B'=空表，则A=B;若A'=空表，而B'≠空表，或者两者均不为空表，且A'的首元小于B'的首元，则A<B;否则A >B。试写一个比较A和B大小的算法。（注意∶在算法中，不要破坏原表A和B ，也不一定先求得A'和B'才可以进行比较）。
顺序表类型定义如下∶
typedef struct {
ElemType *elem ；
int length;
int size;
int increment;
} SqList;
要求实现下列函数∶
char Compare(SqList A,SqList B);
/* 比较顺序表A和B */
/* 返回'<'，若A<B; */
/* '='，若A=B; */
/* '>', 若A>B; */
#include "allinclude.h" //DO NOT edit this line
char Compare(SqList A, SqList B)
{ // Add your code here
if(A.length==0 && B.length==0)
return '=';
if(A.length==0 && B.length!=0)
return '<';
if(A.length!=0 && B.length==0)
return '>';
int i=0;
for(;i<A.length;i++) //A遍历完成后退出
{
if(i==B.length) //B先完成了
return '>';
if(A.elem[i]==B.elem[i])
continue;
else{ if(A.elem[i]>B.elem[i]) //出现不一致
return '>';
return '<';
}
}
if( i<B.length) //i==A.length 前缀相同，如果A长度小
return '<';
return '=';
}16.DC02PE35
【题目】试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表（a1，a2，….，an）逆置为（an，an-1，…，a1）。
顺序表类型定义如下∶
typedef struct {
ElemType *elem;
int length;
int size;
int increment;
} SqList;
实现下列函数∶
void Inverse(SqList &L);
#include "allinclude.h" //DO NOT edit this line
void Inverse(SqList &L)
{ // Add your code here
ElemType temp;
for(int i=0;i<L.length/2;i++)
{
temp = L.elem[i];
L.elem[i] = L.elem[L.length-i-1];
L.elem[L.length-i-1] = temp;
}
}17.DC02PE45
【题目】假设有两个集合A和B分别用两个线性表LA和LB表示
（即∶线性表中的数据元素即为集合中的成员），试写一算法，求并集A=AUB 。
顺序表类型定义如下
typedef struct{
ElemType *elem;// 存储空间的基址
int length;//当前长度
int size; // 存储容量
int increment; // 空间不够增加空间大小
} SqList;
// 顺序表
可调用顺序表的以下接口函数∶
Status InitList_Sq（SqList &L，int size，int inc）; //初始化顺序表L
int ListLength_Sq（SqList L）; // 返回顺序表L中元素个数
Status GetElem_Sq(SqList L,int i,ElemType &e);
//用e返回顺序表L中第i个元素的值
int Search_Sq(SqList L,ElemType e);
// 在顺序表L顺序查找元素e，成功时返回该元素在表中第一次出现的位置，否则返回-1
Status Append_Sq（SqList &L，ElemType e）; //在顺序表L表尾添加元素e
实现如下算法∶
void Union(SqList &La,List Lb)；
#include "allinclude.h" //DO NOT edit this line
void Union(SqList &La, List Lb)
{ // Add your code here
int i=0;
for(;i<Lb.length;i++)
{
if(La.length==La.size)
{
realloc(La.elem,(La.size+La.increment)*sizeof(ElemType));
La.size+=La.increment;
}
if(-1 == Search_Sq(La,Lb.elem[i]))
Append_Sq(La,Lb.elem[i]);
}
}18.DC02PE53
【题目】试写一算法，实现链栈的判空操作。
链栈的类型定义为∶
typedef struct LSNode {
ElemType data; //数据域
struct LSNode *next; //指针域
}LSNode，*LStack; //结点和链栈类型
要求实现下列函数∶
Status StackEmpty_L(LStack S);
/* 对链栈判空。若S是空栈，则返回TRUE; 否则返回FALSE */
#include "allinclude.h" //DO NOT edit this line
Status StackEmpty_L(LStack S)
{ // Add your code here
if(S ==NULL)
return true;
else return false;
}19.DC02PE55
【题目】试写一算法，实现链栈的取栈顶元素操作。
链栈的类型定义为∶
typedef struct LSNode {
ElemType data; //数据域
struct LSNode *next; //指针域
} LSNode，*LStack;//结点和链栈类型
要求实现下列函数∶
Status GetTop_L(LStack S,ElemType &e);
/* 取链栈S的栈顶元素到e，并返回OK; */
/* 若S是空栈，则失败，返回ERROR。*/
#include "allinclude.h" //DO NOT edit this line
Status GetTop_L(LStack S, ElemType &e)
{ // Add your code here
if(S == NULL)
return ERROR;
e=S->data;
return OK;
}
20.DC02PE61
【题目】试写一算法，实现链队列的判空操作。
链队列的类型定义为∶
typedef struct LQNode {
ElemType data;
struct LONode *next;
}LQNode，*QueuePtr; //结点和结点指针类型
typedef struct {
QueuePtr front;// 头指针
QueuePtr rear;// 队尾指针
} LQueue; // 链队列类型
要求实现下列函数∶
Status QueueEmpty_LQ(LQueue Q);/* 判定链队列Q是否为空队列。*/
/* 若Q是空队列，则返回TRUE，否则FALSE。*/
#include "allinclude.h" //DO NOT edit this line
Status QueueEmpty_LQ(LQueue Q)
{ // Add your code here
if(Q.front==NULL|| NULL == Q.rear)
return true;
return false;
}21.DC02PE63
【题目】试写一算法，实现链队列的求队列长度操作。链队列的类型定义为∶
typedef struct LONode {
ElemType data;
struct LONode *next;
}LQNode，*QueuePtr;//结点和结点指针类型
typedef struct {
QueuePtr front;// 头指针
QueuePtr rear; // 队尾指针
} LQueue; //链队列类型
要求实现下列函数∶
int QueueLength_LQ(LQueue Q);
/* 求链队列Q的长度并返回其值*/
#include "allinclude.h" //DO NOT edit this line
int QueueLength_LQ(LQueue Q)
{ // Add your code here
if(Q.front==NULL|| NULL == Q.rear)
return 0;
int length=1;
QueuePtr temp = Q.front;
for(;temp!=Q.rear;temp=temp->next)
length++;
return length;
}22.DC02PE68
【题目】假设以带头结点的循环链表表示队列，并目只设一个指针指向队尾元素结点 （注意不设头指针），试编写相应的队列初始化、入队列和出队列的算法。
带头结点循环链队列CLQueue的类型定义为∶
typedef char ElemType;
typedef struct CLONode {
ElemType data;
struct CLQNode *next;
}CLQNode，*CLQueue;//结点和结点指针类型
实现下列函数∶
Status InitCLQueue（CLQueue &rear）;//始化空队列
Status EnCLQueue（CLQueue &rear，ElemType x）;// 入队
Status DeCLQueue（CLQueue &rear，ElemType &x）;// 出队
#include "allinclude.h" //DO NOT edit this line
Status InitCLQueue(CLQueue &rear)
{ // Add your code here
rear=(LQNode *)malloc(sizeof(LQNode));
rear->next= rear;
return OK;
}
Status EnCLQueue(CLQueue &rear, ElemType x)
{ // Add your code here
LQNode *temp=(LQNode*)malloc(sizeof(LQNode));
temp->data=x;
temp->next=rear->next;
rear->next=temp;
rear=temp;
return OK;
}
Status DeCLQueue(CLQueue &rear, ElemType &x)
{ // Add your code here
if(rear->next==rear)
return ERROR;
LQNode *temp=rear->next->next;
x=temp->data;
rear->next->next=rear->next->next->next;
free(temp);
temp=NULL;
return OK;
}23.DC02PE71
【题目】试写一算法，实现带头结点单链表的判空操作。
单链表的类型定义为∶
typedef struct LNode {
ElemType data;
struct LNode *next;
}LNode，*LinkList; //结点和结点指针类型
要求实现下列函数∶
Status ListEmpty_L(LinkList L);
/* 判定带头结点单链表L是否为空链表。*/
/* 若L是空链表，则返回TRUE，否则FALSE。*/
#include "allinclude.h" //DO NOT edit this line
Status ListEmpty_L(LinkList L)
{ // Add your code here
if(L->next==NULL)
return true;
return false;
}
24.DC02PE73
【题目】试写一算法，实现带头结点单链表的销毁操作。单链表的类型定义为∶
typedef struct LNode {
ElemType data;
struct LNode *next;
}LNode，*LinkList; //结点和结点指针类型
要求实现下列函数∶
Status DestroyList_L(LinkList &L);/* 销毁带头节点单链表L，并返回0K。*/
#include "allinclude.h" //DO NOT edit this line
Status DestroyList_L(LinkList &L)
{ // Add your code here
LNode *temp1,*temp=L->next;
while(temp!=NULL)
{
temp1=temp;
temp=temp->next;
free(temp1);
}
free(L);
L=NULL;
return OK;
}
25.DC02PE75
【题目】试写一算法，实现带头结点单链表的清空操作。
单链表的类型定义为∶
typedef struct LNode {
ElemType data;
struct LNode *next;
}LNode，*LinkList; //结点和结点指针类型
要求实现下列函数∶
Status ClearList_L(LinkList &L);
/* 将带头结点单链表L置为空表，并返回OK。*/
/* 若L不是带头结点单链表，则返回ERROR。 */
#include "allinclude.h" //DO NOT edit this line
Status ClearList_L(LinkList &L)
{ // Add your code here
if(L==NULL)
return ERROR;
LinkList temp=L->next,temp1;
while(temp!=NULL)
{
temp1=temp;
temp=temp->next;
free(temp1);
}
L->next=NULL;
return OK;
}26.DC02PE77
【题目】试写一算法，实现带头结点单链表的求表长度操作。
单链表的类型定义为∶
typedef struct LNode {
ElemType data;
struct LNode *next;
} LNode，*LinkList;// 结点和结点针类型
要求实现下列函数∶
int ListLength_L(LinkList L);
/* 求带头结点单链表L的长度，并返回长度值。*/
/* 若L不是带头结点单链表，则返回-1。 */
#include "allinclude.h" //DO NOT edit this line
int ListLength_L(LinkList L)
{ // Add your code here
int length=0;
if(L==NULL)
return -1;
while(L->next!=NULL) //头结点数据域存辅助信息，或者不存储，所以跳过它
{ length++;
L=L->next;
}
return length;
}
27.DC02PE82
【题目】试写一算法，在带头结点单链表L的第i个位置插入e。
带头结点单链表的类型定义为∶
typedef struct LNode {
ElemType data;
struct LNode *next;
} LNode,*LinkList;
实现下列函数∶
Status Insert_L(LinkList L,int i,ElemType e);/* 在带头结点单链表L的第i个位置插入e，并返回OK。*/
/* 若参数不合理，则返回ERROR。*/
#include "allinclude.h" //DO NOT edit this line
Status Insert_L(LinkList L, int i, ElemType e)
{ // Add your code here
if(i<1||L==NULL)
return ERROR;
LinkList temp=L;
int l=0;
while(l<i-1 && temp->next)
{
temp=temp->next;
l++;
} //temp指向i-1，temp->next就是插入位置
if(l<i-1) //由于temp->next==NULL跳出循环，所以l<i-1
return ERROR;
LNode* E = (LNode*)malloc(sizeof(LNode));
E->data=e;
E->next=temp->next;
temp->next=E;
return OK;
}28.DC02PE84
【题目】试写一算法，在带头结点单链表L删除第i位置的结点，并用变量e返回该结点的数据元素值。带头结点单链表的类型定义为∶
typedef struct LNode {
ElemType data;
struct LNode *next;
} LNode,*LinkList;
实现下列函数∶
Status Delete_L(LinkList L,int i,ElemType &e);
/* 在带头结点单链表L删除第i元素到e，并返回OK。*/
/* 参数不合理，则返回ERROR。*/
#include "allinclude.h" //DO NOT edit this line
Status Delete_L(LinkList L, int i, ElemType &e)
{ // Add your code here
if(i<1||L==NULL)
return ERROR;
int length=0;
LinkList temp=L;
while(length<i-1 && temp->next!=NULL)
{
length++;
temp=temp->next;
}
if(length<i-1||temp->next==NULL)
return ERROR;
LinkList E=temp->next;
e =E->data;
temp->next=E->next;
free (E);
E=NULL;
return OK;
}29.DC02PE86
【题目】试写一算法，在带头结点单链表的第i元素起的所有元素从链表移除，并构成一个带头结点的新链表。带头结点单链表的类型定义为∶
typedef struct LNode {
ElemType data;
struct LNode *next;
} LNode,*LinkList;
实现下列函数∶
Status Split_L(LinkList L,LinkList &Li,int i);
/* 在带头结点单链表L的第i元素起的所有元素 */
/* 移除，并构成带头结点链表Li，返回OK。*/
/* 若参数不合理，则Li为NULL，返回ERROR。*/
#include "allinclude.h" //DO NOT edit this line
Status Split_L(LinkList L, LinkList &Li, int i)
{ // Add your code here
if(i<1||L==NULL)
{ Li=NULL;
return ERROR;
}
int length=0;
LinkList temp=L;
while(length<i-1 && temp->next!=NULL)
{
length++;
temp=temp->next;
}
if(length<i-1||temp->next==NULL)
{ Li=NULL;
return ERROR;
}
Li=(LinkList)malloc(sizeof(LNode));
Li->next=temp->next;
temp->next=NULL;
}30.DC02PE88
【题目】试写一算法，在带头结点单链表删除第i元素起的所有元素。
带头结点单链表的类型定义为∶
typedef struct LNode {
ElemType data;
struct LNode *next;
} LNode,*LinkList;
实现下列函数∶
Status Cut_L(Linklist L,int i);
/* 在带头结点单链表L删除第i元素起的所有元素，并返回OK。*/
/* 若参数不合理，则返回ERROR。 */
#include "allinclude.h" //DO NOT edit this line
Status Cut_L(LinkList L, int i)
{ // Add your code here
if(i<1||L==NULL)
return ERROR;
int length=0;
LinkList temp=L;
while(length<i-1 && temp->next!=NULL)
{
length++;
temp=temp->next;
}
if(length<i-1||temp->next==NULL)
return ERROR;
LinkList temp1=temp->next;
temp->next=NULL;
while(temp1->next!=NULL)
{
temp=temp1;
temp1=temp1->next;
free(temp);
temp=NULL;
}
return OK;
}31.DC02PE90
【题目】试写一算法，删除带头结点单链表中所有值为x的元素，并释放被删结点空间。
单链表类型定义如下∶typedef struct LNode {
ElemType data;
struct LNode *next;
} LNode,*LinkList;
实现下列函数∶
Status DeleteX_L(LinkList L,ElemType x);
/* 删除带头结点单链表L中所有值为x的元素，
/* 并释放被删结点空间，返回实际删除的元素个数。*/
#include "allinclude.h" //DO NOT edit this line
Status DeleteX_L(LinkList L, ElemType x)
/* 删除带头结点单链表L中所有值为x的元素， */
/* 并释放被删结点空间，返回实际删除的元素个数。*/
{
LinkList p = L,q;
if (NULL == p)
return ERROR;
int num = 0;
while (p->next!= NULL)
{
q = p->next;
if (q->data == x)
{
p->next = q->next;
free(q);
num++;
}
else
p = p->next;
}
return num;
}
32.DC02PE91
【题目】试写一算法，删除带头结点单链表中所有值小干x的元素，并释放被删结点空间。单链表类型定义如下∶
typedef struct LNode{
ElemType data;
struct LNode *next;
} LNode,*LinkList;
实现下列函数∶
Status DeleteSome_L(LinkList L,ElemType x);
/* 删除带头结点单链表L中所有值小干x的元素，
/* 并释放被测结点空间，返回实际删除的元素个数。*/
#include "allinclude.h" //DO NOT edit this line
Status DeleteSome_L(LinkList L, ElemType x)
{ // Add your code here
if(L==NULL)
return ERROR;
int num=0;
LinkList temp=L,temp1;
while(temp->next!=NULL)
{
temp1=temp->next;
if(temp1->data<x)
{
temp->next=temp1->next;
free(temp1);
temp1=NULL;
num++;
}
else
temp=temp->next;
}
return num;
}