数据结构和算法

用C/C++, Python, Java实现一些基本的数据结构和相关的操作

Posted by tianhaoo on January 2, 2020 本文阅读量

记录基本的数据结构知识

单链表

常量和类型定义

  • C/C++

      typedef struct LNode{
          ElemType data;
          struct LNode* next;
      }LNode, *LinkList;
    
      Linklist L = (Node*)malloc(sizeof(Node));
    
  • Python

      class LNode:
          def __init__(self, elem):
              self.data = elem
              self.next = None
    
    
      class LinkList:
          def __init__(self):
              self.head = LNode("头节点") # head是头指针,指向头结点,而头结点的data中不存储任何信息。
    
  • Java

    
    

一些题目

  1. 求带头结点的单链表长度。

     int Length(LinkList L){
         Node* p = L;
         int count = 0;
         while(p->next != NULL){
             count++;
             p = p->next;
         }
         return count;
     }
    
     def Length(L):
         q = L.head
         count = 0
         while q.next != None:
             count += 1
             q = q.next
         return count
    
  2. 用尽可能短的时间,将两个带头结点的单链表连接在一起。

     void Connect(LinkList &ha, LinkList &hb, int m, int n, LinkList &hc){
         // 将ha和hb指向的单链表合并,用hc传出来
         Linklist hd;
         if(m<=n){
             hc = ha;
             hd = hb;
         }// hc指向短的,hd指向长的
         Node* p = hc;
         while(p->next != NULL){
             p = p->next;
         }
         p->next = hd->next;
         free(hd);
         ha = NULL;
         hb = NULL;
     }
    
     def Connect(L1, m, L2, n, L3):
         ha = L1.head
         hb = L2.head
         if m > n:  
             ha, hb = hb, ha
         p = ha
         while p.next != None:
             p = p.next
         p.next = hb.next
         L3.head = ha
    
  3. 一个递增有序的带头结点的单链表,写一个高效算法,删除所有值相同的多余元素

     void Purge(LinkList L){
         if(L->next != NULL){
             Node* p = L->next;
             while(p->next != NULL){
                 if (p->data == p->next->data){
                     q = p->next;
                     p->next = q->next;
                     free(q);
                 }else{
                     p = p->next;
                 }
             }
         }
     }
    
     def Delete(L):
         p = L.head
         q = p.next
         while p.next is not None:
             if q is not None:
                 while q.data == p.data:
                     q = q.next
                 p.next = q
             p = p.next
             q = p.next
    
  4. 单链表就地逆置

     void Reverse(LinkList &L){
         if(L->next!=NULL){
             p = L->next;
             L->next = NULL;
             do{
                 q = p->next;
                 p->next = L->next;
                 L->next = q;
             }while(p!=NULL);
         }
     }
    
     def Reverse(L):
         p = L.head
         q = p.next
         p.next = None
         while q is not None:
             s = q.next
             q.next = p.next
             p.next = q
             q = s
    
  5. 已知有一个指针指向单链表中的某个结点,以尽可能快的方式删除这个结点。

     void Delete(Node* s, ElemType e){
         e = s->data;
         s->data = s->next->data;
         s->next = s->next->next;
     }
    
     def Delete_one(L, s):
         s.data = s.next.data
         s.next = s.next.next
    
  6. 编写递归算法,求单链表长度(无头结点)

     int Length(LinkList L){
         if(L==NULL){
             return 0;
         }else{
             return Length(L->next) + 1;
         }
     }
    
     def Length(L):
         if L is None:
             return 0
         else:
             return 1 + Length(L.next)
    
  7. 编写递归算法,释放单链表的空间(无头结点)

     void free(LinkList &L){
         if (L!=NULL){
             Delete(L->next);
             free(L);
             L = NULL;
         }
     }
    
  8. 编写递归算法,逆序输出单链表(无头结点)

     void Write(LinkList L){
         if(L != NULL){
             Write(L->next);
             printf(L->data);
         }
     }
    
     def Write(L):
         if L is not None:
             Write(L.next)
             print(L.data, end=" ")
    
  9. 编写递归算法,判断单链表中是否有元素的值和位序相等的元素(无头结点)

     void Exsist(LinkList L, int position){
         if (L==NULL){
             return False;
         }else if(L->data == position){
             return True;
         }else{
             return Exsist(L->next, position+1);
         }
     }
    
     def Exsist(L, position):
         if L is None:
             return False
         elif L.data == position:
             return True
         else:
             return Exsist(L.next, position+1)
    

常量和类型定义

typedef struct BiNode{
    ElemType data;
    struct BiNode* lchild;
    struct BiNode* rchild;
}BiNode, *BiTree;

