欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数据结构与算法--链表、栈、队列

程序员文章站 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;

定义操作

  1. 初始化栈
  2. 入栈
  3. 访问栈顶元素
  4. 出栈
#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.定义操作

  1. 初始化栈队列
  2. 入队列
  3. 访问队列顶元素
  4. 出队列

链式存储

#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;
	}
}
相关标签: 复习 数据结构