插图1.jpg
数据结构中常考的一些内容总结，使用的语言是C/C++语言
一、线性表
线性表是相同数据类型的n(n>=0)个数据元素的有限序列。
线性表的顺序存储就是顺序表,顺序表的结构体
typedef struct{
int data[MaxSize];
int length;
}SqList;
但是感觉一般都是考链表，那么我们直接进入链表的重点吧
链表
//链表的节点类型
typedef struct node{
int val;
struct node* next;
}node,*Linklist;
单链表反转基本成为必考的题目
这里引用一下这位同学写的答案，我个人认为写的比较好
http://blog.csdn.net/FX677588/article/details/72357389
node* reverseList(node* H)
{
if (H == NULL || H->next == NULL) //链表为空或者仅1个数直接返回
return H;
node* p = H, *newH = NULL;
while (p != NULL) //一直迭代到链尾
{
node* tmp = p->next; //暂存p下一个地址，防止变化指针指向后找不到后续的数
p->next = newH; //p->next指向前一个空间
newH = p; //新链表的头移动到p，扩长一步链表
p = tmp; //p指向原始链表p指向的下一个空间
}
return newH;
}
二、二叉树
typedef struct BitNode{
char data;
struct BitNode *lchild,rchild;
}BitNode,*BiTree;
二叉树常考的内容应该就是先序遍历，中序遍历，后续遍历
先序遍历
口诀：根左右
//先序遍历
void PreOrderTraverse(BiTree t)
{
//注意跳出条件
if(t != NULL)
{
//注意访问语句顺序
printf("%c ", t->data);
PreOrderTraverse(t->lchild);
PreOrderTraverse(t->rchild);
}
}
中序遍历
口诀：左根右
//中序遍历
void InOrderTraverse(BiTree t)
{
if(t != NULL)
{
InOrderTraverse(t->lchild);
printf("%c ", t->data);
InOrderTraverse(t->rchild);
}
}
后续遍历
口诀：左右根
//后续遍历
void PostOrderTraverse(BiTree t)
{
if(t != NULL)
{
PostOrderTraverse(t->lchild);
PostOrderTraverse(t->rchild);
printf("%c ", t->data);
}
}
