Anyview数据结构-2

Posted on | Post modified: | In
Words count in article: 4,452 | Reading time ≈ 20

-广工Anyview题解
-数据结构部分-2

/**
【题目】试写一算法，实现顺序栈的判空操作
StackEmpty_Sq(SqStack S)。
顺序栈的类型定义为：
typedef struct {
ElemType elem; // 存储空间的基址
int top; // 栈顶元素的下一个位置，简称栈顶位标
int size; // 当前分配的存储容量
int increment; // 扩容时，增加的存储容量
} SqStack; // 顺序栈
**/

1
2
3
4
5
6
7
8
9
Status StackEmpty_Sq(SqStack S)
/* 对顺序栈S判空。                      */ 
/* 若S是空栈，则返回TRUE；否则返回FALSE */
{
    if(S.top==0)
        return TRUE;
    else
        return FALSE;
}

/**
【题目】试写一算法，实现顺序栈的取栈顶元素操作
GetTop_Sq(SqStack S, ElemType &e)。
顺序栈的类型定义为：
typedef struct {
ElemType elem; // 存储空间的基址
int top; // 栈顶元素的下一个位置，简称栈顶位标
int size; // 当前分配的存储容量
int increment; // 扩容时，增加的存储容量
} SqStack; // 顺序栈
**/

1
2
3
4
5
6
7
8
9
Status GetTop_Sq(SqStack S, ElemType &e) 
/* 取顺序栈S的栈顶元素到e，并返回OK； */ 
/* 若失败，则返回ERROR。              */
{
     if(S.top==0)
        return ERROR;
     e=S.elem[--S.top];
     return OK;
}

/**
【题目】若顺序栈的类型重新定义如下。试编写算法，
构建初始容量和扩容增量分别为size和inc的空顺序栈S。
typedef struct {
ElemType elem; // 存储空间的基址
ElemType top; // 栈顶元素的下一个位置
int size; // 当前分配的存储容量
int increment; // 扩容时，增加的存储容量
} SqStack2;
*/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Status InitStack_Sq2(SqStack2 &S, int size, int inc)
/* 构建初始容量和扩容增量分别为size和inc的空顺序栈S。*/ 
/* 若成功，则返回OK；否则返回ERROR。                 */
{
    S.elem=(ElemType*)malloc(S.size*sizeof(ElemType));
    if(S.elem==NULL)   //构建失败 
        return ERROR;
    if(size<0||inc<0)     //参数错误
        return ERROR;
    S.size=size;
    S.increment=inc;
    S.top=S.elem;
    return OK;           
}

/**
【题目】若顺序栈的类型重新定义如下。试编写算法，
实现顺序栈的判空操作。
typedef struct {
ElemType elem; // 存储空间的基址
ElemType top; // 栈顶元素的下一个位置
int size; // 当前分配的存储容量
int increment; // 扩容时，增加的存储容量
} SqStack2;
*/

1
2
3
4
5
6
7
8
9
Status StackEmpty_Sq2(SqStack2 S)
/* 对顺序栈S判空。                      */ 
/* 若S是空栈，则返回TRUE；否则返回FALSE */
{
    if(S.top==S.elem)
        return TRUE;
    else
        return FALSE;
}

/**
【题目】若顺序栈的类型重新定义如下。试编写算法，
实现顺序栈的入栈操作。
typedef struct {
ElemType elem; // 存储空间的基址
ElemType top; // 栈顶元素的下一个位置
int size; // 当前分配的存储容量
int increment; // 扩容时，增加的存储容量
} SqStack2;
*/

1
2
3
4
5
6
7
8
9
10
11
12
Status Push_Sq2(SqStack2 &S, ElemType e)
/* 若顺序栈S是满的，则扩容，若失败则返回ERROR。*/
/* 将e压入S，返回OK。                          */
{
    if(S.size==S.increment)  //顺序栈已满
        S.elem=(ElemType*)realloc(S.elem,(S.size+S.increment)*sizeof(ElemType));
    if(S.elem==NULL)    //顺序栈扩容失败
        return ERROR;
    *S.top++=e;
    S.size=S.size+S.increment;
    return OK;
}

