C/C++ 資料結構與算法筆記

實作順序表

#include <stdio.h>
#include <stdlib.h>

#define MaxSize 10

int Insert_Elem(int Array[], int *len, int ins, int val)
{
  // 首先來判斷,是否是非法插入
  if (*len == MaxSize || ins < 1 || ins > *len + 1)
    return -1;

  int x;

  for (x = *len - 1; x >= ins - 1; x--)
    Array[x + 1] = Array[x];

  Array[x - 1] = val;      // 插入元素
  *len = *len + 1;         // 表長度自增

  return 1;
}

int main(int argc,char * argv[])
{
  int Array[MaxSize] = { 1, 2, 3, 4, 5 };
  int array_len = 5;           // 數組目前長度

  Insert_Elem(Array, &array_len, 2, 10);  // 在第二個位置插入一個10

  system("pause");
  return 0;
}      

實作連結清單結構

什麼是靜态連結清單？ 一個案例解決疑問.

#include <stdio.h>

struct LinkList
{
  int data;
  char *name;
  struct LinkList *next;
};

int main(int argc,char * argv[])
{
  struct LinkList node1 = { 10, "lyshark",NULL };
  struct LinkList node2 = { 20, "admin",NULL };
  struct LinkList node3 = { 30, "lyshark",NULL };

  node1.next = &node2;
  node2.next = &node3;
  node3.next = NULL;

  struct LinkList *ptr = &node1;
  while (ptr != NULL)
  {
    printf("%d \n", ptr->data);
    printf("%s \n", ptr->name);
    ptr = ptr->next;
  }

  system("pause");
  return 0;
}      

簡單的實作靜态順序表：此種簡單的順序表結構并不靈活，因為其無法動态開辟空間。

#include <stdio.h>
#define MaxSize 10

//參數1：傳遞順序表的首位址
//參數2：len表的長度
//參數3：插入元素的位置
//參數4：待插入的元素值
int InsertElem(int list[], int *len, int x, int y)
{
  if (*len == MaxSize || x < 1 || x > *len + 1)
    return 0;
  for (int z = *len - 1; z >= x - 1; z--)
    list[z + 1] = list[z];
  list[x - 1] = y;
  *len = *len + 1;
  return 1;
}
//參數1：傳遞順序表的首位址
//參數2：len表的長度
//參數3：待删除元素的位置
int DeleteElem(int list[], int *len, int x)
{
  int y;
  if (x < 1 || x >len)
    return 0;
  for (y = x; y <= *len - 1; y++)
    list[y - 1] = list[y];
  *len = *len - 1;
  return 1;
}

int main()
{
  int Sqlist[MaxSize] = {1,2,3,4,5};
  int ListLen = 5;

  for (int x = 0; x < ListLen; x++)
    printf_s("%d ", Sqlist[x]);
  printf_s("\n得到目前數組長度：%d\n", MaxSize - ListLen);

  InsertElem(Sqlist, &ListLen, 3, 100);
  DeleteElem(Sqlist, ListLen, 4);

  for (int x = 0; x < ListLen; x++)
    printf_s("%d ", Sqlist[x]);
  printf_s("\n得到目前數組長度：%d\n", MaxSize - ListLen);
  getchar();
  return 0;
}      

實作動态順序表,可動态生成資料.

#include <stdio.h>
#define MaxSize 10
typedef int ElemType;

typedef struct{
  int *elem;
  int length;
  int size;
}list;

int InitList(list *mem)
{
  mem->elem = (int *)malloc(MaxSize*sizeof(ElemType));
  if (!mem->elem)exit(0);
  mem->length = 0;
  mem->size = MaxSize;
  if (mem->elem != 0)
    return 1;
}

// 參數1：mem類型的指針基位址
// 參數2：i插入元素的位置
// 參數3：item待插入的元素
void InsertElem(list *mem, int i, ElemType item)
{
  ElemType *base, *insertPtr, *p;
  if (i<1 || i>mem->length + 1)exit(0);
  if (mem->length >= mem->size)
  {
    // 說明我們的連結清單滿了,需要追加開辟空間
    base = (ElemType*)realloc(mem->elem, (mem->size + 10)*sizeof(ElemType));
    mem->size = mem->size + 50;
  }
  insertPtr = &(mem->elem[i - 1]); // 取出第二個元素位置位址
  for (p = &(mem->elem[mem->length - 1]); p >= insertPtr; p--)
    *(p + 1) = *p;
  *insertPtr = item;
  mem->length++;
}

// 參數1：mem類型的指針基位址
// 參數2：删除元素的位置
void DeleteElem(list *mem, int i)
{
  ElemType *delItem, *p;
  if (i<1 || i>mem->length)
    exit(0);
  delItem = &(mem->elem[i - 1]);
  p = mem->elem + mem->length - 1;
  for (++delItem; delItem <= p; ++delItem)
    *(delItem - 1) = *delItem;
  mem->length--;
}

int main()
{
  list temp;
  InitList(&temp);
  for (int x = 1; x < 15; x++)
    InsertElem(&temp, x, x );             // 插入1-15
  for (int x = 0; x < temp.length; x++)     // 列印1-15 
    printf("%d ", temp.elem[x]);
  // 删除第三個位置的數值
  DeleteElem(&temp, 3);
  // 列印出删除後的結果
  for (int x = 0; x < temp.length; x++)
    printf("\n%d ", temp.elem[x]);
  getchar();
  return 0;
}      

實作單向連結清單：

#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;
typedef struct node{
  ElemType data;
  struct node *next;
}LinkNode, *LinkList;

// 初始化一個連結清單
LinkList InitLinkList()
{
  LinkList ptr,list = NULL;
  ptr = (LinkList)malloc(sizeof(LinkNode));
  ptr->data = 0;       // 初始化第一個元素始終為0
  ptr->next = NULL;
  if (!list)
    list = ptr;
  return list;
}
// 向連結清單中指針offset指向節點的後面插入新節點,并指派為number
void InsertLinkList(LinkList *list, LinkList offset, ElemType number)
{
  LinkList ptr;
  ptr = (LinkList)malloc(sizeof(LinkNode));
  ptr->data = number;
  ptr->next = offset->next;
  offset->next = ptr;
}
// 删除連結清單中的指定位置中的元素
void DeleteLinkList(LinkList *list, LinkList offset)
{
  LinkList temp;
  if (offset == list){
    *list = offset->next;
    free(offset);
  }
  else
  {
    for (temp = *list; temp->next != offset; temp = temp->next);
      if (temp->next != NULL){
        temp->next = offset->next;
        free(offset);
      }
    }
}
// 銷毀連結清單
void DestroyLinkList(LinkList *list)
{
  LinkList Ptr, temp;
  Ptr = *list;
  while (Ptr)
  {
    temp = Ptr->next;
    free(Ptr);
    Ptr = temp;
  }
  *list = NULL;
}

