数据结构与C语言

发表于 | 分类于
字数统计: 6,863

基于实验楼

C语言实验

语言热度排行 果然是犹豫不决学Java…

“不管你懂多少延续、闭包、异常处理，只要你不能解释为什么 while(*s++=*t++); 的作用是复制字符串，那你就是在盲目无知的情况下编程，就像一个医生不懂最基本的解剖学就在开处方”

Linux 不以文件后缀来区分可执行文件，Linux 下的可执行文件后缀理论上是可以任意更改的。

C语言教程

基本命令

编译：gcc -c **.c 生成对象文件

链接：gcc -o ** **.o 生成没有后缀的可执行文件

同时进行：gcc -o ** **.c

执行：./**

数据类型

gcc 编译器为每个int类型分配四个字节（32 个二进位）。在存储单元中的存储方式是：用整数的补码形式存放。所以当 4 个字节的整数类型取值范围是 -2^31 到（2^31-1）。无符号的基本整型表示为 unsigned int，和 int 类型占有的字节数相同，取值范围是 0 到（2^32-1）

字符型数据在存储时，并不是把该字符本身存放到内存单元中，而是把该字符相应的 ASCII 码值存放到该存储单元中。——真正代表了数据含义的是数据类型，而不是二进制本身。用小写表示的字符的 ASCII 码比用大写表示的 ASCII 码大 32。

存储字符串常量时还要自动在其末尾加上 ‘\0’ 作为字符串结束的标志，所以"b"会占用两个字节而'b'是一个字节

要将一个字符串存放在变量中，必须使用字符数组。C 语言中没有字符串类型，字符串都是存储在字符型数组中的。处理字符串时要加上string.h头文件

在强制类型转换时，得到一个所需类型的中间数据，而原来变量的类型未发生变化

C 库<stdlib.h>中的函数 int atoi(const char *str)把参数 **str** 所指向的字符串转换为一个整数（类型为 int 型）

atoi(),itoa() 与强制类型转换的区别

atoi(),itoa()是整型数和字符串表示的整型数字之间的转换，是函数调用实现的。对内建基本类型之间的强制类型转换是在编译时实现的，对数值可能会截断、重新解释（不能用(int)直接把表示数字的字符串转成数字，好像要 -'0')

运算符

自增运算符 (++) 和自减运算符 (–) 只能用于变量，而不能用于常量或表达式。如 5++ 或者 (a+b)++ 都是不合法的

字符 (char) 型数据和整形数据进行运算，就是把字符的 ASCII 代码与整形运算

输入输出

在 printf 函数中，在格式符 “f” 的前面加 “7.2”。表示的意思是在输出时，指定数据占 7 列，其中小数占 2 列。主要是使小数点对齐，输出时更加美观

  • %d：按照整型数据的实际长度输出。
  • %md：以m指定的字段宽度输出，右对齐。加 -左对齐
  • %ld：输出长整型数据。
  • %mld：输出指定宽度的长整型数据。

在输入函数时，用 %c 格式声明输入字符时，空格字符和转义字符都是作为有效字符输入，所以输入时中间不要有空格

main函数的参数argc和argv

int main(int argc,char *argv[]) = int main(int argc,char **argv)其参数argc和argv用于运行时,把命令行参数传入主程序

int argc英文名为arguments count(参数计数)。运行程序传送给main函数的命令行参数总个数,包括可执行程序名,其中当**argc=1时表示只有一个程序名称,此时存储在argv[0]**中.

char **argv:英文名为arguments value/vector(参数值)。用来存放指向字符串参数的指针数组！指针数组！指针数组！不是字符串本身每个元素指向一个参数,空格分隔参数,其长度为argc.

  • argv[0] 指向程序运行时的全路径名
  • argv[1]指向程序在DOS命令中执行程序名后的第一个字符串
  • argv[2] 指向执行程序名后的第二个字符串
  • argv[argc]为NULL

参考Eastmount的博客

命令行运行程序时，要在可执行文件名后加上参数

条件语句

while和do…while

和 while 语句不同， do...while 语句中的 while（）；后面是有“；”的

另外，当 while 后面的表达式的第一次值为“真”时，两种循环得到的结果是相同的；否则，二者结果不相同(do…while会先执行一次）

要注意的细节

  • #include<stdio.h>不要忘记写#和.h
  • scanf()函数中的表列是地址表列，要加&，数组不用加
  • float的精度只有6~7位，double是15~16位，long double是18~19位
  • 在 Linux 系统下，Ｃ 源文件若调用了 math 库里的函数，则编译时要加上-lm（是字母 l ，不是数字１），表示链接到 math 库。
  • 打印数组时要换行可以用一个全局变量整除来控制

C语言知识点

字符

  • c = getchar(); putchar(c); 输入结尾判定getchar() != EOF
  • 通过getchar()获得的数字实际上是一个该数字的ASCII码，用于数值计算时要用c - '0'

数组

  • a == &a[0]
  • 每个元素是同一数据类型，只能逐个引用(常用for循环)，不能一次引用整个数组。
  • 编译器会为数组分配一段连续内存，二维数组先行后列
  • 定义可以用常量和符号常量，如#define SIZE 10 int a[SIZE];,但一定不能包含变量(访问可用变量)。为了便于后续更改，一般采用符号常量
  • 定义的同时对全部元素赋初值，可以不指定数组长度，如int a[] = {0,1,2,3,4}; 对于二维数组，第一维可以不指定但第二维必须指定 （emmm，发布博文时报错，可能是双大括号的原因，这里删去了，试下能发布的话就是这个原因）
  • 一维数组用例：冒泡排序
  • 二维数组用例：矩阵最大值及行列号——打擂台法

字符数组与字符串

  • 字符数组：char a[] = {'a','b','c','d'}; 长度为4
  • 字符串：char a[] = "abcd"; 以双引号赋值时，系统自动加上'\0'结束符，长度为5
    • <string.h>
    • gets(str); puts(str);
    • strcat(str1,str2); strlen(str); strcpy(str1,str2); strcmp(str1,str2);

函数化结构

  • 在程序中用到的所有函数，必须“先定义，后使用”
  • 自定义的函数要在main函数调用之前声明或定义。 函数声明的作用是把有关函数的信息（函数名、函数类型、函数参数的个数与类型）通知编译系统，在进行到 main 函数调用时知道他们是函数而不是变量或其他对象。
  • 有参函数在调用函数时，主调函数通过参数向被调函数传输数据，要注意被调用函数返回值的类型
  • 在定义函数中指定的形参，在未出现函数调用时，他们并不占内存中的存储单元。在发生函数调用时，函数形参被临时分配内存单元；调用结束，形参单元被释放。所以要注意函数内部变量的作用域
  • C语言中函数不能嵌套定义，但是可以嵌套调用
  • 要访问其他源文件的变量：extern ——用头文件的方式更好#ifndef....#define....#endif
  • 要自己的变量不被访问：static 初始化一次，一直占用空间，循环调用时会共享

指针

  • 变量是对程序中数据存储空间的抽象
  • 指针变量的类型，是指针变量所指向的变量的类型，而不是自身的类型

注意：多维数组中指针的各种运算

数据结构

数据结构实验

时空复杂度

在计算时间复杂度的时候，先找出算法的基本操作，然后根据相应的各语句确定它的执行次数，再找出 T(n) 的同数量级（它的同数量级有以下：1，log(2)n，n，n log(2)n ，n 的平方，n 的三次方，2 的 n 次方，n!），找出后，f(n) = 该数量级，若 T(n)/f(n) 求极限可得到一常数 c，则时间复杂度 T(n) = O(f(n))。

计算空间复杂度主要看可变部分，包括动态分配的空间，以及递归栈所需的空间等。这部分的空间大小与算法有关。一个算法所需的存储空间用 f(n)表示：S(n)=O(f(n))。其中 n 为问题的规模，S(n)表示空间复杂度。

线性表

  1. 集合中必存在唯一的一个”第一个元素”；
  2. 集合中必存在唯一的一个”最后的元素”；
  3. 除最后元素之外，其它数据元素均有唯一的”后继”；
  4. 除第一元素之外，其它数据元素均有唯一的”前驱”。

线性表有顺序和链式两种存储结构

顺序表

易随机存取，已使用的空间存储密度大；不易增删，空间固定难扩充

1
2
3
4
5
6
typedef struct
{
    Elemtype *elem;	//存储空间基址
    int length;		//当前长度
    int size;		//当前分配的表长大小
}SqList;

插入：先判断表是否已满 –> 判断插入位置是否越界 –> 从最后一个元素开始向后移动一位 –> 插入值，length + 1；平均移动一半元素 T(n) = O(n)

归并算法

T(n) = O(n + m)

1
2
3
4
5
6
7
8
9
10
void merge(SqList *A,SqList *B,SqList *C)
{
    int i=1,j=1,k=1;
    while(i <= A->length && j <= B->length)
        if(A->elem[i] <= B ->elem[j]) C->elem[k++] = A->elem[i++];
    else C->elem[k++] = B->elem[j++];
    while(i <= A->length) C->elem[k++] = A->elem[i++];
    while(i <= B->length) C->elem[k++] = B->elem[j++];
    C->length = A->length + B->length;
}
链表
1
2
3
4
5
typedef struct LNode
{
	ElemType data; // 数据域
	struct LNode *next; // 指针域
}LNode, *LinkList;

LinkList h头指针数据域为空，指针域指向单链表的第一个节点，可以避免对链表的第一个结点做特殊处理。因为对于无头结点的空表，插入值时可以直接对第一个结点的数据域赋值，而无需新建一个结点，或者直接改变第一个指针指向的地址为新结点

尾结点指针域为NULL

LNode *p; 常用指向结点的指针变量p，一般直接赋值为某个已存在结点

p = (LinkList)malloc(sizeof(LNode)); free(p); 为要插入的新结点分配空间，删除某结点要释放空间

相比于头插法，尾插法需要多一个尾指针

另外，对于删除操作，可以使用一个暂存已删除结点的avail链表，下次分配时先用链表中的结点，并可以用指针操作在O(1)的复杂度实现整个链表的删除

反转链表

由于链表不支持随机访问，所以交换头尾值的方法并不可行，最好还是直接改变指针域方向

1
2
3
4
5
6
7
8
9
10
11
12
LNode reverseList(LinkList head) {
    LNode next = null;
    LNode pre = null

    while (head != null) {
        next = head.next;
        head.next = pre;
        pre = head;
        head = next;
    }
    return pre;
}
循环链表

通常只设一个尾指针

连接两个单循环链表：O(1)

1
2
3
4
p = RA -> next; // 找到A的头结点
RA -> next = RB -> next -> next; //A尾连B的第一个结点，注意不是头结点
free(RB -> next); //记得删除B的头结点
RB -> next = p; //B尾连A头
双向链表
1
2
3
4
5
typedef struct dlnode
{
    ElemType data;
    struct dlnode *prior,*next;
}DLNode,*DLinkList;

删除结点

1
2
3
p -> prior -> next = p -> next;
p -> next -> prior = p -> prior;
free(p);
双向循环链表

没有空指针域

栈和队列(受限线性表)

栈

通常我们称表尾端为栈顶，表头端为栈底。栈上溢是一种出错状态，下溢则是一种正常状态，常用作程序转移控制条件

可以解决例如数值转换、括号匹配、迷宫求解、表达式求值和汉诺塔等等问题。

也有顺序存储结构和链式存储结构两种表示方法

顺序实现结构体：

1
2
3
4
5
typedef struct{
	SElemType *base;	//栈尾指针
	SElemType *top;		//栈顶指针
	int size;			//栈的大小
}SqStack;

链式实现结构体：

1
2
3
4
typedef struct node{
    ElemType data;
    struct node *next;
}StackNode;

对于链栈，若新申请一个结点时t = NULL 则表示链满；申请成功用头插法插入到top结点前并更新top

多栈共享存储空间：两个栈的栈底分别设在存储空间的两端，向中间延伸，相遇时溢出。

队列

允许插入元素的一端称为队尾，允许删除元素的一端称为队头

应用于操作系统调度任务队列。

顺序实现：

1
2
3
4
typedef struct{
    ElemType elem[MAXSIZE];
    int rear,front;
}SeQueue;

由于队首指针会不断向后移动，前面空间无法利用，造成一种假溢出，于是可以将首尾连起来，构成循环队列。为了区分队满队空，要留出一个空间，队空 sq -> front == sq -> rear 队满sq -> front == (sq -> rear + 1) % MAXSIZE

链表实现：

1
2
3
4
5
6
7
8
9
typedef struct QNode{
	QElemType data;
	struct QNode *next;
}QNode, *QueuePtr;

typedef struct{
	QueuePtr front;	//队头指针
	QueuePtr rear;	//队尾指针
}LinkQueue;

入队时空链表要特殊处理，因为此时都指向同一个结点(对头指针多做一个指向p结点的操作)：

1
2
3
4
5
6
7
8
void In_LQueue(LQueue  *Lq,ElemType x){
    QNode *p;
    p = (QNode*)malloc(sizeof(QNode));
    p -> data = x;
    p -> next = NULL;
    if(Lq -> rear == NULL) Lq -> front = Lq -> rear = p;
    else {Lq -> rear -> next = p; Lq -> rear = p;}
}

出队时同理，当成为空表时，对尾结点多做一个指向新的头结点的操作。

树

用孩子兄弟法将任意的一棵树转成一个没有右孩子二叉树。

树不能为空，二叉树可以为空。二叉树左右子树不能交换，而树的左右子树可以交换

二叉树重要性质
  • 第 i 层最多 $2^{i-1}$ 个结点
  • k 层树最多 $2^k-1$ 个结点
  • $n_0 = n_2 + 1$
完全二叉树性质

假设对各节点从上到下，从左到右依次编号1~n,则对任意节点a编号i，有 ：

  • 当n为偶数时，n1=1，n为奇数时，n1=0
  • 如果i=1,则节点i是根节点，无双亲
  • 如果i>1,则节点i的双亲节点为$\lfloor i/2\rfloor$
  • 如果2i<=n，则i的左孩为2i，如果2i>n，则i无左孩
  • 如果2i+1<=n,则i的右孩为2i+1，否则i无右孩

顺序存储：由于位置隐含了亲子关系，故可用顺序存储的索引来表示关系，元素按在完全二叉树的顺序存储。问题是有很多空闲空间且不便于修改

二叉链式存储：

1
2
3
4
5
typedef struct BiTNode
{
	TElemType data;	//数据
	struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

三叉链表多一个双亲指针

遍历

以递归的方式先序遍历：

1
2
3
4
5
6
7
8
9
Status PreOrderTraverse(BiTree T, void (*visit)(TElemType))
{
	if (T)
	{
		visit(T->data);
		PreOrderTraverse(T->lchild, visit);
		PreOrderTraverse(T->rchild, visit);
	}
}

用栈实现迭代的中序遍历：

1
2
3
4
5
6
7
8
9
10
11
12
void iterInorder(treePointer node){
    int top = -1;
    treePointer stack[MAX_STACK_SIZE];
    for(;;){
        for(;node;node = node -> lchild)
            push(node);
        node = pop();
        if(!node) break;
        printf("%d",node -> data);
        node = node -> rchild;
    }
}

用队列实现层序遍历：

1
2
3
4
5
6
7
8
9
10
11
12
13
void LevelOrder(BinTree BT) {
    if (!BT) return;
    Queue Q; 
    BinTree T; 
    Q = CreatQueue(MaxSize); //创建变初始化队列 
    Add(Q,BT); 
    while(!IsEmpty(Q)){ 
        T = Delete(Q); 
        printf("%d ", T->Data);    //访问队列中的结点 
        if (T->Left) Add(Q,T->Left); 
        if (T->Right) Add(Q,T->Right); 
    } 
}

由二叉树的先/后/层序遍历结合一个中序遍历可以唯一确定一个二叉树

递归判断二叉树相等：

1
2
3
int equal(BinTree first,BinTree second){
	return ((!first) && (!second) || (first && second && (first -> data == second -> data) && equal(first -> lchild,second -> lchild) && equal(first -> rchild,secnd -> rchild)));
}
线索二叉树

充分利用空指针域，存放中序遍历的前驱或后继。要设置一个标志位表明存放的是指向孩子的指针还是指向前驱或后继的指针

则可以在O(n)时间内实现中序遍历

堆

基于完全二叉树，对关键字值有特殊的约束——可以用数组实现

从堆顶删除，从堆底插入，中途可能要做多次调整

常用来实现OS中的优先级队列

插入大顶堆：

1
2
3
4
5
6
7
8
9
10
11
12
13
void insert_max_heap(element item,int *n){
    int i;
    if(HEAP_FULL(*n)){
        fprintf(stderr,"the heap is full.\n");
        exit(1);
    }
    i = ++(*n);
    while((i !=1)&&(item.key > heap[i/2].key)){
        heap[i] = heap[i/2];  // 比待插入元素值小则下沉到左子树
        i /= 2;
    }
    heap[i] = item;
}
最大-最小堆

各层交替为最小层和最大层，根结点位于最小层

插入删除操作检查从根到待插入位置路径上的相关结点，根据值大小进行相关调整

应用：双端优先队列

双端堆

根结点无元素，左子树是最小堆，右子树是最大堆

若 i 是最小堆中的一个结点，则在最大堆中对应的同一位置结点是 $ i + 2^{\lfloor log_2 i \rfloor -1}$ 对应位置相互移动时无需调整，在插入时要用这种方式腾出一个位置

二叉搜索树

所有关键字都不同(所以在插入操作中要先判断是否重复)，中序遍历有序

迭代查找：

1
2
3
4
5
6
7
8
tree_pointer search(tree_pointer tree,int key){
    while(tree){
	if(key == tree -> data) return tree;
    else if (key < tree -> data) tree = tree -> left_child;
    else tree = tree -> right_child;
    }
    return null;
}

删除有两个子树的非叶结点：用左子树中最大元素或右子树中最小元素代替被删除结点位置——不同于AVL树，没有平衡要求

平衡二叉树

对树高有约束的二叉搜索树，左右两个子树的高度差的绝对值不超过 1，并且左右两个子树都是一棵平衡二叉树

构造与调整方法平衡二叉树的常用算法有红黑树、AVL、Treap 等。

最小二叉平衡树的节点的公式如下 $F(n)=F(n-1)+F(n-2)+1$ 这个类似于一个递归的数列，可以参考 Fibonacci 数列，1 是根节点，F(n-1)是左子树的节点数量，F(n-2)是右子树的节点数量

哈弗曼树

也称最优二叉树，它是带权路径长度最小的二叉树。

常用于解决最短、最少类构造问题

败者树(选择树)

每个父结点记录较小子树，一直向上比较，直至根结点表示所有记录中最小的结点——区别于堆，非叶结点并不是记录，而是比较结果

常用于外部排序的有序段多路平衡归并，可大幅减少比较次数。$O(nlog_2 k)$

森林

转为二叉树：先将每个树转成二叉树，再把后一个树挂在前一个树的右孩子位置

树的后根遍历—森林中序遍历—二叉树中序遍历 ，先序三者对应

并查集

指针由孩子结点指向父亲结点

由于没有重复元素，可以用数组实现，索引表示元素值，值域表示其双亲结点，根结点父亲用-1表示

合并：让一棵树的根指针直接指向另一个树的根

合并可能产生退化问题，优化方式：

应用：等价类

图

在有向图的邻接表存储中，链表代表的是该顶点的出边表 ，逆邻接表存储入边表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/*
 * 邻接表存储结构
 */
