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

线性表的应用举例

• • 引言
• 应用举例
• • 应用一：多项式的处理
  • 应用二：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=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< 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;
}