考研数据结构—线性表

今天药忘吃喽~ 2023-07-03 12:05 4阅读 0赞

> *走出失恋的最好办法就是开始一项新的工程并全力以赴。*

线性表：具有相同数据类型的数据元素的有限序列。

**1定义**

/*静态定义*/
    #define Maxsize 100  // to define a SqList's length statically
    typedef int Elemtype  
    typedef struct{
        Elemtype data[Maxsize];
        int length;   //current Sqlist length 
    }SqList;
    
    /*动态定义*/
    #define InitSize 100   //初始长度
    typedef int Elemtype
    typedef struct{
        Elemtype *data;
        int Maxsize,length;
    }SqList;
    
    SqList L;
    
    L.data = (Elemtype*)malloc(sizeof(Elemtype)*InitSize);  //malloc 是C中的动态分配函数

**2基本操作**

/*顺序表插入
    
    插入包括三个动作：
    1 返回值是bool 参数有三个分别为（待插顺序表，插入位置，插入数据）
    2 合法性判断 判断插入位置在不在中  判断表满没满，还能不能插入
    3 插入元素，当前表长加1，从插入位置开始把所有元素向后移动一位
    
    */
    bool ListInsert(SqList &L, int i,Elemtype e){
        if (i<0||i>L.length+1)  //待插入位置是否正确
            return false;
        if (L.length>=Maxsize)    //当前表长是否已满
            return false;
        for(int j=L.length; j>=i ;j--)
        {
            L.data[j]=L.data[j-1];
        }
            L.data[i-1] = e;
            L.length++;
            return true;
    }

/*顺序表删除
    
    1 返回类型是booL  参数也是三个（表，位置，被删元素）
    2 判断合法性  表里有没有元素，表里有没有你指定的要删除的位置
    3 所删元素赋值给e，所有元素前移一位
    
    */
    
    bool ListDelete(SqList &L,int i, Elemtype &e)
    {
        if(i<0||i>L.length+1)
            return false;
        if(L.length<1)
            reture false;
        e = L.data[i-1];
        for (int j=i;j<L.length;j++)
            L.data[j-1]=L.data[j];
        L.length--;
        return true;   
    }

/*顺序表的查找
    
    
    
    */
    
    
    int LocateElement(SqList L,Elemtype e) //由于不用修改表，所以没有&
    {
    
        int i;
    
        for(i=0;i<L.length;i++)
        {
            if(L.data[i]==e)
                return i+1;
        }
        return 0;
    }

巩固例题：

/*从顺序表中删除具有最小值的元素（假设唯一），并由函数返回被删除元素的值。空出的位置由最后一个元素填补，若顺序表为空则显示出错误信息并退出运行。*/
    
    bool ListDele(SqList &L,Elemtype &e)
    {
        if(L.length<1)
            return false;
        e = L.data[0];
        int pos=0;
        for (i=1;i<L.length;i++)
        {
            if(L.data[i]<e)
                e = L.data[i];
                pos = i;
        }
        L.data[pos]=L.data[L.length-1];  //注意是最后一个元素是length-1
        L.length--;                    //注意删除后当前长度要减1
        return true;
    }

/*将顺序表的所有元素逆置*/
    void Reserve(SqList &L)
    {
        Elemtype temp;
        for (int i=0;i<L.length;i++)
        {
            temp = L.data[0];
            L.data[i] = L.data[L.length-i-1];
            L.data[L.length-i-1]=temp;
        }
    }

**单链表**

/*链表结点定义*/
    
    typedef struct LNode{
        Elemtype data;
        struct LNode *next;
    }LNode,*LinkLinst;

/*单链表定义头插法*/
    
    typedef struct LNode{
        Elemtype data;
        struct LNode *next;
    }LNode,*LinkList;
    
    LinkList CreatLinkList(LinkList &L){      //头指针
        LNode *s;                            //指向新结点的指针
        int x;                               //新结点的数据
        L = (LinkList)malloc(sizeof(LNode)); //创建头结点，令头指针指向头结点
        L->next = NULL;                      //令成空表
        scanf("%d",&x);                      //输入要插入的值
        while(x!=9999){                      //插入
            s = (LinkList)malloc(sizeof(LNOde));//开辟新结点的地方
            s->data = x;                     //新结点数据值为x
            s->next = L->next;               //新结点后继指向头指针的后继（头插法）
            L->next = s;                      //头结点后继为新结点
            scanf("%d",&x);                    //下一个要插入的结点
        }
        return L;
    }

/*单链表定义之尾插法*/
    
    typedef struct LNode{
        Elemtype data;
        struct LNode *next;
    }LNode,*LinkList;
    
    LinkList CreatLinkList(LinkList &L){
        LNOde *s,*r=L; 
        int x;
        L = (LinkList)malloc(sizeof(LNode));
      
        scanf("%d",&x);
        while(x!=9999){
            s = (LinkList)malloc(sizeof(LNode));
            s->data = x;
            r->next = s;
            r = s;
            scanf("%d",&x);
       }
       r->next = NULL;
       return L;
    }

/*按序号查找结点值*/
    LNode *GetElem(LinkList L,int i){  //注意，返回值类型是LNode*
        int j=1;
        LNode *p = L->next;
        if(i==0) return L;
        if(i<1) return NULL;
        while(p&&j<i){
            p = p->next;
            j++;
        }
        return p;
    }

/*按值查找结点*/
    LNode *LocateElem(LinkList L,Elemtype e){
        LNode *p = L->next;
        while(p!=NULL&&p->data!=e){
            p = p->next;
        }
        return p;
    }

小结：

建表两种方式：头插法 尾插法
    
    表的插入：
    表的删除：
    
    查找 ：按值查找，按位查找
    
    双链表的出现是为了方便找前驱
    
    循环链表的出现是为了能从任意位置遍历链表
    
    typedef struct LNode{
        Elemtype data;
        struct LNode *next;
    }LNode,*LinkList;
    
    LinkList CreatLinkList(LinkList &L){
        LNode *s;
        L = ()malloc();   x
        L->next = NULL;
        scanf("%d",&e);
        while(x!=9999){
            s =()malloc();  x
            s->data = e;
            s->next = L->next;
            L-next = s;        x
            L.length++;
            scanf("%d",&e);
        }
        return L;
    }
    
    
    LinkList CreatLinkList(LinkList &L){
        LNode *s,*r = L;
        int x;
        scanf("%d",&x);
        while(x!=9999){
            s = ()malloc();
            s->data = x;
            r->next = s;
            r = s;
            scanf("%d",&x);
        }
        r->next = NULL;
        return L;
    }
    
    LNode *GetElem(LinkLIst &L,int i){
        int j=1;
        LNode *p = L->next;b
        if(i==1) return L;
        if(i<1||i>L.length) return Null;
        while(i<j){
            p = p->next;
            j++;
        }
        return p;
    }
    
    LNode *LocateElem(L &L,Elem e){
        LNode *p = L->next;
        for(int i=1;i<L.length;i++)
            if(L.data[i]==e)
                return i+1;
        return 0;
    }
    
    p = GetElem(L,i-1);
    s->next = p->next;
    p->next = s;

后面文章还有线性表的练习题，需要的朋友可以查阅，加油！