c语言——链表和二叉树
前
言
本期提供了c语言链表和二叉树的基本程序，仅供参考。电脑上观感更佳。
教材中第9章，有非常全的伪代码与c语言间的转换，在此不再赘述。需要教材可以私聊我。
链表
链表程序举例
输入：无
输出：两个学生的名字和生日
子函数：displayList（递归或非递归）
#include <stdio.h>
#include <stdlib.h>
void displayList(struct MDate_naiss *ptr);
struct MDate_naiss
{
int day, month, year;
char name[40];
struct MDate_naiss *next;
};
int main()
{ //主函数
struct MDate_naiss s1, s2;
struct MDate_naiss *ptr;
s1.year = 2001;
s1.month = 8;
s1.day = 8;
s1.name[0] = 'T';
s1.name[1] = 'o';
s1.name[2] = 'm';
s1.next = &s2;
s2.year = 2001;
s2.month = 2;
s2.day = 2;
s2.name[0] = 'J';
s2.name[1] = 'e';
s2.name[2] = 'r';
s2.name[3] = 'r';
s2.name[4] = 'y';
s2.next = NULL;
ptr = &s1;
displayList(ptr);
return 0;
}
void displayList(struct MDate_naiss *ptr)
{ //非递归
int i;
while (ptr != NULL)
{
i = 0;
while ((*ptr).name[i] != '\0')
{
printf("%c", (*ptr).name[i]);
i++;
}
printf("\n%d-%d-%d\n", (*ptr).day, (*ptr).month, (*ptr).year);
ptr = (*ptr).next;
}
}
void displayList(struct MDate_naiss *ptr)
{ //递归
if (ptr != NULL)
{
int i = 0;
while ((*ptr).name[i] != '\0')
{
printf("%c", (*ptr).name[i]);
i++;
}
printf("\n%d-%d-%d\n", (*ptr).day, (*ptr).month, (*ptr).year);
displayList((*ptr).next);
}
}
二叉树
受到篇幅限制，二叉树的性质和更多用法在下期发布。
二叉树程序举例
输入：任意多的数
输出：建立二叉树，从小到大输出这些数，并输出树的深度
子函数：创造一个节点，插入一个节点，计算树的深度，用递归中序遍历
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
struct Node
{
int data;
struct Node *pleft;
struct Node *pright;
} Node;
struct Node *addnode(int value, struct Node *pnode);
struct Node *createnode(int value);
void listnodes(struct Node *pnode);
int Treeheight(struct Node *pnode);
int main()
{ //主函数
int newvalue = 0;
struct Node *proot = NULL;
char answer = 'n';
do
{
printf("Enter the node value:\n");
scanf("%d", &newvalue);
if (proot == NULL)
proot = createnode(newvalue);
else
addnode(newvalue, proot);
printf("还要输入吗(y or n)?\n");
scanf(" %c", &answer);
} while (answer == 'y');
listnodes(proot);
printf("深度是%d!\n", Treeheight(proot));
return 0;
}
struct Node *addnode(int value, struct Node *pnode)
{ //插入节点
if (pnode == NULL)
return createnode(value);
if (value == pnode->data)
return pnode;
if (value < pnode->data)
{
if (pnode->pleft == NULL)
{
pnode->pleft = createnode(value);
return pnode->pleft;
}
else
return addnode(value, pnode->pleft);
}
else
{
if (pnode->pright == NULL)
{
pnode->pright = createnode(value);
return pnode->pright;
}
else
return addnode(value, pnode->pright);
}
}
struct Node *createnode(int value)
{ //创造一个节点
struct Node *pnode = (struct Node*)malloc(sizeof(struct Node));
pnode->data = value;
pnode->pleft = pnode->pright = NULL;
return pnode;
}
void listnodes(struct Node *pnode)
{ //用递归中序遍历
if (pnode != NULL)
{
listnodes(pnode->pleft);
printf("%d\n", pnode->data);
listnodes(pnode->pright);
}
}
int Treeheight(struct Node *pnode)
{ //用递归计算树的深度
int LD, RD;
if (pnode == NULL)
return 0;
else
{
LD = Treeheight(pnode->pleft);
RD = Treeheight(pnode->pright);
return (LD >= RD? LD:RD)+1;
}
}