AI 助理
备案控制台
开发者社区 云计算 文章 正文

期末不知道如何复习数据结构的话，不妨点进来看看。看明白保你过。

2023-07-13 42
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 期末不知道如何复习数据结构的话，不妨点进来看看。看明白保你过。

顺序表


这个是动态顺序表，我觉得功能已经十分的齐全了，要是有缺少的功能大家可以私信或者在评论区告诉我，我会修改的。


#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int SLDatatype;
typedef struct SeqList
{
  SLDatatype* a;
  int size;//储存的有效数据个数
  int capacity;//容量
}SL;
void SLInit(SL* psl)
{
  assert(psl);
  psl->a = (SLDatatype*)malloc(sizeof(SLDatatype)*4);
  if (psl->a == NULL)
  {
  perror("malloc fail");
  return;
  }
  psl->size = 0;
  psl->capacity = 4;
}
void SLCheckCapacity(SL* psl)
{
  assert(psl);
  if (psl->size == psl->capacity)
  {
  SLDatatype* tmp = (SLDatatype*)realloc(psl->a,sizeof(SLDatatype) * psl->capacity * 2);
  if (tmp == NULL)
  {
    perror("realloc fail");
    return;
  }
  psl->a = tmp;
  psl->capacity *= 2;
  }
}
void SLDestroy(SL* psl)
{
  assert(psl);
  free(psl->a);
  psl->a = NULL;
  psl->size = 0;
  psl ->capacity = 0;
}
void SLPrint(SL* psl)
{
  assert(psl);
  for (int i = 0; i < psl->size; i++)
  {
  printf("%d ", psl->a[i]);
  }
  printf("\n");
}
//STL命名风格
void SLPushBack(SL* psl, SLDatatype x)
{
  assert(psl);
  SLCheckCapacity(psl);
  psl->a[psl->size++] = x;
}
void SLPushFront(SL* psl, SLDatatype x)
{
  assert(psl);
  SLCheckCapacity(psl);
  int end = psl->size-1;
  while (end >= 0)
  {
  psl->a[end + 1] = psl->a[end];
  --end;
  }
  psl->a[0] = x;
  psl->size++;
}
void SLPopBack(SL* psl)
{
  assert(psl);
  if (psl->size <= 0)
  {
  return;
  }
  psl->size--;
}
void SLPopFront(SL* psl)
{
  assert(psl);
  if (psl->size <= 0)
  {
  return;
  }
  for (int i = 0; i < psl->size-1; i++)
  {
  psl->a[i] = psl->a[i + 1];
  }
  psl->size--;
}
void SLInsert(SL* psl, int pos, SLDatatype x)
{
  assert(psl);
  SLCheckCapacity(psl);;
  for (int i = pos; i < psl->size; i++)
  {
  psl->a[i+1] = psl->a[i];
  }
  psl->a[pos] = x;
  psl->size++;
}
void SLErase(SL* psl, int pos)
{
  assert(psl);
  if (psl->size <= 0)
  {
  return;
  }
  for (int i = pos; i < psl->size-1; i++)
  {
  psl->a[i] = psl->a[i + 1];
  }
  psl->size--;
}
// 找到返回下标，没有找到返回-1
int SLFind(SL* psl, SLDatatype x)
{
  assert(psl);
  for (int i = 0; i < psl->size; i++)
  {
  if (psl->a[i] == x)
  {
    return i;
  }
  }
  return -1;
}
void SLModify(SL* psl, int pos, SLDatatype x)
{
  assert(psl);
  psl->a[pos] = x;
}
void menu()
{
  printf("***************************************\n");
  printf("1、尾插数据  2、尾删数据\n");
  printf("3、头插数据  4、头删数据\n");
  printf("5、打印数据  6.修改数据\n");
  printf("-1.退出程序\n");
  printf("***************************************\n");
}
int main()
{
  int option = 0;
  SL s;
  SLInit(&s);
  while (option != -1)
  {
  menu();
  printf("请输入你的操作:>");
  scanf("%d", &option);
  if (option == 1)
  {
    /*printf("请输入要尾插的数据，以-1结束:");
    int x = 0;
    scanf("%d", &x);
    while (x != -1)
    {
    SLPushBack(&s, x);
    scanf("%d", &x);
    }*/
    int n = 0;
    printf("请输入要尾插的数据个数，再依次输入要插入的数据:");
    scanf("%d", &n);
    int x = 0;
    while (n > 0)
    {
    scanf("%d", &x);
    SLPushBack(&s, x);
    n--;
    }
  }
  else if (option == 5)
  {
    SLPrint(&s);
  }
  else if (option == 2)
  {
    int n = 0;
    printf("请输入要尾删的数据个数");
    scanf("%d", &n);
    int x = 0;
    while (n > 0)
    {
    SLPopBack(&s);
    n--;
    }
  }
  else if (option == 3)
  {
    int n = 0;
    printf("请输入要头插的数据个数，再依次输入要插入的数据:");
    scanf("%d", &n);
    int x = 0;
    while (n > 0)
    {
    scanf("%d", &x);
    SLPushFront(&s, x);
    n--;
    }
  }
  else if (option == 4)
  {
    int x;
    int n;
    printf("请输入需要头删的个数");
    scanf("%d", &n);
    while (n)
    {
    SLPopFront(&s);
    n--;
    }
  }
  else if (option == 6)
  {
    printf("请输入要修改的数的下标\n");
    int x;
    scanf("%d", &x);
    printf("请输入修改后的数字\n");
    int n;
    scanf("%d", &n);
    SLModify(&s, x, n);
  }
  else if (option == -1)
  {
    break;
  }
  else
  {
    printf("无此选项,请重新输入\n");
  }
  }
  SLDestroy(&s);
  return 0;
}


