将两个有序线性表合并成一个有序线性表，用C语言 在线急等！！！！

Question

将两个有序线性表合并成一个有序线性表，并去掉重复元素，
谢谢

本人编程实在没天赋！

Answer 1

代码写好了。
经测试VC下通过。
#include <stdio.h>

int merge(int *a,int n1,int *b,int n2,int *s)
{
int i=0,j=0,k=0;
while(i<n1&&j<n2)
{
if(a[i]>b[j]){
if(k&&s[k-1]==b[j])//有重复元素
j++;
else
s[k++]=b[j++];
}
else{
if(k&&s[k-1]==a[i])//有重复元素
i++;
else
s[k++]=a[i++];
}
}
while(i<n1){
if(k&&s[k-1]==a[i])
i++;
else
s[k++]=a[i++];
}
while(j<n2){
if(k&&s[k-1]==b[j])//有重复元素
j++;
else
s[k++]=b[j++];
}
return k;
}
int main()
{
int a[100],b[100],s[200],n1,n2,i,n3;
printf("输入第一个数组元素个数：");
scanf("%d",&n1);
printf("输入%d个升序元素（空格隔开）：",n1);
for(i=0;i<n1;i++)
scanf("%d",&a[i]);
printf("输入第二个数组元素个数：");
scanf("%d",&n2);
printf("输入%d个升序元素（空格隔开）：",n2);
for(i=0;i<n2;i++)
scanf("%d",&b[i]);
n3=merge(a,n1,b,n2,s); //a和b数组的元素合并到s数组里去(并消除重复元素),并返回合并后数组的元素个数
printf("合并后元素数组为：");
for(i=0;i<n3;i++)
printf("%d ",s[i]);
printf("\n");
return 0;
}
附测试数据一组：
5
3 50 50 100 100
3
8 50 80
输出为：3 8 50 80 100

Answer 2

#include<stdio.h>
#include<stdlib.h>
/*线性表*/
struct TLink {
int data;
struct TLink * next;
};/*end struct TLink*/

/*生成新元素*/
struct TLink * new_item(int number)
{
struct TLink * r = 0;
r = (struct TLink *)malloc(sizeof(struct TLink));
r->data = number;
r->next = 0;
return r;
}/*end new_item*/

/*在线性表中查询数据*/
struct TLink * lookup(struct TLink * root, int number)
{
struct TLink * h = root;
while(h) {
if (h->data == number) return h;
h = h->next ;
}/*end lookup*/
return 0;
}

/*在线性表中追加一个数据*/
void append(struct TLink * * root, int number)
{
struct TLink * r = 0, * n = 0;
if (!root) return ;

/*不记录重复元素*/
if (lookup(*root, number)) return;

/*如果表为空则新建表*/
r = *root;
if (!r) {
*root = new_item(number);
return ;
}/*end if*/

/*为保证为有序线性表，如果数据比表头还小则作为表头*/
if (number < r->data ) {
n = new_item(number);
n->next = r;
*root = n;
return ;
}/*end if*/

/*在有序线性表中查找位置插入元素*/
while(r) {
n = r->next ;

/*如果已经是表尾则直接追加*/
if (!n) {
n = new_item(number);
r->next = n;
return ;
}/*end if*/

/*在中央某处插入*/
if (number < n->data ) {
r->next = new_item(number);
r->next->next = n;
return ;
}/*end if*/
r = n;
}/*end while*/
}/*end append*/

/*打印有序线性表*/
void print(struct TLink * root)
{
struct TLink * r = root;
printf("【");
while(r) {
printf("%d ", r->data );
r = r->next ;
}/*end while*/
printf("\b】\n");
}/*end print*/

/*将有序线性表h1合并至有序线性表h0，并销毁线性表h1*/
void merge(struct TLink ** h0, struct TLink ** h1)
{
struct TLink * h = 0, * k = 0;
if (!h0 || !h1) return ;
h = *h1;
while(h) {
append(h0, h->data );
k = h;
h = h->next ;
free(k);
}/*end h*/
h1 = 0;
}