typedef struc CSNode{
    ElemType data;
    struct CSNode* firstchild;
    struct CSNode* nextsibling;
}CSNode, *CSTree;

创建和生成二叉树

  1. 从控制台输入生成二叉树

    • 不是先、中、后、层序创建,而是一种类似层序的,从上到下,从左到右的创建过程。具体是:从根开始a开始,创左子树b,再创b的左子树,如果b的左子树为空,返回空,再接着创建b的右子树。图解如下:

    从控制台创建二叉树的创建过程

     void create_BiTree(BiTree *T)
     {
         char ch;
         scanf("%d",&ch);
         if(ch=='#')
             *T = NULL;
         else
         {
             *T = (BiNode *)malloc(sizeof(BiNode));
             if(!T)
             {
                 printf("开辟内存失败\n");
                 exit(1);
             }
             (*T)->data = ch;
             creatBT(&(*T)->lchild);
             creatBT(&(*T)->rchild);
         }
     }
    
     def create_BiTree(bt=None): 
         x = input()
         if x is "#":
             bt = None
         else:
             bt = BiNode(x)
             bt.lchild = createBiTree(bt.lchild)
             bt.rchild = createBiTree(bt.rchild)
         return bt
    
  2. 根据一个层序序列的列表创建二叉树,相对于上一种方法,更直观一些。

     def create_BiTree2(T, lst, i):
         if i < len(lst):
             if lst[i] == '#':
                 return None
             else:
                 T = BiNode(lst[i])
                 T.lchild = create_BiTree2(T.lchild, lst, 2*i+1)
                 T.rchild = create_BiTree2(T.rchild, lst, 2*i+2)
                 return T
         return T
    

