数据结构代码期末考试

### 数据结构代码复习要点

#### 一、线性表操作实现
对于线性表的操作，常见的有创建、插入、删除等。以下是基于数组和链表两种不同存储方式下的简单例子。

- **顺序表（Array-based List）**

#include<stdio.h>
#define MAXSIZE 100
typedef struct {
    int data[MAXSIZE];
    int length;
} SqList;

// 插入元素
void Insert(SqList *L, int i, int e){
    if(L->length >= MAXSIZE || i<1 || i>L->length+1) return; // 越界处理
    for(int j=L->length;j>=i;j--) L->data[j]=L->data[j-1]; // 后移元素
    L->data[i-1]=e;
    (L->length)++;
}

- **单向链表（Singly Linked List）**

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

typedef struct Node{
    int value;
    struct Node* next;
}Node,*LinkList;

// 创建节点并初始化
Node* CreateNode(int val){
    Node* newNode=(Node*)malloc(sizeof(Node));
    newNode->value=val;
    newNode->next=NULL;
    return newNode;
}

// 尾插法建立链表
void BuildList(LinkList &head,int n){
    head=CreateNode(0); // 建立头结点
    LinkList p=head,q;
    while(n--){
        q=CreateNode(rand()%100);
        p->next=q;p=q;
    }
    free(p);
}

#### 二、栈与队列的应用场景模拟
理解如何利用栈解决括号匹配问题以及使用队列完成层次遍历等问题有助于加深对这两种特殊线性表的理解[^2]。

- **括号匹配检测函数**

int Match(char str[]){
    char stack[100],top=-1;
    for(int i=0;str[i]!='\0';++i){
        switch(str[i]){
            case '(':case '[':case '{':stack[++top]=str[i];break;
            case ')':
                if(top==-1||stack[top]!='('){return 0;}
                top--; break;
            case ']':
                if(top==-1||stack[top]!='['){return 0;}
                top--; break;
            case '}':
                if(top==-1||stack[top]!='{'){return 0;}
                top--; break;
        }
    }
    return top==-1?1:0;
}

#### 三、树形结构构建及其遍历方法
掌握二叉树的各种遍历方式——前序、中序、后序遍历，并能编写相应的递归或非递归版本的程序是十分重要的。

- **二叉树定义及先序遍历**

typedef struct TreeNode{
    int key;
    struct TreeNode *leftChild,*rightChild;
}*BiTree,BiTNode;

// 先序遍历
void PreOrder(BiTree T){
    if(T!=NULL){
        printf("%d ",T->key);
        PreOrder(T->leftChild);
        PreOrder(T->rightChild);
    }
}

#### 四、图论基础概念实践
了解邻接矩阵表示法下求解最短路径Floyd-Warshall算法的具体流程能够帮助更好地应对涉及网络流优化类题目。

- **弗洛伊德多源最短路算法**

const int INF = 99999999;
for(k=0;k<n;++k)
	for(i=0;i<n;++i)
		for(j=0;j<n;++j)
			if(Dist[i][k]+Dist[k][j]<Dist[i][j])
				Dist[i][j]=Dist[i][k]+Dist[k][j];

以上展示了部分典型的数据结构编程练习案例，这些知识点覆盖了大多数本科阶段计算机科学专业所教授的内容范围，在准备期末考试期间应当重点关注上述几个方面并通过实际编码加以巩固[^1]。