首页 数据结构（C++）

  1. 顺序表
    1.1 结构类型的描述
    1.2 顺序表类的定义
    1.3 构造函数
    1.4 复制构造函数
    1.5 按值查找算法
    1.6 插入算法
    1.7 删除算法
    1.8 集合的并运算
    1.9 集合的交运算

  2. 单链表
    2.1 单链表的建立
    2.2 用模板定义的结点类
    2.3 用模板定义的单链表类
    2.4 输出链表所有结点值的算法
    2.5 求单链表长度的算法
    2.6 定位算法
    2.7 搜索算法
    2.8 插入算法
    2.9 删除算法
    2.10 析构函数

  3. 循环链表
    3.1 用模板定义的结点类
    3.2 用模板定义的循环链表类
    3.3 搜索算法
    3.4 插入算法
    3.5 删除算法

  4. 双向循环链表
    4.1 模板定义的链表结点类
    4.2 模板定义的双向循环链表类
    4.3 搜索算法
    4.4 插入算法
    4.5 删除算法

  5. 约瑟夫问题

  6. 递归成员函数
    6.1 不带表头结点输出链表元素值
    6.2 带表头结点输出链表元素值
    6.3 单链表表长

# 一、顺序表

# 1. 结构类型的描述

# 静态存储表示

#define maxSize 100
//const int maxSize=100;
typedef int T;
typedef struct
{
    T data[maxSize];    // 顺序表的静态存储表示
    int n;  //int last;
}SeqList;

# 动态存储表示
typedef int T;
typedef struct
{
    T *data;    // 顺序表的动态存储表示
    int maxSize;
    int n;  //int last;
}SeqList;

# 2. 顺序表类的定义
const int defaultSize=100;
template<class T>
class SeqList
{
protected:
    T *data;    // 存放数组
    int maxSize;    // 最大可容纳表项的项数
    int last;   // 数组中最后一个元素的下标
    void reSize(int newSize);   // 改变数组空间大小
    
public:
    SeqList(int sz=defaultSize);    // 析构函数
    SeqList(SeqList<T> &L); //  复制构造函数
    ~SeqList()  // 析构函数
    {
        delete []data;
    }
    int Size() const    // 求表的最大容量
    {
        return maxSize;
    }
    int Length() const  // 计算表长度
    {
        return last+1;
    }
    int Search(T &x) const; // 搜索 x 在表中位置，函数返回表项序号
    int Locate(int i) const;    // 定位第 i 个表项，函数返回表项序号
    bool getData(int i,T &x);   // 取第 i 个元素
    bool Insert(int i,T &X);    // 插入
    bool Remove(int i,T &x);    // 删除
    
};

# 3. 构造函数
template<class T>
SeqList<T>::SeqList(int sz)
{
    if(sz>0)
    {
        maxSize=sz;
        last=-1;
        data=new T[maxSize];    // 创建表存储数组
        if(data==0)     // 动态分配失败
        {
            cerr <<"存储分配错误！" <<endl;
            exit(1);
        }
    }
}

# 4. 复制构造函数
template<class T>
SeqList<T>::SeqList(SeqList<T> &L)
{
    T value;
    maxSize=L.size();
    last=L.Length()-1;  
    data=new T[maxSize];    // 创建存储数组
    if(data==0) // 动态分配失败
    {
        cerr <<"存储分配错误!" <<endl;
        exit(1);
    }
    for(int i=1;i<=last+1;++i)  // 传送各个表项
    {
        L.getData(i,value);
        data[i-1]=value;
    }
}

# 5. 按值查找算法
// 按值查找算法
template<class T>
int SeqList<T>::Search(T &x) const
{
    // 在表中顺序搜索与给定值 x 匹配的表项，找到则函数返回该表项是第几个元素，否则返回 0
    for(int i=1;i<=last+1;++i)    // 顺序搜索
    {
        if(data[i-1]==x)
        {
            return i;
        }
    }
    return 0;   // 搜索失败
}

# 6. 插入算法
// 插入算法
template<class T>
bool SeqList<T>::Insert(int i,T &x)
{
    if(last==maxSize-1) // 表满
    {
        return false;
    }
    if(i<1 || i>Length()+1)
    {
        return false;   // 参数 i 不合理
    }
    for(int j=last+1;j>=i;--j)  // 依次后移
    {
        data[j]=data[j-1];
    }
    data[i-1]=x;    // 插入
    last++;
    return true;    // 插入成功
}

