单链表练习实验报告 - --李兴福

单链表练习实验

——————电信14--1班 20141303225 李兴福

实验目的：熟练掌握单的基本操作及简单应用。 实验内容：

1、 设计一个算法，将单链表中的N个元素倒置。

2、 设单链表中的数据递增有序，写算法，将元素X插入到单链表中适当位置，且保持该

表的有序性。

3、 用单链表实现两个集合的合并。

4、 将两个用单链表表示的有序表合并成一个有序表。 以下代码均在C--free5.0环境下编译。

首先第一个题目：设计一个算法，将单链表中的N个元素倒置 程序代码：

#include #include

typedef int ELEMTYPE; //定义一个结构体 struct node { ELEMTYPE element; struct node *next;

}; //创建一个头结点和一个尾节点 struct node *head; struct node *tail;

void init() //实现单链表的初始化 { head=(struct node *)malloc (sizeof (struct node )); // 算法复杂度为o(1) if(!head) exit(0); head->next= NULL; tail=head; }

void append(ELEMTYPE a) //将元素一个个的接在单链表后面 { struct node *p; // 算法复杂度为o(1) p=(struct node *)malloc(sizeof(struct node)); if(!p) exit(0); p->element=a; p->next=tail->next; tail->next=p; tail=p; }

void inverse()//实现单链表的逆置 { struct node *p,*r; // While语句影响算法执行时间 算法复杂度为o(n) p=head->next;

if(!p) exit(0); head->next=NULL; while(p) { r=p->next; p->next=head->next; head->next=p; p=r; } }

void traversal() //遍历单链表，将其元素输出 { struct node *p; // for语句影响算法执行时间 算法复杂度为o(n) printf(\ for(p=head->next;p!=NULL;p=p->next) printf(\ printf(\ }

int main() // traversal()函数调用语句影响算法执行时间 { struct node *p; // 算法复杂度为o(n) init(); append(1); append(2); append(3); append(4); append(5); append(6); append(7); append(8); append(9); append(10); traversal(); inverse(); traversal(); }

运行结果如下图：

第二个题目：设单链表中的数据递增有序，写算法，将元素X插入到单链表中适当位置，且保持该表的有序性。 程序代码：

#include #include

typedef int ELEMTYPE; //定义一个结构体 struct node { ELEMTYPE element; struct node *next;

}; //创建一个头结点和一个尾节点 struct node *head; struct node *tail;

void init() //实现单链表的初始化 { head=(struct node *)malloc (sizeof (struct node )); // 算法复杂度为o(1) if(!head) exit(0); head->next= NULL; tail=head; }

void append(ELEMTYPE a) //将元素一个个的接在单链表后面 { struct node *p; // 算法复杂度为o(1) p=(struct node *)malloc(sizeof(struct node)); if(!p) exit(0);

p->element=a; p->next=tail->next; tail->next=p; tail=p; }

int insert(ELEMTYPE a)//插入一个元素后其单链表仍有序 { struct node *q,*ltemp,*p;// While语句影响算法执行时间 算法复杂度为o(n) int j=1; ltemp=(struct node *)malloc(sizeof (struct node)); if(!ltemp) exit(0); ltemp->element=a; q=head->next; p=q->next; while((p->elementelement)&&(q->elementelement)) { p=q; q=q->next; } ltemp->next=p->next; p->next=ltemp; }

void traversal() //遍历单链表，将其元素输出 { struct node *p; // for语句影响算法执行时间 算法复杂度为o(n) printf(\ for(p=head->next;p!=NULL;p=p->next) printf(\ printf(\ }

int main() // insert()调用函数语句影响算法执行时间 算法复杂度为o(n) { struct node *p; init(); append(10); append(30); append(34); append(36); append(40); append(45); append(48);

append(50); append(55); append(60); traversal(); insert(37); insert(42); traversal(); }

其运行结果如下图：

第三个题目：用单链表实现两个集合的合并。 程序代码：

#include #include

typedef int ELEMTYPE; //定义一个结构体 struct node { ELEMTYPE element; struct node *next; };

struct node *head;

struct node *tail; //创建三个头结点和三个尾节点 struct node *head1; struct node *tail1; struct node *head2;

本文来源：https://www.bwwdw.com/article/gx4t.html