[关闭]
@Arbalest-Laevatain 2018-10-15T03:10:32.000000Z 字数 22443 阅读 990

Anyview 数据结构 第二章

数据结构

/******

1【题目】试写一算法，实现顺序栈的判空操作

  1. StackEmpty_Sq(SqStack S)。

顺序栈的类型定义为：

  1. typedef struct {
  2.   ElemType *elem; // 存储空间的基址
  3.   int top;        // 栈顶元素的下一个位置，简称栈顶位标
  4.   int size;       // 当前分配的存储容量
  5.   int increment;  // 扩容时，增加的存储容量
  6. } SqStack;        // 顺序栈

*******/

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

/******

2【题目】试写一算法，实现顺序栈的取栈顶元素操作

  1. GetTop_Sq(SqStack S, ElemType &e)。

顺序栈的类型定义为：

  1. typedef struct {
  2.   ElemType *elem;  // 存储空间的基址
  3.   int top;         // 栈顶元素的下一个位置，简称栈顶位标
  4.   int size;        // 当前分配的存储容量
  5.   int increment;   // 扩容时，增加的存储容量
  6. } SqStack;         // 顺序栈

*******/

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

/******

3【题目】试写一算法，实现顺序栈的出栈操作

  1. Pop_Sq(SqStack &S, ElemType &e)。

顺序栈的类型定义为：

  1. typedef struct {
  2.   ElemType *elem;  // 存储空间的基址
  3.   int top;         // 栈顶元素的下一个位置，简称栈顶位标
  4.   int size;        // 当前分配的存储容量
  5.   int increment;   // 扩容时，增加的存储容量
  6. } SqStack;         // 顺序栈

*******/

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

/******

4 【题目】若顺序栈的类型重新定义如下。试编写算法，

构建初始容量和扩容增量分别为size和inc的空顺序栈S。

  1. typedef struct {
  2.   ElemType *elem; // 存储空间的基址
  3.   ElemType *top;  // 栈顶元素的下一个位置
  4.   int size;       // 当前分配的存储容量
  5.   int increment;  // 扩容时，增加的存储容量
  6. } SqStack2;

*******/

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

/******

5【题目】若顺序栈的类型重新定义如下。试编写算法，

实现顺序栈的判空操作。

  1. typedef struct {
  2.   ElemType *elem; // 存储空间的基址
  3.   ElemType *top;  // 栈顶元素的下一个位置
  4.   int size;       // 当前分配的存储容量
  5.   int increment;  // 扩容时，增加的存储容量
  6. } SqStack2;

*******/

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

/******

6【题目】若顺序栈的类型重新定义如下。试编写算法，

实现顺序栈的入栈操作。

  1. typedef struct {
  2.   ElemType *elem; // 存储空间的基址
  3.   ElemType *top;  // 栈顶元素的下一个位置
  4.   int size;       // 当前分配的存储容量
  5.   int increment;  // 扩容时，增加的存储容量
  6. } SqStack2;

*******/

  1. Status Push_Sq2(SqStack2 &S, ElemType e)
  2. /* 若顺序栈S是满的，则扩容，若失败则返回ERROR。*/
  3. /* 将e压入S，返回OK。                          */
  4. {
  5.     if (S.top>=S.elem+S.size)
  6.      {
  8.         if (S.increment<=0)
  9.             return ERROR;
  10.         ElemType *p;
  11.         p = (ElemType *) realloc (S.elem,(S.size+S.increment)*sizeof(ElemType));
  12.         if (p==NULL)
  13.             return ERROR;
  14.         S.elem=p;
  15.         S.top=S.elem+S.size;
  16.         S.size+=S.increment;
  18.      }
  20.         *S.top=e;
  21.         S.top++;
  22.         return OK;
  23. }

/******

7 【题目】若顺序栈的类型重新定义如下。试编写算法，

实现顺序栈的出栈操作。

  1. typedef struct {
  2.   ElemType *elem; // 存储空间的基址
  3.   ElemType *top;  // 栈顶元素的下一个位置
  4.   int size;       // 当前分配的存储容量
  5.   int increment;  // 扩容时，增加的存储容量
  6. } SqStack2;

*******/

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

/******

8【题目】试写一算法，借助辅助栈，复制顺序栈S1得到S2。

顺序栈的类型定义为：

  1. typedef struct {
  2.   ElemType *elem; // 存储空间的基址
  3.   int top;        // 栈顶元素的下一个位置，简称栈顶位标
  4.   int size;       // 当前分配的存储容量
  5.   int increment;  // 扩容时，增加的存储容量
  6. } SqStack;        // 顺序栈

可调用顺序栈接口中下列函数：

  1. Status InitStack_Sq(SqStack &S, int size, int inc); // 初始化顺序栈S
  2. Status DestroyStack_Sq(SqStack &S); // 销毁顺序栈S
  3. Status StackEmpty_Sq(SqStack S);    // 栈S判空，若空则返回TRUE，否则FALSE
  4. Status Push_Sq(SqStack &S, ElemType e); // 将元素e压入栈S
  5. Status Pop_Sq(SqStack &S, ElemType &e); // 栈S的栈顶元素出栈到e

*******/

  1. Status CopyStack_Sq(SqStack S1, SqStack &S2) 
  2. /* 借助辅助栈，复制顺序栈S1得到S2。    */ 
  3. /* 若复制成功，则返回TRUE；否则FALSE。 */
  4. {
  5.     ElemType e;
  7.     SqStack S0;
  8.    InitStack_Sq(S0, S1.size, S1.increment);
  9.    InitStack_Sq(S2, S1.size, S1.increment);
  11.    S0.top=0;
  12.    S2.top=0;
  13.    if (StackEmpty_Sq(S1)==TRUE )
  14.     {            
  15.         return TRUE;
  16.      }   
  18.    int i,l;
  19.    l=S1.top;
  20.    for (i=0;i<l;i++)
  21.    {
  22.       Pop_Sq(S1, e);
  23.       Push_Sq(S0, e);
  24.    }
  25.    for (i=0;i<l;i++)
  26.    {
  27.       Pop_Sq(S0, e);
  28.       Push_Sq(S2,e);
  29.    }
  30.    DestroyStack_Sq(S0);
  31.    return OK;
  32. }

