当前位置： 首页 > ds >正文

单向链表、双向链表、栈、队列复习（7.14）

ds 2025/7/15 12:57:56

前瞻简介

1、数据结构：相互之间存在一种或多种特定关系的数据元素的集合。

逻辑结构：
集合，所有数据在同一个集合中，关系平等。
线性，数据和数据之间是一对一的关系
树， 一对多
图，多对多

物理结构(在内存当中的存储关系)
顺序存储，数据存放在连续的存储单位中。逻辑关系和物理关系一致。需预先分配空间，大小固定。插入删除需移动大量数据。可以通过下标直接访问指定数据
链式，数据存放的存储单位是随机或任意的，可以连续也可以不连续。不需要预先分配，大学可变，动态分配。新节点插入删除容易。访问数据需要整体遍历

2、栈是限定仅在表尾进行插入和删除操作的线性表。
先进后出
栈顶:允许操作的一端        栈底:不允许操作的一端

3、队列是只允许在一段进行插入，而在另一端进行删除操作的线性表。                                                  先进先出，FIFO
允许插入的称谓队尾，允许删除的一端队头。
入队                                出队

1、单向链表

新节点大小就是数据加指针的总字节数，通过malloc申请，所以地址随机。删除节点需要通过free函数释放申请的空间。节点插入就是让新节点的下一个先指向前一个的下一个，然后前一个的下一个指向新节点。

jlinklist.c

#include"head.h"Node* create_link()
{Node* temp = malloc(sizeof(Node));if(NULL == temp){perror("create_link malloc head");exit(1);}bzero(temp,sizeof(Node));temp->next=NULL;return temp;}int is_empty(Node* list)
{if(list->next==NULL)return 1;else return 0;
}int inset_link(Node*list,DATATYPE data)
{Node*temp =malloc(sizeof(Node));if(NULL == temp){perror("malloc new node");exit(1);}temp->data =data;temp->next = NULL;temp->next = list->next;list->next = temp;}
void show(Node*list)
{Node* temp = list->next;while(temp){printf("姓名：%s\t性别：%s\t年龄：%s\t能力：%s\n",temp->data.name,temp->data.sex,temp->data.age,temp->data.score);temp=temp->next;}
}int insert_tail_link(Node* list, DATATYPE data)
{Node* p = list->next;Node* new_node = malloc(sizeof(Node));if(NULL == new_node){perror("malloc now node tail insert");exit(1);}new_node->data =data;new_node->next =NULL;if(NULL == p){list->next = new_node;}else{while(p->next){p=p->next;}p->next =  new_node;}}Node* find_list(Node*list,char* name)
{if(is_empty(list)){printf("链表是空的，\n");return NULL;}Node* p = list->next;while(p){if(strcmp(p->data.name,name)==0){return p;}p=p->next;}return NULL;}int modify_list(Node*list, char* name ,DATATYPE data)
{Node* temp = find_list(list,name);if(NULL == temp){printf("修改出错\n");return -1;}temp->data = data;return 0;
}int delete_list(Node*list,char* name)
{if(is_empty(list)){printf("表空\n");return -1;}Node* p=list;Node* q = list;while(p){p=p->next;if(strcmp(p->data.name,name)==0){q->next = p->next;free(p);return 0;}q= p;}return -1;}
int destroy_list(Node*list)
{Node* temp = list->next;while(temp){list->next= temp->next;free(temp);temp= list->next;}free(list);
}

head.h

#ifndef  _LINKLIST_H_
#define _LINKLIST_H_typedef struct 
{char name[10];char sex;int age;int socre;
}DATATYPE;typedef struct _node_
{DATATYPE data;struct _node_ *next;
}LinkNode;typedef struct  
{LinkNode* head;int clen;
}LinkList;extern LinkList*CreateLinkList();
extern int InsertHeadLinkList(LinkList*ll,DATATYPE*data);
extern int InsertTailLinkList(LinkList*ll,DATATYPE*data);
extern int InsertPosLinkList(LinkList*ll,DATATYPE*data,int pos);extern int IsEmptyLinkList(LinkList*ll);
extern int GetSizeLinkList(LinkList*ll);
extern int ShowLinkList(LinkList*ll);
extern DATATYPE* FindLinkList(LinkList*ll,char*name);
extern int ModifyLinkList(LinkList*ll,char*name,DATATYPE*data);
extern int DeleteLinkList(LinkList*ll,char*name);
extern int DestroyLinkList(LinkList**ll);extern LinkNode* FindMidLinkList(LinkList*ll);
extern LinkNode* FindLastKLinkList(LinkList*ll,int k);
extern int RevertLinkList(LinkList*ll);
extern int InsertSortLinkList(LinkList*ll);
extern int IsRingLinkList(LinkList*ll);#endif

