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

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));    //创建新结点 ss->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));    //创建新结点 ss->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 个数据结点,返回 falsereturn 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 的结点,返回 0return(0);else      //存在值为 e 的结点,返回其逻辑序号 ireturn(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 个结点,返回 falsereturn false;else     //找到第 i-1 个结点 p,插入新结点并返回 true{ s=(LinkNode *)malloc(sizeof(LinkNode));s->data=e;     //创建新结点 s,其 data 域置为 es->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 个结点,返回 falsereturn false;else     //找到第 i-1 个结点 p{ q=p->next;     //q 指向第 i 个结点if (q==NULL)     //若不存在第 i 个结点,返回 falsereturn 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;
}