青海教育厅门户网站,摄影工作室建设,口碑优化seo,网站建设基本流程视频目录
栈
栈概念
顺序栈
链式栈#xff08;链表实现#xff09;
顺序栈和链式栈的区别是什么#xff1f;
队列
队列概念
顺序队列
链式队列
双向链表 栈
栈概念
什么是栈#xff1f;
只能在一端进行插入和删除数据的线性表(称为栈)#xff0c;把能进行插入和删…目录
栈
栈概念
顺序栈
链式栈链表实现
顺序栈和链式栈的区别是什么
队列
队列概念
顺序队列
链式队列
双向链表 栈
栈概念
什么是栈
只能在一端进行插入和删除数据的线性表(称为栈)把能进行插入和删除的这一端叫栈顶另一端成为栈底。实现栈可以用顺序表实现(顺序栈)也可以用链表实现(链式栈)。
栈的特点
先进后出first in last out FILO
后进先出last in first out LIFO
顺序栈
逻辑结构线性结构存储结构顺序存储定义一个结构体描述顺序栈的信息
typedef int datatype_t;
typedef struct
{datatypde_t *data; //保存栈的地址(数组)int top; //保存栈顶数据的下标int len; //栈的大小
}seqstack_t,*seqstack_p;
栈的常用操作
#include stdio.h
#include stdlib.htypedef int datatype_t;
typedef struct {datatype_t *data; // 保存栈的地址(数组)int top; // 保存栈顶数据的下标int len; // 栈的大小
} seqstack_t, *seqstack_p;// 1. 创建一个空栈
seqstack_p createStack(int size) {seqstack_p stack (seqstack_p)malloc(sizeof(seqstack_t));if (stack NULL) {printf(Failed to allocate memory for stack.\n);return NULL;}stack-data (datatype_t*)malloc(size * sizeof(datatype_t));if (stack-data NULL) {printf(Failed to allocate memory for stack data.\n);free(stack);return NULL;}stack-top -1;stack-len size;return stack;
}// 2. 入栈
int push(seqstack_p stack, datatype_t value) {if (stack-top stack-len - 1) {printf(Stack is full. Cannot push %d.\n, value);return 0;}stack-top;stack-data[stack-top] value;return 1;
}// 3. 判断栈是否满
int isFull(seqstack_p stack) {return stack-top stack-len - 1;
}// 4. 出栈
int pop(seqstack_p stack, datatype_t *value) {if (stack-top -1) {printf(Stack is empty. Cannot pop.\n);return 0;}*value stack-data[stack-top];stack-top--;return 1;
}// 5. 判断栈是否为空
int isEmpty(seqstack_p stack) {return stack-top -1;
}// 6. 求栈的长度
int stackLength(seqstack_p stack) {return stack-top 1;
}// 7. 获取栈顶的值
int getTop(seqstack_p stack, datatype_t *value) {if (stack-top -1) {printf(Stack is empty. Cannot get top value.\n);return 0;}*value stack-data[stack-top];return 1;
}int main() {int size 5;seqstack_p stack createStack(size);if (stack NULL) {return 1;}push(stack, 1);push(stack, 2);push(stack, 3);int topValue;if (getTop(stack, topValue)) {printf(Top value: %d\n, topValue);}printf(Stack length: %d\n, stackLength(stack));while (!isEmpty(stack)) {int value;pop(stack, value);printf(Pop value: %d\n, value);}free(stack-data);free(stack);return 0;
}
链式栈链表实现
逻辑结构线性结构存储结构链式存储定义节点结构
typedef int datatype_t;
typedef struct node_t
{datatype_t data; //数据struct node_t *next; //节点
}linkstack_t,*linkstack_p;
链式栈的操作
#include stdio.h
#include stdlib.htypedef int datatype_t;
typedef struct node_t {datatype_t data;struct node_t* next;
} linkstack_t, *linkstack_p;// 1. 创建一个空的栈
linkstack_p createStack() {linkstack_p stack (linkstack_p)malloc(sizeof(linkstack_t));if (stack NULL) {printf(Failed to allocate memory for stack.\n);return NULL;}stack-next NULL;return stack;
}// 2. 入栈
void push(linkstack_p stack, datatype_t value) {linkstack_p newNode (linkstack_p)malloc(sizeof(linkstack_t));if (newNode NULL) {printf(Failed to allocate memory for new node.\n);return;}newNode-data value;newNode-next stack-next;stack-next newNode;
}// 3. 判断栈是否为空
int isEmpty(linkstack_p stack) {return stack-next NULL;
}// 4. 出栈
datatype_t pop(linkstack_p stack) {if (isEmpty(stack)) {printf(Stack is empty. Cannot pop.\n);return NULL;}linkstack_p temp stack-next;datatype_t value temp-data;stack-next temp-next;free(temp);return value;
}// 5. 清空栈
void clearStack(linkstack_p stack) {while (!isEmpty(stack)) {pop(stack);}
}// 6. 求栈的长度
int stackLength(linkstack_p stack) {int count 0;linkstack_p p stack-next;while (p ! NULL) {count;p p-next;}return count;
}// 7. 获取栈顶的值
datatype_t getTop(linkstack_p stack) {if (isEmpty(stack)) {printf(Stack is empty. Cannot get top value.\n);return NULL;}return stack-next-data;
}int main() {linkstack_p stack createStack();push(stack, 1);push(stack, 2);push(stack, 3);printf(Stack length: %d\n, stackLength(stack));datatype_t topValue getTop(stack);printf(Top value: %d\n, topValue);while (!isEmpty(stack)) {datatype_t value pop(stack);printf(Pop value: %d\n, value);}clearStack(stack);free(stack);return 0;
}
顺序栈和链式栈的区别是什么
1顺序栈的存储结构是顺序存储链式栈的存储结构是链式存储
2顺序栈的长度受限制而链栈不会
队列
队列概念
什么是队列
只允许在两端进行插入和删除操作的线性表在队尾插入插入数据的这一端被称为队尾删除的一端被称为队头。实现队列的方式有两种顺序队列 链式队列
队列特点
先进先出、后进后出 FIFO LILO
顺序队列
逻辑结构线性结构存储结构顺序结构定义顺序队列的结构体
#define N 6
typedef int datatype_t;
typedef struct
{datatype_t data[N];//顺序表定义的队int front; //队头下标int rear; //队尾下标
}sequeue_t;
顺序队列基础操作
#include stdio.h
#include stdlib.h#define N 6
typedef int datatype_t;
typedef struct {datatype_t data[N]; // 顺序表定义的队int front; // 队头下标int rear; // 队尾下标
} sequeue_t;// 1. 创建一个空的顺序队列
sequeue_t* createQueue() {sequeue_t* queue (sequeue_t*)malloc(sizeof(sequeue_t));if (queue NULL) {printf(Failed to allocate memory for queue.\n);return NULL;}queue-front 0;queue-rear 0;return queue;
}// 2. 入队
void enqueue(sequeue_t* queue, datatype_t value) {if ((queue-rear 1) % N queue-front) { printf(Queue is full. Cannot enqueue.\n);return;}queue-data[queue-rear] value;queue-rear (queue-rear 1) % N;
}// 3. 判断队列是否满
int isFull(sequeue_t* queue) {return (queue-rear 1) % N queue-front;
}// 4. 出队
datatype_t dequeue(sequeue_t* queue) {if (queue-front queue-rear) {printf(Queue is empty. Cannot dequeue.\n);return NULL;}datatype_t value queue-data[queue-front];queue-front (queue-front 1) % N;return value;
}// 5. 判断队列是否为空
int isEmpty(sequeue_t* queue) {return queue-front queue-rear;
}// 6. 计算队列的长度
int queueLength(sequeue_t* queue) {return (queue-rear - queue-front N) % N;
}// 7. 清空队列
void clearQueue(sequeue_t* queue) {queue-front queue-rear;
}int main() {sequeue_t* queue createQueue();enqueue(queue, 1);enqueue(queue, 2);enqueue(queue, 3);printf(Queue length: %d\n, queueLength(queue));while (!isEmpty(queue)) {datatype_t value dequeue(queue);printf(Dequeued value: %d\n, value);}if (isEmpty(queue)) {printf(Queue is empty.\n);}clearQueue(queue);free(queue);return 0;
}
链式队列
逻辑结构线性结构存储结构链式存储定义节点结构体
typedef int datatype;
typedef struct node_t
{datatype data; //数据域struct node_t *next;
}link_t;//保存头尾节点地址结构体
typedef struct
{link_t *front; //头指针link_t *rear; //尾指针int len; //保存队列的长度(个数)
}queue_t;
链式队列的操作
#include stdio.h
#include stdlib.htypedef int datatype;typedef struct node_t {datatype data; // 数据域struct node_t *next; // 指向下一个节点的指针
} link_t;typedef struct {link_t *front; // 头指针link_t *rear; // 尾指针int len; // 队列长度
} queue_t;// 创建空队列
void createQueue(queue_t *queue) {queue-front NULL;queue-rear NULL;queue-len 0;
}// 入队
void enqueue(queue_t *queue, datatype data) {link_t *newNode (link_t*)malloc(sizeof(link_t));newNode-data data;newNode-next NULL;if (queue-rear NULL) {queue-front newNode;queue-rear newNode;} else {queue-rear-next newNode;queue-rear newNode;}queue-len;
}// 出队
datatype dequeue(queue_t *queue) {if (queue-front NULL) {printf(Queue is empty.\n);return -1; // 用-1表示队列为空的情况}link_t *temp queue-front;datatype data temp-data;queue-front queue-front-next;free(temp);if (queue-front NULL) {queue-rear NULL;}queue-len--;return data;
}// 判断队列是否为空
int isQueueEmpty(queue_t *queue) {return (queue-front NULL);
}// 清空队列
void clearQueue(queue_t *queue) {while (queue-front ! NULL) {link_t *temp queue-front;queue-front queue-front-next;free(temp);}queue-rear NULL;queue-len 0;
}// 计算队列的长度
int getQueueLength(queue_t *queue) {return queue-len;
}int main() {queue_t queue;createQueue(queue);// 测试入队enqueue(queue, 10);enqueue(queue, 20);enqueue(queue, 30);// 测试出队printf(Dequeued element: %d\n, dequeue(queue));// 测试判断队列是否为空if (isQueueEmpty(queue)) {printf(Queue is empty.\n);} else {printf(Queue is not empty.\n);}// 测试清空队列clearQueue(queue);// 测试计算队列的长度printf(Queue length: %d\n, getQueueLength(queue));return 0;
}
双向链表
逻辑结构线性结构存储结构链式存储保存数据的结构体
typede int datatype;typedef struct node_t
{datatype data; //数据域struct node_t *prior; //保存前一个节点的地址struct node_t *next; //保存后一个节点地址
}link_t;//用于保存双向链表信息的结构体
typedef struct
{link_t *head; //保存头节点地址link_t *tail //保存尾节点的地址int len; //保存双向链表的长度
}double_t;
双向链表的操作
#include stdio.h
#include stdlib.htypedef int datatype;typedef struct node_t {datatype data; // 数据域struct node_t *prior; // 前一个节点的指针struct node_t *next; // 后一个节点的指针
} link_t;typedef struct {link_t *head; // 头节点的指针link_t *tail; // 尾节点的指针int len; // 双向链表的长度
} double_t;// 创建一个空的双向链表
void createDoubleList(double_t *list) {list-head NULL;list-tail NULL;list-len 0;
}// 向双向链表的指定位置插入数据
void insertData(double_t *list, int pos, datatype data) {if (pos 0 || pos list-len) {printf(Invalid position.\n);return;}link_t *newNode (link_t*)malloc(sizeof(link_t));newNode-data data;if (pos 0) {newNode-prior NULL;newNode-next list-head;if (list-head ! NULL) {list-head-prior newNode;}list-head newNode;if (list-tail NULL) {list-tail newNode;}} else if (pos list-len) {newNode-prior list-tail;newNode-next NULL;if (list-tail ! NULL) {list-tail-next newNode;}list-tail newNode;} else {link_t *current list-head;int i 0;while (i pos) {current current-next;i;}newNode-prior current-prior;newNode-next current;current-prior-next newNode;current-prior newNode;}list-len;
}// 遍历双向链表
void traverseList(double_t *list) {link_t *current list-head;while (current ! NULL) {printf(%d , current-data);current current-next;}printf(\n);
}// 删除双向链表指定位置的数据
void deleteData(double_t *list, int pos) {if (pos 0 || pos list-len) {printf(Invalid position.\n);return;}link_t *current list-head;if (pos 0) {list-head current-next;if (list-head ! NULL) {list-head-prior NULL;}if (list-tail current) {list-tail NULL;}} else if (pos list-len - 1) {current list-tail;list-tail current-prior;list-tail-next NULL;} else {int i 0;while (i pos) {current current-next;i;}current-prior-next current-next;current-next-prior current-prior;}free(current);list-len--;
}// 判断双向链表是否为空
int isDoubleListEmpty(double_t *list) {return (list-head NULL);
}// 求双向链表的长度
int getDoubleListLength(double_t *list) {return list-len;
}// 查找指定数据出现的位置
int findDataPosition(double_t *list, datatype data) {link_t *current list-head;int pos 0;while (current ! NULL) {if (current-data data) {return pos;}current current-next;pos;}return -1; // 表示未找到数据
}// 修改指定位置的数据
void modifyData(double_t *list, int pos, datatype newData) {if (pos 0 || pos list-len) {printf(Invalid position.\n);return;}link_t *current list-head;int i 0;while (i pos) {current current-next;i;}current-data newData;
}// 删除双向链表中的指定数据
void deleteDataByValue(double_t *list, datatype data) {int pos findDataPosition(list, data);if (pos ! -1) {deleteData(list, pos);} else {printf(Data not found.\n);}
}// 转置双向链表
void reverseList(double_t *list) {if (list-len 1) {return;}link_t *current list-head;link_t *temp NULL;while (current ! NULL) {temp current-prior;current-prior current-next;current-next temp;current current-prior;}temp list-head;list-head list-tail;list-tail temp;
}int main() {double_t list;createDoubleList(list);// 测试向双向链表的指定位置插入数据insertData(list, 0, 10);insertData(list, 1, 20);insertData(list, 2, 30);// 测试遍历双向链表traverseList(list);// 测试删除双向链表指定位置的数据deleteData(list, 1);// 测试判断双向链表是否为空if (isDoubleListEmpty(list)) {printf(Double linked list is empty.\n);} else {printf(Double linked list is not empty.\n);}// 测试求双向链表的长度printf(Double linked list length: %d\n, getDoubleListLength(list));// 测试查找指定数据出现的位置int pos findDataPosition(list, 20);if (pos ! -1) {printf(Data found at position: %d\n, pos);} else {printf(Data not found.\n);}// 测试修改指定位置的数据modifyData(list, 0, 50);// 测试删除双向链表中的指定数据deleteDataByValue(list, 30);// 测试转置双向链表reverseList(list);// 再次遍历双向链表traverseList(list);return 0;
}
