1.设有n 个整数组成的序列存放于一个带头结点的单链表中，HEAD为头指针。每个整数为－1，0，1之一。。。。

Question

1.设有n 个整数组成的序列存放于一个带头结点的单链表中，HEAD为头指针。每个整数为－1，0，1之一。编写一个时间复杂度为O（n）的算法，使该序列按负数、零、正数的次序排好。(数据结构问题，用C解决)

Answer 1

//此题适用计数排序
#include <stdio.h>
#include <stdlib.h>

typedef struct node
{
int num;
struct node * next;
}Node, *List;

List ListInit(List Head, int n)
{
List p;
int i;
for(i = 0; i < n; i ++)
{
p = (List)malloc(sizeof(Node));
p->next = Head;
Head = p;
}
return Head;
}
List ListReleas(List Head)
{
List p = Head;

while(Head)
{
p = Head;
Head=p->next;
free(p);
}
return Head;
}

int main()
{
List Head = NULL, p = NULL;
int count[3] = {0}, n, inum;
printf("输入节点数：");
scanf("%d", &n);
Head = ListInit(Head, n);

printf("输入每个节点值（共%d个，只接受-1,0,1）：\n", n);
p = Head;
while( p != NULL )
{
scanf("%d", &p->num);
if(p->num < 2 && p->num > -2)
p = p->next;
}

//以下为排序（计数排序）
p = Head;
while( p != NULL )
{
count[p->num + 1] ++;
p = p->next;
}

p = Head;
inum = -1;
while( p != NULL )
{
if(count[inum + 1])
{
p->num = inum;
p = p->next;
count[inum + 1]--;
}
else
inum ++;
}

//以下为输出
p = Head;
while( p != NULL )
{
printf("%d ", p->num);
p = p->next;
}
printf("\n");

ListReleas(Head);

return 0;
}

Answer 2

PS:按我对时间复杂度的理解,只要不嵌套循环,算法的时间负复杂度应为O(n),但不绝对,也有其它情形存在.如果时间复杂度不对,请你自己思考下,怎么解决,自己要多练习,多思考.
刚刚突然想起来有两种情况没考虑,有bug存在,重新修改了.
#include <stdio.h>
#include <stdlib.h>

typedef struct LinkNode
{
int data;
struct LinkNode *next;
}STRU_LINKLIST;

void CreateList(STRU_LINKLIST *asp_Head, int ai_Num)
{
/*逆序建立链表*/
int li_Index;
STRU_LINKLIST *lsp_Temp;

for (li_Index = ai_Num; li_Index > 0; --li_Index)
{
lsp_Temp = (STRU_LINKLIST *)malloc(sizeof(STRU_LINKLIST)); /*新节点*/
scanf("%d",&lsp_Temp->data);/*节点值*/
if( lsp_Temp->data > 1 || lsp_Temp->data < -1 )
{
printf("输入值非法,使用默认值 1!!\n");
lsp_Temp->data = 1;
}
lsp_Temp->next = asp_Head->next;
asp_Head->next = lsp_Temp;
}
}

