数据结构与算法

发布于 2023-11-19  77 次阅读


int SubSeq(LinkList A, LinkList B) {//10
	//请在下面编写代码
	/********************Begin********************/
LinkList pre = A;
	LinkList p = pre->next;
	LinkList q = B->next;
	while(p && q)
	{
		if(p->val == q->val)
		{
			p = p->next;
			q = q->next;
		}
		else{
			pre = pre->next;
			p = pre->next;
			q = B->next;
		}
	}
	if(q == NULL)
		return true;
	else
		return false;

	/*********************End*********************/
}
//1
#include "sqlist.h"					//声明顺序表的类型

//整体建立顺序表
void CreateList(SqList *&L, ElemType a[], int n)
{
	L = (SqList *)malloc(sizeof(SqList));
	for (int i = 0; i < n; i++)
		L->data[i] = a[i];
	L->length = n;
}

//初始化线性表
void InitList(SqList *&L)
{
	L = (SqList *)malloc(sizeof(SqList));	//分配存放线性表的空间
	L->length = 0;
}

//输出线性表
void DispList(SqList *L)
{
	for (int i = 0; i < L->length; i++)
		printf("%c ", L->data[i]);
	printf("\n");
}

//插入第i个元素
bool ListInsert(SqList *&L, int i, ElemType e)
{
    //请在下面输入代码
    /******************************Begin/******************************/
	int n=0;
    for(n=L->length;n>=i;n--){
      L->data[n]=L->data[n-1];}
      L->data[i-1]=e;
      ++L->length;
    
    
    /******************************Begin/******************************/
}

//删除第i个元素
bool ListDelete(SqList *&L, int i, ElemType &e)
{
	//请在下面输入代码
    /******************************Begin/******************************/
	int n=0;
    for(n=i;n<L->length;n++){
        L->data[n-1]=L->data[n];
        
        }L->length--;
    
    
    
    /******************************Begin/******************************/
}

//7
#include <stdio.h>
#include <stdlib.h>

const int MAXSIZE = 3010;   //循环队列最大容量
typedef int ElemType;       //循环队列元素类型

ElemType Q[MAXSIZE];        //数组模拟循环队列
int front, rear;            //队首、队尾指针

//初始化循环队列
void InitQueue()
{
    front = rear = 0;
}

//判循环队列是否为空,空返回true;非空返回false
bool EmptyQueue()
{
    return front == rear;
}

//判循环队列是否满,满返回true,不满返回false
bool FullQueue()
{
    return (rear + 1) % MAXSIZE == front;
}

//入队列操作:先把队尾指针加1,然后把元素放入队尾指针指示的位置
void EnQueue(ElemType e)
{
    if (FullQueue())
    {
        return;  //队列已满,无法入队
    }
    Q[rear] = e;
    rear = (rear + 1) % MAXSIZE;
}

//出队列操作:把队首指针加1
void DeQueue()
{
    if (EmptyQueue())
    {
        return;  //队列为空,无法出队
    }
    front = (front + 1) % MAXSIZE;
}

//取队首元素
ElemType GetQueue()
{
    if (EmptyQueue())
    {
        return -1;  //队列为空,无队首元素
    }
    return Q[front];
}

//求解约瑟夫环问题
void josephus(int n, int m)
{
    InitQueue();  //初始化循环队列

    //将1到n依次入队
    for (int i = 1; i <= n; i++)
    {
        EnQueue(i);
    }

    
    while (!EmptyQueue())
    {
        //找到第m个人
        for (int i = 0; i < m - 1; i++)
        {
            //将前m-1个人依次出队并重新入队
            ElemType frontElem = GetQueue();
            DeQueue();
            EnQueue(frontElem);
        }
        //将第m个人出队
        ElemType josephusElem = GetQueue();
        DeQueue();

        printf("%d", josephusElem);
        if (!EmptyQueue())
        {
            printf(" ");
        }
    }
    printf("\n");
}

