线性表之“单链表”

链接存储方法:

链接方式存储的线性表简称为链表（Linked List）。
链表的具体存储表示为：

① 用一组任意的存储单元来存放线性表的结点（这组存储单元既可以是连续的，也可以是不连续的）
② 链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息（称为指针（pointer）或链(link)）

链表的结点结构

data域–存放结点值的数据域
next域–存放结点的直接后继的地址（位置）的指针域（链域）

单链表类型描述

[code lang=”CPP”]
typedef int DataType; //定义数据类型

typedef struct LNode // 定义节点类型
{
DataType data; // 节点的数据存储域
struct LNode *next; // 节点的指针域
}ListNode;

typedef ListNode *LinkList;
[/code]

代码示例如下

下载地址：https://github.com/gongjiehong/ListNode/archive/master.zip

[code lang=”C”]
#include <stdlib.h>
#include <stdio.h>

typedef int DataType; //定义数据类型

typedef struct LNode // 定义节点类型
{
DataType data; // 节点的数据存储域
struct LNode *next; // 节点的指针域
}ListNode;

typedef ListNode *LinkList;

void init_list(LinkList *head, DataType data); // 初始化线性表

int list_is_empty(LinkList head); // 判断表是否为空

ListNode *get(LinkList head, int index); // 通过index查找数据

ListNode *locate_elem(LinkList head, DataType data); // 通过内容查找

int locate_postion(LinkList head, DataType data); // 查找定位

int insert_list(LinkList head, int index, DataType data); // 插入数据

int delete_list(LinkList head, int index, DataType *dataVector); // 删除数据并查看删除的值是什么

int list_length(LinkList head); // 表长度

void destroy_list(LinkList head); // 销毁表

[/code]

[code lang=”C”]
#include "ListNode.h"

void init_list(LinkList *head, DataType data) // 初始化线性表
{
*head = (ListNode *)malloc(sizeof(ListNode));
if (*head == NULL)
{
printf("初始化失败！");
exit(-1);
}
(*head)->next = NULL;
}

int list_is_empty(LinkList head) // 判断表是否为空
{
if (head->next != NULL)
{
return 0;
}
else
{
return 1;
}
}

ListNode *get(LinkList head, int index) // 通过index查找数据
{
ListNode *tempPoint;
int j;

/* 等价于判空
if (head->next == NULL)
{
return NULL;
}
*/

if (list_is_empty(head))
{
return NULL;
}

if (index < 0) { return NULL; } j = 0; tempPoint = head; while (tempPoint->next != NULL && j < index) { tempPoint = tempPoint->next;
j++;
}
if (j == index)
{
return tempPoint;
}
else
{
return NULL;
}
}

ListNode *locate_elem(LinkList head, DataType data) // 通过内容查找
{
if (list_is_empty(head))
{
return NULL;
}

if (head->data == data)
{
return head;
}

LinkList tempPoint = head->next;

int is_founded = 0;

while (tempPoint != NULL)
{
if (tempPoint->data == data)
{
is_founded = 1;
break;
}
else
{
tempPoint = tempPoint->next;
}
}

if (is_founded)
{
return tempPoint;
}
else
{
return NULL;
}

}

int locate_postion(LinkList head, DataType data) // 查找定位
{
if (list_is_empty(head))
{
return 0;
}

if (head->data == data)
{
return 0;
}

LinkList tempPoint = head->next;
int index = 1;
int is_founded = 0;

while (tempPoint != NULL)
{
if (tempPoint -> data == data)
{
is_founded = 1;
break;
}
else
{
tempPoint = tempPoint->next;
index++;
}
}
if (is_founded)
{
return index;
}
else
{
return 0;
}
}

int insert_list(LinkList head, int index, DataType data) // 插入数据
{
// if (list_is_empty(head))
// {
// return 0;
// }
//
// if (index >= list_length(head))
// {
// return 0;
// }

ListNode *tempPoint, *prePoint;
int j = 0;
tempPoint = head;

while (tempPoint != NULL && j < index – 1) { tempPoint = tempPoint->next;
j++;
}
if (tempPoint == NULL)
{
printf("位置有误");
return 0;
}

prePoint = (ListNode *)malloc(sizeof(ListNode));
if (prePoint == NULL)
{
return 0;
}
prePoint->data = data;
/*插入结点操作*/
prePoint->next = tempPoint->next;
tempPoint->next = prePoint;
return 1;
}

int delete_list(LinkList head, int index, DataType *dataVector) // 删除数据并查看删除的值是什么
{
ListNode *pre,*p;
int j;
pre = head;
j = 0;
while(pre->next != NULL && pre->next->next != NULL && j < index-1)/*判断是否找到前驱结点*/ { pre=pre->next;
j++;
}
if(j != index-1) /*如果没找到要删除的结点位置，说明删除位置错误*/
{
printf("删除位置错误");
return 0;
}
/*指针p指向单链表中的第i个结点，并将该结点的数据域值赋值给e*/
p = pre->next;
*dataVector = p->data;
/*将前驱结点的指针域指向要删除结点的下一个结点，也就是将p指向的结点与单链表断开*/
pre->next=p->next;
free(p); /*释放p指向的结点*/
return 1;
}

int list_length(LinkList head) // 表长度
{
ListNode *tempPoint;
int count = 0;
tempPoint = head;
while(tempPoint->next != NULL)
{
tempPoint = tempPoint->next;
count++;
}
return count;

}

void destroy_list(LinkList head) // 销毁表, 从起始节点一直往后销毁释放内存
{
ListNode *p,*q;
p = head;
while(p != NULL)
{
q = p;
p = p->next;
free(q);
}
}
[/code]

[code lang=”C”]
#include <iostream>
#include "ListNode.c"

int main(int argc, const char * argv[]) {
// insert code here…
std::cout << "Hello, World!\n";
LinkList listA;
DataType data = NULL;

init_list(&listA, data);

for (int index = 1; index < 100; index ++)
{
insert_list(listA, index, index);
}

printf("链表长度为：%d\n", list_length(listA));

//显示链表的内容；
printf("链表的内容为：\n");
for (int i = 1; i <= 100; i++) { ListNode *p = get(listA,i); if (p) { printf("%5d",p->data);
}
}
printf("\n");

delete_list(listA, 7, &data);

for (int i = 1; i <= 100; i++) { ListNode *p = get(listA,i); if (p) { printf("%5d",p->data);
}
}
printf("\n");

delete_list(listA, 7, &data);

for (int i = 1; i <= 100; i++) { ListNode *p = get(listA,i); if (p) { printf("%5d",p->data);
}
}
printf("\n");