int main()
{
  LinkList forc, ListPtr;
  ListPtr = InitLinkList(); // 初始化連結清單

  forc = ListPtr;
  for (int i = 0; i < 10;i++)
  { // 寫入0-10
    InsertLinkList(&ListPtr, forc, i);
    forc = forc->next;
  }

  forc = ListPtr;
  while (forc)
  { // 循環周遊連結清單節點
    printf("連結清單節點中的資料：%d \n", forc->data);
    forc = forc->next;
  }

  forc = ListPtr;
  for (int i = 0; i < 4; i++)    // 移動指針 
    forc = forc->next;
  DeleteLinkList(&ListPtr, forc);// 删除第4個位置上的元素

  DestroyLinkList(&ListPtr);  // 銷毀連結清單
  getchar();
  return 0;
}      

另一種實作方式（連結清單）

#include <stdio.h>
#include <stdlib.h>

// 定義連結清單節點類型
struct LinkNode
{
  int data;
  struct LinkNode *next;
};

struct LinkNode *init_link()
{  // 建立一個頭結點,頭結點不需要添加任何資料
  struct LinkNode *header = malloc(sizeof(struct LinkNode));
  header->data = 0;
  header->next = NULL;

  struct LinkNode *p_end = header;    // 建立一個尾指針

  int val = -1;
  while (1)
  {
    scanf("%d", &val);  // 輸入插入的資料
    if (val == -1)      // 如果輸入-1說明輸入結束了
      break;

    // 先建立新節點
    struct LinkNode *newnode = malloc(sizeof(struct LinkNode));
    newnode->data = val;
    newnode->next = NULL;

    // 将節點插入到連結清單中
    p_end->next = newnode;
    // 更新尾部指針指向
    p_end = newnode;
  }
  return header;
}

// 周遊連結清單
int foreach_link(struct LinkNode *header)
{
  if (NULL == header || header->next == NULL)
    return 0;

  while (header->next != NULL)
  {
    printf("%d \n", header->data);
    header = header->next;
  }
  return 1;
}

// 在header節點中oldval插入資料
void insert_link(struct LinkNode *header,int oldval,int newval)
{
  struct LinkNode *pPrev = header;
  struct LinkNode *Current = pPrev->next;

  if (NULL == header)
    return;


  while (Current != NULL)
  {
    if (Current->data == oldval)
      break;

    pPrev = Current;
    Current = Current->next;
  }
  // 如果值不存在則預設插入到尾部
  //if (Current == NULL)
  //  return;

  // 建立新節點

  struct LinkNode *newnode = malloc(sizeof(struct LinkNode));
  newnode->data = newval;
  newnode->next = NULL;

  // 新節點插入到連結清單中
  newnode->next = Current;
  pPrev->next = newnode;
}

// 清空連結清單
void clear_link(struct LinkNode *header)
{
  // 輔助指針
  struct LinkNode *Current = header->next;

  while (Current != NULL)
  {
    // 儲存下一個節點位址
    struct LinkNode *pNext = Current->next;
    printf("清空資料: %d \n", Current->data);
    free(Current);
    Current = pNext;
  }
  header->next = NULL;
}

// 删除值為val的節點
int remove_link(struct LinkNode *header, int delValue)
{
  if (NULL == header)
    return;

  // 設定兩個指針,指向頭結點和尾結點
  struct LinkNode *pPrev = header;
  struct LinkNode *Current = pPrev->next;

  while (Current != NULL)
  {
    if (Current->data == delValue)
    {
      // 删除節點的過程
      pPrev->next = Current->next;
      free(Current);
      Current = NULL;
    }
  }

  // 移動兩個輔助指針
  pPrev = Current;
  Current = Current->next;
}

// 銷毀連結清單
void destroy_link(struct LinkNode *header)
{
  if (NULL == header)
    return;

  struct LinkNode *Curent = header;
  while (Curent != NULL)
  {
    // 先來儲存一下下一個節點位址
    struct LinkNode *pNext = Curent->next;

    free(Curent);

    // 指針向後移動
    Curent = pNext;
  }
}

// 反響排序
void reverse_link(struct LinkNode *header)
{
  if (NULL == header)
    return;

  struct LinkNode *pPrev = NULL;
  struct LinkNode *Current = header->next;
  struct LinkNode * pNext = NULL;

  while (Current != NULL)
  {
    pNext = Current->next;
    Current->next = pPrev;

    pPrev = Current;
    Current = pNext;
  }
  header->next = pPrev;
}


int main(int argc, char* argv[])
{
  struct LinkNode * header = init_link();

  reverse_link(header);
  foreach_link(header);

  clear_link(header);
  system("pause");
  return 0;
}      

簡單的連結清單

LinkList.c

#include"LinkList.h"


//初始化連結清單
struct LinkNode *Init_LinkList()
{

  //建立頭結點
  struct LinkNode *header = malloc(sizeof(struct LinkNode));
  header->data = - 1;
  header->next = NULL;

  //尾部指針
  struct LinkNode *pRear = header;

  int val = -1;
  while (true)
  {

    printf("輸入插入的資料:\n");
    scanf("%d",&val);
    if (val == -1)
    {
      break;
    }

    //先建立新節點
    struct LinkNode *newnode = malloc(sizeof(struct LinkNode));
    newnode->data = val;
    newnode->next = NULL;

    //新節點插入到連結清單中
    pRear->next = newnode;

    //更新尾部指針指向
    pRear = newnode;


  }

  return header;
}