单链表


#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLTDataType;
typedef struct SListNode
{
  SLTDataType data;
  struct SListNode* next;
}SLTNode;
void SLTPrint(SLTNode* phead)
{
  SLTNode* cur = phead;
  while (cur != NULL)
  {
  printf("%d=>", cur->data);
  cur = cur->next;
  }
  printf("NULL");
  printf("\n");
}
SLTNode* BuyLTNode(SLTDataType x)
{
  SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
  if (newnode == NULL)
  {
  perror("malloc fail");
  return NULL;
  }
  newnode->data = x;
  newnode->next = NULL;
  return newnode;
}
void SLPushFront(SLTNode** pphead, SLTDataType x)
{
  SLTNode* newnode = BuyLTNode(x);
  if (*pphead == NULL)
  {
  *pphead = newnode;
  }
  else
  {
  newnode->next = *pphead;
  *pphead = newnode;
  }
}
void SLPushBack(SLTNode** pphead, SLTDataType x)
{
  SLTNode* cur = *pphead;
  SLTNode* newnode = BuyLTNode(x);
  if (*pphead == NULL)
  {
  *pphead = newnode;
  newnode = *pphead;
  }
  else
  {
  while (cur->next!= NULL)
  {
    cur = cur->next;
  }
  cur->next = newnode;
  }
}
void SLPopFront(SLTNode** pphead)
{
  assert(*pphead);
  SLTNode* del = *pphead;
  *pphead = (*pphead)->next;
  free(del);
}
void SLPopBack(SLTNode** pphead)
{
  assert(*pphead);
  if ((*pphead)->next == NULL)
  {
  free(*pphead);
  *pphead = NULL;
  }
  else
  {
  SLTNode* tail = *pphead;
  // 找到尾结点
  while (tail->next->next)
  {
    tail = tail->next;
  }
  free(tail->next);
  tail->next = NULL;
  }
}
void TestSList2()
{
  SLTNode* plist = NULL;
  SLPushBack(&plist, 1);
  SLPushBack(&plist, 2);
  SLPushBack(&plist, 3);
  SLPushBack(&plist, 4);
  SLPopFront(&plist);
  SLPushFront(&plist, 1);
  SLPopBack(&plist);
  SLPushBack(&plist, 4);
  SLTPrint(plist);
}
int main()
{
  TestSList2();
  return 0;
}


双向链表


