数据结构算法总结

一

假设以带头结点的循环链表表示一个队列 并只设一个指针指向队尾元素结点，用C语言编写相应的队列初始化、入队列和出队列的算法
以下是使用带头结点的循环链表表示队列的C语言代码，包括队列初始化、入队列和出队列的算法：

// 定义队列元素结构体
typedef struct node {
  int data;
  struct node *next;
} Node;

// 定义队列结构体
typedef struct {
  Node *rear; // 指向队尾元素结点
} Queue;

// 初始化队列
void InitQueue(Queue *q) {
  q->rear = (Node *)malloc(sizeof(Node)); // 创建头结点
  q->rear->next = q->rear; // 头结点的next指针指向头结点本身，表示链表为空
}

// 入队列
void EnQueue(Queue *q, int data) {
  Node *new_node = (Node *)malloc(sizeof(Node)); // 创建新结点
  new_node->data = data;
  new_node->next = q->rear->next; // 新结点的next指针指向头结点，保持循环链表特性
  q->rear->next = new_node; // 队尾元素结点的next指针指向新结点
  q->rear = new_node; // 更新队尾指针为新结点
}

// 出队列
int DeQueue(Queue *q) {
  if (q->rear->next == q->rear) { // 队列为空，不能出队列
    printf("Queue is empty!\n");
    return -1;
  }
  Node *first_node = q->rear->next->next; // 获取队头元素结点
  int data = first_node->data; // 保存队头元素的数据
  q->rear->next->next = first_node->next; // 队头元素结点从队列中移除
  if (first_node == q->rear) { // 队列中只有一个元素时，出队列后队列为空
    q->rear = q->rear->next; // 队尾指针指向头结点
  }
  free(first_node); // 释放队头元素结点的内存空间
  return data;
}

二

希望循环队列中的元素都得到运用，现在需要设置一个标志域tag，以tag的值为0还是1来区分，尾指针和头指针值相同时的队列元素是空还是满，试编写与此结构相应的入队和出队算法

以下是循环队列的入队和出队算法，使用一个标志位tag表示队列的状态，0表示队列为空，1表示队列为满。

入队算法：
void Enqueue(int* queue, int queue_size, int* rear, int* tag, int element) {
 // 判断队列是否为满
 if (*tag == 1 && (*rear + 1) % queue_size == *front) {
  printf("Queue is full.\n");
  return;
 }
 // 将元素插入队列尾
 queue[*rear] = element;
 // 移动队列尾指针
 *rear = (*rear + 1) % queue_size;
 // 如果队列尾指针等于队列头指针，表示队列已满
 if (*rear == *front) {
  *tag = 1;
 }
}

出队算法：
int Dequeue(int* queue, int queue_size, int* front, int* rear, int* tag) {
 // 判断队列是否为空
 if (*tag == 0 && *front == *rear) {
  printf("Queue is empty.\n");
  return -1;
 }
 // 取出队列头元素
 int element = queue[*front];
 // 移动队列头指针
 *front = (*front + 1) % queue_size;
 // 如果队列头指针等于队列尾指针，表示队列已空
 if (*front == *rear) {
  *tag = 0;
 }
 return element;
}

这里的参数说明：

queue：指向循环队列数组的指针
queue_size：循环队列的大小
front：指向队列头的指针
rear：指向队列尾的指针
tag：队列状态的标志位
element：待入队或待出队的元素
在入队算法中，首先判断队列是否为满，如果队列已满则直接返回。否则将元素插入队列尾，并将队列尾指针后移一位。如果队列头指针等于队列尾指针，表示队列已满，将标志位tag设置为1。

在出队算法中，首先判断队列是否为空，如果队列为空则直接返回。否则取出队列头元素，并将队列头指针后移一位。如果队列头指针等于队列尾指针，表示队列已空，将标志位tag设置为0。最后返回取出的元素

三

利用线性表的顺序存储结构完成一个班级的一个学期的所有课程的管理，要求实现：增加、删除、修改学生的成绩记录等功能。线性表的长度设为全班的人数（35人），一个学期的课程设为3门，定义如下：

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

