精华内容
下载资源
问答
  • 单链表的基本操作

    2017-02-04 13:09:46
    单链表的基本操作

    代码示例

    /*
        function:单链表的基本操作
        created by : xilong
        date: 2017.2.3
    */
    #include "iostream"
    #include <stdlib.h>
    using namespace std;
    
    #define OK 1
    #define ERROR 0
    #define TRUE 1
    #define FALSE 0
    
    typedef int Status;
    typedef int ElemType;
    typedef struct Node // 结构体定义
    {
        ElemType data;
        struct Node *next;
    } Node;
    typedef struct Node *LinkList;
    
    /*
        功能: 初始化一个带有头结点的单链表
    */
    LinkList InitList()
    {
        LinkList head;
        head = (LinkList)malloc(sizeof(LinkList));
        head->next = NULL;  // 头结点指向NULL表示这是一个带有头结点的空单链表
        return head;
    }
    
    /*
        功能:头插法(随机)建立一个单链表
    */
    void CreateFormHead(LinkList *head, int n)
    {
        LinkList s;
        int i;
        srand(time_t(1));  // 随机种子
    
        for (i = 0; i < n; i++)
        {
            s = (LinkList)malloc(sizeof(LinkList));  // 申请内存
            s->data = rand() % 100 + 1;              // 随机生成0-100内任意的一个数
            s->next = (*head)->next;                 // 将申请结点的next指向原来头结点的next
            (*head)->next = s;                       // 将头结点的next指向申请的结点
        }
    }
    /*
        功能:头插法(自己输入)建立一个单链表
    */
    void CreateFormHead2(LinkList *head)
    {
        LinkList s;
        double c;
        int flag = 1;
        while (flag)
        {
            cin >> c;
            if (c != -99999)                             // 输入-99999结束输入
            {
                s = (LinkList)malloc(sizeof(LinkList));  // 申请内存
                s->data = c;                             // 将输入的数据放到申请结点的data中
                s->next = (*head)->next;                 // 将申请结点的next指向原来头结点的next
                (*head)->next = s;                       // 将头结点的next指向申请的结点
            }
            else
            {
                flag = 0;
            }
        }
    }
    /*
        功能:利用尾插法创建单链表
    */
    void CreateFormTail(LinkList *head)
    {
        LinkList r,s;
        r = *head;
        double c;
        int flag = 1;
        while (flag)
        {
            cin >> c;
            if (c != -99999)   // 输入-99999结束输入
            {
                s = (LinkList)malloc(sizeof(LinkList));
                s->data = c;   // 将输入的数据放到申请结点的data中
                r->next = s;   // 第一次时,r原本指向头结点,将头结点的next指向申请的结点
                r = s;         // 将r指向申请结点,意思是,r和s都指向最后一个结点
            }
            else
            {
                flag = 0;
                r->next = NULL;
            }
    
        }
    }
    
    /*
        功能:在带头节点的单链表第 i 个位置插入元素 e
    */
    Status List_Insert(LinkList *head, int i, ElemType e)
    {
        LinkList pre, s;
        pre = *head;         // 将指针 pre 指向链表的头结点
        int k=1;
        while (pre && k < i) // 找到第 i-1 个结点,使指针 pre 指向它
        {
            pre = pre->next;
            k++;
        }
        if (!pre || k > i)
        {
            cout << "插入位置不合理!" << endl;
            return ERROR;
        }
    
        s = (LinkList)malloc(sizeof(Node));  // 为 e 申请一个新的结点并由 s 指向它
        s->data = e;                         // 将带插入结点的值 e 赋给 s 的数据域
        s->next = pre->next;                 // 插入操作
        pre->next = s;                       // 插入操作
        return OK;
    }
    
    /*
        功能:删除单链表第 i 个位置的元素,并将删除的元素保存到变量 *e 中
    */
    Status List_Delete(LinkList *head, int i, ElemType *e)
    {
        LinkList pre, r;
        pre = *head;
        int k = 1;                  // 如果k=0, 则下面程序找到的是第 i 个元素
        while (pre->next && k < i)  // 找到第 i-1 个结点,使指针 pre 指向它
        {
            pre = pre->next;
            ++k;
        }
        if (!(pre->next) || k > i)
        {
            cout << "删除位置不合理!" << endl;
            return ERROR;
        }
        r = pre->next;
        pre->next = r->next;
        *e = r->data;
        free(r);
        return OK;
    }
    /*
        功能:查找第 i 个元素,并将该的元素保存到变量 *e 中
    */
    Status Get_Data(LinkList *head, int i, ElemType *e)
    {
        LinkList p;
        p = *head;
        int k = 0;           // 如果k=1, 则下面程序找到的是第 i-1 个元素
        while (p && k < i)   // 找到第 i 个元素, 指针 p 指向第 i 个元素
        {
            p = p->next;
            k++;
        }
        if (!p || k > i)
        {
            cout << "查找位置不合理!" << endl;
            return ERROR;
        }
        *e = p->data;      // 将第 i 个元素保存到变量 *e 中
        return OK;
    }
    
    /*
        功能:显示单链表中所有数据
    */
    Status PrintList(LinkList *head)
    {
        LinkList p;
        p = (*head)->next;
        if (head != NULL)
            do
            {
                cout << p->data << " ";
                p = p->next;
            } while (p != NULL);
            cout << endl;
            return OK;
    }
    
    void main()
    {
        LinkList head;
        ElemType e;
        cout << "开始初始化..............................................." << endl;
        head = InitList();              // 初始化一个空链表
        cout << "初始化操作完毕!" << endl;
        cout << "开始建表(这里是尾插法建表,输入-99999结束建表)..........." << endl;
        //CreateFormHead(&head,10);     // 头插法,随机插入10个数(可用)
        //CreateFormHead2(&head);       // 头插法,自己创建(可用)
        CreateFormTail(&head);          // 尾插法,自己创建
        cout << "建表操作完毕!" << endl;
        cout << "开始插入................................................." << endl;
        List_Insert(&head, 5, 21);      // 插入21在第5个位置上
        cout << "插入操作完毕!" << endl;
        cout << "打印线性表中的所有数据:";
        PrintList(&head);
        cout << "--------------------------------------------" << endl;
        cout << "开始删除(这里删除第2个元素)............................" << endl;
        List_Delete(&head, 2, &e);      // 删除第2个元素
        cout << "删除操作完毕!" << endl;
        cout << "删除后打印线性表中的所有数据:";
        PrintList(&head);
        cout << "--------------------------------------------" << endl;
        cout << "开始查找(这里查找第6个元素)............................." << endl;
        Get_Data(&head,6, &e);         // 查找第6个元素
        cout << "查找操作完毕!" << endl;
        cout << "打印查找到的数据:";
        cout << e << endl;             // 打印第6个元素
        system("pause");
    }

    运行截图

    这里写图片描述

    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 4,453
精华内容 1,781
关键字:

单链表的基本操作