[数据结构与算法]数据结构笔记一

基本概念

什么是数据结构

// 计算函数运行时间 使用 time.h头文件
#include <stdio.h>
#include <time.h>
#include <math.h>
#define MAXK 1e7
#define MAX 10
clock_t start, stop;
double duration;

double f1(double a[], double x)
{
	double sum = 0;
	for (int i = 0; i < MAX; i++)
	{
		sum += a[i] * pow(x, i);
		
	}
		
	return sum;
}
double f2(double a[], double x)
{
	double sum = a[MAX-1];
	for (int i = MAX - 1; i > 0; i--)
	{
		sum = a[i - 1] + x * sum;
	}
		
	return sum;
}
int main(void)
{
	double a[MAX];
	double sum1, sum2;
	a[0] = 1;
	for (int i = 1; i <= MAX - 1; i++)
	{
		a[i] = (1.0 / i);
	}
		
	start = clock();
	for(int i = 1 ; i < MAXK ; i++)
		f1(a, 1.1);
	stop = clock();
	sum1 = f1(a,1.1);
	duration = ((double)(stop - start)) / CLK_TCK/ MAXK;
	printf("%6.2E %lf\n", duration , (double)(stop - start));
	printf(" %lf\n", sum1);

	start = clock();
	for (int i = 1; i < MAXK; i++)
		f2(a, 1.1);
	stop = clock();
	sum2 = f2(a,1.1);
	duration = ((double)(stop - start)) / CLK_TCK /MAXK;
	printf("%6.2E  %lf\n", duration, (double)(stop - start));
	printf("%lf\n", sum2);

	
	return 0;
}

抽象数据类型
抽象数据结构包括

1. 类型名称
2. 数据对象集
3. 操作集

什么是算法

算法的定义
1.一个有限指令集
2.接受一些输入
3.产生输出
4.在一定步骤后终止
每一条指令
1.有明确的目标
2.计算机能处理的范围内
3.描述应不依赖于任何一种计算机语言以及具体
实现手段
什么是好的算法

• 1.时间复杂度
  • 1.for 语句复杂度 = for本身的复杂度 * for 内部语句的复杂度
  • 2 if - else 语句 复杂度 为 各个分支语句 最大复杂度
• 2.空间复杂度

算法示例 - 最大子列和
1.暴力算法

int maxsum = 0;
for( int i = 0 ; i < N ; i++)
	for(int j = i ; j < N ;j++)
	{
		int thatsum = 0;
		for(int k = i ; k <= j ;k++ )
		{
			thatsum += a[k];
		}
		if( maxsum < thatsum)
			maxsum = thatsum;
	}	

#include <stdio.h>
#define N  10
int f(int a[], int n)
{
	int thissum, maxsum = 0;
	int i, j;
	for (i = 0; i < n; i++)
	{
		thissum = 0;
		for (j = i; j < n; j++)
		{
			thissum += a[j];
			if (thissum > maxsum)
			{
				maxsum = thissum;
			}
		}
	}
	return maxsum;
}

int main()
{
	int a[] = { 1,2 ,2,3,5,-1,-2,2,19,1 };
    f(a,  N);
	return 0;
}

for( int i = 0 ; i < N ; i++)
	for(int j = i ; j < N ;j++)
	{
		int thatsum = 0;
		for(int k = i ; k <= j ;k++ )
			thatsum += a[j] ; // 这里
		if( maxsum < thatsum)
			maxsum = thatsum;
	}	

2.分而治之

// 伪算法
int DivideAndConquer( int List[], int left, int right )
{ /* 分治法求List[left]到List[right]的最大子列和 */
    int MaxLeftSum, MaxRightSum; /* 存放左右子问题的解 */
    int MaxLeftBorderSum, MaxRightBorderSum; /*存放跨分界线的结果*/

    int LeftBorderSum, RightBorderSum;
    int center, i;

    if( left == right )  { /* 递归的终止条件，子列只有1个数字 */
        if( List[left] > 0 )  return List[left];
        else return 0;
    }

    /* 下面是"分"的过程 */
    center = ( left + right ) / 2; /* 找到中分点 */
    /* 递归求得两边子列的最大和 */
    MaxLeftSum = DivideAndConquer( List, left, center );
    MaxRightSum = DivideAndConquer( List, center+1, right );

    /* 下面求跨分界线的最大子列和 */
    MaxLeftBorderSum = 0; LeftBorderSum = 0;
    for( i=center; i>=left; i-- ) { /* 从中线向左扫描 */
        LeftBorderSum += List[i];
        if( LeftBorderSum > MaxLeftBorderSum )
            MaxLeftBorderSum = LeftBorderSum;
    } /* 左边扫描结束 */

    MaxRightBorderSum = 0; RightBorderSum = 0;
    for( i=center+1; i<=right; i++ ) { /* 从中线向右扫描 */
        RightBorderSum += List[i];
        if( RightBorderSum > MaxRightBorderSum )
            MaxRightBorderSum = RightBorderSum;
    } /* 右边扫描结束 */

    /* 下面返回"治"的结果 */
    return Max3( MaxLeftSum, MaxRightSum, MaxLeftBorderSum + MaxRightBorderSum );
}

