数据结构实验1.2：单向链表

实验内容：

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