数据结构第一次上机代码

---

报告

一般合并

在顺序表里改写 利用原有功能写出

#include<stdio.h>
#include<iostream>
#include<malloc.h>
#include<stdlib.h>
using namespace std;
#define OK 1 //通过
#define ERROR 0 //错误 
#define OVERFLOW -2 //堆栈溢出
#define LIST_INIT_SIZE 10 //线性表储存空间初始分配量
#define LISTINCREMRNT 10 //线性表储存空间的分配增量
typedef int Status; //函数类型,其值为状态码
typedef int ElemType; //抽象数据类型

					  //线性表动态分配顺序储存结构
typedef struct
{
	ElemType* elem;//储存空间基址
	int length;//当前长度
	int listsize;//当前分配的存储容量
}SqList;

//初始化一个空的表
Status InitList(SqList* L)
{

	L->elem = (ElemType*)__vcrt_malloc_normal(LIST_INIT_SIZE * sizeof(ElemType));
	if (!(L->elem))
		exit(OVERFLOW);//分配失败
	L->length = 0;//长度
	L->listsize = LIST_INIT_SIZE;//容量

	return OK;
}

//插入
Status ListInsert(SqList* L, int i, ElemType e)
{
	if (i<1 || i>L->length + 1)
		return ERROR;

	ElemType* q = &(L->elem[i - 1]), *p = NULL;// q为插入位置
	for (p = &(L->elem[L->length - 1]); p >= q; --p)
		* (p + 1) = *p;// 插入位置及之后的元素后移
	*q = e;// 插入e
	++(L->length);// 表长增加1
	if (L->length == L->listsize) {
		ElemType*  newbase = (ElemType*)realloc(L->elem, (L->listsize + LISTINCREMRNT) * sizeof(ElemType));
		if (!newbase)
			exit(OVERFLOW);
		L->elem = newbase;// 新基址
		L->listsize += LISTINCREMRNT;// 增加存储容量
	}
	return OK;
}
//获取长度
int getLength(SqList* L)
{
	return L->length;
}
//通过索引取值
ElemType getElemByIndex(SqList* L, int i)
{
	return L->elem[i - 1];
}
//通过值取索引
int getIndexByElem(SqList* L, ElemType e)
{
	for (int j = 0; j < L->length; ++j)
	{
		if ((L->elem[j]) == e)
			return j + 1;
	}
	return -1;
}

//遍历表
Status myPrintf(SqList* L)
{
	for (int i = 0; i < L->length; i++) {
		cout << "第"<< i + 1<<"个值------------" << (L->elem[i])<<endl;
		
	}
	return OK;
}
//创建表
Status creatList(SqList* L)
{
	scanf_s("%d", &(L->length));
	printf("输入为 %d\n", L->length);
	for (int i = 0; i < L->length; i++)
	{
		cin >> L->elem[i];

	}
	return OK;
}
//合并
Status mergeList(SqList* LA,SqList* LB)
{
	if (LA->length < LB->length) {
		SqList* temp;
		temp = LA;
		LA = LB;
		LB = temp;
	}
	for (int i = 0; i < LB->length; i++)
	{
		ElemType e = getElemByIndex(LB,i+1);
		if (getIndexByElem(LA, e)==-1) {
			ListInsert(LA, 1, e);
		}
	}
	printf("合并后\n");
	myPrintf(LA);
	return OK;
}
int main(void) {
	SqList* LA = (SqList*)__vcrt_malloc_normal(sizeof(SqList));
	InitList(LA);
	printf("请输入表A的长度\n");
	creatList(LA);
	myPrintf(LA);
	SqList* LB = (SqList*)__vcrt_malloc_normal(sizeof(SqList));
	InitList(LB);
	printf("请输入表B的长度\n");
	creatList(LB);
	myPrintf(LB);

	mergeList(LA, LB);
	system("pause");
	
	return 0;
}

有序集合链式合并

同样改写单链表 用了原有功能实现 改写了一个查找 可以忽略无序的单链表 相同的元素也会插入 不过可以根据写一个代码改改

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#define OK 1 //通过
#define ERROR 0 //错误 
typedef int Status; //函数类型,其值为状态码
typedef int ElemType; //抽象数据类型
					   //单链表
