黑马程序员技术交流社区

标题: 学海无涯苦作舟 [打印本页]

作者: 你已成为群主 时间: 2020-1-10 13:51
标题: 学海无涯苦作舟
一、链表的实现（核心代码）
1．定义
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。
2．
（1）节点头插法的说明
见《万门终身VIP》1-1页
（2）头插法代码实现
#include<stdio.h>
struct Node
{
int data;
struct Node *next;
};

int main()
{
int n;
struct Node *L,*p;
L = (struct Node *)malloc(sizeof(struct Node));
L->next = NULL;
printf("请输入一个节点数据");
scanf("%d",&n);
while(n!=9999){
      p = (struct Node *)malloc(sizeof(struct Node));
      p->data=n;
      p->next=L->next;
      L->next=p;
      scanf("%d",&n);
}
return 0;
}
3．尾插法
#include<stdio.h>
struct Node
{
int data;
struct Node *next;
};

int main()
{
int n;
struct Node *L,*r,*p;
L = (struct Node *)malloc(sizeof(struct Node));
r = L;
printf("请输入一个整数");
scanf("%d",&n);
while(n!=9999)
{
      p = (struct Node *)malloc(sizeof(struct Node));
      p->data = n;
      r->next=p;
      r=p;
      scanf("%d",&n);
}
r->next = NULL;
return 0;
}

二、栈和队列的实现（数组与链表的）

1．栈和队列的定义
（1）队列是一种先进先出的数据结构
（2）栈是一种先进后出的数据结构
2．用数据和链表实现栈
（1）用数组实现栈
#include<stdio.h>
#include<stdlib.h>
#define MaxSize 50
typedef struct QueStack
{
int top;
int data[MaxSize];
};
int main()
{
struct QueStack *s;
InitQueStack(&s);
int isEmpty = IsEmptyQueStack(&s);
printf("%d \n",isEmpty);
push(&s,6);
push(&s,19);
pop(&s,9);
getTop(&s,10);
return 0;
}
// 出栈
int pop(struct QueStack *s,int n){
if(s->top == -1){
      return 0;
}else{
      n = s->data[s->top--];
      printf("出栈成功 %d,当前指针移动到：%d \n",n,s->top);
      return 1;
}
}
// 获得栈顶元素
int getTop(struct QueStack *s,int n){
if(s->top == -1){
      return 0;
}else{
      n = s->data[s->top];
      printf("该栈顶的元素为：%d \n",n);
}
}
// 入栈
int push (struct QueStack *s,int n){
if(s->top == MaxSize-1){
      return 0;
}else{
      s->data[++(s->top)] = n;
      printf("入栈成功 %d \n",s->data[s->top]);
      return 1;
}
}
// 初始化栈
void InitQueStack(struct QueStack *s)
{
s->top = -1;
printf("初始化成功%d \n",s->top);
}
// 判读栈是否为空
int IsEmptyQueStack(struct QueStack* s)
{
if(s->top == -1)
      return 1;
else
      return 0;
}

（2）用链表实现栈
我们知道栈的特点是先进后出，而链表中的头插法正好满足我们的需求，因为头插法后面插入的节点位于链表的开头，所以我们可以使用头插法来插入节点，在弹出节点的时候弹出链表的第一个节点即可，而第一个节点是很容易找出来的，所以可以很轻松地实现栈的压入和弹出操作；
#include<stdio.h>
#include<stdlib.h>
#define MaxSize 50
struct Node
{
int data;
struct Node *next;
};

int main()
{
// 用链标实现栈，我们都知道栈是先进后出的线性表，然后
// 链标的头插法真好是先进后出的，所有可以用链表的头插法来模仿栈
struct Node *L;
L = (struct Node *)malloc(sizeof(struct Node));
L->next = NULL;
for(int i = 0; i < 6; i ++)
{
      push(L,i);
}
int n;

printf("%d \n",Getlength(L));
pop(L,n);
Getlength(L);
return 0;
}

