数据结构与算法（ｅｄｕｃｏｄｅｒ作业）

文章目录

前言
一、栈
- 栈——实验及提升训练

前言

数据结构与算法（Ｃ语言）头歌平台

一、栈

顺序表

关卡一　第1关求顺序线性表中连续子表（最少有一个元素）的最大和
第2关寻找缺失的第一个正数
第3关在有序的顺序线性表中找目标值出现的第一个和最后一个位置

#include 
#include 


typedef int DataType;
struct seqList
{//有3个数据成员
  int MAXNUM;//用于记录顺序线性表中能存放的最大元素个数的 整型 MAXNUM   
  int curNum;//用于存放顺序线性表中数据元素的个数  整型  curNum
  DataType *element;//用于存放顺序线性表数据元素的连续空间的起始地址  
};

typedef struct seqList *PseqList;


PseqList createNullList_seq(int m)
{ //若m=0，则返回NULL 
    PseqList plist = (struct seqList *)malloc(sizeof(struct seqList));
    if(plist == NULL) return NULL; //分配空间失败
    plist->MAXNUM = m ;
    plist->curNum = 0;
    plist->element = (DataType *)malloc(sizeof(DataType)*m);
    if(plist->element == NULL) 
    {
        free(plist);
        return NULL;
    }
    return plist;
}




int insertP_tail(PseqList plist , int x)
{
    if(plist->curNum == plist->MAXNUM) //若表满，则无法插入
    {
       printf("list if full !");
       return 0;
    }
    plist->element[plist->curNum] = x ;
    plist->curNum++;
    return 1;

}


int destroyList_seq(PseqList plist)
{
    //返回值为销毁的线性表中现有数据元素的个数，若待销毁的线性表不存在，则返回0
    if(plist == NULL) return 0;
    int m = plist->curNum;
    free(plist->element);
    free(plist);
    return m;
    
}

void printList_seq(PseqList plist)
{//逐个输出线性表的元素，相邻的两个数据元素之间以一个空格为分隔符隔开
   for(int i=0;icurNum;i++)
        printf("%d ",plist->element[i]);
}

//第一关:求顺序线性表中连续子表（最少有一个元素）的最大和并输出
int seqMaxSum(PseqList plist)
{
        int sum,maxsum,i;
    sum=maxsum=0;
    for(i=0;icurNum;i++)
    {
    	sum=sum+plist->element[i];
    	if(sum>maxsum)
    	{
    		maxsum=sum;
		}
		else if(sum<0)
		{
			sum=0;
		}
	}
	return maxsum;
}

//第二关：寻找线性表中没有出现的最小的正整数
int findMinNumber(PseqList plist)
{
    //若线性表为空，则返回0
    int a1=0,a2=plist->curNum;
    int temp;
    while(a1
    	if(plist->element[a1]==a1+1)//规定a[0]=1,a[1]=2,a[i]=i+1
    	{
    		a1++;
            }
		else if(plist->element[a1]>a2||plist->element[a1]<=1||plist->element[plist->element[a1]-1]==plist->element[a1])
		{//不在1到i+1范围就交换a[a[i]-1]=a[i]
			plist->element[a1]=plist->element[a2--];
		}
		else
		{
			temp=plist->element[a1];
			plist->element[a1]=plist->element[plist->element[a1]-1];
			plist->element[temp-1]=temp;
		}
     	}
     	return a1+1;
}

//第三关：找出给定目标值target在有序线性表中出现的起始位置和结束位置
void findPos(PseqList plist,int target, int *pos)
{
//起始位置放在pos[0], 结束位置放在pos[1]
    int a1=0,a2=plist->curNum-1;
	pos[0]=-1;
    pos[1]=-1;
    while(a1<=a2)
    {
    	if(plist->element[a1]!=target)
    	{
    		a1++;
		}
		else
		{
			pos[0]=a1;
		}
		if(plist->element[a2]!=target)
		{
			a2--;
		}
		else
		{
			pos[1]=a2;
		}
		if(pos[0]!=-1&&pos[1]!=-1)
		{
			break;
		}
	}
	return pos;
}

链式栈

第1关一元多项式相加

#ifndef _LAB1_H_
#define  _LAB1_H_
#include 
#include  



//存放多项式某项的结点结构 
struct node
{
  int exp ;  // 表示指数
  int coef ; //表示系数
  struct node *next;  //指向下一个结点的指针
};