# 7. 删除算法
// 删除算法
template<class T>
bool SeqList<T>::Remove(int i,T &x)
{
    // 从表中删除第 i 个表项，通过应用型参数 x 返回被删元素。函数返回删除成功信息
    if(last==-1)
    {
        return false;   // 表空
    }
    if(i<1 || i>last+1)
    {
        return false;   // 参数 i 不合理
    }
    x=data[i-1];
    for(int j=i;j<=last;++j)    // 依次前移
    {
        data[j-1]=data[j];
    }
    last--;
    return true;
}

# 8. 集合的并运算
// 集合的 并 运算
void Union(SeqList<int> &LA,SeqList<int> &LB)
{
    int n1=LA.Length();
    int n2=LB.Length();
    int i,k,x;
    for(i=1;i<=n2;++i)
    {
        LB.getData(i,x);    // 在 LB 中任取一元素
        k=LA.Search(x);     // 在 LA 中搜索他
        if(k==0)    // 若在 LA 中未找到，插入它
        {
            LA.Insert(n1+1,x);  // 插入到第 n 个表项位置
            n1++;
        }
    }
}

# 9. 集合的交运算
// 集合的 交 运算
void Intersection(SeqList<int> &LA,SeqList<int> &LB)
{
    int n1=LA.Length();
    int x,k,i=1;
    while(i<=n1)
    {
        LA.getData(i,x);    // 在 LA 中取一元素
        k=LB.Search(x); // 在 LB 中搜索它
        if(k==0)    // 找不到
        {
            LA.Remove(i,x); // 找不到，删除
            n1--;
        }
        else
        {
            i++;
        }
    }
}


# 二、单链表
# 1. 单链表的建立
# 链表结点
struct LinkNode // 链表结点
{
    int data;   //T data;
    LinkNode *link;
};

# 头插法
// 头插法
template<class T>
List<T>::HLinkList(int n)
{
    first=0;
    for(int i=0;i<n;++i)
    {
        p=new LinkNode<T>();
        cin >>p->data;
        p->link=first;
        first=p;
    }
}

# 尾插法
// 尾插法
template<class T>
List<T>::RLinkList(int n)
{
    first=tail=new LinkNode<T>();
    first->link=0;
    for(int i=0;i<n;++i)
    {
        p=new LinkNode<T>;
        cin >>p->data;
        p->link=0;
        tail->link=p;
        tail=p;
    }
}

# 2. 用模板定义的结点类
// 用模板定义的结点类
template<class T>
struct LinkNode // 链表结点类的定义
{
    T data; // 数据域
    LinkNode<T> *link;  // 链指针域
    LinkNode()  // 构造函数
    {
        link=0;
    }
    LinkNode(T item,LinkNdoe<T> *ptr=0) // 构造函数，创建新的结点
    {
        data=item;
        link=ptr;
    }
    bool operator==(T X)    // 重载函数，判断相等
    {
        return data.key==x; 
    }
    bool operator!=(T x)    
    {
        return data.key!=x;
    }
};

# 3. 用模板定义的单链表类
// 用模板定义的单链表类
template<class T>
class List
{
protected:
    LinkNode<T> *first; // 表头指针
public:
    List()  // 构造函数
    {
        first=new LinkNode<T>;
    }
    List(T x)   // 构造函数
    {
        first=new LinkNode<T>(x);
    }
    List(List<T> &L);   // 复制构造函数
    ~List(){}   // 析构函数
    void makeEmpty();   // 将链表置为空表
    int Length() const; // 计算链表的长度
    LinkNode<T> *Search(T x);   // 搜索含 x 元素
    LinkNode<T> *Locate(int x); // 定位第 i 个元素
    T *getData(int i);  // 取出第 i 个元素值
    void setData(int i,T x);    // 更新第 i 元素值
    bool Insert(int i,T x); // 在第 i 元素后插入
    bool Remove(int i,T &x);    // 删除第 i 个元素
    bool IsEmpty() const    // 判断表空
    {
        return first->link==0 ? true : false;
    }
    LinkNode<T> *getFirst() const
    {
        return first;
    }
    void setFirst(LinkNode<T> *f)
    {
        first=f;
    }
    void sort();    // 排序
    void Print();   // 输出整条链表的结点值
};

