基础数据结构【四】————环形链表与多项式

主要演示环形列表节点的创建插入， 删除，遍历，环形链表连接 。双向链表节点的建立与插入 ，双向链表中节点的删除 以及环形链表在多项式中的应用

DEMO1:环形链表节点的创建与插入  

/*
[名称]:ch03_08.cpp
[示范]:环形链表节点的创建与插入 
*/
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <string.h> 
#include <iomanip>
using namespace std;
class list
{   public:int num,score;char name[10];class list *next;
};
typedef struct list node;
typedef node *link;link findnode(link head,int num)
{link ptr;ptr=head;while(ptr!=NULL){if(ptr->num==num)return ptr;ptr=ptr->next;}return ptr;
}link insertnode(link head,link after,int num,int score,char name[10])   
{  link InsertNode;InsertNode=new node;link CurNode=NULL;InsertNode->num=num;InsertNode->score=score;strcpy(InsertNode->name,name);InsertNode->next=NULL;if(InsertNode==NULL){cout<<"内存分配失败"<<endl;return NULL;}else{if(head==NULL)	//链表是空的{head=InsertNode;InsertNode->next=head;return head;}              else{if(after==NULL)	//新增节点到链表头部的位置{//(1)将新增节点的指针指向链表头部InsertNode->next=head;CurNode=head;while(CurNode->next!=head)CurNode=CurNode->next;//(2)找到链表尾部，将它的指针指向新增节点CurNode->next=InsertNode;//(3)将链表头指针向新增节点head=InsertNode;return head;}else //新增节点到链表头部以外的地方{//(1)将新增节点的指针指向after的下一个节点InsertNode->next=after->next;//(2)将节点after的指针指向新增节点after->next=InsertNode;return head; }} }
}int main()
{  link head,ptr,newnode;int new_num, new_score;char new_name[10];int i,j,position=0,find,data[12][2];char namedata[12][10]={{"Allen"},{"Scott"},{"Marry"},{"John"},{"Mark"},{"Ricky"},{"Lisa"},{"Jasica"},{"Hanson"},{"Amy"},{"Bob"},{"Jack"}};srand((unsigned)time(NULL));cout<<"座号  成绩  座号  成绩  座号  成绩  座号  成绩"<<endl;cout<<"=============================================="<<endl;for(i=0;i<12;i++){  data[i][0]=i+1;data[i][1]=rand()%50+51;}for(i=0;i<3;i++){  for (j=0;j<4;j++)cout<<"["<<data[j*3+i][0]<<"] ["<<data[j*3+i][1]<<"]  ";cout<<endl;}head=new node;  //建立链表的头指针if(!head){  cout<<"Error!! 内存分配失败!!"<<endl;exit(1);}head->num=data[0][0];for (j=0;j<10;j++)head->name[j]=namedata[0][j];head->score=data[0][1];head->next=NULL;ptr=head;for(i=1;i<12;i++)  //建立链表{  newnode=new node;newnode->num=data[i][0];for (j=0;j<10;j++)newnode->name[j]=namedata[i][j];newnode->score=data[i][1];newnode->next=NULL;ptr->next=newnode;//将前一个节点指向新创建的节点ptr=newnode; //新节点成为前一个节点}newnode->next=head;//将最后一个节点指向头部节点就成了环形链表while(1){  cout<<"请输入要插入其后的学生编号，结束输入-1：";cin>>position;if(position==-1)    /*循环中断条件*/break;else{  ptr=findnode(head,position);cout<<"请输入新插入的学生编号：";cin>>new_num;cout<<"请输入新插入的学生成绩：";cin>>new_score;cout<<"请输入新插入的学生姓名：";cin>>new_name;head=insertnode(head,ptr,new_num,new_score,new_name);}}ptr=head;//指向链表的开头cout<<"\n\t座号\t    姓名\t成绩\n";      cout<<"\t==============================\n";do{cout<<"\t["<<ptr->num<<"]\t[ "<<setw(10)<<ptr->name<<"]\t["<<ptr->score<<"]\n";ptr=ptr->next;//指向下一个节点} while(head!=ptr && head!=head->next);delete newnode;system("pause");return 0;
}

DEMO2:环形链表节点的删除 

/*
[名称]:ch03_09.cpp
[示范]:环形链表节点的删除 
*/
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <iomanip>
using namespace std;
class list
{  public:int num,score;char name[10];class list *next;
};
typedef class list node;
typedef node *link;link findnode(link head,int num)
{link ptr;ptr=head;while(ptr!=NULL){if(ptr->num==num)return ptr;ptr=ptr->next;}return ptr;
}link deletenode(link head,link del)   
{link CurNode=NULL;  link PreNode=NULL;link TailNode=NULL;if(head==NULL){cout<<"[环形链表已经空了]";return NULL;}else{if(del==head) //删除的节点是链表头部{CurNode=head;while(CurNode->next!=head)CurNode=CurNode->next;//找到最后一个节点并记录下来TailNode=CurNode;//(1)将链表头指针移到下一个节点head=head->next;//(2)将链表最后一个节点的指针指向新的链表头部TailNode->next=head;return head;} else //要删除的节点不是链表头部{CurNode=head;while(CurNode->next!=del)CurNode=CurNode->next;//(1)找到要删除节点的前一个节点并记录下来PreNode=CurNode;//要删除的节点CurNode=CurNode->next;//(2)将要删除节点的前一个指针指向要删除节点的下一个节点PreNode->next=CurNode->next;free(CurNode);return head;}}
}int main()
{  link head,ptr,newnode;int new_num, new_score;char new_name[10];int i,j,position=0,find,data[12][2];char namedata[12][10]={{"Allen"},{"Scott"},{"Marry"},{"John"},{"Mark"},{"Ricky"},{"Lisa"},{"Jasica"},{"Hanson"},{"Amy"},{"Bob"},{"Jack"}};srand((unsigned)time(NULL));cout<<"座号  成绩  座号  成绩  座号  成绩  座号  成绩"<<endl;cout<<"=============================================="<<endl;for(i=0;i<12;i++){  data[i][0]=i+1;data[i][1]=rand()%50+51;}for(i=0;i<3;i++){  for (j=0;j<4;j++)cout<<"["<<data[j*3+i][0]<<"]"<<setw(4)<<"["<<data[j*3+i][1]<<"]  ";cout<<endl;}head=new node;   //建立链表头指针if(!head){  cout<<"Error!! 内存分配失败!!"<<endl;exit(1);}head->num=data[0][0];for (j=0;j<10;j++)head->name[j]=namedata[0][j];head->score=data[0][1];head->next=NULL;ptr=head;for(i=1;i<12;i++) //建立链表{  newnode=new node;newnode->num=data[i][0];for (j=0;j<10;j++)newnode->name[j]=namedata[i][j];newnode->score=data[i][1];newnode->next=NULL;ptr->next=newnode;	//将前一个节点指向新建立的节点ptr=newnode;			//新节点成为前一个节点}newnode->next=head;		//将最后一个节点指向头部节点就成了环形链表while(1){  cout<<"请输入要删除的学生编号，结束输入-1：";cin>>position;if(position==-1) //循环中断条件break;else{  ptr=findnode(head,position);head=deletenode(head,ptr);}}ptr=head;//指向链表的开头cout<<"\n\t座号\t    姓名\t成绩\n";         cout<<"\t==============================\n";do{cout<<"\t["<<ptr->num<<"]\t[ "<<setw(10)<<ptr->name<<"]\t["<<ptr->score<<"]"<<endl;ptr=ptr->next;//指向下一个节点} while(head!=ptr && head!=head->next);free(head);system("pause");return 0;
}

DEMO3:

[示范]:将两个学生成绩的环形链表连接起来，然后打印出连接后的链表内容

/*
[名称]:ch03_10.cpp
[示范]:将两个学生成绩的环形链表连接起来，然后打印出连接后的链表内容
*/
#include <iostream>
#include <iomanip>
#include <ctime>
#include <cstdlib>
using namespace std;
class list
{public:int num,score;char name[10];class list *next;
};
typedef class list node;
typedef node *link;
link creat_link(int data[10][2],int num);
void print_link(link head);
link concat(link ptr1,link ptr2);
int main()
{  link ptr1,ptr2,ptr;int i,data1[6][2],data2[6][2];srand(time(NULL));for (i=1;i<=6;i++){  data1[i-1][0]=i*2-1;data1[i-1][1]=rand()%49+52;data2[i-1][0]=i*2;data2[i-1][1]=rand()%49+52;}ptr1=creat_link(data1,6);//建立串行1ptr2=creat_link(data2,6);//建立串行2i=0;cout<<"\t\t       原 链 表 数 据："<<endl;cout<<"\t    座号 成绩   座号 成绩   座号 成绩"<<endl;cout<<"\t    =================================="<<endl;cout<<"环形链表1 ：";print_link(ptr1);cout<<"环形链表2 ：";print_link(ptr2);cout<<"\t    =================================="<<endl;cout<<"连接后的链表：";ptr=concat(ptr1,ptr2);			//连接环形链表print_link(ptr);system("pause");
}
link creat_link(int data[10][2],int num) //建立链表子程序
{  link head,ptr,newnode;for(int i=0;i<num;i++){  newnode=new node;if(!newnode){  cout<<"Error!! 内存分配失败!!"<<endl;exit(i);}if(i==0)//建立链表头部{  newnode->num=data[i][0];newnode->score=data[i][1];newnode->next=NULL;head=newnode;ptr=head;}else //建立链表其他节点{  newnode->num=data[i][0];newnode->score=data[i][1];newnode->next=NULL;ptr->next=newnode;ptr=newnode;}newnode->next=head;}return ptr;//返回链表
}
void print_link(link head)//打印链表子程序
{  link ptr;int i=0;ptr=head->next;do {  cout<<"["<<setw(2)<<ptr->num<<"-"<<setw(3)<<ptr->score<<"] -> ";i++;if(i>=3)//每行打印三个元素{  cout<<"\n\t    ";i=0;}ptr=ptr->next;}while(ptr!=head->next);cout<<endl;
}
link concat(link ptr1,link ptr2)		//连接链表子程序
{  link head;head=ptr1->next;		//在ptr1和ptr2中，各找任意一个节点ptr1->next=ptr2->next;	//把两个节点的next对调即可ptr2->next=head;return ptr2;
}

DEMO4:双向链表节点的建立与插入

/*
[名称]:ch03_11.cpp
[示范]:双向链表节点的建立与插入 
*/
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <string.h> 
#include <iomanip>
using namespace std;
class list
{  public:int num,score;char name[10];class list *llink;class list *rlink;
};
typedef class list node;
typedef node *link;link findnode(link head,int num)
{link ptr;ptr=head;while(ptr!=NULL){if(ptr->num==num)return ptr;ptr=ptr->rlink;}return ptr;
}link insertnode(link head,link ptr,int num,int score,char name[10])   
{  link newnode=(link)malloc(sizeof(node));link newhead=(link)malloc(sizeof(node));newnode=new node;//memset(newnode,0,sizeof(node));newnode->num=num;newnode->score=score;strcpy(newnode->name,name);if(head==NULL) /*双向链表是空的*/{newnode=new node;// memset(newhead,0,sizeof(node));       newhead->num=num;newhead->score=score;strcpy(newhead->name,name);return newhead;}else{if(ptr==NULL){cout<<"[错误:不是链表中的节点]"<<endl;}if(ptr==head) //插入链表头部的位置{head->llink=newnode;newnode->rlink=head;head=newnode;}else{if(ptr->rlink==NULL) //插入链表末尾的位置{ptr->rlink=newnode;newnode->llink=ptr;newnode->rlink=NULL;}else //插入中间节点的位置{newnode->rlink=ptr->rlink;ptr->rlink->llink=newnode;ptr->rlink=newnode;newnode->llink=ptr;}}}return head;
}
int main(void)
{  link head,ptr;link llinknode=NULL;link newnode=NULL;int new_num, new_score;char new_name[10];int i,j,position=0,find,data[12][2];char namedata[12][10]={{"Allen"},{"Scott"},{"Marry"},{"John"},{"Mark"},{"Ricky"},{"Lisa"},{"Jasica"},{"Hanson"},{"Amy"},{"Bob"},{"Jack"}};srand((unsigned)time(NULL));cout<<"座号  成绩  座号  成绩  座号  成绩  座号  成绩"<<endl;cout<<"=============================================="<<endl;for(i=0;i<12;i++){  data[i][0]=i+1;data[i][1]=rand()%50+51;}for(i=0;i<3;i++){  for (j=0;j<4;j++)cout<<"["<<setw(2)<<data[j*3+i][0]<<"] ["<<setw(3)<<data[j*3+i][1]<<"]  ";cout<<endl;}head=new node;//建立链表头指针if(head==NULL){  cout<<"Error!! 内存分配失败!!"<<endl;exit(1);}else{head=new node;head->num=data[0][0];for (j=0;j<10;j++)head->name[j]=namedata[0][j];head->score=data[0][1];llinknode=head;for(i=1;i<12;i++) //建立链表{  newnode=new node;newnode->llink = NULL;newnode->rlink = NULL;newnode->num=data[i][0];for (j=0;j<10;j++)newnode->name[j]=namedata[i][j];newnode->score=data[i][1];llinknode->rlink=newnode;newnode->llink=llinknode;llinknode=newnode;}}while(1){  cout<<"请输入要插入其后的学生编号，结束输入-1：";cin>>position;if(position==-1)//循环中断条件break;else{  ptr=findnode(head,position);cout<<"请输入新插入的学生编号：";cin>>new_num;cout<<"请输入新插入的学生成绩：";cin>>new_score;cout<<"请输入新插入的学生姓名：";cin>>new_name;head=insertnode(head,ptr,new_num,new_score,new_name);}}cout<<endl<<"\t座号\t    姓名\t成绩"<<endl;         cout<<"\t=============================="<<endl;ptr=head;while(ptr!=NULL){cout<<"\t["<<setw(2)<<ptr->num<<"]\t[ "<<setiosflags(ios::left)<<setw(10)<<ptr->name<<"]\t["<<setw(3)<<ptr->score<<"]"<<endl;ptr=ptr->rlink;   }free(head);free(newnode);system("pause");return 0;
}

DEMO5:双向链表中节点的删除 

/*
[名称]:ch03_12.cpp
[示范]:双向链表中节点的删除 
*/
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <iomanip>
using namespace std;
class list
{  public:int num,score;char name[10];class list *llink;class list *rlink;
};
typedef class list node;
typedef node *link;link findnode(link head,int num)
{link ptr;ptr=head;while(ptr!=NULL){if(ptr->num==num)return ptr;ptr=ptr->rlink;}return ptr;
}link deletenode(link head,link del)   
{  if(head==NULL) //双向链表是空的{cout<<"[链表是空的]"<<endl;return NULL;}if(del==NULL){cout<<"[错误:不是链表中的节点]"<<endl;return NULL;}if(del==head){head=head->rlink;          head->llink=NULL;}else{if(del->rlink==NULL) //删除链表尾{del->llink->rlink=NULL;}else //删除中间节点{del->llink->rlink=del->rlink;del->rlink->llink=del->llink;}}free(del);return head;
}int main()
{  link head,ptr;link llinknode=NULL;link newnode=NULL;int new_num, new_score;char new_name[10];int i,j,position=0,find,data[12][2];char namedata[12][10]={{"Allen"},{"Scott"},{"Marry"},{"John"},{"Mark"},{"Ricky"},{"Lisa"},{"Jasica"},{"Hanson"},{"Amy"},{"Bob"},{"Jack"}};srand((unsigned)time(NULL));cout<<"座号  成绩  座号  成绩  座号  成绩  座号  成绩"<<endl;cout<<"=============================================="<<endl;for(i=0;i<12;i++){  data[i][0]=i+1;data[i][1]=rand()%50+51;}for(i=0;i<3;i++){  for (j=0;j<4;j++)cout<<"["<<setw(2)<<data[j*3+i][0]<<"] ["<<setw(3)<<data[j*3+i][1]<<"]  ";cout<<endl;}head=new node; //建立链表头指针if(head==NULL){  cout<<"Error!! 内存分配失败!!"<<endl;exit(1);}else{head=new node;head->num=data[0][0];for (j=0;j<10;j++)head->name[j]=namedata[0][j];head->score=data[0][1];llinknode=head;for(i=1;i<12;i++) //建立链表{  newnode=new node;newnode->llink = NULL;newnode->rlink = NULL;newnode->num=data[i][0];for (j=0;j<10;j++)newnode->name[j]=namedata[i][j];newnode->score=data[i][1];llinknode->rlink=newnode;newnode->llink=llinknode;llinknode=newnode;}}while(1){  cout<<"请输入删除的学生编号，结束输入-1：";scanf("%d",&position);if(position==-1) //循环中断条件break;else{  ptr=findnode(head,position);head=deletenode(head,ptr);}}cout<<endl<<"\t座号\t    姓名\t成绩"<<endl;         cout<<"\t=============================="<<endl;ptr=head;while(ptr!=NULL){cout<<"\t["<<setiosflags(ios::right)<<setw(2)<<ptr->num<<"]\t[ "<<setiosflags(ios::left)<<setw(10)<<ptr->name<<"]\t["<<setw(3)<<ptr->score<<"]"<<endl;ptr=ptr->rlink;   }system("pause");return 0;
}

DEMO6:多项式相加

/*
[名称]:ch03_13.cpp
[示范]:多项式相加
*/
#include <iostream>
using namespace std;
class list //声明链表结构
{  public :int coef,exp;class list *next;
};
typedef class list node;
typedef node *link;
link creat_link(int data[4]);
void print_link(link head);
link sum_link(link a,link b);
int main()
{  link a,b,c;int data1[4]={3,0,4,2}; //多项式A的系数int data2[4]={6,8,6,9}; //多项式B的系数cout<<"原始多项式："<<endl<<"A=";a=creat_link(data1);    //建立多项式Ab=creat_link(data2);    //建立多项式Bprint_link(a);          //打印多项式Acout<<"B=";print_link(b);          //打印多项式Bcout<<"多项式相加的结果：\nC=";c=sum_link(a,b);        //C为A、B多项式相加的结果print_link(c);          //打印多项式Csystem("pause");
}
link creat_link(int data[4])//建立多项式子程序
{link head,newnode,ptr;for(int i=0;i<4;i++){  newnode = new node;if(!newnode){  cout<<"Error!! 内存分配失败!!"<<endl;exit(1);}if(i==0){  newnode->coef=data[i];newnode->exp=3-i;newnode->next=NULL;head=newnode;ptr=head;}else if(data[i]!=0){  newnode->coef=data[i];newnode->exp=3-i;newnode->next=NULL;ptr->next=newnode;ptr=newnode;}}return head;
}
void print_link(link head) //打印多项式子程序
{  while(head!=NULL) {  if(head->exp==1 && head->coef!=0)	//X^1时不显示指数cout<<head->coef<<"X + ";else if(head->exp!=0 && head->coef!=0)cout<<head->coef<<"X^"<<head->exp<<" + ";else if(head->coef!=0)           	//X^0时不显示变量cout<<head->coef;head=head->next;}cout<<endl;
}
link sum_link(link a,link b) //多项式相加子程序
{  int sum[4],i=0;link ptr;ptr=b;while(a!=NULL) //判断多项式1{  b=ptr; 	//重复比较A和B的指数while(b!=NULL){  if(a->exp==b->exp)	//指数相等，系数相加{  sum[i]=a->coef+b->coef;a=a->next;b=b->next;i++;}else if(b->exp > a->exp)	//B指数较大，指定系数给C{  sum[i]=b->coef;b=b->next;i++;}else if(a->exp > b->exp)	//A指数较大，指定系数给C{  sum[i]=a->coef;a=a->next;i++;}}}return creat_link(sum);	//建立相加结果的链表C
}