精华内容
下载资源
问答
  • //判断对称性 bool isSym(ListNode *head,int m){ if(head==NULL) return true; int mid=m/2; ListNode *p=head; int count=0; //获取链表长度 while(p){ count++; p=p-...
  • 请设计一个算法判断该链表的前m个结点的data域是否中心对称。例如xx, xyx, xyyx都是中心对称。如果m超过链表的长度,则只需要链表中的数据元素对称即认为对称。 输入说明 : 第一行为链表元素的个数n 第二行输入...

    问题描述 :

    设带头结点的单链表的头指针为head,结点结构由data和next两个域构成,其中data域为int型。请设计一个算法判断该链表的前m个结点的data域是否中心对称。例如xx, xyx, xyyx都是中心对称。如果m超过链表的长度,则只需要链表中的数据元素对称即认为对称。

    输入说明 :
    第一行为链表元素的个数n
    第二行输入单链表的数据元素(数据元素之间以空格分隔)
    第三行为m

    输出说明 :

    输出一个字符:
    T(表示对称)
    F(表示不对称)

    输入范例 :

    10
    1 2 3 2 1 1 2 3 4 5
    5
    

    输出范例 :

    T
    

    思路

    1. 找到前m个结点的中点
    2. 逆置后半段
    3. 从两段的第一个结点开始依次比较

    注意事项:如果m大于链表长度,直接让m=n

    代码

    #include <iostream>
    
    using namespace std;
    
    struct ListNode
    {
        int data;
        ListNode *next;
    };
    
    //从键盘读入数据创建链表,新结点插入到尾部
    ListNode *createByTail(int n)
    {
        ListNode *head;
        ListNode *p1,*p2;
        int data;
        head=new ListNode;
        head->next=NULL;//head指向头结点,此时为空链表
        p2=head;
        while(n>0)    //num为0,意味着用户输入结束
        {
            cin>>data;
            p1=new ListNode;
            p1->data=data;
            p2->next=p1;
            p2=p1;   //p2始终指向最后一个结点(即尾指针)
            n--;
        }
        p2->next=NULL;  //切记:最后一个结点的next赋值为NULL
        return head;
    }
    
    bool func(ListNode* head,int m,int n){
        ListNode *head2=head->next;
        if(m>n) m=n;
        int i=0;
        while(i<m/2){
            head2=head2->next;
            i++;
            //cout<<i<<" "<<head2->data<<endl;
        }
        //此时head2指向后半段的第一个
        
        //逆置
        ListNode *p=head2->next;
        head2->next=NULL;
        while(i<m-1){
            ListNode *temp=p;
            p=p->next;
            temp->next=head2;
            head2=temp;
            i++;
        }
    
    	//从两个链表的头开始比较
        ListNode *l1=head->next;
        ListNode *l2=head2;
        while(l2){
            //cout<<"1:"<<l1->data<<endl;
            //cout<<"2:"<<l2->data<<endl;
            if(l1->data!=l2->data) return false;
            l1=l1->next;
            l2=l2->next;
        }
        return true;
    }
    
    int main()
    {
        int n;
        cin>>n;
        ListNode* head=createByTail(n);//采用尾插法创建带头结点的单链表
        int m;
        cin>>m;
        bool res=func(head,m,n);
        if(res) cout<<"T"<<endl;
        else cout<<"F"<<endl;
        return 0;
    }
    
    

    原始链表:1 2 3 2 1 1 2 3 4 5
    前m个:1 2 3 2 1
    找到前m个的中点(后半段的起始结点):3
    逆置后半段,新链表:1 2 3
    指针 l1,指向链表1 2 3 2 1的头
    指针 l2,指向链表1 2 3 的头
    依次往后比较,直到 l2 为NULL

    展开全文
  • 第三行:待判断对称性的链表长度 输出说明 : 如第一行输入值为0、1、2、3之外的值,直接输出“err” 否则: 第一行:单链表A的遍历结果(数据元素之间以"->"分隔) 空行 第三行:true(对称) false...

    输入说明 :

    第一行:顺序表A的数据元素的数据类型标记(0:int,1:double,2:char,3:string)

    第二行:单链表A的数据元素(数据元素之间以空格分隔)

    第三行:待判断对称性的链表长度

    输出说明 :

    如第一行输入值为0、1、2、3之外的值,直接输出“err”

    否则:

    第一行:单链表A的遍历结果(数据元素之间以"->"分隔)

    空行

    第三行:true(对称)

                 false(不对称)

    坑死了,鬼知道,只有一个元素的时候是不对称的啊。。。

    #include <iostream>
    #include <bits/stdc++.h>
    using namespace std;
    
    template<class ElemType>
    void print(vector<ElemType> a,int len) {
        for( int m=0; m<len; ++m) { 
            cout<<a[m];
            if(m!=len-1)
                cout<<"->";
            else
                cout<<endl;
        }
    
    }
    
    
    template<class ElemType>
    
    void Judge_Symmetry( vector<ElemType> &a, int num ) {
        bool flag=0;
        print(a,a.size());
        
        if(a.size()==1) {
            cout<<endl<<"false"<<endl;//只有一个元素的时候是不对称的
            return;
        }
        
        for(int i=0; i<=num; ++i) {
            if(i<=num&&a[i]==a[num-i])
                flag=1;
            else
                flag=0;
        }
        cout<<endl;
        if(flag)
            cout<<"true"<<endl;
        else
            cout<<"false"<<endl;
    }
    
    int main() {//0:int,1:double,2:char,3:string
        int tmy,loc;
        string line,elem;
        stringstream ss;
        cin>>tmy>>loc;
        getchar();
        if(tmy!=0&&tmy!=1&&tmy!=2&&tmy!=3)
            cout<<"err"<<endl;
        else {
            getline(cin,line);
            ss<<line;
            vector<string>v;
            vector<int>vi;
            vector<double>vd;
            while(ss>>elem) {
                if(tmy==0) {
                    int i=atoi(elem.c_str());
                    vi.push_back(i);
                }
    
                else if(tmy==1) {
                    double d=atof(elem.c_str());
                    vd.push_back(d);
                } else
                    v.push_back(elem);
            }
            if(tmy==0)
                Judge_Symmetry(vi,loc-1);
            else if(tmy==1)
                Judge_Symmetry(vd,loc-1);
            else
                Judge_Symmetry(v,loc-1);
            return 0;
        }
    }
    
    
    

    展开全文
  • 判断单链表是否对称

    2020-04-16 16:40:47
    } //判断是否对称 int dc(LinkList L,int n){ int i; LinkList p; int s[30]; p=L->next; for(i=0;i;i++){//一半先保存到数组中 s[i]=p->data; p=p->next; } i--; printf("i的值:%d\n",i); if(1==n%2...
    #include<stdio.h>
    #include<stdlib.h>
    typedef struct Node{
    	int data;
    	struct Node *next;
    }LinkNode,*LinkList;
    
    void Create_T(LinkList head);
    void trans(LinkList head);
    int lenght(LinkList L);
    int dc(LinkList L,int n);
    void main(){
    	LinkList head,p,q,u,pre,tail;
    	int i,len;
    	head= (LinkList)malloc(sizeof(LinkNode));//head指向新生成的头结点
    	head->next=NULL;//初始化一个空的单链表
    	printf("请输入各个结点的值:\n");
    	Create_T(head);
    	trans(head);
    	len=lenght(head);
    	printf("链表长度为:%d\n",len);
    	if(dc(head,len)>=0)
    		printf("不对称\n");
    	else
    		printf("对称\n");
    }
    
    //尾插法创建单链表
    void Create_T(LinkList head){
    	LinkList tail,p;
    	int num;
    	tail=head;
    	while(scanf("%d",&num),num!=-1){
    		p=(LinkList)malloc(sizeof(LinkNode));
    		p->data=num;
    		tail->next=p;
    		tail=p;
    	}
    	tail->next=NULL;
    }
    //遍历链表
    void trans(LinkList head){
    	LinkList p=head->next;
    	while(p){
    		printf("%d ",p->data);
    		p=p->next;
    	}
    	printf("\n");
    }
    //链表的长度
    int lenght(LinkList L){
    	LinkList p=L->next;
    	int len=0;
    	while(p){
    		len++;
    		p=p->next;
    	}
    	return len;
    }
    //判断是否对称
    int dc(LinkList L,int n){
    	int i;
    	LinkList p;
    	int s[30];
    	p=L->next;
    	for(i=0;i<n/2;i++){//一半先保存到数组中
    		s[i]=p->data;
    		p=p->next;
    	}
    	i--;
    	printf("i的值:%d\n",i);
    	if(1==n%2){
    		p=p->next;
    	}		
    	while(p&&i>=0){
    		if(s[i]==p->data){
    			i--;
    			p=p->next;
    		}
    		else
    			break;
    	}
    	return i;
    }
    
    展开全文
  • 判断单链表是否中心对称

    千次阅读 2020-08-13 18:00:40
    试设计算法判断该链表的全部n个字符是否中心对称。例如xyx、xyyx都是中心对称。 算法思想:将链表前半部分存入栈中,然后依次出栈和链表后半部分比较。如果长度为奇数时跳过中间元素,与后半段比较。 注意一个点,...

    设单链表的表头指针为L,结点结构由data和next两个域构成,其中data为字符型。试设计算法判断该链表的全部n个字符是否中心对称。例如xyx、xyyx都是中心对称。

    算法思想:将链表前半部分存入栈中,然后依次出栈和链表后半部分比较。如果长度为奇数时跳过中间元素,与后半段比较。

    注意一个点,while(p),p是遍历指针,代码段总是报空指针异常,我就很纳闷,为什么最后一个结点的next,能进入循环。
    查看结构体发现,next指针并未初始化为NULL,实际指向内存随机一块空间,如果构建单链表的时候不把表尾指向NULL,就会导致next进入循环。

    #include<iostream>
    #include<stack>
    using namespace std;
    //判断链表字符是否中心对称
    //算法思想:将链表前半部分存入栈中,然后依次出栈和链表后半部分比较。
    typedef struct LNode {//本名
    	char data;    //数据域
    	struct LNode* next; //指针域
    }LNode, * LinkList;//别名,LinkList代表表头
    
    LinkList List_tailInsert(LinkList& L) {
    	LNode* s; LNode* r; char x;int length = 0;
    	L = (LinkList)malloc(sizeof(LNode));
    	L->next = NULL;
    	r = L;
    	cout << "输入链表长度" << endl;
    	cin >> length;
    	cout << "输入元素" << endl;
    	while (length)
    	{
    		cin >> x;
    		s = (LinkList)malloc(sizeof(LNode));
    		s->data = x;
    		r->next = s;
    		r = s;
    		length--;
    	}
    	r->next = NULL;
    	return L;
    }
    void show(LinkList L) {
    	LNode* p = L->next;
    	while (p) {
    		cout << p->data;
    		p = p->next;
    	}
    	cout << endl;
    }
    bool judegement(LinkList L, int n) {
    	stack<char> s;
    	LNode* p = L->next;
    	for (int i = 0; i < n / 2; i++) {
    		s.push(p->data);
    		p = p->next;
    	}
    	if (n % 2 == 1)p = p->next;
    	while(p) {
    		if (p->data == s.top()) {
    			s.pop();
    			p = p->next;
    		}
    		else {
    			return false;
    		}
    	}
    	return true;
    }
    int main() {
    	LinkList l;
    	List_tailInsert(l);
    	show(l);
    	cout << judegement(l,5) << endl;
    }
    
    展开全文
  • } if (check_P(place) == false)//位置合法性判断 return false; if (place == size() - 1)//尾部插入特判 { push_back(num); return true; } LinkNode* p = get_address(place); LinkNode* p2 = new LinkNode;//...
  • 一.算法思想 ...思路二:将单链表的元素全部进栈,然后依次与单链表进行比较,直到比较到链表L为止,该算法与第一个算法相比实现起来较简单,但需要扫描两次单链表,效率较低。 二.源代码 //判断链表数
  • //单链表为空或者只有一个元素时,默认为对称 DLNode *p,*q; p = L->next; q = L->prior; while (p!=q&&p->next!=q) { if (p->data == q->data) { p = p->next; q = q->prior; } else ...
  • 题目:设单链表的表头指针为L,结点结构由data和next两个域构成,其中...栈是先进后出,所以前一半链表中元素可以实行“逆置输出”,此时和后一半元素进行比较,可以判断中心对称性 1)让链表的前一半元素一次进栈...
  • * 有一个带头节点的单链表,用于存放整数序列,设计一个算法判断该序列是否是对称的。 */ public static void main(String[] args) { // TODO Auto-generated method stub int [] arr={1,2,3,2,1}; ...
  • 有一单链表L,用于存放整数序列,设计一个算法判断该序列是否是对称的。若是输出1,否则输出0。 输入格式: 有多组数据,每组第一行为单链表元素个数n(0<n<50);第二行为单链表的各元素。 输出格式: 若序列...
  • 这道题的难点在于,单链表无法倒着遍历,无法使用双指针技巧。容易想到的思路就是把原始链表反转存入一条新的链表,然后比较这两条链表是否相同。**其实也可以借助二叉树后序遍历的思路,不需要显式反转原始链表也...
  • 预计阅读时间:7 分钟今天聊聊如何判断一个链表是不是回文链表。之前有两篇文章写了回文串和回文序列相关的问题:经典面试题:最长回文子串子序列解题模板:最长回文子序列我们知道,寻找回文串的核...
  • 因为回⽂串是对称的, 所以正着读和倒着读应该是⼀样的, 这⼀特点是解决回⽂串问题的关键. 这道题的关键在于, 单链表⽆法倒着遍历, ⽆法使⽤双指针技巧。 那么最简单的办法就是, 把原始链表反转存⼊⼀条新的链表...
  •  printf("单链表显示:");  if(q==NULL)  printf("链表为空!");  else if(q->next==NULL)  printf("%c/n",q->strdate);  else  {  while(q->next!=NULL)  {  printf("%c",q->strdate); ...
  • 写出算法dc(h,n),判断该链表的前n个字符是否中心对称。例如xyx,xyyx都是中心对称(2018) int dc(LinkList h,int n){ char s[]; int i; LinkList *p=h->next; for(i=A;i<=n/B;i++){ s[i]=p->data;...
  • 判断链表结点对称 (10 分)

    千次阅读 2019-09-14 20:32:25
    设计算法,判断带头结点的循环双向链表中的数据结点是否对称。 如果对称,输出“yes” 如果不对称,输出“no” 链表空则输出“NULL” #include <stdio.h> #include <iostream> using namespace std; ...
  • 判断一个字符串是否是中心对称 C++描述
  • 链表的设计--单链表逆序开始

    千次阅读 2010-02-09 20:42:00
    这个问题仅仅可以考察人们对c语言特别是指针的熟悉程度,在实际编程中没有任何的意义,单链表逆序无论如何都要花费大量的时间,如果非要这么做为何不用空间来换时间,比如用双链表,然而如果你使用了双链表的话,...
  • 实验报告有流程图,代码带注释及运行结果和应用算法实现,报告很全
  • 判断链表前N个字符是否中心对称

    千次阅读 2019-01-01 21:46:27
    7、题目:设单链表的表头指针为h(这里我习惯的用了head),结点结构由data和next两个域构成,其中data域为字符型。 试设计算法判断该链表的前n个字符是否中心对称。例如xyx,xyyx都是中心对称。 #include &lt;...
  • 不过,由于它良好的对称性,使得对某个结点的前后结点的操作,带来了方便,可以有效提高算法的时间性能。说白了,就是用空间来换时间。 线性表总结回顾 线性表是零个或多个具有相同类型的数据元素的有限序列。认识了...
  • 数据结构单链表OJ题自行分析 例题1 给你一个链表的头节点head和一个整数val,请你删除链表中所有满足Node.val == val的节点,并返回新的头节点 //方法1 自带头节点的单链表算法 void SListPushVal(SListNode...
  • 1. 设单链表中存放有n个字符,试编写算法,判断该字符串是否有中心对称的关系,例如xyzzyx是中心对称的字符串。(提示:将单链表中的一半字符先依次进栈,然后依次出栈与单链表中的另一半字符进行比较。) //...
  • 算法,还要分析时间复杂度以判断是否可行。 2.写完代码后,如何编写测试用例?也就是两类测试用例:功能测试和边界测试! 3.如何能及时发现并纠正代码的问题?提前想好测试用例,写完代码后,立即用事先准备好的...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,759
精华内容 1,103
关键字:

判断单链表的对称性