数据结构—单链表基本操作C语言实现

#include
#include
#include
int temptag = 0;
typedef int ElemType;
typedef struct LNode //定义单链表结点类型
{
ElemType data;
struct LNode *next;
} LinkList;

void InitList(LinkList *&L) //初始化链表，若要重新输入数据，就应该先初始化链表
{
L=(LinkList *)malloc(sizeof(LinkList)); //创建头结点
L->next=NULL;
printf("初始化链表成功！\n");
}

void DestroyList(LinkList *&L) //销毁链表，也就是释放内存
{
LinkList *p=L,*q=p->next;
while (q!=NULL)
{
free(p);
p=q;
q=p->next;
}
free(p);
}


int ListLength(LinkList *L) //输出链表的长度
{
LinkList *p=L;int i=0;
while (p->next!=NULL)
{
i++;
p=p->next;
}
return(i);
}

void DispList(LinkList *L) //显示链表的数据
{
printf("链表中的数据如下：\n");
LinkList *p=L->next;
while (p!=NULL)
{
printf("%d ",p->data);
p=p->next;
}
printf("\n");
}

int GetElem(LinkList *L,int i,ElemType &e) //获取链表中的任意位置的元素。但是不能越界
{
int j=1;
LinkList *p=L->next;
while (j{
j++;
p=p->next;
}
if (p==NULL)
return 0;
else
{
e=p->data;
return 1;
}
}


int ListInsert(LinkList *&L,int i,ElemType e) //插入新的节点
{
int j=0;
LinkList *p=L,*s;
while (j{
j++;
p=p->next;
}
if (p==NULL) //未找到第i-1个结点
{
printf("未找到第%d个节点！\n", (i-1));
return 0;
}
else //找到第i-1个结点*p
{
s=(LinkList *)malloc(sizeof(LinkList)); //创建新结点*s
s->data=e;
s->next=p->next; //将*s插入到*p之后
p->next=s;
return 1;
}
}

int ListDelete(LinkList *&L,int i) //删除相应位置的节点
{
int j=0;
LinkList *p=L,*q;
while (j{
j++;
p=p->next;
}
if (p==NULL) //未找到第i-1个结点
return 0;
else //找到第i-1个结点*p
{
q=p->next; //q指向要删除的结点
if (q==NULL) return 0;
//e=q->data;
p->next=q->next; //从单链表中删除*q结点
free(q); //释放*q结点
return 1;
}
}

void jiangxu(LinkList *&L) //降序排列链表中的元素
{
int temp1, temp2;
LinkList *q, *temp;
q = L->next;
while(q != NULL)
{
temp = q->next;
while(temp != NULL)
{
temp1 = q->data;
temp2 = temp->data;
if(temp1 < temp2)
{
q->data = temp2;
temp->data = temp1;
}
temp = temp->next;
}
q = q->next;
}
}

void nizhi(LinkList *&L) //将链表中的元素顺序逆置
{
LinkList *New, *p, *q;
p = L->next;
New = (LinkList *)malloc(sizeof(LinkList));
New->next = NULL;
while(p != NULL)
{
LinkList *s=(LinkList *)malloc(sizeof(LinkList));
s

->data = p->data;
p = p->next;
s->next = New->next;
New->next = s;
}
L = New;
}

void MaxAndMin(LinkList *&L) //求最大值和最小值
{
LinkList *temp;
int Max, Min;
temp = L->next;
Max = -100;
Min = 100;

while(temp != NULL)
{
if(temp->data <= Min)
{
Min = temp->data;
}
if(temp->data >= Max)
{
Max = temp->data;
}
temp = temp->next;
}
printf("最大值是：%d\n最小值是：%d\n", Max, Min);
}

void Add(LinkList *&L) //添加一个新的链表，并与之前的链表合并，降序输出
{
LinkList *List2, *p;
InitList(List2);
int data, tag = 1;
printf("请输入第二个链表的数据：\n");
scanf("%d", &data);
while(data != -1)
{
ListInsert(List2, tag, data);
tag++;
scanf("%d", &data);
}
printf("第一个链表：\n");
DispList(L);
printf("第二个链表：\n");
DispList(List2);
p = List2->next;
while(p != NULL)
{
LinkList *s=(LinkList *)malloc(sizeof(LinkList));
s->data = p->data;
p = p->next;
s->next = L->next;
L->next = s;
}
jiangxu(L);
printf("合并后的链表：\n");
DispList(L);
}

int MaxDigui(LinkList *&L) //递归求最大值
{
int MaxValue;
if(!L->next)
return L->data;
else
{
MaxValue=MaxDigui(L->next);
if(L->data > MaxValue)
MaxValue = L->data;
return MaxValue;
}
}

LinkList *CreatLinkList (LinkList *&L) //递归创建链表
{
//建立单链表
int ch;
scanf("%d",&ch);
if(ch==-1)
{
L = NULL;
return L;
}
else
{

L=(LinkList *)malloc(sizeof(LinkList));
L->data=ch;
L->next = NULL;
return CreatLinkList (L->next);
}
}

int IsAscendOrder(LinkList *L) //递归检查链表是否单调递增
{
if(L->next == NULL)
return 1;
else
{
if(L->next->data < L->data)
return 0;
else
return IsAscendOrder(L->next);
}
}

int main()
{
LinkList *h;
ElemType e;
int temp = 1, data;
while(temp != 0)
{
printf("********************************************************************************");
printf(" (1 )输入 1，初始化单链表h\n");
printf(" (2 )输入 2，采用尾插法插入元素, -1表示输入结束\n");
printf(" (3 )输入 3，输出单链表h:\n");
printf(" (4 )输入 4，输出单链表h长度\n");
printf(" (5 )输入 5，然后输入N，查找单链表的第N个元素\n");
printf(" (6 )输入 6，在第M个元素位置上插入元素NUM\n");

printf(" (7 )输入 7，然后输入K，删除链表的第K个元素\n");
printf(" (8 )输入 8，释放单链表\n");
printf(" (9 )输入 9，将链表元素降序排列\n");
printf(" (10)输入10，输出最大值和最小值\n");
printf(" (11)输入11，将该链表逆置\n");
printf(" (12)输入12，创建第二个链表，并合并之前链表，降序输出\n");
printf(" (13)输入13，用递归算法创建链表\n");
printf(" (14)输入14，用递归算法求最大值\n");
printf(" (15)输入15，用递归算法判断链表数据是否单调递增\n");
printf("********************************************************************************");
scanf("%d", &temp);
if(temp == 1)
InitList(h);
else if(temp == 2)
{
int tag = 1;
scanf("%d", &data);
while(data != -1)
{
ListInsert(h, tag, data);
tag++;
scanf("%d", &data);
}
printf("数据插入成功！\n");
}
else if(temp == 3)
DispList(h);
else if(temp == 4)
printf("该单链表的长度 = %d\n",ListLength(h));
else if(temp == 5)
{
int N;
scanf("%d", &N);
if(N<1||N>ListLength(h))
printf("你输入的数据不合法！\n");
else
{
GetElem(h,N,e);
printf("第%d个元素是%d\n", N, e);
}
}
else if(temp == 6)
{
int M, num;
printf("请输入M值和NUM值:\n");
scanf("%d%d", &M, &num);
if(M<=0||M>ListLength(h)+1)
printf("你输入的数据不合法！\n");
else
ListInsert(h, M, num);
}
else if(temp == 7)
{
int K;
scanf("%d", &K);
ListDelete(h,K);
}
else if(temp == 8)
DestroyList(h);
else if(temp == 9)
{
jiangxu(h);
}
else if(temp == 10)
{
MaxAndMin(h);
}
else if(temp == 11)
{
nizhi(h);
}
else if(temp == 12)
{
Add(h);
}
else if(temp == 13)
{
LinkList *temp;
temp = CreatLinkList(h);

LinkList *T;
T = (LinkList *)malloc(sizeof(LinkList));
T->next = h->next;
T->data = h->data;
h->next = T;
}
else if(temp == 14)
{
int res2;
res2 = MaxDigui(h);
printf("最大值是%d\n", res2);
}
else if(temp ==

15)
{
int pand;
pand = IsAscendOrder(h->next);
if(pand == 1)
printf("该链表的数据是单调递增的\n");
else if(pand == 0)
printf("该链表的数据不是单调递增的\n");
}
}
system("pause");
return 0;
}