/******

9【题目】试写一算法，求循环队列的长度。

循环队列的类型定义为：

  1. typedef struct {
  2.   ElemType *base;  // 存储空间的基址
  3.   int front;       // 队头位标
  4.   int rear;        // 队尾位标，指示队尾元素的下一位置
  5.   int maxSize;     // 最大长度
  6. } SqQueue;

*******/

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

/******

10【题目】如果希望循环队列中的元素都能得到利用，

则可设置一个标志域tag，并以tag值为0或1来区分尾
指针和头指针值相同时的队列状态是"空"还是"满"。
试编写与此结构相应的入队列和出队列的算法。
本题的循环队列CTagQueue的类型定义如下：

  1. typedef struct {
  2.   ElemType elem[MAXQSIZE];
  3.   int tag;
  4.   int front;
  5.   int rear;
  6. } CTagQueue;

******/

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

/******

11【题目】假设将循环队列定义为：以域变量rear

和length分别指示循环队列中队尾元素的位置和内
含元素的个数。试给出此循环队列的队满条件，并
写出相应的入队列和出队列的算法（在出队列的算
法中要返回队头元素）。
本题的循环队列CLenQueue的类型定义如下：

  1. typedef struct {
  2.   ElemType elem[MAXQSIZE];
  3.   int length;
  4.   int rear;
  5. } CLenQueue;

******/

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

12【题目】已知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的算法。

本题的循环队列的类型定义如下：

  1. typedef struct {
  2.   ElemType *base; // 存储空间的基址
  3.   int front;      // 队头位标
  4.   int rear;       // 队尾位标，指示队尾元素的下一位置
  5.   int maxSize;    // 最大长度
  6. } SqQueue;
  7. **********/
  8. long Fib(int k, int n)
  9. /* 求k阶斐波那契序列的第n项fn
  10. 要求：必须使用循环队列
  11. */
  12. {
  13.     long sum = 0;
  14.     int i, j,m;
  15.     SqQueue a;
  16.     a.maxSize = k+1;    
  17.     //注意循环队列由于判空判满的问题所以有一个元素空间没有用
  18.     a.base = (ElemType*)malloc(a.maxSize * sizeof(ElemType));
  19.     a.front = 0;
  20.     a.rear = 0;
  23.     if (n < k - 1)
  24.     {
  25.         sum = 0;
  26.         return sum;
  27.     }
  28.     else if (n == k-1)
  29.     {
  30.         sum = 1;
  31.         return sum;
  32.     }
  34.     //初始化该队列对应的斐波那契数列
  35.     do
  36.     {
  37.         a.base[a.rear] = 0;
  39.         a.rear = (a.rear + 1) % a.maxSize;
  40.     } while ((a.rear + 1) % a.maxSize != a.front);
  41.     a.base[a.rear-1] = 1;
  42.     cout << a.base[a.rear-1] << endl;
  43.     cout << a.rear << endl;
  44.     cout << a.front << endl;
  45.     cout << endl;
  47.     m = a.front;
  48.     for (i = k-1; i < n; i++)
  49.     {
  50.         long v = 0;
  51.         j = a.front;
  52.         do
  53.         {
  54.             v += a.base[j];
  55.             cout << "v:" << v << "  " << "j:" << j << endl;
  56.             j = (j + 1) % a.maxSize;
  57.         } while ((j + 1) % a.maxSize != a.front);
  58.         cout << endl;
  59.         cout << "v:" << v << "  "<< "i:" << i << endl;
  60.         cout << "rear   " << a.rear << endl;
  61.         cout << endl;
  64.         a.base[a.rear] = v;
  65.         if ((a.rear + 1) % a.maxSize == a.front)
  66.         {
  67.             a.rear = a.front;
  68.         }
  69.         else
  70.             a.rear = (a.rear + 1) % a.maxSize;
  73.         a.front = (a.front + 1) % a.maxSize;
  76.     }
  78.     sum = 0;
  79.     j = a.front;
  80.     do
  81.     {
  82.         sum += a.base[j];
  83.         cout << a.base[j] << "  " << "j:" << j << endl;
  84.         j = (j + 1) % a.maxSize;
  85.     } while ((j + 1) % a.maxSize != a.front);
  87.     return sum;
  88. }

/******

12【题目】设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'才进行比较）。
顺序表类型定义如下：

  1. typedef struct {
  2.   ElemType *elem;
  3.   int       length;
  4.   int       size;
  5.   int       increment;
  6. } SqList;

******/

  1. char Compare(SqList A, SqList B)
  2. /* 比较顺序表A和B,      */
  3. /*   返回'<', 若A<B;    */
  4. /*       '=', 若A=B;    */
  5. /*       '>', 若A>B     */
  6. {
  7.    int i;
  8.     if (A.elem[0]!=B.elem[0])
  9.     {
  10.         if (A.elem[0] < B.elem[0])
  11.             return '<';
  12.         else if (A.elem[0] > B.elem[0] )
  13.             return '>';
  14.         else if (A.length == B.length)
  15.             return '=';
  16.     }
  18.     for (i=0;i<A.length;i++)
  19.     {
  20.         if (A.elem[i] == B.elem[i])
  21.             continue;
  22.         else 
  23.             break;
  24.     }
  26.      if (i == A.length)
  27.     {
  28.         if (i == B.length)
  29.             return '=';
  30.         else 
  31.             return '<';
  32.     }
  33.     else
  34.     {
  35.         if (i+1 == B.length)
  36.             return '>';
  37.         else if (A.length < B.length)
  38.             return '<';
  39.         else if (A.length > B.length)
  40.             return '>';
  41.         else if (A.elem[i+1] < B.elem[i+1])
  42.             return '<';
  43.         else 
  44.             return '>';
  45.     }
  46. }

/******

13 【题目】试写一算法，实现顺序表的就地逆置，

即利用原表的存储空间将线性表(a1,a2,…,an)
逆置为(an,an-1,…,a1)。
顺序表类型定义如下：

  1. typedef struct {
  2.   ElemType *elem;
  3.   int       length;
  4.   int       size;
  5.   int       increment;
  6. } SqList;
  7. **********/
  8. void Inverse(SqList &L)
  9. {
  10.     for (i=0;i<L.length/2;i++)
  11.     {
  12.         ElemType t;
  13.         t = L.elem[i];
  14.         L.elem[i] = L.elem[L.length - i - 1];
  15.         L.elem[L.length - i - 1] = t;
  16.     }
  17. }

