数据结构学习

最近发现学长这数据结构总结的真是不错，今天重头看了一遍，我基础差，我感觉还是先把基本的操作学熟后，再连连高端操作，我感觉把这些程序自己再打一遍的话，数据结构前几单元就没问题了。
/
一，

/简单顺序表的实现
#include<iostream> 
#define MAXSIZE 10
#define OVERFLOW -2
using namespace std;
 
typedef struct{
	int *elem;//数据域 
	int length;//长度 
}Sqlist;//顺序表 
 
bool InitList(Sqlist &L)
{
	L.elem=new int[MAXSIZE];
	if(!L.elem)	
		return false;
	L.length=0;
	return true;
}//判断是否为空表 
 
int ListInsert(Sqlist &L,int i,int e)
{
	if(i<1||i>L.length+1)
		return false;
	if(L.length==MAXSIZE)
		return OVERFLOW;
	for(int j=L.length-1;j>=i-1;j--)
		L.elem[j+1]=L.elem[j];
	L.elem[i-1]=e;
	L.length++;
	return true;	
} //删除元素的位置 
 
bool GetElem(Sqlist L,int i,int &e)
{
	if(i<1||i>L.length)
	{
		cout << "访问位置不合法!\n";
		return false;
	}
	e=L.elem[i-1];
	return true; 
}
//删除第i个元素 
bool ListDelete(Sqlist &L,int i)
{
	if(i<1||i>L.length)
		return false;
	for(int j=i;j<L.length;j++)
		L.elem[j-1]=L.elem[j];
	L.length--;
	return true;
}
//定位e 
int LocateElem(Sqlist L,int e)
{
	for(int i=0;i<L.length;i++)
		if(L.elem[i]==e)
			return i+1;
	return 0; 
}
 
void ClearList(Sqlist &L)
{
	L.length=0;
}
 
int main()
{
	int n;
	Sqlist L;
	cout << "简单顺序表的基本操作:\n"
		 << "1、建立顺序表并存储5个数\n"
		 << "2、插入\n"
		 << "3、删除\n"
		 << "4、查找\n"
		 << "5、取值\n"
		 << "6、清空\n"
		 << "0、退出系统\n";
	while(1)
	{
		int k,l,m;
		cout <<"输入序号,进行相关操作:";
		cin >> n;
		switch(n)
		{
			case 1:
				if(InitList(L))
				{
					cout << "顺序表创建成功\n";
					for(int i=1;i<=5;i++)
						ListInsert(L,i,i); 
				}
				else 
				{
					cout << "顺序表创建失败，自动退出程序!\n";
					break;
				}
				break;
			case 2:
				cout << "请输入插入位置与插入值:";	
				cin >> k >> l;
				m=ListInsert(L,k,l);
				if(!m)
				{
					cout << "插入失败!\n";
					if(m==OVERFLOW)
						cout << "初始分配空间已满!\n";
					else 
						cout << "插入位置不合法!\n";
				}	
				break;
			case 3:
				cout << "请输入要删除元素的位置:";
				cin >> l;
				m=ListDelete(L,l);
				if(!m)
					cout << "删除位置不合法!\n";
				break;
			case 4:
				cout << "请输入要查找的值:";
				cin >> k;
				m=LocateElem(L,k); 
				if(!m)
					cout <<"顺序表中没有这个值!\n";
				else
					cout << m << endl;
				break;
			case 5:
				cout << "请输入要取第几个值:";
				cin >> k;
				GetElem(L,k,m);
				if(m!=false)
					cout << m << endl;
				break;
			case 6:
				ClearList(L);
				break;
			case 0:
				exit(0);
		}
		cout << "------------------------------------------------\n";
		cout << "当前顺序表:\n";
		for(int i=1;i<=L.length;i++)
		{
			int m;
			GetElem(L,i,m);
			cout << m << " ";
		}
		cout << "\n------------------------------------------------\n";
	}
	return 0;
}

二，

//简单实现单链表
#include<iostream>
 
using namespace std;
 
typedef struct LNode{
	int data;				//数据域 
	struct LNode *next;		//指针域 
}LNode,*Linklist;
 
bool InitList(Linklist &L)
{
	L=new LNode;

    	L->next=NULL;
    	L->data=0;
	return true;
}
 
bool GetElem(Linklist &L,int i,int &e)
{
	LNode *p=L->next;
	int j=1;
	while(p&&j<i)
	{
		p=p->next;
		j++;
	}
	if(!p||j>i)
		return false;
	e=p->data;
	return true;
}
 
