线性表的链式存储结构c++

太过爱你忘了你带给我的痛 2022-11-30 01:46 221阅读 0赞

> 《数据结构》（第2版）陈越

#include <iostream>
    using namespace std;
    
    
    typedef struct LNode *PtrToLNode;
    
    struct LNode{
        //定义链表结点的结构
        
        int Data;
        PtrToLNode Next;
    };
    
    typedef PtrToLNode Position;//代表结点的地址
    typedef PtrToLNode List;
    
    int Length(List L){
        //1.求表长
        
        Position p;//移动指针；
        int cnt = 0;//初始化计数器
        p = L;//p指向链表的第一个结点
        
        while(p){
        //p != NULL
            
            cnt++;
            p = p->Next;//当前p指向的是第cnt个结点
            
        }
        return cnt;
    }
    
    
    //查找
    int FindKth(List L, int K){
        //2.按位序查找，从第1个到第n个
        Position p;
        
        int cnt = 1;//位序从1开始
        p = L;//p指向的是L的第一个结点
        
        while(p && cnt < K){
        
            p = p->Next;
            cnt++;
        }
        
           
        if((cnt == K) && p != NULL)//找到第K个
            return p->Data;
        else
            return -1;
        
    }
    
    
    Position Find(List L, int x){
        //3.按值查找
        Position p = L;//p指向L的第一个结点
        
        while(p && p->Data != x){
        
            p = p->Next;
        }
        
        return p;//如没找到，则返回NUlL
    
    }
    
    
    List Insert(List L, int x, int i){
        //4.插入(不带头结点的链表，调用函数需要用一个临时指针来接收返回值并进行判断，因为若插入不成功会返回NUlL)
        Position tmp, pre;//pre代表第i-1个位置
        
        tmp = (Position)malloc(sizeof(struct LNode));//申请、填装新结点
        tmp ->Data = x;
        
        if(i == 1){
        //新结点插入在表头
            tmp->Next = L;
            return tmp;//返回新表头指针
            
        }
        
        else{
        //查找位序为i-1的结点
            
            int cnt = 1;//位序从1开始
            pre = L;//pre指向L的第一个结点
            
            while(pre && cnt < i-1){
        
                pre = pre->Next;
                cnt++;
            }
            
            if(pre == NULL || cnt != i-1){
        //位置参数错误
                cout << "位置参数错误" << endl;
                free(tmp);
                return NULL;
                
            }
            else{
        //找到了待插结点的前一个结点pre
                tmp->Next = pre->Next;
                pre->Next = tmp;
                return L;
                
            }
        }
            
    }
    
    
    bool Delete(List L, int i）{
        //5.删除单链表中位序为i的结点
        //默认L带有头结点
        
        Positon pre, tmp;
        int cnt = 0;
        
        //查找位序为i-1的结点
        pre = L;//指向表头，空的“头结点”
        while(pre && cnt < i-1){
        
            pre = pre->Next;
            cnt++;
        }
        if(pre == NULL || cnt != i-1 || pre->Next = NULL){
        //所找结点或位序为i的结点不在链表L中
            cout << "位置参数错误" << endl;
            return false;
            
        }
        else{
        //找到了待删结点的前一个结点pre
            //将结点删除
            tmp = pre->Next;
            pre->Next = tmp->Next;
            free(tmp);
            return true;
            
        }
        
    }