数据结构课设报告

return BiTree_leaf_nodes(T->lchild) + BiTree_leaf_nodes(T->rchild) + 1;

return BiTree_leaf_nodes(T->lchild) + BiTree_leaf_nodes(T->rchild);

struct Book {
		string name;
		string tel;
	};
	struct Node {
		Book data;
		Node * next;
	};
	Node *head;
	Node *_temp;	//用作临时结点指针方便函数调用


void Address_books::Change_contact()//修改联系人信息
{
	string info;
	cout << "输入你要修改的联系人的相关信息(姓名或联系方式):";
	cin >> info;
	if (!Find(info))
		return;
	
	else {
		cout << "输入该联系人新的姓名:";
		cin >> info;
		this->_temp->next->data.name = info;
		cout << "输入该联系人新的电话号码:";
		cin >> info;
		this->_temp->next->data.tel = info;
		cout << endl << "联系人信息更新成功!" << endl;
	}
	
}

void Address_books::Delete()//删除联系人
{
	string info;
	cout << "输入你要删除的联系人的相关信息(姓名或联系方式):";
	cin >> info;
	if (!Find(info))
		return;

	else {
		cout << "确定删除联系人 "<< _temp->next->data.name <<" 的信息吗?	(y or n)?:";
		char c;
		cin >> c;
		if (c == 'y' || c == 'Y') {
			Node *q = _temp->next;
			this->_temp->next = _temp->next->next;
			delete q;
			q = NULL;
			cout << endl << "联系人信息删除成功!" << endl;
		}
		else
			return;	
	}
}

void Address_books::Find_contact()//查找联系人
{
	string info;
	cout << "输入你要查找的联系人的相关信息(姓名或联系方式):";
	cin >> info;
	Find(info);
}

ElemType Address_books::Find(string info)
{
	Node *temp = head->next;
	this->_temp = head;	//查找第一个结点时没有进入while循环_temp为空的情况
	if (head->next == NULL)
	{
		cout << "空电话本,没有联系人!" << endl;
		return FALSE;
	}
	while (temp != NULL && temp->data.name != info && temp->data.tel!=info)
	{
		this->_temp = temp;	//_temp指向信息结点的前一个,方便删除
		temp = temp->next;	
	}
	if (!temp)
	{
		cout << "查找失败，相关联系人不存在！" << endl;
		return FALSE;
	}
	else
		cout << "查找成功，相关联系人信息如下: " << endl
		<< "姓名:" << temp->data.name << endl << "电话号码:" << temp->data.tel << endl;
	return TRUE;
}

//定义操作数栈
typedef struct OPERANDSTACK {
	int *base;
	int *top;
	int stacksize;
}OPERANDSTACK;

//定义操作符栈
typedef struct OPERATORSTACK {
	char *base;
	char *top;
	int stacksize;
}OPERATORSTACK;

//判断c是否是一个运算操作符  
bool isOperator(char c)
{
	switch (c) {
	case '+':
	case '-':
	case '*':
	case '/':
	case '(':
	case ')':
	case '#':	//将'#'作为运算符栈opter的栈底元素，判断表达式是否求值完毕
		return true;
		break;
	default:
		return false;
		break;
	}
}

//如果以*c开始的操作数后仍是数字就加上前面的数字进行合并
const char *getOpnd(const char *c, int *op)
{
	//获得以*c开始的操作数，返回后c为操作符  
	int sum = 0, temp;
	while (!isOperator(*c))
	{
		temp = *c - '0';
		sum = sum * 10 + temp;
		c++;
	}
	*op = sum;

	return c;
}

char op[7][7] =
{
{ '>', '>', '<', '<', '<', '>', '>' },
{ '>', '>', '<', '<', '<', '>', '>' },
{ '>', '>', '>', '>', '<', '>', '>' },
{ '>', '>', '>', '>', '<', '>', '>' },
{ '<', '<', '<', '<', '<', '=', ' ' },
{ '>', '>', '>', '>', ' ', '>', '>' },
{ '<', '<', '<', '<', '<', ' ', '=' }
};

//优先级的处理
char precede(char op1, char op2)
{
	int i, j; //用来记录优先级坐标点位置
	switch (op1) {
	case '+': i = 0; break;
	case '-': i = 1; break;
	case '*': i = 2; break;
	case '/': i = 3; break;
	case '(': i = 4; break;
	case ')': i = 5; break;
	case '#': i = 6; break;
	}
	switch (op2) {
	case '+': j = 0; break;
	case '-': j = 1; break;
	case '*': j = 2; break;
	case '/': j = 3; break;
	case '(': j = 4; break;
	case ')': j = 5; break;
	case '#': j = 6; break;
	}
	return op[i][j];
}

/*---稀疏矩阵的三元组顺序表存储表示---*/
struct Triple{
	int i, j;		//非零元的行下标和列下标
	ElemType e;
};

struct TSMatrix {
	Triple data[MAXSIZE];		//非零元的三元组表
	int row, col, total;		//矩阵的行数、列数、非零元个数
};

