数据结构：顺序表和链表的实现和应用

快来打我* 2023-06-26 08:18 2阅读 0赞

## **实验内容：** ##

1. 采用递增有序的顺序表表示集合，求解两个集合的交集

（1）定义顺序表的存储结构；

（2）实现存储递增有序集合的顺序表的建立、求交集运算；

2. 采用递增有序的链表表示集合，求解两个集合的交集

（1）定义链表的存储结构；

（2）实现存储递增有序集合的链表的建立、求交集运算；

3. 比较顺序表和链表的优缺点和适用场合

## **实验代码：** ##

1.顺序表

#include<stdio.h>
    #include<iostream>
    using namespace std;
    
    #define InitSize 20//表长度的初始定义
    
    typedef int ElemType;
    typedef struct {
    	ElemType* data;//指示动态分配数组的指针
    	int MaxSize;//数组的最大容量
    	int Length;//数组当前个数
    }SqList;//动态分配数组顺序表的类型定义
    
    //初始化顺序表
    SqList InitList(SqList& L) {
    	L.data = new ElemType[InitSize];//C++的初始动态分配语句
    	if (!L.data) {
    		printf("初始化失败");
    		exit(OVERFLOW);
    	}
    	L.Length = 0;
    	L.MaxSize = InitSize;
    	return L;
    }
    //创建顺序表
    SqList CreateList(SqList& L) {
    	int n;
    	printf("需要输入的顺序表的个数为：");
    	scanf_s("%d", &n);
    	for (int i = 0; i < n; i++) {
    		scanf_s("%d",&L.data[i]);
    		L.Length++;
    	}
    	return L;
    }
    //显示顺序表
    void DisplayList(SqList L) {
    	for (int i = 0; i < L.Length; i++) {
    		printf("%d", L.data[i]);
    		printf(" ");
    	}
    	printf("\n\n");
    }
    //求交集
    void InterSection(SqList &L1, SqList &L2,SqList &L3) {
    	int i = 0,j = 0,k=0;
    	while (i < L1.Length && j < L2.Length) {
    		if (L1.data[i] == L2.data[j]) {  //如果L1和L2的元素相等，则记录到L3
    			L3.data[k] = L1.data[i];
    			i++;
    			j++;
    			k++;
    		}
    		else {
    			if (L1.data[i] < L2.data[j])//如果L1的元素<L2的元素，则记录L1的i值加一
    				i++;
    			else                        //如果L1的元素>L2的元素，则记录L2的j值加一
    				j++;
    		}
    		L3.Length = k;                  //重新定义下L3的长度
    	}
    }
    
    //主函数
    int main() {
    	SqList L1,L2,L3;
    
    	//初始化并创建顺序表L1
    	InitList(L1);
    	CreateList(L1);
    	printf("创建的第一个顺序表L1为：");
    	DisplayList(L1);
    
    	//初始化并创建顺序表L2
    	InitList(L2);
    	CreateList(L2);
    	printf("创建的第二个顺序表L2为：");
    	DisplayList(L2);
    
    	//求顺序表L1和顺序表L2的交集
    	InitList(L3);
    	InterSection(L1, L2, L3);
    	printf("顺序表L1和顺序表L2的交集为：");
    	DisplayList(L3);
    	return 0;
    }

2.单链表