/******

14【题目】试对一元稀疏多项式Pn(x)采用存储量同多项式

项数m成正比的顺序存储结构，编写求Pn(x0)的算法（x0
为给定值）。

一元稀疏多项式的顺序存储结构:

  1. typedef struct {
  2.   int  coef;  // 系数
  3.   int   exp;  // 指数
  4. } Term;
  6. typedef struct {
  7.   Term  *elem;   // 存储空间基址
  8.   int    length; // 长度（项数）
  9. } Poly;
  10. **********/
  11. float Evaluate(Poly P, float x)
  12. /* P.elem[i].coef 存放ai，                        */
  13. /* P.elem[i].exp存放ei (i=1,2,...,m)              */
  14. /* 本算法计算并返回多项式的值。不判别溢出。       */
  15. /* 入口时要求0≤e1<e2<...<em，算法内不对此再作验证 */
  16. {
  17.     int i, j;
  18.     float sum = 0;
  19.     float t;
  20.     for ( i = 0; i < P.length; i++)
  21.     {
  22.         t = x;
  23.         if (P.elem[i].exp == 0)
  24.         {
  25.             t = 1.0;
  26.         }
  27.         else
  28.         {
  29.             for ( j = 1; j < P.elem[i].exp; j++)
  30.                 t *= x;
  31.         }
  32.         sum += (float)P.elem[i].coef*t;
  33.     }
  34.     return sum;
  35. }

测试代码

  1. typedef struct {
  2.     int  coef;  // 系数
  3.     int   exp;  // 指数
  4. } Term;
  6. typedef struct {
  7.     Term  *elem;   // 存储空间基址
  8.     int    length; // 长度（项数）
  9. } Poly;
  11. float Evaluate(Poly P, float x)
  12. /* P.elem[i].coef 存放ai，                        */
  13. /* P.elem[i].exp存放ei (i=1,2,...,m)              */
  14. /* 本算法计算并返回多项式的值。不判别溢出。       */
  15. /* 入口时要求0≤e1<e2<...<em，算法内不对此再作验证 */
  16. {
  17.     int i, j;
  18.     float sum = 0;
  19.     float t;
  20.     for ( i = 0; i < P.length; i++)
  21.     {
  22.         t = x;
  23.         if (P.elem[i].exp == 0)
  24.         {
  25.             t = 1.0;
  26.         }
  27.         else
  28.         {
  29.             for ( j = 1; j < P.elem[i].exp; j++)
  30.                 t *= x;
  31.         }
  32.         sum += (float)P.elem[i].coef*t;
  33.     }
  34.     return sum;
  35. }
  37. int main()
  38. {
  39.     Poly p;
  40.     //Poly *a = (Poly*)malloc(sizeof(Poly));
  41.     p.length = 3;
  42.     p.elem = (Term*)malloc(p.length*sizeof(Term));
  43.     for (int i = 0; i < p.length; i++)
  44.     {
  45.         p.elem[i].coef = i + 1;
  46.         p.elem[i].exp = i;
  47.     }
  49.     double x = 0.01;
  50.     float re = Evaluate(p,x);
  52.     printf("%lf\n",re);
  53.     printf("%lf\n", 1.0 + 2.0*x + 3.0*x*x);
  55.     return 0;
  56. }

/******

15 【题目】假设有两个集合A和B分别用两个线性表LA和LB

表示(即：线性表中的数据元素即为集合中的成员），
试写一算法，求并集 ＝
顺序表类型定义如下

  1. typedef struct {
  2.   ElemType *elem;     // 存储空间的基址
  3.   int length;    // 当前长度
  4.   int size;      // 存储容量 
  5.   int increment; // 空间不够增加空间大小
  6. } SqList;  // 顺序表
  8. //可调用顺序表的以下接口函数：   
  9. Status InitList_Sq(SqList &L, int size, int inc); // 初始化顺序表L
  10. int ListLength_Sq(SqList L);  // 返回顺序表L中元素个数
  11. Status GetElem_Sq(SqList L, int i, ElemType &e); 
  12. // 用e返回顺序表L中第i个元素的值
  13. int Search_Sq(SqList L, ElemType e); 
  14. // 在顺序表L顺序查找元素e，成功时返回该元素在表中第一次出现的位置，否则返回-1
  15. Status Append_Sq(SqList &L, ElemType e);  // 在顺序表L表尾添加元素e
  16. **********/
  17. void Union(SqList &La, SqList Lb)
  18. {
  19.     if (La.elem == NULL)
  20.         if (Lb.elem == NULL)
  21.             La.elem == NULL;
  22.         else
  23.             La.elem = Lb.elem;
  24.     else
  25.     {
  26.        int la = ListLength_Sq(La);
  27.         int lb = ListLength_Sq(Lb);
  29.         int i,j;
  30.         for (i = 1;i <= lb;i++)
  31.         {
  32.             GetElem_Sq(Lb,i,j);
  33.             if (Search_Sq(La,j) != -1)
  34.                 continue;
  35.             else
  36.             {
  37.                 //if (La.length+1 == La.size)
  38.                 Append_Sq(La,j);
  39.             }    
  40.         }
  41.     }             
  43. }

求出并集，要放到第一个表里！！

/******

16【题目】试写一算法，实现链栈的判空操作。

链栈的类型定义为：

  1. typedef struct LSNode {
  2.   ElemType data;       // 数据域
  3.   struct LSNode *next; // 指针域
  4. } LSNode, *LStack;    // 结点和链栈类型
  5. ***********/
  6. Status StackEmpty_L(LStack S)
  7. /* 对链栈S判空。若S是空栈，则返回TRUE；否则返回FALSE */
  8. {
  9.     if (S == NULL)
  10.         return TRUE;
  11.     else
  12.         return  FALSE;
  13. }

