typedef struct node
{
int data;
struct node *next;
}Lnode,*linklist;
void link_print(linklist head); //打印链表
{
linklist *p = head;
if (p == NULL)
{
printf("empty list \n");
}
while(p != NULL)
{
printf("p->data is %d\n",p->data);
p = p->next;
}
}
linklist link_create() //创建链表(后插)并且返回链表的头指针
{
linklist head=NULL,tail=NULL,s1=NULL;
int a;
printf("请输入数据,零除外\n ");
scanf("%d\n",&a);
while(a != 0)
{
s1 = (linklist)malloc(Lnode);
if(s1 == NULL)
{
printf("malloc fail\n");
return head;
}
s->data = a;
if (head == NULL)
{
head = s1;
tail = s1;
head->next = NULL;
}
else
{
tail ->next = s1;
tail = s1;
tail ->next = NULL;
}
printf("请输入数据,零除外\n ");
scanf("%d\n",&a);
}
return head;
}
linklist link_create() //创建链表(前插)并且返回链表的头指针
{
linklist head=NULL,tail=NULL,s1=NULL;
int a;
printf("请输入数据,零除外\n ");
scanf("%d\n",&a);
while(a != 0)
{
s1 = (linklist)malloc(Lnode);
if(s1 == NULL)
{
printf("malloc fail\n");
return head;
}
s->data = a;
if (head == NULL)
{
head = s1;
head->next = NULL;
}
else
{
s1->next = head;
head = s1
}
printf("请输入数据,零除外\n ");
scanf("%d\n",&a);
}
return head;
}
int link_getLength(linklist head)//测试链表的长度
{
linklist p=head ;
int len = 0;
while(p != NULL)
{
len ++;
p=p->next;
}
return len;
}
linklist link_searchByindex(linklist head,int index) //查找链表中的第几个结点
{
int i=0;
linklist p = head ;
if((index<1)||(index>link_getLength(head)))
{
printf(&quot; 不存在 \n&quot;);
return head;
}
for(i=1;i<index;i++)
{
p=p->next;
}
return p;
}
void delete_list(linklist head) //删除整个链表
{
linklist p = head ;
while(head != NULL)
{
p = head->next;
free(head);
head = p;
}
}
int link_insert_add(linklist head,int data,int index)
*入参:head:要插入链表头指针的地址,data插入的数据,index:插入位置
*返回值:插入成功返回0,插入失败返回-1,
*/
{
linklist p = head,s1=NULL;
if((index<1)||(index>link_getLength(head)))
{
printf(&quot;没有这个位子&quot;);
return -1;
}
s1=(linklist)malloc(sizeof(Lnode));
if(s1 == NULL)
{
printf(&quot;malloc fail\n&quot;);
return -1;
}
s1 ->data = data;
if((index ==1)||(head == NULL))
{
s1->next =head;
head = s1;
}
else
{
int len=link_getLength(head);
linklist p=NULL;
p = link_searchByindex(head,index-1);
if(p!=NULL)
{
s1->next = p->next;
p->next = s1;
}
else
{
printf(&quot;insert error\n&quot;);
free(s1);
return -1;
}
}
return 0;
}
linklist link_delete(linklist head,int index) //删除链表中的第index个节点
{
linklist p=head,p1=NULL;
if(p==NULL)
{
printf(&quot;empty list\n&quot;);
return head;
}
if((index<1)||(index>link_getLength(head)))
{
printf(&quot;没有这个节点\n&quot;);
return head;
}
if(index ==1)
{
head =p->next;
free(p);
}
if(index ==(link_getLength(head)))
{
index=index-1;
while(index--)
{
p1=p;
p=p->next;
}
p1->next=NULL;
free(p);
}
if((index != 1)&&(index !=(link_getLength(head))))
{
index=index-1;
while(index--)
{
p1=p;
p=p->next;
}
p1->next = p->next;
free(p);
}
return head;
}
linklist getMaxFormOld(linklist pold)//找节点中最大的data
{
linklist pMax = pold;
linklist p=pold->next;
while(p!=NULL)
{
if(pMax->data < p->data)
{
pMax = p;
}
p=p->next;
}
return pMax;
}
linklist removeFormOld(linklist pold,linklist pmax)//移除链表中的最大节点
{
if(pold == pmax)
{
pold =pold->next;
}
else
{
linklist p =pold;
while(p!=NULL)
{
if(p->next ==pmax)
break;
p=p->next;
}
p->next =pmax->next;
}
return pold;
}
linklist addToNew(linklist pnew,linklist pmax)//添加新的节点
{
pmax->next = pnew;
pnew = pmax;
return pnew;
}
linklist link_sort(linklist pOld)
{
linklist pNew = NULL;
linklist pmax;
while(pOld!=NULL)
{
/*从旧链表上找最大值节点的地址*/
pmax = getMaxFormOld(pOld);
/*将最大值节点从旧链表上拆下来*/
pOld=removeFormOld(pOld,pmax);
/*将最大值节点以前插入的方式插入到新链表*/
pNew=addToNew(pNew,pmax);
}
return pNew;
} |