#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int LTDataType;
typedef struct ListNode
{
  struct ListNode* prev;
  struct ListNode* next;
  LTDataType data;
}LTNode;
LTNode* BuyLTNode(LTDataType x)
{
  LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
  if (newnode == NULL)
  {
  perror("malloc fail");
  return NULL;
  }
  newnode->data = x;
  newnode->next = NULL;
  newnode->prev = NULL;
  return newnode;
}
LTNode* LTInit()
{
  LTNode* phead = BuyLTNode(-1);
  phead->next = phead;
  phead->prev = phead;
  return phead;
}
void LTPrint(LTNode* phead)
{
  assert(phead);
  printf("GUard<==>");
  LTNode* cur = phead->next;
  while (cur != phead)
  {
  printf("%d<==>", cur->data);
  cur = cur->next;
  }
  printf("\n");
}
bool LTEmpty(LTNode* phead)
{
  assert(phead);
  return phead->next == phead;
}
void LTPushBack(LTNode* phead, LTDataType x)
{
  assert(phead);
  LTNode* tail = phead->prev;
  LTNode* newnode = BuyLTNode(x);
  newnode->next = phead;
  phead->prev = newnode;
  newnode->prev = tail;
  tail->next = newnode;
}
void LTPushFront(LTNode* phead, LTDataType x)
{
  assert(phead);
  LTNode* head = phead->next;
  LTNode* newnode = BuyLTNode(x);
  phead->next = newnode;
  newnode->prev = phead;
  newnode->next = head;
  head->prev = newnode;
}
void LTPopBack(LTNode* phead)
{
  assert(phead);
  assert(!LTEmpty(phead));
  LTNode* tail = phead->prev;
  LTNode* tailprev = tail->prev;
  free(tail);
  phead->prev = tailprev;
  tailprev->next = phead;
}
void LTPopFront(LTNode* phead)
{
  LTNode* head = phead->next;
  LTNode* headnext = head->next;
  phead->next = headnext;
  headnext->prev = phead;
  free(head);
}
LTNode* LTFind(LTNode* phead, LTDataType x)
{
  LTNode* cur = phead->next;
  while (cur!=phead)
  {
  if (cur->data == x)
  {
    return cur;
  }
  cur = cur->next;
  }
  return NULL;
}
// 在pos之前插入
void LTInsert(LTNode* pos, LTDataType x)
{
  assert(pos);
  LTNode* prev = pos->prev;
  LTNode* newnode = BuyLTNode(x);
  newnode->next = pos;
  pos->prev = newnode;
  prev->next = newnode;
  newnode->prev = prev;
}
// 删除pos位置的值
void LTErase(LTNode* pos)
{
  assert(pos);
  LTNode* posPrev = pos->prev;
  LTNode* posNext = pos->next;
  posPrev->next = posNext;
  posNext->prev = posPrev;
}
void LTDestroy(LTNode* phead)
{
  assert(phead);
  LTNode* cur = phead->next;
  while (cur!=phead)
  {
  LTNode* next = cur->next;
  free(cur);
  cur = next;
  }
  free(phead);
}
void TestList3()
{
  LTNode* plist = LTInit();
  LTPushFront(plist, 1);
  LTPushFront(plist, 2);
  LTPushFront(plist, 3);
  LTPushFront(plist, 4);
  LTPrint(plist);
  LTNode* pos = LTFind(plist, 3);
  if (pos)
  {
  LTInsert(pos, 30);
  }
  LTPopFront(plist);
  LTPopBack(plist);
  LTPushBack(plist, 9);
  LTPrint(plist);
  LTDestroy(plist);
  plist = NULL;
}
int main()
{
  TestList3();
  return 0;
}


像头插，尾删这样的功能，我们可以直接通过复用 LTInsert和LTErase来实现，这样写可以大幅度简化代码，让代码精简。代码如下：


