线性表及其实现数据结构学习

左手的ㄟ右手 2024-02-19 16:13 50阅读 0赞

*课程是跟着MOOC 数据结构 陈越、何钦铭二位老师学的，这遍两个目的：1.复习，2.找找不同大学教学水平的差距*

问题引入：一元多项式的表示及运算

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzI1Njk4_size_16_color_FFFFFF_t_70][]

如何表示？

（1）最容易想到的办法（顺序存储方式）：用结构体数组存储多项式的每一项的系数及指数。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzI1Njk4_size_16_color_FFFFFF_t_70 1][]

但是这种结构有弊端，如下图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzI1Njk4_size_16_color_FFFFFF_t_70 2][]

很显然，我们要用一个空间为2001的数组仅仅存了3个有用的数据，其他项全为零，造成巨大的浪费。

（2）我们只存储非零项，用结构体数组存储非零项的系数及指数（按指数从大到小排列）

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzI1Njk4_size_16_color_FFFFFF_t_70 3][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzI1Njk4_size_16_color_FFFFFF_t_70 4][]

多项式相加的基本方法：

比较当前的两项指数的大小，大的那项加到p3（存储结果的数组）里，若两项系数相等，将两项系数相加，指数不变，加到p3里，继续加，直到p1或p2其中的某一个表达式为空，将另一个表达式剩余部分按顺序加到p3里。

一元多项式 求和 （链式实现）

#include<iostream>
    using namespace std;
    #define NULL 0
    
    typedef struct node{
    	int index;  //指数 
    	int ratio;   // 系数 
    	struct node* next;
    }node,* List;
    
    void CreateList(List &l)
    {
    	l=new node;
    	l->next=NULL;
    }
    void add(int z,int x,List &l)  //采用头插法 
    {
    	List n=new node;
    	n->index=z;
    	n->ratio=x;
    	n->next=l->next;
    	l->next=n;
    }
    int input(List &l)
    {
    	int m=0,a=0,b=0;
    	int i=0,j=0;
    	cout<<"Please input the number of polynomials:"<<endl;
    	cin>>m;
    	for(i=0;i<m;i++)
    	{
    		cout<<"Please input the coefficients and exponents of the item."<<endl;
    		cin>>a>>b;
    		add(a,b,l);
    		
    	}
    	return 1;
     } 
    int collect(List a,List b,List &c)
    {
    	List Pa=a->next;
    	List Pb=b->next;
    	List Pc=c;
    	while((Pa)&&(Pb))
    	{
    		if((Pa->index)<(Pb->index))
    		{
    			
    			Pc->next=Pa;
    			
    			Pc=Pa;
    			cout<<Pc->ratio<<"  "<<Pc->index<<endl;
    			Pa=Pa->next;
    		}
    		else
    		if((Pa->index)==(Pb->index))
    		{
    			
    			Pa->ratio=Pa->ratio+Pb->ratio;
    			
    			Pc->next=Pa;
    		    
    			Pc=Pa;cout<<Pc->ratio<<"  "<<Pc->index<<endl;
    			Pa=Pa->next;
    			Pb=Pb->next;
    			
    		}
    		else
    		if((Pa->index)>(Pb->index))
    		{
    			
    			Pc->next=Pb;
    			
    			Pc=Pb;cout<<Pc->ratio<<"  "<<Pc->index<<endl;
    			Pb=Pb->next;	
    		}
    	}
    	while(Pa!=NULL)
    	{
    		Pc->next=Pa;
    	}
    	while(Pb!=NULL)
    	{
    		Pc->next=Pb;
    		Pb=Pb->next;
    	}
    	delete Pa,Pb,Pc;
    	return 1;
    }
    void Traversal(List l)
    {
    	l=l->next;   //跳过头结点 
    	while(l)
    	{
    		cout<<l->ratio<<"x^"<<l->index<<" ";
    		l=l->next;
    	}
    	cout<<endl;
    }
    
    
    int main()
    {
    	List a,b,c;
    	CreateList(a);
    	CreateList(b);
    	CreateList(c);
    	
    	input(a);
    	cout<<"input another one:"<<endl;
    	input(b);
    	Traversal(a);
    	Traversal(b);
    	collect(a,b,c);
    	Traversal(c);
    	return 0;
    }

