数据结构（二）线性表

约定不等于承诺〃 2022-05-11 15:06 254阅读 0赞

## 线性表 ##

### 1. 什么是线性表 ###

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

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

### 2. 线性表的抽象数据类型描述 ###

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

#### 1. 线性表的顺序存储实现 ####

利用数组的连续存储空间顺序存放线性表的各元素

注：顺序存储中是序号是下标，从 0 开始

#include<stdio.h>
    #include<malloc.h>
    #define MAXSIZE 100  // MAXSIZE 定义为 Data 数组的大小
    typedef int ElementType;  // ElementType 可定义为任意类型
    typedef struct LNode *List; 
    struct LNode{
        
       ElementType Data[MAXSIZE]; 
       int Last;  // Last 定义线性表的最后一个元素
    };
    List L;
    //访问下标为 i 的元素：L->Data[i]
    //线性表的长度：L->Last+1
    
    List MakeEmpty(); //初始化顺序表 
    int Find(ElementType X,List L); //查找 X 第一次出现的下标 
    void Insert(ElementType X,int i,List L); //在下标为 i 的地方插入 X 
    void Delete(int i,List L);   //删除下标为 i 的当前值 
    ElementType FindKth(int K,List L);  //返回下标为 K 的当前值
    int Length(List L);  //返回顺序表的长度 
     
    //初始化 
    List MakeEmpty(){
        
        List L;
        L = (List)malloc(sizeof(struct LNode));
        L->Last = -1;
        return L;
    }
    
    // 按值查找 
    int Find(ElementType X,List L){
        
        int i=0;
        while(i <= L->Last && L->Data[i] != X)  
            i++;
        if(L->Last < i)  //如果没找到，返回 -1
            return -1; 
        else    // 找到后返回下标 
            return i;
    }
    
    // 插入
    void Insert(ElementType X,int i,List L){
        
        int j;
        if(L->Last == MAXSIZE-1){
          //位置已满 
            printf("表满");
            return;
        }
        if(i < 0 || L->Last+1 < i){
          //位置越界，如果将数插入 L->Data[L->Last+1]，下面都不用腾位置了 
            printf("位置不合法");
            return;
        }
        for(j=L->Last;j>=i;j--)   // 从后往前依次向后挪一个，给 a[i]腾出位置     
            L->Data[j+1] = L->Data[j];   
        L->Data[i] = X;    //新元素插入
        L->Last++;    // Last仍然指向最后元素
        return;
    } 
    
    //删除
    void Delete(int i,List L){
        
        int j;
        if(i < 0 || L->Last <i){
          //位置越界，而删除最多到 L->Data[L->Last]
            printf("L->Data[%d]不存在元素",i);
            return;
        }
        for(j=i;j<=L->Last;j++)   // 从前往后依次向前挪一个，将 a[i] 覆盖了 
            L->Data[j-1] = L->Data[j];
        L->Last--;  // Last仍然指向最后元素
        return;
    }
    
    // 按序查找
    ElementType FindKth(int K,List L){
        
    	if(K < 0 || L->Last < K){
          //位置越界
            printf("L->Data[%d]不存在元素",K);
            return;
        }
        return L->Data[K];
    }
    
    //表长
    int Length(List L){
        
    	return L->Last+1;
    } 
    
    int main(){
        
    	int i=0;
    	L = MakeEmpty();
    	Insert(11,0,L);
    	printf("在线性表L-Data[0]插入11\n");
    	Insert(25,0,L);
    	printf("在线性表L-Data[0]插入25\n");
    	Insert(33,0,L);
    	printf("在线性表L-Data[0]插入33\n");
    	Insert(77,0,L);
    	printf("在线性表L-Data[0]插入77\n");
    	printf("此时的线性表为："); 
    	for(i=0;i<Length(L);i++)
    		printf("%d ",L->Data[i]);
    	printf("\n");
    	printf("查找值为12的下标是：%d\n",Find(12,L));
    	printf("下标为3的线性表的值是：%d\n",FindKth(3,L));
    	Delete(2,L);
    	printf("删除线性表中下标为2的元素\n");
    	Delete(2,L);
    	printf("删除线性表中下标为2的元素\n");
    	printf("此时的线性表为："); 
    	for(i=0;i<Length(L);i++)
    		printf("%d ",L->Data[i]);
    	printf("\n"); 
    	return 0;
    }

#### 2. 线性表的链表存储实现 ####

不要求逻辑上相邻的两个元素物理上也相邻，通过"链"建立起数据之间的逻辑关系

*  插入、删除不需要移动数据元素，只需要修改"链"

注：链表存储中序号从 1 开始