#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef struct Node
{
  int data;
  struct Node* next;
  struct Node* prev;
}Node;
Node* BuyListNode(int x);
Node* SLInit();
void LTPopFront(Node* phead);
void LTPushFront(Node* phead, int x);
void LTPopBack(Node* phead);
void LTDestroy(Node* phead);
void LTPushBack(Node* phead, int x);
void LTErase(Node* phead);
void LTInsert(Node* pos, int x);
int LTEmpty(Node* phead);
void Print(Node* phead);
Node* BuyListNode(int x)
{
  Node* newnode = (Node*)malloc(sizeof(Node));
  newnode->data = x;
  newnode->next = NULL;
  newnode->prev = NULL;
  return newnode;
}
Node* SLInit()
{
  Node* phead = BuyListNode(-1);
  phead->next = phead;
  phead->prev = phead;
  return phead;
}
void LTInsert(Node* pos, int x)
{
  assert(pos);
  Node* newnode = BuyListNode(x);
  Node* prev = pos->prev;
  newnode->next = prev->next;
  newnode->prev = prev;
  prev->next = newnode;
  pos->prev = newnode;
}
void LTPushFront(Node* phead, int x)
{
  assert(phead);
  LTInsert(phead->next, x);
}
void LTPushBack(Node* phead, int x)
{
  assert(phead);
  LTInsert(phead, x);
}
void LTPopFront(Node* phead)
{
  assert(phead);
  assert(!LTEmpty(phead));
  LTErase(phead->prev);
}
void LTErase(Node* pos)
{
  assert(pos);
  Node* prev = pos->prev;
  Node* next = pos->next;
  prev->next = next;
  next->prev = prev;
}
void LTPopBack(Node* phead)
{
  assert(phead);
  assert(!LTEmpty(phead));
  LTErase(phead->prev);
}
void LTDestroy(Node* phead)
{
  assert(phead);
  Node* cur = phead->next;
  while (phead != cur)
  {
  Node* next = cur->next;
  free(cur);
  cur = next;
  }
  free(phead);
}
int LTEmpty(Node* phead)
{
  assert(phead);
  return phead == phead->next;
}
void Print(Node* phead)
{
  Node* cur = phead->next;
  while (cur != phead)
  {
  Node* next = cur->next;
  printf("%d<==>", cur->data);
  cur = next;
  }
  printf("\n");
}


循环双向链表 


typedef int DLLData;
typedef struct DLLNode
{
  DLLData data;
  struct ListNode* next;
  struct ListNode* prev;
}ListNode;
// 创建返回链表的头结点.
ListNode* ListCreate()
{
  ListNode* guard = (ListNode*)malloc(sizeof(ListNode));
  guard->next = guard->prev = guard;
  return guard;
}
// 创建一个新的结点
ListNode* BuyNewnode(LTDataType x)
{
  ListNode* new_node = (ListNode*)malloc(sizeof(ListNode));
  new_node->data = x;
  return new_node;
}
// 双向链表销毁
void ListDestroy(ListNode* phead)
{
  assert(phead);
  ListNode* tmp = phead->next, *node = phead->next;
  phead->next = NULL;
  while (tmp)
  {
  node = tmp->next;
  free(tmp);
  tmp = node;
  }
}
// 双向链表打印
void ListPrint(ListNode* phead)
{
  assert(phead);
  ListNode* tmp = phead->next;
  printf("phead<=>");
  while (tmp != phead)
  {
  printf("%d<=>", tmp->data);
  tmp = tmp->next;
  }
  printf("phead\n");
}
// 双向链表尾插
void ListPushBack(ListNode* phead, LTDataType x)
{
  assert(phead);
  ListInsert(phead, x);
}
// 双向链表尾删
void ListPopBack(ListNode* phead)
{
  assert(phead);
  assert(!CheckVoid(phead));
  ListErase(phead->prev);
}
// 双向链表头插
void ListPushFront(ListNode* phead, LTDataType x)
{
  assert(phead);
  ListInsert(phead->next, x);
}
// 双向链表头删
void ListPopFront(ListNode* phead)
{
  assert(phead);
  assert(!CheckVoid(phead));
  ListErase(phead->next);
}
// 双向链表查找
ListNode* ListFind(ListNode* phead, LTDataType x)
{
  assert(phead);
  ListNode* tmp = phead->next;
  while (tmp != phead)
  {
  if (tmp->data == x)
    return tmp;
  tmp = tmp->next;
  }
  return NULL;
}
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x)
{
  ListNode* front = pos->prev;
  ListNode* new_node = BuyNewnode(x);
  front->next = new_node;
  new_node->next = pos;
  pos->prev = new_node;
  new_node->prev = front;
}
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos)
{
  pos->prev->next = pos->next;
  pos->next->prev = pos->prev;
  free(pos);
}
// 检查链表为空
bool CheckVoid(ListNode* rhs)
{
  assert(rhs);
  return rhs->next == rhs;
}


栈


