程序员经验分享-hwhale

广工 AnyviewC 数据结构习题 第二章

2023-05-16

广工 AnyviewC 数据结构习题 第二章

  • 广工 AnyviewC 数据结构习题 第二章
  • Anyview 数据结构 第二章
    • 1【题目】试写一算法，实现顺序栈的判空操作
    • 2【题目】试写一算法，实现顺序栈的取栈顶元素操作
    • 3【题目】试写一算法，实现顺序栈的出栈操作
    • 4 【题目】若顺序栈的类型重新定义如下。试编写算法，
    • 5【题目】若顺序栈的类型重新定义如下。试编写算法，
    • 6【题目】若顺序栈的类型重新定义如下。试编写算法，
    • 7 【题目】若顺序栈的类型重新定义如下。试编写算法，
    • 8【题目】试写一算法，借助辅助栈，复制顺序栈S1得到S2。
    • 9【题目】试写一算法，求循环队列的长度。
    • 10【题目】如果希望循环队列中的元素都能得到利用，
    • 11【题目】假设将循环队列定义为：以域变量rear
    • 12【题目】已知k阶斐波那契序列的定义为:
    • 12【题目】设A=(a1,…,am)和B=(b1,…,bn)均为有序顺序表，
    • 13 【题目】试写一算法，实现顺序表的就地逆置，
    • 14【题目】试对一元稀疏多项式Pn(x)采用存储量同多项式
    • 15 【题目】假设有两个集合A和B分别用两个线性表LA和LB
    • 16【题目】试写一算法，实现链栈的判空操作。
    • 17 【题目】试写一算法，实现链栈的取栈顶元素操作。
    • 18 【题目】试写一算法，实现链队列的判空操作。
    • 19 【题目】试写一算法，实现链队列的求队列长度操作。
    • 20【题目】（PE68） 假设以带头结点的循环链表表示队列，并且
      • 在自己电脑的测试代码及数据
    • 21 【题目】试写一算法，实现带头结点单链表的判空操作。
    • 22 【题目】试写一算法，实现带头结点单链表的销毁操作。
    • 23 【题目】试写一算法，实现带头结点单链表的清空操作。
    • 24 【题目】试写一算法，实现带头结点单链表的求表长度操作。
    • 25（PE82）【题目】试写一算法，在带头结点单链表L插入第i元素e。
      • 测试代码
    • 26（84）【题目】试写一算法，在带头结点单链表删除第i元素到e。
    • 27 【题目】试写一算法，在带头结点单链表的第i元素起的
    • 28【题目】试写一算法，在带头结点单链表删除第i元素
    • 29【题目】试写一算法，删除带头结点单链表中所有值
    • 30【题目】试写一算法，删除带头结点单链表中所有值

广工 AnyviewC 数据结构习题 第二章

Anyview 数据结构 第二章

/**********

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

StackEmpty_Sq(SqStack S)。

顺序栈的类型定义为：

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

***********/

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

/**********

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

GetTop_Sq(SqStack S, ElemType &e)。

顺序栈的类型定义为：

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

***********/

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

/**********

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

Pop_Sq(SqStack &S, ElemType &e)。

顺序栈的类型定义为：

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

***********/

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

/**********

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

构建初始容量和扩容增量分别为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。                 */
{
    if (size>0 && inc>0)
     {
        S.size=size;
        S.increment=inc;
        S.top=size;
        return OK;
     }        
     return ERROR;
}

/**********

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

实现顺序栈的判空操作。

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

***********/

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

/**********

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

实现顺序栈的入栈操作。

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

***********/

Status Push_Sq2(SqStack2 &S, ElemType e)
/* 若顺序栈S是满的，则扩容，若失败则返回ERROR。*/
/* 将e压入S，返回OK。                          */
{
    if (S.top>=S.elem+S.size)
     {
        
        if (S.increment<=0)
            return ERROR;
        ElemType *p;
        p = (ElemType *) realloc (S.elem,(S.size+S.increment)*sizeof(ElemType));
        if (p==NULL)
            return ERROR;
        S.elem=p;
        S.top=S.elem+S.size;
        S.size+=S.increment;
        
     }
        
        *S.top=e;
        S.top++;
        return OK;
}

/**********

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

实现顺序栈的出栈操作。

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

***********/

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

/**********

8【题目】试写一算法，借助辅助栈，复制顺序栈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

***********/