int main(int argc, char* argv[])
{
    int n, m;
    scanf("%d %d", &n, &m);
    josephus(n, m);
    return 0;
} 

//3
LinkNode *p=L->next->next,*q;
    L->next->next=NULL;
    while(p!=NULL){
        q=L;
        while(q->next!=NULL&&q->next->data<p->data)q=q->next;
       LinkNode *r=q->next;
        q->next=p;
        p=p->next;
        q->next->next=r;
    }

    //4
 // 比较L1和L2的第一个结点的数据,将较小的结点赋值给L,并将对应的指针后移一位
        if (L1->data <= L2->data) {
            L = L1;
            L1 = L1->next;
        }
        else {
            L = L2;
            L2 = L2->next;
        }
        // 将p指向L的第一个结点
        p = L;
        // 循环遍历L1和L2,直到其中一个为空为止
        while (L1 != NULL && L2 != NULL) {
            // 比较L1和L2的当前结点的数据,将较小的结点链接到p的后面,并将对应的指针后移一位
            if (L1->data <= L2->data) {
                p->next = L1;
                L1 = L1->next;
            }
            else {
                p->next = L2;
                L2 = L2->next;
            }
            // 将p指向下一个结点
            p = p->next;
        }
        // 如果L1不为空,则将其链接到p的后面
        if (L1 != NULL) {
            p->next = L1;
        }
        // 如果L2不为空,则将其链接到p的后面
        if (L2 != NULL) {
            p->next = L2;
        }

//5
//初始化顺序栈
void InitStack(SqStack *&s)
{
	//请在下面编写代码
	/**************************************Begin**************************************/
s=(SqStack *)malloc(sizeof(SqStack));
s->top=-1;

    /***************************************End**************************************/
}

//销毁顺序栈
void DestroyStack(SqStack *&s)
{
    //请在下面编写代码
	
    /**************************************Begin**************************************/

free(s);
    /***************************************End**************************************/
}

//判断栈空否
bool StackEmpty(SqStack *s)		
{
	//请在下面编写代码
	/**************************************Begin**************************************/
return (s->top==-1);

    /***************************************End**************************************/
}

//进栈
bool Push(SqStack *&s, ElemType e)	 
{
	//请在下面编写代码
	/**************************************Begin**************************************/
if(s->top==MaxSize-1){
    return false;
}
s->top++;
s->data[s->top]=e;
return true;

    /***************************************End**************************************/
}

//出栈
bool Pop(SqStack *&s, ElemType &e)	 
{
	//请在下面编写代码
	/**************************************Begin**************************************/
if(s->top==-1)
  return false;
e=s->data[s->top];
s->top--;
return true;

    /***************************************End**************************************/
}

//取栈顶元素
bool GetTop(SqStack *s, ElemType &e)	 
{
	//请在下面编写代码
	/**************************************Begin**************************************/
if(s->top==-1)
return true;

    /***************************************End**************************************/
} 

/**
 * 判断给出的括号表达式是否匹配:匹配返回true;不匹配返回false
 */
bool is_valid(char* str)
{
	//请在下面编写代码
	/*************************Begin*********************/
   int len = strlen(str);
	int pos = 0;
	int* ans = (int*)malloc(sizeof(int)*len);
	for (int i = 0; i < len; i++)
	{
		if ((str[i] == '(') || (str[i] == '{') || (str[i] == '['))
		{
			ans[pos++] = str[i];
		}
		if (str[i] == ')')
		{
			if ('(' == ans[pos - 1])
			{
				pos--;
			}
			else
			{
				return false;
			}
		}
		if (str[i] == '}')
		{
			if ('{' == ans[pos - 1])
			{
				pos--;
			}
			else
			{
				return false;
			}
		}
		if (str[i] == ']')
		{
			if ('[' == ans[pos - 1])
			{
				pos--;
			}
			else
			{
				return false;
			}
		}
	}
	if (pos != 0)
	{
		return false;
	}
	return true;
	/**************************End**********************/
}

