实验内容：
1．随机产生或键盘输入一组元素（不少于10个元素），建立一个带头结点的单链表。
2．把单链表中的元素逆置（不允许申请新的结点空间）。
3．删除单链表中所有的偶数元素结点。
4．编写在非递减有序链表中插入一个元素使链表元素仍有序的函数，利用该函数建立一个
非递减有序单链表。
5．利用算法4建立两个非递减有序单链表，然后合并成一个非递增链表。
6．把算法1建立的链表分解成两个链表，其中一个全部为奇数，另一个全部为偶数（尽量
利用已有存储空间）。
7．在主函数中设计一个简单菜单，调用上述算法。
实验说明 :
1．结点类型定义
typedef int ElemType； // 元素类型
typedef struct LNode
{
ElemType data ;
struct LNode * next ;
} LNode, *pLinkList ;
2．为了简单，采用带头结点的单链表。
源代码:
#include <iostream>
#include <time.h>
#include <iomanip>
#include <stdlib.h>
using namespace std;
typedef int ElemType;
typedef struct LNode
{
ElemType data;
struct LNode* next;
}LNode, *pLinkList;
pLinkList LinkList_Init() //单链表创建
{
int n;
LNode *phead, *temp, *p;
phead = new LNode;
if (phead == NULL)
{
cout << "链表创建失败！" << endl;
exit(0);
}
cout << "输入需要随机产生的元素的个数(不少于10个)：";
cin >> n;
temp = phead;
srand(unsigned(time(NULL)));
for (int i = 0; i < n; i++)
{
p = new LNode;
p->data = rand() % 100;
temp->next = p;
temp = p;
}
temp->next = NULL;
return phead;
}
void LinkList_Display(pLinkList phead) //输出链表
{
phead = phead->next;
while (phead)
{
cout << setw(4) << phead->data;
phead = phead->next;
}
cout << endl;
}
void LinkList_Free(pLinkList phead) //链表释放
{
LNode *p;
while (phead)
{
p = phead;
phead = phead->next;
delete p;
}
}
void LinkList_Convert(pLinkList phead) //单链表中的元素逆置
{
LNode *p1, *p2, *p3; //p3为第一个结点，p2为第二个结点，p1为第三个结点
if (phead->next == NULL)
{
cout << "链表为空！" << endl;
return;
}
p3 = phead->next;
p2 = p3->next;
if (p2 == NULL)
{
return;
}
p1 = p2->next;
p3->next = NULL;
while (p1)
{
p2->next = p3;
p3 = p2;
p2 = p1;
p1 = p1->next;
}
p2->next = p3;
phead->next = p2;
}
void LinkLIst_Del_oushu(pLinkList phead) //删除单链表中所有的偶数元素结点
{
LNode *p1, *p2;
p2 = phead;
phead = phead->next;
while (phead)
{
if (phead->data % 2 == 0)
{
p1 = phead;
phead = phead->next;
delete p1;
p2->next = phead;
continue;
}
p2 = phead;
phead = phead->next;
}
}
void LinkList_Sort(pLinkList phead) //排序
{
ElemType *num, temp;
LNode *p;
int count = 0, i = 0;
if (phead->next == NULL)
{
cout << "链表为空！" << endl;
return;
}
p = phead->next;
while (p)
{
count++;
p = p->next;
}
num = new ElemType[count];
p = phead->next;
while (p)
{
num[i++] = p->data;
p = p->next;
}
for (int j = 0; j < count - 1; j++)
for (int k = 0; k < count - j - 1; k++)
if (num[k] > num[k + 1])
{
temp = num[k];
num[k] = num[k + 1];
num[k + 1] = temp;
}
p = phead->next;
i = 0;
while (p)
{
p->data = num[i++];
p = p->next;
}
delete[] num;
}
void LinkList_Insert(pLinkList phead, ElemType elem) //插入一个元素
{
LNode *p1, *p2, *tmp = NULL;
p1 = phead->next;
p2 = phead;
while (p1)
{
if (elem < p1->data)
break;
p2 = p1;
p1 = p1->next;
}
tmp = new LNode;
tmp->data = elem;
p2->next = tmp;
tmp->next = p1;
}
void LinkList_Divide(pLinkList L1, pLinkList L2) //链表分解成奇数和偶数两个链表
{
LNode *p1, *p2;
p2 = L1;
p1 = L1->next;
while (p1)
{
if ((p1->data) % 2 == 0)
{
L2->next = p1;
L2 = p1;
p1 = p1->next;
p2->next = p1;
}
else
{
p2 = p1; p1 = p1->next;
}
}
L2->next = NULL;
}
void LinkList_Cat(pLinkList L1, pLinkList L2) //链表合并,
{
pLinkList p1, p2;
p2 = L1;
p1 = L1->next;
while (p1)
{
p2 = p1; p1 = p1->next;
}
p2->next = L2->next;
LinkList_Sort(L1);
LinkList_Convert(L1);
}
int main()
{
LNode *L = NULL, *L1 = NULL, *L2 = NULL;
int num;
cout << "1:随机产生或键盘输入一组元素（不少于10个元素）,建立一个带头结点的单链表" << endl;
cout << "2:单链表中的元素逆置" << endl;
cout << "3:单链表排序输出" << endl;
cout << "4:删除单链表中所有的偶数元素结点" << endl;
cout << "5:插入一个元素，用该函数建立一个非递减有序单链表（插入）" << endl;
cout << "6:建立两个非递减有序单链表，然后合并成一个非递增链表（合并）" << endl;
cout << "7:链表分解成两个链表，其中一个全部为奇数，另一个全部为偶数" << endl;
cout << "8:退出" << endl;
cout << endl;
while (true)
{
cout << "请输入一个数字选项：";
cin >> num;
switch (num)
{
case 1:
{ L = LinkList_Init();
cout << "L链表为：";
LinkList_Display(L);
cout << endl;
}break;
case 2:
{ LinkList_Convert(L);
cout << "链表为：";
LinkList_Display(L);
cout << endl;
}break;
case 3:
{ LinkList_Sort(L);
cout << "链表为：";
LinkList_Display(L);
cout << endl;
}break;
case 4:
{ LinkLIst_Del_oushu(L);
cout << "链表为：";
LinkList_Display(L);
cout << endl;
}break;
case 5:
{ ElemType elem;
cout << "输入要插入的元素：";
cin >> elem;
LinkList_Sort(L);
LinkList_Insert(L, elem);
cout << "链表为：";
LinkList_Display(L);
cout << endl;
}break;
case 6:
{
L1 = LinkList_Init();
cout << "L1链表为：";
LinkList_Display(L1);
L2 = LinkList_Init();
cout << "L2链表为：";
LinkList_Display(L2);
LinkList_Cat(L1, L2);
cout << "合并的链表为：";
LinkList_Display(L1);
cout << endl;
}break;
case 7:
{
L2 = new LNode;
LinkList_Divide(L1, L2);
cout << "L1链表为：";
LinkList_Display(L1);
cout << "L2链表为：";
LinkList_Display(L2);
LinkList_Free(L2);
cout << endl;
}break;
case 8:
{
LinkList_Free(L);
delete L1;
cout << endl;
cout << "链表已释放并删除"<<endl;
cout << endl;
}break;
default:
cout << "输入错误！请重新输入！" << endl;
cout << endl;
}
}
return 0;
}
运行截图：
image
网友评论