第1页 / 共10页
第2页 / 共10页
第3页 / 共10页
第4页 / 共10页
第5页 / 共10页
第6页 / 共10页
第7页 / 共10页
第8页 / 共10页
数据结构实验二（单链表基本操作）题目和源程序.doc
实验 2：单链表基本操作
一、 实验目的
1. 学会定义单链表的结点类型，实现对单链表的一些基本操作和具体
的函数定义，了解并掌握单链表的类定义以及成员函数的定义与调用。
2. 掌握单链表基本操作及两个有序表归并、单链表逆置等操作的实现。
二 、实验要求
1．预习 C 语言中结构体的定义与基本操作方法。
2．对单链表的每个基本操作用单独的函数实现。
3．编写完整程序完成下面的实验内容并上机运行。
4．整理并上交实验报告。
三、实验内容
1．编写程序完成单链表的下列基本操作：
(1)初始化单链表 La。
(2)在 La 中第 i 个元素之前插入一个新结点。
(3)删除 La 中的第 i 个元素结点。
(4)在 La 中查找某结点并返回其位置。
(5)打印输出 La 中的结点元素值。
2 .构造两个带有表头结点的有序单链表 La、Lb，编写程序实现将 La、
Lb 合并成一个有序单链表 Lc。
合并思想是：程序需要 3 个指针：pa、pb、pc，其中 pa，pb 分别指
向 La 表与 Lb 表中当前待比较插入的结点，pc 指向 Lc 表中当前最后一个结
点。依次扫描 La 和 Lb 中的元素，比较当前元素的值，将较小者链接到*pc
之后，如此重复直到 La 或 Lb 结束为止，再将另一个链表余下的内容链接到
pc 所指的结点之后。
3．构造一个单链表 L，其头结点指针为 head，编写程序实现将 L 逆置。
（即最后一个结点变成第一个结点，原来倒数第二个结点变成第二个结点，
如此等等。）
四、思考与提高
1．如果上面实验内容 2 中合并的表内不允许有重复的数据该如何操作？
2．如何将一个带头结点的单链表 La 分解成两个同样结构的单链表 Lb，
Lc，使得 Lb 中只含 La 表中奇数结点，Lc 中含有 La 表的偶数结点？
02_单链表.cpp -- 单链表基本操作
/*----------------------------------------
*
* 对单链表的每个基本操作都用单独的函数来实现
* 水上飘 2009 年写
----------------------------------------*/
// ds02.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include
#include
#include
using namespace std;
typedef int ElemType;
typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode, *LinkList;
//确保输入的数据正确
int Oncemore()
{
int n ;
cout << "输入错误，请重新输入：" ;
cin >> n ;
cout << endl ;
if( n <= 2 )
n = Oncemore( ) ;
return n ;
}
//初始化单链表 L
void InitList(LinkList &L)
{
L = (LinkList)malloc(sizeof(LNode));
L->next = NULL;
}
//逆位序创建一个带头结点的单链线性表
LinkList CreateList( LinkList &L, int n )
{
LinkList p ;
for( int i = 0; i < n; i++ )
{
p = (LinkList)malloc(sizeof(LNode)) ;
p->data = (int)(rand()%100) ;
//给新生成的结点随机赋一个
p->next = L->next ; L->next = p ;
//插入到表头
}
return L;
值
}
//在 L 中第 i 个元素之前插入一个新结点
void Insert(LinkList &L, int i)
{
LNode *p;
LNode *p1;
int m;
p1 = L->next ;
p = (LinkList)malloc(sizeof(LNode)) ;
p->data = (int)(rand()%100) ;
//给新生成的结点随机赋一个
值
}
for(m = 2; m < i; m++)
p1 = p1->next ;
if(m == i)
{
p->next = p1->next ;
p1->next = p;
cout << "在 L 中第 i 个元素之前插入一个新结点成功.";
}
else cout << "在 L 中第 i 个元素之前插入一个新结点失败.";
//删除 La 中的第 i 个元素结点
void Delete(LinkList &L, int j)
{
LNode *p;
LNode *p1;
int m;
p1 = L->next ;
for(m = 1; m < j; m++)
{
p1 = p1->next ;
if(m == (j-2))
p = p1;
//p 指向欲删除结点的
//p 结点指向欲删除结点的
前一个结点
}
if(m == j)
{
p->next = p1->next ;
下一个结点
delete p1;
cout << "删除 L 中的第 j 个元素结点成功．";
}
else cout << "删除 La 中的第 j 个元素结点失败．";
}
//在 L 中查找某结点并返回其值
int Lookup(LinkList &L, int k)
{
LNode *p;
p = L->next ;
int i;
for(i = 1; i < k; i++)
p = p->next ;
if(i == k)
{
cout << "在 L 中查找第ｉ个结点并返回其值成功.";
return p->data ;
cout << "在 L 中查找ｉ个结点并返回其值失败.";
return 0;
}
else
{
}
}
/*LinkList mix(LinkList &L)
{
LinkList p1,p2,p3;
p1 = L->next ;
p2 = L->next ;
p3 = L->next ;
while(p1->next != NULL)
{
if(p1->data > p1->next->data)
p2 = p1->next ;
p1 = p1->next ;
}
if(p3->next = NULL)
{
L->next = NULL;
return p1;
}
else
{
p3 = L->next ;
while(p3->next != p2 && !p3->next)
p3 = p3->next ;
p3->next = p2->next ;
p2->next = NULL ;
return p2;
}
}
void Union(LinkList &La,LinkList &Lb,LinkList &Lc)
{
LinkList pa,pb,pc;
pc = Lc;
while(La->next != NULL && Lb->next != NULL)
{
pa = mix(La);
pb = mix(Lb);
if(pa->data < pb->data)
{
pc->next = pa ;
pc = pa;
}
else
{
}
pc->next = pb ;
pc = pb;
}
if(La->next != NULL)
pc->next = La->next ;
if(Lb->next != NULL)
pc->next = Lb->next ;
}*/
//使线性表按值非递减排列
void Notdegression( LinkList &L, int n )
{
int m ;
LinkList pa;
while(n)
{
pa = L->next ;
while( pa->next )
{
if( pa->data > pa->next->data )
{
m = pa->data ;
pa->data = pa->next->data ;
pa->next->data = m ;
pa = pa->next ;
}
else
{
}
}
n-- ;
pa = pa->next ;
continue ;
}
}
//归并 La 和 Lb，得到元素也按非递减排列的 Lc
void Merger( LinkList &La, LinkList &Lb, LinkList &Lc )
{
Lc = (LinkList)malloc(sizeof(LNode));
LinkList pa, pb, pc ;
pa = La->next ;
pb = Lb->next ;
Lc->next = NULL ;
pc = Lc ;
while(pa && pb)
个结点
{
if(pa->data < pb->data)
{
pc->next = pa ;
pc = pa ;
pa = pa->next;
}
else
{
//当 pa 不为最后一个结点
//交换两个结点的值
//移向下一个结点
//移向下一个结点
//初始化
//当 pa 或 pb 没有到最后一
//pa 结点插入到 Lc 表的末端
//pb 结点插入到 Lc 表的末
端
pc->next = pb ;
pc = pb;
pb = pb->next ;
}
}
pc->next = pa ? pa : pb ;
Lc 的末端*/
delete La;
delete Lb;
}
/*判断 La 表和 Lb 表是否已插入完，
若没有，则剩下的插入到
//释放头结点
//将 L 逆置（即最后一个结点变成第一个结点，原来倒数第二个结点变成第二个结点，如此
等等。）
void CutBack(LinkList &L)
{
LinkList p1,p2,p3;
p1 = L->next ;
p3 = L ;
while(p1->next)
指向倒数第二个结点
{
p1 = p1->next ;
p3 = p3->next ;
}
p2 = p1;
while(p3 != L)
{
p2->next = p3;
p3->next = NULL ;
p2 = L->next ;
p3 = L ;
while(p2->next)
结点，p3 指向倒数第二个结点
{
}
p2 = p2->next ;
p3 = p3->next ;
}
p2->next = NULL ;
p3->next = p1 ;
表的第一个结点
}
//p1 指向最后一个结点，p3
//p2 指向最后一个结点
//实现倒置
//指向第一个结点
//指向头结点
//p2 指向新表的最后一个
//让新表最后一个结点指向空
//让 p3 即 L 头结点指向新
//L1 指向第一个结点
//输出最后一个结点的值
//输出单链表 L
void OutputList( LinkList &L )
{
cout << endl;
LNode *L1 ;
int i = 0 ;
L1 = L->next ;
while(L1->next != NULL)
{
cout << setw(5) << L1->data ;
L1 = L1->next ;
i++ ;
if( i % 5 == 0)
cout << endl ;
}
cout << setw(5) << L1->data ;
cout << endl << endl ;
}
//第一题
void FirstTitle()
{
cout << "第一题开始：" << endl;
LinkList L;
int n;
cout << "输入表的元素个数:";
cin >> n;
if(n <= 2)
n = Oncemore();
InitList(L);
CreateList(L,n);
OutputList(L);
int i,j;
cout << "输入插入的位置:";
cin >> i;
Insert(L,i);
OutputList(L);
cout << "输入删除的位置:";
cin >> j;
Delete(L,j);
OutputList(L);
int k,m;
cout << "输入要查找的结点的序号：";
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