typedef  struct node * PNODE ;


PNODE createPoly(void)
{
    //在此处填写代码，能实现创建一个多项式并返回多项式头指针的函数
	//注意：头指针不存放多项式的项。
    
 	PNODE L,temp,ltemp;
 	L=(PNODE)malloc(sizeof(struct node));
 	L->coef=-1;
 	L->exp=-1;
 	L->next=NULL;

 	ltemp=L;
 	do
 	{
 	    temp=(PNODE)malloc(sizeof(struct node));
 	    scanf("%d %d ",&temp->coef,&temp->exp);
 	    temp->next=NULL;
 	    ltemp->next=temp;
 	    ltemp=temp;
 	}
 	while(temp->coef!=0||temp->exp!=0);
    return L;
    
}


PNODE addPoly(PNODE polyAddLeft , PNODE polyAddRight)
{
    //在此处填写代码，能实现创两个多项式相加并返回结果多项式头指针的函数
    
    PNODE temp_A,temp_B,temp,L,polyAddResult;
    temp_A=polyAddLeft->next;
    temp_B=polyAddRight->next;
    while(temp_B->coef!=0||temp_B->exp!=0)
    {
        for(temp=temp_A;;temp=temp->next)
        {
            if(temp->exp==temp_B->exp)
            {
                temp->coef+=temp_B->coef;
                break;
            }
            else if(temp->next->coef==0&&temp->next->exp==0)
            {
                L=(PNODE)malloc(sizeof(struct node));
                L->coef=temp_B->coef;
                L->exp=temp_B->exp;

                L->next=temp->next;
                temp->next=L;
                break;
            }
            else if(temp->next->exp>temp_B->exp)
            {
                L=(PNODE)malloc(sizeof(struct node));
                L->coef=temp_B->coef;
                L->exp=temp_B->exp;
                if(temp->exp>temp_B->exp)
                {
                    L->next=polyAddLeft->next;
                    polyAddLeft->next=L;
                    break;
                }
                L->next=temp->next;
                temp->next=L;
                break;
            }
        }
         temp_B=temp_B->next;
    }
    return polyAddLeft;
    
}


 void printPoly(PNODE poly)
 {
 	//在此处填写代码，能实现按格式输出多项式的功能，输出格式样例见说明
    
    PNODE L;
    int t=0;
    for(L=poly->next;L->coef!=0||L->exp!=0;L=L->next)
    {
        if(t==0)
        {
            printf("%dx^%d",L->coef,L->exp);
            t=1;
        }
        else
        {
            if(L->coef>=0)
            {
                if(L->coef>0)
                    printf("+%dx^%d",L->coef,L->exp);

            }
            else
                printf("%dx^%d",L->coef,L->exp);
        }

    }
    
}
int k=0;
void destroyPoly(PNODE poly)
{
//释放存储多项式的链表空间
    PNODE temp,ltemp;
    ltemp=poly;
    temp=ltemp->next;
    if(k==0)
    {
        k++;
        return ;
    }
    while(temp!=NULL)
    {
        free(ltemp);
        ltemp=temp;
        temp=ltemp->next;
    }

}
#endif

第2关利用单链表实现集合基本运算

#ifndef _LINKSET_H_
#define _LINKSET_H_
#include 
#include 

typedef int DataType;

struct  node
{
    DataType  element;
    struct node  *next;
};
typedef struct node * SET;
void insert(DataType datax, SET set);


SET InitSet(int num)
{

    SET p;
    p = ( struct  node *)malloc(sizeof(struct node)) ;
    p->next = NULL;
    p->element = num;
    int temp;
    for(int i =0;i
        scanf("%d",&temp);
        insert(temp, p); //调用insert函数，将输入数据插入集合
    }
    return p;
}



int find(DataType datax, SET  set)
{
    //请在此处填写代码，在set集合中查找值为datax的成员，若找到返回1，否则返回0
    
    SET temp;
    for(temp=set->next;temp!=NULL;temp=temp->next)
    {
        if(temp->element==datax)
            return 1;
    }
    return 0;

    
}


void insert(DataType datax, SET set)
{
    //请在此处填写代码，将datax插入集合set， 注意因集合元素是无序的，只需将新成员插入表头
    
    SET temp;
    temp=(SET)malloc(sizeof(struct node));
    temp->element=datax;
    temp->next=set->next;
    set->next=temp;
    set->element++;
    
 }


