0217 数据结构（线性表、二叉树代码）_线性表怎么画二叉树

目录

一、线性表知识点

二、代码练习

1.二叉树代码浅试

2.链表浅试

---

一、线性表知识点

0215

1.二维数组只存在行指针列指针概念，没有二级指针

2.二叉树是有序树，左右有序   
 n0 = n2 + 1   （根节点+度2节点新生的一个，度1节点不产生新的叶）
 

3.数据结构概念：

数据类型：原子类型、结构类型、抽象数据类型
数据结构：逻辑结构、物理结构、数据的运算
物理结构：顺序存储、链式存储、索引存储、散列存储
逻辑结构：线性、集合、树型、图型
算法五个特性：有穷性、确定性、可行性、输入、输出
好的算法：正确性、可读性、健壮性、效率与低存储量需求
度量：时间复杂度、空间复杂度

4.静态链表:存储结构数组   访问结构链表
   结构体内使用的结构体指针只能指向自己

0216

1.NULL空间不允许操作

2. 1) 数组a[m] a 等价于 &a[0] 2)数组a[m][m] a 等价于 a[0] *a

3.指针p++ 按元素加 指针差是元素数

4.使用指针接收数据要提前分配空间

5.malloc()  calloc() free() realloc() 重新分配新空间以修改空间大小

6.具有n个节点的完全二叉树的深度必为 Llog2n| + 1

 7.头结点、首元结点 (第一个元素)、头指针（是否实际物理内存）
    结构体内只能有指向自身的结构体指针不能是结构体：4+x = x （数据域 + 结构体 = 结构体）

8.双向链表：pNode->next  加判断if (pNode->next != NULL)   pNode->prev有时也需要

0217

1.init_queue() 时队列为空：front = rear = 0；

   所以队满时rear永远追不上front  (rear+1)%MAX_SIZE == front；

二、代码练习

1.二叉树代码浅试

#include <stdio.h>
#include <stdlib.h>
 
#define NULLKY '?'
#define MAX_NODE 50
 
typedef struct BTNode
{
	char data;
	struct BTNode *Lchild,*Rchild;
}BTNode;
 
BTNode *Create_BTree(void)
{
	BTNode *T, *p, *s[MAX_NODE];
    char ch;
	int i,j;
 
	while(1)
	{
		scanf("%d",&i);
		if (0 == i)
		{
			break;
		}
		else
		{
			ch = getchar();
			p = (BTNode*)malloc(sizeof(BTNode));
			p->data = ch;
			p->Lchild = p->Rchild = NULL;
			s[i] = p;
			if (1 ==i)
			{
				T = p;
			}
			else
			{
                j = i / 2;
				if (i % 2 == 0)
				{
					s[j]->Lchild = p;
				}
				else
				{
					s[j]->Rchild = p;
				}
			 
			}
		}
	}
    return T;
}
 
BTNode *Preorder_Create_BTree(BTNode **T)
{
	char ch;
	ch = getchar(); 
	getchar();
	if (ch == NULLKY)
	{
        *T = NULL;
		return *T;
	}
	else
	{
        (*T) = (BTNode *)malloc(sizeof(BTNode));
		(*T)->data = ch;
		Preorder_Create_BTree(&(*T)->Lchild);
		Preorder_Create_BTree(&(*T)->Rchild);
		return *T;
	}
}
 
void visit(char data)
{
	printf("%c\n",data);
}
 
void PreorderTraverse(BTNode *T)
{
	BTNode *stack[MAX_NODE], *p = T, *q;
	int top = 0;
	stack[top] = NULL;
 
	if (T == NULL)
	{
		printf("Binary Tree is Empty!\n");
	}
	else
	{
        do
		{
            visit(p->data);
 
			q = p->Rchild;
			if (q != NULL)
			{
				stack[++top] = q;
			}
 
			p = p->Lchild;
			if (p == NULL)
			{
                p = stack[top];
 
				//stack[0]会被访问到，赋初始NULL
				top--;
			}
		}
		while(p != NULL);
	}
}
 
void InorderTraverse(BTNode *T)
{
	BTNode *stack[MAX_NODE], *p = T;
	int top = 0, bool = 1;
 
	if (T == NULL)
	{
		printf("Binart Tree is Empty!\n");
	}
	else
	{
        do
		{
			while (p != NULL)
			{
				stack[++top] = p;
				p = p->Lchild;
			}
			if (top == 0)
			{
				bool = 0;
			}
			else 
			{
				p = stack[top];
				top--;
				visit(p->data);
				p = p->Rchild;
			}
		} while (bool != 0);
	}
}
 