Status CopyStack_Sq(SqStack S1, SqStack &S2) 
/* 借助辅助栈，复制顺序栈S1得到S2。    */ 
/* 若复制成功，则返回TRUE；否则FALSE。 */
{
    ElemType e;
    
    SqStack S0;
   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;
   l=S1.top;
   for (i=0;i<l;i++)
   {
      Pop_Sq(S1, e);
      Push_Sq(S0, e);
   }
   for (i=0;i<l;i++)
   {
      Pop_Sq(S0, e);
      Push_Sq(S2,e);
   }
   DestroyStack_Sq(S0);
   return OK;
}

/**********

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

循环队列的类型定义为：

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

***********/

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

/**********

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

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

typedef struct {
  ElemType elem[MAXQSIZE];
  int tag;
  int front;
  int rear;
} CTagQueue;

**********/

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;
    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;
    return OK;
}

/**********

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

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

typedef struct {
  ElemType elem[MAXQSIZE];
  int length;
  int rear;
} CLenQueue;

**********/

Status EnCQueue(CLenQueue &Q, ElemType x)
  /* 将元素x加入队列Q，并返回OK；*/
  /* 若失败，则返回ERROR。       */
{
   if (Q.elem==NULL || 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)
  /* 将队列Q的队头元素退队到x，并返回OK；*/
  /* 若失败，则返回ERROR。               */
{
    if (Q.elem==NULL ||Q.length==0)
        return ERROR;
    if(Q.rear+1>=Q.length)  
        x=Q.elem[Q.rear+1-Q.length];
    else
        x=Q.elem[MAXQSIZE-Q.length+Q.rear+1];
    //x = Q.elem[(Q.length-Q,rear + MAXQSIZE) % MAXQSIZE];
    --Q.length;
    return OK;
}

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的算法。

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

typedef struct {
  ElemType *base; // 存储空间的基址
  int front;      // 队头位标
  int rear;       // 队尾位标，指示队尾元素的下一位置
  int maxSize;    // 最大长度
} SqQueue;
**********/
long Fib(int k, int n)
/* 求k阶斐波那契序列的第n项fn
要求：必须使用循环队列
*/
{
	long sum = 0;
	int i, j,m;
	SqQueue a;
	a.maxSize = k+1;	
	//注意循环队列由于判空判满的问题所以有一个元素空间没有用
	a.base = (ElemType*)malloc(a.maxSize * sizeof(ElemType));
	a.front = 0;
	a.rear = 0;


	if (n < k - 1)
	{
		sum = 0;
		return sum;
	}
	else if (n == k-1)
	{
		sum = 1;
		return sum;
	}

	//初始化该队列对应的斐波那契数列
	do
	{
		a.base[a.rear] = 0;

		a.rear = (a.rear + 1) % a.maxSize;
	} while ((a.rear + 1) % a.maxSize != a.front);
	a.base[a.rear-1] = 1;
	cout << a.base[a.rear-1] << endl;
	cout << a.rear << endl;
	cout << a.front << endl;
	cout << endl;

	m = a.front;
	for (i = k-1; i < n; i++)
	{
		long v = 0;
		j = a.front;
		do
		{
			v += a.base[j];
			cout << "v:" << v << "	" << "j:" << j << endl;
			j = (j + 1) % a.maxSize;
		} while ((j + 1) % a.maxSize != a.front);
		cout << endl;
		cout << "v:" << v << "	"<< "i:" << i << endl;
		cout << "rear	" << a.rear << endl;
		cout << endl;

		
		a.base[a.rear] = v;
		if ((a.rear + 1) % a.maxSize == a.front)
		{
			a.rear = a.front;
		}
		else
			a.rear = (a.rear + 1) % a.maxSize;
		

		a.front = (a.front + 1) % a.maxSize;
		
		
	}

	sum = 0;
	j = a.front;
	do
	{
		sum += a.base[j];
		cout << a.base[j] << "	" << "j:" << j << endl;
		j = (j + 1) % a.maxSize;
	} while ((j + 1) % a.maxSize != a.front);

	return sum;
}

/**********

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’的首元，则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     */
{
   int i;
    if (A.elem[0]!=B.elem[0])
    {
        if (A.elem[0] < B.elem[0])
            return '<';
        else if (A.elem[0] > B.elem[0] )
            return '>';
        else if (A.length == B.length)
            return '=';
    }
    
    for (i=0;i<A.length;i++)
    {
        if (A.elem[i] == B.elem[i])
            continue;
        else 
            break;
    }
    
     if (i == A.length)
    {
        if (i == B.length)
            return '=';
        else 
            return '<';
    }
    else
    {
        if (i+1 == B.length)
            return '>';
        else if (A.length < B.length)
            return '<';
        else if (A.length > B.length)
            return '>';
        else if (A.elem[i+1] < B.elem[i+1])
            return '<';
        else 
            return '>';
    }
}

/**********

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

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

typedef struct {
  ElemType *elem;
  int       length;
  int       size;
  int       increment;
} SqList;
**********/
void Inverse(SqList &L)
{
    for (i=0;i<L.length/2;i++)
	{
		ElemType t;
		t = L.elem[i];
		L.elem[i] = L.elem[L.length - i - 1];
		L.elem[L.length - i - 1] = t;
	}
}

/**********

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

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

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

typedef struct {
  int  coef;  // 系数
  int   exp;  // 指数
} Term;

typedef struct {
  Term  *elem;   // 存储空间基址
  int    length; // 长度（项数）
} Poly;
**********/
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;
	float t;
	for ( i = 0; i < P.length; i++)
	{
		t = x;
		if (P.elem[i].exp == 0)
		{
			t = 1.0;
		}
		else
		{
			for ( j = 1; j < P.elem[i].exp; j++)
				t *= x;
		}
		sum += (float)P.elem[i].coef*t;
	}
	return sum;
}