线性表的顺序存储：

#include<iostream> 
    #include<stdio.h>
    using namespace std;
    #define ok 1
    #define error 0
    #define overflew -2
    #define MAXSIZE 10
    typedef int Status;
    typedef int elemtype;
    typedef struct  s1
    {
    	elemtype *elem;
    	int length;
    }Sqlist;
    Status creat(Sqlist &l)
    {
    	l.elem=new elemtype[MAXSIZE];
    	l.length=0;
    	if(!l.elem) return error;
    	return ok;
    }
    Status getelem(Sqlist l,int i,int &e)
    {
    	if(i<1||i>l.length) return error;
    	e=l.elem[i-1];
    	return ok;
    }
    int locateelem(Sqlist l,int m)
    {
    	int i;
    	for(i=0;i<l.length;i++)
    	if(l.elem[i]==m) return i+1;
    	//else cout<<"找不到该数"<<endl;
    }
    Status insertelem(Sqlist &l,int i,int e)
    {
    	int j;
    	if(i<1||i>l.length+1)
    	return overflew;
    	if(l.length==MAXSIZE) cout<<"errors"<<endl;
    	for(j=l.length-1;j>=i-1;j--)
    	
    	
    	l.elem[j+1]=l.elem[j];
    	l.elem[i-1]=e;
    	l.length++;
    	
    	return ok;
    }
    Status deleteelem(Sqlist &l,int i)
    {
    	int j;
    	if(i<1||i>l.length)
    	return overflew;
    	for(j=i;j<=l.length-1;j++)
    	l.elem[j-1]=l.elem[j];
    	l.length--;
    	return ok;
    }
    Status assign(Sqlist &l)
    {
    	int i,n,m; 
    	cout<<"请输入顺序表的长度:"<<endl;
    	cin>>n;
    	cout<<"请输入顺序表中的元素："<<endl;
    	for(i=1;i<=n;i++)
    	{
    		cin>>m;
    		insertelem(l,i,m);
    	}
    	return ok;
    }
    int main()
    {
    	int i,j,e,t;
    	Sqlist l;
    	creat(l);
    	
    	assign(l);
    	cout<<"请输入你要查找的第i个元素："<<endl;
    	cin>>i;
    	getelem(l,i,e);
    	cout<<"你要查找的第"<<i<<"个元素："<<e<<endl;
    	cout<<"请输入你要查找的数值："<<endl;
    	cin>>i;
    	j=locateelem(l,i);
    	cout<<"你要查找的数值在顺序表中的位置："<<j<<endl;
    	cout<<"请输入你要插入的位置及数值:"<<endl;
    	cin>>i>>e;
    	insertelem(l,i,e);
    	for(j=0;j<10;j++)
    	cout<<l.elem[j]<<' ';
    	cout<<endl;
    	cout<<"此时插入位置的元素为："<<l.elem[i-1]<<' '<<"表的长度:"<<l.length<<endl;
    	cout<<"请输入你要删除元素的位置:"<<endl;
    	cin>>i;
    	deleteelem(l,i);
    	cout<<"此时表中元素为："<<endl;
    	for(j=0;j<l.length;j++)
    	cout<<l.elem[j]<<' ';
    	cout<<endl;
    	cout<<"此时被删除元素位置的数据为："<<l.elem[i-1]<<"表的长度:"<<l.length<<endl;
    	return 0;
    }

链式存储：

