设为首页收藏本站
开启辅助访问

数据结构

 您所在的位置：网站首页 › 树形结构的应用举例 › 数据结构

数据结构

#数据结构| 来源: 网络整理| 查看: 265

线性表的应用举例 引言 应用举例应用一：多项式的处理应用二：Joseph问题（约瑟夫算法）joseph代码思路构建：joseph代码完整示例：

引言

我们前面学习了线性表的顺序存储，顺序表的链式存储，但是在实际运用过程中我们该如何应用呢？ 在这里插入图片描述

应用举例 应用一：多项式的处理

多项式表示 与 相加:

设一元n次多项式: 在这里插入图片描述 它的n+1个系数可形成一个线性表:p(p0，p1，… ，pn)，而x的指数i(0 ≤i ≤ n)对应系数 pi 的序号。无疑Pn(x)中有许多系数为0的项，如: P2000(x)= 1+ 3X1000 + 2X2000 我们看个多项式的案例： 在这里插入图片描述对于这样繁琐的多项式合并计算，如果多了，我们应该如何解决快速计算，可以用线性表来解决。我们要抽取处理实际应用中线性表是哪一个？ 一个线性多项式，用一个线性表来表示。（只考虑有效项）

对应的线性表就是P(1,0，……，0,3，……,2). 显然这些0元素在存储结构中要占用大量的存储空间，是一种浪费,且处理起来费时，所以去掉Pn(x)中系数为0的项，写作: P。 (x) = P,xe1 + P2xe2 +..........+ P_xen 其中:Pi(1 ≤ i ≤ m) ≠ 0，且 0≤ el < e2 < e3 data_t data; struct node_t *next; }linknode_t , *linklist_t;

例如 设两多项式A，B分别为：

C为A，B多项式的合并 在这里插入图片描述 我们思考，如何形成多项式A，B的链表结构，可以参照我们之前“建立链表的算法”。

A和B的链表结构如图： 在这里插入图片描述 多项式的合并，就是两个链表，需要两个指针，分别指向两个链表中的第一个结点，根据结点的指数域（exp）去比较，如果遇到，指数相同就相加，遇到指数小的，先去合并。

算法思路： 设指针pa，pb分别指向两链表中的某个结点（初始指向第一个结点);若pa->data.exp < pb->data.exp,则pa结点应为和的一项；若pa->data.exp > pb->data.exp,则pb结点应为和的一项；若pa->data.exp = pb->data.exp,则两结点对应系数相加； { sum = pa->data.coef + pb->data.coef }sum != 0 , 相加结果应为和的一项。

结果链表图为 在这里插入图片描述

应用二：Joseph问题（约瑟夫算法）

Joseph问题:

设编号分别为:1，2，…，n的n个人围坐一圈。约定序号为 k (1 ≤ k ≤ n)的人, 从1开始计数，数到m的那个人出列，他的下一位又从1开始计数，数到m的那个人又出列，依次类推，直到所有人出列为止。

例2-9设n=8，k=3，m=4时，如图所示。 在这里插入图片描述 比如有8个人坐一圈，3号队员开始从1数数，依次类推，当6号队员应该数4（m）的时候,他出列，类推下去，直到所有人出列。 出列序列为:(6，2，7，4，3，5，1，8)。

算法思路:

用一个不带头结点的循环链表来处理Josephu问题:

先构想结构体的定义建立一个有n个结点的（无头结点）单循环链表验证链表的正确性：遍历链表，然后从第k结点起从1计数，计到m时，对应结点从链表中删除;然后再从被删除结点的下一个结点起又从1开始计数……，直到所有结点都出列时算法结束。

算法对应的链表结构如图所示。

joseph代码思路构建： 单项循环链表的建立 第一步：先构想结构体的定义 #ifndef _JOSEPH_H__ #define _JOSEPH_H__ #include #include typedef struct node{ int data; struct node *next; }listnode, *linklist; extern linklist list_create(); extern void list_show(linklist H); #endif

在这里插入图片描述 第二步：建立一个有n个结点的（无头结点）单循环链表，并且验证链表的正确性：遍历链表，