/**********

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

表示(即：线性表中的数据元素即为集合中的成员），
试写一算法，求并集 A ＝ A ∪ B A＝A∪B 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
**********/
void Union(SqList &La, SqList Lb)
{
    if (La.elem == NULL)
        if (Lb.elem == NULL)
            La.elem == NULL;
        else
            La.elem = Lb.elem;
    else
    {
       int la = ListLength_Sq(La);
        int lb = ListLength_Sq(Lb);
    
        int i,j;
        for (i = 1;i <= lb;i++)
        {
            GetElem_Sq(Lb,i,j);
            if (Search_Sq(La,j) != -1)
                continue;
            else
            {
                //if (La.length+1 == La.size)
                Append_Sq(La,j);
            }    
        }
    }             
     
}

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

/**********

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

链栈的类型定义为：

typedef struct LSNode {
  ElemType data;       // 数据域
  struct LSNode *next; // 指针域
} LSNode, *LStack;    // 结点和链栈类型
***********/
Status StackEmpty_L(LStack S)
/* 对链栈S判空。若S是空栈，则返回TRUE；否则返回FALSE */
{
    if (S == NULL)
        return TRUE;
    else
        return  FALSE;
}

/**********

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

链栈的类型定义为：

typedef struct LSNode {
  ElemType data;       // 数据域
  struct LSNode *next; // 指针域
} LSNode, *LStack;    // 结点和链栈类型
***********/
Status GetTop_L(LStack S, ElemType &e) 
/* 取链栈S的栈顶元素到e，并返回OK; */
/* 若S是空栈，则失败，返回ERROR。  */
{
    if (S == NULL)
        return ERROR;
    else
    {
        e = S->deta;
        return  OK;
    }
}

/**********

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

链队列的类型定义为：

typedef struct LQNode {     
  ElemType  data;  
  struct LQNode  *next;  
} LQNode, *QueuePtr; // 结点和结点指针类型

typedef struct {     
  QueuePtr  front;  // 队头指针
  QueuePtr  rear;   // 队尾指针
} LQueue;  // 链队列类型


Status QueueEmpty_LQ(LQueue Q)
/* 判定链队列Q是否为空队列。           */
/* 若Q是空队列，则返回TRUE，否则FALSE。*/
{
   if (Q.front->next == Q.rear)
    return TRUE;
    else
    return FALSE;
}

/**********

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

链队列的类型定义为：

typedef struct LQNode {     
  ElemType  data;  
  struct LQNode  *next;  
} LQNode, *QueuePtr; // 结点和结点指针类型
typedef struct {     
  QueuePtr  front;  // 队头指针
  QueuePtr  rear;   // 队尾指针
} LQueue;  // 链队列类型
***********/
int QueueLength_LQ(LQueue Q)
/* 求链队列Q的长度并返回其值 */
{
    int l = 0;
    QueuePtr p = Q.front;
    while(p->next != Q.rear)
    {
        l++;
        p = p->next;
    }
    return l;
}

/**********

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

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

typedef struct LQNode {
  ElemType data;
  struct LQNode *next;
} LQNode, *CLQueue;
**********/
Status InitCLQueue(CLQueue &rear) // 初始化空队列
{ 

    if (NULL == (rear = (CLQueue) malloc (sizeof(CLQueue))))
        return OVERFLOW;
    else
    {
        rear->next = NULL;
        //L->next = rear;
        return OK;
    }
}

Status EnCLQueue(CLQueue &rear, ElemType x) // 入队
{ 
    CLQueue p;
    //q = rear->next;
   if (NULL == (p = (LQNode*) malloc (sizeof(LQNode))))
        return OVERFLOW;
    p->data = x;
    
    //printf("%c\n",x);
    //printf("\n");
        
    p->next = rear->next;
    
    rear->next = p;
    rear = p;
    //rear->next->data;
    return OK;
}

