目錄
- 一、題目描述
- 二、演算法
- （1）演算法思想
- （2）演算法描述
- 三、完整原始碼
- 四、運行結果展示
一、題目描述
假設利用兩個線性表 LA 和 LB 分別表示兩個集合 A 和 B （即線性表中的資料元素為集合中的成員），現要求一個新的集合 A = AUB .假如，設
LA = (7,5,3,11)
LB = (2,6,3)
合并后
LA = (7,5,3,11,2,6)
二、演算法
（1）演算法思想
擴大線性表LA，將存在于線性表LB中而不存在于LA中的資料放到線性表LA中，只要從線性表LB中依次取得每個元素，并依次在線性表LA中進行查訪，若不存在則將其插入，
（2）演算法描述
/*合并*/
void Union(LinkList& LA, LinkList& LB,int n,int m)
{
int e,a;
for (int i = 1;i <= n;i++)
{
e = GetElem(LB, i, e);//取LB中第i個元素賦值給e
a = LocateElem(LA, e);//回傳0或者1
if (a != 1 )//鏈表里面元素為空了或者沒有找到元素
ListInsert(LA,m, e);//LA中不存在和e相同的資料元素，插入
}
}
三、完整原始碼
#include<stdio.h>
#define OK 1
#define ERROR 0
typedef int ElemType;
typedef int Status;
/*定義鏈式存盤結構*/
typedef struct LNode
{
ElemType data;
struct LNode* next;
}*LinkList;
/*鏈表的初始化*/
Status InitList(LinkList& L)
{
L = new LNode;
L->next = NULL;
return OK;
}
/*創建鏈表*/
void CreateList(LinkList& L,int n)
{
LinkList p;//生成一個新結點*p
L = new LNode;
L->next = NULL;
for (int i = n;i > 0;--i)
{
p = new LNode;
printf("請輸入第%d個元素：", i);
scanf_s("%d", &p->data);//輸入元素
p->next = L->next;//新結點與后繼結點接起來
L->next = p;//新結點與前驅結點接起來
}
}
/*按序號查找元素*/
Status GetElem(LinkList L, int i, ElemType& e)
{
LinkList p;
int j = 1;
p = L->next;//初始化，p指向第一個結點
while (p && j < i)
{
p = p->next;//p向后掃描
++j;
}
if (!p || j > i) return ERROR;//i值不存在
e = p->data;//第i個元素的資料域賦值給e
return e;
}
/*查訪LA*/
Status LocateElem(LinkList L, ElemType e)
{
LinkList p;
p = L->next;//p指向頭結點
while ( p && p->data != e )//鏈表不為空且沒有找到要找元素就一直回圈
{
p = p->next;//p往下找
}
/*跳出回圈，要么是鏈表沒元素，要么是找到要找的元素*/
if (!p) return ERROR;//如果鏈表空了，回傳0
return OK;//回傳1說明找到元素了
}
/*插入到LA*/
Status ListInsert(LinkList &L,int m,ElemType &e)
{
LinkList p;
p = L;
int j = 0;
while (p && j < m)
{
p = p->next;
++j;
}
if (!p || j > m) return ERROR;
LinkList s;//新建結點
s = new LNode;
s->data = e;//存入資料域
s->next = p->next;//更改指標的位置
p->next = s;
return OK;
}
/*合并*/
void Union(LinkList& LA, LinkList& LB,int n,int m)
{
int e,a;
for (int i = 1;i <= n;i++)
{
e = GetElem(LB, i, e);//取LB中第i個元素賦值給e
a = LocateElem(LA, e);//回傳0或者1
if (a != 1 )//鏈表里面元素為空了或者沒有找到元素
ListInsert(LA,m, e);//LA中不存在和e相同的資料元素，插入
}
}
/*輸出鏈表*/
void PrintList(LinkList L)
{
LinkList p;
p = L->next;
while (p)
{
printf("%d,", p->data);
p = p->next;
}
}
int main()
{
int m, n,e;
LinkList LA, LB;//宣告兩個鏈表
InitList(LA);//初始化LA
InitList(LB);//初始化LB
printf("請輸入LA元素的個數m：");
scanf_s("%d", &m);
CreateList(LA, m);//創建LA
printf("集合LA的元素為：");
printf("LA=（");
PrintList(LA);//輸出集合LA
printf(")\n");
printf("\n");
printf("請輸入LB元素的個數n：");
scanf_s("%d", &n);
CreateList(LB, n);//創建LB
printf("集合LB的元素為：");
printf("LB=（");
PrintList(LB);//輸出集合LB
printf(")\n");
printf("\n");
printf("合并后集合為：");
Union(LA,LB,n,m);//合并LA和LB
printf("LA=（");
PrintList(LA);
printf(")\n");
return 0;
}
四、運行結果展示
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/185959.html
標籤：其他