目录
一、线性表的链式存储结构
编辑
二、单链表
1头插法
2尾插法
3按序号查找
4按值查找
5插入
6删除
三、双链表
1定义
2插入
3删除
四、循环与静态链表
1循环链表
1循环单链表：
2循环双链表：
3应用场景：
2静态链表
应用场景；
一、线性表的链式存储结构
typedef struct LNode{
Elemtype data;
struct LNode *next;
}LNode,*LinkList;
二、单链表
1头插法
建立新的结点分配内存空间，将新结点插入到当前链表的表头
Linklist Creatlist1(Linklist &L){
LNode *s; //辅助指针
int x;
L=(Linklist)malloc(sizeof(LNode)); //创建头结点
L->next=NULL; //空表
scanf("%d",&x); //输入节点的值
while(X!=9999){
s=(LNode*)malloc(sizeof(LNode)); //创建头结点
s->data=x;
s->next=L->next;
L->next=s;
scanf("%d",&x); //输入节点的值
}
return L;
}
2尾插法
建立新的结点分配内存空间，将新结点插入到当前链表的表尾
Linklist Createlist2(Linklist &L){
int x;
L=(Linklist)malloc(sizeof(LNode));
LNode *s,*r=L; //r为表尾指针
scanf("%d",&x);
while(x!=9999){
s=(LNode*)malloc(sizeof(LNode));
s->data=x;
r->next=s;
r=s;
scanf("%d",&x);
}
r->next=NULL; //尾指针置空
return L;
}
3按序号查找
在单链表中从第一个结点出发，顺指针next域逐个往下搜索，直到找到第i个结点为止,否则返回最后一个结点指针域NULL
LNode *Getelem(Linklist L,int i){
int j=1; //计数用的
LNode *p=L->next; //第一个节点赋值给p
if(i==0)
return L; //若i=0返回头结点
if(i<1)
return NULL; //若i无效，返回NULL
while(p&&j p=p->next; j++; } return p; //如果大于表长，直接返回p } 4按值查找 从单链表第一个结点开始，由前往后依次比较表中各结点数据域的值，若某结点数据域的值等于给定值e，则返回该结点的指针；若整个单链表中没有这样的结点，则返回NULL。 LNode *Locateelem(Linklist L,Elemtype e){ LNode *p=L->next; while(p!=NULL&&p->data!=e) p=p->next; reurn p; } 5插入 插入操作是将值为x的新结点插入到单链表的第i个位置上。先检查插入位置的合法性，然后找到待插入位置的前驱结点，即第i−1个结点，再在其后插入新结点。 算法思路： 1.取指向插入位置的前驱结点的指针 ① p=GetElem(L,i-1); 2.令新结点*s的指针域指向*p的后继结点 ② s->next=p->next; 3.令结点*p的指针域指向新插入的结点*s ③ p->next=s; 6删除 删除操作是将单链表的第i个结点删除。先检查删除位置的合法性，然后查找表中第i−1个结点，即被删结点的前驱结点，再将其删除。 算法思路： 1.取指向删除位置的前驱结点的指针 p=GetElem(L,i-1); 2.取指向删除位置的指针 q=p->next; 3.p指向结点的后继指向被删除结点的后继 p->next=q->next 4.释放删除结点 free(q); 三、双链表 1定义 //单链表节点类型 typedef struct LNode{ Elemtype data; struct LNode *next; }LNode,*Linklist; //双链表节点类型 typedef struct DNode{ Elemtype data; struct LNode *prior,*next; }DNode,*DLinklist; 2插入 插入：(方法不唯一) ① s->next=p->next; ② p->next->prior=s; ③ s->prior=p; ④ p->next=s; 3删除 删除： ① p->next=q->next; ② q->next->prior=p; ③ free(q); 四、循环与静态链表 1循环链表 1循环单链表： 循环单链表和单链表的区别在于，表中最后一个结点的指针不是NULL，而改为指向头结点，从而整个链表形成一个环 带头节点判空：p→next=head 2循环双链表： 类比循环单链表，循环双链表链表区别于双链表就是首尾结点构成环 当循环双链表为空表时，其头结点的prior域和next域都等于Head。p→prior==head&&p→next==head 3应用场景： 约瑟夫问题、拉丁方阵问题 2静态链表 静态链表：静态链表是用数组来描述线性表的链式存储结构。 数组第一个元素不存储数据，它的指针域存储第一个元素所在的数组下标。链表最后一个元素的指针域值为-1。 应用场景； 1.不支持指针的低级语言 2.数据元素数据固定不变的场景（如操作系统的文件分配表FAT） 文章来源
发表评论