数据结构（链表的操作算法）

1.实验要求

编写一个程序linklist.cpp,实现单链表的各种基本运算和整体建表算法(假设单链表的元素类型 ElemType为char)，设计一个程序exp2_1.cpp，完成如下功能:

(1)初始化单链表h。

(2)依次采用尾插法插入a、b、c、d、e元素。

(3)输出单链表h。

(4)输出单链表h长度。

(5)判断单链表h是否为空。

(6)输出单链表h的第3个元素。

(7)输出元素a的位置。

(8)在第4个元素位置上插人1元素。

(9)输出单链表h。

(10)删除单链表h的第3个元素。

(11)输出单链表h。

(12)释放单链表h。

2.代码及解释

#include <stdio.h>
#include <malloc.h>
typedef char ElemType;    //定义一种新类型名ElemType，该类型同char效果一样 
typedef struct LNode
{
ElemType data;
struct LNode *next;   //指向后继结点
}LinkNode;    //单链表结点类型
void CreateListF(LinkNode *&L,ElemType a[],int n)   //头插法建立单链表
{
LinkNode *s;    //让指针S指向头结点 
L=(LinkNode *)malloc(sizeof(LinkNode));     //创建头结点
L->next=NULL;    //先将头结点后面一位节点附上空值 
for (int i=0;i<n;i++)
{
s=(LinkNode *)malloc(sizeof(LinkNode));    //创建新结点 s
s->data=a[i];    //向后遍历将，将数据传入指针 
s->next=L->next;     //将结点 s 插在原开始结点之前,头结点之后
L->next=s;    //让指针值赋给链表的下一个元素 
}
}
void CreateListR(LinkNode *&L,ElemType a[],int n)    //尾插法建立单链表
{
LinkNode *s,*r;    //创建两个指针指向链表 
L=(LinkNode *)malloc(sizeof(LinkNode));     //创建头结点
L->next=NULL;    //先将头结点后面一位节点附上空值 
r=L;     //r 始终指向尾结点,开始时指向头结点
for (int i=0;i<n;i++)
{
s=(LinkNode *)malloc(sizeof(LinkNode));    //创建新结点 s
s->data=a[i];    //将列表值赋给指针s 
r->next=s;     //将结点 s 插入 r 结点之后
r=s;    //r指针指向s指针 
}
r->next=NULL;     //尾结点 next 域置为 NULL
}
void InitList(LinkNode *&L)     //初始化线性表
{
L=(LinkNode *)malloc(sizeof(LinkNode));     //创建头结点
L->next=NULL;     //单链表置为空表
}
void DestroyList(LinkNode *&L)     //销毁线性表
{
LinkNode *pre=L,*p=pre->next;    //pre指向L,p指向pre的下一个值 
while (p!=NULL)    //p不为空 
{ 
free(pre);    //释放pre 
pre=p;      //pre、p 同步后移一个结点
p=pre->next;
}
free(pre);     //此时 p 为 NULL,pre 指向尾结点,释放它
}
bool ListEmpty(LinkNode *L)     //判线性表是否为空表
{
return(L->next==NULL);
}
int ListLength(LinkNode *L)     //求线性表的长度
{ 
int i=0;
LinkNode *p=L;     //p 指向头结点,n 置为 0(即头结点的序号为 0)
while (p->next!=NULL)    //p指针的下个节点不为空，向后移一位，长度加1 
{ 
i++;
p=p->next;
}
return(i);     //循环结束,p 指向尾结点,其序号 i 为结点个数
}
void DispList(LinkNode *L)     //输出线性表
{ 
LinkNode *p=L->next;     //p 指向首结点
while (p!=NULL)     //p 不为 NULL,输出 p 结点的 data 域
{ 
printf("%c ",p->data);
p=p->next;     //p 移向下一个结点
}
printf("\n");
}
bool GetElem(LinkNode *L,int i,ElemType &e)     //求线性表中第 i 个元素值
{ 
int j=0;
if (i<=0) return false;     //i<=0 错误返回假
LinkNode *p=L;     //p 指向头结点,j 置为 0(即头结点的序号为 0)
while (j<i && p!=NULL)     //找第 i 个结点 p
{ 
j++;
p=p->next;
}
if (p==NULL)     //不存在第 i 个数据结点,返回 false
return false;
else     //存在第 i 个数据结点,返回 true
{ 
e=p->data;
return true;
}
}
int LocateElem(LinkNode *L,ElemType e)     //查找第一个值域为 e 的元素序号
{ 
int i=1;
LinkNode *p=L->next;     //p 指向首结点,i 置为 1(即首结点的序号为 1)
while (p!=NULL && p->data!=e)     //查找 data 值为 e 的结点,其序号为 i
{ 
p=p->next;
i++;
}
if (p==NULL)     //不存在值为 e 的结点,返回 0
return(0);
else      //存在值为 e 的结点,返回其逻辑序号 i
return(i);
}
bool ListInsert(LinkNode *&L,int i,ElemType e)     //插入第 i 个元素
{ 
int j=0;
if (i<=0) return false;     //i 错误返回假
LinkNode *p=L,*s;     //p 指向头结点,j 置为 0(即头结点的序号为 0)
while (j<i-1 && p!=NULL)     //查找第 i-1 个结点 p
{
j++;
p=p->next;
}
if (p==NULL)     //未找到第 i-1 个结点,返回 false
return false;
else     //找到第 i-1 个结点 p,插入新结点并返回 true
{ 
s=(LinkNode *)malloc(sizeof(LinkNode));
s->data=e;     //创建新结点 s,其 data 域置为 e
s->next=p->next;     //将结点 s 插入到结点 p 之后
p->next=s;
return true;
}
}
bool ListDelete(LinkNode *&L,int i,ElemType &e)     //删除第 i 个元素
{ 
int j=0;
if (i<=0) return false;     //i 错误返回假
LinkNode *p=L,*q;     //p 指向头结点,j 置为 0(即头结点的序号为 0)
while (j<i-1 && p!=NULL)     //查找第 i-1 个结点
{ 
j++;
p=p->next;
}
if (p==NULL)     //未找到第 i-1 个结点,返回 false
return false;
else     //找到第 i-1 个结点 p
{ 
q=p->next;     //q 指向第 i 个结点
if (q==NULL)     //若不存在第 i 个结点,返回 false
return false;
e=q->data;
p->next=q->next;     //从单链表中删除 q 结点
free(q);     //释放 q 结点
return true;     //返回 true 表示成功删除第 i 个结点
}
}
int main()
{
LinkNode *La;
ElemType a[]={'a','b','c','d','e'},elem,ch;
InitList(La);
printf("(1)输出初始化后的链表 La:\n ");
DispList(La);
printf("(2)依次采用尾插法插入 a、b、c、d、e 元素。 \n");
CreateListR(La,a,5);
printf("(3)输出单链表 La: ");
DispList(La);
printf("(4)输出单链表 La 长度:%d\n ",ListLength(La));
printf("(5)判断单链表 La 是否为空: ");
printf((ListEmpty(La))?"非空":"空");
printf("\n");
printf("(6)输出单链表 h 的第 3 个元素:");
GetElem(La,3,elem);
printf("%c\n",elem);
printf("(7)输出元素 a 的位置为: %d\n",LocateElem(La,'a'));
printf("(8)在第 4 个元素位置上插入一个字符,请输入：");
scanf("%c",&ch);
ListInsert(La,4,ch);
printf("(9)输出插入元素后的单链表 La：");
DispList(La);
printf("(10)删除单链表 La 的第 3 个元素。\n");
ListDelete(La,3,ch);
printf("(11)输出删除第 3 个元素后的单链表 La：");
DispList(La);
}

