数据结构实践项目——链表

本组项目针对《数据结构基础系列(2):线性表》课程第8-15节
8. 线性表的链式存储
9. 建立单链表
10. 单链表基本操作的实现
11. 单链表应用举例
12. 双链表
13. 循环链表
14. 线性表的应用
15. 有序表

【项目1 - 建立单链表】
  定义单链表存储结构,用头插法和尾插法建立单链表,并显示建立好以后的结果。
  请在下面代码的基础上开展工作:

#include <stdio.h>
#include <malloc.h>
typedef int ElemType;
typedef struct LNode        //定义单链表结点类型
{
    ElemType data;
    struct LNode *next;     //指向后继结点
} LinkList;

void CreateListF(LinkList *&L,ElemType a[],int n);//头插法建立单链表
void CreateListR(LinkList *&L,ElemType a[],int n);//尾插法建立单链表
void DestroyList(LinkList *&L); //销毁单链表
void DispList(LinkList *L)  //输出单链表

int main()
{
    LinkList *L1, *L2;
    ElemType a[8]= {7, 9, 8, 2, 0, 4, 6, 3};
    CreateListF(L1, a, 8);
    printf("头插法建表结果:");
    DispList(L1);
    CreateListR(L2, a, 6);
    printf("尾插法建表结果:");
    DispList(L2);
    DestroyList(L1);
    DestroyList(L2);
    return 0;
}
//在下面写自定义函数(实现相关算法)的代码

参考解答

【项目2 - 建设“单链表”算法库】
  按照“0207将算法变程序”部分建议的方法,建设自己的专业基础设施算法库。这一周,建的是单链表的算法库。
  算法库包括两个文件:
  头文件:linklist.h,包含定义顺序表数据结构的代码、宏定义、要实现算法的函数的声明;
  源文件:linklist.cpp,包含实现各种算法的函数的定义
  
  请采用程序的多文件组织形式,建立如上的两个文件,另外再建立一个源文件(如main.cpp),编制main函数,完成相关的测试工作。
  测试工作可以采用“渐进”的思路,每次涉及的函数应该尽可能少。
  例如,首先设计测试函数,可以涉及初始化线性表、销毁线性表、输出线性表、插入数据元素对应的函数,设计的测试函数可以是

#include "linklist.h"
int main()
{
    LinkList *L;
    InitList(L);
    ListInsert(L, 1, 15);
    ListInsert(L, 1, 10);
    ListInsert(L, 1, 5);
    ListInsert(L, 1, 20);
    DispList(L);
    DestroyList(L);
    return 0;
}

参考解答

【项目3 - 单链表应用】
  完成下面的应用时,除项目中给出的特殊要求,其余工作均可利用项目2完成的算法支持。
  1、设计一个算法,将一个带头结点的数据域依次为a1,a2,…,an(n≥3)的单链表的所有结点逆置,即第一个结点的数据域变为an,…,最后一个结点的数据域为a1。实现这个算法,并完成测试。

提示:实现算法时,可以设计下面的函数:void Reverse(LinkList *&L)

  2、已知L1和L2分别指向两个单链表的头结点,且已知其长度分别为m、n,请设计算法将L2连接到L1的后面。实现这个算法,完成测试,并分析这个算法的复杂度。

提示:实现算法时,可以设计下面的函数:void Link(LinkList &L1, LinkList &L2)

  3、设计一个算法,判断单链表L是否是递增的。实现这个算法,并完成测试。

[参考解答]

【项目4 - 建设双链表算法库(选做)】
  算法库包括两个文件:
  头文件:dlinklist.h,包含定义顺序表数据结构的代码、宏定义、要实现算法的函数的声明;
  源文件:dlinklist.cpp,包含实现各种算法的函数的定义
  请采用程序的多文件组织形式,建立如上的两个文件,另外再建立一个源文件(如main.cpp),编制main函数,完成相关的测试工作。
参考解答

【项目5 - 猴子选大王】
  一群猴子,编号是1,2,3 …m,这群猴子(m个)按照1-m的顺序围坐一圈。从第1只开始数,每数到第n个,该猴子就要离开此圈,这样依次下来,直到圈中只剩下最后一只猴子,则该猴子为大王。输入m和n,输出为大王的猴子是几号。

