Categories: 算法相关

线性表之“单链表”

链接存储方法:

链接方式存储的线性表简称为链表(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");

return 0;
}
[/code]

龚杰洪

Share
Published by
龚杰洪
Tags: 链表

Recent Posts

GOLANG面试八股文-并发控制

背景 协程A执行过程中需要创建…

1 年 ago

MYSQL面试八股文-常见面试问题和答案整理二

索引B+树的理解和坑 MYSQ…

1 年 ago

MYSQL面试八股文-InnoDB的MVCC实现机制

背景 什么是MVCC? MVC…

1 年 ago

MYSQL面试八股文-索引类型和使用相关总结

什么是索引? 索引是一种用于加…

1 年 ago

MYSQL面试八股文-索引优化之全文索引(解决文本搜索问题)

背景:为什么要有全文索引 在当…

1 年 ago