定义
若将线性表记为(a1,....ai-1,ai,ai+1,....,an)，则表中ai-1领先于ai,ai领先于ai+1,称ai-1是ai 的直接前驱元素，ai+1是ai的直接后继元素，当i = 1,2, ... n-1时，ai有且仅有一个直接后继，当i = 2,3,...,n时，ai有且仅有一个直接前驱， （通俗来说，就是用一根线将数据串联起来）
线性表的顺序存储结构：
指的是用一段地址连续的存储单元依次存储线性表的数据元素（也就是数组）
优点：1.无须为表示表中元素之间的逻辑关系而增加额外的存储空间 2.可以快速存取表中任一位置的元素
缺点：1.插入和删除操作需要移动大量元素 2.当线性表长度变化较大时，难以确定存储空间的容量
3.造成存储空间的浪费
线性表的链式存储结构
就是链表中包含数据域、指针域，当个数据叫做结点，只包含一个指针域的叫做单链表
1.头指针：
链表第一个结点的存储位置叫做头指针，就相当于 struct Node * n = createNode();n 就为头指针
2.头结点：
在链表的第一个结点前附设一个结点，称为头结点，就是在第一个存储数据结点前面的那个结点，这个结点数据域不存数据
3.异同：
头指针：
1.头指针是指链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指针
2.头指针具有标识意义，所以用头指针冠以链表的名字
3.无论链表是否为空，头指针均不为空，头指针是链表的必要元素
头结点：
1.头结点是为了操作的统一和方便而设立的，放在第一个结点之前，其数据域一般无意义
2.有了头结点，对在第一元素结点前插入结点和删除第一结点，其操作与其他结点的操作就统一了，
3.头结点不一定时链表的必须要素
4.当链表的整表创建
4.1头插法
void CreateListHead(LinkList *L,int n){
LinkList p;
int i;
srand(time(0)); //随机产生数
(*L) = (LinkList) malloc(sizeof(Node));
(*L)->next = NULL;
for(i = 0;i<n;i++){
p = (LinkList)malloc(sizeof(Node));
p->data = rand()%100 +1;
p->next = (*L)->next;
(*L)->next = p;
}
}
4.2尾插法
void CreateListHead(LinkList *L,int n){
LinkList p,r;
int i;
srand(time(0)); //随机产生数
(*L) = (LinkList) malloc(sizeof(Node));
(*L)->next = NULL;
for(i = 0;i<n;i++){
p = (LinkList)malloc(sizeof(Node));
p->data = rand()%100 +1;
r->next = p;
r = p;
}
r->next = NULL;
}
4.2整表删除
Status ClearList(LinkList *L){
LInkList p, q;
p = (*L)->next;
while(p){
q = p->pnext;
free(p);
p = q;
}
(*L)->next = NULL;
return OK;
}
5.静态链表
定义：用数组描述的链表，这种方法也叫游标实现法
我们对数组的第一个和最后一个元素作为特殊元素处理，不存数据，我们通常把未被使用的数组元素称为备用链表，而数组第一个元素，即下标为0的元素的cur就存放备用链表的第一个结点的下标，而数组的最后一个元素的cur则存放第一个有数值的元素下标，相当于单链表的头结点作用。
d9e7cb8f702284fdda1d4e654142323.jpg
# define MAXSIZE 1000
typedef stuct{
ElemType data;
int cur;
}Component,StaticLinkList[MAXSIZE];
//将这个链表初始化
Status InitList(StaticLinkList space){
int i;
for(i = 0;i< MAXSIZE -1;i++){
space[i].cur = i+1;
}
space[MAXSIZE].cur = 0;
return OK;
}
5.1静态链表的插入操作
8e6fe780d39cd58116aaa3997d46ce3.jpg
// 这个函数是得到下一个存储空间的下标
int Malloc_SLL(StaticLinkList space){
int i = space[0].cur;
if(space[0].cur)
space[0].cur = space[i].cur;
return i;
}
Status ListInsert(StaticLinkList L,int i,ElemType e){
int j,k,l;
k = MAX_SIZE -1; //得到的是第一个有值元素的下标
if(i < 1 || i > ListLength(L) + 1)
return ERROR;
j = Malloc_SSL(L); // 得到插入的下标，并将0下标中备用链表更新；
if(j){ // 在C 语言中，除了0，都是真
L[j].data = e; // 赋值
// 找到插入下标之前的元素下标
for(l = 1;l <= i -1;l++){
k = L[k].cur;
}
//将插入前的那个元素存储的下标赋值给插入的元素，即插入元素执行下一个元素
L[j].cur = L[k].cur;
// 前一个元素指向插入元素
L[k].cur = j;
return OK;
}
}
5.2静态链表的删除操作
// 删除在L中第i 个数据元素e
Status ListDelete(StaticLinkList L,int i){
int j,k;
if(i < 1 || i > ListLength(L))
return ERROR;
k = MAX_SIZE -1;
for(j = 1;j<= i -1;j++)
k = L[k].cur;
j = L[k].cur;
L[k].cur = L[j].cur;
Free_SSL(L,j);
return OK;
}
void Free_SSL(StaticLinkList space,int k){
space[k].cur = space[0].cur;
space[0].cur = k;
}
//静态链表长度
int ListLength(StaticLinkList L){
int j = 0;
int i = L[MAXSIZE -1].cur;
while(i){
i = L[i].cur;
j++;
}
return j;
}
6.循环链表
定义：将单链表中终端结点的指针端由空指针改为指向头结点，就是整个单链表形成一个环，这种头尾相接的单链表称为单循环链表。
3a9505df3e84263ef3568f732a6a1f7.jpg
将两个循环链表合为一个的代码
p = rearA->next; //保存A的头结点
rearA->next= rearB->next->next; // 使A指向B的第一个有值元素，
q = rearB->next;//将头结点赋值给q
rearB->next = p;//将B指向A的头结点
free(q);//释放B的头结点
7.双向链表
定义：是在前链表的每个结点中，在设置一个指向其前驱结点的指针域
ElemType data;
struct DulNode *prior;
struct DulNode *next;
}DulNode,* DuLinkList;
插入数据：先搞定插入结点的前驱和后继，再搞定后结点的前驱，最后解决前结点的后继
cfd35ed398d3a35a044f405e1fe2e9d.jpg
删除数据：记得free(p);
fe66e15eb4e4d1666a2e761c41a845c.jpg
网友评论