2、双向链表

节点大小为前指针、后指针和数据的总字节数。第一个节点前指针指向空，最后一个节点后指针指向空。

doulink.c

#include"head.h"Node* create_link()
{Node* temp = malloc(sizeof(Node));if(NULL == temp){perror("create_link malloc head");exit(1);}bzero(temp,sizeof(Node));temp->next=NULL;temp->prev=NULL;return temp;}int is_empty(Node* list)
{if(list->next==NULL)return 1;else return 0;
}int inset_link(Node*list,DATATYPE data)
{Node*temp =malloc(sizeof(Node));if(NULL == temp){perror("malloc new node");exit(1);}temp->data =data;temp->next = NULL;temp->prev =  NULL;temp->next = list->next;temp->prev = list;list->next = temp;if(temp->next)temp->next->prev = temp;}
void show(Node*list)
{Node* temp = list->next;while(temp){printf("姓名：%s\t性别：%s\t年龄：%s\t能力：%s\n",temp->data.name,temp->data.sex,temp->data.age,temp->data.score);temp=temp->next;}
}int insert_tail_link(Node* list, DATATYPE data)
{Node* p = list;Node* new_node = malloc(sizeof(Node));if(NULL == new_node){perror("malloc now node tail insert");exit(1);}new_node->data =data;new_node->next =NULL;new_node->prev =NULL;while(p->next){p=p->next;}new_node->prev = p;p->next = new_node;}Node* find_list(Node*list,char* name)
{if(is_empty(list)){printf("链表是空的，\n");return NULL;}Node* p = list->next;while(p){if(strcmp(p->data.name,name)==0){return p;}p=p->next;}return NULL;}int modify_list(Node*list, char* name ,DATATYPE data)
{Node* temp = find_list(list,name);if(NULL == temp){printf("修改出错\n");return -1;}temp->data = data;return 0;
}int delete_list(Node*list,char* name)
{if(is_empty(list)){printf("表空\n");return -1;}Node* temp= find_list(list,name);if(temp){temp->prev->next = temp->next;if(temp->next)temp->next->prev = temp->prev;free(temp);}return -1;}
int destroy_list(Node*list)
{Node* temp = list->next;while(temp){list->next= temp->next;free(temp);temp= list->next;}free(list);
}

head.h

#ifndef __HEAD_H__
#define __HEAD_H__
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct person {char name[32];char sex[10];char age[10];char score[10];
}DATATYPE;typedef struct node {struct node *prev;DATATYPE data;struct node *next;
}Node;Node *create_link();
int is_full(Node*list);
int is_empty(Node* list);
int inset_link(Node*list,DATATYPE data);
void show(Node*list);
int insert_tail_link(Node* list, DATATYPE data);
Node* find_list(Node*list,char* name);
#endif

3、链式栈

linkstack.c

#include"head.h"Node* create_stack()
{Node *temp=malloc(sizeof(Node));if(NULL == temp){perror("malloc create_stack");exit(1);}bzero(temp,sizeof(Node));temp->next=NULL;return temp;}int is_empty(Node* list)
{if(NULL ==list->next )return  1;elsereturn 0;
}
int push_stack(Node* list,DATATYPE data)
{Node* temp = malloc(sizeof(Node));if(NULL == temp){perror("node malloc");exit(1);}temp->data = data;temp->next = NULL;temp->next =  list->next;list->next = temp;return 0;
}DATATYPE pop_stack(Node*list)
{DATATYPE data={0};if(is_empty(list)){printf("Stack 已经空了\n");return data;}Node* temp = list->next;list->next = temp->next;data = temp->data;free(temp);return data;}int destroy_stack(Node* list)
{Node* temp = list->next;while(temp){list->next= temp->next;free(temp);}free(list);}Node* get_top(Node*list)
{Node* temp = list->next;return temp;
}

head.h

#ifndef __HEAD_H__
#define __HEAD_H__
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct person {char name[32];char sex[10];char age[10];char score[10];
}DATATYPE;typedef struct __NODE__
{DATATYPE data;struct __NODE__* next;}Node;/*typedef struct __stack__
{Node* head;int tlen;int top;
}Stack;*/
Node* create_stack();
int is_full(Node* list);
int is_empty(Node* list);
int push_stack(Node* list,DATATYPE data);
DATATYPE pop_stack(Node*list);
int destroy_stack(Node* list);
Node* get_top(Node*list);
#endif

