Data Strucrure
本文主要介绍线性表的链式存储结构
为什么要使用链式存储结构？
首先我们知道，根据线性表的顺序存储结构，我们可以对顺序表的数据元素进行随机存取，其存储位置可以用简单公式来表示。然而，顺序表在插入、删除操作上需要耗费大量时间在移动数据元素。另外数组长度相对固定的静态特性，导致当表中数据较多而其变化较大时，操作过程相对复杂，时间复杂度高，浪费时间。
单链表定义与表示
线性表的链式存储结构的特点是：用一组任意的存储单元存储线性表数据元素(这组存储单元可以连续，也可以不连续)。所以数据元素之间的逻辑关系除了存储自身数据之外，还需要存储一个指向其直接后继元素信息。所以链式表数据元素一般包含两个存储域，一个是存储自身数据的值域，另一个存储直接后继信息的指针域。
Link.jpeg
使用结构体定义单链表的结点
typedef struct LNode
{
Elemtype data;
struct LNode *next;
}LNode,*LinkList;
通常习惯上用LinkList定义单链表，强调定义的是某个单链表的头指针；用LNode*通常定义指向单链表中任意结点的指针变量。
为什么要增加单链表头结点？
首先头结点只包含指针域(即指向后继的地址)，增加头结点是为了让首元结点拥有前驱结点，操作时无需对首元结点进行特殊处理。
单链表基本操作与顺序表不同
在顺序表中，两个相邻数据元素的物理位置是紧邻的，其存储位置可以通过简单公式得到，而在单链表中，数据元素的存储位置都是随机的。查找第i个数据元素时，只能从头指针的指针域L=L->next来查询，称为顺序存取。
单链表基本操作
- 初始化单链表 InitLinkList(LinkList L)
- 单链表取直 GetElem(LinkList L,int i,ElemType e)
- 单链表查询 *LocateElem(LinkList L,ElemType e)
- 单链表插入 ListInsert(LinkList &L,int i,ElemType e)
- 单链表删除 ListDelete(LinkList &L,int i)
- 前插法创建单链表 CreateList_H(LinkList &L,int n)
- 后插法创建单链表 CreateList_R(LinkList &L,int n)
基本操作分析
1. 初始化单链表
Status InitList(LinklList &L)
{
L = new LNode;//new 一个新头结点
L->next = NULL;//头结点的next域为NULL，代表为空链表
return OK;
}//初始化
2. 单链表取值(按值查找)
Status GetElem(LinklList L,int i,int &e)
{
LinklList p;
p = new LNode; //new 一个p结点
p = L->next; //p结点为头结点指向的下一个结点
if(i<=0) //判断是否在范围内
return ERROR;
for(int j=1;j<=i;j++)
{
p = p->next;
if(!p) //p结点为空就返回ERROR
return ERROR;
}
e = p->data; //否则e赋值为p结点的值域
return OK;
}//取值
3.单链表查询(按值查询)
LNode *LocateElem(LinklList L,int e)
{
LinklList p;
p = new LNode; //new 一个p结点
for(p=L->next;p!=NULL;p=p->next) //遍历链表
if(p->data == e) //如果找到了
{
printf("%d\n",p->data);//就输出p结点的值域
return p;
}
}
单链表插入
4.单链表插入
Status LinkInsert(LinklList &L,int i,int e)
{
LinklList p,s;
p = new LNode;//new 一个p结点
p = L->next; //p结点指向链表第一个结点
for(int j = 1;j<=i-1; j++ )//遍历
{
p = p->next;
if(!p)
return ERROR;
}
s = new LNode; //new 一个s结点
s->data = e; //s结点的值域等于要插入的数据
if(i == 1)//特殊情况，当要插入的位置是第一位时
{
s->next = L->next; //s的next域等于头结点L的next域
L->next = s; //头结点的next域等于s结点
return OK;
}
s->next = p->next; //一般情况
p->next = s;
return OK;
}//插入
单链表删除
5.单链表的删除
Status LinkDelete(LinklList &L,int i)
{
LinklList p,q;
p = new LNode; //new 一个p结点
p = L->next; //p结点为链表中的第一个结点
if(i<1)
return ERROR;
for(int j = 1;j<=i-1; j++ )
if(!p)
return ERROR;
q = new LNode; //new 一个q结点
q = p->next; //q节点指向被删除节点的下一个结点
if(i == 1) //特殊情况
{
q = L->next; //q节点为链表第一个结点
L->next = L->next->next;//头结点L的next域直接跳过被删除结点q，等于结点q的next域
delete q;//释放空间
return OK;
}
p->next = p->next->next;//一般情况
delete q;
return OK;
}//删除
前插法创建单链表
6.前插法创建链表
void CreateList_H(LinklList &L,int n)
{
LinklList p;
L = new LNode; //new 一个头结点L
L->next = NULL; //头结点L的next域为空，相当于空链表
for(int i = 0; i < n; i++)//遍历
{
p = new LNode; //new 一个p结点
scanf("%d",&p->data); //读入p结点的值域
p->next = L->next; //p的next域赋值为L的next域
L->next = p; //L的next域指向结点p
}
}
C++完整代码
#include<cstdio>
#include<iostream>
using namespace std;
#define maxsize 10010
#define OK 1
#define ERROR 0
#define OVERFLOW -1
typedef int Status;
int e;
int n;
typedef struct LNode
{
int data;
struct LNode *next;
}LNode, *LinklList;
//LinklList *p,*L;
//p = new LNode;
Status InitList(LinklList &L)
{
L = new LNode;
L->next = NULL;
return OK;
}//初始化
Status GetElem(LinklList L,int i,int &e)
{
LinklList p;
p = new LNode;
p = L->next;
if(i<=0)
return ERROR;
for(int j=1;j<=i;j++)
{
p = p->next;
if(!p)
return ERROR;
}
e = p->data;
return OK;
}//取值
LNode *LocateElem(LinklList L,int e)
{
LinklList p;
p = new LNode;
for(p=L->next;p!=NULL;p=p->next)
if(p->data == e)
{
printf("%d\n",p->data);
return p;
}
}
Status LinkInsert(LinklList &L,int i,int e)
{
LinklList p,s;
p = new LNode;
p = L->next;
for(int j = 1;j<=i-1; j++ )
{
p = p->next;
if(!p)
return ERROR;
}
s = new LNode;
s->data = e;
if(i == 1)
{
s->next = L->next;
L->next = s;
return OK;
}
s->next = p->next;
p->next = s;
return OK;
}//插入
Status LinkDelete(LinklList &L,int i)
{
LinklList p,q;
p = new LNode;
p = L->next;
if(i<1)
return ERROR;
for(int j = 1;j<=i-1; j++ )
if(!p)
return ERROR;
q = new LNode;
q = p->next;
if(i == 1)
{
q = L->next;
L->next = L->next->next;
delete q;
return OK;
}
p->next = p->next->next;
delete q;
return OK;
}//删除
void CreateList_H(LinklList &L,int n)
{
LinklList p;
L = new LNode;
L->next = NULL;
for(int i = 0; i < n; i++)
{
p = new LNode;
scanf("%d",&p->data);
p->next = L->next;
L->next = p;
}
}
void travel(LinklList L)
{
LinklList p;
p = new LNode;
for(p = L->next;p!=NULL;p=p->next)
printf("%d\n",p->data);
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
LinklList L,p,q;
int e;
InitList(L);
CreateList_H(L,n);
travel(L);
/*for(p = L->next;p!=NULL;p=p->next)
printf("%d\n",p->data);*/
LinkInsert(L,3,10);
/*for(p = L->next;p!=NULL;p=p->next)
printf("%d\n",p->data);*/
travel(L);
LinkDelete(L,1);
/*for(p = L->next;p!=NULL;p=p->next)
printf("%d\n",p->data);*/
travel(L);
LocateElem(L,10);
e = 10;
GetElem(L,3,e);
printf("%d\n",e);
}
return 0;
}
吐槽一下，最近笔者开始使用ubuntu来作业，chromium很吃资源，经常时不时卡死，疯狂读硬盘，可怜我那个战斗了四年的5400转机械硬盘，年后该考虑加根内存，上个固态。
最近很火的鹦鹉兄弟表情
暂告一段落
END.
网友评论