首页 > > 程序设计 > C/C++ >

数据结构之线性表（链表）

2018-06-17 21:20:38来源：未知阅读 ()

链表

1.链表的定义：线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是

连续的，也可以是不连续的）。因此，为了表示每个数据元素ai与其直接后继数据元素ai+1之间的逻辑关系，对数据元素

ai来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置）。这两部分信息组

成数据元素ai的存储映像，称为结点。它包括两个域，其中存储数据元素信息的域称为数据域；存储直接后继存储位置的

域称为指针域。指针域中存储的信息称做指针或链。n个结点（ai(1<=i<=n）的存储映像）链结成一个链表，即为线性表的

链式存储结构。又由于此链表的每个结点中只包含一个指针域，故又称线性链表或单链表。

2.链表的数据结构

#define ElemType int 
typedef struct ListNode
{
    ElemType data;
    ListNode *next;
}ListNode;
typedef struct List
{
    ListNode *first;
    ListNode *last;
    size_t size;
}List;

3.在链表中有以下操作：

void InitList(List *list);
bool push_back(List *list, ElemType x);
bool push_front(List *list, ElemType x);
void show(List *list);
void pop_back(List *list);
bool insert_val(List *list, ElemType x);
bool delete_val(List *list, ElemType key);
ListNode *find_key(List *list, ElemType key);
void clear_list(List *list);
void reverse_list(List *list);
void sort_list(List *list);
void destroy_list(List *list);

以上声明的方法有：（1）初始化一个链表.（2）尾插法向链表中添加元素.（3）头插法向链表中添加元素.（4）展示链表

内容.（5）尾部删除链表中的数据元素.（6）按值向链表中插入数据元素.（7）按值删除链表中的数据元素.（8）按值查找

链表中的数据数据元素.（9）清空链表操作.（10）逆序排列链表中的数据元素.（11）对链表中的数据元素进行排序.（12）

销毁链表.

4.将上面所声明的方法在LinkList.h的头文件中进行实现：

#ifndef _LINKLIST_H
#define _LINKLIST_H

#include <iostream>
#include <assert.h>
using namespace std;

#define ElemType int 
typedef struct ListNode
{
    ElemType data;
    ListNode *next;
}ListNode;
typedef struct List
{
    ListNode *first;
    ListNode *last;
    size_t size;
}List;

void InitList(List *list);
bool push_back(List *list, ElemType x);
bool push_front(List *list, ElemType x);
void show(List *list);
void pop_back(List *list);
bool insert_val(List *list, ElemType x);
bool delete_val(List *list, ElemType key);
ListNode *find_key(List *list, ElemType key);
void clear_list(List *list);
void reverse_list(List *list);
void sort_list(List *list);
void destroy_list(List *list);

void InitList(List *list)
{
    list->first = list->last = (ListNode*)malloc(sizeof(ListNode));
    list->last->next = NULL;
    assert(list->first != NULL);
    list->size = 0;
}

bool push_back(List *list, ElemType x)
{
    ListNode *s = (ListNode*)malloc(sizeof(ListNode));
    if (s == NULL)
        return false;
    s->data = x;
    s->next = NULL;
    list->last->next = s;
    list->last = s;
    list->size++;
    return true;
}

bool push_front(List *list, ElemType x)
{
    ListNode *s = (ListNode*)malloc(sizeof(ListNode));
    if (s == NULL)
        return false;
    s->data = x;
    s->next = list->first->next;
    list->first->next = s;
    if (list->size == 0)
        list->last = s;
    list->size++;
    return true;
}

void show(List *list)
{
    ListNode *p = list->first->next;
    while (p != NULL)
    {
        cout << p->data << "->";
        p = p->next;
    }
    cout << "Over." << endl;
}

void pop_back(List *list)
{
    if (list->size == 0)
        return;
    ListNode *p = list->first;
    while (p->next != list->last)
        p = p->next;
    p->next = NULL;
    free(list->last);
    list->last = p;
    list->size--;
}

bool insert_val(List *list, ElemType x)
{
    ListNode *p = list->first;
    while (p->next != NULL && p->next->data < x)
        p = p->next;
    ListNode *s = (ListNode*)malloc(sizeof(ListNode));
    if (s == NULL)
        return false;
    s->data = x;
    s->next = NULL;
    s->next = p->next;
    p->next = s;
    if (p == list->last)
        list->last = s;
    list->size++;
    return true;
}

bool delete_val(List *list, ElemType key)
{
    if (list->size == 0)
        return false;
    ListNode *p = list->first;
    while (p->next != NULL && p->next->data != key)
        p = p->next;
    if (p->next == NULL)
        return false;
    ListNode *q = p->next;
    p->next = q->next;
    if (q == list->last)
        list->last = p;
    free(q);
    list->size--;
    return true;
}

ListNode *find_key(List *list, ElemType key)
{
    if (list->size == 0)
        return false;
    ListNode *p = list->first->next;
    while (p != NULL &&p->data != key)
        p = p->next;
    return p;
}

void clear_list(List *list)
{
    if (list->size == 0)
        return;
    ListNode *p = list->first->next;
    while (p != NULL)
    {
        list->first->next = p->next;
        free(p);
        p = list->first->next;
    }
    list->last = list->first;
    list->size = 0;
}

void reverse_list(List *list)
{
    if (list->size <= 1)
        return;
    ListNode *p = list->first->next;
    ListNode *q = p->next;
    list->last = p;
    list->last->next = NULL;
    while (q != NULL)
    {
        p = q;
        q = p->next;
        p->next = list->first->next;
        list->first->next = p;
    }
}

void sort_list(List *list)
{
    if (list->size <= 1)
        return;
    ListNode *p = list->first->next;
    ListNode *q = p->next;
    list->last = p;
    list->last->next = NULL;
    ListNode *t;
    while (q != NULL)
    {
        p = q;
        q = q->next;
        t = list->first;
        while (t->next != NULL && p->data > t->next->data)
            t = t->next;
        if (t->next = NULL)
            list->last = p;
        p->next = t->next;
        t->next = p;
    }
}

void destroy_list(List *list)
{
    clear_list(list);
    free(list->first);
    list->first = list->last = NULL;
}

#endif

5.将上面所实现的方法在主函数中调用实现：

#include <iostream>
#include "LinkList.h"
using namespace std;

int main()
{
    List mylist;
    InitList(&mylist);

    ListNode *p = NULL;
    ElemType item;
    int pos;
    int select = 1;
    while (select)
    {
        cout << "******************************************" << endl;
        cout << "*[1] push_back       [2] push_front      *" << endl;
        cout << "*[3] Show            [4] pop_back        *" << endl;
        cout << "*[5] insert_val      [6] delete_val      *" << endl;
        cout << "*[7] find_key        [8] reverse_list    *" << endl;
        cout << "*[9] sort_list       [10] clear_list     *" << endl;
        cout << "*[0] quit_system                         *" << endl;
        cout << "******************************************" << endl;
        cout << "请选择:>";
        cin >> select;
        switch (select)
        {
        case 1:
            cout << "请输入要插入的数据(-1结束):>";
            while (cin >> item, item != -1)     //逗号表达式
            {
                push_back(&mylist, item);
            }
            break;
        case 2:
            cout << "请输入要插入的数据(-1结束):>";
            while (cin >> item, item != -1) 
            {
                push_front(&mylist, item);
            }
            break;
        case 3:
            show(&mylist);
            break;
        case 4:
            pop_back(&mylist);
            break;
        case 5:
            cout << "请输入要插入的值:>";
            cin >> item;
            insert_val(&mylist, item);
            break;
        case 6:
            cout << "请输入要删除的值:>";
            cin >> item;
            delete_val(&mylist, item);
            break;
        case 7:
            cout << "请输入要查找的值:>";
            cin >> item;
            p = find_key(&mylist, item);
            if (p == NULL)
            {
                cout << "要查找的值:" << item << "不存在!" << endl;
            }
            break;
        case 8:
            reverse_list(&mylist);
            break;
        case 9:
            sort_list(&mylist);
            break;
        case 10:
            clear_list(&mylist);
            break;
        }
        system("pause");
        system("cls");
    }
    destroy_list(&mylist);

    return 0;
}