|
|
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
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<i && p!=NULL)
{
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<i-1 && p!=NULL)
{
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<i-1 && p!=NULL)
{
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 Delete2(LinkList *&L)//刪除表中所有值相同的多余元素（使得操作后的線性表中所有元素的值均不相同），
{
LinkList *p,*q,*s;
p=L;
q=L->next;
while(q->next)
{
if(q->data==q->next->data)
{
p->next=q->next;
s=q;
q=q->next;
free(s);
}
else
{
p=p->next;
q=q->next;
}
}
printf("刪除成功!!!!\n");
}
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);
Delete2(L);
printf("合并后的鏈表：\n");
DispList(L);
}
int main()
{
LinkList *h;
ElemType e;
int temp = 1, data;
while(temp != 0)
{
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");
scanf("%d", &temp);
if(temp == 1)
InitList(h);
else if(temp == 2)
{
printf("請輸入數據:");
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;
printf("請輸入數據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;
printf("請輸入數據k:");
scanf("%d", &K);
if(K<=0||K>ListLength(h))
printf("無效輸入請重新選擇刪除 \n");
else
ListDelete(h,K);
}
else if(temp == 8)
{
printf("降序成功");
jiangxu(h);
}
else if(temp == 9)
{
MaxAndMin(h);
}
else if(temp == 10)
{ printf("逆置成功");
nizhi(h);
}
else if(temp == 11)
{
Add(h);
}
}
system("pause");
return 0;
}
|
|
