typedef int status
#define OVERFLOW -2
#define OK 1
#define ERROR -1
#include "stdio.h"
#include "stdlib.h"
typedef struct LNode {
Elemtype data
struct LNode *next
}*linklist
/档绝/构造链表毁亮
void Create_Linklist(linklist &L)
{
linklist p
p=(linklist)malloc(sizeof(LNode))
if(!p)
exit(OVERFLOW)
L=p
L->next =NULL
}
//节点插入
void Insert_Linklist(linklist &L)
{
linklist p
int n,i
printf("请输入插入节点的个数n: ")
scanf("%d",&n)
getchar()
for(i=ni>0i--)
{
p=(linklist )malloc(sizeof(LNode))
scanf("%d",&p->data)
p->next=L->next
L->next =p
}
}
//遍历输出并输出长度
status Visit_linklist(linklist &L)
{
linklist p
int i=1
p=L->next
if(L->next==NULL)
return ERROR
while(p->next !=NULL)
{
printf("%d ",p->data )
p=p->next
i++
}
printf("%d\n",p->data )
printf("长度为：%d\n",i)
return OK
}
//查找值为x的直接前驱结点q并输出
void Search_linklist(linklist &L)
{
int x,k=0
linklist p=L,q
printf("输入x: ")
scanf("%d",&x)
getchar()
if(L->next ==NULL)
printf("该表为空 ！\n")
while(p->next!=NULL)
{
q=p
if(p->next ->data ==x)
{
printf("%d ",q->data )
k=1
}
p=p->next
}
if(p->next &&p->data ==x)
{
printf("%d ",p->data )
k=1
}
if(k==0)
printf("未找到值为%d的结点\n",&x)
printf("\n")
}
/行余姿/删除节点
status Delete_linklist(linklist &L)
{
linklist p,q
int k=0,x
printf("请输入删除节点的值x: ")
scanf("%d",&x)
getchar()
if(L->next ==NULL)
return ERROR
p=L
q=L->next
while(q!=NULL)
if(q->data ==x)
{
k=1
p=q
p->next =q->next
free(q)
q=p->next
}
else
{
p=q
q=p->next
}
if(k==0)
printf("表中没有值为%d的结点！\n",&x)
return OK
}
//链表逆置
void ListInverse_linkliast(linklist &L)
{
linklist k,p,q
p=L
while (p->next !=NULL)
{
p=p->next
}
k=p
while (L->next !=p)
{
q=L->next
L->next = q->next
k->next =q
}
}
//链表奇偶分解
void Break_linklist (linklist &La,linklist &Lb)
{
linklist p,q
p=La->next
q=Lb
while(p->next!=NULL)
{
if(p->data %2==0)
{
q->next =p
q=q->next
}
p=p->next
}
if(p->data %2==0)
{
q->next =p
q=q->next
}
}
//主菜单
void main()
{
linklist L1,L2
printf(" （1） 建立带头节点的单链表\n")
printf(" （2） 插入节点\n")
printf(" （3） 计算链表长度并输出单链表\n")
printf(" （4） 查找值为x的直接前驱结点并输出其值\n")
printf(" （5） 删除节点值为x的结点\n")
printf(" （6） 逆置单链表结点\n")
printf(" （7） 单链表奇偶分解\n")
int choice
printf(" 请输入选择：")
while(scanf("%d",&choice))
{
getchar()
printf("\n\n")
switch(choice)
{
case 1:
Create_Linklist(L1)
break
case 2:
Insert_Linklist(L1)
break
case 3:
Visit_linklist(L1)
break
case 4:
Search_linklist(L1)
break
case 5:
Delete_linklist(L1)
break
case 6:
ListInverse_linkliast(L1)
break
case 7:
Create_Linklist(L2)
Break_linklist (L1,L2)
break
default:
printf(" 输入有误！")
break
}
}
}
二、单链表枯基的基本运算
建立了一个单链表之后，如果要进行一些如插入、删除等 *** 作该怎么办？所以还须掌握一些单链表的基本算法，来实现这些 *** 作。单链表的基本运算包括：查找、插入和删除。下面我们就一一介绍这三种基本运算的算法，并结合我们建立单链表的例子写出相应的程序。
1、查找
对单链表进行查找的思路为：对单链表的结点依次扫描，检测其数据域是否是我们所要查好的值，若是返回该结点的指针，否则返回NULL。
因为在单链表的链域中包含了后继结点的存储地址，所以当我们实现的时候，只要知道该单链表的头指针，即可依次对每个结点的数据域进行检测。
以下是应用查找算法的一个例州败笑子：
#include
#include
#include /*包含一些字符串处理函数的头文件*/
#define N 10
typedef struct node
{
char name[20]
struct node *link
}stud
stud * creat(int n) /*建立链表的函数*/
{
stud *p,*h,*s
int i
if((h=(stud *)malloc(sizeof(stud)))==NULL)
{
printf("不能分配内存空间!")
exit(0)
}
h->name[0]='\0'
h->link=NULL
p=h
for(i=0i<ni ) {
if((s= (stud *) malloc(sizeof(stud)))==NULL)
{
printf("不能分配内存空间!")
exit(0)
}
p->link=s
printf("请输入第%d个人的姓名册含",i 1)
scanf("%s",s->name)
s->link=NULL
p=s
}
return(h)
}
stud * search(stud *h,char *x) /*查找链表的函数，其中h指针是链表的表头指针，x指针是要查找的人的姓名*/
{
stud *p/*当前指针，指向要与所查找的姓名比较的结点*/
char *y/*保存结点数据域内姓名的指针*/
p=h->link
while(p!=NULL)
{
y=p->name
if(strcmp(y,x)==0) /*把数据域里的姓名与所要查找的姓名比较，若相同则返回0，即条件成立*/
return(p)/*返回与所要查找结点的地址*/
else p=p->link
}
if(p==NULL)
printf("没有查找到该数据!")
}
main()
{
int number
char fullname[20]
stud *head,*searchpoint/*head是表头指针，searchpoint是保存符合条件的结点地址的指针*/
number=N
head=creat(number)
printf("请输入你要查找的人的姓名:")
scanf("%s",fullname)
searchpoint=search(head,fullname)/*调用查找函数，并把结果赋给searchpoint指针*/
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）