typedef struct EdgeNode
{
	int adjvex;	//顶点的位置
	struct EdgeNode *next; //指向下一条边的指针
}EdgeNode, *EdgeLink;

typedef struct VexNode
{
	VexType data;	//顶点数据
	EdgeNode *firstEdge;	//指向第一条依附该顶点的边的指针
}VexNode, AdjList[MAX_NUM];

typedef struct
{
	AdjList adjList;
	int vexNum, edgeNum;	//顶点数和边数
}ALGraph;
DFS&BFS

深度优先搜索是树的先根遍历的推广，广度优先搜索是树的按层次遍历的推广。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
/*
 * 递归从第i个结点深度优先遍历图
 */
void DFS(ALGraph G, int i)
{
	EdgeLink p;
	visited[i] = TRUE;
	printf("%c ", G.adjList[i].data);
	p = G.adjList[i].firstEdge;
	while (p)
	{
		if (!visited[p->adjvex])
		{
			DFS(G, p->adjvex);
		}
		p = p->next;
	}
}

/*
 * 深度优先遍历
 */
Status DFSTraverse(ALGraph G)
{
	int i;
	for (i = 0; i < MAX_NUM; i++)
	{
		visited[i] = FALSE;
	}
	for (i = 0; i < G.vexNum; i++)
	{
		if (!visited[i])
		{
			DFS(G, i);
		}
	}
	return OK;
}

