【数据结构】- 代码题大合集

代码部分

#include 
#include 

typedef int ListItem;

typedef struct alist *List;
typedef struct alist
{
   int maxsize;     //表的最大长度
   int n;           //表长
   ListItem *table; //表元素数组
} AList;

// 查找元素x所在的位置
int ListLocate(ListItem x, List L)
{
   int i;
   for (i = 0; i < L->n; i++)
   {
      if (L->table[i] == x)
      {
         return ++i;
      }
   }
   return 0;
}

// 顺序表结构初始化(2017)
List ListInit(int size)
{
   List L = malloc(sizeof(*L));
   L->table = malloc(size * sizeof(ListItem));
   L->maxsize = size;
   L->n = 0;
   return L;
}

// 在顺序表L的位置k之后插入元素x （2016、2017）
void ListInsert(int k, ListItem x, List L)
{
   if (k < 0 || k > L->n) // 校验k是否合法
      Error("Out of bounds");
   if (L->n == L->maxsize) // 判断表是否已满
      Error("Out of memory");
   for (int i = L->n - 1; i >= k; i--)
      L->table[i + 1] = L->table[i];
   L->table[k] = x;
   L->n++; // 插入成功
}

// 返回元素x在表L中的位置（2017）
int ListLocate(ListItem x, List L)
{
   int i;
   for (i = 0; i < L->n; i++)
      if (L->table[i] == x)
         return ++i;
   return 0;
}

// 从表L中删除位置k处的元素
ListItem ListDelete(int k, List L)
{
   int i;
   ListItem x;
   if (k < 1 || k > L->n) // 校验k是否合法
      Error("Out of bounds");
   if (L->n == 0) // 判断表是否为空
      Error("List empty");

   x = L->table[k - 1]; // 保存要被删除的元素结点
   for (int i = k; i < L->n; i++)
      L->table[i - 1] = L->table[i];
   (L->n)--;
   return x;
}

图文并茂

代码

#include 
#include 

typedef int ListItem;

typedef struct node *link;
typedef struct node
{                    // 链表结点
   ListItem element; // 结点数据域
   link next;        // 结点链域
} Node;

typedef struct list *List; // 链头指针
typedef struct list
{
   link first; // 其中first是链表头指针
} Llist;

// 初始化单链表
List ListInit()
{
   List L = malloc(sizeof(*L));
   L->first = 0;
   return L;
}

// 新建一个单链表结点
link NewNode()
{
   link p;
   if ((p = malloc(sizeof(Node))) == 0)
      Error("Exhausted memory.");
   else
      return p;
}

// 测试单链表是否为空
int ListEmpty(List L)
{
   return L->first == 0;
}

// 计算单链表的长度
int ListLength(List L)
{
   int len = 0;
   link p;
   p = L->first; //搜索指针p指向第1个结点
   while (p != NULL)
   {
      len++;
      p = p->next; //p搜索到最后一个结点并记录下其位置
   }
   return len;
}

// 单链表_插入：在链表中位置k后面插入新元素 (2013)
void ListInsert(int k, ListItem x, List L)
{
   link p, newnode;
   int i;
   if (k < 0 || (k != 0 && L->first == 0))
   {
      Error("Out of bounds");
   }
   p = L->first;                // 指针p指向表首
   for (i = 1; i < k && p; i++) // 搜索到第k个结点
      p = p->next;
   newnode = malloc(sizeof(Node));
   newnode->element = x;
   if (k)
   {
      // 表中间/表尾插入
      newnode->next = p->next; // 第k +1个结点挂到新结点之后
      p->next = newnode;       // 新结点挂到第k个结点之后
   }
   else
   {
      // 在表首插入
      newnode->next = L->first; // 新结点插入到表首结点之前
      L->first = newnode;       // 新结点插入后为表首结点
   }
}

// 在链表中删除第k个结点  (2015)
ListItem ListDelete(int k, List L)
{
   link p, q;
   ListItem x;
   int i;
   if (k < 1 || !L->first)
      Error("Out of bounds");
   p = L->first; // 搜索指针p指向表首节点
   if (k == 1)
   {
      // 删除表首元素
      L->first = p->next;
   }
   else
   {
      // 删除表中或表尾元素
      q = L->first; // 搜索指针q指向表首
      for (i = 1; i < k - 1 && q; i++)
         q = q->next;
      //q搜索到第k- 1个结点
      if (q == 0)
         Error("Out of bounds");
      p = q->next;       //p指向第k个结点
      q->next = p->next; //第k+1 个结点挂到第k-1个结点之后
      x = p->element;  // 保存要删除的元素结点
      free(p); // 释放第k个结点
      return x;
   }
}

// 在单链表中按内容查找 (2014)
int Locate(ListItem x, List L)
{
   // 返回表中值为x的元素的位置
   int i = 1;
   link p;
   p = L->first; // 指针p指向表头
   while (p != NULL && p->element != x)
   {
      p = p->next;
      i++; // p搜索到元素x并记录下其位置
   }
   return p ? i : 0;
}