/******

17 【题目】试写一算法，实现链栈的取栈顶元素操作。

链栈的类型定义为：

  1. typedef struct LSNode {
  2.   ElemType data;       // 数据域
  3.   struct LSNode *next; // 指针域
  4. } LSNode, *LStack;    // 结点和链栈类型
  5. ***********/
  6. Status GetTop_L(LStack S, ElemType &e) 
  7. /* 取链栈S的栈顶元素到e，并返回OK; */
  8. /* 若S是空栈，则失败，返回ERROR。  */
  9. {
  10.     if (S == NULL)
  11.         return ERROR;
  12.     else
  13.     {
  14.         e = S->deta;
  15.         return  OK;
  16.     }
  17. }

/******

18 【题目】试写一算法，实现链队列的判空操作。

链队列的类型定义为：

  1. typedef struct LQNode {     
  2.   ElemType  data;  
  3.   struct LQNode  *next;  
  4. } LQNode, *QueuePtr; // 结点和结点指针类型
  6. typedef struct {     
  7.   QueuePtr  front;  // 队头指针
  8.   QueuePtr  rear;   // 队尾指针
  9. } LQueue;  // 链队列类型
  1. Status QueueEmpty_LQ(LQueue Q)
  2. /* 判定链队列Q是否为空队列。           */
  3. /* 若Q是空队列，则返回TRUE，否则FALSE。*/
  4. {
  5.    if (Q.front->next == Q.rear)
  6.     return TRUE;
  7.     else
  8.     return FALSE;
  9. }

/******

19 【题目】试写一算法，实现链队列的求队列长度操作。

链队列的类型定义为：

  1. typedef struct LQNode {     
  2.   ElemType  data;  
  3.   struct LQNode  *next;  
  4. } LQNode, *QueuePtr; // 结点和结点指针类型
  5. typedef struct {     
  6.   QueuePtr  front;  // 队头指针
  7.   QueuePtr  rear;   // 队尾指针
  8. } LQueue;  // 链队列类型
  9. ***********/
  10. int QueueLength_LQ(LQueue Q)
  11. /* 求链队列Q的长度并返回其值 */
  12. {
  13.     int l = 0;
  14.     QueuePtr p = Q.front;
  15.     while(p->next != Q.rear)
  16.     {
  17.         l++;
  18.         p = p->next;
  19.     }
  20.     return l;
  21. }

未知错误

/******

（做到这，存在问题）20【题目】（PE68） 假设以带头结点的循环链表表示队列，并且

只设一个指针指向队尾元素结点(注意不设头指针)，
试编写相应的队列初始化、入队列和出队列的算法。
带头结点循环链队列CLQueue的类型定义为：

  1. typedef struct LQNode {
  2.   ElemType data;
  3.   struct LQNode *next;
  4. } LQNode, *CLQueue;
  5. **********/
  6. Status InitCLQueue(CLQueue &rear) // 初始化空队列
  7. { 
  9.     if (NULL == (rear = (CLQueue) malloc (sizeof(CLQueue))))
  10.         return OVERFLOW;
  11.     else
  12.     {
  13.         rear->next = NULL;
  14.         //L->next = rear;
  15.         return OK;
  16.     }
  17. }
  19. Status EnCLQueue(CLQueue &rear, ElemType x) // 入队
  20. { 
  21.     CLQueue l,p;
  22.    if (NULL == (l = (CLQueue) malloc (sizeof(CLQueue))))
  23.         return OVERFLOW;
  24.     l->data = e;
  25.     p = rear;
  26.     while (p->next != rear)
  27.     {
  28.         p = p->next;
  29.     }
  30.     l->next = p->next;
  31.     p->next = l;
  32.     return OK;
  33. }
  35. Status DeCLQueue(CLQueue &rear, ElemType &x) // 出队
  36. { 
  37. CLQueue p = rear;
  39.     if (rear->next == NULL)
  40.         return ERROR;
  41.     else
  42.     {
  43.         while (p->next != rear)
  44.             p = p->next;
  45.         x = rear->data;
  46.         rear = rear->next;
  47.         p->next = rear;
  48.         return OK;
  49.     }
  50. }

更正后代码

  1. Status EnCLQueue(CLQueue &rear, ElemType x) // 入队
  2. { 
  3.     CLQueue p;
  4.     //q = rear->next;
  5.    if (NULL == (p = (LQNode*) malloc (sizeof(LQNode))))
  6.         return OVERFLOW;
  7.     p->data = x;
  9.     //printf("%c\n",x);
  10.     //printf("\n");
  12.     p->next = rear->next;
  14.     rear->next = p;
  15.     rear = p;
  16.     //rear->next->data;
  17.     return OK;
  18. }

注意：
在使用malloc函数来分派内存的时候，前面括号里是该类型的指针类型，后面括号才是该类型
（隔了一段时间就容易忘……2333……）

错误信息

  1. <第2次运行>  2018/10/12 8:29:49
  2. A$: InitCLQueue(rear) : OK     Queue = (( ))
  3. E$: InitCLQueue(rear) : OK     Queue = (( ))
  4. ===== Right =====
  5.     Queue=( SHQ)
  6. A$:  EnCLQueue(rear, 'M') = OK    --> ( SHQM)
  7. A$:  DeCLQueue(rear,  e ) = OK    --> ( HQ)  e = 'S'
  8. E$:  EnCLQueue(rear, 'M') = OK    --> ( SH繫)
  9. E$:  DeCLQueue(rear,  e ) = OK    --> ( HQ)  e = 'S'
  10. ----- Error -----
  11.     Queue=( CXMPVPWM)
  12. A$:  EnCLQueue(rear, 'B') = OK    --> ( CXMPVPWMB)
  13. A$:  DeCLQueue(rear,  e ) = OK    --> ( XMPVPWM)  e = 'C'
  14. E$:  EnCLQueue(rear, 'B') = OK    --> ( CXMPVPW旴)
  15. E$:  DeCLQueue(rear,  e ) = OK    --> ( XMPVPWM)  e = 'C'
  16. ----- Error -----
  17.     Queue=( BOWQFLJUF)
  18. A$:  EnCLQueue(rear, 'B') = OK    --> ( BOWQFLJUFB)
  19. A$:  DeCLQueue(rear,  e ) = OK    --> ( OWQFLJUF)  e = 'B'
  20. E$:  EnCLQueue(rear, 'B') = OK    --> ( BOWQFLJUJB)
  21. E$:  DeCLQueue(rear,  e ) = OK    --> ( OWQFLJUF)  e = 'B'
  22. ----- Error -----
  23.     Queue=( KCUVYBAC)
  24. A$:  EnCLQueue(rear, 'M') = OK    --> ( KCUVYBACM)
  25. A$:  DeCLQueue(rear,  e ) = OK    --> ( CUVYBAC)  e = 'K'
  26. E$:  EnCLQueue(rear, 'M') = OK    --> ( KCUVYBA鸐)
  27. E$:  DeCLQueue(rear,  e ) = OK    --> ( CUVYBAC)  e = 'K'
  28. ----- Error -----
  29.     Queue=( )
  30. A$:  EnCLQueue(rear, 'Z') = OK    --> ( Z)
  31. A$:  DeCLQueue(rear,  e ) = ERROR --> ( )
  32. E$:  EnCLQueue(rear, 'Z') = OK    --> ( Z)
  33. E$:  DeCLQueue(rear,  e ) = ERROR --> ( )
  34. ===== Right =====
  35. Error：4     Right：2

