【数据结构周周练】002顺序表与链表

叁歲伎倆 2021-06-11 15:12 432阅读 0赞

**目录**

习题一：求子表并比较大小

1、题目

2、链表实现

3、顺序表实现

习题二：判断是否为子表

1、题目

2、链表实现

3、顺序表实现

--------------------

这次一共只有两道题，每道题用两种线性表：顺序表与链表分别实现，但是关于求数组长度的函数还是有待完善的，在一些编译器下编译会出问题，主要是题目的算法原理啦，如果大家能够更好的算法实现，在下面评论哦！

# 习题一：求子表并比较大小 #

## 1、题目 ##

将数组A\[\]与数组B\[\]写入线性表C与线性表D，将表头相同部分去掉得到子表，求字表并比较子表大小。规定字母表后面的大于前面的，a大于空。例：A\[10\] = \{a,b,c,d,e,f,g,h,i,j\}， B\[10\] = \{a,b,c,d,e,f,g,f,g,h\}

字表分别为： C : h,i,j;   D : f,g,h;

## 2、链表实现 ##

### 代码 ###

#define OVERFLOW -1
    
    #include <iostream>
    #include<malloc.h>
    
    using namespace std;
    
    char A[] = { 'a','b','c','d','e','f','g','h','i','j' };
    char B[] = { 'a','b','c','d','e','f','g','f','g','h' };
    
    int ArrLength(char *Arr) {
    	int i = 0;
    	while (Arr[i])
    		i++;
    	return i;
    }
    
    typedef struct LNode {
    	char elem;
    	LNode *next;
    }LNode,*LinkList;
    
    
    int InitList(LinkList &L) {
    	L = (LinkList)malloc(sizeof(LNode));
    	if (!L) {
    		return OVERFLOW;
    		cout << "未成功分配空间" << endl;
    	}
    	
    	L->next = NULL;
    	return 1;
    }
    
    int CreatList(LinkList &L,char *Arr) {
    	LinkList p = L;
    	LinkList q;
    	int sizeArr = ArrLength(Arr);
    	for (int i = 0; i < ArrLength(Arr); i++)
    	{
    		q = (LinkList)malloc(sizeof(LNode));
    		q->elem = Arr[i];
    		q->next = NULL;
    		p->next = q;
    		p = q;
    		q = p->next;
    	}
    	return 1;
    }
    
    void VisitList(LinkList L) {
    	LinkList p = L->next;
    	while (p)
    	{
    		cout << p->elem << ",";
    		p = p->next;
    	}
    	cout << endl;
    }
    
    int ChildList(LinkList &C, LinkList &D) {
    	LinkList cp = C->next;
    	LinkList dp = D->next;
    
    	while (cp->elem == dp->elem)
    	{
    		C->next = cp->next;
    		D->next = dp->next;
    		free(cp);
    		free(dp);
    		cp = C->next;
    		dp = D->next;
    	}
    	return 1;
    }
    
    int CompareList(LinkList &C, LinkList &D) {
    	if (C->next == NULL &&D->next != NULL)
    		return 1;
    	else if (C->next != NULL &&D->next == NULL)
    		return 0;
    	else if (C->next->elem < D->next->elem)
    		return 1;
    	else
    		return 0;
    }
    
    void main() {
    	LinkList C,D;
    	InitList(C);
    	InitList(D);
    	CreatList(C, A);
    	CreatList(D, B);
    	cout << "线性表C为：" << endl;
    	VisitList(C);
    	cout << "线性表D为：" << endl;
    	VisitList(D);
    
    	ChildList(C, D);
    	cout << "线性表C的字表为：" << endl;
    	VisitList(C);
    	cout << "线性表D的字表为：" << endl;
    	VisitList(D);
    	if (CompareList(C, D))
    		cout << "C 表的子表小" << endl;
    	else
    		cout << "D 表的子表小" << endl;
    }

### 执行结果 ###

![70][]

## 3、顺序表实现 ##

### 代码 ###

