哦哦哦

uuu水水水水水 · 发表于 2020-11-6 23:41:58

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#define false 0
#define true 1
typedef struct Node
{
int data; //数据域
struct Node * pNext; //指针域
}NODE, *PNODE;
//创建一个链表
PNODE create_list(void)
{
int len; //用来存放有效节点的个数
int i;
int val; //用来临时存放用户输入的结点的值
PNODE pHead = (PNODE)malloc(sizeof(NODE));
if (NULL == pHead)
{
printf("分配失败, 程序终止!");
exit(-1);
}
PNODE pTail = pHead;
pTail->pNext = NULL;
printf("请输入您需要生成的链表节点的个数: len = ");
scanf("%d", &len);
for (i=0; i<len; ++i)
{
printf("请输入第%d个节点的值: ", i+1);
scanf("%d", &val);
PNODE pNew = (PNODE)malloc(sizeof(NODE));
if (NULL == pNew)
{
printf("分配失败, 程序终止!");
exit(-1);
}
pNew->data = val;
pTail->pNext = pNew;
pNew->pNext = NULL;
pTail = pNew;
}
return pHead;
}
//遍历链表
void traverse_list(PNODE pHead)
{
printf("遍历所得链表为：");
PNODE p=pHead->pNext;
while(NULL!=p)
{
printf("%d ",p->data);
p=p->pNext;
}
printf("");
}
//求链表长度
int length_list(PNODE pHead)
{
int len=0;
PNODE p=pHead;
while(p->pNext!=NULL)
{
len++;
p=p->pNext;
}
printf("现在的链表长度为：%d",len);
return len ;
}
//插入一个结点
void insert_list(PNODE pHead)
{
int pos ;
int val;
int i = 0;
printf("请选择在第几个节点插入");
scanf("%d",&pos);
printf("请输入所插入节点的值：");
scanf("%d",&val);
PNODE p = pHead;
while (NULL!=p && i<pos-1)
{
p = p->pNext;
++i;
}
if (i>pos-1 || NULL==p)
return false;
PNODE pNew = (PNODE)malloc(sizeof(NODE));
if (NULL == pNew)
{
printf("动态分配内存失败!");
exit(-1);
}
pNew->data = val;
PNODE q = p->pNext;
p->pNext = pNew;
pNew->pNext = q;
return true;
}
//删除一个结点
Bool delete_list(PNODE pHead, int pos, int * pVal)
{
int i = 0;
PNODE p = pHead;
while (NULL!=p->pNext && i<pos-1)
{
p = p->pNext;
++i;
}
if (i>pos-1 || NULL==p->pNext)
return false;
PNODE q = p->pNext;
*pVal = q->data;
//删除p节点后面的结点
p->pNext = p->pNext->pNext;
free(q);
q = NULL;
return true;
}
//根据指定的位序查找
void Find_elem_byloc (PNODE pHead)
{
int cnt = 1;//位序从1开始
int pos ;
printf("请输入你要按序号查找的数的序号：");
scanf("%d",&pos );
PNODE pnode = pHead->pNext ;
while
(pnode && cnt < pos)
{
pnode = pnode -> pNext;
cnt++;
}
if((cnt==pos)&&pnode)
printf("您查找的数为：%d",pnode->data);
else printf("您查找数不存在");
}
//按值查找
void Find_elem_bypri (PNODE pHead)
{
int i ;
printf("请输入您要查找的值");
scanf("%d" , &i );
PNODE pnode = pHead->pNext;
while(pnode && pnode ->data!=i ){
pnode = pnode -> pNext;
}
if(pnode)
printf("查找成功，您查找的数为：%d",pnode->data);
else
printf("您查找数不存在");
}
//链表冒泡排序
PNODE ListSort(PNODE pHead)
{
PNODE p,q,tail ,h;
tail = NULL;
h = pHead;
while(h->pNext!=tail)
{
p =pHead;
q = p->pNext;
while(q->pNext!=tail)
{
if(p->pNext->data > q->pNext->data)
{
p->pNext = q->pNext;
q->pNext = q->pNext->pNext;
p->pNext->pNext = q;
p = p->pNext;
}
else
{
p = p->pNext;
q = q->pNext;
}
}
tail = q; //前移一位
}
return pHead;
}
//创建另一个链表
PNODE create_list_sec(void)
{
int len; //用来存放有效节点的个数
int i;
int val; //用来临时存放用户输入的结点的值
PNODE pHeadt = (PNODE)malloc(sizeof(NODE));
if (NULL == pHeadt)
{
printf("分配失败, 程序终止!");
exit(-1);
}
PNODE pTail = pHeadt;
pTail->pNext = NULL;
printf("请输入您需要生成的链表节点的个数: len = ");
scanf("%d", &len);
for (i=0; i<len; ++i)
{
printf("请输入第%d个节点的值: ", i+1);
scanf("%d", &val);
PNODE pNew = (PNODE)malloc(sizeof(NODE));
if (NULL == pNew)
{
printf("分配失败, 程序终止!");
exit(-1);
}
pNew->data = val;
pTail->pNext = pNew;
pNew->pNext = NULL;
pTail = pNew;
}
return pHeadt;
}
//合并两个链表
PNODE Merge_LinkList(PNODE pHead , PNODE pHeadt,PNODE pHeadm)
{
PNODE Lc,La,Lb,pa,pb,pc,ptr;
La = pHead;
Lb = pHeadt;
Lc = pHeadm;
pa=La->pNext ;
pb=Lb->pNext ;
while (pa&&pb)
{
if (pa->data<=pb->data) {
pc->pNext=pa ; pc=pa ; pa=pa->pNext ;
}
else {pc->pNext = pb; pc = pb; pb = pb->pNext;}
}
pc->pNext=pa ? pa :pb ;
free(Lb) ;
return(Lc) ;
}
void ShowMenu()//显示菜单
{
int i;
int WIDESIZE = 65;
printf("");
printf("------------------------");
printf(" 欢迎使用线性表的链式表示和实现 ");
printf("------------------------");
printf(" ");
for(i=0;i<WIDESIZE;i++)
{
printf("*");
}
printf("");
printf(" * 1.系统帮助及说明 **");
printf(" 2.创建一个链表 *");
printf(" * 3.求链表的长度 ");
printf("** 4.插入一个结点 *");
printf(" * 5.删除一个结点 **");
printf(" 6.按成位序找结点信息 *");
printf(" * 7.按值查找结点信息 **");
printf(" 8.排序第一个链表 *");
printf(" * 9.创造第二个链表 **");
printf(" 10.排序第二个链表 *");
printf(" * 11.遍历第一个链表 **");
printf(" 12.退出该系统 *");
printf(" * 13.合并两个链表 **");
for(i=0;i<4;i++)
{
printf(" ");
}
printf(" ");
for(i=0;i<WIDESIZE;i++)
{
printf("*");
}
printf("");
printf("--------------------------------");
printf(" 2019级电科一班王岸基作品 ");
printf("----------------------------------");
printf("请按所需输入菜单编号:");
}
void ShowHelp()//显示帮助信息
{
printf("1、此系统可以实现线性表的链式表示和实现");
printf("2、输入对应功能项的编号即可进行不同功能的操作。");
}
int main(void)
{
PNODE pHead = NULL;
PNODE pHeadt = NULL ;
PNODE pHeadm = NULL ;
int pos ;
int val ;
int len ;
int flag = -1;
int choice;
while(flag!=12)
{
ShowMenu();
scanf("%d",&choice);
switch (choice)
{
case 1:
ShowHelp();break;
case 2:
pHead = create_list();
printf("创造的链表");
traverse_list(pHead);break;
case 3:
len=length_list(pHead);break;
case 4:
insert_list(pHead);
printf("插入后");
traverse_list(pHead);;break;
case 5:
printf("请选择在第几个节点删除");
scanf("%d",&pos);
if(delete_list(pHead,pos,&val))
{
printf("删除成功，您所删除的元素是：%d",val);
}
else
{
printf("删除失败！您所删除的元素不存在！");
}
printf("删除后");
traverse_list(pHead);break;
case 6:
Find_elem_byloc(pHead); break;
case 7:
Find_elem_bypri(pHead);break;
case 8:
pHead = ListSort(pHead);
printf("排序后");
traverse_list(pHead);break;
case 9:
pHeadt = create_list_sec();
printf("创造的另一个链表");
traverse_list(pHeadt);break;
case 10:
pHeadt = ListSort(pHeadt);
printf("排序后第二个链表");
traverse_list(pHeadt);break;
case 11:
traverse_list(pHead);break;
case 13:
traverse_list(Merge_LinkList(pHead,pHeadt,pHeadm ));
case 12:
flag = 12;break;
}
}
return 0;
}

复制代码