算法设计作业-单链表

有一个不带头结点的单链表L，设计一个算法删除所有值为x的结点。
要求：（1）建立单链表，并输出链表中的所有数据；
                  （键盘输入数据：88,66,100,90,100,65,78,100,85,100）
           （2）删除所有值为100的数据，并输出链表中的所有数据。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef struct LNode
{
int data;
struct LNode *next;
}LNode;
LNode *CreatList(LNode *h,int t,int n)
{
int x;
LNode *s = (LNode *)malloc(sizeof(LNode));
if(t>n) return h;
scanf("%d",&x);
s->data = x;
s->next = h;
h = s;
h = CreatList(h,t+1,n);
return h;
}
void Output(LNode *h)
{
while(h!=NULL){
printf("%d ",h->data);
h =
h->next;
}
printf("n");
}
/* 非递归写法
LNode *Delete(LNode *now,int num)
{
int flag = 0;
LNode *pre,*nhead,*p;
pre = NULL;nhead = NULL;
while(now != NULL){
if(now->data == num){
p = now;
if(pre == NULL){
now = now->next;
}
else{
pre->next = now->next;
now = now->next;
}
free(p);
}
else{
if(flag == 0){
nhead = now;
flag = 1;
}
pre = now;
now = now->next;
}
}
return nhead;
}*/
LNode *Delete(LNode *pre,LNode *now,int num,LNode *nhead,int flag)
{
LNode *p;
if(now == NULL) return nhead;
if(now -> data == num){
p = now;
if(pre == NULL){
now = now->next;
nhead = Delete(pre,now,num,nhead,flag);
}
else{
pre->next = now->next;
now = now->next;
nhead = Delete(pre,now,num,nhead,flag);
}
free(p);
}
else{
if(flag == 0){
nhead = now;
flag = 1;
}
pre = now;
nhead = Delete(pre,now->next,num,nhead,flag);
}
return nhead;
}
int main()
{
int n,x,num;
printf("输入数据的数量为：");
scanf("%d",&n);
printf("请输入n个数据:");
scanf("%d",&x);
LNode *h = (LNode *)malloc(sizeof(LNode));
h->data = x;
h->next = NULL;
LNode *head = CreatList(h,2,n);
printf("当前链表为：");
Output(head);
printf("请输入要删除的数据:");
scanf("%d",&num);
//	LNode *nhead = Delete(head,num);
LNode *nhead = Delete(NULL,head,num,NULL,0);
Output(nhead);
}
// 88 66 100 90 100 65 78 100 85 100

对于含n（n>0）个结点的二叉树，所有结点值为int类型，设计一个算法由其先序序列a和中序序列b创建对应的二叉链存储结构。
要求：（1）建立二叉链表存储的二叉树，先序序列是：1,2,4,8,9,5,10,11,3,6,12,7；

                                                          中序序列是：8,4,9,2,10,5,11,1,12,6,3,7.
          （2）分别输出输出二叉树的先序、中序、后序序列。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef struct BTNode
{
int data;
struct BTNode *lchild,*rchild;
}BTNode;
BTNode *CreatBTree(int a[],int b[],int n)
{
int k;
if(n<=0) return NULL;
int root = a[0];
BTNode *bt = (BTNode *)malloc(sizeof(BTNode));
bt->data = root;
for(k=0;k<n;++k){
if(b[k]==root)
break;
}
bt->lchild = CreatBTree(a+1,b,k);
bt->rchild = CreatBTree(a+k+1,b+k+1,n-k-1);
return bt;
}
void Output_DLR(BTNode *bt)
{
if(bt==NULL) return ;
printf("%d ",bt->data);
Output_DLR(bt->lchild);
Output_DLR(bt->rchild);
}
void Output_LDR(BTNode *bt)
{
if(bt==NULL) return ;
Output_LDR(bt->lchild);
printf("%d ",bt->data);
Output_LDR(bt->rchild);
}
void Output_LRD(BTNode *bt)
{
if(bt==NULL) return ;
Output_LRD(bt->lchild);
Output_LRD(bt->rchild);
printf("%d ",bt->data);
}
int main()
{
int n = 12;
int a[] = {1,2,4,8,9,5,10,11,3,6,12,7};
int b[] = {8,4,9,2,10,5,11,1,12,6,3,7};
BTNode *bt = CreatBTree(a,b,n);
printf("先序：");Output_DLR(bt);printf("n");
printf("中序：");Output_LDR(bt);printf("n");
printf("后序：");Output_LRD(bt);printf("n");
}

总结：递归中，返回上一层时一定要用东西接住，比如

nhead = Delete(pre,now,num,nhead,flag);

否则有时候可能正确，但是很容易出错误。

最后

以上就是结实芹菜为你收集整理的算法设计作业-单链表的全部内容，希望文章能够帮你解决算法设计作业-单链表所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。