#include <iostream.h>
#include <stdlib.h>
#define NULL 0
typedef struct NODE
{
int data;
struct NODE *next;
} LNode, *LList;
LList ListCreat(int n) //创建带头结点的链表
{
int i;
LList L,head,p1,p2;
L=(LList)malloc(sizeof(NODE));
p1=(LList)malloc(sizeof(NODE));
cout<<"请输入第1个数:";
cin>>p1->data;
head=NULL;
for(i=1;i<n;i++)
{
if(i==1) head=p1;
else p2->next=p1;
p2=p1;
p1=(LList)malloc(sizeof(NODE));
cout<<"请输入第"<<i+1<<"个数:";
cin>>p1->data ;
}
p2->next=p1;
p2->next->next=NULL;
L->next=head;
cout<<"---------------------------------------------------------"<<endl;
return(L);
}
void PrintD(LList &L) //遍历单链表
{
LList p;
p=L->next;
while(p!=NULL)
{
cout.width(6);
cout<<p->data;
p=p->next;
}
cout<<endl;
}
void PrintN(LList &L) //遍历指针域
{
LList p;
int i=1;
p=L;
while(p!=NULL)
{
cout.width(14);
cout<<p->next;
if(i%5==0) cout<<endl;
p=p->next;
i++;
}
cout<<endl<<"---------------------------------------------------------"<<endl;
}
void DeleteElem(LList &L, int i) //删除带头结点的链表的第i个元素
{
LList p=L, q;
int j=0;
while (p->next && j<i-1)
{
p = p->next;++j;
}
if (!(p->next)||j>i-1)
cout<<"ERROR"<<endl;
q=p->next; p->next=q->next;
free(q);
cout<<"删除第"<<i<<"个元素后的链表为:"<<endl;
PrintD(L);
cout<<"删除第"<<i<<"个元素后的指针域为:"<<endl;
PrintN(L);
}
void ListInsert(LList &L, int i,int e) // 在带头结点的单链线性表L的第i个元素之前插入元素e
{
LList p,s;
p = L;
int j = 0;
while (p && j < i-1)
{
p = p->next;
++j;
}
if (!p || j > i-1) cout<<"ERROR"<<endl;
s = (LList)malloc(sizeof(NODE));
s->data = e; s->next = p->next;
p->next = s;
cout<<"在链表第"<<i<<"处插入"<<e<<"后的链表为:"<<endl;
PrintD(L);
cout<<"在链表第"<<i<<"处插入"<<e<<"后的指针域为:"<<endl;
PrintN(L);
}
void ListReverse(LList &L) //翻转单链表
{
LList p=L->next,q,front=NULL;
while(p!=NULL)
{
q=p->next;
p->next=front;
front=p;
p=q;
}
L->next=front;
cout<<"倒置后的链表为:"<<endl;
PrintD(L);
cout<<"倒置后的链表的指针域为:"<<endl;
PrintN(L);
}
void main() //主函数
{
LList H;
int n1,n2,n3,n4;
cout<<"开始执行程序:"<<endl;
cout<<"---------------------------------------------------------"<<endl;
cout<<"请输入链表长度:";
cin>>n1;
cout<<"---------------------------------------------------------"<<endl;
H=ListCreat(n1);
cout<<endl<<"创建长度为"<<n1<<"的链表:"<<endl;
PrintD(H);
cout<<"初始化链表指针域为:"<<endl;
PrintN(H);
cout<<"请输入删除元素位置:";
cin>>n2;
DeleteElem(H, n2);
cout<<"请输入插入元素位置和值:";
cin>>n3>>n4;
ListInsert(H, n3,n4);
ListReverse(H);
}