1.单链表
1.1算法描述
1.2代码
#include <stdio.h>
#include<malloc.h>
typedef char elemtype;
typedef struct lnode
{
elemtype data;
struct lnode *next;
}linklist;
void initlist (linklist *&L)//创建一个表
{
L=(linklist *)malloc(sizeof(linklist));
L->next=NULL;
}
int listlnsert(linklist *&L,int i,elemtype e)//在第i个位置插入元素
{
int j=0;
linklist *p=L,*s;
while(j<i-1&&p!=NULL)
{
j++;
p=p->next;
}
if(p==NULL)
return 0;
else
{
s=(linklist*)malloc(sizeof(linklist));
s->data=e;
s->next=p->next;
p->next=s;
return 1;
}
}
int listdelete(linklist *&L,int i,elemtype &e)//删除元素
{
int j=0;
linklist *p=L,*q;
while(j<i-1&&p!=NULL)
{
j++;
p=p->next;
}
if(p==NULL)
return 0;
else
{
q=p->next;
e=q->data;
p->next=q->next;
free(q);
return 1;
}
}
void destroylist(linklist *L)//释放表
{
free(L);
}
int getelem(linklist *L,int i,elemtype &e)//表中第i个元素是什么
{
int j=0;
linklist *p=L;
while(j<i&&p!=NULL)
{
j++;
p=p->next;
}
if(p==NULL)
return 0;
else
{
e=(p->data) ;
return 1;
}
}
void displist(linklist *L)//输出表
{
linklist*p=L->next;
while(p!=NULL)
{
printf("%c",p->data);
p=p->next;
}
printf("\n");
}
int main()
{
linklist *h;
elemtype e;
printf("(1)初始化单链表h\n");
initlist (h);
printf("(2)依次采用尾插法插入元素a,b,c,d,e\n");
listlnsert(h,1,'a');
listlnsert(h,2,'b');
listlnsert(h,3,'c');
listlnsert(h,4,'d');
listlnsert(h,5,'e');
printf("(3)输出单链表h:");
displist(h);
getelem(h,3,e);
printf("(4)单链表h的第三个元素=%c\n",e);
printf("(5)在第四个元素位置上插入f元素\n");
listlnsert(h,4,'f');
printf("(6)输出单链表h:");
displist(h);
printf("(7)删除单链表h上的第三个元素:\n");
listdelete(h,3,e);
printf("(8)输出单链表h:");
displist(h);
printf("(9)释放单链表h:\n");
destroylist(h);
return 0;
}
1.3运行结果
(1)初始化单链表h
(2)依次采用尾插法插入元素a,b,c,d,e
(3)输出单链表h:abcde
(4)单链表h的第三个元素=c
(5)在第四个元素位置上插入f元素
(6)输出单链表h:abcfde
(7)删除单链表h上的第三个元素:
(8)输出单链表h:abfde
(9)释放单链表h:
请按任意键继续. . .
2.树的递归遍历
2.1算法描述
2.2代码
#include<stdio.h>
#include<malloc.h>
typedef char elemtype;
typedef struct node{
elemtype data;
struct node *lchild,*rchild;
}btnode,*bitree;
bitree createbitree()
{
char ch;
scanf("%c",&ch);
bitree t=nullptr;
if(ch=='#') t=NULL;
else
{
t=(btnode *)malloc(sizeof(btnode));
t->data =ch;
t->lchild =createbitree();
t->rchild =createbitree();
}
return t;
}
void preorder(btnode *b)
{
if(b!=NULL)
{
printf("%c",b->data );
preorder(b->lchild );
preorder(b->rchild );
}
}
void inorder(btnode *b)
{
if(b!=NULL)
{
inorder(b->lchild );
printf("%c",b->data );
inorder(b->rchild );
}
}
void postorder(btnode *b)
{
if(b!=NULL)
{
postorder(b->lchild );
postorder(b->rchild );
printf("%c",b->data );
}
}
int main()
{
btnode *b;
b=createbitree();
printf("先序遍历访问结果：\n");
preorder(b);printf("\n");
printf("中序遍历访问结果：\n");
inorder(b);printf("\n");
printf("后序遍历访问结果：\n");
postorder(b);printf("\n");
return 0;
}
2.3运行结果
-+a##*b##-c##d##/e##f##
先序遍历访问结果：
-+a*b-cd/ef
中序遍历访问结果：
a+b*c-d-e/f
后序遍历访问结果：
abcd-*+ef/-
请按任意键继续. . .