#include"joseph.h" linklist list_create(){ linklist H,r,p; int n; int i; loop: //定点回到这 puts("please input n"); scanf("%d",&n); if(n puts("maloc failed"); return NULL; } //建立了无结点循环单链表，尾结点r指向H H->data = 1; H->next = H; r = H; // for(i =2 ; i puts("maloc failed"); return NULL; } p->data = i; r->next = p; r = p; } p->next =H; return H; } void list_show(linklist H){ linklist p = H; while(p->next != H){ printf("%d ",p->data); p = p->next; } printf("%d",p->data); puts(""); }

第二步：建立一个有n个结点的（无头结点）单循环链表，并且验证链表的正确性：遍历链表，

#include"joseph.h" int main() { linklist H; H=list_create(); list_show(H); return 0; }

在这里插入图片描述 循环链表建立好了，我们来继续joseph算法

接下来我们完成Joseph算法本身

首先我们要知道joseph算法，规则是序号为k的人从1开始计数，数到m那个人出列，他的下一位在从1开始数，所有人出列为止。

比如从3号开始数，到6号时候数到了4，故6号出列，6号出列（6号结点从循环链表里删除）要找到他前一个结点，我们看图 在这里插入图片描述 为什么要在2尾有个r尾结点呢，我们想这种情况，当m=1时，从3开始数，只要是3一开始数，他就要出列，所以考虑到这种情况，一开始数数的人就是要被删除的人，我们 要有一个指针指向数k的结点的前一个结点 （r=H； r->next->data = k;）

//尾指针r要指向k（开始数数的人）的前一个结点上

void list_jose(linklist H , int k ,int m){ linklist r; r=H; //指针r 开始时 指向 第一个节点上 //判断r指向的下一个结点的值是不是k（开始数数的人） //若不是，r向下移动 在进行判断下一个结点 while(r->next->data != k){ r = r->next; } printf("k= %d\n",k); }

从 r 指向3号（开始数的人）的前一个结点（2号）了，3号开始数，到6号时候数到了4，故6号出列，6号出列（6号结点从循环链表里删除）要找到他前一个结点 ，这时候 r 指针移动3次 （m-1次） 指向要被删除结点的前一个结点

k=3,m=4 在这里插入图片描述

int i; //在此之前r已经指到了k的前一个结点，开始数数， for(i=0 ; i int i; linklist r,p; r=H; //指针r 开始时 指向 第一个节点上 //判断r指向的下一个结点的值是不是k（开始数数的人） //若不是，r向下移动 在进行判断下一个结点 while(r->next->data != k){ r = r->next; } printf("k= %d\n",k); while(r->next != r){ //由于所有结点都删除后，就剩一个结点，来判断这种情况 for(i=0 ; i int data; struct node *next; }listnode, *linklist; extern linklist list_create(); extern void list_show(linklist H); extern void list_jose(linklist H,int k, int m); #endif

文件二：joseph.c

#include"joseph.h" //循环单链表创建 linklist list_create(){ linklist H,r,p; int n; int i; loop: puts("please input n"); scanf("%d",&n); if(n puts("maloc failed"); return NULL; } H->data = 1; H->next = H; r = H; for(i =2 ; i puts("maloc failed"); return NULL; } p->data = i; r->next = p; r = p; } p->next =H; return H; } //遍历循环单链表 void list_show(linklist H){ linklist p = H; while(p->next != H){ printf("%d ",p->data); p = p->next; } printf("%d",p->data); puts(""); } //joseph规则删除结点 void list_jose(linklist H , int k ,int m){ int i; linklist r,p; r=H; while(r->next->data != k){ r = r->next; } printf("k= %d\n",k); while(r->next != r){ for(i=0 ; i linklist H; int k=1; int m=1; H = list_create(); list_show(H); list_jose(H,k,m); return 0; }

-----------------------------------------很棒学习完了数据结构的 线性表的应用举例--------------------------------------------------

在这里插入图片描述

--------------------------------------------------------[下期预告：栈]------------------------------------------------------



【本文地址】


今日新闻

推荐新闻

CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3