void InsertByValue_LinkList(struct LinkNode *header, int oldval, int newval)
{
  if (NULL == header)
  {
    return;
  }


  //兩個輔助指針變量
  struct LinkNode *pPrev = header;
  struct LinkNode *pCurrent = pPrev->next;

  while (pCurrent != NULL)
  {

    if (pCurrent->data == oldval)
    {
      break; 
    }

    pPrev = pCurrent;
    pCurrent = pCurrent->next;
  }

#if 0
  //如果pCurrent為NULL  說明連結清單中不存在值為oldval的結點
  if (pCurrent == NULL)
  {
    return;
  }
#endif


  //先建立新結點
  struct LinkNode *newnode = malloc(sizeof(struct LinkNode));
  newnode->data = newval;
  newnode->next = NULL;

  //新節點插入到連結清單中
  newnode->next = pCurrent;
  pPrev->next = newnode;



}
//删除值為val的結點
void RemoveByValue_LinkList(struct LinkNode *header, int delValue)
{

  if (NULL == header)
  {
    return;
  }

  //兩個輔助指針變量
  struct LinkNode *pPrev = header;
  struct LinkNode *pCurrent = pPrev->next;

  while (pCurrent != NULL)
  {

    if (pCurrent->data == delValue)
    {
      break;
    }

    //移動兩個輔助指針
    pPrev = pCurrent;
    pCurrent = pCurrent->next;
  }

  if (NULL == pCurrent)
  {
    return;
  }

  //重建立立待删除節點的前驅和後繼結點關系
  pPrev->next = pCurrent->next;
  //釋放删除節點記憶體
  free(pCurrent);
  pCurrent = NULL;

}
//周遊
void Foreach_LinkList(struct LinkNode *header)
{
  if (NULL == header)
  {
    return;
  }

  //輔助指針變量
  struct LinkNode *pCurrent = header->next;

  while (pCurrent != NULL)
  {
    printf("%d ",pCurrent->data);
    pCurrent = pCurrent->next;
  }

}
//銷毀
void Destroy_LinkList(struct LinkNode *header)
{
  if (NULL == header)
  {
    return;
  }

  //輔助指針變量
  struct LinkNode *pCurrent = header;

  while (pCurrent != NULL)
  {
    //先儲存下目前結點的下一個節點位址
    struct LinkNode *pNext = pCurrent->next;

    //釋放目前結點記憶體
    printf("%d節點被銷毀!\n", pCurrent->data);
    free(pCurrent);

    //指針向後移動
    pCurrent = pNext;

  }

}
//清空
void Clear_LinkList(struct LinkNode *header)
{
  if (NULL == header)
  {
    return;
  }


  //輔助指針變量
  struct LinkNode *pCurrent = header->next;

  while (pCurrent != NULL)
  {

    //先儲存下目前結點的下一個節點位址
    struct LinkNode *pNext = pCurrent->next;

    //釋放目前結點記憶體
    free(pCurrent);

    //pCurrent指向下一個節點
    pCurrent = pNext;

  }

  header->next = NULL;

}      

linklist.h

#define _CRT_SECURE_NO_WARNINGS

#pragma once

#include<stdlib.h>
#include<stdbool.h>
#include<stdio.h>

#ifdef __cplusplus
extern "C"{
#endif


  //定義節點資料類型
  struct LinkNode
  {
    int data;
    struct LinkNode *next;
  };

  //初始化連結清單
  struct LinkNode *Init_LinkList();
  //在值為oldval的位置插入新的資料newval
  void InsertByValue_LinkList(struct LinkNode *header,int oldval,int newval);
  //删除值為val的結點
  void RemoveByValue_LinkList(struct LinkNode *header,int delValue);
  //周遊
  void Foreach_LinkList(struct LinkNode *header);
  //銷毀
  void Destroy_LinkList(struct LinkNode *header);
  //清空
  void Clear_LinkList(struct LinkNode *header);

#ifdef __cplusplus
}
#endif      

main.c

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include"LinkList.h"

void test()
{
  //初始化連結清單 100 200 666 300 400 500 600
  struct LinkNode *header =  Init_LinkList();
  //列印連結清單
  Foreach_LinkList(header);
  //插入資料
  InsertByValue_LinkList(header, 200, 666);
  //列印連結清單
  printf("\n-------------------\n");
  Foreach_LinkList(header);

  //清空連結清單
  Clear_LinkList(header);
  //列印連結清單

  InsertByValue_LinkList(header, 1000, 111);
  InsertByValue_LinkList(header, 1000, 211);
  InsertByValue_LinkList(header, 1000, 311);
  InsertByValue_LinkList(header, 1000, 411);

  printf("\n-------------------\n");
  Foreach_LinkList(header);


  RemoveByValue_LinkList(header,311);
  printf("\n-------------------\n");
  Foreach_LinkList(header);

  RemoveByValue_LinkList(header, 211);
  printf("\n-------------------\n");
  Foreach_LinkList(header);

  //銷毀連結清單
  Destroy_LinkList(header);

}

int main(){

  test();

  system("pause");
  return EXIT_SUCCESS;
}      

StaticArray

#include <stdio.h>
#include <stdlib.h>

#define MaxSize 10
typedef int ElemType;

typedef struct{
  int *data;
  int current_size;
  int max_size;
}Dynamic_Array;

// 初始化動态數組,傳遞進來一個數組首位址
int Init_Dynamic_Array(Dynamic_Array *Array)
{
  Array->data = (int *)malloc(MaxSize * sizeof(ElemType));
  if (!Array->data)                    // 判斷malloc是否配置設定成功
    return 0;

  Array->current_size = 0;             // 初始化元素個數
  Array->max_size = MaxSize;           // 初始化最大存儲個數

  if (Array->data != 0)                // 數組配置設定成功則傳回1
    return 1;
  return 0;
}

// 參數1: Array = > 數組元素指針基位址
// 參數2: ins => 待插入元素的位置
// 參數3: val => 待插入的元素
int Insert_Dynamic_Array(Dynamic_Array *Array, int ins, ElemType val)
{
  ElemType *base, *insertPtr, *p;

  // 判斷如果插入元素位置小于開頭,或者大于結尾,則直接傳回錯誤
  if (ins < 0 || ins > Array->current_size + 1)
    return 0;

  if (Array->current_size >= Array->max_size)
  {
    // 如果循環到這裡,說明我們的存儲空間滿了,需要配置設定一塊更大的空間
    base = (ElemType*)realloc(Array->data, (Array->max_size + 10)*sizeof(ElemType));
    Array->max_size = Array->max_size + 40;       // 長度遞增
  }
  // 取出第二個元素的位置,insertPtr為插入元素的位置
  insertPtr = &(Array->data[ins - 1]);

  // 循環指針,為待插入元素空出一個空間,指針後移操作
  for (p = &(Array->data[Array->current_size - 1]); p >= insertPtr; p--)
    *(p + 1) = *p;           // 将ins以後的元素全部後移一個機關
  *insertPtr = val;            // 在第ins個位置上插入元素val
  Array->current_size++;     // 目前元素數遞增
  return 1;
}

// 參數1: Array = > 數組元素指針基位址
// 參數2: ins => 待删除元素的位置
int Delete_Dynamic_Array(Dynamic_Array *Array, int ins)
{
  ElemType *delItem, *p;
  if (ins < 0 || ins>Array->current_size)
    return 0;

  delItem = &(Array->data[ins - 1]);              // delItem指向第ins個元素
  p = Array->data + Array->current_size - 1;      // p指向表尾部

  for (++delItem; delItem <= p; ++delItem)        // 從表位向前,ins位置以後的元素依次前移
    *(delItem - 1) = *delItem;

  Array->current_size--;
  return 0;
}

int main(int argc, char * argv[])
{
  Dynamic_Array MyArray;

  // 初始化數組,并儲存首位址到MyArray
  Init_Dynamic_Array(&MyArray);

  // 插入測試資料
  for (int x = 0; x <= 20; x++)
    Insert_Dynamic_Array(&MyArray, x, x);

  // 删除元素中的 1,3,5 這幾個位置
  Delete_Dynamic_Array(&MyArray, 1);
  Delete_Dynamic_Array(&MyArray, 3);
  Delete_Dynamic_Array(&MyArray, 5);

  // 循環删除後的資料
  for (int x = 0; x < MyArray.current_size - 1; x++)
    printf("%d ", MyArray.data[x]);

  system("pause");
  return 0;
}      

