链表合并
数据结构
课程
设计
领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计
报告
软件系统测试报告下载sgs报告如何下载关于路面塌陷情况报告535n,sgs报告怎么下载竣工报告下载
设计题目:链表合并
学 院 经济与管理学院
专 业 信息管理与信息系统
班 级 信管102
学 号 3100561028
姓 名 田龙波
2011秋季学期
一、问题描述
实现两个链表的合并。
二、基本要求
1) 建立两个链表A和B，链表元素个数分别为m和n个;
2) 假设元素分别为(x1,x2,…xm)，和(y1,y2, …yn);
3)把它们合并成一个顺序表C，使得:当m>=n时，C=x1,y1,x2,y2,…xn,yn,…,xm
当n>m时，C=y1,x1,y2,x2,…ym,xm,…,yn 4)输出顺序表C
5) 用直接插入排序法对顺序表C进行升序排序，生成链表D，并输出链表D。 6)能删除链表D中指定位置和指定值的元素。
三、算法思想
首先定义一个结构体，然后建立两个链表A和B，输入A，B的长度a,b及数据，并显示输入的A，B的信息。链表元素把它们合成一个表C，要实现当a>=b时C=x1,y1,x2,y2,…xn,yn,…,xm当b>a时，C=y1,x1,y2,x2,…ym,xm,…最后显示C的信息，用直接插入排序法对表C进行升序排序，生成链表D，并输出链表D。删除链表D中的信息，首先找到要删除的位置然后进行删除操作，删除后显示信息
四、数据结构
带头结点的链表结点结构定义如下:
struct Node
{
int number;
struct Node *next;
};
五、模块划分
(1) struct Node()，功能是定义结构体;
(2) struct Node *create()，功能是创建单链表;
(3) void showlist()，功能是显示单链表所有元素;
(4) struct Node * inter_link()，功能是合并两个链表;
(5) void InsertSort()，功能椒用直接插入排序法进行排序; (6)void DelList()，功能是删除单链表中第i个元素;
(7)void main()，功能是调用其他子函数实现算法。
六、源程序
#include
#include
#include
#include
#define L sizeof(struct Node)
struct Node /*定义结构体*/ {
int number;
struct Node *next;
};
struct Node *create(int a) /*创建单链表*/ {
int n;
struct Node *p1, *p2, *head;
head = NULL;
n = 0;
p2 = p1 = (struct Node *) malloc(L);
scanf("%d", &p1->number);
while (a)
{
n = n + 1;
if (n == 1)
head = p1;
else
p2->next = p1;
p2 = p1;
p1 = (struct Node *) malloc(L);
if (a != 1)
scanf("%d", &p1->number);
a--;
}
p2->next = NULL;
return (head);
}
void showlist(struct Node *head)
{
struct Node *p;
p = head;
if (head != NULL)
do
{
printf("%d", p->number);
printf(" ");
p = p->next;
}
while (p != NULL);
printf("\n");
}
struct Node * inter_link(struct Node * ch1, int a, struct Node * ch2, int b)
{
int temp;
struct Node *head, *p1, *p2, *p;
if (a >= b) /*判断a，b大小并合并 */
{
head = p1 = ch1;
p2 = ch2;
} else
{
head = p1 = ch2;
p2 = ch1;
temp = a, a = b, b = temp; /*交换a和b*/
}
p = head; /*p指向p1中的第一个元素*/
while (p2 != NULL)
{
p1 = p1->next;
p->next = p2;
p = p2;
p2 = p2->next;
p->next = p1;
p = p1;
}
return head;
}
void InsertSort(struct Node *p, int m) /*排序*/ {
int i, j, t;
struct Node *k;
k = p;
for (i = 0; i < m - 1; i++)
{
for (j = 0; j < m - i - 1; j++)
{
if (p->number > (p->next)->number)
{
t = p->number;
p->number = (p->next)->number;
(p->next)->number = t;
}
p = p->next;
}
p = k;
}
}
void DelList(struct Node *head,int i) /*删除单链表中第i个元素*/
{
struct Node*p,*q;
int j=0;
if(head->next==NULL)
{
printf("\n\t\t\t线性表已经为空～\n");
return;
}
if(i<1)
{
printf("\n\t\t\t位置不合法～\n");
return;
}
p=head;
while(p->next!=NULL && jnext;
j++;
}
if(p->next==NULL || j>i-1)
{
printf("\n\t\t\t没找到要删除的位置～\n");
return;
}
else
{
q=p->next; p->next=q->next; /*删除第i个结点*/
free(q);
}
}
void main()
{
struct Node *p1, *p2;
int a,b;
int h,i;
printf("请输入第一个链表A:\n");
printf("输入链表的长度a:");
scanf("%d", &a);
printf("请输入链表数据:");
p1 = create(a);
printf("链表A的信息: ");
showlist(p1);
printf("请输入第二个链表B:\n");
printf("输入链表的长度b:");
scanf("%d", &b);
printf("请输入链表数据:");
p2 = create(b);
printf("链表B的信息:");
showlist(p2);
p1 = inter_link(p1, a, p2, b);
h = a + b;
printf("合并后的链表C:");
showlist(p1);
InsertSort(p1, h);
printf("排序后的链表:");
showlist(p1);
printf("请输入要删除的位置:");
scanf("%d",&i);
DelList(p1,i-1);
printf("删除后的链表:");
showlist(p1);
}
七、测试数据
(1)A表:12 65 48
B表:22 78 55 16 87 (2)A表:36 5 11 91 25
B表:45 2 77 68
八、运行及测试情况
运行界面为:请输入第一个链表A:
输入链表的长度a:3
请输入链表数据:12 65 48
链表A的信息: 12 65 48 请输入第二个链表B:
输入链表的长度b:5
请输入链表数据:22 78 55 16 87 链表B的信息:22 78 55 16 87
合并后的链表C:22 12 78 65 55 48 16 87
排序后的链表:12 16 22 48 55 65 78 87
请输入要删除的位置:2
删除后的链表:12 22 48 55 65 78 87
Press any key to continue
请输入第一个链表A:
输入链表的长度a:5
请输入链表数据:36 5 11 91 25
链表A的信息: 36 5 11 91 25 请输入第二个链表B:
输入链表的长度b:4
请输入链表数据:45 2 77 68
链表B的信息:45 2 77 68
合并后的链表C:36 45 5 2 11 77 91 68 25
排序后的链表:2 5 11 25 36 45 68 77 91
请输入要删除的位置:4
删除后的链表:2 5 11 36 45 68 77 91 Press any key to continue
九、实验总结
通过这次数据结构课程设计，我对单链表的认识有了更深刻的了解，现已经掌握了尾插法建立单链表，两个链表的合并，直接插入排序法排序及删除指定位置的数值等算法，最终实现了两个链表的合并，同时也体会到了恰当的算法思想的重要性以及一个程序的完整性和治学的严谨性。在实验的过程中我也遇到这样的问题:定义的结构体有误，语法出错，输入的数据类型与定义的类型不一致等等。我及时地向老师同学询问，解决了自己地难题。这次实验我获益匪浅，也认识到自己薄弱的环节，为以后的学习打下了基础。
浙公网安备 33021202002483