实现单链表的基本操作，必须包括初始化链表(元素为空)、销毁链表、求表长、查找、...

Saber丶Lance

#include<stdio.h>
#include<stdlib.h>
#include<string.h>


/************************类型定义************************/ 
typedef char datatype;

void printElem(datatype x)
{
        printf("%c",x);
}

typedef struct node
{
        datatype data;
        struct node *next;
}LNode,*LinkList;

/**********************单链表的基本操作*********************/ 
//创建空的单链表 （需说明是否带头结点） 
LinkList Create_Linklist()
{
        LinkList H=(LNode *)malloc(sizeof(LNode));
        if(H)
                H->next=NULL;
        return H;
}

//销毁单链表 
void Destroy_Linklist(LinkList *H)
{ 
        LinkList q,p;
        p = *H;
        while(p)
        {
                q=p;
                p=p->next;
                free(q);
        }
        *H=NULL;
} 

//求表长 
int Length_LinkList(LinkList H)
{
        LinkList j;
        int i=0;
        j=H->next;
        while(j)
        {
                i += 1;
                j=j->next;
        }
        return i;
}

//按序号查找
LinkList Get_LinkList(LinkList H,int i)
{
        LinkList p;
        p=H->next;
        int ret=Length_LinkList(H);
        if(i<=ret)
                for(int j=1;j<=ret;j++)
                {
                        if(j==i)
                                return p;
                        else
                                p=p->next;
                }
        else
                return NULL;
} 

//按值查找
 LinkList Get_LinkList(LinkList H,datatype x)
{
        LinkList p;
        p=H->next;
        int ret=Length_LinkList(H);
        for(int i=0;i<ret;i++)
        {
                if(p->data==x)
                        return p;
                else
                        p=p->next;
        }
} 

//插入
int Insert_LinkList(LinkList H,int i,datatype x)
{
        LNode *p;
        p = Get_LinkList(H,i-1);
        if(p==NULL)
        {
                printf("插入的位置错误!");
                return 0; 
        } 
        else
        {
                LNode *s=(LNode *)malloc(sizeof(LNode));
                s->data=x;
                s->next=p->next;
                p->next=s;
                return 1;
        }
} 

//删除(按序号)
int Delete_LinkList(LinkList H,int i)
{
        LNode *p,*s;
        p = Get_LinkList(H,i-1);
        if(p==NULL)
        {
                printf("第i-1个结点不存在！");
                return -1;
        }
        else if(p->next=NULL)
        {
                printf("第i个结点不存在！");
                return 0;
        }
        else
        {
                s=p->next;
                p->next=s->next;
                free(s);
                return 1;
        }
        
} 

//删除(按值)
int Delete_LinkList(LinkList H,datatype x)
{
        LNode *p,*s;
        p = Get_LinkList(H,x);
        int ret=Length_LinkList(H);
        s=H;
        for(int i=1;i<=ret;i++)
        {
                if(s->next==p)
                        s->next=p->next;
                else
                        s=s->next;
        }
        free(p);
        return 1;
} 

/*******************程序的功能函数**************************/ 
//打印单链表(带头结点)
void Print(LinkList H)
{
        printf("head:");
    LinkList p=H->next;
        while(p)
        {
                printf("-->");
                printElem(p->data);
                p = p->next;        
        }
        printf("\n");
}

//查找(按值或按序号查找，用户可选择任意一种方式)
void Search(LinkList H)
{
        int choice,x,i;
        LNode *p,*s;        
        printf("请选择按值查找or按序号查找(1 or 2)：");
        scanf("%d",&choice);
        if(choice==1)
        {
                printf("请输入将要查找的值:");
                scanf("%d",&x);
                p=Get_LinkList(H,x);
                s=H->next;
                int ret=Length_LinkList(H);
                for(int i=1;i<=ret;i++)
                {
                        if(s==p)
                                printf("该值位于第i个位置");
                        else
                                s=s->next;                                 
                }        
        }
        else if(choice==2)
        {
                printf("请输入序号：");
                scanf("%d",&i);
                p=Get_LinkList(H,i);
                printf("值为：%d",p->data);
        }
        else
                printf("输入错误！");
}

//插入 
void Insert(LinkList H)
{
        int x,i,p;
        printf("请输入将要插入的值及其位置：");
        scanf("%d %d",&x,&i);
        p=Insert_LinkList(H,i,x);
        if(p)
                printf("插入成功!");
        else
                printf("插入失败!");        
}

