数据结构——“线性表的应用举例“ 深度分析学完线性表工作中应用在哪?

数据结构——“线性表的应用举例“ 深度分析学完线性表工作中应用在哪?,第1张

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

引言

我们前面学习了线性表的顺序存储,顺序表的链式存储,但是在实际运用过程中我们该如何应用呢?

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

多项式表示相加:

  • 设一元n次多项式:
    它的n+1个系数可形成一个线性表:p(p0,p1,… ,pn),而x的指数i(0 ≤i ≤ n)对应系数 pi 的序号。无疑Pn(x)中有许多系数为0的项,如:

    我们看个多项式的案例:
    对于这样繁琐的多项式合并计算,如果多了,我们应该如何解决快速计算,可以用线性表来解决。我们要抽取处理实际应用中线性表是哪一个?
    一个线性多项式,用一个线性表来表示。(只考虑有效项)

对应的线性表就是P(1,0,……,0,3,……,2). 显然这些0元素在存储结构中要占用大量的存储空间,是一种浪费,且处理起来费时,所以去掉Pn(x)中系数为0的项,写作:

其中:Pi(1 ≤ i ≤ m) ≠ 0,且 0≤ el < e2 < e3 <…< em = n,于是,系数的序号 i 并不反映x的指数ei,故对应的线性表每项要用两个值表示,即:

P2000(x),
对应的线性表为:P( (1,0) , (3,1000) , (2,2000) )
讨论用单链表的形式存储多项式及两个多项式相加。

将多形式中的一项存储于一个结点,结点类型描述如图

结点类型描述

typedef struct
{
  float coef;
  int exp;
}data_t;

typedef struct node_t
{
    data_t data;
    struct node_t *next;
}linknode_t , *linklist_t;

例如 设两多项式A,B分别为:

  • C为A,B多项式的合并

    我们思考,如何形成多项式A,B的链表结构,可以参照我们之前“建立链表的算法”。

A和B的链表结构如图:

多项式的合并,就是两个链表,需要两个指针,分别指向两个链表中的第一个结点,根据结点的指数域(exp)去比较,如果遇到,指数相同就相加,遇到指数小的,先去合并。

  • 算法思路:
    1. 设指针pa,pb分别指向两链表中的某个结点(初始指向第一个结点);
    2. pa->data.exp < pb->data.exp,则pa结点应为和的一项;
    3. pa->data.exp > pb->data.exp,则pb结点应为和的一项;
    4. pa->data.exp = pb->data.exp,则两结点对应系数相加;
      { sum = pa->data.coef + pb->data.coef
      }
    5. 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问题:

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

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

joseph代码思路构建:
  1. 单项循环链表的建立
    第一步:先构想结构体的定义
#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 < 0){
		puts("n sound n>0");
		goto loop;  //回到loop 继续指向loop下代码
	}

	if((H = (linklist)malloc(sizeof(listnode))) == NULL){
		puts("maloc failed");
		return NULL;
	}
	//建立了无结点循环单链表,尾结点r指向H
	H->data = 1;
	H->next = H;
	r = H;

    //
	for(i =2 ; i<=n ;i++){
		if((p = (linklist)malloc(sizeof(listnode))) == NULL){
			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=Hr->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< m-1 ;i++){
        //r跟着移动 ,数到m,r指向被删除的前一个结点
        r = r->next; 
   }

此时要删除6号。,要借助指针p来删除

joseph算法代码示例

void list_jose(linklist H , int k ,int m){
        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<m-1 ;i++){  //在此之前r已经指到了k的前一个结点,开始数数,              
                        r = r->next;    //r跟着移动 ,数到m,r指向被删除的前一个结点
                }
                p=r->next;   //p指向被删除的结点
                r->next = p->next;   //删除结点前一个结点next 指向 删除结点下一个结点
                printf("%d ",p->data);  //打印删除的结点
                free(p);    //释放(删除)结点
                p=NULL;      //指针置空  防止称为野指针
        }
        //由于所有结点都删除后,就剩一个结点,打印这个结点,并删除它
        printf("%d ",r->data);
        free(r);
        r=NULL;
        puts("");
}


我们再来验证以下几种情况

  1. k=3 m=1 (从3号开始数,刚数就出列)

    没问题
  2. k=1 m=1 (从1号开始数,刚数就出列)

    没问题
joseph代码完整示例:

文件一:joseph.h

#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);
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 < 0){
		puts("n sound n>0");
		goto loop;
	}

	if((H = (linklist)malloc(sizeof(listnode))) == NULL){
		puts("maloc failed");
		return NULL;
	}
	H->data = 1;
	H->next = H;
	r = H;

	for(i =2 ; i<=n ;i++){
		if((p = (linklist)malloc(sizeof(listnode))) == NULL){
			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<m-1 ;i++){
			r = r->next;
		} 
		p=r->next;
		r->next = p->next;
		printf("%d ",p->data);
		free(p);
		p=NULL;
	}

	printf("%d ",r->data);
	free(r);
	r=NULL;
	puts("");
}

文件三:test.c

#include"joseph.h"

int main(){
linklist H;
int k=1;
int m=1;

H = list_create();
list_show(H);

list_jose(H,k,m);

return 0;
}

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/789037.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-05-05
下一篇 2022-05-05

发表评论

登录后才能评论

评论列表(0条)

保存