/*
 * 广度优先遍历
 */
Status BFSTraverse(ALGraph G)
{
	int i;
	EdgeLink p;
	LinkQueue Q;
	InitQueue(&Q);
	for (i = 0; i < MAX_NUM; i++)
	{
		visited[i] = FALSE;
	}
	for (i = 0; i < G.vexNum; i++)
	{
		if (!visited[i])
		{
			visited[i] = TRUE;
			printf("%c ", G.adjList[i].data);
			EnQueue(&Q, i);
			while (!IsEmpty(Q))
			{
				DeQueue(&Q, &i);
				p = G.adjList[i].firstEdge;
				while (p)
				{
					if (!visited[p->adjvex])
					{
						visited[p->adjvex] = TRUE;
						printf("%c ", G.adjList[p->adjvex].data);
						EnQueue(&Q, p->adjvex);
					}
					p = p->next;
				}
			}
		}
	}
	return OK;
}

无向图中的极大连通子图称为连通分量，如果是有向图中的任意一对顶点都有路径，那么这个就是强连通图，相应的它的极大连通子图就称为强连通分量。

一个连通图的一个极小连通子图，它包含所有顶点，但足以构成一棵树的 n-1 条边，加一条边必定会形成环，这个就称为生成树

关节点：删除该点及关联边后的新图至少含两个连通分支

