单链表的实现

学过数据结构后，只是知道链表是什么，有什么用，但真到用和实现时，却总是感觉无从下手，本文来梳理一遍链表的实现

单链表的实现

链表的初始化和创建

链表初始化

// 单链表的初始化 L为指向头结点的头指针
void InitList(LinkList &L)
{// 构造一个空的单链表L
    L = new Node;   // 生成新的结点作为头结点，用头结点L指向头结点（这时候L就代表改单链表）
    L->next= NULL;  // 头结点的指针域置空
}

头插法创建单链表

// 头插法创建单链表
void CreateList_H(LinkList& L,int n)
{
    for(int i = 0;i < n;i++)
    {
        Node* p = new Node; // 生成新节点指针p p指向新的结点
        cout<<"请输入第"<<i+1<<"个元素：";
        cin>>p->data;
        p->next = L->next; // 从头部插入
        L->next = p;
    }
}

尾插法创建单链表

// 尾插法创建单链表
void CreateList_R(LinkList& L,int n)
{
    Node* r = L; // 尾指针r指向头结点
    for(int i = 0;i < n;i++)
    {
        Node* p = new Node; // 生成新指针结点p
        cout<<"请输入第"<<i+1<<"个元素：";
        cin>>p->data;
        p->next = NULL; // 将新节点的指针域置空
        r->next = p; // 将新节点*p插入尾结点*r之后
        r = p;
    }
}

获取值

获取指定位置单链表值

// 获取指定位置单链表值
void GetElem(LinkList L,int i)
{
    Node* p = L->next; // 生成新指针结点p指向首元结点
    int j = 1;
    while(p && j < i)
    {
        p = p->next; // p指向下一个结点
        j++;
    }
    if(!p || j > i)
        cout<<"i的值不合法!"<<endl;
    else
        cout<<p->data<<endl;
}

查找指定的值，返回元素结点指针

// 单链表按值查找，返回值为找到的元素结点的指针
Node* LocateElem(LinkList L,ElemType e)
{
    Node* p = L->next; // 初始化p，使p指向首元结点
    while(p && p->data != e)
        p = p->next; //顺链表扫描，直到p为空或者找到相应元素为止
    return p;
}

判断是否为空

// 判断链表是否为空
void isEmpty(LinkList L)
{
    if(L->next = NULL)
        cout<<"链表为空"<<endl;
    else
        cout<<"链表不为空"<<endl;
}

单链表插入和删除

单链表在指定位置插入元素

// 单链表指定位置插入元素
void LinkInsert(LinkList& L,int i,ElemType e)
{
    Node* p = L; // 生成新指针结点p指向链表L 因为有可能插入到第一个，所以不指向头结点
    int j = 0;
    while(p && j < i-1)
    {
        p = p->next;
        j++;
    }
    if(!p || j > i-1)
        cout<<"插入位置不合法！"<<endl;
    else{
        Node* s = new Node; // 生成新指针结点s
        s->data = e; // 将结点指针s的数据域置为e
        s->next = p->next;
        p->next = s;
        cout<<"数据插入成功！"<<endl;
    }
}

删除指定位置元素

// 删除指定位置元素
void ListDelete(LinkList& L,int i)
{
    Node* p = L; // 有可能删除第一个元素，所以不指向首元结点
    int j = 0;
    while((p->next) && j < i-1)
    {
        p = p->next;
        j++;
    }
    if(!(p->next)||j > j-1)
        cout<<"删除位置不合理!"<<endl;
    else
    {
        Node* q = p->next; // 临时保存被删结点的地址以备释放
        p->next = q->next; // 改变删除结点前驱结点的指针域，指向删除结点的后继结点
        delete q; // 释放删除结点的空间
        cout<<"删除成功！"<<endl;
    }
}

删除和清空表

清空单链表

// 清空单链表
void ClearList(LinkList L)
{
    LinkList p,q;
    p = L->next; // p指向第一个结点
    while(p != NULL)
    {
        q = p->next;
        delete p;
        p = q;
    }
    L->next = NULL;
    cout<<"链表已清空!"<<endl;
}

整表删除

// 整表删除
void DestoryList(LinkList L)
{
    LinkList p;
    while(L)
    {
        p = L;
        L = L->next;
        delete p;
    }
    cout<<"链表已删除"<<endl;
}

获取单链表的长度

// 获取单链表的长度
int GetLen(LinkList L)
{
    int len = 0;
    Node* p = L;
    if(L == NULL)
        return -1;
    while(p->next != NULL)
    {
        p = p->next;
        len++;
    }
    return len;
}

两个有序链表的归并

