#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef char ElemType;
typedef struct Node /*结点类型定义*/
{
ElemType data;
struct Node * next;
}Node, *LinkList; /* LinkList为结构指针类型*/
void InitList(LinkList *L);
void CreateFromHead(LinkList L);
void CreateFromTail(LinkList L);
void InsList(LinkList L, int i, ElemType e);
int DelList(LinkList L, int i, ElemType *e);
Node *GetData(LinkList L, int i);
int Locate(LinkList L, ElemType key);
void Output(LinkList L);
LinkList MergeLinkList(LinkList LA, LinkList LB);
void InitList(LinkList *L)
{
*L = (LinkList)malloc(sizeof(Node));
(*L)->next = NULL;
}
void CreateFromHead(LinkList L)
{
Node *s;
int flag = 1;
char c;
/* 设置一个标志,初值为1,当输入“$"时,flag为0,建表结束*/
while (flag)
{
c = getchar();
if (c != '$') /*为读入的字符分配存储空间*/
{
s = (Node*)malloc(sizeof(Node));
s->data = c;
s->next = L->next; L->next = s;
}
else
flag = 0;
}
}
void CreateFromTail(LinkList L) /*将新增的字符追加到链表的末尾*/
{
Node *r, *s;
int flag = 1;
char c;
r = L; /*r指针始终动态指向链表的当前表尾*/
while (flag)/*标志,初值为1.输入“$"时flag为0,建表结束*/
{
c = getchar();
if (c != '$')
{
s = (Node*)malloc(sizeof(Node));
s->data = c;
r->next = s;
r = s;
}
else
{
flag = 0;
r->next = NULL;
}
}
}
void InsList(LinkList L, int i, ElemType e)
{
Node *pre, *s;
int k = 0;
pre = L;
while (pre != NULL&&k<i - 1)
{
pre = pre->next;
k = k + 1;
}
if (pre==NULL)
{
printf("插入位置不合理!");
return;
}
s = (Node*)malloc(sizeof(Node));
s->data = e;
s->next = pre->next;
pre->next = s;
}
int DelList(LinkList L, int i, ElemType *e)
{
Node *pre, *r;
pre = L;
int k = 0;
while (pre->next != NULL&&k<i - 1)
{
pre = pre->next;
k = k + 1;
}
if (pre->next==NULL)
{
printf("删除结点的位置i不合理!");
return ERROR;
}
r = pre->next;
pre->next = pre->next->next;
*e = r->data;
free(r);
return OK;
}
Node *GetData(LinkList L, int i)
{
int j;
Node *p;
p = L;
j = 0;
while ((p->next != NULL) && (j<i))
{
p = p->next;
j++;
}
if(i == j)
return p;
else
return NULL;
}
int Locate(LinkList L, ElemType key)
/*在带头结点的单链表L中查找其结点值等于key的结点,若找到则返回该结点的位置p,否则返回NULL*/
{
Node *p;
p = L->next; /*从表中第一个结点开始 */
int j = 0;
printf("%c", key);
while (p != NULL)
{
if (p->data != key)
{
p = p->next;
j++;
}
else
{
j++;
break; /*找到结点值=key时退出循环 */
}
}
return j;
}
void Output(LinkList L)
{
Node *p;
p = L->next;
while(p!=NULL)
{
printf("%c", p->data);
p=p->next;
}
printf("\n");
}
LinkList MergeLinkList(LinkList LA, LinkList LB)
{
Node *pa, *pb;
LinkList r,LC;
pa = LA->next;
pb = LB->next;
LC = LA;
LC->next = NULL;
r = LC;
while (pa!= NULL&&pb!= NULL)
{
if (pa->data <= pb->data)
{
r->next = pa;
r = pa;
pa = pa->next;
}
else
{
r->next = pb;
r = pb;
pb = pb->next;
}
}
if (pa!=NULL)
r->next = pa;
else
r->next = pb;
free(LB);
return(LC);
}
int main()
{
LinkList list;
LinkList aList, bList, cList;
list = NULL;
int m,j,o,q;
char n,k,t;
Node *p;
InitList(&list);//链表初始化
/*printf("用头插法建立单链表,请输入链表数据,以$结束!\n");
CreateFromHead(list);*/
printf("用尾插法建立单链表,请输入链表数据,以$结束!\n");
CreateFromTail(list);
printf("创建完毕的单链表元素为:");
Output(list);
printf("请输入要插入的位置:\n");
scanf_s("%d", &m);
printf("请输入要插入的元素值:\n");
fflush(stdin);
scanf_s("%c", &n,1);
InsList(list, m, n);
printf("插入完毕后的元素值为:");
Output(list);
printf("请输入要删除的元素位置:\n");
scanf_s("%d", &j);
DelList(list, j, &k);
printf("删除的元素值为:%c\n", k);
printf("删除完毕后的元素值为:");
Output(list);
printf("请输入要查找的结点序号:\n");
scanf_s("%d", &o);
p = GetData(list, o);
if (p != NULL)
printf("该结点的值为:%c\n", p->data);
else
printf("未找到此结点!\n");
printf("请输入要查找的元素值:\n");
fflush(stdin); //清空输入缓冲区
scanf_s("%c",&t,1);
q = Locate(list,t);
if (q != 0)
printf("该结点所在的位置为:%d\n",q);
else
printf("未找到此结点!\n");
aList = NULL;
InitList(&aList);//链表初始化
printf("创建非递减链表LA:\n");
printf("用尾插法建立单链表,请输入链表数据,以$结束!\n");
CreateFromTail(aList);
bList = NULL;
InitList(&bList);//链表初始化
printf("创建非递减链表LB:\n");
printf("用尾插法建立单链表,请输入链表数据,以$结束!\n");
CreateFromTail(bList);
cList = NULL;
cList=MergeLinkList(aList, bList);
printf("合并完毕后的链表元素值为:");
Output(cList);
//system("pause");
return 0;
}