在线扫描

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

例题
#include <iostream>
#define N 100000
using namespace std;
void f(int a[], int n)
{
	int i = 0;
	int thissum = 0, maxsum = 0;
	int cnt1 = 0;
	int x1 = a[0] ,x2 = a[0], y1 = a[0];
	for ( i = 0; i < n; i++)
	{
		if (a[i] >= 0)
			break;
	}
	if (i == n)
	{
		cout << 0 << ' ' << a[0] << ' ' << a[n-1];
		return;
	}
	for (i = 0; i < n; i++)
	{
		thissum += a[i];
		if (thissum < 0)
		{
			thissum = 0;
			cnt1++;
			if (cnt1 == 1)
			{
				x1 = a[i + 1];
			}
			else if (cnt1 == 2)
			{
				x2 = a[i + 1];
			}
			else if (cnt1 == 3)
			{
				cnt1 = 2;
				x2 = a[i + 1];
			}
		}	
		else if (thissum > maxsum)
		{
			maxsum = thissum;
			y1 = a[i];
			if (cnt1 == 2)
			{
				x1 = x2;
				cnt1 = 0;
			}
		}

	}
    if (maxsum == 0)
        {cout << 0 << ' ' <<  0 << ' '<< 0;return;}
	cout << maxsum << ' ' <<  x1 << ' '<< y1;
}

int main()
{
	int n;
	int a[N];
	cin >> n;
	for (int i = 0;i < n ; i++)
	{
		cin >> a[i];
	}
	f(a, n);
	return 0;
}

线性结构

线性表及其实现

// 单链表的删除和插入
#include <stdio.h>
#include <iostream>
#include <malloc.h>
typedef struct node {
	int data;
	struct node* next;
}Node;
typedef struct node* linklist;

int ListInsert(linklist L, int i, int dat);
int ListDelete(linklist L, int i);
linklist Init(linklist L);

using namespace std;

int main()
{

	linklist L = NULL;
	L = Init(L);
	int i = 0;
	i = ListInsert(L, 1, 1);
	i = ListInsert(L, 2, 2);
	i = ListInsert(L, 3, 4);
	i = ListDelete(L, 1);
	cout << L->next->data << endl;
	return 0;
}
// 初始化表头，创建头节点，L为指向头节点的指针
linklist Init(linklist L)
{
	L = (linklist)malloc(sizeof(Node));
	if (L == NULL)
	{
		cout << "error" << endl;
		return NULL;
	}
	(L)->next = NULL;
	return L;
}
// 插入节点
int ListInsert(linklist L, int i, int dat)
{
	linklist p, s;
	int j = 1;
	p = L;
	while (p && j < i)
	{
		p = p->next;
		j++;
	}
	if (p == NULL || j > i)
	{
		return 0;
	}
	s = (linklist)malloc(sizeof(Node));
	if (s == NULL)
	{
		cout << "error" << endl;
		return 0;
	}
	s->data = dat;
	s->next = p->next;
	p->next = s;
	return 1;
}
//删除节点
int ListDelete(linklist L, int i)
{
	linklist p, q;
	p = L;
	int data;  
	int j = 1;
	while (p->next && j < i) // 定位在待删除前的节点前 
	{
		p = p->next;
		j++;
	}
	if (j > i || p->next == NULL)
	{
		cout << "error" << endl;
		return 0;
	}
	q = p->next;  //q为待删除的节点
	data = q->data;
	p->next = q->next;
	free(q);
	cout << data << endl;
	return 1;
}