DynamicArray

dynamice.h

#pragma once

#include<stdlib.h>
#include<string.h>

#ifdef __cplusplus
extern "C"{
#endif
  struct DynamicArray
  {
    void **addr;   // 存放元素或結構體的首位址
    int curr_size; // 存放目前元素數量
    int max_size;  // 存放目前最大元素數
  };
  struct DynamicArray *Init_DynamicArray(int size);
  void Insert_DynamicArray(struct DynamicArray *ptr, int index, void *data);
  void Foreach_DynamicArray(struct DynamicArray *ptr, void(*_callback)(void *));
  void RemoveByPos_DynamicArray(struct DynamicArray *ptr, int index);
  void RemoveByValue_DynamicArray(struct DynamicArray *ptr, void *data, int(*compare)(void*, void *));
  void Destroy_DynamicArray(struct DynamicArray *ptr);
#ifdef __cplusplus }
#endif      

#include"DynamicArray.h"

// 初始化動态數組,初始化後直接傳回數組的首位址
struct DynamicArray *Init_DynamicArray(int size)
{
  // 如果小于0則說明沒有元素,傳回NULL
  if (size <= 0)
    return NULL;

  // 配置設定結構指針,此處配置設定的是結構體指針,并沒有配置設定空間
  struct DynamicArray *ptr = malloc(sizeof(struct DynamicArray));
  if (ptr != NULL)
  {
    ptr->curr_size = 0;              // 将目前元素索引設定為0
    ptr->max_size = size;            // 預設最大數組元素數為size
    // 實際配置設定存儲空間：大小是max_size 最大元素
    ptr->addr = malloc(sizeof(void *) * ptr->max_size);
    return ptr;
  }
  return NULL;
}

// 将元素插入到指定位置
// 參數1: 傳入數組首位址
// 參數2: 傳入要插入元素位置
// 參數3: 傳入插入的元素或結構
void Insert_DynamicArray(struct DynamicArray *ptr, int index, void *data)
{
  // 判斷如果數組不為空,或者是data不為空,則繼續執行
  if (ptr != NULL || data != NULL)
  {
    // 如果插入位置小于目前0,或者大于目前元素總個數
    if (index < 0 || index > ptr->curr_size)
    {
      // 就自動把它插入到元素的末尾位置
      index = ptr->curr_size;
    }

    // 緊接着判斷目前元素數是否大于最大值,大于則配置設定空間
    if (ptr->curr_size >= ptr->max_size)
    {
      // 配置設定一塊更大的空間,這裡配置設定原始空間的2倍
      int new_max_size = ptr->max_size * 2;
      void **new_space = malloc(sizeof(void *) * new_max_size);

      // 接着将原來空間中的資料拷貝到新配置設定的空間
      memcpy(new_space, ptr->addr, sizeof(void *) * ptr->max_size);

      // 釋放原來的記憶體空間,并更新指針的指向為新空間的位址
      free(ptr->addr);
      ptr->addr = new_space;
      ptr->max_size = new_max_size;
    }

    // 開始移動元素,給ins元素騰出空來
    for (int x = ptr->curr_size - 1; x >= index; --x)
    {
      // 從後向前,将前一個元素移動到後一個元素上
      ptr->addr[x + 1] = ptr->addr[x];
    }
    // 設定好指針以後,開始指派
    ptr->addr[index] = data;
    ptr->curr_size++;
    return 1;
  }
  return 0;
}

// 周遊數組中的元素,這裡的回調函數是用于強制類型轉換,自定義輸出時使用
void Foreach_DynamicArray(struct DynamicArray *ptr, void(*_callback)(void *))
{
  if (ptr != NULL || _callback != NULL)
  {
    for (int x = 0; x < ptr->curr_size; x++)
    {
      // 調用回調函數并将數組指針傳遞過去
      _callback(ptr->addr[x]);
    }
  }
}

// 根據位置删除指定元素,index = 元素的下标位置
void RemoveByPos_DynamicArray(struct DynamicArray *ptr, int index)
{
  if (ptr == NULL)
    return NULL;

  // 判斷目前插入位置index必須大于0且小于curr_size
  if (index > 0 || index < ptr->curr_size - 1)
  {
    for (int i = index; i < ptr->curr_size - 1; ++i)
    {
      // 每次循環都将後一個元素覆寫到前一個元素上
      ptr->addr[i] = ptr->addr[i + 1];
    }
    ptr->curr_size--;   // 最後目前元素數量應該減去1
  }
}

// 按照元素的指定值進行元素删除,這裡需要回調函數指定要删除元素的值是多少
void RemoveByValue_DynamicArray(struct DynamicArray *ptr, void *data, int(*compare)(void*, void *))
{
  if (ptr != NULL && data != NULL && compare != NULL)
  {
    for (int i = 0; i < ptr->curr_size; ++i)
    {
      if (compare(ptr->addr[i], data))
      {
        RemoveByPos_DynamicArray(ptr, i);
        break;
      }
    }
  }
}

//銷毀數組
void Destroy_DynamicArray(struct DynamicArray *ptr)
{
  if (ptr != NULL)
  {
    if (ptr->addr != NULL)
    {
      free(ptr->addr);
      ptr->addr = NULL;
    }
    free(ptr);
    ptr = NULL;
  }
}      

#include<stdio.h>
#include"DynamicArray.h"

struct Student
{
  int uid;
  char name[64];
  int age;
};

// 回調函數用于輸出元素
void MyPrint(void *data)
{
  // 強制類型轉換,轉成我們想要的類型
  struct Student *ptr = (struct Student *)data;
  printf("Uid: %d --> Name: %s \n", ptr->uid, ptr->name);
}

// 回調函數用于對比元素
int myCompare(void *x, void *y)
{
  struct Student *p1 = (struct Student *)x;
  struct Student *p2 = (struct Student *)y;

  if (strcmp(p1->name, p2->name) == 0)
  {
    return 1;
  }
  return 0;
}

int main()
{
  //建立動态數組
  struct DynamicArray *ptr = Init_DynamicArray(5);

  // 建立元素
  struct Student stu1 = { 1001, "admin1", 22 };
  struct Student stu2 = { 1002, "admin2", 33 };
  struct Student stu3 = { 1003, "admin3", 44 };
  struct Student stu4 = { 1004, "admin4", 55 };

  // 将元素插入到數組
  Insert_DynamicArray(ptr, 0, &stu1);
  Insert_DynamicArray(ptr, 1, &stu2);
  Insert_DynamicArray(ptr, 3, &stu3);
  Insert_DynamicArray(ptr, 4, &stu4);

  RemoveByPos_DynamicArray(ptr, 0);     // 根據下标移除元素

  // 删除元素是 p_delete 的資料
  struct Student p_delete = { 1002, "admin2", 33 };
  RemoveByValue_DynamicArray(ptr, &p_delete, myCompare);

  Foreach_DynamicArray(ptr, MyPrint);   // 周遊元素
  Destroy_DynamicArray(ptr);            // 銷毀順序表

  system("pause");
  return EXIT_SUCCESS;
}      

LinkList

linklist.h

#pragma once

#include<stdlib.h>
#include<string.h>
#include<stdio.h>

#ifdef __cplusplus
extern "C"{
#endif

  typedef void * LinkList;
  typedef void(*FOREACH)(void *);
  typedef int(*COMPARE)(void *,void *);

  //初始化連結清單
  LinkList Init_LinkList();
  //插入節點
  void Insert_LinkList(LinkList list,int pos,void *data);
  //周遊連結清單
  void Foreach_LinkList(LinkList list, FOREACH myforeach);
  //按位置删除
  void RemoveByPos_LinkList(LinkList list,int pos);
  //按值删除
  void RemoveByVal_LinkList(LinkList list, void *data, COMPARE compare);
  //清空連結清單
  void Clear_LinkList(LinkList list);
  //大小
  int Size_LinkList(LinkList list);
  //銷毀連結清單
  void Destroy_LinkList(LinkList list);


#ifdef __cplusplus
}
#endif      

linklist.c

#include"LinkList.h"

//連結清單節點資料類型
struct LinkNode
{
  void *data;
  struct LinkNode *next;
};

//連結清單資料類型
struct LList
{
  struct LinkNode header;
  int size;
};



//初始化連結清單
LinkList Init_LinkList()
{
  struct LList *list = malloc(sizeof(struct LList));
  if (NULL == list)
  {
    return NULL;
  }

  list->header.data = NULL;
  list->header.next = NULL;
  list->size = 0;

  return list;
}
//插入節點
void Insert_LinkList(LinkList list, int pos, void *data)
{
  
  if (NULL == list)
  {
    return;
  }

  if (NULL == data)
  {
    return;
  }

  struct LList * mylist = (struct LList *)list;

  if (pos < 0 || pos > mylist->size)
  {
    pos = mylist->size;
  }

  //查找插入位置
  struct LinkNode *pCurrent = &(mylist->header);
  for (int i = 0; i < pos; ++i)
  {
    pCurrent = pCurrent->next;
  }

  //建立新節點
  struct LinkNode *newnode = malloc(sizeof(struct LinkNode));
  newnode->data = data;
  newnode->next = NULL;

  //新節點插入到連結清單中
  newnode->next = pCurrent->next;
  pCurrent->next = newnode;

  mylist->size++;
}


//周遊連結清單
void Foreach_LinkList(LinkList list, FOREACH myforeach) /*回調函數*/
{

  if (NULL == list)
  {
    return;
  }

  if (NULL == myforeach)
  {
    return;
  }

  struct LList * mylist = (struct LList *)list;

  struct LinkNode *pCurrent = mylist->header.next;

  while (pCurrent != NULL)
  {
    myforeach(pCurrent->data);
    pCurrent = pCurrent->next;
  }

}


//按位置删除
void RemoveByPos_LinkList(LinkList list, int pos)
{

  if (NULL == list)
  {
    return;
  }

  struct LList *mylist = (struct LList *)list;

  if (pos < 0 || pos > mylist->size - 1)
  {
    return;
  }


  //找位置
  struct LinkNode *pCurrent = &(mylist->header);
  for (int i = 0; i < pos; ++i)
  {
    pCurrent = pCurrent->next;
  }


  //先儲存待删除結點
  struct LinkNode *pDel = pCurrent->next;
  //重建立立待删除結點的前驅和後繼結點關系
  pCurrent->next = pDel->next;
  //釋放删除節點記憶體
  free(pDel);
  pDel = NULL;

  mylist->size--;

}
//按值删除
void RemoveByVal_LinkList(LinkList list, void *data, COMPARE compare)
{

  if (NULL == list)
  {
    return;
  }

  if (NULL == data)
  {
    return;
  }

  if (NULL == compare)
  {
    return;
  }

  struct LList *mylist = (struct LList *)list;

  //輔助指針變量
  struct LinkNode *pPrev = &(mylist->header);
  struct LinkNode *pCurrent = pPrev->next;

  while (pCurrent != NULL)
  {
    if (compare(pCurrent->data, data))
    {
      //找到了
      pPrev->next = pCurrent->next;
      //釋放删除節點記憶體
      free(pCurrent);
      pCurrent = NULL;
      mylist->size--;
      break;
    }

    pPrev = pCurrent;
    pCurrent = pCurrent->next;
  }

}
//清空連結清單
void Clear_LinkList(LinkList list)
{
  if (NULL == list)
  {
    return;
  }

  struct LList *mylist = (struct LList *)list;

  //輔助指針變量
  struct LinkNode *pCurrent = mylist->header.next;

  while (pCurrent != NULL)
  {
    //先緩存下一個節點的位址
    struct LinkNode *pNext = pCurrent->next;
    //釋放目前結點記憶體
    free(pCurrent);

    pCurrent = pNext;

  }

  mylist->header.next = NULL;
  mylist->size = 0;

}
//大小
int Size_LinkList(LinkList list)
{
  if (NULL == list)
  {
    return -1;
  }

  struct LList *mylist = (struct LList *)list;

  return mylist->size;
}
//銷毀連結清單
void Destroy_LinkList(LinkList list)
{

  if (NULL == list)
  {
    return;
  }

  //清空連結清單
  Clear_LinkList(list);
  free(list);
  list = NULL;
}      

main.c

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

#include"LinkList.h"

struct Person
{

  char name[64];
  int age;
};

void myPrint(void *data)
{
  struct Person *person = (struct Person *)data;
  printf("Name:%s Age:%d\n",person->name,person->age);
}

int myComapre(void *d1,void *d2)
{
  struct Person *p1 = (struct Person *)d1;
  struct Person *p2 = (struct Person *)d2;

#if 0
  if (strcmp(p1->name,p2->name) == 0 && p1->age == p2->age)
  {
    return 1;
  }

  return 0;
#endif

  return strcmp(p1->name, p2->name) == 0 && p1->age == p2->age;

}

void test()
{
  //建立連結清單
  LinkList list = Init_LinkList();

  //建立資料
  struct Person p1 = { "aaa", 10 };
  struct Person p2 = { "bbb", 20 };
  struct Person p3 = { "ccc", 30 };
  struct Person p4 = { "ddd", 40 };
  struct Person p5 = { "eee", 50 };
  struct Person p6 = { "fff", 60 };
  struct Person p7 = { "ggg", 70 };


  //插入資料
  Insert_LinkList(list, 0, &p1);
  Insert_LinkList(list, 0, &p2); //2 3 1
  Insert_LinkList(list, 1, &p3);
  Insert_LinkList(list, 2, &p4); //2 3 4 1
  Insert_LinkList(list, 20, &p5); //2 3 4 1 5
  Insert_LinkList(list, 3, &p6); //2 3 4 6 1 5
  Insert_LinkList(list, 6, &p7); //2 3 4 6 1 5 7

  Foreach_LinkList(list, myPrint);

  printf("----------------------\n");
  printf("List Size:%d\n", Size_LinkList(list));
  RemoveByPos_LinkList(list, 3);
  printf("----------------------\n");
  Foreach_LinkList(list, myPrint);


  struct Person pDelPerson = { "ggg", 70 };
  RemoveByVal_LinkList(list, &pDelPerson, myComapre);
  printf("----------------------\n");
  Foreach_LinkList(list, myPrint);

  //清空連結清單
  Clear_LinkList(list);
  printf("----------------------\n");
  printf("List Size:%d\n", Size_LinkList(list));

  //銷毀連結清單
  Destroy_LinkList(list);
}

int main(){
  test();
  system("pause");
  return EXIT_SUCCESS;
}      

SeqStack

順序連結清單就是通過數組的方式實作的連結清單結構。

SeqStack.h

#pragma once

#include <stdio.h>
#include<stdlib.h>
#include<string.h>

#ifdef __cplusplus
extern "C"{
#endif

#define MAX 1024
typedef void * SeqStack;

  struct SStack
  {
    void *data[MAX];   // 存放棧元素
    int size;          // 棧中元素個數
  };
  SeqStack Init_SeqStack();
  void Push_SeqStack(SeqStack stack, void *data);
  void Pop_SeqStack(SeqStack stack);
  void *Top_SeqStack(SeqStack stack);
  int Size_SeqStack(SeqStack stack);
  void Destroy_SeqStack(SeqStack stack);
#ifdef __cplusplus
}
#endif      

SeqStack.c

#include "SeqStack.h"

// 初始化一個順序棧
SeqStack Init_SeqStack()
{
  struct SStack *stack = malloc(sizeof(struct SStack));
  // 如果stack指針不為空,則将棧初始化一下
  if (stack != NULL)
  {
    stack->size = 0;
    for (int i = 0; i < MAX; ++i)
    {
      stack->data[i] = NULL;
    }
  }
  return stack;
}

// 入棧
void Push_SeqStack(SeqStack stack, void *data)
{
  if (stack == NULL || data == NULL)
  {
    return;
  }

  struct SStack *s = (struct SStack *)stack;
  if (s->size == MAX)
  {
    return;
  }
  s->data[s->size] = data;
  s->size++;
}

//出棧
void Pop_SeqStack(SeqStack stack)
{
  if (NULL == stack)
  {
    return;
  }

  struct SStack *s = (struct SStack *)stack;

  if (s->size == 0)
  {
    return;
  }
  s->data[s->size - 1] = NULL;
  s->size--;
}

//獲得棧頂元素
void *Top_SeqStack(SeqStack stack)
{
  if (NULL == stack)
  {
    return NULL;
  }

  struct SStack *s = (struct SStack *)stack;
  if (s->size == 0)
  {
    return NULL;
  }
  return s->data[s->size - 1];
}

//獲得棧的大小
int Size_SeqStack(SeqStack stack)
{
  if (NULL == stack)
  {
    return -1;
  }
  struct SStack *s = (struct SStack *)stack;
  return s->size;
}

//銷毀棧
void Destroy_SeqStack(SeqStack stack)
{
  if (NULL != stack)
  {
    free(stack);
  }
  return;
}      

main.c

#include "SeqStack.h"

struct Student
{
  int uid;
  char name[64];
};


int main(int argc,char *argv[])
{
  // 初始化棧,預設配置設定空間為1024
  SeqStack stack = Init_SeqStack();

  // 穿件一些測試資料
  struct Student stu1 = { 1001, "admin" };
  struct Student stu2 = { 1002, "guest" };
  struct Student stu3 = { 1003, "lyshark" };

  // 将輸入加入到棧中
  Push_SeqStack(stack, &stu1);
  Push_SeqStack(stack, &stu2);
  Push_SeqStack(stack, &stu3);

  // 循環輸出棧頂元素
  while (Size_SeqStack(stack) > 0)
  {
    // 獲得棧頂元素
    struct Student *ptr = (struct Student *)Top_SeqStack(stack);
    printf("Uid: %d --> Name: %s \n", ptr->uid, ptr->name);
    printf("目前棧大小: %d \n", Size_SeqStack(stack));
    Pop_SeqStack(stack);
  }

  // 銷毀棧
  Destroy_SeqStack(stack);
  stack = NULL;

  system("pause");
  return 0;
}      

LinkStack

通過使用連結清單的方式實作的棧。

LinkStack.h

#pragma once
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

struct StackNode
{
  struct StackNode *next;
};
struct LStack
{
  struct StackNode header;
  int size;
};

typedef void* LinkStack;

#ifdef __cplusplus
extern "C"{
#endif  
  LinkStack Init_LinkStack();
  void Push_LinkStack(LinkStack stack, void *data);
  void Pop_LinkStack(LinkStack stack);
  void* Top_LinkStack(LinkStack stack);
  int Size_LinkStack(LinkStack stack);
  void Destroy_LinkStack(LinkStack stack);
#ifdef __cplusplus
}
#endif      

LinkStack.c

#include"LinkStack.h"

// 初始化
LinkStack Init_LinkStack()
{
  struct LStack *stack = malloc(sizeof(struct LStack));
  if (NULL == stack)
  {
    return NULL;
  }

  stack->header.next = NULL;
  stack->size = 0;
  return stack;
}

// 入棧
void Push_LinkStack(LinkStack stack, void *data)
{
  if (NULL == stack || NULL == data)
  {
    return;
  }

  // 先将頭指針進行強轉
  struct LStack *ls = (struct LStack *)stack;
  // 把節點進行強轉
  struct StackNode *node = (struct StackNode *)data;

  node->next = ls->header.next;
  ls->header.next = node;
  ++(ls->size);
}

// 出棧
void Pop_LinkStack(LinkStack stack)
{
  if (NULL == stack)
  {
    return;
  }

  struct LStack *ls = (struct LStack *)stack;

  if (ls->size == 0)
  {
    return;
  }

  //緩存第一個節點
  struct StackNode *pFirst = ls->header.next;
  ls->header.next = pFirst->next;
  ls->size--;
}

// 獲得棧頂元素
void* Top_LinkStack(LinkStack stack)
{
  if (NULL == stack)
  {
    return NULL;
  }

  struct LStack *ls = (struct LStack *)stack;
  if (ls->size == 0)
  {
    return NULL;
  }

  return ls->header.next;
}

// 獲得大小
int Size_LinkStack(LinkStack stack)
{
  if (NULL == stack)
  {
    return -1;
  }
  struct LStack *ls = (struct LStack *)stack;
  return ls->size;
}

// 銷毀棧
void Destroy_LinkStack(LinkStack stack)
{
  if (NULL != stack)
  {
    free(stack);
    stack = NULL;
  }
  return;
}      

main.c

#include "LinkStack.h"

struct Student
{
  int uid;
  char name[64];
};

int main(int argc,char *argv[])
{
  // 初始化棧,預設配置設定空間為1024
  LinkStack stack = Init_LinkStack();

  // 穿件一些測試資料
  struct Student stu1 = { 1001, "admin" };
  struct Student stu2 = { 1002, "guest" };
  struct Student stu3 = { 1003, "lyshark" };

  // 将輸入加入到棧中
  Push_LinkStack(stack, &stu1);
  Push_LinkStack(stack, &stu2);
  Push_LinkStack(stack, &stu3);

  // 循環輸出棧頂元素
  while (Size_LinkStack(stack) > 0)
  {
    // 獲得棧頂元素
    struct Student *ptr = (struct Student *)Top_LinkStack(stack);
    printf("Uid: %d --> Name: %s \n", ptr->uid, ptr->name);
    printf("目前棧大小: %d \n", Size_LinkStack(stack));
    Pop_LinkStack(stack);
  }

  // 銷毀棧
  Destroy_LinkStack(stack);
  stack = NULL;

  system("pause");
  return 0;
}      

LinkQueue

LinkQueue.h

#pragma once

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

struct BiNode
{
  int data;
  struct BiNode *lchild;
  struct BiNode *rchild;
};

//連結清單結點的資料類型
struct QueueNode
{
  struct QueueNode *next;
};

//連結清單資料類型
struct LQueue
{
  struct QueueNode header; //頭結點
  struct QueueNode *rear; //尾指針
  int size;
};

typedef void* LinkQueue;

#ifdef __cplusplus
extern "C"{
#endif

  //初始化
  LinkQueue Init_LinkQueue();
  //入隊
  void Push_LinkQueue(LinkQueue queue, void *data);
  //出隊
  void Pop_LinkQueue(LinkQueue queue);
  //獲得隊頭元素
  void* Front_LinkQueue(LinkQueue queue);
  //獲得隊尾元素
  void* Back_LinkQueue(LinkQueue queue);
  //大小
  int Size_LinkQueue(LinkQueue queue);
  //銷毀隊列
  void Destroy_LinkQueue(LinkQueue queue);

#ifdef __cplusplus
}
#endif      

LinkQueue.c

#include"LinkQueue.h"

//初始化
LinkQueue Init_LinkQueue()
{
  struct LQueue *queue = malloc(sizeof(struct LQueue));
  if (NULL == queue)
  {
    return NULL;
  }

  queue->header.next = NULL;
  queue->size = 0;
  queue->rear = &(queue->header);
  return queue;
}

//入隊
void Push_LinkQueue(LinkQueue queue, void *data)
{
  if (NULL == queue || NULL == data)
  {
    return;
  }
  
  struct LQueue *q = (struct LQueue *)queue;
  struct QueueNode *n = (struct QueueNode *)data;

  q->rear->next = n;
  n->next = NULL;
  //更新尾指針
  q->rear = n;
  q->size++;
}

//出隊
void Pop_LinkQueue(LinkQueue queue)
{
  if(NULL == queue)
  {
    return;
  }

  struct LQueue *q = (struct LQueue *)queue;
  
  if (q->size == 0)
  {
    return;
  }

  if (q->size == 1)
  {

    q->header.next = NULL;
    q->rear = &(q->header);
    q->size--;

    return;
  }

  struct QueueNode *pFirstNode = q->header.next;
  q->header.next = pFirstNode->next;
  q->size--;
}

//獲得隊頭元素
void* Front_LinkQueue(LinkQueue queue)
{
  if (NULL == queue)
  {
    return NULL;
  }

  struct LQueue *q = (struct LQueue *)queue;
  return q->header.next;
}

//獲得隊尾元素
void* Back_LinkQueue(LinkQueue queue)
{
  if (NULL == queue)
  {
    return NULL;
  }

  struct LQueue *q = (struct LQueue *)queue;
  return q->rear;
}

//大小
int Size_LinkQueue(LinkQueue queue)
{
  if (NULL == queue)
  {
    return -1;
  }

  struct LQueue *q = (struct LQueue *)queue;
  return q->size;
}

//銷毀隊列
void Destroy_LinkQueue(LinkQueue queue)
{
  if (NULL == queue)
  {
    return;
  }
  
  struct LQueue *q = (struct LQueue *)queue;
  q->header.next = NULL;
  q->rear = NULL;
  q->size = 0;
  
  free(queue);
  queue = NULL;
}      

main.c

#include"LinkQueue.h"

struct Person
{
  struct QueueNode node;
  char name[64];
  int age;
};

int main(){

  //初始化隊列
  LinkQueue queue = Init_LinkQueue();

  //建立資料
  struct Person p1 = { NULL, "aaa", 10 };
  struct Person p2 = { NULL, "bbb", 20 };
  struct Person p3 = { NULL, "ccc", 30 };
  struct Person p4 = { NULL, "ddd", 40 };
  struct Person p5 = { NULL, "eee", 50 };
  struct Person p6 = { NULL, "fff", 60 };

  //插入隊列
  Push_LinkQueue(queue, &p1);
  Push_LinkQueue(queue, &p2);
  Push_LinkQueue(queue, &p3);
  Push_LinkQueue(queue, &p4);
  Push_LinkQueue(queue, &p5);
  Push_LinkQueue(queue, &p6);

  struct Person *pBack = (struct Person *)Back_LinkQueue(queue);
  printf("隊尾元素:%s %d\n",pBack->name,pBack->age);

  while(Size_LinkQueue(queue) > 0)
  {
    //獲得隊頭元素
    struct Person *person = (struct Person *)Front_LinkQueue(queue);
    //列印隊頭元素
    printf("Name:%s Age:%d\n", person->name,person->age);
    //彈出隊頭元素
    Pop_LinkQueue(queue);
  }
  //銷毀隊列
  Destroy_LinkQueue(queue);

  system("pause");
  return EXIT_SUCCESS;
}      

二叉樹知識點

二叉樹，對每個節點的檢視都是，先左後右

DLR - 先序周遊，先通路根，再左，最後右

LDR - 中序周遊 ，先左，再根，再右

LRD - 後序周遊，先左，再右，再根

二叉樹遞歸周遊

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

struct BiNode
{
  char ch;
  struct BiNode *lchild;
  struct BiNode *rchild;
};

//二叉樹遞歸周遊
void recursion(struct BiNode *root)
{
  if (NULL == root)
  {
    return;
  }

  //遞歸周遊左子樹
  recursion(root->lchild);
  //遞歸周遊右子樹
  recursion(root->rchild);
  printf("%c ", root->ch);

}

int main()
{
  struct BiNode nodeA = { 'A', NULL, NULL };
  struct BiNode nodeB = { 'B', NULL, NULL };
  struct BiNode nodeC = { 'C', NULL, NULL };
  struct BiNode nodeD = { 'D', NULL, NULL };
  struct BiNode nodeE = { 'E', NULL, NULL };
  struct BiNode nodeF = { 'F', NULL, NULL };
  struct BiNode nodeG = { 'G', NULL, NULL };
  struct BiNode nodeH = { 'H', NULL, NULL };

  nodeA.lchild = &nodeB;
  nodeA.rchild = &nodeF;
  nodeB.rchild = &nodeC;
  nodeC.lchild = &nodeD;
  nodeC.rchild = &nodeE;
  nodeF.rchild = &nodeG;
  nodeG.lchild = &nodeH;
  recursion(&nodeA);
  
  system("pause");
  return EXIT_SUCCESS;
}      

求葉子的高度寬度：

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
#include<stdlib.h>


struct BiNode
{
  char ch;
  struct BiNode *lchild;
  struct BiNode *rchild;
};

//int num = 0;

void cuculateLeafNum(struct BiNode *root,int *p)
{
  if (NULL == root)
  {
    return;
  }

  if (root->lchild == NULL && root->rchild == NULL)
  {
    (*p)++;
  }


  cuculateLeafNum(root->lchild, p);
  cuculateLeafNum(root->rchild, p);
}


int getTreeHeight(struct BiNode *root)
{
  if (NULL == root)
  {
    return 0;
  }


  //求樹的左子樹高度
  int lheight = getTreeHeight(root->lchild);
  //求樹的右子樹高度
  int rheight = getTreeHeight(root->rchild);

  int height = lheight > rheight ? lheight + 1 : rheight + 1;

  return height;
}


void showBiTree(struct BiNode *root)
{
  if (NULL == root)
  {
    return;
  }

  printf("%c ",root->ch);
  showBiTree(root->lchild);
  showBiTree(root->rchild);
}


struct BiNode *copyBiTree(struct BiNode *root)
{
  if (NULL == root)
  {
    return NULL;
  }

  //先拷貝左子樹
  struct BiNode *lchild = copyBiTree(root->lchild);
  //拷貝右子樹
  struct BiNode *rchild = copyBiTree(root->rchild);


  struct BiNode *newnode = malloc(sizeof(struct BiNode));
  newnode->lchild = lchild;
  newnode->rchild = rchild;
  newnode->ch = root->ch;

  return newnode;
}

void freeSpace(struct BiNode *root)
{
  if (NULL == root)
  {
    return;
  }

  //釋放左子數記憶體
  freeSpace(root->lchild);
  //釋放右子樹
  freeSpace(root->rchild);

  printf("%c 被釋放!\n", root->ch);
  free(root);
}

int main(){

    struct BiNode nodeA = { 'A', NULL, NULL };
  struct BiNode nodeB = { 'B', NULL, NULL };
  struct BiNode nodeC = { 'C', NULL, NULL };
  struct BiNode nodeD = { 'D', NULL, NULL };
  struct BiNode nodeE = { 'E', NULL, NULL };
  struct BiNode nodeF = { 'F', NULL, NULL };
  struct BiNode nodeG = { 'G', NULL, NULL };
  struct BiNode nodeH = { 'H', NULL, NULL };

  nodeA.lchild = &nodeB;
  nodeA.rchild = &nodeF;
  nodeB.rchild = &nodeC;
  nodeC.lchild = &nodeD;
  nodeC.rchild = &nodeE;
  nodeF.rchild = &nodeG;
  nodeG.lchild = &nodeH;

  //1. 求二叉樹的葉子節點數目
  int num = 0;
  cuculateLeafNum(&nodeA, &num);
  printf("葉子節點數目:%d\n", num);

  //2. 求二叉樹的高度
  int height = getTreeHeight(&nodeA);
  printf("樹的高度:%d\n",height);

  //3. 拷貝二叉樹
  struct BiNode *root = copyBiTree(&nodeA);
  showBiTree(root);
  printf("\n");
  showBiTree(&nodeA);

  freeSpace(root);

  system("pause");
  return EXIT_SUCCESS;
}      

通過棧實作的二叉樹

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<stdbool.h>
#include"SeqStack.h"

struct BiNode
{
  char ch;
  struct BiNode *lchild;
  struct BiNode *rchild;
};

struct Info
{
  struct BiNode *node;
  bool flag;
};

struct Info* createInfo(struct BiNode *node, bool flag)
{
  struct Info *info = malloc(sizeof(struct Info));
  info->flag = flag;
  info->node = node;

  return info;
}

void nonRecursion(struct BiNode *root)
{

  //初始化棧
  SeqStack stack = Init_SeqStack();
  //先把根節點壓入棧中
  Push_SeqStack(stack, createInfo(root, false));

  while (Size_SeqStack(stack) > 0)
  {
    //獲得棧頂元素  
    struct Info *info = (struct Info *)Top_SeqStack(stack);
    //彈出棧頂元素
    Pop_SeqStack(stack);


    if (info->flag)
    {
      printf("%c ",info->node->ch);
      free(info);
      continue;
    }

    //将根節壓入棧中
    info->flag = true;
    Push_SeqStack(stack, info);

    //将右子樹壓入棧中
    if (info->node->rchild != NULL)
    {
      Push_SeqStack(stack, createInfo(info->node->rchild, false));
    }

    //将左子樹壓入棧中
    if (info->node->lchild != NULL)
    {
      Push_SeqStack(stack, createInfo(info->node->lchild, false));
    }
  }

  //銷毀棧
  Destroy_SeqStack(stack);
}

int main(){

  struct BiNode nodeA = { 'A', NULL, NULL };
  struct BiNode nodeB = { 'B', NULL, NULL };
  struct BiNode nodeC = { 'C', NULL, NULL };
  struct BiNode nodeD = { 'D', NULL, NULL };
  struct BiNode nodeE = { 'E', NULL, NULL };
  struct BiNode nodeF = { 'F', NULL, NULL };
  struct BiNode nodeG = { 'G', NULL, NULL };
  struct BiNode nodeH = { 'H', NULL, NULL };

  nodeA.lchild = &nodeB;
  nodeA.rchild = &nodeF;
  nodeB.rchild = &nodeC;
  nodeC.lchild = &nodeD;
  nodeC.rchild = &nodeE;
  nodeF.rchild = &nodeG;
  nodeG.lchild = &nodeH;

  nonRecursion(&nodeA);
  system("pause");
  return EXIT_SUCCESS;
}      

版權聲明：本部落格文章與代碼均為學習時整理的筆記，文章 [均為原創] 作品，轉載請 [添加出處] ，您添加出處是我創作的動力！