/**
【题目】若顺序栈的类型重新定义如下。试编写算法，
实现顺序栈的出栈操作。
typedef struct {
ElemType elem; // 存储空间的基址
ElemType top; // 栈顶元素的下一个位置
int size; // 当前分配的存储容量
int increment; // 扩容时，增加的存储容量
} SqStack2;
*/

1
2
3
4
5
6
7
8
9
Status Pop_Sq2(SqStack2 &S, ElemType &e) 
/* 若顺序栈S是空的，则返回ERROR；    */ 
/* 否则将S的栈顶元素出栈到e，返回OK。*/
{
    if(S.top==S.elem)   //顺序栈为空  
        return ERROR;
    e=*(--S.top);
    return OK;
}

/**
【题目】试写一算法，借助辅助栈，复制顺序栈S1得到S2。
顺序栈的类型定义为：
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(SqStack &S, ElemType e); // 将元素e压入栈S
Status Pop_Sq(SqStack &S, ElemType &e); // 栈S的栈顶元素出栈到e
**/
解题思路：栈是先进后出的，因此借用S3，需要用来两次倒序，第一次倒序插入S3，再将S3倒序插入S2，即所有元素正序，即完成复制顺序栈操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
Status CopyStack_Sq(SqStack S1, SqStack &S2) 
/* 借助辅助栈，复制顺序栈S1得到S2。    */ 
/* 若复制成功，则返回TRUE；否则FALSE。 */
{
     SqStack S3;
     int e;
     InitStack_Sq(S2,S1.size,S1.increment);
     InitStack_Sq(S3,S1.size,S1.increment);
     while(StackEmpty_Sq(S1)!=TRUE){ //先将S1元素倒序插入S3
       Pop_Sq(S1,e);
       Push_Sq(S3,e);
       }
     if(S3.elem==NULL)    //S1倒序插入S3失败
        return ERROR;
     while(StackEmpty_Sq(S3)!=TRUE){ //再将S3元素倒序插入S2
       Pop_Sq(S3,e);
       Push_Sq(S2,e);
       }
     if(S2.elem==NULL)   //S3倒序插入S2失败
        return FALSE;
     return OK;       
}

/**
【题目】试写一算法，求循环队列的长度。
循环队列的类型定义为：
typedef struct {
ElemType base; // 存储空间的基址
int front; // 队头位标
int rear; // 队尾位标，指示队尾元素的下一位置
int maxSize; // 最大长度
} SqQueue;
**/

1
2
3
4
5
int QueueLength_Sq(SqQueue Q)
/* 返回队列Q中元素个数，即队列的长度。 */ 
{
   return (Q.rear-Q.front+Q.maxSize)%Q.maxSize;
}

/**
【题目】如果希望循环队列中的元素都能得到利用，
则可设置一个标志域tag，并以tag值为0或1来区分尾
指针和头指针值相同时的队列状态是”空”还是”满”。
试编写与此结构相应的入队列和出队列的算法。
本题的循环队列CTagQueue的类型定义如下：
typedef struct {
ElemType elem[MAXQSIZE];
int tag;
int front;
int rear;
} CTagQueue;
**/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
Status EnCQueue(CTagQueue &Q,ElemType x)
/* 将元素x加入队列Q，并返回OK；*/
/* 若失败，则返回ERROR。       */
{
   if(Q.tag==1&&Q.front==Q.rear)
        return ERROR;
   Q.elem[Q.rear]=x;
   Q.rear=(Q.rear+1)%MAXQSIZE;
   if(Q.front==Q.rear)
   Q.tag=1;
   return OK ;
} 
Status DeCQueue(CTagQueue &Q, ElemType &x)
/* 将队列Q的队头元素退队到x，并返回OK；*/
/* 若失败，则返回ERROR。               */
{ 
     if(Q.tag==0&&Q.front==Q.rear)
       return ERROR;
      x=Q.elem[Q.front];
      Q.front=(Q.front+1)%MAXQSIZE;
      if(Q.front==Q.rear)
         Q.tag=0;
      return OK; 
}