List Merge(List L1, List L2)
{
	List p, q;
	List L = (List)malloc(sizeof(struct Node));
	L->Next = NULL;
	p = L;
	L1 = L1->Next; L2 = L2->Next;
	while (L1 != NULL && L2 != NULL)
	{
		if (L1->Data >= L2->Data)
		{
			p->Next = L2;
			q = L2->Next;
			p = p->Next;
			p->Next = L1;
			L2 = q;
			L1 = L1->Next;
		}
		else if (L1->Data <= L2->Data)
		{
			p->Next = L1;
			q = L1->Next;
			p = p->Next;
			p->Next = L2;
			L1 = q;
			L2 = L2->Next;
		}
	}
	while (L1 != NULL)
	{
		p->Next = L1;
		p = p->Next;
		L1 = L1->Next;
	}
	while (L2 != NULL)
	{
		p->Next = L2;
		p = p->Next;
		L2 = L2->Next;
	}
	p->Next = NULL;
	return L;
}

栈

• 操作集
  • 1.生成空堆栈
  • 2.判断堆栈S是否已满
  • 3.将元素item压栈
  • 4.判断堆栈是否为空
  • 5.删除并返回栈顶元素

栈的顺序储存

//栈的顺序储存
#include <stdio.h>
#define MAXSIZE 4
typedef struct sqstack {
	int data[MAXSIZE] = {0};  // 存放了所有数据元素
	int top = -1;  // -1代表堆栈空
}Stack;
int Push(Stack *L, int e);
int Pop(Stack* L);
int main()
{
	Stack L;
	Push(&L, 2);
	Push(&L, 4);
	Push(&L, 8);
	Pop(&L);
	Pop(&L);
	Pop(&L);
	return 0;
}

int Push(Stack *L, int e)  //插入   检查上界
{
	if (L->top - 1 >= MAXSIZE)
	{
		printf("overflow error");
		return -1;
	}
	else
	{
		L->top++;
		L->data[L->top] = e;
		return 1;
	}
}
int Pop(Stack *L) //弹出   检查下界
{
	if (L->top == -1)
	{
		printf("the squence is empty pop error");
		return -1;
	}
	else
	{
		printf("%d\n", L->data[L->top]);
		L->top--;
		return 1;
	}
}

//栈的顺序储存 （栈的空间共享）
#include <stdio.h>
#define MAXSIZE 4
typedef struct sqstack {
	int data[MAXSIZE] = {0};  // 存放了所有数据元素
	int top1 = -1;  // -1代表堆栈空
	int top2 = MAXSIZE;
}Stack;
int Push(Stack *L, int e, int stacknumber);
int Pop(Stack* L, int stacknumber);
int main()
{
	Stack L;
	Push(&L, 2,1);
	Push(&L, 4,1);
	Push(&L, 8,1);
	Pop(&L,1);
	Pop(&L,1);
	Pop(&L,2);
	return 0;
}

int Push(Stack *L, int e, int stacknumber)  //插入   检查上界
{
	if (L->top2 - L->top1 == 1)
	{
		printf("error");
		return -1;
	}
	if (stacknumber == 1)
	{
		L->top1++;
		L->data[L->top1] = e;
		return 1;
	}
	else if (stacknumber == 2) {
		L->top2--;
		L->data[L->top2] = e;
		return 1;
	}
}
int Pop(Stack *L, int stacknumber) //弹出   检查下界
{
	if (stacknumber == 1)
	{
		if (L->top1 == -1) {
			printf("the stack is empty.error");
			return -1;
		}
		else {
			printf("%d", L->data[L->top1]);
			L->top1--;
			return 1;
		}
	}
	else if (stacknumber == 2)
	{
		if (L->top2 == MAXSIZE) {
			printf("the stack is empty.error");
			return -1;
		}
		else {
			printf("%d", L->data[L->top2]);
			L->top2++;
			return 1;
		}
	}
}

栈的链式储存

#include <stdio.h>
#include <malloc.h>
#include <iostream>
typedef struct node {
	int data;
	struct node* next;
} Stacknode, *linkstack;
linkstack S;
using namespace std;
int Initstack(linkstack * s);
int Push(linkstack *top, int dat);
int Pop(linkstack *top);
int main()
{
	Initstack(&S);
	Push(&S, 1) ;
	Push(&S, 2);
	Push(&S, 4);
	Pop(&S) ;
	Pop(&S);
	Pop(&S);
	return 0;
}
int Initstack(linkstack *top)
{
	*top = NULL;
	return 1;
}
int Push(linkstack *top, int dat)
{
	linkstack p = (linkstack)malloc(sizeof(Stacknode));
	if (p == NULL)
	{
		printf("overflow");
		return -1;
	}
	p->data = dat;
	p->next = *top;
	*top = p;
	return 1;
}
int Pop(linkstack *top)
{
	linkstack p;
	if (*top == NULL)
	{
		printf("the stack is empty");
		return -1;
	}
	p = *top;
	printf("%d", p->data);
	*top = p->next;
	free(p);
	return 1;
}

