首页 > 其他分享 >数据结构-线性表

数据结构-线性表

时间：2022-10-07 17:56:36浏览次数：45  
标签：p2 p3 p1 线性表 NULL next LinkList 数据结构

​@

目录
最近懒，栈和队列找机会发。

XDOJ0258-链表去重

//xdoj0258.c
#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 100000 //address是非负5位整数
​
typedef struct LNode{
    int data;
    int next;
}LNode;
​
LNode Nodes[MAXSIZE];//结点数组，下标为address
​
void Display(LNode Nodes[],int p){
    while(p!=-1){
        if(Nodes[p].next==-1){
            printf("%05d %d -1",p,Nodes[p].data);
        }else{
            printf("%05d %d %05d\n",p,Nodes[p].data,Nodes[p].next);
        }
        p=Nodes[p].next;
    }
}
​
void DeleteNode(LNode Nodes[],int p,int address){
    //传入表和需要删除的结点地址
    while(Nodes[p].next != address){
        p=Nodes[p].next;
    }
    Nodes[p].next=Nodes[address].next;
}
​
int main(){
    int n,p,index;
    scanf("%d%d",&p,&n);
​
    for(int i=0;i<n;i++){
        scanf("%d",&index);//两个scanf必须分开，否则数组赋值会出错
        scanf("%d%d",&Nodes[index].data,&Nodes[index].next);
    }
​
    for(int i=p;i!=-1;i=Nodes[i].next){
        for(int j=Nodes[i].next;j!=-1;j=Nodes[j].next){
            if(Nodes[i].data == Nodes[j].data || Nodes[i].data == -Nodes[j].data){
                //abs相同，删除后一个结点
                DeleteNode(Nodes,p,j);
                n--;
            }
        }
    }
    printf("%d\n",n);
    Display(Nodes,p);
    return 0;
}

​

XDOJ0263-递增链表的插入

//xdoj0263.c
​
#include<stdio.h>
#include<stdlib.h>
#define ElemType int
​
typedef struct LNode{
    ElemType data;
    struct LNode* next;
}LNode, *LinkList;
​
//创建头结点
LinkList LinkListInit(){
​
    LinkList L=(LinkList)malloc(sizeof(LNode));
    L->next=NULL;
    return L;
}
​
void CreateLinkList(LinkList L,LinkList p,ElemType e){
    LinkList s=(LinkList)malloc(sizeof(LNode));
​
    s->data=e;
​
    p->next=s;
    s->next=NULL;
}
​
void InsertLinkList(LinkList L,ElemType e){
    LinkList p=L;
​
    //将p移动到插入的空隙 前一个结点
    while(p->next!=NULL && p->next->data < e){
        p=p->next;
    }
​
    //开始插入
    LinkList s=(LinkList)malloc(sizeof(LNode));
    s->data=e;
    s->next=p->next;
    p->next=s;
}
​
void DisplayLinkList(LinkList L){
    LinkList p=L->next;
    while(p->next!=NULL){
        printf("%d ",p->data);
        p=p->next;
    }
    printf("%d",p->data);
}
​
int main(){
    int n;
    ElemType e,tmp;
    LinkList L=LinkListInit();
    LinkList pos=L;//动态指针，指向L表最后一个结点，方便创建L
​
    scanf("%d %d",&n,&e);
    for(int i=0;i<n;i++){
        scanf("%d",&tmp);
        CreateLinkList(L,pos,tmp);
        pos=pos->next;
    }
    // DisplayLinkList(L);
    // printf("\n");
    //开始插入e
    InsertLinkList(L,e);
    DisplayLinkList(L);
    return 0;
}

​

XDOJ0264-反转链表

//xdoj0264.c
#include<stdio.h>
#include<stdlib.h>
#define ElemType int
​
typedef struct LNode{
    ElemType data;
    struct LNode* next;
}LNode, *LinkList;
​
LinkList InitLinkList(){
    LinkList L=(LinkList)malloc(sizeof(LNode));
    L->next=NULL;
    return L;
}
​
void DisplayLinkList(LinkList L){
    LinkList p=L->next;
    while(p->next!=NULL){
        printf("%d ",p->data);
        p=p->next;
    }
    printf("%d",p->data);
}
​
int main(){
    LinkList Ls[100];// 足够大的指针数组
    int n,length,tmp;
​
    scanf("%d",&n);
​
    //直接构造反转链表
    for(int i=0;i<n;i++){
        Ls[i]=InitLinkList();
        scanf("%d",&length);
        for(int j=0;j<length;j++){
            scanf("%d",&tmp);
            LinkList p=Ls[i];//p始终指向头结点
            LinkList s=(LinkList)malloc(sizeof(LNode));
            s->data=tmp;
​
            s->next=p->next;
            p->next=s;
        }
    }
    //输出
    for(int i=0;i<n-1;i++){
        DisplayLinkList(Ls[i]);
        printf("\n");
    }
    DisplayLinkList(Ls[n-1]);
​
    return 0;
}

