搜索到
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"); } // 3.查找双链表中第i个结点 dNode *find(dLinkList head, int i) { dNode *p = head; if(i < 1) { printf("非法的索引！\n"); return NULL; } if(!p) { printf("双链表为空！\n"); return NULL; } int j = 1; while (p->rLink && i != j) { p = p->rLink; j++; } if(i > j) return NULL; return p; } // 4.找到双链表的尾结点 dNode *rear(dLinkList head) { dNode *p = head; if(!p) return NULL; while (p->rLink) p = p->rLink; return p; } // 5.在双链表尾部插入值为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 { p = rear(p); p->rLink = q; q->lLink = p; } } // 6.在双链表的第i个结点后插入值为x的新结点 void insert(dLinkList *head, int i, dataType x) { if(i < 0) { printf("非法的插入位置！\n"); return; } dNode *p = *head,*q; q = (dNode*) malloc(sizeof(dNode)); q->data = x; q->rLink = NULL; if(i == 0) // 在表头插入 { if(p) // 链表非空时 { q->rLink = *head; (*head)->lLink = q; *head = q; } q->lLink = NULL; *head = q; return; } p = find(*head,i); if(p) { if(p->rLink) // 如果p不是尾结点 p->rLink->lLink = q; q->rLink = p->rLink; // 以下两行不可换位置 q->lLink = p; p->rLink = q; } else printf("插入索引越界！\n"); } // 7.双链表中删除一个值为x的结点 void del(dLinkList *head, dataType x) { dNode *p = *head; if(!p) { printf("链表为空，无法删除！\n"); return; } while (p) // 寻找要删除的p结点 { if(p->data == x) break; p = p->rLink; } if(p) { if(!p->lLink && !p->rLink) // 只有一个结点时 { free(p); *head = NULL; return; } if(!p->lLink) // 如果删除首结点 { *head = p->rLink; p->rLink->lLink = NULL; free(p); return; } if(!p->rLink) // 如果删除尾结点 { p->lLink->rLink = NULL; free(p); return; } // 中间结点的删除 p->lLink->rLink = p->rLink; p->rLink->lLink = p->lLink; free(p); return; } else printf("没有找到这样的结点，无法删除！\n"); } int main() { dLinkList list; // 声明指向双链表的头指针 init(&list); // 初始化双链表 display(list); // 输出双链表 for (int i = 1; i <= 5; i++) rearInsert(&list,i); // 插入结点 display(list); int i = 5; dataType x = 6; dNode *n = find(list,i); if(n) printf("链表的第%d个元素是%d\n",i,n->data); else printf("链表访问越界！\n"); printf("在第%d个位置后面插入元素%d\n",i,x); insert(&list,i,x); display(list); printf("删除一个值为%d的元素\n",x); del(&list,x); 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 *head) { *head = NULL; } // 2.获取循环单链表的尾结点 node *rear(linkList head) { node *p = head; while (p) { if(p->next == head) break; p = p->next; } return p; } // 3.输出循环单链表各结点的值 void display(linkList head) { node *p = head; if(!p) { printf("循环单链表为空！\n"); return; } while (p->next != head) { printf("%d ",p->data); p = p->next; } printf("%d\n",p->data); } // 4.查找值为x的结点 node* findX(linkList head, dataType x) { node *p = head; if(!p) { printf("循环单链表为空！\n"); return head; } while (p->next != head) { if(p->data == x) return p; p = p->next; } if(p->data == x) return p; else return NULL; } // 5.查找第i个结点 node *find(linkList head, int i) { node *p = head; if(i < 1) { printf("索引非法！\n"); return NULL; } if(!p) { printf("循环单链表为空！\n"); return head; } int j = 1; while (p->next != head && i != j) { p = p->next; j++; } if(i == j) return p; return NULL; } // 6.循环单链表的尾部插入结点 void rearInsert(linkList *head, dataType x) { node *p = *head,*q; q = (node*) malloc(sizeof(node)); q->data = x; if(!p) { q->next = q; *head = q; return; } p = rear(*head); p->next = q; q->next = *head; } // 7.在循环单链表的第i个位置后插入元素x void insert(linkList *head, int i, dataType x) { if(i < 0) { printf("非法的插入位置，无法插入！\n"); return; } node *p = *head,*q,*r; q = (node*) malloc(sizeof(node)); q->data = x; if(i == 0) // 当要在链表最前方插入时 { if(!p) // 链表为空时 { *head = q; (*head)->next = *head; return; } // 链表非空时 r = rear(*head); // 找到尾结点 q->next = *head; r->next = q; *head = q; return; } p = find(*head,i); // 其他位置插入则需要找到插入位置 if(!p) printf("非法的位置，无法插入！\n"); else { if(p->next == (*head)) // 如果在尾结点后插入 { p->next = q; q->next = *head; return; } q->next = p->next; // 中间的位置插入 p->next = q; } } // 6.删除循环单链表中值为x的元素 void del(linkList *head, dataType x) { node *p = *head,*q; if(!p) { printf("链表为空，无法删除！\n"); return; } p = findX(p,x); if(!p) { printf("未找到这样的结点，无法删除！\n"); return; } if((*head)->next == *head) // 只有一个结点时 { free(p); *head = NULL; return; } if(p->next == *head) // 如果是删除最后一个结点 { if(p == (*head)->next) // 只有两个结点时 { (*head)->next = *head; free(p); } else // 多于两个结点时 { p->data = p->next->data; q = p->next; p->next = p->next->next; *head = p; free(q); return; } } else { p->data = p->next->data; // 中间结点的删除 q = p->next; p->next = p->next->next; free(q); } } int main() { linkList list; // 声明循环单链表 init(&list); // 初始化空的不带头结点的循环单链表 display(list); // 输出单链表 for (int i = 1; i <= 5; i++) rearInsert(&list,i); display(list); int i = 5; node *n = find(list,i); // 查找第i个元素 if(n) printf("链表的第%d个元素是%d\n",i,n->data); else printf("链表访问越界！\n"); dataType x = 6; printf("在第%d个位置后面插入元素%d\n",i,x); insert(&list,i,x); display(list); printf("删除一个值为%d的元素\n",x); del(&list,x); 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 *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; } // 4.查找第i个结点 node *find(linkList head, int i) { node *p = head->next; // p为工作指针，初值为头结点的下一结点 if(i < 0) { printf("索引非法!"); exit(1); } if(i == 0) return head; int j = 1; while (p && i!=j) { p = p->next; j++; } return p; } // 5.在单链表的第i个位置后插入元素x void insert(linkList *head, int i, dataType x) { node *p = find(*head,i),*q; q = (node*) malloc(sizeof(node)); q->data = x; q->next = p->next; p->next = q; } // 6.删除单链表中值为x的元素 void del(linkList *head, dataType x) { node *p = (*head)->next,*pre = *head; while (p && p->data != x) { pre = p; p = p->next; } if(p) { pre->next = p->next; free(p); } else printf("没有找到该结点，无法删除！\n"); } int main() { linkList list; // 声明头指针 init(&list); // 初始化单链表 display(list); // 输出单链表 for (int i = 1; i <= 10; i++) rearInsert(&list,i); // 插入结点 display(list); int i = 2; node *n = find(list,i); if(n) printf("第%d个结点的值是%d\n",i,n->data); else printf("第%d个结点不存在！\n",i); dataType x = 0; printf("在第%d个结点后插入一个值为%d的结点\n",i,x); insert(&list,i,x); display(list); printf("在带头结点的单链表中删除一个值为%d的结点\n",x); del(&list,x); 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; } printf("\n"); } // 3.查找单链表中的第i个元素 node *find(linkList list, int i) { if(i < 1) return NULL; int j = 1; node *p = list; while (p && j!=i) { p = p->next; j++; } return p; } // 4.在单链表尾部插入元素 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; } } // 5.在单链表第i个位置后插入元素 void insert(linkList *list,int i,dataType x) { node *p = *list,*q; // p初值为当前链表指针指向的位置 q = (node*)malloc(sizeof(node)); // 创建新节点 q->data = x; p = find(p,i); // 找到第i个结点 if(!p) { if(i == 0) // 如果是在第1个元素前插入 { q->next = *list; // 若在链表前插入，则把链表挂在新结点后 *list = q; // 更新链表指针的的地址，让它指向q } else { printf("位置不存在，无法插入元素！\n"); exit(1); } } else { q->next = p->next; // 把p结点后的结点挂在q结点后 p->next = q; // 把新结点插入p结点后 } } // 6.删除一个值为x的结点 void del(linkList *head, dataType x) { node *p = *head,*pre = NULL; // p为工作指针，q为前驱指针 if(!*head) // 1.链表为空时 { printf("链表为空，无法删除！\n"); exit(1); // 遇到错误终止程序 } while (p && p->data != x) // 寻找x结点 { pre = p; p = p->next; } if(p) // 找到x结点 { if(!pre) // 如果要删除的是第一个结点 *head = p->next; else pre->next = p->next; free(p); } else printf("未找到结点%d\n",x); } // 7.删除倒数第m个元素 void delM(linkList *list, int m) { // p为链表的工作指针，pre为p的前驱指针，q指向待删结点 node *p = *list, *pre = NULL, *q; if(!p) { printf("单链表为空，无法删除！\n"); return; } int n = 0, i, j = 1; // n为链表个数，i、j为链表位序 while (p) // 统计链表结点个数 { n++; p = p->next; } i = n-m+1; // 删除的是第i个结点 if(i < 1 || i > n) { printf("不存在该结点，无法删除！\n"); return; } p = *list; // 重置p指针指回首结点 while (p->next && j < i) // 寻找要删除的结点 { j++; pre = p; p = p->next; } q = p; // q指向待删结点 if(!pre) // 删除的是首结点 *list = p->next; else pre->next = p->next; free(q); } int main() { linkList list; // 声明一个指向链表的指针 init(&list); // 初始化链表 display(list); for (int i = 1; i <= 10; i++) // 循环插入值 rearInsert(&list,i); display(list); // 输出链表 int i = 1; node *n = find(list,i); // 查找第i个元素 if(n) printf("链表的第%d个元素是%d\n",i,n->data); else printf("链表访问越界！\n"); dataType x = 5; printf("在第%d个位置后面插入元素%d\n",i,x); insert(&list,i,x); display(list); // 输出链表 printf("删除一个值为%d的元素\n",x); del(&list,x); display(list); // 输出链表 printf("删除倒数第%d个元素\n",5); delM(&list,5); display(list); // 输出链表 return 0; }
-
顺序循环队列及其实现 #include <stdio.h> #include <stdlib.h> // 定义队列的容量，可以修改为更小的值测试循环队列 #define MAX_SIZE 100 typedef int dataType; // 2.4.3 顺序存储的循环队列 typedef struct { dataType a[MAX_SIZE]; int front,rear; // 队头指针和队尾指针 }seqQueue; // 1.初始化队列 void init(seqQueue *queue) { queue->front = queue->rear = 0; } // 2.判断队列是否为空 int empty(seqQueue queue) { return queue.rear == queue.front; } // 3.打印队列 void display(seqQueue queue) { if(empty(queue)) { printf("队列为空！\n"); return; } while (!empty(queue)) { printf("%d ",queue.a[queue.front]); queue.front = (queue.front + 1)%MAX_SIZE; } printf("\n"); } // 4.获取队首结点的值 dataType get(seqQueue queue) { if(empty(queue)) { printf("队列为空！\n"); exit(1); } return queue.a[queue.front]; } // 5.入队操作 void insert(seqQueue *queue, dataType x) { if((queue->rear + 1)%MAX_SIZE == queue->front) { printf("队列已满，无法入队！\n"); exit(1); } queue->a[queue->rear] = x; queue->rear = (queue->rear + 1)%MAX_SIZE; } // 6.出队操作 void del(seqQueue *queue) { if(queue->rear == queue->front) { printf("队列为空，无法出队！\n"); exit(1); } queue->front = (queue->front + 1)%MAX_SIZE; } // 7.获取队列中元素的个数 int getSize(seqQueue queue) { return (queue.rear-queue.front+MAX_SIZE)%MAX_SIZE; } int main() { seqQueue queue; // 声明队列 init(&queue); // 初始化队列 dataType a = 1, b = 2; insert(&queue,a); // 元素入队 insert(&queue,b); // 元素入队 printf("此时队列中元素有%d个\n", getSize(queue)); display(queue); // 打印队列元素 del(&queue); // 队首元素出队 printf("队首元素是%d\n", get(queue)); display(queue); // 打印队列元素 return 0; }