#define OVERFLOW -1
    #define LISTMAXSIZE 20
    #define LISTINCREMENT 5
    
    #include <iostream>
    #include<malloc.h>
    using namespace std;
    typedef char ElemType;
    typedef struct {
    	ElemType * elem;
    	int length;
    	int ListSize;
    }SqList;
    
    char A[] = { 'a','b','c','d','e','f','g','h','i','j' };
    char B[] = { 'a','b','c','d','e','f','g','f','g','h' };
    
    int ArrLength(char *Arr) {
    	int i = 0;
    	while (Arr[i])
    		i++;
    	return i;
    }
    
    int Min(int a, int b) {
    	if (a < b)
    		return a;
    	else
    		return b;
    }
    
    int InitSqList(SqList &L) {
    	L.elem = (ElemType *)malloc(LISTMAXSIZE * sizeof(SqList));
    	// S.elem = (ElemType *)malloc(MAXLISTSIZE * sizeof(SqList));
    	if (!L.elem)
    	{
    		cout << "空间分配失败" << endl;
    		return OVERFLOW;
    	}
    	L.length = 0;
    	L.ListSize = LISTMAXSIZE;
    	return 1;
    }
    
    int CreatSqList(SqList &L, char *Arr) {
    	for (int i = 0; i < ArrLength(Arr); i++)
    	{
    		if (L.length == L.ListSize)
    		{
    			ElemType * newElem = (ElemType *)realloc(L.elem, (L.ListSize + LISTINCREMENT) * sizeof(SqList));
    			if (!newElem)
    			{
    				cout << "空间分配失败" << endl;
    				return OVERFLOW;
    			}
    			L.elem = newElem;
    			L.ListSize += LISTINCREMENT;
    		}
    		L.elem[i] = Arr[i];
    		L.length++;
    	}
    	return 1;
    }
    
    int ChildSqList(SqList &C, SqList &D) {
    	int k = 0;
    	int i = 0;
    	while (C.elem[i] == D.elem[i] && i < Min(C.length, D.length)) {
    		k++;
    		i++;
    	}
    	for ( i = k; i < C.length; i++)
    	{
    		C.elem[i-k] = C.elem[i];
    	}
    	for (i = k; i < D.length; i++)
    	{
    		D.elem[i - k] = D.elem[i];
    	}
    	C.length -= k;
    	D.length -= k;
    	return 1;
    }
    
    int CompareSqList(SqList &C, SqList &D) {
    	if (C.elem[0] == NULL && D.elem[0] != NULL)
    	{
    		return 1;
    	}
    	else if(C.elem[0] != NULL && D.elem[0] == NULL)
    	{
    		return 0;
    	}
    	else if (C.elem[0] < D.elem[0])
    	{
    		return 1;
    	}
    	else
    	{
    		return 0;
    	}
    }
    void VisitSqList(SqList &L) {
    	for (int i = 0; i < L.length; i++)
    	{
    		cout << L.elem[i] << ",";
    	}
    	cout << endl;
    }
    
    void main() {
    	SqList C,D;
    	InitSqList(C);
    	InitSqList(D);
    	CreatSqList(C, A);
    	CreatSqList(D, B);
    	cout << "线性表C为：" << endl;
    	VisitSqList(C);
    	cout << "线性表D为：" << endl;
    	VisitSqList(D);
    
    	ChildSqList(C, D);
    	cout << "线性表C的字表为：" << endl;
    	VisitSqList(C);
    	cout << "线性表D的字表为：" << endl;
    	VisitSqList(D);
    	if (CompareSqList(C, D))
    		cout << "C 表的子表小" << endl;
    	else
    		cout << "D 表的子表小" << endl;
    }

### 执行结果 ###

![70 1][]

# 习题二：判断是否为子表 #

## 1、题目 ##

A:123456789;     B:456;      C:457;

判断B，C是否为A的连续子序列（字表）。

## 2、链表实现 ##

### 代码 ###

#include <iostream>
    #include<malloc.h>
    using namespace std;
    
    int A[] = { 1,2,3,4,5,6,7,8,9 };
    int B[] = { 4,5,6 };
    int C[] = { 4,5,7 };
    
    int ArrLength(int *Arr) {
    	int i = 0;
    	while (Arr[i]) {
    		//cout << (Arr[i]);
    		i++;
    	}
    	return i;
    }
    
    //template<class T>
    //int ArrLength1(T& Arr) {
    //	return sizeof(Arr) / sizeof(Arr[0]);
    //}
    
    typedef struct LNode {
    	int elem;
    	LNode *next;
    }LNode, *LinkList;
    
    int InitList(LinkList &L) {
    	L = (LinkList)malloc(sizeof(LNode));
    	if (!L)
    	{
    		cout << "空间分配失败" << endl;
    		return OVERFLOW;
    	}
    	L->next = NULL;
    	return 1;
    }
    
    int CreatList(LinkList &L,int* Arr) {
    	LinkList p = L;
    	LinkList q;
    	int length = ArrLength(Arr);
    	for (int i = 0; i <length; i++)
    	{
    		q = (LinkList)malloc(sizeof(LNode));
    		if (!q)
    		{
    			cout << "空间分配失败" << endl;
    			return OVERFLOW;
    		}
    		q->elem = Arr[i];
    		q->next = NULL;
    		p->next = q;
    		p = q;
    	}
    	return 1;
    }
    
    int JudgeContinuationChildList(LinkList Parent, LinkList Child) {
    	LinkList P = Parent->next;
    	LinkList C = Child->next;
    	while (C && P)
    	{
    		if (C->elem == P->elem)
    			C = C->next;
    		else if (C)
    			C = Child->next;
    		P = P->next;
    	}
    	if (C)
    		return 0;
    	else
    		return 1;
    }
    
    void VisitList(LinkList L) {
    	LinkList p = L->next;
    	while (p)
    	{
    		cout << p->elem << ","  ;
    		p = p->next;
    	}
    	cout << endl;
    }
    
    void main() {
    
    	LinkList LA, LB, LC;
    	InitList(LA);
    	CreatList(LA, A);
    	InitList(LB);
    	CreatList(LB, B);
    	InitList(LC);
    	CreatList(LC, C);
    	cout << "线性表A为：" << endl;
    	VisitList(LA);
    	cout << "线性表B为：" << endl;
    	VisitList(LB);
    	cout << "线性表C为：" << endl;
    	VisitList(LC);
    	cout << "A:" << ArrLength(A) << endl;
    	cout << "B:" << ArrLength(B) << endl;
    	cout << "C:" << ArrLength(C) << endl;
    
    	if (JudgeContinuationChildList(LA,LB))
    	{
    	cout << "线性表 B 是 A 的连续子序列" << endl;
    	}
    	else
    	{
    	cout << "线性表 B 不是 A 的连续子序列" << endl;
    	}
    
    	if (JudgeContinuationChildList(LA, LC))
    	{
    	cout << "线性表 C 是 A 的连续子序列" << endl;
    	}
    	else
    	{
    	cout << "线性表 C 不是 A 的连续子序列" << endl;
    	}
    
    }