栈的应用

• 中缀表达式的求值
• 递归
  什么时候使用递归
  1 定义是递归的 斐波那契数列
  2 数据结构是递归的 比如链表
  3 问题的求解的方法是递归的 汉诺塔问题

队列

名称：队列
数据对象集：线性表

• 操作集
  • 生成空队列
  • 判断队列是否满
  • 插入元素
  • 判断是否为空
  • 删除元素

队列的顺序储存

#include <stdio.h>
#include <malloc.h>
#include<iostream>
#define MAXSIZE 5
using namespace std;
typedef struct queue {
	int data[MAXSIZE];
	int front;
	int rear;
}Queue;
int Enqueue(Queue* q, int dat);
int Dequeue(Queue* q);
int InitQueue(Queue* q);
int main(void)
{
	Queue q;      
	InitQueue(&q);
	Enqueue(&q, 1);Enqueue(&q, 2);Enqueue(&q, 4);
	Dequeue(&q);Dequeue(&q);Dequeue(&q);
	return 0;
}
int InitQueue(Queue* q)
{
	q->front = 0;
	q->rear = 0;
	return 1;
}
int Enqueue(Queue* q, int dat)
{
	if ((q->rear + 1) % MAXSIZE == q->front)
	{
		cout << "overflow" << ' ' << "error" << endl;
		return -1;
	}
	q->data[q->rear] = dat;
	q->rear++;
	return 1;
} 
int Dequeue(Queue* q)
{
	if (q->front == q->rear)
	{
		cout << "overflow" << ' ' << "error" << endl;
		return -1;
	}
	cout << q->data[q->front] << endl;
	q->front++;
	return 1;
}

队列的链式储存

#include <stdio.h>
#include <malloc.h>
#include<iostream>
#define MAXSIZE 5
using namespace std;
typedef struct node {
	int data;
	struct node* next;
}Node;
typedef struct qnode {
	struct node* front;
	struct node* rear;
}Qnode, *Queue;

int Enqueue(Queue q, int dat);
int Dequeue(Queue q);
int InitQueue(Queue q);
int main(void)
{
	Qnode q;      
	InitQueue(&q);
	Enqueue(&q, 1); Enqueue(&q, 2); Enqueue(&q, 4);
	Dequeue(&q);
	Dequeue(&q);
	Dequeue(&q);
	return 0;
}
int InitQueue(Queue q)
{
	(q)->front = NULL;
	(q)->rear = NULL;
	return 1;
}
int Enqueue(Queue Q, int dat)
{
	Node* p = (Node*)malloc(sizeof(Node));
	if (p == NULL) {
		cout << "error" << endl;
		return -1;
	}
	p->data = dat;                  
	if (Q->rear == NULL){    //   首节点需特殊处理
		p->next = NULL;
		Q->rear = p; 
		Q->front = p;
	}else {
		Q->rear->next = p;
		Q->rear = p;
	}
	return 1;
} 
int Dequeue(Queue Q)
{
	if (Q->front == NULL) {
		cout << "error" << endl;
		return -1;
	}                                     //没得删
	cout << Q->front->data << endl; 
	Node* p = Q->front;
	Q->front = Q->front->next ;
	if (Q->rear == p)              // 删完了
		Q->rear = Q->front;
	free(p);
	return 1;
}

练习

// 多项式乘法和加法
#include <stdio.h>
#include <malloc.h>
#include<iostream>
using namespace std;
typedef struct node {
	int coe;  //系数
	int exp;  // 指数
	struct node* next;
}Node, * polynomial;

polynomial read(void);   // 读取函数
polynomial merge(polynomial L1, polynomial L2); // 多项式加法
polynomial dot(polynomial L1, polynomial L2);  // 多项式乘法
void print(polynomial L);  // 打印函数

