首页 > 代码库 > 数据结构和算法-学习笔记5
数据结构和算法-学习笔记5
线性表两种存储结构-链式存储
定义：用一组任意的存储单元存储线性表的数据元素，这组存储单元可以存在内存中未被占用的任意位置
我们把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。指针域中存储的信息称为指针或链。这两部分信息组成数据元素称为存储映像，称为结点（Node）
单链表
头结点和头指针的区别
头指针：
-链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指针
-头指针具有标示作用，所以常用头指针冠以链表的名字
-无论链表是否为空，头指针均不为空
-头指针是链表的必要元素
头结点：
-头结点是为了操作的统一和方便而设立的，放在第一个元素的结点之前，其数据域一般无意义
-有了头结点，对在第一元素结点前插入结点和删除第一结点起操作与其它结点的操作就统一了
-头结点不是链表的必要元素
单链表图例
空链表
用结构指针来描述单链表存储结构
typedef struct Node
{
ElemType data;//数据域
struct Node* Next;//指针域
}Node;
typedef struct Node* LinkList;
单链表的读取
思路：
①声明一个结点p指向链表的第一个结点，初始化j从1开始
②当就j<i时，就遍历链表，让p的指针向后移动，不断指向下一结点，j+1；
③若到链表末尾p为空，则说明第i个元素不存在；
④否则查找成功，返回结点p数据
示例代码
Status GetElem(LinkList L,int i,ElemType *e)
{
int j;
LinkList p;
p = L->next;
j = 1;
while(p && j<1)
{
p = p->next;
++j;
}
if(!p || j>i)
{
return ERROR;
}
*e = p->data;
return OK;
}
时间复杂度O(n)
单链表插入
如，在ai和ai+1中间插入s结点
思路：
-声明一个结点p指向表头结点，初始化j从1开始；
-j<1，就遍历表，让p向后移动，不断指向下一个结点（j++）
-若链表末位p为空，则说明要插入的i位置不存在
-如果查找成功，生成一个s结点
-将数据元素e赋值给s->data；
-单链表插入刚才两个标准语句
-返回成功
代码：
Status ListInsert(LinkList *L,int i,ElemType e)
{
int j;
LinkList p,s;
p = +L;
j =1;
while(p && j<i) //遍历第i个元素，从1开始到i结束
{
p = p->next;
j++;
}
if(!p || j>1)//如果到末尾，就返回提示
{
return ERROR;
}
s=(LinkList)malloc(sizeof(Node));
s->data =http://www.mamicode.com/e;//赋值
//以下两句不可写反哦
s->next = p->next;
p->next = s;
return OK;
}
单链表的删除操作
如在单链表a1，a2，a3中把a2删除
思路：
-声明结点p指向链表第一个结点，初始化j=1；
-当就j<1时，遍历链表，让p指针后移，不断指向下一个结点
-若到链表尾部为空，则说明要删除的i位置不存在
-查找成功，将结点p->next赋值给q
-单链表的删除标准语句p->next = q->next
-将q结点中数据赋值给e，返回
-释放q结点
代码：
Status ListInsert(LinkList *L,int i,ElemType e)
{
int j;
LinkList p,q;
p = +L;
j = 1;
while(p->next && j<i) //遍历第i个元素，从1开始到i结束
{
p = p->next;
++j;
}
if(!(p->next) || j>1)//如果到末尾，就返回提示
{
return ERROR;
}
q = p->next;
p->next = q->next;
*e = q->data;
free(q);
return OK;
}
对于插入和删除越频繁的操作，单链表的效率优势越明显
数据结构和算法-学习笔记5