void PostorderTraverse(BTNode *T)
{
	BTNode *s1[MAX_NODE], *p = T;
	int s2[MAX_NODE], top = 0, bool = 1;
 
	if (T == NULL)
	{
		printf("Binary Tree is Empty !\n");
	}
	else
	{
        do
		{
			while(p != NULL)
			{
				s1[++top] = p;
				s2[top] = 0;
				p = p->Lchild;
			}
			if (top == 0)
			{
				bool = 0;
			}
			else if (s2[top] == 0)
			{
				p = s1[top]->Rchild;
				s2[top] = 1;
			}
			else
			{
                p = s1[top];
				top--;
				visit(p->data);
				p = NULL;// 使循环将继续进行而不死循环
			}
		} while (bool != 0);
		
	}
}
 
void LevelTraverse(BTNode *T)
{
	BTNode *Queue[MAX_NODE], *p = T;
	int front = 0, rear = 0;
 
	if (p != NULL)
	{
		Queue[++rear] = p;
		while (front < rear)
		{
			p = Queue[++front];
			visit(p->data);
			if (p->Lchild != NULL)
			{
				Queue[++rear] = p->Lchild;
			}
			if (p->Rchild != NULL)
			{
				Queue[++rear] = p->Rchild;
			}
		}
	}
}
 
//段错误，无法运行
int search_leaves(BTNode *T)
{
	BTNode *stack[MAX_NODE], *p = T;
	int top = 0, num = 0;
 
	if (T != NULL)
	{
		stack[++top] = p;
		while (top > 0)
		{
			p = stack[top--];
			if (p->Lchild == NULL && p->Rchild == NULL)
		    {
				num++;
			}
            if (p->Rchild != NULL)
			    stack[++top] = p->Rchild;
			if (p->Lchild != NULL)
			    stack[++top] == p->Lchild;	
		}
	}
	return num;
}
 
//层数不对
int search_depth(BTNode *T)
{
	BTNode *Queue[MAX_NODE], *p = T;
	int front = 0, rear = 0, depth = 0, level;
 
	if (T != NULL)
	{
		Queue[++rear] = p;
		level = rear;
		while (front < rear)
		{
			p = Queue[++front];
			if (p->Lchild != NULL)
			{
				Queue[++rear] = p->Lchild;
			}
			if (p->Rchild != NULL)
			{
				Queue[++rear] = p->Rchild;
			}
			if (front == level)
			{
				depth++;
				level = rear;
			}
		}
	}
}
int main()
{
    BTNode * head;
	int leafs = 0;
 
	//输入A B D ? ? E ? G ? ? C F ? ? ?
	Preorder_Create_BTree(&head);  
 
	//leafs = search_leaves(head);
    // printf("leafs:%d\n",leafs);
 
	printf("depths:%d\n",search_depth(head));
 
    //PreorderTraverse(head);
	//InorderTraverse(head);
    //PostorderTraverse(head);
	//LevelTraverse(head);
 
	return 0;
}

2.链表浅试

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
#define MALLOC_OK 1
#define MALLOC_NO 0
#define CREATE_OK 1
#define CREATE_NO 0
 
struct node
{
	int num;
	char name[20];
	char sex;
	int age;
	char add[100];
 
	struct node * next;
};
 
typedef struct node Node;
typedef Node * Link;
 
void create_link(Link * head)
{
	//第一个节点就赋值了NULL，末尾已经是NULL值了
	//空链表无表头节点，头指针  
    *head = NULL;  
}
 
int is_malloc_ok(Link new_node)
{
	if (NULL == new_node)
	{
		printf("malloc error!\n");
		return MALLOC_NO;
	}
 
	return MALLOC_OK;
} 
 
int create_node(Link * new_node)
{
	*new_node = (Link)malloc(sizeof(Node)); 
    
	if (MALLOC_OK == is_malloc_ok(*new_node))
	{
		return CREATE_OK;
	}
 
    return CREATE_NO;
 
   /*简单粗暴
	if (NULL == *new_node)
	{
		printf("malloc error!\n");
		//结束进程
		exit(-1);
	}
   */
}
 
void insert_node_head(Link * head, Link new_node)
{
    new_node->next = *head;//指针只能是->
	*head = new_node;
}
 
void insert_node_tail(Link * head, Link new_node)
{
    Link p = NULL;
 
	p = *head;
 
	if (NULL == *head)
	{
		*head = new_node;
		new_node->next = NULL;
	}
	else
	{
		while (p->next != NULL)
		{
			p = p->next;
		}
 
		p->next = new_node;
		new_node->next = NULL;
	}
 
}
 
void insert_node_mid(Link *head, Link new_node, int loc)
{
	Link p = NULL;
	Link q = NULL;
 
	p = q = *head;
 
    //while (p->num != loc && p != NULL) 
	//p等于NULL,没有num值,段错误
	// 与运算符短路
	while (p != NULL && p->num != loc)
    {
		q = p;
        p = p->next;
	}
 
    if (p == *head)
	{
        new_node->next = *head;
		*head = new_node;
	}
    else
	{
		q->next = new_node;
		new_node->next = p;
	}
 
}
 