int main(void)
{
int i = 0; struct TLink * x=0, *y = 0;
int a[] = {8,4,3,9,5,1};
int b[] = {7,2,1,5,6,0};
printf("原数据为：\n数组A：【");
for(i = 0; i < 6; i++) {
printf("%d ", a[i]);
append(&x, a[i]);
}/*next*/
printf("\b】\n数组B：【");
for(i = 0; i < 6; i++) {
printf("%d ", b[i]);
append(&y, b[i]);
}/*next*/
printf("\b】\n转换为有序线性表\nA：");
print(x);
printf("B：");
print(y);
printf("AB合并后为：");
merge(&x, &y);
print(x);
return 0;
}

/*以上程序运行结果示例：
原数据为：
数组A：【8 4 3 9 5 1】
数组B：【7 2 1 5 6 0】
转换为有序线性表
A：【1 3 4 5 8 9】
B：【0 1 2 5 6 7】
AB合并后为：【0 1 2 3 4 5 6 7 8 9】

*/

Answer 3

楼主是不是信管的= =

Answer 4

//---------------------------------------------------------------------------

#include <stdio.h>
#include <stdlib.h>

typedef struct tagStruNode
{
int val;
tagStruNode * pNext;
}STRU_NODE, *PSTRU_NODE;

//打印链表
void PrintLink(const PSTRU_NODE pLink)
{
PSTRU_NODE p = pLink;
while(NULL != p )
{
printf("%d,", p->val);
p = p->pNext;
}

printf("\n");
}

//将节点加入到一个增序排列的链表中
void AddNodeToLinkByInc(PSTRU_NODE * pLink, int val)
{
PSTRU_NODE p1 = *pLink;
PSTRU_NODE p2 = *pLink;

while(NULL != p1)
{
if(p1->val > val)
{
PSTRU_NODE pNew = (PSTRU_NODE)malloc(sizeof(STRU_NODE));
pNew->val = val;
if(p1 == p2) //加入到头节点
{
*pLink = pNew;
pNew->pNext = p1;
}
else
{
p2->pNext = pNew;
pNew->pNext = p1;
}

break;
}

p2 = p1;
p1 = p1->pNext;
}

if(NULL == p1)
{
PSTRU_NODE pNew = (PSTRU_NODE)malloc(sizeof(STRU_NODE));
pNew->val = val;
pNew->pNext = NULL;

if (NULL == * pLink) //头节点为NULL
{
*pLink = pNew;
}
else //加入到尾部
{
p2->pNext= pNew;
}

return;
}
}

//清除链表
void ClearLink(PSTRU_NODE pLink)
{
PSTRU_NODE p = pLink;
PSTRU_NODE p1 = NULL;
while(NULL != p)
{
p1 = p->pNext;
free(p);
p = p1;
}
}

//组合两个有序链表(增序)
PSTRU_NODE Combine(PSTRU_NODE pLink1, PSTRU_NODE pLink2)
{
PSTRU_NODE pL1 = pLink1;
PSTRU_NODE pL2 = pLink2;

PSTRU_NODE pOutLink = NULL;
while(NULL != pL1)
{
AddNodeToLinkByInc(&pOutLink, pL1->val);
pL1 = pL1->pNext;
}

while(NULL != pL2)
{
AddNodeToLinkByInc(&pOutLink, pL2->val);
pL2 = pL2->pNext;
}

return pOutLink;
}

int main()
{
PSTRU_NODE pLink1 = NULL;
PSTRU_NODE pLink2 = NULL;
PSTRU_NODE pCombineLink = NULL;

for(int i = 0; i < 5; i++)
{
AddNodeToLinkByInc(&pLink1, i);
AddNodeToLinkByInc(&pLink2, i + 5);
}

PrintLink(pLink1);
PrintLink(pLink2);

pCombineLink = Combine(pLink1, pLink2);
PrintLink(pCombineLink);

ClearLink(pLink1);
ClearLink(pLink2);
ClearLink(pCombineLink);

return 0;
}本回答被提问者和网友采纳