int Getlength(struct Node *head)
{
int i=0;
struct Node *p;
if(head->next==NULL)
      return 0;
else
{
      p=head->next;
      printf("第%d个链表的数据是%d \n",i,p->data);
      while(p && p->next != NULL)
      {
         i++;
         p=p->next;
         printf("第%d个链表的数据是%d \n",i,p->data);
      }
      return i;
}
}

// 出栈
int pop(struct Node *L,int n)
{
printf("将%d弹出栈 \n",n);
struct Node *p;
if(L->next == NULL)
{
      return 0;
}
else
{
      p = L->next;
      n = p->data;
      L->next = p->next;
      free(p);
      return 1;
}
}
// 人栈
void push(struct Node *L,int n)
{
printf("将%d压入栈 \n",n);
struct Node *p = (struct Node *)malloc(sizeof(struct Node));
p->data = n;
p->next = L->next;
L->next = p;
}

3．用数组和链表实现队列
（1）用数组实现队列
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#define MaxSize 50
typedef struct Queue
{
int data[MaxSize];
int front; // 队首元素在数组中的下标
int rear; // 队尾元素在数组中的下标
};
int main()
{
int n;
struct Queue *q;
q = (struct Queue *)malloc(sizeof(struct Queue));
InitQueue(q);
enQueue(q,1);
enQueue(q,2);
enQueue(q,3);
enQueue(q,6);
enQueue(q,10);
traverseQuene(q);
outQueue(q,2);
traverseQuene(q);
int A = is_fullQueue(q);
printf("%d",A);
destroyQueue(q);
return 0;

}
// 初始化队列
void InitQueue(struct Queue *q)
{
q->front = 0;
q->rear = 0;
}
// 判断队列是否为满队列
int is_fullQueue(struct Queue *q)
{
if((q->rear + 1) % MaxSize == q->front)
      return 1;
else
      return 0;
}
// 判断是否是队空
int is_emptyQueue(struct Queue *q)
{
if(q->front == q->rear)
      return 1;
else
      return 0;
}
// 入队
int enQueue(struct Queue *q,int n)
{
if(is_fullQueue(q) == 1)
{
      return 0;
}
else
{
      printf("入队%d成功 \n",n);
      q->data[q->rear] = n;
      q->rear = (q->rear + 1)%MaxSize;
      return 1;
}
}
// 出队
int outQueue(struct Queue *q,int n)
{
if(is_emptyQueue(q) == 1)
{
      return 0;
}
else
{
      n = q->data[q->front];
      q->front = (q->front + 1)%MaxSize;
      printf("删除的元素是:%d\n",q->data[q->front-1]);
      return 1;
}
}
// 遍历队列
void traverseQuene(struct Queue *q)
{
int i=q->front;
while(i!=q->rear)
{
      i=(i+1)%MaxSize;
      printf("%d ",q->data[i-1]);
}
printf("\n");
}

// 销毁队列
void destroyQueue(struct Queue *q)
{
free(q);
q=NULL;
}

（2）用栈实现队列
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#define MaxSize 50
typedef struct Node
{
int data;
struct Node *next;
};
typedef struct Queue
{
struct Node *front,*rear;
};
int main()
{
int i = 5,j = 5;
struct Queue *q = (struct Queue *)malloc(sizeof(struct Queue));
InitQueue(q);
printf("开始入队:\n");
while(i--)
{
      printf("元素%c入队，队列为：",i);
      insertQueue(q,i);
      display(q);
}
printf("开始出队:\n");
while(j--)
{
      printf("第%d个元素出队，队列为：",5-j);
      deleteQueue(q);
      display(q);
}
printf("\n");
return 0;
}
// 初始队列
void InitQueue(struct Queue *q)
{

q->front = q->rear = NULL;
}
// 判断队列是否为空
int is_emptyQueue(struct Queue *q)
{
if(q->front == NULL)
      return 1;
else
      return 0;
}
// 入队
void insertQueue(struct Queue *q,int data)
{
struct Node *node = (struct Node *)malloc(sizeof(struct Node));
node->data = data;
node->next = NULL;// 尾插法，插入元素指向空
if(q->rear == NULL)
{
      q->front = node;
      q->rear = node;
}
else
{
      // 让node成为当前尾部节点的下一个节点
      q->rear->next = node;
      // 尾部指针指向node
      q->rear = node;
}
}
// 出队删除首元素
void deleteQueue(struct Queue *q)
{
struct Node *node = q->front;
if(is_emptyQueue(q) == 1)
{
      return;
}
// 是否只有一个元素
if(q->front == q->rear)
{
      q->front = NULL;
      q->rear = NULL;
}
else
{
      q->front = q->front->next;
      free(node);
}
}
void display(struct Queue *q)
{
struct Node *n = (struct Node *)malloc(sizeof(struct Node));
n = q->front;
if(n == NULL)
{
      return;
}
while(n!=NULL)
{
      printf("%d",n->data);
      n = n->next;
}
printf("\n");

}

