数据结构第二章笔记【代码实现，经反复测试】
一.关于类的部分
说明：
在(datastucture.h)中，封装一个名为datastucture的命名空间，在名为datastucture的命名空间封装一个class LinearList名为线性表的类：
#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include <malloc.h>
#include <stdio.h>
namespace datastucture{
class LinearList//1.线性表的类
{
typedef public int ElemType;
#pragma region 1.定义_顺序表初始化
#define MaxSize 50
typedef struct {
ElemType data[MaxSize];
int length;//顺序表的当前长度
}SqList;//静态顺序表
public:SqList SqList1,SqList2,SqList3;
#define InitSize 100
typedef struct {
ElemType* data;//指示动态分配数组的指针
int MaxSize1, length;//数组的最大容量和当前个数
}SeqList;//动态顺序表
public:SqList SeqList1,SeqList2,SeqList3;
#pragma endregion
#pragma region 2.定义_链表初始化
typedef struct LNode { //定义单链表结点类型
ElemType data; //数据域
struct LNode* next; //指针域
}LNode, * LinkList;
public: LinkList L1,L2,L3,L4;
public: LNode*LN1=NULL, *LN2 = NULL;//定义指向节点的指针LN1，LN2
typedef struct DNode { //定义双链表结点类型
ElemType data; //数据域
struct DNode* prior, * next; //前驱和后继指针
}DNode, * DLinkList;
#define MaxSize 50 //静态链表的最大长度
typedef struct { //定义静态链表结构类型
ElemType data; //存储数据元素
int next; //下一个元素的数组下标
}SLinkList[MaxSize];
#pragma endregion
#pragma region 1.方法_顺序表方法
public:SqList CreateList(void) {//本算法实现初始化序表中的静态顺序表，并不带元素。
SqList L;
L.length = 0;
return L;
}
public:SqList CreateList(ElemType e1, ElemType e2, ElemType e3) {//本算法实现初始化序表中的静态顺序表，并带3个元素。
SqList L;
L.data[0] = e1;
L.data[1] = e2;
L.data[2] = e3;
L.length = 3;
return L;
}
public:bool Listinsert(SqList& L, int i, ElemType e) {//本算法实现删插入序表中的静态顺序表L中第i个位置的元素
if (i<1 || i>L.length + 1) //判断i的范围是否有效
return false;
if (L.length >= MaxSize) //当前存储空间己满，不能插入
return false;
for (int j = L.length;j >= i;j--)//将第i个元素及之后的元素后移
L.data[j] = L.data[j - 1];
L.data[i - 1] = e;//在位置i处放入e
L.length++; //线性表长度加1
return true;
}
public:bool ListDelete(SqList& L, int i, ElemType& e) {//本算法实现删除顺序表中的静态顺序表L中第i个位置的元素
if (i<1 || i>L.length) //判断i的范围是否有效
return false;
e = L.data[i - 1]; //将被删除的元素赋值给e
for (int j = i;j < L.length;j++)//将第i个位置之后的元素前移
L.data[j - 1] = L.data[j];
L.length--; //线性表长度减1
return true;
}
public:int LocateElem(SqList L, ElemType e) {//本算法实现查找顺序表中的静态顺序表L中查找第一个元素值等于e的元素
//实现查找顺序表中值为e的元素
int i;
for (i = 0;i < L.length;i++)
if (L.data[i] == e)
return i + 1; //返回其位序i+1
return 0; //退出循环，说明查找失败
}
public:ElemType GetElem(SqList L, int i) {//本算法实现查找顺序表中的静态顺序表L中查找第i元素值
if (i<1 || i>L.length)
return 0; //退出循环，说明查找失败
else
return L.data[i - 1];
}
public:bool UpdateElem(SqList& L, int i, ElemType e) {//本算法实现查找顺序表中的静态顺序表L中查找第i元素值
if (i<1 || i>L.length)
return false; //退出循环，说明查找失败
else
L.data[i - 1] = e;
return true;
}
public:void PrintList(SqList& L)//直接全部查询
{
for (int i = 0; i < L.length; i++)
{
printf("%d ", L.data[i]);
}
printf("\n");
}
public:void PrintList(SqList& L, bool ret)//根据结果并查询
{
if (ret!=0)
{
printf("True:");
PrintList(L);
}
else {
printf("False\n");
}
}
public:void PrintList(SqList& L, int ret)//根据结果并查询
{
if (ret)
{
printf("True:");
PrintList(L);
}
else {
printf("False\n");
}
}
#pragma endregion
#pragma region 2.方法_单链表方法
/*
#include <malloc.h>
#include <stdio.h>
*/
#define ERROR 9999
bool IsLinkListEmpty(LinkList L)//判断单链表
{
return (L==NULL);
}
void DestroyLinkList(LinkList& L)//销毁单链表
{
if (L == NULL)
return;
LNode* p = L;
LNode* s=L->next;
while (s!=NULL)
{
free(p);//释放上一个结点
p = s;//定位下一个结点
s = s->next;//转向下一个结点
}
free(s);
L = NULL;//防止野指针。
}
LinkList CreateLinkList1(LinkList& L) {
//从表尾到表头逆向建立单链表L，每次均在头结点之后插入元素
LNode* s;int x;
L = (LinkList)malloc(sizeof(LNode)); //创建头结点
L->next = NULL; //初始化为空链表
scanf("%d", &x);
while (x!= ERROR) { //循环输入
s = (LNode*)malloc(sizeof(LNode));//创建新结点
s->data = x;
s->next = L->next;
L->next = s; //将新结点插入表中，L为头指针
scanf("%d", &x);
}//while结束
return L;
}
LinkList CreateLinkList2(LinkList& L) {
//从表头到表尾正向建立单链表L，每次均在表尾插入元素
int x; //设元素类型为整型
L = (LinkList)malloc(sizeof(LNode));
LNode* s, * r = L; //r为表尾指针
int y= scanf("%d", &x);
while (x != ERROR) { //循环输入
s = (LNode*)malloc(sizeof(LNode));
s->data = x;
r->next = s;
r = s; //r指向新的表尾结点
scanf("%d", &x);
}
r->next = NULL; //尾结点指针置空
return L;
}
void PrintLinkList(LinkList L)
{
L = L->next;
while (L!=NULL)
{
printf("%d ",L->data);
L= L->next;
}
printf("\n");
}
LNode* GetElem(LinkList L, int i) {//按序号查找结点值的算法如下：
//本算法取出单链表L(带头结点)中第i个位置的结点指针
if (i < 0)
return NULL; //若i无效，则返回NULL
if (i == 0)
return L; //若i==0，则返回头结点
int j = 1; //计数，初始化为1
LNode* p = L->next; //头结点指针赋给P
while (p != NULL && j < i) { //从第1个结点开始找，查找第i个结点
p = p->next;
j++;
}
return p; //返回第i个结点的指针，如果i大于表长，p= NULL,直接返回p即可
}
LNode* LocateElem(LinkList L, ElemType e) {
//本算法查找单链表L(带头结点)中数据域值等于e的结点指针，否则返回NULL
LNode* p = L->next;
while (p != NULL && p->data != e)//从第1个结点开始查找data域为e的结点
p = p->next;
return p; //找到后返回该结点指针，否则返回NULL
}
bool DeleteLinkListNode(LinkList &L, int i)//删除第i个节点
{
LinkList p = GetElem(L, i-1);//查找删除位置的前驱结点
if (p == NULL)
{
return false;
}
LinkList q;
q = p->next;//令q指向被删除结点
p->next = q->next;//将*q结点从链中“断开”,断链。
free(q);//释放结点的存储空间
q = NULL;//为了避免野指针
return true;
}
int LinkListLength(LinkList L)//求表长
{
int length = 0;//定义一个变量来记录表长
if (L == NULL || L->next == NULL)
return length;
LNode* p = L;
while (p->next != NULL)
{
p = p->next;
length++;
}
return length;//返回表长
}
bool UpdateLinkList(LinkList &L,int i,ElemType e)//单链表改第i结点的数据
{
if (i == 0)//头结点不可修改指
return false;
if (i < 0)//位置不合法
return false;
LinkList p = GetElem(L, i);//查找第i结点的数据结点
p->data = e;//修改第i结点的数据
return true;
}
bool InsertLinkListNode1(LinkList &L, int i, ElemType e)//前插法插入第i个节点
{
LinkList p = GetElem(L, i - 1);//查找删除位置的前驱结点
if (p == NULL)
{
return false;
}
LinkList s= (LNode*)malloc(sizeof(LNode));//为s指针创建内存
s->data = e;
s->next = p->next;
p->next = s;
return true;
}
bool InsertLinkListNode2(LinkList &L, int i, ElemType e)//后插法插入第i个节点
{
LinkList p = GetElem(L, i - 1);//查找删除位置的前驱结点
if (p == NULL)
{
return false;
}
LinkList s= (LNode*)malloc(sizeof(LNode));//为s指针创建内存
s->data = e;
s->next = p->next; //修改指针域，不能颠倒
p->next = s;
ElemType temp = p->data; //交换数据域部分
p->data = s->data;
s->data = temp;
return true;
}
#pragma endregion
};
}
二.关于main()函数的部分
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include "ConsoleApplication1.h"
#include "datastructure.h"
using namespace datastucture;
int main()
{
printf("=====================================《第一内容.顺序表B》====================================\n");
#pragma region 第一内容.顺序表
/*
顺序表
1.初始化和查
2.增
3.删
4.找
5.改
*/
LinearList List1;
#pragma region 1.顺序表初始化
List1.SqList2;//取这个静态线性表，想法初始化成作3元素表。
List1.SqList1 =List1.CreateList();//取线性表类中.静态线性表SqList1，想法初始化成作空表。
List1.SqList2 = List1.CreateList(7,8,9);//取线性表类中.静态线性表SqList1，想法初始化成作空表。
printf("打印一下SqList1表-空表\n");
List1.PrintList(List1.SqList1);
printf("打印一下SqList2表-7,8,9表\n");
List1.PrintList(List1.SqList2);
#pragma endregion
#pragma region 2.顺序表增数据
bool res1 = List1.Listinsert(List1.SqList2, 5, 101);
printf("打印一下增后的SqList2表的不合法插入在第5个的位置插入101\n");
List1.PrintList(List1.SqList2, res1);
bool res2 = List1.Listinsert(List1.SqList2, 2, 101);
printf("打印一下增后的SqList2表的合法插入在第2个的位置插入101\n");
List1.PrintList(List1.SqList2, res2);
#pragma endregion
#pragma region 3.顺序表删数据
int del1 = -1;
int del2 = -1;
bool res3 = List1.ListDelete(List1.SqList2, 5, del1);
printf("删除元素%d[若为-1,则视为非找到].打印一下增后的SqList2表的不合法删除,删除第5位置\n", del1);
List1.PrintList(List1.SqList2, res1);
bool res4 = List1.ListDelete(List1.SqList2, 3, del2);
printf("删除元素%d[若为-1,则视为非找到].打印一下增后的SqList2表的合法删除,删除第3位置\n",del2);
List1.PrintList(List1.SqList2, res2);
#pragma endregion
#pragma region 4.顺序表找数据
int number1= List1.LocateElem(List1.SqList2, 2);
printf("按值2查找,位置为%d[若为0,则视为非找到].打印一下增后的SqList2表的不合法查找\n", number1);
List1.PrintList(List1.SqList2, number1);
int number3 = List1.LocateElem(List1.SqList2, 9);
printf("按值9查找,位置为%d[若为0,则视为非找到].打印一下增后的SqList2表的合法查找\n", number3);
List1.PrintList(List1.SqList2, number3);
int number2 = List1.GetElem(List1.SqList2, 2);
printf("按位置2查找元素为%d[若为0,则视为非找到].打印一下增后的SqList2表的合法查找\n", number2);
List1.PrintList(List1.SqList2, number2);
int number4 = List1.GetElem(List1.SqList2, 7);
printf("按位置7查找元素为%d[若为0,则视为非找到].打印一下增后的SqList2表的不合法查找\n", number4);
List1.PrintList(List1.SqList2, number4);
#pragma endregion
#pragma region 5.顺序表改数据
bool res5 = List1.UpdateElem(List1.SqList2, 2, 444);
printf("按位修改元素.打印一下增后的SqList2表的合法修改,将第2个位置修改成444\n");
List1.PrintList(List1.SqList2, res5);
bool res6 = List1.UpdateElem(List1.SqList2, 8, 444);
printf("按位修改元素.打印一下增后的SqList2表的不合法修改,将第8个位置修改成444\n");
List1.PrintList(List1.SqList2, res6);
#pragma endregion
#pragma endregion
printf("=====================================《第一内容.顺序表E》====================================\n");
printf("=====================================《第二内容.链表B》====================================\n");
#pragma region 第二内容.链表
/*
链表
1.初始化和查
2.增
3.删
4.找
5.改
*/
#pragma region 1.单链表头插法初始化
printf("用头插法生成带头结点的单链表。控制台输入：1 2 3 4 5 9999\n");
List1.L1 = List1.CreateLinkList1(List1.L1);//头插法，生成一个带头结点的
printf("得到的头插法生成带头结点的单链表：");
List1.PrintLinkList(List1.L1);
#pragma endregion
#pragma region 2.单链表尾插法初始化
printf("用尾插法生成带头结点的单链表。控制台输入：1 2 3 4 5 9999\n");
List1.L2 = List1.CreateLinkList2(List1.L2);//头插法，生成一个带头结点的
printf("得到的尾插法生成带头结点的单链表：");
List1.PrintLinkList(List1.L2);
#pragma endregion
#pragma region 3.单链表按位查找
printf("用按位2查找List1.L1\n");
List1.LN1 = List1.GetElem(List1.L1, 2);
if (List1.LN1!=NULL)
{
printf("用按位2查找,查找到的值为%d：\n",List1.LN1->data);
}
#pragma endregion
#pragma region 4.单链表按值查找
printf("用按值2查找List1.L1\n");
List1.LN2 = List1.LocateElem(List1.L1, 2);
if (List1.LN2 != NULL)
{
printf("用按值2查找,查找到的值为%d：\n", List1.LN2->data);
}
#pragma endregion
#pragma region 5.单链表前插法插入元素
printf("前插法插入元素888到List1.L1的第2个位置上\n");
bool res10=List1.InsertLinkListNode1(List1.L1,2,888);
if (res10)
{
printf("True\n");
List1.PrintLinkList(List1.L1);
}
else
{
printf("False\n");
}
#pragma endregion
#pragma region 6.单链表后插法插入元素
printf("后插法插入元素888到List1.L2的第2个位置上\n");
bool res11 = List1.InsertLinkListNode1(List1.L2, 2, 888);
if (res11)
{
printf("True\n");
List1.PrintLinkList(List1.L2);
}
else
{
printf("False\n");
}
#pragma endregion
#pragma region 7.单链表删除第i结点
printf("单链表删除第1结点\n");
bool res12 = List1.DeleteLinkListNode(List1.L1,1);
if (res12)
{
printf("True\n");
List1.PrintLinkList(List1.L1);
}
else
{
printf("False\n");
}
#pragma endregion
#pragma region 8.单链表改第i结点的数据
printf("单链表List1.L1改第1结点，改成333。\n");
bool res13 = List1.UpdateLinkList(List1.L1,1, 333);
if (res13)
{
printf("True\n");
List1.PrintLinkList(List1.L1);
}
else
{
printf("False\n");
}
#pragma endregion
#pragma region 9.单链表表长
printf("单链表List1.L1取表长：%d。\n", List1.LinkListLength(List1.L1));
#pragma endregion
#pragma region 10.销毁单链表
printf("销毁单链表List1.L1\n");
List1.DestroyLinkList(List1.L1);
printf("判断List1.L1单链表是否被销毁:%s\n", List1.IsLinkListEmpty(List1.L1) == 1 ? "TRUE" : "FALSE");
printf("判断List1.L2单链表是否被销毁:%s\n\n", List1.IsLinkListEmpty(List1.L2) == 1 ? "TRUE" : "FALSE");
#pragma endregion
#pragma endregion
printf("=====================================《第二内容.链表E》====================================\n");
return 0;
}
三.代码运行后的部分