#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int STDataType;
typedef struct Stack
{
  STDataType* a;
  int top;
  int capacity;
}ST;
void STInit(ST* pst)
{
  assert(pst);
  pst->a = NULL;
  pst->top = 0;//这里要注意，如果设置top为-1，则为指向数据位置，如果设置top=0,则指向数据的下一个位置。
  pst->capacity = 0;
}
bool STEmpty(ST* pst)
{
  assert(pst);
  return pst->top == 0;
}
void STDestroy(ST* pst)
{
  assert(pst);
  free(pst->a);
  pst->a = NULL;
  pst->top = pst->capacity = 0;
}
void STPush(ST* pst, STDataType x)
{
  if (pst->top == pst->capacity)
  {
  int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
  STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * newcapacity);
  if (tmp == NULL)
  {
    perror("realloc fail");
    return;
  }
  pst->a = tmp;
  pst->capacity = newcapacity;
  }
  pst->a[pst->top] = x;
  pst->top++;
}
void STPop(ST* pst)
{
  assert(pst);
  assert(!STEmpty(pst));
  pst->top--;
}
STDataType STTop(ST* pst)
{
  assert(pst);
  assert(!STEmpty(pst));
  return pst->a[pst->top - 1];
}
int STSize(ST* pst)
{
  assert(pst);
  return pst->top;
}
void TestStack1()
{
  ST st;
  STInit(&st);
  STPush(&st, 1);
  STPush(&st, 2);
  printf("%d ", STTop(&st));
  STPop(&st);
  STPush(&st, 3);
  STPush(&st, 4);
  while (!STEmpty(&st))
  {
  printf("%d ", STTop(&st));
  STPop(&st);
  }
  STDestroy(&st);
}
int main()
{
  TestStack1();
  return 0;
}


队列


#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int QDataType;
typedef struct QueueNode
{
  QDataType data;
  struct QueueNode* next;
}QNode;
typedef struct Queue
{
  QNode* phead;
  QNode* ptail;
  int size;
}Queue;
void QueueInit(Queue* pq)
{
  assert(pq);
  pq->phead = NULL;
  pq->ptail = NULL;
  pq->size = 0;
}
bool QueueEmpty(Queue* pq)
{
  assert(pq);
  return pq->size == 0;
}
void QueueDestroy(Queue* pq)
{
  assert(pq);
  QNode* cur = pq->phead;
  while (cur)
  {
  QNode* next = cur->next;
  free(cur);
  cur = next;
  }
  pq->ptail = pq->phead = NULL;
  pq->size = 0;
}
void QueuePush(Queue* pq, QDataType x)
{
  assert(pq);
  QNode* newnode = (QNode*)malloc(sizeof(QNode));
  if (newnode == NULL)
  {
  perror("malloc fail");
  return;
  }
  newnode->data = x;
  newnode->next = NULL;
  if (pq->ptail == NULL)
  {
  assert(pq->phead == NULL);
  pq->ptail = pq->phead = newnode;
  }
  else
  {
  pq->ptail->next = newnode;
  pq->ptail = newnode;
  }
  pq->size++;
}
void QueuePop(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
  if (pq->phead->next == NULL)
  {
  free(pq->phead);
  pq->phead = pq->ptail = NULL;
  }
  else
  {
  //头删
  QNode* next = pq->phead->next;
  free(pq->phead);
  pq->phead = next;
  }
  pq->size--;
}
QDataType QueueFront(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
  return pq->phead->data;
}
QDataType QueueBack(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
  return pq->ptail->data;
}
int QueueSize(Queue* pq)
{
  assert(pq);
  return pq->size;
}
int main()
{
  Queue* pq = (Queue*)malloc(sizeof(Queue));;
  QueueInit(pq);
  QueuePush(pq, 1);
  QueuePush(pq, 2);
  QueuePush(pq, 3);
  QueuePush(pq, 4);
  QueuePush(pq, 5);
  printf("%d\n", QueueSize(pq));
  printf("%d\n", QueueFront(pq));
  printf("%d\n", QueueBack(pq));
  return 0;
}


循环队列