XDOJ0276-多项式加减法

//xdoj0276.c
#include<stdio.h>
#include<stdlib.h>
​
typedef struct LNode{
    int p;//系数
    int e;//指数
    struct LNode* next;
}LNode,*LinkList;
​
LinkList InitLinkList(){
    LinkList L=(LinkList)malloc(sizeof(LNode));
    L->next=NULL;
    return L;
}
​
//多项式相加
LinkList PolyAdd(LinkList L1,LinkList L2){
    LinkList p1=L1->next;
    LinkList p2=L2->next;
    LinkList result=(LinkList)malloc(sizeof(LNode));//作为结果返回
    result->next=NULL;
    result->e=0;//头结点存多项式的项数，便于输出 result->e表示结果的项数
    LinkList p3=result;
    //指数一样，则系数相加，若系数之和为0，则free
    //指数不一样，指数大的先插入进去,每执行一次插入，记录一次
    while(p1!=NULL && p2!=NULL){//注意这里最后要检验 究竟是谁先到底
        if(p1->e > p2->e){
            //p1的指数比较大，插入p1结点
            LinkList s=(LinkList)malloc(sizeof(LNode));
            s->e=p1->e;
            s->p=p1->p;
            s->next=NULL;
​
            p3->next=s;
            p3=p3->next;
​
            result->e++;
​
            p1=p1->next;
​
        }else if(p1->e < p2->e){
            //p2的指数比较大，插入p2结点
            LinkList s=(LinkList)malloc(sizeof(LNode));
            s->e=p2->e;
            s->p=p2->p;
            s->next=NULL;
​
            p3->next=s;
            p3=p3->next;
​
            result->e++;
​
            p2=p2->next;
​
​
        }else{//指数相等
            if(p1->p + p2->p == 0){
                ;
            }else{
                //系数之和不为0
                LinkList s=(LinkList)malloc(sizeof(LNode));
                s->p=p1->p + p2->p;
                s->e=p1->e;
                s->next=NULL;
​
                p3->next=s;
                p3=p3->next;
​
                result->e++;
            }
            //指数相等的情况，p1 和 p2 都要移动
            p1=p1->next;
            p2=p2->next;
        }
    }
    //还没完，while条件内部 不一定遍历结束
    if(p1 == NULL && p2==NULL){
        //如果p1和p2 都空，则恰好遍历结束
        return result;
    }else{
        if(p1==NULL){
            while(p2){
                LinkList s=(LinkList)malloc(sizeof(LNode));
                s->p=p2->p;
                s->e=p2->e;
                s->next=NULL;
​
                p3->next=s;
                p3=p3->next;
​
                result->e++;
​
                p2=p2->next;
            }
        }else if(p2==NULL){
            while(p1){
                LinkList s=(LinkList)malloc(sizeof(LNode));
                s->p=p1->p;
                s->e=p1->e;
                s->next=NULL;
​
                p3->next=s;
                p3=p3->next;
​
                result->e++;
​
                p1=p1->next;
            }
        }
        return result;
    }
}
​
//多项式相减 注意插入的时候先把L2的结点系数乘-1
LinkList PolyMinus(LinkList L1,LinkList L2){
    LinkList p1=L1->next;
    LinkList p2=L2->next;
    LinkList result=(LinkList)malloc(sizeof(LNode));//作为结果返回
    result->next=NULL;
    result->e=0;//头结点存多项式的项数，便于输出 result->e表示结果的项数
    LinkList p3=result;
    //指数一样，则系数相加，若系数之差为0，则free
    //指数不一样，指数大的先插入进去,每执行一次插入，记录一次
    while(p1!=NULL && p2!=NULL){//注意这里最后要检验 究竟是谁先到底
        if(p1->e > p2->e){
            //p1的指数比较大，插入p1结点
            LinkList s=(LinkList)malloc(sizeof(LNode));
            s->e=p1->e;
            s->p=p1->p;
            s->next=NULL;
​
            p3->next=s;
            p3=p3->next;
​
            result->e++;
​
            p1=p1->next;
​
        }else if(p1->e < p2->e){
            //p2的指数比较大，插入p2结点 记得乘-1
            LinkList s=(LinkList)malloc(sizeof(LNode));
            s->e=p2->e;
            s->p=-(p2->p);
            s->next=NULL;
​
            p3->next=s;
            p3=p3->next;
​
            result->e++;
​
            p2=p2->next;
​
        }else{//指数相等
            if(p1->p - p2->p == 0){
                ;
            }else{
                //系数之差不为0
                LinkList s=(LinkList)malloc(sizeof(LNode));
                s->p=p1->p - p2->p;
                s->e=p1->e;
                s->next=NULL;
​
                p3->next=s;
                p3=p3->next;
​
                result->e++;
            }
            //指数相等的情况，p1 和 p2 都要移动
            p1=p1->next;
            p2=p2->next;
        }
    }
    //还没完，while条件内部 不一定遍历结束
    if(p1 == NULL && p2==NULL){
        //如果p1和p2 都空，则恰好遍历结束
        return result;
    }else{
        if(p1==NULL){
            while(p2){//注意p2的系数要取相反数
                LinkList s=(LinkList)malloc(sizeof(LNode));
                s->p=-(p2->p);
                s->e=p2->e;
                s->next=NULL;
​
                p3->next=s;
                p3=p3->next;
​
                result->e++;
​
                p2=p2->next;
            }
        }else if(p2==NULL){
            while(p1){
                LinkList s=(LinkList)malloc(sizeof(LNode));
                s->p=p1->p;
                s->e=p1->e;
                s->next=NULL;
​
                p3->next=s;
                p3=p3->next;
​
                result->e++;
​
                p1=p1->next;
            }
        }
        return result;
    }
}
​
void DisplayLinkList(LinkList L){
    LinkList p=L;
    printf("%d",p->e);
    p=p->next;
    if(p==NULL){//但如果多项式没有非零系数项，则仅用0（M的值）表示，后面没有系数和幂次值出现。
        //沙比oj有测试样例结果为0的
        //细节问题
        return;
    }
    printf(" ");
    while(p->next){
        printf("%d %d ",p->p,p->e);
        p=p->next;
    }
    printf("%d %d",p->p,p->e);
    return;
}
​
int main(){
    int m1,m2;
    LinkList L1=InitLinkList();
    LinkList L2=InitLinkList();
    LinkList p1=L1;
    LinkList p2=L2;
​
    //输入部分
    scanf("%d",&m1);
    for(int i=0;i<m1;++i){
        LinkList s=(LinkList)malloc(sizeof(LNode));
        scanf("%d %d",&s->p,&s->e);
        s->next=NULL;
        p1->next=s;
​
        p1=p1->next;
    }
​
    scanf("%d",&m2);
    for(int i=0;i<m2;++i){
        LinkList s=(LinkList)malloc(sizeof(LNode));
        scanf("%d %d",&s->p,&s->e);
        s->next=NULL;
        p2->next=s;
​
        p2=p2->next;
    }
​
    //开始处理
    LinkList p3=PolyAdd(L1,L2);
    printf("\n");
    DisplayLinkList(p3);
​
    printf("\n");
    LinkList p4=PolyMinus(L1,L2);
    DisplayLinkList(p4);
​
    return 0;
}