#include<iostream>
    using namespace std;
    
    typedef int ElemType;
    typedef struct LNode {//定义单链表结点类型
    	ElemType data;//数据域
    	struct LNode* next;//指针域
    }LNode,*LinkList;
    
    //初始化单链表
    LinkList InitList() {
    	LinkList L;
    	L = (LNode*)malloc(sizeof(LNode));
    	if (L == NULL) {
    		printf("初始化失败！\n");
    		exit(1);
    	}
    	L->next = NULL;
    	return L;
    }
    
    //用尾插法建立单链表
    LinkList List_TailInsert(LinkList& L) {
    	//从表头到表尾正向建立单链表L，每次均在表尾插入元素
    	int x;//设元素类型为整型
    	L = (LinkList)malloc(sizeof(LNode));
    	LNode* s, * r = L;//r为表尾指针
    	scanf_s("%d", &x);//输入结点的值
    	while (x != -1) {//输入-1表示结束
    		s = (LNode*)malloc(sizeof(LNode));
    		s->data = x;
    		r->next = s;
    		r = s;//r指向新的表尾结点
    		scanf_s("%d", &x);
    	}
    	r->next = NULL;//尾结点指针置空
    	return L;
    }
    
    //打印单链表
    void PrintList(LinkList L) {
    	LNode* p;
    	p = L->next;
    	while (p != NULL) {
    		printf("%d->", p->data);
    		p = p->next;
    	}
    	printf("\n");
    }
    
    //单链表求交集
    void InterSection(LinkList A, LinkList B, LinkList &C) {
    	//本算法产生单链表A和B的公共元素的单链表C
    	C = InitList();
    	LNode* p = A->next, * q = B->next, * r, * s;
    	C = (LinkList)malloc(sizeof(LNode));//建立表C
    	r = C;//r始终指向C的尾结点
    	while (p != NULL && q != NULL) {//循环跳出条件
    		if (p->data < q->data)
    			p = p->next;//若A的当前元素较小，后移指针
    		else if (p->data > q->data)
    			q = q->next;//若B的当前元素较小，后移指针
    		else {//找到公共元素结点
    			s = (LNode*)malloc(sizeof(LNode));
    			s->data = p->data;//复制产生结点*s
    			r->next = s;//将*s链接到C上（尾插法）
    			r = s;
    			p = p->next;//表A和B继续向后扫描
    			q = q->next;
    		}
    	}
    	r->next = NULL;//置C尾结点指针为空
    }
    
    //主函数
    int main() {
    	LinkList L1,L2,L3;//单链表的头指针
    
    	//创建第一个单链表
    	L1 = InitList();
    	printf("以输入-1结束，用头插法创建的第一个单链表为：");
    	L1 = List_TailInsert(L1);
    	PrintList(L1);
    
    	//创建第二个单链表
    	L2 = InitList();
    	printf("以输入-1结束，用头插法创建的第一个单链表为：");
    	L2 = List_TailInsert(L2);
    	PrintList(L2);
    
    	//求交集
    	L3 = InitList();
    	printf("两个单链表的交集为：");
    	InterSection(L1, L2, L3);
    	PrintList(L3);
    }

## **实验结果：** ##

1.顺序表

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoZW5oYWliYl8_size_16_color_FFFFFF_t_70][]

2.单链表

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoZW5oYWliYl8_size_16_color_FFFFFF_t_70 1][]

## **实验总结：** ##

1.线性表的顺序存储类型描述中有ElemType的元素类型，但是在VC中需要typedef int ElemType，才能使用，否则会出现未定义标识符ElemType

2.出现C6031 返回值被忽略: "scanf"的原因是因为在ANSI C中没有scanf\_s(),只有scanf()，但是scanf()在读取时不检查边界，所以可能会造成内存泄露。于是Microsoft公司在VS中提供了scanf\_s()，所以只需要把把scanf换为scanf\_s就可以解决问题了

3.出现引发了未经处理的异常:写入访问权限冲突的问题是因为没有初始化顺序表，所以只需要InitList(L);就可以解决这个问题了

4.LinkList和LNode\*不同名字的同一个指针类型，LinkList类型的指针变量head表示他是单链表的头指针，LNode \*类型的指针变量p表示它是指向某一结点的指针

5.求单链表的交集时打印的结果一直出不来，困扰了好久，后来上网查找，比对了别人的代码，发现自己缺少了一个&，导致对链表修改的失败，打印不出来结果

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoZW5oYWliYl8_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191230220200778.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoZW5oYWliYl8=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoZW5oYWliYl8_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20191230220200802.jpeg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoZW5oYWliYl8=,size_16,color_FFFFFF,t_70