// 在单链表中按序号查找
ListItem ListRetrieve(int k, List L)
{
   //返回表中第k个元素
   int i;
   link p;
   if (k < 1)
      Error("Out bounds"); //k 值不合理
   p = L->first;
   i = 1; //搜索指针p指向表头
   while (p != NULL && i < k)
   {
      p = p->next; //p搜索到第k个结点
      i++;
   }
   return p->element; //返回第k个元素
}

图文

代码

#include 
#include 

typedef int ListItem;

typedef node *link;
typedef struct node //链表结点
{
    ListItem element; //结点数据域
    link next;        //结点链域
} node;

// 循环链表的结构
typedef struct clist *List;
typedef struct clist
{
    int length; 
    link last;  
} Clist;

// 循环链表初始化
List Listlnit()
{
    link newnode;
    List L = malloc(sizeof(*L));
    newnode = malloc(sizeof(node));
    newnode->next = newnode;
    L->last = newnode;
    L->length = 0;
    return L;
}

// 循环链表_查找元素x的位置
int ListLocate(ListItem x, List L)
{
    int i = 1;
    link p;
    p = L->last->next->next; 
    while (p->element != x)
    {
        
        p = p->next;
        i++;
    }
    return (p == L->last->next) ? 0 : i;
}

// 循环链表的删除、插入操作和单链表大同小异......

图文

代码

#include 
#include 

typedef int ListItem;

typedef struct node *link;
typedef struct node
{
    ListItem element; // 数据
    link left, right; // 指针
} Node;

typedef struct dlist *List;
typedef struct dlist
{
    int length;             
    link leftEnd, rightEnd; 

} Dlist; //双向链表

// 建立空的双向链表
List ListInit()
{
    link newnode;
    List L = malloc(sizeof(*L));
    newnode = NewNode();
    newnode->left = newnode;
    newnode->right = newnode;
    L->leftEnd = newnode;
    L->length = 0;
    return L;
}

// 双向链表_查找第k个位置的元素
ListItem ListRetrieve(int k, List L)
{
    int i = 1;
    link p;
    if (k < 1 || k > L->length) // 校验k值是否合法
        Error("Out of bounds.");
    p = L->leftEnd->right; // p指向表头
    while (i < k)
    {
        p = p->right;
        i++;
    }
    return p->element;
}

// 双向链表_查找元素x所在的位置
int ListLocate(ListItem x, List L)
{
    int i = 1;
    link p;
    p = L->leftEnd->right; // p 指向表头
    while (p->element != x)
    {
        p = p->right;
        i++; 
    }
    return (p == L->leftEnd) ? 0 : i; // 如果结点p等于表头指针则说明没找到
}

// 双向链表_插入：在第k个位置上插入元素x
void ListInsert(int k, ListItem х, List L)
{
    link p, newnode;
    int i;
    if (k < 0 || k > L->length)
        Error("Out of bounds.");
    p = L->leftEnd->right; 
    for (i = 1; i < k; i++)
        p = p->right; // 查找第k个元素

    newnode = NewNode();
    newnode->element = х;
    newnode->left = p;
    newnode->right = p->right;
    p->right->left = newnode;
    p->right = newnode;
    L->length++;
}

// 双向链表_删除
ListItem ListDelete(int k, List L)
{
    //在链表中删除第k个结点
    link p;
    ListItem x;
    int i;
    if (k < 1 || k > L->length)
        Error("Out of bounds");
    p = L->leftEnd->right; 
    for (i = 1; i < k; i++)
        p = p->right; //找第k个结点

    p->left->right = p->right; //重新链接
    p->right->left = p->left;

    x = p->element;
    free(p);
    return x;
}

图文

代码

#include 
#include 

typedef int StackItem;

typedef struct astack *Stack;
typedef struct astack
{                    // 顺序栈定义
    StackItem *data; // 栈数组
    int top, maxtop; // top栈顶位置   maxtop栈顶位置的最大值
} Astack;            // 栈的容量为maxtop+ 1

// 创建顺序空栈
Stack StackInit(int size)
{
    Stack S = malloc(sizeof(*S));
    S->data = malloc(size * sizeof(StackItem));
    S->maxtop = size - 1;
    S->top = -1;
    return S;
}

int StackEmpty(Stack S)
{
    //判断栈是否空?空则返回1，否则返回0
    return S->top < 0;
}

int StackFull(Stack S)
{
    //判断栈是否满?满则返回1，否则返回0
    return S->top >= S->maxtop;
}

// 顺序栈_入栈
void Push(StackItem x, Stack S)
{
    // 判断栈是否已满
    if (StackFull(S))
        Eror("Stack is full");

    S->top++;            // 栈顶加1预留空位
    S->data[S->top] = x; // 栈顶加入新元素
}

// 顺序栈_出栈
StackItem Pop(Stack S)
{
    if (StackEmpty(S)) // 判断是否为空栈
        Error("Stack is empty");
    else
    {
        StackItem x;
        x = S->data[S->top]; // 记录栈顶元素
        S->top--;            // 栈顶--
        return x;
    }
}

