2.4 应用

2.1 顺序

2.2 链式

尾插法

空间复杂度:

O(1)

#include
#include
#define LENGTH sizeof(struct node)
//定义一个节点
int len;//全局变量n
typedef struct node
{
	int Coffficient;
	int Exponent;
	struct node* next;
}*Pnode,Node;
//创建一个单链表(尾插法)
Pnode Create_List()
{
	Node * p,* tail, *head;
	int a,b;
	
	head = (Node*)malloc(LENGTH);//原型应为malloc（1*LENGTH），1省略
	tail = head;
	tail->next = NULL;
	printf("请输入结点个数:");
	scanf_s("%d", &len);
	printf("请输入元素,系数= ， 指数=:\n");
	for (int i = 0; i < len; i++)
	{
		scanf_s("%d,%d", &a,&b);
			p = (Node*)malloc(LENGTH);
			p->Coffficient=a;
			p->Exponent = b;
			tail->next = p;
			p->next = NULL;
			tail = p;
	}
	return head;//f返回头结点
}
//按指数排序
void Sort_Linklist1(Node* phead) {//冒泡排序
	Node* p = phead->next;
	Node* q;
	int temp1,temp2, i=0;
	for (; i < len-1; i++, p = p->next) {
		for (q = p->next; q!= NULL; q = q->next) {

			if (p->Exponent < q->Exponent) {
				temp1 = p->Exponent;
				p->Exponent = q->Exponent;
				q->Exponent = temp1;
				temp2 = p->Coffficient;
				p->Coffficient = q->Coffficient;
				q->Coffficient = temp2;
			}
		}
	}	
}
//比较函数
int compare(int Exponent1, int Exponent2) {
	if (Exponent1 > Exponent2)
		return 1;
	if (Exponent1Coffficient = a;
	p->Exponent = b;
	p->next = NULL;
	(*temp)->next = p;
	*temp = p;
}
Pnode Add_List(Node* p1, Node* p2) {
	Node* front,*rear;
	p1 = p1->next;//从头结点的下一节点开始遍历
	p2 = p2->next;
	int sum;
	rear = (Node*)malloc(LENGTH);
	front = rear;
	while (p1 && p2) {
		switch (compare(p1->Exponent, p2->Exponent)) {
		case 1:
			Attach(p1->Coffficient, p1->Exponent, &rear);
			p1 = p1->next;
			break;
		case -1:
			Attach(p2->Coffficient, p2->Exponent, &rear);
			p2= p2->next;
			break;
		case 0:
			sum = p1->Coffficient + p2->Coffficient;
			Attach(sum, p2->Exponent, &rear);
			p1 = p1->next;
			p2 = p2->next;
			break;
		}
	}
	for (; p1; p1 = p1->next)//p2为空循环结束后继续遍历p1
		Attach(p1->Coffficient, p1->Exponent, &rear);
	for(;p2;p2=p2->next)//p1为空循环结束后继续遍历p2
		Attach(p2->Coffficient, p2->Exponent, &rear);
	rear->next = NULL;
	return front;
}

//遍历链表
void Print_List(Node* phead)
{
	Node* p = phead->next;//跳过头结点进行遍历
	while (p != NULL)//尾结点为空时终止（尾结点的指针域为空）
	{
		printf("%dX^%d\t", p->Coffficient,p->Exponent);
		p = p->next;
	}printf("\n");
}

int main()
{
	Node* s1,*s2,*s3;
	printf("请先创建链表\n");
	printf("输入Polynomial1");
	s1= Create_List();
	printf("指数从大到小排序后：\n");
	Sort_Linklist1(s1);
	Print_List(s1);
	printf("输入Polynomial2");
	s2= Create_List();
	Sort_Linklist1(s2);
	printf("指数从大到小排序后：\n");
	Print_List(s2);
	s3=Add_List(s1, s2);
	printf("多项式相加后：\n");
	Print_List(s3);
	return 0;
}

3. 栈和队列

3.1 定义及特点

栈:

队:

特点:

栈:后进先出

队列:先进先出

3.2 应用

3.3 栈的表示和实现

1. 数据类型定义

SElemType是指元素类型

2. 顺序栈

1. 初始化

2. 判断是否为空及长度

3. 清空及释放

delete s.base 释放了数组的内存,但指针还是指向这块内存,只是这块内存不能被访问,所有将它们设为null

4. 入栈

5. 出栈

3. 链表

1. 初始化及是否为空

2. 入栈、出栈及取栈顶

**4.递归

见算法:递归

1. 缺点及转化

3.4 队列的表示和实现

1. 数据类型定义

2.顺序队列

front rear是表示指针,但不是指针变量,不是真正的指针

1. 初始化

2.求队列长度

3.入队

4.出栈

5.取队头元素

3. 链队列

1. 初始化

2. 销毁

3. 入队

4.出队

5. 取队头元素