首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 开发语言 > C语言 >

明天要交了，准备崩溃了，知道思路但是不会写。用数据结构写的。可是小弟我的数据结构知识完全不会

2013-10-01 
明天要交了，准备崩溃了，知道思路但是不会写。用数据结构写的。可是我的数据结构知识完全不会。题目：试设计算

明天要交了，准备崩溃了，知道思路但是不会写。用数据结构写的。可是我的数据结构知识完全不会。
题目：试设计算法，将单链表中前 m 个结点和后 n 个结点进行互换，即将线性表    (a1, a2, …, am, b1, b2, …, bn )   改变成     (b1, b2, …, bn, a1, a2, …, am ) 。



我的想法是：先建立一个存放(a1, a2, …, am, b1, b2, …, bn）的线性表，然后再将将 (b1, b2, …, bn )从链表的当前位置上删除之后再插入 a1 到之前，并将 am设为表尾。

明天要交了，准备崩溃了，知道思路但是不会写。用数据结构写的。可是小弟我的数据结构知识完全不会


#include <stdio.h>
#include <malloc.h>
typedef struct LNode
{
int data;
struct LNode *next;
}LinkList;

void CreateList(LinkList* &L,int n)
{
int i;
L=(struct LNode*)malloc(sizeof(struct LNode));
L->next = NULL;
LinkList *p;
for(i=n;i>0;--i)
{
P=(struct LNode*)malloc(sizeof(struct LNode));
scanf("%d",&p->data);
p->next = L->next;
L->next = p;
}
}

int main()
{
struct LNode;
return 0;
}



数据结构
[解决办法]
我的思路：把b1插到表头，a1插到表尾。把b2插到b1后，a2插到a1后。依次进行就可以 
[解决办法]
两部分的组内顺序都不变，那么找到 am 和 bn，bn->next = a1; am->next = null; 不就可以了吗
[解决办法]

//假设带表头结点的单向链表头指针为head，试编写一个算法将值为5的结点插入到连接表的第k个结点前，删除第k个节点，并对该链表进行排序。
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <time.h>
struct NODE {
    int          data;
    struct NODE *next;
} H,*head,*p,*q,*s1,*s2,*s3,*s4,*s;
int i,j,k,n,t,m;
int main() {
    srand(time(NULL));

    //填写头节点数据
    H.data=-1;
    H.next=NULL;
    head=&H;

    //创建10个节点的单链表
    p=head;
    for (i=0;i<10;i++) {
        q=(struct NODE *)malloc(sizeof(struct NODE));
        if (NULL==q) return 1;
        q->data=rand()%100;//填写0..99的随机值
        q->next=NULL;
        p->next=q;
        p=q;
    }

    //输出整个单链表
    s=head->next;
    while (1) {
        if (NULL==s) {
            printf("\n");
            break;
        }
        printf("%02d->",s->data);
        s=s->next;
    }

    //将值为5的结点插入到单链表的第k个结点前
    k=3;
    n=0;
    p=head;
    while (1) {
        if (NULL==p) {
            break;
        }
        n++;
        if (k==n) {
            q=(struct NODE *)malloc(sizeof(struct NODE));
            if (NULL==q) return 1;
            q->data=5;
            q->next=p->next;
            p->next=q;
            break;
        }
        p=p->next;
    }

    //输出整个单链表
    s=head->next;
    while (1) {
        if (NULL==s) {
            printf("\n");
            break; 
 
        }
        printf("%02d->",s->data);
        s=s->next;
    }

    //删除第k个节点
    k=5;
    n=0;
    p=head;
    while (1) {
        if (NULL==p) {
            break;
        }
        n++;
        if (k==n) {
            q=p->next;
            if (q) {
                p->next=q->next;
                free(q);
            }
            break;
        }
        p=p->next;
    }

    //输出整个单链表
    s=head->next;
    while (1) {
        if (NULL==s) {
            printf("\n");
            break;
        }
        printf("%02d->",s->data);
        s=s->next;
    }

    //从小到大排序
    for (p=head;p!=NULL && p->next!=NULL;p=p->next) {
        for (q=p->next;q!=NULL && q->next!=NULL;q=q->next) {
            if (p->next->data > q->next->data) {

                //交换data
//              printf("swap %02d %02d\n",p->next->data,q->next->data);
//              t=p->next->data;p->next->data=q->next->data;q->next->data=t;

                //或者

                //交换next
//              printf("swap %02d %02d\n",p->next->data,q->next->data);
                s1=p->next;
                s2=p->next->next;
                s3=q->next;
                s4=q->next->next;

                if (s2!=s3) {
                     p->next=s3;
                    s3->next=s2;
                     q->next=s1;
                    s1->next=s4;
                } else {
                     p->next=s3;
                    s3->next=s1;
                           q=s3;
                    s1->next=s4;
                }

                //输出整个单链表
//              s=head->next;
//              while (1) {
//                  if (NULL==s) {
//                      printf("\n"); 
 
//                      break;
//                  }
//                  printf("%02d->",s->data);
//                  s=s->next;
//              }
//              getchar();
            }
        }
    }

    //输出整个单链表
    s=head->next;
    while (1) {
        if (NULL==s) {
            printf("\n");
            break;
        }
        printf("%02d->",s->data);
        s=s->next;
    }

    //将单链表中前 m 个结点和后 n 个结点进行互换,m+n为链表总长10
    m=4;
    n=6;
    k=0;
    p=head;
    while (1) {
        if (NULL==p) {
            break;
        }
        k++;
        if (m+1==k) {
            q=p;
        }
        s=p;
        p=p->next;
    }
    s1=head->next;
    head->next=q->next;
    s->next=s1;
    q->next=NULL;

    //输出整个单链表
    s=head->next;
    while (1) {
        if (NULL==s) {
            printf("\n");
            break;
        }
        printf("%02d->",s->data);
        s=s->next;
    }

    //释放所有节点
    p=head->next;
    while (1) {
        if (NULL==p) {
            break;
        }
        q=p->next;
        free(p);
        p=q;
    }

    return 0;
}
//18->94->58->17->27->20->43->57->75->78->
//18->94->05->58->17->27->20->43->57->75->78->
//18->94->05->58->27->20->43->57->75->78->
//05->18->20->27->43->57->58->75->78->94->
//43->57->58->75->78->94->05->18->20->27->
//

[解决办法]
引用:
Quote: 引用:

//假设带表头结点的单向链表头指针为head，试编写一个算法将值为5的结点插入到连接表的第k个结点前，删除第k个节点，并对该链表进行排序。
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <time.h>
struct NODE {
    int          data;
    struct NODE *next;
} H,*head,*p,*q,*s1,*s2,*s3,*s4,*s;
int i,j,k,n,t,m;
int main() {
    srand(time(NULL));

    //填写头节点数据
    H.data=-1;
    H.next=NULL;
    head=&H;

    //创建10个节点的单链表
    p=head;
    for (i=0;i<10;i++) {
        q=(struct NODE *)malloc(sizeof(struct NODE));
        if (NULL==q) return 1;
        q->data=rand()%100;//填写0..99的随机值
        q->next=NULL;
        p->next=q;
        p=q;
    }

    //输出整个单链表
    s=head->next; 
 
    while (1) {
        if (NULL==s) {
            printf("\n");
            break;
        }
        printf("%02d->",s->data);
        s=s->next;
    }

    //将值为5的结点插入到单链表的第k个结点前
    k=3;
    n=0;
    p=head;
    while (1) {
        if (NULL==p) {
            break;
        }
        n++;
        if (k==n) {
            q=(struct NODE *)malloc(sizeof(struct NODE));
            if (NULL==q) return 1;
            q->data=5;
            q->next=p->next;
            p->next=q;
            break;
        }
        p=p->next;
    }

    //输出整个单链表
    s=head->next;
    while (1) {
        if (NULL==s) {
            printf("\n");
            break;
        }
        printf("%02d->",s->data);
        s=s->next;
    }

    //删除第k个节点
    k=5;
    n=0;
    p=head;
    while (1) {
        if (NULL==p) {
            break;
        }
        n++;
        if (k==n) {
            q=p->next;
            if (q) {
                p->next=q->next;
                free(q);
            }
            break;
        }
        p=p->next;
    }

    //输出整个单链表
    s=head->next;
    while (1) {
        if (NULL==s) {
            printf("\n");
            break;
        }
        printf("%02d->",s->data);
        s=s->next;
    }

    //从小到大排序
    for (p=head;p!=NULL && p->next!=NULL;p=p->next) {
        for (q=p->next;q!=NULL && q->next!=NULL;q=q->next) {
            if (p->next->data > q->next->data) {

                //交换data
//              printf("swap %02d %02d\n",p->next->data,q->next->data);
//              t=p->next->data;p->next->data=q->next->data;q->next->data=t;

                //或者

                //交换next
//              printf("swap %02d %02d\n",p->next->data,q->next->data);
                s1=p->next;
                s2=p->next->next;
                s3=q->next; 
 
                s4=q->next->next;

                if (s2!=s3) {
                     p->next=s3;
                    s3->next=s2;
                     q->next=s1;
                    s1->next=s4;
                } else {
                     p->next=s3;
                    s3->next=s1;
                           q=s3;
                    s1->next=s4;
                }

                //输出整个单链表
//              s=head->next;
//              while (1) {
//                  if (NULL==s) {
//                      printf("\n");
//                      break;
//                  }
//                  printf("%02d->",s->data);
//                  s=s->next;
//              }
//              getchar();
            }
        }
    }

    //输出整个单链表
    s=head->next;
    while (1) {
        if (NULL==s) {
            printf("\n");
            break;
        }
        printf("%02d->",s->data);
        s=s->next;
    }

    //将单链表中前 m 个结点和后 n 个结点进行互换,m+n为链表总长10
    m=4;
    n=6;
    k=0;
    p=head;
    while (1) {
        if (NULL==p) {
            break;
        }
        k++;
        if (m+1==k) {
            q=p;
        }
        s=p;
        p=p->next;
    }
    s1=head->next;
    head->next=q->next;
    s->next=s1;
    q->next=NULL;

    //输出整个单链表
    s=head->next;
    while (1) {
        if (NULL==s) {
            printf("\n");
            break;
        }
        printf("%02d->",s->data);
        s=s->next;
    }

    //释放所有节点
    p=head->next;
    while (1) {
        if (NULL==p) {
            break;
        }
        q=p->next;
        free(p);
        p=q; 
 
    }

    return 0;
}
//18->94->58->17->27->20->43->57->75->78->
//18->94->05->58->17->27->20->43->57->75->78->
//18->94->05->58->27->20->43->57->75->78->
//05->18->20->27->43->57->58->75->78->94->
//43->57->58->75->78->94->05->18->20->27->
//





你的方法好复杂，太高深了。。。要用线性表的知识实现呢，没必要用到随机数吧？？

赵老师从来只给例子，当然不排除他喜欢灌水的缘故。
其次，方法思想你有了，难在哪里？
[解决办法]
引用:
Quote: 引用:

两部分的组内顺序都不变，那么找到 am 和 bn，bn->next = a1; am->next = null; 不就可以了吗


这个想法我懂，要用线性表的知识怎么实现呢？？


假设链表头是 head，你试试下面代码可以不，我没有运行哈，没时间测试下,变量自己定义，自己做有效判断
a = head;
for(i = 0; i < m; i++)
a = a->next;

b = a->next;
while(NULL != b->next)
b = b->next;

b->next = head;
a->next = NULL;
就这样完事，输出看看对不对
[解决办法]
上面的代码还要在最后加一句 head = b; 刚才忘了加
[解决办法]

#include <stdio.h>
#include <malloc.h>

typedef struct LNode
{
    int data;
    struct LNode *next;
} LNode,*LinkList;

void CreateList(LinkList &L,int n)
{
    int i;
    struct LNode *tail,*p;
    L=(struct LNode*)malloc(sizeof(struct LNode));
    L->next = NULL;
    tail=L;
    for(i=0; i<n; i++)
    {
        p=(struct LNode*)malloc(sizeof(struct LNode));
        printf("please input %dth number\n",i);
        fflush(stdin);
        scanf("%d",&p->data);
        p->next=NULL;
        tail->next=p;
        tail=p;
    }
}

int main()
{
    struct LNode *head;
    CreateList(head,10);
    LNode *q=head->next;
    while(q != NULL)
    {
        printf("%d\n",q->data);
        q=q->next;
    }
    return 0;
}

编译过了
[解决办法]
引用:
Quote: 引用:

两部分的组内顺序都不变，那么找到 am 和 bn，bn->next = a1; am->next = null; 不就可以了吗





看看我这个代码，输出部分怎么写呢？？

#include <stdio.h>
#include <malloc.h>

typedef struct LNode
{
int data;
struct LNode *next;
}LNode,*LinkList;

……

int main()
{
    int n,m;
struct LNode *head,*r;
scanf("%d%d",&n,&m);
CreateList(head,n);
exchange(r,m);
//这部分怎么写输出？？
return 0;
}


输出不至于这么难吧，哥们
p = head;
i = 0;
while(NULL != p)
    printf("The %dst node, data = %d.\n", ++i, p->data);
[解决办法]
撸主,将a1...am,b1....bn分别逆序，再将整个线性表逆序即可，编程简单，效率还高。
[解决办法]
    //将单链表中前 m 个结点和后 n 个结点进行互换,m+n为链表总长10
    m=4;
    n=6;
    k=0;
    p=head;
    while (1) {
        if (NULL==p) {
            break;
        }
        k++;
        if (m+1==k) {
            q=p;
        }
        s=p;
        p=p->next;
    }
    s1=head->next;
    head->next=q->next;
    s->next=s1; 
 
    q->next=NULL;

[解决办法]
//将单链表中前 m 个结点和后 n 个结点进行互换,m+n为链表总长10
    m=4;
    n=6;
    k=0;
    p=head;
    while (1) {
        if (NULL==p) {
            break;
        }
        k++;
        if (m+1==k) {
            q=p;//q指向旧链表第m个结点
        }
        s=p;//让s总是指向p的前一个结点
        p=p->next;
    }
    //此时s指向旧链表最后一个结点
    // head->1->2->3->4->5->6->7->8->9->10->NULL
    //               q^                s^

    s1=head->next;//保存旧链表第1个结点的地址到s1中
    // head->1->2->3->4->5->6->7->8->9->10->NULL
    //     s1^       q^                s^

    head->next=q->next;//新链表第1个结点指向旧链表第m+1个结点
    //     /-------------v
    // head  1->2->3->4->5->6->7->8->9->10->NULL
    //     s1^       q^                s^


    s->next=s1;//旧链表最后一个结点的next指向旧链表第1个结点
    //     /-------------v
    // head  1->2->3->4->5->6->7->8->9->10\
    //     s1^       q^                s^  
[解决办法]

    //       
[解决办法]
____________________________/

    q->next=NULL;//旧链表第m个结点的next指向NULL
    //     /-------------v
    // head  1->2->3->4  5->6->7->8->9->10\
    //     s1^       q^\->NULL         s^  
[解决办法]

    //       
[解决办法]
____________________________/


[解决办法]
你需要的是一个将链表斩断的函数和一个将链表连接的函数。

typedef struct LNode
{
    int data;
    struct LNode *next;
}LinkList;

LinkList* list_cut(LinkList* lst,int pos,LinkList** suffix)
{
    LNode* iter = NULL;
    int count = 0;

    for (iter = lst; NULL != iter; iter = iter->next) {
        if (pos == ++count) {
            break;
        }
    }

    // 如果传入的位置参数超过链表长度了
    if (NULL == iter) {
        return NULL;
    }

    *suffix = iter->next;
    iter->next = NULL;

    return lst;
}

ListList* list_concat(ListList* lst1,ListList* lst2)
{
    ListList* iter = NULL;

    if (NULL == lst1)
        return lst2;

    // 找到最后一个元素
    for (iter = lst1; NULL != iter->next; iter = iter->next) {
        ;
    }

    iter->next = lst2;

    return lst1;
}

int main(int argc,char** argv)  
 
{
    ListList* lst1 = NULL;
    ListList* lst2 = NULL;
    ...
    // 假设已经创建好链表在lst1中了；

    lst1 = list_cut(lst1,m,&lst2);
    // 现在已经斩成两段了，重新连上即可
    lst1 = list_concat(lst2,lst1);

    // 大功告成！
    return 0; 
}

[解决办法]
一个单链表。。插入删除遍历都有了。。。特别给你加了一个置换，置换在后面



#include<iostream>
using namespace std;
typedef struct Node
{
int data;
struct Node* pNext;

}NODE,*PNODE;//NODE等价于struct Node,*PNODE等价于struct Node*

PNODE create_list(void );//创建链表，并给每个节点赋值
void traverse_list(PNODE);//遍历链表
bool Is_empty(PNODE);//判断链表是否为空
bool insert_list(PNODE,int,int);     //插入一个节点
bool delete_list(PNODE,int,int*);//删除一个节点
bool displace(PNODE ,int) ;
int main(void)
{
PNODE pHead=nullptr;
bool t;
int i=0,val=0,b=0;
int* val1=&val;
pHead=create_list();
 traverse_list(pHead);
cout<<"要插入的位置和插入的数值：";
cin>>i>>val;
insert_list(pHead,i,val);
traverse_list(pHead);
cout<<"指定要删除的位置：";
cin>>b;
t=delete_list(pHead,b,val1);
 traverse_list(pHead);
if(t)
cout<<"删除的节点的值为："<<*val1<<endl;
 displace(pHead,3) ;
 traverse_list(pHead);
system("pause");
return 0;

}
PNODE create_list(void)//创建一个链表，并给链表的节点赋值！
{
PNODE pHead=new NODE;
PNODE p=pHead;
p->pNext=nullptr;
int len;
int val;
cout<<"输入你想要链表的长度 len=";
cin>>len;
for(int i=0;i<len;i++)
{
cout<<endl<<"输入第"<<i+1<<"个节点的值：";
cin>>val;
PNODE New=new NODE;
New->data=val;//给节点赋值
New->pNext=nullptr;
p->pNext=New;//把节点的地址赋值给p所指向节点的指针域
p=New;//把节点的地址赋值给指针P

}
return pHead;

}

void traverse_list(PNODE pHead)//这是一个链表的遍历函数
{
if((Is_empty(pHead)))
{
cout<<"这是一个空链表！"<<endl;
return ;
}
PNODE p=pHead;
cout<<"链表的内容为：";
while(p->pNext != nullptr)
{
p=p->pNext;//把下一个节点的地址赋值给指针P
cout<<p->data<<"  ";//输出节点的值

}
cout<<endl;
return ;
}

bool Is_empty(PNODE pHead)//判断一个链表是否为空
{
if(nullptr==pHead->pNext)
return true;
return false;

}

bool insert_list(PNODE pHead,int position,int val)//插入函数，附带判断插入是否成功！
{
int i=1;
PNODE p=pHead->pNext;
while(i<position-1&&p!=nullptr)//查询要插入的位置
{
p=p->pNext;
i++;
}
if(i>position-1
[解决办法]
nullptr==p)//如果查询失败，返回false....nullptr==p直接查询现在的指针是否为空！！为空后，后面的肯定不执行！
{
cout<<"插入失败！！"<<endl;
return false;
}
else
{
PNODE New=new NODE;
New->data =val;
if(nullptr==New)
{
cout<<"插入节点失败！"<<endl;
return false;
}
if(Is_empty(p))//下面都是插入细节
{
p->pNext=New;
New->pNext=nullptr;
return true;
}
else
{
New->pNext=p->pNext;
p->pNext=New;
return true;
}
}




}

bool delete_list(PNODE pHead,int position,int *val)
{

int i=1;
PNODE r=nullptr;
PNODE p=pHead->pNext;
while(i<position-1&&p!=nullptr)//查询要插入的位置
{
p=p->pNext;
i++;
}
if(i>position-1
[解决办法]
nullptr==p)//如果查询失败，返回false
{
cout<<"插入失败！！"<<endl;
return false;
}
else
{

if(Is_empty(p))//下面都是删除细节
{
*val=p->pNext->data;
r=p->pNext;
p->pNext=nullptr;
delete r;
return true;

}
else
{
*val=p->pNext->data;
r=p->pNext;
p->pNext=p->pNext->pNext;
delete r;
return true;
}
}




}


bool displace(PNODE pHead,int position)//置换
{
int i=1;
PNODE p=pHead->pNext;
PNODE q=pHead->pNext;
while(q->pNext != nullptr)//把尾节点找出来
{
q=q->pNext;

}

while(i<position-1&&p!=nullptr)//查询要插入的位置
{
p=p->pNext;
i++;
}
if(i>position-1
[解决办法]
nullptr==p)//如果查询失败，返回false....nullptr==p直接查询现在的指针是否为空！！为空后，后面的肯定不执行！
{
cout<<"置换失败！！"<<endl;
return false;
}
else
{
if(Is_empty(p))//下面都是插入细节 
 
{
cout<<"这是最后一个节点，置换失败"<<endl;
return false;
}
else
{
q->pNext=pHead->pNext;
pHead->pNext=p->pNext;
p->pNext=nullptr;
return true;

}
}


}


[解决办法]
#include"stdio.h"
#include"malloc.h"

struct SLNode
{
int data;
struct SLNode * next;
};

class SLList
{
private:
struct SLNode * head;
struct SLNode * tail;
int size;
public:
SLList()
{
size=0;
head=NULL;
tail=NULL;
}
SLList(int SIZE)
{
size=SIZE;
        SLNode * p,*q,*s;
s=(SLNode *)malloc(sizeof(SLNode));
scanf("%d",&(s->data));
s->next=NULL;
tail=s;
p=s;
for(int i=0;i<size-1;i++)
{
q=(SLNode *)malloc(sizeof(SLNode));
scanf("%d",&(q->data));
            s->next=q;
s=q;
tail=q;
}
head=p;
}
    int getsize(){return size;}
struct SLNode * gethead(){return head;}
struct SLNode * gettail(){return tail;}
void sethead(SLNode * h){ this->head=h;}
void settail(SLNode * t){ this->tail=t; tail->next=NULL;}
void setsize(int s){this->size=s;}

};

void cut(SLList &right,int pos,SLList &left)
{
int size;
size=right.getsize();
if(size<pos)
{
printf("错误的位置");
}
SLNode *p,*s;
p=right.gethead();
for(int i=0;i<pos;i++)
{
s=p;
p=p->next;
}
left.sethead(p);
left.settail(right.gettail());
left.setsize(size-pos);
right.settail(s);
}

void cat(SLList &former,SLList later)
{
int size1=former.getsize();
int size2=later.getsize();
int size=size1+size2;
former.setsize(size);
SLNode * p,*q,*s;
p=former.gettail();
    q=later.gethead();
p->next=q;
    s=later.gettail();
    former.settail(s);

}

int main()
{
SLList list(10);
SLList list1;
SLNode * Head=list.gethead();
int size=list.getsize();
SLNode *p=Head;
for(int i=0;i<size;i++)
{
printf("%d->",p->data);
p=p->next;
}
printf("\n");
    cut(list,4,list1);
cat(list1,list);
SLNode *Head1=list1.gethead();
while(Head1!=NULL)
{
printf("%d->",Head1->data);
Head1=Head1->next;
}
}  


你运行一下这个，应该可以。

读书人精选
热点排行