//删除 (按值或按序号删除，用户可选择任意一种方式)
void Delete(LinkList H)
{
        int choice,x,i,p;
        printf("请选择按值删除or按序号删除(1 or 2)：");
        scanf("%d",&choice);
        if(choice==1)
        {
                printf("请输入将要删除的值：");
                scanf("%d",&x);
                p=Delete_LinkList(H,x);
                if(p)
                        printf("删除成功!"); 
        }
        else if(choice==2)
        {
                printf("请输入将要删除的序号：");
                scanf("%d",&i);
                p=Delete_LinkList(H,i);
                if(p)
                        printf("删除成功!");
        }
        else
                printf("输入有误！");
                
}

/*******************main函数**************************/
void printChoice()
{
        printf("\n请选择功能：\n");
        printf("\t1.打印\n");
        printf("\t2.查找\n");   
        printf("\t3.插入\n");
        printf("\t4.删除\n");  
        printf("\t5.退出程序\n");
        printf("请选择:");
}

int main()
{
        LinkList H=Create_Linklist();
        if(!H)
        {
                printf("空间分配失败！");
                return 0;
        }
        int choice=-1;
        while(1)
        {
                printChoice();
                scanf("%d",&choice);
                
                switch(choice)
                {
                        case 1:
                                Print(H);
                                break;
                        case 2:
                                Search(H);
                                break;
                        case 3:
                                Insert(H);
                                break;
                        case 4:
                                Delete(H);
                                break;
                        default:
                                printf("程序结束!\n");
                                break;
                }
                if(choice==5)
                        break;
        }
}

运行时可以正常插入数据，但其它功能均有异常。。。

Saber丶Lance

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

/************************类型定义************************/ 
typedef char datatype;

void printElem(datatype x)
{
        printf("%c",x);
}

typedef struct node
{
        datatype data;
        struct node *next;
}LNode,*LinkList;

/**********************单链表的基本操作*********************/ 
//创建空的单链表 （需说明是否带头结点） 
LinkList Create_Linklist()
{
        LinkList H=(LNode *)malloc(sizeof(LNode));
        if(H)
                H->next=NULL;
        return H;
}

//销毁单链表 
void Destroy_Linklist(LinkList *H)
{ 
        LinkList q,p;
        p = *H;
        while(p)
        {
                q=p;
                p=p->next;
                free(q);
        }
        *H=NULL;
} 

//求表长 
int Length_LinkList(LinkList H)
{
        LinkList j;
        int i=0;
        j=H->next;
        while(j)
        {
                i += 1;
                j=j->next;
        }
        return i;
}

//按序号查找
LinkList Get_LinkList(LinkList H,int i)
{
        LinkList p;
        p=H->next;
        int ret=Length_LinkList(H);
        if(i<=ret)
                for(int j=1;j<=ret;j++)
                {
                        if(j==i)
                                return p;
                        else
                                p=p->next;
                }
        else
                return NULL;
} 

//按值查找
 LinkList Get_LinkList(LinkList H,datatype x)
{
        LinkList p;
        p=H->next;
        int ret=Length_LinkList(H);
        for(int i=0;i<ret;i++)
        {
                if(p->data==x)
                        return p;
                else
                        p=p->next;
        }
} 

//插入
int Insert_LinkList(LinkList H,int i,datatype x)
{
        LNode *p;
        if(i==1)
        {
                LNode *s=(LNode *)malloc(sizeof(LNode));
                s->data=x;
                H->next=s;
                s->next=NULL;
        }
        else
        {
                p = Get_LinkList(H,i-1);
                if(p==NULL)
                        {
                                printf("插入的位置错误!");
                                return 0; 
                        } 
                else
                {
                        LNode *s=(LNode *)malloc(sizeof(LNode));
                        s->data=x;
                        s->next=p->next;
                        p->next=s;
                        return 1;
                }
        }
} 

//删除(按序号)
int Delete_LinkList(LinkList H,int i)
{
        LNode *p,*s;
        p = Get_LinkList(H,i-1);
        if(p==NULL)
        {
                printf("第%d个结点不存在！",i-1);
                return -1;
        }
        else if(p->next=NULL)
        {
                printf("第%d个结点不存在！",i);
                return 0;
        }
        else
        {
                s=p->next;
                p->next=s->next;
                free(s);
                return 1;
        }
        
} 

