最近发现学长这数据结构总结的真是不错，今天重头看了一遍，我基础差，我感觉还是先把基本的操作学熟后，再连连高端操作，我感觉把这些程序自己再打一遍的话，数据结构前几单元就没问题了。
/
一，
/简单顺序表的实现
#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;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/114915.html原文链接：https://javaforall.net
