2025年高效链表合并算法实战解析与优化技巧

EASTCHINAINSTITUTEOFTECHNOLOGY

课程设计汇报

课程设计题目：两个链表的合并

专业：软件工程

班级：

姓名：

学号：

指导教师：

年月日

目录

1.课程设计的目的及规定

2.课程设计的内容（分析和设计）

3.算法流程图

4.详细环节

5.代码

6.显示成果

7.课程设计的总结

一.课程设计的目的及规定

1.目的：实现两个链表的合并

2.规定：

（1）建立两个链表A和B,链友元素个数分别为m和n个。

（2）假设元素分别为（xl,x2,…xm）,和（yl,y2,…yn）。把它们合并成一种线形表C,使得：

当m>=n时，C=x1,y1,x2.y2,...xn.yn,...,xm

当n>m时，C=y1,x1,y2.x2,...yin,xm,...,yn

输出线形表C

（3）用直接插入排序法对C进行升序排序，生成链表D,并输出链表D。

（4）能删除指定单链表中指定位子和指定值的元素。

二.课程设计的内容（分析和设计）

1・.分析

由题目的有关信息可以分析得：苜先我们需要建立两个跳表AB.A链表的元素个数为m,B链表的

元素个数为n；在将A、B链表进行合并，根据m和n的大小关系决定链表C的元素次序；再将C

进行直接插入排序得到一种新的链表D；没次输入完一次链表信息，程序都会对对应的链表进行输入

操作以此保证程序输入的数据是你想要输入的数据。同步当你合并好和排序好后都会进行输出操作。

最终当排序好后你可以指定你所要删除数据的位置来删除你所要删除的数据。

2.设计

本次课程设计所需要用到的是有关链表的建立、合并以及直接插入排序的排序算法。需要先建立两个

链表，再将其合并为一种无序链表，最终对这个无序链表进行直接插入排序并将其输出。难点在于将

AB合并为链表C的操作以及对链表C进行直接插入排序的操作和根据顾客的意愿可以对链表进行删

除的操作。

三.算法流程图

四.详细环节

(1)构造体的创立：structNode

⑵链表的创立：structNode"create()链表的创立。

(3)链表的输出：voidprint(structNode*head)功能是*『链表进行输出。

(4)链表的合并：structNode*inter_link(structNode*chainI.inta.structNode*chain2.intb)

算法的功能是实现两个链表的交叉合并，并且可以根据两链表的长短将行不通的插入。

(5)排序：voidInseriSort(slruclNode*p,intm)算法的功能是对一合并好的链表进行升序插入排

序。

(6)按位删除操作：structNode*dclc(e_link(structNode*p,：nti)。

(7)按值删除操作：structNode*dclcte_linkz(structNode*i)«

(8)上函数：main。函数重耍是对算法进行测试。

五.代码

structNode〃数据构造定义如卜.:

longintnumber;

structNode*next;

}Node,*linkList;

#include<stdlib.h>〃源程序：

#include<stdio.h>

#inckidc<conio.h>

#include<malkx:.h>

#defineerror0

#dcfinenull1

#defineLsizeof(siructNode)

structNode*create(inta)//链表创立函数

{

intn;

structNode*pl,*p2.*hcad;

head=NULL;

n=0;

p2=pi=(structNode*)malloc(L);〃分派内存

scanf("%ld",&pl->numbcr);

while(a)〃录入链表信息

(

n=n+1;

if(n==1)

head=pl;

else

p2->nex(=pl;

P2=pl；

pl=(structNode*)malloc(L);

if(a!=1)〃分派内存

scanf("%ld'\&p1->number);

ay〃控制输入的个数

)

p2->next=NULL;

return(head):

}〃链表创立函数结束

voidprint(structNode*head)〃输出函数

structNode*p;

p=head;

printf("数字:\n")；

if(head!=NULL)

d。〃循环实现输出

(

p->number);

printf("");

p=p->next;

}while(p!=NULL);

printf("\n");

)

〃链表的交叉合并算法