Status DeCLQueue(CLQueue &rear, ElemType &x) // 出队
{ 
CLQueue p = rear;

    if (rear->next == NULL)
        return ERROR;
    else
    {
        while (p->next != rear)
            p = p->next;
        x = rear->data;
        rear = rear->next;
        p->next = rear;
        return OK;
    }
}

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

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

#include <iostream>
#include <cstdlib>

using namespace std;

#define TRUE 1
#define FALSE 0

#define OK 1
#define ERROR 0
#define OVERFLOW -1

typedef int Status;

#define ElemType char 

typedef struct LQNode {
	ElemType data;
	struct LQNode *next;
} LQNode, *CLQueue;


Status InitCLQueue(CLQueue &rear) // 初始化空队列
{
	if (NULL == (rear = (CLQueue)malloc(sizeof(CLQueue))))
		return OVERFLOW;
	else
	{
		rear->next = rear;
		//L->next = rear;
		return OK;
	}
}


Status EnCLQueue(CLQueue &rear, ElemType x) // 入队
{
	CLQueue p;
	if (NULL == (p = (CLQueue)malloc(sizeof(CLQueue))))
		return OVERFLOW;
	p->data = x;
	p->next = rear->next;
	rear->next = p;
	rear = p;
	return OK;
}


Status DeCLQueue(CLQueue &rear, ElemType &x) // 出队
{
	CLQueue p = rear->next;
	CLQueue q = p->next;

	if (rear->next == rear)
		return ERROR;
	else
	{
		x = q->data;
		p->next = q->next;
		return OK;
	}
}

//定义一个打印函数
void printCLquene(CLQueue rear)
{
	CLQueue p = rear->next;
	p = p->next;
	while (p != rear->next)
	{
		printf("%c",p->data);
		p = p->next;
	}
	cout << endl;
}

//输入函数
void input(CLQueue &rear,int n)
{
	char c;
	CLQueue q,p;

	
	p = rear->next;
	for (int i = 0; i < n; i++)
	{
		cout << "输入data" << endl;
		cin >> c;

		q = (CLQueue)malloc(sizeof(CLQueue));
		q->data = c;

		
		rear->next = q;
		rear = q;
		rear->next = p;
	}
}

int main()
{
	//定义一个循环列表
	CLQueue rear, p,q;
	初始化
	InitCLQueue(rear);

	input(rear, 3);
	
	printCLquene(rear);

	//入队操作
	ElemType e;
	e = 'M';
	EnCLQueue(rear,e);

	printCLquene(rear);

	return 0;
}

/**********

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

单链表的类型定义为：

typedef struct LNode {     
  ElemType  data;  
  struct LNode  *next;  
} LNode, *LinkList; // 结点和结点指针类型
***********/
Status ListEmpty_L(LinkList L)
/* 判定带头结点单链表L是否为空链表。   */
/* 若L是空链表，则返回TRUE，否则FALSE。*/
{
    if (L->next == NULL)
        return TRUE;
    else
        return FALSE;
}

/**********

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

单链表的类型定义为：

typedef struct LNode {     
  ElemType  data;  
  struct LNode  *next;  
} LNode, *LinkList; // 结点和结点指针类型
***********/
Status DestroyList_L(LinkList &L)
/* 销毁带头结点单链表L，并返回OK。*/
{
    LinkList p,q;
    LinkList a,b,c;
    p = L->next;
    if (p == NULL)
    {
        free(L);
        return OK;  
    }
    while (p != NULL)
    {
        q = p;
        p = p->next;
        free(q);
    }
    
    free(L);
    return OK;
}

/**********

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

单链表的类型定义为：

typedef struct LNode {     
  ElemType  data;  
  struct LNode  *next;  
} LNode, *LinkList; // 结点和结点指针类型
***********/
Status ClearList_L(LinkList &L)
/* 将带头结点单链表L置为空表，并返回OK。*/
/* 若L不是带头结点单链表，则返回ERROR。 */
{
     if (NULL == L)
        return  ERROR;
   LinkList p,q;
    LinkList a,b,c;
    p = L->next;
    if (p == NULL)
        return OK;
    while (p != NULL)
    {
        q = p;
        p = p->next;
        free(q);
    }
    
    L->next = NULL;
    return OK;
}

/**********

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

单链表的类型定义为：

typedef struct LNode {     
  ElemType  data;  
  struct LNode  *next;  
} LNode, *LinkList; // 结点和结点指针类型
***********/
int ListLength_L(LinkList L)
/* 求带头结点单链表L的长度，并返回长度值。*/
/* 若L不是带头结点单链表，则返回-1。      */
{
    if (NULL == L)
        return -1;
   LinkList p;
    p = L->next;
    
    int num = 0;
    while (p != NULL)
    {
        p = p->next;
        num++;
    }
    return num;
}