#define Max_length  2
typedef  struct {
	int  xh;         /* 学号 */
	char  n[10];  /* 姓名 */
	int   c1, c2, c3;  /* 3门课程成绩 */
} Element;
/* 在第i个记录的后面插入一个学生的记录算法 */
int Insert_list(int i, Element s[], int* n_pointer) {
	/* n_pointer存放已输入的最大记录数 */
	int j, n;
	n = *n_pointer;
	if ((n == Max_length) || (i < 1) || (i > n + 1)) return (0);
	for (j = n; j >= i; j--) s[j + 1] = s[j];   /* 移动 */
	printf("Input Data for inserting（XH  Name  C1  C2  C3）\n");
	scanf_s("%d %s %d %d %d", &s[i].xh, &s[i].n,20, &s[i].c1, &s[i].c2, &s[i].c3);
	n++;  *n_pointer = n; 	return (1);
}
/* 删除第i个学生的记录算法 */
int Delete_list(int i, Element s[], int* n_pointer) {
	int j, n;
	n = *n_pointer;
	if ((i < 1) || (i > n))  return (0);
	for (j = i + 1; j <= n; j++) { /* 移动 */
		s[j - 1].xh = s[j].xh; 	strcpy_s(s[j - 1].n, s[j].n);
		s[j - 1].c1 = s[j].c1;  	s[j - 1].c2 = s[j].c2; 	s[j - 1].c3 = s[j].c3;
	}
	n--;  *n_pointer = n;  return (1);
}
/* 查找学号为x算法 */
int Locate_list(Element s[], int n, int x) {
	int i;
	for (i = 1; i <= n; i++)  if (s[i].xh == x) return (i);
	return (0);
}
/* 修改学号为i的学生的记录函数 */
int Change_list(int i, Element s[]) {
	if ((i < 1) || (i > Max_length + 1)) return (0);
	printf("Input data for updating:\n");
	scanf_s(" %d %s %d %d %d", &s[i].xh, &s[i].n,20, &s[i].c1, &s[i].c2, &s[i].c3);
	return (1);
}
/* 打印已建立的数据记录，n是记录总数 */
void Print_list(Element s[], int n) {
	int i;
	if (n > Max_length)return;
	printf("   XH     Name     C1     C2     C3  \n");
	printf("-------------------------------------\n");
	for (i = 1; i <= n; i++)
		printf("%4d%10s%7d%7d%7d\n", s[i].xh, s[i].n, s[i].c1, s[i].c2, s[i].c3);
}

int main() {
	Element s[Max_length];
	int i, records = 0;
	for (i = 1; i <= Max_length; i++) Insert_list(i, s, &records);  /* 创建线性表 */
	Print_list(s, records);  /* 显示学生记录内容*/
	return 0;
}

编译环境：

visual studio 2022

四

单向链表的基本操作，创建一个由六个节点组成的单向链表：能够增加、删除、查找、移动节点。

#include  <stdio.h>
#include  <stdlib.h>
#include  <malloc.h>
#define   NULL  0
typedef struct Linear_chain_node {
	int data;
	struct Linear_chain_node* link;
}  NODE;
/* 建立单链表 */
NODE* Create_single_chain(int n)
{
	NODE* head, * p, * q;
	int i;
	p = (NODE*)malloc(sizeof(NODE));
	p->data = 0;
	p->link = NULL;
	head = p;
	for (i = 1; i <= n; i++)
	{
		q = (NODE*)malloc(sizeof(NODE));
		printf("Enter Data : "); scanf(" % d", &q->data);
		q->link = NULL;  p->link = q;  p = q;
	}
	return (head);
}
/* 单链表查找节点 */
int* Found(NODE* head, int x) {
	NODE* p;
	int pos = 0;
	p = head;
	while ((p->link != NULL) && (p->data != x)) { p = p->link; pos++; }
	if (p->link != NULL)
		return pos;
	else
		return (0);
}
/* 插入新结点（第i个结点后）*/
int Insert(NODE* head, int i, int x) 
{
	NODE* p, * q;
	int j;
	if (i <= 0)  return (0);
	q = head;
	j = 1;
	while ((j < i) && (q != NULL)) 
	{ q = q->link;  j++; }
	if (q == NULL)  
		return (0);
	p = (NODE*)malloc(sizeof(NODE));
	p->data = x;  
	p->link = q->link;  
	q->link = p;
	return (1);
}
/* 删除结点p的算法 */
int Delete(NODE* head, NODE* p) 
{
	NODE* q;
	if (p == head) {
		head = head->link;
		free(p);
		return (1);
	}
	q = head;
	while ((q->link != p) && (q->link != NULL)) q = q->link;
	if (q->link == NULL)  
		return (0);
	q->link = p->link;  
	free(p);
	return (1);
}
/* 求线性链表长度 */
int Length(NODE* head) {
	int n;
	NODE* p;
	n = 0;  
	p = head;
	while (p != NULL) 
	{
		n++;
		p = p->link;
	}
	return (n);
}
/* 将最大结点移到队尾 */
void Move(NODE* head) {
	NODE* p;   /* 遍历 */
	NODE* s;   /* p的前驱,末结点 */
	NODE* q;   /* 最大的结点 */
	NODE* r;   /* q的前驱 */
	s = head;  
	p = head->link;  
	q = head;
	while (p != NULL) 
	{
		if (p->data > q->data) 
		{
			r = s;  q = p;
		}
		s = p;
		p = p->link;
	}
	if (q != s) {
		if (q == head) 
		{ head = head->link; }
		else { r->link = q->link; }
		s->link = q;  
		q->link = NULL;
	}
}
/* 输出链表 */
void Print(NODE* head) 
{
	NODE* p;
	p = head;
	printf("Linear List : ");
	while (p != NULL) 
	{ printf(" % d\t", p->data);  
	printf("\n"); 
	p = p->link; }
	printf("\n");
}
/* 主函数 */
void main() {
	NODE* head, * p, * q;
	int i, j, l, x, n;
	printf("Enter node number for creating:");
	scanf(" % d", &n);    /* n=6 */
	head = Create_single_chain(n);
	Print(head);
	printf("Enter data for found:");
	scanf(" % d", &x);
	i = Found(head, x);
	if (i == 0) printf("No found node!\n");
	else printf("Found node at position: %d\n", i);
	printf("Enter data and position for inserting: ");
	scanf(" % d % d", &x, &i);
	n = Insert(head, i, x);
	if (n) printf("Insert succ！\n");
	else printf("Insert fail!\n");
	Print(head);
	printf("Enter position for deleting: ");
	scanf(" % d", &i);
	p = head;
	j = 0;
	while (p != NULL && j < i) { p = p->link; j++; }
	if (p == NULL)  printf("Not delete\n");
	n = Delete(head, p);
	if (n) printf("Delete succ\n");
	else  printf("Delete fail\n");
	Print(head);
	l = Length(head);
	printf("length = % d\n", l);
	Move(head);
	printf("Moving max data to tail : \n");
		Print(head);
}