void ListSort(STRU_LINKLIST *asp_Head, int ai_NodeNum)
{
STRU_LINKLIST *lsp_Tail; /*链表尾部指针*/
STRU_LINKLIST *lsp_Curr; /*当前位置*/
STRU_LINKLIST *lsp_Front; /*当前指针的前一个位置*/
int li_Index;

lsp_Tail = asp_Head;
lsp_Front = asp_Head;
lsp_Curr = asp_Head;

/*找到链表尾*/
for ( li_Index = 0; li_Index < ai_NodeNum; ++li_Index)
lsp_Tail = lsp_Tail->next;

lsp_Curr = lsp_Curr->next; /*指向第一个节点*/

li_Index = ai_NodeNum;
while ( li_Index--)
{
/*第一个节点值为-1,直接跳过*/
if ( (li_Index == ai_NodeNum - 1) && lsp_Curr->data == -1 )
{
lsp_Curr = lsp_Curr->next;
lsp_Front = lsp_Front->next;
continue;
}
/*最后一个节点是1,不做调整*/
if ( ( li_Index == 0 ) && lsp_Curr->data == 1 )
{
continue;
}
/*如果节点的值为1,将其调整到链表尾*/
if ( lsp_Curr->data == 1 )
{
lsp_Front->next = lsp_Curr->next; /*调整链表*/
lsp_Curr->next = NULL; /*断开连接*/
lsp_Tail->next = lsp_Curr; /*插入到链表尾部*/
lsp_Tail = lsp_Tail->next; /*将尾指针调整到结尾*/
lsp_Curr = lsp_Front->next; /*调整当前节点指针*/
continue;
}
/*如果节点的值为0,节点位置不做调整*/
if ( lsp_Curr->data == 0 )
{
lsp_Curr = lsp_Curr->next;
lsp_Front = lsp_Front->next;
continue;
}
/*如果节点的值为-1,将其调整到链表头*/
if ( lsp_Curr->data == -1 )
{
lsp_Front->next = lsp_Curr->next;
lsp_Curr->next = asp_Head->next;
asp_Head->next = lsp_Curr;
lsp_Curr = lsp_Front->next;
}
}
}
int main()
{
STRU_LINKLIST *lsp_Head;
STRU_LINKLIST *lsp_Temp;
int li_NodeNum;
int li_Index;

lsp_Head = (STRU_LINKLIST *)malloc(sizeof(STRU_LINKLIST));
lsp_Head->next = NULL;/*建立头节点*/
lsp_Temp = lsp_Head;

printf("输入要创建的节点个数(链表逆序建立):");
scanf("%d",&li_NodeNum);
printf("输入节点值,只能为0,1,-1\n");

CreateList(lsp_Head, li_NodeNum); /*创建链表*/
lsp_Temp = lsp_Temp->next;/*调整到第一个节点*/
printf("链表当前顺序为:");
for ( li_Index = 0; li_Index < li_NodeNum; ++li_Index )
{
printf("%d\t", lsp_Temp->data);
lsp_Temp = lsp_Temp->next;
}

ListSort(lsp_Head, li_NodeNum);
printf("\n排序后的顺序为:");
lsp_Temp = lsp_Head->next;/*调整到第一个节点*/
for ( li_Index = 0; li_Index < li_NodeNum; ++li_Index )
{
printf("%d\t", lsp_Temp->data);
lsp_Temp = lsp_Temp->next;
}
return 0;
}

Answer 3

#include <iostream.h>

class Node //链表结点类
{
public:
Node():next(NULL){}
Node(int n,Node * ptr=NULL):num(n),next(ptr){}
Node * next;
int GetNum() const
{
return num;
}
private:
int num;
};

class List //链表类
{
friend ostream & operator <<(ostream & os,List & l); //重载输出,用于输出链表
public:
List():head(NULL){} //缺省构造函数
List(int * a,int size); //从数组构造链表
int Add(int n); //增加结点
int Del(int n); //删除结点
private:
Node * head;
};

List::List(int * a,int size)
{
head=NULL;
for(int i=0;i<size;i++)
Add(a[i]);
}

int List::Add(int n)
{
if(head==NULL)
{
head=new Node(n);
return 1;
}
else
{
Node * p=head;
while(p->next!=NULL)
p=p->next;
p->next=new Node(n);
return 1;
}
return 0;
}

int List::Del(int n)
{
Node * p=head;
while(p!=NULL)
{
if(p->GetNum()==n)
{
if(p==head)
{
head=head->next;
delete p;
p=head;
}
else
{
Node * r=head;
while(r->next!=p)
r=r->next;
r->next=p->next;
delete p;
p=r->next;
}
}
if(p!=NULL)
p=p->next;
}
return 1;
}

ostream & operator <<(ostream & os,List & l)
{
Node * p=l.head;
while(p!=NULL)
{
os<<p->GetNum()<<" ";
p=p->next;
}
return os;
}

int main()
{
int in,i;
int a[10];
cout<<"输入10个数,存放在数组中:"<<endl;
for(i=0;i<10;i++)
{
cin>>a[i];
}
List l(a,10);
cout<<l<<endl;

cout<<"输入一个要加入到链表的数据:"<<endl;
cin>>in;
l.Add(in);
cout<<l<<endl;

cout<<"输入一个要删除的数据:"<<endl;
cin>>in;
l.Del(in);
cout<<l<<endl;
return 0;
}