设有两个线性表A和B皆是单链表存储结构。同一个表中的元素各不相同，且递增有序。写一算法，构成一个新的
下面大体介绍一下基本思想：
由于是递增的单链表：0->0->0->0 这种结构不能逆向反问；所以直接做操作是很不好实现的；
所以我第一步是将两链表的指针反转，这样就使原来两链表由递增序列变成了递减序列；第二步在根据
合并排序的思想，将两个链合并； 思路比较简单，你一看因该能明白，我用C++实现了一下想法，代码如下：
#include
using namespace std;
const int N = 8;
struct Node
{
int data;
Node* next;
Node(int d = 0, Node* n = 0):data(d), next(n){}
};
void Print(Node* p)
{
do
{
cout data << " ";
p = p->next ;
}while(p);
cout << endl;
}
void Create(Node*& List)
{
int i;
Node* tail = 0;
for(i = 0; i < N; i++)
{
Node* q = new Node;
q->data = (rand()%100);
if(tail == 0) tail = q, List = q;
else
{
tail->next = q;
tail = tail->next;
}
}
}
void Sort(Node*& List)
{
for(Node* p = List; p != 0; p = p->next)
{
for(Node* q = p; q != 0; q = q->next)
{
if(q->data data) swap(q->data, p->data);
}
}
}
void Converse(Node*& List) //将链表中指针逆向,实际上就是将递增序列变为递减序列
{
Node* p, *q, *temp;
p = List; //第一个节点
q = p->next; //第二个节点
temp = q->next; //第三个节点
List->next = 0;
while(temp)
{
q->next = p;
p = q;
q = temp;
temp = temp->next;
}
List = q;
q->next = p;
}
void Merge(Node*& List1, Node*&List2, Node*& List3)
{
//这里做法类似归并排序
Node* p, *q, *tail;
p = List1, q = List2;
while(p && q)
{
if(List3 == 0)
{
List3 = p->data > q->data ? p : q;
if(List3 == p) p = p->next;
else q = q->next;
List3->next = 0;
tail = List3;
}
else
{
Node* t = p->data > q->data ? p : q;
if(t == p) p = p->next;
else q = q->next;
tail->next = t;
tail = t;
}
}
//将剩余的直接接过去即可；
if(p == 0) tail->next = q;
else tail->next = p;
}
int main()
{
Node* List1 = 0, *List2 = 0, *List3 = 0;
Create(List1);
Create(List2);
Sort(List1);
Sort(List2);
cout << "两个递增序列如下：" << endl;
Print(List1);
Print(List2);
cout << "反转后的序列如下: " << endl;
Converse(List1);
Converse(List2);
Print(List1);
Print(List2);
Merge(List1, List2, List3);
cout << "合并结果如下：" << endl;
Print(List3);
system("pause");
return 0;
}
#include"stdio.h"
#include"malloc.h"
struct list
{
int data;
struct list *next;
};
struct list *head1,*head2,*p1,*p2,*q1,*q2;
void main()
{
int n=0;
void unionlist();
p1=q1=(struct list*)malloc(sizeof(struct list));
printf("请输入第一个链表的信息
");
scanf("%d",&p1->data);
while(p1->data!=0)
{
n=n+1;
if(n==1)
head1=q1;
else
q1->next=p1;
q1=p1;
p1=(struct list*)malloc(sizeof(struct list));
scanf("%d",&p1->data);
}
q1->next=NULL;
n=0;
p2=q2=(struct list*)malloc(sizeof(struct list));
printf("请输入第二个链表的信息
");
scanf("%d",&p2->data);
while(p2->data!=0)
{
n=n+1;
if(n==1)
head2=q2;
else
q2->next=p2;
q2=p2;
p2=(struct list*)malloc(sizeof(struct list));
scanf("%d",&p2->data);
}
q2->next=NULL;
unionlist();
}
void unionlist()
{
struct list *head,*p;
int i=0;
p1=head1;
p2=head2;
head=p=(struct list*)malloc(sizeof(struct list));
p->data=0;
while(p1 && p2)
{
if(p1->datadata)
{
p->next=p1;
p=p1;
p1=p1->next;
}
else
{
p->next=p2;
p=p2;
p2=p2->next;
}
}
p->next=p1?p1:p2;
p=head;
printf("合并后的链表为如下：
");
while(p)
{
i=i+1;
if(i==1)
p=p->next;
printf("%3d",p->data);
p=p->next;
}
printf("
");
free(head1);
free(head2);
}
这个问题就是剔除A中的B元素，最朴素的算法就是遍历A，逐个判断是否在B中，算法复杂度为O(n*m)，若用二分查找的话，就是O(n*logm)，显然效率低下。
考虑到A,B中元素都是有序的，对A中第一个元素，在B中找到第一个不比它小的元素，若两者相等，则该元素剔除，否则加入到c中；对A中下个元素，重复该过程，一直到A或B某一个比较完。算法复杂度为O(n+m)。
struct Node {
int num;
struct Node *pNext;
};
typedef struct Node *List;
List chaji( List a, List b)
{
List c = NULL;
while ( a != NULL && b!= NULL)
{
while ( a->num > b->num)
b = b->pNnext;
if ( a->num < b->num)
{
if (c == NULL)
c = malloc(sizeof(struct Node));
else
{
c->pNext = malloc(sizeof(struct Node));
c = c->pNext;
}
c->num = a->num;
c->pNext = NULL;
}
a = a->pNext;
}
return c;
}
编程问题,有关数据结构的
答：if(pa->data<=pb->data){//如果链表a中pa指向的的节点值不大于b的节点值 pc->next = pa;//则链表c（也就是最终合成好的链表）优先加入pa指向的节点 pc = pa;//现在指向pc到新加入的pa节点 pa = pa->next; //pa指向a链表中的下一个节点 } 整个代码是将两个链表合并，并使其中的...
求C++程序:用线性表求多项式相加,要求运用类的知识(顺序,单链俩种)
答：LNode *sum(LNode *head1,LNode *head2) //多项式相加函数 { LNode *pa,*pb,*pc,*head;int n=0;pa=head1->next;pb=head2->next;head=new LNode;pc=head;while(pa!=NULL&&pb!=NULL){ pc->next=new LNode;pc=pc->next;pc->a=pa->a+pb->a;pc->b=n++;pa=pa->next...
c语言链表的操作
答：int CreateLink_L(LinkList &L,int n){// 创建含有n个元素的单链表LinkList p,q;int i;ElemType e;L = (LinkList)malloc(sizeof(LNode));L->next = NULL; // 先建立一个带头结点的单链表q = (LinkList)malloc(sizeof(LNode));q = L;for (i=0; i<n; i++) {scanf("%d...
如何创建单链表?
答：建立单链表的常用方法有两种：头插法建表、尾插法建表 建立单链表的常用方法有两种。下面以顺序存储为例来叙述。(1) 头插法建表 该方法从一个空表开始，读取数组a中的字符，生成新结点，将读取的数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直到结束为止。算法如下：void...
菜鸟看数据结构算法 有些地方看不懂 求解
答：scanf(&p->data);//输入元素值 先说这句，运算符优先级问题，写成这样能理解了吧&（p->data），运算符->的优先级是高于&的，明白了吧 后面是这样插的，第一次加入p L---p---NULL 第二次加入pp L---pp---p---NULL 就是插入的数在L后面，但是跟之前插入的数比是在前面，这就是逆序...
单链线性表头结点算第一个结点吗?如果算 要在单链线性表中第i位置插...
答：while(flag) /* flag初值为1，当输入"#"时，置flag为0，建表结束*/ { c=getchar();if(c!='#'){ s=(Node*)malloc(sizeof(Node)); /*建立新结点s*/ s->data=c;s->next=L->next;/*将s结点插入表头*/ L->next=s;} else flag=0;} } //计算链表长度 void length(Link...
c语言 链表操作:建立,显示及节点的插入,删除
答：void CreateList_L(LinkList &L, int n) // 算法2.11 { // 逆位序输入（随机产生）n个元素的值，建立带表头结点的单链线性表L LinkList p;int i;L = (LinkList)malloc(sizeof(LNode));L->next = NULL; // 先建立一个带头结点的单链表 for (i=n; i>0; --i){ p = ...
线性表的建立及基本操作的实现
答：if(a==b) return 1; else return 0;}// 初始条件: 线性表L已存在,compare()是数据元素判定函数(满足为1,否则为0)// 操作结果: 返回L中第1个与...// 在带头结点的单链线性表L中,删除第i个元素,并由e返回其值Status ListDelete(LinkList L,int i,ElemType &e) { LinkList p,q; p = L; int...
数据结构,链表的题。
答：LinkList p = L->next; /* p指向第一个结点 */ while(p) { /* 没到表尾 */ i++;p = p->next;} return i;} Status ListInsert(LinkList *L, int i, ElemType e) /* 算法2.9。不改变L */ { /* 在带头结点的单链线性表L中第i个位置之前插入元素e */ int j = 0;Link...
悬赏求助各位编程大人 小弟有一C++题目着实让我蛋疼 下面由一版本 望高...
答：} 用这个直接代替原来的函数，或者不代替也行，这两个是重载函数，根据输入参数不同自动选择。include "stdafx.h"include <stdio.h> include <stdlib.h> define ElemType int define NULL 0 typedef enum{OK,ERROR}Status; // typedef struct node { ElemType data;struct node *next;} *Link,...
