C语言 链表合并并排序

Python021

C语言 链表合并并排序,第1张

/**********start**********//以下是伪代码，有些变量需要定义

if(heada->num

<=

headb->num)//判断第一个节点是在a还是b上，小的作为新链表的头结点，然后设置指示指针pa，pb，p分别在a链表，b链表，新链表上向后移动

{head=heada

pa=heada->next

pb=headb}

else

{head=headb

pa=heada

pb=headb->next}

p=head

while(pa

&&

pb)//当a，b链表都没到达尾部时，比较a，b链表上当前指示指针pa，pb所指节点的大小，并把新链表的p指向较小的(pa或pb所指的)，然后向后移动一下

{

if

(pa->num<=pb->num)

{p->next=pap=p->nextpa=pa->next}

else

{p->next=pbp=p->nextpb=pb->next}

}

if(pa)//说明a链表没到尾部，b链表已结束，直接把a链表剩下的部分接在新链表最后

{

p->next=pa

tail=taila

}

if(pb)//同上b链表后面的部分接在新链表后

{

p->next=pb

tail=tailb

}

tail->next=NULL

/***********end***********/

//创建data型结构，为生成链表做准备

struct data

{

int value

data *next

}

//对链表进行排列的函数

void line(data *p,int n)

{ int temp,i,j

data *tp

for(i=0i<n-1i++)

for(j=0,tp=pj<n-i-1j++,tp=tp->next)

{ if(tp->value>tp->next->value)

{temp=tp->next->value

tp->next->value=tp->value

tp->value=temp

}

}

}

以上是冒泡法对链表排序的例子；

//输出答案的函数

void answer(data *p)

{ while(p!=NULL) {

cout<<p->value<<endl

p=p->next

}

}

以上是遍历链表的函数p是链表的头指针

#include<stdio.h>

#include<malloc.h>

#include<string.h>

struct node

{

char data[20]

struct node*link

}

typedef struct node ListNode

void ListInsert(ListNode**L,char x[]) //构造链表时直接排序

{

ListNode *p, *q, *curr

p = (ListNode*)malloc(sizeof(ListNode))

//构造一个新结点

strcpy(p->data,x)

p->link = NULL

//原链表没有结点的情况

if((*L) == NULL)

{

(*L) = p

return

}

else if(strcmp(x,(*L)->data) <= 0)

{

p->link = (*L)

(*L) = p

return

}

else

{

curr = (*L)

q = (*L)

//找到比x大的第一个元素

while(q != NULL &&strcmp(x,q->data) >= 0)

{

curr = q

q = q->link

}

p->link = curr->link

curr->link = p

return

}

}

void Print(ListNode*L)//输出函数

{

ListNode *curr = L

while(curr!=NULL)

{

printf("%s ",curr->data)

curr=curr->link

}

}

void main()

{

int n,i

char a[20]

ListNode *head

head=NULL

printf("请你输入要输入的元素的个数: ")

scanf("%d",&n)

printf("请你逐个输入%d个字符型元素:\n",n)

for(i = 0i <ni++)

{

scanf("%s",a)

ListInsert(&head,a)

}

printf("链表中数据输出如下：\n")

Print(head)

}