# 4. 输出链表所有结点值的算法
// 输出链表所有结点值的算法
template<class T>
void List<T>::Print()
{
    LinkNode<T> *p=first->link;
    while(p!=0)
    {
        cout <<p->data <<" ";
        p=p->link;
    }
}


# 5. 求单链表长度的算法
// 求单链表长度的算法
template<class T>
int List<T>::Length() const
{
    LinkNode<T> *p=first->link;
    int count=0;    // 检测指针 p 指示第一个结点
    while(p!=0)
    {
        count++;
        p=p->link;
    }
    return count;
}

# 6. 定位算法
// 单链表的定位算法
template<class T>
LinkNode<T> *List<T>::Locate(int i)
{
    // 函数返回第 i 个元素的地址
    if(i<0)
    {
        return 0;
    }
    LinkNode<T> *current=first;
    int k=0;
    while(current!=0 && k<i)
    {
        current=current->link;
        k++;
    }
    return current; // 返回第 i 号结点地址或 0
}

# 7. 搜索算法
// 单链表的搜索算法
template<class T>
LinkNode<T> *List<T>::Search(T x)
{
    // 在表中搜索含数据 x 的结点，搜索成功是函数返回该结点地址
    LinkNode<T> *current=first->link;
    while(current!=0 && current->data!=x)
    {
        current=current->link;
    }
    return current;
}


# 8. 插入算法
// 插入算法
// 将新元素 x 插入在链表中第 i 个结点之后
// 将新元素 x 插入在链表中第 i 个结点之前，则可以插在 i 之后，再对换 i 和 i+1 的 data 值
template<class T>
bool List<T>::Insert(int i,T x)
{
    // 将新元素 x 插入在链表中第 i 个结点之后
    LinkNode<T> *current=Locate(i);
    if(current==0)  // 无插入位置
    {
        return false;
    }
    LinkNode<T> *newNode=new LinkNode<T>(x);
    newNode->link=current->link;
    current->link=newNode;
    return true;
}

# 9. 删除算法
// 删除算法
template<class T>
bool List<T>::Remove(int i,T &x)
{
    LinkNode<T> *current=Locate(i-1);
    if(current==0 || current->link==0)// 删除不成功
    {
        return false;
    }
    LinkNode<T> *del=current->link;
    current->link=del->link;
    x=del->data;
    delete del;
    return true;
}

# 10. 析构函数
// 析构函数
template<class T>
List<T>::~List()// 析构函数：从链头开始删
{
    LinkNode<T> *q;
    while(first!=0)
    {
        q=first;    // 保存被删结点
        first=first->link;  // 从链上摘下该结点
        delete q;   // 删除
    }
}


# 三、循环链表
# 1. 用模板定义的结点类
template<class T>
struct CircLinkNode // 链表结点类的定义
{
    T data; // 数据域
    CircLinkNode<T> *link;  // 链指针域
    CircLinkNode(CircLinkNode<T> *next=0)  // 构造函数
    {
        link=next;
    }
    CircLinkNode(T d,CircLinkNode<T> *next=0) // 构造函数，创建新的结点
    {
        data=d;
        link=next;
    }
    bool operator==(T X)    // 重载函数，判断相等
    {
        return data.key==x.key; 
    }
    bool operator!=(T x)    
    {
        return data.key!=x.key;
    }
};

# 2. 用模板定义的循环链表类
// 用模板定义的循环链表类
template<class T>
class CircList
{
private:
    CircLinkNode<T> *first,*last; // 头指针，尾指针
public:
    CircList(const T x);  // 构造函数
    CircList(CircList<T> &L);   // 复制构造函数
    ~CircList(){}   // 析构函数
    int Length() const; // 计算链表的长度
    CircLinkNode<T> *Search(T x);   // 搜索含 x 元素
    CircLinkNode<T> *Locate(int x); // 定位第 i 个元素
    T *getData(int i);  // 取出第 i 个元素值
    void setData(int i,T x);    // 更新第 i 元素值
    bool Insert(int i,T x); // 在第 i 元素后插入
    bool Remove(int i,T &x);    // 删除第 i 个元素
    bool IsEmpty() const    // 判断表空
    {
        return first->link==0 ? true : false;
    }
    LinkNode<T> *getFirst() const   // 返回表头结点地址
    {
        return first;
    }
    void setFirst(LinkNode<T> *f)   // 设置表头结点地址
    {
        first=f;
    }
    void sort();    // 排序
    void Print();   // 输出整条链表的结点值
};


