搜索到
57
篇与
的结果
-
单链表按奇、偶数拆分 单链表按奇、偶数拆分将一个结点值为自然数的单链表拆分成两个单链表，原表为偶数结点值为奇数的结点按原表相对次序组成新链表#include <stdio.h> #include <stdlib.h> typedef int dataType; typedef struct linkNode { dataType data; struct linkNode *next; }node,*linkList; // 1.初始化不带头结点的单链表 void init(linkList *head) { *head = 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.7 将一个结点值为自然数的单链表拆分成两个单链表，原表为偶数结点 // 值为奇数的结点按原表相对次序组成新链表 void split(linkList *head, linkList *oddList) { // p为当前链表工作指针，p为奇数链表工作指针，pre为当前链表前驱指针 node *p = *head,*q,*pre; while (p) { if(p->data%2 == 1) // 如果是奇数 { if(p == *head) // 如果当前结点是头结点 { *head = p->next; // 更新原链表头结点 if(!*oddList) // 如果奇数链表为空 *oddList = q = p; // 更新奇数链表头指针和工作指针 else { q->next = p; q = p; // 更新奇数链表工作指针 } } else { pre->next = p->next; // 逻辑删除当前结点 if(!*oddList) // 如果奇数链表为空 *oddList = q = p; // 更新奇数链表 else { q->next = p; q = p; } } p = p->next; // 向后遍历 q->next = NULL; // 奇数链表结束标识 } else // 如果是偶数 { pre = p; // 保存前驱指针 p = p->next; } } } int main() { linkList list,oddList; init(&list); init(&oddList); scanInsert(&list); split(&list,&oddList); display(list); printf("\n"); display(oddList); 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; }
-
在单链表中插入结点 在带头结点单链表值为y的结点前插入一个值为x的结点#include <stdio.h> #include <stdlib.h> typedef int dataType; // 带头结点的单链表 typedef struct linkNode { dataType data; struct linkNode *next; }node,*linkList; // 1.初始化带头结点的单链表 void init(linkList *head) { node *p = (node*)malloc(sizeof(node)); p->next = NULL; *head = p; } // 2.输出链表 void display(linkList head) { node *p = head->next; if(!p) { printf("单链表为空！\n"); return; } while (p) { printf("%d ",p->data); p = p->next; } printf("\n"); } // 3.在链表尾部插入元素 void rearInsert(linkList *head, dataType x) { node *p = *head,*q; // head初值为头结点 q = (node*) malloc(sizeof(node)); q->data = x; q->next = NULL; while (p->next) // 找到尾结点 p = p->next; p->next = q; } // 寻找结点值为x的前驱结点 node *findXPre(linkList head, dataType x) { node *p = head->next,*pre = head; while (p && p->data != x) { pre = p; p = p->next; } if(!p) return NULL; return pre; } // 3.8.4.在带头结点单链表值为y的结点前插入一个值为x的结点 void insert(linkList *head, dataType y, dataType x) { node *p = findXPre(*head,y),*q; if(!p) { printf("没有找到这样的结点，无法插入！\n"); return; } q = (node*) malloc(sizeof(node)); q->data = x; q->next = p->next; p->next = q; } int main() { linkList list; // 声明头指针 init(&list); // 初始化单链表 for (int i = 1; i <= 10; i++) rearInsert(&list,i); // 插入结点 display(list); dataType y = 1,x = 0; printf("在带头结点单链表值为%d的结点前插入一个值为%d的结点\n",y,x); insert(&list,y,x); display(list); return 0; }
-
求单链表的结点个数 求单链表的结点个数1.求单链表的结点个数#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; } printf("\n"); } // 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.2 统计单链表结点个数 int count(linkList head) { node *p = head; int i = 0; while (p) { p = p->next; i++; } return i; } int main() { linkList list; // 声明一个指向链表的指针，即头指针 init(&list); // 初始化链表 scanInsert(&list); display(list); // 输出链表 printf("链表的结点个数是%d个", count(list)); return 0; }2.求带头结点的单链表的结点个数#include <stdio.h> #include <stdlib.h> typedef int dataType; // 带头结点的单链表 typedef struct linkNode { dataType data; struct linkNode *next; }node,*linkList; // 1.初始化带头结点的单链表 void init(linkList *head) { node *p = (node*)malloc(sizeof(node)); p->next = NULL; *head = p; } // 2.输出链表 void display(linkList head) { node *p = head->next; if(!p) { printf("单链表为空！\n"); return; } while (p) { printf("%d ",p->data); p = p->next; } printf("\n"); } // 3.根据用户输入构造带头结点的单链表 void scanInsert(linkList *head) { node *p = *head,*q; dataType x; printf("请输入(以9999作为结束标识)...\n"); scanf("%d",&x); while (x!=9999) { q = (node*) malloc(sizeof(node)); q->data = x; q->next = NULL; p->next = q; p = q; scanf("%d",&x); } } // 3.8.3 统计带头结点单链表结点个数 int count(linkList head) { node *p = head->next; int i = 0; while (p) { p = p->next; i++; } return i; } int main() { linkList list; // 声明头指针 init(&list); // 初始化单链表 scanInsert(&list); display(list); printf("链表的结点个数是%d个", count(list)); return 0; }