// 两个有序链表的归并
void Merge(LinkList A,LinkList B,LinkList &C)
{
    Node* p = A->next;  // p指向首元结点
    Node* q = B->next;  //q指向首元结点
    C = A;
    C->next = NULL;
    Node* r = C;
    while(p != NULL && q != NULL)
    {
        if(p->data <= q->data)
        {
            r->next = p;
            p = p->next;
            r = r->next;
        }else{
            r->next = q;
            q = q->next;
            r = r->next;
        }
    }
    if(p != NULL)
        r->next = p;
    if(q != NULL)
        r->next = q;
}

完整代码

#include <iostream>
using namespace std;
#define ElemType int
typedef struct Node
{
    ElemType data;  // 结点数据域
    struct Node *next; //结点指针域
}Node,*LinkList; // Node为单链表的结点 LinkList为指向结点Node的指针
/*
这是定义一个结构体，这个结构体有两个属性，
一个是ElemType类型的data;
另一个是这个结构体类型的指针next;
给这个结构定义了一个别名:Node，一个指针的别名:LinkList;
Node a; 等价于 struct node a;
都是声明一个struct node结构体类型的结构体变量 a;
LinkList b; 等价于 struct Node *b;等价于 Node *b;
但是为了提高代码的可读性，我们用LinkList声明链表eg：LinkList L
声明一个struct Node结构体类型的指针变量 b（这个指针变量指向结点Node）;
重要：
Node* p=L->next;//这是新建一个指针名叫p，它指向的是首元结点。
即：p代表首元结点的地址，*p就代表指向这个地址p，这里可理解为*p就是首元结点
*/