XDOJ0278-约瑟夫环

//xdoj0278.c
#include<stdio.h>
#include<stdlib.h>
typedef struct LNode{
    int num,passwopd;
    struct LNode *next;
}LNode,*Linklist;
​
Linklist L,p,s;
//创建循环链表
void Creatlinklist(int n){
    L = (Linklist)malloc(sizeof(LNode));
  p = L;
    int i;
    int x;
    for (i = 1; i < n;i++){
        s = (Linklist)malloc(sizeof(LNode));
        p->next = s;
        p = s;
    }
    p->next = L;
    s = L;
}
void Input(int n){
  int x;
  for(int i=1;i<=n;i++){
    scanf("%d",&x);
    s->passwopd = x;
    s->num = i;
    s=s->next;
  }
  s = p;
}
//输出并出列
void Output(int n,int m){
    for(int i = 1; i <= n;i++){
        for(int j = 1; j <m;j++){
            s = s->next;
        }
        p = s->next;
        m = p->passwopd;
        printf("%d ", p->num);
        s->next = p->next;
        free(p);
    }
}
int main(){
    int n, m;
    scanf("%d%d",&n,&m);
    Creatlinklist(n);
    Input(n);
    Output(n, m);
    return 0;
}

XDOJ0279-一元稀疏多项式计算器

去年写的程序，今年交进去错了，不晓得oj搞什么鬼，以下是重新写的