双连通图：不含关节点的连通图

最小生成树

权值最小的生成树为最小生成树，可以用

  • kruskal（克鲁斯卡尔）算法：按权值递增加边，保证加入后不构成环路——中间可能构成森林
  • Prim（普里姆）算法：从单一节点树开始加边并构成一个树——中间始终是一个树
  • Sollin算法：第一步形成包含所有树的森林，之后每一步为每棵树选一条边——森林融合成树
单源多目标最短路径

Dijkstra 算法采用的是贪心策略 ，具体实现

完全最短路径

法一：多次调用Dijkstra 算法

法二：计算代价矩阵

判断任意两个顶点之间是否存在一条路径，可以通过传递闭包矩阵和自反传递闭包矩阵解决

说实话这部分，没看太懂…开学考试完了再回头好好理解一下

算法汇总

最大子序和
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<stdio.h>
#define SIZE 13
int longestsum(int n[]);


int main()
{
	int a[SIZE];
	int i,rs;
	printf("please input %d number:\n",SIZE);
	for(i =0;i < SIZE;i++){	
	scanf("%d",&a[i]);}
	rs = longestsum(a);
	printf("The longest subquence sum is %d",rs);
	return 0;
}

int longestsum(int n[])
{
	int thissum=0,i,maxsum;
	maxsum = n[0];
	for(i =0;i < SIZE;i++){
		thissum += n[i];
		if(thissum > maxsum){maxsum = thissum;}
		else if(thissum < 0){thissum = 0;}
	}
	return maxsum;
}