4．循环队列（为什么）

为什么要使用循环队列？

防止空间的避免浪费
为充分利用向量空间，克服"假溢出"现象的方法是：将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。存储在其中的队列称为循环队列（Circular Queue）。循环队列是把顺序队列首尾相连，把存储队列元素的表从逻辑上看成一个环，成为循环队列。

什么是队列队空？

队满：
if((q->rear + 1) % MaxSize == q->front)
队空：
q->front == q->rear

本周的作业要求：

1.给出循环队列的存储结构定义。
2.完成循环队列的基本操作函数。
      1)    初始化循环队列；
      2)    建立循环队列；
      3)    实现入队和出队操作；
      4)    采用下面两种方法实现对满和队空的判断操作：

方法一：修改队满条件，浪费一个元素空间，队满时数组中只有一个空闲单元(必做)；
方法二：设置标志flag，当front==rear且flag=0时为队空，当front==rear且flag=1时为队满(必做)；

三、树的定义（出度、入度、叶节点、树的高度）

二叉树的前中后序遍历，以及非递归算法；P340-341
typedef struct TreeNode{
int data; // 数据元素
struct TreeNode *lchild,*rchild; // 左右孩子指针
int ltag,rtag;  // 左右线索标志
}TreeNode,*BitTree;
1．二叉树的前序遍历
// 前序遍历
void PreOrder(BitTree *BT)
{
if(BT != NULL)
{
      printf("%C",BT->data) // 访问更节点
      PreOrder(BT->lchild);  // 递归遍历左子树
      PreOrder(BT->rchild);  // 递归遍历右子树
}
}

// 层次序遍历
void LevelOrder(BitTree BT){
BitTree *Q[stackSize];
int rear,front;
rear = 0;
front = 0;
BitTree *p = BT; //队列初始化
Q[rear++] = p;    //p是遍历指针，跟进队
while(rear != front){
      p = Q[front];
      front = (front + 1)%queueSize;
      printf("%c",p->data); //访问
      if(p->lchild != NULL){  // 若有左子对进队
         Q[rear] = p->lchild;
         rear = (rear + 1)%queueSize;
      }
      if(p->rchild != NULL){  // 若有右子对进队
         Q[rear] = p->rchild;
         rear = (rear + 1)%queueSize;
      }
}
}

2．二叉树的中序遍历
// 中序遍历
void InOrder(BitTree *BT)
{
if(BT != NULL)
{
      InOrder(BT->lchild);  // 递归遍历左子树
      printf("%c",BT->data);// 访问跟节点
      InOrder(BT->rchild); // 递归遍历右子树
}
}

// 中序遍历非递归算法
#define stackSize 20 // 预定义栈大小，相当于树高
void InOrder(BitTree BT){
BitTree *S[stackSize];
int top = -1;
BitTree *p = BT; // p是遍历指针
do{
      while(p != NULL){ // 遍历左子树节点
         S[++top] = p;
         p = p->lchild;
      }
      if(top > -1){    // 栈不空时退栈
         p=S[top--];
         printf("%c",p->data);// 退栈,访问
         p=p->rchild; // 遍历指针进到右子树的节点
      }
}while(p != NULL || top > -1)

}