4、链式队列

seqque.c

#include"head.h"LinkQueue* create_queue(int n)
{LinkQueue* que = malloc(sizeof(LinkQueue));if(NULL == que){perror("malloc que");exit(1);}bzero(que,sizeof(LinkQueue));que->blank = malloc(sizeof(Node));if(NULL == que->blank){perror("blank malloc");exit(1);}que->head = NULL;que->tail =NULL;que->tlen = n;que->clen = 0;return que;}
int is_full(LinkQueue* list)
{return list->tlen == list->clen;
}
int is_emptp(LinkQueue* list)
{return list->clen == 0; 
}
int enter_queue(LinkQueue* list,DATATYPE ddd)
{if(is_full(list)){printf("队列已经满了\n");return -1;}Node* temp = malloc(sizeof(Node));if(NULL == temp){perror("malloc new node");exit(1);}bzero(temp,sizeof(Node));temp->data = ddd;temp->next= NULL;if(list->tail)list->tail->next = temp;else{list->head = temp;}list->tail = temp;list->clen++;return 0;}
DATATYPE quie_queue(LinkQueue* list)
{DATATYPE ddd; // bzero(&ddd,sizeof(ddd));if(is_emptp(list)){printf("队列已经空了\n");return ddd;}list->blank->next = list->head->next;ddd = list->head->data;free(list->head);list->head = list->blank->next;return ddd;}void destroy_queue(LinkQueue* list)
{while(list->head){list->blank->next = list->head->next;free(list->head);list->head = list->blank->next;}free(list->blank);free(list);
}

head.h

#ifndef __HEAD_H__
#define __HEAD_H__
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct  
{char name[50];char sex[10];char age[10];char addr[50];
}DATATYPE;
typedef struct __NODE__
{DATATYPE data;struct __NODE__ *next;
}Node;
typedef struct __queue__ {Node * blank;Node* head;Node* tail;int tlen;int clen;}LinkQueue;LinkQueue* create_queue(int n);
int is_full(LinkQueue* list);
int is_emptp(LinkQueue* list);
int enter_queue(LinkQueue* list,DATATYPE ddd);
DATATYPE quie_queue(LinkQueue* list);
void destroy_queue(LinkQueue* list);#endif

http://www.xdnf.cn/news/15555.html

相关文章：

  • LSV负载均衡
  • Usage of standard library is restricted (arkts-limited-stdlib) ＜ArkTSCheck＞
  • 防火墙技术概述
  • Java行为型模式---模板方法模式
  • 【html基本界面】
  • 【视频格式转换】.264格式转为mp4格式
  • 7.15 窗口函数 | 二分 | 位运算
  • 互斥锁与同步锁
  • SAP-ABAP：SAP库存管理核心增强：IF_EX_MB_DOCUMENT_BADI 深度解析
  • AI驱动编程范式革命：传统开发与智能开发的全维度对比分析
  • 【人工智能】通过 Dify 构建聊天助手
  • 【t检验】用奶茶店排队案例解释
  • LangChain 和 Dify 是什么
  • 基于51单片机的贪吃蛇游戏Protues仿真设计
  • 数据分类分级和重要数据标准解读
  • 文献查找任务及其方法
  • 当前（2024-07-14）视频插帧（VFI）方向的 SOTA 基本被三篇顶会工作占据，按“精度-速度-感知质量”三条线总结如下，供你快速定位最新范式
  • 计算机毕业设计Java轩辕购物商城管理系统 基于 SpringBoot 的轩辕电商商城管理系统 Java 轩辕购物平台管理系统设计与实现
  • 如何解决pip安装报错ModuleNotFoundError: No module named ‘collections’问题
  • 来时路,零帧起手到Oracle大师
  • 大模型安全建设：破误区、识风险、筑防线20250714
  • 体验RAG GitHub/wow-rag
  • HTML 文本格式化标签
  • Redis7持久化
  • TextIn：大学生的文档全能助手，让学习效率飙升
  • 【JAVA】监听windows中鼠标侧面键的按钮按下事件
  • React之旅-06 Ref
  • 波兰无人机具身导航基准测试与最新进展！FlySearch：探索视觉语言模型的探索能力
  • python学智能算法（十八）|SVM基础概念-向量点积
  • 深入了解linux系统—— 进程信号的产生