数据结构之线性表（单链表的实现）

目录

一、单链表的原理

二、单链表的实现

1.单链表的定义

2.单链表的初始化

3.清空单链表

4.单链表是否为空

5.单链表的长度

6.获取指定位置 i 的元素

7.获取指定元素 e 的位置  

8.向链表中插入指定位置的元素

9.向链表中删除指定位置的元素

10.遍历链表中的元素

三、打印测试功能

1.测试

2.结果输出

3.总代码

---

一、单链表的原理

        本章节紧跟上一篇文章《顺序表的实现》来继续讲述线性表的一种：单链表。

        前面我们讲的线性表的顺序存储结构。它是有缺点的，最大的缺点就是插入和删除时需要移动大量元素，这显然就需要耗费时间。能不能想办法解决呢?

         要解决这个问题，我们就得考虑一下导致这个问题的原因。为什么当插入和删除时，就要移动大量元素，仔细分析后，发现原因就在于相邻两元素的存储位置也具有邻居关系。它们编号是1，2，3，…，n，它们在内存中的位置也是挨着的，中间没有空隙，当然就无法快速介入，而删除后，当中就会留出空隙，自然需要弥补。问题就出在这里。

        我们可以在第一个元素时，就知道第二个元素的位置(内存地址)，而找到它;在第二个元素时，再找到第三个元素的位置(内存地址)。这样所有的元素我们就都可以通过遍历而找到，而这就是单链表的特点，如下图所示。

         而链表的结构则如下图所示，第一个节点的指针由头节点所指，第二个节点的指针由第一个节点所指，以此类推。

二、单链表的实现

1.单链表的定义

        定义一些功能常量和单链表的结构。

        这里需要注意的是，我给链表起别名的是一个指针，后面我们在实现链表功能的时候，我们传递函数参数的时候要传递的是一个双指针（LinkList* L）。 这是因为链表的结构使然，因为链表存储的是其他链表的指针，它是一个地址，后面我们在进行链表的增加和删除的时候，会经常涉及到指针的变化。

        如果函数的参数是本身一级指针，那么在函数内部对指针的修改将不会反映到函数外部，因为函数接收到的是指针的一个副本。使用指针的指针作为参数，则可以确保在函数内部对指针的修改能够反映到原始的指针上。

typedef  struct  Node*  LinkList;

#include <iostream>#define MAX_SIZE 20
#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;

2.单链表的初始化

        链表的初始化主要是为头节点分配内存空间，使它的data 和 next 都指向为 NULL，方便我们后续的操作。

Status InitList(LinkList* L)
{*L = (LinkList)malloc(sizeof(Node));if (*L == NULL) return ERROR;(*L)->data = 0;(*L)->next = NULL;return OK;
}

3.清空单链表

        对链表进行清空操作，因为是用 malloc 进行分配的空间，对堆中的空间进行释放操作。

Status ClearList(LinkList* L)
{LinkList p, q;p = (*L)->next;while (p != NULL) {	q = p->next;free(p);p = q;}(*L)->next = NULL;return OK;
}

4.单链表是否为空

        判断头节点指向的元素是否为空。即 next 是否为 NULL。

Status isListEmpty(LinkList L)
{if (L->next  == NULL) return TRUE;return FALSE;
}

5.单链表的长度

        求链表的长度，定义一个变量，然后用while循环遍历链表。

int ListLength(LinkList L)
{int num{ 0 };LinkList temp = L->next;while (temp != NULL){temp = temp->next;num++;}return num;
}

6.获取指定位置 i 的元素

        定义一个变量，进行while操作，判断是否与指定位置 i 相同，获取其节点值。

Status GetElem(LinkList L, int i, ElemType* e)
{int num{ 1 };LinkList temp = L->next;while (temp != NULL && num < i){temp = temp->next;num++;}	if (temp == NULL || num > i) return ERROR;*e = temp->data;
}

7.获取指定元素 e 的位置  

        和上述功能类似，返回值为 int 位置。

int LocateElem(LinkList L, ElemType* e)
{int num{ 0 };LinkList temp = L->next;while (temp != NULL){num++;if (temp->data = *e){return num;}temp = temp->next;}return 0;
}

8.向链表中插入指定位置的元素

          此功能为链表的难点所在，需要根据图像理解实现，如下图所示。 

     

Status LinkInsert(LinkList* L, int i, ElemType e)
{int j;LinkList p, s;p = *L;j = 1;while (p != NULL && j < i){p = p->next;++j;}	if (!p || j > i) return ERROR;s = (LinkList)malloc(sizeof(Node));if (s == NULL) return ERROR;s->data = e;s->next = p->next;p->next = s;return OK;}

9.向链表中删除指定位置的元素

        和上功能类似，如图所示。

Status LinkDelete(LinkList* L, int i, ElemType* e)
{int j;LinkList p, s;j = 1;p = (*L);while (p != NULL && j < i){p = p->next;++j;}if (!p || j > i) return ERROR;s = p->next;p->next = s->next;*e = s->data;free(s);return OK;
}

10.遍历链表中的元素

        功能比较简单，通过不断遍历打印其节点的data值。