/**
【题目】假设将循环队列定义为：以域变量rear
和length分别指示循环队列中队尾元素的位置和内
含元素的个数。试给出此循环队列的队满条件，并
写出相应的入队列和出队列的算法（在出队列的算
法中要返回队头元素）。
本题的循环队列CLenQueue的类型定义如下：
typedef struct {
ElemType elem[MAXQSIZE];
int length;
int rear;
} CLenQueue;
**/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
Status EnCQueue(CLenQueue &Q, ElemType x)
  /* 将元素x加入队列Q，并返回OK；*/
  /* 若失败，则返回ERROR。       */
{
    if(Q.length==MAXQSIZE)  //队列满
      return ERROR;
    Q.elem[Q.rear]=x;
    Q.rear=(Q.rear+1)%MAXQSIZE; 
    Q.length++;
    return TRUE;
}
Status DeCQueue(CLenQueue &Q, ElemType &x)
  /* 将队列Q的队头元素退队到x，并返回OK；*/
  /* 若失败，则返回ERROR。               */
{
    if(Q.length==0)     //队列空
        return ERROR;   
    int front;         
    front=MAXQSIZE-Q.length+Q.rear;
    x=Q.elem[front%MAXQSIZE];
    front=(front+1)%MAXQSIZE;
    Q.length--;
    return OK;
}

/**
【题目】已知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;
*/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
long Fib(int k, int n)
/* 求k阶斐波那契序列的第n+1项fn */
{
    int i,j ;
   if(1 >=k|| 0 > n) return ERROR;
   SqQueue fib;
   fib.base = (ElemType*)malloc(30*sizeof(ElemType));
   fib.maxSize = 30;
   fib.front = fib.rear = 0;
   for(;fib.rear < k;fib.rear++)
   {
        if(fib.rear<k-1) 
            fib.base[fib.rear] = 0;
        else
            fib.base[fib.rear] = 1;
   }
   
   while(fib.rear <= n)
   {
        j = 1;
        while(j <= k)
        {
             fib.base[fib.rear] +=fib.base[fib.rear-j];
             j++;
         }
        fib.rear++;
  }
    return fib.base[n];
}

/**
【题目】设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’的首元，则AB。试写一个比
较A和B大小的算法。（注意：在算法中，不要破坏原表A
和B，也不一定先求得A’和B’才进行比较）。
顺序表类型定义如下：
typedef struct {
ElemType elem;
int length;
int size;
int increment;
} SqList;
*/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
char Compare(SqList A, SqList B)
/* 比较顺序表A和B,      */
/*   返回'<', 若A<B;    */
/*       '=', 若A=B;    */
/*       '>', 若A>B     */
{     
    int i=0;  //计数器    
    while(A.elem[i]==B.elem[i]&&i<A.length&&i<B.length)         
        i++;      
    if(A.length==B.length)
        return '=';      
    else if(A.elem[i]<B.elem[i]||i==A.length)         
        return '<';      
    else if(A.elem[i]>B.elem[i]||i==B.length) 
        return '>';
}

/**
【题目】试写一算法，实现顺序表的就地逆置，
即利用原表的存储空间将线性表(a1,a2,…,an)
逆置为(an,an-1,…,a1)。
顺序表类型定义如下：
typedef struct {
ElemType elem;
int length;
int size;
int increment;
} SqList;
*/

1
2
3
4
5
6
7
8
9
10
void Inverse(SqList &L)
{
   int i;
   int temp;
   for(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;
    }
}