//删除(按值)
int Delete_LinkList(LinkList H,datatype x)
{
        LNode *p,*s;
        p = Get_LinkList(H,x);
        int ret=Length_LinkList(H);
        s=H;
        for(int i=1;i<=ret;i++)
        {
                if(s->next==p)
                        s->next=p->next;
                else
                        s=s->next;
        }
        free(p);
        return 1;
} 

/*******************程序的功能函数**************************/ 
//打印单链表(带头结点)
void Print(LinkList H)
{
        printf("head:");
    LinkList p=H->next;
        while(p)
        {
                printf("-->");
                printElem(p->data);
                p = p->next;        
        }
        printf("\n");
}

//查找(按值或按序号查找，用户可选择任意一种方式)
void Search(LinkList H)
{
        int choice,i;
        char x;
        LNode *p,*s;        
        printf("请选择按值查找or按序号查找(1 or 2)：");
        scanf("%d",&choice);
        if(choice==1)
        {
                printf("请输入将要查找的值:");
                scanf("%s",&x);
                p=Get_LinkList(H,x);
                s=H->next;
                int ret=Length_LinkList(H);
                for(int i=1;i<=ret;i++)
                {
                        if(s==p)
                                printf("该值位于第%d个位置\n",i);
                        else
                                s=s->next;                                 
                }        
        }
        else if(choice==2)
        {
                printf("请输入序号：");
                scanf("%d",&i);
                p=Get_LinkList(H,i);
                printf("值为：%d",p->data);
        }
        else
                printf("输入错误！");
}

//插入 
void Insert(LinkList H)
{
        int i,p;
        char x;
        printf("请输入将要插入的值及其位置：");
        scanf("%s %d",&x,&i);
        p=Insert_LinkList(H,i,x);
        if(p)
                printf("插入成功!");
        else
                printf("插入失败!");        
}

//删除 (按值或按序号删除，用户可选择任意一种方式)
void Delete(LinkList H)
{
        int choice,i,p;
        char x;
        printf("请选择按值删除or按序号删除(1 or 2)：");
        scanf("%d",&choice);
        if(choice==1)
        {
                printf("请输入将要删除的值：");
                scanf("%s",&x);
                p=Delete_LinkList(H,x);
                if(p)
                        printf("删除成功!"); 
        }
        else if(choice==2)
        {
                printf("请输入将要删除的序号：");
                scanf("%d",&i);
                p=Delete_LinkList(H,i);
                if(p)
                        printf("删除成功!");
        }
        else
                printf("输入有误！");
                
}

/*******************main函数**************************/
void printChoice()
{
        printf("\n请选择功能：\n");
        printf("\t1.打印\n");
        printf("\t2.查找\n");   
        printf("\t3.插入\n");
        printf("\t4.删除\n");  
        printf("\t5.退出程序\n");
        printf("请选择:");
}

int main()
{
        LinkList H=Create_Linklist();
        if(!H)
        {
                printf("空间分配失败！");
                return 0;
        }
        int choice=-1;
        while(1)
        {
                printChoice();
                scanf("%d",&choice);
                
                switch(choice)
                {
                        case 1:
                                Print(H);
                                break;
                        case 2:
                                Search(H);
                                break;
                        case 3:
                                Insert(H);
                                break;
                        case 4:
                                Delete(H);
                                break;
                        default:
                                printf("程序结束!\n");
                                break;
                }
                if(choice==5)
                        break;
        }
}

程序改为这个后，可以插入，按值查找正常，但按序号查找和按序号删除均不正常

K鱼C

//我是这么写的：
#include <stdio.h>
#include<stdlib.h>
#define MaxLen 20

///定义单链表
typedef struct LinkNode
{
        int data;                                //数据域
        struct LinkNode *next;  //指针域
}LinkList;

void ShowLinkList(LinkList *head); //声明打印函数

///单链表初始化(生成头结点动态分配存储空间,返回头结点)
LinkList * InitList()
{
        LinkList * head;
        head = (LinkList *)malloc(sizeof(LinkList));
        head -> next = NULL;
        return head;
}

///头插法建表
LinkList * CreateListH(LinkList *head)
{
        int n;
    int i;
        LinkList * l;
        printf("请输入该链表需要存入多少个数字：");
        scanf("%d", &n);

        printf("请输入要存入该链表的数字（以空格隔开）：");
        for(i = 0;i < n;i++)
        {
                l = (LinkList *)malloc(sizeof(LinkList));
                scanf("%d", &l -> data);
                l -> next = head -> next;               
                head -> next = l;
        }
        ShowLinkList(head);                //打印一下
       
        return head;
}

///尾插法建表
LinkList * CreateListL(LinkList *head)
{
        int n;
    int i;
        LinkList *l, *p;
        printf("请输入该链表需要存入多少个数字：");
        scanf("%d", &n);

        p = head;
        printf("请输入要存入该链表的%d数字（以空格隔开）：", n);
        for(i = 0;i < n;i++)
        {
                l = (LinkList *)malloc(sizeof(LinkList));
                scanf("%d", &l -> data);
                l -> next = NULL;

                while(p -> next != NULL)
                {
                        p = p -> next;
                }
                p -> next = l;
        }
        ShowLinkList(head);//打印一下
        return head;
}

///1.求表长
int GetLengthList(LinkList *head)
{
        int count = 0;
        LinkList *p = head -> next;
        while(p)
        {
                p = p-> next;
                count++;
        }
        return count;
}

///2.按值查找
void Locate(LinkList *head)
{
        int i = 1,x;
        printf("请输入需要查找的数值：");
        scanf("%d", &x);

        LinkList *p = head -> next;
        while(p && p -> data != x)
        {
                p = p -> next;
                i++;
        }
        if(p)
        {
                printf("已找到，在第%d个\n", i);
        }
        else
        {
                printf("未找到！\n");
        }
}

///3.插入节点
void InsList(LinkList *head)
{
        int i, j;
        LinkList *p = head,*q;
       

        printf("请输入需要在第几个位置（头结点算是第0个）插入： ");
        scanf("%d", &i);

        if(i <= 0 || i > GetLengthList(head))
        {
                printf("插入失败，插入位置错误！\n");
        }
        else
        {
                j = 1;
                while(p && j < i)
                {
                        p = p-> next;
                        j++;
                }
                        q = (LinkList *)malloc(sizeof(LinkList));

                        printf("请输入需要插入的数： ");
                        scanf("%d", &q -> data);

                        q -> next = p -> next;
                        p -> next = q;

                        printf("插入成功！");
                        ShowLinkList(head);                //打印一下
        }
}


///4.删除结点
void DelNode(LinkList *head)
{
        int i, j;
        LinkList *p = head,*q;
       

        printf("请输入需要在第几个位置（头结点算是第0个）删除： ");
        scanf("%d", &i);

        if(i <= 0 || i > GetLengthList(head))
        {
                printf("删除失败，删除位置错误！\n\n\n");
        }
        else
        {
                j = 0;
                while(p && j < i - 1)
                {
                        p = p-> next;
                        j++;
                }

                if(p)
                {
                        q = p -> next;
                        j = q -> data;
                        p -> next = q -> next;

                        printf("删除第%d个数%d成功！", i, j);
                        ShowLinkList(head);                //打印一下
                }
                else
                {
                        printf("删除失败，删除位置错误！\n\n\n");
                }
        }
}

///打印链表
void ShowLinkList(LinkList *head)
{
        LinkList *p = head -> next;
        printf("当前链表为： ");
        while(p)
        {
                printf("%d ",p -> data);
                p = p-> next;
        }
        printf("\t长度为%d个。\n\n\n", GetLengthList(head));
}

///主函数
int main()
{
        LinkList *head = CreateListL(InitList());
        int a = 0;

        printf("-----------------------------------单链表操作---------------------------------\n\n");

        for(int j = 0;j < MaxLen;j++)
        {
                printf("请输入您要进行操作的序号:1.求表长\n\t\t\t 2.按值查找\n\t\t\t 3.插入结点\n\t\t\t 4.删除结点\n\n ");
                scanf("%d",&a);
                switch(a)
                {
                        case 1:printf("当前链表的长度为：%d \n\n\n" ,GetLengthList(head));break;
                        case 2:Locate(head);break;
                        case 3:InsList(head);break;
                        case 4:DelNode(head);break;                       
                        default :printf("\n操作失败！无此操作序号。\n\n");
                }
        }
               
        free(head);

        getchar();
        return 0;
}

Saber丶Lance

K鱼C 发表于 2018-3-25 21:09
//我是这么写的：
#include
#include

这个按值查找我基本都实现了，还有就是插入数据时可以在任何逻辑正确的位置插入，就是这个按序号查找我的程序会出现其他结果。。。

K鱼C

链表貌似不包含这个功能

810778176@qq.co

你这是带还是不带头结点