利用线性表的基本运算,实现如果在线性表A中出现的元素,在线性表B中也出现,则将A中该元素删除。,也就是求两个线性表的差集。
SeqList.h
#pragma once
#define ListSize 200
#include <iostream>
using namespace std;
typedef int DataType;
typedef struct
{
DataType list[ListSize];
int length;
}SeqList;
//初始化线性表
void InitList(SeqList *L)
{
L->length = 0;//把线性表长度置为0
}
//判断线性表是否为空,线性表为空返回1,否则返回0
int ListEmpty(SeqList L)
{
if (L.length == 0)
return 1;
else
return 0;
}
//按照序号查找
int GetElem(SeqList L, int i, DataType *e)
/*查找线性表中第i个元素,查找成功返回给e,并返回1表示成功,否则返回-1,表示失败*/
{
if (i<1 || i>L.length)
return -1;
else
*e = L.list[i - 1];
return 1;
}
//按照内容查找
int LocateElem(SeqList L, DataType e)
{
int i;
for (i = 0; i < L.length; i++)/*从第一个元素开始与e进行比较*/
if (L.list[i] == e) /*若存在与e相等的元素*/
return i + 1; /*返回该元素的在线性表中的序号*/
return 0; /*否则,返回0 */
}
//插入操作
int InsertList(SeqList *L, int i, DataType e)
/*在顺序表中的第i个位置插入元素e,插入成功返回1,插入不合法返回-1,顺序表满返回0.*/
{
int j;
if (i<1||i>L->length+1)/*在插入元素前,判断插入位置是否合法*/
{
cout <<"插入位置"<<i<<"不合法!" << endl;
return -1;
}
else if (L->length>=ListSize)/*在插入元素之前,判断顺序表是否已经满,不能插入元素*/
{
cout << "顺序表已经满,不能插入元素。" << endl;
return 0;
}
else
{
for (j = L->length; j >= i; j--)
/*将第i个位置以后的元素依次后移*/
{
L->list[j] = L->list[j - 1];
}
L->list[i - 1] = e;
L->length = L->length + 1;
return 1;
}
}
/*删除操作,删除第i个元素*/
int DeleteList(SeqList *L, int i, DataType *e)
{
int j;
if (L->length<=0)
{
cout << "顺序表表已空,不能进行删除!" << endl;
return 0;
}
else if (i<1||i>L->length)
{
cout << "删除位置不合适!" << endl;
return -1;
}
else
{
*e = L->list[i - 1];
for (j = i; j <= L->length - 1;j++)
{
L->list[j - 1] = L->list[j];
}
L->length = L->length - 1;
return 1;
}
}
/*求线性表的长度*/
int ListLength(SeqList L)
{
return L.length;
}
/*清空顺序表*/
void ClearList(SeqList *L)
{
L->length = 0;
}
main.cpp
/*求两个线性表的差集*/
#include"SeqList.h"
/*删除A中出现B的元素的函数声明*/
void DelElem(SeqList *A, SeqList B);
void main()
{
int i, j, flag;
DataType e;
/*声明顺序表A,B*/
SeqList A, B;
/*初始化顺序表*/
InitList(&A);
InitList(&B);
/*插入顺序表A中10个数*/
for ( i = 1; i <= 10; i++)
{
if (InsertList(&A, i, i*2+10)==0)
{
cout << "位置不合法!" << endl;
return;
}
}
/*插入顺序表B中8个数*/
for ( i = 1,j=10; i <= 8;j=j+2, i++)
{
if (InsertList(&B,i,j+i*2)==0)
{
cout << "位置不合法!" << endl;
return;
}
}
cout << "顺序表A中的元素:" << endl;
for ( i = 1; i <= A.length; i++)
{
flag = GetElem(A, i, &e);
if (flag==1)
{
cout << e << " ";
}
}
cout << endl;
cout << "顺序表B中的元素:" << endl;
for ( i = 1; i <= B.length; i++)
{
flag = GetElem(B, i, &e);
if (flag == 1)
{
cout << e << " ";
}
}
cout << endl;
cout << "将A中出现在B中的元素删除后, A剩余的元素(A-B):" <<endl;
DelElem(&A, B);
/*显示删除后A中的所有的元素*/
for ( i = 1; i <= A.length; i++)
{
flag = GetElem(A, i, &e);
if (flag==1)
{
cout << e << " ";
}
}
cout << endl;
getchar();
}
/*求A-B,删除A中含有B中元素剩下的A*/
void DelElem(SeqList *A, SeqList B)
{
int i, flag, pos;
DataType e;
for (i = 1; i <= B.length; i++)
{
flag = GetElem(B, i, &e);/*依次把B中元素取出来给e*/
if (flag==1)
{
pos = LocateElem(*A, e); /*在A中查找e*/
if (pos > 0) /*如果该元素存在*/
{
DeleteList(A, pos, &e);/*删除该元素*/
}
}
}
}
结果: