数据结构_C语言(三)

代码

My MiniPage[1]

本页面由王旭升（wpaladins）编写，转载请注明出处即可，无需申请！

目录

A

#include<stdio.h>                      //A
#include<string.h>
struct xg
{
    int xi;
    int ui;
}a[10000],b[10000];
int main()
{
    int i,j,n=0,m=0;
    int sum[10000];
    memset(sum,0,sizeof(sum));
    while(1)
    {
        scanf("%d%d",&a[n].xi,&a[n].ui);
        if(a[n++].ui==-1)
        break;
    }
    while(1)
    {
        scanf("%d%d",&b[m].xi,&b[m].ui);
        if(b[m++].ui==-1)
        break;
    }
    for(i=0;i<n-1;i++)
    {
        for(j=0;j<m-1;j++)
        {
            sum[a[i].ui+b[j].ui]+=a[i].xi*b[j].xi;
        }
    }
    int flag=0;
    for(i=9999;i>=0;i--)
    {
        if(sum[i])
        {
            printf("%d %d ",sum[i],i);
            flag=1;
        }
    }
    if(flag==0)
    printf("0\n");
    return 0;
}

B

代码2运用数学归纳法，由五班大神施维提供：

#include<stdio.h>                              //B
#include<string.h>
int main()
{
    int m,n,t,M;
    int a[10001];
    while(~scanf("%d%d",&m,&n)&&m&&n)
    {
        memset(a,0,sizeof(a));
        M=m-1;
        int i=1;
        while(M--)
        {
            t=0;
            for(;;i++)
            {
                if(!a[i])
                {
                    t++;
                }
                if(t==n)
                {
                    a[i]=1;
                    break;
                }
                if(i==m)
                {
                    i=0;
                }
            }
        }
        for( i=1;i<=m;i++)
        {
            if(a[i]==0)
            {
                printf("%d\n",i);
                break;
            }
        }
    }
    return 0;
}

代码2

#include<stdio.h>
int main ()
{
    int s,n,i,m;
    while((scanf("%d%d",&n,&m))&&n&&m)
    {
        s=0;
        for(i=2;i<=n;i++)
        {
            s=(s+m)%i;
        }
        printf("%d\n",s+1);
    }
    return 0;
}

C

#include<stdio.h>
#include<string.h>
struct xg
{
    int xi;
    int ui;
}a[10000],b[10000];
int main()
{
    int i,j,n=0,m=0;
    int sum[10000];
    memset(sum,0,sizeof(sum));
    while(1)
    {
        scanf("%d%d",&a[n].xi,&a[n].ui);
        if(a[n++].ui==-1)
        break;
    }
    while(1)
    {
        scanf("%d%d",&b[m].xi,&b[m].ui);
        if(b[m++].ui==-1)
        break;
    }
    for(i=0;i<n-1;i++)
    {
        sum[a[i].ui]+=a[i].xi;
    }
    for(j=0;j<m-1;j++)
    {
        sum[b[j].ui]+=b[j].xi;
    }
    int flag=0;
    for(i=9999;i>=0;i--)
    {
        if(sum[i])
        {
            printf("%d %d ",sum[i],i);
            flag=1;
        }
    }
    if(flag==0)
    printf("0\n");
    return 0;
}

D

有代码2版本

