数据结构 day05

5. 队列

5.3. 链式队列

5.3.1. 特征

逻辑结构：线性结构
存储结构：链式存储
操作：创建、入列、出列、判空、清空

5.3.2. 代码实现

头文件：linkqueue.h

#ifndef __LINKQUEUE_H__
#define __LINKQUEUE_H__
typedef int datatype;
typedef struct node_t
{datatype data;struct node_t *next;
} linkqueue_node_t, *linkqueue_list_t;typedef struct // 将队列头指针和尾指针封装到一个结构体里
{linkqueue_list_t front; // 相当于队列的头指针linkqueue_list_t rear;  // 相当于队列的尾指针// 有了链表的头指针和尾指针，那么我们就可以操作这个链表
} linkqueue_t;
//1.创建一个空的队列，用有头链表。
linkqueue_t *createEmptyLinkQueue();
//2.入列 data代表入列的数据
int inLinkQueue(linkqueue_t *p, datatype data);
// 3. 出列
//思想：每次释放front所指节点，然后移动front到后一个节点返回当前节点数据
datatype outLinkQueue(linkqueue_t *p);
//4.判断队列是否为空
int isEmptyLinkQueue(linkqueue_t *p);
//5.求队列长度的函数
int lengthLinkQueue(linkqueue_t *p);
//6.清空队列
void clearLinkQueue(linkqueue_t *p);
#endif

1. 创建一个空的队列，用有头链表。

linkqueue_t *createEmptyLinkQueue();
{// 申请空间存放队列结构linkqueue_list_t q = (linkqueue_list_t)malloc(sizeof(linkqueue_node_t));if (q == NULL){printf("Space opening failure!!\n");return -1;}// 初始化q->next = NULL;// 申请空间存放头尾指针linkqueue_t *p = (linkqueue_t*) malloc(sizeof(linkqueue_t));if(p == NULL){printf("Space opening failure!!\n");free(q);return -1;}// 初始化p->front = q;p->rear = q;return p;
}

2. 入列

int inLinkQueue(linkqueue_t *p, datatype data);
{// 开辟空间存放新节点，定义指针pnew指向新节点linkqueue_list_t pnew = (linkqueue_list_t)malloc(sizeof(linkqueue_node_t));// 容错判断if(pnew == NULL){printf("Space opening failure!!\n");return -1;}// 新节点初始化pnew->data = data;pnew->next = NULL;// 链接新节点p->rear->next = pnew;// 尾指针移动p->rear = pnew;return 0；
}

3. 出列, 每次释放front所指下一个节点，然后移动front到后一个节点返回当前节点数据

datatype outLinkQueue(linkqueue_t *p);
{// 容错判断if(isEmptyLinkQueue(p)){printf("Linkqueue is empty!!\n");return -1;}// 定义指针pdel，指向被删除节点linkqueue_list_t pdel = p->front->next;// 定义变量，暂存出列数据datatype data = pdel->data;// 删除节点p->front->next = pdel->next;free(pdel);pdel = NULL;// 出列完成后，如果队列为空，那么召回rearif(p->front == NULL)p->rear = p->front;// 返回出列数据return data;
}

4. 判断队列是否为空

int isEmptyLinkQueue(linkqueue_t *p);
{// 以队列的特性呈现return p->rear == p->front;
}

也可以使用p->front->next == NULL;来作为判断队列为空的条件，但这是链表特性的内容，作为队列的操作内容，尽量以队列的特性呈现

5. 求队列长度的函数

int lengthLinkQueue(linkqueue_t *p);
{// 定义变量存放长度int len =0;// 定义头指针，头指针遍历链表linkqueue_list_t h = p->front;// 遍历链表while(h->next == NULL){h = h->next;len ++;}return len;
}

多定义一个头指针的原因：通过地址找到的front，所以对于front来说，相当于地址传递，所以改变front的指向会影响队头的值

6. 清空队列

void clearLinkQueue(linkqueue_t *p);
{while(!isEmptyLinkQueue(p))outLinkQueue(p);
}

6. 双向链表

6.1. 特性

逻辑特性：线性结构
存储结构：链式存储
操作：增删改查
创建：模仿链式队列的形式创建

6.2. 代码实现

头文件 doublelinklist.h

#ifndef __DOUBLELINKLIST_H__
#define __DOUBLELINKLIST_H__// 双向链表的节点定义typedef int datatype;
typedef struct node_t
{datatype data;        // 数据域struct node_t *next;  // 指向下一个节点的指针 next 先前的struct node_t *prior; // 指向前一个节点的指针 prior 下一个
} link_node_t, *link_node_p;// 将双向链表的头指针和尾指针封装到一个结构体里
// 思想上有点像学的链式队列
typedef struct doublelinklist
{link_node_p head; // 指向双向链表的头指针link_node_p tail; // 指向双向链表的尾指针int len;          // 用来保存当前双向链表的长度
} double_list_t, *double_list_p;//1.创建一个空的双向链表
double_list_p createEmptyDoubleLinkList();
// 2.向双向链表的指定位置插入数据 post位置， data数据
int insertIntoDoubleLinkList(double_list_p p, int post, datatype data);
// 3.遍历双向链表
void showDoubleLinkList(double_list_p p);
// 4.判断双向链表是否为空
int isEmptyDoubleLinkList(double_list_p p);
// 5.删除双向链表指定位置数据
int deletePostDoubleLinkList(double_list_p p, int post);
//6.求双向链表的长度
int lengthDoubleLinkList(double_list_p p);
//7.查找指定数据出现的位置 data被查找的数据
int searchPostDoubleLinkList(double_list_p p,datatype data);
//8.修改指定位置的数据,post修改的位置 data被修改的数据
int changeDataDoubleLinkList(double_list_p p,int post, datatype data)
// 9.删除双向链表中的指定数据 data代表删除所有出现的data数据
void deleteDataDoubleLinkList(double_list_p p, datatype data)；
#endif

