#1022 数据结构 exercise6-递归

数据结构 exercise6-递归

1.删除以L为首节点指针的单链表中值为x的所有节点。2.输出以L为首节点指针的单链表中最小节点值。3.用递归方法实现字符串的置换操作Replace( S, T, R)。

1.删除以L为首节点指针的单链表中值为x的所有节点。

#include<stdio.h> #include<iostream> #include<string.h> typedef struct SqNode { int data; struct SqNode* Next; }SqNode,*SqList; SqList CreateList(SqList L) { L = (SqList)malloc(sizeof(SqNode)); SqList s; SqList r; int Value=0; printf("请输入您需要创建的链表\n"); scanf("%d", &Value); getchar(); L->data = Value; L->Next = NULL; r = L; scanf("%d", &Value); getchar(); while (Value!=999) { s = (SqList)malloc(sizeof(SqNode)); s->data = Value; s->Next = r->Next; r->Next = s; r = s; scanf("%d", &Value); getchar(); } return L; } //创建链表 SqList DeleteElement(SqList *L, int Value) { SqList s; if (*L == NULL) { return 0; } if ((*L)->data == Value ) { s = *L; *L = (*L)->Next; free(s); DeleteElement(L,Value); } else { DeleteElement(&((*L)->Next), Value); } } void PrintList(SqList L) { SqList s; s = L; while (s != NULL) { printf("%d\t", s->data); s = s->Next; } printf("\n"); } void main() { SqList L=NULL; L=CreateList(L); PrintList(L); DeleteElement(&L, 3); PrintList(L); }

2.输出以L为首节点指针的单链表中最小节点值。

#include <stdio.h> #include <stdlib.h> #define ERROR NULL typedef int ElementType; typedef struct LNode *PtrToLNode; struct LNode { ElementType Data; PtrToLNode Next; }; typedef PtrToLNode Position; typedef PtrToLNode List; List MakeEmpty(); bool Insert( List L, ElementType X, Position P ); void deleteMinNode(List L); int main() { List L; ElementType X; Position P; int N; L = MakeEmpty(); scanf("%d", &N); while ( N-- ) { scanf("%d", &X); Insert(L, X, L->Next); } printf("before delete:\n"); for ( P=L->Next; P; P = P->Next ) printf("%d ", P->Data); printf("after delete:\n"); deleteMinNode(L); for ( P=L->Next; P; P = P->Next ) printf("%d ", P->Data); return 0; } List MakeEmpty() { List L =(List)malloc(sizeof(struct LNode)); L->Next = NULL; return L; } /* 带头结点的插入 注意这里是倒序插入，测试的时候输入数据的时候要小心一下*/ bool Insert( List L, ElementType X, Position P ) { /* 这里默认L有头结点 */ Position temp, pre; /* 查找P的前一个结点,这里最开始没想到for循环不需要写循环体内程序就可以了 */ for ( pre=L; pre&&pre->Next!=P; pre=pre->Next ) ; if ( pre==NULL ) { /* P所指的结点不在L中 */ printf("Wrong Position for Insertion\n"); return false; } else { /* 找到了P的前一个结点pre */ /* 在P前插入新结点 */ temp = (Position)malloc(sizeof(struct LNode)); /* 申请、填装结点 */ temp->Data = X; temp->Next = P; pre->Next = temp; //刚开始忘记写return true； return true; } } void deleteMinNode(List L) { if(L == NULL) return; List cur = L->Next,curPre = L,min = L->Next, minPre; while(cur!= NULL){ if(cur->Data < min->Data){ minPre = curPre; min = cur; } curPre = cur; cur = cur->Next; } minPre->Next = min->Next; free(min); }

3.用递归方法实现字符串的置换操作Replace( S, T, R)。