void release_link (Link * head)
{
	Link p = NULL;
 
	p = *head;
 
    //*head隐含赋NULL值 
	while(*head != NULL)
	{
        *head = (*head)->next;
		free(p);
		p = *head;
	}
}
 
void insert_node_sort(Link *head, Link new_node)
{
	Link p = NULL;
	Link q = NULL;
 
	p = q = *head;
 
	while (p != NULL && p->num < new_node->num)
    {
		q = p;
        p = p->next;
	}
 
    if (p == *head)
	{
        new_node->next = *head;
		*head = new_node;
	}
    else
	{
		q->next = new_node;
		new_node->next = p;
	}
 
}
 
void delete_node(Link *head,int num)
{
    Link p = NULL;
	Link q = NULL;
 
	p = q = *head;
 
	if (NULL == *head)
	{
		printf("link is empty!\n");
	}
    else
	{
		while(p != NULL && p->num != num)
		{
			q = p;
			p = p->next;
		}
 
		if (NULL == p)
		{
			printf("no such node!\n");
		}
		else if(p == *head)
		{
            *head = p->next;
			free(p);
		}
		else
		{
            q->next = p->next;
			free(p);
		}
	}
}
 
void reverse_link(Link * head)
{
	Link p1 = NULL, p2 = NULL, p3 = NULL;
 
    if (NULL == *head)
	{
		printf("reverse: Link is empty!\n");
	}
 
	p1 = *head;
 
	if (NULL == (*head)->next)
	{
		return;
	}
 
	p2 = p1->next;
	p3 = p2->next;
 
	while (p3 != NULL)
	{
        p2->next = p1;
		p1 = p2;
		p2 = p3;
		
		p3 = p3->next;
	}
	
	(*head)->next = NULL;	
 
	p2->next = p1;
 
	*head = p2;
}
 
int get_len(Link head)
{
	Link p = head;
    int len = 0;
 
	while (p != NULL)
	{
        ++len;
		p = p->next;
	}
 
	return len;
}
 
void display_link(Link head)
{
	Link p = NULL;
 
	p = head;
 
	if (NULL == head)
	{
		printf("link is empty!\n");
		return;
	}
 
    while (p != NULL)
	{
		printf("%d\n",p->num);
		p = p->next;
	}
}
 
Link find_node(Link head, int num)
{
    Link p = head;
 
	while (p != NULL)
	{
        if (p->num = num)
		{
			return p;
		}
		p = p->next;
	}
 
	return NULL;
}
 
Link link_sort(Link *head)
{
	if(*head == NULL || (*head)->next == NULL)  
	{
		return *head;
	}
 
	Node * p ,*q, *pre, *post; 
 
	p = (*head)->next;
	(*head)->next = NULL;
 
	while(p != NULL)
		{	
			post = *head;
			while(post != NULL && post->num >= p->num)
			{
				pre = post;
				post = post->next;
			}
 
			if(post == *head)
			{
				*head = p;
			}
			else
			{
				pre->next = p;
			}
 
			q = p;
			p = p->next;
			q->next = post;
	}
 
	return *head;
}
 
int main()
{
    Link head = NULL;
	Link new_node = NULL;
    int i;
    int loc;
	int num;
 
	srand((unsigned)time(NULL));
 
	create_link(&head);
 
    for (i = 0; i < 10; i++)
	{
		//需要带回新的值
		//循环，给机会重复，代码体现
		if (CREATE_OK == create_node(&new_node))
		{
            new_node->num = rand() % 100;
            insert_node_sort(&head,new_node);
 
			//带表头节点不需要考虑是否为空
			//修改head指针，由空变非空，要考虑链表为空
            //insert_node_tail(&head,new_node);
		    //insert_node_head(&head, new_node);	
		}
	}
    
	/*
	printf("please input location :\n");
	scanf("%d",&loc);
    if (CREATE_OK ==create_node(&new_node))
	{
		printf("please input num:\n");
		scanf("%d",&new_node->num);
		insert_node_mid(&head,new_node,loc);
	}
	*/
    
	printf("link:\n");
    display_link(head);
 
	printf("sort:\n");
	link_sort(&head);
	display_link(head);
 
    /*
	printf("please inpuat delete num:\n");
	scanf("%d",&num);
	delete_node(&head,num);
    printf("delete:\n");
	display_link(head);
    */
 
    // reverse_link(&head);
	// printf("reverse:\n");
	// display_link(head);
 
	// printf("lengths:%d\n",get_len(head));
 
	// printf("addr:%p\n",find_node(head,head->num));
 
    release_link(&head);
	display_link(head);
 
	return 0;
}