数据结构(期末总结)_2、请根据以下算法画出对应图形:(5分)p=(lnode *)malloc(sizeof(lnode

按照我学习的过程更新，所以我会一直更这个文章

第一章：

因为第一章没有什么代码可看的，所以我就拿笔记本写了点笔记出来。

都是一些基本的属于概念，搞清楚其中的关系就行了。

 

 

第二章 线性表

2.1 等我学会再补

2.2 链表：

 链表节点的定义：

//定义一个结构体
typedef struct LNode
{
	int data;
	struct LNode* next;
}LNode,* p;

首先我们必须先初始化链表。我看很多人都是把插入数据的过程，跟创建空链表的过程分开来搞。但是我感觉不如像我下面那样一步到位比较方便得了：

by the way我的链表是带头结点的，然后使用的方法是尾插法（头插入法我理解的不够好怕搞错，尾插入比较好理解）：

LNode *InitList()
{
	int i,temp;
	//输入有多少个节点
	int n;
	printf("请问你要输入多长的链表");
	scanf_s("%d", &n);
	LNode* head,*tail,*p;
	//头节点先指向尾节点
	head =tail= (LNode*)malloc(sizeof(LNode));
	tail->next = NULL;
	for (i = 0; i < n; i++)
	{
		printf("输入第%d个位置的data", i + 1);
		scanf_s("%d", &temp);
		p = (LNode*)malloc(sizeof(LNode));
		p->data=temp;
		p->next = NULL;
		tail->next = p;
		tail = p;
	}
	return head;
}

下面是这个链表所要实现的各种功能：

1.返回第i个元素的值 int GetElem(LNode* L, int i)

这个比较简单也比较好理解，找到第i个位置的，只需要把链表从头到尾走i次，然后输出所对应的data就是那个值了

//返回第i个元素的值
int GetElem(LNode* L, int i)
{
	int flag = i;
	while (flag >= 1)
	{
		L = L->next;
		flag--;
	}
	printf("链表第%d位置的数值为%d", i, L->data);
	return L->data;
}

2.插入一个值 void Insert(LNode* L, int i, int e)

这个函数的目的就是在第i-1个位置的后面接上一个值：

        首先我们开辟一个节点，用于存储新节点的数据

        然后走i-1次找到那个要插入的位置，把新节点接在后面，然后再把新结点的指针指向原来的第i个位置，就好了：

//插入一个值
void Insert(LNode* L, int i, int e)
{
	int flag=i;
	LNode* temp;
	LNode *p;
	p = (LNode*)malloc(sizeof(LNode));
	p->data = e;
	p->next = NULL;
	while (flag > 1)
	{
		L = L->next;
		flag--;
	}
	p->next = L->next;
	L->next = p;
}

3.删除第i个节点：void ListDelete(LNode* L, int i)

这里我用的方法是我开一个节点指针，指向的的是原来的那个L的下一个节点，就是我不管L指到哪里，我都有一个tempnode指向它的下一个。

然后开始找第i个位置：我们先让L走到第i-1个位置，然后这时候就像上面所说的tempnode走到了第i个位置了嘛：

然后这个时候我们把第i-1个位置的next指针（L的）指向第i个位置（tempnode的）的next指针，就实现了i-1到i+1，i就被绕过去了，然后free掉i，结束。

void ListDelete(LNode* L, int i)
{
 
	LNode* tempnode;
	tempnode = L->next;
	int flag = i;
	while (flag > 1)
	{
		L = L->next;
		tempnode = tempnode->next;
		flag--;
	}
	L->next = tempnode->next;
	free(tempnode);
}

全局代码展示：

#include<stdio.h>
#include<stdlib.h>
//定义一个结构体
typedef struct LNode
{
	int data;
	struct LNode* next;
}LNode,* p;
 
//创造一个链表——尾插入法
LNode *InitList()
{
	int i,temp;
	//输入有多少个节点
	int n;
	printf("请问你要输入多长的链表");
	scanf_s("%d", &n);
	LNode* head,*tail,*p;
	//头节点先指向尾节点
	head =tail= (LNode*)malloc(sizeof(LNode));
	tail->next = NULL;
	for (i = 0; i < n; i++)
	{
		printf("输入第%d个位置的data", i + 1);
		scanf_s("%d", &temp);
		p = (LNode*)malloc(sizeof(LNode));
		p->data=temp;
		p->next = NULL;
		tail->next = p;
		tail = p;
	}
	return head;
}
//返回第i个元素的值
int GetElem(LNode* L, int i)
{
	int flag = i;
	while (flag >= 1)
	{
		L = L->next;
		flag--;
	}
	printf("链表第%d位置的数值为%d", i, L->data);
	return L->data;
}
 
 
//插入一个值
void Insert(LNode* L, int i, int e)
{
	int flag=i;
	LNode* temp;
	LNode *p;
	p = (LNode*)malloc(sizeof(LNode));
	p->data = e;
	p->next = NULL;
	while (flag > 1)
	{
		L = L->next;
		flag--;
	}
	p->next = L->next;
	L->next = p;
}
 
void ListDelete(LNode* L, int i)
{
 
	LNode* tempnode;
	tempnode = L->next;
	int flag = i;
	while (flag > 1)
	{
		L = L->next;
		tempnode = tempnode->next;
		flag--;
	}
	L->next = tempnode->next;
	free(tempnode);
}
//顺序输出链表
void print(LNode *L)
{
	LNode* tempnode;
	tempnode = L->next;
	while (tempnode)
	{
		printf("%d   ", tempnode->data);
		tempnode = tempnode->next;
	}
}
int main()
{
	LNode* list = InitList();
	print(list);
	Insert(list, 2, 6);
	printf("\n");
	print(list);
	printf("\n");
	int a = GetElem(list, 3);
	printf("\n");
	printf("删除第四个节点:\n");
	ListDelete(list, 4);
	print(list);
	return 0;
}

第三章 栈和队列

3.1栈

先定义一个结构体来表示栈

#include<stdio.h>
#define Maxsize 10000
 
typedef struct stack
{
	int data[Maxsize];
	int top;
}stack;

然后，我的这个栈需要完成下面三个功能：

push入栈

pop输出并且出栈

top输出但是不出栈

push入栈

//将栈顶输出，并且栈顶出栈 
int pop(stack *a)
{
	if(a->top==0)
	{
		printf("underflow");
		return -1;
	}
	printf("输出栈%d\n",a->data[a->top]);
	a->top--;
	return a->top;
}

pop输出并且出栈

int pop(stack *a)
{
	if(a->top==0)
	{
		printf("underflow");
		return -1;
	}
	printf("输出栈%d\n",a->data[a->top]);
	a->top--;
	return a->top;
}

top输出但是不出栈

//栈顶输出，栈顶不出栈 
int top(stack *a)
{
	if(a->top==0)
	{
		printf("underflow");
		return -1;
	}
	printf("输出栈但不出栈 % d\n",a->data[a->top]);
	return top;
}

全局代码演示：

#include<stdio.h>
#define Maxsize 10000
 
typedef struct stack
{
	int data[Maxsize];
	int top;
}stack;
 
int push(stack *a, int x)
{
	if(a->top==Maxsize)
	{
		printf("overflow");
		return -1;
	}
	a->top++; 
	a->data[a->top]=x;
	printf("入栈%d\n", x);
	return a->top;
}
 
//将栈顶输出，并且栈顶出栈 
int pop(stack *a)
{
	if(a->top==0)
	{
		printf("underflow");
		return -1;
	}
	printf("输出栈%d\n",a->data[a->top]);
	a->top--;
	return a->top;
}
 
//栈顶输出，栈顶不出栈 
int top(stack *a)
{
	if(a->top==0)
	{
		printf("underflow");
		return -1;
	}
	printf("输出栈但不出栈 % d\n",a->data[a->top]);
	return top;
}
 
 
int main()
{
	stack *b;
	stack a;
	b = &a;
	a.top=0;
	push(b,1);
	push(b,2);
	push(b,3);
	pop(b);
	top(b);
	pop(b);
}

3.2队列

#include<stdio.h>
#define N 100000
 
typedef struct queue
{
	int data[N];
	int front;
	int rear;
} queue;
 
//初始化列表 
void init(queue *myqueue)
{
	myqueue->front=0;
	myqueue->rear=0; 
}
//1为空
//o为不空 
int isempty(queue *myqueue)
{
	if(myqueue->front==myqueue->rear)
	{
		return 1;
	}
	else
	{
		return 0;
	}
}
 
void EnQueue(queue *myqueue)
{
	int num;
	if(myqueue->rear==N)
	{
		printf("error");
	}
	else
	{
		
		myqueue->data[myqueue->rear]=num;
		myqueue->rear+=1;
	}
}
void DeQueue (queue *myqueue)
{
	if(myqueue->front==myqueue->rear)
	{
		printf("error");
	}
	else
	{
		
		printf("%d\n",myqueue->data[myqueue->front]);
		myqueue->front+=1;
	}
	
}