Status visit(ElemType e)
{printf("%d->", e);return OK;
}
Status ListTraverse(LinkList L)
{LinkList p = L->next;while (p != NULL){visit(p->data);p = p->next;} printf("\n");return OK;
}

三、打印测试功能

1.测试

        测试主要为测试以上的功能是否可以实现。

int TestSingleList()
{LinkList L;ElemType e;Status ret;int j, k;// 初始化ret = InitList(&L);printf("初始化长度：%d\n", ListLength(L));for(j = 1; j <= 5; j++){ret = LinkInsert(&L, 1, j);}printf("插入5个元素后：");ListTraverse(L);ret = isListEmpty(L);printf("是否为空，%d\n", ret);ret = ClearList(&L);printf("清空后的长度：%d\n", ListLength(L));printf("是否为空，%d\n", ret);for (j = 1; j <= 10; j++){ret = LinkInsert(&L, j, j);}printf("插入10个元素后：");ListTraverse(L);LinkInsert(&L, 3, 100);printf("在第2个节点后面增加元素100：");ListTraverse(L);LinkDelete(&L, 2, &e);printf("删除第二个节点,节点元素为%d :", e);ListTraverse(L);ClearList(&L);return 0;
}

2.结果输出

           结果输出如图所示：

3.总代码

        总代码如下：

#include <iostream>#define MAX_SIZE 20
#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;Status visit(ElemType e)
{printf("%d->", e);return OK;
}Status InitList(LinkList* L)
{*L = (LinkList)malloc(sizeof(Node));if (*L == NULL) return ERROR;(*L)->data = 0;(*L)->next = NULL;return OK;
}Status ClearList(LinkList* L)
{LinkList p, q;p = (*L)->next;while (p != NULL) {	q = p->next;free(p);p = q;}(*L)->next = NULL;return OK;
}Status isListEmpty(LinkList L)
{if (L->next  == NULL) return TRUE;return FALSE;
}int ListLength(LinkList L)
{int num{ 0 };LinkList temp = L->next;while (temp != NULL){temp = temp->next;num++;}return num;
}Status GetElem(LinkList L, int i, ElemType* e)
{int num{ 1 };LinkList temp = L->next;while (temp != NULL && num < i){temp = temp->next;num++;}	if (temp == NULL || num > i) return ERROR;*e = temp->data;
}int LocateElem(LinkList L, ElemType* e)
{int num{ 0 };LinkList temp = L->next;while (temp != NULL){num++;if (temp->data = *e){return num;}temp = temp->next;}return 0;
}Status LinkInsert(LinkList* L, int i, ElemType e)
{int j;LinkList p, s;p = *L;j = 1;while (p != NULL && j < i){p = p->next;++j;}	if (!p || j > i) return ERROR;s = (LinkList)malloc(sizeof(Node));if (s == NULL) return ERROR;s->data = e;s->next = p->next;p->next = s;return OK;}Status LinkDelete(LinkList* L, int i, ElemType* e)
{int j;LinkList p, s;j = 1;p = (*L);while (p != NULL && j < i){p = p->next;++j;}if (!p || j > i) return ERROR;s = p->next;p->next = s->next;*e = s->data;free(s);return OK;
}Status ListTraverse(LinkList L)
{LinkList p = L->next;while (p != NULL){visit(p->data);p = p->next;} printf("\n");return OK;
}Status CreateListHead(LinkList* L,int n)
{LinkList p;srand((unsigned)time(0));*L = (LinkList)malloc(sizeof(Node));if (*L == NULL) return ERROR;(*L)->next = NULL;for (int i = 0; i < n; i++){p = (LinkList)malloc(sizeof(Node));if (p == NULL) return ERROR;p->data = rand() % 100 + 1;p->next = (*L)->next;(*L)->next = p;}return OK;
}Status CreateListTail(LinkList* L,int n)
{LinkList p, r;srand((unsigned)time(0));*L = (LinkList)malloc(sizeof(Node));if (*L == NULL) return ERROR;(*L)->next = NULL;r = (*L);for (int i = 0; i < n; i++){p = (LinkList)malloc(sizeof(Node));if (p == NULL) return ERROR;p->data = rand() % 100 + 1;r->next = p;r = p;}return OK;
}int TestSingleList()
{LinkList L;ElemType e;Status ret;int j, k;// 初始化ret = InitList(&L);printf("初始化长度：%d\n", ListLength(L));for(j = 1; j <= 5; j++){ret = LinkInsert(&L, 1, j);}printf("插入5个元素后：");ListTraverse(L);ret = isListEmpty(L);printf("是否为空，%d\n", ret);ret = ClearList(&L);printf("清空后的长度：%d\n", ListLength(L));printf("是否为空，%d\n", ret);for (j = 1; j <= 10; j++){ret = LinkInsert(&L, j, j);}printf("插入10个元素后：");ListTraverse(L);LinkInsert(&L, 3, 100);printf("在第2个节点后面增加元素100：");ListTraverse(L);LinkDelete(&L, 2, &e);printf("删除第二个节点,节点元素为%d :", e);ListTraverse(L);ClearList(&L);return 0;
}int main()
{return TestSingleList();
}