structNode*intcr_link(structNode*chain1,inta,structNode*chain2,intb)(

int(emp;

structNode*head,*pl,*p2,*pos;

/*判断a,b大小并合并*/

if(a>=b){

head=pl=chainl;

p2=chain2;

}else/*b>a*/{

head=pl=chain2;

p2=chainl;

temp=a,a=b,b=temp;/*互换a和b*/

)

/*下面把pl的每个元素插在p2对应元素之前，pl长a.p2长b*/

pos=head;/*此时pos指向pl中的第一种元素*/

while(p2!=NULL){〃漂亮，蛇形插入

pl=pl->next;

pos->next=p2;

pos=p2;

p2=p2->next;

pos->next=pl;

pos=pl;

)

returnhead;

}

〃对合并好的钵表讲行排序

voidInscnSort(structNode*p.intm)〃排序函数

(

inti,j,t;

structNode*k;

k=p；

for(i=0;i<m-l;i++){

for(j=0;j<m-i-l;j++){

if(p->number>(p->next)->number){

t=p->number;

p->numbcr=(p->ncxt)->nuinbcr;

(p->next)->number=t;

)

p=p->ncxt;

1

p=k;

)

)

structNode♦delete_link(structNode*i)〃按位删除

{structNode*q;

intj=O;

while(j<i-l&&p->next)

{p=p->ncxt;

j++；

)

if(j==i-l&&p->ncxt)

(

q=p->next;

p->ncxt=q->ncxt;

free(q);

)

elsereturnerror;

)

structNode*delete_linkz(structNode*p,in[i)〃按值删除

{structNode*q;

structNode*k：

intj=O;

inth=();

while(p&&p->numher!=i)

p=p->next;

j++；

if(p)

(

while(h<j-l&&p->ncxt){

p=p->next;

h++;

)

if(h==j-l&&p->next){

k=p->next;

p->next=k->next;

free(k);

}

)

else

returnerror;

)

〃主函数

intniain()//niain函数

{

structNode*pl,*p2;

inta;

intb;

inth;

intt;

intm;

printf("请输入第一种链表:\n");

printf("\n输入链表的长度a:\n");

scanf("%d",&a);

printf("请输入链表数据：”);

p1=create(a);

printf("\n你刚刚输入的第一种链表信息:\n")；

print(pl);

printf("\n请输入第二个链表:\n");

printf("\n输入链表的长度b:\iT);

scanf(”％d”,&b);

printf("请输入链表数据：”)；

p2=create(b);

printf("\n你刚刚输入的第二个链表的信息:\n”)；

print(p2);

pi=inter_link(pl.a,p2,?);

h=a+b;

printf(”\n合并后的链表\n：");

print(pl);

InscrtSort(pl,h);

printf("\n排序后的链表:\n");

print(pl);

printf("\n请输入钵表中你所要删除数据的所在位皆:\n)

scanfC%d”,&t);

dele〔e」ink(pl,t);

printf("\n链表删除数据后链表的信息:\n”)；

print(pl);

printf("\n请输入你想要删除的数值:\n");

scanf("%d",&m);

delete_linkz(p1,m);

printf("\n链表删除数据后链表的信息

print(pl);

return0;

｝六.显示成果

(1)m<n

Ic，r*C:\Docu>entsandSettinesVAdainistrator\^Sl\Debue\tina.exe'-nx

p青输入笫一个链表：

将人链表的长度a：

请输入链表数据：1222232114

你刚才输入的笫一个链表信息、：

数字：

1222232114

请输入第二个链表:

输入链表的长度b：

▼

*C:\DocuBentsandSettings'AdBinistratorA臬面\Debug\tina.exe*

请输入第二个链表：

输入链表的长度b:

7

请输入链表数据：11223344556688

你刚才输入的第二个链表的信息：

数字：

11223344556688

口7握的链表

L：|景

it1122223333442155156688

爹梦的链表:

厂-

111115212222333344556688

Pressanykeytocontinue

(2)m>n

[c(.C:\DocuBeirtsandSettings'Adainistratoir'桌面\Debug\tina・exe'

请输入笫一个链表:

输入链表的长度a：

7

请输入链表数据：11223344556688

你刚才输入的第一个链表信息：

数字：

11223344556688

请输入第二个链表:

输入链表的长度出

3.m=n

[c(.C:\Docu>eTrtsandSettings\Ad>inistra~to【\桌面\Debug\tina,exe'

请输入第一个链表:

型入链表的长度a：

请输入链表数据：1122334455

你刚才输入的第一个链表信息：

数字：

1122334455

请输入第二个链表:

输入链表的长度b：

*C:\Docu>entsandSetati.ngs\AdBinistrator\臬面\Debug\tina.exe'

请输入第二个链表:

倒入链表的长度b：

情输入链表数据：1214253621

忤刚才输入的第二个链表的信息:

散字：

螺恒的链表

11122214332544368821

后

的

链表

田

u序