在自己电脑的测试代码及数据

  1. #include <iostream>
  2. #include <cstdlib>
  4. using namespace std;
  6. #define TRUE 1
  7. #define FALSE 0
  9. #define OK 1
  10. #define ERROR 0
  11. #define OVERFLOW -1
  13. typedef int Status;
  15. #define ElemType char 
  17. typedef struct LQNode {
  18.     ElemType data;
  19.     struct LQNode *next;
  20. } LQNode, *CLQueue;
  23. Status InitCLQueue(CLQueue &rear) // 初始化空队列
  24. {
  25.     if (NULL == (rear = (CLQueue)malloc(sizeof(CLQueue))))
  26.         return OVERFLOW;
  27.     else
  28.     {
  29.         rear->next = rear;
  30.         //L->next = rear;
  31.         return OK;
  32.     }
  33. }
  36. Status EnCLQueue(CLQueue &rear, ElemType x) // 入队
  37. {
  38.     CLQueue p;
  39.     if (NULL == (p = (CLQueue)malloc(sizeof(CLQueue))))
  40.         return OVERFLOW;
  41.     p->data = x;
  42.     p->next = rear->next;
  43.     rear->next = p;
  44.     rear = p;
  45.     return OK;
  46. }
  49. Status DeCLQueue(CLQueue &rear, ElemType &x) // 出队
  50. {
  51.     CLQueue p = rear->next;
  52.     CLQueue q = p->next;
  54.     if (rear->next == rear)
  55.         return ERROR;
  56.     else
  57.     {
  58.         x = q->data;
  59.         p->next = q->next;
  60.         return OK;
  61.     }
  62. }
  64. //定义一个打印函数
  65. void printCLquene(CLQueue rear)
  66. {
  67.     CLQueue p = rear->next;
  68.     p = p->next;
  69.     while (p != rear->next)
  70.     {
  71.         printf("%c",p->data);
  72.         p = p->next;
  73.     }
  74.     cout << endl;
  75. }
  77. //输入函数
  78. void input(CLQueue &rear,int n)
  79. {
  80.     char c;
  81.     CLQueue q,p;
  84.     p = rear->next;
  85.     for (int i = 0; i < n; i++)
  86.     {
  87.         cout << "输入data" << endl;
  88.         cin >> c;
  90.         q = (CLQueue)malloc(sizeof(CLQueue));
  91.         q->data = c;
  94.         rear->next = q;
  95.         rear = q;
  96.         rear->next = p;
  97.     }
  98. }
  100. int main()
  101. {
  102.     //定义一个循环列表
  103.     CLQueue rear, p,q;
  104.     ////初始化
  105.     InitCLQueue(rear);
  107.     input(rear, 3);
  109.     printCLquene(rear);
  111.     //入队操作
  112.     ElemType e;
  113.     e = 'M';
  114.     EnCLQueue(rear,e);
  116.     printCLquene(rear);
  118.     return 0;
  119. }

/******

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

单链表的类型定义为：

  1. typedef struct LNode {     
  2.   ElemType  data;  
  3.   struct LNode  *next;  
  4. } LNode, *LinkList; // 结点和结点指针类型
  5. ***********/
  6. Status ListEmpty_L(LinkList L)
  7. /* 判定带头结点单链表L是否为空链表。   */
  8. /* 若L是空链表，则返回TRUE，否则FALSE。*/
  9. {
  10.     if (L->next == NULL)
  11.         return TRUE;
  12.     else
  13.         return FALSE;
  14. }

/******

22 【题目】试写一算法，实现带头结点单链表的销毁操作。

单链表的类型定义为：

  1. typedef struct LNode {     
  2.   ElemType  data;  
  3.   struct LNode  *next;  
  4. } LNode, *LinkList; // 结点和结点指针类型
  5. ***********/
  6. Status DestroyList_L(LinkList &L)
  7. /* 销毁带头结点单链表L，并返回OK。*/
  8. {
  9.     LinkList p,q;
  10.     LinkList a,b,c;
  11.     p = L->next;
  12.     if (p == NULL)
  13.     {
  14.         free(L);
  15.         return OK;  
  16.     }
  17.     while (p != NULL)
  18.     {
  19.         q = p;
  20.         p = p->next;
  21.         free(q);
  22.     }
  24.     free(L);
  25.     return OK;
  26. }

/******

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

单链表的类型定义为：

  1. typedef struct LNode {     
  2.   ElemType  data;  
  3.   struct LNode  *next;  
  4. } LNode, *LinkList; // 结点和结点指针类型
  5. ***********/
  6. Status ClearList_L(LinkList &L)
  7. /* 将带头结点单链表L置为空表，并返回OK。*/
  8. /* 若L不是带头结点单链表，则返回ERROR。 */
  9. {
  10.      if (NULL == L)
  11.         return  ERROR;
  12.    LinkList p,q;
  13.     LinkList a,b,c;
  14.     p = L->next;
  15.     if (p == NULL)
  16.         return OK;
  17.     while (p != NULL)
  18.     {
  19.         q = p;
  20.         p = p->next;
  21.         free(q);
  22.     }
  24.     L->next = NULL;
  25.     return OK;
  26. }