//头插创建链表 
void CreateList_H(Linklist &L,int n)
{
	L=new LNode;
	L->next=NULL;
	L->data=0;
	for(int i=0;i<n;i++)
	{
		int m;
		LNode *p=new LNode;
		cin >> m;
		p->data=m;
		p->next=L->next;
		L->next=p; 
		L->data++;
	}
}
 
//尾插 
void CreateList_R(Linklist &L,int n)
{
	L=new LNode;
	L->data=0;
	L->next=NULL;
	LNode *r;
	r=L;
	for(int i=0;i<n;i++)
	{
		int m;
		LNode *p=new LNode;
		cin >> m;
		p->data=m;
		p->next=NULL;
		r->next=p;
		r=p;
		L->data++;
	}
}
 
//插入
bool ListInsert(Linklist &L,int i,int e)
{
	LNode *p=L;
	int j=0;
	while(p&&j<i-1)
	{
		p=p->next;
		j++;
	}
	if(!p||j>i-1)
		return false;
	LNode *s=new LNode;
	s->data=e;
	s->next=p->next;
	p->next=s;
	L->data++;
	return true;
} 
 
bool ListDelete(Linklist &L,int i)
{
	LNode *p=L;
	int j=0;
	while(p->next&&j<i-1)
	{
		p=p->next;
		j++; 
	} 
	if(!(p->next)||j>i-1)
		return false;
	LNode *q;			//存储p->next  为了一会儿释放 
	q=p->next;
	p->next=q->next;
	L->data--;
	delete q;
	return true;
}
 
//定位
int LocateElem(Linklist L,int e)
{
	LNode *p=L->next;
	int j=1;
	while(p&&p->data!=e)
	{
		p=p->next;
		j++;
	}
	if(j>L->data)
		return false;
	return j;
 } 
 
void ClearList(Linklist &L)
{
	LNode *p,*q;
	p=L->next;
	while(p)
	{
		q=p->next;
		delete p;
		p=q;
	}
	L->next=NULL;
}
 
int main()
{
	cout << "-----简单实现单链表:----\n"
		 << "1、链表初始化\n"
		 << "2、插入\n" 
		 << "3、头插创建n个数的链表\n"
		 << "4、尾插创建n个数的链表\n"
		 << "5、删除\n"
		 << "6、取值\n"
		 << "7、定位\n"
		 << "8、销毁\n"
		 << "0、退出系统\n";
	int n;
	Linklist L;			
	while(1)
	{
		int num;
		int j,k;
		cout << "-------------------------------------\n";
		cout << "请输入想要执行的操作:";
		cin >> n;
		switch(n)
		{
			case 1:
				if(InitList(L))
					cout << "链表初始化成功!\n";
				break;
			case 2:
				cout << "请输入要插入的位置，以及要插入的数据元素:";
				cin >> j >> k;
				if(ListInsert(L,j,k))
					cout << "插入成功!\n";
				else 
					cout << "插入位置不合法!\n";
				break;
			case 3:
				cout << "请输入你想要存储多少个数:";
				cin >> num;
				CreateList_H(L,num);
				break; 
			case 4:
				cout << "请输入你想要存储多少个数:";
				cin >> num;
				CreateList_R(L,num);
				break;
			case 5:
				cout << "请输入要删除第几个元素:";
				cin >> j;
				if(ListDelete(L,j))
					cout << "删除成功!\n";
				else	
					cout << "删除位置不合法!\n";
				break;
			case 6:
				cout << "请输入要取第几个位置的元素:";
				cin >> j;
				if(GetElem(L,j,k))
					cout << "第" << j << "个位置的元素是" << k << endl;
				else
					cout << "位置不合法!\n";
				break; 
			case 7:
				cout << "请输入要找的值:";
				cin >> k;
				num=LocateElem(L,k);
				if(num)
					cout << "在第" <<  num << "个!\n";
				else 
					cout << "没有找到该值!\n";
				break;
			case 8:
				cout << "链表已经销毁！自动退出程序！\n";
				exit(0);
			default :
				exit(0);
				
		}
		cout << "--------------------------------------------\n";
		cout << "当前链表的长度是" << L->data << "!\n";
		cout << "当前链表的数字信息是:\n";
		for(int i=1;i<=L->data;i++)
		{
			int e;
			GetElem(L,i,e);
			cout << e << "  ";
		}
		cout << "\n";
	}	
	return 0;
}

三，

多项式合并
//实现多项式的运算 
#include<iostream>
 
using namespace std;
 
typedef struct PNode{
	float coef;			//系数 
	int expn;			//指数 
	struct PNode *next;
}PNode,*Polyn;