typedef struct LNode
{
	ElemType data;
	struct LNode *next;
}LNode, *LinkList;
//初始化
Status initList(LinkList* L)
{
	*L = (LinkList)malloc(sizeof(LNode));
	(*L)->data = 0;
	(*L)->next = NULL;
	return OK;
}
//判空
char* isEmpty(LinkList* L)
{
	return (*L)->next == NULL ? "空" : "不空";
}
//获取长度
int getLength(LinkList* L)
{
	LinkList p = *L;
	int i = 0;
	while (p->next)
	{
		++i;
		p = p->next;
	}
	return i;
}
//默认头插法建表
Status creatListHead(LinkList* L , ElemType str[],int n)
{
	LinkList p;
	(*L)->data = n;
	for (int i = 0; i <n; ++i)
	{
		p = (LinkList)malloc(sizeof(LNode));
		p->data = str[i];
		p->next = (*L)->next;
		(*L)->next = p;
	}
	return OK;
}
//默认尾插法建表 
Status creatListEnd(LinkList* L, ElemType str[], int n)
{
	LinkList p, r = *L;

	(*L)->data = n;
	for (int i = 0; i < n; ++i)
	{
		p = (LinkList)malloc(sizeof(LNode));
		p->data = str[i];
		p->next = NULL;//必须要否则遍历异常
		r->next = p;
		r = p;
	}
	return OK;
}
//遍历表
Status traversalList(LinkList L)
{
	LinkList p = L->next;
	while (p)
	{
		printf("%d ", p->data);
		p = p->next;
	}
	printf("\n");
	return OK;
}
//插入
Status insertList(LinkList* L, int i, ElemType c)
{
	if (L == NULL || (i > (*L)->data || i < 1))return ERROR;
	LinkList p = *L;
	int j = 0;
	while (p&&j<i - 1)
	{
		p = p->next;//定在前一个
		j++;
	}
	LinkList q = (LinkList)malloc(sizeof(LNode));
	q->data = c;
	q->next = p->next;
	p->next = q;
	(*L)->data++;
	return OK;
}
//按位查找
LNode* getListByIndex(LinkList L, int i)
{
	//if (L == NULL || (i > (L)->data || i < 1))return NULL;
	LinkList p = L;
	int j = 0;
	while (p&&j<i - 1)
	{
		p = p->next;//前一个

		j++;
	}
	//	p = p->next;
	return (p);//前一个
}
//按值查找
LNode* getListByElem(LinkList L, ElemType c,int* i)
{
	LinkList p = L;
	int j = 0;
	while (p&&p->next->data != c)
	{
		p = p->next;//前一个
		j++;
	}
	*i = j + 1;
	return p->next; 
};

//合并
Status mergeList(LinkList* LA, LinkList* LB )
{
	if (getLength(LA)>getLength(LB))
	{
		LinkList* temp=LA;
		LA = LB;
		LB = temp;
	}
	ElemType e;
	for (int i = 1; i <= getLength(LA); i++)
	{
		 e = getListByIndex(*LA, i)->next->data;//取元素
		//printf("___%d\n", e);
		for (int i = 1; i <= getLength(LB); i++)
		{
		//	printf("___---%d\n", i);
			if (getListByIndex(*LB, i)->next->data>e)
			{
				//printf("_----__%d\n", i);
				insertList(LB, i, e);
				break;
			};
		}
	}
	printf("合并后: ");
	traversalList(*LB);
	return OK;
}

int main(void)
{
	ElemType stra[4] = { 3,5,8,11 };
	ElemType strb[7] = { 2,6,8,9,11,15,20 };
	LinkList LA,LB;
	initList(&LA);
	initList(&LB);
	creatListEnd(&LA, stra,sizeof(stra)/sizeof(stra[0]));
	creatListEnd(&LB, strb, sizeof(strb) / sizeof(strb[0]));
	printf("表LA: ");
	traversalList(LA);
	printf("表LB: ");
	traversalList(LB);
	mergeList(&LA, &LB);
	system("pause");
	return 0;
}

一元稀疏多项式加法

改写上面的合并 实现两个稀疏多项式相加 同时不会插入相同的元素 同时添加了计算的功能

#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#define OK 1 //通过
#define ERROR 0 //错误 
typedef int Status; //函数类型,其值为状态码
typedef long double ElemType; //抽象数据类型
					  //单链表