/******

24 【题目】试写一算法，实现带头结点单链表的求表长度操作。

单链表的类型定义为：

  1. typedef struct LNode {     
  2.   ElemType  data;  
  3.   struct LNode  *next;  
  4. } LNode, *LinkList; // 结点和结点指针类型
  5. ***********/
  6. int ListLength_L(LinkList L)
  7. /* 求带头结点单链表L的长度，并返回长度值。*/
  8. /* 若L不是带头结点单链表，则返回-1。      */
  9. {
  10.     if (NULL == L)
  11.         return -1;
  12.    LinkList p;
  13.     p = L->next;
  15.     int num = 0;
  16.     while (p != NULL)
  17.     {
  18.         p = p->next;
  19.         num++;
  20.     }
  21.     return num;
  22. }

/******

(存在问题) 25（PE82）【题目】试写一算法，在带头结点单链表L插入第i元素e。

带头结点单链表的类型定义为：

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

错误信息

  1. <第3次运行>  2018/10/12 9:23:42
  2. A$: L0 = ( )
  3. A$: Insert_L(L0, 0, '*') = ERROR  L0 = ( )
  4. A$: Insert_L(L0, 1, '*') = OK     L0 = ( *)
  5. A$: Insert_L(L0, 2, '*') = ERROR  L0 = ( )
  6. E$: L0 = ( )
  7. E$: Insert_L(L0, 0, '*') = ERROR  L0 = ( )
  8. E$: Insert_L(L0, 1, '*') = OK     L0 = ( *)
  9. E$: Insert_L(L0, 2, '*') = ERROR  L0 = ( )
  10. ===== Right =====
  11. A$: L1 = ( a)
  12. A$: Insert_L(L1, 0, '*') = ERROR  L1 = ( a)
  13. A$: Insert_L(L1, 1, '*') = OK     L1 = ( *a)
  14. A$: Insert_L(L1, 2, '*') = OK     L1 = ( a*)
  15. A$: Insert_L(L1, 6, '*') = ERROR  L1 = ( a)
  16. E$: L1 = ( a)
  17. E$: Insert_L(L1, 0, '*') = ERROR  L1 = ( a)
  18. E$: Insert_L(L1, 1, '*') = OK     L1 = ( *
  19. E$: Insert_L(L1, 2, '*') = OK     L1 = ( 
  20. E$: Insert_L(L1, 6, '*') = ERROR  L1 = ( a)
  21. ----- Error -----
  23. A$: L2 = ( ab)
  24. A$: Insert_L(L2, 0, '*') = ERROR  L2 = ( ab)
  25. A$: Insert_L(L2, 1, '*') = OK     L2 = ( *ab)
  26. A$: Insert_L(L2, 2, '*') = OK     L2 = ( a*b)
  27. A$: Insert_L(L2, 3, '*') = OK     L2 = ( ab*)
  28. A$: Insert_L(L2, 4, '*') = ERROR  L2 = ( ab)
  29. E$: L2 = ( ab)
  30. E$: Insert_L(L2, 0, '*') = ERROR  L2 = ( ab)
  31. E$: Insert_L(L2, 1, '*') = OK     L2 = ( *a?
  32. E$: Insert_L(L2, 2, '*') = OK     L2 = ( a*?
  33. E$: Insert_L(L2, 3, '*') = OK     L2 = ( a
  34. E$: Insert_L(L2, 4, '*') = ERROR  L2 = ( ab)
  35. ----- Error -----
  37. A$: L3 = ( abcdefg)
  38. A$: Insert_L(L3, 0, '*') = ERROR  L3 = ( abcdefg)
  39. A$: Insert_L(L3, 1, '*') = OK     L3 = ( *abcdefg)
  40. A$: Insert_L(L3, 2, '*') = OK     L3 = ( a*bcdefg)
  41. A$: Insert_L(L3, 6, '*') = OK     L3 = ( abcde*fg)
  42. A$: Insert_L(L3, 7, '*') = OK     L3 = ( abcdef*g)
  43. A$: Insert_L(L3, 8, '*') = OK     L3 = ( abcdefg*)
  44. A$: Insert_L(L3, 9, '*') = ERROR  L3 = ( abcdefg)
  45. E$: L3 = ( abcdefg)
  46. E$: Insert_L(L3, 0, '*') = ERROR  L3 = ( abcdefg)
  47. E$: Insert_L(L3, 1, '*') = OK     L3 = ( *abcdef#)
  48. E$: Insert_L(L3, 2, '*') = OK     L3 = ( a*bcdef)
  49. E$: Insert_L(L3, 6, '*') = OK     L3 = ( abcde*f?
  50. E$: Insert_L(L3, 7, '*') = OK     L3 = ( abcdef*?
  51. E$: Insert_L(L3, 8, '*') = OK     L3 = ( abcdef
  52. E$: Insert_L(L3, 9, '*') = ERROR  L3 = ( abcdefg)
  53. ----- Error -----
  55. Error：3     Right：1

测试代码

  1. #include <iostream>
  2. #include <cstdlib>
  4. using namespace std;
  6. #define TRUE 1
  7. #define FALSE 0
  9. #define OK 1
  10. #define ERROR 0
  11. #define OVERFLOW -1
  13. typedef int Status;
  15. #define ElemType char 
  17. typedef struct LNode {
  18.     ElemType      data;
  19.     struct LNode *next;
  20. } LNode, *LinkList;
  23. Status Insert_L(LinkList L, int i, ElemType e)
  24. /* 在带头结点单链表L插入第i元素e，并返回OK。*/
  25. /* 若参数不合理，则返回ERROR。              */
  26. {
  27.     LinkList p = L;
  28.     if (NULL == p || i <1)
  29.         return ERROR;
  31.     int num = 1;
  32.     while (p->next != NULL && num<i)
  33.     {
  34.         p = p->next;
  35.         num++;
  36.     }
  37.     if (num <i)
  38.         return ERROR;
  39.     LinkList m;
  40.     m = (LinkList)malloc(sizeof(LinkList));
  42.     m->next = p->next;
  43.     p->next = m;
  44.     m->data = e;
  46.     return OK;
  47. }
  49. //初始化带头结点的单链表函数
  50. void InitLinkList(LinkList &L)
  51. {
  52.     LinkList q;
  54.     char c[] = {"abcdefg"};
  56.     q = L;
  57.     //q->next = L->next;
  59.     for (int i = 0; i < 7; i++)
  60.     {
  61.         LinkList p = (LinkList)malloc(sizeof(LinkList));
  62.         p->data = c[i];
  63.         p->next = q->next;
  64.         q->next = p;
  65.         q = q->next;
  66.     }
  67.     //L = q;
  68. }
  71. //定义打印函数
  72. void printLinkLIst(LinkList &L)
  73. {
  74.     LinkList p;
  75.     p = L->next;
  77.     while (p != NULL)
  78.     {
  79.         cout << p->data;
  80.         p = p->next;
  81.     }
  82.     cout << endl;
  83. }
  85. int main()
  86. {
  87.     //定义一个带头结点的单链表
  88.     //L3 = ( abcdefg)
  89.     LinkList L = (LinkList)malloc(sizeof(LinkList));
  90.     L->next = NULL;
  92.     InitLinkList(L);
  94.     printLinkLIst(L);
  96.     Insert_L(L,2,'*');
  98.     printLinkLIst(L);
  100.     return 0;
  101. }