#include<stdio.h>                      //D
#include<string.h>
int main()
{
    int i,j,m,n;
    int a[210],b[210];              //数组，所以是线性表；
    while(~scanf("%d",&m))              //用第一个输入的数据在while中的方法达到输入多组数据的效果，注意写法；
    {
        for(i=0;i<m;i++)
        {
            scanf("%d",&a[i]);              //为数组a的每个元素赋值；
        }
        scanf("%d",&n);                         //数组b的大小
        for(i=0;i<n;i++)
        {
            scanf("%d",&b[i]);                      //为数组b的每个元素赋值；
        }
        printf("%d",a[0]);                          //从此开始的八行，按照体重要求打印一次数组a和b,但是由于空格的问题，就必须将第一个数据单独打出，剩下的数据以" %d"的形式打出；
        for(i=1;i<m;i++)
            printf(" %d",a[i]);
        printf("\n");
        printf("%d",b[0]);
        for(i=1;i<n;i++)
            printf(" %d",b[i]);
        printf("\n");
        for(i=0;i<n;i++)                                //用i来遍历b；
        {
            int t=0;
            for(j=0;j<m;j++)                            //用i来遍历a；
            {
                if(a[j]==b[i])
                {
                    t=1;
                    break;
                }
            }
            if(t==0)
            {
                a[m++]=b[i];                             //先将b[i]的值赋给a[m],然后m++；
            }
            printf("%d",a[0]);                           //从此开始的四行，是为了将数组在每次加完一个数之后输出；
            for(j=1;j<m;j++)
                printf(" %d",a[j]);
            printf("\n");
        }
        printf("\n");                                    //按照题目要求，每组数据之间换行；
    }
    return 0;
}

代码2

#include <stdio.h>
#include <stdlib.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 201
typedef int Status;
typedef int ElemType;
Status visit(ElemType c)
{
    printf(" %d",c);
    return OK;
}
typedef struct
{
    ElemType data[MAXSIZE];
    int length;
}SqList;
Status InitList(SqList *L)
{
    L->length=0;
    return OK;
}Status ListEmpty(SqList L)
{
    if(L.length==0)
        return TRUE;
    else
        return FALSE;
}
Status ClearList(SqList *L)
{
    L->length=0;
    return OK;
}
int ListLength(SqList L)
{
    return L.length;
}
Status GetElem(SqList L,int i,ElemType *e)
{
    if(L.length==0 || i<1 || i>L.length)
            return ERROR;
    *e=L.data[i-1];
    return OK;
}
int LocateElem(SqList L,ElemType e)
{
    int i;
    if (L.length==0)
            return 0;
    for(i=0;i<L.length;i++)
    {
            if (L.data[i]==e)
                    break;
    }
    if(i>=L.length)
            return 0;
    return i+1;
}
Status ListInsert(SqList *L,int i,ElemType e)
{
    int k;
    if (L->length==MAXSIZE)
        return ERROR;
    if (i<1 || i>L->length+1)
        return ERROR;
    if (i<=L->length)
    {
        for(k=L->length-1;k>=i-1;k--)
            L->data[k+1]=L->data[k];
    }
    L->data[i-1]=e;
    L->length++;
    return OK;
}
Status ListDelete(SqList *L,int i,ElemType *e)
{
    int k;
    if (L->length==0)
        return ERROR;
    if (i<1 || i>L->length)
        return ERROR;
    *e=L->data[i-1];
    if (i<L->length)
    {
        for(k=i;k<L->length;k++)
            L->data[k-1]=L->data[k];
    }
    L->length--;
    return OK;
}
void ListTraverse(SqList L)
{
    int i;
    printf("%d", L.data[0]);
    for(i=1;i<L.length;i++)
            visit(L.data[i]);
    printf("\n");
}
void unionL(SqList *La,ElemType c)
{
    int La_len,i;
    La_len=ListLength(*La);
    if (!LocateElem(*La,c))
            ListInsert(La,++La_len,c);
}
int  main()
{
  SqList La, Lb;
  InitList(&La);
  InitList(&Lb);
  int m, n, i, num, Lb_len;
  while(scanf("%d", &m) != EOF){
  for(i = 0;i < m; i++){
    scanf("%d", &num);
    ListInsert(&La, i+1, num);
  }
    scanf("%d", &n);
  for
  (i = 0;i < n; i++){
    scanf("%d", &num);
    ListInsert(&Lb, i+1, num);
  }
    Lb_len=ListLength(Lb);
    ListTraverse(La);
    ListTraverse(Lb);
    ElemType e;
    for(i = 1; i <= Lb_len; i++){
      GetElem(Lb,i,&e);
      unionL(&La, e);
      ListTraverse (La);
    }
  printf("\n");
    ClearList(&La);
    ClearList(&Lb);
  }
}

