#include <malloc.h>
#include <stdio.h>
#include
using namespace std;
const int MAXSIZE=100;
typedef int ElemType;
typedef struct node
{\tElemType data;\ \t\t\t\t//数据域
\tstruct node *next;\ \t\t\t\t//指针域
} SLinkNode;\ \t\t\t\t\t\t//单链表结点类型
void InitList(SLinkNode *&L)\t\t\t\t\t\t\t\t//初始化单链表L
{\tL=(SLinkNode *)malloc(sizeof(SLinkNode));\t//创建头结点L
\tL->next=NULL;
}
void DestroyList(SLinkNode *&L)\t\t\t\t//销毁单链表L
{\tSLinkNode *pre=L,*p=pre->next;
\twhile (p!=NULL)
\t{\tfree(pre);
\t\tpre=p; p=p->next;\ \t\t\t//pre、p同步后移
\t}
\tfree(pre);
}
int GetLength(SLinkNode *L)\t\t\t\t//求长度
{\tint i=0;
\tSLinkNode *p=L->next;
\twhile (p!=NULL)
\t{\ti++;
\t\tp=p->next;
\t}
\treturn i;
}
int GetElem(SLinkNode *L,int i,ElemType &e)\t//求第i个结点值
{\tint j=0;
\tSLinkNode *p=L;\ \t\t\t\t\t//p指向头结点，计数器j置为0
\tif (i<=0) return 0;\ \t\t\t\t\t//参数i错误返回0
\twhile (p!=NULL && j<i)
\t{\tj++;
\t\tp=p->next;
\t}
\tif (p==NULL)
\t\treturn 0;\ \t\t\t\t\t//未找到返回0
\telse
\t{\te=p->data;
\t\treturn 1;\ \t\t\t\t//找到后返回1
\t}
}
int Locate(SLinkNode *L,ElemType e)\t//求第一个值为e的结点位置
{\tSLinkNode *p=L->next;
\tint j=1;\ \t\t\t\t\t\t\t//p指向第一个数据结点，j置为其序号1
\twhile (p!=NULL && p->data!=e)
\t{\tp=p->next;
\t\tj++;
\t}
\tif (p==NULL) return(0);\ \t\t\t//未找到返回0
\telse return(j);\ \t\t\t\t//找到后返回其序号
}
int InsElem(SLinkNode *&L,ElemType x,int i)\t//插入结点值为x的结点
{\tint j=0;
\tSLinkNode *p=L,*s;
\tif (i<=0) return 0;\ \t\t\t\t//参数i错误返回0
\twhile (p!=NULL && j<i-1)\t\t//查找第i-1个结点p
\t{\tj++;
\t\tp=p->next;
\t}
\tif (p==NULL)
\t\treturn 0;\ \t\t\t\t//未找到第i-1个结点时返回0
\telse\ \t\t\t\t\t\t\t\t//找到第i-1个结点p
\t{\ts=(SLinkNode *)malloc(sizeof(SLinkNode));
\t\ts->data=x;\ \t\t\t\t\t//创建存放元素x的新结点s
\t\ts->next=p->next;\ \t\t\t//将s结点插入到p结点之后
\t\tp->next=s;
\t\treturn 1;\ \t\t\t\t//插入运算成功,返回1
\t}
}
int DelElem(SLinkNode *&L,int i)\t//删除结点
{\tint j=0;
\tSLinkNode *p=L,*q;
\tif (i<=0) return 0;\ \t\t\t\t//参数i错误返回0
\twhile (p!=NULL && j<i-1)\t\t//查找第i-1个结点
\t{\tj++;
\t\tp=p->next;
\t}
\tif (p==NULL)
\t\treturn 0;\ \t\t\t\t//未找到第i-1个结点时返回0
\telse\ \t\t\t\t\t\t\t//找到第i-1个结点p
\t{\tq=p->next;\ \t\t\t\t\t//q指向被删结点
\t\tif (q==NULL)
\t\t\treturn 0;\ \t\t\t\t//没有第i个结点时返回0
\t\telse
\t\t{\tp->next=q->next;\ \t//从单链表中删除q结点
\t\t\tfree(q);\ \t\t\t\t//释放其空间
\t\t\treturn 1;
\t\t}
\t}
}
void DispList(SLinkNode *L)\t\t\t//输出单链表
{\tSLinkNode *p=L->next;
\twhile (p!=NULL)
\t{\tprintf("%d ",p->data);
\t\tp=p->next;
\t}
\tprintf("\n");
}
void CreateListF(SLinkNode *&L,ElemType a[],int n)\t//头插法建表
{\tSLinkNode *s; int i;
\tL=(SLinkNode *)malloc(sizeof(SLinkNode));\t\t//创建头结点
\tL->next=NULL;\ \t\t\t\t\t\t\t\t\t//头结点的next域置空
\tfor (i=0;i<n;i++)\ \t\t\t\t\t\t\t//遍历a数组所有元素
\t{\ts=(SLinkNode *)malloc(sizeof(SLinkNode));
\t\ts->data=a[i];\ \t\t\t\t\t\t//创建存放a[i]元素的新结点s
\t\ts->next=L->next;\ \t\t\t\t\t//将s插在头结点之后
\t\tL->next=s;
\t}
}
void CreateListR(SLinkNode *&L,ElemType a[],int n)\t//尾插法建表
{\tSLinkNode *s,*tc; int i;
\tL=(SLinkNode *)malloc(sizeof(SLinkNode));\t\t//创建头结点
\ttc=L;\ \t\t\t\t\t\t\t\t\t\t//tc为L的尾结点指针
\tfor (i=0;i<n;i++)
\t{\ts=(SLinkNode *)malloc(sizeof(SLinkNode));
\t\ts->data=a[i];\ \t\t\t\t\t\t//创建存放a[i]元素的新结点s
\t\ttc->next=s;\ \t\t\t\t\t\t\t//将s结点插入tc结点之后
\t\ttc=s;
\t}
\ttc->next=NULL;\ \t\t\t\t\t\t\t//尾结点next域置为NULL
}
//补充代码
void Move(SLinkNode *&L) {
\tSLinkNode * negativeHead = (SLinkNode *)malloc(sizeof(SLinkNode));
\tSLinkNode * zeroHead = (SLinkNode *)malloc(sizeof(SLinkNode));
\tSLinkNode * positiveHead = (SLinkNode *)malloc(sizeof(SLinkNode));
\tSLinkNode * negativeTail = negativeHead;
\tSLinkNode * zeroTail = zeroHead;
\tSLinkNode * positiveTail = positiveHead;
\tSLinkNode * p = L->next;
\twhile (p != NULL) {
\t\tif (p->data < 0) {
\t\t\tnegativeTail->next = p;
\t\t\tnegativeTail = p;
\t\t} else if (p->data == 0) {
\t\t\tzeroTail->next = p;
\t\t\tzeroTail = p;
\t\t} else {
\t\t\tpositiveTail->next = p;
\t\t\tpositiveTail = p;
\t\t}
\t\tp = p->next;
\t}
\tnegativeTail->next = zeroHead->next;
\tzeroTail->next = positiveHead->next;
\tpositiveTail->next = NULL;
\tL->next = negativeHead->next;
\tfree(negativeHead);
\tfree(zeroHead);
\tfree(positiveHead);
}
int main()
{
\tSLinkNode *L;
\tint n;
\tElemType a[MAXSIZE];
\tcin >> n;
\tfor(int i=0; i<n; i++)
\t\tcin >> a[i];
\tCreateListR(L, a, n);\ \t\t\t\t\t//尾插法建表
\tMove(L);
\tDispList(L);
\tDestroyList(L);
\treturn 0;
}