# 3. 搜索算法
// 搜索算法
template<class T>
CircLinkNode<T> *CircList<T>::Search(T x)
{
    // 在链表中从头搜索其数据值为 x 的结点
    current=first->link;
    while(current!=first && current->data!=x)
    {
        current=current->link;
    }
    return current;
}
image-20250922212126139
# 4. 插入算法
同单链表插入算法
image-20251006114922996
# 5. 删除算法
同单链表删除算法
image-20251006114935789


# 四、双向循环链表
image-20250922213435977
image-20250922213455906
image-20250922213514769
# 1. 模板定义的链表结点类
image-20251006115537375
template<class T>
struct DblNode  // 链表结点类定义
{
    T data; // 链表结点数据
    DblNode<T> *ILink,*rLink;   // 前驱、后继指针
    DblNode(DblNode<T> *l=0,DblNode<T> *r=0)    // 构造函数
    {
        ILink=l;
        rLink=r;
    }
    DblNode(T value,DblNode<T> *l=0,DblNode<T> *r=0)    // 构造函数
    {
        data=value;
        ILink=l;
        rLink=r;
    }
};

# 2. 模板定义的双向循环链表类
template<class T>
class DblList   // 双向循环链表类定义
{
private:
    DblNode<T> *first;  // 表头指针
public:
    DblList(T uniqueVal)    // 构造函数
    {
        first=new DblNode<T>(uniqueVal);
        first->rLink=first->lLink=first;
    }
    DblNode<T> *getFirst() const    // 获取头结点
    {
        return first;
    }
    void setFirst(DblNode<T> *ptr)  // 设置头结点地址
    {
        first=ptr;
    }
    DblNode<T> *Search(T x,int d);  // 搜索算法：按 d 方向寻找值为 x 的结点
    DblNode<T> *Locate(int i,int d);    // 定位算法：定位序号为 i (>=0) 的结点：d=0 前驱方向，d!=0 后继方向
    bool Insert(int i,T x,int d);   // 插入算法：在第 i 个结点后插入包含值 x 的新结点
    bool Remove(int i,T &x,int d);  // 删除算法：删除第 i 个结点
    bool IsEmpty()  // 判断表空
    {
        return first->rLink==first;
    }
};

# 3. 搜索算法
image-20251006121943875
first 哨兵节点
template<class T>
DblNode<T> *DblList<T>::Search(T x,int d)// 搜索算法
{
    DblNode<T> *current=(d==0)? first->lLink : first->rLink;   // 按 d 确定搜索方向
    while(current!=first && current->data!=x)
    {
        current=(d==0)? current->lLink : current->rLink;
    }
    if(current!=first)//first 哨兵节点
    {
        return current;// 搜索成功
    }
    else
    {
        return 0;   // 搜索失败
    }
}


# 4. 插入算法
image-20251006122750436 image-20251006122801803
template<class T>
bool DblList<T>::Insert(int i,T x,int d)// 插入算法
{
    DblNode<T> *current=Locate(i,d);// 查找第 i 个结点
    if(current==0)
    {
        return false;// 插入失败
    }
    DblNode<T> *newNd=new DblNode<T>(x);
    if(d==0)// 前驱方向
    {
        newNd->lLink=current->lLink;// 链入 lLink 链
        current->lLink=newNd;
        newNd->lLink->rLink=newNd;// 链入 rLink 链
        newNd->rLink=current;
    }
    else// 后继方向
    {
        newNd->rLink=current->rLink;
        current->rLink=newNd;
        newNd->rLink->lLink=newNd;
        newNd->lLink=current;
    }
    return true;    // 插入成功
}

