线性表的链式存储结构

93 阅读 0 评论 62 点赞

我是靠谱客的博主生动悟空，这篇文章主要介绍线性表的链式存储结构，现在分享给大家，希望可以做个参考。

1.定义结构体

复制代码

1
2
3
4
5
6
7
8
9
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef struct Node{
int data; // 链表的每个结点的值
struct Node *next; // 定义一个结构体指针，用来指向下一个结点
}Node;
typedef struct Node *LinkList; // 重载定义名

2.表的创建（头插法

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
void CreatList(LinkList *L,int m[],int n)
{
LinkList p; // 定义一个结构体指针
(*L) = (LinkList)malloc(sizeof(Node)); // 也可用 (*L) = new Node;(开辟空间
(*L)->next = NULL;// 定义一个指向第一个节点的空指针
for(int i = 1; i <= n; i ++ )
{
p = (LinkList)malloc(sizeof(Node));(开辟空间
p->data = m[i];
p->next = (*L)->next;
(*L)->next = p;
}
}

3.表的创建（尾插法

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void CreatList1(LinkList *L,int m[],int n)
{
LinkList p, r;// r尾指针初始化
(*L) = (LinkList)malloc(sizeof(Node));
(*L)->next = NULL;
r = (*L);
for(int i = 1; i <= n; i ++ )
{
p = (LinkList)malloc(sizeof(Node));
p->data = m[i];
p->next = NULL;
r->next = p;
r = p;
}
}

4.获取元素的操作

1.用指针p指向首元结点

2.从首元结点开始依次顺着链域next向下查找，只要指向当前结点不为空，并且p所指结点的数据域不等于给定值e，则循环执行以下操作：p指向下一结点。

3.返回p。若查找成功，p此时即为结点的地址值，若查找失败，p的值即为NULL。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
int gerlist(LinkList L, int i, int* e) // 获取第i个插入的元素
{
LinkList p = L->next;
int j = 1;
while(p && j < i)
{
p = p->next;
j ++;
}
if(!p || j > i) return -1; // 寻找失败
*e = p->data;
return 1;
}

5.插入元素的操作

1.查找结点m[i - 1]并由指针p指向该结点

2.生成一个新结点*s

3.讲新生成的结点数据域置为e

4.将新结点*s的指针域指向结点m[i]

5.将结点*p的指针域指向新结点*s

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int insertlist(LinkList *L, int i, int e) // 在i位置后插入元素e
{
LinkList p, s;
p = *L;
int j = 1;
while(p &&j < i)
{
j ++;
p = p->next;
}
if(!p || j > i) return -1;
s=(LinkList)malloc(sizeof(Node));
s->data = e;
s->next = p->next;
p->next = s;
return 1;
}

6.删除元素的操作

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//删除第i个后面的元素
int ListDelete(LinkList *L,int i)
{
LinkList = p, q;
int j = 1;
p = *L;
while(p->next && j < i){ // p的后面必须得有结点
p->next;
j ++;
}
if(!p->next || j > i) return -1;
q = p->next;
p->next = q->next;
free(q);//将结点的空间释放
return 1;
}

7.输出结点

复制代码

1
2
3
4
5
6
7
8
9
10
void Ountlist(LinkList L)
{
LinkList p;
p = L->next;
while(!p){
cout<<p->data<<' ';
p->next;
}
cout<<'n';
}

8.主函数

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

int main()
{
LinkList L;
int e;
int n, m[1000];
cin>>n;
for(int i = 1; i <= n; i ++ ) cin>>m[i];
CreatList(&L, m, n);
gerlist(L, 3, &e);
insertlist(&L, 3, e);
ListDelete(&L, 2);
Ountlist(L);
return 0;
}