数据结构实验3--数组与广义表

本系列文章广泛借鉴了各种教材和博客文章，由于完成时间比较久远，如果有遗漏标注的请联系我补充或删除解答。本文中解答仅供参考学习。

其他章节实验见：分类 - 数据结构 - Loststar’s blog

鞍点问题

题目

若矩阵A中的某一元素A[i,j]是第i行中的最小值，而又是第j列中的最大值，则称A[i,j]是矩阵A中的一个鞍点。写出一个可以确定鞍点位置的程序。

解答

#include<stdio.h>
#define m 3
#define n 3
int arr[m][n] = { //矩阵
	30,40,11,
	2,5,6,
	1,8,9
};
int main()
{
	for (int i = 0; i < m; i++)
	{
		int dstI = i, dstJ = 0;
		int minX = arr[i][0];
		
		//找第i行的最小值(dstX,dstY)
		for (int j = 0; j < n; j++)
		{
			if (arr[i][j] < minX) 
			{
				minX = arr[i][j];
				dstI = i;
				dstJ = j;
			}
		}

		int maxY = arr[dstI][dstJ],flag=1;

		//遍历dstJ列，查找有没有比arr[dstI][dstJ]大的数
		for (int j = 0; j < m; j++)
		{
			if (arr[j][dstJ] > maxY)
			{
				flag = 0;
				break;
			}
		}
		
		if (flag == 1)
		{
			flag = 0;
			printf("(%d,%d)", dstI, dstJ);
		}
	}
}

运行结果

得到鞍点。在上文提到的测试矩阵中是(0,2)。

稀疏矩阵转置

题目

输入稀疏矩阵中每个元素的行号、列号、值，建立稀疏矩阵的三元组存储结构，并将此矩阵转置，显示转置前后的三元组结构。

解答

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#define  MAXSIZE  12500
typedef struct {
	int  i, j;      //该非零元的行下标和列下标
	int value;    // 该非零元的值
} Triple;  // 三元组类型
typedef struct {
	Triple data[MAXSIZE + 1];
	int iTot;
	int jTot;
	int	numTot; //行数，列数，非零元个数
} TSMatrix;  // 稀疏矩阵类型

int TransposeSMatrix(TSMatrix M, TSMatrix &T)
{
	T.iTot = M.jTot;
	T.jTot = M.iTot;
	T.numTot = M.numTot;
	int q = 1;
	if (T.numTot!=0)
	{
		for (int col = 1; col <= M.jTot; col++)
		{
			for (int p = 1; p <= M.numTot; p++)
			{
				if (M.data[p].j == col)
				{
					T.data[q].i = M.data[p].j;
					T.data[q].j = M.data[p].i;
					T.data[q].value = M.data[p].value;
					q++;
				}
			}
		}
	}
	return 0;
}
int ShowSMatrix(TSMatrix M)
{
	int p = 1;
	for (int i = 1; i <= M.iTot; i++)
	{
		for (int j = 1; j <= M.jTot; j++)
		{
			if (M.data[p].i == i && M.data[p].j == j)
			{
				printf("%d ", M.data[p].value);
				p++;
			}
			else
			{
				printf("0 ");
			}
		}
		printf("\n");
	}
	return 0;
}
int main()
{
	TSMatrix M, T;
	int a, b, c;
	printf("行数、列数、非零元个数：\n");
	scanf("%d %d %d", &M.iTot, &M.jTot, &M.numTot);
	for (int temp = 1; temp <= M.numTot; temp++)
	{
		scanf("%d %d %d", &M.data[temp].i, &M.data[temp].j, &M.data[temp].value);
	}
	printf("转置前\n");
	ShowSMatrix(M);
	TransposeSMatrix(M, T);
	printf("转置后\n");
	ShowSMatrix(T);
}

运行结果

广义表

题目

用头尾链表存储表示法建立广义表，输出广义表，求广义表的表头、广义表的表尾和广义表的深度。

解答

这题我当时不会，大部分对着博客（广义表的创建 喜爱兰兰-CSDN博客 创建广义表）学然后默写调通。现在把默写部分替换回原作者带有清晰注释的部分。求深度部分来自严蔚敏《数据结构》。

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX_STR_LEN 100
typedef char AtomType;
typedef enum { ATOM, LIST } ElemTag;
// ATOM==0:原子, LIST==1:子表
typedef struct GLNode {
	ElemTag  tag;   // 标志域
	union {
		AtomType  atom;      // 原子结点的数据域
		struct { struct GLNode *hp, *tp; } ptr;
	};
} *GList;

char hstr[MAX_STR_LEN], istr[MAX_STR_LEN];

