基础数据结构【四】————环形链表与多项式
生活随笔
收集整理的這篇文章主要介紹了
基础数据结构【四】————环形链表与多项式
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
主要演示環形列表節點的創建插入，?刪除，遍歷，環形鏈表連接?。雙向鏈表節點的建立與插入 ，雙向鏈表中節點的刪除 以及環形鏈表在多項式中的應用
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
}
?
總結
以上是生活随笔為你收集整理的基础数据结构【四】————环形链表与多项式的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： LV的包包大概要多少钱一个？
- 下一篇： 猪脚饭做法的全部过程，正宗猪脚饭怎么做好