// 获取栈顶元素
StackItem StackTop(Stack S)
{
    if (StackEmpty(S))
        Err("Stack is empty");
    return S->data[S->top];
}

代码

#include 
#include 

typedef int StackItem;

typedef struct snode *slink;
typedef struct snode
{
   StackItem element; // 结点数据
   slink next;        // 结点链指针
} StackNode;

typedef struct lstack *Stack;
typedef struct lstack
{
   slink top; // 栈顶结点指针
} Lstack;

// 创建空栈的算法
Stack StackInit()
{
   Stack s = malloc(sizeof(*s));
   s->top = 0;
   return s;
}

// 创建链式栈结点
slink NewStackNode()
{
   slink p;
   if ((p = malloc(sizeof(StackNode))) == 0)
      Error("Exhausted memory");
   else
      return p;
}

int StackEmpty(Stack S)
{
    //判断栈是否空?空则返回1，否则返回0
    return S->top == 0;
}

// 链栈_进栈，将x元素压入到链栈中 （2015、2018）
void Push(StackItem x, Stack s)
{
   slink p;
   p = malloc(sizeof(StackNode));
   p->element = x; // 结点赋值
   p->next = s->top;
   s->top = p; // 链入栈顶
}

// 链栈_出栈操作 （2018）
StackItem Pop(Stack S)
{ 
   slink p;
   StackItem x;
   if (StackEmpty(S))  // 判断是否空栈
      Error("Stack is empty");
   x = S->top->element; // 保存原栈顶的值
   p = S->top;
   S->top = p->next; // 摘下原栈顶结点
   free(p);          // 释放原栈顶结点
   return x;
}

代码

#include 

typedef int QItem;
typedef struct qnode *qlink;
typedef struct qnode
{
   QItem element; // 队列结点数据
   qlink next;    // 结点链指针
} QNode;

typedef struct lque *Queue;

typedef struct lque
{
   qlink front, rear;
} Lqueue;

// 创建一个链式队列的结点
qlink NewQNode()
{
   qlink p;
   if ((p = malloc(sizeof(QNode)) == 0))
      Error(" Exhausted memory");
   else
      return p;
}

// 初始化链式队列
Queue QueueInit()
{
   Queue Q = malloc(sizeof(*Q));
   Q->rear = Q->front = 0;
   return Q;
}

// 判断链式队列是否为空
int QueueEmpty(Queue Q)
{
   return Q->front == 0;
}

// 链式队列_入队操作
void EnQueue(QItem x, Queue Q)
{
   qlink p;
   p = NewQNode(); // 创建一个新结点
   p->element = x;
   p->next = 0;
   // 在队尾插入新结点
   if (Q->front) // 队列非空
   {
      Q->rear->next = p;
      Q->rear = p;
   }
   else
   { //空队列，创建第一个结点
      Q->front = p;
      Q->rear = p;
   }
}

// 链式队列_出队操作，删去队头结点，并返回队头元素的值
QItem DeleteQueue(Queue Q)
{
   qlink p;
   QItem x;
   if (Q->front == Q->rear) // 判断是否空队列
      Error("Queue is empty");
   x = Q->front->element; // 保存队头的值
   p = Q->front;
   Q->front = Q->front->next; // 新队头!
   free(p);
   return x;
}

代码

#include 
#include 

typedef int QItem;

typedef struct aque *Queue;
typedef struct aque
{
    int maxsize;  
    int front;    
    int rear;     
    QItem *queue; 
} Aqueue;

// 循环队列初始化
Queue QueueInit(int size)
{
    Queue Q = malloc(sizeof(*Q));
    Q->queue = malloc(size * sizeof(QItem));
    Q->maxsize = size;
    Q->front = Q->rear = 0;
    return Q;
}

// 判断循环队列是否为空（2017）
int QueueEmpty(Queue Q)
{
    return Q->rear == Q->front;
}

// 判断循环队列是否已满 （2017）
int QueueFull(Queue Q)
{
    return ((Q->rear + 1) % Q->maxsize == Q->front) ? 1 : 0;
}

// 取出循环队列第一个元素
QItem QueueFirst(Queue Q)
{
    if (QueueEmpty(Q))
        Error("Queue is empty");
    return Q->queue[(Q->front + 1) % Q->maxsize];
}

// 取出循环队列最后一个元素
QItem QueueLast(Queue Q)
{
    if (QueueEmpty(Q))
        Error("Queue is empty");
    return Q->queue[Q->rear];
}

// 循环队列中插入元素x（2017）
void EnterQueue(QItem x, Queue Q)
{
    if (QueueFull(Q))
        Error("Queue is full"); // 判断循环队列是否为满
    Q->rear = (Q->rear + 1) % Q->maxsize;
    Q->queue[Q->rear] = x;
}

// 循环队列_出队操作 （2017）
QItem DeleteQueue(QItem x, Queue Q)
{
    if (QueueEmpty(Q))
        Error("Queue is empty");
    Q->front = (Q->front + 1) % Q->maxsize;
    x = Q->queue[Q->front];  // 将出队的元素保存到x中
}