//创建多项式  实现链表递增 
void CreatePolyn(Polyn &L,int n)
{
	L=new PNode;		//创建带有头结点的空链表
	L->next=NULL;
	for(int i=0;i<n;i++)
	{
		Polyn s=new PNode;
		cout << "请输入第" << i+1 << "个系数和指数（中间用空格隔开）:";
		cin >> s->coef >> s->expn;		
		PNode *pre,*q;
		pre=L;			//pre指向待找结点前驱 
		q=L->next;		//q指向待找结点 
		while(q&&q->expn < s->expn)
		{
			pre=q;
			q=q->next;
		}
		//然后把s插入到pre和q中间
		s->next=q;
		pre->next=s;
	}
}
 
//遍历取值 
void T_GetElem(Polyn L)
{
	PNode *p;
	p=L->next;
	while(p)
	{
		cout << p->coef << " " << p->expn << endl;
		p=p->next;
	}
}
 
//多项式相加
void AddPolyn(Polyn &A,Polyn &B)
{
	PNode *p1,*p2,*p3;
	p1=A->next;p2=B->next;
	p3=A;	
	while(p1&&p2)
	{
		if(p1->expn==p2->expn)
		{
			int sum=p1->coef+p2->coef;
			//如果和等于0  销毁p1 p2 
			//否则 销毁p2，改变p1的指数值 
			if(sum==0)
			{
				PNode *r=p1;p1=p1->next;delete r;
				PNode *w=p2;p2=p2->next;delete w;
			}
			else
			{
				p1->coef=sum;
				PNode *r=p2;p2=p2->next;delete r;
				//把p1链在p3之后，再更新p3 
				p3->next=p1;
				p3=p1;
				p1=p1->next;
			}
		}
		else if(p1->expn<p2->expn)
		{
			//链p1  p1指向下一个结点 
			p3->next=p1;
			p3=p1;
			p1=p1->next;
		} 
		else
		{
			//链p2 
			p3->next=p2;
			p3=p2;
			p2=p2->next;
		}
	}
	p3->next=p1?p1:p2;
	delete B;		//销毁B的表头 
} 
 
//A-B
void SubPolyn(Polyn &A,Polyn &B)
{
	PNode *p1,*p2,*p3;
	p1=A->next;p2=B->next;
	p3=A;
	while(p1&&p2)
	{
		if(p1->expn==p2->expn)
		{
			int sub=p1->coef-p2->coef;
			if(sub==0)
			{
				PNode *r=p1;p1=p1->next;delete r;
				PNode *w=p2;p2=p2->next;delete w;
			}
			else 
			{
				p1->coef=sub;
				p3->next=p1;
				p3=p1;
				p1=p1->next;
				PNode *r=p2;
				p2=p2->next;
				delete r;
			}
		}
		else if(p1->expn < p2->expn)
		{
			p3->next=p1;
			p3=p1;
			p1=p1->next;
		}
		else 
		{
			p2->coef=-p2->coef;
			p3->next=p2;
			p3=p2;
			p2=p2->next;
		}
	}
	if(!p1)
	{
		p3->next=p2;
		p3=p2;
		while(p3)
		{
			p3->coef=-p3->coef;
			p3=p3->next;
		}
	}
	else if(!p2)
	{
		p3->next=p1;
	}
	delete B;
}
 
int main()
{
	Polyn PA,PB;
	int n;
	cout << "输入多项式 PA 的项数 :" ;
	cin >> n;
	CreatePolyn(PA,n);
	cout << "多项式PA的各个系数:\n";
	T_GetElem(PA);
	cout << "------------------------\n";
	cout << "输入多项式 PB 的项数 :" ;
	cin >> n;
	CreatePolyn(PB,n);
	cout << "多项式PB的各个系数:\n";
	T_GetElem(PB);
	cout << "------------------------\n";
	cout << "现在你可以做一个选择：\n";
	cout << "1、PA+PB\n2、PA-PB\n3、PB-PA\n0、退出程序\n";
	cin >> n;
	switch(n)
	{
		case 1:
			AddPolyn(PA,PB);
			cout << "相加后的各项:\n";
			T_GetElem(PA);
			break;
		case 2:
			cout << "PA-PB后的各项:\n";
			SubPolyn(PA,PB);
			T_GetElem(PA);
			break;
		case 3:
			cout << "PB-PA后的各项:\n";
			SubPolyn(PB,PA);
			T_GetElem(PB);
			break;
		case 0:
			exit(0);
	} 
	return 0;
}

发布者：全栈程序员-用户IM，转载请注明出处：https://javaforall.cn/114915.html原文链接：https://javaforall.cn

【正版授权，激活自己账号】： Jetbrains全家桶Ide使用，1年售后保障，每天仅需1毛

【官方授权正版激活】： 官方授权正版激活支持Jetbrains家族下所有IDE 使用个人JB账号...