int main(void)
{
	polynomial L1 = read();
	polynomial L2 = read();
	polynomial L3 = merge(L1,L2);
	polynomial L4 = dot(L1, L2);
	print(L4);
	print(L3);
	return 0;
}

int Init(polynomial* L)  // 初始化链表头节点
{
	*L = (polynomial)malloc(sizeof(Node));
	if (*L == NULL) {
		cout << "error";
		return -1;
	}
	(*L)->next = NULL;
	return 1;
}
polynomial read(void)
{
	polynomial L;
	polynomial front, rear;
	int n;
	Init(&L);
	front = rear = L; 
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		polynomial p = (polynomial)malloc(sizeof(Node));
		if (p == NULL) {
			cout << "error";
			return NULL;
		}
		cin >> p->coe >> p->exp; // fill 
		p->next = NULL;
		rear->next = p;
		rear = p;
	}
	return front;
	
}
polynomial attach(polynomial *rear, int coe, int exp)  // 向结果多项式中插入新节点
{
	polynomial p = (polynomial)malloc(sizeof(Node));
	if (p == NULL) {
		cout << "error";
		return NULL;
	}
	p->coe = coe;
	p->exp = exp;
	p->next = NULL;
	(*rear)->next = p;
	(*rear) = p;
	return (*rear);
}
polynomial merge(polynomial L1, polynomial L2)
{
	polynomial L;
	polynomial front, rear;
	Init(&L);
	front = rear = L;
	L1 = L1->next; L2 = L2->next;
	while (L1 && L2)   // 比较指数大小 大的输出 指针后移 （一次操作一个链表）
	{
		if (L1->exp > L2->exp){
			rear = attach(&rear,L1->coe,L1->exp);
			L1 = L1->next;
		}
		else if (L1->exp < L2->exp) {
			rear = attach(&rear, L2->coe,L2->exp);
			L2 = L2->next;
		}
		else if (L1->exp == L2->exp){
			if (L2->coe + L1->coe == 0)
			{
				L2 = L2->next;
				L1 = L1->next;
				continue;
			}
			rear = attach(&rear, L2->coe + L1->coe, L2->exp);
			L2 = L2->next;
			L1 = L1->next;
		}
	}
	while (L1)     //输出剩余项
	{
		rear = attach(&rear, L1->coe, L1->exp);
		L1 = L1->next;
	}
	while (L2)
	{
		rear = attach(&rear, L2->coe, L2->exp);
		L2 = L2->next;
	}
	return L;

}
polynomial dot(polynomial L1, polynomial L2)   // 逐项插入法
{
	polynomial L;
	polynomial rear;
	polynomial t1, t2;
	polynomial p, q;
	Init(&L);
	t1 = L1->next;
	t2 = L2->next;
	rear = L;
	while (t1 && t2)// 保证t1为非空的前提下 用t1的第一项与t2的每一项相乘 将结果保留到结果多项式
	{
		attach(&rear, t1->coe * t2->coe, t1->exp + t2->exp);
		t2 = t2->next;
	}
	if (t1)
		t1 = t1->next;
	while (t1)
	{
		t2 = L2->next, rear = L;  // 指针重新指向表头
		while (t2)
		{
			int coe = t1->coe * t2->coe;   
			int exp = t1->exp + t2->exp;    //计算指数和系数
			while ( rear->next && exp < rear->next->exp)  
				rear = rear->next;  // 将指针定位到结果多项式中节点指数比新节点小的前一项上 插入
			if (rear->next && exp == rear->next->exp) {
				rear->next->coe += coe;  
				if (rear->next->coe == 0) { // 如果系数为零 删除节点
					q = rear->next;
					rear->next = q->next;
					free(q);
				}
			}
			else  {
				p = (polynomial)malloc(sizeof(Node));
				if (p == NULL) {
					cout << "error" << endl;
					return NULL;
				}
				p->coe = coe;
				p->exp = exp;
				q = rear->next;
				rear->next = p;
				p->next = q;
			}
			t2 = t2->next;
		}
		t1 = t1->next;
	}
	return L;
}
void print(polynomial L)
{
	if (L->next == NULL)
	{
		cout << 0 << ' ' << 0 << endl;
		return;
	}
	L = L->next;
	while (L)
	{
		int flag = 1;
		if (L->next == NULL) flag = 0;
		if (flag)
			cout << L->coe << ' ' << L->exp << ' ';
		else
			cout << L->coe << ' ' << L->exp;
		L = L->next;
	}
	cout << endl;
}