/**
【题目】试对一元稀疏多项式Pn(x)采用存储量同多项式
项数m成正比的顺序存储结构，编写求Pn(x0)的算法（x0
为给定值）。
一元稀疏多项式的顺序存储结构:
typedef struct {
int coef; // 系数
int exp; // 指数
} Term;
typedef struct {
Term elem; // 存储空间基址
int length; // 长度（项数）
} Poly;
*/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
float Evaluate(Poly P, float x)
/* P.elem[i].coef 存放ai，                        */
/* P.elem[i].exp存放ei (i=1,2,...,m)              */
/* 本算法计算并返回多项式的值。不判别溢出。       */
/* 入口时要求0≤e1<e2<...<em，算法内不对此再作验证 */
{
    int i,j;
    float sum=0,sum1;
    for(i=0;i<P.length;i++)
    {
        sum1=P.elem[i].coef ;
        for(j=0;j<P.elem[i].exp;j++)
          sum1=sum1*x;
        sum+=sum1;
    }
    return sum;
}

/**
【题目】假设有两个集合A和B分别用两个线性表LA和LB
表示(即：线性表中的数据元素即为集合中的成员），
试写一算法，求并集A＝A∪B。
顺序表类型定义如下
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
*/

1
2
3
4
5
6
7
8
9
10
11
void Union(SqList &La, SqList Lb)
{
    int i,j;
    ElemType e;
    for(i=0;i<Lb.length;i++){     
         GetElem_Sq(Lb,i+1,e);
         if(-1==Search_Sq(La,e))
            Append_Sq(La,e);
    }
    La.length = ListLength_Sq(La);
}

/**
【题目】试写一算法，实现链栈的判空操作。
链栈的类型定义为：
typedef struct LSNode {
ElemType data; // 数据域
struct LSNode next; // 指针域
} LSNode, LStack; // 结点和链栈类型
*/

1
2
3
4
5
6
7
8
Status StackEmpty_L(LStack S)
/* 对链栈S判空。若S是空栈，则返回TRUE；否则返回FALSE */
{
   if(S==NULL)
        return TRUE;
   else
        return FALSE;
}

/**
【题目】试写一算法，实现链栈的取栈顶元素操作。
链栈的类型定义为：
typedef struct LSNode {
ElemType data; // 数据域
struct LSNode next; // 指针域
} LSNode, LStack; // 结点和链栈类型
*/

1
2
3
4
5
6
7
8
9
10
11
Status GetTop_L(LStack S, ElemType &e) 
/* 取链栈S的栈顶元素到e，并返回OK; */
/* 若S是空栈，则失败，返回ERROR。  */
{
    LSNode *p;
    if(S==NULL)
        return ERROR;
    else
        e=S->data;
    return OK;
}

/**
【题目】试写一算法，实现链队列的判空操作。
链队列的类型定义为：
typedef struct LQNode {
ElemType data;
struct LQNode next;
} LQNode, QueuePtr; // 结点和结点指针类型
typedef struct {
QueuePtr front; // 队头指针
QueuePtr rear; // 队尾指针
} LQueue; // 链队列类型
*/

1
2
3
4
5
6
7
8
9
Status QueueEmpty_LQ(LQueue Q)
/* 判定链队列Q是否为空队列。           */
/* 若Q是空队列，则返回TRUE，否则FALSE。*/
{
    if(Q.rear==NULL)
        return TRUE;
    else
        return FALSE;
}

/**
【题目】试写一算法，实现链队列的求队列长度操作。
链队列的类型定义为：
typedef struct LQNode {
ElemType data;
struct LQNode next;
} LQNode, QueuePtr; // 结点和结点指针类型
typedef struct {
QueuePtr front; // 队头指针
QueuePtr rear; // 队尾指针
} LQueue; // 链队列类型
*/

1
2
3
4
5
6
7
8
9
10
11
12
13
int QueueLength_LQ(LQueue Q)
/* 求链队列Q的长度并返回其值 */
{
   LQNode *p=Q.front;
   int i=1;
   if(Q.rear==NULL)
        return ERROR;
   while(p!=Q.rear){
       p = p->next;
       i++;
   }
   return i;
}