/**********

25（PE82）【题目】试写一算法，在带头结点单链表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。              */
{
    LinkList p = L;
    if (NULL == p || i <1)
        return ERROR;
    
    int num = 1;
    while (p->next != NULL && num<i)
    {
        p = p->next;
        num++;
    }
    if (num <i)
        return ERROR;
    LinkList m;
    m = (LinkList) malloc (sizeof(LNode));
    
    m->next = p->next;
    p->next = m;
    m->data = e;
    
    return OK;
}

测试代码

#include <iostream>
#include <cstdlib>

using namespace std;

#define TRUE 1
#define FALSE 0

#define OK 1
#define ERROR 0
#define OVERFLOW -1

typedef int Status;

#define ElemType char 

typedef struct LNode {
	ElemType      data;
	struct LNode *next;
} LNode, *LinkList;


Status Insert_L(LinkList L, int i, ElemType e)
/* 在带头结点单链表L插入第i元素e，并返回OK。*/
/* 若参数不合理，则返回ERROR。              */
{
	LinkList p = L;
	if (NULL == p || i <1)
		return ERROR;

	int num = 1;
	while (p->next != NULL && num<i)
	{
		p = p->next;
		num++;
	}
	if (num <i)
		return ERROR;
	LinkList m;
	m = (LinkList)malloc(sizeof(LinkList));

	m->next = p->next;
	p->next = m;
	m->data = e;

	return OK;
}

//初始化带头结点的单链表函数
void InitLinkList(LinkList &L)
{
	LinkList q;
	
	char c[] = {"abcdefg"};
	
	q = L;
	//q->next = L->next;

	for (int i = 0; i < 7; i++)
	{
		LinkList p = (LinkList)malloc(sizeof(LinkList));
		p->data = c[i];
		p->next = q->next;
		q->next = p;
		q = q->next;
	}
	//L = q;
}


//定义打印函数
void printLinkLIst(LinkList &L)
{
	LinkList p;
	p = L->next;

	while (p != NULL)
	{
		cout << p->data;
		p = p->next;
	}
	cout << endl;
}

int main()
{
	//定义一个带头结点的单链表
	//L3 = ( abcdefg)
	LinkList L = (LinkList)malloc(sizeof(LinkList));
	L->next = NULL;

	InitLinkList(L);

	printLinkLIst(L);

	Insert_L(L,2,'*');

	printLinkLIst(L);

	return 0;
}

/**********

26（84）【题目】试写一算法，在带头结点单链表删除第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。                */
{
    LinkList p = L;
    LinkList q ;
    if (NULL == p || i <1)
        return ERROR;
    
    int num = 0;
    while (p->next != NULL && num<i)
    {
        q = p;
        p = p->next;
        num++;
    }
    
    if (i > num)
        return ERROR;
    
        LinkList m = p;
        e = m->data;
        q->next = m->next;
   
     //free(m);
     return OK;
}

/**********

27 【题目】试写一算法，在带头结点单链表的第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。  */
{
     LinkList p = L;
  LinkList q;
  q = (LinkList) malloc (sizeof(LNode));
  Li = (LinkList) malloc (sizeof(LNode));
    if (NULL == p || i <1)
    {
        Li = NULL;
        return ERROR;
    }
    
    int num = 0;
    while (p->next != NULL && num<i)
    {
        q = p;
        p = p->next;
        num++;
    }
    if (i > num)
    {
        Li = NULL;
        return ERROR;
    }
        
     LinkList p1 = p;
     LinkList p2 = Li;
     
     while (p1 != NULL)
     {
        q->next = p1->next;
        
        p1->next = p2->next;
        p2->next = p1;
        
        p1 = q->next;
        p2 = p2->next;
     }
     
     return OK;
}

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

/**********

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

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

typedef struct LNode {
  ElemType      data;
  struct LNode *next;
} LNode, *LinkList;
**********/
Status Cut_L(LinkList L, int i)
/* 在带头结点单链表L删除第i元素起的所有元素，并返回OK。*/
/* 若参数不合理，则返回ERROR。                         */
{
     LinkList p = L;
    if (NULL == p || i <1)
        return ERROR;
    
    int num = 0;
    while (p->next != NULL )
    {
        p = p->next;
        num++;
    }
    
    if (i > num)
        return ERROR;
        
     LinkList m = L;
     for(int k=0;k<i-1;k++)
        m = m->next;
    
    m->next=null;
      return OK;
}

