数据结构与算法--链表、栈、队列
程序员文章站
2022-06-04 09:21:53
...
3.链表
3.1意义:
链表,别名链式存储结构或单链表,用于存储逻辑关系为 “一对一” 的数据。与顺序表不同,链表不限制数据的物理存储状态。
顺序表通过连续的地址建立元素之间前后连接关系,链表通过指针方式建立元素之间前后连接关系。且用法和顺序表相似,只是适用场景有所不同。
3.2链式存储结构
使用链表存储的数据元素,其物理存储位置是随机的。数据元素随机存储,并通过指针表示数据之间逻辑关系的存储结构
3.3实现
链表中每个数据的存储都由以下两部分组成:
1: 数据元素本身,其所在的区域称为数据域;
2: 指向直接后继元素的指针,所在的区域称为指针域;
typedef int LinkType; //存储单元类型 目的为了使链表适和更多数据类型,
// 节点结构体
typedef struct _Node{
LinkType elem; //存储空间基地址
struct _Node* next; //指向下一个结点
} Node;
// 链表结构体
typedef struct {
Node* head;
} Linklist;
3.4优化
1:创建
用户使用LinkType忘记初始化,可以把结构体定义和初始化合二为一。
LinkType linklist_create();
2:随机访问元素
获取元素linklist_get(),只能获取到顺序表中的元素的副本,如果需要改变顺序表中的元素,可以提供如下函数。
LinkType* linklist_at(LinkList* plist,int index);
3:遍历
提供一个对顺序表的整体操作的接口。
typedef void (*LinkList_Traversal)(const LinkType* value);
void linklist_traverse(LinkList* plist,LinkList_Traversal fp);
4:获取链表大小
每次获取链表元素个数都要整个遍历一遍,时间复杂度为O(n)。在LinkList中添加成员int size;记录链表元素个数,时间复杂度降为O(1)。注意初始化、添加和删除元素函数都需要添加相应处理。
5:尾添加数据
每次尾添加数据都要整个遍历一遍,时间复杂度为O(n)。在LinkList中添加成员Node* tail;记录链表最后一个节点,时间复杂度降为O(1)。注意初始化、添加和删除元素函数都需要添加相应处理。
6:头节点
链表添加第一个节点和最后一个节点需要额外处理,添加一个额外的头节点可以简化处理。头指针出现改变的情况,链表添加第一个节点和最后一个节点与添加删除中间节点处理一致。
3.5链表的插入和删除
3.5.1插入
typedef struct node{
int coe;
int exp;
struct node *next;
}LNode,*LinkList;
LinkList Creat_LinkList1(){
LinkList H=(LinkList)malloc(sizeof(LNode));
H->next=NULL;
LNode *s=H;
LNode *r=H;
int coe,exp;
printf("请输入一元多项式的系数和指数 如果输入两个-1 就退出一元多项式的输入");
scanf("%d %d",&coe,&exp);
while(coe!=-1){
s=(LinkList)malloc(sizeof(LNode));
s->coe=coe;
s->exp=exp;
r->next=s;
r=s;
scanf("%d %d ",&coe,&exp);
}
r->next=NULL;
return H;
}
3.5.1开头删除
注意: 存在两种特殊情况需要处理
1: 空链表删除节点。此情况使用断言或者抛出异常。
2: 待删除节点的链表中只有一个节点删除后,需要把头指针和尾指针设置为空
静态链表
静态链表相当于用一个数组来实现线性表的链式存储结构,使用下标代替指针。主要被用于没有指针的计算机语言。FAT文件系统是使用静态链表实现的。
3.4其他链表
3.4.1循环链表
单链表有一个特点只能从头指针开始遍历整个链表,循环单链表可以从任意节点开始遍历整个链表。
3.4.1.1前端插入节点
3.4.1.4结尾插入节点
3.4.2双向链表
单链表在末尾删除节点时,需要获得删除节点前面的一个节点。这需要从队列开头一直遍历到结尾,导致效率瓶颈。双向链表很好的解决这个问题。
3.4.2.1前端插入节点
3.4.3.4结尾插入节点
注意: 存在两种特殊情况需要处理
1: 空链表删除节点。此情况使用断言或者抛出异常。
2: 待删除节点的链表中只有一个节点删除后,需要把头指针和尾指针设置为空
4栈
4.1意义:
栈是一种只能从表的一端存取数据且遵循 LIFO(先进后出)原则的线性存储结构。栈的开口端被称为栈顶,封口端被称为栈底。
4.2操作:
1:进栈:向栈中添加元素,此过程被称为"进栈"(入栈或压栈);
2:出栈:从栈中提取出指定元素,此过程被称为"出栈"(或弹栈);
4.3作用
栈一般用来处理逆序和回退相关的处理。
4.4实现
栈是操作受限制的线性表,根据不同的存储结构可分成顺序栈和链式栈。
1:在顺序栈中,可以将顺序表的有效长度作为栈顶指针,在顺序表的末尾删除和插入节点。
2:在链式栈中,可以将链表的头结点作为栈顶指针,入栈采用头插法
4.5定义结构
typedef int StackType; //存储单元类型
typedef struct stackNode {
StackType *element; //存储空间基地址
int size; //当前长度
int capacity; //当前分配的存储容量
}Stack;
定义操作
- 初始化栈
- 入栈
- 访问栈顶元素
- 出栈
#include<stdio.h>
typedef int SElemType;
typedef struct StackNode{
SElemType data;
struct StackNode *next;
}StackType,*LinkStackPtr;
typedef struct LinkStack{
LinkStackPtr top;
int count;
}LinkStack;
Status Push(LinkStack *S,SElemtype e){
LinkStackPtr s=(LinkStackPtr)malloc(sizeof(StackType));
s->data =e;
s->next=S->top;
S->top=s;
S->count++;
return OK;
}
Status Pop(LinkStack *S,SElemtype e){
LinkStackPtr p;
//if(Stack);
*e=S->top->data;
p=S->top;
S->top=S->top->next;
free(p);
S->count--;
return OK;
}
int main(){
}
5队列
5.1意义:
队列是一种只能从表的一端存数据另一端取数据且遵循FIFO(先进先出)原则的线性存储结构。
5.2作用
队列一般用来处理与**等待相关**的处理。
5.3实现
考虑到每次出队和入队都要移动队首和队尾指针。若采用**顺序存储**,将会有可能造成顺序表前段部分存储单元的浪费。虽说可以采用**循环队列**的方式复用存储单元,若遇到**队列满**的情况,将队列扩容比较麻烦。因此建议用链表的方式实现队列。
5.4定义结构
typedef int QueueType;
struct LinkNode{
QueueType key;
struct LinkNode *next;
};
typedef struct {
struct LinkNode *head;//队列的头指针
struct LinkNode *end;//队列的尾指针
}Queue;
5.6.定义操作
- 初始化栈队列
- 入队列
- 访问队列顶元素
- 出队列
链式存储
#include<stdio.h>
typedef int QElemType;
typedef struct QNode{
QElemType data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct{
QueuePtr front ,rear;
}LinkQueue;
LinkQueue Init_Qnode(){
LinkQueue *q=(LinkQueue *)malloc(sizeof(LinkQueue));
QNode *p=(QueuePtr)malloc(sizeof(QNode));
p->next=NULL;
q->front=q->rear=p;
return q;
}
int EnQueue(LinkQueue *Q,QElemType e){
QueuePtr s=(QueuePtr)malloc(sizeof(QNode));
if(!s){
return 0;
}
s->data=e;
s->next=NULL;
Q->rear->next=s;
Q->rear=s;
return 1;
}
Status DeQueue(LinkQueue *Q,QelemType *e){
QueuePtr p;
if(Q->front==Q->rear)
return 0;
p=Q->front->next;
*e=p->data;
Q->front->next=p->next;
if(Q->rear==p){
Q->rear=Q->front;
}
free(p);
return 1;
}
int Empty_LinkQueue(LinkQueue *q){
if(q->front==q->rear){
return 0;
}else{
return 1;
}
}
顺序存储
#include<stdio.h>
typedef int QElemType;
typedef struct {
QElemType data[5];
int front;
int rear;
}SqQueue;
Status InitQueue(SqQueue *Q){
Q->front=0;
Q->rear=0;
return OK;
}
int QueueLength(SqQueue Q){
return (Q.rear-Q.front+5)%5;
}
Status EnQueue(SqQueue *Q,QElemType e){
if((Q->rear+1)%5==Q->front){
return ERROR;
}
Q->data[Q->rear]=e;
Q->rear=(Q->rear+1)%s;
}
Status DeQueue(SqQueue *Q,QElemType *e){
if(Q->front==Q->rear){
return ERROR;
*e=Q->data[Q->front];
Q->front=(Q->front+1)%5;
return OK;
}
}