单链表
2020-10-22 本文已影响0人
WhiteStruggle
ListBook_Link.h
#ifndef _ListBook_Link_
#define _ListBook_Link_
#include<iostream>
#include <string>
#include <stdlib.h>
#include <malloc.h>
using namespace std;
#define LIST_SIZE sizeof(L_Node) // 结构体的字节数
typedef struct Once_Message
{
char name[20];
char address[20];
char phone[20];// 存放的数据信息
}msg;
typedef struct Student
{
msg infor;
struct Student* next; // 线性表的 next 指针
}L_Node, *List_Node;
// 程序员 类
class Programmer
{
public:
/**
注意使用合理的结构声明，
Node * 强调结构体
List_Node 强调指针链表
*/
bool IsNULL (List_Node L); // 判断是否为空表
int ListLength (List_Node L); // 线性表的长度
L_Node* InitList(); // 构建空的线性表
bool GetElem (List_Node L, int cur_e, List_Node &pre_e); // 查找本位
bool PriorElem (List_Node L, int cur_e, List_Node &pre_e); // 返回前驱
bool NextElem (List_Node L, int cur_e, List_Node &pre_e); // 返回后驱
bool ListInsert(List_Node& L, int i, msg e); // 添加数据e
bool ListDelete(List_Node& L, int i, msg &e); // 删除 i 位置上的数据
bool ClearList (List_Node& L); // 清空，重置线性表
bool DestroyList(List_Node& L); // 销毁线性表
void FindList (List_Node L); // 查看 表的数据
};
// 判断是否为空表
bool Programmer::IsNULL (List_Node L)
{
return L->next == NULL;
}
// 构建空的线性表
L_Node* Programmer::InitList ()
{
L_Node* L;
// 分配空间
L = (List_Node)malloc(LIST_SIZE);
// 分配失败，结束
if (L == NULL) exit(1);
// 初始化链表头节点
L->next = NULL;
return L;
}
// 线性表的长度
int Programmer::ListLength(List_Node L)
{
if (this->IsNULL(L)) return 0;
int length = 0;
while (L->next != NULL)
{
length++;
L = L->next;
}
return length;
}
// 返回前驱
bool Programmer::PriorElem (List_Node L, int cur_e, List_Node &pre_e)
{
if (this->IsNULL(L)) return false; // 判断是否为空表
if (cur_e <= 1 || cur_e > this->ListLength(L) ) return false; // 判断 cur_e 的值是否合法
L_Node * p = L; // 引用链表
int num = 0; // 用来判断位置
while (p->next && num < cur_e-1)
{
p = p->next;
num++;
}
pre_e = p;// 返回找到的位置
return true;
}
// 查找 i 位置
bool Programmer::GetElem (List_Node L, int cur_e, List_Node &pre_e)
{
if (this->IsNULL(L)) return false; // 判断是否为空表
if (cur_e < 1 || cur_e > this->ListLength(L)) return false; // 判断 cur_e 的值是否合法
L_Node * p = L; // 引用链表
int num = 0; // 用来判断位置
while (p->next && num < cur_e)
{
p = p->next;
num++;
}
pre_e = p;// 返回找到的位置
return true;
}
// 返回后驱
bool Programmer::NextElem (List_Node L, int cur_e, List_Node &pre_e)
{
if (this->IsNULL(L)) return false; // 判断是否为空表
if (cur_e < 1 || cur_e >= this->ListLength(L)) return false; // 判断 cur_e 的值是否合法
L_Node * p = L; // 引用链表
int num = 0; // 用来判断位置
/*
cur_e 是从 1 开始
num 是从 0 开始
表头为空
例如：有三个数据，cure_e = 2
H -》 1 -》(1) -》 1 -》 0
循环条件判断： num：0 1 2 3 n
cur_e：2 2 2 2 2
p: 0 1 2 3 n
循环次数：0 1 2 3 n
*/
while (p->next && num <= cur_e)
{
p = p->next;
num++;
}
pre_e = p; // 返回找到的位置
return true;
}
// 在 i 前添加数据e
bool Programmer::ListInsert(List_Node& L, int i, msg e)
{
// local 用来判断 添加到i位置的 前后 哪个位置
L_Node *p = L;
// 判断 i 值，小于 1 为错误的输入，当表为空时，若想要插入第一个数据，就需要
if (i < 1 || i >
( this->IsNULL(L) ?
( this->ListLength(L) + 1)
: this->ListLength(L)
)
) return false;
// 分配内存空间
L_Node * q =(List_Node)malloc(LIST_SIZE);
if (!q) exit(1);
// 添加数据
strcpy_s(q->infor.name, e.name);
strcpy_s(q->infor.address, e.address);
strcpy_s(q->infor.phone, e.phone);
q->next = NULL;
// 表头插入
if (i == 1 && this->IsNULL(L))
{
L->next = q;
}
else
{
this->PriorElem(L, i, p); // 前驱
if(p->next != NULL)
q->next = p->next;
p->next = q;
}
return true;
}
// 删除 i 位置的数据
bool Programmer::ListDelete(List_Node& L, int i, msg &e)
{
if (this->IsNULL(L)) return false; // 判断是否为空表
if (i < 1 || i > this->ListLength(L)) return false; // 判断 cur_e 的值是否合法
// q 用来存储要删除内容的内存地址
List_Node p = L, q;
this->PriorElem(L, i, p); // 返回前驱
q = p->next;
// 获取值
strcpy_s(e.name, p->next->infor.name);
strcpy_s(e.address, p->next->infor.address);
strcpy_s(e.phone, p->next->infor.phone);
/*
p->next 指向要删除的数据地址
p->next->next 指向后驱元素的地址
*/
if (i == 1 || p->next->next != NULL)
{
p->next = p->next->next;
}
else
{
p->next = NULL;
}
// 释放删除空间
free(q);
return true;
}
// 清空，重置线性表
bool Programmer::ClearList (List_Node& L)
{
List_Node p = L->next,q;
while (p != NULL)
{
q = p->next;
free(p);
p = q;
}
L->next = NULL;
return true;
}
// 销毁线性表
bool Programmer::DestroyList(List_Node& L)
{
this->ClearList(L);
free(L);
if (!L) exit(1);
return true;
}
// 查看 表的数据
void Programmer::FindList (List_Node L)
{
if (this->IsNULL(L))
{
cout << "Not Found More！" << endl;
}
else
{
int i = 1;
while(L->next)
{
L = L->next;
cout
<< "第" << i << ":"
<< L->infor.name
<< "，来自 " << L->infor.address
<< "，联系方式：" << L->infor.phone << endl;
i++;
}
}
}
#endif
测试使用：
#include <iostream>
#include <stdlib.h>
#include "ListBook_Link.h" // 上边创建的头文件
using namespace std;
void Link_list_Book();
int main()
{
Link_list_Book();
system("pause");
return 0;
}
void Link_list_Book()
{
Programmer man;
List_Node L = man.InitList();
int a = man.ListLength(L);
cout << "链表的长度："
<< a
<< endl;
msg ee = { "小渡","港","62" };
man.ListInsert(L, 1, ee); // 添加数据
msg e[5] =
{
{"小我","北极" ,"1"},
{"小名","台湾" ,"2"},
{"小为","钓鱼岛","3"},
{"小Y" ,"河南" ,"4"},
{"小Z" ,"深圳" ,"5"}
};
int i = 1; // 添加数据
while(i < 6)
{
man.ListInsert(L, i, e[i - 1]);
i++;
}
ee = { "小","港","6874512" };
man.ListInsert(L, 2, ee); // 添加数据
msg demo;
if(man.ListDelete(L, 59, demo)) // 删除数据
cout << demo.address << endl; // 删除数据的信息
man.FindList(L); // 查看所有的数据
man.ClearList(L); // 清空数据
man.DestroyList(L); // 销毁表
L = man.InitList(); // 新建表
a = man.ListLength(L);
cout << "链表的长度："
<< a
<< endl;
}
遇到的问题：
0xC0000005: 写入位置 0x00000000 时发生访问冲突
进行插值时，新分配的内存空间无法进行赋值，一直显示访问冲突，当时使用的 string类型，之后又测试了 char *，都无法进行赋值
原因：
内存空间分配问题，数据所占内存空间是未知的，但是在分配内存时，已经固定，两者便产生了矛盾
在分配的内存空间，不要使用指针类型，进行命名，内存空间无法分配
-
在分配内存空间时，要注意 malloc 与 free 的关系，及时合理删除多余的内存空间
-
注意指针
声明指针
数据类型 * 变量名 = NULL;
例如：
char * str；
带星号(*) 的取指针的值
*str 表示 数据的具体内容
str 表示 数据存放的地址