# 5. 删除算法
image-20251006124451985 image-20251006124509324
template<class T>
bool DblList<T>::Remove(int i,T &x,int d)// 删除算法
{
    DblNode<T> *current=Locate(i,d);
    if(current==0)
    {
        return false;// 删除失败
    }
    current->rLink->lLink=current->lLink;// 从 lLink 摘下
    current->lLink->rLink=current->rLink;// 从 rLink 摘下
    x=current->data;// 保存删除的数据
    delete current;// 删除
    return true;// 删除成功
}

# 五、约瑟夫问题
image-20251007120246398 image-20251007152003448 image-20251007152019141 image-20251007152033370 image-20251007152057506 image-20251007152107428
void Josephus(int n,int start,int m)// 隔 m 人
{
    int counter,j,*A=new int[n];//counter 出来的人数   n 总人数
    for(j=0;j<n;++j)// 初始化，把各位置号存入数组中
    {
        A[j]=j+1;
    }
    counter=1;
    start--;
    while(counter<n)// 当前已站出人数比总人数少
    {
        cout <<A[start];// 输出当前要站出来的人的位置号
        for(j=start;j<n-counter;++j)
        {
            A[j]=A[j+1];// 位置号前移
        }
        start=(start+m-1)%(n-counter);
        counter++;
    }
    cout <<A[0];
}


# 六、递归成员函数
# 1. 不带表头结点输出链表元素值
# 方法一
class Link
{
    LinkNode *head;// 不带表头结点
public:
    void Print(LinkNode *h);// 递归函数
    LinkNode *getHead()
    {
        return head;
    }
};
void Link::Print(LinkNode *h)
{
    if(h!=0)// 当前节点不为空
    {
        cout <<h->data <<" ";
        Print(h->link);// 递归打印下一个节点
    }
}
void main()
{
    Link MyLink;
    //...
    MyLink.Print(MyLink.getHead());
}

# 方法二
class link
{
    LinkNode *head;// 不带表头结点
	void Print(LinkNode *h);// 递归函数
    
public:
    void Print()// 递归函数
    {
        Print(head);
    }
};
 
void Link::Print(LinkNode *h)
{
    if(h!=0)// 当前节点不为空
    {
        cout <<h->data <<" ";
        Print(h->link);// 递归打印下一个节点
    }
}
void main()
{
    Link MyLink;
    //...
    MyLink.Print();
}

# 2. 带表头结点输出链表元素值
# 方法一
class link
{
    LinkNode *first;// 带表头结点
    
public:
    void Print(LinkNode *h);// 递归函数
  	LinkNode *getFirstNext()
    {
        return first->next;
    }
};
void Link::Print(LinkNode *h)
{
    // 方法一：正向输出
    if(h!=0)// 当前节点不为空
    {
        cout <<h->data <<" ";
        Print(h->link);// 递归打印下一个节点
    }
    /*	方法二：反向输出
    if (h!=0)// 当前节点不为空
    {
    	Print (h->link);// 递归打印下一个节点
        cout <<h->data <<" ";
    }
    */
}
void main()
{
	Link MyLink;
    //...
    MyLink.Print(MyLink.getFirstNext());
}

# 方法二
class link
{
    LinkNode *first;// 带表头结点
    void Print(LinkNode *h);// 递归函数
    
public:
    void Print()
    {
        Print(first->next);
    }
};
void Link::Print(LinkNode *h)
{
    if(h!=0)// 当前节点不为空
    {
        cout <<h->data <<" ";
        Print(h->link);// 递归打印下一个节点
    }
}
void main()
{
	Link MyLink;
    //...
    MyLink.Print();
}

# 3. 单链表表长
# 方法一
int counter=0;
void Length1(LinkNode *h)
{
    if(h==0)// 终止条件
    {
        return;
    }
    else
    {
        counter++;
        Length1(h->next);// 递归项    
    }
}

# 方法二
int counter=0;
void Length1(LinkNode *h)
{
    if(h==0)// 终止条件
    {
        return;
    }
    else
    {
        Length1(h->next);// 递归项
        counter++;    
    }
}

# 方法三
int Length1(LinkNode *h)
{
    if(h==0)// 终止条件
    {
        return;
    }
    else
    {
        return 1+Length1(h->next);// 递归项  
    }
}
  
 更新于