E

#include<stdio.h>                                      //E
#include<string.h>
int main()
{
    int i,n,m;
    int a[101],b[101],z[202];
    int p=0,q=0;
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    scanf("%d",&m);
    for(i=0;i<m;i++)
    {
        scanf("%d",&b[i]);
    }
    if(a[0]>b[0])
    {
        z[0]=b[0];
        q=1;
    }
    else
    {
        z[0]=a[0];
        p=1;
    }
    printf("%d ",z[0]);
    for(i=1;i<m+n;i++)
    {
        if(p==n&&q==m)
            break;
        if(a[p]<b[q])
        {
            if(p<n)
                z[i]=a[p++];
            else
                z[i]=b[q++];
        }
        else
        {
            if(q<m)
                z[i]=b[q++];
            else
                z[i]=a[p++];
        }
        printf("%d",z[i]);
        if(i!=m+n-1)
        printf(" ");
    }
    return 0;
}

F

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define LIST_INIT_SIZE 100         // 线性表存储空间的初始分配量
#define LISTINCREMENT 10        // 线性表存储空间的分配增量
typedef int Status;                        // 定义返回值状态类型
#define OK 1
#define ERROR 0
typedef struct{                // 定义数据类型，存放的是一个名字，所以只有字符数组
        char name[100];
}ElemType;
typedef struct{
        ElemType * elem;        // 存储空间基址
        int length;                        // 当前长度
        int listsize;                // 当前分配的存储容量（以sizeof(ElemType)为单位）
}SqList;
Status InitList_Sq(SqList *L) { // 算法2.3
        // 构造一个空的线性表L。
        L->elem = (ElemType *) malloc(LIST_INIT_SIZE*sizeof(ElemType));
        if (!L->elem)
                return OK; // 存储分配失败
        L->length = 0; // 空表长度为0
        L->listsize = LIST_INIT_SIZE; // 初始存储容量
        return OK;
} // InitList_Sq
Status ListInsert_Sq(SqList *L, int i, ElemType e) { // 算法2.4
        // 在顺序线性表L的第i个元素之前插入新的元素e，
        // i的合法值为1≤i≤ListLength_Sq(L)+1
        ElemType *p;
        if (i < 1 || i > L->length + 1)
                return ERROR; // i值不合法
        if (L->length >= L->listsize) { // 当前存储空间已满，增加容量
                ElemType *newbase = (ElemType *) realloc(L->elem, (L->listsize
                                + LISTINCREMENT) * sizeof(ElemType));
                if (!newbase)
                        return ERROR; // 存储分配失败
                L->elem = newbase; // 新基址
                L->listsize += LISTINCREMENT; // 增加存储容量
        }
        ElemType *q = &(L->elem[i - 1]); // q为插入位置
        for (p = &(L->elem[L->length - 1]); p >= q; --p)
                *(p + 1) = *p;
        // 插入位置及之后的元素右移
        *q = e; // 插入e
        ++L->length; // 表长增1
        return OK;
} // ListInsert_Sq
Status ListDelete_Sq(SqList *L, int i, ElemType *e) { // 算法2.5
        // 在顺序线性表L中删除第i个元素，并用e返回其值。
        // i的合法值为1≤i≤ListLength_Sq(L)。
        ElemType *p, *q;
        if (i < 1 || i > L->length)
                return ERROR; // i值不合法
        p = &(L->elem[i - 1]); // p为被删除元素的位置
        *e = *p; // 被删除元素的值赋给e
        q = L->elem + L->length - 1; // 表尾元素的位置
        for (++p; p <= q; ++p)
                *(p - 1) = *p; // 被删除元素之后的元素左移
        --L->length; // 表长减1
        return OK;
} // ListDelete_Sq
int LocateElem_Sq(SqList L, ElemType e, Status(*compare)(ElemType, ElemType)) { // 算法2.6
        // 在顺序线性表L中查找第1个值与e满足compare()的元素的位序。
        // 若找到，则返回其在L中的位序，否则返回0。
        int i;
        ElemType *p;
        i = 1; // i的初值为第1个元素的位序
        p = L.elem; // p的初值为第1个元素的存储位置
        while (i <= L.length && !(*compare)(*p++, e))
                ++i;
        if (i <= L.length)
                return i;
        else
                return 0;
} // LocateElem_Sq
void ListShow(SqList L){
        // 将顺序表中的所有元素都显示出来，每个姓名之间用空格分开
        int i;
        for(i=0;i<L.length;i++){
                if(i){                // 用来判断是否需要输出空格
                        putchar(' ');
                }
                printf("%s", L.elem[i].name);        // 输出姓名
        }
        putchar('\n');        // 注意最后需要换行
}
Status cmp(ElemType e1, ElemType e2){
        // 用来比较两个ElemType元素是否相等
        return (Status)!strcmp(e1.name, e2.name);
}
int main(){
        SqList namelist;                // 定义姓名列表
        InitList_Sq(&namelist);        // 初始化姓名列表
        char strInstruct[10];        // 用来保存每行开头的指令
        int pos;                                // 用来保存插入或者搜索的位置
        ElemType e;                                // 用来保存姓名的节点
        while(scanf("%s", strInstruct) != EOF){
                if(strcmp(strInstruct, "insert") == 0){        // 插入姓名
                        scanf("%d%s" ,&pos, e.name);                // 读取待插入的位置与姓名
                        ListInsert_Sq(&namelist, pos, e);        // 将姓名插入到pos之前
                }else if(strcmp(strInstruct, "show") == 0){        // 显示列表中所有的元素
                        ListShow(namelist);
                }else if(strcmp(strInstruct, "delete") == 0){        // 删除某个姓名
                        scanf("%s", e.name);                // 读取需要删除的元素
                        // 先查找这个姓名在列表中的位置
                        // 然后调用 ListDelete_Sq 删除该元素
                        pos = LocateElem_Sq(namelist, e, cmp);
                        ListDelete_Sq(&namelist, pos, &e);
                }else if(strcmp(strInstruct, "search") == 0){        // 查找某个姓名的位置
                        scanf("%s", e.name);                // 读取需要查找的元素
                        printf("%d\n", LocateElem_Sq(namelist, e, cmp));
                }
        }
        return 0;
}

