精华内容
下载资源
问答
  • 求顺序表中第一个值为x的元素的前驱后继的存储位置,用指针参数前驱后继的值也可以得到了。
  • 那么Ai在链表中的prenxt就分别对应其前驱和后继 从后往前查,查完后就删除这个点(因为题目要求是1<=j<i1<=j<i1<=j<i) 删除的话,就直接把 i 的nxt置...

    传送门


    牢骚

    看到这种题,绝对的平衡树乱搞
    但我需要练习链表啊
    昨天偷懒贴了ldx的读优,结果他又没有加负数,气……

    分析

    将A数组排序后,建立链表
    那么Ai在链表中的pre和nxt就分别对应其前驱和后继
    从后往前查,查完后就删除这个点(因为题目要求是 1 &lt; = j &lt; i 1&lt;=j&lt;i 1<=j<i
    删除的话,就直接把 i 的nxt置为 i 这个点的前驱的nxt, i 的pre置为 i 这个点的后继的pre,这样就相当于把 i 跳过了


    需要额外注意的就是序列与链表的一 一对应关系

    代码

    #include<bits/stdc++.h>
    #define in read()
    #define N 100009
    using namespace std;
    inline int read(){
    	int f=1,ans=0;char ch;
    	while((ch=getchar())<'0'||ch>'9') if(ch=='-') f=-1;
    	while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
    	return f==1?ans:-ans;
    }
    int n,a[N];
    struct node{
    	int val,id;
    	int nxt,pre;
    }p[N];
    int tot=0,b[N],idx[N];
    int ans[N][3];
    void remove(int pos){
    	p[p[pos].pre].nxt=p[pos].nxt;
    	p[p[pos].nxt].pre=p[pos].pre;
    }
    bool cmp(const int &i,const int &j){
    	return a[i]<a[j];
    }
    int main(){
    	n=in;
    	int i,j,k;
    	for(i=1;i<=n;++i) a[i]=in,b[i]=i;
    	sort(b+1,b+n+1,cmp);
    	tot=1;
    	p[1].val=a[b[1]];
    	p[1].id=b[1];// 链表中对应的序列中的编号
    	idx[b[1]]=1;//序列中的点对应的链表中的位置
    	for(i=2;i<=n;++i){
    		idx[b[i]]=++tot;
    		p[tot].val=a[b[i]];p[tot].id=b[i];
    		p[tot].pre=tot-1;p[tot-1].nxt=tot;
    	}
    	for(i=n;i>=2;--i){
    		int pos=idx[i];
    		int mp=2000000009,mn=2000000009;
    		if(p[pos].pre) mp=abs(p[pos].val-p[p[pos].pre].val);
    		if(p[pos].nxt) mn=abs(p[pos].val-p[p[pos].nxt].val);
    		if(mp<=mn){
    			ans[i][0]=mp;
    			ans[i][1]=p[p[pos].pre].id;
    		}
    		else{
    			ans[i][0]=mn;
    			ans[i][1]=p[p[pos].nxt].id;
    		}
    		remove(pos);
    	}
    	for(i=2;i<=n;++i) printf("%d %d\n",ans[i][0],ans[i][1]);
    	return 0;
    }
    
    展开全文
  • 下列给定程序中,函数fun()的功能是:按顺序给s所指数组中的元素赋予从2开始的偶数,然后再按顺序对每5个元素求一个平均值,并将这些值依次存放在w所指的数组中。若s所指数组中元素的个数不是5的倍数,多余部分忽略...

    下列给定程序中,函数fun()的功能是:按顺序给s所指数组中的元素赋予从2开始的偶数,然后再按顺序对每5个元素求一个平均值,并将这些值依次存放在w所指的数组中。若s所指数组中元素的个数不是5的倍数,多余部分忽略不计。例如,s所指数组有14个元素,则只对前10个元素进行处理,不对最后的4个元素求平均值。

    请改正函数fun()中的错误,使它能得出正确的结果。

    注意:不要改动main函数,不得增行或删行,也不得更改程序的结构。

    试题程序:

    include <stdio.h>

    define SIZE 20

    fun (double *s, double *w)

    { int k, i; double sum;

    for(k=2, i=0; i<SIZE; i++)

    {s [i]=k; k+=2;}

    sum=0.0;

    for(k=0, i=0; i<SIZE;i++)

    {sum+=s[i];

    /*************found******...

    展开全文
  • 请设计一个算法,将P所指向节点的前驱变为P所指节点的后继节点。 Solution 此问题也可以看作交换p与p的后继节点位置 找到三个指针即可 p pp:p的前驱 ppp:p的前驱前驱 void exchangeNode(Node p) { // 如果...

    问题描述

    假设循环单链表不空, 且无表头节点无表头指针, 指针P指向链表中某节点。请设计一个算法,将P所指向节点的前驱变为P所指节点的后继节点。

    Solution

    此问题也可以看作交换p与p的前驱节点位置
    找到三个指针即可

    p
    pp:p的前驱
    ppp:p的前驱的前驱

    void exchangeNode(Node p) {
    	// 如果只有一个或者两个节点直接退出 
    	if (p->next->next == p) {
    		return;
    	} 
    	Node ppp = p, pp = p->next;
    	//  找到 pp,ppp 
    	while (ppp->next->next != p) {
    		ppp = ppp->next;
    		pp = pp->next;
    	}
    	// 交换节点 
    	pp->next = p->next;
    	ppp->next = p;
    	p->next = pp; 
    } 
    

    节点断开以及连接顺序如下:
    在这里插入图片描述

    展开全文
  • 数据结构——单链表基本操作(初始化,销毁,统计元素个数,指定位置元素,查找元素位置,求前驱后继,插入,删除,清空,遍历输出) 1.实验目的 通过该实验,深入理解链表的逻辑结构、物理结构等概念,掌握链表基本...

    数据结构——单链表基本操作(初始化,销毁,统计元素个数,指定位置元素,查找元素位置,求前驱后继,插入,删除,清空,遍历输出)

    1.实验目的
    通过该实验,深入理解链表的逻辑结构、物理结构等概念,掌握链表基本操作的编程实现,熟练掌握C++语言中指针的操作。
    2.实验内容:单链表基本操作(初始化,销毁,统计元素个数,指定位置元素,查找元素位置,求前驱后继,插入,删除,清空,遍历输出),用菜单形式对应各个操作,使其编程一个完整的小软件。
    控制台

    #include<bits/stdc++.h>
    
    using namespace std;
    
    #define OK 1
    #define ERROR 0
    
    typedef int ElemType;
    typedef int Status;
    
    typedef struct LNode{
        ElemType data;
        struct LNode *next;
    }LNode,*LinkList;
    
    //1.初始化链表
    Status InitList(LinkList &L){
        L=new LNode;
        if(!L) return ERROR;
        L->next=NULL;
        return OK;
    }
    
    //2.销毁链表
    Status DestoryList(LinkList &L){
        LinkList q;
        while(L){
            q=L;
            L=L->next;
            delete q;
        }
        return OK;
    }
    
    //3.链表中数据元素个数
    Status ListLength(LinkList L){
        LinkList p=L->next;
        int sum=0;
        while(p){
            sum++;
            p=p->next;
        }
        return sum;
    }
    
    //4.所指位序的元素值
    Status GetElem(LinkList L,int i,ElemType &e){
        LinkList p=L->next;
        int j=1;
        while(p&&j<i){
            p=p->next;
            ++j;
        }
        if(!p || j>i)
            return ERROR;
        e=p->data;
        return e;
    }
    
    //5.链表已存在元素的位序
    Status LocateElem(LinkList L,ElemType e){
        LinkList p=L->next;
        int i=1;
        while(p){
            if(p->data==e){
                cout<<i<<" ";
                p=p->next;
                i++;
            }else{
                p=p->next;
                i++;
            }
        }
        cout<<endl;
        return OK;
    }
    
    //6.请输入元素,求直接前驱
    Status PriorElem(LinkList L,ElemType e){
        LinkList p=L->next;
        if(e==p->data){
            cout<<"无前驱"<<endl;
            return ERROR;
        }
        LinkList q;
        while(p && p->data!=e){
            q=p;
            p=p->next;
        }
        cout<<q->data<<endl;
        return OK;
    }
    
    //7.请输入元素,求直接后继
    Status NextElem(LinkList L,ElemType e){
        LinkList p=L->next;
        while(p && p->data!=e){
            p=p->next;
        }
        if(p->next==NULL){
            cout<<"无后继"<<endl;
            return ERROR;
        }
        p=p->next;
        cout<<"后继为:"<<p->data;
        return OK;
    }
    
    //8.在第i个位置插入元素
    Status InsertElem(LinkList &L,int i,ElemType e){
        LinkList p=L;
        int j=0;
        while(p && j<i-1){
            p=p->next;
            j++;
        }
        if(!p || j>i-1) return ERROR;
        LNode *s=new LNode;
        s->next=p->next;
        p->next=s;
        s->data=e;
        cout<<"插入成功"<<endl;
        return OK;
    }
    
    //9.删除第i个元素
    Status DeleteElem(LinkList &L,int i){
        LinkList p;
        p=L;
        int j=0;
        while(p->next && j<i-1){
            p=p->next;
            j++;
        }
        if(!(p->next) || j>i-1) return ERROR;
        LinkList r=p->next;
        p->next=r->next;
        delete r;
        cout<<"删除成功"<<endl;
        return OK;
    }
    
    
    //10.清空链表
    Status ClearList(LinkList &L){
        LinkList p,q;
        p=L->next;
        while(p){
            q=p->next;
            delete p;
            p=q;
        }
        L->next=NULL;
        cout<<"已清空"<<endl;
        return OK;
    }
    
    //11.输出所输入的链表元素
    Status PrintElem(LinkList L){
        LinkList p=L->next;
        while(p){
            cout<< p->data <<" ";
            p=p->next;
        }
        cout<<endl;
        return OK;
    }
    
    //12.初始化并输入链表元素(尾插法)
    void CreateList(LinkList &L,int n){
        L=new LNode;
        L->next=NULL;
        LinkList r=L;
        cout<<"请输入"<<n<<"个数据"<<endl;
        for(int i=0;i<n;i++){
            LNode *p=new LNode;
            cin>>p->data;
            p->next=NULL;
            r->next=p;
            r=p;
        }
        cout<<"创建完成"<<endl;
    }
    
    
    int main(){
    
        LNode *L;
        ElemType e;
        int flag;
        int i,n;
    
        cout<<"可执行的操作有:"<<endl;
        cout<<"****************************************"<<endl;
        cout<<"****** 1.初始化或重置链表        *******"<<endl;
        cout<<"****** 2.销毁链表                *******"<<endl;
        cout<<"****** 3.链表中数据元素个数      *******"<<endl;
        cout<<"****** 4.所指位序的元素值        *******"<<endl;
        cout<<"****** 5.链表已存在元素的位序    *******"<<endl;
        cout<<"****** 6.请输入元素,求直接前驱  *******"<<endl;
        cout<<"****** 7.请输入元素,求直接后继  *******"<<endl;
        cout<<"****** 8.在第i个位置插入元素     *******"<<endl;
        cout<<"****** 9.删除第i个元素           *******"<<endl;
        cout<<"****** 10.清空链表               *******"<<endl;
        cout<<"****** 11.输出所输入的链表元素   *******"<<endl;
        cout<<"****** 12.初始化并输入链表元素   *******"<<endl;
        cout<<"****** 13.退出                   *******"<<endl;
        cout<<"****************************************"<<endl;
    
        while(flag){
                cout<<"请输入你的选择:"<<endl;
                cin >> flag;
                switch(flag){
                case 1:{
                    InitList(L);
                    cout<<"初始化成功"<<endl;
                    break;
                }
                case 2:{
                    DestoryList(L);
                    cout<<"销毁成功"<<endl;
                    break;
                }
                case 3:{
                    cout<<"链表长度为:";
                    cout<<ListLength(L)<<endl;
                    break;
                }
                case 4:{
                    cin>>i;
                    cout<<"第"<<i<<"位元素为:";
                    cout<<GetElem(L,i,e)<<endl;
                    break;
                }
                case 5:{
                    cout<<"请输入要查询的元素:";
                    cin>>e;
                    LocateElem(L,e);
                    break;
                }
                case 6:{
                    cout<<"请输入要查询的元素:";
                    cin>>e;
                    cout<<"前驱为:";
                    PriorElem(L,e);
                    break;
                }
                case 7:{
                    cout<<"请输入要查询的元素:";
                    cin>>e;
                    NextElem(L,e);
                    break;
                }
                case 8:{
                    cout<<"请输入要插入的结点:";
                    cin>>i>>e;
                    int n=InsertElem(L,i,e);
                    if(n==0) cout<<"非法位置"<<endl;
                    break;
                }
                case 9:{
                    cout<<"请输入要删除结点的位序:";
                    cin>>i;
                    DeleteElem(L,i);
                    break;
                }
                case 10:{
                    ClearList(L);
                    break;
                }
                case 11:{
                    PrintElem(L);
                    break;
                }
                case 12:{
                    cin>>n;
                    CreateList(L,n);
                    break;
                }
                case 13:{
                    return 0;
                }
            }
        }
        return OK;
    }
    

    如有不当之处,请指正!懒得写注释了,这次先省了哈哈。

    展开全文
  • 单链表和双链表

    2021-02-02 13:38:55
    单列表双列表单链表单链表的简单操作双链表双链表的简单操作 单链表 单链表的最大特点是可以将... 单链表结点中只有一个只指向后继的指针,使得单链表只能从头结点开始一次顺序的先后遍历。要访问某个结点的前驱结点
  • 单链表

    2019-11-07 22:36:14
    线性表的特征:对于非空表,第一个元素无前驱,最后一个元素无后继,其他中间的元素有且仅有一个直接前驱和一个直接后继单链表 单链表是线性表的链式存储结构,即链表 将线性表中各元素分布在存储器的不同存储块...
  • 单链表插入删除

    2020-09-28 21:56:17
    1、先开辟一个新的结点:s,s其实代表的也就是这个结点的地址 2.新结点中赋值 3.把上一个结点地址赋给新结点,也是让新结点先...p前继结点找不到,还是老办法,找后继结点q,然后pq交换数据,然后把后继结q点的地址给p.
  • StaticLinkLinst.h#ifndefSTATIC_LINKLIST_H#defineSTATIC_LINKLIST_HtypedefvoidStaticLinkListNode;//静态单链表节点...//静态单链表/**创建静态单链表*@paramcapacity静态单链表的最大容量*@ret...
  • 数据结构学习心得——单链表

    千次阅读 2017-08-17 18:36:14
    在链表存储中,每个结点不仅包含所有的元素的信息,还包含元素之间逻辑关系的信息,如单链表前驱结点包含后继结点的地址信息,这样就可以通过前驱结点中的地址信息找到后继结点的位置。 (2)单列表 在每个节点...
  • 单链表反转

    2016-09-03 23:42:44
    思路:用head保存当前位置,利用前驱和后继指针来保存上一个下一个指针  记住4个步骤:1,先保存head.next 不然断链了 2,反转链表 3,pre前移到head的位置 4,head前移到next的位置 /* public class ListNode { ...
  • 思路:用两对前驱和后继节点,分别比较当前节点的前驱和后继以及最小值界定啊的前驱和后继。 遍历完整个链表,删除最小值节点即可。 struct node { int val; node *next; }; void deleteMin(node *head) { node...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 12,060
精华内容 4,824
关键字:

单链表的前驱和后继