void copySet(SET setA, SET setB)
{
    //请在此处填写代码，实现将集合setA的成员复制到集合setB的功能
    
    SET temp_A;
    for(temp_A=setA->next;temp_A!=NULL;temp_A=temp_A->next)
    {
            insert(temp_A->element,setB);
    }

    
}


void printSet(SET set)
{
    //请在此处填写代码，实现输出集合元素的功能，元素之间以空格为分界符
    
    SET temp;
    for(temp=set->next;temp!=NULL;temp=temp->next)
        printf("%d ",temp->element);

    
}


SET setUnion(SET setA ,SET setB)
{
    //请在此处填写代码，可直接使用上面已经实现的各操作
    
    SET temp,set;
    set=(SET)malloc(sizeof(struct node));
    set->element=0;
    set->next=NULL;
    copySet(setA,set);
    for(temp=setB->next;temp!=NULL;temp=temp->next)
    {
        if(find(temp->element,set)==0)
            insert(temp->element,set);
    }
    return set;
    
}


SET setIntersect(SET setA ,SET setB)
{
    //请在此处填写代码，可直接使用上面已经实现的各操作
    
    SET temp_A,temp_B,set,temp;

    set=(SET)malloc(sizeof(struct node));
    set->element=0;
    set->next=NULL;

    for(temp_B=setB->next;temp_B!=NULL;temp_B=temp_B->next)
    {
        if(find(temp_B->element,setA)==1)
        {
            for(temp_A=setA->next;temp_A->element!=temp_B->element;temp_A=temp_A->next)
            {}
            insert(temp_A->element,set);
        }
    }
    return set;

    
}


SET setExcept(SET setA ,SET setB)
{
    //请在此处填写代码，可直接使用上面已经实现的各操作
    
    SET temp_A,temp_B,set,temp;

    set=(SET)malloc(sizeof(struct node));
    set->element=0;
    set->next=NULL;

    for(temp_A=setA->next;temp_A!=NULL;temp_A=temp_A->next)
    {
        if(find(temp_A->element,setB)==0)
        {
            insert(temp_A->element,set);
        }
    }
    return set;

    
}

void destroySet(SET set)
{
//释放存储集合的链表空间，表头为set
    SET temp,ltemp;
    ltemp=set;
    temp=set->next;
    while(temp!=NULL)
    {
        free(ltemp);
        ltemp=temp;
        temp=ltemp->next;
    }
}
#endif

第3关大数相加

#include 
#include 
struct node
{//链表结点类型，包含一个存放整型数据的 data 成员，和一个指向下一个结点的next成员
    int data ;
    struct node *next ;   
};

struct node *mycreateList()
{//函数功能：创建一个只有一个头结点的空链表，头节点的数据域赋值为0，并将表头结点的地址返回
  struct node *head = (struct node *)malloc(sizeof(struct node));
  head->data = 0;
  head->next = NULL;
  return head;
}


void myinsertHead(struct node * head, int insData )
{
	
   struct node *p ;
   p = (struct node *)malloc(sizeof(struct node));
   p->data = insData;
   p->next = head->next ;
   head->next = p ;
}

void myinsertTail(struct node *  head , int insData )
{
	
   struct node *p ,*q ;
   p = (struct node *)malloc(sizeof(struct node));
   p->data = insData;
   p->next = NULL;
   q = head ;
   while(q->next!=NULL) 
     q = q->next;
   q->next = p ;
}

void myprintList(struct node *L)
{
     
	struct node *p = L->next ;
	while(p)
	 {
	  printf("%d ",p->data);
	  p = p->next ;
      }
}
void genNumber( struct node *A , int num)
{//本函数用于接收输入的大数的各个位，返回大数链表表头，可使用上面已实现的链表插入函数

    int i,n;
    for(i=0;i
        scanf("%d",&n);
        myinsertHead(A,n);
    }


}

struct node *addNumber(struct node *A ,struct node *B)
{
    //此处实现函数求两数相加，并返回和值链表的表头；
    
    int num=0,lnum=0;
    struct node *temp_A,*temp_B,*C;
    for(temp_A=A->next,temp_B=B->next;temp_A!=NULL&&temp_B!=NULL;temp_A=temp_A->next,temp_B=temp_B->next)
    {
        num=(temp_A->data+temp_B->data+lnum)/10;
        temp_A->data=(temp_A->data+temp_B->data+lnum)%10;
        lnum=num;

    }
    temp_A->data+=lnum;