/******

(存在问题) 26（84）【题目】试写一算法，在带头结点单链表删除第i元素到e。

带头结点单链表的类型定义为：

  1. typedef struct LNode {
  2.   ElemType      data;
  3.   struct LNode *next;
  4. } LNode, *LinkList;
  5. **********/
  6. Status Delete_L(LinkList L, int i, ElemType &e)
  7. /* 在带头结点单链表L删除第i元素到e，并返回OK。*/
  8. /* 若参数不合理，则返回ERROR。                */
  9. {
  10.     LinkList p = L;
  11.     LinkList q ;
  12.     if (NULL == p || i <1)
  13.         return ERROR;
  15.     int num = 0;
  16.     while (p->next != NULL && num<i)
  17.     {
  18.         q = p;
  19.         p = p->next;
  20.         num++;
  21.     }
  23.     if (i > num)
  24.         return ERROR;
  26.         LinkList m = p;
  27.         e = m->data;
  28.         q->next = m->next;
  30.      //free(m);
  31.      return OK;
  32. }

错误信息

  1. <第2次运行>  2018/10/12 10:10:09
  2. A$: L0 = ( )
  3. A$: Delete_L(L0, 0, e) = ERROR  L0 = ( )
  4. A$: Delete_L(L0, 1, e) = ERROR  L0 = ( )
  5. A$: Delete_L(L0, 2, e) = ERROR  L0 = ( )
  6. E$: L0 = ( )
  7. E$: Delete_L(L0, 0, e) = ERROR  L0 = ( )
  8. E$: Delete_L(L0, 1, e) = ERROR  L0 = ( )
  9. E$: Delete_L(L0, 2, e) = ERROR  L0 = ( )
  10. ===== Right =====
  11. A$: L1 = ( a)
  12. A$: Delete_L(L1, 0, e) = ERROR  L1 = ( a)
  13. A$: Delete_L(L1, 1, e) = OK     L1 = ( )  e = 'a'
  14. A$: Delete_L(L1, 2, e) = ERROR  L1 = ( a)
  15. A$: Delete_L(L1, 3, e) = ERROR  L1 = ( a)
  16. E$: L1 = ( a)
  17. E$: Delete_L(L1, 0, e) = ERROR  L1 = ( a)
  18. E$: Delete_L(L1, 1, e) = ERROR  L1 = ( a)
  19. E$: Delete_L(L1, 2, e) = ERROR  L1 = ( a)
  20. E$: Delete_L(L1, 3, e) = ERROR  L1 = ( a)
  21. ----- Error -----
  22. A$: L2 = ( ab)
  23. A$: Delete_L(L2, 0, e) = ERROR  L2 = ( ab)
  24. A$: Delete_L(L2, 1, e) = OK     L2 = ( b)  e = 'a'
  25. A$: Delete_L(L2, 2, e) = OK     L2 = ( a)  e = 'b'
  26. A$: Delete_L(L2, 3, e) = ERROR  L2 = ( ab)
  27. A$: Delete_L(L2, 8, e) = ERROR  L2 = ( ab)
  28. E$: L2 = ( ab)
  29. E$: Delete_L(L2, 0, e) = ERROR  L2 = ( ab)
  30. E$: Delete_L(L2, 1, e) = ERROR  L2 = ( ab)
  31. E$: Delete_L(L2, 2, e) = ERROR  L2 = ( ab)
  32. E$: Delete_L(L2, 3, e) = ERROR  L2 = ( ab)
  33. E$: Delete_L(L2, 8, e) = ERROR  L2 = ( ab)
  34. ----- Error -----
  35. A$: L3 = ( abcdefg)
  36. A$: Delete_L(L3, 0, e) = ERROR  L3 = ( abcdefg)
  37. A$: Delete_L(L3, 1, e) = OK     L3 = ( bcdefg)  e = 'a'
  38. A$: Delete_L(L3, 2, e) = OK     L3 = ( acdefg)  e = 'b'
  39. A$: Delete_L(L3, 5, e) = OK     L3 = ( abcdfg)  e = 'e'
  40. A$: Delete_L(L3, 7, e) = OK     L3 = ( abcdef)  e = 'g'
  41. A$: Delete_L(L3, 8, e) = ERROR  L3 = ( abcdefg)
  42. A$: Delete_L(L3, 9, e) = ERROR  L3 = ( abcdefg)
  43. E$: L3 = ( abcdefg)
  44. E$: Delete_L(L3, 0, e) = ERROR  L3 = ( abcdefg)
  45. E$: Delete_L(L3, 1, e) = ERROR  L3 = ( abcdefg)
  46. E$: Delete_L(L3, 2, e) = ERROR  L3 = ( abcdefg)
  47. E$: Delete_L(L3, 5, e) = ERROR  L3 = ( abcdefg)
  48. E$: Delete_L(L3, 7, e) = ERROR  L3 = ( abcdefg)
  49. E$: Delete_L(L3, 8, e) = ERROR  L3 = ( abcdefg)
  50. E$: Delete_L(L3, 9, e) = ERROR  L3 = ( abcdefg)
  51. ----- Error -----
  52. Error：3     Right：1

