C语言数据结构与算法:链表

Python013

C语言数据结构与算法:链表,第1张

先搞清楚基本概念,不懂再问

//    返回一个带头结点的且具有五个结点的链表 

link *initLink()

{

    link * p=(link*)malloc(sizeof(link))    //    创建头结点 

    link * temp=p    //    使用变量temp在下面创建结点时指向链表末端 

    for(int i=1 i<5 i++)

    {

        link *a=(link*)malloc(sizeof(link))    //    创建一个结点 

        a->elem=i        //    为结点赋值 

        a->next=NULL    //    指针域暂时赋为NULL,若后面还要创建结点的话再修改 

        temp->next=a    //    因为temp指向链表末端,即最后一个结点

                        //    故该节点指针域应指向刚才创建的结点 a 

        temp=temp->next//    连接好以后,temp指向下一个结点(刚才创建的结点a,现在是链表末端) 

    }

    return p    //    返回头结点 

}

typedefstruct_List{intdatastruct_List*next}ListintQuery(List**head,intx){List*p=(*head)->nextintn=1while(p&&p->data!=x){p=p->nextn++}if(p)returnnelsereturn-1}

下面给出一个参考程序,与你的要求不完全一样,仅作参考,下面程序在vc++ 6.0运行成功,因为参入了c++的引用做函数参数概念,故下面程序若要在c环境中运行还需要做一些修改。

#include "stdlib.h"

#include "stdio.h"

#define N 5

typedef struct LNode{

int data

struct LNode *next

}LNode,*linklist

void Insertlist(linklist &L,int e)

{

/*L为已知有序递增链表,在L的适当位置插入p,使得L保持有序性*/

linklist p,q,t

p=(linklist)malloc(sizeof(LNode))

p->data=e

if(L->next) /*判断链表L是否为空链表*/

{

q=L->next/*将L第一个元素地址给q*/

t=L

while(q->next&&q->data<p->data)/*若q不是最后一个节点,且q的值小于p的值

则q后移一位*/

{

t=q

q=q->next

}/*查找插入位置*/

if(q->data>=p->data)

{

p->next=q

t->next=p

}

else

{

q->next=p

p->next=NULL

} /*插入节点*/

}

else

{

L->next=p

p->next=NULL

}

} /*Insertlist结束*/

void createlist_l(linklist &L,int t)

{

/*从键盘输入t个整数,建立一个有t个节点的有序链表,节点的值从小到大排列*/

int i,m

L=(linklist)malloc(sizeof(LNode))

L->next=NULL /*建立一个带头节点单链表*/

for(i=ti>0i--)

{

printf("请输入一个整数:") /*打印输入提示信息*/

scanf("%d",&m)/*输入元素值*/

Insertlist(L,m) /*调用插入函数,将新生成的节点插入链表中*/

}

} /*createlist_l结束*/

void mergelist(linklist &L1,linklist L2)

{

/*已知有序递增链表L1和L2,归并L1和L2生成新的有序链表,用的地址L1作为新链表地址返回*/

linklist pa,pb,pc,pd

pa=L1->next

pb=L2->next

pc=L1

while(pa&&pb)

{

if(pa->data<=pb->data) /*若pa的值小于或等于pb的值,则帕pa\pc同时后移*/

{

pc=pa

pa=pa->next

}

else /*若pa的值大于pb的值,则pa前插入pb,pb和pc后移*/

{

pd=pb->next

pb->next=pa

pc->next=pb

pc=pb

pb=pd

}

}

pc->next=pa?pa:pb/*插入剩余段*/

free(L2)/*释放L2的头节点*/

} /*mergelist结束*/

void printlist_l(linklist L)

{

/*打印已知链表*/

linklist p

printf("链表la为\n")

p=L->next

while(p)

{

printf("%5d",p->data)

p=p->next

}

printf("\n\n\n")

} /*printlist_l结束*/

int main(int argc, char* argv[])

{

linklist L1,L2

createlist_l(L1,N)

printlist_l(L1)

createlist_l(L2,N)

printlist_l(L2)

mergelist(L1,L2)

printlist_l(L1)

return 0

}

运行结果

[测试数据]:

输入第一组整数:23 45 11 78 34

输出的排序单链表应为:11 23 34 45 78

输入第二组整数:90 13 45 66 10

输出的排序单链表应为:10 13 45 66 90

合并两个单链表,输出排好序的结果应为:

10 11 13 23 34 45 45 66 78 90