Question

数据结构实验

数据结构实验大神何在，求解

Answer 1

我写的顺序线性表的完整的C++代码。

核心操作函数基本依照《数据结构(C语言版)》教材。仅供参考。

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <iostream.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;

typedef int ElemType;


#define LIST_INIT_SIZE 80
	//线性表存储空间的初始分配量
#define LISTINCREMENT 10
	//线性表存储空间的分配增量
typedef struct{
	ElemType	*elem;	//内存基址，ElemType为数据元素类型
	int			length;	//当前表长
	int			listsize;	//当前分配的存储空间大小，以sizeof(ElemType)为单位
}SqList;	//sequential list


//构造一个空的顺序表
Status InitList_Sq( SqList &L ) {
	L.elem = (ElemType*) malloc (LIST_INIT_SIZE * sizeof(ElemType));
	//L.elem=new ElemType(LIST_INIT_SIZE);
	if (!L.elem) exit(OVERFLOW);
	L.length = 0;
	L.listsize = LIST_INIT_SIZE;
	return OK;   //OK是1
} // InitList_Sq

//在顺序表中查询数据元素e是否存在，返回它的位序
int LocateElem_Sq(SqList L, ElemType e) {
	int i = 1;	//从首元素开始比较
	ElemType *p = L.elem;	//p 指向首元素
	while ((i <= L.length) && (e!=*p))
		{  ++i; ++p;  }	//继续查找
	if (i <= L.length) return  i;	//查找成功，返回位序
	else return 0;	//不成功
}

//在顺序表L的第 i 个元素之前插入新元素e,
// i 的取值范围为 1≤i≤L.length+1
Status ListInsert_Sq(SqList &L,int i,ElemType e) { 
	if (i < 1 || i > L.length+1) return ERROR;	//不合法
	if (L.length == L.listsize) {	//存储空间已满，增加分配
	    ElemType *newbase = (ElemType *)realloc(L.elem, (L.listsize+LISTINCREMENT) * sizeof (ElemType) );
	    if (!newbase) exit(OVERFLOW);	//存储分配失败
	    L.elem = newbase;	//新基址
	    L.listsize += LISTINCREMENT;	//增加存储容量
	}
	//合法性检查
	ElemType *q = L.elem+ i - 1;	// q 指示插入位置
	ElemType *p; 
	for (p = L.elem + L.length - 1; p >= q;  --p)  
		*(p+1) = *p;	// 插入位置及之后的元素右移
	*q = e;	// 插入e。  L.elem[i-1]=e
	++ L.length;	// 表长增1
	return OK;
}

//删除顺序表L的第 i 个元素，并用e返回，
//1 ≤ i ≤ L.length
Status ListDelete_Sq(SqList &L,int i,ElemType &e) {
	if ((i < 1) || (i > L.length))  return ERROR;	//删除位置不合法
	ElemType *p = L.elem + i-1;	//p为被删除元素的位置
	e = *p;	// 被删除元素L.elem[i-1]赋给 e
	ElemType *q = L.elem + L.length-1;	//表尾元素的位置
	for (++p; p <= q; ++p)
		*(p-1) = *p;	//被删除元素之后的元素左移
	--L.length;	//表长减1
	return OK;
} 



//将顺序表L销毁
void DestroyList_Sq(SqList &L) {
	free(L.elem);
} 


//将顺序表L重置为空表 
void ClearList_Sq(SqList &L) {
	L.length = 0;
} 

//若顺序表L为空表，则返回TRUE，否则返回FALSE
Status ListEmpty_Sq(SqList L) {
	if(L.length)  return FALSE;
	else  return TRUE;
}

//返回顺序表L中数据元素的个数
int ListLength_Sq(SqList L) {
	return L.length;
}

//用e返回顺序表L中第i个数据元素的值 
Status GetElem_Sq(SqList L, int i, ElemType &e) {
	if (i < 1 || i > L.length) return ERROR;	//不合法
	ElemType *p = L.elem + i-1;
	e = *p;
	return OK;
} 

//用pre_e返回顺序表L中cur_e的前驱
Status PriorElem_Sq(SqList L, ElemType cur_e, ElemType &pre_e) {
	int i = LocateElem_Sq(L,cur_e);
	if(i==0 || i==1) return ERROR;
	GetElem_Sq(L, i-1, pre_e);
	return OK;
} 

