//帶頭結點的單連結清單
#include <iostream>
#include <stdlib.h>
using namespace std;
typedef int ElemType;
typedef struct Node
{
ElemType data;
struct Node *next;
}LNode,*LinkList;
void InitList(LinkList *L);
void Create_head(LinkList l);
void Create_rear(LinkList l);
void Output(LinkList l);
void ReverseList(LinkList l);
LNode *Pos(LinkList l,int i);
void Insert_Order(LinkList &l,int x);
LinkList MergeList(LinkList La,LinkList Lb);
int ListLength(LinkList l);
void SortList(LinkList l);
void ShowMenu()
{
cout<<"——————————————————————————————"<<endl;
cout<<"1、初始化一個單連結清單"<<endl;
cout<<"2、用頭插法建立一個單連結清單"<<endl;
cout<<"3、用尾插法建立一個單連結清單"<<endl;
cout<<"4、輸出一個單連結清單"<<endl;
cout<<"5、反轉一個單連結清單"<<endl;
cout<<"6、按位置查找某節點"<<endl;
cout<<"7、在有序單連結清單中有序插入一個資料"<<endl;
cout<<"8、擷取單連結清單的長度"<<endl;
cout<<"9、對該單連結清單排序"<<endl;
cout<<"10、合并兩個單連結清單"<<endl;
cout<<"0、退出"<<endl;
cout<<"——————————————————————————————"<<endl;
}
int main()
{
ShowMenu();
int n;
LinkList l;
while(1)
{
cout<<"請輸入你要操作的元素序号:";
cin>>n;
switch(n)
{
case 1:
{
InitList(&l);
break;
}
case 2:
{
Create_head(l);
break;
}
case 3:{
Create_rear(l);
break;
}
case 4:{
Output(l);
break;
}
case 5:{
ReverseList(l);
break;
}
case 6:{
cout<<"請輸入你要查找的位置:";
int m;
cin>>m;
LNode *p = Pos(l,m);
if(p)
cout<<"該位置的值為:"<<p->data<<endl;
break;
}
case 7:{
cout<<"請輸入你要插入的元素:";
int x;
cin>>x;
Insert_Order(l,x);
cout<<"插入後輸出該單連結清單:";
Output(l);
break;
}
case 8:{
cout<<"該單連結清單長度為:"<<ListLength(l)<<endl;
break;
}
case 9:{
SortList(l);
cout<<"輸出排序後的連結清單:";
Output(l);
break;
}
case 10:{
LinkList l1,l2;
InitList(&l1);
InitList(&l2);
Create_rear(l1);
Create_rear(l2);
SortList(l1);
SortList(l2);
LinkList p = MergeList(l1,l2);
cout<<"輸出合并以後的連結清單:";
Output(p);
break;
}
case 0:{
exit(0);
break;
}
default:{
cout<<"非法的數字序号!\n";
}
}
}
return 0;
}
void InitList(LinkList *L)
{
*L = new LNode;
(*L)->next = NULL;
}
void Create_head(LinkList l)
{
int m ;
while(1)
{
cin>>m;
if(m==-1)
break;
LNode *s = new LNode;
s->data = m;
s->next = l->next;
l->next = s;
}
}
void Create_rear(LinkList l)
{
cout<<"請依次輸入資料,并以-1作為結束标記:\n";
int m;
LNode *p = l;
while(1)
{
cin>>m;
if(m==-1)
break;
LNode *s = new LNode;
s->data = m;
p->next = s;
p = s;
}
p->next = NULL;
}
void ReverseList(LinkList l)
{
LNode *p = l->next; //p為原連結清單的目前處理節點
l->next = NULL; //逆置單連結清單初始為空
LNode *q;
while(p)
{
q = p->next; //q儲存目前處理節點的下一節點
p->next = l->next;
l->next = p;
p = q;
}
}
/*
LNode *Pos(LinkList l,int i)
{
if(i<=0)
return NULL;
LNode *p = l->next;
int j = 1;
while(j<i && p->next)
{
j++;
p = p->next;
}
if(i==j) return p;
else return NULL;
}
*/
LNode *Pos(LinkList l,int i)
{
if(i<0)
return NULL;
LNode *p = l;
while(i--)
{
p = p->next;
if(p == NULL)
{
return NULL;
break;
}
}
return p;
}
//有序插入
void Insert_Order(LinkList &l,int x)
{
LNode *s = new LNode;
LNode *p,*pre;
s->data = x;
s->next = NULL;
if(l->next == NULL)
l->next = s;
if(x <= l->next->data)
{
s->next = l->next;
l->next = s;
}
else
{
p = l->next;
while(p && x>p->data)
{
pre = p;
p = p->next;
}
s->next = pre->next;
pre->next = s;
}
}
LinkList MergeList(LinkList La,LinkList Lb)
{
LNode *pa,*pb;
LinkList Lc;
pa = La->next;
pb = Lb->next;
Lc = La;
Lc->next = NULL;
LNode *r = Lc;
while(pa && pb)
{
if(pa->data<=pb->data)
{
r->next = pa;
r = pa;
pa = pa->next;
}
else
{
r->next = pb;
r = pb;
pb = pb->next;
}
}
if(pa)
r->next = pa;
else
r->next = pb;
delete Lb;
return Lc;
}
int ListLength(LinkList l)
{
LNode *p = l->next;
int len = 0;
while(p)
{
len++;
p = p->next;
}
return len;
}
void SortList(LinkList l)
{
LinkList p;
int n,i,j;
int temp;
n = ListLength(l);
if(n==0)
return;
p = l->next;
for(i=1;i<n;i++)
{
p = l->next;
for(j=0;j<n-j;j++)
{
if(p->data > p->next->data)
{
temp = p->data;
p->data = p->next->data;
p->next->data = temp;
}
p = p->next;
}
}
}
void Output(LinkList l)
{
LNode *p;
p=l->next;
while(p)
{
cout<<p->data<<" ";
p = p->next;
}
cout<<"\n";
}