// 单链表的初始化 L为指向头结点的头指针
void InitList(LinkList &L)
{// 构造一个空的单链表L
    L = new Node;   // 生成新的结点作为头结点，用头结点L指向头结点（这时候L就代表改单链表）
    L->next= NULL;  // 头结点的指针域置空
}
// 头插法创建单链表
void CreateList_H(LinkList& L,int n)
{
    for(int i = 0;i < n;i++)
    {
        Node* p = new Node; // 生成新节点指针p p指向新的结点
        cout<<"请输入第"<<i+1<<"个元素：";
        cin>>p->data;
        p->next = L->next; // 从头部插入
        L->next = p;
    }
}
// 尾插法创建单链表
void CreateList_R(LinkList& L,int n)
{
    Node* r = L; // 尾指针r指向头结点
    for(int i = 0;i < n;i++)
    {
        Node* p = new Node; // 生成新指针结点p
        cout<<"请输入第"<<i+1<<"个元素：";
        cin>>p->data;
        p->next = NULL; // 将新节点的指针域置空
        r->next = p; // 将新节点*p插入尾结点*r之后
        r = p;
    }
}
// 获取指定位置单链表值
void GetElem(LinkList L,int i)
{
    Node* p = L->next; // 生成新指针结点p指向首元结点
    int j = 1;
    while(p && j < i)
    {
        p = p->next; // p指向下一个结点
        j++;
    }
    if(!p || j > i)
        cout<<"i的值不合法!"<<endl;
    else
        cout<<p->data<<endl;
}
// 单链表按值查找，返回值为找到的元素结点的指针
Node* LocateElem(LinkList L,ElemType e)
{
    Node* p = L->next; // 初始化p，使p指向首元结点
    while(p && p->data != e)
        p = p->next; //顺链表扫描，直到p为空或者找到相应元素为止
    return p;
}
// 判断链表是否为空
void isEmpty(LinkList L)
{
    if(L->next = NULL)
        cout<<"链表为空"<<endl;
    else
        cout<<"链表不为空"<<endl;
}
// 单链表指定位置插入元素
void LinkInsert(LinkList& L,int i,ElemType e)
{
    Node* p = L; // 生成新指针结点p指向链表L 因为有可能插入到第一个，所以不指向头结点
    int j = 0;
    while(p && j < i-1)
    {
        p = p->next;
        j++;
    }
    if(!p || j > i-1)
        cout<<"插入位置不合法！"<<endl;
    else{
        Node* s = new Node; // 生成新指针结点s
        s->data = e; // 将结点指针s的数据域置为e
        s->next = p->next;
        p->next = s;
        cout<<"数据插入成功！"<<endl;
    }
}
// 删除指定位置元素
void ListDelete(LinkList& L,int i)
{
    Node* p = L; // 有可能删除第一个元素，所以不指向首元结点
    int j = 0;
    while((p->next) && j < i-1)
    {
        p = p->next;
        j++;
    }
    if(!(p->next)||j > j-1)
        cout<<"删除位置不合理!"<<endl;
    else
    {
        Node* q = p->next; // 临时保存被删结点的地址以备释放
        p->next = q->next; // 改变删除结点前驱结点的指针域，指向删除结点的后继结点
        delete q; // 释放删除结点的空间
        cout<<"删除成功！"<<endl;
    }
}
// 打印单链表
void PrintList(LinkList L)
{
    Node* p;
    if(L->next == NULL)
        cout<<"该单链表为空！"<<endl;
    else
    {
        p = L->next;
        while(p)
        {
            cout<<p->data<<' ';
            p = p->next;
        }
        cout<<endl;
    }
}
// 清空单链表
void ClearList(LinkList L)
{
    LinkList p,q;
    p = L->next; // p指向第一个结点
    while(p != NULL)
    {
        q = p->next;
        delete p;
        p = q;
    }
    L->next = NULL;
    cout<<"链表已清空!"<<endl;
}
// 整表删除
void DestoryList(LinkList L)
{
    LinkList p;
    while(L)
    {
        p = L;
        L = L->next;
        delete p;
    }
    cout<<"链表已删除"<<endl;
}
// 获取单链表的长度
int GetLen(LinkList L)
{
    int len = 0;
    Node* p = L;
    if(L == NULL)
        return -1;
    while(p->next != NULL)
    {
        p = p->next;
        len++;
    }
    return len;
}
// 两个有序链表的归并
void Merge(LinkList A,LinkList B,LinkList &C)
{
    Node* p = A->next;  // p指向首元结点
    Node* q = B->next;  //q指向首元结点
    C = A;
    C->next = NULL;
    Node* r = C;
    while(p != NULL && q != NULL)
    {
        if(p->data <= q->data)
        {
            r->next = p;
            p = p->next;
            r = r->next;
        }else{
            r->next = q;
            q = q->next;
            r = r->next;
        }
    }
    if(p != NULL)
        r->next = p;
    if(q != NULL)
        r->next = q;
}
void menu()
{
    cout << "---------------------------" << endl;
    cout << "0---创建表" << endl;
    cout << "1---清空单链表" << endl;
    cout << "2---判断单链表是否为空" << endl;
    cout << "3---求单链表长度" << endl;
    cout << "4---获取单链表指定位置元素" << endl;
    cout << "5---在单链表指定位置插入元素" << endl;
    cout << "6---删除单链表指定位置元素" << endl;
    cout << "7---显示单链表" << endl;
	cout << "8---两个有序链表归并" << endl;
    cout << "    退出，输入一个负数!" << endl;
    cout << "请输入操作代码：";
}
int main()
{
    LinkList L;
    InitList(L);
    int num;
    menu();
    cin>>num;
    int index;
    int n;
    while(num >= 0)
    {
        if (num == 8)
		{
			Node* A;
			InitList(A);
			cout << "注意两个链表元素大小从小到大排序" << endl;
			cout << "创建第一个链表" << endl;
			cout << "请输入元素个数：";
			cin >> n;
			CreateList_R(A, n);
			Node* B;
			InitList(B);
			cout << "创建第二个链表" << endl;
			cout << "请输入元素个数：";
			cin >> n;
			CreateList_R(B, n);
			Node* C;
			InitList(C);
			Merge(A, B, C);
			cout << "合并后链表元素为";
			PrintList(C);
			menu();
			cin >> num;
			continue;
		}
		if (GetLen(L) == 0 && num != 0)
		{
			cout << "链表长度为0，请先为链表添加数据。" << endl;
			cout << "请输入表的长度：";
			cin >> n;
			CreateList_R(L, n);
			menu();
			cin >> num;
			continue;
		}
		switch (num)
		{
		case 0:
			int n;
			cout << "请输入表的长度";
			cin >> n;
			CreateList_R(L, n);
			break;
		case 1:
			ClearList(L);
			break;
		case 2:
			isEmpty(L);
			break;
		case 3:
			cout << "链表长度为："<<GetLen(L) << endl;
			break;
		case 4:
			int index;
			cout << "请输入位置：";
			cin >> index;
			cout << "该位置元素为：";
			GetElem(L, index);
			break;
		case 5:
			ElemType e;
			cout << "请输入位置和元素：";
			cin >> index >> e;
			LinkInsert(L, index, e);
			break;
		case 6:
			cout << "请输入位置：";
			cin >> index;
			ListDelete(L, index);
			break;
		case 7:
			PrintList(L);
			break;
		default:
			cout << "输入数字有误，请重新输入。" << endl;
			break;
		}
        menu();
		cin >> num;
    }
    return 0;
}