数据结构之线性表

谁践踏了优雅 2022-12-30 08:15 113阅读 0赞

### 目录 ###

*  1.线性表的定义
 *  2.线性表之顺序表
 *  3.线性表之单链表
 *  4.广义表
 *  5.多重链表

引子：  
对于这样一个多项式  f ( x ) = a 0 + a 1 x + . . . + a n − 1 x n − 1 + a n x n f(x)=a\_0+a\_1 x+...+a\_\{n-1\}x^\{n-1\}+a\_n x^n f(x)=a0\+a1x\+...\+an−1xn−1\+anxn该如何表示？首先可以看出多项式中的关键数据有两类：多项式的项数n,各项系数以及指数。

**方法1：顺序存储结构直接表示**  
对于 f ( x ) = 4 x 5 + 3 x 2 + 1 f(x)=4x^5+3x^2+1 f(x)=4x5\+3x2\+1可表示为a\[i\] = \[1, 0, 3, 0, 0, 5\]，下表i对应指数，a\[i\]对应系数。  
这种对于 f ( x ) = 4 x 1 00 + 3 x 2 + 1 f(x)=4x^100+3x^2+1 f(x)=4x100\+3x2\+1而言有浪费太多空间，几乎都是0.

**方法2：顺序存储结构表示非零项**  
将多项式看作一个 （ a i , i ） （a\_i, i） （ai,i）的二元组的集合,按照指数大小顺序存储。 f ( x ) = 4 x 5 + 3 x 2 + 1 f(x)=4x^5+3x^2+1 f(x)=4x5\+3x2\+1表示为:

**方法3：链表结构存储非零项**  
链表中的每个节点存储多项式中的一个非零项，包括系数和指数两个数域以及一个指针域。 f ( x ) = 9 x 1 2 + 15 x 8 + 3 x 2 f(x)=9x^12+15x^8+3x^2 f(x)=9x12\+15x8\+3x2表示为:  
![在这里插入图片描述][2020122418025739.png]

# 1.线性表的定义 #

对于上面多项式表示的问题，我们可以看出：  
1.同一个问题具有不同的表示（存储）方法  
2.有一类共性问题:有序线性序列的组织和管理

**什么是线性表？**

“线性表(Linear List)”：由同类型数据元素构成有序序列的线性结构

*  表中元素个数称为线性表的长度
 *  线性表没有元素时，称为空表
 *  表起始位置称表头，表结束位置称表尾

**线性表的抽象数据类型描述**

类型名称：线性表（List）  
数据对象集：线性表是 n (≥0)个元素构成的有序序列( a1, a2, …,an )  
操作集：线性表 List，整数i表示位置，元素X ElementType，  
线性表基本操作主要有：  
1、List MakeEmpty()：初始化一个空线性表L；  
2、ElementType FindKth( int K, List L )：根据位序K，返回相应元素 ；  
3、int Find( ElementType X, List L )：在线性表L中查找X的第一次出现位置；  
4、void Insert( ElementType X, int i, List L)：在位序i前插入一个新元素X；  
5、void Delete( int i, List L )：删除指定位序i的元素；  
6、int Length( List L )：返回线性表L的长度n。

# 2.线性表之顺序表 #

下面是以c语言实现的顺序表