#include<stdio.h>
    #include<malloc.h>
    typedef int ElementType; // ElementType 可定义为任意类型
    typedef struct LNode *List;
    struct LNode{
        
    	ElementType Data;   //数据域 
    	List Next;   // 下一个链表的地址 
    }; 
    List L;
    
    List MakeEmpty(); //初始化链表 
    int Length(List L);  // 以遍历链表的方法求链表长度 
    List FindKth(int K,List L);  // 按序号查找 
    List Find(ElementType X,List L);  // 按值查找 
    List Insert(ElementType X,int i,List L);  //将 X 插入到第 i-1(i>0) 个结点之后 
    List Delete(int i,List L); // 删除第 i(i>0) 个结点 
    void Print(List L); // 输出链表元素 
    
    // 初始化链表 
    List MakeEmpty(){
        
    	List L = (List)malloc(sizeof(struct LNode));
    	L = NULL;
    	return L;
    }
    
    //求表长 
    int Length(List L){
        
    	List p = L;
    	int len=0;
    	while(p){
          // 当 p 不为空 
    		p = p->Next;
    		len++;
    	}
    	return len;
    } 
    
    // 按序查找 
    List FindKth(int K,List L){
        
    	List p = L;
    	int i = 1;  //从 1 开始 
    	while(p && i<K){
        
    		p = p->Next;
    		i++;
    	}
    	if(i == K)    // 找到了 
    		return p;
    	else    // 未找到 
    		return NULL;
    } 
    
    // 按值查找  
    List Find(ElementType X,List L){
        
    	List p = L;
    	while(p && p->Data!=X)
    		p = p->Next;
    	// 找到了，返回 p
    	// 未找到，返回 NULL，此时 p 等于 NULL 
    	return p;   
    } 
    
    /* 插入
    1. 用 s 指向一个新的结点
    2. 用 p 指向链表的第 i-1 个结点 
    3. s->Next = p->Next，将 s 的下一个结点指向 p 的下一个结点 
    4. p->Next = s，将 p 的下一结点改为 s   */
    List Insert(ElementType X,int i,List L){
        
    	List p,s;
    	if(i == 1){
             // 新结点插入在表头 
    		s = (List)malloc(sizeof(struct LNode));
    		s->Data = X;
    		s->Next = L;
    		return s;     //插入的结点为头结点 
    	}
    	p = FindKth(i-1,L);   // 找到第 i-1 个结点
    	if(!p){
           // 第 i-1 个结点不存在 
    		printf("结点错误");
    		return NULL;
    	}else{
        
    		s = (List)malloc(sizeof(struct LNode));
    		s->Data = X;
    		s->Next = p->Next;   //将 s 的下一个结点指向 p 的下一个结点 
    		p->Next = s;   // 将 p 的下一结点改为 s
    		return L;
    	}
    }
    
    /* 删除
    1. 用 p 指向链表的第 i-1 个结点 
    2. 用 s 指向要被删除的的第 i 个结点
    3. p->Next = s->Next，p 指针指向 s 后面
    4. free(s)，释放空间 
    */
    List Delete(int i,List L){
        
    	List p,s;
    	if(i==1){
           //如果要删除头结点 
    		s = L;
    		if(L)   // 如果不为空 
    			L = L->Next;
    		else
    			return NULL;
    		free(s);   // 释放被删除结点 
    		return L; 
    	}
    	p = FindKth(i-1,L);    // 查找第 i-1 个结点
    	if(!p || !(p->Next)){
             // 第 i-1 个或第 i 个结点不存在 
    		printf("结点错误");
    		return NULL;
    	}else{
        
    		s = p->Next;    // s 指向第 i 个结点 
    		p->Next = s->Next;  //从链表删除 
    		free(s);  // 释放被删除结点 
    		return L;
    	}
    }
    
    // 输出链表元素 
    void Print(List L){
        
    	List t;
    	int flag = 1;
    	printf("当前链表为：");
    	for(t = L;t;t =t->Next){
        
    		printf("%d  ",t->Data);
    		flag = 0;
    	}
    	if(flag)
    		printf("NULL");
    	printf("\n"); 
    }
    
    int main(){
        
    	L = MakeEmpty();
    	Print(L);
    	L = Insert(11,1,L);
    	L = Insert(25,1,L);
    	L = Insert(33,2,L);
    	L = Insert(77,3,L);
    	Print(L);
    	printf("当前链表长度为：%d\n",Length(L));
    	printf("此时链表中第二个结点的值是：%d\n",FindKth(2,L)->Data);
    	printf("查找22是否在该链表中：");
    	if(Find(22,L))
    		printf("是！\n");
    	else
    		printf("否！\n");
    	printf("查找33是否在该链表中：");
    	if(Find(33,L))
    		printf("是！\n");
    	else
    		printf("否！\n");
    	L = Delete(1,L);
    	L = Delete(3,L);
    	printf("----------删除后-----\n"); 
    	Print(L);
    	return 0;
    }

## 课后编程题题解 ##

[两个有序链表序列的合并][Link 1]  
[一元多项式的乘法与加法运算][Link 2]  
[Reversing Linked List][]  
[Pop Sequence][]

[Link 1]: https://blog.csdn.net/liyuanyue2017/article/details/83214908
[Link 2]: https://blog.csdn.net/liyuanyue2017/article/details/83244253
[Reversing Linked List]: https://blog.csdn.net/liyuanyue2017/article/details/83269991
[Pop Sequence]: https://blog.csdn.net/liyuanyue2017/article/details/83302030