#include<iostream>
    #include<stdio.h>
    using namespace std;
    #define ok 1
    #define error 0
    #define overflew -1
    #define MAXSIZE 10
    #define NULL 0
    typedef int Status;
    typedef int ElemType;
    typedef struct lnode
    {
    	ElemType data;
    	struct lnode* next;
    }lnode,* Linklist;
    Status Initlist(Linklist &l)
    {
    	l=new lnode;
    	l->next=NULL;
    	if(!l) return error;
    	return ok;
    }
    Status ListInsert(Linklist &l,int i,ElemType e)
    {
    	Linklist p=l,s;
    	int j=0;
    	for(;p&&j<i-1;j++)
    	{
    		p=p->next;
    	}
    	if(!p||j>i-1)  return error;
    	s=new lnode;
    	s->data=e;
    	s->next=p->next;
    	p->next=s;
    	return ok;
    }
    Status ListDelete(Linklist &l,int i)
    {
    	Linklist p=l;
    	int j=0;
    	for(;p->next&&j<i-1;j++)
    	p=p->next;
    	if(!p->next||j>i-1)  return error;
    	p->next=p->next->next;
    	return ok;
    }
    Linklist LocateElem(Linklist l,ElemType e)
    {
    	Linklist p=l->next;
    	while(p&&p->data==e)
    	p=p->next;
    	if(p)
    	return p;
    	if(!p)  return error;
    }
    Status Getelem(Linklist l,int i,ElemType &e)
    {
    	Linklist p=l->next;
    	int j=1;
    	for(;p&&j<i;j++)
    	p=p->next;
    	if(!p||j>i) return error;
    	e=p->data;
    	return ok;
    }
    Status weichafa(Linklist &l)
    {
    	int m,i,n;
    	
    	
    	cout<<"请输入你要插入元素的个数：";
    	cin>>m;
    	for(i=1;i<=m;i++)
    	{
    		
    		
    		cout<<"请输入你要插入的元素："; 
    		cin>>n;
    		ListInsert(l,i,n);
    	 } 
    	 return ok;
    }
    int  Listlength(Linklist l)
    {
    	Linklist p=l->next;
    	int i=1;
    	while(p)
    	{
    		p=p->next;
    		i++;
    	}
    	
    	return i-1;
    }
    int main()
    {
    	int i,k=0,m1,m2;
    	Linklist l,p;
    	Initlist(l);
    	weichafa(l);
    	
    	cout<<"此时链表中存储的元素为："<<endl;
    	for(p=l->next;p;)
    	{
    		cout<<p->data<<"  ";
    		p=p->next;
    	 } 
    	 cout<<endl;
    	 cout<<"请输入你要插入的位置及元素：";
    	 cin>>m1>>m2;
    	 ListInsert(l,m1,m2);
    	 
    	cout<<"此时链表中存储的元素为："<<endl;
    	for(p=l->next;p;)
    	{
    		
    		cout<<p->data<<"  ";
    		p=p->next;
    	 } 
    	 cout<<endl;
    	  cout<<"请输入你要删除的位置：";
    	  cin>>m1;
    	  ListDelete(l,m1);
    	   
    	cout<<"此时链表中存储的元素为："<<endl;
    	for(p=l->next;p;)
    	{
    		cout<<p->data<<"  ";
    		p=p->next;
    	 }
    	 cout<<endl;
    	 cout<<"链表的长度为："<<endl;
    	  cout<<Listlength(l)<<endl;
    	 return 0;
    	 
    	 
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzI1Njk4_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/f16a48fe4d784cf9b6fefec50f050158.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzI1Njk4_size_16_color_FFFFFF_t_70 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/809d2a08a1cf49daba822bb45e859da9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzI1Njk4_size_16_color_FFFFFF_t_70 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/1ee029a30d5a4d1b9ef914c679f5611a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzI1Njk4_size_16_color_FFFFFF_t_70 3]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/5852ee4495034c619428e906052fdea8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzI1Njk4_size_16_color_FFFFFF_t_70 4]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/ff25b81dcc85495aa20ab3f431e75f56.png