    C=mycreateList();
    temp_A=A->next;
    while(temp_A!=NULL)
    {
        myinsertHead(C,temp_A->data);
        temp_A=temp_A->next;
    }
    return C;

  
}

栈——实验及提升训练

栈与递归函数

中缀表达式转换为后缀表达式

#include 
#include 
#include
// 自己定义需要的栈结构，及栈基本操作函数，假设操作数都是整数
struct stack
{
    int a_x;//a的系数
    int x_x;//x的系数
};

int result(int n,int m,int a,int x)//分别表示n站，最后一站下车的人数m，始发站上车人数a，求第x站时车上的人数
{
    struct stack up[20],dowm[20],sum[20];
    up[1].a_x=1;up[1].x_x=0;//定义从1开始
    up[2].a_x=0;up[2].x_x=1;

    dowm[1].a_x=0;dowm[1].x_x=0;
    dowm[2].a_x=0;dowm[2].x_x=1;

    sum[1].a_x=1;sum[1].x_x=0;
    sum[2].a_x=1;sum[2].x_x=0;
    
    int i;
    for(i=3;i
        up[i].a_x=up[i-1].a_x+up[i-2].a_x;
        up[i].x_x=up[i-1].x_x+up[i-2].x_x;

        dowm[i].a_x=up[i-1].a_x;
        dowm[i].x_x=up[i-1].x_x;

        sum[i].a_x=sum[i-1].a_x+up[i].a_x-dowm[i].a_x;
        sum[i].x_x=sum[i-1].x_x+up[i].x_x-dowm[i].x_x;
    }
    int temp,num;
    //最后一个车站下车人数m等于第n-1个车站出发的人数。
    temp=(m-sum[n-1].a_x*a)/sum[n-1].x_x;//得到在第二站上车的人数
    if(x==n)
    {
        num=sum[x-1].a_x*a+sum[x-1].x_x*temp;
    }
    else
    {
        num=sum[x].a_x*a+sum[x].x_x*temp;
    }
    return num;
}
//第二关
  
typedef char DataType;
struct node 
{
    DataType  info;
    struct node  *link;
};
typedef struct node *PNode;

struct LinkStack {
    PNode  top;
};
typedef struct LinkStack *Stack;

Stack createNullStack_link()  //创建一个空的链栈
{   
    Stack plinkstack = (Stack)malloc(sizeof(struct LinkStack));
    plinkstack->top = NULL;
    return plinkstack;
}

int push_link(Stack L ,DataType x)  //在栈中插入数据元素x，若插入不成功，返回0；插入成功返回值为1
{
    PNode q = (PNode)malloc(sizeof(struct node));
    if(q == NULL) return 0;

    q->info = x;
    q->link = L->top;
    L->top = q;
    return 1;
}

DataType pop_link(Stack L)  //弹栈并返回删除元素，若栈为空，则返回-1
{
    PNode p;
    DataType temp = L->top->info;
    p = L->top;
    L->top = L->top->link;
    free(p);
    return temp;
}

Stack  inToPost(char *expression)
{
    //在此处填写代码，完成中缀表达式转换为后缀表达式并输出
    
    Stack L = createNullStack_link();
    int len = strlen(expression);

    push_link(L, '#');
    for(int i = 0; i < len; i++)
    {
        if(expression[i] >= '0' && expression[i] <= '9')
        {
            printf("%d",expression[i] - '0');
        }
        else
        {
            printf(" ");
            if(expression[i] == '+' || expression[i] == '-')
            {
                if(L->top->info == '*' ||L->top->info == '/')
                {
                    print(L);
                    push_link(L, expression[i]);
                }
                else
                {
                    if(L->top->info != '#')
                    {
                        printf("%c ", pop_link(L));
                        push_link(L, expression[i]);
                    }
                    else push_link(L, expression[i]);
                }
            }
            else
            {
                if(L->top->info == '*')
                {
                    printf("%c ", pop_link(L));
                    push_link(L, expression[i]);
                }
                else push_link(L, expression[i]);
            }
        }
    }
    printf(" ");
    return L;
    
}

//print函数用于输出后缀表达式，参数是 inToPost的返回值
void print(Stack s)
{
    while(s->top->info != '#')
    {
        printf("%c ", pop_link(s));
    }
}

数据结构与算法（ｅｄｕｃｏｄｅｒ作业）

C/C++/C#相关栏目本月热门文章