1. 创建一个空的双向链表

double_list_p createEmptyDoubleLinkList()
{// 申请空间存放头尾指针double_list_p p = (double_list_p)malloc(sizeof(double_list_t));if (p == NULL){printf("Space opening failure!!\n");return NULL;}// 申请空间存放头节点link_node_p ph = (link_node_p)malloc(sizeof(link_node_t));if (ph == NULL){printf("Space opening failure!!\n");free(p);p = NULL;return NULL;}// 头尾指针初始化，头节点初始化p->head = ph;p->tail = ph;p->len = 0;ph->next = NULL;ph->prior = NULL;return p;
}

2. 向双向链表的指定位置插入数据 post位置， data数据

int insertIntoDoubleLinkList(double_list_p p, int post, datatype data)
{// 容错判断if (post < 0 || post > p->len){printf("post is err!!\n");return -1;}// 定义temp暂存head或taillink_node_p temp = NULL;// 定义pnew指向被插入节点link_node_p pnew = (link_node_p)malloc(sizeof(link_node_t));// 初始化pnew->data = data;pnew->prior = NULL;pnew->next = NULL;// 判断插入位置在前半段还是后半段if (post < p->len / 2){temp = p->head;for (int i = 0; i < post; i++)temp = temp->next;}else{temp = p->tail;for (int i = p->len - 1; i > post; i--)temp = temp->prior;}// 建立链接pnew->next = temp->next;pnew->prior = temp;temp->next = pnew;if (post == p->len)// 尾指针移动p->tail = pnew;elsepnew->next->prior = pnew;// 长度+1p->len++;
}

3. 遍历双向链表

void showDoubleLinkList(double_list_p p)
{// 定义h，代替head移动遍历link_node_p temp = NULL;printf("正向遍历：");temp = p->head;while (temp->next != NULL){temp = temp->next;printf("%-4d", temp->data);}printf("\n");printf("反向遍历：");temp = p->tail;while (temp != p->head){printf("%-4d", temp->data);temp = temp->prior;}printf("\n");
}

4. 判断双向链表是否为空

int isEmptyDoubleLinkList(double_list_p p)
{return p->len == 0;
}

5. 删除双向链表指定位置数据

int deletePostDoubleLinkList(double_list_p p, int post)
{// 容错判断if (isEmptyDoubleLinkList(p) || post < 0 || post > p->len - 1){printf("deletePostDoubleLinkList err");return -1;}// 定义一个pdel指向被删除节点link_node_p pdel = NULL;// 判断前半段还是后半段if (post < p->len / 2){pdel = p->head;for (int i = 0; i <= post; i++)pdel = pdel->next;}else{pdel = p->tail;for (int i = p->len - 1; i >= post; i--)pdel = pdel->prior;}// 删除操作pdel->prior->next = pdel->next;if (pdel->next == NULL)p->tail = pdel->prior;elsepdel->next->prior = pdel->prior;return 0;
}

6. 求双向链表的长度

int lengthDoubleLinkList(double_list_p p)
{return p->len;
}

7. 查找指定数据出现的位置 data被查找的数据

// 7.查找指定数据出现的位置 data被查找的数据
int searchPostDoubleLinkList(double_list_p p, datatype data)
{// 定义temp指向头指针，代替头指针移动link_node_p temp = p->head;// 定义变量post，保存位置int post = 0;while (temp->next == NULL){temp = temp->next;if (temp->data == data)return post;post++;}return -1;
}

8. 修改指定位置的数据,post修改的位置 data被修改的数据

int changeDataDoubleLinkList(double_list_p p,int post, datatype data)
{// 容错判断if (isEmptyDoubleLinkList(p) || post < 0 || post > p->len - 1){printf("changeDataDoubleLinkList err");return -1;}// 定义一个temp，代替头尾指针移动link_node_p temp = NULL;if (post < p->len / 2){temp = p->head;for (int i = 0; i <= post; i++)temp = temp->next;}else{temp = p->tail;for (int i = p->len - 1; i >= post; i--)temp = temp->prior;}// 修改数据temp->data = data;return 0;
}

9. 删除双向链表中的指定数据 data代表删除所有出现的data数据

void deleteDataDoubleLinkList(double_list_p p, datatype data)
{// 定义pdel遍历，暂存被删除节点link_node_p pdel = p->head->next;// 遍历链表，直到pdel指向最后一个节点时停止while (pdel == p->tail){if (pdel->data == data){pdel->prior->next = pdel->next;pdel = pdel->prior;free(pdel->next->prior);pdel->next->prior = pdel;p->len--;}pdel = pdel->next;}// 判断最后一个节点数据是否匹配，匹配删除，不匹配就结束遍历if (pdel->data == data){p->len--;p->tail = pdel->prior;p->tail->next = NULL;free(pdel);}pdel = NULL;
}

从头节点后节点开始用指针pdel遍历，相当于遍历无头链表，遇到需要删除节点的就用pdel指向它然后删除，如果不需要删除则pdel继续往后走一个节点。