欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【C语言数据结构】线性表五:线性表的链式表示和实现(静态链表代码)

程序员文章站 2022-06-06 13:58:46
...

一.问题((A-B)U(B-A))静态链表实现

*《数据结构》P33

*  需要注意的是算法2.14没什么好说的,只是初始化整个结构体数组,算法2.15是在整个备用空间取一个结点当成新链表,算法2.16是把不再使用的节点还到备用链表上

* 可以看到算法2.17就是主要的算法了,其主要结构就是两个for循环,第一个for循环用于建立集合A的静态链表,第二个for用来输入集合B的元素,在每一趟循环中用while去遍历链表A,看元素是插入还是删除

【C语言数据结构】线性表五:线性表的链式表示和实现(静态链表代码)

【C语言数据结构】线性表五:线性表的链式表示和实现(静态链表代码)

【C语言数据结构】线性表五:线性表的链式表示和实现(静态链表代码)

二.代码与结果

#ifndef __HEAD_H__
#define __HEAD_H__ 100
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <strings.h>

#define MAXSIZE 10
#define PRINT(format,...) printf(format,##__VA_ARGS__)

/*static linklist*/
typedef struct
{
    int data;
    int cur;
} SLinkList;

/*function declarations*/
void initspace_sl(SLinkList* s);
void diff_sl(SLinkList * s);
void print_sl(SLinkList* s);
#endif
#include "head.h"
#define DEBUG 100
int main(void)
{
    SLinkList s[MAXSIZE];
    initspace_sl(&s[0]);

#ifdef DEBUG
    print_sl(s);
#endif

    diff_sl(s);
    print_sl(s);
    return 0;
}

 

#include "head.h"
static int malloc_sl(SLinkList* s)
{
    int i = 0;
    i = s[0].cur;
    if(i != 0)
    {
        s[0].cur = s[i].cur;
    }
    return i;
}

/*将下标为k的节点回收*/
static void free_sl(SLinkList* s, int k)
{
    s[k].cur = s[0].cur;
    s[0].cur = k;
    s[k].data = 0xFFFFFFFF;
    return;
}

/*(A - B) U (B - A)*/
/*首先假设A={1, 3, 4}
  首先假设B={2, 4, 6}
 */
void diff_sl(SLinkList* s)
{
    int head = 0;
    int i = 0;    //for circle
    int j = 0;    //for circle
    int k = 0;    //for traverse chain-A
    int prev = 0; //for traverse chain-A record previous pos
    int rear = 0;
    int tmp_b = 0;

    head = malloc_sl(s);
    rear = head;

    /*chain A*/
    for(i = 0; i < 3; i++)
    {
        j = malloc_sl(s);
        PRINT("Please input data to A:%d/3:", i+1);
        scanf("%d", &(s[j].data));
        s[rear].cur = j;
        rear = j;
    }
    s[rear].cur = 0;

    /*chain B*/
    for(i = 0; i < 3; i++)
    {
        PRINT("Please input data to B:%d/3:", i+1);
        scanf("%d", &tmp_b);
        k = s[head].cur;
        while((k != s[rear].cur) && (s[k].data != tmp_b))
        {
            prev = k;
            k = s[k].cur;
        }
        /*当前表中不存在该元素,插入在rear之后
         *且rear位置不变
         */
        if(k == s[rear].cur)/*insert*/
        {
            j = malloc_sl(s);
            s[j].data = tmp_b;
            s[j].cur = s[rear].cur;
            s[rear].cur = j;
        }
        else               /*delete*/
        {
            s[prev].cur = s[k].cur;
            if(k == rear)
            {
                rear = prev;
            }
            free_sl(s, k);
        }
    }
    return;
}

void initspace_sl(SLinkList* s)
{
    int i = 0;
    for(i = 0; i < MAXSIZE; i++)
    {
        s[i].data = 0xFFFFFFFF;
        s[i].cur = i + 1;
    }
    s[MAXSIZE - 1].cur = 0;
    return;
}

void print_sl(SLinkList* s)
{
    int i = 0;
    PRINT("=====START=====\n");
    for(i = 0; i < MAXSIZE; i++)
    {
        PRINT("s[%d].data = %#x, s[%d].cur = %d\n", i, s[i].data, i, s[i].cur);
    }
    PRINT("=====ENDOF=====\n");
    return;
}

 情形一:A={1,3,5} B={2,4,6}  (A - B)U(B - A)={1,3,5,6,4,2}

【C语言数据结构】线性表五:线性表的链式表示和实现(静态链表代码)

 情形二:A={1,3,4} B={2,4,6}  (A - B)U(B - A)={1,3,6,2}

【C语言数据结构】线性表五:线性表的链式表示和实现(静态链表代码)