3．二叉树的后序遍历
// 后序遍历
void PostOrder(BitTree *BT)
{
if(BT != NULL)
{
      PostOrder(BT->lchild); // 递归遍历左子树
      PostOrder(BT->rchild); //递归遍历右子树
      printf("%c",BT->data);  // 访问根节点
}
}

// 后序遍历的非递归算法
void PostOrder(BitTree BT){
BitTree *S[stackSize];
int top = -1;
BitTree *p = BT,*pre = NULL; // p是遍历指针，pre是前驱指针
do{
      while(p != NULL){ // 左子树进栈
         S[++top] = p;
         p = p->lchild;  // 向最左下节点走下去
      }
      if(top > -1){
         p = S[top];  // 用p元素记忆栈顶
         if(p->rchild != NULL && p->rchild != pre){
            p = p->rchild;
         }else{
            printf("%c",p->data); // 访问
            pre = p; // 记忆刚访问过的接电脑
            p = NULL; // 转遍历右子树或访问跟节点
            top--;
         }
      }
}while(p != NULL || top != -1);
}

四、Huffmun实现，求最小权值

Huffmun树的代码：
#include<stdio.h>
#define MAX 30
#define inf 100000000
typedef char valType;
typedef int wghType;
struct HFMnode
{
valType data;
wghType weight;
int parent;
int lchild;
int rchild;
};
struct HFMcode
{
char code[MAX];
int start;
};
void createHFMtree(HFMnode *node,int n)
{
int i,m1,m2,l,r;
for(i=n+1; i<=2*n-1; i++)
{
      m1=m2=inf;
      l=r=0;
      int k;
      for(k=1; k<=i-1; k++)
         if(node[k].parent==0)
         {
            if(node[k].weight<m1)
            {
                  m2=m1;
                  r=l;
                  m1=node[k].weight;
                  l=k;
            }
            else if(node[k].weight<m2)
            {
                  m2=node[k].weight;
                  r=k;
            }
         }
      node.weight=node[l].weight+node[r].weight;
      node.lchild=l;
      node.rchild=r;
      node[l].parent=i;
      node[r].parent=i;
}
}
void createHFMcode(HFMnode *node, HFMcode *hcode,int n)
{
int i;
for(i=1; i<=n; i++)
{
      HFMcode d;
      d.start=n;
      int num=i;
      int father=node[num].parent;
      while(father!=0)
      {
         if(node[father].lchild==num)
            d.code[d.start--]='0';
         else
            d.code[d.start--]='1';
         num=father;
         father=node[num].parent;
      }
      hcode=d;
}
}
void printHFMcode(HFMnode * node,HFMcode * hcode,int n)
{
int i;
for(i=1; i<=n; i++)
{
      printf("%c: ",node.data);
      for(int k=hcode.start+1; k<=n; k++)
         putchar(hcode.code[k]);
      puts("");
}
}
void main()
{
HFMnode node[2*MAX];
HFMcode hcd[MAX];
int n;
scanf("%d\n",&n);
for(int i=1; i<=n; i++)
{
      printf("输入第%d个节点的值\n",i);
      scanf("%c",&node.data);
      printf("输入它的权重\n");
      scanf("%d\n",&node.weight);
}
for(int i=1; i<=2*n-1; i++)
      node.parent=node.lchild=node.rchild=0;
createHFMtree(node,n);
createHFMcode(node,hcd,n);
printHFMcode(node,hcd,n);
}

定义：
即求带权路径长度，WPL最小的二叉树被称为最优二叉树；

https://blog.csdn.net/qq_29519041/article/details/81428934

五、平衡二叉树(AVL)

1、判断是否平衡？
父节点的右子树层数减去左子树层数,当取值为-1,0,1时，该节点为平衡点；
如下图：

2、判断哪个是不平衡节点？
当该节点数大于等于2或者小于等于-2时，为不平衡节点；
如下图：

3、依据图示辨别是LL旋转、LR旋转、RR旋转、RL旋转；
旋转注意点：

（1）LL旋转或RR旋转注意点：
1)

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2