G

H

#include<stdio.h>                                       //H
#include<string.h>
int nex[11]={2,0,3,4,5,6,7,8,9,10,0};
char mem[11][10];
int mal()
{
    int i=nex[0];
    if(nex[0])
    {
        nex[0]=nex[nex[0]];
    }
    return i;
}
int len(char s[])
{
    int i=0;
    while(s[i++]);
    return i;
}
void search(char s[])
{
    int i=nex[1];
    while(i&&strcmp(s,mem[i]))
        i=nex[i];
    printf("%2d\n********************\n",i);
    return ;
}
void show()
{
    int i,le;
    for(i=0;i<11;i++)
    {
        le=len(mem[i]);
        printf("%-8s%2d\n",mem[i],nex[i]);
    }
    printf("********************\n");
    return;
}
void insert(int w,char s[])
{
    int p1=1,p2=nex[1];
    int r=mal();
    strcpy(mem[r],s);
    int t=1;
    while(t!=w)
    {
        p1=p2;
        p2=nex[p2];
        t++;
    }
    nex[r]=p2;
    nex[p1]=r;
    return;
}
void del(int w)
{
    int p1=1,p2=nex[1];
    int t=1;
    while(t!=w)
    {
        p1=p2;
        p2=nex[p2];
        t++;
    }
    nex[p1]=nex[p2];
    nex[p2]=nex[0];
    nex[0]=p2;
}
int main()
{
    char zo[10];
    int W;
    while(~scanf("%s",zo))
    {
        switch(zo[2])
        {
            case 'o':{
                show();
                break;
            }
            case 's':{
                scanf("%d%s",&W,zo);
                insert(W,zo);
                break;
            }
            case 'l':{
                scanf("%d",&W);
                del(W);
                break;
            }
            case 'a':{
                scanf("%s",zo);
                search(zo);
                break;
            }
        }
    }
    return 0;
}