//xdoj0279.c
#include<stdio.h>
#include<stdlib.h>
​
typedef struct LNode{
    int p;//系数
    int e;//指数
    struct LNode* next;
}LNode,*LinkList;
​
LinkList InitLinkList(){
    LinkList L=(LinkList)malloc(sizeof(LNode));
    L->next=NULL;
    return L;
}
​
//多项式相加 指数递增
LinkList PolyAdd(LinkList L1,LinkList L2){
    LinkList p1=L1->next;
    LinkList p2=L2->next;
    LinkList result=(LinkList)malloc(sizeof(LNode));//作为结果返回
    result->next=NULL;
    result->e=0;//头结点存多项式的项数，便于输出 result->e表示结果的项数
    LinkList p3=result;
    //指数一样，则系数相加，若系数之和为0，则free
    //指数不一样，指数小的先插入进去,每执行一次插入，记录一次
    while(p1!=NULL && p2!=NULL){//注意这里最后要检验 究竟是谁先到底
        if(p1->e > p2->e){
            //p1的指数比较大，插入p2结点
            LinkList s=(LinkList)malloc(sizeof(LNode));
            s->e=p2->e;
            s->p=p2->p;
            s->next=NULL;
​
            p3->next=s;
            p3=p3->next;
​
            result->e++;
​
            p2=p2->next;
​
        }else if(p1->e < p2->e){
            //p2的指数比较大，插入p1结点
            LinkList s=(LinkList)malloc(sizeof(LNode));
            s->e=p1->e;
            s->p=p1->p;
            s->next=NULL;
​
            p3->next=s;
            p3=p3->next;
​
            result->e++;
​
            p1=p1->next;
​
​
        }else{//指数相等
            if(p1->p + p2->p == 0){
                ;
            }else{
                //系数之和不为0
                LinkList s=(LinkList)malloc(sizeof(LNode));
                s->p=p1->p + p2->p;
                s->e=p1->e;
                s->next=NULL;
​
                p3->next=s;
                p3=p3->next;
​
                result->e++;
            }
            //指数相等的情况，p1 和 p2 都要移动
            p1=p1->next;
            p2=p2->next;
        }
    }
    //还没完，while条件内部 不一定遍历结束
    if(p1 == NULL && p2==NULL){
        //如果p1和p2 都空，则恰好遍历结束
        return result;
    }else{
        if(p1==NULL){
            while(p2){
                LinkList s=(LinkList)malloc(sizeof(LNode));
                s->p=p2->p;
                s->e=p2->e;
                s->next=NULL;
​
                p3->next=s;
                p3=p3->next;
​
                result->e++;
​
                p2=p2->next;
            }
        }else if(p2==NULL){
            while(p1){
                LinkList s=(LinkList)malloc(sizeof(LNode));
                s->p=p1->p;
                s->e=p1->e;
                s->next=NULL;
​
                p3->next=s;
                p3=p3->next;
​
                result->e++;
​
                p1=p1->next;
            }
        }
        return result;
    }
}
​
//多项式相减 注意插入的时候先把L2的结点系数乘-1
LinkList PolyMinus(LinkList L1,LinkList L2){
    LinkList p1=L1->next;
    LinkList p2=L2->next;
    LinkList result=(LinkList)malloc(sizeof(LNode));//作为结果返回
    result->next=NULL;
    result->e=0;//头结点存多项式的项数，便于输出 result->e表示结果的项数
    LinkList p3=result;
    //指数一样，则系数相减，若系数之差为0，则free
    //指数不一样，指数大的先插入进去,每执行一次插入，记录一次
    while(p1!=NULL && p2!=NULL){//注意这里最后要检验 究竟是谁先到底
        if(p1->e > p2->e){
            //p1的指数比较大，插入p2结点 记得乘-1
            LinkList s=(LinkList)malloc(sizeof(LNode));
            s->e=p2->e;
            s->p=-(p2->p);
            s->next=NULL;
​
            p3->next=s;
            p3=p3->next;
​
            result->e++;
​
            p2=p2->next;
​
        }else if(p1->e < p2->e){
            //p2的指数比较大，插入p1结点
            LinkList s=(LinkList)malloc(sizeof(LNode));
            s->e=p1->e;
            s->p=p1->p;
            s->next=NULL;
​
            p3->next=s;
            p3=p3->next;
​
            result->e++;
​
            p1=p1->next;
​
        }else{//指数相等
            if(p1->p - p2->p == 0){
                ;
            }else{
                //系数之差不为0
                LinkList s=(LinkList)malloc(sizeof(LNode));
                s->p=p1->p - p2->p;
                s->e=p1->e;
                s->next=NULL;
​
                p3->next=s;
                p3=p3->next;
​
                result->e++;
            }
            //指数相等的情况，p1 和 p2 都要移动
            p1=p1->next;
            p2=p2->next;
        }
    }
    //还没完，while条件内部 不一定遍历结束
    if(p1 == NULL && p2==NULL){
        //如果p1和p2 都空，则恰好遍历结束
        return result;
    }else{
        if(p1==NULL){
            while(p2){//注意p2的系数要取相反数
                LinkList s=(LinkList)malloc(sizeof(LNode));
                s->p=-(p2->p);
                s->e=p2->e;
                s->next=NULL;
​
                p3->next=s;
                p3=p3->next;
​
                result->e++;
​
                p2=p2->next;
            }
        }else if(p2==NULL){
            while(p1){
                LinkList s=(LinkList)malloc(sizeof(LNode));
                s->p=p1->p;
                s->e=p1->e;
                s->next=NULL;
​
                p3->next=s;
                p3=p3->next;
​
                result->e++;
​
                p1=p1->next;
            }
        }
        return result;
    }
}
​
//输出L表，以多项式形式输出
void DisplayLinkList(LinkList L){
    LinkList p=L->next;
    if(p==NULL){
        //p为空，则说明L1和L2运算后为0
        printf("0");
        return;
    }
    while(p){
        if(p->p < 0){
            //如果系数小于0
            if(p->p == -1){
                //如果系数是-1，输出的时候应该是-x的某次方，而不是-1x的某次方
                if(p->e==1){
                    //如果系数是-1，且指数是1，那么应该输出-x
                    printf("-x");
                }else if(p->e==0){
                    //如果系数是-1，且指数是0，那么应该输出-1
                    printf("-1");
                }else{
                    //如果系数是-1，且指数不是0和1，那么应该输出-x的某次方
                    printf("-x^%d",p->e);
                }
            }else if(p->p!=-1){
                //如果系数不是-1，那么输出应该是px的某次方
                if(p->e==1){
                    //如果系数不是-1，且指数是1，那么应该输出px
                    printf("%dx",p->p);
                }else if(p->e==0){
                    //如果系数不是-1，且指数是0，那么应该输出p
                    printf("%d",p->p);
                }else{
                    //如果系数不是-1，且指数不是0和1，那么应该输出px的某次方
                    printf("%dx^%d",p->p,p->e);
                }
            }
        }else{
            //如果系数大于0
            if(p->p == 1){
                //如果系数是1，输出的时候应该是x的某次方
                if(p->e==1){
                    printf("x");
                }else if(p->e==0){
                    printf("1");
                }else{
                    printf("x^%d",p->e);
                }
            }else{
                //如果系数不是1，那么输出应该是px的某次方
                if(p->e==1){
                    //如果系数不是1，且指数是1，那么应该输出px
                    printf("%dx",p->p);
                }else if(p->e==0){
                    //如果系数不是1，且指数是0，那么应该输出p
                    printf("%d",p->p);
                }else{
                    //如果系数不是1，且指数不是0和1，那么应该输出px的某次方
                    printf("%dx^%d",p->p,p->e);
                }
            }
        }
        if(p->next!=NULL){//如果p的下一个存在
            if(p->next->p > 0 ){//且下一个系数大于0
                //则由此补上加号
                printf("+");
            }
        }
        p=p->next;
    }
}
​
int main(){
    int n,m,t;
    LinkList L1=InitLinkList();
    LinkList L2=InitLinkList();
    LinkList p1=L1;
    LinkList p2=L2;
​
    //input part
    scanf("%d%d%d",&n,&m,&t);
    for(int i=0;i<n;i++){
        LinkList s=(LinkList)malloc(sizeof(LNode));
        scanf("%d%d",&s->p,&s->e);
        p1->next=s;
        s->next=NULL;
​
        p1=p1->next;
    }
    for(int i=0;i<m;i++){
        LinkList s=(LinkList)malloc(sizeof(LNode));
        scanf("%d%d",&s->p,&s->e);
        p2->next=s;
        s->next=NULL;
​
        p2=p2->next;
    }
    //operation part
    LinkList L3;
    switch(t){
        case 0:L3=PolyAdd(L1,L2);break;
        case 1:L3=PolyMinus(L1,L2);break;
        default:break;
    }
    //outputpart
    DisplayLinkList(L3);
​
    return 0;
}

最后

感兴趣的可以关注我的微信公众号，第一时间收到动态

标签：p2,p3,p1,线性表,NULL,next,LinkList,数据结构
From： https://www.cnblogs.com/iamnotphage/p/16760158.html

相关文章

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99