一些题目

  1. 二叉树不是树的特例

  2. 二叉树的五种基本形态

  3. 二叉树的中序序列(树的后根序列) + 任一个其他序列 唯一确定一个二叉树或树

    • 先序:根左右
    • 中序:左根右
    • 后序:左右根
    • 逆中序:右根左
    • 逆后序:根右左
    • 树的后根序列即对应二叉树的中序序列
  4. 递归遍历二叉树

     void PreOrder(BiTree T){
         visit(*T);
         PreOrder(T->lchild);
         PreOrder(T->rchild);
     }
    
    
     def PreOrder(T):
         if T is not None:
             print(T.data, end=" ")
             PreOrder(T.lchild)
             PreOrder(T.rchild)
    
  5. 非递归先序遍历二叉树

     void PreOrder(BiTree T){
         InitStack(s);
         Push(s, NULL);
         p=T
         while(p!=NULL){
             while(p!=NULL){
                 visit(*T);
                 if(p->rchild!=NULL){
                     Push(s, p);
                 }
                 p = p->lchild;
             }
             Pop(s, p);
         }
     }
    
     def PreOrder2(T):
         S = []
         S.append(None)
         p = T
         while p is not None:
             while p is not None:
                 print(p.data, end=" ")
                 if p.rchild is not None:
                     S.append(p.rchild)
                 p = p.lchild
             p = S.pop()
    
  6. 删除子树,释放占用的空间

     void Delete(BiTree &T){
         if(T!=NULL){
             Delete(T->lchild);
             Delete(T->rchild);
             free(T);
             T=NULL;
         }
     }
    
  7. 判断两棵二叉树是否相似/镜像/相等

     Status Similar(BiTree T1, BiTree T2){
         if (T1==NULL && T2==NULL){
             return True;
         }else if(T1==NULL && T2!=NULL){
             return False;
         }else if(T1!=NULL && T2==NULL){
             return False;
         }else{
             return Similar(T1->lchild, T2->lchild) && Similar(T1->rchild, T2->rchild);
         }
     }
    
     def Similar(T1, T2):
         if T1 is None and T2 is None:
             return True
         elif T1 is None or T2 is None:
             return False
         else:
             return Similar(T1.lchild, T2.lchild) and Similar(T1.rchild, T2.rchild)
    
  8. 交换一个二叉树的左右子树

     void Swap(BiTree T){
         Swap(T->lchild);
         Swap(T->rchild);
         temp = T->lchild;
         T->lchild = T->rchild;
         T->rchild = temp;
     }
    
     def Swap(T):
         if T is not None:
             Swap(T.lchild)
             Swap(T.rchild)
             T.lchild, T.rchild = T.rchild, T.lchild
    
  9. 求一个二叉树的高度(利用二叉树的五种形态)

     int Depth(BiTree T){
         if(T==NULL){
             return 0;
         }else{
             return 1 + max(Depth(T->lchild), Depth(T->rchild));
         }
     }
    
     def Height(T):
         if T is None:
             return 0
         else:
             return 1 + max(Height(T.lchild), Height(T.rchild))
    
  10. 求一个二叉树的高度(利用带一个参数遍历的方法)

    void Depth(BiTree T, int level, int &d){
        if(T!=NULL){
            if(level > d){
                d = level;
            }
            Depth(T->lchild, level+1, d);
            Depth(T->rchild, level+1, d);
        }
    }
    
    def Depth(T, level, lst):
        if T is not None:
            if level > lst[0]:
                lst[0] = level
            Depth(T.lchild, level+1, lst)
            Depth(T.rchild, level+1, lst)
    
  11. 求二叉树度为0的结点(叶子结点)个数

    int Count(BiTree T){
        if(T==NULL){
            return 0;
        }else if(T->lchild==NULL && T->rchild==NULL){
            return 1;
        }else{
            return Count(T->lchild) + Count(T->rchild);
        }
    }
    
    def Count(T):
        if T is None:
            return 0
        elif T.lchild is None and T.rchild is None:
            return 1
        else:
            return Count(T.lchild) + Count(T.rchild)
    
  12. 求二叉树度为1的结点

    int Count(BiTree T){
        if (T==NULL){
            return 0;
        }else if(T->lchild!=NULL && T->rchild==NULL){
            return 1 + Count(T->lchild);
        }else if(T->lchild==NULL && T->rchild!=NULL){
            return 1 + Count(T->rchild);
        }else{
            return Count(T->lchild) + Count(T->rchild);
        }
    }
    
    def Count2(T):
        if T is None:
            return 0
        elif T.lchild is None and T.rchild is not None:
            return 1
        elif T.lchild is not None and T.rchild is None:
            return 1
        else:
            return Count2(T.lchild) + Count2(T.rchild)
    
  13. 将一棵二叉树根朝左,躺倒打印出来(见严蔚敏习题集)

    • 逆中序遍历次序决定行数
    • 结点所在的层数决定列数
    void Print(BiTree T, int level){
        if(T!=NULL){
            Write(T->rchild, level+1);
            for(int i=0; i<level; i++){
                printf(" ");
            }
            printf(T->data);
            printf("\n");
            Write(T->lchild, level+1);
        }
    }
    
    def Write(T, level):
        if T is not None:
            Write(T.rchild, level+1)
            for i in range(level):
                print("   ", end="")
            print(T.data)
            Write(T.lchild, level+1)
    
  14. 统计一棵由孩子兄弟链表表示的树中,叶子的个数

    即统计没有firstchild的结点个数

    int Count(CSTree T){
        if(T==NULL){
            return 0;
        }else if(T->firstChild==NULL){
            return 1 + Count(T->nextsibling);
        }else{
            return Count(T->firstchild) + Count(T->nextsibling);
        }
    }
    
    def Count3(T):
        if T is None:
            return 0
        elif T.lchild is None:
            return 1 + Count3(T.rchild)
        else:
            return Count3(T.lchild) + Count3(T.rchild)
    
  15. 统计一棵由孩子兄弟链表表示的树,树的度为多少

    即统计↘方向的结点个数

    void Count(CSTree T, int &d){
        if(T!=NULL){
            p = T->firstchild;
            if(p != NULL){
                n = 1;
                while(p!-=NULL){
                    n++;
                    p=p->next;
                }
                if(n > d){
                    d = n;
                } 
            }
            Count(T->lchild, d);
            Count(T->rchild, d);
        }
    }
    
  16. 求树/森林的深度

    int Depth(CSTree T){
        if(T==NULL){
            return 0;
        }else{
            return max(1 +Depth(T->firstchild), Depth(T->nextsibling));
        }
    }
    
  17. 判断一棵二叉树是否中序有序(判断一个二叉排序树是否合法)

    Status BST(BiTree T, BiTree &pre){
        // pre指向被访问的结点的中序前驱
        if (T==NULL){
            return True;
        }else{
            if(BST(T->lchild, pre) == False){
                return False;
            }
            if(pre != NULL && T->data <= pre.data){
                return False;
            }
            pre = T;
            return BST(T->rchild, pre);
        }
    }
    
    
    # 用一个全局变量pre
    
    def BST(T):
        global pre
        if pre is not None:
            print(pre.data)
        if T is None:
            return True
        else:
            if not BST(T.lchild):
                return False
            if pre is not None and T.data < pre.data:
                return False
            pre = T
            return BST(T.rchild)
    
    # 用一个引用型变量pre_lst
        
    def BST2(T, pre_lst):
        if T is None:
            return True
        else:
            if not BST2(T.lchild, pre_lst):
                return False
            if pre_lst[0] is not None and T.data < pre_lst[0].data:
                return False
            pre_lst[0] = T
            return BST2(T.rchild, pre_lst)
    
  18. 将一个结点插入一个二叉排序树

    void InsertBST(BiTree &T, BiNode* p){
        if(T==NULL){
            T = p;
        }else if(p->data < T->data){
            InsertBST(T->lchildb, p);
        }else if(p->data > T->data){
            InsertBST(T->rchild, p);
        }else{
            free(p);
        }
    }
    

