线性表的链式存储结构(LinkList)
2019-07-03 本文已影响0人
fastcv
前言
为了克服顺序表的缺点，可以采用链式方式存储线性表。通常将采用链式存储结构的线性表称为线性链表。
在顺序表中，用一组地址连续的存储单元来依次存放线性表的节点，因此节点的逻辑顺序和物理顺序是一致的。而链表则不然，链表是用一组任意的存储单元来存放线性表的节点，这组存储单元可以是连续的，也可以是非连续的，甚至是零散分布和内存的任何位置上。
示意图
为了正确地表示结点间的逻辑关系，必须在存储线性表的每个数据元素值的同时，存储指示其后续的地址信息，这两部分信息组成的存储映像称为结点（Node）
结点表示图
LinkListNode.PNG
结点包括两个域：数据域用来存储结点的值，指针域用来存储数据元素的直接后续的地址。
单链表中每个节点的存储地址存放在其前驱结点的指针域中，由于线性表中的第一个结点无前驱，所以应设一个头结点H指向第一个结点。由于线性表的最后一个结点没有直接后继，则指定单链表的最后一个结点的指针域为“空”（NULL）。这里称为H。在H结点的数据域中，我们可以存放整个表的长度值。那么一个单链表的存储示意图为
单链表表示图
我们理解的逻辑图：
LinkListExample.PNG
实际中可能的存储地址图：
LinkListAdd.PNG
线性表链式存储的表示
可以理解为将不同的地址连起来存储我们需要的值，用来节约内存空间，消除碎片。
1、定义一个节点（使用结构体）
LinkList.h
#ifndef _LINKLIST_H_
#define _LINKLIST_H_
typedef struct Node
{
int data;
Node *next;
}Node,*LinkList;
LinkList init(LinkList L); //初始化表
int length(LinkList L); //得到总长度
int get_int(LinkList L,int loc); //根据下标得到存储的值
void get_all(LinkList L); //得到所有存储的值
void add(LinkList L,LinkList element); //新增
bool del(LinkList L,int loc); //根据下标删除
bool update(LinkList L,int loc,int new_element); //更新
bool empty(LinkList L); //判断是否为空
bool clear(LinkList L); //清空表
LinkList destory(LinkList L); //销毁表
void insert(LinkList L,int loc,int element); //插入数据
#endif
这里面我们首先定义了一个结构体作为节点，表示每个位置前面图中的结点，这里有两个内容，data是用来存放数据的（头结点中存放表长度），next表示下一个结点的地址（没有就为NULL），下面那些是我们需要完成的方法。
2、完成相应的方法
LinkList.cpp
#include <stdio.h>
#include "LinkList.h"
#include <malloc.h>
LinkList init(LinkList L) //初始化表
{
L = (LinkList)malloc(sizeof(Node)); //头指针
L->next = NULL;
L->data = 0;
printf("init success!!\n");
return L;
}
int length(LinkList L) //得到总长度
{
return L->data;
}
int get_int(LinkList L,int loc) //根据下标得到存储的值
{
if(loc < 0 || loc > L->data-1)
{
printf("the loc don't exists!!\n");
return -1;
}
LinkList p = L;
int i=0;
while(p->next != NULL && i<=loc)
{
p = p->next;
i++;
}
return p->data;
}
void get_all(LinkList L) //得到所有存储的值
{
if(L->data == 0)
{
printf("the list is null\n");
return;
}
LinkList p = L;
while(p->next != NULL )
{
p = p->next;
printf("%7d",p->data);
}
}
void add(LinkList L,int data) //新增
{
LinkList element = (LinkList)malloc(sizeof(Node));
element->data = data;
element->next = NULL;
LinkList p = L;
while(p->next != NULL){
p = p->next;
}
p->next = element;
L->data++;
}
bool del(LinkList L,int loc) //根据下标删除
{
LinkList p = L,q;
int i=0;
while(p->next != NULL && loc > i)
{
p = p->next;
i++;
}
q = p->next;
p->next = q->next;
q->next = NULL;
q->data = NULL;
q = NULL;
L->data--;
printf("del success!\n");
return true;
}
bool update(LinkList L,int loc,int new_element) //更新
{
LinkList p = L;
int i=0;
while(p->next != NULL && loc >= i)
{
p = p->next;
i++;
}
p->data = new_element;
return true;
}
bool empty(LinkList L) //判断是否为空
{
if(L->data == 0 && L->next == NULL){
printf("is empty!\n");
return true;
}
return false;
}
bool clear(LinkList L) //清空表
{
LinkList p = L,q;
int i=0;
while(p->next != NULL)
{
p = p->next;
p->data = NULL;
L->data--;
i++;
}
L->next = NULL;
printf("total clear data is %4d",i);
return true;
}
LinkList destory(LinkList L) //销毁表
{
clear(L);
L = NULL;
printf("destory Successed!! \n");
return L;
}
void insert(LinkList L,int loc,int data) //插入数据
{
LinkList p=L,q;
int i = 0;
while(p->next != NULL && i<loc)
{
p = p->next;
i++;
}
q = p->next;
LinkList element = (LinkList)malloc(sizeof(Node));
element->data = data;
element->next = q;
p->next = element;
}
3、运行查看结果
LinkListMain.cpp
#include <stdio.h>
#include "LinkList.cpp"
int main()
{
LinkList L;
L = init(L);
empty(L);
for(int i=0;i<15;i++)
{
add(L,i);
}
empty(L);
printf("length is %d \n",length(L));
printf("the 10 is %d \n",get_int(L,10));
get_all(L);
del(L,3);
del(L,3);
del(L,3);
printf("length is %d \n",length(L));
get_int(L,10);
get_all(L);
printf("\n");
update(L,5,1000);
insert(L,3,33333);
get_all(L);
clear(L);
destory(L);
return 0;
}
运行结果：
init success!!
is empty!
length is 15
the 10 is 10
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
del success!
del success!
del success!
length is 12
0 1 2 6 7 8 9 10 11 12 13 14
0 1 2 33333 6 7 1000 9 10 11 12 13 14
total clear data is 13
total clear data is 0
destory Successed!!
--------------------------------
Process exited with return value 0
Press any key to continue . . .
链式表的优缺点
优点：新增和删除效率高
缺点：查找和修改效率低
这样，线性表的链式存储就了解完了，我们用自己写的这个来完成各小任务吧
题目1
有两个单链表LA和LB，其元素均为非递减有序排列，编写算法，将它们合并成一个单链表LC，要求LC也是非递减有序排列。例如，LA=(2,2,3)，LB=(1,3,3,4)，则LC=(1,2,2,3,3,4)。
算法分析
1、原来的两个都是非递减有序排列，也就是不需要我们排序了。
2、我们将下标从第一个结点开始，将LA和LB进行比较，小的先放入LC
，大的与另外的下一位比较，小的放入，依次进行下去。
3、最后将LA或者LB中多的放入LC中即可
实现
LinkList MergeLinkList(LinkList La,LinkList Lb,LinkList Lc)
{
LinkList pa,pb,pc;
pa = La->next;
pb = Lb->next;
Lc->data = La->data + Lb->data;
pc = Lc;
while(pa != NULL && pb != NULL)
{
if(pa->data <= pb->data)
{
pc->next = pa;
pc=pc->next;
pa = pa->next;
}else{
pc->next = pb;
pc=pc->next;
pb = pb->next;
}
}
if(pa != NULL)
pc->next = pa;
else
pc->next = pb;
return Lc;
}
算法性能分析
时间复杂度为：O(n)，空间复杂度不考虑，题目有前提条件