提示:
(1)链表解法:可以用一个循环单链表来表示这一群猴子。表示结点的结构体中有两个成员:一个保存猴子的编号,一个为指向下一个人的指针,编号为m的结点再指向编号为1的结点,以此构成环形的链。当数到第n个时,该结点被删除,继续数,直到只有一个结点。
(2)使用结构数组来表示循环链:结构体中设一个成员表示对应的猴子是否已经被淘汰。从第一个人未被淘汰的数起,每数到n时,将结构中的标记改为0,表示这只猴子已被淘汰。当数到数组中第m个元素后,重新从第一个数起,这样循环计数直到有m-1被淘汰。
(3)该问题为计算机科学中的经典问题,很多实际的问题可以抽象到这种模型上来。感兴趣的同学请搜索“约瑟夫问题”。
参考解答

【项目5- 循环双链表应用】
  设非空线性表ha和hb都用带头节点的循环双链表表示。设计一个算法Insert(ha,hb,i)。其功能是:i=0时,将线性表hb插入到线性表ha的最前面;当i>0时,将线性表hb插入到线性表ha中第i个节点的后面;当i大于等于线性表ha的长度时,将线性表hb插入到线性表ha的最后面。
  请在实现算法时,除项目中给出的特殊要求,其余工作均可利用项目4完成的算法支持。
参考解答

【项目6 - 多项式求和】
  用单链表存储一元多项式,并实现两个多项式的加法。

提示:
1、存储多项式的数据结构
  多项式的通式是pn(x)=anxn+an1xn1+...+a1x+a0。n次多项式共有n+1项。直观地,可以定义一个数组来存储这n+1个系数。以多项式p(x)=3.4x109.6x8+7.2x2+x为例,存储这个多项式的数组如下图:
数据结构实践项目——链表
  可以看出,这种方案适合对某些多项式的处理。但是,在处理一些次数高但项数少的多项式时,存在浪费空间的现象,会有很多闲置的0。
  可以使用如下定义的单链表结构存储多项式:链表中的每一个结点是多项式中的一项,结点的数据域包括指数和系数两部分,由指针域连接起多项式中的各项。

typedef struct pnode //定义单链表结点类型,保存多项式中的一项,链表构成多项式 {
double coef; //系数,浮点数
int exp; //指数,正整数*
struct pnode *next; //指向下一项的指针
} PolyNode;

  用于表示多项式的链表将如下图所示,在建立多项式的链表时,已经令结点按指数由大到小的顺序排列。
数据结构实践项目——链表

2、多项式加法在链表存储结构下的实现
  链表存储结构下,多项式加法的实现 在如上定义的单链表存储结构基础上,讨论实现多项式加法的算法。
  两个多项式相加,其规则是对具有相同指数的项,令其系数相加。设两个待相加的多项式的链表的头指针分别为head1(第一个多项式)和head2(第二个多项式),两者的和保存到链表head1中。只需要先将head1和head2链表的首结点作为当前结点(分别用p1和p2指向)开始检测,在遍历链表的过程中,分情况作如下处理:
  (1)若两个多项式中当前结点的指数值相同,则它们的系数相加,结果保存到p1结点,并将p2结点删除。如果相加后的系数不为0,p1指向第一个多项式的下一个结点,准备随后的工作,否则,不保存系数为0的项,将当前p1结点删除。
  (2)当两个多项式中对应结点的指数值不相等时,若p1指向的结点的指数大,则p1简单地指向下一结点即可;而p2指向的结点大时,需要将p2结点插入到p1前,然后p2再重新指回到第二个多项式中的下一结点,继续进行处理。
  (3)检测过程直到其中的任一个链表结束。若p1不为空,第一个多项式中的剩余项已经在链表中,不作处理,如果p2不为空,只需要将p2链接到相加后的第一个多项式末尾。
  上面的讨论假设多项式链表中,已经按指数由大到小排序,在加法之前,采取多种手段保证这一前提成立。

参考解答

上一篇:Python 最强编辑器详细使用指南!(三)


下一篇:满江红开放技术研究组织发布Seam 2.0中文文档正式版