# include<stdio.h>
# include<malloc.h>
# define TRUE 1
# define FALSE 0
/*链队列*/
/*链队列的存储结构*/
typedef struct Node {
  int data;      //队列数据域
  struct Node* next;    //队列指针域
}LinkQueueNode;
typedef struct {
  LinkQueueNode* front;//头指针
  LinkQueueNode* rear;//尾指针
}LinkQueue;
/*链队列的初始化*/
int InitQueue(LinkQueue* Q) {
  Q->front = (LinkQueueNode*)malloc(sizeof(LinkQueueNode));
  if (Q->front != NULL) {
  Q->rear = Q->front;
  Q->front->next = NULL;
  return TRUE;
  }
  else
  return FALSE;    //溢出
}
/*链队列的创建*/
void CreateQueue(LinkQueue* Q) {
  LinkQueueNode* NewNode;
  int c, flag = 1;
  while (flag) {
  scanf("%d", &c);
  if (c != 0) {
    NewNode = (LinkQueueNode*)malloc(sizeof(LinkQueueNode));
    NewNode->data = c;
    Q->rear->next = NewNode;  //新结点插入到队尾
    Q->rear = NewNode;    //修改队尾指针
  }
  else {
    flag = 0;
    NewNode->next = NULL;
  }
  }
}
/*链队列入队*/
int EnterQueue(LinkQueue* Q, int x) {
  /*将数据元素x插入到队列Q中*/
  LinkQueueNode* NewNode;
  NewNode = (LinkQueueNode*)malloc(sizeof(LinkQueueNode));
  if (NewNode != NULL) {
  NewNode->data = x;
  NewNode->next = NULL;
  Q->rear->next = NewNode;  //新结点插入到队尾
  Q->rear = NewNode;    //修改队尾指针
  return TRUE;
  }
  return FALSE;
}
/*链队列出队*/
int DeleteQueue(LinkQueue* Q, int* x) {
  /*将队列Q的队头元素出队，并保存到x中*/
  LinkQueueNode* p;
  if (Q->front == Q->rear)  //空队列
  return FALSE;
  p = Q->front->next;    //p指向队头元素
  Q->front->next = p->next;  //队头元素p出队
  if (Q->rear == p)    //若队中只有一个元素p，则p出队后成为空队
  Q->rear = Q->front;
  *x = p->data;
  free(p);
  return TRUE;
}
/*队列输出*/
void Display(LinkQueue* Q) {
  if (Q->front == Q->rear)  //空队列
  printf("空队列！\n");
  else {
  LinkQueueNode* p;
  p = Q->front->next;   //p指向队头元素
  while (p != NULL) {
    printf("%d ", p->data);
    p = p->next;
  }
  printf("\n");
  }
}
int main() {
  int x;
  LinkQueue Q;
  InitQueue(&Q);      //初始化队列
  printf("创建队列(以0结束)：");  //创建
  CreateQueue(&Q);
  printf("创建的队列元素为：");
  Display(&Q);
  EnterQueue(&Q, 5);    //入队
  printf("入队后队中元素为：");
  Display(&Q);
  DeleteQueue(&Q, &x);    //出队
  printf("出队元素为：%d\n", x);
  printf("出队后队中元素为：");
  Display(&Q);
  return 0;
}


二叉树


二叉树的层序遍历需要用到队列的知识，大家看代码可能不理解是什么意思，不过没关系。


只要你画个图，一切就会豁然开朗！