### 执行结果 ###

![70 2][]

**注，该代码在别人的电脑上编译时出现了一些问题，与编译器、编译环境有关，解决方案为，修改求数组长度的方式，该方式不适合int型数组。大家可以尝试一下。**

## 3、顺序表实现 ##

### 代码 ###

#define LISTMAXSIZE 20
    #define LISTINCREMENT 5
    
    #include <iostream>
    #include<malloc.h>
    using namespace std;
    
    int A[] = { 1,2,3,4,5,6,7,8,9 };
    int B[] = { 4,5,6 };
    int C[] = { 4,5,7 };
    
    template<class T>
    int ArrLength1(T& Arr) {
    	return sizeof(Arr) / sizeof(Arr[0]);
    }
    int ArrLength(int *Arr) {
    	int i = 0;
    	while (Arr[i])
    		i++;
    	return i;
    }
    
    typedef struct {
    	int * elem;
    	int length;
    	int listsize;
    }SqList;
    
    int InitSqList(SqList &S) {
    	S.elem = (int *)malloc(LISTMAXSIZE * sizeof(SqList));
    	if (!S.elem) {
    		cout << "空间分配失败" << endl;
    		exit(OVERFLOW);
    	}
    	S.length = 0;
    	S.listsize = LISTMAXSIZE;
    }
    
    int CreatSqList(SqList &S, int *A) {
    	for (int i = 0; i < ArrLength(A); i++)
    	{
    		if (S.length == S.listsize)
    		{
    			int *newElem = (int*)realloc(S.elem, (S.listsize + LISTINCREMENT) * sizeof(SqList));
    			if (!newElem)
    			{
    				cout << "空间分配失败" << endl;
    				exit(OVERFLOW);
    			}
    			S.elem = newElem;
    			S.listsize += LISTINCREMENT;
    		}
    		S.elem[i] = A[i];
    		S.length++;
    	}
    	return 1;
    }
    
    void VisitSqList(SqList &S) {
    	for (int i = 0; i < S.length; i++)
    	{
    		cout << S.elem[i] << ",";
    	}
    	cout << endl;
    }
    
    int JudgeContinuationChildList(SqList Parent, SqList Child) {
    	int i = 0;
    	int j = 0;
    	while (i < Parent.length && j < Child.length)
    	{
    		if (Parent.elem[i]  == Child.elem[j])
    		{
    			i++;
    			j++;
    		}
    		else if (j!=0)
    		{
    			j = 0;
    		}
    		else
    		{
    			i++;
    		}
    	}
    	if (j == Child.length)
    		return 1;
    	else
    		return 0;
    }
    
    void main() {
    
    	SqList LA, LB, LC;
    	InitSqList(LA);
    	CreatSqList(LA, A);
    	InitSqList(LB);
    	CreatSqList(LB, B);
    	InitSqList(LC);
    	CreatSqList(LC, C);
    	cout << "线性表A为：" << endl;
    	VisitSqList(LA);
    	cout << "线性表B为：" << endl;
    	VisitSqList(LB);
    	cout << "线性表C为：" << endl;
    	VisitSqList(LC);
    	cout << "A:" << ArrLength(A) << endl;
    	cout << "B:" << ArrLength(B) << endl;
    	cout << "C:" << ArrLength(C) << endl;
    
    	if (JudgeContinuationChildList(LA, LB))
    	{
    		cout << "线性表 B 是 A 的连续子序列" << endl;
    	}
    	else
    	{
    		cout << "线性表 B 不是 A 的连续子序列" << endl;
    	}
    
    	if (JudgeContinuationChildList(LA, LC))
    	{
    		cout << "线性表 C 是 A 的连续子序列" << endl;
    	}
    	else
    	{
    		cout << "线性表 C 不是 A 的连续子序列" << endl;
    	}
    }

### 执行结果 ###

![70 3][]

[70]: /images/20210516/6b850f7ba0144530ae6e3ec77f9aeadd.png
[70 1]: /images/20210516/ec7ef574d6544c45bc670531e5e813e5.png
[70 2]: /images/20210516/519e72c110c94210ae384a47fe348c9e.png
[70 3]: /images/20210516/666dc0caad3748faaee7fbaa417852d7.png