#include<stdio.h>
    #include<stdlib.h>
    #define MAXSIZE 100 //定义顺序表的最大长度
    
    typedef int ElementType;
    typedef struct LNode *List;
    struct LNode{ 
        ElementType data[MAXSIZE];
        int Last;
    };
    
    List MakeEmpty();
    ElementType FindKth(int K, List L);
    int Find(ElementType X, List L);
    void Insert(ElementType X, int i, List L);
    void Delete(int i, List L);
    int Length(List L);
    void show(List L);
    
    int Length(List L)
    { 
        return L->Last+1;
    }
    
    void Delete(int i, List L)
    { 
        if(i < 1|| i > L->Last+1)
            return;
        for(int k = i-1; k < L->Last+1; k++)
        { 
            L->data[k] = L->data[k+1];
        }
        L->Last--;
        return;
    }
    
    void Insert(ElementType X, int i, List L)
    { 
        if(L->Last == MAXSIZE - 1)
            return;
        if(i < 1|| i > L->Last+2)
            return;
        for(int k = L->Last; k>=i-1; k--){ 
            L->data[k+1] = L->data[k];
        }
        L->data[i-1] = X;
        L->Last++;
    }
    int Find(ElementType X, List L)
    { 
        for(int i=0; i <= L->Last; i++)
        { 
            if(X == L->data[i])
                return i;
        }
        return -1;
    
    }
    ElementType FindKth(int K, List L)
    { 
        return L->data[K-1];
    }
    
    List MakeEmpty()
    { 
        List Ptrl;
        Ptrl = (List )malloc(sizeof(struct LNode));
        Ptrl->Last = -1;
        return Ptrl;
    }
    void show(List L)
    { 
        for(int i=0; i <= L->Last; i++)
        { 
            printf("%d ",L->data[i]);
        }
        printf("\n");
    }
    
    int main()
    { 
        List L = MakeEmpty();
        printf("初始顺序表长度:%d\n",Length(L));
        Insert(2,1,L);
        printf("从第一个位置添加元素2,输出此时顺序表的长度:%d\n",Length(L));
        Insert(3,2,L);
        printf("从第二个位置添加元素3,输出此时顺序表的长度:%d\n",Length(L));
        printf("输出第一个位置的元素:%d\n",FindKth(1, L));
        printf("在第二个位置插入元素1\n");
        Insert(1,2,L);
        printf("输出此时顺序表的元素\n");
        show(L);
        printf("寻找元素1所在的位置:%d\n",Find(1,L));
        printf("输出此时顺序表的长度:%d\n", Length(L));
        printf("删除第二个位置的元素\n");
        Delete(2, L);
        printf("输出此时顺序表的元素\n");
        show(L);
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MDQ4NzU2_size_16_color_FFFFFF_t_70]  
注：c语言的几个知识点  
[指针实现内存动态分配][Link 1]  
[使用typedef定义数据类型][typedef]

# 3.线性表之单链表 #

单链表和顺序表最大的区别就是无法直接获取某个位置的节点，但是删除和增加相比顺序表会比较方便，顺序表的删除和增加都需要移动节点，单链表则不需要。所以说单链表的增加和删除，需要通过遍历节点找到要增加或者节点的位置，然后直接增或删就可以了，而顺序表则是直接找到要增加或者节点的位置，增或删后，后面的节点都要依次移动。

#include<stdio.h>
    #include<stdlib.h>
    
    struct node{ 
         int data;
         struct node *next;
    };
    typedef struct node Lnode, *List;
    List MakeEmpty();
    void Insert(int x, int i, List ptr);
    int Length(List ptr);
    List Find(int k, List ptr);
    void Print(List ptr);
    
    void Print(List ptr)
    { 
         List p = ptr;
         while(p->next){ 
              p = p->next;
              printf("%d ", p->data);
         }
    }
    List MakeEmpty()
    { 
         List p = (List )malloc(sizeof(Lnode));
         p->next = NULL;
         return p;
    }
    int Length(List ptr)
    { 
         int i = 0;
         while(ptr->next){ 
              i++;
              ptr = ptr->next;
         }
         return i;
    }
    List Find(int k, List ptr)
    { 
         int len = Length(ptr);
         if(k > len+1){ 
              printf("error");
              return NULL;
         }
         List p = ptr;
         for(int i=1; i < k; i++){ 
              p = p->next;
         }
         return p;
    }
    void Insert(int x, int i, List ptr)
    { 
         int len = Length(ptr);
    
         if(i > len+1 || i <= 0)
         { 
              printf("位置错误");
              return;
         }
         else{ 
              List p = Find(i, ptr);
              List q = (List )malloc(sizeof(Lnode));
              q->data = x;
              q->next = p->next;
              p->next = q;
         }
    }
    void Delete(int i, List ptr)
    { 
         int len = Length(ptr);
    
         if(i > len || i < 0)
         { 
              printf("位置错误");
              return;
         }
         else{ 
              List p = Find(i, ptr);
              List q = p->next;
              p->next = q->next;
              free(q);
         }
    }
    
    
    int main()
    { 
         List ptr = MakeEmpty();
         Insert(10, 1, ptr);
         Insert(9, 1, ptr);
         Insert(8, 1, ptr);
         Insert(7, 2, ptr);
         Print(ptr);
         printf("\n");
         Delete(2, ptr);
         Print(ptr);
    }

# 4.广义表 #

