数据结构实验一——顺序表的相关操作

#include<iostream>
#include<algorithm>
#include<stdlib.h>
#include<set>

using namespace std;

struct ListNode {
	int data;
	ListNode *Next;
};

typedef ListNode * List;
typedef int ElementType;

//返回表长
int ListLength(List L) {
	int cnt = 0;
	List p = L;
	while (p) {
		cnt++;
		p = p->Next;
	}
	return cnt;
}

//返回元素的值
int GetElem(List L, ElementType pos) {
	List p = L;
	for (int i = 0; i < pos - 1; i++)
		p = p->Next;
	return p->data;
}

//查找表中是否有对应元素
bool LocateElem(List L, ElementType v) {
	List p = L;
	while (p) {
		if (p->data == v)
			return true;
		p = p->Next;
	}
	return false;
}

//链表插入
void ListInsert(List L, ElementType pos, ElementType v) {
	List p = L;
	for (int i = 1; i < pos - 1; i++)
		p = p->Next;
	List temp = (List)malloc(sizeof(ListNode));
	temp->data = v;
	temp->Next = p->Next;
	p->Next = temp;
}

//链表打印及去重排序
void PrintList(List L) {
	set<int> s;
	bool flag = false;
	List p = L;
	while (p) {
		printf("%s%d", flag ? " " : "", p->data);
		flag = true;
		p = p->Next;
	}
	cout << endl;
	p = L;
	flag = false;
	printf("去重后的元素：");
	while (p) {
		s.insert(p->data);
		p = p->Next;
	}
	for (set<int>::iterator it = s.begin(); it != s.end(); it++) {
		printf("%s%d", flag ? " " : "", *it);
		flag = true;
	}
	cout << endl;
	p = L;
	flag = false;
	printf("排序后的元素为：");
	for (auto it : s) {
		printf("%s%d", flag ? " " : "", it);
		flag = true;
	}
	cout << endl;
}

void PrintList2(List L) {
	bool flag = false;
	List p = L;
	while (p) {
		printf("%s%d", flag ? " " : "", p->data);
		flag = true;
		p = p->Next;
	}
	cout << endl;
}

//链表创建
List create(char id) {
	ElementType all;
	printf("请输入集合%c的元素个数：%c = ", id, id + 23);
	scanf("%d", &all);
	printf("请输入集合%c的元素：", id);
	List head, p;//头插法创建链表
	head = NULL;
	p = head;
	for (int i = 0; i < all; i++) {
		int n;
		cin >> n;
		p = (List)malloc(sizeof(struct ListNode));
		p->data = n;
		p->Next = head;
		head = p;
	}
	printf("集合%c中的元素为：", id);
	PrintList(head);
	return head;
}

//这个求并集的算法还是有些问题，待我日后再改。
void UnionList(List a, List b) {
	int lena = ListLength(a), lenb = ListLength(b);
	for (int i = 1; i <= lenb; i++) {
		ElementType v = GetElem(b, i);
		if (!LocateElem(a, v))
			ListInsert(a, ++lena, v);
	}
	printf("合并后的集合为：");
	PrintList2(a);

}

int main() {
	List La = create('A');
	List Lb = create('B');
	UnionList(La, Lb);
	system("pause");
	return 0;
}

运行结果如下：

溜了溜了，第一遍没上传过来，很气。

好了，作为不食言的我，今天决定传上来顺序表的操作，这个表实现了所有功能。

#include <iostream>
#include <stdlib.h>
#include <set>
using namespace std;
#define MAXSIZE 20
#define ERROR -1 
set<int> s1, s2,s3,s4,s5;
int book[1000];
typedef int ElementType;
typedef int Position;
typedef struct LNode *List;
struct LNode {
	ElementType Data[MAXSIZE];
	Position Last; /* 保存线性表中最后一个元素的位置 */
};
int cnt = 0;
List MakeEmpty();
void createList(List L);
void PrintList(List L);
void PrintList2(List L);

int main()
{
	List L,L2;
	ElementType X;
	Position P;
	int N;
	L = MakeEmpty();
	printf("请输入A集合的元素个数：");
	createList(L);
	PrintList(L);
	L2 = MakeEmpty();
	printf("请输入B集合的元素个数：");
	createList(L2);
	PrintList2(L2);
	printf("有序集合A:");
	for (auto it : s1) cout<<it <<" ";
	cout << endl;
	printf("有序集合B:");
	for (auto it : s2) cout<<it<<" ";
	cout << endl;
	s4 = s1;
	s5 = s2;
	s3 = s1;
	printf("AB的并集为：");
	for (auto it : s2) {
		if (book[it] == 0) {
			L->Last++;
			s1.insert(it);
		}		
	}
	for (auto it:s1) cout << it <<" ";
	cout << endl;
	printf("AB的交集为：");
	for(auto it:s3)
		for (auto it2 : s2) {
			if (it == it2)
				cout << it << " ";
		}
	cout << endl;
	printf("A-B的差积为：");
	for (auto it : s2) {
		if (book[it] == 1)
			s3.erase(it);
	}	
	for (auto it : s3) cout << it <<" ";
	cout << endl;
	printf("B-A的差积为：");
	for (auto it : s4) {
		if (book[it] == 1)
			s5.erase(it);
	}
	for (auto it : s5) cout << it <<" ";
	cout << endl;
	system("pause");
	return 0;
}

List MakeEmpty() {
	List p;
	p = (List)malloc(sizeof(struct LNode));
	p->Last = -1;
	return p;
}
void createList(List L) {
	int n;
	cin >> n;
	printf("请输入集合的元素：");
	if (cnt == 1) {
		for (int i = 1; i <= n; i++)
		{
			cin >> L->Data[i];
			L->Last = i;
			s2.insert(L->Data[i]);
		}
	}
	else {
		for (int i = 1; i <= n; i++)
		{
			cin >> L->Data[i];
			L->Last = i;
			s1.insert(L->Data[i]);
			book[L->Data[i]] = 1;
		}
	}
	cnt++;
}

void PrintList(List L) {
	printf("原集合的元素为：");
	for (int i = 1; i <= L->Last; i++)
		cout << L->Data[i] <<" ";
	cout << endl;
	printf("集合去重后剩余元素个数：");
	int cnt = 0;
	for (auto it : s1) cnt++;
	cout << cnt<<endl;
	printf("集合去重后剩余元素：");
	for (auto it : s1)
		cout << it << " ";
	cout << endl;
}
void PrintList2(List L) {
	printf("原集合的元素为：");
	for (int i = 1; i <= L->Last; i++)
		cout << L->Data[i] << " ";
	cout << endl;
	printf("集合去重后剩余元素个数：");
	int cnt = 0;
	for (auto it : s2) cnt++;
	cout << cnt << endl;
	printf("集合去重后剩余元素：");
	for (auto it : s2)
		cout << it << " ";
	cout << endl;
}

下附运行结果：