//用next_e返回顺序表L中cur_e的后继 
Status NextElem_Sq(SqList L, ElemType cur_e, ElemType &next_e) {
	int i = LocateElem_Sq(L,cur_e);
	if(i==0 || i==L.length) return ERROR;
	GetElem_Sq(L, i+1, next_e);
	return OK;
} 

//依次对顺序表L的每个数据元素调用函数visit()
void ListTraverse_Sq(SqList L, Status visit(int i, ElemType e)) {
	int i = 1;
	ElemType *p = L.elem;
	while (i <= L.length) {
		visit(i,*p);
		++i; ++p;
	}
} 


//遍历_输出
Status print(int i, ElemType e){
	cout<<"第"<<i<<"个元素值为："<<e<<endl; 
} 


main()
{
	SqList L; 
	int choice,reply;
	ElemType e,e2;
	int i;
	
	while(1){
		cout<<"对顺序表L的操作：";
		cout<<"1.初始化 2.插入 3.删除 4.遍历 5.取值 6.查找 7.统计个数"<<endl;
		cout<<"                 8.是否空表 9.前驱 10.后继 11.清空 12.销毁   0.退出"<<endl; 
		cin>>choice;
		
		switch(choice){
		case 1://构造一个空的顺序表
			reply = InitList_Sq(L);
			if(reply == 0) cout<<"                                        失败！"<<endl; 
			break;
		case 2://在顺序表L的第 i 个元素之前插入新元素e（ i 的取值范围为 1≤i≤L.length+1
			cout<<"请输入新数据元素的值："; cin>>e;
			cout<<"请输入插入到表中的位序："; cin>>i;
			reply = ListInsert_Sq(L, i, e);
			if(reply == 0) cout<<"                                        失败！"<<endl; 
			break;
		case 3://删除顺序表L的第 i 个元素，并用e返回（1 ≤ i ≤ L.length
			cout<<"请输入欲删除的数据在表中的位序："; cin>>i;
			reply = ListDelete_Sq(L, i, e);
			if(reply == 0) cout<<"                                        失败！"<<endl; 
			else
			cout<<"您删除的数据为："<<e<<endl;
			break;
		case 4://依次对顺序表L的每个数据元素调用函数visit()
			ListTraverse_Sq(L, print);
			break;
		case 5://用e返回顺序表L中第i个数据元素的值
			cout<<"请输入位序："; cin>>i;
			reply = GetElem_Sq(L, i, e);
			if(reply == 0) cout<<"                                        失败！"<<endl; 
			else
			cout<<"表中第"<<i<<"个数据的值为："<<e<<endl;
			break;
		case 6://在顺序表中查询数据元素e是否存在，返回它的位序
			cout<<"请输入欲查找的数据元素的值："; cin>>e;
			i = LocateElem_Sq(L, e);
			if(i != 0) cout<<"该数据在表中的位序为："<<i<<endl;
			else cout<<"该数据在表中并不存在。"<<endl;
			break;
		case 7://返回顺序表L中数据元素的个数
			i = ListLength_Sq(L);
			cout<<"表中有"<<i<<"个数据元素。"<<endl;
			break;
		case 8://若顺序表L为空表，则返回TRUE，否则返回FALSE
			reply = ListEmpty_Sq(L);
			if(reply == TRUE) cout<<"该表为空表。"<<endl;
			else  cout<<"该表不是空表。"<<endl;
			break;
		case 9://用pre_e返回顺序表L中cur_e的前驱
			cout<<"请输入欲查找的数据元素的值："; cin>>e;
			reply = PriorElem_Sq(L, e, e2);
			if(reply == 0) cout<<"                                        失败！"<<endl; 
			else
			cout<<"该数据元素的前驱元素的值为："<<e2<<endl;
			break;
		case 10://用next_e返回顺序表L中cur_e的后继 
			cout<<"请输入欲查找的数据元素的值："; cin>>e;
			reply = NextElem_Sq(L, e, e2);
			if(reply == 0) cout<<"                                        失败！"<<endl; 
			else
			cout<<"该数据元素的后继元素的值为："<<e2<<endl;
			break;
		case 11://将顺序表L重置为空表 
			ClearList_Sq(L);
			break;
		case 12://将顺序表L销毁
			DestroyList_Sq(L);
			break;
		case 0:
			exit(0); 
		default:
			break;
		}
		cout<<endl; 
	}
}

Answer 2

这个我会，可以帮你写！