/**
【题目】假设以带头结点的循环链表表示队列，并且
只设一个指针指向队尾元素结点(注意不设头指针)，
试编写相应的队列初始化、入队列和出队列的算法。
带头结点循环链队列CLQueue的类型定义为：
typedef struct LQNode {
ElemType data;
struct LQNode next;
} LQNode, CLQueue;
**/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
Status InitCLQueue(CLQueue &rear) // 初始化空队列
{ 
    LQNode *p;
    p=(LQNode*)malloc(sizeof(LQNode));
    if(p==NULL)
        return ERROR;
    p->next=p;
    rear=p;
    return OK;
}
Status EnCLQueue(CLQueue &rear, ElemType x) // 入队
{ 
    LQNode *p;
    p=(LQNode*)malloc(sizeof(LQNode));
    if(p==NULL)
        return ERROR;
    p->data=x;
    p->next=rear->next;
    rear->next=p;
    rear=p;
    return OK;
}
Status DeCLQueue(CLQueue &rear, ElemType &x) // 出队
{ 
   if(rear==rear->next)
       return ERROR;
   else{
       x=rear->next->next->data;
       rear->next->next=rear->next->next->next;
    }    
  return OK;
}

/**
【题目】试写一算法，实现带头结点单链表的判空操作。

单链表的类型定义为：
typedef struct LNode {
ElemType data;
struct LNode next;
} LNode, LinkList; // 结点和结点指针类型
*/

1
2
3
4
5
6
7
8
Status ListEmpty_L(LinkList L)
/* 判定带头结点单链表L是否为空链表。   */
/* 若L是空链表，则返回TRUE，否则FALSE。*/
{
   if(NULL == L->next) 
        return TRUE;
    return  FALSE;
}

/**
【题目】试写一算法，实现带头结点单链表的销毁操作。
单链表的类型定义为：
typedef struct LNode {
ElemType data;
struct LNode next;
} LNode, LinkList; // 结点和结点指针类型
*/

1
2
3
4
5
6
Status DestroyList_L(LinkList &L)
/* 销毁带头结点单链表L，并返回OK。*/
{
    free(L);
    return OK;
}

/**
【题目】试写一算法，实现带头结点单链表的清空操作。

单链表的类型定义为：
typedef struct LNode {
ElemType data;
struct LNode next;
} LNode, LinkList; // 结点和结点指针类型
*/

1
2
3
4
5
6
7
8
9
10
11
Status ClearList_L(LinkList &L)
/* 将带头结点单链表L置为空表，并返回OK。*/
/* 若L不是带头结点单链表，则返回ERROR。 */
{
   if(L==NULL) 
      return ERROR;
   if(L->next==NULL) 
      return OK;
   L->next=NULL;
   return OK;
}

/**
【题目】试写一算法，实现带头结点单链表的求表长度操作。
单链表的类型定义为：
typedef struct LNode {
ElemType data;
struct LNode next;
} LNode, LinkList; // 结点和结点指针类型
*/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int ListLength_L(LinkList L)
/* 求带头结点单链表L的长度，并返回长度值。*/
/* 若L不是带头结点单链表，则返回-1。      */
{  
   LNode *p;
   int i=0;
   if(NULL==L)
      return -1;
   p = L->next;
   while(p != NULL){
      p = p->next;
      i++;
   }
   return i;
}

/**
【题目】试写一算法，在带头结点单链表L插入第i元素e。
带头结点单链表的类型定义为：
typedef struct LNode {
ElemType data;
struct LNode next;
} LNode, LinkList;
**/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
Status Insert_L(LinkList L, int i, ElemType e)
/* 在带头结点单链表L插入第i元素e，并返回OK。*/
/* 若参数不合理，则返回ERROR。              */ 
{
    if(i==0)
        return ERROR;
    LinkList p,q,p1,b;
    int j=0,k=0;
    q=(LNode*)malloc(sizeof(LNode));
    q->data=e;
    q->next=NULL;
    p1=L;
    b=L;
    while(b!=NULL){        
        b=b->next;
        k++;
    }
    if(k<i)
        return ERROR;
    while(j<i){
        p=p1;
        p1=p->next;
        j++;    
    }
    q->next=p->next;
    p->next=q;
    return OK;
}

