实验一 单向链表

来源：百度知道 编辑：UC知道 时间：2024/05/25 22:07:09
一、实验目的
1、帮助读者复习C语言程序设计中的知识。
2、熟悉线性表的基本运算在链式存储结构上的实现。
二、实验前的准备工作
1、掌握线性表的逻辑结构。
2、掌握线性表的链式存储结构。
3、熟练掌握线性表的插入、删除等操作。
三、实验指导
1、算法分析
①为使算法的时间复杂度为O(n+m)只能采用“平移指针，一次扫描”的方法，于是设两个指针分别指向两个线性表表头。
②为使合并后仍为一个有序表，需对指针所指结点的数据域进行比较。
③要使合并后的有序表为递减有序表，比较后选出较小的一个将其从原链表中取出插入到新表的表首。
④指针后移，重复②，③步，直到其中一个表结束，将尚未结束表的元素依次取出插入新表。
⑤为减少头指针的变化，采用带有头结点的链表。
2、算法如下
struct node
{int data;
struct node *link;
}
typedef struct node NODE;
NODE *merge_link(NODE *head_a,NODE *head_b)
{NODE *p,*q,*head;
head=(NODE*)malloc(sizeof(NODE));
head->link=NULL;
p=head_a->link;
q=head_b->link;
while((p!=NULL)&&(q!=NULL))
if(p->data<q->data)
{head_a->link=p->link;
p->link=head->link;
head->link=p;
p=head_a->link;
}
else
{head_b->link=q->link;
q->link=head->link;
head->link=q;q=head_b->link;
}
whi

下面大体介绍一下基本思想：
由于是递增的单链表：0->0->0->0 这种结构不能逆向反问；所以直接做操作是很不好实现的；
所以我第一步是将两链表的指针反转，这样就使原来两链表由递增序列变成了递减序列；第二步在根据
合并排序的思想，将两个链合并； 思路比较简单，你一看因该能明白，我用C++实现了一下想法，代码如下：
#include <iostream>

using namespace std;

const int N = 8;

struct Node
{
int data;
Node* next;
Node(int d = 0, Node* n = 0):data(d), next(n){}
};

void Print(Node* p)
{
do
{
cout << p->data << " ";
p = p->next ;
}while(p);
cout << endl;
}

void Create(Node*& List)
{
int i;
Node* tail = 0;

for(i = 0; i < N; i++)
{
Node* q = new Node;
q->data = (rand()%100);

if(tail == 0) tail = q, List = q;
else
{
tail->next = q;
tail = tail->next;
}
}
}

void Sort(Node*& List)
{
for(Node* p = List; p != 0; p = p->next)
{
for(Node*