/**********

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

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

typedef struct LNode {
  ElemType      data;
  struct LNode *next;
} LNode, *LinkList;
**********/
Status DeleteX_L(LinkList L, ElemType x)
/* 删除带头结点单链表L中所有值为x的元素，      */
/* 并释放被删结点空间，返回实际删除的元素个数。*/
{
    LinkList p = L;
    if (NULL == p->next)
        return ERROR;
    
    int num = 0;
    LinkList m;
    while (p != NULL)
    {
        m = p;
        if (m->next->data == x)
        {
            m = m->next;
            p->next = m->next;
            free(m);
            num++;
        }
        p = p->next;
    }
    
    return num;
}

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

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

typedef struct LNode {
  ElemType      data;
  struct LNode *next;
} LNode, *LinkList;
******/
Status DeleteSome_L(LinkList L, ElemType x)
/* 删除带头结点单链表L中所有值小于x的元素，    */
/* 并释放被删结点空间，返回实际删除的元素个数。*/
{
     LinkList p = L;
    if (NULL == p->next)
        return ERROR;
    
    int num = 0,flag;
    LinkList m;
    while (p->next != NULL)
    {
        flag = 0; 
        if (p->next->data < x)
        {
            m = p->next;
            p->next = m->next;
            free(m);
            num++;
            flag = 1;
        }
        if (!flag)
            p = p->next;
    }
    
    return num;
}
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

广工 AnyviewC 数据结构习题 第二章 的相关文章

  • WIndows下cmd报错退出进程，代码为1

    WIndows下cmd报错退出进程 xff0c 代码为1 不知道什么原因出现了这种情况 参考微软官方回答 xff08 https answers microsoft com zh hans windows forum all cmd E6

  • docker使用load加载tar镜像时报错no such file or directory

    docker使用load加载tar镜像时报错no such file or directory 解决docker在使用load加载tar镜像时报错open var lib docker tmp docker import xxxxxxxxx

  • sudo启动的程序找不到动态库文件

    sudo启动的程序找不到动态库文件 在 bashrc中添加的LD LIBRARY PATH xff0c 并sudo ldconfig后 xff0c sudo启动的程序还是找不到依赖库 原因分析 sudo启动的程序不会用到bashrc中的配置

  • Pycharm显示cannot find declaration to go to，设置子目录为根目录

    Pycharm显示cannot find declartion to go to xff0c 设置子目录为根目录 使用Pycharm用ctrl跳转函数时显示cannot find declaration to go to 原因可能有很多 x

  • pycharm 2021.2.2 版本之前试用期过了怎么办

    pycharm 2021 2 2 版本之前试用期过了怎么办 虽然 jetbrains 的产品是商业收费 xff0c 而且价格不菲 xff0c 但官方还是为免费使用留下的空间 xff0c 实在良心 收费版可以免费试用30天 xff0c 问题是

  • layabox Native 自己下载资源并缓存

    我们在开发中 xff0c 不管是打的网络版还是本地版 xff0c 或多或少都有可能加载一些网络上的资源 xff0c 并且这些资源不想用dcc方式 xff0c 毕竟现在苹果对热更新管得比较严 xff0c 那如果不用dcc方式 xff0c 我们

  • Flutter 浅析之 自定义view 六 CircleProgressBar

    技术无止境 xff0c 只怕不学习啊 xff0c Flutter 我们开始吧 CircleProgressBar原型进度条 自定义view结合动画来完成进度条效果 CustomPainter 先来想想使用canvas的哪个方法来完成绘制 首

  • RoboMaster机甲大师：裁判系统服务器搭建（完全版）

    RoboMaster机甲大师 xff1a 裁判系统服务器搭建 xff08 完全版 xff09 更新 2022 03 28更新 2022 03 23前言准备搭建步骤MySQL安装配置环境组建局域网路由器端 Router 服务器端 Server

  • HTTP 请求方法 GET/POST/PUT/DELETE

    Web HTTP基础知识 HTTP请求是什么 xff1f HTTP超文本传输协议 xff0c 是确保服务器 xff08 Server xff09 和客户端 xff08 Client xff09 之间的正确通信 一个请求和响应的过程 xff1

  • kalibr标定工具使用方法

    1 首先在docker中安装ubuntu14 04 在16 04编译不过 xff0c 不知道为什么 xff0e 2 安装kalibr ros包 xff0e 3 下载官方提供的验证数据 xff0e 4 我们先标定相机 xff0c 使用的数据为

  • C语言、C++ 和 C# 三者的区别

    按时间顺序说一说这三门语言的基本吧 xff0c 这样比较一下儿就能知道他们的区别了 一 xff1a xff23 语言 xff23 语言诞生得非常早 xff0c 当时人们普遍还习惯用汇编语言编写软件 xff0c 而且没有什么统一 xff0c

  • requests的代理使用

    import requests from lxml import etree headers 61 39 User Agent 39 39 Mozilla 5 0 Macintosh Intel Mac OS X 10 15 7 Apple

  • HiMPP SAMPLE_VENC分析

    mpp中的例程 每一个例程面向一个典型应用 xff0c common是通用性主体函数 xff0c 我们只分析vencvenc中的main调用venc中的功能函数 xff0c 再调用common中的功能函数 xff0c 再调用mpp中的API

  • H264数据格式解析

    什么是H 264 H264 是 MPEG 4 标准所定义的最新编码格式 xff0c 同时也是技术含量最高 代表最新技术水平的视频编码格式之一 xff0c 标准写法应该是H 264H264 视频格式是经过有损压缩的 xff0c 但在技术上尽可

  • ISP和IQ调试

    什么是ISP isp image signal process 图像信号处理 xff0c 这是技术image signal processor 图像信号处理器 这是设备本质 xff1a 通过数字运算来修补前端采集的不理想数据 xff0c 尽

  • cortex-m3中寄存器

    简介 Cortex M3 是一个 32 位处理器内核 内部的数据路径是 32 位的 xff0c 寄存器是 32 位的 xff0c 存储器接 口也是 32 位的 CM3 采用了哈佛结构 xff0c 拥有独立的指令总线和数据总线 xff0c 可

  • RGBD-SLAM（一）——深度摄像机

    工欲善其事必先利其器 我们先从能够获取RGBD数据的相机开始谈起 首先我们来看一看其分类 一 根据其工作原理主要分为三类 xff1a 1 双目方案 xff1a xff08 1 xff09 原理 xff1a http blog csdn ne

  • 软件执行的流程

    什么是编译原理 代码执行分为2个部分 compilers 编译器 1 将代码编译成可执行文件 xff0c 汇编代码或者字节码 xff0c MDK就是一个编译器interpreters 解释器 1 执行编译器生成的可执行文件 xff0c mc

  • 编译器过程概述

    Lexical Analysis xff08 词法分析 xff09 词法分析的目的是将程序文本划分为单词 xff0c 或者我们在编译器中所说的 xff0c 标记利用程序文本中的空格 xff0c 分号等符号来识别程序文本 Parsing xf

  • 编程语言的一些答疑

    为什么会有这么多中编程语言 因为需求是多种多样的 xff0c 为一种语言实现所有需求是非常困难的 为什么会有新的编程语言 实现一个新的编译器并不困难 xff0c 几个人就可以了 xff0c 大型的编译器可能也就十几个人 xff0c 真正的成

