本文共 7970 字，大约阅读时间需要 26 分钟。

目录

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

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

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 
   
    #include
    
     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;}
    
   

执行结果

3、顺序表实现

代码

#define OVERFLOW -1#define LISTMAXSIZE 20#define LISTINCREMENT 5#include 
   
    #include
    
     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;}
    
   

执行结果

习题二：判断是否为子表

1、题目

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

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

2、链表实现

代码

#include 
   
    #include
    
     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
     
      //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 
      
       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;	}}
      
     
    
   

执行结果

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

3、顺序表实现

代码

#define LISTMAXSIZE 20#define LISTINCREMENT 5#include 
   
    #include
    
     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
     
      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;	}}
     
    
   

执行结果