五

用c语言建立单链表并实现：单链表的就地逆置。 将两个非递减有序单链表，合并成一个非递减链表。将两个非递减有序单链表，合并成一个非递增链表。编写一个主函数,调试上述算法

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

// 定义单链表结构体节点
typedef struct ListNode {
    int val;
    struct ListNode* next;
} ListNode;

// 将一个数组转换为单链表
ListNode* arrayToList(int arr[], int n) {
    if (n <= 0) {
        return NULL;
    }
    ListNode* head = (ListNode*)malloc(sizeof(ListNode));
    head->val = arr[0];
    head->next = NULL;
    ListNode* cur = head;
    for (int i = 1; i < n; i++) {
        ListNode* node = (ListNode*)malloc(sizeof(ListNode));
        node->val = arr[i];
        node->next = NULL;
        cur->next = node;
        cur = node;
    }
    return head;
}

// 打印单链表
void printList(ListNode* head) {
    while (head) {
        printf("%d ", head->val);
        head = head->next;
    }
    printf("\n");
}

// 单链表就地逆置
void reverseList(ListNode** head) {
    ListNode* prev = NULL;
    ListNode* cur = *head;
    while (cur != NULL) {
        ListNode* next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    *head = prev;
}

// 合并两个非递减有序单链表成一个非递减有序单链表
ListNode* mergeListsAsc(ListNode* l1, ListNode* l2) {
    ListNode* dummy = (ListNode*)malloc(sizeof(ListNode));
    dummy->val = 0;
    dummy->next = NULL;
    ListNode* cur = dummy;
    while (l1 != NULL && l2 != NULL) {
        if (l1->val <= l2->val) {
            cur->next = l1;
            l1 = l1->next;
        }
        else {
            cur->next = l2;
            l2 = l2->next;
        }
        cur = cur->next;
    }
    if (l1 != NULL) {
        cur->next = l1;
    }
    if (l2 != NULL) {
        cur->next = l2;
    }
    return dummy->next;
}

// 合并两个非递减有序单链表成一个非递增有序单链表
ListNode* mergeListsDesc(ListNode* l1, ListNode* l2) {
    ListNode* dummy = (ListNode*)malloc(sizeof(ListNode));
    dummy->val = 0;
    dummy->next = NULL;
    ListNode* cur = dummy;
    while (l1 != NULL && l2 != NULL) {
        if (l1->val >= l2->val) {
            cur->next = l1;
            l1 = l1->next;
        }
        else {
            cur->next = l2;
            l2 = l2->next;
        }
        cur = cur->next;
    }
    if (l1 != NULL) {
        cur->next = l1;
    }
    if (l2 != NULL) {
        cur->next = l2;
    }
    reverseList(&dummy->next);
    return dummy->next;
}

int main() {
    int arr1[] = { 1, 3, 5 };
    int arr2[] = { 2, 4, 6 };
    ListNode* l1 = arrayToList(arr1, 3);
    ListNode* l2 = arrayToList(arr2, 3);

    printf("l1: ");
    printList(l1);
    printf("l2: ");
    printList(l2);

    ListNode* mergedAsc = mergeListsAsc(l1, l2);
    printf("merged in ascending order: ");
    printList(mergedAsc);

    l1 = arrayToList(arr1, 3);
    l2 = arrayToList(arr2, 3);
    ListNode* mergedDesc = mergeListsDesc(l1, l2);
    printf("merged in descending order: ");
    printList(mergedDesc);

    return 0;
}

解析：

// 将一个数组转换为单链表//

这段代码定义了一个函数arrayToList()，其目的是将输入的数组转换为链表。函数接收两个参数：一个整数数组arr和一个表示arr长度的整数n。

首先，如果n小于等于0，那么函数返回空指针NULL，否则它会创建一个新的链表头节点，并将数组的第一个元素值存储到头节点的val成员中，将头节点的next指针设置为空指针。

然后，函数使用一个循环遍历数组中的剩余元素。在每次循环中，创建一个新的链表节点，并将当前元素的值存储到该节点的val成员中。将新节点的next指针设置为空指针，并将当前节点的next指针指向该新节点。最后，将当前节点更新为新节点，以便用于下一次循环。

当循环结束后，函数返回链表的头节点。这样，通过调用该函数并传入适当的参数，就可以将一个整数数组转换成一个链表。

Q:(ListNode*)malloc(sizeof(ListNode));这行是什么意思

**A:**这行代码使用了C语言中的动态内存分配函数malloc()，它在堆上分配了一块大小为sizeof(ListNode)的内存空间，并返回该内存块的起始地址。ListNode*表示这是一个指向ListNode类型对象的指针，因此该代码行创建了一个新的ListNode类型的对象，并将其地址存储在指针变量中。

六

利用栈实现数据的分类，要求当输入为偶数时进栈1，当输入为奇数时进栈2，最后分别从栈1和栈2输出偶数和奇数序列。/2023/4/24

#include<stdio.h>
#include <intrin.h>

typedef struct Stack {
    int* data;
    int top, size;
} Stack;

void push(Stack* s, int x)//入栈算法
{
    if (s->top < s->size)
    {
        s->top = s->top + 1;
        s->data[s->top] = x;
    }
    else printf("OVERFLOW");
}

int pop(Stack* s)//出栈算法
{
    if (s->top > 0)
    {
        s->top = s->top - 1;
        return s->data[s->top + 1];
    }
    else
    {
        printf("UNDERFLOW");
        return -1; // 出错返回-1
    }
}

void Print(Stack* s) // 输出栈中所有元素
{
    for (int i = 1; i <= s->top; i++)
    {
        printf("%d ", s->data[i]);
    }
    printf("\n");
}

int main()
{
    Stack even_stack, odd_stack;
    even_stack.top = 0;
    odd_stack.top = 0;
    even_stack.size = 100;
    odd_stack.size = 100;
    even_stack.data = (int*)malloc(even_stack.size * sizeof(int));
    odd_stack.data = (int*)malloc(odd_stack.size * sizeof(int));

    int n;
    printf("请输入一组数 (输入0以结束):\n");
    scanf_s("%d", &n);
    while (n != 0)
    {
        if (n % 2 == 0)
            push(&even_stack, 1);
        else
            push(&odd_stack, 2);
        scanf_s("%d", &n);
    }

    printf("偶数栈： ");
    Print(&even_stack);

    printf("奇数栈： ");
    Print(&odd_stack);

    free(even_stack.data);
    free(odd_stack.data);

    return 0;
}

七

Dijkstra algorithm 迪杰斯特拉算法

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

#define MAX_V 100

struct Edge {
    int src, dst;
    int weight;
};

struct Graph {
    int V;
    struct Edge* edges;
};

void init_graph(struct Graph* graph, int V) {
    graph->V = V;
    graph->edges = (struct Edge*)malloc(sizeof(struct Edge) * V * V);

}

void add_edge(struct Graph* graph, int src, int dst, int weight) {
    graph->edges[src * graph->V + dst].src = src;
    graph->edges[src * graph->V + dst].dst = dst;
    graph->edges[src * graph->V + dst].weight = weight;
}

void dijkstra(struct Graph* graph, int src) {
    int* dist = (int*)malloc(sizeof(int) * graph->V);
    int* prev = (int*)malloc(sizeof(int) * graph->V);


    for (int i = 0; i < graph->V; i++) {
        dist[i] = INT_MAX;
        prev[i] = -1;
    }

    dist[src] = 0;

    while (1) {
        int u = -1;

        for (int i = 0; i < graph->V; i++) {
            if (dist[i] < INT_MAX && (u == -1 || dist[i] < dist[u])) {
                u = i;
            }
        }

        if (u == -1) {
            break;
        }

        for (int i = 0; i < graph->V; i++) {
            if (dist[i] > dist[u] + graph->edges[u * graph->V + i].weight) {
                dist[i] = dist[u] + graph->edges[u * graph->V + i].weight;
                prev[i] = u;
            }
        }
    }

    for (int i = 0; i < graph->V; i++) {
        printf("The shortest distance from %d to %d is %d\n", src, i, dist[i]);
    }

    free(dist);
    free(prev);
}

int main() {
    struct Graph graph;

    init_graph(&graph, 5);

    add_edge(&graph, 0, 1, 4);
    add_edge(&graph, 0, 2, 1);
    add_edge(&graph, 1, 2, 2);
    add_edge(&graph, 1, 3, 7);
    add_edge(&graph, 2, 3, 9);
    add_edge(&graph, 3, 4, 2);

    dijkstra(&graph, 0);

    return 0;
}

八

实验：最短路径
利用图的最短路径原理为用户提供路径咨询，掌握求最短路径的算法并编程实现
设计一个旅游景点导游模拟程序，为来访的客人提供景点最短路径的信息查询服务，任意选取n个城市，构成一个有向带权图，图中顶点表示城市，边上的权值表示两点间的距离，根据用户指定的始点和终点输出相应的最短路径

/2023/5 22

#include <stdio.h>
#include <limits.h>

#define MAX_VERTICES 100

int graph[MAX_VERTICES][MAX_VERTICES];
int dist[MAX_VERTICES];
int visited[MAX_VERTICES];

void dijkstra(int start, int end, int num_vertices) {
    // 初始化距离数组和访问标记数组
    for (int i = 0; i < num_vertices; i++) {
        dist[i] = INT_MAX;
        visited[i] = 0;
    }

    // 起点到自身的距离为0
    dist[start] = 0;

    // 进行n-1次循环（n为顶点数），每次找出一个距离起点最近的未访问顶点，并更新它的邻接顶点的距离
    for (int i = 0; i < num_vertices - 1; i++) {
        int min_dist = INT_MAX;
        int u;

        // 找出一个距离起点最近的未访问顶点
        for (int j = 0; j < num_vertices; j++) {
            if (!visited[j] && dist[j] < min_dist) {
                min_dist = dist[j];
                u = j;
            }
        }

        visited[u] = 1;

        // 更新与u相邻的顶点的距离
        for (int v = 0; v < num_vertices; v++) {
            if (!visited[v] && graph[u][v] != -1 && dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v];
            }
        }
    }

    // 输出最短路径的长度
    printf("从顶点 %d 到顶点 %d 的最短距离为 %d\n", start, end, dist[end]);

    // 确定最短路径上的顶点
    int path[MAX_VERTICES];
    int index = 0;
    int current = end;
    path[index++] = current;

    while (current != start) {
        for (int i = 0; i < num_vertices; i++) {
            if (graph[i][current] != -1 && dist[i] + graph[i][current] == dist[current]) {
                current = i;
                path[index++] = current;
                break;
            }
        }
    }

    // 输出最短路径上的顶点
    printf("从顶点 %d 到顶点 %d 的最短路径为：: ", start, end);
    for (int i = index - 1; i >= 0; i--) {
        printf("%d ", path[i]);
    }
    printf("\n");
}

int main() {
    // 读入图的信息
    printf("输入[顶点数][边数]");
    int num_vertices;
    int num_edges;
    scanf_s("%d%d", &num_vertices, &num_edges);
   
    // 初始化图的邻接矩阵
    for (int i = 0; i < num_vertices; i++) {
        for (int j = 0; j < num_vertices; j++) {
            graph[i][j] = -1;
        }
    }

    // 读入边的信息
    for (int i = 0; i < num_edges; i++) {
        int source, dest, weight;
        printf("输入数据，参数分别是：[起点][终点][两点间的距离]\n");
        scanf_s("%d%d%d", &source, &dest, &weight);
        printf("___________________________________ \n");
        printf("|                                  |\n");
        printf("|    %d    ----%d----->   %d          |\n", source, weight, dest);
        printf("|__________________________________| \n");
        graph[source][dest] = weight;
    }

    dijkstra(0, num_vertices - 1, num_vertices);

    return 0;
}