typedef struct LNode
{
	ElemType conf;//系数
	ElemType expn;//指数
	struct LNode *next;
}LNode, *LinkList;
//初始化
Status initList(LinkList* L)
{
	*L = (LinkList)malloc(sizeof(LNode));
	(*L)->conf = -1;
	(*L)->expn = -1;
	(*L)->next = NULL;
	return OK;
}
//判空
char* isEmpty(LinkList* L)
{
	return (*L)->next == NULL ? "空" : "不空";
}
//获取长度
int getLength(LinkList* L)
{
	LinkList p = *L;
	int i = 0;
	while (p->next)
	{
		++i;
		p = p->next;
	}
	return i;
}

//默认尾插法建表 
Status creatListEnd(LinkList* L, ElemType c[], ElemType e[], int n)
{
	LinkList p, r = *L;

	
	for (int i = 0; i < n; ++i)
	{
		p = (LinkList)malloc(sizeof(LNode));
		p->conf = c[i];
		p->expn = e[i];
		p->next = NULL;//必须要否则遍历异常
		r->next = p;
		r = p;
	}
	return OK;
}
//遍历表
Status traversalList(LinkList L)
{
	LinkList p = L->next;
	while (p)
	{
		if (p->conf>=0)
		{
			printf("+%fx%f", p->conf,p->expn);
		}
		else
		{
			printf("%fx%f", p->conf, p->expn);
		}
		p = p->next;
	}
	printf("\n");
	return OK;
}
//插入
Status insertList(LinkList* L, int i, ElemType c, ElemType e)
{
	if (L == NULL || (i > getLength(L) || i < 1))return ERROR;
	LinkList p = *L;
	int j = 0;
	while (p&&j<i - 1)
	{
		p = p->next;//定在前一个
		j++;
	}
	LinkList q = (LinkList)malloc(sizeof(LNode));
	q->conf = c;
	q->expn = e;
	q->next = p->next;
	p->next = q;
	return OK;
}
//按位查找
LNode* getListByIndex(LinkList L, int i)
{
	//if (L == NULL || (i > (L)->data || i < 1))return NULL;
	LinkList p = L;
	int j = 0;
	while (p&&j<i - 1)
	{
		p = p->next;//前一个

		j++;
	}
	//	p = p->next;
	return (p);//前一个
}
//按值查找
LNode* getListByElem(LinkList L, ElemType e, int* i)
{
	LinkList p = L;
	int j = 0;
	while (p&&p->next->expn != e)
	{
		p = p->next;//前一个
		j++;
	}
	*i = j + 1;
	return p->next;
};
//计算
long double calculateMultinomial(LinkList L, int x)
{
	LinkList p = L->next;
	long double sum=0;
	while (p)
	{
		sum = p->conf*pow(x, p->expn)+sum;
		p = p->next;
	}

	return sum;
}
//合并
Status mergeList(LinkList* LA, LinkList* LB)
{
	if (getLength(LA)>getLength(LB))
	{
		LinkList* temp = LA;
		LA = LB;
		LB = temp;
	}
	ElemType e,c;
	for (int i = 1; i <= getLength(LA); i++)
	{
		e = getListByIndex(*LA, i)->next->expn;//取指数
		c = getListByIndex(*LA, i)->next->conf;//取系数
		//先指数相同
		for (int i = 1; i <= getLength(LB); i++)
		{
			if (getListByIndex(*LB, i)->next->expn==e)
			{
				getListByIndex(*LB, i)->next->conf =getListByIndex(*LB, i)->next->conf + c;//系数相加
				break;
			};
		}
		//指数不同
		for (int i = 1; i <= getLength(LB); i++)
		{
			if (getListByIndex(*LB, i)->expn<e&&getListByIndex(*LB, i)->next->expn>e)
			{
				insertList(LB, i, c, e);
				break;
			};
		}
	}
	printf("多项式相加后: ");
	traversalList(*LB);
	printf("请输入x的值 ");
	int x;
	scanf_s("%d", &x);
	printf("答案为 %f\n\n", calculateMultinomial(*LB, x));
	return OK;
}

