线性表
顺序存储
#include "head.h"
#define OK 1
#define ERROR 0
#define SeqList_SIZE 20
typedef int ElementType;
typedef int Status;
typedef struct SeqList{
ElementType* data;
int length;
int MaxSize;
}SeqList;
Status InitSeqList(SeqList& a){
ElementType* q;
a.data = (ElementType*)malloc(SeqList_SIZE * sizeof (ElementType));
q = a.data;
a.length = 0;
a.MaxSize = SeqList_SIZE;
int i = 0;
for(i = 0; i < 10; i ++)
{
*q = i;
a.length ++ ;
q ++ ;
}
return OK;
}
Status CleaSeqList(SeqList& a){
if(!a.length)
return ERROR;
a.length = 0;
return OK;
}
Status PrintSeqList(SeqList & a){
if(!a.length)
{
printf("SeqList is empty\n");
return false;
}
int i;
for(i = 0; i < a.length; i ++)
printf("%d ", *(a.data + i));
puts("");
return OK;
}
Status Add(SeqList& a, int idx, int value){
if(idx < 1 || idx > a.length)
return ERROR;
int i;
for(i = a.length; i > idx; i --)
a.data[i] = a.data[i - 1];
a.length ++ ;
a.data[i] = value;
return OK;
}
Status Del(SeqList& a, int idx){
if(idx < 1 || idx > a.length)
return ERROR;
int i;
for(i = idx; i < a.length; i ++)
a.data[i] = a.data[i + 1];
a.length -- ;
return OK;
}
链式存储
#include "head.h"
#define mal_list (List)malloc(sizeof (struct ListNode))
#define OK 1
#define ERROR 0
typedef int ElementType;
typedef int Status;
typedef struct ListNode{
ElementType val;
ListNode* next;
}ListNode, *List;
Status InitList(List& list){
list = mal_list ;
list->next = NULL;
return OK;
}
Status InsertToTail(List& list, int value){
List p, s;
p = list;
while(p->next)
p = p->next;
s = mal_list ;
s->next = NULL;
s->val = value;
p->next = s;
return OK;
}
Status InsertToHead(List& list, int value){
List p = mal_list ;
p->val = value;
p->next = list->next;
list->next = p;
return OK;
}
Status RemoveIndex(List& list, int idx){
List p = list;
while(--idx && p)
p = p->next;
if(idx)
return ERROR;
List temp = p->next;
p->next = p->next->next;
free(temp);
return OK;
}
Status RemoveValue(List& _list, int value){
List list = _list;
while(list->next)
{
if(list->next->val == value)
{
list->next = list->next->next;
return OK;
}
else
list = list->next;
}
return ERROR;
}
// 在第idx个点后面插入value
Status Insert(List& list, int idx, int value){
List p = list;
while(idx --)
p = p->next;
if(idx ^ -1)
return ERROR;
List temp = mal_list ;
temp->val = value;
temp->next = p->next;
p->next = temp;
return OK;
}
Status ReverseList(List& list){
List a, b, c;
if(!list->next || !list->next->next)
return OK;
a = NULL, b = list->next;
while(b)
{
c = b->next;
b->next = a;
a = b; b = c;
}
list->next = a;
return OK;
}
List ReverseListCreateNew(List head){
if(!head || !head->next)
return head;
List res = ReverseListCreateNew(head->next);
head->next->next = head;
head->next = NULL;
return res;
}
List CreateList(int* arr, int len){
List phead, p, s;
phead = mal_list ;
phead->next = NULL;
p = phead;
int i = 0;
for(; i < len; i ++)
{
s = mal_list ;
s->next = NULL;
s->val = *(arr + i);
p->next = s;
p = p->next;
}
return phead;
}
Status PrintList(List list){
while(list->next)
{
list = list->next;
printf("%d ", list->val);
}
puts("");
return OK;
}
栈、队列和数组
栈
#include "head.h"
#define OK 1
#define ERROR 0
#define SeqStack_SIZE 10
#define SIZE_DELTA 2
const int Inf = 0x3f3f3f3f;
typedef int ElementType;
typedef int Status;
typedef struct SeqStack{
ElementType* top;
ElementType* base;
int size;
}SeqStack;
Status InitSeqStack(SeqStack& stack){
stack.base = (ElementType*)malloc(SeqStack_SIZE * sizeof (ElementType));
if(!stack.base)
return ERROR;
stack.size = SeqStack_SIZE ;
stack.top = stack.base;
return OK;
}
Status IsEmpty(SeqStack& stack){
if(stack.top == stack.base)
return true;
return false;
}
Status Push(SeqStack& stack, int val){
if(stack.top - stack.base >= stack.size - 2)
{
stack.base = (ElementType*)realloc(stack.base, (stack.size * SIZE_DELTA) * sizeof(SeqStack));
if(!stack.base)
return ERROR;
stack.top = stack.base + stack.size - 2;
stack.size *= SIZE_DELTA;
}
* stack.top ++ = val;
return OK;
}
ElementType Pop(SeqStack& stack){
if(stack.base == stack.top)
return Inf;
return *( -- stack.top);
}
Status Converstion(ElementType x){
ElementType res = 0;
SeqStack stack;
InitSeqStack(stack);
while(x)
{
Push(stack, x % 2);
x >>= 1;
}
while(!IsEmpty(stack))
printf("%d", Pop(stack));
puts("");
return OK;
}
h01
题目描述:
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <time.h>
#include <string.h>
#define OK 1
#define ERROR 0
#define SeqList_SIZE 20
typedef int ElementType;
typedef int Status;
#define stl srand((int)time(NULL))
typedef struct SeqList{
ElementType* data;
int length;
int MaxSize;
}SeqList;
void quick_sort(SeqList& s, int l, int r){
if(l >= r) return;
int x = s.data[(l + l) / 2], i = l - 1, j = r + 1;
while(i < j)
{
do i ++ ; while(s.data[i] < x);
do j -- ; while(s.data[j] > x);
if(i < j)
{
s.data[i] ^= s.data[j];
s.data[j] ^= s.data[i];
s.data[i] ^= s.data[j];
}
else
quick_sort(s, l, j), quick_sort(s, j + 1, r);
}
}
SeqList merge_SeqList(SeqList& s1, SeqList& s2){
int i = 0, j = 0;
int n = s1.length, m = s2.length;
SeqList t;
t.length = 0, t.MaxSize = n + m + 2;
t.data = (ElementType*)malloc((n + m + 2) * sizeof (ElementType));
ElementType* q = t.data;
while(i < n && j < m)
{
if(s1.data[i] <= s2.data[j])
*(q ++ ) = s1.data[i ++], t.length ++ ;
else
*(q ++ ) = s2.data[j ++], t.length ++ ;
}
while(i < n)*(q ++ ) = s1.data[i ++ ], t.length ++ ;
while(j < m)*(q ++ ) = s2.data[j ++ ], t.length ++ ;
return t;
}
Status InitSeqList(SeqList& a){
ElementType* q;
a.data = (ElementType*)malloc(SeqList_SIZE * sizeof (ElementType));
q = a.data;
a.length = 0;
a.MaxSize = SeqList_SIZE;
int i = 0;
for(i = 0; i < 10; i ++)
{
*(q ++) = rand() % 100;
a.length ++ ;
}
return OK;
}
Status CleaSeqList(SeqList& a){
if(!a.length)
return ERROR;
a.length = 0;
return OK;
}
Status PrintSeqList(SeqList & a){
if(!a.length)
{
printf("SeqList is empty\n");
return false;
}
int i;
for(i = 0; i < a.length; i ++)
printf("%d ", *(a.data + i));
puts("");
return OK;
}
Status Add(SeqList& a, int idx, int value){
if(idx < 1 || idx > a.length)
return ERROR;
int i;
for(i = a.length; i > idx; i --)
a.data[i] = a.data[i - 1];
a.length ++ ;
a.data[i] = value;
return OK;
}
Status Del(SeqList& a, int idx){
if(idx < 1 || idx > a.length)
return ERROR;
int i;
for(i = idx; i < a.length; i ++)
a.data[i] = a.data[i + 1];
a.length -- ;
return OK;
}
void solve(){
SeqList L1, L2;
InitSeqList(L1), InitSeqList(L2);
PrintSeqList(L1), PrintSeqList(L2);
quick_sort(L1, 0, L1.length - 1), quick_sort(L2, 0, L2.length - 1);
SeqList res = merge_SeqList(L1, L2);
PrintSeqList(res);
}
int main(){
stl;
solve();
return 0;
}
h02
题目描述:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define mal_list (List)malloc(sizeof (struct LinkList))
#define OK 1
#define ERROR 0
#define SIZE 20
typedef int ElementType;
typedef int Status;
typedef struct LinkList{
ElementType val;
LinkList* next;
}LinkList, *List;
Status InitList(List& l){
l = mal_list;
l->next = NULL;
return OK;
}
Status InsertToHead(List& head, int val){
List p = mal_list;
p->val = val;
p->next = head->next;
head->next = p;
return OK;
}
Status PrintList(List list){
while(list->next)
{
list = list->next;
printf("%d ",list->val);
}
puts("");
return OK;
}
List merge_List(List l1, List l2){
List p = mal_list;
p->next = NULL;
List res = p;
while(l1 && l2)
{
if(l1->val <= l2->val)
p->next = l1, l1 = l1->next;
else
p->next = l2, l2 = l2->next;
p = p->next;
}
while(l1)
p->next = l1, l1 = l1->next, p = p->next;
while(l2)
p->next = l2, l2 = l2->next, p = p->next;
p->next = NULL;
return res;
}
void solve(){
List l1, l2;
InitList(l1), InitList(l2);
int i = 9;
for(; i >= 1; i -= 2)
InsertToHead(l1, i);
for(i = 10; i >= 2; i -= 2)
InsertToHead(l2, i);
PrintList(l1);
PrintList(l2);
List res = merge_List(l1->next, l2->next);
PrintList(res);
}
int main (){
solve();
return 0;
}
一、线性表
(一)线性表的定义和基本操作
(二)线性表的实现
顺序存储
链式存储
线性表的应用
二、栈、队列和数组
栈和队列的基本概念
栈和队列的顺序存储结构
栈和队列的链式存储结构
栈和队列的应用
特殊矩阵的存储和压缩
三、树与二叉树
(一)树的基本概念
(二)二叉树
二叉树的定义及其主要特征
二叉树的顺序存储结构和链式存储结构
二叉树的遍历
线索二叉树的基本概念和构造
(三)树、森林
树的存储结构
森林与二叉树的转换
树和森林的遍历
(四)树与二叉树的应用
二叉排序树
平衡二叉树
哈夫曼(Huffman)树的哈弗曼编码
四、图
(一)图的基本概念
(二)图的存储及基本操作
邻接矩阵法
邻接表法
邻接多重表、十字链表
(三)图的遍历
深度优先搜索
广度优先搜索
四)图的基本应用
最小(代价)生成树
最短路径
拓扑排序
关键路径
五、查找
查找的基本概念
顺序查找法
分块查找法
折半查找法
B树及其基本操作、B+树及其基本概念
散列(Hash)表
字符串模式匹配(KMP)
查找算法的分析及应用
六、排序
(一)排序的基本概念
(二)插入排序
直接插入排序
折半插入排序
(三)起泡排序(bubble sort)
(四)简单选择排序
(五)希尔排序(shell sort)
(六)快速排序
(七)堆排序
(八)二路归并排序(merge sort)
(九)基数排序
(十)外部排序
(十一)各种内部排序算法的比较
(十二)排序算法的应用
题目清单
讲义
第1讲 时间复杂度、矩阵展开 一、时间、空间复杂度 只考虑次数,不考虑常数。常见复杂度有:O(1)、O(n)、O(sqrt(n))、O(n^k)、O(logn)、O(nlogn) 考题:2011-1、2012-1、2013-1、2014-1、2017-1、2019-1 二、矩阵展开 矩阵的按行展开、按列展开,展开后下标从0开始。 考题:2016-4、2018-3、2020-1
第2讲 线性表
第3讲 栈与队列
第4讲 树的基本概念、二叉树、树和森林
第5讲 二叉排序树、平衡树、表达式树
第6讲 Huffman编码和Huffman树
第7讲 图的基本概念、存储、遍历、拓扑排序
第8讲 最小生成树、最短路、关键路径
第9讲 基本概念、顺序、折半、分块查找法、B/B+树
第10讲 散列(Hash)表、字符串模式匹配(KMP)
第11讲 基本概念、插入、冒泡、选择、希尔、快速、堆、归并排序
第12讲 桶排序、基数排序、外部排序
第21讲 红黑树和并查集
第一讲 排序与进位制
成绩排序
给定学生的成绩单,成绩单中包含每个学生的姓名和分数,请按照要求将成绩单按成绩从高到低或从低到高的顺序进行重新排列。
对于成绩相同的学生,无论以哪种顺序排列,都要按照原始成绩单中靠前的学生排列在前的规则处理。
输入格式
第一行包含整数 $N$,表示学生个数。
第二行包含一个整数 $0$ 或 $1$,表示排序规则,$0$ 表示从高到低,$1$ 表示从低到高。
接下来 $N$ 行,每行描述一个学生的信息,包含一个长度不超过 $10$的小写字母构成的字符串表示姓名以及一个范围在 $0 \sim 100$ 的整数表示分数。
输出格式
输出重新排序后的成绩单。
每行输出一个学生的姓名和成绩,用单个空格隔开。
数据范围
$1 \le N \le 1000$
输入样例1:
4
0
jack 70
peter 96
Tom 70
smith 67
输出样例1:
peter 96
jack 70
Tom 70
smith 67
输入样例2:
4
1
jack 70
peter 96
Tom 70
smith 67
输出样例2:
smith 67
jack 70
Tom 70
peter 96
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
const int N = 1010;
struct Stu{
string name;
int score, id;
bool operator<(const Stu& s)const{
return score ^ s.score ? score < s.score : id < s.id;
}
bool operator>(const Stu& s)const{
return score > s.score ? score > s.score : id < s.id;
}
}p[N];
int main(){
int n; cin >> n;
bool flg; cin >> flg;
for(int i = 0; i < n; i ++)
{
string name;
int score;
cin >> name >> score;
p[i] = {name, score, i};
}
if(flg)
stable_sort(p, p + n);
else
stable_sort(p, p + n, greater<Stu>());
for(int i = 0; i < n; i ++)
cout << p[i].name << " " << p[i].score << endl;
return 0;
}
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
const int N = 1010;
struct Stu{
string name;
int score, id;
}p[N];
int main(){
int n; cin >> n;
bool flg; cin >> flg;
for(int i = 0; i < n; i ++)
{
string name;
int score;
cin >> name >> score;
p[i] = {name, score, i};
}
if(flg)
sort(p, p + n, [=](Stu& p1, Stu& p2){
return p1.score ^ p2.score ? p1.score < p2.score : p1.id < p2.id;
});
else
sort(p, p + n, [=](Stu& p1, Stu& p2){
return p1.score ^ p2.score ? p1.score > p2.score : p1.id < p2.id;
});
for(int i = 0; i < n; i ++)
cout << p[i].name << " " << p[i].score << endl;
return 0;
}
第二讲 链表、日期问题
第三讲 表达式求值
第四讲 树的遍历
第五讲 二叉搜索树与表达式树
第六讲 Huffman树
第七讲 拓扑排序
第八讲 最小生成树、最短路
第十讲 哈希表和KMP
第十一讲 排序
第十二讲 排序、多路归并和摩尔投票法
第十三讲 DFS
第十四讲 模拟、递推、BFS
第十五讲 字符串处理、递归和背包问题
第十六讲 高精度和因式分解
第十七讲 枚举和位运算
第十八讲 矩阵、计算几何和前缀和
第十九讲 推公式、最短路、思维题
第二十讲 哈希表、双指针、序列型DP
第二十一讲 红黑树和并查集