I

#include<stdio.h>                          //I
#include<malloc.h>
struct nood                                     //双向链表；
{
    int val;
    struct nood *next;
    struct nood *front;
}head,rear;
int main()
{
    int i,n,t;
    while(~scanf("%d",&n))
    {
        head.next=&rear;
        rear.front=&head;
        struct nood *p=&head;
        int b=0;
        for(i=0;i<n;i++)                                //插入操作
        {
            b=1;
            scanf("%d",&t);
            struct nood *r=(struct nood*)malloc(sizeof(struct nood));
            r->val=t;
            r->next=p->next;
            r->front=p;
            p->next->front=r;
            p->next=r;
            p=r;
            printf("%d ",t);
        }
        if(b==1)
            printf("\n");
        if(n==0)
        {
            printf("list is empty\n");
            continue;
        }
        p=rear.front;
        b=0;
        while(p!=&head)
        {
            printf("%d ",p->val);
            p=p->front;
        }
        printf("\n");
    }
    return 0;
}

J

#include<stdio.h> //J
#include<malloc.h>
struct nood
{
    int val;
    struct nood *next;
}head,rear;                         //定义了头结点和尾结点，全局变量；
int main()
{
    int i,n,t;
    int q=0;                                    //q的作用主要是在每次打完原始数据后换行；
    while(~scanf("%d",&n))                              //数据为多组，使用这个方式输入，需要按ctrl+z才能退出程序；
    {
        if(!q)
            q=1;
        head.next=&rear;                                        //头结点的指针指向首个结点；
        struct nood *p=&head;                                   //定义了一个结构体指针p(辅助的结点)并且将它跟头结点一样指向首个结点，用以遍历和插入；
        int b=0;                                                        //相当于flag，不参与运算，仅仅标志着一个变化；
        for(i=0;i<n;i++)
        {
            scanf("%d",&t);                                             //读取即将存到现在结点的数据；
            struct nood *r=(struct nood*)malloc(sizeof(struct nood));                 //申请一个新的空间，为要插入的结点；
            r->val=t;                                                   //将新的结点的val存上值；
            r->next=p->next;                                            //第一次p为头结点，将为结点r的前一个结点，后来也将为结点r的前一个结点，p->next为&rear，此处的意思是在head 和rear之间插入元素；
            p->next=r;                                                  //让辅助结点p指向要插入的结点，为下一次结点p作为插入结点的前一个结点--做准备；
            p=r;                                                        //p地址应该是插入结点的前一个结点的地址，将地址r给地址p，为下一次插入--做准备；
            printf("%d ",t);                                            //输出原始数据；
        }
        if(n==0)                                                        //判断链表为空的情况；
        {
            printf("list is empty\n");
            continue;
        }
        if(q)                                                           //在原始数据之后打上换行，放在这里时因为链表为空时不需要打换行；
            printf("\n");
        p=head.next;                                                    //p的重新利用，指向首个结点；
        while(p->next!=&rear)                                           //对数据进行操作的循环，判断链表的遍历是否结束，由于此处p-val要与p->next->val比较，所以就判断下一个是不是为尾结点；
        {
            while(p->val==p->next->val)
                p->next=p->next->next;
            if(p->next!=&rear)
                p=p->next;
        }
        p=head.next;
        b=0;
        while(p!=&rear)                                                 //打出新数据的循环，判断链表的遍历是否结束，尾结点不进入循环；
        {
            printf("%d ",p->val);
            p=p->next;
        }
        printf("\n");
    }
    return 0;
}