//6
LinkNode *p=head,*q=NULL;
    while(head!=q){
        p=head;
        while(q!=p->next){
            p=p->next;
        }
        printf("%d ",p->data);
        q=p;
    }

//8
ListNode* deleteNode(ListNode* head, int val) {
    //请在下面编写代码
    /********************Begin********************/
      if (!head) {
        return NULL; // 空链表,直接返回
    }
    if (head->val == val) {
        ListNode* temp = head;
        head = head->next;
        free(temp); // 删除头结点
        return head;
    }
    ListNode* prev = head;
    ListNode* curr = head->next;
    while (curr) {
        if (curr->val == val) {
            prev->next = curr->next;
            free(curr); // 删除当前节点
            break;
        }
        prev = curr;
        curr = curr->next;
    }
    return head;

    
    /*********************End*********************/
}

//9
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

#include <stdlib.h>

typedef int DataType; //元素数据类型

const int MAXN = 100001; //队列最大容量

//循环队列类型定义
typedef struct {
  DataType data[MAXN];
  int head; //队首指针
  int tail; //队尾指针
  int MaxSize; //队列最大容量
}
SqQueue;

//初始化一个空的循环队列:(1)设置队列最大容量,(2)设置队首、队尾指针
void InitQueue(SqQueue* &Q, int capacity) {
  //请在下面编写代码
  /**********************Begin**********************/
  Q = (SqQueue * ) malloc(sizeof(SqQueue));
  Q -> head = Q -> tail = 0;
  Q -> MaxSize = capacity;

  /***********************End***********************/
}

//判队列是否为空
int QueueEmpty(SqQueue * Q) {
  //请在下面编写代码
  /**********************Begin**********************/
  return Q->head == Q->tail ? 1 : 0;
  /***********************End***********************/
}

//判队列是否满
int QueueFull(SqQueue * Q) {
  //请在下面编写代码
  /**********************Begin**********************/
  return (Q->tail + 1) % Q->MaxSize == Q->head ? 1 : 0;
  /***********************End***********************/
}

//入队列操作
void Push(SqQueue* &Q, DataType e) {
  //请在下面编写代码
  /**********************Begin**********************/

  Q->tail = (Q->tail + 1) % Q->MaxSize;
  Q->data[Q->tail] = e;

  /***********************End***********************/
}

//删除队首元素:队首元素存入变量e
void Pop(SqQueue * & Q, DataType & e) {
  //请在下面编写代码
  /**********************Begin**********************/

  Q->head = (Q->head + 1) % Q->MaxSize;
  e = Q->data[Q->head];

  /***********************End***********************/
}

//取队首元素,存入变量e
void GetHead(SqQueue * & Q, DataType & e) {
  //请在下面编写代码
  /**********************Begin**********************/

  e = Q->data[(Q->head + 1)%Q->MaxSize];

  /***********************End***********************/
}

//主函数
int main() {
  int n, q;
  scanf("%d %d", & n, & q); //输入队列容量、询问次数

  SqQueue * Q; //声明循环队列Q
  //循环队列,里面最多放置n个元素,循环队列容量为n+1
  InitQueue(Q, n + 1);

  //请在下面编写代码
  /**********************Begin**********************/

  while (q--) {
    int e = 0;
    char op[10];
    scanf("%s", op);
    switch (op[1]) {
      case 'u': 
        scanf("%d", & e);
        if (QueueFull(Q)) {
          printf("full\n");
        } else {
          Push(Q, e);
        }
        break;
      case 'o': 
        if (QueueEmpty(Q)) {
          printf("empty\n");
        } else {
          Pop(Q, e);
          printf("%d\n", e);
        }
        break;
      case 'r': 
        if (QueueEmpty(Q)) {
          printf("empty\n");
        } else {
          GetHead(Q, e);
          printf("%d\n", e);
        }
        break;
    }
  }

  /***********************End***********************/
  return 0;
}