常量和类型定义

邻接表存储表示

#define MAX_SIZE 100
typedef struct ArcNode{
    int adjvex;
    struct ArcNode* nextarc;
}ArcNode;
typedef struct VNode{
    Elemtype data;
    ArcNode* firstarc;
}VNode;
typedef struct Graph{
    Graph[MAX_SIZE] vertices;
    int vexnum, arcnum;
}
class ArcNode:
    def __init__(self, adjvex, nextarc, weight):
        self.adjvex = adjvex   # 这条边指向谁
        self.nextarc = nextarc  # 下一条边是哪个
        self.weight = weight  # 边的权值


class VNode:
    def __init__(self, index, data, firstarc):
        self.index = index   # 顶点的编号
        self.data = data   # 顶点的数据
        self.firstarc = firstarc  # 指向第一条边


class Graph:
    def __init__(self, vertices, vexnum, arcnum):
        self.vertices = vertices  # VNode组成的列表
        self.vexnum = vexnum  # 顶点数
        self.arcnum = arcnum  # 边数

class ArcNode{
    int weight; // 边的权重
    int vexIndex; // 这条边指向的节点 的编号
    ArcNode nextArc;  // 下一条边
    ArcNode(int weight, int adjVex, ArcNode nextArc){
        this.weight = weight;
        this.vexIndex = vexIndex;
        this.nextArc = nextArc;
    }
}

class VNode{
    int index;  // 节点的编号
    String data;  // 节点的数据
    ArcNode firstArc;  // 从这个点出发的第一条边
    VNode(int index, String data, ArcNode firstArc){
        this.index = index;
        this.data = data;
        this.firstArc = firstArc;
    }
}

class Graph{
    int vexNum;
    int arcNum;
    VNode[] vertices;
    Graph(int vexNum, int arcNum, VNode[] vertices){
        this.vexNum = vexNum;
        this.arcNum = arcNum;
        this.vertices = vertices;
    }
}

一些题目

  1. 采用深度优先遍历的方法,判断是否存在从i号结点到j号结点的路径

Status DFS(Graph G, int i, int j, Status visited[], Status &found){
    ArcNode *p;
    visisted[i] = True;
    if(i==j){
        found = True;
    }else{
        p = G.vertices[i].firstarc;
        while(!found && p!=NULL){
            if(!visited[p->adjvex]){
                DFS(G, p->adjvex, j, visited, found);
            }
            p = p->nextarc;
        }
    }
}
Status Path(Graph G, int i, int j){
    Status visited[MAx_SIZE];
    Status found;
    for(int k=0; k<G.vexnum; k++){
        visited[k] = False;
    }
    found = False;
    DFS(G, i, j, visited, found);
    return found;
}


def dfs(G, i, j, visited, found):
    visited[i] = True
    if i == j:
        found[0] = True
    else:
        p = G.vertices[i].firstarc
        while not found[0] and p is not None:
            if not visited[p.adjvex]:
                dfs(G, p.adjvex, j, visited, found)
            p = p.nextarc

def path(G, i, j):
    visited = [False for i in range(G.vexnum)]
    found= [False]
    dfs(G, i, j, visited, found)
    return found[0]



if __name__ == "__main__":
    INF = float('inf')
    adj = [[0,8,INF,5,INF],   # 先用邻接表表示
            [INF,0,3,INF,INF],
            [INF,INF,0,INF,6],
            [INF,INF,9,0,INF],
            [INF,INF,INF,INF,0]]

    # 将邻接表表示的图存储在邻接链表里
    vertices = []
    vexnum = len(adj)
    for i in range(len(adj)):  # 初始化顶点列表
        vertices.append(VNode(i, "顶点"+str(i)+"的data", None))

    arcnum = 0
    for i in range(len(vertices)):
        v = vertices[i]
        p = None
        for j in range(len(adj[v.index])):
            weight = adj[i][j]
            if 0 < weight < INF:
                arcnum += 1
                if p is not None:
                    p.nextarc = ArcNode(j, None, weight)
                else:
                    p = ArcNode(j, None, weight)
                    vertices[i].firstarc = p


    G = Graph(vertices, vexnum, arcnum)

    print(G.vexnum)
    print(G.arcnum)

    print(path(G, 0, 4))
    print(path(G, 1, 3))