如下具体描述，求指教两道数据结构算法？

Question

1.设有两个带点结点的单链表A和B，链表中结点的数据域为data（没为整型），指针域为next。请用C语言函数形式写出将表A和B合并为一个单链表L的算法Union(A,B,L)(若A和B中有数据值相同的结点，只保留其中一个）
2.编写算法，实现串的基本操作Strcompare(S,T)
谢谢了

Answer 1

#include<stdio.h>#include<stdlib.h>#include<malloc.h>//-----------线性表的单链表存储结构-------------typedef int ElemType;typedef struct Node{ElemType data;struct Node *next;} *LNode, *LinkList;//----------线性表的单链表基本操作------------LinkList InitList(void); //构造一个空的线性表LNode NewLNode(ElemType X);//构造一个数据域为X的新结点LNode FindPrefious(ElemType X, LinkList L);//初始条件：线性表L已存在。 操作结果：在线性表L中寻找值为X的结点，若找到则返回该结点的前驱，否则返回NULL。void ListDelete(LNode Pre);//初始条件：线性表L中结点P已找到。 操作结果：删除该结点。//初始条件：线性表L中结点P已找到，新结点S已构造。 操作结果：在该结点之前插入新结点X。void ListInsert(LNode Pre, LNode S);LinkList CreateList(ElemType a[], ElemType len); //用来构造一个链表void Union(LinkList A, LinkList B, LinkList * L); //合并两个串int Strcompare(LinkList S, LinkList T); //比较两个串的大小void PrintLink(LinkList L); //输出链表int main(void){LNode LA, LB, L;ElemType A[5]={1,2,3,4,5}, B[8]={3,4,5,6,7,8,9,11};//把集合A和B分别存入两个单向链表LA和LB中LA = CreateList(A, 5);LB = CreateList(B, 8);PrintLink(LA); //输出链表PrintLink(LB); //输出链表Union(LA, LB, &L);//合并两个串PrintLink(L); //输出链表if (Strcompare(LA, LB) > 0) //比较两个串的大小printf("LA > LB\n");else if (Strcompare(LA, LB) < 0)printf("LA < LB\n");elseprintf("LA = LB\n");system("pause");return 0;}void Union(LinkList A, LinkList B, LinkList * L)//合并两个串{ElemType X;LNode S, P;*L = InitList(); //构造一个空的线性表P = A->next;while(P) //遍历链表A{X = P->data;S = NewLNode(X); //构造一个数据域为X的新结点ListInsert(*L, S); //把新结点S插到头结点后面。P = P->next;}P = B->next;while(P) //遍历链表B{X = P->data;if(!FindPrefious(X, A)) //看看A中是否有数据值相同的结点，只保留其中一个{S = NewLNode(X); //构造一个数据域为X的新结点ListInsert(*L, S); //把新结点S插到头结点后面。}P = P->next;}}void PrintLink(LinkList L) //输出链表{LNode P = L->next;while(P) //遍历链表L{printf("%d ", P->data);P = P->next;}printf("\n");}int Strcompare(LinkList S, LinkList T)//比较两个串的大小{LNode PS, PT;PS = S->next;PT = T->next;while(PS && PT) //遍历链表A{if (PS->data > PT->data)return 1;else if (PS->data < PT->data)return -1;PS = PS->next;PT = PT->next;}if (PS)return 1;else if (PT)return -1;elsereturn 0;}LinkList CreateList(ElemType a[], ElemType len)//用来构造一个链表{LNode L, S;ElemType i;L = InitList(); //构造一个空的线性表for(i=0; i<len; i++){S = NewLNode(a[i]); //构造一个数据域为a[i]的新结点ListInsert(L, S); //把新结点S插到头结点后面。}return L;}LinkList InitList(void) //构造一个空的线性表{LNode Head;Head = (LNode)malloc(sizeof(struct Node)); //为链表的头结点分配空间if(!Head){printf("Out of space!");return NULL;}Head->next = NULL;return Head;//返回头结点}LNode NewLNode(ElemType X)//构造一个数据域为X的新结点{LNode S;S = (LNode)malloc(sizeof(struct Node));//为新结点分配空间if(!S){printf("Out of space!");return NULL;}S->data = X;S->next = NULL;return S;//返回新结点}//线性表L已存在。 操作结果：在线性表L中寻找值为X的结点，若找到则返回该结点的前驱，否则返回NULL。LNode FindPrefious(ElemType X, LinkList L){LNode P = L;while(P->next && P->next->data != X)//遍历链表寻找值为X的结点P = P->next;if(!P->next) //如果找不到值为X的结点,返回NULLreturn NULL;else //若找到则返回该结点的前驱Preturn P;}//初始条件：线性表L中结点P已找到，新结点S已构造。。 操作结果：在该结点之前插入新结点X。void ListInsert(LNode Pre, LNode S){S->next = Pre->next;Pre->next = S;}

Answer 2

一写这样的程序就找到了上学时的感觉。本程序在VS2008下运行通过，如需ANSI C++编译器下运行，请将Console替换成标准输入输出Cout和Cin，如需ANSI C编译器下运行，请将Console替换成printf和Scanf程序如下：#include "stdlib.h"#include "string.h"using namespace System;#define NULL 0#define TRUE 1#define FALSE 0typedef int BOOL;typedef struct NODE{int data;struct NODE*next;}Node;/***********测试数据*************************/void CreateList(Node *pHeadA,Node *pHeadB) //构造两个链表{Node *p,*q;int i=0;p=pHeadA;for(i=0;i<100;i++){q=new Node;q->data=i;q->next=NULL;p->next=q;p=q;}p=pHeadB;for(i=50;i<150;i++){q=new Node;q->data=i;q->next=NULL;p->next=q;p=q;}}void DisplayList(Node *pList) //遍历链表{Node *p;if(pList->next!=NULL) p=pList->next;while (p!=NULL){Console::Write(p->data);Console::Write(" ");p=p->next;}}/******************************************/BOOL IsExistInList(Node *pList,int nValue) //判断值nValue是否在链表中存在{Node *p;if(pList->next!=NULL) p=pList->next;else{return FALSE;}while (p!=NULL){if(p->data==nValue) return TRUE;p=p->next;}return FALSE;}void Union(Node *pListA,Node *pListB,Node *pListC) //将链表A,B,连接成表C{Node *p,*q;p=pListC;while(pListA!=NULL || pListB!=NULL) //遍历A，B链表的所有有节点，逐一判断在pListC中是否存在，不存在则插入{pListA=pListA->next;pListB=pListB->next;if(pListA!=NULL) //对于链表A{if(!IsExistInList(pListC,pListA->data)) //如果不存在则插入{q=new Node;q->data=pListA->data;q->next=NULL;p->next=q;p=q;}}if(pListB!=NULL) //对于链表B{if(!IsExistInList(pListC,pListB->data)) //如果不存在则插入{q=new Node;q->data=pListB->data;q->next=NULL;p->next=q;p=q;}}}}int Strcompare(char *pStrA,char *pStrB) //字符串比较{char *p1=pStrA,*p2=pStrB;while(*p1!='\0' && *p2!='\0'){if(*p1<*p2) return -1;else if(*p1>*p2) return 1;p1++;p2++;}if (strlen(p1)>strlen(p2)){return 1;}else if(strlen(p1)<strlen(p2)){return -1;}else return 0;}int main(void){Node *pHeadA,*pHeadB; //初始化链表头pHeadA=new Node;pHeadA->data=-999;pHeadA->next=NULL;pHeadB=new Node;pHeadB->data=-999;pHeadB->next=NULL;CreateList(pHeadA,pHeadB); //建立两个测试链表DisplayList(pHeadA); //显示链表Console::WriteLine();DisplayList(pHeadB);Console::WriteLine();Node *pHeadC; //建立目的链表pHeadC=new Node;pHeadC->data=-999;pHeadC->next=NULL;Union(pHeadA,pHeadB,pHeadC); //合并链表DisplayList(pHeadC);int n=Strcompare("wuchunlei","wuchunlei"); //比较两个字符串n=Strcompare("wuchunlei","wuchunleil");n=Strcompare("wuchunleil","wuchunlei");n=Strcompare("wuchunlai","wuchunlei");n=Strcompare("wuchunlei","wuchunlai");n=Strcompare("wuchunlei","auchunlei");Console::Read();return 0;}