void SubString(char *substr, char *inputstr, int start, int end) 
{	//截取字符串中间内容，本程序中主要用于去头尾括号
	for (char *temp = inputstr + start; temp <= inputstr + end; temp++)
	{
		*substr = *temp;
		*substr++;
	}
	*substr = '\0';
}
void SplitHeadStr(char *&inputstr, char *&headstr) 
{
	//将非空串inputstr分割成两个部分，headstr为第一个','之前的子串，inputstr为之后的字串
	int n = strlen(inputstr);
	int i = 0;
	int k = 0; //记录尚为配对的左括号的个数
	do {
		//找出最高层头尾分隔点
		//由于字符串最外面没有括号，所以找到逗号的时候左右括号数应该相等，否则不是最高层
		if (inputstr[i] == '(')
			k++;
		else if (inputstr[i] == ')')
			k--;
		i++;
	} while (i < n && (inputstr[i] != ',' || k != 0));

	if (i < n) {
		SubString(headstr, inputstr, 0, i - 1);
		SubString(inputstr, inputstr, i + 1, strlen(inputstr) - 1);
	}
	else {
		strcpy(headstr, inputstr);
		inputstr = '\0'; 
	}
}
int CreateGList(GList &L, char *s)
{
	if (strcmp(s, "()") == 0)
		L = NULL; //建立空表
	else {
		L = (GList)malloc(sizeof(struct GLNode));  //新建一个表结点 
		if (L == NULL)
			return -1;
		if (strlen(s) == 1) { //原子结点 
			L->tag = ATOM;;
			L->atom = *s;
		}
		else {
			char *headstr = hstr;
			L->tag = LIST;
			SubString(s, s, 1, strlen(s) - 2); //脱去最外边的括号 
			GList pointer = L;
			do { //创建子表 
				SplitHeadStr(s, headstr); //headstr为分割后的表头，s为分割后的表尾 
				char tstr[MAX_STR_LEN];
				strcpy(tstr, headstr);
				CreateGList(pointer->ptr.hp, tstr);  //递归创建表头 
				if (s != NULL && strlen(s) != 0) {  //如果表尾不为空的话 
					GList tailnode = (GList)malloc(sizeof(struct GLNode));
					if (pointer == NULL)
						return -1;
					tailnode->tag = LIST;  //广义表的表尾肯定是一张表 
					pointer->ptr.tp = tailnode;
					pointer = tailnode; 
				} 
			} while (s != NULL && strlen(s) != 0);  //直到表尾为空NULL则退出 
			pointer->ptr.tp = NULL;  //最后将表尾赋值为NULL 
		} 
	}
	return 0;
}

void PrintGList(const GList L) {
	printf("(");
	GList pointer = L;  
	do {
		GList temp = pointer->ptr.hp;
		if (temp != NULL) {  //递归输出表头中原子结点 
			if (temp->tag == ATOM)
			{
				printf("%c", temp->atom);
			}
			else
			{
				PrintGList(temp);
			}
				
		}
		if (pointer->ptr.tp != NULL)
		{	//后面还有
			printf(",");
		}
		pointer = pointer->ptr.tp;  // 指针指向表尾,判断表尾是否空
	} while (pointer != NULL);
	printf(")");
}

int GetGListDepth(GList L)
{
	if (!L)
		return 1;//空表
	if (L->tag == ATOM)
		return 0;//原子
	int max = 0;
	for (GList pp = L; pp; pp = pp->ptr.tp) 
	{
		int dep = GetGListDepth(pp->ptr.hp);
		if (dep > max) {
			max = dep;//每次找到表中遍历到深度最大的表，并用max记录
		}
	}
	return max + 1;
}

int main() {
	char s[100];
	scanf("%s", &s);
	int left = 0, right = 0;
	for (int i = 0; i < strlen(s); i++)
	{
		if (s[i] == '(')
			left++;
		if (s[i] == ')')
			right++;
	}
	if (left != right)
	{
		printf("error");
		return -1;
	}
	strcpy(istr, s);
	GList L;
	char *head=(char*)malloc(MAX_STR_LEN*sizeof(char)), *tail=(char*)malloc(MAX_STR_LEN * sizeof(char));
	strcpy(tail, istr);
	CreateGList(L, istr);
	SubString(tail, tail, 1, strlen(tail) - 2);
	printf("广义表:");
	PrintGList(L);
	SplitHeadStr(tail, head);
	printf("\nhead:%s\ntail:%s\n",head,tail);
	printf("\n深度：%d", GetGListDepth(L));
	return 0;
}

结果