更多常规算法

一元多项式相加 O(m + n)

特别注意：两系数之和为0的情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
int poltn_add(Node *&A,Node *&B)
{
    Node *p,*q,*p1,*m;
    p=A->next;
    p1=A;
    q=B->next;
	while (p&&q)
	{
		if (p->exp < q->exp)
		{
			p = p->next;
			p1 = p1->next;
		}
		else
		{
			if (p->exp > q->exp)
			{
				m = q;
				q = q->next;
				m->next = p;
				p1->next = m;
				p1 = m;
			}
			else
			{
				p->coef = p->coef + q->coef;
				if (p->coef != 0)
				{
					p = p->next;
					p1 = p1->next;
					m = q;
					m = q;
					q = q->next;
					free(m);
				}
			}
		}
	}
    return 0;
}

如果是更多的多项式相加，可以创建中间多项式，用两两相加实现

多项式相乘，也可以分解成一系列的加法运算

更详细解法

等价关系和等价类

定义：集合S上的关系≡≡,称为S上为等价关系，当且仅当它在S上是对称的，自反的，传递的。

时间和空间的开销是O(m+n).

关键步骤：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
printf("Enter a pair of numbers (-1 -1 to quit):" );
//循环输入等价关系的元素对
scanf("%d%d",&i,&j);
while(i>=0)
{
   x=(node_pointer)malloc(sizeof(node));
   if(IS_FULL(x))
   {
      fprintf(stderr,"the memory is full\n");
      exit(1);
   }
   //插入到第i个链表的前端
   x->data=j;
   x->link=seq[i];
   seq[i]=x;
   x=(node_pointer)malloc(sizeof(node));
   if(IS_FULL(x))
   {
      fprintf(stderr,"the memory is full\n");
      exit(1);
   }
   //插入到第j个链表的前端
   x->data=i;
   x->link=seq[j];
   seq[j]=x;
   printf("Enter a pair of numbers (-1 -1 to quit):" );
   scanf("%d%d",&i,&j);
}