测试代码

/******

27 【题目】试写一算法，在带头结点单链表的第i元素起的

所有元素从链表移除，并构成一个带头结点的新链表。
带头结点单链表的类型定义为：

  1. typedef struct LNode {
  2.   ElemType      data;
  3.   struct LNode *next;
  4. } LNode, *LinkList;
  5. **********/
  6. Status Split_L(LinkList L, LinkList &Li, int i)
  7. /* 在带头结点单链表L的第i元素起的所有元素 */
  8. /* 移除，并构成带头结点链表Li，返回OK。   */
  9. /* 若参数不合理，则Li为NULL，返回ERROR。  */
  10. {
  11.      LinkList p = L;
  12.   LinkList q;
  13.   q = (LinkList) malloc (sizeof(LNode));
  14.   Li = (LinkList) malloc (sizeof(LNode));
  15.     if (NULL == p || i <1)
  16.     {
  17.         Li = NULL;
  18.         return ERROR;
  19.     }
  21.     int num = 0;
  22.     while (p->next != NULL && num<i)
  23.     {
  24.         q = p;
  25.         p = p->next;
  26.         num++;
  27.     }
  28.     if (i > num)
  29.     {
  30.         Li = NULL;
  31.         return ERROR;
  32.     }
  34.      LinkList p1 = p;
  35.      LinkList p2 = Li;
  37.      while (p1 != NULL)
  38.      {
  39.         q->next = p1->next;
  41.         p1->next = p2->next;
  42.         p2->next = p1;
  44.         p1 = q->next;
  45.         p2 = p2->next;
  46.      }
  48.      return OK;
  49. }

注意！！别忘了出错的时候把Li置为空

测试代码

  1. #include <iostream>
  3. using namespace std;
  5. #define TRUE 1
  6. #define FALSE 0
  8. #define OK 1
  9. #define ERROR 0
  10. #define OVERFLOW -1
  12. typedef int Status;
  14. #define ElemType char 
  16. typedef struct LNode {
  17.     ElemType      data;
  18.     struct LNode *next;
  19. } LNode, *LinkList;
  22. Status Split_L(LinkList L, LinkList &Li, int i)
  23. /* 在带头结点单链表L的第i元素起的所有元素 */
  24. /* 移除，并构成带头结点链表Li，返回OK。   */
  25. /* 若参数不合理，则Li为NULL，返回ERROR。  */
  26. {
  27.     LinkList p = L->next;
  28.     LinkList q = L;
  29.     //q = (LinkList)malloc(sizeof(LinkList));
  30.     if (NULL == p || i <1)
  31.         return ERROR;
  33.     int num = 0;
  34.     while (p != NULL && num<i)
  35.     {
  36.         if (num != 0)
  37.         {
  38.             p = p->next;
  39.             q = q->next;
  40.         }
  42.         num++;
  43.     }
  44.     if (i > num)
  45.         return ERROR;
  47.     LinkList p1 = p;
  48.     LinkList p2 = Li;
  50.     while (p1 != NULL)
  51.     {
  52.         q->next = p1->next;
  54.         p1->next = p2->next;
  55.         p2->next = p1;
  57.         p1 = q->next;
  58.         p2 = p2->next;
  59.     }
  61.     return OK;
  62. }
  65. //初始化带头结点的单链表函数
  66. void InitLinkList(LinkList &L)
  67. {
  68.     LinkList q;
  70.     char c[] = { "abcdefg" };
  72.     q = L;
  73.     //q->next = L->next;
  75.     for (int i = 0; i < 7; i++)
  76.     {
  77.         LinkList p = (LinkList)malloc(sizeof(LinkList));
  78.         p->data = c[i];
  79.         p->next = q->next;
  80.         q->next = p;
  81.         q = q->next;
  82.     }
  83.     //L = q;
  84. }
  87. //定义打印函数
  88. void printLinkLIst(LinkList &L)
  89. {
  90.     LinkList p;
  91.     p = L->next;
  93.     while (p != NULL)
  94.     {
  95.         cout << p->data;
  96.         p = p->next;
  97.     }
  98.     cout <<endl;
  99. }
  102. int main()
  103. {
  104.     //L3 = (abcdefg)
  105.     LinkList L = (LinkList)malloc(sizeof(LinkList));
  106.     L->next = NULL;
  108.     LinkList Li = (LinkList)malloc(sizeof(LinkList));
  109.     Li->next = NULL;
  111.     InitLinkList(L);
  113.     printLinkLIst(L);
  115.     int re = Split_L(L, Li, 2);
  117.     printLinkLIst(L);
  118.     printLinkLIst(Li);
  120.     cout << re << endl;
  122.     return 0;
  123. }

/******

28【题目】试写一算法，在带头结点单链表删除第i元素

起的所有元素。
带头结点单链表的类型定义为：

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

/******

29【题目】试写一算法，删除带头结点单链表中所有值

为x的元素，并释放被删结点空间。
单链表类型定义如下：

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

30【题目】试写一算法，删除带头结点单链表中所有值

小于x的元素，并释放被删结点空间。
单链表类型定义如下：

  1. typedef struct LNode {
  2.   ElemType      data;
  3.   struct LNode *next;
  4. } LNode, *LinkList;
  5. ******/
  6. Status DeleteSome_L(LinkList L, ElemType x)
  7. /* 删除带头结点单链表L中所有值小于x的元素，    */
  8. /* 并释放被删结点空间，返回实际删除的元素个数。*/
  9. {
  10.      LinkList p = L;
  11.     if (NULL == p->next)
  12.         return ERROR;
  14.     int num = 0,flag;
  15.     LinkList m;
  16.     while (p->next != NULL)
  17.     {
  18.         flag = 0; 
  19.         if (p->next->data < x)
  20.         {
  21.             m = p->next;
  22.             p->next = m->next;
  23.             free(m);
  24.             num++;
  25.             flag = 1;
  26.         }
  27.         if (!flag)
  28.             p = p->next;
  29.     }
  31.     return num;
  32. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注