随机推荐

  • 【串口系列】不定长接收多种方式

    目录 背景 声明 开发环境 正文 一 接收中断 43 空闲中断 二 接收中断 43 T35定时器中断 T35定时器 三 空闲中断 43 DMA 43 循环队列 背景 在单片机开发过程中 xff0c 串口通讯是一种非常常用的串行通通讯方式 x

  • 迭代器学习笔记

    本文是学习 STL源码剖析 时的学习笔记 1 迭代器是一种smart pointer 迭代器是一种类 xff0c 其包装了原生指针 xff0c 并重载了operator operator gt operator 61 operator 43

  • linux中gdb调试出现buffer overflow detected，program terminated with signal SIGABRT Aborted

    strcpy str1 str2 或memcpy p1 p2 size 极易出错 一定要确保str1 p1已经申请缓存 xff0c 且缓存空间充足 本次出错地方为 xff1a linux下文件地址较长 xff0c str1只申请了40个字节

  • Git系列一：Git安装 git gui here和git bash here的区别

    Git简介 xff1a Git 的工作就是创建和保存你的项目的快照及与之后的快照进行对比 说白了就是代码版本的控制系统 据个人实测 xff0c 在写论文的时候 xff0c 会有很多论文备份 xff0c 很不方便 xff0c Git对Word

  • VirtualBox虚拟机配置ssh与宿主机互通，实现文件传输

    在virtualbox中安装好Ubuntu16 04之后 xff0c 由于virtualbox与主机之间的文件拖放总是失败 已经安装好了增强功能 xff0c 双向复制 xff0c 文件拖放功能 xff0c 但还是出现问题 xff0c 因此搭

  • catkin_make编译报错：/usr/bin/ld: 找不到 -lxxx

    Linux下编译程序的时候 xff0c 出现 usr bin ld cannot find lxxx的错误 xff0c 主要的原因是找不到相应的动态库 xff0c 库文件没有导入到ld检索目录中 比如找不到 xff1a usr bin ld

  • Altium designer的工程文件都被改成SolidWorks2022了，且无法修改默认的启动程序的解决办法：

    安装soildworks2022后就发现电脑里的PCB工程文件除了 xx PcbDoc 默认打开方式是AD xff0c 其他的默认打开方式都是SoildWorks 而且右键更改属性里的默认打开方式也无法解决问题 解决办法 xff1a 需要修

  • printf输出bool值 | printf转换符

    bool类型是当整形输出的 bool c 61 false printf 34 d n 34 c 1 xff0e 转换说明符 a A 浮点数 十六进制数字和p P 记数法 C99 c 字符 d 有符号十进制整数 f 浮点数 包括float和

  • Cmake升级 更新 Ubuntu16.04 + ROS

    重要提示 千万不要卸载 Ubuntu原有的cmake xff0c 否则之前经过原有cmake编译过的文件将也会被删除 xff0c 比如 ros 千万不要使用下面这句命令删除原有的 cmake xff01 xff01 xff01 xff01

  • Ubuntu下扫描同一局域网的其他设备IP

    1 安装arp scan sudo apt get install arp scan 2 使用ifconfig查看本机IP地址 xff0c 一般有线在interface en0 eth0 无线在wlan0上 ifconfig 箭头中所指是我

  • C/C++基础 C语言预编译宏__LINE__、__FILE__、__DATE__、__TIME__、__FUNCTION__

    ANSIC标准定义了以下6种可供C语言使用的预定义宏 xff1a LINE 在源代码中插入当前源代码行号 FILE 在源代码中插入当前源代码文件名 DATE 在源代码中插入当前编译日期 注意和当前系统日期区别开来 TIME 在源代码中插入当

  • linux下每次git clone不需输入账号密码的方法

    有的仓库有很多的子模块 submodule 当clone的时候每个子模块都会让输入一次账户密码 xff0c 不胜其烦 xff0c 解决方法如下 xff1a 在 下 xff0c touch创建文件 git credentials 用vim编辑

  • Ubuntu创建新用户的两种方法

    组里的服务器是Ubuntu系统 xff0c 跑实验的话需要远程访问 xff0c 这样的话需要在服务器上创建一个自己的账户 xff0c 本文记录一下在Ubuntu系统下创建新用户的过程 xff08 服务器的远程访问一般通过ssh来实现 xff

  • Ubuntu中gnome-terminal的使用

    基本使用 gnome terminal命令用于打开一个新的终端 xff0c 直接在命令行就可以打开一个新的终端 gnome terminal 打开后自动最大化 gnome terminal maximize 打开后全屏 gnome term

  • 【计算机基础】字节序

    字节序 计算机最小的存储单位是 位 xff08 Bit xff09 xff0c 但是 xff0c 计算机中最基本的存储单位是字节 xff08 Byte xff09 1 Byte 61 8 Bit 计算机在存储大于1字节的数据时 xff0c

  • 内存中堆和栈的区别

    在说堆和栈之前 xff0c 我们先说一下JVM xff08 虚拟机 xff09 内存的划分 xff1a Java程序在运行时都要开辟空间 xff0c 任何软件在运行时都要在内存中开辟空间 xff0c Java虚拟机运行时也是要开辟空间的 J

  • 1.5 万字 + 40 张图解 HTTP 常见面试题（值得收藏）

    作者 xff1a 小林coding 图解计算机基础网站 xff1a https xiaolincoding com 大家好 xff0c 我是小林 xff0c 我最开始写的第一篇图解文章就是这篇 xff1a 那时候我也就不到 100 读者 x

  • libcurl第七课 multipart/formdata表单使用

    场景 multipart form data是浏览器用表单上传文件的方式 最常见的情境是 xff1a 在写邮件时 xff0c 向邮件后添加附件 xff0c 附件通常使用表单添加 xff0c 也就是用multipart form data格式

  • 【测绘专用】中海达全站仪数据导入南方CASS

    先从全站仪导入数据到电脑 xff08 我是用U盘的 xff09 xff0c 然后打开数据文件后是这个样子 上图并不是导出后原先的数据格式 导出文件后 xff0c 它的数据格式实际上不是上面这样的 xff0c 要经过处理后才行 从中海达下载数

  • 广工 AnyviewC 数据结构习题 第二章

    广工 AnyviewC 数据结构习题 第二章 广工 AnyviewC 数据结构习题 第二章Anyview 数据结构 第二章1 题目 试写一算法 xff0c 实现顺序栈的判空操作2 题目 试写一算法 xff0c 实现顺序栈的取栈顶元素操作3

热门标签