/**
【题目】试写一算法，在带头结点单链表的第i元素起的
所有元素从链表移除，并构成一个带头结点的新链表。
带头结点单链表的类型定义为：
typedef struct LNode {
ElemType data;
struct LNode next;
} LNode, LinkList;
**/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
Status Split_L(LinkList L, LinkList &Li, int i)
/* 在带头结点单链表L的第i元素起的所有元素 */
/* 移除，并构成带头结点链表Li，返回OK。   */
/* 若参数不合理，则Li为NULL，返回ERROR。  */
{
   if(i<=0||L==null) {
     Li==null;
     return ERROR;
     }
     
   LinkList a,b,c;
   int j=0,k=0;
   Li=(LNode*)malloc(sizeof(LNode));
   Li->next=null;
   a=L;
   b=L;
   while(a->next!=null){
     j++;
     a=a->next;
   }
   if(j<i) {
   Li=null;
   return ERROR;
   }
   while(k<i-1){
   b=b->next;
   k++;
   }
   c=b->next;
   Li->next=c;
   b->next=null;
   return OK;
}

/**
【题目】试写一算法，在带头结点单链表删除第i元素
起的所有元素。
带头结点单链表的类型定义为：
typedef struct LNode {
ElemType data;
struct LNode next;
} LNode, LinkList;
**/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
Status Cut_L(LinkList L, int i)
/* 在带头结点单链表L删除第i元素起的所有元素，并返回OK。*/
/* 若参数不合理，则返回ERROR。                         */
{
    LinkList p1,p2,p3;
    int j=0,k=0;
    p2=L;
    p1=L;
    p3=L;
    if(NULL==L||L->next==NULL)
        return ERROR;
        
    while(p1->next!=null){
       p1=p1->next;
       j++;
     }
    if(j<i||i==0)
        return ERROR;
 
    while(k<i){
       p2=p3;
       p3=p2->next;
       k++;
     }
    p2->next=null;
    return OK;
}

/**
【题目】试写一算法，删除带头结点单链表中所有值
为x的元素，并释放被删结点空间。
单链表类型定义如下：
typedef struct LNode {
ElemType data;
struct LNode next;
} LNode, LinkList;
**/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
Status DeleteX_L(LinkList L, ElemType x)
/* 删除带头结点单链表L中所有值为x的元素，      */
/* 并释放被删结点空间，返回实际删除的元素个数。*/
{
    LinkList p1,p2,p3;
    int j=0;
    if(NULL==L) 
        return ERROR;
    p1=p2=L;
    while(p2!=NULL){
      p2=p1->next;
      if(p2->data==x){
        p3=p2;
        p2=p3->next;
        p1->next=p2;
        free(p3);
        j++;
      }
      else if(p2->data!=x){
          p1=p2;
          p2=p1->next;
       }            
    }    
    return j;
}

/**
【题目】试写一算法，删除带头结点单链表中所有值
小于x的元素，并释放被删结点空间。
单链表类型定义如下：
typedef struct LNode {
ElemType data;
struct LNode next;
} LNode, LinkList;
**/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
Status DeleteSome_L(LinkList L, ElemType x)
/* 删除带头结点单链表L中所有值小于x的元素，    */
/* 并释放被删结点空间，返回实际删除的元素个数。*/
{
    LinkList p1,p2,p3;
    int j=0;
    if(NULL==L) 
        return ERROR;
    p1=p2=L;
    while(p2!=NULL){
      p2=p1->next;
      if(p2->data<x&&p2!=null){
        p3=p2;
        p2=p3->next;
        p1->next=p2;
        free(p3);
        j++;
      }
      else if(p2->data>=x){
          p1=p2;
          p2=p1->next;
       }            
    }    
    return j;
}
Thanks for your reward！