搜索到
40
篇与
的结果
-
逆向打印双链表 从右往左打印双链表#include <stdio.h> #include <stdlib.h> typedef int dataType; // 3.5 双链表 typedef struct dLinkNode { dataType data; struct dLinkNode *lLink,*rLink; }dNode,*dLinkList; // 1.初始化不带头结点的双链表 void init(dLinkList *head) { *head = NULL; } // 2.输出双链表各结点的值 void display(dLinkList head) { dNode *p = head; if(!p) { printf("双链表为空！\n"); return; } do{ printf("%d ",p->data); p = p->rLink; } while (p); printf("\n"); } // 4.在双链表尾部插入值为x的结点 void rearInsert(dLinkList *head, dataType x) { dNode *p = *head,*q; q = (dNode*) malloc(sizeof(dNode)); q->data = x; q->rLink = NULL; if(!p) // 链表为空时 { *head = q; q->lLink = NULL; } else { while (p->rLink) // 找到双链表的尾结点 p = p->rLink; p->rLink = q; q->lLink = p; } } // 3.8.10 从右往左打印双链表 void recursivePrint(dLinkList list) { if(!list) // 当双链表为空时防止出错 { printf("双链表为空！"); return; } if(list->rLink) recursivePrint(list->rLink); printf("%d ",list->data); } int main() { dLinkList list; // 声明指向双链表的头指针 init(&list); // 初始化双链表 for (int i = 1; i <= 5; i++) rearInsert(&list,i); // 插入结点 display(list); // 输出双链表 recursivePrint(list); return 0; } -
在双链表中插入结点 在双链表中值为y的结点前插入一个值为x的结点#include <stdio.h> #include <stdlib.h> typedef int dataType; // 3.5 双链表 typedef struct dLinkNode { dataType data; struct dLinkNode *lLink,*rLink; }dNode,*dLinkList; // 1.初始化不带头结点的双链表 void init(dLinkList *head) { *head = NULL; } // 2.输出双链表各结点的值 void display(dLinkList head) { dNode *p = head; if(!p) { printf("双链表为空！\n"); return; } do{ printf("%d ",p->data); p = p->rLink; } while (p); printf("\n"); } // 4.在双链表尾部插入值为x的结点 void rearInsert(dLinkList *head, dataType x) { dNode *p = *head,*q; q = (dNode*) malloc(sizeof(dNode)); q->data = x; q->rLink = NULL; if(!p) // 链表为空时 { *head = q; q->lLink = NULL; } else { while (p->rLink) // 找到双链表的尾结点 p = p->rLink; p->rLink = q; q->lLink = p; } } // 3.8.9 在双链表中值为y的结点前插入一个值为x的结点 void frontInsert(dLinkList *head, dataType y, dataType x) { dNode *p = *head,*q; // p为工作指针，q为新结点指针 if(!p) { printf("双链表为空，无法插入！\n"); return; } while (p && p->data != y) // 找到y结点 p = p->rLink; if(!p) { printf("没有这样的结点，无法插入！\n"); return; } q = (dNode*) malloc(sizeof(dNode)); q->data = x; if(p == *head) // 如果是头结点前插入 { p->lLink = q; q->rLink = *head; q->lLink = NULL; *head = q; // 更新头结点 } else { q->lLink = p->lLink; p->lLink->rLink = q; q->rLink = p; p->lLink = q; } } int main() { dLinkList list; // 声明指向双链表的头指针 init(&list); // 初始化双链表 for (int i = 1; i <= 5; i++) rearInsert(&list,i); // 插入结点 display(list); // 输出双链表 dataType y = 1,x = 8; printf("在双链表中值为%d的结点前插入一个值为%d的结点\n",y,x); frontInsert(&list,y,x); display(list); return 0; }
-
单链表删除所有值大于x而不大于y的结点 单链表删除所有值大于x而不大于y的结点#include <stdio.h> #include <stdlib.h> typedef int dataType; // 单链表 typedef struct linkNode { dataType data; struct linkNode *next; }node,*linkList; // 1.初始化不带头结点的单链表 void init(linkList *list) { *list = NULL; // 表示链表指针指向空处 } // 2.输出单链表元素 void display(linkList list) { node *p = list; // p为工作指针，初值为头指针 if(!p) { printf("链表为空！\n"); return; } else { while (p) { printf("%d ",p->data); p = p->next; } } printf("\n"); } // 3.在单链表尾部插入元素 void rearInsert(linkList *list, dataType x) { node *p = *list,*q; // p初值为当前链表指针指向的结点 q = (node*)malloc(sizeof(node)); // 创建新节点 q->data = x; q->next = NULL; // 新节点的指针域置空 if(!p) *list = q; // 如果当前链表为空 else { while (p->next) // 找到最后一个结点 p = p->next; p->next = q; } } // 3.8.8 删除所有值大于x而不大于y的结点 void del(linkList *list, dataType x, dataType y) { node *p = *list,*q,*pre; // p为工作指针，pre为前驱结点指针 if(!p) { printf("链表为空！\n"); return; } while (p) { if(p->data > y) // 有序链表，当值超过边界则退出循环 break; if(p->data > x && p->data <= y) { if(p == *list) // 如果要删除的是第一个结点 *list = p->next; else pre->next = p->next; q = p; p = p->next; free(q); // 释放空间 } else { pre = p; // 使前驱结点指针指向当前结点 p = p->next; // 向后遍历 } } } int main() { linkList list; // 声明一个指向链表的指针，即头指针 init(&list); // 初始化链表 for (int i = 1; i <= 10; i++) // 循环插入结点 rearInsert(&list,i); display(list); // 输出链表 dataType x = 2,y = 6; printf("删除所有值大于%d而不大于%d的结点\n",x,y); del(&list,x,y); display(list); // 输出链表 return 0; }
-
单链表原地逆置 单链表原地逆置#include <stdio.h> #include <stdlib.h> typedef int dataType; // 单链表 typedef struct linkNode { dataType data; struct linkNode *next; }node,*linkList; // 1.初始化不带头结点的单链表 void init(linkList *list) { *list = NULL; // 表示链表指针指向空处 } // 2.输出单链表元素 void display(linkList list) { node *p = list; // p为工作指针，初值为头指针 if(!p) { printf("链表为空！\n"); return; } while (p) { printf("%d ",p->data); p = p->next; } } // 3.根据用户输入构造单链表 void scanInsert(linkList *head) { node *p,*q; dataType x; printf("请输入(以9999作为结束标识)...\n"); scanf("%d",&x); while (x!=9999) { q = (node*) malloc(sizeof(node)); q->data = x; q->next = NULL; if(!*head) // 创建第一个结点时 { *head = q; p = *head; } else { p->next = q; p = p->next; } scanf("%d",&x); } } // 3.8.6 单链表原地逆置 void reverse(linkList *head) { node *p = *head, *s; *head = NULL; while (p) { s = p; p = p->next; s->next = *head; *head = s; } } // 3.8.6.1 带头结点的单链表原地逆置 void reverse1(linkList *head) { node *p = (*head)->next, *q; (*head)->next = NULL; while (p) // 依次取下结点插入头结点后面(关键步骤) { q = p; p = p->next; q->next = (*head)->next; (*head)->next = q; } } int main() { linkList list; init(&list); scanInsert(&list); reverse(&list); display(list); return 0; }
-
判断单链表是否有序 判断单链表是否有序#include <stdio.h> #include <stdlib.h> typedef int dataType; typedef struct linkNode { dataType data; struct linkNode *next; }node,*linkList; // 1.初始化不带头结点的单链表 void init(linkList *list) { *list = NULL; // 表示链表指针指向空处 } // 2.根据用户输入构造单链表 void scanInsert(linkList *head) { node *p,*q; dataType x; printf("请输入(以9999作为结束标识)...\n"); scanf("%d",&x); while (x!=9999) { q = (node*) malloc(sizeof(node)); q->data = x; q->next = NULL; if(!*head) // 创建第一个结点时 { *head = q; p = *head; } else { p->next = q; p = p->next; } scanf("%d",&x); } } // 3.8.5 判断单链表是否有序 int isOrder(linkList head) { node *p = head; if(!p || !p->next) // 链表为空或只有一个节点时默认有序 return 1; while (p->next) // 先找到第一个严格有序的 { if(p->data == p->next->data) p = p->next; else break; } if(!p->next || !p->next->next) // 链表只剩一个或两个节点时默认有序 return 1; if(p->data < p->next->data) // 链表增序 { while (p->next) { if(p->data > p->next->data) return 0; p = p->next; } } else // 链表降序 { while (p->next) { if(p->data < p->next->data) return 0; p = p->next; } } return 1; } int main() { linkList list; init(&list); scanInsert(&list); if(isOrder(list)) printf("链表有序！"); else printf("链表无序！"); return 0; }