分别插入到对方的链表中。输出时每遍历到一个新的位置，改变其标志位，以后不再输出。

稀疏矩阵十字链表存储 O(max{col,row} + terms)

多种存储方式

在十字链表中，数组的每一行的非零元素结点构成一个带头结点的循环链表，每一列的非零元素结点也构成一个带头结点的循环链表，这种组织方法使同一非零元素结点既处在某一行的链表中，又处在某一列的链表中。因此非零元素结点中设有两个指针域：指针域down指向其同列的下一个非零元素的结点，right域指向其同行的下一个非零元素结点。除这两个域外，结点中还应设有存放该非零元素的行值、列值、元素值的域。

结构体：

1
2
3
4
5
6
7
8
9
10
typedef  int ElemType;
typedef struct OLNode{
	int row, col;
	union 
	{
		struct OLNode *next;	//表头结点使用next域
		ElemType e;				//表中元素结点使用e域
	}uval;
	struct OLNode *down, *right;
}OLNode,*OLink;

详细解释

用三元组法比较简单可用数组实现，转置时直接在新的数组中交换原来的行列即可。这种转置的复杂度很高 O(row col terms)

改进：先确定原矩阵中每列非零元素对应转置矩阵的每行非零元素位置，就可以从起始位置开始处理

矩阵乘法：…以后再看

迷宫问题

回溯法

字符串匹配

对朴素串匹配 O( n * m)进行改进：可以先比较第一个和最后一个字符，可以在一定程度上减少比较次数

KMP算法O( n + m)：主串不回退，模式串的后缀与前缀在多大程度上重合，next数组首位为0，第二位为1，之后是前后缀匹配的长度或将前后缀匹配数组后移一位，next数组首位置-1