Status MultSMatrix(TSMatrix A, TSMatrix B, TSMatrix & C)
{// 将稀疏矩阵A和B进行乘法运算后赋给矩阵C
// 原理:用A的一行的元素与B的每一列的元素对应相乘再相加求解
// 时间复杂度:O(A.row*B.col+A.total/A.col*B.total)

	if (A.col != B.row)
	{
		cout << "A的列标不等于B的行标!计算失败" << endl;
		return ERROR;
	}

	C.row = A.row;
	C.col = B.col;
	C.total = 0;

	/*memset()用于逐字节的把整个数组设置为一个指定的值*/
	int* Anum = new int[A.row + 1];
	memset(Anum, 0, (A.row + 1) * sizeof(int));
	int* Arpos = new int[A.row + 1];
	memset(Arpos, 0, (A.row + 1) * sizeof(int));

	int* Bnum = new int[B.row + 1];
	memset(Bnum, 0, (B.row + 1) * sizeof(int));
	int* Brpos = new int[B.row + 1];
	memset(Brpos, 0, (B.row + 1) * sizeof(int));

	int i, arow, p, p_up, brow, q, q_up, ccol;

	for (i = 0; i < A.total; i++)
		Anum[A.data[i].i]++;
	//计算A中每行的非零元在data中的起始下标
	for (i = 1; i <= A.row; i++)
		Arpos[i] = Arpos[i - 1] + Anum[i - 1];

	for (i = 0; i < B.total; i++)
		Bnum[B.data[i].i]++;
	//计算B中每行的非零元在data中的起始下标
	for (i = 1; i <= B.row; i++)
		Brpos[i] = Brpos[i - 1] + Bnum[i - 1];

	int* mult = new int[B.col + 1];

	for (arow = 0; arow <= A.row; arow++)
	{

		p_up = arow < A.row ? Arpos[arow + 1] : A.total;	//条件表达式，若arow<A.row,执行:前一条语句，否则后一条
		for (p = Arpos[arow]; p < p_up; p++)
		{
			memset(mult, 0, (B.col + 1) * sizeof(int));

			brow = A.data[p].j;
			q_up = brow < B.row ? Brpos[brow + 1] : B.total;
			for (q = Brpos[brow]; q < q_up; q++)
			{
				mult[B.data[q].j] += A.data[p].e * B.data[q].e;
			}
			for (ccol = 1; ccol <= B.col; ccol++)
			{
				if (fabs(mult[ccol])>1e-7)
				{
					C.data[C.total].i = arow;
					C.data[C.total].j = ccol;
					C.data[C.total].e = mult[ccol];

					C.total++;
				}
			}
		}
	}
	delete[] Anum;
	delete[] Arpos;
	delete[] Bnum;
	delete[] Brpos;

	return OK;
}

#include <vector>
#include <stack>
int BiTree_leaf_nodes(BiTree T)
{
	if (T == NULL)
		return 0;
	if (T->lchild == 0 && T->rchild == 0)
		return BiTree_leaf_nodes(T->lchild) + BiTree_leaf_nodes(T->rchild) + 1;
	else
		return BiTree_leaf_nodes(T->lchild) + BiTree_leaf_nodes(T->rchild);
}

void BiTree_parents(BiTree T, char e)
{
	int count = 0;	//记录相同值的结点数
	bool root = false;	//记录结点是根节点的情况
	vector<char> v1;	//存储具有双亲结点的双亲结点值
	stack<BiTree> S;	//非递归先序遍历

	if (T == NULL)
		return;
	if (T->data == e) {
		count++;
		root = true;
	}
	while (!S.empty() || T)
	{
		while (T)
		{
			S.push(T);
			if ((T->lchild && T->lchild->data == e) || (T->rchild && T->rchild->data == e)) {
				count++;
				v1.push_back(T->data);
			}	
			T = T->lchild;
		}
		T = S.top(); S.pop();
		T = T->rchild;
	}
	cout << "该值对应的结点共有 " << count << " 个,对应的双亲为:" << endl;
	int n = 0;
	if (root) {
		cout << "第" << ++n <<"个结点为根结点,无双亲结点!" << endl;
	}
	
	for (auto i : v1) {
		cout << "第" << ++n << "个结点的双亲结点:" << i << endl;
	}
}

void Topological_sort(ALGraph G)
{
	stack<int> s;
	int i, k;
	//入度为0入栈
	for (i = 0; i < G.vexnum; ++i)
	{
		if (!G.vertices[i].count)//把入度为零的点先放入栈中
			s.push(i);
	}
	int count = 0;
	ArcNode *p = new ArcNode;
	while (!s.empty())
	{
		i = s.top();
		s.pop();
		cout << G.vertices[i].data << "-";
		count++;
		for (p = G.vertices[i].firstarc; p ; p = p->nextarc)
		{
			k = p->adjvex;
			if (!(--G.vertices[k].count))
				s.push(k);
		}
	}
	if (count < G.vexnum)
	{
		cout << "该图(网)有回路！";
		cout << endl;
	}
	else
		cout << "该图(网)无回路";
	
}

return (BiTree_depth(T->lchild) > BiTree_depth(T->rchild)) ? (BiTree_depth(T->lchild) + 1) : (BiTree_depth(T->rchild) + 1);

void BiTree_parents(BiTree T, char e)
{
	int count = 0;	//记录相同值的结点数
	bool root = false;	//记录结点是根节点的情况
	vector<char> v1;	//存储具有双亲结点的双亲结点值
	stack<BiTree> S;	//非递归先序遍历

	if (T == NULL)
		return;
	if (T->data == e) {
		count++;
		root = true;
	}
	while (!S.empty() || T)
	{
		while (T)
		{
			S.push(T);
			if ((T->lchild && T->lchild->data == e) || (T->rchild && T->rchild->data == e)) {
				count++;
				v1.push_back(T->data);
			}	
			T = T->lchild;
		}
		T = S.top(); S.pop();
		T = T->rchild;
	}
	cout << "该值对应的结点共有 " << count << " 个,对应的双亲为:" << endl;
	int n = 0;
	if (root) {
		cout << "第" << ++n <<"个结点为根结点,无双亲结点!" << endl;
	}
	for (auto i : v1) {
		cout << "第" << ++n << "个结点的双亲结点:" << i << endl;
	}
}