#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int BTDataType;
typedef struct BinaryTreeNode
{
  BTDataType data;
  struct BinaryTreeNode* left;
  struct BinaryTreeNode* right;
}BTNode;
typedef BTNode* QDataType;
typedef struct QueueNode
{
  struct QueueNode* next;
  QDataType data;
}QNode;
typedef struct Queue
{
  QNode* phead;
  QNode* ptail;
  int size;
}Queue;
void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);
void QueuePush(Queue* pq, QDataType x);
void QueuePop(Queue* pq);
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
int QueueSize(Queue* pq);
bool QueueEmpty(Queue* pq);
BTNode* BuyNode(BTDataType x)
{
  BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
  if (newnode == NULL)
  {
  perror("malloc fail");
  return NULL;
  }
  newnode->data = x;
  newnode->left = NULL;
  newnode->right = NULL;           
  return newnode;
}
void PrevOrder(BTNode* root)
{
  if (root == NULL)
  {
  printf("NULL ");
  return;
  }
  printf("%d ", root->data);
  PrevOrder(root->left);
  PrevOrder(root->right);
}
void InOrder(BTNode* root)
{
  if (root == NULL)
  {
  printf("NULL");
  return;
  }
  InOrder(root->left);
  printf("%d ", root->data);
  InOrder(root->right);
}
void PostOrder(BTNode* root)
{
  if (root == NULL)
  {
  printf("NULL ");
  return;
  }
  PostOrder(root->left);
  PostOrder(root->right);
  printf("%d ", root->data);
}
int BTNodeSize(BTNode* root)
{
  return root == NULL ? 0 : BTNodeSize(root->left) + BTNodeSize(root->right) + 1;
}
int BTreeLeafSize(BTNode* root)
{
  if (root == NULL)
  {
  return 0;
  }
  if (root->left == NULL && root->right == NULL)
  {
  return 1;
  }
  return BTreeLeafSize(root->left) + BTreeLeafSize(root->right);
}
int BTreeHeight(BTNode* root)
{
  if (root == NULL)
  {
  return 0;
  }
  int LeftHeight = BTreeHeight(root->left);
  int RightHeight = BTreeHeight(root->right);
  return LeftHeight > RightHeight ? LeftHeight + 1 : RightHeight + 1;
}
int BTreeLevelKSize(BTNode* root, int k)
{
  assert(k > 0);
  if (root == NULL)
  {
  return 0;
  }
  if (k == 1)
  {
  return 1;
  }
  return BTreeLevelKSize(root->left, k - 1) + BTreeLevelKSize(root->right, k - 1);
}
BTNode* BTFind(BTNode* root, BTDataType x)
{
  if (root == NULL)
  {
  return NULL;
  }
  if (root->data == x)
  {
  return root;
  }
  BTNode* ret1 = BTFind(root->left, x);
  if (ret1)
  {
  return ret1;
  }
  BTNode* ret2 = BTFind(root->right, x);
  if (ret2)
  {
  return ret2;
  }
  return NULL;
}
void BTreeNodeDestroy(BTNode* root)
{
  if (root == NULL)
  {
  return;
  }
  BTreeNodeDestroy(root->left);
  BTreeNodeDestroy(root->right);
  free(root);
}
// 判断二叉树是否是完全二叉树
bool BTreeComplete(BTNode* root)
{
  Queue q;
  QueueInit(&q);
  if (root)
  QueuePush(&q, root);
  while (!QueueEmpty(&q))
  {
  BTNode* front = QueueFront(&q);
  QueuePop(&q);
  // 遇到空就跳出
  if (front == NULL)
    break;
  QueuePush(&q, front->left);
  QueuePush(&q, front->right);
  }
  // 检查后面的节点有没有非空
  // 有非空，不是完全二叉树
  while (!QueueEmpty(&q))
  {
  BTNode* front = QueueFront(&q);
  QueuePop(&q);
  if (front)
  {
    QueueDestroy(&q);
    return false;
  }
  }
  QueueDestroy(&q);
  return true;
}
void InsertSort(int* a, int n)
{
  for (int i = 1; i < n; ++i)
  {
  // [0, end] 有序，插入tmp依旧有序
  int end = i - 1;
  int tmp = a[i];
  while (end >= 0)
  {
    if (a[end] > tmp)
    {
    a[end + 1] = a[end];
    --end;
    }
    else
    {
    break;
    }
  }
  a[end + 1] = tmp;
  }
}


图的知识太多了，我在这里就不列举了。


大家期末加油。。。祝大家拿满绩。。。

