實(shí)驗(yàn)內(nèi)容：
1．隨機(jī)產(chǎn)生或鍵盤輸入一組元素（不少于10個(gè)元素），建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表。
2．把單鏈表中的元素逆置（不允許申請(qǐng)新的結(jié)點(diǎn)空間）。
3．刪除單鏈表中所有的偶數(shù)元素結(jié)點(diǎn)。
4．編寫在非遞減有序鏈表中插入一個(gè)元素使鏈表元素仍有序的函數(shù)，利用該函數(shù)建立一個(gè)
非遞減有序單鏈表。
5．利用算法4建立兩個(gè)非遞減有序單鏈表，然后合并成一個(gè)非遞增鏈表。
6．把算法1建立的鏈表分解成兩個(gè)鏈表，其中一個(gè)全部為奇數(shù)，另一個(gè)全部為偶數(shù)（盡量
利用已有存儲(chǔ)空間）。
7．在主函數(shù)中設(shè)計(jì)一個(gè)簡(jiǎn)單菜單，調(diào)用上述算法。
實(shí)驗(yàn)說(shuō)明 :
1．結(jié)點(diǎn)類型定義
typedef int ElemType； // 元素類型
typedef struct LNode
{
ElemType data ;
struct LNode * next ;
} LNode, *pLinkList ;
2．為了簡(jiǎn)單，采用帶頭結(jié)點(diǎn)的單鏈表。
源代碼:
#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() //單鏈表創(chuàng)建
{
int n;
LNode *phead, *temp, *p;
phead = new LNode;
if (phead == NULL)
{
cout << "鏈表創(chuàng)建失?。? << endl;
exit(0);
}
cout << "輸入需要隨機(jī)產(chǎn)生的元素的個(gè)數(shù)(不少于10個(gè))：";
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為第一個(gè)結(jié)點(diǎn)，p2為第二個(gè)結(jié)點(diǎn)，p1為第三個(gè)結(jié)點(diǎn)
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) //刪除單鏈表中所有的偶數(shù)元素結(jié)點(diǎn)
{
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) //插入一個(gè)元素
{
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) //鏈表分解成奇數(shù)和偶數(shù)兩個(gè)鏈表
{
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:隨機(jī)產(chǎn)生或鍵盤輸入一組元素（不少于10個(gè)元素）,建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表" << endl;
cout << "2:單鏈表中的元素逆置" << endl;
cout << "3:單鏈表排序輸出" << endl;
cout << "4:刪除單鏈表中所有的偶數(shù)元素結(jié)點(diǎn)" << endl;
cout << "5:插入一個(gè)元素，用該函數(shù)建立一個(gè)非遞減有序單鏈表（插入）" << endl;
cout << "6:建立兩個(gè)非遞減有序單鏈表，然后合并成一個(gè)非遞增鏈表（合并）" << endl;
cout << "7:鏈表分解成兩個(gè)鏈表，其中一個(gè)全部為奇數(shù)，另一個(gè)全部為偶數(shù)" << endl;
cout << "8:退出" << endl;
cout << endl;
while (true)
{
cout << "請(qǐng)輸入一個(gè)數(shù)字選項(xiàng)：";
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 << "輸入錯(cuò)誤！請(qǐng)重新輸入！" << endl;
cout << endl;
}
}
return 0;
}
運(yùn)行截圖：
image