1.实验要求

编写一个程序exp2_2.cpp,采用单链表表示集合(假设同一个集合中不存在重复素)，将其按递增方式排序，构成有序单链表，并求这样的两个集合的并、交和差。 

2.代码及解释

#include "linklist.cpp"    //引用linklist.cpp时，需要将linklist.cpp中的main函数注释 
void sort(LinkNode *&L) //单链表元素递增排序
{
LinkNode *p,*pre,*q;
p=L->next->next; //p 指向 L 的第 2 个数据结点
L->next->next=NULL; //构造只含一个数据结点的有序表
while (p!=NULL)
{ 
q=p->next; //q 保存 p 结点的后继结点
pre=L; //从有序表开头进行比较,pre 指向插入结点 p 的前驱结点
while (pre->next!=NULL && pre->next->data<p->data)
pre=pre->next; //在有序表中找 pre 结点
p->next=pre->next;//将结点 pre 之后插入 p 结点
pre->next=p;
p=q; //扫描原单链表余下的结点
}
}
void Union(LinkNode *ha,LinkNode *hb,LinkNode *&hc) //求两有序集合的并
{
LinkNode *pa=ha->next,*pb=hb->next,*s,*tc;
hc=(LinkNode *)malloc(sizeof(LinkNode)); //创建头结点
tc=hc;
while (pa!=NULL && pb!=NULL)
{
if (pa->data<pb->data)
{
s=(LinkNode *)malloc(sizeof(LinkNode)); //复制结点
s->data=pa->data;
tc->next=s;tc=s;
pa=pa->next;
}
else if (pa->data>pb->data)
{
s=(LinkNode *)malloc(sizeof(LinkNode)); //复制结点
s->data=pb->data;
tc->next=s;tc=s;
pb=pb->next;
}
else
{
s=(LinkNode *)malloc(sizeof(LinkNode)); //复制结点
s->data=pa->data;
tc->next=s;tc=s;
pa=pa->next; //重复的元素只复制一个
pb=pb->next;
}
}
if (pb!=NULL) pa=pb; //复制余下的结点
while (pa!=NULL)
{
s=(LinkNode *)malloc(sizeof(LinkNode)); //复制结点
s->data=pa->data;
tc->next=s;tc=s;
pa=pa->next;
}
tc->next=NULL;
}
void InterSect(LinkNode *ha,LinkNode *hb,LinkNode *&hc) //求两有序集合的交
{
 LinkNode *pa=ha->next,*pb,*s,*tc;
 hc=(LinkNode *)malloc(sizeof(LinkNode));
 tc=hc;
 while (pa!=NULL)
 {
 pb=hb->next;
 while (pb!=NULL && pb->data<pa->data) 
 pb=pb->next; 
 if (pb!=NULL && pb->data==pa->data) //若 pa 结点值在 B 中
 {
 s=(LinkNode *)malloc(sizeof(LinkNode)); //复制结点
 s->data=pa->data;
 tc->next=s;tc=s;
 }
 pa=pa->next;
 }
 tc->next=NULL;
}
void Subs(LinkNode *ha,LinkNode *hb,LinkNode *&hc) //求两有序集合的差
{
 LinkNode *pa=ha->next,*pb,*s,*tc;
 hc=(LinkNode *)malloc(sizeof(LinkNode));
 tc=hc;
 while (pa!=NULL)
 {
 pb=hb->next;
 while (pb!=NULL && pb->data<pa->data) 
 pb=pb->next; 
 if (!(pb!=NULL && pb->data==pa->data)) //若 pa 结点值不在 B 中
 {
 s=(LinkNode *)malloc(sizeof(LinkNode)); //复制结点
 s->data=pa->data;
 tc->next=s;tc=s;
 }
 pa=pa->next;
 }
 tc->next=NULL;
}
int main()
{
LinkNode *ha,*hb,*hc;
ElemType a[]={'c','a','e','h'};
ElemType b[]={'f','h','b','g','d','a'};
printf("集合的运算如下:\n");
CreateListR(ha,a,4);
CreateListR(hb,b,6);
printf(" 原 集 合 A: ");DispList(ha);
printf(" 原 集 合 B: ");DispList(hb);
sort(ha);
sort(hb);
printf(" 有序集合 A: ");DispList(ha);
printf(" 有序集合 B: ");DispList(hb);
Union(ha,hb,hc);
printf(" 集合的并 C: ");DispList(hc);
InterSect(ha,hb,hc);
printf(" 集合的交 C: ");DispList(hc);
Subs(ha,hb,hc);
printf(" 集合的差 C: ");DispList(hc);
DestroyList(ha);
DestroyList(hb);
DestroyList(hc);
return 1;
}

原文地址：https://blog.csdn.net/m0_61903191/article/details/142645251

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！