对于一个一元多项式的表示，前面讲过可以采用一个单链表表示，那么对于一个二元多项式： P ( x , y ) = ( 9 y 2 + 4 ) x 12 + ( 15 y 3 − y ) x 8 + 3 x 2 P(x,y)=(9y^2+4)x^\{12\} +(15y^3-y)x^8+3x^2 P(x,y)=(9y2\+4)x12\+(15y3−y)x8\+3x2，如何进行表示？  
可以采用一个“复杂”链表进行表示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MDQ4NzU2_size_16_color_FFFFFF_t_70 1]

这个复杂链表就称为广义表，可以看出：

*  广义表是线性表的扩展
 *  对于线性表，n个元素都是基本的单元素
 *  广义表中，其元素不仅可以是单元素也可以是另一个广义表

那么具体该怎么去实现呢，节点既可以是单元素，也可以是另一个广义表，这一点可以通过union去实现，即联合，联合可以把不同类型的数据组合在一起，而通过标志域判断是单元素还是广义表。

例如：

typedef struct GNode *GList;
    struct GNode{ 
         int Tag; //标志域：0表示结点是单元素，1表示结点是广义表
         union {   //子表指针域Sublist与单元素数据域Data复用，即共用存储空间
              ElementType Data;
              GList SubList;
         }URegion;
         GList Next; //指向后继结点
    };

# 5.多重链表 #

多重链表其实就是广义表中的一种，多重链表中的节点可能同时隶属于多个链

*  多重链表中的指针域可能会有多个，例如广义表中的例子，其指针域包含了Next和SubList两个指针域；
 *  但包含两个指针域的链表并不一定是多重链表，比如双向链表不是多重链表

多重链表有广泛的用途，基本上如树、图等相对复杂的数据结构都可以采用多重链表方式实现存储。

例：矩阵的表示：  
矩阵可以用二维数组表示，但二维数组表示有两个缺陷：

*  一是数组的大小需要事先确定
 *  二是对于“稀疏矩阵 ”，将造成大量的存储空间浪费。

【分析】 采用一种典型的多重链表——十字链表来存储稀疏矩阵

**只存储矩阵非0元素项**

*  结点的数据域：行坐标Row、列坐标Col、数值Value

**每个结点通过两个指针域，把同行、同列串起来;**

*  行指针(或称为向右指针)Right
 *  列指针（或称为向下指针）Down

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MDQ4NzU2_size_16_color_FFFFFF_t_70 2]  
图中节点有两种类型，一种是term类型，一种是head类型。  
term类型，有两个指针一个指向同一行，一个指向同一列，同一行与同一列分别设计成一个循环列表，所以每个节点既属于某一行也属于某一列，所以称为十字链表。

head类型，作为行链表与列链表的头节点。

最左上角的term，作为整个链表的入口，这个节点的行值、列值与value值表示这个矩阵4行5列，有7个非零值。通过该节点可以找到所有行的头节点，所有列的头节点，所以这是一个入口节点。

对于这两种类型的节点，二者虽然里面的内容不同，但有共性，都有两个指针。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MDQ4NzU2_size_16_color_FFFFFF_t_70 3]

所以可以利用union来表示两个不同类型的节点  
![在这里插入图片描述][20210403155728621.png]

*  用一个标识域Tag来区分头结点和非0元素结点
 *  头节点的标识值为“Head”，矩阵非0元素结点的标识值为“Term”

参考：  
浙大数据结构\_陈越老师的课程，讲的非常好。  
[链接：https://www.bilibili.com/video/BV1H4411N7oD?p=17][https_www.bilibili.com_video_BV1H4411N7oD_p_17]

--------------------

这篇博客从2020年写到了2021年，立的flag啥时候才能实现hhh。

[2020122418025739.png]: /images/20221120/213d6fcc606b43eab52dca9daa9c05e0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MDQ4NzU2_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20201227233136284.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MDQ4NzU2,size_16,color_FFFFFF,t_70
[Link 1]: https://blog.csdn.net/qq_38048756/article/details/111699307
[typedef]: https://blog.csdn.net/qq_38048756/article/details/111759553
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MDQ4NzU2_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20210403151427844.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MDQ4NzU2,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MDQ4NzU2_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20210403154931838.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MDQ4NzU2,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MDQ4NzU2_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20210403155520244.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MDQ4NzU2,size_16,color_FFFFFF,t_70
[20210403155728621.png]: https://img-blog.csdnimg.cn/20210403155728621.png
[https_www.bilibili.com_video_BV1H4411N7oD_p_17]: https://www.bilibili.com/video/BV1H4411N7oD?p=17

数据结构之线性表

发表评论取消回复

还没有评论，来说两句吧...

相关阅读