陈大大陈
目录
相关文章
樊梓慕
|
11月前
|
存储 安全 Java
【C++】引用之带你“消除”C语言版数据结构教材的一些困惑（虽然是C++的内容，但是强烈建议正在学习数据结构的同学点进来看看）
【C++】引用之带你“消除”C语言版数据结构教材的一些困惑（虽然是C++的内容，但是强烈建议正在学习数据结构的同学点进来看看）
樊梓慕
66 0
锡兰Ceylan_
|
存储 机器学习/深度学习 人工智能
【开卷数据结构 】图的基本介绍，不进来看看吗？
【开卷数据结构 】图的基本介绍，不进来看看吗？
锡兰Ceylan_
191 1
ephemerals__
|
12天前
|
C语言
【数据结构】栈和队列（c语言实现）（附源码）
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表，遵循“先进后出”原则；队列则在一端插入、另一端删除，遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现，并提供了完整的代码示例。栈和队列在实际应用中非常广泛，如二叉树的层序遍历和快速排序的非递归实现等。
ephemerals__
85 9
那年春天
|
3天前
|
存储 算法
非递归实现后序遍历时，如何避免栈溢出？
后序遍历的递归实现和非递归实现各有优缺点，在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
那年春天
12 1
德国都芳最好
|
6天前
|
存储 算法 Java
数据结构的栈
栈作为一种简单而高效的数据结构，在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈，可以有效地解决许多与数据存储和操作相关的问题。
德国都芳最好
43 21
html的七十二变
|
9天前
|
存储 JavaScript 前端开发
执行上下文和执行栈
执行上下文是JavaScript运行代码时的环境，每个执行上下文都有自己的变量对象、作用域链和this值。执行栈用于管理函数调用，每当调用一个函数，就会在栈中添加一个新的执行上下文。
html的七十二变
22 2
dufadayang
|
11天前
|
存储
系统调用处理程序在内核栈中保存了哪些上下文信息？
【10月更文挑战第29天】系统调用处理程序在内核栈中保存的这些上下文信息对于保证系统调用的正确执行和用户程序的正常恢复至关重要。通过准确地保存和恢复这些信息，操作系统能够实现用户模式和内核模式之间的无缝切换，为用户程序提供稳定、可靠的系统服务。
dufadayang
37 4
java冯坚持
|
1月前
|
算法 程序员 索引
数据结构与算法学习七：栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈，并展示了如何利用栈和中缀表达式实现一个综合计算器。
java冯坚持
28 1
数据结构与算法学习七：栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
肾透侧视攻城狮
|
15天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总（10）【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子；这都学不会；能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛？！！！
肾透侧视攻城狮
15 1
禁默
|
1月前
初步认识栈和队列
初步认识栈和队列
禁默
58 10

热门文章

最新文章

  • 1
    我花了一夜用数据结构给女朋友写个H5走迷宫游戏
  • 2
    数据结构学习笔记【持续更新】
  • 3
    基于OHCI的USB主机 —— OHCI（自定义数据结构）
  • 4
    【数据结构与算法】一篇文章彻底搞懂二分查找（思路图解+代码优化）两种实现方式，递归与非递归
  • 5
    学数据结构，只需要基本的编程体验
  • 6
    数据结构（2）：栈的原理和实现
  • 7
    算法导论第十四章 数据结构的扩张
  • 8
    【数据结构7】查找
  • 9
    基于OHCI的USB主机 —— UFI数据结构2
  • 10
    R语言学习笔记（一）数据结构
  • 1
    `geopandas`是一个开源项目，它为Python提供了地理空间数据处理的能力。它基于`pandas`库，并扩展了其对地理空间数据（如点、线、多边形等）的支持。`GeoDataFrame`是`geopandas`中的核心数据结构，它类似于`pandas`的`DataFrame`，但包含了一个额外的地理列（通常是`geometry`列），用于存储地理空间数据。
    67
  • 2
    “解锁Python高级数据结构新姿势：图的表示与遍历，让你的算法思维跃升新高度
    40
  • 3
    Redis数据结构—跳跃表 skiplist 实现源码分析
    60
  • 4
    逆袭之路！用 Python 玩转图的 DFS 与 BFS，让数据结构难题无处遁形
    63
  • 5
    Python中的列表（List）和元组（Tuple）是两种重要的数据结构
    51
  • 6
    【数据结构OJ题】链表分割
    30
  • 7
    【数据结构常见七大排序（三）上】—交换排序篇【冒泡排序】And【快速排序】
    44
  • 8
    【数据结构常见七大排序（二）】—选择排序篇【直接选择排序】And【堆排序】
    32
  • 9
    【数据结构常见七大排序（一）】—插入排序篇【直接插入排序】And【希尔排序】
    43
  • 10
    【数据结构OJ题】链表的回文结构
    37

    • 相关课程

    更多
  • Go语言核心编程 - 数据结构和算法
  • 天池leetcode编程基础课
  • 程序设计类比赛汇总
  • Java面试疑难点解析 - 系统架构及项目设计
  • 全栈数据工程师养成攻略

    • 相关电子书

    更多
  • 如何使用Tair增强数据结构构建丰富在线实时场景
  • Apache Flink 流式应用中状态的数据结构定义升级
  • 超全算法笔试-模拟题精解合集
    • 下一篇
    阿里云OSS设置跨域访问