线性表总结（c语言）

谁借莪１个温暖的怀抱￠ 2022-05-18 00:06 188阅读 0赞

# 线性表 #

## 线性表特点 ##

*  存在一个唯一的一个被称作”第一个”的数据元素
 *  存在唯一的一个被称做”最后一个”的数据元素
 *  除第一个之外，集合中的每个数据元素均只有一个前驱
 *  除最后一个之外，集合中每个数据元素均只有一个后继

### 定义 ###

一个线性表是n个数据元素的有限序列。

## 算法设置 ##

顺序表和线性链表

#define LIST_INIT_SIZE 100
    #define LISTINCREMENT 10
    //顺序表
    typedef struct{
        ElemType * elem;
        int length;
        int listsize;
    }SqList;
    //链表
    typedef struct LNode{
        ElemType data;
        struct LNode *next;
    }LNode,*LinkList;

### 基本操作 ###

/*
    InitList(&L);    //构造一个空线性表L
    DestoryList(&L);  //销毁线性表
    ClearList(&L);    //清空线性表
    ListEmpty(L);  //判空
    ListLength(K); //返回线性表长度
    GetElem(L,i,&e); //传入L线性表,i索引，返回e
    
    LocateElem(L,e,compare()) //返回第一个与e满足关系的数据元素位序，不存在则返回0
    PriorElem(L,cur_e,&pre_e)  //若cur_e是L的数据元素，且不是第一个，则用pre_e返回他的前驱。
    NextElem(L,cur_e,&next_e)  //若cur_e是L的数据元素，且不是最后一个，用next_e返回他的后继
    ListInsert(&L,i,e)   //在L中第i个位置之前插入新的数据元素e,L的长度加1
    ListDelete(&L,i,&e)  //删除L的第i个数据元素，并调用e返回其值，L的长度减1
    ListTraverse(L,visit())  //依次对L的每个数据元素调用函数visit()。一旦visit()失败，则操作失败
    */

### 线性表(顺序存储结构) ###

#include <stdio.h>
    #include <stdlib.h>
    #include "sequenceList.h" 
    
    bool compare(ElemType e1,ElemType e2) {
        return e1 == e2 ? TRUE : FALSE;
    }
    
    void visit(ElemType e) {
        printf("%d ", e);
    }
    
    Status InitList(SqList &L) {
        //创造一个空表
        L.elem = (ElemType *)malloc(sizeof(ElemType)*LIST_INIT_SIZE);
        if (!L.elem)
        {
            exit(OVERFLOW);
        }
        L.length = 0;
        L.listsize = LIST_INIT_SIZE;
        return OK;
    }
    
    Status ListEmpty(SqList L)  
    {
        //判空
        return L.length == 0 ? TRUE : FALSE;
    }
    
    int ListLength(SqList L) 
    {
        //返回线性表长度
        return L.length;
    }
    
    Status GetElem(SqList L,int i,ElemType &e) //传入L线性表,i索引，返回e
    {
        //先判断索引的合法性
        if (i < 0 || i >= L.length)
        {
            return FALSE;
        }
        e = L.elem[i];
        return TRUE;
    }
    
    void ClearList(SqList &L)    //清空线性表
    {
        L.length = 0;
    }
    
    void DestoryList(SqList &L)  //销毁线性表
    {
        free(L.elem);
        L.length = L.listsize = 0;
    }
    
    int LocateElem(SqList L,ElemType e,bool (*compare)(ElemType,ElemType)) //返回第一个与e满足关系的数据元素位序，不存在则返回-1 compare
    {
        for (int i = 0; i < L.length; i++)
        {
            if (compare(L.elem[i],e))
            {
                return i;
            }
        }
        return -1;
    }
    
    Status PriorElem(SqList L,ElemType cur_e,ElemType &pre_e)  
    {
        //若cur_e是L的数据元素，且不是第一个，则用pre_e返回他的前驱。
    
        for (int i = 1; i < L.length; i++)
        {
            if (L.elem[i] ==  cur_e)
            {
                pre_e = L.elem[i - 1];
                return TRUE;
            }
        }
        return FALSE;
    }
    
    Status NextElem(SqList L, ElemType cur_e, ElemType &next_e)  
    {
        //若cur_e是L的数据元素，且不是最后一个，用next_e返回他的后继
        for (int i = 0; i < L.length - 1; i++)
        {
            if (L.elem[i] == cur_e)
            {
                next_e = L.elem[i + 1];
                return TRUE;
            }
        }
        return FALSE;
    }  
    
    Status ListInsert(SqList &L,int i,ElemType e)   
    {
        //在L中第i个位置之前插入新的数据元素e,L的长度加1
        //1.判断i的合法性
        if (i < 0|| i > L.length)
        {
            return FALSE;
        }
        //2.判断线性表长度够不够，不够，realloc
        if (L.listsize == L.length)
        {
            L.listsize += LISTINCREMENT;
            L.elem = (ElemType *)realloc(L.elem, L.listsize);
            if (!L.elem)
            {
                exit(OVERFLOW);
            }
        }
        //3.将i元素向后以一个单位 从后向前移动
        for (int j = L.length; j > i; j--)
        {
            L.elem[j] = L.elem[j - 1];
        }
        //4.插入e
        L.elem[i] = e;
        L.length++;
        return TRUE;
    }  
    
    Status ListDelete(SqList &L,int i,ElemType &e)  
    {
        //删除L的第i个数据元素，并调用e返回其值，L的长度减1
        //1.判断i的合法性
        if (i < 0 || i >= L.length)
        {
            return FALSE;
        }
        //2.将索引为i的元素取出来，赋值给e
        e = L.elem[i];
    
        //3.i后面的元素向前移动1个单位，从前向后移动 j最后位置在倒数第二个位置，索引为L.length - 2
        for (int j = i; j < L.length - 1; j++)
        {
            L.elem[j] = L.elem[j + 1];
        }
        L.length--;
        return TRUE;
    }
    
    void ListTraverse(SqList L,void (*visit)(ElemType))  
    {
        //依次对L的每个数据元素调用函数visit()。一旦visit()失败，则操作失败
        for (int i = 0; i < L.length; i++)
        {
            visit(L.elem[i]);
        }
    }

### 线性表（链式存储结构） ###

### 2.10指出以下算法中的错误和低效(即费时)之处，并将它改写为一个及正确又高效的算法 ###

Status DeleteK(SqList &a, int i,int k) {
        //本过程从顺序存储结构的线性表a中删除第i个元素起的k个元素 
        if (i < 1|| k < 0|| i+k>a.length)
        {
            return INFEASIBLE;
        }
        else
        {
            for (int count = 0; count < k; count++)
            {
                for (int j = a.length; j >= i + 1; j--) {
                    a.elem[j - 1] = a.elem[j];
                    a.length--;
                }
            }
        }
        return OK;
    }

### 2.11 设顺序表va中的数据元素递增有序，试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。 ###