int main(void)
{
	ElemType ac[4] = { 7,3,9,5 };//系数
	ElemType ae[4] = { 0,1,8,17 };//指数
	
	ElemType bc[3] = { 8,22,-9};
	ElemType be[3] = { 1,7,8};
	LinkList LA, LB;
	int x;
	initList(&LA);
	initList(&LB);
	creatListEnd(&LA, ac,ae,4 );
	creatListEnd(&LB, bc, be, 3);

	printf("多项式LA: ");
	traversalList(LA);

	printf("请输入x的值 ");
	scanf_s("%d", &x);
	printf("答案为 %f\n\n", calculateMultinomial(LA, x));

	printf("多项式LB: ");
	traversalList(LB);

	printf("请输入x的值 ");
	scanf_s("%d", &x);
	printf("答案为 %f\n\n", calculateMultinomial(LB, x));

	mergeList(&LA, &LB);
	
	
	system("pause");
	return 0;
}

附加 有序集合的顺序合并

可以忽略短的无序集合 不会插入相同的元素

#include<stdio.h>
#include<iostream>
#include<malloc.h>
#include<stdlib.h>
using namespace std;
#define OK 1 //通过
#define ERROR 0 //错误 
#define OVERFLOW -2 //堆栈溢出
#define LIST_INIT_SIZE 10 //线性表储存空间初始分配量
#define LISTINCREMRNT 10 //线性表储存空间的分配增量
typedef int Status; //函数类型,其值为状态码
typedef int ElemType; //抽象数据类型

					  //线性表动态分配顺序储存结构
typedef struct
{
	ElemType* elem;//储存空间基址
	int length;//当前长度
	int listsize;//当前分配的存储容量
}SqList;

//初始化一个空的表
Status InitList(SqList* L)
{

	L->elem = (ElemType*)__vcrt_malloc_normal(LIST_INIT_SIZE * sizeof(ElemType));
	if (!(L->elem))
		exit(OVERFLOW);//分配失败
	L->length = 0;//长度
	L->listsize = LIST_INIT_SIZE;//容量

	return OK;
}

//插入
Status ListInsert(SqList* L, int i, ElemType e)
{
	if (i<1 || i>L->length + 1)
		return ERROR;

	ElemType* q = &(L->elem[i - 1]), *p = NULL;// q为插入位置
	for (p = &(L->elem[L->length - 1]); p >= q; --p)
		* (p + 1) = *p;// 插入位置及之后的元素后移
	*q = e;// 插入e
	++(L->length);// 表长增加1
	if (L->length == L->listsize) {
		ElemType*  newbase = (ElemType*)realloc(L->elem, (L->listsize + LISTINCREMRNT) * sizeof(ElemType));
		if (!newbase)
			exit(OVERFLOW);
		L->elem = newbase;// 新基址
		L->listsize += LISTINCREMRNT;// 增加存储容量
	}
	return OK;
}
//获取长度
int getLength(SqList* L)
{
	return L->length;
}
//通过索引取值
ElemType getElemByIndex(SqList* L, int i)
{
	return L->elem[i - 1];
}
//通过值取索引
int getIndexByElem(SqList* L, ElemType e)
{
	for (int j = 0; j < L->length; ++j)
	{
		if ((L->elem[j]) == e)
			return j + 1;
	}
	return -1;
}

//遍历表
Status myPrintf(SqList* L)
{
	for (int i = 0; i < L->length; i++) {
		cout << "第"<< i + 1<<"个值------------" << (L->elem[i])<<endl;
		
	}
	return OK;
}
//创建表
Status creatList(SqList* L)
{
	scanf_s("%d", &(L->length));
	printf("输入为 %d\n", L->length);
	for (int i = 0; i < L->length; i++)
	{
		cin >> L->elem[i];

	}
	return OK;
}
//合并
Status mergeList(SqList* LA,SqList* LB)
{
	if (LA->length < LB->length) {
		SqList* temp;
		temp = LA;
		LA = LB;
		LB = temp;
	}
	for (int i = 0; i < LB->length; i++)
	{
		ElemType e = getElemByIndex(LB,i+1);
		if (getIndexByElem(LA, e)==-1) {
			ListInsert(LA, 1, e);
		}
	}
	printf("合并后\n");
	myPrintf(LA);
	return OK;
}
int main(void) {
	SqList* LA = (SqList*)__vcrt_malloc_normal(sizeof(SqList));
	InitList(LA);
	printf("请输入表A的长度\n");
	creatList(LA);
	myPrintf(LA);
	SqList* LB = (SqList*)__vcrt_malloc_normal(sizeof(SqList));
	InitList(LB);
	printf("请输入表B的长度\n");
	creatList(LB);
	myPrintf(LB);

	mergeList(LA, LB);
	system("pause");
	
	return 0;
}